A generalized Gittins index for a Markov chain and its recursive calculation

DOI10.1016/j.spl.2008.01.049zbMath1146.60057OpenAlexW2166619657WikidataQ56001618 ScholiaQ56001618MaRDI QIDQ945795

Isaac M. Sonin

Publication date: 17 September 2008

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.spl.2008.01.049

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Markov and semi-Markov decision processes (90C40) Optimal stopping in statistics (62L15)

Related Items (11)

Open Bandit Processes with Uncountable States and Time-Backward Effects ⋮ Four proofs of Gittins' multiarmed bandit theorem ⋮ Continue, quit, restart probability model ⋮ The multi-armed bandit, with constraints ⋮ Optimal activation of halting multi‐armed bandit models ⋮ Index policy for multiarmed bandit problem with dynamic risk measures ⋮ Testing indexability and computing Whittle and Gittins index in subcubic time ⋮ MULTI-ARMED BANDITS UNDER GENERAL DEPRECIATION AND COMMITMENT ⋮ Stochastic scheduling: a short history of index policies and new approaches to index generation for dynamic resource allocation ⋮ Optimal stopping of Markov chains and three abstract optimization problems ⋮ Parallel computing for Markov chains with islands and ports

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Continuous multi-armed bandits and multiparameter processes
• The elimination algorithm for the problem of optimal stopping
• The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem
• A short proof of the Gittins index theorem
• A stochastic representation theorem with applications to optimization and obstacle problems.
• A (2/3)n³ Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain
• State reduction in a Markov decision process
• Branching Bandit Processes
• Extensions of the multiarmed bandit problem: The discounted case
• The Multi-Armed Bandit Problem: Decomposition and Computation
• A Note on Bandits with a Twist
• General Gittins index processes in discrete time.
• Increasing the reliability of a machine reduces the period of its work
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• Optimal Sequencing and Resource Allocation in Research and Development Projects
• Index Policies for Stochastic Search in a Forest with an Application to R&D Project Management

This page was built for publication: A generalized Gittins index for a Markov chain and its recursive calculation