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

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

cs.LGOct 26, 2026

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

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

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.

Figures & tables

	Feedback	Baseline covers	Baseline regret	Adversarial	Stochastic	Horizon
Even-Dar et al. (2008)	full info.	(designated distr.)	$O(1)$	near- $\sqrt{T}$	—	known
Müller et al. (2025)	bandit	every action	$O(1)$	$\widetilde{O}(\sqrt{T})$	$O(\sqrt{T})$	known
Hu et al. (2026)	full info.	not required	$O(\log^{2}T)$	$\widetilde{O}(\sqrt{T})$	$O(\log^{2}T)$	free
Zimmert et al. (2019)	semi-bandit	no baseline	—	$O(\sqrt{T})$	$O(\log T)$	free
Duet (this paper)	semi-bandit	every arm	$O(\log T)$	$\widetilde{O}(\sqrt{T})$	$O(\mathrm{polylog}\,T/\delta)$	free

Table 1

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: Proof dependencies for Duet . Arrows show the inputs to each step, from phase certificates through restart bounds and regret accounting to the final guarantees.

Combinatorial Semi-Bandits

See all 12 papers

Conservative Dueling Bandits: Preference Learning under Baseline Constraints
Oct 27, 2026Rohan Deb, Mohammad Ghavamzadeh, Arindam BanerjeeDueling Bandits Contextual Bandits
University of Illinois, Urbana Champaign · Qualcomm AI Research
Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives
Mar 19, 2026S Akash, Pratik Gajane, Jawar SinghDueling Bandits Multi-Armed Bandits
Indian Institute of Technology Patna, India · University of Orléans, France
Replicable Dueling Bandits
Oct 14, 2026Rohan Deb, Aadirupa Saha, Udaya Ghai +2Dueling Bandits Multi-Armed Bandits
University of Illinois, Urbana Champaign · University of Illinois, Chicago · Amazon +1

Oct 27, 2026J/K move · Enter open · S save

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee

University of Illinois, Urbana Champaign · Qualcomm AI Research

Dueling Bandits Contextual Bandits

Open paper AskPDF arXiv

Contextual dueling bandits learn from pairwise comparisons, the same feedback used to fine-tune language models from human preferences. Standard algorithms explore aggressively and can show users two poor options. We study conservative contextual dueling bandits, which require that, at every round, the cumulative score of the better displayed item stay above a

(1-α)

fraction of a trusted baseline's. An item's score is its probability of beating the best available item, so the constraint depends only on utility differences and needs no absolute rewards. This also changes how safety can be certified: we show that transferring the safety test of the conservative bandit algorithm CLUCB unchanged can incur linear regret, even when the baseline's utilities are known exactly. For linear utilities, we develop MaxInP-BC, which certifies scores through utility gaps and, when it must fall back, pairs the baseline with an informative partner so that fallback rounds still drive learning. It is safe with high probability at all times, with regret

\tilde{O}(d\sqrt{T}/κ)

plus an additive cost of conservatism that does not grow with the horizon. For general utility classes, we develop BTIGW-BC, which turns the guarantee of an online logistic-regression oracle into cumulative safety certificates. It is safe at all times, makes finitely many fallbacks, and has sublinear regret whenever the oracle's logistic regret is sublinear. In experiments, both satisfy the constraint, which their unconstrained counterparts often violate, at a moderate cost in regret.

Abstract

Combinatorial Semi-Bandits

Explore similar work

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives

Replicable Dueling Bandits