Four proofs of Gittins' multiarmed bandit theorem

DOI10.1007/s10479-013-1523-0zbMath1348.60065MaRDI QIDQ333080

Esther Frostig, Gideon Weiss

Publication date: 9 November 2016

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-013-1523-0

zbMATH Keywords

linear programming; dynamic programming; Gittins index; bandit problems

Mathematics Subject Classification ID

60K25: Queueing theory (aspects of probability theory)

90C39: Dynamic programming

60G40: Stopping times; optimal stopping problems; gambling theory

90C40: Markov and semi-Markov decision processes

Related Items

MULTI-ARMED BANDITS UNDER GENERAL DEPRECIATION AND COMMITMENT, Approximation algorithms for stochastic combinatorial optimization problems, Decomposing risk in an exploitation-exploration problem with endogenous termination time, Gittins' theorem under uncertainty, Robust control of the multi-armed bandit problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The multi-armed bandit, with constraints
• A generalized Gittins index for a Markov chain and its recursive calculation
• Arm-acquiring bandits
• On the Gittins index for multiarmed bandits
• Multiple feedback at a single-server station
• Multi-armed bandits in discrete and continuous time
• Discrete multiarmed bandits and multiparameter processes
• A short proof of the Gittins index theorem
• Multi-armed bandit problem revisited
• Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach
• Almost optimal policies for stochastic systems which almost satisfy conservation laws
• Finite state multi-armed bandit problems: Sensitive-discount, average-reward and average-overtaking optimality
• Restless bandits, partial conservation laws and indexability
• A (2/3)n³ Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain
• Multi‐Armed Bandit Allocation Indices
• Scheduling for Minimum Total Loss Using Service Time Distributions
• Addendum to ‘On an index policy for restless bandits'
• Branching Bandit Processes
• Parallel Scheduling of Multiclass M/M/m Queues: Approximate and Heavy-Traffic Optimization of Achievable Performance
• Extensions of the multiarmed bandit problem: The discounted case
• The Multi-Armed Bandit Problem: Decomposition and Computation
• Characterization and Optimization of Achievable Performance in General Queueing Systems
• On an index policy for restless bandits
• Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control
• Dynamic Scheduling of a Multiclass Queue: Discount Optimality
• Optimal Control of Single-Server Queuing Networks and Multi-Class M/G/1 Queues with Feedback
• Time-Sharing Service Systems. I
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• The Achievable Region Approach to the Optimal Control of Stochastic Systems
• Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues
• Risk-Sensitive and Risk-Neutral Multiarmed Bandits