CS Paper Radar

Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints

Yige Wang, Hanyang Li, Yiming Zong, Wanteng Ma, Jiashuo Jiang

cs.LG ·submitted 2026-09-29 10:10 UTC · v1
benchmark

Abstract

We study sparse linear contextual bandits with knapsack constraints under joint reward and consumption corruption. Consumption corruption creates a challenge beyond corrupted rewards: it affects not only statistical estimates, but also the recorded budget, resource prices, and stopping decisions that govern future allocation. We develop Robust Optimistic Primal--Dual (ROPD), an estimator-modular framework that combines corruption-aware confidence widths with online resource prices and a budget-safety rule. With concrete sparse implementation, ROPD achieves regret against a clean population-LP benchmark of $\widetilde O(T^{2/3}+ΓT^{1/3})$ under forced exploration and population-design coverage, and $\widetilde O(\sqrt T+Γ)$ under on-policy realized-design coverage, for a supplied valid corruption bound $Γ$ under the stated proportional-budget scaling and fixed model/design parameters. When the corruption level is unknown, Shared-Grid adapts confidence radii around common point estimates fitted to a single realized history, incurring explicit initialization and master-comparison costs; its sharper on-policy guarantee additionally requires recommendation coverage. Both methods preserve observed budgets on every realization and bound clean resource violation by cumulative consumption corruption. These results connect corruption-robust sparse estimation with resource accounting, pricing, and stopping in high-dimensional online allocation.

Closest papers

Nearest neighbours by meaning across the whole index.

Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

cs.LG stat.ML ·2026-10-28 ·Qiwei Di, Quanquan Gu
theory similarity 0.69
Abstract · 39 pages, 1 table

We study adversarial linear bandits with strong corruption, in which an adaptive adversary chooses the reward vectors and a strong adversary corrupts each observed reward after seeing the learner's action, subject to a known total corruption budget $C$. Strong corruption breaks the importance-weighted reward estimates used by adversarial bandit algorithms: by corrupting only the rounds in which a rarely sampled action is drawn, the adversary amplifies each unit of corruption by the inverse of its sampling probability. The best known bound for this problem, $\tilde O(\sqrt{d^3T} + dC)$ by Liu et al. (2024), is a factor $\sqrt{d}$ above the corruption-free rate in its leading term, and whether $\tilde O(d\sqrt{T} + dC)$ regret is achievable was left open. We propose CRW-FTRL, which runs follow-the-regularized-leader with a radius-weighted entropy regularizer and estimates rewards with a normalized kernel estimator whose sensitivity to corruption is governed by per-action radii instead of inverse sampling probabilities. The radii are nondecreasing and are chosen jointly with the sampling distribution through a monotone log-determinant barrier problem, so that a negative linear term in the regularizer cancels both the corruption bias and the estimation error of every comparator. For $K$ actions in $\mathbb{R}^d$, CRW-FTRL achieves $\tilde O(\sqrt{dT\log K} + dC)$ regret with high probability against an adaptive adversary, which matches the best known corruption-free rate and the $Ω(dC)$ lower bound up to logarithmic factors. Applied to a discretization of a general compact action set, it yields $\tilde O(d\sqrt{T} + dC)$ regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.

0.17

Budgeted Bayesian Bandits for Future Utilization

cs.LG cs.DS ·2026-10-16 ·Sudipto Guha
similarity 0.67
Abstract

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.

0.14

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

cs.LG ·2026-08-27 ·Spyros Dragazis, Aldo Pacchiano
theory similarity 0.66
Abstract

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight $\tilde{\mathcal{O}}(d\sqrt{T})$ regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

0.08

Cancellation-Free Constrained SquareCB for Safe Controller Selection

cs.LG cs.AIstat.ML ·2026-11-16 ·Kartik Pandit, Sourav Ganguly, Arnob Ghosh
similarity 0.64
Abstract

We study constrained contextual bandits, in which a learner chooses one of $K$ actions in each round to minimize loss while keeping the expected cost of its play below a budget. Existing reductions to online regression weight the cost by a Lagrange multiplier learned from past constraint residuals, so slack in some rounds can offset violations in others. We instead run SquareCB proposed in \citep{foster2020beyond} with a rectified weight on the cost: it is zero when the estimated cost is within the budget, and otherwise just large enough to bring it back to the budget. Under realizability and Slater's condition with margin $δ$, the algorithm attains regret $O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)}/δ)$ and cancellation-free violation $\sum_t(V_c^{p_t}-b)^+=O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)})$, where $\mathrm{Reg}_{\mathsf{Sq}}$ is the error of the regression oracle. The same bounds hold when the budget must be met in every context, potentially adversarially chosen contexts. In controller selection for a safe-control-gym quadrotor and a BOPTEST building, the violation is 6 to 9 times lower than that of primal-dual and virtual-queue baselines, with a lower or comparable regret.

0.07

Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits

cs.LG stat.ML ·2026-10-15 ·Spyros Dragazis, Yilei Chen, Aldo Pacchiano
theory similarity 0.64
Abstract

We study how to evaluate $K$ target policies simultaneously in stochastic contextual bandits with linear reward structure. Given a known $d$-dimensional feature map and reward-free access to policy queries, we propose PRISMA (Policy evaluation through Regularized Information Sharing and Mixture Allocation), an algorithm that estimates every target policy's value to accuracy $\varepsilon$ with probability at least $1-δ$. The algorithm uses $\widetilde{\mathcal{O}}\!\left( \frac{(L^2S^2+β^2)(1\veeρ^\star)}{\varepsilon^2} \cdot \log(K) \right)$ context draws and reward observations, where $ρ^\star\le d$ is an instance-dependent measure of the difficulty of designing a shared sampling distribution. Here, $L$, $S$, and $β$ bound the feature norm, reward parameter norm, and reward noise, respectively, and the suppressed factors are logarithmic in $K$, $d$, and $1/δ$. Our method combines reward-free planning, a regularized sampling design, and a single ridge regression estimator shared across all target policies. An adaptive doubling procedure selects the regularization scale without knowledge of $ρ^\star$. The guarantees require no numerical lower bound on second-moment eigenvalues and have no explicit dependence on the cardinalities of the context and action spaces. Policy-query costs are accounted for separately, with $K$ queries per shared planning context.

0.17

Action-Centered Causal Bandits for Budget-Constrained Promotion Targeting

cs.LG ·2026-11-06 ·Yifan Lin, Kaixu Yang, Di Mo
publishedbenchmarktheory similarity 0.64
Abstract · Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM 2027)

Web platforms select among costly interventions for each user to maximize incremental outcomes under a global budget. We formulate this problem as a budget-constrained contextual bandit with heterogeneous treatment effects. Although an action-independent outcome baseline cancels from treatment comparisons, modeling a nonlinear baseline can increase statistical complexity. We propose DR-CATE-CBwK, an action-centered causal bandit that directly learns treatment contrasts. Its online update remains valid under baseline-model misspecification without inverse-propensity weighting. It combines an offline doubly robust learner to warm-start treatment-effect estimates, an online action-centered estimator for sequential contrast learning, and a primal-dual controller with an affordable-action rule to enforce the effective-cost budget pathwise. For linear conditional average treatment effects (CATEs) in a stationary i.i.d. setting, we prove a high-probability (\widetilde{O}(Kd\sqrt{T})) regret bound, where K is the number of priced actions, d the context dimension, and T the horizon. We benchmark against the fluid linear program (LP) under the coverage-guaranteed action rule. We further show that the action-centered estimating moment remains unbiased under any predictable baseline estimate, whereas a specified separate-arm reward regression can exhibit asymptotic contrast bias under action-dependent logging and shared-baseline misspecification. On a semi-synthetic job-marketplace benchmark with real logged features and simulated outcomes, our practical Thompson-restricted variant achieves the lowest regret among evaluated budget-feasible methods in the operating regime. It reduces regret by approximately 20% versus the strongest reward-based baseline, outperforming raw-reward contextual bandits, BwK baselines, and a static offline policy, while never exceeding the effective-cost budget.

0.27

Adaptive Budgeted Data Acquisition for Robust Off-Policy Evaluation from Multiple Loggers

cs.LG stat.ML ·2026-11-06 ·Amitakshar Biswas, Ruoqing Zhu
similarity 0.63
Abstract

We consider off-policy evaluation when additional data can be purchased from several existing logging policies (or loggers) with heterogeneous costs per observation. While existing work on multiple loggers presumes a fixed number of observations from each logger, we study how to allocate a limited budget across them sequentially to evaluate a finite class of target policies. We propose Adaptive Greedy, an algorithm that purchases observations sequentially from the affordable logger that has the most cost-normalized variance reduction across the target policies. It turns out that each such purchase is an 'approximate conditional-gradient step' for the corresponding design problem. Under mild assumptions, we establish that the empirical allocation converges almost surely to the optimal design at an explicit rate. We also derive the asymptotic normality of the final pooled estimator and show that it attains the semiparametric efficiency bound. Simulations and a semi-synthetic application based on the AIDS Clinical Trials Group Study 175 show that Adaptive Greedy outperforms standard allocation strategies, remains accurate if stopped early, and matches the final accuracy of repeated integer programming at a fraction of its computational cost.

0.10

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

cs.AI cs.IT ·2026-09-24 ·Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu +3 more
benchmarkhot direction similarity 0.63
Abstract

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of $M$ tasks with $L$ binary paths per task under the hard budget $(M+t)K$, where each path costs at most $K$ responses or episodes. For fixed $L \ge 3$ and $0 < α\le 1/12$, the optimal expected width on the worst pure cohort is $Θ_{α,L}([M(t+1)]^{-1/2})$ when every task is observed and $Θ_{α,L}([M(t+\sqrt{M})]^{-1/2})$ when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0\% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6\%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.

0.57