Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

Traditional Bandit Convex Optimization (BCO) relies on the assumption that observed loss functions are convex and smooth, allowing for efficient gradient estimation. However, real-world systems often exhibit non-convexity or non-smoothness due to measurement noise, model misspecification, or adversarial interference. This paper investigates whether a learner can still achieve sublinear regret when the observed losses are only approximately convex and smooth, specifically when they deviate from a structured convex sequence by a globally bounded cumulative amount.

The authors introduce a model where each loss function $f_t$ is decomposed into a structured component $h_t$ (which is convex and $\beta$-smooth) and an arbitrary perturbation $\sigma_t$. The key constraint is a global budget: the sum of the absolute differences $|f_t(x_t) - h_t(x_t)|$ over the time horizon $T$ is bounded by a constant $C$. To handle this, the authors adapt the SCRiBLe algorithm—a bandit optimization method that uses self-concordant barriers to define local geometry. The proposed "Shrunk and Scaled SCRiBLe" (SS-SCRiBLe) algorithm operates on a restricted feasible set and uses a scaled Dikin ellipsoid sampling scheme to maintain stability under the influence of the perturbations.

The study establishes an expected regret bound for the SS-SCRiBLe algorithm that explicitly characterizes the impact of the perturbation budget $C$. The regret is shown to be sublinear in $T$, effectively interpolating between the standard smooth convex bandit setting (when $C=0$) and the more general perturbed setting. The analysis demonstrates that by shrinking the decision set and scaling the exploration steps, the learner can successfully disentangle the structured convex component from the adversarial noise, even when the observed feedback is non-convex.