PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.36245v1cs.LGcs.GT

TL;DR

DUET tackles the challenge of improving on an acceptable baseline without paying excessive exploration costs. It uses empirical tests to adjust phased learning, with guarantees for baseline regret, adversarial losses, and stochastic losses under stated assumptions.

  • Problem

    Improving on an acceptable baseline requires exploration away from it, while the learner must balance adversarial robustness and stochastic adaptivity without knowing the regime or gap.

    Source: §1 · p. 2

  • Method

    DUET uses two observable tests in a horizon-free phased mixing scheme, instantiated with entropy-FTRL in mixed phases and hybrid-FTRL in pure phases.

    Source: §1 · p. 3, §5 · p. 15

  • Results

    At every deterministic horizon, DUET achieves logarithmic expected baseline regret, adversarial robustness, and gap-dependent polylogarithmic regret for i.i.d. losses with a unique optimum.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The same scheme combines baseline protection, adversarial robustness, and stochastic adaptivity, with baseline rounds also supplying exploration when every arm is covered.

    Source: §5 · p. 15

    The guarantees require full baseline arm coverage, and the stochastic rate additionally requires i.i.d. losses and a unique optimum.

    Source: §5 · p. 15

Abstract

from arXiv · show

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.

1. Introduction

DUET addresses the tension between improving on an acceptable baseline and limiting the exploration cost, while seeking adversarial robustness and stochastic adaptivity without advance knowledge of horizon, gap, or regime. Its two empirical tests and two base learners support baseline protection alongside learning guarantees, subject to baseline arm coverage.

1. Introduction

  • The motivating setting includes deployed routing, recommendation, or scheduling policies with acceptable performance that a learner is asked to improve without paying much for the attempt.Baseline protection bounds expected excess loss relative to that fixed rule.Source: §1 · p. 2
  • Improvement requires departing from the baseline, but a stochastic-gap-calibrated budget may fail under adversarial losses, while an adversarial-scale budget may permit unnecessary excess loss when a gap exists.The learner must use feedback to decide when and how far to depart from the baseline.Source: §1 · p. 2
  • The baseline must select every arm with probability at least δ > 0; it need not assign positive probability to every action, and its rounds can provide exploration.Without arm coverage, uniformly logarithmic baseline regret can force Ω(T / log T) regret to the best action.Source: §1 · p. 3

1.1. Key idea and technical contributions: two tests, one ledger

  • DUET is a horizon-free phased mixing scheme using entropy-FTRL in mixed phases and hybrid-FTRL in pure phases, with observable tests that adjust learning weight and empirical-regret budget.Doubling yields logarithmically many stages and phases per stage.Source: §1 · p. 3, §1.1 · pp. 4–5

1. Introduction

  • At every deterministic horizon, DUET guarantees logarithmic expected regret to the baseline, adversarial robustness, and gap-dependent polylogarithmic regret under i.i.d. losses with a unique optimum, without knowing the horizon, gap, or regime.The adversarial guarantee is against any fixed action under non-anticipating adversaries.Source: §1 · p. 3
  • DUET extends the comparison with Müller et al. (2025) to combinatorial semi-bandits, a horizon-free procedure, and a gap-dependent stochastic rate, but does not improve their constant baseline guarantee.The stated prior stochastic guarantee is from a separate algorithm; Hu et al. (2026) assume controlled adaptivity for their adversarial guarantee.Source: §1 · pp. 3–4, Table 1 · p. 4

1.1. Key idea and technical contributions: two tests, one ledger

  • Stopped empirical-maximum certificates supply the stronger guarantee needed for data-dependent restarts, beyond ordinary best-of-both-worlds regret to a fixed comparator at a fixed horizon.For random regrets to individual actions, max_X E D_T(X) ≤ E max_X D_T(X).Source: §1 · p. 4
  • Its key analysis challenge is bounding a fresh learner’s positive empirical regret at a phase-ending stopping time, where the empirically best action is also shaped by estimation noise.Mixed phases use retained baseline observation probability; pure phases use a monotone regret bound and a deterministic-length comparison.Source: §1.1 · p. 5

2. Setting and objectives

The setting is a finite-action combinatorial semi-bandit with losses observed only on selected arms and a baseline distribution that covers every arm. The objectives are defined at deterministic horizons, with stochastic fast rates requiring i.i.d. losses and a unique optimal action.

2. Setting and objectives

  • Each feasible action is a binary arm-selection vector; the learner draws an action, incurs its selected-arm losses, and observes those losses individually.Actions may select different numbers of arms, and the loss of every action is bounded by a known L ≤ m.Source: §2 · p. 5
  • The non-anticipating protocol lets losses depend on the past and announced distribution, but not the realized draw, making importance-weighted estimates unbiased.A known baseline distribution must have marginal arm coverage δ > 0.Source: §2 · p. 6
  • At every deterministic horizon, the objectives are logarithmic expected regret to the baseline, sublinear adversarial regret, and a gap-dependent stochastic fast rate.The comparator is fixed in advance, with the maximum over actions outside the expectation.Source: §2 · p. 6
  • The stochastic fast-rate setting assumes i.i.d. loss vectors independent of learner seeds and a unique optimal action with positive minimum gap.Coordinates within a loss vector may be correlated.Source: §2 · p. 6

3. Our results

DUET mixes a baseline with a learning distribution, using empirical tests to adjust the learner’s weight and restart budget. It provides logarithmic expected baseline regret alongside adversarial and stochastic fixed-action regret guarantees.

3.1. The DUET mixing scheme

  • The tests use importance-weighted loss estimates to compare the learner and baseline against the same best fixed action.The learner statistic measures positive empirical regret, while the baseline statistic measures empirical excess loss; their difference supplies evidence for increasing the learner’s weight.Source: §3.1 · p. 7
  • DUET doubles the empirical-regret budget and restarts when the learner exceeds it; otherwise, sufficient empirical evidence of an advantage over the baseline doubles the learner’s weight.The budget controls the learning cost allowed in a stage, while the weight controls how much of that cost affects played actions.Source: §3.1 · p. 7
  • DUET uses entropy-FTRL in mixed phases, where baseline mixing preserves observation coverage, and hybrid-FTRL in pure phases, where that coverage may vanish.The two learners provide the bounds required by the restart tests.Source: §3.1 · pp. 7–9, §3.2 · p. 9

3.2. Main guarantees

  • The algorithm needs neither the horizon, the stochastic gap, nor the environment type as input.Its learning rates use elapsed phase time and known problem parameters.Source: §3.1 · p. 9, §3.2 · p. 10
  • Baseline regret is O(log(eT)); fixed-action regret is O(T/δ log^3(eT)) adversarially and O(log^4(eT)/(δ∆)) under independence and a unique optimum.Only the stochastic rate requires independence and a unique optimum.Source: Remark 2 (Reading the guarantees) · p. 10

Remark 2 (Reading the guarantees)

  • Summing the phase and stage bounds introduces additional logarithmic factors, while the same empirical quantity admits both adversarial and stochastic bounds.The scheme therefore needs no test to identify the environment regime.Source: Remark 2 (Reading the guarantees) · p. 10

4. Why DUET works

DUET’s accounting links gains from completed phases to baseline protection and charges budget increases to observed empirical regret. Conditional bounds for stopped phases let these mechanisms yield baseline and learning guarantees at deterministic horizons.

4.1. Completed phases pay for baseline protection

  • Completed phases that increase the learner’s weight bank estimated gains that offset later exposure, bounding estimated baseline regret by 2LJ_T, including when a stage ends at the horizon.A weight increase requires a completed phase whose learning cost fits the current threshold.Source: §4.1 · p. 11

4.2. Bounding stage thresholds by empirical phase regret

  • A stage threshold increase is less than twice the empirical regret of the phase that triggered it, so each increase is charged to observed learning cost.The additional comparator cost is bounded by the stage threshold and charged to the triggering phase.Source: §4.2 · p. 11, Lemma 1 (From empirical phase regret… · p. 12

Lemma 1 (From empirical phase regret to estimated total regret)

  • The transfer bound absorbs stage-threshold costs into total empirical phase regret, with a factor J_T because each stage threshold can appear across at most J_T phases.The sum over phase intervals is bounded using R_s(I) ≤ J_T(2L + 2U_T); summing over at most J_T^2 phases yields the stated transfer.Source: Lemma 1 (From empirical phase regret… · p. 12

4.3. Stopped phases require control before taking expectation

  • Stopped endpoints require controlling the expected positive empirical maximum conditionally on the phase’s start, because the same noisy estimates select the comparator and trigger stopping.Mixed phases use baseline coverage to control estimation fluctuations; pure phases instead use a nonnegative, nondecreasing majorant of empirical regret.Source: §4.3 · pp. 12–14

4.4. Conditional restarts turn phase bounds into three guarantees

  • Conditional stopped-phase certificates remain valid after fixing the start history, allowing bounds to be summed over a deterministic list of possible phase labels despite random restarts.The argument uses independence of future losses and fresh learner randomness under the stochastic assumption, and conditional sampling identities under the adversarial assumption.Source: §4.4 · p. 14
  • The resulting expected empirical-regret bounds, combined with the transfer bound and unbiasedness for fixed comparators, establish the theorem’s guarantees at every deterministic horizon.The proof takes expectations in the transfer bound and then takes the supremum over fixed comparators.Source: §4.4 · p. 15

5. Discussion

DUET combines baseline protection with adversarial robustness and stochastic adaptivity through two observable tests and phase-specific FTRL learners. Its guarantees rely on full arm coverage, and sharper bounds and lower computational costs remain open directions.

5. Discussion

  • Two observable tests govern learning-weight increases and empirical-regret-budget restarts, while entropy-FTRL and hybrid-FTRL supply certificates in mixed and pure phases.The scheme operates without knowing the horizon, stochastic gap, or environment type.Source: §5 · p. 15
  • The guarantees require full arm coverage, and small coverage probability δ worsens the bounds.Baseline regret is logarithmic in expectation at each fixed horizon; no pathwise baseline guarantee is asserted.Source: §5 · p. 15
  • Sharper bounds for actions revealing many arms remain a future-work direction; the general feasible-family benchmark is discussed alongside a sharper bound for fixed-size subsets.The paper notes that the maximum feasible action size alone does not imply full-information feedback.Source: §5 · p. 15
  • Refining DUET's rates requires coordinated changes to both learners and new stopped-phase bounds propagated through restart analysis.A sharper pure-phase bound alone would leave the mixed phase's current dependence on m; retaining all three guarantees while refining the rates remains open.Source: §5 · p. 15
  • The authors report that AI tools were used only to improve wording and exposition after earlier reviews helped clarify pathwise proof arguments.The student authors and supervisor began the problem before GPT-5.6 models were released.Source: §5 · p. 15

Appendix A. Proof dependency diagram

The appendix maps DUET's proof dependencies and fixes the setting and assumptions used in its bounds. The stochastic bounds require additional independence and uniqueness conditions beyond the common proof inputs.

Appendix A. Proof dependency diagram

  • Figure 1 traces proof inputs from phase certificates through restart bounds and regret accounting to the final guarantees; only stochastic bounds additionally require Assumptions A3 and A4.The diagram's common inputs include DUET, Assumptions A1 and A2, and unbiasedness.Source: Appendix A · p. 19, Figure 1 · p. 19

Appendix B. Notation and setting

  • The setting uses a finite feasible action set X of binary selections over d arms, with P denoting its convex hull and N its number of actions.A selected arm is represented by Xi = 1; actions can also be treated by their supports.Source: Appendix B · p. 20
  • The analysis conditions on a pre-draw history that includes the sampling distribution but excludes the learner's fresh draw, while the learner uses only observed feedback.The action-selection marginal is the conditional probability of selecting each arm.Source: Appendix B · p. 20

C.1. Stochastic assumption

  • Future loss-randomness pairs are independent of the past under the stochastic assumption, although losses within a round may be correlated.This assumption is needed only for stochastic bounds.Source: §C.1 · p. 21

C.2. Full-action convention and stochastic gap

  • Bounds use the full action set, including dominated actions; the stochastic gap is defined relative to a unique mean-loss-minimizing action.The minimum gap is positive over all other actions.Source: §C.2 · p. 22

C.3. Necessity of coverage

The coverage lower bound shows why baseline coverage is necessary for jointly small baseline regret and learning regret. The appendix also connects observable empirical-regret certificates to expected regret and verifies them for DUET's learners.

C.3. Necessity of coverage

  • The proof derives the lower bound by comparing two i.i.d. environments whose second-arm losses differ, while the learner observes that arm only when selecting it.The argument applies a change-of-measure inequality to the number of second-arm selections.Source: §C.3 · p. 22
  • With baseline regret B = O(log(eT)), some i.i.d. environment with a unique optimal action forces learning regret Ω(T/log(eT)), so coverage cannot generally be dropped while retaining both rates.The lower-bound construction uses two actions and a baseline that never selects the second arm.Source: §C.3 · p. 22

Appendix D. Loss estimation and empirical-regret certificate

  • Importance-weighted semi-bandit estimates are conditionally unbiased, allowing predictable estimated-regret bounds to transfer to expected regret.The proof conditions on the pre-draw history and current losses, then uses the fresh-draw identity and tower property.Source: Appendix D · p. 23

Proof

  • The phasewise certificate bounds estimated regret simultaneously for all comparators pathwise, and the entropy-FTRL and hybrid-FTRL learners used in DUET satisfy its conditions.The certificate also applies to realized intervals after data-dependent restarts.Source: Proof · pp. 23–24

Appendix E. FTRL learners for DUET

DUET uses entropy-FTRL in mixed phases and hybrid-FTRL in pure phases, with padding and projection to support their implementations. The mixed-phase mixture ensures arm coverage, while a loss shift in pure phases preserves empirical regret.

Appendix E. FTRL learners for DUET

  • In mixed phases, baseline-learning mixtures give each original arm coordinate sampling marginal at least ρ; dummy coordinates have known zero loss and need no estimator.A second-order FTRL inequality and martingale concentration control the mixed-phase certificate.Source: Appendix E · pp. 24, 26
  • Padding with zero-loss dummy arms maps actions to equal-size vectors without changing action losses, gaps, or regrets.The padded dimension is at most 2d, and projection removes coordinates common to every action while preserving gaps.Source: Appendix E · pp. 24–25
  • Mixed phases use entropy-FTRL on the action simplex, while pure phases use hybrid-FTRL on the convex hull of projected actions.The pure-phase learner uses local learning rate ηn = n^-1/2.Source: Appendix E · pp. 24, 26, 27
  • Zero padding preserves entropy-FTRL probabilities and, when coupled with the same baseline, yields identical marginals, estimates, and restart decisions.The action bijection preserves the softmax denominator and action-set size.Source: Appendix E · p. 26
  • Pure phases shift the loss vector by the all-one vector, and equal action sizes make this shift preserve the empirical-regret statistic.The shift changes each action's loss by the same amount, so action comparisons are unchanged.Source: Appendix E · pp. 25, 27

Appendix F. Implementation details of DUET

DUET organizes learning into phases within stages, using empirical-regret and comparator-gap tests to control restarts and mixing. Mixed phases combine a base learner with the baseline; pure phases use the base learner alone.

Appendix F. Implementation details of DUET

  • The phase mixing weight doubles until it reaches one, at which point the baseline is no longer mixed into the played distribution.The played action distribution is the mixture of the base learner’s distribution and the baseline distribution.Source: Appendix F · pp. 27–28
  • DUET uses entropy-FTRL in mixed phases and hybrid-FTRL with direct sampling in pure phases, with each phase using local time and a fresh learner.Restarts clear cumulative estimates; the pure-phase sampling map is fixed in advance.Source: Appendix F · p. 28
  • A stage restarts with a doubled empirical-regret budget when Uu:t exceeds Rs; otherwise, a comparator-gap test can double the mixing weight within the stage.Both tests use statistics from the current phase, and a restart begins a fresh phase.Source: Appendix F · pp. 27–28
  • Positive arm-selection marginals are maintained in both phase types, keeping the original-arm importance-weight denominators positive.Mixed phases have xt,i ≥ δ/2; in pure phases, variable coordinates have positive marginals and constant-one coordinates have marginal one.Source: Appendix F · p. 28

Appendix G. Proof of the FTRL learners’ empirical-regret bound

The proof establishes stopped empirical-regret certificates for mixed and pure phases, then transfers them to data-dependent phase starts. Mixed-phase arguments use coverage and fluctuation bounds, while pure-phase arguments use a nonnegative majorant and continuation to an analysis horizon.

Appendix G. Proof of the FTRL learners’ empirical-regret bound

  • The one-phase lemma supplies stopped empirical-regret bounds for entropy-FTRL in mixed phases and hybrid-FTRL in pure phases under adversarial or stochastic conditions.Its stochastic case assumes i.i.d. losses and a unique optimal action with positive gap; its adversarial case assumes A1 on each local round.Source: Appendix G · p. 29
  • For mixed phases, full coverage supports fluctuation bounds, and continuation to H yields a bound on the stopped empirical maximum.The argument includes both adversarial and stochastic mixed-phase certificates.Source: Appendix G · pp. 29, 35, 38
  • Fresh-run certificates remain valid after data-dependent starts by conditioning on the phase-start history and weighting each contribution by its reach probability.The proof does not condition on the future exit event.Source: Appendix G · p. 29
  • For pure phases, a nonnegative, nondecreasing majorant bounds the stopped empirical maximum by its value at H.The pure-phase analysis also derives adversarial and stochastic bounds from the hybrid-FTRL majorant.Source: Appendix G · pp. 29, 36, 37

Appendix H. Restarts and phase counting

The appendices bound DUET’s number of phases, transfer fresh-run certificates to adaptive restarts, and convert total empirical-regret control into expected regret guarantees.

Appendix H. Restarts and phase counting

  • DUET has at most JT stages, at most JT phases per stage, and at most J2T phase intervals in total.At a stage-budget crossing, the next budget doubles; comparator-gap restarts stop when the mixing weight reaches one.Source: Appendix H · pp. 39–40

Lemma H.3 (Conditional validity after a data-dependent restart)

  • Conditioning on the history at a data-dependent phase start lets the fresh-run certificate apply, with each phase contribution weighted by its probability of being reached.This transfer uses the conditional laws of future losses and fresh seeds, without conditioning on the future exit event.Source: Lemma H.3 (Conditional validity after… · p. 40

Appendix I. Main regret bounds and proofs

  • Theorem I.1 converts phasewise empirical-regret control into expected regret, and the DUET mixing scheme needs neither the regime nor the gap Δ.Corollary H.4 supplies the empirical-regret premises for DUET.Source: Appendix I · p. 43

I.1. Proof of the general DUET bound

The proof accounts for regret phase by phase, yielding baseline protection and fixed-comparator bounds. It also establishes the hybrid-FTRL majorant estimates used to control pure phases.

I.1. Proof of the general DUET bound

  • The expected baseline regret is at most 2LJT, where JT is the phase-counting bound.The corollary gives DUET’s guarantees for deterministic horizons without knowing T, Δ, or the regime.Source: §I.1 · pp. 43, 47
  • Comparator-gap exits generate geometric gains that cover terminal costs, leaving at most 2L estimated baseline regret per stage.Summing across stages and applying unbiasedness gives the expected baseline-regret bound.Source: §I.1 · p. 43
  • The DUET corollary gives fixed-comparator regret bounds under non-anticipating adversarial losses and under stochastic assumptions A3 and A4.The implementation enumerates all N = |X| actions.Source: §I.1 · p. 47

Appendix J. Hybrid-FTRL majorant bounds

  • For pure phases, hybrid-FTRL’s nonnegative majorant controls the stopped empirical maximum; stochastic self-bounding supplies an additional control on pure-phase regret.The majorant estimate uses stability and penalty bounds, while the stochastic argument assumes i.i.d. losses and a unique mean-optimal action.Source: Appendix J · p. 49

Appendix K. Auxiliary probability results

The appendices support the regret analyses with probability bounds and technical justifications, specify conditions limiting the stochastic guarantees, and situate DUET among related work on conservative exploration, safety constraints, resource budgets, best-of-both-worlds learning, and adaptive regularization. They highlight differences in comparators, feedback, guarantees, and proof requirements.

K.1. Bernstein, Ville, and Freedman inequalities

  • Freedman-type bounds control martingale deviations, including estimated-gap deviations and crossings over all prefixes.Conditional Bernstein and Ville inequalities yield a maximal bound that also applies under phase-start conditional laws; the fixed-time bound follows by event inclusion.Source: §K.1 · pp. 56–57

K.2. Stopped martingales

  • The stopped-martingale L2 identity bounds optimal-action fluctuations at a stopped mixed phase.Predictable stopping indicators preserve the martingale variance identity, and Cauchy–Schwarz converts the variance bound into an expected absolute fluctuation.Source: §K.2 · pp. 57–58

K.3. Tail integration, exponential series, and layer cake

  • Tail integration converts finite-set exponential tails into bounds on expected maxima, with maximization inside the expectation.Ville’s inequality and a union bound give the tail bound; Tonelli’s theorem permits integration, including for the stated finite-set bound.Source: §K.3 · pp. 58–59
  • The layer-cake identity converts gap-tail mass into expected pseudo-regret with 1/∆ dependence when positive gaps are bounded below by ∆.The identity also holds after summing over rounds; the appendix further bounds two exponential series uniformly over phase length for the layer-cake argument.Source: §K.3 · pp. 59, 61

K.4. Max-increment and importance-weighted overshoot

  • The max-increment and overshoot bounds control threshold crossings when the empirical comparator changes, assuming nonnegative losses and p ≥ βz coordinatewise.Under these conditions, importance-weighted estimates are bounded by observed action loss.Source: §K.4 · p. 62

Appendix L. Well-definedness of the pure-phase update

  • The pure-phase optimizer is unique and interior on every nonconstant coordinate, its gradient equals the potential gradient, and every original arm has strictly positive marginal.This establishes that pure-phase importance weighting and the potential-gradient update are well-defined.Source: Appendix L · pp. 63–64

M.1. Combinatorial decisions and feedback models

  • Aggregate-bandit feedback reveals total action loss, while semi-bandit feedback reveals selected component losses; the cited feedback-model work does not impose this paper’s baseline constraint.Baseline coverage bounds arm observation probabilities during mixed phases, enabling entropy-FTRL analysis.Source: §M.1 · p. 65

M.2. Stochastic combinatorial learning and instance dependence

  • The stochastic guarantee allows dependence within loss vectors but assumes i.i.d. vectors independent of learner randomness and a unique optimal action; it does not improve unconstrained rates or oracle guarantees.The paper’s simultaneous baseline and adversarial guarantees introduce coverage and restart factors.Source: §M.2 · p. 65

M.3. Conservative exploration relative to a baseline

  • Unlike Müller et al. (2025), DUET adapts its mixing weight and regret budget without horizon knowledge, with logarithmic expected baseline loss and gap-dependent stochastic regret under arm coverage.Müller et al. obtain constant expected baseline regret and near-square-root adversarial regret using a known-horizon algorithm with a fixed restart threshold; DUET’s baseline bound is logarithmic, and its stochastic bound is gap-dependent.Source: §M.3 · pp. 65–66

M.4. Structured conservative and safe semi-bandits

  • DUET’s expected cumulative baseline-regret guarantee implies neither Hou et al.’s variance-budget constraint nor Katariya et al.’s itemwise safety guarantee.Katariya et al. use exchangeable action spaces and itemwise comparisons; Hou et al. require each selected action’s component variances to stay below a budget simultaneously with high probability.Source: §M.4 · p. 66

M.5. Cumulative constraints and resource budgets

  • DUET’s budget tracks a signed loss difference, so outperforming the baseline contributes negatively, unlike standard knapsack accounting and its reward-oriented comparator.Its constraint and feedback also differ from aggregate convex constraints studied by Mahdavi et al.Source: §M.5 · p. 66

M.6. Stochastic and adversarial adaptation

  • DUET’s final comparator maximum is outside expectation; controlling random comparator-dependent regret alone is insufficient, and Auer and Chiang’s separation requires matching comparators, adversaries, and rates.Unlike corruption-dependent stochastic semi-bandit results, DUET assumes i.i.d. losses and benchmarks against exact feasible actions rather than an approximation-regret benchmark.Source: §M.6 · p. 67

M.7. Adaptive regularization and hybrid FTRL

  • DUET’s pure-phase learner follows Zimmert et al. (2019)’s hybrid-FTRL method, applying its regularizer after the reduction and proving a monotone empirical-regret majorant.Replacing DUET’s base learners with later unconstrained refinements requires verifying their stopped empirical-maximum bounds.Source: §M.7 · p. 67

M.8. Perturbation methods and contextual extensions

The related-work comparisons distinguish DUET’s arbitrary-action, baseline-constrained setting from specialized perturbation and contextual approaches. The section also explains the certificate DUET needs and bounds the scope of its guarantees.

M.8. Perturbation methods and contextual extensions

  • Zhan et al. (2026) study m-set semi-bandits, while DUET addresses arbitrary finite action sets with a baseline constraint.Their near-best-of-both-worlds guarantees apply when m ≤ d/2; DUET requires further arguments for its broader action sets and baseline constraint.Source: §M.8 · p. 67
  • Li et al. (2026) study contextual combinatorial semi-bandits with independent bounded contexts; DUET uses no contexts and constrains expected regret relative to a covering baseline.Their linear model also assumes positive-definite context covariance, additional independent context samples, and adversarial loss coefficients independent of the action sequence.Source: §M.8 · p. 67

M.9. Computation, alternative adaptation, and optimal actions

  • Neu and Bartók (2016) provide oracle-efficient adversarial semi-bandits without computing all sampling probabilities, whereas DUET enumerates actions.Neu (2015) adapts to the best action’s cumulative loss, which may grow linearly despite a positive gap; Lykouris et al. (2018) give stronger high-probability small-loss bounds without DUET’s baseline constraint.Source: §M.9 · pp. 67–68
  • DUET’s certificate and restart analysis retains a unique optimal combinatorial action and a positive minimum gap.The results of Jin et al. (2023) for multiple optimal arms in multi-armed bandits do not remove this assumption.Source: §M.9 · p. 68

M.10. The certificate required by baseline-constrained phases

  • Mixed sampling, empirical phase endpoints, and data-dependent restarts require control of the positive empirical comparator maximum, beyond a fixed-length expected-regret bound.Lemma G.1 establishes this control using coverage and entropy FTRL in mixed phases and a nonnegative, nondecreasing hybrid-FTRL majorant in pure phases; Lemma H.3 justifies reuse after restarts.Source: §M.10 · p. 68
  • DUET’s three guarantees hold at every fixed horizon, but they do not provide simultaneous high-probability baseline bounds or regret bounds at arbitrary data-dependent stopping times.The martingale estimates use the concentration framework of Freedman (1975); Appendix K states the versions used.Source: §M.10 · p. 68
Loading 2610.36245v1…