Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

# Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
Source: [https://arxiv.org/html/2609.13547](https://arxiv.org/html/2609.13547)
###### Abstract

We study switching regret in adversarial multi\-armed bandits, where the learner competes with an arm sequence that changes at mostSStimes\. WhenSSis known, an optimal expected regret of𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)is obtainable\([Auer et al\., 2002](https://arxiv.org/html/2609.13547#bib.bib4)\)\. However, whenSSis unknown,[Marinov and Zimmert \(2021\)](https://arxiv.org/html/2609.13547#bib.bib18)show that this guarantee is impossible under an adaptive adversary\. In this paper, we show that a single algorithm achieves𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)expected regret for everySSagainst an oblivious adversary, resolving an open problem of[Auer et al\. \(2019b\)](https://arxiv.org/html/2609.13547#bib.bib6)\. Our algorithm combines a fixed\-share learner initialized with a small learning rate and dyadic\-interval subroutines that search for local improvements using randomized learning rates and implicit exploration\. Importantly, a non\-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small\. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switchesSS\.

## 1Introduction

Adversarial multi\-armed bandits have been studied for decades as a fundamental model of sequential decision making under partial feedback\. Over a horizon ofTTrounds, a learner repeatedly chooses one ofKKactions and observes only the loss of the chosen action, while the environment may assign losses to all actions arbitrarily\. The classical performance measure is static regret, which compares the learner’s cumulative loss with that of the best fixed action in hindsight\. The minimax static regret isΘ⁡\(K​T\)\\Theta\(\\sqrt\{KT\}\)\([Auer et al\., 2002](https://arxiv.org/html/2609.13547#bib.bib4);[Audibert and Bubeck, 2009](https://arxiv.org/html/2609.13547#bib.bib3)\)\.

Static regret, however, may not be strong enough when the best action changes over time\. This motivates the stronger notion ofSS\-switching regret, which compares the learner with the best action sequence that switches actions at mostSStimes\. In non\-stationary stochastic bandits, this benchmark is often motivated by environments whose loss distributions undergo at mostSSchanges\. A line of work has developed algorithms that attain near\-optimal dynamic regret even without knowing the number of distributional changesSSin advance\([Auer et al\., 2019a](https://arxiv.org/html/2609.13547#bib.bib5);[Auer et al\., 2019b](https://arxiv.org/html/2609.13547#bib.bib6);[Wei and Luo, 2021](https://arxiv.org/html/2609.13547#bib.bib26);[Suk and Kpotufe, 2022](https://arxiv.org/html/2609.13547#bib.bib23)\)\.

Much less is known when the losses are adversarial\. The seminal work of[Auer et al\. \(2002\)](https://arxiv.org/html/2609.13547#bib.bib4)introduced EXP3\.S, which achieves𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)switching regret when its parameters are tuned usingSS\.111We use𝒪~​\(⋅\)\\widetilde\{\\mathcal\{O\}\}\(\\cdot\)to suppress logarithmic factors\.Thus, the optimal rate is known when the switch budget is given to the learner\. For an adaptive adversary, this dependence on prior knowledge cannot in general be removed\. In particular,[Marinov and Zimmert \(2021\)](https://arxiv.org/html/2609.13547#bib.bib18)showed that no single algorithm can attain the minimax rate simultaneously over all switching classes\.

The corresponding problem for an oblivious adversary remained less understood\. Recently,[Qian and Wei \(2026\)](https://arxiv.org/html/2609.13547#bib.bib19)showed that, for a piecewise\-constant deterministic loss sequence with a known number of changes, one algorithm can simultaneously achieve the optimal static and dynamic regret rates\. From the perspective of switching regret, their result controlsS=0S=0together with one prescribed nonzero value ofSS, equal to the known number of loss changes\. It does not provide the optimal guarantee simultaneously for every possible value ofSS\. This leaves the following question open:

Can a single algorithm, without knowingSS, achieve𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)switching regret simultaneously for everySSagainst an oblivious adversary?

##### Contribution

In this paper, we answer this question affirmatively by designing a single algorithm that guarantees𝒪⁡\(\(S\+1\)​K​T​log4⁡\(K​T\)\)\\mathcal\{O\}\(\\sqrt\{\(S\+1\)KT\}\\log^\{4\}\(KT\)\)expected regret simultaneously for allS∈\{0,…,T−1\}S\\in\\\{0,\\ldots,T\-1\\\}\. This matches the minimax dependence onSS,KK, andTTup to logarithmic factors, resolving the open problem proposed in[Auer et al\. \(2019b\)](https://arxiv.org/html/2609.13547#bib.bib6)\.

Our algorithm starts with a fixed\-share main learner at a small learning rate and launches auxiliary learners on dyadic intervals to search for local improvements across different time scales\. Each auxiliary learner can either follow the main distribution or shift probability mass toward a challenger arm, using a randomized learning rate and implicit exploration to learn from bandit feedback\. A key design choice is a non\-uniform prior that places most weight on following the main learner\. This keeps the aggregate initialization penalty for retaining the main distribution small, while preserving the ability to exploit local improvements\.

Throughout this process, the algorithm also tracks an observable estimate of the auxiliary learners’ cumulative improvement over the main learner\. When this estimate reaches a prescribed threshold, the algorithm restarts the main learner at twice its learning rate\. The analysis explains why this rule adapts to an unknown switch budget\. If the main learner falls substantially behind a switching comparator, its disadvantage can be traced to dyadic intervals on which a fixed arm performs better\. We show that the randomized learning rates allow the auxiliary learners to capture enough of these improvements despite bandit feedback\. Relating the estimated improvements to the actual losses then controls the regret within each epoch and shows that the accumulated gains cover the extra cost of larger learning rates in expectation\.

### 1\.1Related Work

##### Switching regret in adversarial multi\-armed bandits\.

[Auer et al\. \(2002\)](https://arxiv.org/html/2609.13547#bib.bib4)initiated the study of switching regret under bandit feedback through the EXP3\.S algorithm\. For a comparator with at mostSSswitches, an appropriate choice of its learning and sharing rates yields𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)regret\. However, the learning\-rate tuning depends onSS\. Their result therefore gives an optimal guarantee for a prescribed switch budget, but it does not provide a single run that is optimally tuned for two switch budgets requiring different learning\-rate scales, let alone for everySSsimultaneously\.

[Marinov and Zimmert \(2021\)](https://arxiv.org/html/2609.13547#bib.bib18)formulated this simultaneous\-adaptation question as a model\-selection problem\. They characterized the relevant Pareto frontier and showed that an adaptive adversary rules out optimal regret for both a static comparator and richer switching comparators in the same run\. However, their lower bound does not cover an oblivious adversary, where the entire loss sequence is fixed before the interaction starts and does not adapt to the learner’s actions\. In this setting, one generic route is to manage differently tuned copies of EXP3\.S using a master construction such as the Bandit\-over\-Bandit framework of[Cheung et al\. \(2022\)](https://arxiv.org/html/2609.13547#bib.bib13)\. However, this only yields𝒪~​\(K1/4​T3/4\+\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(K^\{1/4\}T^\{3/4\}\+\\sqrt\{\(S\+1\)KT\}\)switching regret for allSSsimultaneously\([Qian and Wei, 2026](https://arxiv.org/html/2609.13547#bib.bib19)\)\.[Auer et al\. \(2019b\)](https://arxiv.org/html/2609.13547#bib.bib6)explicitly left optimal adversarial regret without prior knowledge of the switch budget as an open problem\.

More recently,[Qian and Wei \(2026\)](https://arxiv.org/html/2609.13547#bib.bib19)took a first step toward removing this overhead for oblivious deterministic losses\. They obtain optimal static and dynamic regret simultaneously when the loss vector is piecewise constant and the number of its stationary pieces is known\. From the perspective of switching regret, their guarantee controlsS=0S=0together with one prescribed nonzero value ofSS, determined by the known number of environmental changes\. Therefore, it does not give one algorithm that is simultaneously optimal for every comparator switch budget on an arbitrary oblivious loss table\.

##### Dynamic regret beyond adversarial multi\-armed bandits\.

Early work on dynamic regret under environmental nonstationarity studied stochastic multi\-armed bandits\([Besbes et al\., 2014](https://arxiv.org/html/2609.13547#bib.bib7);[Auer et al\., 2019a](https://arxiv.org/html/2609.13547#bib.bib5)\)and contextual bandits\([Luo et al\., 2018](https://arxiv.org/html/2609.13547#bib.bib15);[Chen et al\., 2019](https://arxiv.org/html/2609.13547#bib.bib9)\)\. This line was extended to linear and generalized linear bandits\([Cheung et al\., 2019](https://arxiv.org/html/2609.13547#bib.bib11);[Russac et al\., 2019](https://arxiv.org/html/2609.13547#bib.bib21);[Russac et al\., 2021](https://arxiv.org/html/2609.13547#bib.bib22);[Faury et al\., 2021](https://arxiv.org/html/2609.13547#bib.bib14)\), combinatorial semi\-bandits\([Chen et al\., 2021](https://arxiv.org/html/2609.13547#bib.bib10)\), and nonstationary Markov decision processes\([Cheung et al\., 2020](https://arxiv.org/html/2609.13547#bib.bib12);[Mao et al\., 2021](https://arxiv.org/html/2609.13547#bib.bib17)\)\.[Wei and Luo \(2021\)](https://arxiv.org/html/2609.13547#bib.bib26)subsequently developed a prior\-free black\-box reduction that recovers the results for multi\-armed and contextual bandits and extends optimal dynamic\-regret adaptation to linear bandits and reinforcement learning\. Further developments in stochastic and contextual bandits include[Suk and Kpotufe \(2022\)](https://arxiv.org/html/2609.13547#bib.bib23);[Abbasi\-Yadkori et al\. \(2023\)](https://arxiv.org/html/2609.13547#bib.bib2);[Suk and Kpotufe \(2023\)](https://arxiv.org/html/2609.13547#bib.bib24)\. Related work has also studied bandit convex optimization and nonstationary stochastic optimization with bandit feedback\([Besbes et al\., 2015](https://arxiv.org/html/2609.13547#bib.bib8);[Zhao et al\., 2021](https://arxiv.org/html/2609.13547#bib.bib27);[Wang, 2025](https://arxiv.org/html/2609.13547#bib.bib25)\)\. These works study environmental nonstationarity or comparator path length, while our result instead adapts to the switch count of a hindsight comparator on arbitrary oblivious loss tables under finite\-armed bandit feedback\.

Another recent advance is[Rumi et al\. \(2026\)](https://arxiv.org/html/2609.13547#bib.bib20), which obtains the optimal𝒪~​\(d⁡\(S\+1\)​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{d\(S\+1\)T\}\)switching dependence for unconstrained adversarial linear bandits without knowingSS, up to the loss\-scale and comparator\-norm factors\. Their method exploits a scale–direction decomposition specific to the unbounded action spaceℝd\\mathbb\{R\}^\{d\}, and they note that extending it to constrained action sets is nontrivial\. Our finite\-armed bandit setting restricts each played action to one of theKKarms and reveals only that arm’s loss, so their result does not imply ours\.

## 2Preliminaries and Notation

##### Notation\.

For an integern≥1n\\geq 1, write\[n\]≜\{1,…,n\}\[n\]\\triangleq\\\{1,\\ldots,n\\\}\. LetΔK\\Delta\_\{K\}denote the probability simplex on\[K\]\[K\], defined byΔK≜\{x∈ℝK:∑i=1Kxi=1,xi≥0,∀i∈\[K\]\}\.\\Delta\_\{K\}\\triangleq\\\{x\\in\\mathbb\{R\}^\{K\}:\\sum\_\{i=1\}^\{K\}x\_\{i\}=1,x\_\{i\}\\geq 0,~\\forall i\\in\[K\]\\\}\.Leteie\_\{i\}denote theii\-th standard basis vector inℝK\\mathbb\{R\}^\{K\}, and write⟨x,y⟩\\left\\langle x,y\\right\\ranglefor the standard inner product\. We use bold symbols for sequences, writing𝐚=\{at\}t∈\[N\]\\mathbf\{a\}=\\\{a\_\{t\}\\\}\_\{t\\in\[N\]\}, where the lengthNNis understood from context\. The indicator of an event is denoted by𝕀​\{⋅\}\\mathbb\{I\}\\\{\\cdot\\\}\. All logarithms are natural unless a base is displayed, andlog\+⁡z≜max⁡\{0,log⁡z\}\\log^\{\+\}z\\triangleq\\max\\\{0,\\log z\\\}forz\>0z\>0\. Let𝟏\\mathbf\{1\}and𝟎\\mathbf\{0\}denote all\-one and all\-zero vectors in the appropriate dimension\. For probability vectorsx,yx,yin a common simplex, letKL\(x∥y\)\\text\{\\rm KL\}\(x\\\|y\)denote the Kullback\-Leibler divergence fromxxtoyy\.

##### Problem setting\.

AssumeT\>K≥2T\>K\\geq 2\. The interaction between the learner and the environment lasts forTTrounds\. Before the learner draws any private randomness, an*oblivious*adversary fixes a deterministic loss tableℓ∈\[0,1\]T×K\\ell\\in\[0,1\]^\{T\\times K\}whereKKis the number of actions\. Writeℓt=\(ℓt,1,…,ℓt,K\)\\ell\_\{t\}=\(\\ell\_\{t,1\},\\ldots,\\ell\_\{t,K\}\)for the loss vector at roundtt\. At each roundt∈\[T\]t\\in\[T\], the learner selects a distributionpt∈ΔKp\_\{t\}\\in\\Delta\_\{K\}using its past observations and private randomness, draws an armit∼pti\_\{t\}\\sim p\_\{t\}, incurs lossℓt,it\\ell\_\{t,i\_\{t\}\}, and observes only this selected loss\. All expectations are over the learner’s randomization for the fixed loss table\. There is no cost or constraint on the learner’s own changes of arm\.

##### Switching regret\.

ForS∈\{0,…,T−1\}S\\in\\\{0,\\ldots,T\-1\\\}, define the class of comparator sequences with at mostSSswitches by

𝒰S≜\{𝐮=\{ut\}t∈\[T\]:ut∈\{e1,…,eK\},∑t=2T𝕀\{ut≠ut−1\}≤S\}\.\\displaystyle\\mathcal\{U\}\_\{S\}\\triangleq\\left\\\{\\mathbf\{u\}=\\\{u\_\{t\}\\\}\_\{t\\in\[T\]\}:u\_\{t\}\\in\\\{e\_\{1\},\\ldots,e\_\{K\}\\\},\\ \\sum\_\{t=2\}^\{T\}\\mathbb\{I\}\\\{u\_\{t\}\\neq u\_\{t\-1\}\\\}\\leq S\\right\\\}\.\(1\)For eachSS, fix a best comparator

𝐮\(S\)≜\{ut\(S\)\}t∈\[T\]∈arg⁡min⁡∑t=1T𝐮∈𝒰S⁡⟨ut,ℓt⟩,\\displaystyle\\mathbf\{u\}^\{\(S\)\}\\triangleq\\\{u\_\{t\}^\{\(S\)\}\\\}\_\{t\\in\[T\]\}\\in\\arg\\min\_\{\\mathbf\{u\}\\in\\mathcal\{U\}\_\{S\}\}\\sum\_\{t=1\}^\{T\}\\left\\langle u\_\{t\},\\ell\_\{t\}\\right\\rangle,\(2\)breaking ties according to an arbitrary deterministic rule\. The comparator𝐮\(S\)\\mathbf\{u\}^\{\(S\)\}depends only on the loss table and is therefore fixed before the learner randomizes\. For the learner’s distribution sequence𝐩=\{pt\}t∈\[T\]\\mathbf\{p\}=\\\{p\_\{t\}\\\}\_\{t\\in\[T\]\}, define itsSS\-switching regret by

𝐑𝐞𝐠T​\(𝐮\(S\)\)≜∑t=1T⟨pt−ut\(S\),ℓt⟩\.\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\triangleq\\sum\_\{t=1\}^\{T\}\\left\\langle p\_\{t\}\-u\_\{t\}^\{\(S\)\},\\ell\_\{t\}\\right\\rangle\.Our goal is to design a single algorithm, without knowledge ofSS, such that𝔼⁡\[𝐑𝐞𝐠T​\(𝐮\(S\)\)\]≤𝒪~​\(\(S\+1\)​K​T\)\\mathbb\{E\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\widetilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{\(S\+1\)KT\}\\right\)for everyS∈\{0,…,T−1\}S\\in\\\{0,\\ldots,T\-1\\\}\. During the analysis, we also compare other decision sequences with𝐮\(S\)\\mathbf\{u\}^\{\(S\)\}over subintervals of the horizon\. For an intervalI⊆\[T\]I\\subseteq\[T\]and a possibly random sequence𝐚=\{at\}t∈\[T\]\\mathbf\{a\}=\\\{a\_\{t\}\\\}\_\{t\\in\[T\]\}withat∈ΔKa\_\{t\}\\in\\Delta\_\{K\}, define

𝐑𝐞𝐠I𝐚​\(𝐮\(S\)\)≜∑t∈I⟨at−ut\(S\),ℓt⟩\.\\displaystyle\\mathbf\{\\mathbf\{Reg\}\}\_\{I\}^\{\\mathbf\{a\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\triangleq\\sum\_\{t\\in I\}\\left\\langle a\_\{t\}\-u\_\{t\}^\{\(S\)\},\\ell\_\{t\}\\right\\rangle\.\(3\)In particular,𝐑𝐞𝐠T​\(𝐮\(S\)\)=𝐑𝐞𝐠\[T\]𝐩​\(𝐮\(S\)\)\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)=\\mathbf\{\\mathbf\{Reg\}\}\_\{\[T\]\}^\{\\mathbf\{p\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\.

## 3A Fixed\-Share Learner with Interval Subroutines

We now present a single algorithm that, without knowingSS, achieves𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)expected switching regret simultaneously for all switch budgetsSS\. The algorithm has three layers: a fixed\-share main learner, a collection of subroutines operating over canonical dyadic intervals, and an outer mechanism that increases the main learning rate when there is sufficient evidence that the current rate is too conservative\.

##### Algorithm intuition\.

To understand why these three layers are needed, first suppose thatSSis known\. A fixed\-share bandit learner with learning rateη\\etaadmits a regret bound of the form

𝒪⁡\(\(S\+1\)​log⁡\(K​T\)η\+η​K​T\);\\mathcal\{O\}\\left\(\\frac\{\(S\+1\)\\log\(KT\)\}\{\\eta\}\+\\eta KT\\right\);see, for example,[Auer et al\. \(2002\)](https://arxiv.org/html/2609.13547#bib.bib4)\. The two terms capture a basic tension\. A relatively small learning rate limits the stability cost and is appropriate when the comparator rarely switches, but it may respond too slowly when the comparator changes frequently\. A large learning rate is more responsive, but incurs a greater stability cost\. IfSSwere known, these two effects could be balanced in advance\. BecauseSSdescribes a hindsight comparator, however, the learner cannot determine the appropriate scale during play\.

Our key idea is to infer the need for greater responsiveness without estimatingSSor locating the switch points\. Instead, the algorithm looks for a locally estimable signal of an overly conservative learning rate: over some period, a fixed arm performs substantially better than the main learner\. This leads to the central design principle of our approach:*search for regret rather than switches*\.

Indeed, a comparator with at mostSSswitches plays a fixed arm on at mostS\+1S\+1contiguous segments\. If the main learner suffers large switching regret, this regret must therefore be reflected in local periods over which some fixed arm has a substantial advantage\. The locations and lengths of these periods are unknown, so the algorithm must search over many time scales simultaneously\. Canonical dyadic intervals provide an efficient multiscale scaffold: every comparator segment can be decomposed into only a logarithmic number of such intervals\. We therefore launch an auxiliary subroutine on each dyadic interval\. Each subroutine acts as a local challenger and tests whether shifting probability mass from the main distribution toward a particular arm would improve performance\. Rather than reconstructing the comparator, the subroutines collectively search for*local regret witnesses*\. The accumulated evidence from these witnesses provides the outer mechanism with a criterion for moving the main fixed\-share learner to a larger learning\-rate scale\. Crucially, we initialize each subroutine with*a strongly non\-uniform prior*: it places massT/\(T\+1\)T/\(T\+1\)on following the main distribution and spreads the remaining mass uniformly over theKKarms\. Each challenger therefore starts with a strong preference for the main distribution, while retaining the ability to shift toward a better arm\. Technically, this asymmetry keeps the initialization cost of the many subroutines that do not yield useful regret witnesses small, while allowing strong witnesses to pay for the cost of comparing with an alternative arm\.

There is one further difficulty: testing a challenger changes the outer main learner’s dynamic, making it harder to tell whether the challenger performs better than the main learner\. We address this by randomly separating the two roles\. On*main rounds*, only the fixed\-share learner updates\. On*challenge rounds*, which are reserved for testing, the main distribution is frozen while the active interval subroutines perturb the sampling distribution\. This separation provides a stable reference for evaluating the challengers\. The resulting bandit feedback is then converted into a running credit signal that estimates their cumulative improvement over the main distribution\.

Finally, the outer mechanism uses this credit to adapt the learning rate\. The algorithm begins with a conservative rate, protecting its performance when the comparator has few switches\. It restarts with a doubled learning rate only after the accumulated credit is sufficient to cover the additional stability cost of becoming more aggressive\. In this sense, the adaptation is*self\-financing*: the same local evidence indicating that the current rate is too small also pays for moving to the next rate\. The algorithm can therefore search across learning\-rate scales without ever knowing the comparator’s switch budget\.

For the interval updates, let𝒳=conv⁡\{𝟎,e1,…,eK\}\{\\mathcal\{X\}\}=\\operatorname\{conv\}\\\{\\mathbf\{0\},e\_\{1\},\\ldots,e\_\{K\}\\\}\. Forx,y∈𝒳x,y\\in\{\\mathcal\{X\}\}, define the completed vectorx¯=\(1−‖x‖1,x1,…,xK\)\\bar\{x\}=\(1\-\\\|x\\\|\_\{1\},x\_\{1\},\\ldots,x\_\{K\}\)and useKL\(x∥y\)≜KL\(x¯∥y¯\)\\text\{\\rm KL\}\(x\\\|y\)\\triangleq\\text\{\\rm KL\}\(\\bar\{x\}\\\|\\bar\{y\}\)\. The additional coordinate represents retaining the main distribution\.

Algorithm 1Fixed\-share main learner with dyadic interval subroutinesInput:Number of armsKKand horizonTT\.

1Set

L≜⌈20​log⁡\(2​K​T\)⌉L\\triangleq\\left\\lceil 20\\log\(2KT\)\\right\\rceil,

η1=100​LK​T\\eta\_\{1\}=\\frac\{100L\}\{\\sqrt\{KT\}\},

α=1100​L2\\alpha=\\frac\{1\}\{100L^\{2\}\}, and

Q=1000Q=1000\.

2Set

j=1j=1,

ηj=η1\\eta\_\{j\}=\\eta\_\{1\},

Cj=0C\_\{j\}=0,

𝒜=∅\{\\mathcal\{A\}\}=\\emptyset, and

q1,i=1/Kq\_\{1,i\}=1/Kfor all

i∈\[K\]i\\in\[K\]\.

3for*t=1,…,Tt=1,\\ldots,T*do

4foreach*canonical dyadic intervalJJ\(defined in[Eq\.\(4\)](https://arxiv.org/html/2609.13547#S3.E4)\) starting attt*do

5Draw

UJ∼Unif⁡\(0,1\)U\_\{J\}\\sim\\operatorname\{Unif\}\(0,1\)and set

ηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}\.

6Set

xt,J,i=1/\(K⁡\(T\+1\)\)x\_\{t,J,i\}=1/\(K\(T\+1\)\)for all

i∈\[K\]i\\in\[K\]and add

JJto

𝒜\{\\mathcal\{A\}\}\.

7Set

𝒜t=𝒜\{\\mathcal\{A\}\}\_\{t\}=\{\\mathcal\{A\}\}and draw

bt∼Bernoulli⁡\(1/2\)b\_\{t\}\\sim\\operatorname\{Bernoulli\}\(1/2\)\.

8if*bt=1b\_\{t\}=1*thenSet

pt=qtp\_\{t\}=q\_\{t\}\.

9elseSet

ptp\_\{t\}according to[Eq\. \(5\)](https://arxiv.org/html/2609.13547#S3.E5)\.

10Draw

it∼pti\_\{t\}\\sim p\_\{t\}and observe

ℓt,it\\ell\_\{t,i\_\{t\}\}\.

11if*bt=1b\_\{t\}=1*then

12Set

ℓ^t,iq=2𝕀\{i=it\}ℓt,it/qt,it\\widehat\{\\ell\}^\{q\}\_\{t,i\}=2\\mathbb\{I\}\\\{i=i\_\{t\}\\\}\\ell\_\{t,i\_\{t\}\}/q\_\{t,i\_\{t\}\}for all

ii\.

13Compute

q~t\+1=argminq∈ΔK\{ηj⟨q,ℓ^tq⟩\+KL\(q∥qt\)\}\\widetilde\{q\}\_\{t\+1\}=\\arg\\min\_\{q\\in\\Delta\_\{K\}\}\\\{\\eta\_\{j\}\\left\\langle q,\\widehat\{\\ell\}\_\{t\}^\{q\}\\right\\rangle\+\\text\{\\rm KL\}\(q\\\|q\_\{t\}\)\\\}\.

14Set

qt\+1,i=\(1−1/T\)​q~t\+1,i\+1/\(K​T\)q\_\{t\+1,i\}=\(1\-1/T\)\\widetilde\{q\}\_\{t\+1,i\}\+1/\(KT\)for all

ii\.

15Leave all interval states unchanged and set

Zt=0Z\_\{t\}=0\.

16else

17Set

qt\+1=qtq\_\{t\+1\}=q\_\{t\}\.

18foreach*J∈𝒜tJ\\in\{\\mathcal\{A\}\}\_\{t\}*do

19Set

ℓ^t,J,i=𝕀\{i=it\}ℓt,it/\(pt,it\+ηJ\)\\widehat\{\\ell\}\_\{t,J,i\}=\\mathbb\{I\}\\\{i=i\_\{t\}\\\}\\ell\_\{t,i\_\{t\}\}/\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)for all

ii\.

20Set

zt,J,i=ℓ^t,J,i−⟨qt,ℓ^t,J⟩z\_\{t,J,i\}=\\widehat\{\\ell\}\_\{t,J,i\}\-\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\ranglefor all

ii\.

21Set

xt\+1,J=argminx∈𝒳\{ηJ⟨x,zt,J⟩\+KL\(x∥xt,J\)\}x\_\{t\+1,J\}=\\arg\\min\_\{x\\in\{\\mathcal\{X\}\}\}\\\{\\eta\_\{J\}\\left\\langle x,z\_\{t,J\}\\right\\rangle\+\\text\{\\rm KL\}\(x\\\|x\_\{t,J\}\)\\\}\.

22Set

Zt=ℓt,it​\(qt,it/pt,it−1\)Z\_\{t\}=\\ell\_\{t,i\_\{t\}\}\(q\_\{t,i\_\{t\}\}/p\_\{t,i\_\{t\}\}\-1\)\.

23Set

Cj←Cj\+ZtC\_\{j\}\\leftarrow C\_\{j\}\+Z\_\{t\}\.

24if*Cj≥Q​K​T​ηjC\_\{j\}\\geq QKT\\eta\_\{j\}andt<Tt<T*then

j←j\+1j\\leftarrow j\+1,

ηj←2​ηj−1\\eta\_\{j\}\\leftarrow 2\\eta\_\{j\-1\},

Cj←0C\_\{j\}\\leftarrow 0,

𝒜←∅\{\\mathcal\{A\}\}\\leftarrow\\emptyset, and

qt\+1,i←1/Kq\_\{t\+1,i\}\\leftarrow 1/Kfor all

ii\.

25elseRemove from

𝒜\{\\mathcal\{A\}\}every

J∈𝒜tJ\\in\{\\mathcal\{A\}\}\_\{t\}with ending time round

tt\.

##### Algorithm walkthrough\.

We now follow[Algorithm1](https://arxiv.org/html/2609.13547#alg1)in its execution order while explaining how each step implements the preceding intuition\. Throughout the algorithm,qt∈ΔKq\_\{t\}\\in\\Delta\_\{K\}denotes the distribution maintained by the main fixed\-share learner, whereaspt∈ΔKp\_\{t\}\\in\\Delta\_\{K\}denotes the physical distribution from which the learner draws its arm\. The main learner provides the reference distribution, the interval subroutines test for local improvements over this reference, and the outer mechanism uses the detected improvement to determine when the main learning rate should be increased\.

The algorithm proceeds in consecutive random epochs\. During epochIjI\_\{j\}, the main learner uses the fixed learning rateηj\\eta\_\{j\}, andCjC\_\{j\}denotes the credit accumulated since the beginning of that epoch\. We set

L≜⌈20​log⁡\(2​K​T\)⌉,α≜1100​L2,η1≜100​LK​T,Q≜1000,L\\triangleq\\left\\lceil 20\\log\(2KT\)\\right\\rceil,\\qquad\\alpha\\triangleq\\frac\{1\}\{100L^\{2\}\},\\qquad\\eta\_\{1\}\\triangleq\\frac\{100L\}\{\\sqrt\{KT\}\},\\qquad Q\\triangleq 1000,as defined in[Algorithm1](https://arxiv.org/html/2609.13547#alg1)\. The algorithm starts with the conservative rateη1\\eta\_\{1\}, the uniform main distribution, and zero credit\. The rate remains fixed within an epoch and is doubled only when the accumulated credit reaches the restart threshold\.

The first step of each round implements the multiscale search for local regret witnesses\. For integersh,k≥0h,k\\geq 0satisfying\(k\+1\)​2h≤T\(k\+1\)2^\{h\}\\leq T, we call

Jk,h≜\{k​2h\+1,…,\(k\+1\)​2h\}\\displaystyle J\_\{k,h\}\\triangleq\\\{k2^\{h\}\+1,\\ldots,\(k\+1\)2^\{h\}\\\}\(4\)a*canonical dyadic interval*of length2h2^\{h\}and in the following, we useJJto represent a canonical dyadic interval in general\. These intervals are defined using the original global clock and are not shifted when a new epoch begins\. In[Line1](https://arxiv.org/html/2609.13547#alg1)and[Line1](https://arxiv.org/html/2609.13547#alg1), the algorithm launches a subroutine for every canonical dyadic interval beginning at the current round\. Since every constant segment of a switching comparator can be decomposed into only𝒪⁡\(log⁡T\)\\mathcal\{O\}\(\\log T\)such intervals, a large switching regret must be witnessed by a controlled number of subroutines\. This is how the algorithm implements the principle of searching for regret rather than switches\.

More concretely, each subroutine is an entropy\-OMD learner that maintainsxt,J∈𝒳x\_\{t,J\}\\in\{\\mathcal\{X\}\}\. Specifically, the coordinatext,J,ix\_\{t,J,i\}is the mass assigned to challengingqtq\_\{t\}with armii, whereas the missing mass1−‖xt,J‖11\-\\\|x\_\{t,J\}\\\|\_\{1\}represents retaining the main distribution\. This additional option allows a subroutine to remain close toqtq\_\{t\}when it has not found convincing evidence for any arm\. Crucially,[Line1](https://arxiv.org/html/2609.13547#alg1)uses a strongly non\-uniform initialization:xt,J,i=1/\(K⁡\(T\+1\)\)x\_\{t,J,i\}=1/\(K\(T\+1\)\), leaving massT/\(T\+1\)T/\(T\+1\)on retaining the main distribution\. This choice is essential to controlling the collective cost of the multiscale search\. Intuitively, this prior makes following the main learner the natural starting point for each challenger\. Many intervals may offer no useful improvement, so making it inexpensive to stay with the main distribution helps control the cost of searching across many time scales\. At the same time, every arm retains positive initial weight, allowing a challenger to shift toward a better arm when the feedback supports doing so\. At launch,[Line1](https://arxiv.org/html/2609.13547#alg1)drawsUJ∼Unif⁡\(0,1\)U\_\{J\}\\sim\\operatorname\{Unif\}\(0,1\)and assigns the rateηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}\. We first describe how the subroutine is used and return to the reason for this randomized choice at the end of the walkthrough\.

After launching the new subroutines,[Line1](https://arxiv.org/html/2609.13547#alg1)draws a fresh coinbt∼Bernoulli⁡\(1/2\)b\_\{t\}\\sim\\operatorname\{Bernoulli\}\(1/2\)that determines how the observed loss is used\. On a main round, wherebt=1b\_\{t\}=1, the learner setspt=qtp\_\{t\}=q\_\{t\}\. The observed loss is converted into an importance\-weighted loss vector and passed only to the main learner, while the interval states remain unchanged\. The factor22in the estimator compensates for entering the main branch with probability1/21/2, making the estimator unbiased\. The entropy\-OMD and fixed\-share update in[Line1](https://arxiv.org/html/2609.13547#alg1)then advancesqtq\_\{t\}and keeps all arms available for comparison with a switching sequence\.

On a challenge round, wherebt=0b\_\{t\}=0, the main distribution is instead frozen in[Line1](https://arxiv.org/html/2609.13547#alg1)\. The active subroutines perturb the physical distribution according to

pt=\(1−α​∑J∈𝒜t‖xt,J‖1\)​qt\+α​∑J∈𝒜txt,J,\\displaystyle p\_\{t\}=\\left\(1\-\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\\|x\_\{t,J\}\\\|\_\{1\}\\right\)q\_\{t\}\+\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}x\_\{t,J\},\(5\)where𝒜t\{\\mathcal\{A\}\}\_\{t\}is the collection of active subroutines\. Thus each subroutine transfers a small amount of probability mass fromqtq\_\{t\}toward the arms it currently considers promising, whileα\\alphalimits the aggregate influence of all challengers\. Freezingqtq\_\{t\}during this test is essential: it ensures that the reference distribution does not move in response to the same observation used to evaluate the challengers\. The routing step therefore realizes the separation between learning the reference and testing alternatives that was described in the intuition\.

After drawingit∼pti\_\{t\}\\sim p\_\{t\}and observingℓt,it\\ell\_\{t,i\_\{t\}\}, the algorithm conveys this single bandit observation to every active subroutine through a subroutine\-specific implicit\-exploration estimate\. Because the arm is sampled from the shared physical distributionptp\_\{t\}, rather than from the distribution proposed by any individual subroutine, it is important to have the implicit\-exploration offsetηJ\\eta\_\{J\}to prevent the estimate from becoming excessively large when this probability is small\. The estimated loss is then centered by the estimated loss ofqtq\_\{t\}before the OMD update in[Line1](https://arxiv.org/html/2609.13547#alg1)\. Consequently, the subroutine learns whether its proposed perturbation improves upon the main distribution, rather than attempting to minimize its loss in isolation\.

The improvement found on challenge rounds is summarized by the credit variable\. In[Line1](https://arxiv.org/html/2609.13547#alg1), the algorithm recordsZt=ℓt,it​\(qt,it/pt,it−1\)Z\_\{t\}=\\ell\_\{t,i\_\{t\}\}\(q\_\{t,i\_\{t\}\}/p\_\{t,i\_\{t\}\}\-1\)on a challenge round and setsZt=0Z\_\{t\}=0on a main round\. Conditional on the distributions chosen before the arm is drawn, the mean ofZtZ\_\{t\}is⟨qt−pt,ℓt⟩\\left\\langle q\_\{t\}\-p\_\{t\},\\ell\_\{t\}\\right\\rangle\. Positive credit therefore indicates that the challenger mixtureptp\_\{t\}has incurred less loss than the reference distributionqtq\_\{t\}\. Moreover, this credit enters with a negative sign when the physical regret is decomposed into the regret ofqtq\_\{t\}and the difference betweenptp\_\{t\}andqtq\_\{t\}\. It is therefore both evidence that the current main learner is insufficiently responsive and a resource for paying the cost of increasing its learning rate\.

The update in[Line1](https://arxiv.org/html/2609.13547#alg1)then addsZtZ\_\{t\}to the current epoch creditCjC\_\{j\}\. OnceCj≥Q​K​T​ηjC\_\{j\}\\geq QKT\\eta\_\{j\}, this indicates that the physical distribution has accumulated enough improvement over the main distribution to pay for the additional stability cost associated with doubling the learning rate\. Therefore,[Line1](https://arxiv.org/html/2609.13547#alg1)terminates epochIjI\_\{j\}, discards its active subroutines, resets the main distribution, and starts epochIj\+1I\_\{j\+1\}with zero credit and learning rateηj\+1=2​ηj\\eta\_\{j\+1\}=2\\eta\_\{j\}\. Thus the algorithm becomes more responsive only after the challengers have accumulated sufficient improvement to support this change\. This is the self\-financing adaptation described in the preceding intuition\.

It remains to explain the randomized learning rate in[Line1](https://arxiv.org/html/2609.13547#alg1), which is a key device allowing the local tests to operate without knowing the strength of the regret witness in advance\. For an armaa, define its cumulative advantage over the main distribution onJJbyAJ\(a\)≜∑t∈J:bt=0⟨qt−ea,ℓt⟩A\_\{J\}\(a\)\\triangleq\\sum\_\{t\\in J:b\_\{t\}=0\}\\left\\langle q\_\{t\}\-e\_\{a\},\\ell\_\{t\}\\right\\rangle\. A positive value means that armaaincurs less loss thanqtq\_\{t\}on the challenge rounds ofJJ\.

Recall that the purpose of the subroutine onJJis to test whether shifting probability mass fromqtq\_\{t\}toward a fixed arm can improve the learner’s performance onJJ, rather than to solve a separate bandit problem on its own\. At a high level,ηJ\\eta\_\{J\}determines how aggressively subroutineJJtests its alternatives\. A larger rate allows it to move probability mass away fromqtq\_\{t\}more quickly and hence react to a weaker or shorter\-lived advantage\. Such responsiveness is also more costly, because the subroutine becomes more sensitive to noisy bandit estimates\. A smaller rate keeps the subroutine closer toqtq\_\{t\}and is less costly, but requires a stronger or more persistent advantage before it reacts substantially\. SinceAJ​\(a\)A\_\{J\}\(a\)is unknown whenJJbegins, the algorithm cannot select the appropriate sensitivity directly\.

Consequently, the drawUJ∼Unif⁡\(0,1\)U\_\{J\}\\sim\\operatorname\{Unif\}\(0,1\)assigns each interval a random sensitivity level\. If an interval contains a strong regret witness, then a broad range of rate realizations can respond to it\. A weaker witness requires a more aggressive realization, but it also contributes less to the total regret\. The analysis therefore does not require every subroutine to receive the appropriate rate\. Instead, it aggregates the credit generated by the subroutines that happen to be sufficiently responsive and uses their contributions to control the total advantage over the dyadic cover\. At the same time, using the sameηJ\\eta\_\{J\}as the implicit\-exploration offset limits the estimation cost of aggressive subroutines\.

We can now state the switching\-regret guarantee of[Algorithm1](https://arxiv.org/html/2609.13547#alg1)\.

###### Theorem 3\.1\.

For every oblivious loss tableℓ∈\[0,1\]T×K\\ell\\in\[0,1\]^\{T\\times K\}, and everyS∈\{0,…,T−1\}S\\in\\\{0,\\ldots,T\-1\\\},[Algorithm1](https://arxiv.org/html/2609.13547#alg1)guarantees

𝔼⁡\[𝐑𝐞𝐠T​\(𝐮\(S\)\)\]≤𝒪⁡\(\(S\+1\)​K​T​log4⁡\(K​T\)\)\.\\displaystyle\\mathbb\{E\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\sqrt\{\(S\+1\)KT\}\\log^\{4\}\(KT\)\\right\)\.\(6\)

To our knowledge,[Algorithm1](https://arxiv.org/html/2609.13547#alg1)is the first algorithm for finite\-armed adversarial bandits that, against every oblivious loss table, achieves the minimax\-optimal dependence𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)simultaneously for everyS∈\{0,…,T−1\}S\\in\\\{0,\\ldots,T\-1\\\}without prior knowledge ofSS\. This resolves the adversarial switching\-regret problem posed by[Auer et al\. \(2019b\)](https://arxiv.org/html/2609.13547#bib.bib6)and subsequently highlighted by[Marinov and Zimmert \(2021\)](https://arxiv.org/html/2609.13547#bib.bib18);[Luo et al\. \(2022\)](https://arxiv.org/html/2609.13547#bib.bib16);[Qian and Wei \(2026\)](https://arxiv.org/html/2609.13547#bib.bib19)\.

##### Proof overview\.

LetI1,…,INI\_\{1\},\\ldots,I\_\{N\}denote the epochs reached by the algorithm, letHj≜\|Ij\|H\_\{j\}\\triangleq\|I\_\{j\}\|, and letCj≜∑t∈IjZtC\_\{j\}\\triangleq\\sum\_\{t\\in I\_\{j\}\}Z\_\{t\}be the credit accumulated during epochIjI\_\{j\}\. We write𝔼j​\[⋅\]\\mathbb\{E\}\_\{j\}\[\\cdot\]for expectation conditional on the history beforeIjI\_\{j\}begins\. SinceZtZ\_\{t\}has conditional mean⟨qt−pt,ℓt⟩\\left\\langle q\_\{t\}\-p\_\{t\},\\ell\_\{t\}\\right\\ranglegiven the information available before samplingiti\_\{t\}, we have

𝔼⁡\[𝐑𝐞𝐠T​\(𝐮\(S\)\)\]=𝔼⁡\[∑j=1N𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)−∑j=1NCj\]\.\\displaystyle\\mathbb\{E\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]=\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]\.\(7\)We therefore bound the regret of the main sequence\{qt\}t∈\[T\]\\\{q\_\{t\}\\\}\_\{t\\in\[T\]\}while retaining the negative credit until the terms it pays for have been identified\.

We use two complementary bounds within each epoch\. The standard fixed\-share analysis gives

𝔼j​\[𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)\]≤𝒪~​\(\(S\+1\)/ηj\)\+𝒪⁡\(ηj​K​𝔼j​\[Hj\]\)\.\\mathbb\{E\}\_\{j\}\[\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\]\\leq\\widetilde\{\\mathcal\{O\}\}\(\(S\+1\)/\\eta\_\{j\}\)\+\\mathcal\{O\}\(\\eta\_\{j\}K\\mathbb\{E\}\_\{j\}\[H\_\{j\}\]\)\.The inverse\-rate term decreases withηj\\eta\_\{j\}, whereas the stability term will be paid by the accumulated credit\. This bound is therefore useful at the larger learning\-rate scales\. Whenηj\\eta\_\{j\}is small, however, its inverse\-rate term can be much larger than the desired regret\.

For the small\-rate epochs, we instead use the interval subroutines to control the regret of the main sequence directly, which is the key technical ingredient enabling adaptation to an unknown switch budget\. Restricting the comparator to an epoch and decomposing each of its constant pieces into canonical dyadic intervals produces at most𝒪⁡\(\(S\+1\)​L\)\\mathcal\{O\}\(\(S\+1\)L\)disjoint intervals\. On each such intervalJJ, letaJa\_\{J\}be the arm played by the deterministic comparator for a fixedSS\. The subroutine associated withJJtests whetheraJa\_\{J\}substantially outperforms the main distribution on that interval\. Aggregating these tests over the dyadic cover gives

𝔼j​\[𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)\]≤𝒪⁡\(ηj​K​T​L2\+\(S\+1\)​K​T​L3\)\.\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\eta\_\{j\}KTL^\{2\}\+\\sqrt\{\(S\+1\)KT\}\\,L^\{3\}\\right\)\.\(8\)The credit process is used internally to prove this bound: the restart threshold limits the total improvement that the interval subroutines can accumulate within an epoch\. Importantly, the right\-hand side of[Eq\. \(8\)](https://arxiv.org/html/2609.13547#S3.E8)contains no credit term\. Thus, all credit terms in[Eq\. \(7\)](https://arxiv.org/html/2609.13547#S3.E7)remain available for the final amortization argument\.

We also point out that the randomized learning rateηJ\\eta\_\{J\}is essential to[Eq\. \(8\)](https://arxiv.org/html/2609.13547#S3.E8)\. For a dyadic intervalJJ, define the advantage ofaJa\_\{J\}over the main distribution on the challenge rounds byAJ≜∑t∈J:bt=0⟨qt−eaJ,ℓt⟩A\_\{J\}\\triangleq\\sum\_\{t\\in J:b\_\{t\}=0\}\\left\\langle q\_\{t\}\-e\_\{a\_\{J\}\},\\ell\_\{t\}\\right\\rangle\. ForAJ\>0A\_\{J\}\>0, the OMD inequality, up to estimation costs, lower\-bounds the improvement obtained by the corresponding subroutine byAJ−𝒪⁡\(L/ηJ\)A\_\{J\}\-\\mathcal\{O\}\(L/\\eta\_\{J\}\)\. Thus, the subroutine recovers a constant fraction ofAJA\_\{J\}wheneverηJ\\eta\_\{J\}is at least a constant multiple ofL/AJL/A\_\{J\}\. The difficulty is thatAJA\_\{J\}is unknown whenJJbegins\. Under the choiceηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}, whereUJ∼Unif⁡\(0,1\)U\_\{J\}\\sim\\operatorname\{Unif\}\(0,1\), the probability thatηJ\\eta\_\{J\}exceeds the scale required for an advantageAJA\_\{J\}is proportional toAJA\_\{J\}, up to truncation at one\. Hence, intervals with larger advantages are more likely to receive sufficiently responsive subroutines, whereas intervals with smaller advantages contribute less regret\. Aggregating these local tests over the dyadic cover gives the𝒪⁡\(\(S\+1\)​K​T​L3\)\\mathcal\{O\}\(\\sqrt\{\(S\+1\)KT\}\\,L^\{3\}\)term in[Eq\. \(8\)](https://arxiv.org/html/2609.13547#S3.E8), while their aggregate estimation and update costs contribute𝒪⁡\(ηj​K​T​L2\)\\mathcal\{O\}\(\\eta\_\{j\}KTL^\{2\}\)\.

One technical issue remains: the endpoint of an epoch is determined by the credit process and therefore depends on the randomized subroutines\. The full proof handles this technical issue by first suppressing restarts and analyzing a fixed\-rate continuation of the epoch\. It establishes the required bounds simultaneously over all deterministic prefixes and then evaluates them at the actual epoch endpoint\.

Finally, fixSSfor the analysis and split the epochs atηj=Θ⁡\(η1​S\+1\)\\eta\_\{j\}=\\Theta\(\\eta\_\{1\}\\sqrt\{S\+1\}\)\. Below this cutoff, we apply[Eq\. \(8\)](https://arxiv.org/html/2609.13547#S3.E8); above it, we use the fixed\-share bound\. The credit\-amortization argument shows that the credits of the completed epochs pay for the fixed\-share stability terms, while a separate debt bound controls the credit of the final, possibly incomplete epoch\. As the learning rate doubles between epochs, the sum of the small\-rate termsηj​K​T\\eta\_\{j\}KTis dominated by the cutoff rate, while the sum of the large\-rate inverse terms is dominated by the first rate above the cutoff\. Substitutingη1=Θ~​\(1/K​T\)\\eta\_\{1\}=\\widetilde\{\\Theta\}\(1/\\sqrt\{KT\}\)yields𝒪~​\(\(S\+1\)​K​T\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\+1\)KT\}\)regret\.

## 4Proof of[Theorem3\.1](https://arxiv.org/html/2609.13547#S3.Thmtheorem1)

In this section, we prove[Theorem3\.1](https://arxiv.org/html/2609.13547#S3.Thmtheorem1)in the steps outlined above\. FixS∈\{0,…,T−1\}S\\in\\\{0,\\ldots,T\-1\\\}and the deterministic comparator𝐮\(S\)\\mathbf\{u\}^\{\(S\)\}determined by the oblivious loss table\. For every reached epoch, writeIj=\{τj,…,ρj\}I\_\{j\}=\\\{\\tau\_\{j\},\\ldots,\\rho\_\{j\}\\\}andHj=ρj−τj\+1H\_\{j\}=\\rho\_\{j\}\-\\tau\_\{j\}\+1, whereτj\\tau\_\{j\}andρj\\rho\_\{j\}are its first and last rounds, respectively\. Letℱj\{\\mathcal\{F\}\}\_\{j\}denote the history before roundτj\\tau\_\{j\}, and write𝔼j\[⋅\]≜𝔼\[⋅∣ℱj\]\\mathbb\{E\}\_\{j\}\[\\cdot\]\\triangleq\\mathbb\{E\}\[\\cdot\\mid\{\\mathcal\{F\}\}\_\{j\}\]\. LetNNbe the number of reached epochs\. All sums over epochs below include only reached epochs; equivalently, unreached contributions are interpreted as zero\.

We use two within\-round histories\. Letℋt\\mathcal\{H\}\_\{t\}contain all randomness revealed before drawingbtb\_\{t\}, including the rates of newly launched intervals, and let𝒢t=σ⁡\(ℋt,bt\)\\mathcal\{G\}\_\{t\}=\\sigma\(\\mathcal\{H\}\_\{t\},b\_\{t\}\)\. Thusqtq\_\{t\}isℋt\\mathcal\{H\}\_\{t\}\-measurable, whileptp\_\{t\}is𝒢t\\mathcal\{G\}\_\{t\}\-measurable andit∼pti\_\{t\}\\sim p\_\{t\}conditional on𝒢t\\mathcal\{G\}\_\{t\}\. For the interval updates on𝒳\{\\mathcal\{X\}\}, we use the completed relative entropy defined in[Section3](https://arxiv.org/html/2609.13547#S3)\.

At most one canonical interval of each length is active at a given round, so\|𝒜t\|≤L\|\{\\mathcal\{A\}\}\_\{t\}\|\\leq L\. Sinceα​L≤1/2\\alpha L\\leq 1/2, the mixture in[Eq\. \(5\)](https://arxiv.org/html/2609.13547#S3.E5)givespt≥qt/2p\_\{t\}\\geq q\_\{t\}/2coordinatewise on challenge rounds\. Consequently,\|Zt\|≤1\|Z\_\{t\}\|\\leq 1\. We will use this bound to control the overshoot at an epoch endpoint\.

##### Step 1: decompose the regret across epochs\.

For every reached epoch, defineCj≜∑t∈IjZtC\_\{j\}\\triangleq\\sum\_\{t\\in I\_\{j\}\}Z\_\{t\}to be the cumulative credit at the end of epochjj\. Conditional on𝒢t\\mathcal\{G\}\_\{t\}, the distributionsptp\_\{t\}andqtq\_\{t\}are fixed andit∼pti\_\{t\}\\sim p\_\{t\}\. Hence, on a challenge round,

𝔼⁡\[Zt∣𝒢t\]\\displaystyle\\mathbb\{E\}\[Z\_\{t\}\\mid\\mathcal\{G\}\_\{t\}\]=∑i=1Kpt,i​ℓt,i​\(qt,ipt,i−1\)=⟨qt−pt,ℓt⟩\.\\displaystyle=\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\ell\_\{t,i\}\\left\(\\frac\{q\_\{t,i\}\}\{p\_\{t,i\}\}\-1\\right\)=\\left\\langle q\_\{t\}\-p\_\{t\},\\ell\_\{t\}\\right\\rangle\.On a main round, both sides are zero becausept=qtp\_\{t\}=q\_\{t\}andZt=0Z\_\{t\}=0\. Summing this identity over the horizon and using the partition into epochs gives

𝔼⁡\[𝐑𝐞𝐠T​\(𝐮\(S\)\)\]=𝔼⁡\[∑j=1N𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)−∑j=1NCj\]\.\\displaystyle\\mathbb\{E\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]=\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]\.\(9\)We retain the negative credit term until Step 3\.

##### Step 2: establish two bounds for\{qt\}t∈\[T\]\\\{q\_\{t\}\\\}\_\{t\\in\[T\]\}sequence\.

The first bound follows from the fixed\-share analysis\. The first term accounts for comparator switches, while the second is the stability cost of the bandit estimates\.

###### Lemma 4\.1\.

For every reached epochIjI\_\{j\},

𝔼j​\[𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)\]≤3​\(S\+1\)​log⁡\(K​T\)ηj\+ηj​K​𝔼j​\[Hj\]\.\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\frac\{3\(S\+1\)\\log\(KT\)\}\{\\eta\_\{j\}\}\+\\eta\_\{j\}K\\mathbb\{E\}\_\{j\}\[H\_\{j\}\]\.\(10\)

The proof is deferred to[AppendixA\.2](https://arxiv.org/html/2609.13547#A1.SS2)\. However, as mentioned before, the inverse\-rate term in[Eq\. \(10\)](https://arxiv.org/html/2609.13547#S4.E10)is too large whenηj\\eta\_\{j\}is small\. We therefore use the interval subroutines to obtain a complementary bound in order to control the case whereηj\\eta\_\{j\}is small, which is the key component of the analysis\. We first isolate the technical statement that captures their contribution\.

We first define several notations which will be useful in the analysis\. Fix a reached epochIjI\_\{j\}\. To handle its random endpoint, we define a coupled fixed\-rate continuation starting from the algorithm’s state at the beginning of roundτj\\tau\_\{j\}\. This auxiliary process keeps the outer rate equal toηj\\eta\_\{j\}and suppresses all subsequent restarts until global timeTT\. It uses the same random variables as the actual algorithm through roundρj\\rho\_\{j\}and fresh continuation randomness afterward\. Since the adversary is oblivious, both processes run against the same fixed loss table, including afterρj\\rho\_\{j\}\.

LetZt\(j,cont\)Z\_\{t\}^\{\(j,\\mathrm\{cont\}\)\}be the credit sample generated by this auxiliary process at roundtt, and, for everyn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, defineCj,ncont≜∑t=τjnZt\(j,cont\)C\_\{j,n\}^\{\\mathrm\{cont\}\}\\triangleq\\sum\_\{t=\\tau\_\{j\}\}^\{n\}Z\_\{t\}^\{\(j,\\mathrm\{cont\}\)\}\. By construction, the continuation and the actual algorithm coincide onIjI\_\{j\}, soCj,ρjcont=∑t=τjρjZt=CjC\_\{j,\\rho\_\{j\}\}^\{\\mathrm\{cont\}\}=\\sum\_\{t=\\tau\_\{j\}\}^\{\\rho\_\{j\}\}Z\_\{t\}=C\_\{j\}\. Let𝒥\\mathcal\{J\}denote the fixed family of canonical dyadic intervals in\[T\]\[T\], defined using the original global clock, and set

𝒥j≜\{J∈𝒥:min⁡J≥τj\}\.\\displaystyle\\mathcal\{J\}\_\{j\}\\triangleq\\\{J\\in\\mathcal\{J\}:\\min J\\geq\\tau\_\{j\}\\\}\.Thus𝒥j\\mathcal\{J\}\_\{j\}contains every interval scheduled to start fromτj\\tau\_\{j\}throughTT, including those starting afterρj\\rho\_\{j\}\. Restarts do not change this launch schedule\. They discard active subroutines and change the outer rate used for subsequent launches\. In the continuation, everyJ∈𝒥jJ\\in\\mathcal\{J\}\_\{j\}instead receives the rateηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}and runs for its full interval\. We define the aggregate charge over this entire continuation by

Γj≜∑J∈𝒥j\|J\|​min⁡\{K​ηJ,α\},\\displaystyle\\Gamma\_\{j\}\\triangleq\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\}\|J\|\\min\\\{K\\eta\_\{J\},\\alpha\\\},\(11\)where\|J\|\|J\|denotes the length of intervalJJ\. Specifically,Γj\\Gamma\_\{j\}serves as a common budget for estimation and curvature costs across the interval subroutines in the continuation\.

For every endpointn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, decompose each constant piece of the comparator on\{τj,…,n\}\\\{\\tau\_\{j\},\\ldots,n\\\}into maximal contained canonical dyadic intervals\. Denote this disjoint family by𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\), and letaJa\_\{J\}be the comparator arm onJ∈𝒟j​\(n\)J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\. In the fixed\-rate continuation, define

AJ​\(n\)≜∑t∈J,bt=0⟨qt−eaJ,ℓt⟩\.\\displaystyle A\_\{J\}\(n\)\\triangleq\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,b\_\{t\}=0\\end\{subarray\}\}\\left\\langle q\_\{t\}\-e\_\{a\_\{J\}\},\\ell\_\{t\}\\right\\rangle\.\(12\)for allJ∈𝒟j​\(n\)J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\. Here and below, per\-round quantities inside a continuation calculation refer to that continuation\. Note that for a fixed endpointnn, conditioning onℱj\{\\mathcal\{F\}\}\_\{j\}, all continuation routing bits, and the independent main\-action seeds*fixes*the reference pathqtq\_\{t\}and hence the advantagesAJ​\(n\)A\_\{J\}\(n\), while leaving theUJU\_\{J\}independent and uniform\. This is due to the obliviousness of the losses and the fact that the continuation updatesqtq\_\{t\}only on main rounds and never restarts\. At the actual endpoint, the cover𝒟j​\(ρj\)\{\\mathcal\{D\}\}\_\{j\}\(\\rho\_\{j\}\)and advantagesAJ​\(ρj\)A\_\{J\}\(\\rho\_\{j\}\)coincide with those generated by the algorithm onIjI\_\{j\}\.

Our next goal is to bound the sum of the advantages over this cover, shown in the following lemma\. Since each round is routed to a challenge round with probability1/21/2independently of the preceding history, the same bound, up to a factor of two, also controls the expected regret of the full main sequence\.

###### Lemma 4\.2\.

[Algorithm1](https://arxiv.org/html/2609.13547#alg1)guarantees that every reached epochIjI\_\{j\}satisfies

𝔼j​\[∑J∈𝒟j​\(ρj\)AJ​\(ρj\)\]≤𝒪⁡\(ηj​K​T​L2\+\(S\+1\)​K​T​L3\)\.\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(\\rho\_\{j\}\)\}A\_\{J\}\(\\rho\_\{j\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\eta\_\{j\}KTL^\{2\}\+\\sqrt\{\(S\+1\)KT\}\\,L^\{3\}\\right\)\.\(13\)Consequently, we also have

𝔼j​\[𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)\]≤𝒪⁡\(ηj​K​T​L2\+\(S\+1\)​K​T​L3\)\.\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\eta\_\{j\}KTL^\{2\}\+\\sqrt\{\(S\+1\)KT\}\\,L^\{3\}\\right\)\.\(14\)

To prove this lemma, we use several supporting results shown as follows\. The first lemma bounds the size of the comparator\-dependent dyadic cover\. The comparator has at mostS\+1S\+1constant segments, each requiring only𝒪⁡\(log⁡T\)\\mathcal\{O\}\(\\log T\)canonical dyadic intervals, so the total cover size is𝒪⁡\(\(S\+1\)​log⁡T\)\\mathcal\{O\}\(\(S\+1\)\\log T\)\.

###### Lemma 4\.3\.

Fix a comparator sequence𝐮\(S\)\\mathbf\{u\}^\{\(S\)\}with at mostSSswitches\. For every reached epochIjI\_\{j\}and everyn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, the family𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)partitions\{τj,…,n\}\\\{\\tau\_\{j\},\\ldots,n\\\}, the comparator is constant on everyJ∈𝒟j​\(n\)J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\), and\|𝒟j​\(n\)\|≤\(S\+1\)​L\|\{\\mathcal\{D\}\}\_\{j\}\(n\)\|\\leq\(S\+1\)L\.

The proof is deferred to[AppendixA\.3](https://arxiv.org/html/2609.13547#A1.SS3)and follows by counting dyadic intervals within each constant segment\. We next select the intervals whose randomized rates allow their advantages to pay the OMD initialization costs\. Set

m≜\(S\+1\)​L,dj≜64​Lηj,δ0≜\(2​K​T\)−10\.\\displaystyle m\\triangleq\(S\+1\)L,\\qquad d\_\{j\}\\triangleq\\frac\{64L\}\{\\eta\_\{j\}\},\\qquad\\delta\_\{0\}\\triangleq\(2KT\)^\{\-10\}\.For everyJ∈𝒟j​\(n\)J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\), define

gJ​\(n\)\\displaystyle g\_\{J\}\(n\)≜α​AJ​\(n\),\\displaystyle\\triangleq\\alpha A\_\{J\}\(n\),XJ​\(n\)\\displaystyle X\_\{J\}\(n\)≜𝕀\{ηJAJ\(n\)≥64L\},\\displaystyle\\triangleq\\mathbb\{I\}\\\{\\eta\_\{J\}A\_\{J\}\(n\)\\geq 64L\\\},\(15\)Wj​\(n\)\\displaystyle W\_\{j\}\(n\)≜∑J∈𝒟j​\(n\)gJ​\(n\)​XJ​\(n\),\\displaystyle\\triangleq\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}g\_\{J\}\(n\)X\_\{J\}\(n\),wheregJ​\(n\)g\_\{J\}\(n\)is the scaled signed advantage onJJ,XJ​\(n\)X\_\{J\}\(n\)marks intervals whose advantage can cover the OMD initialization cost at rateηJ\\eta\_\{J\}, andWj​\(n\)W\_\{j\}\(n\)is their total scaled advantage\. Since only positive advantages can be selected,Wj​\(n\)≥0W\_\{j\}\(n\)\\geq 0\.

The next lemma uses the conditional independence established above to bound the full signed sum throughWj​\(n\)W\_\{j\}\(n\)\. We will then controlWj​\(n\)W\_\{j\}\(n\)using the credit bound and the restart rule, yielding[Eq\. \(13\)](https://arxiv.org/html/2609.13547#S4.E13)\.

###### Lemma 4\.4\.

For every reached epochIjI\_\{j\}and every fixed continuation endpointn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, conditional onℱj\{\\mathcal\{F\}\}\_\{j\}, with probability at least1−δ01\-\\delta\_\{0\},

∑J∈𝒟j​\(n\)AJ​\(n\)≤Wj​\(n\)\+dj​L/2α\+2​m​dj​\(Wj​\(n\)\+dj​L/2\)α\.\\displaystyle\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}A\_\{J\}\(n\)\\leq\\frac\{W\_\{j\}\(n\)\+d\_\{j\}L/2\}\{\\alpha\}\+\\frac\{\\sqrt\{2md\_\{j\}\\bigl\(W\_\{j\}\(n\)\+d\_\{j\}L/2\\bigr\)\}\}\{\\alpha\}\.\(16\)

The proof is deferred to[AppendixA\.4](https://arxiv.org/html/2609.13547#A1.SS4)\. Under the conditioning above, the valuesgJ​\(n\)g\_\{J\}\(n\)do not depend on the random rates\. Intervals withgJ​\(n\)≤0g\_\{J\}\(n\)\\leq 0are never selected, those withgJ​\(n\)≥djg\_\{J\}\(n\)\\geq d\_\{j\}are always selected, and each interval with0<gJ​\(n\)<dj0<g\_\{J\}\(n\)<d\_\{j\}is selected with probabilitygJ​\(n\)/djg\_\{J\}\(n\)/d\_\{j\}\. An optimized exponential\-moment argument then relates the full signed sum of the advantages to the selected advantageWj​\(n\)W\_\{j\}\(n\)\.

It remains to relateWj​\(n\)W\_\{j\}\(n\)to the observable credit\. For every selected interval, we compare its subroutine witheaJe\_\{a\_\{J\}\}\. Every other subroutine is compared with𝟎\\mathbf\{0\}\. Under the completion used in the interval OMD update,𝟎\\mathbf\{0\}places all its mass on the reference coordinate, so this amounts to comparing the subroutine with the reference distributionqtq\_\{t\}\. This controls every unselected subroutine relative toqtq\_\{t\}*without paying the initialization penalty*associated with a particular arm and this also explains the reason for a non\-uniform prior\. For a selected interval, comparison witheaJe\_\{a\_\{J\}\}incurs an initialization penalty of𝒪⁡\(α​L/ηJ\)\\mathcal\{O\}\(\\alpha L/\\eta\_\{J\}\)\. The selection conditionηJ​AJ​\(n\)≥64​L\\eta\_\{J\}A\_\{J\}\(n\)\\geq 64Lensures that this penalty is at mostgJ​\(n\)/64g\_\{J\}\(n\)/64\. Hence, the total initialization penalty removes at mostWj​\(n\)/64W\_\{j\}\(n\)/64from the selected advantage\.

The next key lemma then shows that the credit retains a constant fraction ofWj​\(n\)W\_\{j\}\(n\)after accounting for these initialization penalties\. Its proof is rather technical and combines several ingredients\. First, the OMD analysis converts the selected advantages into credit and implicit exploration controls the importance\-weighted loss estimates, which provides concentration to the true losses at the price of a small bias\. With oblivious losses, conditioning on the routing and main\-action randomness fixes the reference path and hence the interval advantagesAJ​\(n\)A\_\{J\}\(n\)for each fixed endpointnn\. The selection conditionηJ​AJ​\(n\)≥64​L\\eta\_\{J\}A\_\{J\}\(n\)\\geq 64Lthen depends only on the interval rates\. Revealing these rates determines the selected family without exposing the challenge\-action randomness\. Conditional on this information and the preceding challenge observations, each challenge arm is still sampled fromptp\_\{t\}, so the loss estimates retain the conditional moment bounds needed for concentration\. The resulting estimation\-bias and OMD curvature costs are controlled byΓj\\Gamma\_\{j\}\. The complete proof is deferred to[AppendixA\.5](https://arxiv.org/html/2609.13547#A1.SS5)\.

###### Lemma 4\.5\.

For every reached epochIjI\_\{j\}and every fixed continuation endpointn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, conditional onℱj\{\\mathcal\{F\}\}\_\{j\}, with probability at least1−δ01\-\\delta\_\{0\},

Cj,ncont≥34​Wj​\(n\)−K​T​ηj20−4​Γj\.\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}\\geq\\frac\{3\}\{4\}W\_\{j\}\(n\)\-\\frac\{KT\\eta\_\{j\}\}\{20\}\-4\\Gamma\_\{j\}\.\(17\)

This lemma will be used in two ways\. In the proof of[Lemma4\.2](https://arxiv.org/html/2609.13547#S4.Thmtheorem2), we evaluate[Eq\. \(17\)](https://arxiv.org/html/2609.13547#S4.E17)at the actual epoch endpointn=ρjn=\\rho\_\{j\}\. The restart rule and the boundZt≤1Z\_\{t\}\\leq 1giveCj,ρjcont=Cj≤Q​K​T​ηj\+1C\_\{j,\\rho\_\{j\}\}^\{\\mathrm\{cont\}\}=C\_\{j\}\\leq QKT\\eta\_\{j\}\+1, which yields an upper bound onWj​\(ρj\)W\_\{j\}\(\\rho\_\{j\}\)\. SinceWj​\(n\)≥0W\_\{j\}\(n\)\\geq 0, the same inequality also givesCj,ncont≥−KTηj/20−4ΓjC\_\{j,n\}^\{\\mathrm\{cont\}\}\\geq\-KT\\eta\_\{j\}/20\-4\\Gamma\_\{j\}\. This lower bound will be used in Step 3 to control the possible credit deficit in the final epoch, which may end without reaching the restart threshold\. It remains to controlΓj\\Gamma\_\{j\}\. AlthoughηJ\\eta\_\{J\}has infinite expectation, each contribution toΓj\\Gamma\_\{j\}is truncated, which gives the finite expectation below\.

###### Lemma 4\.6\.

For every reached epochIjI\_\{j\},[Algorithm1](https://arxiv.org/html/2609.13547#alg1)guarantees that𝔼j​\[Γj\]≤K​T​ηj100\.\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]\\leq\\frac\{KT\\eta\_\{j\}\}\{100\}\.

The proof is via a direct calculation and is deferred to[AppendixA\.6](https://arxiv.org/html/2609.13547#A1.SS6)\. We now combine the preceding three lemmas to bound the signed dyadic advantage\.

###### Proof of[Lemma4\.2](https://arxiv.org/html/2609.13547#S4.Thmtheorem2)\.

Fix a reached epoch and condition onℱj\{\\mathcal\{F\}\}\_\{j\}\. Letℰj\\mathcal\{E\}\_\{j\}be the event that both[Eq\. \(16\)](https://arxiv.org/html/2609.13547#S4.E16)and[Eq\. \(17\)](https://arxiv.org/html/2609.13547#S4.E17)hold for everyn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}\. Applying[Lemma4\.4](https://arxiv.org/html/2609.13547#S4.Thmtheorem4)and[Lemma4\.5](https://arxiv.org/html/2609.13547#S4.Thmtheorem5)at each fixed endpoint and taking a union bound givesℙ⁡\(ℰj∣ℱj\)≥1−2​T​δ0\\mathbb\{P\}\(\\mathcal\{E\}\_\{j\}\\mid\{\\mathcal\{F\}\}\_\{j\}\)\\geq 1\-2T\\delta\_\{0\}\. On this event, we may evaluate both estimates atn=ρjn=\\rho\_\{j\}even thoughρj\\rho\_\{j\}is random\.

SinceCj,ρjcont=CjC\_\{j,\\rho\_\{j\}\}^\{\\mathrm\{cont\}\}=C\_\{j\}, the restart rule and\|Zt\|≤1\|Z\_\{t\}\|\\leq 1giveCj≤Q​K​T​ηj\+1C\_\{j\}\\leq QKT\\eta\_\{j\}\+1\. Combining this inequality with[Eq\. \(17\)](https://arxiv.org/html/2609.13547#S4.E17), and usingK​T​ηj≥1KT\\eta\_\{j\}\\geq 1, yields, onℰj\\mathcal\{E\}\_\{j\},

Wj​\(ρj\)≤2​\(Q\+1\)​K​T​ηj\+8​Γj\.\\displaystyle W\_\{j\}\(\\rho\_\{j\}\)\\leq 2\(Q\+1\)KT\\eta\_\{j\}\+8\\Gamma\_\{j\}\.\(18\)Moreover, based on the choice ofdjd\_\{j\}, we havedj​LK​T​ηj=64​L2K​T​ηj2≤6410000<1\.\\frac\{d\_\{j\}L\}\{KT\\eta\_\{j\}\}=\\frac\{64L^\{2\}\}\{KT\\eta\_\{j\}^\{2\}\}\\leq\\frac\{64\}\{10000\}<1\.Onℰj\\mathcal\{E\}\_\{j\},[Eq\. \(18\)](https://arxiv.org/html/2609.13547#S4.E18)anddj​L≤K​T​ηjd\_\{j\}L\\leq KT\\eta\_\{j\}giveWj​\(ρj\)\+dj​L2≤2​\(Q\+1\)​K​T​ηj\+8​Γj\+K​T​ηj2=𝒪⁡\(K​T​ηj\+Γj\)\.W\_\{j\}\(\\rho\_\{j\}\)\+\\frac\{d\_\{j\}L\}\{2\}\\leq 2\(Q\+1\)KT\\eta\_\{j\}\+8\\Gamma\_\{j\}\+\\frac\{KT\\eta\_\{j\}\}\{2\}=\\mathcal\{O\}\(KT\\eta\_\{j\}\+\\Gamma\_\{j\}\)\.Substituting into[Eq\. \(16\)](https://arxiv.org/html/2609.13547#S4.E16)therefore yields

∑J∈𝒟j​\(ρj\)AJ​\(ρj\)≤𝒪⁡\(K​T​ηj\+Γj\+m​dj​\(K​T​ηj\+Γj\)α\)\.\\displaystyle\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(\\rho\_\{j\}\)\}A\_\{J\}\(\\rho\_\{j\}\)\\leq\\mathcal\{O\}\\left\(\\frac\{KT\\eta\_\{j\}\+\\Gamma\_\{j\}\+\\sqrt\{md\_\{j\}\(KT\\eta\_\{j\}\+\\Gamma\_\{j\}\)\}\}\{\\alpha\}\\right\)\.
Onℰjc\\mathcal\{E\}\_\{j\}^\{c\}, the signed sum is at mostTT, andℙ⁡\(ℰjc∣ℱj\)≤2​T​δ0\\mathbb\{P\}\(\\mathcal\{E\}\_\{j\}^\{c\}\\mid\{\\mathcal\{F\}\}\_\{j\}\)\\leq 2T\\delta\_\{0\}\. Since the preceding upper bound is nonnegative, taking conditional expectations and then applying Jensen’s inequality gives

𝔼j​\[∑J∈𝒟j​\(ρj\)AJ​\(ρj\)\]\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(\\rho\_\{j\}\)\}A\_\{J\}\(\\rho\_\{j\}\)\\right\]≤𝒪⁡\(K​T​ηj\+𝔼j​\[Γj\]\+m​dj​𝔼j​\[K​T​ηj\+Γj\]α\+2​T2​δ0\)\\displaystyle\\leq\\mathcal\{O\}\\left\(\\frac\{KT\\eta\_\{j\}\+\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]\+\\sqrt\{md\_\{j\}\}\\,\\mathbb\{E\}\_\{j\}\[\\sqrt\{KT\\eta\_\{j\}\+\\Gamma\_\{j\}\}\]\}\{\\alpha\}\+2T^\{2\}\\delta\_\{0\}\\right\)≤𝒪⁡\(K​T​ηj\+𝔼j​\[Γj\]\+m​dj​\(K​T​ηj\+𝔼j​\[Γj\]\)α\+1\)\\displaystyle\\leq\\mathcal\{O\}\\left\(\\frac\{KT\\eta\_\{j\}\+\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]\+\\sqrt\{md\_\{j\}\(KT\\eta\_\{j\}\+\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]\)\}\}\{\\alpha\}\+1\\right\)≤𝒪⁡\(K​T​ηj\+m​dj​K​T​ηjα\+1\)\.\\displaystyle\\leq\\mathcal\{O\}\\left\(\\frac\{KT\\eta\_\{j\}\+\\sqrt\{md\_\{j\}KT\\eta\_\{j\}\}\}\{\\alpha\}\+1\\right\)\.Here we used2​T2​δ0≤12T^\{2\}\\delta\_\{0\}\\leq 1and, in the last inequality,𝔼j​\[Γj\]≤K​T​ηj/100\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]\\leq KT\\eta\_\{j\}/100from[Lemma4\.6](https://arxiv.org/html/2609.13547#S4.Thmtheorem6)\. Since1/α=100​L21/\\alpha=100L^\{2\}andm​dj​K​T​ηj=64​\(S\+1\)​K​T​L2md\_\{j\}KT\\eta\_\{j\}=64\(S\+1\)KTL^\{2\}, this proves[Eq\. \(13\)](https://arxiv.org/html/2609.13547#S4.E13)\.

To obtain[Eq\. \(14\)](https://arxiv.org/html/2609.13547#S4.E14), setft≜⟨qt−ut\(S\),ℓt⟩f\_\{t\}\\triangleq\\left\\langle q\_\{t\}\-u\_\{t\}^\{\(S\)\},\\ell\_\{t\}\\right\\rangle\. Because the comparator and loss sequence are chosen in advance, beforebtb\_\{t\}is drawn, bothftf\_\{t\}and the event that roundttbelongs toIjI\_\{j\}are determined by the preceding history\. Sinceℙ⁡\(bt=0∣ℋt\)=1/2\\mathbb\{P\}\(b\_\{t\}=0\\mid\\mathcal\{H\}\_\{t\}\)=1/2, the tower property gives

𝔼j\[𝐑𝐞𝐠Ij𝐪\(𝐮\(S\)\)\]=2𝔼j\[∑t∈Ij:bt=0ft\]=2𝔼j\[∑J∈𝒟j​\(ρj\)AJ\(ρj\)\]\.\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]=2\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{t\\in I\_\{j\}:b\_\{t\}=0\}f\_\{t\}\\right\]=2\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(\\rho\_\{j\}\)\}A\_\{J\}\(\\rho\_\{j\}\)\\right\]\.Combining this identity with[Eq\. \(13\)](https://arxiv.org/html/2609.13547#S4.E13)proves[Eq\. \(14\)](https://arxiv.org/html/2609.13547#S4.E14)\. ∎

##### Step 3: use the credit to pay the stability terms\.

Every completed epoch reaches the restart threshold and therefore has credit at leastQ​K​T​ηjQKT\\eta\_\{j\}\. Only the final epoch can end before reaching this threshold, so its credit may be negative\. To control this possible deficit at its random endpoint, defineFj≜maxτj≤n≤T⁡\(−Cj,ncont\)\+\.F\_\{j\}\\triangleq\\max\_\{\\tau\_\{j\}\\leq n\\leq T\}\\left\(\-C\_\{j,n\}^\{\\mathrm\{cont\}\}\\right\)\_\{\+\}\.This is the largest debt incurred by the fixed\-rate continuation over all possible endpoints\. Since the actual epoch and its continuation coincide throughρj\\rho\_\{j\}, its credit is at least−Fj\-F\_\{j\}\. Moreover,Wj​\(n\)≥0W\_\{j\}\(n\)\\geq 0, so dropping this nonnegative term from[Eq\. \(17\)](https://arxiv.org/html/2609.13547#S4.E17)gives a lower bound on the credit at every fixed endpoint\. Combining these endpoint\-wise bounds with[Lemma4\.6](https://arxiv.org/html/2609.13547#S4.Thmtheorem6)gives the following estimate\.

###### Lemma 4\.7\.

Every reached epochIjI\_\{j\}satisfies𝔼j​\[Fj\]≤K​T​ηj10\.\\mathbb\{E\}\_\{j\}\[F\_\{j\}\]\\leq\\frac\{KT\\eta\_\{j\}\}\{10\}\.

###### Proof\.

For each fixedn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\},[Eq\. \(17\)](https://arxiv.org/html/2609.13547#S4.E17)andWj​\(n\)≥0W\_\{j\}\(n\)\\geq 0implyCj,ncont≥−KTηj/20−4ΓjC\_\{j,n\}^\{\\mathrm\{cont\}\}\\geq\-KT\\eta\_\{j\}/20\-4\\Gamma\_\{j\}except on an event of conditional probability at mostδ0\\delta\_\{0\}\. A union bound over the possible endpoints therefore givesFj≤K​T​ηj/20\+4​ΓjF\_\{j\}\\leq KT\\eta\_\{j\}/20\+4\\Gamma\_\{j\}with conditional probability at least1−T​δ01\-T\\delta\_\{0\}\. On the failure event, the deterministic boundFj≤TF\_\{j\}\\leq Tfollows because every continuation credit increment has absolute value at most one\. Taking conditional expectations and applying[Lemma4\.6](https://arxiv.org/html/2609.13547#S4.Thmtheorem6)yields

𝔼j​\[Fj\]≤K​T​ηj20\+4​𝔼j​\[Γj\]\+T2​δ0≤K​T​ηj20\+4​K​T​ηj100\+K​T​ηj100=K​T​ηj10\.\\displaystyle\\mathbb\{E\}\_\{j\}\[F\_\{j\}\]\\leq\\frac\{KT\\eta\_\{j\}\}\{20\}\+4\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]\+T^\{2\}\\delta\_\{0\}\\leq\\frac\{KT\\eta\_\{j\}\}\{20\}\+\\frac\{4KT\\eta\_\{j\}\}\{100\}\+\\frac\{KT\\eta\_\{j\}\}\{100\}=\\frac\{KT\\eta\_\{j\}\}\{10\}\.The choicesδ0=\(2​K​T\)−10\\delta\_\{0\}=\(2KT\)^\{\-10\}andηj≥η1=100​L/K​T\\eta\_\{j\}\\geq\\eta\_\{1\}=100L/\\sqrt\{KT\}ensureT2​δ0≤K​T​ηj/100T^\{2\}\\delta\_\{0\}\\leq KT\\eta\_\{j\}/100\. ∎

We next compare the total credit with the fixed\-share stability cost\. Each completed epoch contributes at leastQ​K​T​ηjQKT\\eta\_\{j\}in credit and incurs at mostK​T​ηjKT\\eta\_\{j\}in stability\. The final epoch may instead contribute a deficit, but[Lemma4\.7](https://arxiv.org/html/2609.13547#S4.Thmtheorem7)controls this deficit in expectation\. Since the learning rates double across epochs, the credit accumulated before the final epoch absorbs both the stability costs and the expected final deficit\. The following lemma makes this self\-financing property precise\.

###### Lemma 4\.8\.

The epoch credits satisfy𝔼⁡\[∑j=1Nηj​K​Hj−∑j=1NCj\]≤1110​K​T​η1\.\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\eta\_\{j\}KH\_\{j\}\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]\\leq\\frac\{11\}\{10\}KT\\eta\_\{1\}\.

###### Proof\.

Whether epochjjis reached is determined before that epoch begins\. We may therefore condition on its initial history\. Applying[Lemma4\.7](https://arxiv.org/html/2609.13547#S4.Thmtheorem7)and the tower property then gives

𝔼⁡\[∑j=1NFj\]≤K​T10​𝔼​\[∑j=1Nηj\]\.\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}F\_\{j\}\\right\]\\leq\\frac\{KT\}\{10\}\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\eta\_\{j\}\\right\]\.\(19\)Every completed epochj<Nj<NsatisfiesCj≥Q​K​T​ηjC\_\{j\}\\geq QKT\\eta\_\{j\}, whereas the final epoch satisfiesCN≥−FNC\_\{N\}\\geq\-F\_\{N\}\. Since everyFjF\_\{j\}is nonnegative, we can lower bound∑j=1NCj\\sum\_\{j=1\}^\{N\}C\_\{j\}as follows:

∑j=1NCj≥Q​K​T​∑j=1N−1ηj−∑j=1NFj\.\\displaystyle\\sum\_\{j=1\}^\{N\}C\_\{j\}\\geq QKT\\sum\_\{j=1\}^\{N\-1\}\\eta\_\{j\}\-\\sum\_\{j=1\}^\{N\}F\_\{j\}\.\(20\)Taking expectations, applying[Eq\. \(19\)](https://arxiv.org/html/2609.13547#S4.E19), together with∑j=1Nηj=η1\+2​∑j=1N−1ηj\\sum\_\{j=1\}^\{N\}\\eta\_\{j\}=\\eta\_\{1\}\+2\\sum\_\{j=1\}^\{N\-1\}\\eta\_\{j\}andHj≤TH\_\{j\}\\leq Tgive that

𝔼⁡\[∑j=1Nηj​K​Hj−∑j=1NCj\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\eta\_\{j\}KH\_\{j\}\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]≤𝔼⁡\[∑j=1Nηj​K​T−Q​K​T​∑j=1N−1ηj\+∑j=1NFj\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\eta\_\{j\}KT\-QKT\\sum\_\{j=1\}^\{N\-1\}\\eta\_\{j\}\+\\sum\_\{j=1\}^\{N\}F\_\{j\}\\right\]≤1110​K​T​η1−\(Q−2−15\)​K​T​𝔼​\[∑j=1N−1ηj\]≤1110​K​T​η1,\\displaystyle\\leq\\frac\{11\}\{10\}KT\\eta\_\{1\}\-\\left\(Q\-2\-\\frac\{1\}\{5\}\\right\)KT\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\-1\}\\eta\_\{j\}\\right\]\\leq\\frac\{11\}\{10\}KT\\eta\_\{1\},where the last inequality usesQ=1000Q=1000\. This proves the result\. ∎

##### Step 4: combine the two epoch bounds\.

Finally, we apply the two main\-sequence bounds in complementary rate regimes\. For any fixed value ofSS, letjSj\_\{S\}be the largest deterministic index satisfyingηjS≤η1​S\+1\\eta\_\{j\_\{S\}\}\\leq\\eta\_\{1\}\\sqrt\{S\+1\}\. Becauseηj=2j−1​η1\\eta\_\{j\}=2^\{j\-1\}\\eta\_\{1\}, there are at mostLLsuch indices and∑j=1jSηj≤2​η1​S\+1\.\\sum\_\{j=1\}^\{j\_\{S\}\}\\eta\_\{j\}\\leq 2\\eta\_\{1\}\\sqrt\{S\+1\}\.Applying[Lemma4\.2](https://arxiv.org/html/2609.13547#S4.Thmtheorem2)to the reached epochs withj≤jSj\\leq j\_\{S\}, then using the tower property and the geometric sum, gives

𝔼⁡\[∑j≤jS𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)\]≤𝒪⁡\(η1​K​T​S\+1​L2\+\(S\+1\)​K​T​L4\)\.\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{j\\leq j\_\{S\}\}\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\eta\_\{1\}KT\\sqrt\{S\+1\}\\,L^\{2\}\+\\sqrt\{\(S\+1\)KT\}\\,L^\{4\}\\right\)\.\(21\)For the reached epochs withj\>jSj\>j\_\{S\}, apply[Lemma4\.1](https://arxiv.org/html/2609.13547#S4.Thmtheorem1)\. SinceηjS\+1\>η1​S\+1\\eta\_\{j\_\{S\}\+1\}\>\\eta\_\{1\}\\sqrt\{S\+1\}and the learning rates double, the inverse\-rate terms form a geometric sum controlled by their first term\. Therefore,

𝔼⁡\[∑j\>jS𝐑𝐞𝐠Ij𝐪​\(𝐮\(S\)\)\]≤𝒪⁡\(S\+1​log⁡\(K​T\)η1\)\+𝔼⁡\[∑j\>jSηj​K​Hj\]\.\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{j\>j\_\{S\}\}\\mathbf\{\\mathbf\{Reg\}\}\_\{I\_\{j\}\}^\{\\mathbf\{q\}\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\frac\{\\sqrt\{S\+1\}\\log\(KT\)\}\{\\eta\_\{1\}\}\\right\)\+\\mathbb\{E\}\\left\[\\sum\_\{j\>j\_\{S\}\}\\eta\_\{j\}KH\_\{j\}\\right\]\.\(22\)
Substituting[Eq\. \(21\)](https://arxiv.org/html/2609.13547#S4.E21)and[Eq\. \(22\)](https://arxiv.org/html/2609.13547#S4.E22)into[Eq\. \(9\)](https://arxiv.org/html/2609.13547#S4.E9)gives

𝔼⁡\[𝐑𝐞𝐠T​\(𝐮\(S\)\)\]\\displaystyle\\mathbb\{E\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]≤𝒪⁡\(η1​K​T​S\+1​L2\+\(S\+1\)​K​T​L4\+S\+1​log⁡\(K​T\)η1\)\\displaystyle\\leq\\mathcal\{O\}\\left\(\\eta\_\{1\}KT\\sqrt\{S\+1\}\\,L^\{2\}\+\\sqrt\{\(S\+1\)KT\}\\,L^\{4\}\+\\frac\{\\sqrt\{S\+1\}\\log\(KT\)\}\{\\eta\_\{1\}\}\\right\)\+𝔼⁡\[∑j\>jSηj​K​Hj−∑j=1NCj\]\.\\displaystyle\\qquad\+\\mathbb\{E\}\\left\[\\sum\_\{j\>j\_\{S\}\}\\eta\_\{j\}KH\_\{j\}\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]\.Since each stability termηj​K​Hj\\eta\_\{j\}KH\_\{j\}is nonnegative,[Lemma4\.8](https://arxiv.org/html/2609.13547#S4.Thmtheorem8)gives that

𝔼⁡\[∑j\>jSηj​K​Hj−∑j=1NCj\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{j\>j\_\{S\}\}\\eta\_\{j\}KH\_\{j\}\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]≤𝔼⁡\[∑j=1Nηj​K​Hj−∑j=1NCj\]≤1110​K​T​η1\.\\displaystyle\\leq\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{N\}\\eta\_\{j\}KH\_\{j\}\-\\sum\_\{j=1\}^\{N\}C\_\{j\}\\right\]\\leq\\frac\{11\}\{10\}KT\\eta\_\{1\}\.Combining these inequalities yields

𝔼⁡\[𝐑𝐞𝐠T​\(𝐮\(S\)\)\]≤𝒪⁡\(η1​K​T​S\+1​L2\+\(S\+1\)​K​T​L4\+S\+1​log⁡\(K​T\)η1\+K​T​η1\)\.\\displaystyle\\mathbb\{E\}\\left\[\\mathbf\{\\mathbf\{Reg\}\}\_\{T\}\(\\mathbf\{u\}^\{\(S\)\}\)\\right\]\\leq\\mathcal\{O\}\\left\(\\eta\_\{1\}KT\\sqrt\{S\+1\}\\,L^\{2\}\+\\sqrt\{\(S\+1\)KT\}\\,L^\{4\}\+\\frac\{\\sqrt\{S\+1\}\\log\(KT\)\}\{\\eta\_\{1\}\}\+KT\\eta\_\{1\}\\right\)\.\(23\)Finally, substitutingη1=100​L/K​T\\eta\_\{1\}=100L/\\sqrt\{KT\}andL=⌈20​log⁡\(2​K​T\)⌉L=\\lceil 20\\log\(2KT\)\\rceilinto[Eq\. \(23\)](https://arxiv.org/html/2609.13547#S4.E23)finishes the proof\.

## 5Conclusion

We study switching regret for adversarial multi\-armed bandits when the comparator’s switch count is unknown\. Against an oblivious loss table, a single algorithm achieves𝒪⁡\(\(S\+1\)​K​T​log4⁡\(K​T\)\)\\mathcal\{O\}\(\\sqrt\{\(S\+1\)KT\}\\log^\{4\}\(KT\)\)expected regret for every switch budgetSS\. The algorithm obtains this adaptation by letting interval subroutines earn observable credit and using that credit to fund increases of the main learning rate\. Two complementary epochwise estimates separate the cost of insufficient sensitivity from the stability cost of a larger rate\. Future work includes further reducing the logarithmic factors and extending the construction to broader bandit problems such as linear and convex bandits\.

##### Acknowledgments\.

The author used GPT\-6 for assistance with writing and to explore proof strategies\. The author has checked the arguments and takes full responsibility for the content of the paper\.

## References

- Abbasi\-Yadkoriet al\.\(2023\)Y\. Abbasi\-Yadkori, A\. György, and N\. LazićA new look at dynamic regret for non\-stationary stochastic bandits\.Journal of Machine Learning Research24\(288\)\.Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Audibert and Bubeck \(2009\)J\. Audibert and S\. BubeckMinimax policies for adversarial and stochastic bandits\.InConference on Learning Theory,Cited by:[§1](https://arxiv.org/html/2609.13547#S1.p1.1)\.
- Aueret al\.\(2002\)P\. Auer, N\. Cesa\-Bianchi, Y\. Freund, and R\. E\. SchapireThe nonstochastic multiarmed bandit problem\.SIAM Journal on Computing32\(1\)\.Cited by:[§A\.2](https://arxiv.org/html/2609.13547#A1.SS2.p1.1),[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.13547#S1.p1.1),[§1](https://arxiv.org/html/2609.13547#S1.p3.1),[§3](https://arxiv.org/html/2609.13547#S3.SS0.SSS0.Px1.p1.2),[Abstract](https://arxiv.org/html/2609.13547#abstract1.1)\.
- Aueret al\.\(2019a\)P\. Auer, Y\. Chen, P\. Gajane, C\. Lee, H\. Luo, R\. Ortner, and C\. WeiAchieving optimal dynamic regret for non\-stationary bandits without prior information\.InConference on Learning Theory,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2609.13547#S1.p2.1)\.
- Aueret al\.\(2019b\)P\. Auer, P\. Gajane, and R\. OrtnerAdaptively tracking the best bandit arm with an unknown number of distribution changes\.InConference on Learning Theory,Cited by:[§1](https://arxiv.org/html/2609.13547#S1.SS0.SSS0.Px1.p1.1),[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2609.13547#S1.p2.1),[§3](https://arxiv.org/html/2609.13547#S3.SS0.SSS0.Px2.p14.1),[Abstract](https://arxiv.org/html/2609.13547#abstract1.1)\.
- Besbeset al\.\(2014\)O\. Besbes, Y\. Gur, and A\. ZeeviStochastic multi\-armed\-bandit problem with non\-stationary rewards\.InAdvances in Neural Information Processing Systems,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Besbeset al\.\(2015\)O\. Besbes, Y\. Gur, and A\. ZeeviNon\-stationary stochastic optimization\.Operations Research63\(5\)\.Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Beygelzimeret al\.\(2011\)A\. Beygelzimer, J\. Langford, L\. Li, L\. Reyzin, and R\. SchapireContextual bandit algorithms with supervised learning guarantees\.InInternational Conference on Artificial Intelligence and Statistics,Cited by:[§A\.7\.2](https://arxiv.org/html/2609.13547#A1.SS7.SSS2.p10.3.1),[§A\.7\.2](https://arxiv.org/html/2609.13547#A1.SS7.SSS2.p13.8.1)\.
- Chenet al\.\(2021\)W\. Chen, L\. Wang, H\. Zhao, and K\. ZhengCombinatorial semi\-bandit in the non\-stationary environment\.InConference on Uncertainty in Artificial Intelligence,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Chenet al\.\(2019\)Y\. Chen, C\. Lee, H\. Luo, and C\. WeiA new algorithm for non\-stationary contextual bandits: efficient, optimal and parameter\-free\.InConference on Learning Theory,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Cheunget al\.\(2019\)W\. C\. Cheung, D\. Simchi\-Levi, and R\. ZhuLearning to optimize under non\-stationarity\.InInternational Conference on Artificial Intelligence and Statistics,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Cheunget al\.\(2020\)W\. C\. Cheung, D\. Simchi\-Levi, and R\. ZhuReinforcement learning for non\-stationary Markov decision processes: the blessing of \(More\) optimism\.InInternational Conference on Machine Learning,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Cheunget al\.\(2022\)W\. C\. Cheung, D\. Simchi\-Levi, and R\. ZhuHedging the drift: learning to optimize under nonstationarity\.Management Science68\(3\)\.Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px1.p2.1)\.
- Fauryet al\.\(2021\)L\. Faury, Y\. Russac, M\. Abeille, and C\. CalauzènesA technical note on non\-stationary parametric bandits: existing mistakes and preliminary solutions\.InAlgorithmic Learning Theory,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Luoet al\.\(2018\)H\. Luo, C\. Wei, A\. Agarwal, and J\. LangfordEfficient contextual bandits in non\-stationary worlds\.InConference on Learning Theory,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Luoet al\.\(2022\)H\. Luo, M\. Zhang, P\. Zhao, and Z\. ZhouCorralling a larger band of bandits: a case study on switching regret for linear bandits\.InConference on Learning Theory,Cited by:[§3](https://arxiv.org/html/2609.13547#S3.SS0.SSS0.Px2.p14.1)\.
- Maoet al\.\(2021\)W\. Mao, K\. Zhang, R\. Zhu, D\. Simchi\-Levi, and T\. BasarNear\-optimal model\-free reinforcement learning in non\-stationary episodic MDPs\.InInternational Conference on Machine Learning,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Marinov and Zimmert \(2021\)T\. V\. Marinov and J\. ZimmertThe Pareto frontier of model selection for general contextual bandits\.InAdvances in Neural Information Processing Systems,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2609.13547#S1.p3.1),[§3](https://arxiv.org/html/2609.13547#S3.SS0.SSS0.Px2.p14.1),[Abstract](https://arxiv.org/html/2609.13547#abstract1.1)\.
- Neu \(2015\)G\. NeuExplore no more: improved high\-probability regret bounds for non\-stochastic bandits\.InAdvances in Neural Information Processing Systems,Cited by:[§A\.7\.2](https://arxiv.org/html/2609.13547#A1.SS7.SSS2.p1.1),[§A\.7\.2](https://arxiv.org/html/2609.13547#A1.SS7.SSS2.p12.1.1)\.
- Qian and Wei \(2026\)J\. Qian and C\. WeiAchieving optimal static and dynamic regret simultaneously in bandits with deterministic losses\.Note:arXiv:2602\.07418External Links:2602\.07418Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px1.p2.1),[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px1.p3.1),[§1](https://arxiv.org/html/2609.13547#S1.p4.1),[§3](https://arxiv.org/html/2609.13547#S3.SS0.SSS0.Px2.p14.1)\.
- Rumiet al\.\(2026\)A\. Rumi, A\. Jacobsen, N\. Cesa\-Bianchi, and F\. VitaleParameter\-free dynamic regret for unconstrained linear bandits\.InInternational Conference on Artificial Intelligence and Statistics,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p2.1)\.
- Russacet al\.\(2021\)Y\. Russac, L\. Faury, O\. Cappé, and A\. GarivierSelf\-concordant analysis of generalized linear bandits with forgetting\.InInternational Conference on Artificial Intelligence and Statistics,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Russacet al\.\(2019\)Y\. Russac, C\. Vernade, and O\. CappéWeighted linear bandits for non\-stationary environments\.InAdvances in Neural Information Processing Systems,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Suk and Kpotufe \(2022\)J\. Suk and S\. KpotufeTracking most significant arm switches in bandits\.InConference on Learning Theory,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2609.13547#S1.p2.1)\.
- Suk and Kpotufe \(2023\)J\. Suk and S\. KpotufeTracking most significant shifts in nonparametric contextual bandits\.InAdvances in Neural Information Processing Systems,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Wang \(2025\)Y\. WangOn adaptivity in nonstationary stochastic optimization with bandit feedback\.Operations Research73\(2\)\.Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.
- Wei and Luo \(2021\)C\. Wei and H\. LuoNon\-stationary reinforcement learning without prior knowledge: an optimal black\-box approach\.InConference on Learning Theory,Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2609.13547#S1.p2.1)\.
- Zhaoet al\.\(2021\)P\. Zhao, G\. Wang, L\. Zhang, and Z\. ZhouBandit convex optimization in non\-stationary environments\.Journal of Machine Learning Research22\(125\)\.Cited by:[§1\.1](https://arxiv.org/html/2609.13547#S1.SS1.SSS0.Px2.p1.1)\.

## Appendix AOmitted Details in[Section4](https://arxiv.org/html/2609.13547#S4)

This appendix supplies the proofs deferred from[Section4](https://arxiv.org/html/2609.13547#S4)\.[AppendixA\.1](https://arxiv.org/html/2609.13547#A1.SS1)records the histories and conditional independence used throughout the analysis\.[AppendixA\.2](https://arxiv.org/html/2609.13547#A1.SS2)proves the fixed\-share bound, and[AppendixA\.3](https://arxiv.org/html/2609.13547#A1.SS3)constructs the comparator’s dyadic cover\.[AppendixA\.4](https://arxiv.org/html/2609.13547#A1.SS4)recovers the full advantage from the selected intervals;[AppendixA\.5](https://arxiv.org/html/2609.13547#A1.SS5)relates their advantage to credit; and[AppendixA\.6](https://arxiv.org/html/2609.13547#A1.SS6)bounds the expected continuation charge\. Finally,[AppendixA\.7](https://arxiv.org/html/2609.13547#A1.SS7)collects the OMD analysis and proves the technical lemma on the shared credit comparison\.

### A\.1Histories and conditioning

We retainℱj\{\\mathcal\{F\}\}\_\{j\},ℋt\\mathcal\{H\}\_\{t\}, and𝒢t\\mathcal\{G\}\_\{t\}with their meanings in[Section4](https://arxiv.org/html/2609.13547#S4)\. Letℋtend\\mathcal\{H\}\_\{t\}^\{\\mathrm\{end\}\}denote the history of observations and random variables revealed through the update and restart decision at roundtt, withℋ0end\\mathcal\{H\}\_\{0\}^\{\\mathrm\{end\}\}containing only the fixed input\. Then

ℋt\\displaystyle\\mathcal\{H\}\_\{t\}=σ⁡\(ℋt−1end,\(UJ\)J​launched at​t\),\\displaystyle=\\sigma\\bigl\(\\mathcal\{H\}\_\{t\-1\}^\{\\mathrm\{end\}\},\(U\_\{J\}\)\_\{J\\text\{ launched at \}t\}\\bigr\),𝒢t\\displaystyle\\mathcal\{G\}\_\{t\}=σ⁡\(ℋt,bt\),\\displaystyle=\\sigma\(\\mathcal\{H\}\_\{t\},b\_\{t\}\),ℋt−1end\\displaystyle\\mathcal\{H\}\_\{t\-1\}^\{\\mathrm\{end\}\}⊆ℋt⊆𝒢t⊆ℋtend\.\\displaystyle\\subseteq\\mathcal\{H\}\_\{t\}\\subseteq\\mathcal\{G\}\_\{t\}\\subseteq\\mathcal\{H\}\_\{t\}^\{\\mathrm\{end\}\}\.In particular, the epoch\-start history isℱj=ℋτj−1end\{\\mathcal\{F\}\}\_\{j\}=\\mathcal\{H\}\_\{\\tau\_\{j\}\-1\}^\{\\mathrm\{end\}\}, before the interval launches atτj\\tau\_\{j\}\. Here the right\-hand side denotes the stopped sigma\-algebra, sinceτj−1\\tau\_\{j\}\-1is a stopping time for\(ℋtend\)t=0T\(\\mathcal\{H\}\_\{t\}^\{\\mathrm\{end\}\}\)\_\{t=0\}^\{T\}\. For an unreached epoch, setτj=T\+1\\tau\_\{j\}=T\+1; then\{j≤N\}∈ℱj\\\{j\\leq N\\\}\\in\{\\mathcal\{F\}\}\_\{j\}\. Moreover,𝕀\{t∈Ij\}\\mathbb\{I\}\\\{t\\in I\_\{j\}\\\}isℋt\\mathcal\{H\}\_\{t\}\-measurable, because the restart decision is made after roundttand the threshold\-crossing round remains inIjI\_\{j\}\.

To couple each epoch with its fixed\-rate continuation, assign to every deterministic epoch indexjja collection of random variables: routing bitsbj,t∼Bernoulli⁡\(1/2\)b\_\{j,t\}\\sim\\operatorname\{Bernoulli\}\(1/2\), interval\-rate variablesUj,Jrate∼Unif⁡\(0,1\)U\_\{j,J\}^\{\\mathrm\{rate\}\}\\sim\\operatorname\{Unif\}\(0,1\), and action\-sampling variablesUj,tmain,Uj,tchal∼Unif⁡\(0,1\)U\_\{j,t\}^\{\\mathrm\{main\}\},U\_\{j,t\}^\{\\mathrm\{chal\}\}\\sim\\operatorname\{Unif\}\(0,1\)\. These variables are mutually independent across all epochs, rounds, intervals, and types\. The routing bit determines whether roundttuses the main or challenge branch\. The variableUj,JrateU\_\{j,J\}^\{\\mathrm\{rate\}\}determines the learning rate assigned to intervalJJ\. The variablesUj,tmainU\_\{j,t\}^\{\\mathrm\{main\}\}andUj,tchalU\_\{j,t\}^\{\\mathrm\{chal\}\}are used to sample the arm on the main and challenge branches, respectively\. Concretely, a uniform variableuusamples from a distributionr∈ΔKr\\in\\Delta\_\{K\}by choosing

i=min⁡\{a∈\[K\]:u≤∑k=1ark\}\.i=\\min\\left\\\{a\\in\[K\]:u\\leq\\sum\_\{k=1\}^\{a\}r\_\{k\}\\right\\\}\.Thus the main branch usesr=qtr=q\_\{t\}andu=Uj,tmainu=U\_\{j,t\}^\{\\mathrm\{main\}\}, whereas the challenge branch usesr=ptr=p\_\{t\}andu=Uj,tchalu=U\_\{j,t\}^\{\\mathrm\{chal\}\}\. Independence concerns these underlying random variables; the sampled arms may depend on earlier observations through their sampling distributions\.

The actual algorithm reveals only the random variables needed for its current launches and chosen branch\. Before epochjjstarts, none of its assigned variables has been used, so conditional onℱj\{\\mathcal\{F\}\}\_\{j\}they remain independent and retain their specified distributions\. The fixed\-rate continuation from[Section4](https://arxiv.org/html/2609.13547#S4)uses the same variables as the actual epoch but suppresses subsequent restarts\. Within this continuation, writeUJ=Uj,JrateU\_\{J\}=U\_\{j,J\}^\{\\mathrm\{rate\}\}andηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}forJ∈𝒥jJ\\in\\mathcal\{J\}\_\{j\}\. HenceUJU\_\{J\}is exactly the uniform variable used at launch in[Algorithm1](https://arxiv.org/html/2609.13547#alg1), with the epoch index omitted\.

The actual epoch and its continuation consequently have identical states, actions, and credit throughρj\\rho\_\{j\}, including the threshold\-crossing round\. Afterward, actual play uses the random variables assigned to subsequent epochs, while the continuation continues using those assigned to epochjj\. ThereforeCj,ρjcont=CjC\_\{j,\\rho\_\{j\}\}^\{\\mathrm\{cont\}\}=C\_\{j\}\. As in[Section4](https://arxiv.org/html/2609.13547#S4), per\-round symbols in continuation calculations refer to this continued process\. In particular, rates assigned afterρj\\rho\_\{j\}need not equal those assigned at the corresponding actual future launches\.

For the continuation analysis, we reveal information in three stages\. First,ℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}includes all continuation routing bits and main\-branch action\-sampling variables\. Because the losses are fixed and the reference distribution changes only on main rounds, this information determines the entire reference path\(qt\)t=τjT\(q\_\{t\}\)\_\{t=\\tau\_\{j\}\}^\{T\}\. For each fixed endpointn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, it also determines the cover𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)and the advantages\(AJ​\(n\)\)J∈𝒟j​\(n\)\(A\_\{J\}\(n\)\)\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}, while leaving the interval\-rate variables independent and uniform\. Second,ℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}additionally reveals all continuation interval rates, thereby determiningΓj\\Gamma\_\{j\}and the intervals selected from𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)at each fixed endpointnn\. Finally,𝒱j,tchal\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}additionally reveals the challenge\-branch action\-sampling variables before roundtt\. This determines the current interval states andptp\_\{t\}, while leavingUj,tchalU\_\{j,t\}^\{\\mathrm\{chal\}\}independent and uniform\. Formally,

ℱjpath\\displaystyle\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}=σ⁡\(ℱj,\(bj,t,Uj,tmain\)t=τjT\),\\displaystyle=\\sigma\\bigl\(\{\\mathcal\{F\}\}\_\{j\},\(b\_\{j,t\},U\_\{j,t\}^\{\\mathrm\{main\}\}\)\_\{t=\\tau\_\{j\}\}^\{T\}\\bigr\),ℱjrate\\displaystyle\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}=σ⁡\(ℱjpath,\(UJ\)J∈𝒥j\),\\displaystyle=\\sigma\\bigl\(\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\},\(U\_\{J\}\)\_\{J\\in\\mathcal\{J\}\_\{j\}\}\\bigr\),𝒱j,tchal\\displaystyle\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}=σ⁡\(ℱjrate,\(Uj,schal\)τj≤s<t\)\.\\displaystyle=\\sigma\\bigl\(\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\},\(U\_\{j,s\}^\{\\mathrm\{chal\}\}\)\_\{\\tau\_\{j\}\\leq s<t\}\\bigr\)\.These histories satisfy

ℱj⊆ℱjpath⊆ℱjrate=𝒱j,τjchal⊆𝒱j,tchal⊆𝒱j,t\+1chal\.\{\\mathcal\{F\}\}\_\{j\}\\subseteq\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\\subseteq\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}=\{\\mathcal\{V\}\}\_\{j,\\tau\_\{j\}\}^\{\\mathrm\{chal\}\}\\subseteq\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\\subseteq\{\\mathcal\{V\}\}\_\{j,t\+1\}^\{\\mathrm\{chal\}\}\.Table[1](https://arxiv.org/html/2609.13547#A1.T1)summarizes the information determined by each history and the random variables used in the corresponding conditional calculation\.

HistoryInformation already determinedRemaining randomness used in the analysisℋtend\\mathcal\{H\}\_\{t\}^\{\\mathrm\{end\}\}Actual play through roundtt, including its restart decisionFuture launch, routing, and action drawsℱj\{\\mathcal\{F\}\}\_\{j\}History before epochjjstarts;τj\\tau\_\{j\}and the reset stateAll random variables assigned to epochjjℋt\\mathcal\{H\}\_\{t\}Past play, current interval rates and states, andqtq\_\{t\}Routing bitbtb\_\{t\}, followed by the branch action𝒢t\\mathcal\{G\}\_\{t\}ℋt\\mathcal\{H\}\_\{t\}plusbtb\_\{t\}andptp\_\{t\}Armit∼pti\_\{t\}\\sim p\_\{t\}ℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}Continuation routing bits and reference path;𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)and\(AJ​\(n\)\)J∈𝒟j​\(n\)\(A\_\{J\}\(n\)\)\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}for fixednnInterval\-rate and challenge\-branch action\-sampling variablesℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}ℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}plus all continuation rates, fixed\-endpoint selections, andΓj\\Gamma\_\{j\}Challenge\-branch action\-sampling variables𝒱j,tchal\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}ℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}plus challenge\-branch variables beforett; currentptp\_\{t\}and interval statesThe independent uniform variableUj,tchalU\_\{j,t\}^\{\\mathrm\{chal\}\}Table 1:Actual histories and the enlarged histories used to analyze a fixed\-rate continuation\. The lower three rows describe the successive conditioning steps in the proof\.In particular, the independence ofUj,tchalU\_\{j,t\}^\{\\mathrm\{chal\}\}from𝒱j,tchal\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}gives, on a challenge round,

ℙ⁡\(it=i∣𝒱j,tchal\)=pt,i\.\\mathbb\{P\}\(i\_\{t\}=i\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\)=p\_\{t,i\}\.We use this conditional law for challenge\-round moments\. For routing unbiasedness, we instead condition onℋt\\mathcal\{H\}\_\{t\}, beforebtb\_\{t\}is revealed\. The tower property transfers bounds obtained under the enlarged histories back toℱj\{\\mathcal\{F\}\}\_\{j\}\. Although selection at a fixed endpoint isℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\-measurable, selection at the random endpointρj\\rho\_\{j\}need not be\. We therefore take a union over fixed endpoints before substitutingρj\\rho\_\{j\}, as in the proof of[Lemma4\.2](https://arxiv.org/html/2609.13547#S4.Thmtheorem2)\.

Finally, we retain the completed pointx¯\\bar\{x\}and completed relative entropy from[Section3](https://arxiv.org/html/2609.13547#S3)\. Each interval is initialized withxt,J,i=1/\(K⁡\(T\+1\)\)x\_\{t,J,i\}=1/\(K\(T\+1\)\)fori∈\[K\]i\\in\[K\]\. We denote the corresponding initial distribution on the completed simplex by

π≜\(TT\+1,1K⁡\(T\+1\),…,1K⁡\(T\+1\)\)∈ΔK\+1\.\\pi\\triangleq\\left\(\\frac\{T\}\{T\+1\},\\frac\{1\}\{K\(T\+1\)\},\\ldots,\\frac\{1\}\{K\(T\+1\)\}\\right\)\\in\\Delta\_\{K\+1\}\.Its coordinate00is the initial reference mass1−∑i=1Kxt,J,i=T/\(T\+1\)1\-\\sum\_\{i=1\}^\{K\}x\_\{t,J,i\}=T/\(T\+1\), and its remaining coordinates are the initial arm masses\.

### A\.2Proof of[Lemma4\.1](https://arxiv.org/html/2609.13547#S4.Thmtheorem1)

We prove[Lemma4\.1](https://arxiv.org/html/2609.13547#S4.Thmtheorem1)by adapting the standard fixed\-share analysis of EXP3\.S\([Auer et al\., 2002](https://arxiv.org/html/2609.13547#bib.bib4)\)to the random routing bitbtb\_\{t\}\. We first establish a pathwise bound for every epoch prefix, keeping the update before a possible reset separate from the reset itself\. We then use predictable epoch membership to take expectations at the random endpoint\.

###### Proof of[Lemma4\.1](https://arxiv.org/html/2609.13547#S4.Thmtheorem1)\.

Fix a reached epochIj=\{τj,…,ρj\}I\_\{j\}=\\\{\\tau\_\{j\},\\ldots,\\rho\_\{j\}\\\}and condition onℱj\{\\mathcal\{F\}\}\_\{j\}\. The epoch starts withqτj,i=1/Kq\_\{\\tau\_\{j\},i\}=1/Kand uses the fixed learning rateηj\\eta\_\{j\}\. Letq~t\+1\\widetilde\{q\}\_\{t\+1\}denote the intermediate distribution produced by the entropy\-OMD step, before fixed share, and letqt\+1\+q\_\{t\+1\}^\{\+\}denote the distribution after the within\-epoch update but before a possible reset\. Thusqt\+1=qt\+1\+q\_\{t\+1\}=q\_\{t\+1\}^\{\+\}forτj≤t<ρj\\tau\_\{j\}\\leq t<\\rho\_\{j\}\. At the final roundρj\\rho\_\{j\}, a reset may replaceqρj\+1\+q\_\{\\rho\_\{j\}\+1\}^\{\+\}by the uniform distribution for the next epoch; the potential calculation below usesqρj\+1\+q\_\{\\rho\_\{j\}\+1\}^\{\+\}, so this reset does not enter the current epoch’s bound\.

Define the main learner’s loss estimate on every round byℓ^t,iq≜2​𝕀​\{bt=1,it=i\}​ℓt,itqt,i\.\\widehat\{\\ell\}^\{q\}\_\{t,i\}\\triangleq\\frac\{2\\mathbb\{I\}\\\{b\_\{t\}=1,i\_\{t\}=i\\\}\\ell\_\{t,i\_\{t\}\}\}\{q\_\{t,i\}\}\.In particular,ℓ^tq=0\\widehat\{\\ell\}\_\{t\}^\{q\}=0on challenge rounds\. Conditional onℋt\\mathcal\{H\}\_\{t\}, the routing bit is fair and a main round samples frompt=qtp\_\{t\}=q\_\{t\}, soℙ⁡\(bt=1,it=i∣ℋt\)=qt,i/2\\mathbb\{P\}\(b\_\{t\}=1,i\_\{t\}=i\\mid\\mathcal\{H\}\_\{t\}\)=q\_\{t,i\}/2\. Consequently,

𝔼⁡\[ℓ^t,iq∣ℋt\]\\displaystyle\\mathbb\{E\}\\left\[\\widehat\{\\ell\}^\{q\}\_\{t,i\}\\mid\\mathcal\{H\}\_\{t\}\\right\]=qt,i2​2​ℓt,iqt,i=ℓt,i,\\displaystyle=\\frac\{q\_\{t,i\}\}\{2\}\\frac\{2\\ell\_\{t,i\}\}\{q\_\{t,i\}\}=\\ell\_\{t,i\},\(24\)𝔼⁡\[⟨qt,\(ℓ^tq\)2⟩∣ℋt\]\\displaystyle\\mathbb\{E\}\\left\[\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle\\mid\\mathcal\{H\}\_\{t\}\\right\]=∑i=1Kqt,i2​qt,i​4​ℓt,i2qt,i2=2​∑i=1Kℓt,i2≤2​K\.\\displaystyle=\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\}\{2\}\\,q\_\{t,i\}\\frac\{4\\ell\_\{t,i\}^\{2\}\}\{q\_\{t,i\}^\{2\}\}=2\\sum\_\{i=1\}^\{K\}\\ell\_\{t,i\}^\{2\}\\leq 2K\.\(25\)
On a main round, the entropy\-OMD and fixed\-share updates are

q~t\+1,i=qt,i​e−ηj​ℓ^t,iq𝖹tq,𝖹tq≜∑k=1Kqt,k​e−ηj​ℓ^t,kq,qt\+1,i\+=\(1−1/T\)​q~t\+1,i\+1K​T\.\\widetilde\{q\}\_\{t\+1,i\}=\\frac\{q\_\{t,i\}e^\{\-\\eta\_\{j\}\\widehat\{\\ell\}^\{q\}\_\{t,i\}\}\}\{\\mathsf\{Z\}\_\{t\}^\{q\}\},\\qquad\\mathsf\{Z\}\_\{t\}^\{q\}\\triangleq\\sum\_\{k=1\}^\{K\}q\_\{t,k\}e^\{\-\\eta\_\{j\}\\widehat\{\\ell\}^\{q\}\_\{t,k\}\},\\qquad q\_\{t\+1,i\}^\{\+\}=\(1\-1/T\)\\widetilde\{q\}\_\{t\+1,i\}\+\\frac\{1\}\{KT\}\.On challenge rounds,ℓ^tq=0\\widehat\{\\ell\}\_\{t\}^\{q\}=0and we setq~t\+1=qt\+1\+=qt\\widetilde\{q\}\_\{t\+1\}=q\_\{t\+1\}^\{\+\}=q\_\{t\}\. The exponential\-weights identity then remains valid, with𝖹tq=1\\mathsf\{Z\}\_\{t\}^\{q\}=1\. For every round, usinge−z≤1−z\+z2/2e^\{\-z\}\\leq 1\-z\+z^\{2\}/2forz≥0z\\geq 0andlog⁡z≤z−1\\log z\\leq z\-1forz\>0z\>0gives

log⁡𝖹tq≤𝖹tq−1≤−ηj​⟨qt,ℓ^tq⟩\+ηj22​⟨qt,\(ℓ^tq\)2⟩\.\\log\\mathsf\{Z\}\_\{t\}^\{q\}\\leq\\mathsf\{Z\}\_\{t\}^\{q\}\-1\\leq\-\\eta\_\{j\}\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t\}^\{q\}\\right\\rangle\+\\frac\{\\eta\_\{j\}^\{2\}\}\{2\}\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle\.Combining this bound with the exponential\-weights identity yields, for everyi∈\[K\]i\\in\[K\],

ηj​\(⟨qt,ℓ^tq⟩−ℓ^t,iq\)\\displaystyle\\eta\_\{j\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t\}^\{q\}\\right\\rangle\-\\widehat\{\\ell\}^\{q\}\_\{t,i\}\\right\)=log⁡q~t\+1,iqt,i\+log⁡𝖹tq\+ηj​⟨qt,ℓ^tq⟩\\displaystyle=\\log\\frac\{\\widetilde\{q\}\_\{t\+1,i\}\}\{q\_\{t,i\}\}\+\\log\\mathsf\{Z\}\_\{t\}^\{q\}\+\\eta\_\{j\}\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t\}^\{q\}\\right\\rangle≤log⁡q~t\+1,iqt,i\+ηj22​⟨qt,\(ℓ^tq\)2⟩\\displaystyle\\leq\\log\\frac\{\\widetilde\{q\}\_\{t\+1,i\}\}\{q\_\{t,i\}\}\+\\frac\{\\eta\_\{j\}^\{2\}\}\{2\}\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle≤logqt\+1,i\+qt,i\+𝕀\{bt=1\}logTT−1\+ηj22⟨qt,\(ℓ^tq\)2⟩\.\\displaystyle\\leq\\log\\frac\{q\_\{t\+1,i\}^\{\+\}\}\{q\_\{t,i\}\}\+\\mathbb\{I\}\\\{b\_\{t\}=1\\\}\\log\\frac\{T\}\{T\-1\}\+\\frac\{\\eta\_\{j\}^\{2\}\}\{2\}\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle\.\(26\)The last step usesqt\+1,i\+≥\(1−1/T\)​q~t\+1,iq\_\{t\+1,i\}^\{\+\}\\geq\(1\-1/T\)\\widetilde\{q\}\_\{t\+1,i\}on main rounds; on challenge rounds, every term is zero\. To further analyze the right hand side of[Eq\. \(26\)](https://arxiv.org/html/2609.13547#A1.E26), for any prefix\{τj,…,n\}⊆Ij\\\{\\tau\_\{j\},\\ldots,n\\\}\\subseteq I\_\{j\}, writeut\(S\)=eatu\_\{t\}^\{\(S\)\}=e\_\{a\_\{t\}\}\. Since there is no reset inside this prefix, we haveqt=qt\+q\_\{t\}=q\_\{t\}^\{\+\}forτj<t≤n\\tau\_\{j\}<t\\leq n\. Hence, we have

∑t=τjnlog⁡qt\+1,at\+qt,at=log⁡qn\+1,an\+−log⁡qτj,aτj\+∑t=τj\+1nlog⁡qt,at−1qt,at≤log⁡K\+S​log⁡\(K​T\),\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\log\\frac\{q\_\{t\+1,a\_\{t\}\}^\{\+\}\}\{q\_\{t,a\_\{t\}\}\}=\\log q\_\{n\+1,a\_\{n\}\}^\{\+\}\-\\log q\_\{\\tau\_\{j\},a\_\{\\tau\_\{j\}\}\}\+\\sum\_\{t=\\tau\_\{j\}\+1\}^\{n\}\\log\\frac\{q\_\{t,a\_\{t\-1\}\}\}\{q\_\{t,a\_\{t\}\}\}\\leq\\log K\+S\\log\(KT\),where we useqn\+1,an\+≤1q\_\{n\+1,a\_\{n\}\}^\{\+\}\\leq 1andqτj,aτj=1/Kq\_\{\\tau\_\{j\},a\_\{\\tau\_\{j\}\}\}=1/K\. Moreover, only comparator switches contribute to the last sum, so at mostSSterms are nonzero\. Each term is at mostlog⁡\(K​T\)\\log\(KT\)because every coordinate ofqtq\_\{t\}is at least1/\(K​T\)1/\(KT\), a lower bound preserved by fixed share on main rounds and by the unchanged reference distribution on challenge rounds\. In addition, we have

∑t=τjn𝕀\{bt=1\}logTT−1≤TlogTT−1≤2\.\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\mathbb\{I\}\\\{b\_\{t\}=1\\\}\\log\\frac\{T\}\{T\-1\}\\leq T\\log\\frac\{T\}\{T\-1\}\\leq 2\.Summing[Eq\. \(26\)](https://arxiv.org/html/2609.13547#A1.E26)withi=ati=a\_\{t\}therefore gives the pathwise prefix bound

∑t=τjn⟨qt−ut\(S\),ℓ^tq⟩≤log⁡K\+S​log⁡\(K​T\)\+2ηj\+ηj2​∑t=τjn⟨qt,\(ℓ^tq\)2⟩\.\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\left\\langle q\_\{t\}\-u\_\{t\}^\{\(S\)\},\\widehat\{\\ell\}\_\{t\}^\{q\}\\right\\rangle\\leq\\frac\{\\log K\+S\\log\(KT\)\+2\}\{\\eta\_\{j\}\}\+\\frac\{\\eta\_\{j\}\}\{2\}\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle\.\(27\)The numerator of the first term is at most3​\(S\+1\)​log⁡\(K​T\)3\(S\+1\)\\log\(KT\)\. Since this bound holds for every realized epoch prefix, it also holds atn=ρjn=\\rho\_\{j\}\.

It remains to take expectations without conditioning on the realized endpoint\. For each deterministic roundtt, the indicator𝕀\{t∈Ij\}\\mathbb\{I\}\\\{t\\in I\_\{j\}\\\}isℋt\\mathcal\{H\}\_\{t\}\-measurable: whether roundttbelongs to epochjjis decided before the current routing bit and action\. Moreover, whenevert∈Ijt\\in I\_\{j\}, the epoch\-start historyℱj\{\\mathcal\{F\}\}\_\{j\}has already been revealed\. Thus, for any boundedℱj\{\\mathcal\{F\}\}\_\{j\}\-measurable random variableXX, the productX𝕀\{t∈Ij\}X\\mathbb\{I\}\\\{t\\in I\_\{j\}\\\}isℋt\\mathcal\{H\}\_\{t\}\-measurable\. Applying the tower property to[Eq\. \(24\)](https://arxiv.org/html/2609.13547#A1.E24)and[Eq\. \(25\)](https://arxiv.org/html/2609.13547#A1.E25)yields

𝔼j\[∑t=1T𝕀\{t∈Ij\}⟨qt−ut\(S\),ℓ^tq−ℓt⟩\]\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{t=1\}^\{T\}\\mathbb\{I\}\\\{t\\in I\_\{j\}\\\}\\left\\langle q\_\{t\}\-u\_\{t\}^\{\(S\)\},\\widehat\{\\ell\}\_\{t\}^\{q\}\-\\ell\_\{t\}\\right\\rangle\\right\]=0,\\displaystyle=0,\(28\)𝔼j\[∑t=1T𝕀\{t∈Ij\}⟨qt,\(ℓ^tq\)2⟩\]\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{t=1\}^\{T\}\\mathbb\{I\}\\\{t\\in I\_\{j\}\\\}\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle\\right\]≤2K∑t=1T𝔼j\[𝕀\{t∈Ij\}\]=2K𝔼j\[Hj\]\.\\displaystyle\\leq 2K\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{j\}\[\\mathbb\{I\}\\\{t\\in I\_\{j\}\\\}\]=2K\\mathbb\{E\}\_\{j\}\[H\_\{j\}\]\.\(29\)The first equality follows from[Eq\. \(24\)](https://arxiv.org/html/2609.13547#A1.E24)and theℋt\\mathcal\{H\}\_\{t\}\-measurability ofqtq\_\{t\}andut\(S\)u\_\{t\}^\{\(S\)\}: the former is determined before the current routing bit and action, and the latter is fixed by the oblivious loss table\. Hence both areℋt\\mathcal\{H\}\_\{t\}\-measurable\. Settingn=ρjn=\\rho\_\{j\}in[Eq\. \(27\)](https://arxiv.org/html/2609.13547#A1.E27)and taking𝔼j\\mathbb\{E\}\_\{j\}, we have

𝔼j​\[∑t∈Ij⟨qt−ut\(S\),ℓt⟩\]\\displaystyle\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{t\\in I\_\{j\}\}\\left\\langle q\_\{t\}\-u\_\{t\}^\{\(S\)\},\\ell\_\{t\}\\right\\rangle\\right\]=𝔼j​\[∑t∈Ij⟨qt−ut\(S\),ℓ^tq⟩\]\\displaystyle=\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{t\\in I\_\{j\}\}\\left\\langle q\_\{t\}\-u\_\{t\}^\{\(S\)\},\\widehat\{\\ell\}\_\{t\}^\{q\}\\right\\rangle\\right\]\(since[Eq\. \(28\)](https://arxiv.org/html/2609.13547#A1.E28)\)≤log⁡K\+S​log⁡\(K​T\)\+2ηj\+ηj2​𝔼j​\[∑t∈Ij⟨qt,\(ℓ^tq\)2⟩\]\\displaystyle\\leq\\frac\{\\log K\+S\\log\(KT\)\+2\}\{\\eta\_\{j\}\}\+\\frac\{\\eta\_\{j\}\}\{2\}\\mathbb\{E\}\_\{j\}\\left\[\\sum\_\{t\\in I\_\{j\}\}\\left\\langle q\_\{t\},\(\\widehat\{\\ell\}\_\{t\}^\{q\}\)^\{2\}\\right\\rangle\\right\]\(since[Eq\. \(27\)](https://arxiv.org/html/2609.13547#A1.E27)\)≤3​\(S\+1\)​log⁡\(K​T\)ηj\+ηj​K​𝔼j​\[Hj\]\.\\displaystyle\\leq\\frac\{3\(S\+1\)\\log\(KT\)\}\{\\eta\_\{j\}\}\+\\eta\_\{j\}K\\mathbb\{E\}\_\{j\}\[H\_\{j\}\]\.\(since[Eq\. \(29\)](https://arxiv.org/html/2609.13547#A1.E29)\)This finishes the proof\. ∎

### A\.3Proof of[Lemma4\.3](https://arxiv.org/html/2609.13547#S4.Thmtheorem3)

We now prove[Lemma4\.3](https://arxiv.org/html/2609.13547#S4.Thmtheorem3), showing that each epoch prefix can be partitioned into at most\(S\+1\)​L\(S\+1\)Lcanonical dyadic intervals, on each of which the comparator is constant\. We construct this partition by taking the maximal canonical dyadic intervals contained in each constant comparator segment\. At most two such intervals occur at each scale, giving the required logarithmic bound on the cover size\.

###### Proof of[Lemma4\.3](https://arxiv.org/html/2609.13547#S4.Thmtheorem3)\.

Take all canonical dyadic intervals contained in an integer intervalI⊆\[T\]I\\subseteq\[T\]that are maximal under inclusion\. Singletons are canonical, so these intervals coverII\. Canonical dyadic intervals are either disjoint or nested, and maximality therefore makes the chosen intervals disjoint\. At any fixed dyadic length, there can be at most two maximal intervals\. The dyadic parent of a maximal interval, taken in the full dyadic grid, is not contained inII, so it crosses an endpoint ofII\. At a fixed scale, at most one parent crosses each endpoint, and each such parent has at most one child contained inII; otherwise the parent itself would be contained\. This gives at most two maximal children\. As there are⌊log2⁡T⌋\+1\\lfloor\\log\_\{2\}T\\rfloor\+1possible dyadic lengths and at most two maximal intervals occur at each length, the construction uses at most2​\(⌊log2⁡T⌋\+1\)≤L2\(\\lfloor\\log\_\{2\}T\\rfloor\+1\)\\leq Lintervals\. Figure[1](https://arxiv.org/html/2609.13547#A1.F1)illustrates this construction\.

Figure 1:Maximal canonical dyadic intervals contained inI=\{3,…,13\}I=\\\{3,\\ldots,13\\\}, withT=16T=16\. The highlighted intervals form the disjoint partition\[3,4\]∪\[5,8\]∪\[9,12\]∪\{13\}\[3,4\]\\cup\[5,8\]\\cup\[9,12\]\\cup\\\{13\\\}, where brackets denote integer intervals\. Each highlighted interval’s parent crosses a dashed boundary ofII, and at most two highlighted intervals occur at each length\.Apply this construction separately to every constant segment of𝐮\(S\)\\mathbf\{u\}^\{\(S\)\}restricted to\{τj,…,n\}\\\{\\tau\_\{j\},\\ldots,n\\\}\. There are at mostS\+1S\+1such segments\. Consequently, the resulting family is precisely𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)and has cardinality at most\(S\+1\)​L\(S\+1\)L\. ∎

### A\.4Proof of[Lemma4\.4](https://arxiv.org/html/2609.13547#S4.Thmtheorem4)

We next prove[Lemma4\.4](https://arxiv.org/html/2609.13547#S4.Thmtheorem4), which bounds the full signed advantage∑J∈𝒟j​\(n\)AJ​\(n\)\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}A\_\{J\}\(n\)in terms of the randomly selected contributionWj​\(n\)W\_\{j\}\(n\)\. Conditioning onℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}fixes the cover𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)and these advantages while leaving the interval\-rate draws independent\. The resulting selection indicators are therefore independent, allowing us to apply an exponential\-moment bound\.

###### Proof of[Lemma4\.4](https://arxiv.org/html/2609.13547#S4.Thmtheorem4)\.

Fixn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}and condition onℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\. This fixes𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)and\(AJ​\(n\)\)J∈𝒟j​\(n\)\(A\_\{J\}\(n\)\)\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}, while theUJU\_\{J\}remain independent uniform variables\. ForJ∈𝒟j​\(n\)J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\), definevJ​\(n\)≜gJ​\(n\)/dj=α​AJ​\(n\)/djv\_\{J\}\(n\)\\triangleq g\_\{J\}\(n\)/d\_\{j\}=\\alpha A\_\{J\}\(n\)/d\_\{j\}\. SinceηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}anddj=64​L/ηjd\_\{j\}=64L/\\eta\_\{j\}, the selection event isXJ\(n\)=𝕀\{UJ≤vJ\(n\)\}X\_\{J\}\(n\)=\\mathbb\{I\}\\\{U\_\{J\}\\leq v\_\{J\}\(n\)\\\}\. Hence

ℙ⁡\(XJ​\(n\)=1∣ℱjpath\)=min⁡\{1,\(vJ​\(n\)\)\+\}\.\\displaystyle\\mathbb\{P\}\(X\_\{J\}\(n\)=1\\mid\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\)=\\min\\\{1,\(v\_\{J\}\(n\)\)\_\{\+\}\\\}\.\(30\)
For every fixedλ∈\(0,1\]\\lambda\\in\(0,1\]andJ∈𝒟j​\(n\)J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\), we claim that

𝔼⁡\[eλ​vJ​\(n\)−vJ​\(n\)​XJ​\(n\)∣ℱjpath\]≤eλ2/2\.\\displaystyle\\mathbb\{E\}\\left\[e^\{\\lambda v\_\{J\}\(n\)\-v\_\{J\}\(n\)X\_\{J\}\(n\)\}\\mid\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\\right\]\\leq e^\{\\lambda^\{2\}/2\}\.\(31\)IfvJ​\(n\)≤0v\_\{J\}\(n\)\\leq 0orvJ​\(n\)≥1v\_\{J\}\(n\)\\geq 1, thenXJ​\(n\)=0X\_\{J\}\(n\)=0orXJ​\(n\)=1X\_\{J\}\(n\)=1, respectively, and the exponent is nonpositive\. For0<vJ​\(n\)<10<v\_\{J\}\(n\)<1,[Eq\. \(30\)](https://arxiv.org/html/2609.13547#A1.E30)gives

𝔼⁡\[eλ​vJ​\(n\)−vJ​\(n\)​XJ​\(n\)∣ℱjpath\]=eλ​vJ​\(n\)​\[1−vJ​\(n\)​\(1−e−vJ​\(n\)\)\]≤eλ​vJ​\(n\)−vJ​\(n\)2/2≤eλ2/2\.\\displaystyle\\mathbb\{E\}\\left\[e^\{\\lambda v\_\{J\}\(n\)\-v\_\{J\}\(n\)X\_\{J\}\(n\)\}\\mid\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\\right\]=e^\{\\lambda v\_\{J\}\(n\)\}\\left\[1\-v\_\{J\}\(n\)\(1\-e^\{\-v\_\{J\}\(n\)\}\)\\right\]\\leq e^\{\\lambda v\_\{J\}\(n\)\-v\_\{J\}\(n\)^\{2\}/2\}\\leq e^\{\\lambda^\{2\}/2\}\.The first inequality uses1−x≤e−x1\-x\\leq e^\{\-x\}and1−e−vJ​\(n\)≥vJ​\(n\)−vJ​\(n\)2/2≥vJ​\(n\)/21\-e^\{\-v\_\{J\}\(n\)\}\\geq v\_\{J\}\(n\)\-v\_\{J\}\(n\)^\{2\}/2\\geq v\_\{J\}\(n\)/2\. The second follows from the AM–GM inequalityλ​vJ​\(n\)−vJ​\(n\)22≤λ22\\lambda v\_\{J\}\(n\)\-\\frac\{v\_\{J\}\(n\)^\{2\}\}\{2\}\\leq\\frac\{\\lambda^\{2\}\}\{2\}\.

Recall thatm=\(S\+1\)​Lm=\(S\+1\)Land setr⁡\(n\)≜∑J∈𝒟j​\(n\)vJ​\(n\)=\(α/dj\)​∑J∈𝒟j​\(n\)AJ​\(n\)r\(n\)\\triangleq\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}v\_\{J\}\(n\)=\(\\alpha/d\_\{j\}\)\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}A\_\{J\}\(n\)\. SinceWj​\(n\)/dj=∑J∈𝒟j​\(n\)vJ​\(n\)​XJ​\(n\)W\_\{j\}\(n\)/d\_\{j\}=\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}v\_\{J\}\(n\)X\_\{J\}\(n\), multiplying[Eq\. \(31\)](https://arxiv.org/html/2609.13547#A1.E31)over the conditionally independent selections and using\|𝒟j​\(n\)\|≤m\|\{\\mathcal\{D\}\}\_\{j\}\(n\)\|\\leq mfrom[Lemma4\.3](https://arxiv.org/html/2609.13547#S4.Thmtheorem3)yields

𝔼⁡\[exp⁡\{λ​r​\(n\)−Wj​\(n\)dj\}∣ℱjpath\]≤em​λ2/2\.\\displaystyle\\mathbb\{E\}\\left\[\\exp\\left\\\{\\lambda r\(n\)\-\\frac\{W\_\{j\}\(n\)\}\{d\_\{j\}\}\\right\\\}\\mid\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\\right\]\\leq e^\{m\\lambda^\{2\}/2\}\.\(32\)
Ifr⁡\(n\)≤0r\(n\)\\leq 0, then[Eq\. \(16\)](https://arxiv.org/html/2609.13547#S4.E16)follows immediately fromWj​\(n\)≥0W\_\{j\}\(n\)\\geq 0\. Otherwise, chooseλ⋆​\(n\)=min⁡\{1,r⁡\(n\)/m\}\\lambda^\{\\star\}\(n\)=\\min\\\{1,r\(n\)/m\\\}\. Becauser⁡\(n\)r\(n\)is fixed under the conditioning onℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}, this choice is also fixed\. Applying Markov’s inequality to[Eq\. \(32\)](https://arxiv.org/html/2609.13547#A1.E32)withλ=λ⋆​\(n\)\\lambda=\\lambda^\{\\star\}\(n\)therefore gives, with conditional probability at least1−δ01\-\\delta\_\{0\},

λ⋆​\(n\)​r​\(n\)−m​\(λ⋆​\(n\)\)22≤Wj​\(n\)dj\+log⁡1δ0≜h⁡\(n\)\.\\displaystyle\\lambda^\{\\star\}\(n\)r\(n\)\-\\frac\{m\(\\lambda^\{\\star\}\(n\)\)^\{2\}\}\{2\}\\leq\\frac\{W\_\{j\}\(n\)\}\{d\_\{j\}\}\+\\log\\frac\{1\}\{\\delta\_\{0\}\}\\triangleq h\(n\)\.\(33\)For0<r⁡\(n\)≤m0<r\(n\)\\leq m, substitutingλ⋆​\(n\)=r⁡\(n\)/m\\lambda^\{\\star\}\(n\)=r\(n\)/mgivesr​\(n\)2/\(2​m\)≤h⁡\(n\)r\(n\)^\{2\}/\(2m\)\\leq h\(n\), hencer⁡\(n\)≤2​m​h​\(n\)r\(n\)\\leq\\sqrt\{2mh\(n\)\}\. Forr⁡\(n\)\>mr\(n\)\>m, substitutingλ⋆​\(n\)=1\\lambda^\{\\star\}\(n\)=1givesr⁡\(n\)−m/2≤h⁡\(n\)r\(n\)\-m/2\\leq h\(n\)\. Thush⁡\(n\)\>m/2h\(n\)\>m/2andr⁡\(n\)≤h⁡\(n\)\+m/2≤h⁡\(n\)\+2​m​h​\(n\)r\(n\)\\leq h\(n\)\+m/2\\leq h\(n\)\+\\sqrt\{2mh\(n\)\}\. Consequently, in both cases,

r⁡\(n\)≤h⁡\(n\)\+2​m​h​\(n\)\.r\(n\)\\leq h\(n\)\+\\sqrt\{2mh\(n\)\}\.Usinglog⁡\(1/δ0\)=10​log⁡\(2​K​T\)≤L/2\\log\(1/\\delta\_\{0\}\)=10\\log\(2KT\)\\leq L/2and multiplying bydj/αd\_\{j\}/\\alpha, we obtain

∑J∈𝒟j​\(n\)AJ​\(n\)≤1α​\[Wj​\(n\)\+dj​L2\+2​m​dj​\(Wj​\(n\)\+dj​L2\)\],\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}A\_\{J\}\(n\)\\leq\\frac\{1\}\{\\alpha\}\\left\[W\_\{j\}\(n\)\+\\frac\{d\_\{j\}L\}\{2\}\+\\sqrt\{2md\_\{j\}\\left\(W\_\{j\}\(n\)\+\\frac\{d\_\{j\}L\}\{2\}\\right\)\}\\right\],which is[Eq\. \(16\)](https://arxiv.org/html/2609.13547#S4.E16)\. This bound holds with conditional probability at least1−δ01\-\\delta\_\{0\}givenℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}\. Sinceℱj⊆ℱjpath\{\\mathcal\{F\}\}\_\{j\}\\subseteq\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}, the tower property gives the same guarantee conditional onℱj\{\\mathcal\{F\}\}\_\{j\}\. ∎

### A\.5Proof of[Lemma4\.5](https://arxiv.org/html/2609.13547#S4.Thmtheorem5)

In this section, we prove[Lemma4\.5](https://arxiv.org/html/2609.13547#S4.Thmtheorem5), which shows that continuation credit retains a constant fraction of the selected advantageWj​\(n\)W\_\{j\}\(n\)\. We apply the shared credit comparison in[LemmaA\.2](https://arxiv.org/html/2609.13547#A1.Thmtheorem2)to the selected family and use the selection threshold to pay its arm\-comparison penalties\. The remaining deterministic costs are absorbed intoK​T​ηj/20KT\\eta\_\{j\}/20\.

###### Proof of[Lemma4\.5](https://arxiv.org/html/2609.13547#S4.Thmtheorem5)\.

Fix a reached epochIjI\_\{j\}and an endpointn∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, and condition onℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\. We use the shared\-credit comparison in[LemmaA\.2](https://arxiv.org/html/2609.13547#A1.Thmtheorem2), which lower\-bounds continuation credit by the total scaled advantage of a disjoint interval family, minus the comparison penalties and error terms in[Eq\. \(38\)](https://arxiv.org/html/2609.13547#A1.E38)\. Specifically, we apply the lemma with

𝒮j=𝒮j​\(n\)≜\{J∈𝒟j​\(n\):XJ​\(n\)=1\},δ=δ0,\\mathcal\{S\}\_\{j\}=\\mathcal\{S\}\_\{j\}\(n\)\\triangleq\\\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\):X\_\{J\}\(n\)=1\\\},\\qquad\\delta=\\delta\_\{0\},using the comparator armaJa\_\{J\}on each selected interval\.

We first verify that𝒮j​\(n\)\\mathcal\{S\}\_\{j\}\(n\)satisfies the hypotheses of[LemmaA\.2](https://arxiv.org/html/2609.13547#A1.Thmtheorem2)\. By construction,𝒟j​\(n\)⊆𝒥j\{\\mathcal\{D\}\}\_\{j\}\(n\)\\subseteq\\mathcal\{J\}\_\{j\}is a disjoint family andut\(S\)=eaJu\_\{t\}^\{\(S\)\}=e\_\{a\_\{J\}\}for everyt∈Jt\\in J, so these properties also hold for𝒮j​\(n\)\\mathcal\{S\}\_\{j\}\(n\)\. Moreover,ℱjpath\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{path\}\}determines𝒟j​\(n\)\{\\mathcal\{D\}\}\_\{j\}\(n\)andAJ​\(n\)A\_\{J\}\(n\), whileℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}additionally revealsηJ\\eta\_\{J\}\. Consequently,XJ\(n\)=𝕀\{ηJAJ\(n\)≥64L\}X\_\{J\}\(n\)=\\mathbb\{I\}\\\{\\eta\_\{J\}A\_\{J\}\(n\)\\geq 64L\\\}and𝒮j​\(n\)\\mathcal\{S\}\_\{j\}\(n\)areℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\-measurable\. By[AppendixA\.1](https://arxiv.org/html/2609.13547#A1.SS1), the challenge\-action seeds remain independent and uniform under this conditioning, preserving the conditional sampling law used in[LemmaA\.2](https://arxiv.org/html/2609.13547#A1.Thmtheorem2)\.

Applying[Eq\. \(38\)](https://arxiv.org/html/2609.13547#A1.E38)with the above parameters and evaluating its prefix bound atnntherefore gives, with conditional probability at least1−δ01\-\\delta\_\{0\},

Cj,ncont\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}≥α​∑J∈𝒮j​\(n\)AJ​\(n\)−∑J∈𝒮j​\(n\)αηJ​log⁡6​T​Kδ0​πaJ−2ηj−4​Γj−2​log⁡3δ0−2​α​T​log⁡3δ0,\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\(n\)\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\(n\)\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{6TK\}\{\\delta\_\{0\}\\pi\_\{a\_\{J\}\}\}\-\\frac\{2\}\{\\eta\_\{j\}\}\-4\\Gamma\_\{j\}\-2\\log\\frac\{3\}\{\\delta\_\{0\}\}\-2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\_\{0\}\}\},\(34\)whereπ\\piis the initial distribution of each interval subroutine over the reference coordinate00and theKKarms:π0=TT\+1,πi=1K⁡\(T\+1\)\\pi\_\{0\}=\\frac\{T\}\{T\+1\},\\pi\_\{i\}=\\frac\{1\}\{K\(T\+1\)\}fori∈\[K\]i\\in\[K\]\. These weights follow from the subroutine initialization in[Algorithm1](https://arxiv.org/html/2609.13547#alg1)\.

It remains to bound the arm\-comparison penalties and the three scalar error terms\. Using the value ofπaJ\\pi\_\{a\_\{J\}\}and the definitions ofδ0\\delta\_\{0\}andLL, we obtain that

αηJ​log⁡6​T​Kδ0​πaJ\\displaystyle\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{6TK\}\{\\delta\_\{0\}\\pi\_\{a\_\{J\}\}\}=αηJ​\(10​log⁡\(2​K​T\)\+log⁡\(6​T​K2​\(T\+1\)\)\)≤α​LηJ≤α​AJ​\(n\)64,\\displaystyle=\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\left\(10\\log\(2KT\)\+\\log\\bigl\(6TK^\{2\}\(T\+1\)\\bigr\)\\right\)\\leq\\frac\{\\alpha L\}\{\\eta\_\{J\}\}\\leq\\frac\{\\alpha A\_\{J\}\(n\)\}\{64\},where the first equality uses the definition ofδ0\\delta\_\{0\}andπaJ\\pi\_\{a\_\{J\}\}and the first inequality usesL≥20​log⁡\(2​K​T\)L\\geq 20\\log\(2KT\), and the last inequality is because for everyJ∈𝒮j​\(n\)J\\in\\mathcal\{S\}\_\{j\}\(n\),ηJ​AJ​\(n\)≥64​L\\eta\_\{J\}A\_\{J\}\(n\)\\geq 64LasXJ​\(n\)=1X\_\{J\}\(n\)=1\. Summing this inequality over the selected intervals and substituting into the[Eq\. \(34\)](https://arxiv.org/html/2609.13547#A1.E34)yields

Cj,ncont\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}≥63​α64​∑J∈𝒮j​\(n\)AJ​\(n\)−4​Γj−2ηj−2​log⁡3δ0−2​α​T​log⁡3δ0\.\\displaystyle\\geq\\frac\{63\\alpha\}\{64\}\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\(n\)\}A\_\{J\}\(n\)\-4\\Gamma\_\{j\}\-\\frac\{2\}\{\\eta\_\{j\}\}\-2\\log\\frac\{3\}\{\\delta\_\{0\}\}\-2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\_\{0\}\}\}\.\(35\)The parameter choices giveηj≥100​L/K​T\\eta\_\{j\}\\geq 100L/\\sqrt\{KT\},α=1/\(100​L2\)\\alpha=1/\(100L^\{2\}\), andlog⁡\(3/δ0\)≤L\\log\(3/\\delta\_\{0\}\)\\leq L\. Consequently, we have

2ηj\\displaystyle\\frac\{2\}\{\\eta\_\{j\}\}≤K​T​ηj5000​L2≤K​T​ηj100,\\displaystyle\\leq\\frac\{KT\\eta\_\{j\}\}\{5000L^\{2\}\}\\leq\\frac\{KT\\eta\_\{j\}\}\{100\},2​log⁡3δ0\\displaystyle 2\\log\\frac\{3\}\{\\delta\_\{0\}\}≤2​L≤K​T​ηj100,\\displaystyle\\leq 2L\\leq\\frac\{KT\\eta\_\{j\}\}\{100\},2​α​T​log⁡3δ0\\displaystyle 2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\_\{0\}\}\}≤2​T​L100​L2≤2​1/K10000​L5/2​K​T​ηj≤K​T​ηj100\.\\displaystyle\\leq\\frac\{2\\sqrt\{TL\}\}\{100L^\{2\}\}\\leq\\frac\{2\\sqrt\{1/K\}\}\{10000L^\{5/2\}\}KT\\eta\_\{j\}\\leq\\frac\{KT\\eta\_\{j\}\}\{100\}\.Thus these three costs sum to at most3​K​T​ηj/1003KT\\eta\_\{j\}/100\. By the definitions of the selected family andgJ​\(n\)g\_\{J\}\(n\),

α​∑J∈𝒮j​\(n\)AJ​\(n\)=∑J∈𝒟j​\(n\)gJ​\(n\)​XJ​\(n\)=Wj​\(n\)≥0,\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\(n\)\}A\_\{J\}\(n\)=\\sum\_\{J\\in\{\\mathcal\{D\}\}\_\{j\}\(n\)\}g\_\{J\}\(n\)X\_\{J\}\(n\)=W\_\{j\}\(n\)\\geq 0,where nonnegativity follows fromAJ​\(n\)\>0A\_\{J\}\(n\)\>0on every selected interval\. Substituting into[Eq\. \(35\)](https://arxiv.org/html/2609.13547#A1.E35)gives

Cj,ncont≥6364​Wj​\(n\)−3​K​T​ηj100−4​Γj≥34​Wj​\(n\)−K​T​ηj20−4​Γj,C\_\{j,n\}^\{\\mathrm\{cont\}\}\\geq\\frac\{63\}\{64\}W\_\{j\}\(n\)\-\\frac\{3KT\\eta\_\{j\}\}\{100\}\-4\\Gamma\_\{j\}\\geq\\frac\{3\}\{4\}W\_\{j\}\(n\)\-\\frac\{KT\\eta\_\{j\}\}\{20\}\-4\\Gamma\_\{j\},where the last inequality usesWj​\(n\)≥0W\_\{j\}\(n\)\\geq 0\. This proves[Eq\. \(17\)](https://arxiv.org/html/2609.13547#S4.E17)with conditional probability at least1−δ01\-\\delta\_\{0\}givenℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\. Sinceℱj⊆ℱjrate\{\\mathcal\{F\}\}\_\{j\}\\subseteq\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}, the tower property yields the same guarantee forℱj\{\\mathcal\{F\}\}\_\{j\}\. ∎

### A\.6Proof of[Lemma4\.6](https://arxiv.org/html/2609.13547#S4.Thmtheorem6)

We next prove[Lemma4\.6](https://arxiv.org/html/2609.13547#S4.Thmtheorem6), which bounds the expected aggregate chargeΓj\\Gamma\_\{j\}\.

###### Proof of[Lemma4\.6](https://arxiv.org/html/2609.13547#S4.Thmtheorem6)\.

Condition onℱj\{\\mathcal\{F\}\}\_\{j\}, which fixes𝒥j\\mathcal\{J\}\_\{j\}andηj\\eta\_\{j\}while leaving theUJU\_\{J\}independent and uniform\. ForU∼Unif⁡\(0,1\)U\\sim\\operatorname\{Unif\}\(0,1\)andc\>0c\>0, direct integration gives

𝔼⁡\[min⁡\{cU,1\}\]\\displaystyle\\mathbb\{E\}\\left\[\\min\\left\\\{\\frac\{c\}\{U\},1\\right\\\}\\right\]=\{c\+∫c1cu​du=c⁡\(1\+log⁡\(1/c\)\),0<c<1,1,c≥1,\\displaystyle=\\begin\{cases\}c\+\\displaystyle\\int\_\{c\}^\{1\}\\frac\{c\}\{u\}\\,du=c\(1\+\\log\(1/c\)\),&0<c<1,\\\\ 1,&c\\geq 1,\\end\{cases\}≤c⁡\(1\+log\+⁡1c\),\\displaystyle\\leq c\\left\(1\+\\log^\{\+\}\\frac\{1\}\{c\}\\right\),\(36\)where we recall thatlog\+⁡\(z\)=max⁡\{0,log⁡z\}\\log^\{\+\}\(z\)=\\max\\\{0,\\log z\\\}\. Applying[Eq\. \(36\)](https://arxiv.org/html/2609.13547#A1.E36)withc=K​ηjc=K\\eta\_\{j\}and usingηJ=α​ηj/UJ\\eta\_\{J\}=\\alpha\\eta\_\{j\}/U\_\{J\}, we obtain

𝔼j​\[min⁡\{K​ηJ,α\}\]=α​𝔼j​\[min⁡\{K​ηjUJ,1\}\]≤α​K​ηj​\(1\+log\+⁡1K​ηj\)≤α​K​ηj​L\.\\displaystyle\\mathbb\{E\}\_\{j\}\[\\min\\\{K\\eta\_\{J\},\\alpha\\\}\]=\\alpha\\mathbb\{E\}\_\{j\}\\left\[\\min\\left\\\{\\frac\{K\\eta\_\{j\}\}\{U\_\{J\}\},1\\right\\\}\\right\]\\leq\\alpha K\\eta\_\{j\}\\left\(1\+\\log^\{\+\}\\frac\{1\}\{K\\eta\_\{j\}\}\\right\)\\leq\\alpha K\\eta\_\{j\}L\.The last inequality usesηj≥η1\\eta\_\{j\}\\geq\\eta\_\{1\}and the definition ofLL\. At each dyadic scale, the canonical intervals have total length at mostTT, and there are at mostLLscales\. Therefore, we have

𝔼j​\[Γj\]=∑J∈𝒥j\|J\|​𝔼j​\[min⁡\{K​ηJ,α\}\]≤α​K​ηj​L​∑J∈𝒥j\|J\|≤α​K​T​ηj​L2=K​T​ηj100,\\displaystyle\\mathbb\{E\}\_\{j\}\[\\Gamma\_\{j\}\]=\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\}\|J\|\\,\\mathbb\{E\}\_\{j\}\[\\min\\\{K\\eta\_\{J\},\\alpha\\\}\]\\leq\\alpha K\\eta\_\{j\}L\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\}\|J\|\\leq\\alpha KT\\eta\_\{j\}L^\{2\}=\\frac\{KT\\eta\_\{j\}\}\{100\},which finishes the proof\. ∎

### A\.7Auxiliary estimates

#### A\.7\.1OMD Analysis

The first lemma bounds an interval subroutine’s regret against anyu∈𝒳u\\in\{\\mathcal\{X\}\}by the standard entropy\-OMD argument\. The completion from[Section3](https://arxiv.org/html/2609.13547#S3)expresses the update onΔK\+1\\Delta\_\{K\+1\}, allowing us to telescope the KL divergence to the comparator\.

###### Lemma A\.1\.

Fix an interval subroutineJJin a fixed\-rate continuation and an endpointn∈\[T\]n\\in\[T\]\. On a challenge round, defineyt,J,0≜⟨qt,ℓ^t,J⟩y\_\{t,J,0\}\\triangleq\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangleandyt,J,i≜ℓ^t,J,iy\_\{t,J,i\}\\triangleq\\widehat\{\\ell\}\_\{t,J,i\}fori∈\[K\]i\\in\[K\]\. Then, for everyu∈𝒳u\\in\{\\mathcal\{X\}\},

∑t∈J,t≤nbt=0⟨xt,J−u,zt,J⟩≤KL\(u¯∥π\)ηJ\+ηJ2​∑t∈J,t≤nbt=0⟨x¯t,J,yt,J2⟩,\\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle x\_\{t,J\}\-u,z\_\{t,J\}\\right\\rangle\\leq\\frac\{\\text\{\\rm KL\}\(\\bar\{u\}\\\|\\pi\)\}\{\\eta\_\{J\}\}\+\\frac\{\\eta\_\{J\}\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle,\(37\)whereyt,J2y\_\{t,J\}^\{2\}denotes coordinatewise squaring\. Herex¯=\(1−‖x‖1,x1,…,xK\)\\bar\{x\}=\(1\-\\\|x\\\|\_\{1\},x\_\{1\},\\ldots,x\_\{K\}\)is the completion ofx∈𝒳x\\in\{\\mathcal\{X\}\}, andπ\\piis the completed initial distribution, withπ0=T/\(T\+1\)\\pi\_\{0\}=T/\(T\+1\)andπi=1/\(K⁡\(T\+1\)\)\\pi\_\{i\}=1/\(K\(T\+1\)\)fori∈\[K\]i\\in\[K\]\.

###### Proof\.

By the definitions of the completion andzt,Jz\_\{t,J\}, for everyx∈𝒳x\\in\{\\mathcal\{X\}\},

⟨x¯,yt,J⟩=\(1−‖x‖1\)​yt,J,0\+∑i=1Kxi​ℓ^t,J,i=yt,J,0\+⟨x,zt,J⟩\.\\left\\langle\\bar\{x\},y\_\{t,J\}\\right\\rangle=\(1\-\\\|x\\\|\_\{1\}\)y\_\{t,J,0\}\+\\sum\_\{i=1\}^\{K\}x\_\{i\}\\widehat\{\\ell\}\_\{t,J,i\}=y\_\{t,J,0\}\+\\left\\langle x,z\_\{t,J\}\\right\\rangle\.The first term is independent ofxx, and the completed regularizer is negative entropy onΔK\+1\\Delta\_\{K\+1\}\. Thus, on each challenge round, the OMD update becomesx¯t\+1,J,k=x¯t,J,k​e−ηJ​yt,J,k𝖹t,J,\\bar\{x\}\_\{t\+1,J,k\}=\\frac\{\\bar\{x\}\_\{t,J,k\}e^\{\-\\eta\_\{J\}y\_\{t,J,k\}\}\}\{\\mathsf\{Z\}\_\{t,J\}\},where𝖹t,J≜∑k=0Kx¯t,J,k​e−ηJ​yt,J,k\.\\mathsf\{Z\}\_\{t,J\}\\triangleq\\sum\_\{k=0\}^\{K\}\\bar\{x\}\_\{t,J,k\}e^\{\-\\eta\_\{J\}y\_\{t,J,k\}\}\.Sinceyt,J,k≥0y\_\{t,J,k\}\\geq 0, applyinge−v≤1−v\+v2/2e^\{\-v\}\\leq 1\-v\+v^\{2\}/2forv≥0v\\geq 0andlog⁡z≤z−1\\log z\\leq z\-1forz\>0z\>0gives

log⁡𝖹t,J≤−ηJ​⟨x¯t,J,yt,J⟩\+ηJ22​⟨x¯t,J,yt,J2⟩\.\\log\\mathsf\{Z\}\_\{t,J\}\\leq\-\\eta\_\{J\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}\\right\\rangle\+\\frac\{\\eta\_\{J\}^\{2\}\}\{2\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle\.The exponential\-weights update therefore yields the standard KL\-potential bound

KL\(u¯∥x¯t\+1,J\)−KL\(u¯∥x¯t,J\)=ηJ⟨u¯,yt,J⟩\+log𝖹t,J≤−ηJ⟨x¯t,J−u¯,yt,J⟩\+ηJ22⟨x¯t,J,yt,J2⟩\.\\displaystyle\\text\{\\rm KL\}\(\\bar\{u\}\\\|\\bar\{x\}\_\{t\+1,J\}\)\-\\text\{\\rm KL\}\(\\bar\{u\}\\\|\\bar\{x\}\_\{t,J\}\)=\\eta\_\{J\}\\left\\langle\\bar\{u\},y\_\{t,J\}\\right\\rangle\+\\log\\mathsf\{Z\}\_\{t,J\}\\leq\-\\eta\_\{J\}\\left\\langle\\bar\{x\}\_\{t,J\}\-\\bar\{u\},y\_\{t,J\}\\right\\rangle\+\\frac\{\\eta\_\{J\}^\{2\}\}\{2\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle\.Rearranging and summing overt∈Jt\\in Jwitht≤nt\\leq nandbt=0b\_\{t\}=0telescopes the KL terms\. The initial completed distribution of the subroutine isπ\\pi, and the terminal KL divergence is nonnegative\. Hence

∑t∈J,t≤nbt=0⟨x¯t,J−u¯,yt,J⟩≤KL\(u¯∥π\)ηJ\+ηJ2​∑t∈J,t≤nbt=0⟨x¯t,J,yt,J2⟩\.\\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle\\bar\{x\}\_\{t,J\}\-\\bar\{u\},y\_\{t,J\}\\right\\rangle\\leq\\frac\{\\text\{\\rm KL\}\(\\bar\{u\}\\\|\\pi\)\}\{\\eta\_\{J\}\}\+\\frac\{\\eta\_\{J\}\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle\.Finally, using⟨x¯t,J−u¯,yt,J⟩=⟨xt,J−u,zt,J⟩\\left\\langle\\bar\{x\}\_\{t,J\}\-\\bar\{u\},y\_\{t,J\}\\right\\rangle=\\left\\langle x\_\{t,J\}\-u,z\_\{t,J\}\\right\\ranglegives[Eq\. \(37\)](https://arxiv.org/html/2609.13547#A1.E37)\. The argument holds for everyηJ\>0\\eta\_\{J\}\>0\. ∎

#### A\.7\.2A shared credit comparison

The next technical lemma relates continuation credit to the advantages of selected, disjoint intervals\. We apply the OMD bound with the comparator arm on selected intervals and with𝟎\\mathbf\{0\}elsewhere\. We then control the combined correction and curvature cost by a martingale bound, the arm estimates by the implicit\-exploration inequality of[Neu \(2015, Corollary 1\)](https://arxiv.org/html/2609.13547#bib.bib28), and the reference estimates by Freedman’s inequality\.

###### Lemma A\.2\.

Fix a reached epochIjI\_\{j\}, and let𝒮j⊆𝒥j\\mathcal\{S\}\_\{j\}\\subseteq\\mathcal\{J\}\_\{j\}be anℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\-measurable collection of disjoint intervals such thatut\(S\)=eaJu\_\{t\}^\{\(S\)\}=e\_\{a\_\{J\}\}on everyJ∈𝒮jJ\\in\\mathcal\{S\}\_\{j\}\. For everyδ∈\(0,1\)\\delta\\in\(0,1\), conditional onℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}, with probability at least1−δ1\-\\delta, simultaneously for alln∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\},

Cj,ncont\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}≥α​∑J∈𝒮jAJ​\(n\)−∑J∈𝒮jαηJ​log⁡6​T​Kδ​πaJ−2ηj−4​Γj−2​log⁡3δ−2​α​T​log⁡3δ\.\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{6TK\}\{\\delta\\pi\_\{a\_\{J\}\}\}\-\\frac\{2\}\{\\eta\_\{j\}\}\-4\\Gamma\_\{j\}\-2\\log\\frac\{3\}\{\\delta\}\-2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\}\}\.\(38\)Hereπ\\piis the completed initial distribution from[AppendixA\.1](https://arxiv.org/html/2609.13547#A1.SS1)\. For an interval that may extend beyond the current prefix, we use

AJ​\(n\)≜∑t∈J,t≤nbt=0⟨qt−eaJ,ℓt⟩,A\_\{J\}\(n\)\\triangleq\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle q\_\{t\}\-e\_\{a\_\{J\}\},\\ell\_\{t\}\\right\\rangle,which agrees with[Eq\.\(12\)](https://arxiv.org/html/2609.13547#S4.E12)wheneverJ⊆\{τj,…,n\}J\\subseteq\\\{\\tau\_\{j\},\\ldots,n\\\}\.

###### Proof\.

Condition onℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}, which fixes the family𝒮j\\mathcal\{S\}\_\{j\}and the rates\. All quantities below refer to the continuation\. By[AppendixA\.1](https://arxiv.org/html/2609.13547#A1.SS1), on challenge roundsptp\_\{t\}is𝒱j,tchal\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\-measurable andℙ⁡\(it=i∣𝒱j,tchal\)=pt,i\\mathbb\{P\}\(i\_\{t\}=i\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\)=p\_\{t,i\}\.

We first analyze the OMD dynamic of each subroutine\. For each active interval, its completed decision induces the arm distributionwt,J=\(1−‖xt,J‖1\)​qt\+xt,Jw\_\{t,J\}=\(1\-\\\|x\_\{t,J\}\\\|\_\{1\}\)q\_\{t\}\+x\_\{t,J\}\. The mixture in[Eq\. \(5\)](https://arxiv.org/html/2609.13547#S3.E5)givespt=\(1−α​\|𝒜t\|\)​qt\+α​∑J∈𝒜twt,Jp\_\{t\}=\(1\-\\alpha\|\{\\mathcal\{A\}\}\_\{t\}\|\)q\_\{t\}\+\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}w\_\{t,J\}andpt,i≥qt,i/2p\_\{t,i\}\\geq q\_\{t,i\}/2for alli∈\[K\]i\\in\[K\]due to the choice ofα\\alpha\.

On a challenge roundtt, using the definition ofZt=ℓt,it​\(qt,itpt,it−1\)Z\_\{t\}=\\ell\_\{t,i\_\{t\}\}\\big\(\\frac\{q\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\}\-1\\big\)gives

Zt\\displaystyle Z\_\{t\}=ℓt,it​\(qt,it−pt,it\)pt,it\\displaystyle=\\frac\{\\ell\_\{t,i\_\{t\}\}\(q\_\{t,i\_\{t\}\}\-p\_\{t,i\_\{t\}\}\)\}\{p\_\{t,i\_\{t\}\}\}=α​∑J∈𝒜tℓt,it​\(‖xt,J‖1​qt,it−xt,J,it\)pt,it\\displaystyle=\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\ell\_\{t,i\_\{t\}\}\\bigl\(\\\|x\_\{t,J\}\\\|\_\{1\}q\_\{t,i\_\{t\}\}\-x\_\{t,J,i\_\{t\}\}\\bigr\)\}\{p\_\{t,i\_\{t\}\}\}=α​∑J∈𝒜tℓt,it​\(‖xt,J‖1​qt,it−xt,J,it\)pt,it\+ηJ\+α​∑J∈𝒜tηJ​ℓt,it​\(‖xt,J‖1​qt,it−xt,J,it\)pt,it​\(pt,it\+ηJ\)\\displaystyle=\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\ell\_\{t,i\_\{t\}\}\\bigl\(\\\|x\_\{t,J\}\\\|\_\{1\}q\_\{t,i\_\{t\}\}\-x\_\{t,J,i\_\{t\}\}\\bigr\)\}\{p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\}\+\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\eta\_\{J\}\\ell\_\{t,i\_\{t\}\}\\bigl\(\\\|x\_\{t,J\}\\\|\_\{1\}q\_\{t,i\_\{t\}\}\-x\_\{t,J,i\_\{t\}\}\\bigr\)\}\{p\_\{t,i\_\{t\}\}\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)\}≥−α∑J∈𝒜t⟨xt,J,zt,J⟩−α∑J∈𝒜tηJ​xt,J,it​ℓt,itpt,it​\(pt,it\+ηJ\),\\displaystyle\\geq\-\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\left\\langle x\_\{t,J\},z\_\{t,J\}\\right\\rangle\-\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\eta\_\{J\}x\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)\},\(39\)where the last inequality drops the nonnegative term and uses the definition ofzt,J=ℓ^t,J−⟨qt,ℓ^t,J⟩​𝟏z\_\{t,J\}=\\widehat\{\\ell\}\_\{t,J\}\-\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\\mathbf\{1\}\. Moreover, for each active intervalJ∈𝒜tJ\\in\{\\mathcal\{A\}\}\_\{t\}, recall the notationyt,J,0≜⟨qt,ℓ^t,J⟩y\_\{t,J,0\}\\triangleq\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangleandyt,J,i≜ℓ^t,J,iy\_\{t,J,i\}\\triangleq\\widehat\{\\ell\}\_\{t,J,i\}fori∈\[K\]i\\in\[K\]defined in[LemmaA\.1](https://arxiv.org/html/2609.13547#A1.Thmtheorem1)\. Then, by the definition of the completed vectorx¯t,J\\bar\{x\}\_\{t,J\}and Jensen’s inequality, we have

α2​∑J∈𝒜tηJ​⟨x¯t,J,yt,J2⟩\\displaystyle\\frac\{\\alpha\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle=α2​∑J∈𝒜tηJ​\[\(1−‖xt,J‖1\)​⟨qt,ℓ^t,J⟩2\+⟨xt,J,ℓ^t,J2⟩\]\\displaystyle=\\frac\{\\alpha\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\[\(1\-\\\|x\_\{t,J\}\\\|\_\{1\}\)\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle^\{2\}\+\\left\\langle x\_\{t,J\},\\widehat\{\\ell\}\_\{t,J\}^\{2\}\\right\\rangle\\right\]≤α2​∑J∈𝒜tηJ​\[\(1−‖xt,J‖1\)​⟨qt,ℓ^t,J2⟩\+⟨xt,J,ℓ^t,J2⟩\]\\displaystyle\\leq\\frac\{\\alpha\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\[\(1\-\\\|x\_\{t,J\}\\\|\_\{1\}\)\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}^\{2\}\\right\\rangle\+\\left\\langle x\_\{t,J\},\\widehat\{\\ell\}\_\{t,J\}^\{2\}\\right\\rangle\\right\]=α2​∑J∈𝒜tηJ​⟨wt,J,ℓ^t,J2⟩\\displaystyle=\\frac\{\\alpha\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\\langle w\_\{t,J\},\\widehat\{\\ell\}\_\{t,J\}^\{2\}\\right\\rangle=α2​∑J∈𝒜tηJ​wt,J,it​ℓt,it2\(pt,it\+ηJ\)2,\\displaystyle=\\frac\{\\alpha\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\eta\_\{J\}w\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}^\{2\}\}\{\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)^\{2\}\},\(40\)where the last equality uses the fact thatℓ^t,J\\widehat\{\\ell\}\_\{t,J\}has only one nonzero coordinateℓ^t,J,it=ℓt,it/\(pt,it\+ηJ\)\\widehat\{\\ell\}\_\{t,J,i\_\{t\}\}=\\ell\_\{t,i\_\{t\}\}/\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)\.

Now according to[LemmaA\.1](https://arxiv.org/html/2609.13547#A1.Thmtheorem1), for anyu∈𝒳u\\in\{\\mathcal\{X\}\}, we know that

−α∑t∈J,t≤nbt=0⟨xt,J,zt,J⟩≥−α∑t∈J,t≤nbt=0⟨u,zt,J⟩−αηJKL\(u¯∥π\)−α​ηJ2∑t∈J,t≤nbt=0⟨x¯t,J,yt,J2⟩\.\\displaystyle\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle x\_\{t,J\},z\_\{t,J\}\\right\\rangle\\geq\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle u,z\_\{t,J\}\\right\\rangle\-\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\text\{\\rm KL\}\(\\bar\{u\}\\\|\\pi\)\-\\frac\{\\alpha\\eta\_\{J\}\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle\.For a selected intervalJ∈𝒮jJ\\in\\mathcal\{S\}\_\{j\}, takingu=eaJu=e\_\{a\_\{J\}\}givesKL\(eaJ¯∥π\)=log\(1/πaJ\)\\text\{\\rm KL\}\(\\overline\{e\_\{a\_\{J\}\}\}\\\|\\pi\)=\\log\(1/\\pi\_\{a\_\{J\}\}\)and−⟨eaJ,zt,J⟩=⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\.\-\\left\\langle e\_\{a\_\{J\}\},z\_\{t,J\}\\right\\rangle=\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\.Therefore, we have

−α∑t∈J,t≤nbt=0⟨xt,J,zt,J⟩\\displaystyle\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle x\_\{t,J\},z\_\{t,J\}\\right\\rangle≥α​∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)−αηJ​log⁡1πaJ−α​ηJ2​∑t∈J,t≤nbt=0⟨x¯t,J,yt,J2⟩\.\\displaystyle\\geq\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)\-\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{a\_\{J\}\}\}\-\\frac\{\\alpha\\eta\_\{J\}\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle\.ForJ∉𝒮jJ\\notin\\mathcal\{S\}\_\{j\}, takingu=𝟎u=\\mathbf\{0\}instead givesKL\(𝟎¯∥π\)=log\(1/π0\)\\text\{\\rm KL\}\(\\overline\{\\mathbf\{0\}\}\\\|\\pi\)=\\log\(1/\\pi\_\{0\}\)and⟨𝟎,zt,J⟩=0\\left\\langle\\mathbf\{0\},z\_\{t,J\}\\right\\rangle=0, and hence

−α∑t∈J,t≤nbt=0⟨xt,J,zt,J⟩\\displaystyle\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle x\_\{t,J\},z\_\{t,J\}\\right\\rangle≥−αηJ​log⁡1π0−α​ηJ2​∑t∈J,t≤nbt=0⟨x¯t,J,yt,J2⟩\.\\displaystyle\\geq\-\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{0\}\}\-\\frac\{\\alpha\\eta\_\{J\}\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle\.Summing these bounds over the interval subroutines gives

−α∑t=τjbt=0n∑J∈𝒜t⟨xt,J,zt,J⟩\\displaystyle\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\left\\langle x\_\{t,J\},z\_\{t,J\}\\right\\rangle≥α​∑J∈𝒮j∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)−∑J∈𝒮jαηJ​log⁡1πaJ\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{a\_\{J\}\}\}−∑J∈𝒥j∖𝒮jαηJlog1π0−α2∑t=τjbt=0n∑J∈𝒜tηJ⟨x¯t,J,yt,J2⟩\\displaystyle\\qquad\-\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\\setminus\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{0\}\}\-\\frac\{\\alpha\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle≥α​∑J∈𝒮j∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)−∑J∈𝒮jαηJ​log⁡1πaJ−2ηj−α2​∑t=τjbt=0n∑J∈𝒜tηJ​⟨x¯t,J,yt,J2⟩,\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{a\_\{J\}\}\}\-\\frac\{2\}\{\\eta\_\{j\}\}\-\\frac\{\\alpha\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle,\(41\)where the last inequality uses\|𝒥j\|≤2​T\|\\mathcal\{J\}\_\{j\}\|\\leq 2T,ηJ=α​ηjUJ≥α​ηj\\eta\_\{J\}=\\frac\{\\alpha\\eta\_\{j\}\}\{U\_\{J\}\}\\geq\\alpha\\eta\_\{j\}, and

∑J∈𝒥j∖𝒮jαηJ​log⁡1π0\\displaystyle\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\\setminus\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{0\}\}≤∑J∈𝒥jαηJ​log⁡1π0≤\|𝒥j\|ηj​log⁡1π0≤2ηj\.\\displaystyle\\leq\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{0\}\}\\leq\\frac\{\|\\mathcal\{J\}\_\{j\}\|\}\{\\eta\_\{j\}\}\\log\\frac\{1\}\{\\pi\_\{0\}\}\\leq\\frac\{2\}\{\\eta\_\{j\}\}\.
We now combine this OMD comparison with the preceding credit and curvature bounds\. Sincept=qtp\_\{t\}=q\_\{t\}and henceZt=0Z\_\{t\}=0on main rounds, summing[Eq\. \(39\)](https://arxiv.org/html/2609.13547#A1.E39)over the challenge rounds up tonngives

Cj,ncont=∑t=τjnZt=∑t=τjbt=0nZt≥−α∑t=τjbt=0n∑J∈𝒜t⟨xt,J,zt,J⟩−α∑t=τjbt=0n∑J∈𝒜tηJ​xt,J,it​ℓt,itpt,it​\(pt,it\+ηJ\)\.\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}=\\sum\_\{t=\\tau\_\{j\}\}^\{n\}Z\_\{t\}=\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}Z\_\{t\}\\geq\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\left\\langle x\_\{t,J\},z\_\{t,J\}\\right\\rangle\-\\alpha\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\eta\_\{J\}x\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)\}\.\(42\)By[Eq\. \(40\)](https://arxiv.org/html/2609.13547#A1.E40), the curvature term from[LemmaA\.1](https://arxiv.org/html/2609.13547#A1.Thmtheorem1)satisfies

α2​∑t=τjbt=0n∑J∈𝒜tηJ​⟨x¯t,J,yt,J2⟩\\displaystyle\\frac\{\\alpha\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\\langle\\bar\{x\}\_\{t,J\},y\_\{t,J\}^\{2\}\\right\\rangle≤α2​∑t=τjbt=0n∑J∈𝒜tηJ​wt,J,it​ℓt,it2\(pt,it\+ηJ\)2\.\\displaystyle\\leq\\frac\{\\alpha\}\{2\}\\sum\_\{\\begin\{subarray\}\{c\}t=\\tau\_\{j\}\\\\ b\_\{t\}=0\\end\{subarray\}\}^\{n\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\frac\{\\eta\_\{J\}w\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}^\{2\}\}\{\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)^\{2\}\}\.\(43\)Plugging[Eq\. \(41\)](https://arxiv.org/html/2609.13547#A1.E41)and[Eq\. \(43\)](https://arxiv.org/html/2609.13547#A1.E43)into[Eq\. \(42\)](https://arxiv.org/html/2609.13547#A1.E42)gives

Cj,ncont\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}≥α​∑J∈𝒮j∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)−∑J∈𝒮jαηJ​log⁡1πaJ−2ηj−∑t=τjnDt,\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{1\}\{\\pi\_\{a\_\{J\}\}\}\-\\frac\{2\}\{\\eta\_\{j\}\}\-\\sum\_\{t=\\tau\_\{j\}\}^\{n\}D\_\{t\},\(44\)where we define

Dt≜α​∑J∈𝒜tηJ​\(xt,J,it​ℓt,itpt,it​\(pt,it\+ηJ\)\+wt,J,it​ℓt,it22​\(pt,it\+ηJ\)2\)\\displaystyle D\_\{t\}\\triangleq\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\left\(\\frac\{x\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)\}\+\\frac\{w\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}^\{2\}\}\{2\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)^\{2\}\}\\right\)\(45\)for each challenge roundttand setDt=0D\_\{t\}=0on main rounds\.

By[LemmaA\.3](https://arxiv.org/html/2609.13547#A1.Thmtheorem3)withε=δ/3\\varepsilon=\\delta/3, with conditional probability at least1−δ/31\-\\delta/3, simultaneously for allnn,

∑t=τjnDt≤3​Γj\+32​log⁡3δ\.\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}D\_\{t\}\\leq 3\\Gamma\_\{j\}\+\\frac\{3\}\{2\}\\log\\frac\{3\}\{\\delta\}\.\(46\)Moreover, by[LemmaA\.4](https://arxiv.org/html/2609.13547#A1.Thmtheorem4)withε=δ/3\\varepsilon=\\delta/3, with conditional probability at least1−2​δ/31\-2\\delta/3, simultaneously for allnn,

α​∑J∈𝒮j∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)\\displaystyle\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)≥α​∑J∈𝒮jAJ​\(n\)−∑J∈𝒮jαηJ​log⁡6​T​Kδ−Γj−2​α​T​log⁡3δ−α​log⁡3δ\.\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{6TK\}\{\\delta\}\-\\Gamma\_\{j\}\-2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\}\}\-\\alpha\\log\\frac\{3\}\{\\delta\}\.\(47\)Intersecting these two events and substituting them into[Eq\. \(44\)](https://arxiv.org/html/2609.13547#A1.E44)gives, simultaneously for allnn,

Cj,ncont\\displaystyle C\_\{j,n\}^\{\\mathrm\{cont\}\}≥α​∑J∈𝒮jAJ​\(n\)−∑J∈𝒮jαηJ​\(log⁡1πaJ\+log⁡6​T​Kδ\)−2ηj−4​Γj−\(32\+α\)​log⁡3δ−2​α​T​log⁡3δ\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\left\(\\log\\frac\{1\}\{\\pi\_\{a\_\{J\}\}\}\+\\log\\frac\{6TK\}\{\\delta\}\\right\)\-\\frac\{2\}\{\\eta\_\{j\}\}\-4\\Gamma\_\{j\}\-\\left\(\\frac\{3\}\{2\}\+\\alpha\\right\)\\log\\frac\{3\}\{\\delta\}\-2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\}\}≥α​∑J∈𝒮jAJ​\(n\)−∑J∈𝒮jαηJ​log⁡6​T​Kδ​πaJ−2ηj−4​Γj−2​log⁡3δ−2​α​T​log⁡3δ,\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{6TK\}\{\\delta\\pi\_\{a\_\{J\}\}\}\-\\frac\{2\}\{\\eta\_\{j\}\}\-4\\Gamma\_\{j\}\-2\\log\\frac\{3\}\{\\delta\}\-2\\alpha\\sqrt\{T\\log\\frac\{3\}\{\\delta\}\},where the last inequality usesα≤12\\alpha\\leq\\frac\{1\}\{2\}\. This finishes the proof\. ∎

The first auxiliary lemma controls the denominator correction and the curvature cost collected inDtD\_\{t\}\. Their conditional means are bounded by the chargeΓj\\Gamma\_\{j\}, while a Freedman inequality controls their fluctuations uniformly over all continuation prefixes\.

###### Lemma A\.3\.

Fix a reached epochIjI\_\{j\}and condition onℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\. For everyε∈\(0,1\)\\varepsilon\\in\(0,1\), with conditional probability at least1−ε1\-\\varepsilon, simultaneously for alln∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\},

∑t=τjnDt≤3​Γj\+32​log⁡1ε\.\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}D\_\{t\}\\leq 3\\Gamma\_\{j\}\+\\frac\{3\}\{2\}\\log\\frac\{1\}\{\\varepsilon\}\.\(48\)

###### Proof\.

On a challenge round, the first term in[Eq\. \(45\)](https://arxiv.org/html/2609.13547#A1.E45)satisfies

α​∑J∈𝒜tηJ​xt,J,it​ℓt,itpt,it​\(pt,it\+ηJ\)\\displaystyle\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\frac\{x\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)\}≤α​∑J∈𝒜txt,J,itpt,it≤1,\\displaystyle\\leq\\frac\{\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}x\_\{t,J,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\}\\leq 1,whereasη/\(p\+η\)2≤1/\(4​p\)\\eta/\(p\+\\eta\)^\{2\}\\leq 1/\(4p\)gives

α2​∑J∈𝒜tηJ​wt,J,it​ℓt,it2\(pt,it\+ηJ\)2\\displaystyle\\frac\{\\alpha\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\frac\{w\_\{t,J,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}^\{2\}\}\{\(p\_\{t,i\_\{t\}\}\+\\eta\_\{J\}\)^\{2\}\}≤α​∑J∈𝒜twt,J,it8​pt,it≤18\.\\displaystyle\\leq\\frac\{\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}w\_\{t,J,i\_\{t\}\}\}\{8p\_\{t,i\_\{t\}\}\}\\leq\\frac\{1\}\{8\}\.Thus0≤Dt≤9/80\\leq D\_\{t\}\\leq 9/8on challenge rounds, whileDt=0D\_\{t\}=0on main rounds\. Conditional on𝒱j,tchal\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}, averaging overit∼pti\_\{t\}\\sim p\_\{t\}gives

𝔼⁡\[Dt∣𝒱j,tchal\]\\displaystyle\\mathbb\{E\}\[D\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]=α​∑J∈𝒜tηJ​∑i=1K\(xt,J,i​ℓt,ipt,i\+ηJ\+pt,i​wt,J,i​ℓt,i22​\(pt,i\+ηJ\)2\)\.\\displaystyle=\\alpha\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\eta\_\{J\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{x\_\{t,J,i\}\\ell\_\{t,i\}\}\{p\_\{t,i\}\+\\eta\_\{J\}\}\+\\frac\{p\_\{t,i\}w\_\{t,J,i\}\\ell\_\{t,i\}^\{2\}\}\{2\(p\_\{t,i\}\+\\eta\_\{J\}\)^\{2\}\}\\right\)\.For everyJ∈𝒜tJ\\in\{\\mathcal\{A\}\}\_\{t\}, the first term is at most bothK​ηJK\\eta\_\{J\}andα\\alpha, using respectivelyα​xt,J,i≤pt,i\\alpha x\_\{t,J,i\}\\leq p\_\{t,i\}andηJ/\(pt,i\+ηJ\)≤1\\eta\_\{J\}/\(p\_\{t,i\}\+\\eta\_\{J\}\)\\leq 1\. The second term is at most bothK​ηJ/2K\\eta\_\{J\}/2andα/8\\alpha/8, using respectivelyα​wt,J,i≤pt,i\\alpha w\_\{t,J,i\}\\leq p\_\{t,i\}andηJ​pt,i/\(pt,i\+ηJ\)2≤1/4\\eta\_\{J\}p\_\{t,i\}/\(p\_\{t,i\}\+\\eta\_\{J\}\)^\{2\}\\leq 1/4\. Consequently,

𝔼⁡\[Dt∣𝒱j,tchal\]≤32​∑J∈𝒜tmin⁡\{K​ηJ,α\}\.\\displaystyle\\mathbb\{E\}\[D\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]\\leq\\frac\{3\}\{2\}\\sum\_\{J\\in\{\\mathcal\{A\}\}\_\{t\}\}\\min\\\{K\\eta\_\{J\},\\alpha\\\}\.\(49\)For everyt∈\{τj,…,T\}t\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, letμt≜𝔼⁡\[Dt∣𝒱j,tchal\]\\mu\_\{t\}\\triangleq\\mathbb\{E\}\[D\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]on challenge rounds andμt=0\\mu\_\{t\}=0on main rounds\. Then, for everynn, we have

∑t=τjnμt\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\mu\_\{t\}≤32∑J∈𝒥j\|\{t∈J:t≤n,bt=0\}\|min\{KηJ,α\}≤32Γj\.\\displaystyle\\leq\\frac\{3\}\{2\}\\sum\_\{J\\in\\mathcal\{J\}\_\{j\}\}\\left\|\\\{t\\in J:t\\leq n,\\ b\_\{t\}=0\\\}\\right\|\\min\\\{K\\eta\_\{J\},\\alpha\\\}\\leq\\frac\{3\}\{2\}\\Gamma\_\{j\}\.\(50\)
For everyt∈\{τj,…,T\}t\\in\\\{\\tau\_\{j\},\\ldots,T\\\}, defineXt≜Dt−μt\.X\_\{t\}\\triangleq D\_\{t\}\-\\mu\_\{t\}\.ThenXtX\_\{t\}is𝒱j,t\+1chal\{\\mathcal\{V\}\}\_\{j,t\+1\}^\{\\mathrm\{chal\}\}\-measurable and𝔼⁡\[Xt∣𝒱j,tchal\]=0\\mathbb\{E\}\[X\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]=0, so\{Xt\}t=τjT\\\{X\_\{t\}\\\}\_\{t=\\tau\_\{j\}\}^\{T\}is a martingale\-difference sequence with respect to\(𝒱j,tchal\)t=τjT\+1\(\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\)\_\{t=\\tau\_\{j\}\}^\{T\+1\}\. Since0≤Dt≤9/80\\leq D\_\{t\}\\leq 9/8, we haveXt≤9/8X\_\{t\}\\leq 9/8and

𝔼⁡\[Xt2∣𝒱j,tchal\]=Var⁡\(Dt∣𝒱j,tchal\)≤𝔼⁡\[Dt2∣𝒱j,tchal\]≤98​μt\.\\displaystyle\\mathbb\{E\}\[X\_\{t\}^\{2\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]=\\mathrm\{Var\}\(D\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\)\\leq\\mathbb\{E\}\[D\_\{t\}^\{2\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]\\leq\\frac\{9\}\{8\}\\mu\_\{t\}\.Therefore, by[Eq\. \(50\)](https://arxiv.org/html/2609.13547#A1.E50), for everynn,

∑t=τjn𝔼⁡\[Xt2∣𝒱j,tchal\]≤98​∑t=τjnμt≤2716​Γj\.\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\mathbb\{E\}\[X\_\{t\}^\{2\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]\\leq\\frac\{9\}\{8\}\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\mu\_\{t\}\\leq\\frac\{27\}\{16\}\\Gamma\_\{j\}\.\(51\)Applying Freedman’s inequality \(e\.g\.,[Beygelzimer et al\. \(2011, Theorem 1\)](https://arxiv.org/html/2609.13547#bib.bib1)\) withR=9/8R=9/8gives, for a martingale\-difference sequence with total conditional varianceVV,

∑tXt≤98​log⁡1ε\+8​\(e−2\)9​V\\sum\_\{t\}X\_\{t\}\\leq\\frac\{9\}\{8\}\\log\\frac\{1\}\{\\varepsilon\}\+\\frac\{8\(e\-2\)\}\{9\}Vwith probability at least1−ε1\-\\varepsilon\. To obtain the bound simultaneously over all prefixes, letσ\\sigmabe the firstnnsuch that

∑t=τjnXt\>98​log⁡1ε\+32​\(e−2\)​Γj,\\sum\_\{t=\\tau\_\{j\}\}^\{n\}X\_\{t\}\>\\frac\{9\}\{8\}\\log\\frac\{1\}\{\\varepsilon\}\+\\frac\{3\}\{2\}\(e\-2\)\\Gamma\_\{j\},and setσ=T\+1\\sigma=T\+1if no suchnnexists\. Consider the stopped incrementsX~t=Xt𝕀\{σ≥t\}\\widetilde\{X\}\_\{t\}=X\_\{t\}\\mathbb\{I\}\\\{\\sigma\\geq t\\\}\. Since\{σ≥t\}\\\{\\sigma\\geq t\\\}only depends onXτj,…,Xt−1X\_\{\\tau\_\{j\}\},\\ldots,X\_\{t\-1\}, it is𝒱j,tchal\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\-measurable, meaning that\{X~t\}\\\{\\widetilde\{X\}\_\{t\}\\\}is still a martingale\-difference sequence\. Moreover, by[Eq\. \(51\)](https://arxiv.org/html/2609.13547#A1.E51), its total conditional variance is at most27​Γj/1627\\Gamma\_\{j\}/16\. Therefore, applying Freedman’s inequality once to the stopped sequence gives, with conditional probability at least1−ε1\-\\varepsilon,

∑t=τjTX~t≤98​log⁡1ε\+8​\(e−2\)9​2716​Γj=98​log⁡1ε\+32​\(e−2\)​Γj\.\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{T\}\\widetilde\{X\}\_\{t\}\\leq\\frac\{9\}\{8\}\\log\\frac\{1\}\{\\varepsilon\}\+\\frac\{8\(e\-2\)\}\{9\}\\frac\{27\}\{16\}\\Gamma\_\{j\}=\\frac\{9\}\{8\}\\log\\frac\{1\}\{\\varepsilon\}\+\\frac\{3\}\{2\}\(e\-2\)\\Gamma\_\{j\}\.Ifσ≤T\\sigma\\leq T, however, the stopped sum equals∑t=τjσXt\\sum\_\{t=\\tau\_\{j\}\}^\{\\sigma\}X\_\{t\}and exceeds the same boundary by the definition ofσ\\sigma\. Hence, with conditional probability at least1−ε1\-\\varepsilon, no prefix crosses the boundary, and for allnn,

∑t=τjn\(Dt−μt\)≤98​log⁡1ε\+32​\(e−2\)​Γj\.\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\(D\_\{t\}\-\\mu\_\{t\}\)\\leq\\frac\{9\}\{8\}\\log\\frac\{1\}\{\\varepsilon\}\+\\frac\{3\}\{2\}\(e\-2\)\\Gamma\_\{j\}\.Combining this inequality with[Eq\. \(50\)](https://arxiv.org/html/2609.13547#A1.E50)yields

∑t=τjnDt≤32​Γj\+32​\(e−2\)​Γj\+98​log⁡1ε≤3​Γj\+32​log⁡1ε,\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}D\_\{t\}\\leq\\frac\{3\}\{2\}\\Gamma\_\{j\}\+\\frac\{3\}\{2\}\(e\-2\)\\Gamma\_\{j\}\+\\frac\{9\}\{8\}\\log\\frac\{1\}\{\\varepsilon\}\\leq 3\\Gamma\_\{j\}\+\\frac\{3\}\{2\}\\log\\frac\{1\}\{\\varepsilon\},which proves[Eq\. \(48\)](https://arxiv.org/html/2609.13547#A1.E48)\. ∎

The second auxiliary lemma converts the estimated advantage of the selected intervals into their true advantage\.

###### Lemma A\.4\.

Fix a reached epochIjI\_\{j\}and condition onℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\. Let𝒮j⊆𝒥j\\mathcal\{S\}\_\{j\}\\subseteq\\mathcal\{J\}\_\{j\}be anℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}\-measurable collection of disjoint intervals such thatut\(S\)=eaJu\_\{t\}^\{\(S\)\}=e\_\{a\_\{J\}\}on everyJ∈𝒮jJ\\in\\mathcal\{S\}\_\{j\}\. For everyε∈\(0,1/2\)\\varepsilon\\in\(0,1/2\), with conditional probability at least1−2​ε1\-2\\varepsilon, simultaneously for alln∈\{τj,…,T\}n\\in\\\{\\tau\_\{j\},\\ldots,T\\\},

α​∑J∈𝒮j∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)\\displaystyle\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)≥α​∑J∈𝒮jAJ​\(n\)−∑J∈𝒮jαηJ​log⁡2​T​Kε−Γj−2​α​T​log⁡1ε−α​log⁡1ε\.\\displaystyle\\geq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{2TK\}\{\\varepsilon\}\-\\Gamma\_\{j\}\-2\\alpha\\sqrt\{T\\log\\frac\{1\}\{\\varepsilon\}\}\-\\alpha\\log\\frac\{1\}\{\\varepsilon\}\.\(52\)

###### Proof\.

We first control the arm\-coordinate estimatesℓ^t,J\\widehat\{\\ell\}\_\{t,J\}\. FixJJandnn\. Conditional onℱjrate\{\\mathcal\{F\}\}\_\{j\}^\{\\mathrm\{rate\}\}, the rateηJ\\eta\_\{J\}is fixed, and on every challenge round the sampled arm is drawn fromptp\_\{t\}\. Applying[Neu \(2015, Corollary 1\)](https://arxiv.org/html/2609.13547#bib.bib28)withγ=ηJ\\gamma=\\eta\_\{J\}and failure probabilityε/\(2​T2\)\\varepsilon/\(2T^\{2\}\)gives, simultaneously for alla∈\[K\]a\\in\[K\],

∑t∈J,t≤nbt=0\(ℓ^t,J,a−ℓt,a\)\\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\(\\widehat\{\\ell\}\_\{t,J,a\}\-\\ell\_\{t,a\}\)≤12​ηJ​log⁡2​K​T2ε\.\\displaystyle\\leq\\frac\{1\}\{2\\eta\_\{J\}\}\\log\\frac\{2KT^\{2\}\}\{\\varepsilon\}\.There are fewer than2​T2Tcanonical intervals and at mostTTendpoints\. A union bound therefore gives, with conditional probability at least1−ε1\-\\varepsilon, simultaneously for allJJ,aa, andnn,

∑t∈J,t≤nbt=0\(ℓ^t,J,a−ℓt,a\)≤1ηJ​log⁡2​T​Kε\.\\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\(\\widehat\{\\ell\}\_\{t,J,a\}\-\\ell\_\{t,a\}\)\\leq\\frac\{1\}\{\\eta\_\{J\}\}\\log\\frac\{2TK\}\{\\varepsilon\}\.\(53\)
We next control the first term in the estimated selected advantage\. For every prefixnn, define

Q^n\\displaystyle\\widehat\{Q\}\_\{n\}≜α​∑J∈𝒮j∑t∈J,t≤nbt=0⟨qt,ℓ^t,J⟩,\\displaystyle\\triangleq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle,Qn\\displaystyle Q\_\{n\}≜α​∑J∈𝒮j∑t∈J,t≤nbt=0⟨qt,ℓt⟩\.\\displaystyle\\triangleq\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle q\_\{t\},\\ell\_\{t\}\\right\\rangle\.For everyJ∈𝒮jJ\\in\\mathcal\{S\}\_\{j\}and challenge roundt∈Jt\\in J,

α⁡⟨qt,ℓt⟩−α​𝔼​\[⟨qt,ℓ^t,J⟩∣𝒱j,tchal\]\\displaystyle\\alpha\\left\\langle q\_\{t\},\\ell\_\{t\}\\right\\rangle\-\\alpha\\mathbb\{E\}\\left\[\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\\right\]=α​ηJ​∑i=1Kqt,i​ℓt,ipt,i\+ηJ≤min⁡\{K​ηJ,α\}\.\\displaystyle=\\alpha\\eta\_\{J\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\\ell\_\{t,i\}\}\{p\_\{t,i\}\+\\eta\_\{J\}\}\\leq\\min\\\{K\\eta\_\{J\},\\alpha\\\}\.Summing overJJandttgives

Qn−α​∑J∈𝒮j∑t∈J,t≤nbt=0𝔼⁡\[⟨qt,ℓ^t,J⟩∣𝒱j,tchal\]\\displaystyle Q\_\{n\}\-\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\mathbb\{E\}\\left\[\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\\right\]≤∑J∈𝒮j\|J\|​min⁡\{K​ηJ,α\}≤Γj,\\displaystyle\\leq\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\|J\|\\min\\\{K\\eta\_\{J\},\\alpha\\\}\\leq\\Gamma\_\{j\},\(54\)where the last inequality uses𝒮j⊆𝒥j\\mathcal\{S\}\_\{j\}\\subseteq\\mathcal\{J\}\_\{j\}\. We next control the fluctuation of the estimated loss\. By the assumption, the intervals in𝒮j\\mathcal\{S\}\_\{j\}are disjoint\. Hence, for everytt, there is at most oneJ∈𝒮jJ\\in\\mathcal\{S\}\_\{j\}such thatt∈Jt\\in J\. If such an interval exists, denote it byJtJ\_\{t\}and define

r^t\\displaystyle\\widehat\{r\}\_\{t\}≜α𝕀\{bt=0\}⟨qt,ℓ^t,Jt⟩\.\\displaystyle\\triangleq\\alpha\\mathbb\{I\}\\\{b\_\{t\}=0\\\}\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\_\{t\}\}\\right\\rangle\.If no such interval exists, setr^t=0\\widehat\{r\}\_\{t\}=0\. Then we haveQ^n=∑t=τjnr^t\.\\widehat\{Q\}\_\{n\}=\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\widehat\{r\}\_\{t\}\.LetYt≜𝔼⁡\[r^t∣𝒱j,tchal\]−r^t\.Y\_\{t\}\\triangleq\\mathbb\{E\}\[\\widehat\{r\}\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]\-\\widehat\{r\}\_\{t\}\.ThenYtY\_\{t\}is𝒱j,t\+1chal\{\\mathcal\{V\}\}\_\{j,t\+1\}^\{\\mathrm\{chal\}\}\-measurable and𝔼⁡\[Yt∣𝒱j,tchal\]=0\\mathbb\{E\}\[Y\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]=0, so\{Yt\}t=τjT\\\{Y\_\{t\}\\\}\_\{t=\\tau\_\{j\}\}^\{T\}is a martingale\-difference sequence\. On a challenge round for whichJtJ\_\{t\}exists,

0≤r^t\\displaystyle 0\\leq\\widehat\{r\}\_\{t\}=α​qt,it​ℓt,itpt,it\+ηJt≤α​qt,itpt,it≤2​α,\\displaystyle=\\alpha\\frac\{q\_\{t,i\_\{t\}\}\\ell\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\+\\eta\_\{J\_\{t\}\}\}\\leq\\alpha\\frac\{q\_\{t,i\_\{t\}\}\}\{p\_\{t,i\_\{t\}\}\}\\leq 2\\alpha,where we usedpt≥qt/2p\_\{t\}\\geq q\_\{t\}/2\. Moreover,

𝔼⁡\[r^t∣𝒱j,tchal\]\\displaystyle\\mathbb\{E\}\[\\widehat\{r\}\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]=α​∑i=1Kpt,i​qt,i​ℓt,ipt,i\+ηJt≤α​∑i=1Kqt,i​ℓt,i≤α\.\\displaystyle=\\alpha\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,i\}q\_\{t,i\}\\ell\_\{t,i\}\}\{p\_\{t,i\}\+\\eta\_\{J\_\{t\}\}\}\\leq\\alpha\\sum\_\{i=1\}^\{K\}q\_\{t,i\}\\ell\_\{t,i\}\\leq\\alpha\.ThusYt≤αY\_\{t\}\\leq\\alpha\. Sincer^t2≤2​α​r^t\\widehat\{r\}\_\{t\}^\{2\}\\leq 2\\alpha\\widehat\{r\}\_\{t\}, we also have

𝔼⁡\[Yt2∣𝒱j,tchal\]=Var⁡\(r^t∣𝒱j,tchal\)≤2​α​𝔼​\[r^t∣𝒱j,tchal\]−𝔼​\[r^t∣𝒱j,tchal\]2≤α2\.\\displaystyle\\mathbb\{E\}\[Y\_\{t\}^\{2\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]=\\mathrm\{Var\}\(\\widehat\{r\}\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\)\\leq 2\\alpha\\mathbb\{E\}\[\\widehat\{r\}\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]\-\\mathbb\{E\}\[\\widehat\{r\}\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]^\{2\}\\leq\\alpha^\{2\}\.The same bounds hold trivially whenr^t=0\\widehat\{r\}\_\{t\}=0\. Hence the cumulative conditional variance over every prefix is at mostα2​T\\alpha^\{2\}T\. Applying[Beygelzimer et al\. \(2011, Theorem 1\)](https://arxiv.org/html/2609.13547#bib.bib1)withR=αR=\\alphaand a priori variance upper boundα2​T\\alpha^\{2\}T, together with the same first\-crossing stopping argument as in[LemmaA\.3](https://arxiv.org/html/2609.13547#A1.Thmtheorem3), gives, with conditional probability at least1−ε1\-\\varepsilon, simultaneously for allnn,

∑t=τjnYt\\displaystyle\\sum\_\{t=\\tau\_\{j\}\}^\{n\}Y\_\{t\}≤2​α​T​log⁡1ε\+α​log⁡1ε\.\\displaystyle\\leq 2\\alpha\\sqrt\{T\\log\\frac\{1\}\{\\varepsilon\}\}\+\\alpha\\log\\frac\{1\}\{\\varepsilon\}\.\(55\)SinceQ^n=∑t=τjn𝔼⁡\[r^t∣𝒱j,tchal\]−∑t=τjnYt\\widehat\{Q\}\_\{n\}=\\sum\_\{t=\\tau\_\{j\}\}^\{n\}\\mathbb\{E\}\[\\widehat\{r\}\_\{t\}\\mid\{\\mathcal\{V\}\}\_\{j,t\}^\{\\mathrm\{chal\}\}\]\-\\sum\_\{t=\\tau\_\{j\}\}^\{n\}Y\_\{t\}, combining[Eq\. \(54\)](https://arxiv.org/html/2609.13547#A1.E54)and[Eq\. \(55\)](https://arxiv.org/html/2609.13547#A1.E55)gives

Q^n\\displaystyle\\widehat\{Q\}\_\{n\}≥Qn−Γj−2​α​T​log⁡1ε−α​log⁡1ε\\displaystyle\\geq Q\_\{n\}\-\\Gamma\_\{j\}\-2\\alpha\\sqrt\{T\\log\\frac\{1\}\{\\varepsilon\}\}\-\\alpha\\log\\frac\{1\}\{\\varepsilon\}\(56\)simultaneously for allnn\. Finally, intersecting the events in[Eq\. \(56\)](https://arxiv.org/html/2609.13547#A1.E56)and[Eq\. \(53\)](https://arxiv.org/html/2609.13547#A1.E53), and applying[Eq\. \(53\)](https://arxiv.org/html/2609.13547#A1.E53)witha=aJa=a\_\{J\}, gives

α​∑J∈𝒮j∑t∈J,t≤nbt=0\(⟨qt,ℓ^t,J⟩−ℓ^t,J,aJ\)\\displaystyle\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\(\\left\\langle q\_\{t\},\\widehat\{\\ell\}\_\{t,J\}\\right\\rangle\-\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}\\right\)=Q^n−α​∑J∈𝒮j∑t∈J,t≤nbt=0ℓ^t,J,aJ\\displaystyle=\\widehat\{Q\}\_\{n\}\-\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\widehat\{\\ell\}\_\{t,J,a\_\{J\}\}≥Qn−α​∑J∈𝒮j∑t∈J,t≤nbt=0ℓt,aJ−∑J∈𝒮jαηJ​log⁡2​T​Kε−Γj−2​α​T​log⁡1ε−α​log⁡1ε\\displaystyle\\geq Q\_\{n\}\-\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\ell\_\{t,a\_\{J\}\}\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{2TK\}\{\\varepsilon\}\-\\Gamma\_\{j\}\-2\\alpha\\sqrt\{T\\log\\frac\{1\}\{\\varepsilon\}\}\-\\alpha\\log\\frac\{1\}\{\\varepsilon\}=α​∑J∈𝒮j∑t∈J,t≤nbt=0⟨qt−eaJ,ℓt⟩−∑J∈𝒮jαηJ​log⁡2​T​Kε−Γj−2​α​T​log⁡1ε−α​log⁡1ε\\displaystyle=\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\sum\_\{\\begin\{subarray\}\{c\}t\\in J,\\ t\\leq n\\\\ b\_\{t\}=0\\end\{subarray\}\}\\left\\langle q\_\{t\}\-e\_\{a\_\{J\}\},\\ell\_\{t\}\\right\\rangle\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{2TK\}\{\\varepsilon\}\-\\Gamma\_\{j\}\-2\\alpha\\sqrt\{T\\log\\frac\{1\}\{\\varepsilon\}\}\-\\alpha\\log\\frac\{1\}\{\\varepsilon\}=α​∑J∈𝒮jAJ​\(n\)−∑J∈𝒮jαηJ​log⁡2​T​Kε−Γj−2​α​T​log⁡1ε−α​log⁡1ε\.\\displaystyle=\\alpha\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}A\_\{J\}\(n\)\-\\sum\_\{J\\in\\mathcal\{S\}\_\{j\}\}\\frac\{\\alpha\}\{\\eta\_\{J\}\}\\log\\frac\{2TK\}\{\\varepsilon\}\-\\Gamma\_\{j\}\-2\\alpha\\sqrt\{T\\log\\frac\{1\}\{\\varepsilon\}\}\-\\alpha\\log\\frac\{1\}\{\\varepsilon\}\.The two events each fail with conditional probability at mostε\\varepsilon, so their intersection has conditional probability at least1−2​ε1\-2\\varepsilon\. This proves[Eq\. \(52\)](https://arxiv.org/html/2609.13547#A1.E52)\. ∎