# Budget-Constrained Bandits over General Cost and Reward Distributions

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Feb 2020.

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

- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards](https://mlsanity.com/paper/2306.11455/) (2023)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals](https://mlsanity.com/paper/2306.07071/) (2023)
- [A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback](https://mlsanity.com/paper/2106.05165/) (2021)
- [Engineering Reliable Coding Agents: Evaluating and Operating the System Around the Model](https://mlsanity.com/paper/2608.13867/) (2026)
- [Making the most of your day: online learning for optimal allocation of time](https://mlsanity.com/paper/2102.08087/) (2021)
- [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)
- [On Collaboration in Distributed Parameter Estimation with Resource Constraints](https://mlsanity.com/paper/2307.06442/) (2023)
- [Clustered Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/2308.10722/) (2023)
- [Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs](https://mlsanity.com/paper/2412.15863/) (2024)
- [In-Context Decision Making for Optimizing Complex AutoML Pipelines](https://mlsanity.com/paper/2508.13657/) (2025)
- [Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2605.07171/) (2026)

## Abstract (arXiv)

We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the total cost. The model is general in the sense that it allows correlated and potentially heavy-tailed cost-reward pairs that can take on negative values as required by many applications. We show that if moments of order (2+γ) for some γ > 0 exist for all cost-reward pairs, O(log B) regret is achievable for a budget B>0. In order to achieve tight regret bounds, we propose algorithms that exploit the correlation between the cost and reward of each arm by extracting the common information via linear minimum mean-square error estimation. We prove a regret lower bound for this problem, and show that the proposed algorithms achieve tight problem-dependent regret bounds, which are optimal up to a universal constant factor in the case of jointly Gaussian cost and reward pairs.