Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

• URL: http://arxiv.org/abs/2606.19891v2
• Date: Mon, 22 Jun 2026 03:14:52 GMT
• Title: Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
• Abstract summary: adversarial bandit optimization in the loss functions may be non-smooth.<n>We develop an analysis that controls the additional regret caused by the perturbations.
• Score: 0.6321283533425183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of an underlying convex and $β$-smooth component and an adversarial perturbation that may be chosen after observing the learner's action. The perturbations are subject to a global budget controlling their cumulative magnitude over time. This framework extends the globally budgeted, post-action perturbation model from underlying linear losses to general convex and $β$-smooth losses. For this broader class, we establish expected regret guarantees that explicitly characterize the effect of the perturbation budget. To establish these guarantees, we modify a standard bandit optimization algorithm and develop an analysis that controls the additional regret caused by the perturbations. In the absence of perturbations, our results reduce to regret guarantees for the standard bandit convex optimization setting with $β$-smooth losses.

Related papers

• Outlier-Robust Nonlinear Moving Horizon Estimation using Adaptive Loss Functions [40.32737814489449]
  The proposed approach prioritizes the fitting of uncontaminated data and downweights the contaminated ones.<n>A tuning parameter is incorporated into the framework to control the shape of the loss function for adjusting the estimator's robustness to outliers.<n>The simulation results demonstrate that adaptation occurs in just a few iterations, whereas the traditional behaviour predominates when the measurements are free of outliers.
  arXiv  Detail & Related papers  (2026-04-06T17:06:33Z)
• Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses [0.6321283533425183]
  We study a class of adversarial bandit optimization problems in which the loss functions may be non-smooth.<n>As a special case of our analysis, we recover an improved high-probability for classical bandit optimization.
  arXiv  Detail & Related papers  (2026-03-27T04:33:08Z)
• Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions [3.8469008367869963]
  We introduce Globalized Adversarial Regret Optimization (GARO), a framework that controls adversarial regret.<n>GARO delivers absolute or relative performance guarantees against an oracle with full knowledge of the prediction error.<n>We derive exact tractable reformulations for problems with affine worst-case cost functions and polyhedral norm uncertainty sets.
  arXiv  Detail & Related papers  (2026-03-26T22:39:25Z)
• Tackling Length Inflation Without Trade-offs: Group Relative Reward Rescaling for Reinforcement Learning [74.5532558466687]
  Group Relative Reward Rescaling (GR$3$) is a general, continuous, and reward-dependent gating mechanism.<n> GR$3$maintains training dynamics and downstream performance comparable to standard GRPO.<n>It significantly mitigates length inflation, outperforming state-of-the-art length-regularized baselines.
  arXiv  Detail & Related papers  (2026-03-11T08:41:34Z)
• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner. We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
  arXiv  Detail & Related papers  (2024-08-12T17:08:31Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  We focus on a class of nonsubmodular functions with special structure, and prove regret guarantees for several variants of the online and approximate online bandit gradient descent algorithms. We derive bounds for the agent's regret in the full information and bandit feedback setting, even if the delay between choosing a decision and receiving the incurred cost is unbounded.
  arXiv  Detail & Related papers  (2022-05-15T08:27:12Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  We study the nature of both the optimization and learning problems. We provide an algorithm, namely GCB, guaranteeing sublinear regret at the cost of a potentially linear number of constraints violations. More interestingly, we provide an algorithm, namely GCB_safe(psi,phi), guaranteeing both sublinear pseudo-regret and safety w.h.p. at the cost of accepting tolerances psi and phi.
  arXiv  Detail & Related papers  (2022-01-18T17:24:20Z)
• Bandit Linear Control [0.0]
  We consider the problem of controlling a known linear dynamical system under noise, adversarially chosen costs, and bandit feedback. We present a new and efficient algorithm that, for strongly convex and smooth costs, obtains regret that grows with the square root of the time horizon $T$.
  arXiv  Detail & Related papers  (2020-07-01T21:12:19Z)
• Calibrated Surrogate Losses for Adversarially Robust Classification [92.37268323142307]
  We show that no convex surrogate loss is respect with respect to adversarial 0-1 loss when restricted to linear models. We also show that if the underlying distribution satisfies the Massart's noise condition, convex losses can also be calibrated in the adversarial setting.
  arXiv  Detail & Related papers  (2020-05-28T02:40:42Z)
• Corruption-robust exploration in episodic reinforcement learning [76.19192549843727]
  We study multi-stage episodic reinforcement learning under adversarial corruptions in both the rewards and the transition probabilities of the underlying system. Our framework yields efficient algorithms which attain near-optimal regret in the absence of corruptions. Notably, our work provides the first sublinear regret guarantee which any deviation from purely i.i.d. transitions in the bandit-feedback model for episodic reinforcement learning.
  arXiv  Detail & Related papers  (2019-11-20T03:49:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.