Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

The Gittins Index: A Design Principle for Decision-Making Under Uncertainty

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read One index rule is optimal across bandits, search, and queues—and strong beyond them.

desk verdict A clear, useful Gittins-index tutorial whose central proof rests on an explicitly unproved regularity assumption; state the theorem conditionally until that is fixed. read the letter →

arxiv 2506.10872 v3 pith:EP6OC7GO submitted 2025-06-12 math.OC cs.LGcs.PFmath.PRstat.ML

Ziv Scully , Alexander Terenin This is my paper
classification math.OCcs.LGcs.PFmath.PRstat.ML MSC 90C4090B2290B3660J05
keywords GittinsindexMarkovchainselectionmulti-armedbanditPandora'sboxM/G/1queueBayesianoptimizationtaillatencypolicy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the Gittins index—a single number assigned to each stochastic option—is not just a theoretical curiosity but a usable design principle for decisions under uncertainty. Its central result is that for a class of problems it calls Markov chain selection (MCS), where each decision advances one of several independent stochastic processes, a policy is optimal exactly when it always advances the process with the greatest Gittins index. The paper then shows that the same definition, applied outside the exactly-solvable class, produces strong policies for Bayesian optimization and for minimizing tail latency in queues. A sympathetic reader would take the paper as making the case that comparing each stochastic option to a deterministic alternative is a broadly useful recipe, even where optimality is too much to ask.

What carries the argument

The load-bearing objects are the local MDP, the Gittins index, and the surrogate value. For each chain state s and each deterministic alternative α, the local MDP offers two actions: go (advance the chain, collecting its reward) and stop (terminate and take α). The Gittins index G(s) is the unique α at which go and stop are both optimal, equivalently the value at which the local MDP's root-finding equation is satisfied. The surrogate value Γ(s) is the minimum Gittins index visited along a random trajectory from s to a terminal state; the proof shows the MCS value function is E[max_i Γ_i(s_i)], and that the Bellman optimality equation holds exactly for actions with maximal G(s). This machinery converts a multi-process decision problem into a comparison of scalar indices, and the same local-MDP construction carries over unchanged to settings where optimality fails.

What would settle it

Find a Markov chain selection instance where each chain satisfies the paper's Assumption 3.3 but no policy attains the optimal value, or where a non-optimal policy satisfies Bellman's optimality equation; if such an instance exists, the 'if and only if' version of the Gittins-policy optimality theorem fails.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.7: in the Markov chain selection problem—repeatedly choose one of n independent Markov chains to advance, collecting rewards until the first (or k-th) chain terminates—a policy is optimal if and only if it always selects an action of maximal Gittins index. The Gittins index of a state is defined via a local MDP that pits the stochastic option against a deterministic alternative α: it is the unique α at which 'stop and take α' and 'continue' are both optimal. The paper proves that the MCS value function equals the expectation of the maximum of the chains' surrogate values, where a surrogate value is the minimum Gittins index encountered on the chain's random trajectory, and that this ansatz satisfies the Bellman equation exactly at the max-index action. It then argues the same comparison-to-a-deterministic-alternative construction remains meaningful outside MCS, where it is no longer optimal but yields strong Bayesian optimization policies and asymptotically tail-optimal queue scheduling policies.

Load-bearing premise

The proof assumes that the underlying decision problem's value function is well defined, is attained by at least one policy, and that Bellman's equation exactly characterizes optimality; the authors say they expect this to follow from their standing assumptions but do not prove it.

Editorial extensions

If this is right

  • If Theorem 3.7 is correct, the Gittins policy solves every MCS instance, including undiscounted chains that terminate almost surely and discounted chains without terminal states, in one unified way.
  • It implies optimality for k-finish MCS, hence for minimizing expected kth and total completion times in single-server batch scheduling.
  • It yields that in a stable M/G/1 queue with Poisson arrivals, the Gittins policy minimizes mean latency.
  • It implies that cost-per-sample Bayesian optimization, viewed as Pandora's box with correlated boxes, has a well-defined Gittins acquisition function that matches or beats standard baselines empirically.
  • It implies that a Gittins policy with an inflation factor γ>1 asymptotically minimizes tail probabilities in the M/G/1, improving on first-come-first-served.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the surrogate-value proof extends to interleaved filtrations and continuous time as the paper sketches, index-policy analyses might unify with achievable-region methods, giving approximation guarantees rather than only exact ones.
  • The same 'compare to a deterministic α' recipe suggests testable acquisition functions for non-Gaussian Bayesian optimization models, such as diffusion-based surrogates, where closed-form indices are unavailable but root-finding and automatic differentiation still apply.
  • The γ>1 inflation trick for tail latency is a candidate transfer to other tail-sensitive objectives, such as quantile regret in bandits, if an analogous time-homogeneous formulation can be written.
  • A missing rigorous check—whether Assumption A.1 follows from Assumption 3.3—is the natural first target; closing it would put the 'if and only if' statement on unconditional footing for infinite-state undiscounted instances.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper is a tutorial-length exposition of Gittins index theory, centered on a Markov chain selection (MCS) formulation. It develops Pandora's box as motivation, defines the Gittins index via local MDPs, states an optimality theorem for MCS (Theorem 3.7), and surveys both exact extensions (multi-stage inspection, discounted bandits, MCS-k, M/G/1 scheduling, branching bandits) and heuristic or practical applications (Bayesian optimization, nonobligatory inspection, tail-latency queue scheduling). The stated design principle is 'always choose the Markov chain of greatest Gittins index.' The appendix gives a dynamic-programming proof of the central theorem using surrogate values, together with a discussion of alternative proof techniques.

Significance. The tutorial succeeds as a readable and largely well-organized unified introduction: the local-MDP definition (Definition 3.6), the surrogate-value proof structure, and the systematic treatment of where optimality holds and where it fails are valuable. The paper is also unusually honest about its technical gaps and about the boundary between exact and heuristic Gittins-index use. The connections between cost-per-sample Bayesian optimization and Pandora's box, and between tail-latency minimization and inflation, are interesting design-principle contributions, though they are drawn from the authors' prior work rather than established in this paper. If the proof gap around Assumption A.1 is closed or made explicit, the paper would be a self-contained account of a core result with broad reach.

major comments (3)
  1. [Appendix A.1, Assumption A.1] Theorem 3.7 is proved only under Assumption A.1, which asserts that the MCS value function is well defined, is achieved by some policy, and that optimality is equivalent to satisfying Bellman's equation (A.3). The manuscript explicitly says 'We expect Assumption A.1 to follow from Assumption 3.3, but do not rigorously check this.' This is a load-bearing gap: Theorem A.7 shows the proposed value function solves the Bellman equation and is achieved by the Gittins policy, but the step from 'solves Bellman' to 'is the true optimal value' is exactly Assumption A.1. In undiscounted total-reward MDPs with infinite state spaces, well-posedness and attainability are not automatic, and the authors themselves note that (A.3) can have spurious solutions in practical settings (Scully et al., Appendix D). Please either prove that Assumption A.1 follows from Assumption 3.3, or restate Theorem 3.7 and the design principle (⋆) as conditional on this assumption.
  2. [Appendix A.1, Assumption A.2] The proof also relies on two 'without loss of generality' reductions that are only sketched: replacing discounting by terminal-transition probabilities (Assumption A.2(a)) and eliminating free states (Assumption A.2(b)). These reductions are used before Lemma A.3 and Theorem A.7, yet the manuscript does not show that they preserve the value function, the set of optimal policies, and the Gittins indices of the original MCS instance. Since Theorem 3.7 is the central claim, these reductions need either a proof or a citation to a treatment that supplies the missing details.
  3. [Section 5.3 and Definition 3.2] The tail-latency application is presented as a Gittins-index design principle using an inflation factor γ > 1, but the formal MCS framework in Definition 3.2 and Assumption 3.3 only covers γ ∈ (0,1]. The paper cites Harlev et al. for 'MCS with inflation' but does not define the inflated reward objective in the paper's own notation or state the imported optimality/asymptotic result precisely. Since this is one of the two advertised practical highlights, please add a concise formal description or an explicit statement of which result is being imported and under what assumptions.
minor comments (5)
  1. [Section 2.4] There is a typo in the first paragraph: 'Our goal is to in find a good value' should read 'Our goal is to find a good value.'
  2. [Section 3.1, footnote 3] The footnote contains a duplicated word: 'a Markov chain (without rewards) is is equivalent' should be 'is equivalent.'
  3. [Section 6.2] In the first sentence of Section 6.2, 'The first a comprehensive understanding' appears to be missing a verb; it should probably read 'The first is a comprehensive understanding.'
  4. [Figure 5.4 caption] The caption would be easier to read if the policy names were separated with commas or semicolons, for example 'Boost/Gittins; Nudge-M; Nudge-K; Nudge; SRPT.'
  5. [Section 3.2, Definition 3.6] The convention that infima and suprema of empty sets are ∞ is stated, but the reader may benefit from a one-sentence reminder that, under Assumption A.2(b), free states are the only source of such extended values and are later removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: Theorem 3.7 is proved conditionally on an explicitly stated and unproved Bellman-regularity assumption, and the practical highlights cite prior empirical work rather than deriving their claims from the tutorial's own definitions.

full rationale

The central claim (Theorem 3.7) is not assumed: the Gittins index (Definition 3.6) is defined via co-optimality in the local MDP, and Appendix A proves that the candidate MCS value function (A.16) satisfies the Bellman equation and is attained by the Gittins policy. This is a substantive derivation, not an equivalence-by-construction between the definition of the index and the optimality theorem. The proof is conditional on Assumption A.1, which asserts standard dynamic-programming characterizations; the paper explicitly says, 'We expect Assumption A.1 to follow from Assumption 3.3, but do not rigorously check this.' This is an honest and load-bearing technical gap, but it is not circularity: Assumption A.1 does not mention Gittins indices, surrogate values, or the conclusion that selecting maximal indices is optimal, so the theorem does not reduce to its own input. The practical highlights in Sections 5.1 and 5.3 draw on the authors' prior work (Xie et al. 2024, Yu and Scully 2024, Harlev et al. 2025), but these are external, falsifiable empirical and algorithmic results presented as prior evidence, not as consequences derived from this tutorial's own equations. The renamings of Markovian bandits as MCS and bandit superprocesses as MDP selection are terminological, but the paper supplies a self-contained proof framework, so this is not a pure renaming of a known result. No fitted parameter is relabeled as a prediction, and no self-citation is used to justify the central optimality theorem. The Assumption A.1 caveat should be weighed as a correctness risk, not as circularity.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper's main theorem leans on standard MDP regularity assumptions, one of which (A.1) is explicitly left unproved. The applications in Section 5 depend on the authors' own prior papers for empirical evidence.

free parameters (1)
  • Inflation factor gamma
    In Section 5.3, the Gittins policy for tail latency uses an inflation factor gamma > 1 instead of a discount factor. The paper states it must be 'carefully chosen' to achieve asymptotically minimal tail probabilities, but gives no rule for selecting it. It is a hand-chosen design parameter of the proposed policy.
assumptions (3)
  • domain assumption Assumption 3.3: each Markov chain either terminates in finite time with probability one and finite expected absolute reward, or is discounted with uniformly bounded rewards.
    Ensures the local MDP and MCS value functions are well defined. Invoked in Definition 3.6 and Theorem 3.7.
  • domain assumption Assumption A.1: the MCS value function is well defined, achieved by some policy, and optimality is equivalent to satisfying Bellman's optimality equation.
    The paper states 'We expect Assumption A.1 to follow from Assumption 3.3, but do not rigorously check this.' This is a load-bearing regularity condition for the proof of Theorem 3.7.
  • domain assumption Assumption A.2: no discounting and no 'free' states (non-negative reward, zero probability of direct termination).
    The paper argues these are without loss of generality: discounting can be replaced by random termination, and free states can be played greedily. The reduction is sketched but not fully formalized.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Gittins Index: A Design Principle for Decision-Making Under Uncertainty." pith.science (2026). https://pith.science/paper/EP6OC7GO

@misc{pith2026250610872,
  author       = {Pith},
  title        = {Pith review of: The Gittins Index: A Design Principle for Decision-Making Under Uncertainty},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EP6OC7GO}},
  note         = {Machine review of arXiv:2506.10872}
}
read the original abstract

The Gittins index is a tool that optimally solves a variety of decision-making problems involving uncertainty, including multi-armed bandit problems, minimizing mean latency in queues, and search problems like the Pandora's box model. However, despite the above examples and later extensions thereof, the space of problems that the Gittins index can solve perfectly optimally is limited, and its definition is rather subtle compared to those of other multi-armed bandit algorithms. As a result, the Gittins index is often regarded as being primarily a concept of theoretical importance, rather than a practical tool for solving decision-making problems. The aim of this tutorial is to demonstrate that the Gittins index can be fruitfully applied to practical problems. We start by giving an example-driven introduction to the Gittins index, then walk through several examples of problems it solves - some optimally, some suboptimally but still with excellent performance. Two practical highlights in the latter category are applying the Gittins index to Bayesian optimization, and applying the Gittins index to minimizing tail latency in queues.

Figures

Figures reproduced from arXiv: 2506.10872 by the authors.

Figure 3.1
Figure 3.1. Illustration of the Markov chain for a box with opening cost c and reward distribution p. The states are closed, denoted ⊠; opened with reward v ∈ R, denoted v; and selected, denoted ✓. 3. General formulation of the Gittins index Having seen the Pandora’s box problem, its formulation as a Markov decision process, and its solution, one can ask: is there a general theory this solution is an example of ? We now present… view at source ↗
Figure 3.2
Figure 3.2. Optimal value of the (⊠, α)-local MDP for the two closed boxes in [PITH_FULL_IMAGE:figures/full_fig_p012_3_2.png] view at source ↗
Figure 4.2
Figure 4.2. Markov chain of a job with unknown service time sampled from distribution m—that is, the job’s service time is t with probability mt, and it is at least t with probability m≥t = P∞ u=t mu. The job’s state is its attained service, namely how many time units of service it has already received. Every transition yields reward −1, representing one unit of time passing. The transition probabilities come from the fact that… view at source ↗
Figures from the paper (6 more)
Figure 4.3
Figure 4.3. Figure 4.3: Markov chain of a job with two stages of service. Each stage i requires an unknown amount of service sampled from distribution m(i) , so the service time is a priori unknown, but the agent learns when the transition from the first to the second stage occurs. A job’s …
Figure 5.1
Figure 5.1. Figure 5.1: Results reproduced from Xie et al. [114]: empirical performance (higher is better) of the Gittins policy for Bayesian optimization, also called PBGI (green) in the legend, against other baseline policies, shown in terms of medians and quartiles over 16 seeds. The tas…
Figure 5.2
Figure 5.2. Figure 5.2: A single Pandora’s box with optional inspection is not simply a Markov chain, but an MDP: specifically, from the closed state ⊠, one can take either the ▷open action, which incurs cost but reveals the box’s reward, or the ▷take action, which takes the box without ope…
Figure 5
Figure 5. Figure 5: gives an illustration [PITH_FULL_IMAGE:figures/full_fig_p026_5.png]
Figure 5.3
Figure 5.3. Figure 5.3: Analogue of [PITH_FULL_IMAGE:figures/full_fig_p027_5_3.png]
Figure 5.4
Figure 5.4. Figure 5.4: Results reproduced from Yu and Scully [115]: empirical performance (higher is better) of the Gittins policy for minimizing tail probabilities, also called Boost (blue) in the legend, against other baseline policies, simulated in three different M/G/1 models with diff…

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoning

    cs.AI 2025-11 conditional novelty 6.0 of 10

    Re-FORC learns to forecast reward-versus-thinking-token curves and uses them in a Gittins-style policy, saving ~26% compute at matched accuracy and improving accuracy at matched compute on five math benchmarks.

Reference graph

Works this paper leans on

124 extracted references · 48 canonical work pages · cited by 1 Pith paper

  1. [1]

    Samuli Aalto, Urtzi Ayesta, and Rhonda Righter. 2009. On the Gittins Index in the M/G/1 Queue. Queueing Systems 63, 1-4 (Dec. 2009), 437–458. doi: 10.1007/s11134-009-9141-x . Cited on pages 17, 18, and 31

    doi:10.1007/s11134-009-9141-x 2009

  2. [2]

    Samuli Aalto, Urtzi Ayesta, and Rhonda Righter. 2011. Properties of the Gittins Index with Application to Optimal Scheduling. Probability in the Engineering and Informational Sciences 25, 3 (July 2011), 269–288. doi:10.1017/S0269964811000015. Cited on page 18

    doi:10.1017/s0269964811000015 2011

  3. [3]

    Samuli Aalto and Ziv Scully. 2023. Minimizing the Mean Slowdown in the M/G/1 Queue. Queueing Systems 104, 3-4 (Aug. 2023), 187–210. doi: 10.1007/s11134-023-09888-6 . Cited on pages 17 and 31

    work page doi:10.1007/s11134-023-09888-6 2023

  4. [4]

    Zico Kolter

    Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico Kolter

  5. [5]

    Mohammad Reza Aminian, Vahideh Manshadi, and Rad Niazadeh. 2023. Markovian Search with Socially Aware Constraints. SSRN: 4347447. Cited on page 31

    2023

  6. [6]

    Arjun Anand and Gustavo de Veciana. 2018. A Whittle’s Index Based Approach for QoE Optimization in Wireless Networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems 2, 1 (March 2018), 1–39. doi: 10.1145/3179418. Cited on page 29

    work page doi:10.1145/3179418 2018

  7. [7]

    Ali Aouad, Jingwei Ji, and Yaron Shaposhnik. 2020. Pandora’s Box Problem with Sequential Inspections. SSRN:3726167. Cited on pages 28, 43, and 44

    2020

  8. [8]

    Borkar, and Pratik Shah

    Konstantin Avrachenkov, Vivek S. Borkar, and Pratik Shah. 2024. Lagrangian Index Policy for Restless Bandits with Average Reward. arXiv: 2412.12641. Cited on page 31

    arXiv 2024

Show all 124 references
  1. [9]

    Peter Bank and Christian K¨ uchler. 2007. On Gittins’ Index Theorem in Continuous Time. Stochastic Processes and their Applications 117, 9 (Sept. 2007), 1357–1371. doi: 10.1016/j.spa.2007.01.006. Cited on pages 31 and 44

    2007 doi

  2. [10]

    Bertsekas

    Dimitri P. Bertsekas. 2012. Dynamic Programming and Optimal Control, Volume 2: Approximate Dynamic Programming (4 ed.). Athena Scientific, Belmont, MA. https://www.mit.edu/~dimitrib/ dpbook.html. Cited on page 14

    2012

  3. [11]

    Dimitris Bertsimas. 1995. The Achievable Region Method in the Optimal Control of Queueing Systems; Formulations, Bounds and Policies. Queueing Systems 21, 3 (Sept. 1995), 337–389. doi: 10.1007/ BF01149167. Cited on pages 17 and 44

    1995

  4. [12]

    Dimitris Bertsimas and Jos´ e Ni˜ no-Mora. 1996. Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; a Polyhedral Approach to Indexable Systems.Mathematics of Operations Research 21, 2 (May 1996), 257–306. doi: 10.1287/moor.21.2.257. Cited on page 31

    1996 doi

  5. [13]

    Dimitris Bertsimas and Jos´ e Ni˜ no-Mora. 1999. Optimization of Multiclass Queueing Networks with Changeover Times via the Achievable Region Approach: Part I, the Single-Station Case. Mathematics of Operations Research 24, 2 (May 1999), 306–330. doi: 10.1287/moor.24.2.306. Ci...

    1999 doi

  6. [14]

    Dimitris Bertsimas and Jos´ e Ni˜ no-Mora. 1999. Optimization of Multiclass Queueing Networks with Changeover Times via the Achievable Region Approach: Part II, the Multi-Station Case. Mathematics of Operations Research 24, 2 (May 1999), 331–361. doi: 10.1287/moor.24.2.331. Ci...

    1999 doi

  7. [16]

    Hedyeh Beyhaghi and Linda Cai. 2023. Recent Developments in Pandora’s Box Problem: Variants and Applications. ACM SIGecom Exchanges 21, 1 (June 2023), 20–34. doi: 10.1145/3699814.3699817. Cited on pages 28 and 43

    2023

  8. [17]

    Hedyeh Beyhaghi and Robert Kleinberg. 2019. Pandora’s Problem with Nonobligatory Inspection. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC 2019) . ACM, Phoenix, AZ, 131–132. doi: 10.1145/3328526.3329626. Cited on pages 25 and 28

    2019

  9. [18]

    Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares-Lopez, Fabian Pedregosa, and Jean-Philippe Vert. 2022. Efficient and Modular Implicit Differentiation. In Advances in Neural Information Processing Systems (NeurIPS 2022) , Vol. 35. Cur...

    2022 doi arXiv

  10. [19]

    Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. 2020. Pandora’s Box Problem with Order Constraints. In Proceedings of the 21st ACM Conference on Economics and Computation (EC 2020) . ACM, Budapest, Hungary, 439–458. doi: 10.1145/3391403.3399501. Cited on page 22

    2020

  11. [20]

    Robin Bowers, Elias Lindgren, and Bo Waggoner. 2025. Prophet Inequalities for Bandits, Cabinets, and DAGs. arXiv:2502.08976. Cited on pages 28 and 43

    2025

  12. [21]

    Robin Bowers and Bo Waggoner. 2024. Matching with Nested and Bundled Pandora Boxes. arXiv:2406. 08711. Cited on pages 28 and 44

    2024

  13. [22]

    Boxma and Bert Zwart

    Onno J. Boxma and Bert Zwart. 2007. Tails in Scheduling. ACM SIGMETRICS Performance Evaluation Review 34, 4 (March 2007), 13–20. doi: 10.1145/1243401.1243406. Cited on page 30

    2007

  14. [23]

    Brown and James E

    David B. Brown and James E. Smith. 2013. Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats. Operations Research 61, 3 (June 2013), 644–665. doi: 10.1287/opre.2013.1164. Cited on pages 26, 28, 43, and 44

    2013

  15. [24]

    Felipe Caro and Aparupa Das Gupta. 2022. Robust Control of the Multi-Armed Bandit Problem. Annals of Operations Research 317, 2 (Oct. 2022), 461–480. doi: 10.1007/s10479-015-1965-7 . Cited on page 31

    2022 doi

  16. [25]

    Jhelum Chakravorty and Aditya Mahajan. 2014. Multi-Armed Bandits, Gittins Index, and Its Calculation. In Methods and Applications of Statistics in Clinical Trials , N. Balakrishnan (Ed.). Wiley, Hoboken, NJ, 416–435. doi: 10.1002/9781118596333.ch24. Cited on pages 13, 14, 26, and 31

    2014 doi

  17. [26]

    Nils Charlet and Benny Van Houdt. 2024. Tail Optimality and Performance Analysis of the Nudge-M Scheduling Algorithm. arXiv:2403.06588. Cited on page 30

    2024 arXiv

  18. [27]

    Shuchi Chawla, Dimitris Christou, Amit Harlev, and Ziv Scully. 2024. Combinatorial Selection with Costly Information. arXiv: 2412.03860. Cited on pages 14, 25, 28, 43, and 44

    2024 arXiv

  19. [28]

    Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. 2022. Approximating Pandora’s Box with Correlations. arXiv: 2108.12976. Cited on page 25. 34 Ziv Scully and Alexander Terenin: The Gittins Index

    2022 arXiv

  20. [29]

    Glazebrook, and Kyle Y

    Jake Clarkson, Kevin D. Glazebrook, and Kyle Y. Lin. 2020. Fast or Slow: Search in Discrete Locations with Two Search Modes. Operations Research 68, 2 (Jan. 2020), 552–571. doi:10.1287/opre.2019.1870. Cited on page 28

    2020

  21. [30]

    Lin, and Kevin D

    Jake Clarkson, Kyle Y. Lin, and Kevin D. Glazebrook. 2023. A Classical Search Game in Discrete Locations. Mathematics of Operations Research 48, 2 (May 2023), 687–707. doi: 10.1287/moor.2022

    2023 doi

  22. [31]

    Cohen and Tanut Treetanthiploet

    Samuel N. Cohen and Tanut Treetanthiploet. 2022. Gittins’ Theorem under Uncertainty. Electronic Journal of Probability 27, Article 17 (Jan. 2022), 48 pages. doi: 10.1214/22-EJP742. Cited on page 31

    2022 doi

  23. [32]

    Glazebrook, and Jos´ e Ni˜ no-Mora

    Marcus Dacre, Kevin D. Glazebrook, and Jos´ e Ni˜ no-Mora. 1999. The Achievable Region Approach to the Optimal Control of Stochastic Systems. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 61, 4 (Nov. 1999), 747–791. doi:10.1111/1467-9868.00202. C...

    1999

  24. [33]

    Laura Doval. 2018. Whether or Not to Open Pandora’s Box. Journal of Economic Theory 175 (May 2018), 127–158. doi: 10.1016/j.jet.2018.01.005. Cited on pages 25 and 28

    2018 doi

  25. [34]

    Ioana Dumitriu, Prasad Tetali, and Peter Winkler. 2003. On Playing Golf with Two Balls. SIAM Journal on Discrete Mathematics 16, 4 (Jan. 2003), 604–615. doi: 10.1137/S0895480102408341. Cited on pages 31 and 44

    2003 doi

  26. [35]

    Katharina Eggensperger, Philipp M¨ uller, Neeratyoy Mallik, Matthias Feurer, Rene Sass, Aaron Klein, Noor Awad, Marius Lindauer, and Frank Hutter. 2021. HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO. In Proceedings of the Neural Information P...

    2021 doi arXiv

  27. [36]

    Farias and Eli Gutin

    Vivek F. Farias and Eli Gutin. 2022. Optimistic Gittins Indices. Operations Research 70, 6 (Nov. 2022), 3432–3456. doi: 10.1287/opre.2021.2207. Cited on pages 14, 16, 31, and 32

    2022

  28. [37]

    Peter I. Frazier. 2018. Bayesian Optimization. In Recent Advances in Optimization and Modeling of Contemporary Problems, Esma Gel, Lewis Ntaimo, Douglas Shier, and Harvey J. Greenberg (Eds.). INFORMS, Catonsville, MD, 255–278. doi: 10.1287/educ.2018.0188. Cited on page 22

    2018

  29. [38]

    Esther Frostig and Gideon Weiss. 2016. Four Proofs of Gittins’ Multiarmed Bandit Theorem. Annals of Operations Research 241, 1-2 (June 2016), 127–165. doi: 10.1007/s10479-013-1523-0 . Cited on page 31

    2016 doi

  30. [39]

    Hu Fu, Jiawei Li, and Daogao Liu. 2023. Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) . ACM, Orlando, FL, 789–802. doi: 10.1145/3564246.3585229. Cited on ...

    2023

  31. [40]

    Roman Garnett. 2023. Bayesian Optimization . Cambridge University Press, Cambridge, UK. https: //bayesoptbook.com. Cited on page 22

    2023

  32. [41]

    Nicolas Gast, Bruno Gaujal, and Kimang Khun. 2023. Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time. Mathematical Methods of Operations Research 97, 3 (June 2023), 391–436. doi:10.1007/s00186-023-00821-4 . Cited on pages 14, 26, and 31

    2023 doi

  33. [42]

    Nicolas Gast and Dheeraj Narasimha. 2025. Model Predictive Control Is Almost Optimal for Restless Bandit. arXiv:2410.06307. Cited on page 31

    2025 arXiv

  34. [43]

    Evangelia Gergatsouli and Christos Tzamos. 2023. Weitzman’s Rule for Pandora’s Box with Corre- lations. In Advances in Neural Information Processing Systems (NeurIPS 2023) , Vol. 36. Curran Associates, Inc., New Orleans, LA, 12644–12664. doi: 10.48550/arXiv.2301.13534. Cited o...

    2023 doi arXiv

  35. [44]

    John C. Gittins. 1979. Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society: Series B (Methodological) 41, 2 (Jan. 1979), 148–164. doi: 10.1111/j.2517-6161. 1979.tb01068.x. Cited on pages 7, 9, 10, and 31

    1979 doi

  36. [45]

    Gittins, Kevin D

    John C. Gittins, Kevin D. Glazebrook, and Richard R. Weber. 2011. Multi-Armed Bandit Allocation Indices (2 ed.). Wiley, Chichester, UK. doi: 10.1002/9780470980033. Cited on pages 2, 11, 13, 14, 16, 21, 22, 31, and 44

    2011 doi

  37. [46]

    Gittins and David M

    John C. Gittins and David M. Jones. 1974. A Dynamic Allocation Index for the Sequential Design of Experiments. In Progress in Statistics, Joseph M. Gani, K´ aroly Sarkadi, and Istv´ an Vincze (Eds.). Number 9 in Colloquia Mathematica Societatis J´ anos Bolyai. North-Holland, A...

    1974

  38. [47]

    Glazebrook

    Kevin D. Glazebrook. 1979. Stoppable Families of Alternative Bandit Processes. Journal of Applied Probability 16, 4 (Dec. 1979), 843–854. doi: 10.2307/3213150. Cited on page 28

    1979 doi

  39. [48]

    Glazebrook

    Kevin D. Glazebrook. 1982. On a Sufficient Condition for Superprocesses Due to Whittle. Journal of Applied Probability 19, 1 (March 1982), 99–110. doi: 10.2307/3213920. Cited on pages 28 and 44

    1982 doi

  40. [49]

    Glazebrook

    Kevin D. Glazebrook. 2003. An Analysis of Klimov’s Problem with Parallel Servers. Mathematical Methods of Operations Research 58, 1 (Sept. 2003), 1–28. doi: 10.1007/s001860300278. Cited on pages 17, 20, 21, and 44

    2003 doi

  41. [50]

    Glazebrook, David J

    Kevin D. Glazebrook, David J. Hodge, Christopher Kirkbride, and R. J. Minty. 2014. Stochastic Schedul- ing: A Short History of Index Policies and New Approaches to Index Generation for Dynamic Resource Allocation. Journal of Scheduling 17, 5 (Oct. 2014), 407–425. doi: 10.1007/...

    2014 doi

  42. [51]

    Glazebrook and Jos´ e Ni˜ no-Mora

    Kevin D. Glazebrook and Jos´ e Ni˜ no-Mora. 2001. Parallel Scheduling of MulticlassM/M/m Queues: Approximate and Heavy-Traffic Optimization of Achievable Performance. Operations Research 49, 4 (Aug. 2001), 609–623. doi: 10.1287/opre.49.4.609.11225. Cited on pages 21 and 44

    2001 doi

  43. [52]

    Isaac Grosof, Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. 2022. Optimal Scheduling in the Multiserver-Job Model under Heavy Traffic. Proceedings of the ACM on Measurement and Analysis of Computing Systems 6, 3, Article 51 (Dec. 2022), 32 pages. doi: 10.1145/3570612...

    2022 doi

  44. [53]

    Isaac Grosof, Kunhe Yang, Ziv Scully, and Mor Harchol-Balter. 2021. Nudge: Stochastically Improving upon FCFS. Proceedings of the ACM on Measurement and Analysis of Computing Systems 5, 2, Article 21 (June 2021), 29 pages. doi: 10.1145/3460088. Cited on page 30

    2021 doi

  45. [54]

    Sudipto Guha, Kamesh Munagala, and Saswati Sarkar. 2008. Information Acquisition and Exploitation in Multichannel Wireless Networks. arXiv: 0804.1724. Cited on pages 25 and 28

    2008 arXiv

  46. [55]

    Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. 2019. The Markovian Price of Information. In Integer Programming and Combinatorial Optimization, 20th International Conference (IPCO

    2019

  47. [56]

    Dylan Hadfield-Menell and Stuart Russel. 2015. Multitasking: Efficient Optimal Planning for Bandit Superprocesses. In 31st Conference on Uncertainty in Artificial Intelligence (UAI 2015) . AUAI Press, Amsterdam, The Netherlands, 345–354. https://auai.org/uai2015/proceedings.sh...

    2015

  48. [57]

    11480) , Andrea Lodi and Viswanath Nagarajan (Eds.)

    (Lecture Notes in Computer Science, Vol. 11480) , Andrea Lodi and Viswanath Nagarajan (Eds.). Springer, Cham, Switzerland, 233–246. doi:10.1007/978-3-030-17953-3_18 . Cited on pages 17, 31, 43, and 44

    doi

  49. [58]

    Yige Hong and Ziv Scully. 2024. Performance of the Gittins Policy in the G/G/1 and G/G/ k, with and without Setup Times. Performance Evaluation 163, Article 102377 (Jan. 2024), 26 pages. doi:10.1016/j.peva.2023.102377. Cited on page 21

    2024

  50. [59]

    Amit Harlev, George Yu, and Ziv Scully. 2025. A Gittins Policy for Optimizing Tail Latency.Proceedings of the ACM on Measurement and Analysis of Computing Systems 9, 2, Article 17 (June 2025), 40 pages. doi: 10.1145/3727109. Cited on pages 29 and 30

    2025 doi

  51. [60]

    Yige Hong, Qiaomin Xie, Yudong Chen, and Weina Wang. 2024. Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption. arXiv: 2405. 17882. Cited on page 31

    2024

  52. [61]

    Yige Hong, Qiaomin Xie, Yudong Chen, and Weina Wang. 2023. Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption. In Advances in Neural Information Processing Systems (NeurIPS 2023) . Curran Associates, Inc., New Orleans, LA, 12810–12844. doi: ...

    2023 doi arXiv

  53. [62]

    Haya Kaspi and Avishai Mandelbaum. 1998. Multi-Armed Bandits in Discrete and Continuous Time. The Annals of Applied Probability 8, 4 (Nov. 1998), 1270–1290. doi: 10.1214/aoap/1028903380. Cited on pages 31 and 44

    1998

  54. [64]

    Frank P. Kelly. 1981. Multi-Armed Bandits with Discount Factor near One: The Bernoulli Case. The Annals of Statistics 9, 5 (Sept. 1981), 987–1001. doi: 10.1214/aos/1176345578. Cited on pages 14, 16, and 31

    1981

  55. [65]

    Katehakis and Arthur F

    Michael N. Katehakis and Arthur F. Veinott. 1987. The Multi-Armed Bandit Problem: Decomposition and Computation. Mathematics of Operations Research 12, 2 (May 1987), 262–268. doi: 10.1287/moor. 12.2.262. Cited on pages 26 and 31

    1987 doi

  56. [66]

    Glen Weyl

    Robert Kleinberg, Bo Waggoner, and E. Glen Weyl. 2016. Descending Price Optimally Coordinates Search. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC 2016) . ACM, Maastricht, The Netherlands, 23–24. doi: 10.1145/2940716.2940760. Cited on pages 28, 31, and 44

    2016

  57. [67]

    Michael Jong Kim and Andrew E.B. Lim. 2016. Robust Multiarmed Bandit Problems. Management Science 62, 1 (Jan. 2016), 264–285. doi: 10.1287/mnsc.2015.2153. Cited on pages 14, 16, and 31

    2016

  58. [68]

    Gennadi P. Klimov. 1978. Time-Sharing Service Systems. II. Theory of Probability & Its Applications 23, 2 (1978), 314–321. doi: 10.1137/1123034. Cited on pages 9 and 17

    1978 doi

  59. [69]

    Gennadi P. Klimov. 1974. Time-Sharing Service Systems. I. Theory of Probability & Its Applications 19, 3 (1974), 532–551. doi: 10.1137/1119060. Cited on pages 9 and 17

    1974 doi

  60. [70]

    Tor Lattimore. 2021. Lectures on Information Directed Sampling. Retrieved 2025-03-12 from https: //rlforum.stanford.edu/p/lec-ids/. Lecture 1 Recording, timestamp 31:10. Cited on page 3

    2021

  61. [71]

    Tor Lattimore. 2016. Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits. In 29th Annual Conference on Learning Theory (COLT 2016) (Proceedings of Machine Learning Research, Vol. 49), Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.). P...

    2016

  62. [72]

    Eric Hans Lee, David Eriksson, David Bindel, Bolong Cheng, and Mike Mccourt. 2020. Efficient Rollout Strategies for Bayesian Optimization. InProceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) (Proceedings of Machine Learning Research, Vol. 124) ...

    2020

  63. [73]

    2020.Bandit Algorithms (1 ed.)

    Tor Lattimore and Csaba Szepesv´ ari. 2020.Bandit Algorithms (1 ed.). Cambridge University Press, Cambridge, UK. doi:10.1017/9781108571401. Cited on page 11. 36 Ziv Scully and Alexander Terenin: The Gittins Index

    2020 doi

  64. [74]

    Avi Mandelbaum. 1986. Discrete Multi-Armed Bandits and Multi-Parameter Processes. Probability Theory and Related Fields 71, 1 (Jan. 1986), 129–147. doi: 10.1007/BF00366276. Cited on page 44

    1986 doi

  65. [75]

    Eric Hans Lee, David Eriksson, Valerio Perrone, and Matthias Seeger. 2021. A Nonmyopic Approach to Cost-Constrained Bayesian Optimization. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI 2021) (Proceedings of Machine Learning Rese...

    2021

  66. [76]

    Nicole Megow and Tjark Vredeveld. 2014. A Tight 2-Approximation for Preemptive Stochastic Scheduling. Mathematics of Operations Research 39, 4 (Nov. 2014), 1297–1310. doi: 10.1287/moor. 2014.0653. Cited on page 21

    2014

  67. [77]

    Avi Mandelbaum. 1987. Continuous Multi-Armed Bandits and Multiparameter Processes. The Annals of Probability 15, 4 (Oct. 1987), 1527–1556. doi: 10.1214/aop/1176991992. Cited on pages 31 and 44

    1987

  68. [78]

    Paul Milgrom and Ilya Segal. 2002. Envelope Theorems for Arbitrary Choice Sets. Econometrica 70, 2 (March 2002), 583–601. doi: 10.1111/1468-0262.00296. Cited on page 12

    2002

  69. [79]

    Michela Meister and Jon Kleinberg. 2023. Optimizing the Order of Actions in a Model of Contact Tracing. PNAS Nexus 2, 3, Article pgad003 (March 2023), 11 pages. doi: 10.1093/pnasnexus/pgad003. Cited on page 22

    2023 doi

  70. [80]

    Peter Nash. 1973. Optimal Allocation of Resources between Research Projects. Ph. D. Dissertation. University of Cambridge, Cambridge, UK. https://idiscover.lib.cam.ac.uk/permalink/f/t9gok8/ 44CAM_ALMA21393802550003606. Cited on page 26

    1973

  71. [81]

    Benjamin Moseley, Heather Newman, Kirk Pruhs, and Rudy Zhou. 2025. Robust Gittins for Stochastic Scheduling. arXiv:2504.10743. Cited on page 31

    2025 arXiv

  72. [82]

    Misja Nuyens, Adam Wierman, and Bert Zwart. 2008. Preventing Large Sojourn Times Using SMART Scheduling. Operations Research 56, 1 (Feb. 2008), 88–101. doi: 10.1287/opre.1070.0504. Cited on page 30

    2008

  73. [83]

    Jos´ e Ni˜ no-Mora. 2023. Markovian Restless Bandits and Index Policies: A Review.Mathematics 11, 7 (March 2023), 1639. doi: 10.3390/math11071639. Cited on page 31

    2023 doi

  74. [84]

    Eli Persky. 2021. Exploration and Exploitation: From Bandits to Bayesian Optimisation . Master’s the- sis. University of Cambridge, Cambridge, UK. https://www.mlmi.eng.cam.ac.uk/files/2020-2021_ dissertations/exploration_and_exploitation.pdf. Cited on page 24

    2021

  75. [85]

    Misja Nuyens and Bert Zwart. 2006. A Large-Deviations Analysis of the GI/GI/ 1 SRPT Queue. Queueing Systems 54, 2 (Oct. 2006), 85–97. doi: 10.1007/s11134-006-8767-1 . Cited on page 30

    2006 doi

  76. [86]

    Ziv Scully. 2022. A New Toolbox for Scheduling Theory. Ph. D. Dissertation. Carnegie Mellon University, Pittsburgh, PA. https://ziv.codes/pdf/scully-thesis.pdf. Cited on pages 21, 31, and 44

    2022

  77. [87]

    Linus E. Schrage. 1968. A Proof of the Optimality of the Shortest Remaining Processing Time Discipline. Operations Research 16, 3 (June 1968), 687–690. doi: 10.1287/opre.16.3.687. Cited on pages 18 and 30

    1968 doi

  78. [88]

    Ziv Scully, Isaac Grosof, and Mor Harchol-Balter. 2020. The Gittins Policy Is Nearly Optimal in the M/G/k under Extremely General Conditions. Proceedings of the ACM on Measurement and Analysis of Computing Systems 4, 3, Article 43 (Dec. 2020), 29 pages. doi: 10.1145/3428328. C...

    2020 doi

  79. [89]

    Ziv Scully and Laura Doval. 2024. Local Hedging Approximately Solves Pandora’s Box Problems with Nonobligatory Inspection. arXiv: 2410.19011. Cited on pages 14, 25, 28, 43, and 44

    2024 arXiv

  80. [90]

    Ziv Scully and Mor Harchol-Balter. 2021. The Gittins Policy in the M/G/1 Queue. In19th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt 2021). IEEE, Philadelphia, PA (virtual), 248–255. doi: 10.23919/WiOpt52861.2021.9589051. ...

    2021

  81. [91]

    Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. 2022. Uniform Bounds for Scheduling with Job Size Estimates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs)) . Schloss Dagstuhl – Leibniz-...

    2022 doi

  82. [92]

    Ziv Scully and Lucas van Kreveld. 2025. When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1? Operations Research 73, 3 (May 2025), 1412–1429. doi: 10.1287/ opre.2022.0038. Cited on page 31

    2025

  83. [93]

    Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. 2018. Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs. arXiv: 1805.06865. Cited on pages 14 and 38

    2018 arXiv

  84. [94]

    Kenneth C. Sevcik. 1971. The Use of Service Time Distributions in Scheduling . Ph. D. Dissertation. University of Chicago, Chicago, IL. doi: 10.2172/4710384. Cited on pages 9 and 17

    1971 doi

  85. [95]

    Boxma, Jan-Pieter Dorsman, and Adam Wierman

    Ziv Scully, Lucas van Kreveld, Onno J. Boxma, Jan-Pieter Dorsman, and Adam Wierman. 2020. Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job Sizes. Proceedings of the ACM on Measurement and Analysis of Computing Systems 4, 2, Article 30 (June 2020)...

    2020 doi

  86. [96]

    Sahil Singla. 2018. The Price of Information in Combinatorial Optimization. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) . SIAM, New Orleans, LA, 2523–2532. doi: 10.1137/1.9781611975031.161. Cited on pages 6, 17, and 43

    2018 doi

  87. [97]

    Kenneth C. Sevcik. 1974. Scheduling for Minimum Total Loss Using Service Time Distributions. J. ACM 21, 1 (Jan. 1974), 66–75. doi: 10.1145/321796.321803. Cited on pages 9 and 17

    1974

  88. [98]

    Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. 2012. Practical Bayesian Optimization of Machine Learning Algorithms. In Advances in Neural Information Processing Systems (NIPS 2012) , Vol. 25. Curran Associates, Inc., Lake Tahoe, NV, 2951–2959. doi: 10.48550/arXiv.1206.2944...

    2012 doi arXiv

  89. [99]

    Aleksandrs Slivkins. 2019. Introduction to Multi-Armed Bandits. Foundations and Trends in Machine Learning 12, 1-2 (2019), 1–286. doi: 10.1561/2200000068. Cited on page 11

    2019 doi

  90. [101]

    Tsitsiklis

    J. Tsitsiklis. 1986. A Lemma on the Multiarmed Bandit Problem. IEEE Trans. Automat. Control 31, 6 (June 1986), 576–577. doi: 10.1109/TAC.1986.1104332. Cited on page 31

    1986

  91. [102]

    Ina Maria Verloop. 2016. Asymptotically Optimal Priority Policies for Indexable and Nonindexable Restless Bandits. The Annals of Applied Probability 26, 4 (Aug. 2016), 1947–1995. doi: 10.1214/ 15-AAP1137. Cited on page 31

    2016

  92. [103]

    Benny Van Houdt. 2022. On the Stochastic and Asymptotic Improvement of First-Come First-Served and Nudge Scheduling. Proceedings of the ACM on Measurement and Analysis of Computing Systems 6, 3 (Dec. 2022), 1–22. doi: 10.1145/3570610. Cited on page 30

    2022 doi

  93. [104]

    Richard R. Weber. 1992. On the Gittins Index for Multiarmed Bandits. The Annals of Applied Probability 2, 4 (Nov. 1992), 1024–1033. doi: 10.1214/aoap/1177005588. Cited on pages 31 and 44

    1992

  94. [105]

    von Olivier

    G. von Olivier. 1972. Kostenminimale Priorit¨ aten in Wartesystemen vom Typ M/G/1 [Cost-minimum priorities in queueing systems of type M/G/1]. Elektronische Rechenanlagen 14, 6 (Dec. 1972), 262–271. doi:10.1524/itit.1972.14.16.262. Cited on pages 9 and 17

    1972 doi

  95. [106]

    Weber and Gideon Weiss

    Richard R. Weber and Gideon Weiss. 1990. On an Index Policy for Restless Bandits. Journal of Applied Probability 27, 3 (1990), 637–648. doi: 10.2307/3214547. Cited on pages 29 and 31

    1990 doi

  96. [107]

    Richard R. Weber. 2016. Multi-armed Bandits and the Gittins Index Theorem. Retrieved 2025-06-12 from https://www.statslab.cam.ac.uk/~rrw1/oc/ocgittins.pdf. Cited on page 2

    2016

  97. [108]

    Weitzman

    Martin L. Weitzman. 1979. Optimal Search for the Best Alternative. Econometrica 47, 3 (May 1979), 641–654. doi:10.2307/1910412. Cited on pages 3, 7, and 9

    1979 doi

  98. [109]

    Gideon Weiss. 1988. Branching Bandit Processes. Probability in the Engineering and Informational Sciences 2, 3 (July 1988), 269–278. doi:10.1017/S0269964800000826. Cited on pages 22, 28, 31, and 44

    1988 doi

  99. [110]

    P. Whittle. 1981. Arm-Acquiring Bandits. The Annals of Probability 9, 2 (April 1981), 284–292. doi:10.1214/aop/1176994469. Cited on page 20

    1981

  100. [111]

    Peter Whittle. 1980. Multi-Armed Bandits and the Gittins Index. Journal of the Royal Statistical Society: Series B (Methodological) 42, 2 (1980), 143–149. doi: 10.1111/j.2517-6161.1980.tb01111.x. Cited on pages 26, 28, 31, 38, and 44

    1980

  101. [112]

    Peter Whittle. 2005. Tax Problems in the Undiscounted Case. Journal of Applied Probability 42, 3 (Sept. 2005), 754–765. doi: 10.1239/jap/1127322025. Cited on page 17

    2005

  102. [113]

    Peter Whittle. 1988. Restless Bandits: Activity Allocation in a Changing World. Journal of Applied Probability 25, A (1988), 287–298. doi: 10.2307/3214163. Cited on pages 29 and 31

    1988 doi

  103. [114]

    Qian Xie, Raul Astudillo, Peter Frazier, Ziv Scully, and Alexander Terenin. 2024. Cost-Aware Bayesian Optimization via the Pandora’s Box Gittins Index. In Advances in Neural Information Processing Systems (NeurIPS 2024) , Vol. 37. Curran Associates, Inc., Vancouver, BC, 115523...

    2024 doi arXiv

  104. [115]

    Adam Wierman and Bert Zwart. 2012. Is Tail-Optimal Scheduling Possible? Operations Research 60, 5 (Oct. 2012), 1249–1257. doi: 10.1287/opre.1120.1086. Cited on page 30

    2012

  105. [116]

    Zhe Yu, Yunjian Xu, and Lang Tong. 2018. Deadline Scheduling as Restless Bandits. IEEE Trans. Automat. Control 63, 8 (Aug. 2018), 2343–2358. doi: 10.1109/TAC.2018.2807924. Cited on page 29

    2018

  106. [117]

    George Yu and Ziv Scully. 2024. Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1. Proceedings of the ACM on Measurement and Analysis of Computing Systems 8, 2, Article 27 (June 2024), 33 pages. doi: 10.1145/3656011. Cited on pages 29 and 30

    2024 doi

  107. [118]

    Lucas Zimmer, Marius Lindauer, and Frank Hutter. 2021. Auto-PyTorch: Multi-Fidelity MetaLearning for Efficient and Robust AutoDL. IEEE Transactions on Pattern Analysis and Machine Intelligence 43, 9 (Sept. 2021), 3079–3090. doi: 10.1109/TPAMI.2021.3067763. Cited on page 25. 38...

    2021

  108. [119]

    Qing Zhao. 2020. Multi-Armed Bandits: Theory and Applications to Online Learning in Networks . Springer, Cham, Switzerland. doi: 10.1007/978-3-031-79289-2 . Cited on page 13

    2020 doi

  109. [121]

    Some involve dynamic program- ming (Assumption A.1), while others are taken to ease presentation (Assumption A.2)

    We state the specific assumptions needed for our proof. Some involve dynamic program- ming (Assumption A.1), while others are taken to ease presentation (Assumption A.2)

  110. [122]

    We define the surrogate value of a Markov chain (Definition A.4), a random variable that gives a probabilistic interpretation of the local MDP value function (Lemma A.5)

  111. [123]

    min(T,τ )−1X t=0 rπ∗(s(t))(sπ∗(s(t))) +V ∗ MCS(s(min(T, τ))) # . (A.28) Taking the T → ∞limit and applying dominated convergence via Assumption 3.3 yields V ∗ MCS(s) = E

    We define a guess for the MCS value function by appropriately combining the Markov chains’ surrogate prices, then show that it solves the MCS Bellman equation (Theo- rem A.7). The rough idea is that our MCS value function guess inherits the respective Bellman inequalities of t...

  112. [124]

    This is exactly our Definition A.4

    For each Markov chain i, define a random variable called its surrogate value, denoted Γi. This is exactly our Definition A.4

  113. [125]

    Show that, in MCS, the expected value achieved by any policy π is at most E[Γiπ ], where iπ is the identifier of the Markov chain that π finishes, noting that there is always exactly one such Markov chain under Assumption 3.3(a)

  114. [126]

    Show that the above inequality is in fact an equality when π is the Gittins policy

  115. [127]

    Finally, observe that the Gittins policy always finishes the Markov chain of maximal surrogate value, and thus always obtains surrogate value max i∈{1,...,n} Γi. The economic argument thus gives another interpretation of the value function we derive in Theorem A.7: the expecte...

  116. [2019]

    In Advances in Neural Information Processing Systems (NeurIPS 2019) , Vol

    Differentiable Convex Optimization Layers. In Advances in Neural Information Processing Systems (NeurIPS 2019) , Vol. 32. Curran Associates, Inc., Vancouver, BC, 9562–9574. doi: 10.48550/ arXiv.1910.12430. Cited on page 24. Ziv Scully and Alexander Terenin: The Gittins Index 33

    2019 doi arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.