# Confidence-Budget Matching for Sequential Budgeted Learning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 5 Feb 2021.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [No-Regret Exploration in Goal-Oriented Reinforcement Learning](https://mlsanity.com/paper/1912.03517/) (2019)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [Multi-armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2011.01488/) (2020)

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

- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Reinforcement Learning with History-Dependent Dynamic Contexts](https://mlsanity.com/paper/2302.02061/) (2023)
- [Cooperative Online Learning in Stochastic and Adversarial MDPs](https://mlsanity.com/paper/2201.13170/) (2022)
- [Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback](https://mlsanity.com/paper/2505.24193/) (2025)
- [Query-Reward Tradeoffs in Multi-Armed Bandits](https://mlsanity.com/paper/2110.05724/) (2021)
- [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)
- [Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching](https://mlsanity.com/paper/2601.10418/) (2026)
- [Near-Optimal Stochastic Linear Bandits with Delay](https://mlsanity.com/paper/2606.16656/) (2026)
- [Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback](https://mlsanity.com/paper/2610.17760/) (2026)

## Abstract (arXiv)

A core element in decision-making under uncertainty is the feedback on the quality of the performed actions. However, in many applications, such feedback is restricted. For example, in recommendation systems, repeatedly asking the user to provide feedback on the quality of recommendations will annoy them. In this work, we formalize decision-making problems with querying budget, where there is a (possibly time-dependent) hard limit on the number of reward queries allowed. Specifically, we consider multi-armed bandits, linear bandits, and reinforcement learning problems. We start by analyzing the performance of `greedy' algorithms that query a reward whenever they can. We show that in fully stochastic settings, doing so performs surprisingly well, but in the presence of any adversity, this might lead to linear regret. To overcome this issue, we propose the Confidence-Budget Matching (CBM) principle that queries rewards when the confidence intervals are wider than the inverse square root of the available budget. We analyze the performance of CBM based algorithms in different settings and show that they perform well in the presence of adversity in the contexts, initial states, and budgets.