Four proofs of Gittins' multiarmed bandit theorem

DOI10.1007/S10479-013-1523-0zbMATH Open1348.60065OpenAlexW2109643282MaRDI QIDQ333080FDOQ333080

Authors: 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

Recommendations

• A short proof of the Gittins index theorem
• On the Gittins index for multiarmed bandits
• On Gittins' index theorem in continuous time
• General Gittins index processes in discrete time.
• Multi-armed bandit problem revisited

zbMATH Keywords

linear programmingdynamic programmingGittins indexbandit problems

Mathematics Subject Classification ID

Dynamic programming (90C39) Queueing theory (aspects of probability theory) (60K25) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

Cites Work

• Title not available (Why is that?)
• Arm-acquiring bandits
• On the Gittins index for multiarmed bandits
• Restless bandits, partial conservation laws and indexability
• A \((2/3)n^{3}\) fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain
• Title not available (Why is that?)
• Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
• Title not available (Why is that?)
• Extensions of the multiarmed bandit problem: The discounted case
• Title not available (Why is that?)
• Title not available (Why is that?)
• On an index policy for restless bandits
• Title not available (Why is that?)
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• On duality theory of conic linear problems.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterization and Optimization of Achievable Performance in General Queueing Systems
• Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control
• The Achievable Region Approach to the Optimal Control of Stochastic Systems
• The Multi-Armed Bandit Problem: Decomposition and Computation
• Title not available (Why is that?)
• 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
• 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
• The multi-armed bandit, with constraints
• Title not available (Why is that?)
• 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
• 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
• A generalized Gittins index for a Markov chain and its recursive calculation

Cited In (12)

• Optimal strategies for families of alternative bandit processes
• A Bayesian two-armed bandit model
• Title not available (Why is that?)
• Approximation algorithms for stochastic combinatorial optimization problems
• Robust control of the multi-armed bandit problem
• Technical note -- A note on the equivalence of upper confidence bounds and Gittins indices for patient agents
• A short proof of the Gittins index theorem
• Multi-armed bandit problem revisited
• Gittins' theorem under uncertainty
• Multi-armed bandits under general depreciation and commitment
• Decomposing risk in an exploitation-exploration problem with endogenous termination time
• A lemma on the multiarmed bandit problem

This page was built for publication: Four proofs of Gittins' multiarmed bandit theorem

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