Search papers, labs, and topics across Lattice.
This paper revisits perturbation-based methods for unconstrained Bandit Linear Optimization (uBLO), demonstrating that it effectively reduces uBLO to Online Linear Optimization (OLO). The authors derive expected-regret guarantees by combining their perturbation scheme with comparator-adaptive OLO algorithms, providing insights into the impact of adversarial models. They also establish the first high-probability guarantees for both static and dynamic regret in uBLO, and prove a lower bound of $惟(\sqrt{dT})$ for adversarial linear bandits on the unit Euclidean ball.
Unconstrained bandit linear optimization can be surprisingly reduced to standard online linear optimization using a perturbation approach, unlocking new regret guarantees and high-probability bounds.
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 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 $惟(\sqrt{dT})$ rate for adversarial linear bandits on the unit Euclidean ball, which is of independent interest.
