A Short Proof of the Gittins Index Theorem
Open accessAbstract
We provide a short and elementary proof of the Gittins index theorem for the multi-armed bandit problem, for the case where each bandit is modeled as a finite-state semi-Markov process. We also indicate how this proof can be extended to the branching bandits and Klimov problems.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Exploration should be minimized to perform optimally in this task because stationary distributions were used and it is a 2-armed bandit task.
“Although it could be argued that participants should explore in this task and therefore that referencing choices to an ideal observer is not optimal, exploration should be minimized to perform optimally, as we used stationary distributions and therefore this is a 2-armed bandit task (Tsitsiklis, 1994).”
From Oxytocin decreases aversion to angry faces in an associative learning task (2010) · cites this paper as Tsitsiklis, 1994
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 4
- [2][2] GITTINs, J. C. (1989). Multi-Armed Bandit Allocation Indices. Wiley, New York. -
- [3][3] GITTINS, J. C. and JoNEs, D. M. (1974). A dynamic allocation index for the design of experiments. In Progress in Statistics (J. Gani, K. Sarkadi and I. Vince, eds.) Colloq. Math. Soc. János Bolyai 9. North-Holland, Amsterdam. -
- [7][7] TsITsIKLIs, J. N. (1986). A lemma on the multi-armed bandit problem. IEEE Trans. Automat. Control 31 576–577. -
- [9][9] VARAIYA, P., WALRAND, J. and BUYUKKOC, C. (1985). Extensions of the multi-armed bandit problem: The discounted case. IEEE Trans. Automat. Control AC-30 426-439. -
Cited by
Sorted by citations
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401 · Cited by 994 · see citing works
Hauser, J. R., Urban, G. L., Liberali, G., & Braun, M. I. (2009) · Marketing Science · doi:10.1287/mksc.1080.0459 · Cited by 291 · see citing works
Bayesian Reinforcement Learning: A Survey
Ghavamzadeh, M., Mannor, S., Pineau, J., & Tamar, A. (2015) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000049 · Cited by 289 · see citing works
Adapting to a Changing Environment: the Brownian Restless Bandits.
Slivkins, A., & Upfal, E. (2008) · Cited by 136 · see citing works
Four proofs of Gittins’ multiarmed bandit theorem
Frostig, E., & Weiss, G. (2014) · Annals of Operations Research · doi:10.1007/s10479-013-1523-0 · Cited by 121 · see citing works
Approximation algorithms for restless bandit problems
Guha, S., Munagala, K., & Shi, P. (2010) · Journal of the ACM · doi:10.1145/1870103.1870106 · Cited by 113 · see citing works
Oxytocin decreases aversion to angry faces in an associative learning task
Evans, S., Shergill, S. S., & Averbeck, B. B. (2010) · Neuropsychopharmacology · doi:10.1038/npp.2010.110 · Cited by 97 · see citing works
A Structured Multiarmed Bandit Problem and the Greedy Policy
Mersereau, A. J., Rusmevichientong, P., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031725 · Cited by 93 · see citing works
Self-citationA generalized Gittins index for a Markov chain and its recursive calculation
Sonin, I. M. (2008) · Statistics & Probability Letters · doi:10.1016/j.spl.2008.01.049 · Cited by 96 · see citing works
Approximation algorithms for budgeted learning problems
Guha, S., & Munagala, K. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250807 · Cited by 86 · see citing works
Risk-Sensitive and Risk-Neutral Multiarmed Bandits
Denardo, E. V., Park, H., & Rothblum, U. G. (2007) · Mathematics of Operations Research · doi:10.1287/moor.1060.0240 · Cited by 78 · see citing works
On Playing Golf with Two Balls
Dumitriu, I., Tetali, P., & Winkler, P. M. (2003) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480102408341 · Cited by 65 · see citing works
Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed BanditsPreprint
Lattimore, T. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.06014 · Cited by 65 · see citing works
Website Morphing 2.0: Switching Costs, Partial Exposure, Random Exit, and When to Morph
Hauser, J., Liberali, G., & Urban, G. L. (2014) · Management Sciences · doi:10.1287/mnsc.2014.1961 · Cited by 72 · see citing works
Bayesian Dynamic Pricing in Queueing Systems with Unknown Delay Cost Characteristics
Afèche, P., & Ata, B. (2013) · Manufacturing & Service Operations Management · doi:10.1287/msom.1120.0418 · Cited by 43 · see citing works
Bertsimas, D. (1995) · Queueing Systems · doi:10.1007/bf01149167 · Cited by 45 · see citing works
Cognitive Engine Design for Link Adaptation: An Application to Multi-Antenna Systems
Volos, H. I., & Buehrer, R. M. (2010) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2010.070910.091651 · Cited by 42 · see citing works
Kallenberg, L. C. M. (2003) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4615-0805-2_2 · Cited by 40 · see citing works
Mining Optimal Policies: A Pattern Recognition Approach to Model Analysis
Bravo, F., & Shaposhnik, Y. (2020) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2019.0026 · Cited by 30 · see citing works
The multi-armed bandit, with constraints
Denardo, E. V., Feinberg, E. A., & Rothblum, U. G. (2012) · Annals of Operations Research · doi:10.1007/s10479-012-1250-y · Cited by 26 · see citing works
Index Policies for Stochastic Search in a Forest with an Application to R&D Project Management
Denardo, E. V., Rothblum, U. G., & der Heyden, L. V. (2004) · Mathematics of Operations Research · doi:10.1287/moor.1030.0072 · Cited by 26 · see citing works
Efficient Dynamic Allocation with Uncertain ValuationsPreprint
Bapna, A., & Weber, T. A. (2006) · SSRN Electronic Journal · doi:10.2139/ssrn.874770 · Cited by 25 · see citing works
Markovian Restless Bandits and Index Policies: A Review
Niño‐Mora, J. (2023) · Mathematics · doi:10.3390/math11071639 · Cited by 24 · see citing works
Glazebrook, K. D., Hodge, D. J., Kirkbride, C., et al. (2013) · Journal of Scheduling · doi:10.1007/s10951-013-0325-1 · Cited by 23 · see citing works
Index policies for discounted bandit problems with availability constraints
Dayanik, S., Powell, W. B., & Yamazaki, K. (2008) · Advances in Applied Probability · doi:10.1239/aap/1214950209 · Cited by 22 · see citing works
MULTI-ARMED BANDITS UNDER GENERAL DEPRECIATION AND COMMITMENT
Cowan, W., & Katehakis, M. N. (2014) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964814000217 · Cited by 21 · see citing works
Gossner, O., Steiner, J., & Stewart, C. (2021) · Econometrica · doi:10.3982/ecta17173 · Cited by 19 · see citing works
Niño‐Mora, J. (2008) · Encyclopedia of Optimization · doi:10.1007/978-0-387-74759-0_665 · Cited by 18 · see citing works
Evidence Neutrality and the Moral Value of Information
Askell, A. (2019) · doi:10.1093/oso/9780198841364.003.0003 · Cited by 18 · see citing works
The Markovian Price of Information
Gupta, A., Jiang, H., Scully, Z., et al. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17953-3_18 · Cited by 17 · see citing works
A Framework for Managing Innovation
Kavadias, S., & Hutchison‐Krupat, J. (2020) · doi:10.1287/educ.2020.0219 · Cited by 18 · see citing works
Gutin, E., & Farias, V. F. (2016) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 14 · see citing works
Asynchronous scheduling for energy optimality in systems with multiple servers
Neely, M. J. (2012) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2012.6310911 · Cited by 9 · see citing works
Optimal policy for multi-class scheduling in a single server queue
Osipova, N., Ayesta, U., & Avrachenkov, K. E. (2009) · BIRD (Basque Center for Applied Mathematics) · Cited by 11 · see citing works
Approximation Algorithms for Restless Bandit Problems
Guha, S., Munagala, K., & Shi, P. (2009) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973068.4 · Cited by 11 · see citing works
Bayesian Reinforcement Learning: A Survey
Ghavamzadeh, M., Mannor, S., Pineau, J., & Tamar, A. (2016) · CERN Document Server (European Organization for Nuclear Research) · doi:10.48550/arxiv.1609.04436 · Cited by 10 · see citing works
Reflections on a New Approach to Gittins Indexation
Glazebrook, K. D., & Garbe, R. (1996) · Journal of the Operational Research Society · doi:10.1057/jors.1996.158 · Cited by 9 · see citing works
A Note on Bandits with a Twist
Katta, A.-K., & Sethuraman, J. (2004) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480103433549 · Cited by 9 · see citing works
Approximation Algorithms for Bayesian Multi-Armed Bandit ProblemsPreprint
Guha, S., & Munagala, K. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.3525 · Cited by 8 · see citing works
On Index Policies for Restless Bandit ProblemsPreprint
Guha, S., Munagala, K., & Shi, P. (2007) · arXiv (Cornell University) · Cited by 9 · see citing works
A Framework for Managing InnovationPreprint
Kavadias, S., & Hutchison‐Krupat, J. (2020) · SSRN Electronic Journal · doi:10.2139/ssrn.3615824 · Cited by 8 · see citing works
On the undiscounted tax problem with precedence constraints
Glazebrook, K. D. (1996) · Advances in Applied Probability · doi:10.2307/1428167 · Cited by 8 · see citing works
Niño‐Mora, J. (2001) · Encyclopedia of Optimization · doi:10.1007/0-306-48332-7_507 · Cited by 8 · see citing works
Index policy for multiarmed bandit problem with dynamic risk measures
Malekipirbazari, M., & Çavuş, Ö. (2023) · European Journal of Operational Research · doi:10.1016/j.ejor.2023.08.004 · Cited by 8 · see citing works
Optimal scheduling of tasks when service is subject to disruption: the preempt-repeat case
Glazebrook, K. D. (2005) · Mathematical Methods of Operations Research · doi:10.1007/s001860400386 · Cited by 7 · see citing works
Crosbie, J. H., & Glazebrook, K. D. (2000) · Mathematics of Operations Research · doi:10.1287/moor.25.2.281.12229 · Cited by 7 · see citing works
Optimal control of a broadcasting server
Gummadi, R. (2009) · doi:10.1109/cdc.2009.5400540 · Cited by 6 · see citing works
Continue, quit, restart probability model
Sonin, I. M., & Steinberg, C. (2012) · Annals of Operations Research · doi:10.1007/s10479-012-1089-2 · Cited by 6 · see citing works
Iterated Allocations with Delayed FeedbackPreprint
Guha, S., Munagala, K., & Pál, M. (2010) · arXiv (Cornell University) · Cited by 6 · see citing works
The Gittins Index: A Design Principle for Decision Making Under Uncertainty
Scully, Z., & Terenin, A. (2025) · doi:10.1287/educ.2025.0290 · Cited by 5 · see citing works
Stochastic scheduling problem with varying weight for each job
Gu, M., & Lu, X. (2009) · Asia-Pacific Journal of Chemical Engineering · doi:10.1002/apj.386 · Cited by 5 · see citing works
Open Bandit Processes with Uncountable States and Time-Backward Effects
Wu, X., & Zhou, X. (2013) · Journal of Applied Probability · doi:10.1239/jap/1371648948 · Cited by 5 · see citing works
Stochastic Search in a Forest Revisited
Sethuraman, J., & Tsitsiklis, J. N. (2007) · Mathematics of Operations Research · doi:10.1287/moor.1070.0256 · Cited by 5 · see citing works
Self-citationMultiarmed Bandit Problems with Delayed FeedbackPreprint
Guha, S., Munagala, K., & Pál, M. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.1161 · Cited by 5 · see citing works
Multi-armed Bandits with Limited Exploration
Guha, S., & Munagala, K. (2007) · Cited by 4 · see citing works
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.038 · Cited by 5 · see citing works
Foundations of Information Theory
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.019 · Cited by 4 · see citing works
The Exploration-Exploitation Trade-Off in Sequential Decision Making Problems
Sykulski, A. M. (2011) · ePrints Soton (University of Southampton) · doi:10.25560/9073 · Cited by 3 · see citing works
Foundations of Convex Analysis
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.033 · Cited by 3 · see citing works
The Stochastic Machine Replenishment Problem
Munagala, K., & Shi, P. (2008) · Springer eBooks · doi:10.1007/978-3-540-68891-4_12 · Cited by 3 · see citing works
A mathematical programming approach to stochastic and dynamic optimization problemsPreprint
Bertsimas, D. (1994) · RePEc: Research Papers in Economics · Cited by 3 · see citing works
Asadi, H. (2018) · UA Campus Repository (The University of Arizona) · Cited by 3 · see citing works
Cognitive Radio Engine Design for Link Adaptation
Volos, H. I. (2010) · VTechWorks (Virginia Tech) · Cited by 3 · see citing works
State-Independent Control for Constrained Markov Decision Processes With Birth-Death Dynamics
Zheng, Y., & Eryılmaz, A. (2025) · IEEE Transactions on Networking · doi:10.1109/ton.2025.3553858 · Cited by 2 · see citing works
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.044 · Cited by 2 · see citing works
Parametrized stochastic multi-armed bandits with binary rewards
Jiang, C. W., & Srikant, R. (2011) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2011.5991289 · Cited by 2 · see citing works
The Upper Confidence Bound Algorithm
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.010 · Cited by 2 · see citing works
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.024 · Cited by 2 · see citing works
Tabular and Deep Reinforcement Learning for Gittins Index
Dhankhar, H., Mishra, K., & Bodas, T. (2025) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt66569.2025.11123313 · Cited by 1 · see citing works
Optimizing adaptive marketing experiments with the multi-armed bandit
Schwartz, E. M. (2013) · Scholarly Commons (University of Pennsylvania) · Cited by 1 · see citing works
Experience level analysis for a cognitive radio engine
Asadi, H., Volos, H. I., Marefat, M., et al. (2018) · Analog Integrated Circuits and Signal Processing · doi:10.1007/s10470-018-1199-0 · Cited by 1 · see citing works
The Explore-Then-Commit Algorithm
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.009 · Cited by 1 · see citing works
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.003 · Cited by 1 · see citing works
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.016 · Cited by 1 · see citing works
Open Bandit Processes with Uncountable States and Time-Backward Effects
Wu, X., & Zhou, X. (2013) · Journal of Applied Probability · doi:10.1017/s0021900200013437 · Cited by 1 · see citing works
Empirical Gittins index strategies with ε-explorations for multi-armed bandit problems
Li, X., Li, Y., & Wu, X. (2022) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2022.107610 · Cited by 1 · see citing works
Gittins Index for Simple Family of Markov Bandit Processes with Switching Cost and No Discounting
Savelov, M. P. (2019) · Theory of Probability and Its Applications · doi:10.1137/s0040585x97t989544 · Cited by 1 · see citing works
Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimation
Ornik, M., & Topcu, U. (2019) · PubMed · doi:10.48550/arxiv.1911.12976 · Cited by 6 · see citing works
Stochastic Bandits with Finitely Many Arms
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.008 · Cited by 1 · see citing works
Prediction without loss in multi-armed bandit problemsPreprint
Kapralov, M., & Panigrahy, R. (2010) · arXiv (Cornell University) · Cited by 1 · see citing works
Optimal Resource Allocation in Adaptive Survey Designs
Calinescu, I. M. (2013) · Digital Academic REpository of VU University Amsterdam (Vrije Universiteit Amsterdam) · Cited by 1 · see citing works
Managing R & D and Risky Projects
Cox, L. A. (2011) · Wiley Encyclopedia of Operations Research and Management Science · doi:10.1002/9780470400531.eorms0490 · Cited by 1 · see citing works
Exploration and exploitation in Bayes sequential decision problems
Edwards, J. (2016) · Lancaster EPrints (Lancaster University) · Cited by 1 · see citing works
Optimal search in discrete locations:extensions and new findings
Clarkson, J. (2020) · Lancaster EPrints (Lancaster University) · Cited by 1 · see citing works
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401.049 · Cited by 1 · see citing works
Index policies for discounted bandit problems with availability constraints
Dayanik, S., Powell, W. B., & Yamazaki, K. (2008) · Advances in Applied Probability · doi:10.1017/s0001867800002573 · Cited by 1 · see citing works
A Perpetual Search for Talent Across Overlapping GenerationsPreprint
Agbo, M., & Gordon, S. (2011) · SSRN Electronic Journal · doi:10.2139/ssrn.2000311
Multiarmed Bandits and Gittins Index
Weber, R. (2011) · Wiley Encyclopedia of Operations Research and Management Science · doi:10.1002/9780470400531.eorms1032
Efficient Solution of a Stochastic Scheduling Problem on an Out-Forest—Revisited
Rothblum, U. G. (2009) · SIAM Journal on Optimization · doi:10.1137/070702941
The multi-armed bandit, with constraints
Denardo, E. V., Feinberg, E. A., & Rothblum, U. G. (2012) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2185395.2185430
R & D Planning and Risk Management
Cox, L. A. (2008) · Encyclopedia of Quantitative Risk Analysis and Assessment · doi:10.1002/9780470061596.risk0686
Lin, H. (2002) · DSpace@MIT (Massachusetts Institute of Technology)
Cai, X., Wu, X., & Zhou, X. (2014) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4899-7405-1_6
Optimal data utilization for goal-oriented learning
Cowan, C. W. (2016) · doi:10.7282/t3xp772t
Inference and Decision Making in Large Weakly Dependent Graphical Models
Turner, L. (2017) · Lancaster EPrints (Lancaster University) · doi:10.17635/lancaster/thesis/114
The Markovian Price of InformationPreprint
Gupta, A., Jiang, H., Scully, Z., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.07856
Parametrized Stochastic Multi-armed Bandits with Binary RewardsPreprint
Jiang, C. W., & Srikant, R. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.4460
The Multi-Armed Bandit, with ConstraintsPreprint
Denardo, E. V., Feinberg, E. A., & Rothblum, U. G. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.4640
Savelov, M. P. (2019) · Теория вероятностей и ее применения · doi:10.4213/tvp5303
R & D Planning and Risk Management
Cox, L. A. (2014) · Wiley StatsRef: Statistics Reference Online · doi:10.1002/9781118445112.stat03772
- Authors
- Tsitsiklis, J. N.
- Corresponding author
- Tsitsiklis, John N.
- ORCID
- Tsitsiklis, John N.
- Venue
- The Annals of Applied Probability
- Publisher
- Institute of Mathematical Statistics
- Published
- 1994-02-01
- Volume
- 4
- Issue
- 1
- Pages
- 194-199
- ISSN
- 1050-5164 (ISSN-L)
- 2168-8737
- OpenAlex
- W2159471113
- Cited by
- 143
- References
- 0
- Citations by year
- 2025: 3 · 2024: 1 · 2023: 2 · 2022: 2 · 2021: 1 · 2020: 54 · 2019: 6 · 2018: 2 · 2017: 1 · 2016: 5 · 2015: 3 · 2014: 5 · 2013: 7 · 2012: 5
- FWCI
- 2.76
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- The Annals of Applied Probability (publishedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
- Keywords
- multi-armed bandits, optimal stopping, sequential decision making
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
