Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits

arXiv:2610.36245v1 Announce Type: new 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.