COMPASS-Hedge: Learning Safely Without Knowing the World

View PDF HTML (experimental)

Abstract:Online learning algorithms often faces a fundamental trilemma: balancing regret guarantees between adversarial and stochastic settings and providing baseline safety against a fixed comparator. While existing methods excel in one or two of these regimes, they typically fail to unify all three without sacrificing optimal rates or requiring oracle access to problem-dependent parameters. In this work, we bridge this gap by introducing COMPASS-Hedge. Our algorithm is the first full-information method to simultaneously achieve: i) Minimax-optimal regret in adversarial environments; ii) Instance-optimal, gap-dependent regret in stochastic environments; and iii) $\tilde{\mathcal{O}}(1)$ regret relative to a designated baseline policy, up to logarithmic factors. Crucially, COMPASS-Hedge is parameter-free and requires no prior knowledge of the environment's nature or the magnitude of the stochastic sub optimality gaps. Our approach hinges on a novel integration of adaptive pseudo-regret scaling and phase-based aggression, coupled with a comparator-aware mixing strategy. To the best of our knowledge, this provides the first "best-of-three-world" guarantee in the full-information setting, establishing that baseline safety does not have to come at the cost of worst-case robustness or stochastic efficiency.

Subjects:

Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT)

Cite as: arXiv:2603.22348 [cs.LG]

(or arXiv:2603.22348v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2603.22348

arXiv-issued DOI via DataCite

Submission history

From: Ting Hu [view email] [v1] Sun, 22 Mar 2026 04:17:43 UTC (1,167 KB) [v2] Fri, 27 Mar 2026 16:39:05 UTC (1,167 KB)