A (2/3)n^3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain

DOI10.1287/IJOC.1060.0206MaRDI QIDQ2892371zbMATH OpenOpenAlexWikidataFDO

Authors José Niño-Mora

Publication date 18 June 2012

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.1060.0206

zbMATH Keywords

computational complexitydynamic programmingGittins indexMarkov finite state

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Numerical analysis or methods applied to Markov chains (65C40) Markov and semi-Markov decision processes (90C40)

Recommendations

• A generalized Gittins index for a Markov chain and its recursive calculation
• scientific article; zbMATH DE number 775000
• On the Gittins index for multiarmed bandits
• Computing a classic index for finite-horizon bandits
• General Gittins index processes in discrete time.

Cited in

(16)

• Linear programming relaxations and marginal productivity index policies for the buffer sharing problem
• Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges
• Computing a classic index for finite-horizon bandits
• Optimal stopping of Markov chains and three abstract optimization problems
• Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic
• Four proofs of Gittins' multiarmed bandit theorem
• A Note on M. N. Katehakis' and Y.-R. Chen's Computation of the Gittins Index
• The multi-armed bandit, with constraints
• Optimal policies for observing time series and related restless bandit problems
• Optimistic Gittins Indices
• Testing indexability and computing Whittle and Gittins index in subcubic time
• A general approximation method for optimal stopping and random delay
• A confirmation of a conjecture on Feldman’s two-armed bandit problem
• A $(2/3)n^3$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain
• Dynamic priority allocation via restless bandit marginal productivity indices
• A generalized Gittins index for a Markov chain and its recursive calculation

This page was built for publication: A \((2/3)n^{3}\) fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2892371)