Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

• URL: http://arxiv.org/abs/2603.26066v1
• Date: Fri, 27 Mar 2026 04:33:08 GMT
• Title: Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses
• Abstract summary: 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.
• Score: 0.6321283533425183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a class of adversarial bandit optimization problems in which the loss functions may be non-convex and non-smooth. In each round, the learner observes a loss that consists of an underlying linear component together with an additional perturbation applied after the learner selects an action. The perturbations are measured relative to the linear losses and are constrained by a global budget that bounds their cumulative magnitude over time. Under this model, we establish both expected and high-probability regret guarantees. As a special case of our analysis, we recover an improved high-probability regret bound for classical bandit linear optimization, which corresponds to the setting without perturbations. We further complement our upper bounds by proving a lower bound on the expected regret.

Related papers

• Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses [0.6321283533425183]
  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.
  arXiv  Detail & Related papers  (2026-06-18T07:48:26Z)
• A Perturbation Approach to Unconstrained Linear Bandits [48.45987210959519]
  We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO)<n>We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem.
  arXiv  Detail & Related papers  (2026-03-30T09:17:46Z)
• The Hidden Cost of Approximation in Online Mirror Descent [56.99972253009168]
  Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making.<n>In this work we initiate a systematic study into inexact OMD, and uncover an intricate relation between regularizer smoothness and robustness to approximation errors.
  arXiv  Detail & Related papers  (2025-11-27T10:09:07Z)
• Adversarial bandit optimization for approximately linear functions [0.6321283533425183]
  We consider a bandit optimization problem for non-smooth and non-smooth functions.<n>In each trial the loss function is the sum of a linear function and a small but arbitrary perturbation chosen after observing the player's choice.<n>Our result implies an improved high-probability regret bound for optimization.
  arXiv  Detail & Related papers  (2025-05-27T05:22:01Z)
• Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses [17.368130636104354]
  We construct a convex smooth surrogate loss with a linear regret bound composed with a tailored prediction link.<n>The construction is based on Fenchel-Young losses generated by the convolutional negentropy.<n>Our results are a novel demonstration of how convex analysis penetrates into optimization and statistical efficiency in risk minimization.
  arXiv  Detail & Related papers  (2025-05-14T14:37:32Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  We quantify the excess risk incurred using approximate posterior probabilities in batch binary decision-making.<n>We identify regimes where recalibration alone addresses most of the regret, and regimes where the regret is dominated by the grouping loss.<n>On NLP experiments, we show that these quantities identify when the expected gain of more advanced post-training is worth the operational cost.
  arXiv  Detail & Related papers  (2025-03-23T10:52:36Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• 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)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [6.1866042321432175]
  We establish novel regret bounds for online convex optimization in a setting that interpolates between i.i.d. and fully adversarial losses.<n>In the fully i.i.d. case, our regret bounds match the rates one would expect from results in acceleration, and we also recover the optimalally accelerated rates via online-to-batch conversion.
  arXiv  Detail & Related papers  (2023-03-06T16:41:57Z)
• 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.