Abstract: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.
From: Andrew Jacobsen [view email]
[v1]
Mon, 30 Mar 2026 09:17:46 UTC (62 KB)
[v2]
Fri, 29 May 2026 11:42:46 UTC (76 KB)
[v3]
Sun, 2 Aug 2026 12:33:07 UTC (76 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。