# Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 12 Jun 2023.

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

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Budget-Constrained Bandits over General Cost and Reward Distributions](https://mlsanity.com/paper/2003.00365/) (2020)

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

- [Multi-Drafter Speculative Decoding with Alignment Feedback](https://mlsanity.com/paper/2604.05417/) (2026)
- [Learning to Schedule Online Tasks with Bandit Feedback](https://mlsanity.com/paper/2402.16463/) (2024)
- [Causal Feature Selection Method for Contextual Multi-Armed Bandits in Recommender System](https://mlsanity.com/paper/2409.13888/) (2024)
- [A Unified Online-Offline Framework for Co-Branding Campaign Recommendations](https://mlsanity.com/paper/2505.22254/) (2025)
- [Best Agent Identification for General Game Playing](https://mlsanity.com/paper/2507.00451/) (2025)
- [From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing](https://mlsanity.com/paper/2607.13546/) (2026)

## Abstract (arXiv)

We study the stochastic Budgeted Multi-Armed Bandit (MAB) problem, where a player chooses from K arms with unknown expected rewards and costs. The goal is to maximize the total reward under a budget constraint. A player thus seeks to choose the arm with the highest reward-cost ratio as often as possible. Current state-of-the-art policies for this problem have several issues, which we illustrate. To overcome them, we propose a new upper confidence bound (UCB) sampling policy, ω-UCB, that uses asymmetric confidence intervals. These intervals scale with the distance between the sample mean and the bounds of a random variable, yielding a more accurate and tight estimation of the reward-cost ratio compared to our competitors. We show that our approach has logarithmic regret and consistently outperforms existing policies in synthetic and real settings.