Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

Ishank Juneja; Carlee Joe-Wong; Osman Yağan

cs.LGMay 8, 2026

Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

Authors: Ishank Juneja, Carlee Joe-Wong, Osman Yağan

Organizations: Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA 15213

Abstract

The classic multi-armed bandit (MAB) problem tackles the challenge of accruing maximum reward while making decisions under uncertainty. However, in applications, often the goal is to minimize cost subject to a constraint on the minimum permissible reward, an objective captured by multi-armed bandits with cost-subsidy (MAB-CS). Of interest to this paper is the setting where the quality (reward) constraint is specified relative to the unknown best reward and the cost of each arm is known. We characterize the expected sub-optimal samples required by any policy by proving instance-dependent lower bounds that offer new insight into the problem and are a strict generalization of prior bounds. Then, we propose an algorithm called Cost-Ordered Feasibility (COF) that leverages our insight and intelligently combine samples from all arms to gauge the feasibility of a cheap arm. Thereafter, we analyze COF to establish instance-dependent upper bounds on its expected cumulative cost and quality regret, i.e., relative to the cheapest feasible arm. Finally, we empirically validate the merits of COF, comparing it to baselines from the literature through extensive simulation experiments on the MovieLens and Goodreads datasets as well as representative synthetic instances. Not only does our paper develop qualitatively better theoretical regret upper bounds, but COF also convincingly demonstrates improved empirical performance.

Explore similar work

May 8, 2026cs.LG

Multi-Armed Bandits With Best-Action Queries

We study \emph{multi-armed bandits} (MABs) augmented with \emph{best-action queries}, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the \emph{full-feedback} model, where the learner observes the rewards of all arms after each round. They show that, in both \emph{stochastic} and \emph{adversarial} environments,

k

best-action queries reduce the optimal

\widetilde{\mathcal{O}}(\sqrt{T})

regret to

\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})

. Whether this improvement extends to the more realistic \emph{bandit-feedback} model -- where the learner observes only the reward of the played arm -- was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least

Ω(\sqrt{T-k})

. This lower bound directly extends to adversarial environments. On the positive side, we show that

\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})

regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of \emph{best-action queries} in the \emph{bandit-feedback} model.

Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1

Multi-Armed Bandits O(T^Β)$ Simultaneous Regret Adversaries

Ask PDF

May 1, 2026cs.LG

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Multi-Armed Bandits Regret Trade-Off Errors

Ask PDF

May 7, 2026cs.LG

Constrained Contextual Bandits with Adversarial Contexts

We study budget-constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. We adopt the standard realizability assumption: conditioned on the observed context, rewards and costs are drawn independently from fixed distributions whose expectations belong to known function classes. We focus on the continuing setting, in which the algorithm operates over the entire horizon even after the budget for cumulative cost is exhausted. In this setting, the objective is to simultaneously control regret and the violation of the budget constraint. Building on the seminal

\mathsf{SquareCB}

framework of Foster et al. [2018], we propose a simple and modular framework that leverages online regression oracles to reduce the constrained problem to a standard unconstrained contextual bandit problem with adaptively defined surrogate reward functions. In contrast to prior works, which focus on stochastic contexts, our reduction yields improved guarantees for more general adversarial contexts, together with an efficient algorithm with a compact and transparent analysis.

Dhruv Sarkar, Abhishek Sinha

Linear Contextual Bandits Optimal Bandit Algorithms Token Budgets Adversaries Random

Ask PDF