# Thompson Sampling for Budgeted Multi-armed Bandits

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2015.

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

- [Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs](https://mlsanity.com/paper/2111.06537/) (2021)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Challenges in Statistical Analysis of Data Collected by a Bandit Algorithm: An Empirical Exploration in Applications to Adaptively Randomized Experiments](https://mlsanity.com/paper/2103.12198/) (2021)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals](https://mlsanity.com/paper/2306.07071/) (2023)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Topological Structure Learning Should Be A Research Priority for LLM-Based Multi-Agent Systems](https://mlsanity.com/paper/2505.22467/) (2025)
- [A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback](https://mlsanity.com/paper/2106.05165/) (2021)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [Incentivized Bandit Learning with Self-Reinforcing User Preferences](https://mlsanity.com/paper/2105.08869/) (2021)
- [MNL-Bandit with Knapsacks: a near-optimal algorithm](https://mlsanity.com/paper/2106.01135/) (2021)
- [Identifying Influential Users in Unknown Social Networks for Adaptive Incentive Allocation Under Budget Restriction](https://mlsanity.com/paper/2107.05992/) (2021)
- [GAC: A Deep Reinforcement Learning Model Toward User Incentivization in Unknown Social Networks](https://mlsanity.com/paper/2203.09578/) (2022)
- [Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/2408.15535/) (2024)
- [On Penalization in Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.08311/) (2022)
- [Leveraging User-Triggered Supervision in Contextual Bandits](https://mlsanity.com/paper/2302.03784/) (2023)
- [MADDM: Multi-Advisor Dynamic Binary Decision-Making by Maximizing the Utility](https://mlsanity.com/paper/2305.08664/) (2023)
- [Balancing Risk and Reward: An Automated Phased Release Strategy](https://mlsanity.com/paper/2305.09626/) (2023)
- [AExGym: Benchmarks and Environments for Adaptive Experimentation](https://mlsanity.com/paper/2408.04531/) (2024)
- [In-Context Decision Making for Optimizing Complex AutoML Pipelines](https://mlsanity.com/paper/2508.13657/) (2025)
- [Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making](https://mlsanity.com/paper/2604.26169/) (2026)
- [402Pilot: An x402 Decision Layer for Autonomous Agent Micropayments](https://mlsanity.com/paper/2608.01341/) (2026)
- [Disentangling Task Difficulty from Run-Level Failure in Agent Failure Prediction](https://mlsanity.com/paper/2610.05572/) (2026)

## Abstract (arXiv)

Thompson sampling is one of the earliest randomized algorithms for multi-armed bandits (MAB). In this paper, we extend the Thompson sampling to Budgeted MAB, where there is random cost for pulling an arm and the total cost is constrained by a budget. We start with the case of Bernoulli bandits, in which the random rewards (costs) of an arm are independently sampled from a Bernoulli distribution. To implement the Thompson sampling algorithm in this case, at each round, we sample two numbers from the posterior distributions of the reward and cost for each arm, obtain their ratio, select the arm with the maximum ratio, and then update the posterior distributions. We prove that the distribution-dependent regret bound of this algorithm is O(ln B), where B denotes the budget. By introducing a Bernoulli trial, we further extend this algorithm to the setting that the rewards (costs) are drawn from general distributions, and prove that its regret bound remains almost the same. Our simulation results demonstrate the effectiveness of the proposed algorithm.