Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-24T20:12:24.722Z Has data issue: false hasContentIssue false
  • English
  • Français

Index policies for discounted bandit problems with availability constraints

Part of: Stochastic systems and control Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Savas Dayanik ,
Warren Powell  and
Kazutoshi Yamazaki
Savas Dayanik*
Affiliation:
Princeton University
Warren Powell*
Affiliation:
Princeton University
Kazutoshi Yamazaki*
Affiliation:
Princeton University
*
∗ Postal address: Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ 08544, USA.
∗ Postal address: Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ 08544, USA.
∗ Postal address: Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ 08544, USA.
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.

A multiarmed bandit problem is studied when the arms are not always available. The arms are first assumed to be intermittently available with some state/action-dependent probabilities. It is proven that no index policy can attain the maximum expected total discounted reward in every instance of that problem. The Whittle index policy is derived, and its properties are studied. Then it is assumed that the arms may break down, but repair is an option at some cost, and the new Whittle index policy is derived. Both problems are indexable. The proposed index policies cannot be dominated by any other index policy over all multiarmed bandit problems considered here. Whittle indices are evaluated for Bernoulli arms with unknown success probabilities.

Keywords

Optimal resource allocationmultiarmed bandit problemGittins indexWhittle indexrestart-in problem

MSC classification

Primary: 93E20: Optimal stochastic control
Secondary: 90B36: Scheduling theory, stochastic
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 40 , Issue 2 , June 2008 , pp. 377 - 400
Copyright
Copyright © Applied Probability Trust 2008 

References

Banks, J. S. and Sundaram, R. K. (1992). Denumerable-armed bandits. Econometrica 60, 1071–1096.CrossRefGoogle Scholar
Banks, J. S. and Sundaram, R. K. (1994). Switching costs and the Gittins index. Econometrica 62, 687–694.Google Scholar
Bergemann, D. and Valimaki, J. (2006). Efficient dynamic auctions. Cowles Foundation Discussion Paper 1584, Yale University.CrossRefGoogle Scholar
Brezzi, M. and Lai, T. L. (2000). Incomplete learning endogenous data in dynamic allocation. Econometrica 68, 1511–1516.Google Scholar
Dayanik, S., Powell, W. and Yamazaki, K. (2007). Index policies for discounted bandit problems with availability constraints. Tech. Rep., Department of Tech. Rep. Google Scholar
Gittins, J. C. (1979). Bandit processes and dynamic allocation indices. J. R. Statist. Soc. B 41, 148–177.Google Scholar
Glazebrook, K. D. (1984). Scheduling stochastic Jobs on a single machine subject to breakdowns. Naval Res. Logistics Quart. 31, 251–264.CrossRefGoogle Scholar
Glazebrook, K. D. (1987). Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Res. Logistics 34, 319–335.Google Scholar
Glazebrook, K. D. and Mitchell, H. M. (2002). An index policy for a stochastic scheduling model with improving/deteriorating Jobs. Naval Res. Logistics 49, 706–721.Google Scholar
Glazebrook, K. D., Niño-Mora, J. and Ansell, P. S. (2002). Index policies for a class of discounted restless bandits. Adv. Appl. Prob. 34, 754–774.Google Scholar
Glazebrook, K. D., Ruiz-Hernandez, D. and Kirkbride, C. (2006). Some indexable families of restless bandit problems. Adv. Appl. Prob. 38, 643–672.Google Scholar
Glazebrook, K. D., Ansell, P. S., Dunn, R. T. and Lumley, R. R. (2004). On the optimal allocation of service to impatient tasks. J. Appl. Prob. 41, 51–72.CrossRefGoogle Scholar
Jovanovic, B. (1979). Job matching and the theory of turnover. J. Political Econom. 87, 972–990.Google Scholar
Jun, T. (2004). A survey on the bandit problem with switching costs. De Economist 1524, 513–541.CrossRefGoogle Scholar
Katehakis, M. N. and Derman, C. (1986). Computing optimal sequential allocation rules in clinical trials. In Adaptive Statistical Procedures and Related Topics (Upton, NY, 1985; IMS Lecture Notes Monogr. Ser. 8), Institute of Mathematical Statistics, Hayward, CA, pp. 29–39.Google Scholar
Katehakis, M. N. and Veinott, A. F. Jr. (1987). The multi-armed bandit problem: decomposition and computation. Math. Operat. Res. 12, 262–268.CrossRefGoogle Scholar
Miller, R. A. (1984). Job matching and occupational choice. J. Political Econom. 926, 1086–1120.CrossRefGoogle Scholar
Niño-Mora, J. (2001). Restless bandits, partial conservation laws and indexability. Adv. Appl. Prob. 33, 76–98.Google Scholar
Papadimitriou, C. H. and Tsitsiklis, J. N. (1999). The complexity of optimal queuing network control. Math. Operat. Res. 24, 293–305.CrossRefGoogle Scholar
Ross, S. (1983). Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
Rothschild, M. (1974). A two-armed bandit theory of market pricing. J. Econom. Theory 9, 185–202.Google Scholar
Tsitsiklis, J. N. (1994). A short proof of the Gittins index theorem. Ann. Appl. Prob. 4, 194–199.Google Scholar
Weber, R. R. and Weiss, G. (1990). On an index policy for restless bandits. J. Appl. Prob. 27, 637–648.Google Scholar
Weber, R. R. and Weiss, G. (1991). Addendum to: ‘On an index policy for restless bandits’. Adv. Appl. Prob. 23, 429–430.Google Scholar
Whittle, P. (1980). Multi-armed bandits and the Gittins index. J. R. Statist. Soc. B 42, 143–149.Google Scholar
Whittle, P. (1988). Restless bandits: activity allocation in a changing world. In A Celebration of Applied Probability (J. Appl. Prob. Spec. Vol. 25A), Applied Probability Trust, Sheffield, pp. 287–298.Google Scholar