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

May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

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.

Dhruv Sarkar, Abhishek Sinha

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

Contextual Bandits Adversarial Bandits

Ask PDF

Sep 29, 2026

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

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

Aug 11, 2026

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of

O(\frac{(\ln T)^3}{T})

where

T

is the horizon length. Our bound significantly reduces the

O(\frac{1}{\sqrt{T}})

bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.

Zhen Xu

Management School, University of Liverpool, Liverpool, United Kingdom

Contextual Bandits UCB Algorithms Linear Contextual Bandits

Ask PDF