New algorithm balances safety and learning in sequential decisions
Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits
Machine LearningComputer Science and Game Theory
Summary
Making better choices than a known baseline can be risky because it involves trying new options that might perform worse. The authors propose a new method called DUET that smartly decides when to explore and when to rely on the baseline to keep performance safe. This method adapts to different environments without knowing ahead of time how long it will run or how good the best option is. Their approach maintains strong safety guarantees while learning effectively in both adversarial and normal, random settings.
What this means in practice
- •For online recommendation engineers: Build recommendation systems that safely improve over a default strategy while adapting to changing or uncertain user behaviors.
- •For online advertising teams: Implement ad selection algorithms that guarantee performance close to a baseline while learning new better ad combinations efficiently.
Authors
Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Abstract
Improving on a baseline requires exploring away from it, precisely where its performance may be lost. We propose DUET (Doubling Under Empirical Tests), a horizon-free phased mixing scheme for combinatorial semi-bandits with arbitrary finite action sets. Two observable tests decide when to double the learning weight and when to double the empirical-regret budget and restart. We instantiate the scheme with entropy-FTRL in mixed phases and hybrid-FTRL in pure phases. Assuming the baseline selects every arm with positive probability, this instantiation keeps expected baseline regret logarithmic in $T$, while its expected regret to every fixed action is $\widetilde{O}(\sqrt{T})$ under non-anticipating adversarial losses and polylogarithmic, gap-dependent, under i.i.d. losses with a unique optimal action. All three guarantees hold at every deterministic horizon, and the algorithm knows neither the horizon, nor the gap, nor the environment type. Baseline protection, adversarial robustness, and stochastic adaptivity thus come from one scheme and two base learners, at the price of a logarithm.