Learning Safely Without Knowing the World:COMPASS-Hedge

Ting Hu; Luanda Cai; Emmanouil-Vasileios Vlatakis-Gkaragkounis

cs.LGMar 22, 2026

Learning Safely Without Knowing the World:COMPASS-Hedge

Authors: Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Organizations: Department of Economics, University of Wisconsin–Madison · Department of Finance, University of Wisconsin–Madison · Department of Computer Sciences, University of Wisconsin–Madison

Abstract

Online learning algorithms often face 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. To the best of our knowledge, our algorithm is the first full-information anytime method to simultaneously achieve, up to logarithmic factors: 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. Crucially, COMPASS-Hedge is parameter-free and requires no prior knowledge of the environment's nature or the magnitude of the stochastic suboptimality 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.

Figures & tables

Representative works	Minimax $\tilde{O}(\sqrt{T})$	Stochastic $\tilde{O}(\log A/\Delta)$	Baseline $\tilde{O}(1)$
Even-Dar et al. [ 21 ] ; Müller et al. [ 43 ]	✓	✗	✓
Müller et al. [ 43 ] , App. B.3	✗	✗	✓
Mourtada–Gaïffas [ 42 ]	✓	✓	✗
COMPASS-Hedge (ours)	✓	✓	✓

Table 1: The three-world landscape. Here

\tilde{O}(\cdot)

hides polylogarithmic factors in

T

Panel of Figure 1 — Figure 1: Experimental evaluation. (a)–(b) Stochastic adaptivity on S&P 500 data (2015–2024): Panel (a) reports regret against NVIDIA, the ex-post best single asset, while Panel (b) reports regret against SPY, a market comparator. Compass-Hedge gives the best trade-off: it improves over Hedge variants against NVDA while remaining close to SPY. (c)–(d) Adversarial robustness: Compass-Hedge exhibits vanishing average regret and stable $R_{t}/\sqrt{t}$ , consistent with $O(\sqrt{T})$ adversarial regret. Shaded regions denote 90% CIs.

Panel of Figure 2 — Figure 2: The Best-of-Three-Worlds landscape. Each circle represents one desideratum. Prior algorithms (annotations) cover at most two regions simultaneously. Compass-Hedge (center) is the first to unify all three in a single, parameter-free algorithm.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Adversarial robustness. Panel (a) shows that the average regret of Compass-Hedge vanishes over time, while bad fixed comparators suffer constant average regret. Panel (b) shows that regret normalized by $\sqrt{t}$ remains stable, indicating adversarial $O(\sqrt{T})$ regret up to constant factors. Shaded regions indicate pointwise 90% confidence intervals across trials.

Panel of Figure 4 — Figure 4: S&P 500 Hedge family comparison, 2015–2024. Panel (a) plots cumulative loss minus cumulative NVIDIA loss, i.e., regret against the ex-post best single arm. Panel (b) plots cumulative loss minus cumulative SPY loss, i.e., regret against the market comparator. Compass-Hedge is the only method that remains competitive with both the aggressive best-arm benchmark and the safer market benchmark.

Panel of Figure 5 — Figure 5: Anatomy of the synthetic adversary. The alternating pair $(x^{\prime},x^{\prime\prime})$ produces a structured non-stationary stream anchored to the equilibrium geometry of the game. The sweep over $\varepsilon$ lets us dial comparator quality from “perfect” to “uninformative” while keeping the underlying environment fixed.

Panel of Figure 6 — Figure 6: Time-series behavior in the comparator-quality sweep.

Panel of Figure 7 — Figure 7: Terminal statistics from the comparator-quality sweep.

Panel of Figure 8 — Figure 8: Regret and loss measured against the game value $V^{\star}t$ .

Panel of Figure 9 — Figure 9: Distinguishing $\sqrt{T}$ from linear growth. Curves for regret $/\sqrt{t}$ remain stable rather than drifting upward, final regret scales near-linearly in $\sqrt{T}$ , and the normalized final regret stays essentially flat across horizons—three independent pieces of evidence consistent with $O(\sqrt{T})$ growth.

Panel of Figure 10 — Figure 10: Regret and cumulative loss against $V^{\star}t$ , with the matched comparator overlaid as a dotted baseline.

Panel of Figure 11 — Figure 11: Regret measured against the matched comparator $q_{\varepsilon}$ rather than against $V^{\star}$ .

Panel of Figure 12 — Figure 12: Median regret across 500 trials. Shaded bands are $10^{\text{th}}$ – $90^{\text{th}}$ percentiles. Panels (a) and (c): under an informative Oracle prior, Compass-Hedge (blue) tracks the best expert without incurring comparator regret. Panels (b) and (d): under a deliberately weak Uniform prior, Standard Hedge (orange) exhibits high variance and sporadic blow-ups, whereas Compass-Hedge maintains a nearly flat comparator-regret trajectory—the empirical signature of the $\tilde{O}(1)$ safety guarantee.

Online Learning

Online learning studies algorithms that update predictions or decisions from sequential feedback while controlling cumulative error or regret.

See all 132 papers

Gradient-Variation Regret Bounds for Unconstrained Online Learning
Apr 13, 2026Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Online Convex Optimization Dynamic Regret Minimization
Università degli Studi di Milano & Politecnico di Milano
Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees
Apr 15, 2026Sourav Ganguly, Kartik Pandit, Arnob GhoshAdversarial MARL Reinforcement Learning
Dept. of Electrical and Computer Engineering, NJIT, Newark, NJ, USA
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisMulti-Armed Bandits Minimax Regret
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison

Apr 13, 2026J/K move · Enter open · S save

Gradient-Variation Regret Bounds for Unconstrained Online Learning

Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi, Peng Zhao

Università degli Studi di Milano & Politecnico di Milano

Online Convex Optimization Dynamic Regret Minimization

Open paper AskPDF arXiv

We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation

V_T(u) = \sum_{t=2}^T \|\nabla f_t(u)-\nabla f_{t-1}(u)\|^2

. For

L

-smooth convex losses, we provide fully-adaptive algorithms achieving regret of

\widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^2+G^4)

without requiring prior knowledge of comparator norm

\|u\|

, Lipschitz constant

G

, or smoothness

L

. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).

Abstract

Online Learning

Explore similar work

Gradient-Variation Regret Bounds for Unconstrained Online Learning

Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees

Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays