# On Bayesian index policies for sequential resource allocation

arXiv: https://arxiv.org/abs/1601.01190 · HTML: https://mlsanity.com/paper/1601.01190/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2016.

## Built on by (most cited first, 18 of 18)

- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [An empirical evaluation of active inference in multi-armed bandits](https://mlsanity.com/paper/2101.08699/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits](https://mlsanity.com/paper/2302.01544/) (2023)
- [Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework](https://mlsanity.com/paper/2201.12955/) (2022)
- [Transfer Learning in Bandits with Latent Continuity](https://mlsanity.com/paper/2102.02472/) (2021)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averages](https://mlsanity.com/paper/2308.14350/) (2023)
- [On Lai's Upper Confidence Bound in Multi-Armed Bandits](https://mlsanity.com/paper/2410.02279/) (2024)
- [Communication Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2501.03132/) (2025)
- [A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles](https://mlsanity.com/paper/2301.07156/) (2023)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)
- [Situational-Constrained Sequential Resources Allocation via Reinforcement Learning](https://mlsanity.com/paper/2506.14125/) (2025)
- [Annealed Softmax Greedy in Many-Armed Bayesian Bandits](https://mlsanity.com/paper/2605.31034/) (2026)

## Abstract (arXiv)

This paper is about index policies for minimizing (frequentist) regret in a stochastic multi-armed bandit model, inspired by a Bayesian view on the problem. Our main contribution is to prove that the Bayes-UCB algorithm, which relies on quantiles of posterior distributions, is asymptotically optimal when the reward distributions belong to a one-dimensional exponential family, for a large class of prior distributions. We also show that the Bayesian literature gives new insight on what kind of exploration rates could be used in frequentist, UCB-type algorithms. Indeed, approximations of the Bayesian optimal solution or the Finite Horizon Gittins indices provide a justification for the kl-UCB+ and kl-UCB-H+ algorithms, whose asymptotic optimality is also established.