# Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 21 references that are in the map.
- First posted on arXiv 28 Aug 2024.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Policy Gradient Optimization of Thompson Sampling Policies](https://mlsanity.com/paper/2006.16507/) (2020)
- [Thompson Sampling with Information Relaxation Penalties](https://mlsanity.com/paper/1902.04251/) (2019)

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

- [Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making](https://mlsanity.com/paper/2604.26169/) (2026)

## Abstract (arXiv)

We consider a Bayesian budgeted multi-armed bandit problem, in which each arm consumes a different amount of resources when selected and there is a budget constraint on the total amount of resources that can be used. Budgeted Thompson Sampling (BTS) offers a very effective heuristic to this problem, but its arm-selection rule does not take into account the remaining budget information. We adopt textitInformation Relaxation Sampling framework that generalizes Thompson Sampling for classical K-armed bandit problems, and propose a series of algorithms that are randomized like BTS but more carefully optimize their decisions with respect to the budget constraint. In a one-to-one correspondence with these algorithms, a series of performance benchmarks that improve the conventional benchmark are also suggested. Our theoretical analysis and simulation results show that our algorithms (and our benchmarks) make incremental improvements over BTS (respectively, the conventional benchmark) across various settings including a real-world example.