Bandits with Anytime Knapsacks

Eray Can Elumar; Cem Tekin; Osman Yagan

cs.LGJan 30, 2025

Bandits with Anytime Knapsacks

Authors: Eray Can Elumar, Cem Tekin, Osman Yagan

Organizations: Dept. of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA · Dept. of Electrical Engineering Bilkent University Ankara, Turkey

Abstract

We consider bandits with anytime knapsacks (BwAK), a novel version of the BwK problem where there is an anytime cost constraint instead of a total cost budget. This problem setting introduces additional complexities as it mandates adherence to the constraint throughout the decision-making process. We propose SUAK (Strategic Under-utilization for Anytime Knapsacks), an algorithm that utilizes upper confidence bounds to identify the optimal mixture of arms while maintaining a balance between exploration and exploitation. SUAK is an adaptive algorithm that strategically utilizes the available budget in each round in the decision-making process and skips a round when it is possible to violate the anytime cost constraint. In particular, SUAK slightly under-utilizes the available cost budget to reduce the need for skipping rounds. We show that SUAK attains the same problem-dependent regret upper bound of $O(K \log T)$ established in prior work under the simpler BwK framework, where $K$ denotes the number of arms, and $T$ denotes the time horizon. We also establish an instance-dependent lower bound showing that the $O(K\log T)$ dependence is unavoidable. Finally, we show via extensive simulations that SUAK achieves considerably higher rewards than naive adaptations of BwK algorithms that do not optimize learning under anytime cost constraints.

Figures & tables

$K$	number of non-null arms
$\mathcal{A}=[K]\cup\{\bot\}$	action set, i.e. the set of all arms including the null arm $\bot$
$\bm{\rho}$	mean cost vector indexed by $\mathcal{A}$
$\bm{\mu}$	mean reward vector indexed by $\mathcal{A}$
$\mathds{V}$	set of canonical feasible LP vertices (bases), as defined in ( 10 )
$\rho_{i}(t)$	realized cost of arm $i$ in round $t$
$c(t)=\rho_{i(t)}(t)$	cost incurred in round $t$

Table 1: Notations

Work	Model	Regret Bound
Our work	Shared stochastic cost; hard prefix budget	$O\!\left(\frac{K\log T}{\delta_{\min}^{3}\Delta_{\min}}+\frac{\nu^{*}K\log T}{c\delta_{\min}^{3}}+\frac{K\log T}{c\delta_{\min}^{2}}\right)+O(1)$
Combes et al. (2015)	Arm-specific evolving budgets	$O(\log T)$
Bernasconi et al. (2024b)	BwRK with sublinear violations	$O\left(\sqrt{T}\right)$
Kumar and Kleinberg (2022)	Non-monotonic resource drift	$\widetilde{C}\log T$ , where $\widetilde{C}$ includes $\frac{Km^{2}}{\Delta^{2}\min\{\delta_{\rm drift}^{2},\sigma_{\min}^{2}\}}$ , $K(\gamma^{*})^{-2}$ , and control terms
Li et al. (2021)	Total budget	$O\left(\frac{Kd\log T}{b^{3}\Delta^{2}}+\frac{d^{4}}{b^{2}\min\left\{\chi^{2},\Delta^{2}\right\}\min\left\{1,\sigma^{2}\right\}}\right)$
Flajolet and Jaillet (2015)	Total budget	$O\left(\frac{\lambda^{2}K^{2}\log T}{\delta_{\min}^{3}\Delta}+\frac{K^{2}\sigma\log T}{\delta_{\min}^{3}}\right)$

Table 2: Comparison of our work with prior work on bandits with knapsacks

Panel of Figure 1 — Figure 1: Plots of cumulative empirical regret (top left), number of skips (top right), and average empirical cost deviation $\bar{c}(t)-c$ (bottom).

Panel of Figure 2 — Figure 2: Plots of cumulative empirical regret (top row), number of skips (bottom left), and average empirical cost deviation $\bar{c}(t)-c$ (bottom right). Null-arm pulls caused by dedicated or global skip branches are counted as skips; null-arm pulls selected within an LP base are not.

Explore similar work

Constrained Contextual Bandits with Adversarial Contexts
May 7, 2026Dhruv Sarkar, Abhishek SinhaContextual Bandits Adversarial Bandits
Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Sep 29, 2026Kaixuan Ji, Qiwei Di, Qingyue Zhao +2Multi-Armed Bandits Minimax Regret
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
Aug 11, 2026Zhen XuContextual Bandits UCB Algorithms
Management School, University of Liverpool, Liverpool, United Kingdom

May 7, 2026J/K move · Enter open · S save

Constrained Contextual Bandits with Adversarial Contexts

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Contextual Bandits Adversarial Bandits

Open paper AskPDF arXiv

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal

\mathsf{SquareCB}

algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most

U_T

, our algorithm achieves

O(\sqrt{KTU_T})

regret and

O(\sqrt{KTU_T}\log T)

cumulative expected cost, with high probability, improving upon the previous

O(T^{3/4})

type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.

Abstract

Explore similar work

Constrained Contextual Bandits with Adversarial Contexts

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints