Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-14T17:52:07.435Z Has data issue: false hasContentIssue false
  • English
  • Français

Tax problems in the undiscounted case

Part of:Computer system organizationStochastic processesOperations research and management science

Published online by Cambridge University Press:  14 July 2016

P. Whittle
P. Whittle*
Affiliation:
University of Cambridge
*
∗ Postal address: Statistical Laboratory, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK. Email address: whittle@statslab.cam.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The aim of this paper is to evaluate the performance of the optimal policy (the Gittins index policy) for open tax problems of the type considered by Klimov in the undiscounted limit. In this limit, the state-dependent part of the cost is linear in the state occupation numbers for the multi-armed bandit, but is quadratic for the tax problem. The discussion of the passage to the limit for the tax problem is believed to be largely new; the principal novelty is our evaluation of the matrix of the quadratic form. These results are confirmed by a dynamic programming analysis, which also suggests how the optimal policy should be modified when resources can be freely deployed only within workstations, rather than system-wide.

Keywords

Tax problemmulti-armed bandittime sharingundiscounted limitdynamic programming

MSC classification

Primary:60G40: Stopping times; optimal stopping problems; gambling theory
Secondary:90B36: Scheduling theory, stochastic68M20: Performance evaluation; queueing; scheduling

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 42 , Issue 3 , September 2005, pp. 754 - 765
Copyright
© Applied Probability Trust 2005 

References

Ansell, P. S., Glazebrook, K. D. and Kirkbride, C. (2003). Generalised ‘join the shortest queue’ policies for the dynamic routing of Jobs to multi-class queues. J. Operat. Res. Soc. 54, 379–389.Google Scholar
Gittins, J. C. (1979). Bandit processes and dynamic allocation indices. J. R. Statist. Soc. B 41, 148–177.Google Scholar
Gittins, J. C. (1989). Multi-Armed Bandit Allocation Indices. John Wiley, Chichester.Google Scholar
Klimov, G. P. (1974). Time-sharing service systems. I. Theory Prob. Appl. 19, 532–551.Google Scholar
Klimov, G. P. (1978). Time-sharing service systems. II. Theory Prob. Appl. 23, 314–321.Google Scholar
Lai, T. L. and Ying, Z. (1988). Open bandit processes and optimal scheduling of neural networks. Adv. Appl. Prob. 20, 447–472.CrossRefGoogle Scholar
Varaiya, P., Walrand, J. C. and Buyukkoc, C. (1985). Extensions of the multi-armed bandit problem: the discounted case. IEEE Trans. Automatic Control 30, 426–439.Google Scholar
Whittle, P. (1980). Multi-armed bandits and the Gittins index. J. R. Statist. Soc. B 42, 143–149.Google Scholar
Whittle, P. (1981). Arm-acquiring bandits. Ann. Prob. 9, 284–292.Google Scholar