# Efficient and Adaptive Posterior Sampling Algorithms for Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 17 references that are in the map.
- First posted on arXiv 2 May 2024.

## Builds on (most cited first, 4 of 4)

- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)

## Abstract (arXiv)

We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when T ≤ 288 e64, we derive a more practical bound that tightens the coefficient of the leading term %from 288 e64 to 1270. Additionally, motivated by large-scale real-world applications that require scalability, adaptive computational resource allocation, and a balance in utility and computation, we propose two parameterized Thompson Sampling-based algorithms: Thompson Sampling with Model Aggregation (TS-MA-α) and Thompson Sampling with Timestamp Duelling (TS-TD-α), where α ∈ [0,1] controls the trade-off between utility and computation. Both algorithms achieve O left(Klnα+1(T)/Delta right) regret bound, where K is the number of arms, T is the finite learning horizon, and Delta denotes the single round performance loss when pulling a sub-optimal arm.