Technical note -- A note on the equivalence of upper confidence bounds and Gittins indices for patient agents

DOI10.1287/OPRE.2020.1987MaRDI QIDQ4994155zbMATH OpenOpenAlexFDO

Authors Daniel Russo

Publication date 17 June 2021

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.04732

zbMATH Keywords

Gittins indexmultiarmed banditsupper confidence bound

Mathematics Subject Classification ID

Bayesian problems; characterization of Bayes procedures (62C10) Decision theory (91B06)

Abstract: This note gives a short, self-contained, proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. I consider a Gaussian multi-armed bandit problem with discount factor $gamma$. The Gittins index of an arm is shown to equal the $gamma$-quantile of the posterior distribution of the arm's mean plus an error term that vanishes as $gammao1$. In this sense, for sufficiently patient agents, a Gittins index measures the highest plausible mean-reward of an arm in a manner equivalent to an upper confidence bound.

Recommendations

• On the Gittins index for multiarmed bandits
• Optimistic Gittins Indices
• Four proofs of Gittins' multiarmed bandit theorem
• A short proof of the Gittins index theorem
• On Gittins' index theorem in continuous time

Cites work

• ASYMPTOTIC BAYES ANALYSIS FOR THE FINITE-HORIZON ONE-ARMED-BANDIT PROBLEM
• Asymptotically efficient adaptive allocation rules
• Computing a classic index for finite-horizon bandits
• Finite-time analysis of the multiarmed bandit problem
• scientific article; zbMATH DE number 3474804 (Why is no real title available?)
• scientific article; zbMATH DE number 6193745 (Why is no real title available?)
• Information relaxations and duality in stochastic dynamic programs
• Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Linearly parameterized bandits
• Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
• On the Gittins index for multiarmed bandits
• Optimal stopping and dynamic allocation
• Uncertainty, Information, and Sequential Experiments

Cited in

(2)

• Optimistic Gittins Indices
• Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization

This page was built for publication: Technical note -- A note on the equivalence of upper confidence bounds and Gittins indices for patient agents

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