A Perturbation Approach to Unconstrained Linear Bandits

We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). 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. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the first guarantees with optimal $\sqrt{P_T}$ path-length dependencies without prior knowledge of $P_T$. We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore $\Omega(\sqrt{dT})$ rate for adversarial linear bandits on the Euclidean ball, which is of independent interest.

We study sequential decision problems with linear losses where the learner observes single-point feedback only at the chosen point, known as bandit linear optimization. We show that, for unconstrained decision sets, a classic random-perturbation approach reduces the problem to standard online linear optimization with gradient feedback. This lets us obtain stronger regret guarantees than previous work, including bounds that adapt to the comparator, handle changing benchmarks with optimal dependence on their movement, and develop new high-probability performance guarantees. We also prove a lower bound showing that, in some adversarial linear bandit problems, no algorithm can avoid at least $\Omega(\sqrt{dT})$ regret, which was previously missing from the literature.