# Learning Safely Without Knowing the World:COMPASS-Hedge

arXiv: https://arxiv.org/abs/2603.22348 · HTML: https://mlsanity.com/paper/2603.22348/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 55 references that are in the map.
- First posted on arXiv 22 Mar 2026.

## Builds on (most cited first, 28 of 28)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Online mirror descent and dual averaging: keeping pace in the dynamic case](https://mlsanity.com/paper/2006.02585/) (2020)
- [Conservative Exploration in Reinforcement Learning](https://mlsanity.com/paper/2002.03218/) (2020)
- [The Pareto Regret Frontier for Bandits](https://mlsanity.com/paper/1511.00048/) (2015)
- [Comparator-adaptive Convex Bandits](https://mlsanity.com/paper/2007.08448/) (2020)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Online Charging Scheduling Algorithms of Electric Vehicles in Smart Grid: An Overview](https://mlsanity.com/paper/1609.02791/) (2016)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.18768/) (2025)

## Abstract (arXiv)

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) tildeO(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.