A (2/3)n3 Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain

DOI10.1287/ijoc.1060.0206zbMath1241.90174OpenAlexW2103783883WikidataQ56001619 ScholiaQ56001619MaRDI QIDQ2892371

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

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

Related Items (12)

Optimistic Gittins Indices ⋮ Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic ⋮ Four proofs of Gittins' multiarmed bandit theorem ⋮ The multi-armed bandit, with constraints ⋮ 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 ⋮ Dynamic priority allocation via restless bandit marginal productivity indices ⋮ A generalized Gittins index for a Markov chain and its recursive calculation ⋮ Linear programming relaxations and marginal productivity index policies for the buffer sharing problem ⋮ Unnamed Item ⋮ Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges

This page was built for publication: A (2/3)n³ Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain