重尾噪声下的无参数区间动态遗憾

# Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
Source: [https://arxiv.org/html/2610.02258](https://arxiv.org/html/2610.02258)
###### Abstract

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditionalppth noise moment,1<p≤21<p\\leq 2\. For every fixed intervalIIof lengthnnand comparator path withΛI=1\+PI/D\\Lambda\_\{I\}=1\+P\_\{I\}/D, one learner achieves

𝔼​RegretI⁡\(u\)≤min⁡\{G​D​n,C⁡\[G​D​n⁡\(ΛI\+log2⁡\(2​T\)\)\+σ​D​n1/p​\(ΛI\+log2⁡\(2​T\)\)\(p−1\)/p\]\}\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\leq\\min\\\!\\left\\\{GDn,\\ C\\\!\\left\[GD\\sqrt\{n\(\\Lambda\_\{I\}\+\\log^\{2\}\(2T\)\)\}\+\\sigma Dn^\{1/p\}\(\\Lambda\_\{I\}\+\\log^\{2\}\(2T\)\)^\{\(p\-1\)/p\}\\right\]\\right\\\}\.The learner uses none ofG,σ,p,I,PIG,\\sigma,p,I,P\_\{I\}, and the constant is universal\. Interval adaptation adds to comparator complexity, preserving the distinct mean\-gradient and noise exponents\. The analysis controls calibration in expectation and limits the cost of observation\-scale changes\. Its general theorem compares to distributions over predictably available experts with relative\-entropy dependence on a nonuniform prior\. A common prior favors long windows and long restart lengths\. With the statistics supplied, the interval cost becomes1\+log⁡\(T/n\)1\+\\log\(T/n\), including the optimal full\-horizon static rate\. A change\-of\-measure lower bound identifies the noise power of this logarithm for learners retaining a full\-horizon optimal guarantee, under explicit conditions\. Static comparisons and deterministic partitions follow from the same decisions\.

## IIntroduction

An online learner may run continuously while its performance is evaluated on time windows chosen later\. A full\-horizon guarantee can obscure a short period of poor tracking: regret accumulated before that period may compensate for it\. Interval\-dynamic regret instead compares the learner with a moving decision sequence on each fixed evaluation window\. This distinction is useful when comparator movement is concentrated in an episode or when several windows describe different operating conditions\. With stochastic first\-order feedback, an additional difficulty is that a single observation can be arbitrarily large and the noise can have infinite variance\.

LetDDbe the domain diameter,GGa bound on the selected mean subgradient, andσp\\sigma^\{p\}a uniform conditional bound on the centralppth noise moment\. For a fixed intervalIIand comparatoruu, write

n\\displaystyle n=\|I\|,\\displaystyle=\|I\|,ΛI\\displaystyle\\Lambda\_\{I\}=1\+PI/D,\\displaystyle=1\+P\_\{I\}/D,ρ\\displaystyle\\rho=\(p−1\)/p,\\displaystyle=\(p\-1\)/p,L\\displaystyle L=log⁡\(2​T\)\.\\displaystyle=\\log\(2T\)\.\(I\.1\)To put static, dynamic, and interval guarantees in the same notation, define

ℬI​\(q\)=G​D​n​q\+σ​D​n1/p​qρ\(q≥1\),CI=G​D​n\.\\mathcal\{B\}\_\{I\}\(q\)=GD\\sqrt\{nq\}\+\\sigma Dn^\{1/p\}q^\{\\rho\}\\quad\(q\\geq 1\),\\qquad C\_\{I\}=GDn\.\(I\.2\)ThusℬI​\(1\)\\mathcal\{B\}\_\{I\}\(1\)is the static scale andℬI​\(ΛI\)\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\)is the dynamic scale on a prescribed window\. The exact\-gradient dynamic rate is attained by Ader\[[16](https://arxiv.org/html/2610.02258#bib.bib16)\]; the heavy\-tailed static rate by AdaGrad\[[10](https://arxiv.org/html/2610.02258#bib.bib10)\]; and the joint full\-horizon rate by[Aggarwal \[1\]](https://arxiv.org/html/2610.02258#bib.bib1)\. The question here is the additional cost of supporting unannounced evaluation intervals under unknown noise statistics\.

#### Main result and its significance\.

Theorem[IV\.4](https://arxiv.org/html/2610.02258#S4.Thmtheorem4)gives

𝔼​RegretI⁡\(u\)≤min⁡\{CI,C⁡\[ℬI​\(ΛI\)\+G​D​n​L\+σ​D​n1/p​L2​ρ\]\}\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\leq\\min\\\!\\left\\\{C\_\{I\},\\ C\\left\[\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\)\+GD\\sqrt\{n\}\\,L\+\\sigma Dn^\{1/p\}L^\{2\\rho\}\\right\]\\right\\\}\.\(I\.3\)Equivalently, the upper bound isO⁡\(ℬI​\(ΛI\+L2\)\)O\(\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\+L^\{2\}\)\), capped byCIC\_\{I\}, with universal constants\. Interval adaptation enters additively in comparator complexity\. In particular,ΛI≥L2\\Lambda\_\{I\}\\geq L^\{2\}suffices to absorb it into the prescribed\-window dynamic rate\. Atp=3/2p=3/2, the noise adaptation factor isL2/3L^\{2/3\}while the mean\-gradient factor isLL\. A constant comparator gives the interval\-static boundO⁡\(ℬI​\(1\+L2\)\)O\(\\mathcal\{B\}\_\{I\}\(1\+L^\{2\}\)\)on the same decisions\. Deterministic partitions give finer comparisons when movement is concentrated in time\.

WithG,σ,pG,\\sigma,psupplied, Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1)replacesL2L^\{2\}byχT​\(n\)=1\+log⁡\(T/n\)\\chi\_\{T\}\(n\)=1\+\\log\(T/n\)\. This preserves the full\-horizon rate becauseχT​\(T\)=1\\chi\_\{T\}\(T\)=1\. Theorem[V\.3](https://arxiv.org/html/2610.02258#S5.Thmtheorem3)and Corollary[V\.4](https://arxiv.org/html/2610.02258#S5.Thmtheorem4)show that the noise costσ​D​n1/p​log⁡\(T/n\)ρ\\sigma Dn^\{1/p\}\\log\(T/n\)^\{\\rho\}is necessary in an explicit regime for learners retaining the optimal full\-horizon static rate\. Together, these results separate the statistical cost of local evaluation from the additional upper\-bound cost of learning the noise statistics\.

#### Technical novelty: expected calibration under finite moments\.

The master uses the bounded multiplierF\(z\)=1\+clip\(z,−1/2,1/2\)F\(z\)=1\+\\operatorname\{clip\}\(z,\-1/2,1/2\), building on multi\-rate multiplicative aggregation\[[6](https://arxiv.org/html/2610.02258#bib.bib6)\]\. Its positive tangent excess and logarithmic defect are both bounded bymin⁡\{2​z2,\|z\|\}\\min\\\{2z^\{2\},\|z\|\\\}\. Their conditional expectations are therefore controlled by4​η2​\(D​G\)2\+4​ηp​\(D​σ\)p4\\eta^\{2\}\(DG\)^\{2\}\+4\\eta^\{p\}\(D\\sigma\)^\{p\}\. The calibration allocates aggregate positive drift into bounded responses\. A fixed\-threshold exponential test bounds the expected maximum penalty excess by a constant times its conditional\-moment bound, including when that bound lies below the initial penalty floor\. This control permits a regret calculation directly in expectation while retaining the finite\-ppterm before optimizing the learning rate\. The raw subgradient continues to update every base trajectory unchanged\.

#### Technical novelty: local extraction with the correct prior cost\.

An observation larger thanT3​bT^\{3\}bsets the next scale to2​‖gt‖/T22\\\|g\_\{t\}\\\|/T^\{2\}, so successive scales increase by more than2​T2T\. Only a constant number of phases contribute to the localized comparison outside an explicitly controlled exceptional event\. A pathwise counter budget bounds each phase’s log\-potential byO⁡\(L2\)O\(L^\{2\}\), including its trigger observation\. Keeping the comparison distribution inside logarithmic extraction yieldsKL\(ν∥π\)\\KL\(\\nu\\\|\\pi\)in the master theorem\. Relative\-entropy comparisons are standard in expert aggregation\[[11](https://arxiv.org/html/2610.02258#bib.bib11)\]; here they are combined with predictable availability, finite\-ppdefects, and expected calibration\. A two\-level polynomial prior then separates the cost of locating a window from the costs of selecting its duration and restart length\. This gives an explicit prior\-sensitive bound as well as the simpler interval rate\.

#### Contributions\.

1. 1\.Interval tracking under unknown heavy\-tailed noise\.Algorithm[1](https://arxiv.org/html/2610.02258#algorithm1)and Theorem[IV\.4](https://arxiv.org/html/2610.02258#S4.Thmtheorem4)establish \([I\.3](https://arxiv.org/html/2610.02258#S1.E3)\) with one shared gradient andO⁡\(log⁡T\)O\(\\log T\)projections per round\. Corollaries[IV\.5](https://arxiv.org/html/2610.02258#S4.Thmtheorem5)and[IV\.6](https://arxiv.org/html/2610.02258#S4.Thmtheorem6)give static and deterministic\-partition comparisons\. Table[I](https://arxiv.org/html/2610.02258#S2.T1)places the results alongside the closest full\-horizon and interval guarantees\.
2. 2\.A prior\-sensitive sleeping\-master theorem\.Theorem[IV\.3](https://arxiv.org/html/2610.02258#S4.Thmtheorem3)compares to fixed distributions over predictable expert predictions and availability, with relative\-entropy complexity and an almost\-sure weighted activity budget\. Lemmas[IV\.1](https://arxiv.org/html/2610.02258#S4.Thmtheorem1)and[IV\.2](https://arxiv.org/html/2610.02258#S4.Thmtheorem2)prove the calibration bounds; Appendix[C](https://arxiv.org/html/2610.02258#A3)supplies the complete local comparison\. Proposition[III\.1](https://arxiv.org/html/2610.02258#S3.Thmtheorem1)quantifies the nonuniform prior used by both algorithms\.
3. 3\.Upper and lower bounds for the statistical interval cost\.Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1)gives the supplied\-statistics guarantee with cost1\+log⁡\(T/n\)1\+\\log\(T/n\)and an explicit refinement retaining the prior\. Theorem[V\.3](https://arxiv.org/html/2610.02258#S5.Thmtheorem3)and Corollary[V\.4](https://arxiv.org/html/2610.02258#S5.Thmtheorem4)establish the corresponding logarithmic noise obstruction under a full\-horizon performance requirement\.

## IIRelated Work

#### Static and dynamic regret\.

The moving\-comparator projection analysis originates with[Zinkevich \[19\]](https://arxiv.org/html/2610.02258#bib.bib19), and AdaGrad adapts stepsizes to observed gradient energy\[[5](https://arxiv.org/html/2610.02258#bib.bib5)\]\. Ader achieves the optimal exact\-gradient path\-length dependence through adaptive aggregation and common linear surrogates\[[16](https://arxiv.org/html/2610.02258#bib.bib16)\]\. Under heavy\-tailed feedback,[Liu \[10\]](https://arxiv.org/html/2610.02258#bib.bib10)obtains the optimal static expected rate with classical algorithms, including parameter\-free AdaGrad\.[Aggarwal \[1\]](https://arxiv.org/html/2610.02258#bib.bib1)establishes the joint full\-horizon dynamic rate, its parameter adaptation, and the matching polynomial benchmark\. We use its restarted\-expert inequality at the point where it applies, and give the additional window\-alignment calculation in Appendix[A](https://arxiv.org/html/2610.02258#A1)\. The present local master uses conditional noise moments; the full\-horizon energy argument needs only marginal moments\.

#### Interval and strongly adaptive regret\.

Adaptive regret and strongly adaptive learning provide comparisons on all subintervals\[[7](https://arxiv.org/html/2610.02258#bib.bib7),[3](https://arxiv.org/html/2610.02258#bib.bib3)\]\. Geometric covers and sleeping aggregation reduce these objectives to local expert comparisons\[[9](https://arxiv.org/html/2610.02258#bib.bib9)\]\. Dynamic and interval objectives have already been combined by[Cutkosky \[2\]](https://arxiv.org/html/2610.02258#bib.bib2)and[Zhang et al\. \[17\]](https://arxiv.org/html/2610.02258#bib.bib17)\. In particular, the latter’s AOA algorithm gives the exact\-gradient specializationO⁡\(ℬI​\(ΛI\+L\)\)O\(\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\+L\)\)in Table[I](https://arxiv.org/html/2610.02258#S2.T1)\. Appendix[A\-C](https://arxiv.org/html/2610.02258#A1.SS3)gives the linear\-surrogate normalization used to express that result with the sameG,D,PIG,D,P\_\{I\}notation\. Our results extend local comparisons to unknown conditional finite\-ppnoise, separating the mean\-gradient and noise powers and identifying a statistical interval cost when the parameters are supplied\.

[Xie et al\. \[15\]](https://arxiv.org/html/2610.02258#bib.bib15)give gradient\-variation and small\-loss interval guarantees, including dynamic comparators and adaptation to unknown Lipschitz and smoothness constants\. Its problem\-dependent analysis assumes smooth nonnegative losses, uses exact first\-order information and function values in its scheduling, and retains maximum observed input scales in its adaptive terms\. These results refine local environmental variation\. Our guarantee instead quantifies comparator movement and central noise moments under gradient\-only feedback, including infinite\-variance noise\.

#### Heavy tails and adaptive aggregation\.

Finite\-moment stochastic convex optimization is studied by[Vural et al\. \[14\]](https://arxiv.org/html/2610.02258#bib.bib14), while[Zhang and Cutkosky \[18\]](https://arxiv.org/html/2610.02258#bib.bib18)treat comparator\-norm adaptation in high probability\.[Moulin et al\. \[12\]](https://arxiv.org/html/2610.02258#bib.bib12)give optimal adaptive full\-information expert aggregation under finite second moments and show that maximum\-loss terms can dominate a nominally lower\-order contribution\. Its full\-horizon expert guarantee and our finite\-ppsleeping comparisons have different feedback and localization requirements\. This distinction is relevant even atp=2p=2\.

Multi\-rate excess\-loss bounds, relative\-entropy comparisons, and sleeping\-expert reductions are established tools\[[6](https://arxiv.org/html/2610.02258#bib.bib6),[11](https://arxiv.org/html/2610.02258#bib.bib11)\]\. Adaptive mixture and scale analyses appear in[de Rooij et al\. \[4\]](https://arxiv.org/html/2610.02258#bib.bib4),[Orabona and Pál \[13\]](https://arxiv.org/html/2610.02258#bib.bib13)\. Polynomial priors are used in Ader\[[16](https://arxiv.org/html/2610.02258#bib.bib16)\]; we apply them to distances from the longest window and restart scales\. The complete normalization and selected\-cost calculation appear in Proposition[III\.1](https://arxiv.org/html/2610.02258#S3.Thmtheorem1)\. The calibration test uses nonnegative\-supermartingale reasoning\[[8](https://arxiv.org/html/2610.02258#bib.bib8)\]; its expected overshoot and its combination with a constant number of relevant scale phases are proved here\. The lower bound uses a ternary oracle and a null\-versus\-window change of measure, with the full calculation in Section[V](https://arxiv.org/html/2610.02258#S5)\.

TABLE I:Key results and relation to closely related work\. All rows useℬI​\(q\)\\mathcal\{B\}\_\{I\}\(q\)from \([I\.2](https://arxiv.org/html/2610.02258#S1.E2)\); its argument is the total comparator and adaptation complexity\. WriteL=log⁡\(2​T\)L=\\log\(2T\)andχT​\(n\)=1\+log⁡\(T/n\)\\chi\_\{T\}\(n\)=1\+\\log\(T/n\)\. Upper bounds may be capped byG​D​\|I\|GD\|I\|\.The domain, its diameter, and the horizon are available throughout\. “None” means none ofG,σ,pG,\\sigma,p; path length is also unsupplied\. TheOpO\_\{p\}row permits a coefficient depending only onpp; its noise coefficient isO⁡\(1\+log⁡\(p/\(p−1\)\)\)O\(1\+\\log\(p/\(p\-1\)\)\)\. Constants in our upper bounds and the static AdaGrad row are universal overpp\.†The AOA row is its normalized linear\-surrogate specialization, proved in Appendix[A\-C](https://arxiv.org/html/2610.02258#A1.SS3)\. The supplied\-statistics row withΛI=1\\Lambda\_\{I\}=1gives the static specialization\. Corollary[V\.4](https://arxiv.org/html/2610.02258#S5.Thmtheorem4)establishes its logarithmic noise lower bound under the explicit full\-horizon requirement and parameter regime\.

## IIISetup and Information Model

Let𝒳⊂ℝd\\mathcal\{X\}\\subset\\mathbb\{R\}^\{d\}be nonempty, closed, and convex, with Euclidean diameterD∈\(0,∞\)D\\in\(0,\\infty\), and letT≥2T\\geq 2\. Euclidean projection onto𝒳\\mathcal\{X\}is available\. On roundtt, the learner chooses a predictablext∈𝒳x\_\{t\}\\in\\mathcal\{X\}and receives only one stochastic subgradientgtg\_\{t\}at that point\. Letℱ0\\mathcal\{F\}\_\{0\}contain its random seed andℱt=σ⁡\(ℱ0,g1,…,gt\)\\mathcal\{F\}\_\{t\}=\\sigma\(\\mathcal\{F\}\_\{0\},g\_\{1\},\\ldots,g\_\{t\}\)\. The convex lossℓt\\ell\_\{t\}and a measurable selected subgradient map may be fixed in advance or chosen measurably fromℱt−1\\mathcal\{F\}\_\{t\-1\}\. Each loss admits a measurable selected subgradient map whose norm is at mostGGon𝒳\\mathcal\{X\}\. Writevt∈∂ℓt​\(xt\)v\_\{t\}\\in\\partial\\ell\_\{t\}\(x\_\{t\}\)for its value at the played point andϵt=gt−vt\\epsilon\_\{t\}=g\_\{t\}\-v\_\{t\}\. For deterministic but unknownG,σ≥0G,\\sigma\\geq 0andp∈\(1,2\]p\\in\(1,2\], assume almost surely

𝔼⁡\[gt∣ℱt−1\]=vt,‖vt‖≤G,𝔼⁡\[‖ϵt‖p∣ℱt−1\]≤σp\.\\mathbb\{E\}\[g\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=v\_\{t\},\\qquad\\\|v\_\{t\}\\\|\\leq G,\\qquad\\mathbb\{E\}\[\\\|\\epsilon\_\{t\}\\\|^\{p\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq\\sigma^\{p\}\.\(III\.1\)The selected subgradient bound makes each lossGG\-Lipschitz on𝒳\\mathcal\{X\}\. The conditional law may be asymmetric and depend on the past\. Feedback consists of the gradient vector alone\.

For a deterministic intervalI=\[s,e\]I=\[s,e\]and deterministic comparator sequenceut∈𝒳u\_\{t\}\\in\\mathcal\{X\}, define

RegretI⁡\(u\)\\displaystyle\\operatorname\{Regret\}\_\{I\}\(u\)=∑t=se\[ℓt​\(xt\)−ℓt​\(ut\)\],\\displaystyle=\\sum\_\{t=s\}^\{e\}\[\\ell\_\{t\}\(x\_\{t\}\)\-\\ell\_\{t\}\(u\_\{t\}\)\],PI\\displaystyle P\_\{I\}=∑t=s\+1e‖ut−ut−1‖,\\displaystyle=\\sum\_\{t=s\+1\}^\{e\}\\\|u\_\{t\}\-u\_\{t\-1\}\\\|,ΛI\\displaystyle\\Lambda\_\{I\}=1\+PI/D\.\\displaystyle=1\+P\_\{I\}/D\.\(III\.2\)Thus1≤ΛI≤\|I\|1\\leq\\Lambda\_\{I\}\\leq\|I\|\. Conditional unbiasedness and convexity give

𝔼​RegretI​\(u\)\\displaystyle\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)≤𝔼​∑t∈I⟨gt,xt−ut⟩,\\displaystyle\\leq\\mathbb\{E\}\\sum\_\{t\\in I\}\\langle g\_\{t\},x\_\{t\}\-u\_\{t\}\\rangle,RegretI⁡\(u\)\\displaystyle\\operatorname\{Regret\}\_\{I\}\(u\)≤GD\|I\|almost surely\.\\displaystyle\\leq GD\|I\|\\quad\\text\{almost surely\}\.\(III\.3\)Regret differences are bounded in absolute value byG​DGD, and the linearized terms are integrable because𝔼​‖gt‖≤G\+σ\\mathbb\{E\}\\\|g\_\{t\}\\\|\\leq G\+\\sigma\. The comparisons hold separately for every fixedI,uI,uon the same decisions\. The parametersG,σG,\\sigmaare uniform global bounds\. The local guarantee depends on the evaluation interval through its length and comparator movement, rather than an additive realized energy accumulated before its start\.

#### General sleeping comparisons\.

The master theorem is stated for a finite set of recordsi∈ℳi\\in\\mathcal\{M\}with fixed prior massesπi\>0\\pi\_\{i\}\>0,∑iπi=1\\sum\_\{i\}\\pi\_\{i\}=1\. Recordiihas a predictable availabilityαt,i∈\{0,1\}\\alpha\_\{t,i\}\\in\\\{0,1\\\}and a predictable feasible predictionyt,iy\_\{t,i\}when awake\. At least one record is awake on every round\. For the comparison toii, a deterministic integerni∈\[1,T\]n\_\{i\}\\in\[1,T\]satisfies

∑t=1Tαt,i≤nialmost surely\.\\sum\_\{t=1\}^\{T\}\\alpha\_\{t,i\}\\leq n\_\{i\}\\quad\\text\{almost surely\}\.\(III\.4\)The budget is used only in the proof\. Availability can depend on observed feedback\. Theorem[IV\.3](https://arxiv.org/html/2610.02258#S4.Thmtheorem3)also permits a fixed distribution over records with an almost\-sure budget on its weighted activity\. This pathwise budget controls its possible dependence on calibration\.

#### Dyadic windows and base trajectories\.

SetN=⌈log2⁡T⌉N=\\lceil\\log\_\{2\}T\\rceil\. For0≤k≤N0\\leq k\\leq N, let𝒟k\\mathcal\{D\}\_\{k\}consist of the labeled supports\[a​2k\+1,\(a\+1\)​2k\]∩\[T\]\[a2^\{k\}\+1,\(a\+1\)2^\{k\}\]\\cap\[T\],0≤a<⌈T/2k⌉0\\leq a<\\lceil T/2^\{k\}\\rceil, and put𝒟=⨆k𝒟k\\mathcal\{D\}=\\bigsqcup\_\{k\}\\mathcal\{D\}\_\{k\}\. Labels distinguish coinciding truncated supports\. Every fixed interval is a disjoint union of at most two untruncated dyadic windows of each size, and for1/2≤γ≤11/2\\leq\\gamma\\leq 1its maximal dyadic cover obeys

∑J​in the cover\|J\|γ≤7​\|I\|γ\.\\sum\_\{J\\text\{ in the cover\}\}\|J\|^\{\\gamma\}\\leq 7\|I\|^\{\\gamma\}\.\(III\.5\)MaintainN\+1N\+1shared\-gradient AdaGrad trajectories\. Trajectoryjjrestarts at the left endpoints of𝒟j\\mathcal\{D\}\_\{j\}, from a fixedx0∈𝒳x\_\{0\}\\in\\mathcal\{X\}, and within a block starting atssuses

Vt\(j\)=∑r=st‖gr‖2,xt\+1\(j\)=Π𝒳​\(xt\(j\)−D​gt2​Vt\(j\)\)\.V\_\{t\}^\{\(j\)\}=\\sum\_\{r=s\}^\{t\}\\\|g\_\{r\}\\\|^\{2\},\\qquad x\_\{t\+1\}^\{\(j\)\}=\\Pi\_\{\\mathcal\{X\}\}\\\!\\left\(x\_\{t\}^\{\(j\)\}\-\\frac\{Dg\_\{t\}\}\{\\sqrt\{2V\_\{t\}^\{\(j\)\}\}\}\\right\)\.\(III\.6\)A zero energy leaves the point unchanged\. Every trajectory receives the same linear surrogatex↦⟨gt,x⟩x\\mapsto\\langle g\_\{t\},x\\rangle; the oracle is queried only atxtx\_\{t\}\.

For the interval algorithm, use recordsi=\(j,J\)i=\(j,J\)withJ∈𝒟kJ\\in\\mathcal\{D\}\_\{k\}and0≤j≤k0\\leq j\\leq k\. Setmk=⌈T/2k⌉m\_\{k\}=\\lceil T/2^\{k\}\\rceiland

αt,\(j,J\)\\displaystyle\\alpha\_\{t,\(j,J\)\}=𝟏\{t∈J\},yt,\(j,J\)=xt\(j\),\\displaystyle=\\mathbf\{1\}\\\{t\\in J\\\},\\qquad y\_\{t,\(j,J\)\}=x\_\{t\}^\{\(j\)\},τk\\displaystyle\\tau\_\{k\}=N\+2N\+1​1\(N−k\+1\)​\(N−k\+2\),\\displaystyle=\\frac\{N\+2\}\{N\+1\}\\frac\{1\}\{\(N\-k\+1\)\(N\-k\+2\)\},ζj\|k\\displaystyle\\zeta\_\{j\\mid k\}=k\+2k\+1​1\(k−j\+1\)​\(k−j\+2\),\\displaystyle=\\frac\{k\+2\}\{k\+1\}\\frac\{1\}\{\(k\-j\+1\)\(k\-j\+2\)\},π\(j,J\)\\displaystyle\\pi\_\{\(j,J\)\}=τk​ζj\|kmk\.\\displaystyle=\\frac\{\\tau\_\{k\}\\zeta\_\{j\\mid k\}\}\{m\_\{k\}\}\.\(III\.7\)The prior favors long windows and, within a window scale, long restart lengths\. Locations are uniform within each scale\. Its three factors keep these selection costs separate\. Both the parameter\-free and supplied\-statistics algorithms use this same prior\.

###### Proposition III\.1\(Normalization and selected prior cost\)\.

The masses in \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\) sum to one, andπ\(N,\[T\]\)≥1/4\\pi\_\{\(N,\[T\]\)\}\\geq 1/4\. For an untruncatedJ∈𝒟kJ\\in\\mathcal\{D\}\_\{k\}of lengthnJ=2kn\_\{J\}=2^\{k\}andj∗=⌊log2⁡\(nJ/ΛJ\)⌋j^\{\*\}=\\lfloor\\log\_\{2\}\(n\_\{J\}/\\Lambda\_\{J\}\)\\rfloor,

1\+log⁡\(1/π\(j∗,J\)\)≤cT​\(nJ,ΛJ\),1\+\\log\(1/\\pi\_\{\(j^\{\*\},J\)\}\)\\leq c\_\{T\}\(n\_\{J\},\\Lambda\_\{J\}\),\(III\.8\)where, for1≤n≤T1\\leq n\\leq Tandλ≥1\\lambda\\geq 1,

cT​\(n,λ\)=\\displaystyle c\_\{T\}\(n,\\lambda\)=\{\}1\+log⁡2\+log⁡\(T/n\)\\displaystyle 1\+\\log 2\+\\log\(T/n\)\+2​log⁡\(3\+log2⁡\(T/n\)\)\\displaystyle\+2\\log\\bigl\(3\+\\log\_\{2\}\(T/n\)\\bigr\)\+2​log⁡\(3\+log2⁡λ\)\.\\displaystyle\+2\\log\\bigl\(3\+\\log\_\{2\}\\lambda\\bigr\)\.\(III\.9\)All records satisfylog⁡\(1/πi\)=O⁡\(L\)\\log\(1/\\pi\_\{i\}\)=O\(L\)\.

###### Proof\.

For every integerm≥0m\\geq 0,∑r=0m\[\(r\+1\)​\(r\+2\)\]−1=\(m\+1\)/\(m\+2\)\\sum\_\{r=0\}^\{m\}\[\(r\+1\)\(r\+2\)\]^\{\-1\}=\(m\+1\)/\(m\+2\)\. This normalizesτ\\tauand eachζ⋅\|k\\zeta\_\{\\cdot\\mid k\}\. There aremkm\_\{k\}windows at scalekk, proving normalization ofπ\\pi\. The top\-scale and top\-restart masses are each at least1/21/2, whilemN=1m\_\{N\}=1, proving the root bound\.

For an untruncated window, putr=N−k<1\+log2⁡\(T/nJ\)r=N\-k<1\+\\log\_\{2\}\(T/n\_\{J\}\)andd=k−j∗=⌈log2⁡ΛJ⌉≤1\+log2⁡ΛJd=k\-j^\{\*\}=\\lceil\\log\_\{2\}\\Lambda\_\{J\}\\rceil\\leq 1\+\\log\_\{2\}\\Lambda\_\{J\}\. Sincemk≤2​T/nJm\_\{k\}\\leq 2T/n\_\{J\}and the normalizing factors inτ,ζ\\tau,\\zetaexceed one,

1\+log⁡\(1/π\(j∗,J\)\)≤1\+log⁡\(2​T/nJ\)\+2​log⁡\(r\+2\)\+2​log⁡\(d\+2\),1\+\\log\(1/\\pi\_\{\(j^\{\*\},J\)\}\)\\leq 1\+\\log\(2T/n\_\{J\}\)\\\\ \{\}\+2\\log\(r\+2\)\+2\\log\(d\+2\),which proves \([III\.8](https://arxiv.org/html/2610.02258#S3.E8)\)\. For every labeled record, including truncated supports,mk≤Tm\_\{k\}\\leq T,r,d≤Nr,d\\leq N, solog⁡\(1/πi\)≤log⁡T\+4​log⁡\(N\+2\)=O⁡\(L\)\\log\(1/\\pi\_\{i\}\)\\leq\\log T\+4\\log\(N\+2\)=O\(L\)\. ∎

The leading location cost islog⁡\(T/n\)\\log\(T/n\); scale and restart selection add iterated logarithms\. To see why location has a different role, considerKKdisjoint candidate windows and sum all record masses assigned to each\. At least one window receives mass at most1/K1/K, giving a prior cost at leastlog⁡K\\log Kfor that window\. This elementary allocation fact explains the location term\. The statistical lower bound in Section[V](https://arxiv.org/html/2610.02258#S5)separately establishes its effect on regret\.

###### Proposition III\.2\(Aligned base comparison\)\.

For a fixedJ∈𝒟J\\in\\mathcal\{D\}, choosej∗=⌊log2⁡\(\|J\|/ΛJ\)⌋j^\{\*\}=\\lfloor\\log\_\{2\}\(\|J\|/\\Lambda\_\{J\}\)\\rfloor\. Then

𝔼​∑t∈J⟨gt,xt\(j∗\)−ut⟩≤3​\[G​D​\|J\|​ΛJ\+σ​D​\|J\|1/p​ΛJρ\]\.\\mathbb\{E\}\\sum\_\{t\\in J\}\\langle g\_\{t\},x\_\{t\}^\{\(j^\{\*\}\)\}\-u\_\{t\}\\rangle\\leq 3\\left\[GD\\sqrt\{\|J\|\\Lambda\_\{J\}\}\+\\sigma D\|J\|^\{1/p\}\\Lambda\_\{J\}^\{\\rho\}\\right\]\.\(III\.10\)

This applies the restarted\-AdaGrad inequality of[Aggarwal \[1, Lemma 4\.3\]](https://arxiv.org/html/2610.02258#bib.bib1)to an aligned window\. Appendix[A](https://arxiv.org/html/2610.02258#A1)gives the complete alignment and moment calculation, including the constant three, and proves \([III\.5](https://arxiv.org/html/2610.02258#S3.E5)\)\.

## IVAlgorithm and Interval\-Dynamic Guarantees

### IV\-AThe sleeping master

The master below applies to the general records in Section[III](https://arxiv.org/html/2610.02258#S3); \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\) gives the interval instantiation\. Set

Q\\displaystyle Q=⌈8​log2⁡\(2​T\)⌉,\\displaystyle=\\lceil 8\\log\_\{2\}\(2T\)\\rceil,δ\\displaystyle\\delta=T−6,\\displaystyle=T^\{\-6\},κ\\displaystyle\\kappa=8,\\displaystyle=8,qi,l\\displaystyle q\_\{i,l\}=πi/\(Q\+1\),\\displaystyle=\\pi\_\{i\}/\(Q\+1\),0≤l≤Q\.\\displaystyle 0\\leq l\\leq Q\.\(IV\.1\)A positive observation scalebbdefines ratesηl=2−l/\(8​D​b\)\\eta\_\{l\}=2^\{\-l\}/\(8Db\)\. Pair\-rate wealthsW⁡\(i,l\)W\(i,l\)start at one, and the conceptual potential isΦ=∑i,lqi,l​W​\(i,l\)\\Phi=\\sum\_\{i,l\}q\_\{i,l\}W\(i,l\)\. Ratellhas a penalty guessal=δa\_\{l\}=\\deltaand countersl=0s\_\{l\}=0\. Sleeping wealths remain unchanged; in the interval implementation unborn wealths are one and expired contributions are frozen\.

WriteΦ−\\Phi^\{\-\}for the pre\-round potential\. For awake records set

ut,i,l\\displaystyle u\_\{t,i,l\}=qi,l​W​\(i,l\)Φ−​\(1\+2​al\),\\displaystyle=\\frac\{q\_\{i,l\}W\(i,l\)\}\{\\Phi^\{\-\}\(1\+2a\_\{l\}\)\},At,l\\displaystyle A\_\{t,l\}=∑i​awakeut,i,l,\\displaystyle=\\sum\_\{i\\text\{ awake\}\}u\_\{t,i,l\},xt\\displaystyle x\_\{t\}=∑i,l​awakeut,i,l​ηl​yt,i∑i,l​awakeut,i,l​ηl\.\\displaystyle=\\frac\{\\sum\_\{i,l\\text\{ awake\}\}u\_\{t,i,l\}\\eta\_\{l\}y\_\{t,i\}\}\{\\sum\_\{i,l\\text\{ awake\}\}u\_\{t,i,l\}\\eta\_\{l\}\}\.\(IV\.2\)After observinggtg\_\{t\}, putrt,i=⟨gt,xt−yt,i⟩r\_\{t,i\}=\\langle g\_\{t\},x\_\{t\}\-y\_\{t,i\}\\rangle,zt,i,l=ηl​rt,iz\_\{t,i,l\}=\\eta\_\{l\}r\_\{t,i\}, and update awake wealths by

W\+​\(i,l\)\\displaystyle W^\{\+\}\(i,l\)=W⁡\(i,l\)​F⁡\(zt,i,l\)1\+2​al,\\displaystyle=W\(i,l\)\\frac\{F\(z\_\{t,i,l\}\)\}\{1\+2a\_\{l\}\},F⁡\(z\)\\displaystyle F\(z\)=1\+clip\(z,−1/2,1/2\)\.\\displaystyle=1\+\\operatorname\{clip\}\(z,\-1/2,1/2\)\.\(IV\.3\)Let𝔥⁡\(z\)=\(F⁡\(z\)−1−z\)\+\\mathfrak\{h\}\(z\)=\(F\(z\)\-1\-z\)\_\{\+\}and form, using pre\-round guesses and exposures,

dt,l\\displaystyle d\_\{t,l\}=∑i​awakeut,i,l​𝔥​\(zt,i,l\),\\displaystyle=\\sum\_\{i\\text\{ awake\}\}u\_\{t,i,l\}\\mathfrak\{h\}\(z\_\{t,i,l\}\),dt\\displaystyle d\_\{t\}=∑ldt,l,\\displaystyle=\\sum\_\{l\}d\_\{t,l\},Γt\\displaystyle\\Gamma\_\{t\}=∑l2​al​At,l,\\displaystyle=\\sum\_\{l\}2a\_\{l\}A\_\{t,l\},Ct\\displaystyle C\_\{t\}=Φ\+/Φ−−1\+Γt,\\displaystyle=\\Phi^\{\+\}/\\Phi^\{\-\}\-1\+\\Gamma\_\{t\},\(IV\.4\)Zt,l\\displaystyle Z\_\{t,l\}=\(Ct\)\+dt,l/dt\(dt\>0\),\\displaystyle=\(C\_\{t\}\)\_\{\+\}d\_\{t,l\}/d\_\{t\}\\quad\(d\_\{t\}\>0\),Zt,l\\displaystyle Z\_\{t,l\}=0\(dt=0\)\.\\displaystyle=0\\quad\(d\_\{t\}=0\)\.Updatesl←sl\+Zt,l−2​al​At,ls\_\{l\}\\leftarrow s\_\{l\}\+Z\_\{t,l\}\-2a\_\{l\}A\_\{t,l\}\. Ifsl\>κs\_\{l\}\>\\kappa, doubleala\_\{l\}and reset that counter to zero\. Wealths retain their values during a counter reset\.

The scale changes only after completing the round’s wealth and counter updates:

‖gt‖\>T3​b⟹b\\displaystyle\\\|g\_\{t\}\\\|\>T^\{3\}b\\quad\\Longrightarrow\\quad b←2​‖gt‖/T2,\\displaystyle\\leftarrow 2\\\|g\_\{t\}\\\|/T^\{2\},W\\displaystyle W←1,Φ←1,al←δ,sl←0\.\\displaystyle\\leftarrow 1,\\quad\\Phi\\leftarrow 1,\\quad a\_\{l\}\\leftarrow\\delta,\\quad s\_\{l\}\\leftarrow 0\.\(IV\.5\)Initiallyb=0b=0\. Until the first nonzero observation, play the prior mixture of awake predictions and skip wealth and counter updates; that observation initializesbbthrough \([IV\.5](https://arxiv.org/html/2610.02258#S4.Ex7)\)\. A phase has constant positive scale and includes its final trigger round\.

Algorithm 1Parameter\-free sleeping master with expected calibrationInput:

T≥2T\\geq 2,

𝒳\\mathcal\{X\},

DD, positive prior

π\\pi, predictable awake predictions

1Set \([IV\.1](https://arxiv.org/html/2610.02258#S4.Ex1)\),

b=0b=0,

W=1W=1,

Φ=1\\Phi=1,

al=δa\_\{l\}=\\delta,

sl=0s\_\{l\}=0
2for*t=1,…,Tt=1,\\ldots,T*do

3Obtain the awake predictions; in \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\), restart the scheduled AdaGrad trajectories

4if*b=0b=0*then

5Play the prior mixture of awake predictions; observe

gtg\_\{t\}
6else

7Set

ηl=2−l/\(8​D​b\)\\eta\_\{l\}=2^\{\-l\}/\(8Db\)and compute \([IV\.2](https://arxiv.org/html/2610.02258#S4.Ex2)\) using pre\-round quantities

8Play

xtx\_\{t\}, observe

gtg\_\{t\}, and form all awake excesses

rt,ir\_\{t,i\}
9Compute the updated wealths and potential from \([IV\.3](https://arxiv.org/html/2610.02258#S4.Ex4)\)

10Form

Zt,lZ\_\{t,l\}and every

Yt,l=Zt,l−2​al​At,lY\_\{t,l\}=Z\_\{t,l\}\-2a\_\{l\}A\_\{t,l\}using \([IV\.4](https://arxiv.org/html/2610.02258#S4.E4)\) and old guesses

11Store the updated wealths and potential

12for*l=0,…,Ql=0,\\ldots,Q*do

13Set

sl←sl\+Yt,ls\_\{l\}\\leftarrow s\_\{l\}\+Y\_\{t,l\}
14if*sl\>8s\_\{l\}\>8*then

15Set

al←2​ala\_\{l\}\\leftarrow 2a\_\{l\}and

sl←0s\_\{l\}\\leftarrow 0
16In the interval instantiation, update every base trajectory with the raw

gtg\_\{t\}using \([III\.6](https://arxiv.org/html/2610.02258#S3.E6)\)

17if*‖gt‖\>T3​b\\\|g\_\{t\}\\\|\>T^\{3\}b*then

18Apply the scale change and master reset in \([IV\.5](https://arxiv.org/html/2610.02258#S4.Ex7)\)

Only the scalar wealth score is truncated\. Every AdaGrad trajectory receives the raw gradient\. The first\-order comparison remains untruncated, and the logarithmic defect below accounts for the score modification\. Scale changes leave the base trajectories and their deterministic restarts untouched\. Positive rescaling of all observed gradients leaves the decisions unchanged:bbrescales, the productsηl​rt,i\\eta\_\{l\}r\_\{t,i\}do not, and the normalized base updates are invariant\.

In \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\), there are at most\(N\+1\)​\(N\+2\)/2\(N\+1\)\(N\+2\)/2awake pairs\. The implementation uses one oracle query,O⁡\(log⁡T\)O\(\\log T\)projections, andO⁡\(d​log⁡T\+log3⁡T\)O\(d\\log T\+\\log^\{3\}T\)arithmetic and memory per round, excluding projection cost\. Unborn mass, frozen expired contributions, and phase stamps implement the conceptual pool without scanning it at a reset\. General reawakening specialists require storage of their accumulated wealths, rather than the interval\-specific active\-window bound\. These counts concern exact\-real arithmetic\.

### IV\-BCalibration inequalities and the local theorem

SetH=D​GH=DG,S=D​σS=D\\sigma, and𝔡⁡\(z\)=\(z−log⁡F⁡\(z\)\)\+\\mathfrak\{d\}\(z\)=\(z\-\\log F\(z\)\)\_\{\+\}\. The following two elementary score bounds are the basis of the moment analysis:

0\\displaystyle 0≤q⁡\(z\)≤min⁡\{2​z2,\|z\|\},\\displaystyle\\leq q\(z\)\\leq\\min\\\{2z^\{2\},\|z\|\\\},q⁡\(a\+z\)\\displaystyle q\(a\+z\)≤4​a2\+4​\|z\|p,q∈\{𝔥,𝔡\}\.\\displaystyle\\leq 4a^\{2\}\+4\|z\|^\{p\},\\qquad q\\in\\\{\\mathfrak\{h\},\\mathfrak\{d\}\\\}\.\(IV\.6\)Consequently, every predictable rateη\>0\\eta\>0and awake prediction satisfy

𝔼⁡\[q⁡\(η​rt,i\)∣ℱt−1\]≤h⁡\(η\):=4​η2​H2\+4​ηp​Sp\.\\mathbb\{E\}\[q\(\\eta r\_\{t,i\}\)\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq h\(\\eta\):=4\\eta^\{2\}H^\{2\}\+4\\eta^\{p\}S^\{p\}\.\(IV\.7\)Appendix[B](https://arxiv.org/html/2610.02258#A2)proves \([IV\.6](https://arxiv.org/html/2610.02258#S4.Ex8)\) and the allocation identities used next\. Under asymmetric noise, the positive tangent excess can create potential drift\. Calibration accounts for this drift through \([IV\.7](https://arxiv.org/html/2610.02258#S4.E7)\)\.

###### Lemma IV\.1\(Bounded allocation and a pathwise potential budget\)\.

On each positive\-scale round,

0\\displaystyle 0≤Zt,l≤2,\\displaystyle\\leq Z\_\{t,l\}\\leq 2,𝔼⁡\[Zt,l∣ℱt−1\]\\displaystyle\\mathbb\{E\}\[Z\_\{t,l\}\\mid\\mathcal\{F\}\_\{t\-1\}\]≤At,l​h​\(ηl\),\\displaystyle\\leq A\_\{t,l\}h\(\\eta\_\{l\}\),log⁡\(Φ\+/Φ−\)\\displaystyle\\log\(\\Phi^\{\+\}/\\Phi^\{\-\}\)≤∑l\(Zt,l−2​al​At,l\)\.\\displaystyle\\leq\\sum\_\{l\}\(Z\_\{t,l\}\-2a\_\{l\}A\_\{t,l\}\)\.\(IV\.8\)PutBT=⌈9​log2⁡\(2​T\)⌉B\_\{T\}=\\lceil 9\\log\_\{2\}\(2T\)\\rceil\. On every phase, without a probabilistic event, every guess doubles at mostBTB\_\{T\}times and

log⁡Φ≤\(Q\+1\)​\(BT\+1\)​\(κ\+2\)=O⁡\(L2\)\.\\log\\Phi\\leq\(Q\+1\)\(B\_\{T\}\+1\)\(\\kappa\+2\)=O\(L^\{2\}\)\.\(IV\.9\)The bound includes the potential immediately after an unbounded trigger observation and before its reset\.

###### Proof\.

The mixture cancels∑i,lut,i,l​zt,i,l\\sum\_\{i,l\}u\_\{t,i,l\}z\_\{t,i,l\}pathwise\. ThusΦ\+/Φ−=1\+Ct−Γt\\Phi^\{\+\}/\\Phi^\{\-\}=1\+C\_\{t\}\-\\Gamma\_\{t\}and\(Ct\)\+≤dt\(C\_\{t\}\)\_\{\+\}\\leq d\_\{t\}\. BecauseF≤3/2F\\leq 3/2, the potential ratio is at most3/23/2, while0≤Γt≤10\\leq\\Gamma\_\{t\}\\leq 1\. Hence∑lZt,l=\(Ct\)\+<2\\sum\_\{l\}Z\_\{t,l\}=\(C\_\{t\}\)\_\{\+\}<2andZt,l≤dt,lZ\_\{t,l\}\\leq d\_\{t,l\}\. Taking conditional expectations gives the response bound, andlog⁡x≤x−1\\log x\\leq x\-1gives the log increment\.

On a nontrigger round,\|zt,i,l\|≤T3/8\|z\_\{t,i,l\}\|\\leq T^\{3\}/8\. ThereforeZt,l≤dt,l≤\(T3/8\)​At,lZ\_\{t,l\}\\leq d\_\{t,l\}\\leq\(T^\{3\}/8\)A\_\{t,l\}, so the counter increment is nonpositive wheneveral≥T3/16a\_\{l\}\\geq T^\{3\}/16\. A segment beginning with such a guess has counter at most zero until its possible trigger round\. That final round adds at most two, which cannot exceedκ=8\\kappa=8\. It cannot produce another doubling\. Since doubling belowT3/16T^\{3\}/16yields at mostT3/8T^\{3\}/8, andδ<T3/16\\delta<T^\{3\}/16, every guess is at mostT3/8T^\{3\}/8\. Starting fromT−6T^\{\-6\}permits at most9​log2​T9\\log\_\{2\}Tdoublings\.

A completed counter segment ends in\(κ,κ\+2\]\(\\kappa,\\kappa\+2\]; an unfinished segment has counter at mostκ\\kappa, with negative balances retained\. Summing all increments from the phase’s initial potential one gives \([IV\.9](https://arxiv.org/html/2610.02258#S4.E9)\)\. No moment bound is used in this last argument\. ∎

###### Lemma IV\.2\(Expected maximum calibration excess\)\.

Condition on the start of a positive\-scale phase\. Choose a rate index measurably at that start, and writeh=h⁡\(ηl\)h=h\(\\eta\_\{l\}\)\. Letamaxa\_\{\\max\}be its largest guess during the phase, including the final update\. Then

𝔼⁡\[\(amax−δ\)\+∣phase\-start information\]≤4​h\.\\mathbb\{E\}\[\(a\_\{\\max\}\-\\delta\)\_\{\+\}\\mid\\text\{phase\-start information\}\]\\leq 4h\.\(IV\.10\)This remains valid for a phase ended by an observation\-dependent trigger and forh<δh<\\delta\. Ifh=0h=0, the guess remainsδ\\deltaalmost surely\.

###### Proof\.

Consider a counter segment with fixed guessa≥h\>0a\\geq h\>0, starting at zero\. Putr=a/h≥1r=a/h\\geq 1andλ=\(1\+log⁡r\)/2\\lambda=\(1\+\\log r\)/2\. For0≤Z≤20\\leq Z\\leq 2, convexity giveseλ​Z≤1\+\(e2​λ−1\)​Z/2e^\{\\lambda Z\}\\leq 1\+\(e^\{2\\lambda\}\-1\)Z/2\. Predictability ofAA, together with \([IV\.8](https://arxiv.org/html/2610.02258#S4.Ex9)\), yields

𝔼⁡\[eλ⁡\(Z−2​a​A\)∣ℱt−1\]≤exp⁡\{A​a​\[e2−1−log⁡r−12​r\]\}≤1\.\\mathbb\{E\}\[e^\{\\lambda\(Z\-2aA\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\\\ \\leq\\exp\\\!\\left\\\{Aa\\left\[\\frac\{e\}\{2\}\-1\-\\log r\-\\frac\{1\}\{2r\}\\right\]\\right\\\}\\leq 1\.The last bracket is negative atr=1r=1and has negative derivative forr≥1r\\geq 1\. The exponential counter, stopped at the segment end, is a nonnegative supermartingale\. Its conditional crossing probability is therefore at most

e−λ​κ=q0​\(h/a\)4,q0=e−4<1/4\.e^\{\-\\lambda\\kappa\}=q\_\{0\}\(h/a\)^\{4\},\\qquad q\_\{0\}=e^\{\-4\}<1/4\.\(IV\.11\)This is the standard exponential maximal argument, with the parameter chosen to retain the dependence onh/ah/a\.

Ifh≥δh\\geq\\delta, the first dyadic guessa∗≥ha\_\{\*\}\\geq hlies in\[h,2​h\]\[h,2h\]\. Successive crossings at valid guesses have conditional probability at mostq0q\_\{0\}\. ThusPr⁡\(amax≥2k​a∗∣start\)≤q0k\\Pr\(a\_\{\\max\}\\geq 2^\{k\}a\_\{\*\}\\mid\\text\{start\}\)\\leq q\_\{0\}^\{k\}and

𝔼​amax≤a∗​\(1\+q01−2​q0\)<4​h\.\\mathbb\{E\}a\_\{\\max\}\\leq a\_\{\*\}\\left\(1\+\\frac\{q\_\{0\}\}\{1\-2q\_\{0\}\}\\right\)<4h\.If0<h<δ0<h<\\delta, retain the factor\(h/δ\)4\(h/\\delta\)^\{4\}for the first crossing and useq0q\_\{0\}for subsequent ones\. Summing the tail of the dyadic levels gives

𝔼⁡\(amax−δ\)≤δ​q01−2​q0​\(h/δ\)4≤h\.\\mathbb\{E\}\(a\_\{\\max\}\-\\delta\)\\leq\\frac\{\\delta q\_\{0\}\}\{1\-2q\_\{0\}\}\(h/\\delta\)^\{4\}\\leq h\.All expectations here are conditional on the phase start\. Segment starts and ends are stopping times, so the same conditional arguments apply successively\. Whenh=0h=0, nonnegativity and zero conditional expectation forceZ=0Z=0, and no crossing occurs\. ∎

###### Theorem IV\.3\(Prior\-sensitive predictable sleeping aggregation\)\.

Under \([III\.1](https://arxiv.org/html/2610.02258#S3.E1)\), fix a deterministic distributionν\\nuonℳ\\mathcal\{M\}\. Define its predictable activitywt=∑iνi​αt,iw\_\{t\}=\\sum\_\{i\}\\nu\_\{i\}\\alpha\_\{t,i\}and suppose that, for deterministic1≤nν≤T1\\leq n\_\{\\nu\}\\leq T,

∑t=1Twt≤nνalmost surely\.\\sum\_\{t=1\}^\{T\}w\_\{t\}\\leq n\_\{\\nu\}\\quad\\text\{almost surely\}\.\(IV\.12\)Algorithm[1](https://arxiv.org/html/2610.02258#algorithm1)satisfies

𝔼​∑t∑iνi​αt,i​⟨vt,xt−yt,i⟩\\displaystyle\\mathbb\{E\}\\sum\_\{t\}\\sum\_\{i\}\\nu\_\{i\}\\alpha\_\{t,i\}\\langle v\_\{t\},x\_\{t\}\-y\_\{t,i\}\\rangle≤min⁡\{H​nν,C⁡\[H​nν​𝒦ν\+S​nν1/p​𝒦νρ\]\},\\displaystyle\\quad\\leq\\min\\left\\\{Hn\_\{\\nu\},\\ C\\left\[H\\sqrt\{n\_\{\\nu\}\\mathcal\{K\}\_\{\\nu\}\}\+Sn\_\{\\nu\}^\{1/p\}\\mathcal\{K\}\_\{\\nu\}^\{\\rho\}\\right\]\\right\\\},\(IV\.13\)𝒦ν\\displaystyle\\mathcal\{K\}\_\{\\nu\}=1\+KL\(ν∥π\)\+L2,KL\(ν∥π\)=∑i:νi\>0νilogνiπi\.\\displaystyle=1\+\\KL\(\\nu\\\|\\pi\)\+L^\{2\},\\qquad\\KL\(\\nu\\\|\\pi\)=\\sum\_\{i:\\nu\_\{i\}\>0\}\\nu\_\{i\}\\log\\frac\{\\nu\_\{i\}\}\{\\pi\_\{i\}\}\.The constant is universal\. The learner uses none ofG,σ,p,ν,nνG,\\sigma,p,\\nu,n\_\{\\nu\}\. In particular,ν=ei\\nu=e\_\{i\}yields the individual\-record bound withnν=nin\_\{\\nu\}=n\_\{i\}and𝒦i=1\+log⁡\(1/πi\)\+L2\\mathcal\{K\}\_\{i\}=1\+\\log\(1/\\pi\_\{i\}\)\+L^\{2\}\.

The relative\-entropy dependence retains the benefit of substantial prior mass on several useful experts\. For example, letAAbe a fixed set of records sharing supportJJ, and chooseνi=πi/π⁡\(A\)\\nu\_\{i\}=\\pi\_\{i\}/\\pi\(A\)onAA\. Thennν=\|J\|n\_\{\\nu\}=\|J\|andKL\(ν∥π\)=log\(1/π\(A\)\)\\KL\(\\nu\\\|\\pi\)=\\log\(1/\\pi\(A\)\)\. The theorem compares to their prior\-weighted average prediction onJJ\. This is the standard distribution\-comparison interpretation\[[11](https://arxiv.org/html/2610.02258#bib.bib11)\], now under the conditional finite\-ppmodel and expected calibration\.

#### Proof structure\.

Appendix[C](https://arxiv.org/html/2610.02258#A3)gives the full proof\. For positive wealths, the relative\-entropy variational inequality gives

∑iνilogW\(i,l\)≤KL\(ν∥π\)\+log\(Q\+1\)\+logΦ\.\\sum\_\{i\}\\nu\_\{i\}\\log W\(i,l\)\\leq\\KL\(\\nu\\\|\\pi\)\+\\log\(Q\+1\)\+\\log\\Phi\.\(IV\.14\)Keepingν\\nuinside this step preserves its entropy saving\. Averaging individual\-record bounds would instead charge∑iνi​log⁡\(1/πi\)\\sum\_\{i\}\\nu\_\{i\}\\log\(1/\\pi\_\{i\}\)\.

LetMt=maxr≤t⁡‖gr‖M\_\{t\}=\\max\_\{r\\leq t\}\\\|g\_\{r\}\\\|\. The trigger impliesbt≥Mt−1/T3b\_\{t\}\\geq M\_\{t\-1\}/T^\{3\}\. Predictable rounds withbt<G/T4b\_\{t\}<G/T^\{4\}contribute at most2​H\+S​nν1/p2H\+Sn\_\{\\nu\}^\{1/p\}in expectation\. Except on an event of probability at most2​T−32T^\{\-3\}, at most nine larger\-scale phases occur\. A grid rate is selected predictably in each of these phases, withη≤η∗\\eta\\leq\\eta\_\{\*\}and1/η≤2/η∗\+8​D​b1/\\eta\\leq 2/\\eta\_\{\*\}\+8Db, for a deterministic comparison targetη∗\\eta\_\{\*\}\. The potential budget and \([IV\.14](https://arxiv.org/html/2610.02258#S4.E14)\) giveKν=O\(KL\(ν∥π\)\+L2\)K\_\{\\nu\}=O\(\\KL\(\\nu\\\|\\pi\)\+L^\{2\}\)per phase\. Lemma[IV\.2](https://arxiv.org/html/2610.02258#S4.Thmtheorem2)bounds the expected sum of normalized penalty excesses over those phases by3636\.

The weighted activity in \([IV\.12](https://arxiv.org/html/2610.02258#S4.E12)\) controls both the defects and a single martingale sum\. The resulting tradeoff, apart from the explicitly absorbed remainder, is

2​𝒜νη∗\+400​nν​H2​η∗\+400​nν​Sp​η∗p−1,𝒜ν=9​Kν\.\\frac\{2\\mathcal\{A\}\_\{\\nu\}\}\{\\eta\_\{\*\}\}\+400n\_\{\\nu\}H^\{2\}\\eta\_\{\*\}\+400n\_\{\\nu\}S^\{p\}\\eta\_\{\*\}^\{p\-1\},\\qquad\\mathcal\{A\}\_\{\\nu\}=9K\_\{\\nu\}\.\(IV\.15\)Balancing its two moment terms proves \([IV\.13](https://arxiv.org/html/2610.02258#S4.E13)\)\. The target uses the deterministic weighted activity budget, so rate selection remains predictable even when availability depends on the observed history\. TheL2L^\{2\}term comes from the pathwise calibration budget in Lemma[IV\.1](https://arxiv.org/html/2610.02258#S4.Thmtheorem1); the prior cost remains separate in \([IV\.13](https://arxiv.org/html/2610.02258#S4.E13)\)\.

### IV\-CDynamic regret and temporal concentration

###### Theorem IV\.4\(Additive interval adaptation\)\.

Under \([III\.1](https://arxiv.org/html/2610.02258#S3.E1)\), Algorithm[1](https://arxiv.org/html/2610.02258#algorithm1)with \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\) and \([III\.6](https://arxiv.org/html/2610.02258#S3.E6)\) satisfies, for every fixed intervalIIand fixed comparator path,

𝔼​RegretI​\(u\)\\displaystyle\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)≤min⁡\{G​D​n,C⁡\[ℬI​\(ΛI\)\+G​D​n​L\+σ​D​n1/p​L2​ρ\]\},\\displaystyle\\leq\\min\\\{GDn,\\ C\[\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\)\+GD\\sqrt\{n\}\\,L\+\\sigma Dn^\{1/p\}L^\{2\\rho\}\]\\\},\(IV\.16\)𝔼​RegretI​\(u\)\\displaystyle\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)≤min⁡\{G​D​n,C′​\[G​D​n⁡\(ΛI\+L2\)\+σ​D​n1/p​\(ΛI\+L2\)ρ\]\}\.\\displaystyle\\leq\\min\\\!\\left\\\{GDn,\\ C^\{\\prime\}\\\!\\left\[GD\\sqrt\{n\(\\Lambda\_\{I\}\+L^\{2\}\)\}\+\\sigma Dn^\{1/p\}\(\\Lambda\_\{I\}\+L^\{2\}\)^\{\\rho\}\\right\]\\right\\\}\.\(IV\.17\)The constants are universal for1<p≤21<p\\leq 2\. The same decisions support every stated comparison, using none ofG,σ,p,I,PIG,\\sigma,p,I,P\_\{I\}\.

###### Proof\.

Take the deterministic maximal dyadic cover ofII\. For each pieceJJ, select the fixed restart index from Proposition[III\.2](https://arxiv.org/html/2610.02258#S3.Thmtheorem2)\. In \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\),𝒦i=O⁡\(L2\)\\mathcal\{K\}\_\{i\}=O\(L^\{2\}\), uniformly over records\. The shared\-gradient identity, conditional unbiasedness, Theorem[IV\.3](https://arxiv.org/html/2610.02258#S4.Thmtheorem3), and Proposition[III\.2](https://arxiv.org/html/2610.02258#S3.Thmtheorem2)add the master and base comparisons onJJ\.

Writex=PI/Dx=P\_\{I\}/D\. The power sums \([III\.5](https://arxiv.org/html/2610.02258#S3.E5)\),∑JPJ≤PI\\sum\_\{J\}P\_\{J\}\\leq P\_\{I\}, Cauchy–Schwarz, and Hölder yield

∑J\|J\|​ΛJ\\displaystyle\\sum\_\{J\}\\sqrt\{\|J\|\\Lambda\_\{J\}\}≤7​n\+n​x≤8​n​ΛI,\\displaystyle\\leq 7\\sqrt\{n\}\+\\sqrt\{nx\}\\leq 8\\sqrt\{n\\Lambda\_\{I\}\},∑J\|J\|1/p​ΛJρ\\displaystyle\\sum\_\{J\}\|J\|^\{1/p\}\\Lambda\_\{J\}^\{\\rho\}≤7​n1/p\+n1/p​xρ≤8​n1/p​ΛIρ\.\\displaystyle\\leq 7n^\{1/p\}\+n^\{1/p\}x^\{\\rho\}\\leq 8n^\{1/p\}\\Lambda\_\{I\}^\{\\rho\}\.The static master terms sum by \([III\.5](https://arxiv.org/html/2610.02258#S3.E5)\)\. This proves \([IV\.16](https://arxiv.org/html/2610.02258#S4.E16)\); \([III\.3](https://arxiv.org/html/2610.02258#S3.Ex2)\) supplies its ceiling\. For0<a≤10<a\\leq 1,xa\+ya≤2​\(x\+y\)ax^\{a\}\+y^\{a\}\\leq 2\(x\+y\)^\{a\}, giving \([IV\.17](https://arxiv.org/html/2610.02258#S4.E17)\) with a universal constant\. ∎

###### Corollary IV\.5\(Static comparisons on every fixed interval\)\.

For every fixed intervalIIand pointu∈𝒳u\\in\\mathcal\{X\}, the same learner satisfies

𝔼​RegretI⁡\(u\)≤min⁡\{G​D​n,C​ℬI​\(1\+L2\)\}≤C′​\[G​D​n​L\+σ​D​n1/p​L2​ρ\]\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\leq\\min\\\{GDn,\\ C\\mathcal\{B\}\_\{I\}\(1\+L^\{2\}\)\\\}\\leq C^\{\\prime\}\\left\[GD\\sqrt\{n\}\\,L\+\\sigma Dn^\{1/p\}L^\{2\\rho\}\\right\]\.\(IV\.18\)

###### Proof\.

A constant comparator hasPI=0P\_\{I\}=0andΛI=1\\Lambda\_\{I\}=1\. Apply Theorem[IV\.4](https://arxiv.org/html/2610.02258#S4.Thmtheorem4)and useL≥log⁡4\>1L\\geq\\log 4\>1\. ∎

This specialization makes the cost of local evaluation visible without comparator movement\. The full\-horizon heavy\-tailed static scale isℬ\[T\]​\(1\)\\mathcal\{B\}\_\{\[T\]\}\(1\); calibration addsL2L^\{2\}to the interval comparison\. With supplied statistics, Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1)givesℬI​\(1\+χT​\(n\)\)\\mathcal\{B\}\_\{I\}\(1\+\\chi\_\{T\}\(n\)\), recovering the full\-horizon static scale whenn=Tn=T\.

###### Corollary IV\.6\(Deterministic partitions\)\.

LetU⁡\(J\)U\(J\)be the right side of \([IV\.16](https://arxiv.org/html/2610.02258#S4.E16)\), including its own linear ceiling\. For a fixedI,uI,u, the same algorithm satisfies

𝔼​RegretI⁡\(u\)≤min⁡∑J∈𝒬𝒬​a deterministic partition of​I⁡U⁡\(J\)\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\leq\\min\_\{\\mathcal\{Q\}\\text\{ a deterministic partition of \}I\}\\sum\_\{J\\in\\mathcal\{Q\}\}U\(J\)\.\(IV\.19\)

###### Proof\.

For each deterministic partition, add the expected bounds for its pieces\. Their numerical minimum also bounds the same expectation\. The partition selection is outside expectation\. ∎

For example, in the noiseless case with movement confined to an initial episode of lengthmm, followed by a constant comparator, \([IV\.19](https://arxiv.org/html/2610.02258#S4.E19)\) givesO⁡\(G​D​\[m\+n​L\]\)O\(GD\[m\+\\sqrt\{n\}L\]\)\. WithT=nT=n,m≍n2/3m\\asymp n^\{2/3\}, andPI≍D​mP\_\{I\}\\asymp Dm, this isO⁡\(G​D​n2/3\)O\(GDn^\{2/3\}\), whereas the total\-path expression is of orderG​D​n5/6GDn^\{5/6\}\. The comparison concerns the two upper bounds\. Local evaluation retains information about the temporal concentration of movement that is absent from its total path length alone\.

## VThe Statistical Cost of Interval Adaptation

The polynomial fixed\-window benchmark follows from[Aggarwal \[1, Theorem 5\.1\]](https://arxiv.org/html/2610.02258#bib.bib1): for every fixed lengthn≥2n\\geq 2and path budgetPP, every learner has an admissible fixed instance with expected regret at least

120​min⁡\{G​D​n⁡\(1\+P/D\)\+σ​D​n1/p​\(1\+P/D\)ρ,G​D​n\}\.\\frac\{1\}\{20\}\\min\\\!\\left\\\{GD\\sqrt\{n\(1\+P/D\)\}\+\\sigma Dn^\{1/p\}\(1\+P/D\)^\{\\rho\},\\ GDn\\right\\\}\.\(V\.1\)To place it in a longer run, use zero losses and observations outside the window\. The exact\-gradient and rare\-revelation constructions in that theorem satisfy conditional moments; the entering learner state is simply an independent initial seed\. This supplies the polynomial benchmark on every bounded convex domain\. The results below address the additional cost of locating an unannounced evaluation window\.

### V\-AA full\-horizon\-preserving upper bound with supplied statistics

DefineχT​\(n\)=1\+log⁡\(T/n\)\\chi\_\{T\}\(n\)=1\+\\log\(T/n\)\. The supplied\-statistics variant uses the same bounded score and shared\-gradient bases, but replaces calibration by known penalties\. Both learners use the nonuniform prior in \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\)\. Its complete algorithm and proof are in Appendix[D](https://arxiv.org/html/2610.02258#A4)\.

###### Theorem V\.1\(Supplied\-statistics interval guarantee\)\.

WhenG,σ,pG,\\sigma,pare supplied, withG\>0G\>0, there is a single predictable learner satisfying

𝔼​RegretI⁡\(u\)≤min⁡\{G​D​n,C⁡\[G​D​n⁡\(ΛI\+χT​\(n\)\)\+σ​D​n1/p​\(ΛI\+χT​\(n\)\)ρ\]\}\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\leq\\min\\\!\\left\\\{GDn,\\ C\\\!\\left\[GD\\sqrt\{n\(\\Lambda\_\{I\}\+\\chi\_\{T\}\(n\)\)\}\+\\sigma Dn^\{1/p\}\(\\Lambda\_\{I\}\+\\chi\_\{T\}\(n\)\)^\{\\rho\}\\right\]\\right\\\}\(V\.2\)for every fixedI,uI,u\. The separated form has master termsC⁡\[G​D​n​χT​\(n\)\+σ​D​n1/p​χT​\(n\)ρ\]C\[GD\\sqrt\{n\\chi\_\{T\}\(n\)\}\+\\sigma Dn^\{1/p\}\\chi\_\{T\}\(n\)^\{\\rho\}\]in addition toC​ℬI​\(ΛI\)C\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\)\. It uses one gradient query,O⁡\(log⁡T\)O\(\\log T\)projections, andO⁡\(d​log⁡T\+log2⁡T\)O\(d\\log T\+\\log^\{2\}T\)other arithmetic and storage per round\. Neither the evaluation interval nor comparator movement is supplied\. All constants are universal overpp\. More explicitly, withc=cT​\(n,ΛI\)c=c\_\{T\}\(n,\\Lambda\_\{I\}\)from \([III\.9](https://arxiv.org/html/2610.02258#S3.Ex6)\), the same learner satisfies

𝔼​RegretI⁡\(u\)≤min⁡\{G​D​n,C⁡\[ℬI​\(ΛI\)\+G​D​n​c\+σ​D​n1/p​cρ\]\}\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\leq\\min\\\!\\left\\\{GDn,\\ C\\left\[\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\)\+GD\\sqrt\{nc\}\+\\sigma Dn^\{1/p\}c^\{\\rho\}\\right\]\\right\\\}\.\(V\.3\)

The analysis makes the complete sleeping potential a nonnegative supermartingale, so its expected logarithm at a fixed endpoint is nonpositive\. Proposition[III\.1](https://arxiv.org/html/2610.02258#S3.Thmtheorem1)retains one leading location logarithm, with iterated\-logarithmic scale and restart costs\. Formula \([V\.3](https://arxiv.org/html/2610.02258#S5.E3)\) preserves these costs before the simpler bound \([V\.2](https://arxiv.org/html/2610.02258#S5.E2)\) absorbs them intoΛI\+χT​\(n\)\\Lambda\_\{I\}\+\\chi\_\{T\}\(n\)\. The weighted cover preservesχT​\(n\)\\chi\_\{T\}\(n\)rather than replacing it bylog⁡T\\log T\. AtI=\[T\]I=\[T\], \([V\.2](https://arxiv.org/html/2610.02258#S5.E2)\) is the full\-horizon polynomial benchmark with universal constants\. The fully parameter\-free algorithm in Theorem[IV\.4](https://arxiv.org/html/2610.02258#S4.Thmtheorem4)instead pays its displayedL2L^\{2\}cost on that interval\.

###### Corollary V\.2\(Full\-horizon static rate with supplied statistics\)\.

For every fixed pointu∈𝒳u\\in\\mathcal\{X\}, the learner of Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1)satisfies

𝔼​Regret\[T\]⁡\(u\)≤min⁡\{G​D​T,40​ℬ\[T\]​\(1\)\}\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{\[T\]\}\(u\)\\leq\\min\\\{GDT,\\ 40\\mathcal\{B\}\_\{\[T\]\}\(1\)\\\}\.\(V\.4\)

The root record has prior mass at least1/41/4and runs AdaGrad without a restart\. Direct comparison to this record gives the constant in \([V\.4](https://arxiv.org/html/2610.02258#S5.E4)\), uniformly overpp; the full calculation appears in Appendix[D](https://arxiv.org/html/2610.02258#A4)\. This explains the role of favoring long windows even for a static comparator\.

### V\-BA regret–testing tradeoff

The next theorem quantifies the conflict between small regret on a persistent environment and rapid identification of an unannounced exceptional window\. It applies even when all statistical parameters and the collection of candidate windows are known\.

###### Theorem V\.3\(From full\-horizon regret to a hard interval\)\.

LetT=K​nT=Kn, whereK≥2K\\geq 2andn≥1n\\geq 1are integers\. Fixσ\>0\\sigma\>0,p∈\(1,2\]p\\in\(1,2\], andq∈\(0,1\)q\\in\(0,1\), and set

Δ=σ8​qρ≤G,cq=q2​log⁡3\.\\Delta=\\frac\{\\sigma\}\{8\}q^\{\\rho\}\\leq G,\\qquad c\_\{q\}=\\frac\{q\}\{2\}\\log 3\.\(V\.5\)For every learner there is a fixed constant linear\-loss instance satisfying \([III\.1](https://arxiv.org/html/2610.02258#S3.E1)\), with gradient normΔ\\Delta, called the null instance\. Suppose its expected regret to its constant minimizer is at mostBB, where0<B<D​Δ​T0<B<D\\Delta T\. Then one of theKKconsecutive length\-nnwindows is the exceptional window in another admissible fixed instance, and on that window, against its constant minimizer,

𝔼​RegretI⁡\(u\)≥D​Δ​n​\[1−n​cq\+log⁡2log⁡\(D​Δ​T/B\)\]\+\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\geq D\\Delta n\\left\[1\-\\frac\{nc\_\{q\}\+\\log 2\}\{\\log\(D\\Delta T/B\)\}\\right\]\_\{\+\}\.\(V\.6\)Both instances have independent oracle outputs and satisfy the same conditional central\-moment bound\. When the null regret is zero, the exceptional\-window regret isD​Δ​nD\\Delta n\.

###### Proof\.

Geometry and oracle\.Use a diameter direction as in[Aggarwal \[1, Lemma 5\.2\]](https://arxiv.org/html/2610.02258#bib.bib1)\. There exista,b∈𝒳a,b\\in\\mathcal\{X\}with‖b−a‖=D\\\|b\-a\\\|=D\. Putv=\(b−a\)/Dv=\(b\-a\)/D,c=\(a\+b\)/2c=\(a\+b\)/2, andz\(x\)=⟨v,x−c⟩∈\[−D/2,D/2\]z\(x\)=\\langle v,x\-c\\rangle\\in\[\-D/2,D/2\]\. Set

A=σ4​q1/p\.A=\\frac\{\\sigma\}\{4q^\{1/p\}\}\.The scalar lawsP\+P\_\{\+\}andP−P\_\{\-\}put masses\(3​q/4,q/4,1−q\)\(3q/4,q/4,1\-q\)and\(q/4,3​q/4,1−q\)\(q/4,3q/4,1\-q\), respectively, on\(A,−A,0\)\(A,\-A,0\)\. Their means are±Δ\\pm\\Delta\. Moreover,

𝔼​\|Y−𝔼​Y\|p\\displaystyle\\mathbb\{E\}\|Y\-\\mathbb\{E\}Y\|^\{p\}≤2p​𝔼​\|Y\|p=2p​q​Ap\\displaystyle\\leq 2^\{p\}\\mathbb\{E\}\|Y\|^\{p\}=2^\{p\}qA^\{p\}=2−p​σp≤σp,\\displaystyle=2^\{\-p\}\\sigma^\{p\}\\leq\\sigma^\{p\},KL\(P−∥P\+\)\\displaystyle\\KL\(P\_\{\-\}\\\|P\_\{\+\}\)=cq\.\\displaystyle=c\_\{q\}\.Returngt=Yt​vg\_\{t\}=Y\_\{t\}vindependently across rounds and independently of the query point\. The null loss isℓt​\(x\)=Δ​z​\(x\)\\ell\_\{t\}\(x\)=\\Delta z\(x\)and its oracle isP\+P\_\{\+\}\. In the alternative for windowIjI\_\{j\}, use−Δ​z​\(x\)\-\\Delta z\(x\)andP−P\_\{\-\}onIjI\_\{j\}, retaining the null outside\. All losses are fixed, and their selected gradients have normΔ≤G\\Delta\\leq G\.

A window with small null exploration\.Definew⁡\(x\)=z⁡\(x\)/D\+1/2∈\[0,1\]w\(x\)=z\(x\)/D\+1/2\\in\[0,1\]\. The null regret toaaisD​Δ​∑tw⁡\(xt\)D\\Delta\\sum\_\{t\}w\(x\_\{t\}\)\. Thus some deterministic windowIjI\_\{j\}satisfies

αj:=1n​∑t∈Ij𝔼0​w​\(xt\)≤BD​Δ​T=:ε<1\.\\alpha\_\{j\}:=\\frac\{1\}\{n\}\\sum\_\{t\\in I\_\{j\}\}\\mathbb\{E\}\_\{0\}w\(x\_\{t\}\)\\leq\\frac\{B\}\{D\\Delta T\}=:\\varepsilon<1\.The index depends on the learner’s distribution under the fixed null instance, not on a realized transcript\. Choose this index for the alternative, and writeβj=n−1​∑t∈Ij𝔼j​w​\(xt\)\\beta\_\{j\}=n^\{\-1\}\\sum\_\{t\\in I\_\{j\}\}\\mathbb\{E\}\_\{j\}w\(x\_\{t\}\)\.

Information and interval regret\.By the chain rule for relative entropy, the alternative transcript has divergencen​cqnc\_\{q\}from the null transcript: only thennoracle draws inIjI\_\{j\}change their laws\. Adaptive actions and the independent learner seed add no divergence\. Adjoin an independent uniform roundUUinIjI\_\{j\}andV∼Unif⁡\[0,1\]V\\sim\\operatorname\{Unif\}\[0,1\]\. The event\{V≤w\(xU\)\}\\\{V\\leq w\(x\_\{U\}\)\\\}has probabilitiesαj\\alpha\_\{j\}andβj\\beta\_\{j\}under the two laws\. Data processing and the binary\-entropy bound give

n​cq\\displaystyle nc\_\{q\}≥kl\(βj∥αj\)\\displaystyle\\geq\\operatorname\{kl\}\(\\beta\_\{j\}\\\|\\alpha\_\{j\}\)≥βj​log⁡\(1/αj\)−log⁡2\\displaystyle\\geq\\beta\_\{j\}\\log\(1/\\alpha\_\{j\}\)\-\\log 2≥βj​log⁡\(1/ε\)−log⁡2\.\\displaystyle\\geq\\beta\_\{j\}\\log\(1/\\varepsilon\)\-\\log 2\.Ifαj=0\\alpha\_\{j\}=0, absolute continuity forcesβj=0\\beta\_\{j\}=0and the conclusion is immediate\. Otherwise rearrange the display\. The alternative minimizer onIjI\_\{j\}isbb, and its interval regret is exactlyD​Δ​n​\(1−βj\)D\\Delta n\(1\-\\beta\_\{j\}\)\. This proves \([V\.6](https://arxiv.org/html/2610.02258#S5.E6)\), with the positive part justified by nonnegative roundwise regret\. A zero null regret givesαj=0\\alpha\_\{j\}=0on every window and hence the final assertion\. ∎

###### Corollary V\.4\(A necessary moment\-dependent interval price\)\.

FixC0≥1C\_\{0\}\\geq 1,p∈\(1,2\]p\\in\(1,2\], and integersT=K​nT=Knsatisfying

n≥1\+log⁡K,ρ​log⁡K≥4​\[1\+log⁡\(16​C0\)\]\.n\\geq 1\+\\log K,\\qquad\\rho\\log K\\geq 4\\bigl\[1\+\\log\(16C\_\{0\}\)\\bigr\]\.\(V\.7\)Consider any learner, even supplied withG=σ\>0G=\\sigma\>0andpp, whose full\-horizon expected regret to every fixed constant comparator is at mostC0​D​\(G​T\+σ​T1/p\)C\_\{0\}D\(G\\sqrt\{T\}\+\\sigma T^\{1/p\}\)on every admissible instance\. There is an admissible fixed instance and a deterministic length\-nninterval, with a constant comparator on it, such that

𝔼​RegretI⁡\(u\)≥164​σ​D​n1/p​\(log⁡K\)ρ\.\\mathbb\{E\}\\operatorname\{Regret\}\_\{I\}\(u\)\\geq\\frac\{1\}\{64\}\\sigma Dn^\{1/p\}\(\\log K\)^\{\\rho\}\.\(V\.8\)In this regime the supplied\-statistics upper bound \([V\.2](https://arxiv.org/html/2610.02258#S5.E2)\) for a static comparator isO⁡\(σ​D​n1/p​χT​\(n\)ρ\)O\(\\sigma Dn^\{1/p\}\\chi\_\{T\}\(n\)^\{\\rho\}\)\. Thus the noise power of the interval logarithm is sharp under the stated full\-horizon requirement\.

###### Proof\.

Setb0=ρ​log⁡Kb\_\{0\}=\\rho\\log Kandq=b0/\(4​n\)≤1/8q=b\_\{0\}/\(4n\)\\leq 1/8\. The null guarantee is at mostB=2​C0​σ​D​T1/pB=2C\_\{0\}\\sigma DT^\{1/p\}\. With \([V\.5](https://arxiv.org/html/2610.02258#S5.E5)\),

log⁡\(D​Δ​T/B\)\\displaystyle\\log\(D\\Delta T/B\)=ρ​log⁡\(q​T\)−log⁡\(16​C0\)\\displaystyle=\\rho\\log\(qT\)\-\\log\(16C\_\{0\}\)=b0\+ρ​log⁡\(b0/4\)−log⁡\(16​C0\)\\displaystyle=b\_\{0\}\+\\rho\\log\(b\_\{0\}/4\)\-\\log\(16C\_\{0\}\)≥3​b0/4\.\\displaystyle\\geq 3b\_\{0\}/4\.Here \([V\.7](https://arxiv.org/html/2610.02258#S5.E7)\) impliesb0≥8b\_\{0\}\\geq 8andb0≥4​log⁡\(16​C0\)b\_\{0\}\\geq 4\\log\(16C\_\{0\}\)\. In particularB<D​Δ​TB<D\\Delta T\. Alson​cq\+log⁡2≤b0/4\+log⁡2≤3​b0/8nc\_\{q\}\+\\log 2\\leq b\_\{0\}/4\+\\log 2\\leq 3b\_\{0\}/8\. Theorem[V\.3](https://arxiv.org/html/2610.02258#S5.Thmtheorem3)therefore gives at leastD​Δ​n/2D\\Delta n/2, which equals

σ​D16​n1/p​\(log⁡K\)ρ​\(ρ/4\)ρ≥σ​D64​n1/p​\(log⁡K\)ρ\.\\frac\{\\sigma D\}\{16\}\\,n^\{1/p\}\(\\log K\)^\{\\rho\}\(\\rho/4\)^\{\\rho\}\\geq\\frac\{\\sigma D\}\{64\}\\,n^\{1/p\}\(\\log K\)^\{\\rho\}\.The last inequality usesρρ≥1/2\\rho^\{\\rho\}\\geq 1/2and4−ρ≥1/24^\{\-\\rho\}\\geq 1/2for0<ρ≤1/20<\\rho\\leq 1/2\. FinallyχT​\(n\)=1\+log⁡K≤n\\chi\_\{T\}\(n\)=1\+\\log K\\leq n, son​χT​\(n\)≤n1/p​χT​\(n\)ρ\\sqrt\{n\\chi\_\{T\}\(n\)\}\\leq n^\{1/p\}\\chi\_\{T\}\(n\)^\{\\rho\}\. The constant\-comparator upper bound in \([V\.2](https://arxiv.org/html/2610.02258#S5.E2)\), withG=σG=\\sigma, is therefore of the stated order\. Its scale is at most a constant times the linear ceiling in this regime\. ∎

The full\-horizon requirement and the regime \([V\.7](https://arxiv.org/html/2610.02258#S5.E7)\) are part of the lower bound\. The general tradeoff \([V\.6](https://arxiv.org/html/2610.02258#S5.E6)\) records the dependence on the allowed null regret, including the behavior asppapproaches one\. Atp=2p=2the logarithmic noise power is1/21/2; forp<2p<2it isρ<1/2\\rho<1/2\. The gap between the parameter\-freeL2L^\{2\}upper cost and the supplied\-statisticsχT​\(n\)\\chi\_\{T\}\(n\)cost therefore identifies calibration as a further question beyond the established statistical obstruction\.

## VIConclusions

One learner attains heavy\-tailed dynamic regret on every fixed interval with an additivelog2⁡T\\log^\{2\}Tadaptation cost and universal moment constants\. Expected calibration and a local relative\-entropy comparison support predictable sleeping experts, static comparators, and deterministic partitions\. A shared nonuniform prior separates window location, duration, and restart complexity\. With supplied statistics, the cost reduces to1\+log⁡\(T/n\)1\+\\log\(T/n\); a regret–testing argument establishes its logarithmic noise power under a full\-horizon optimality requirement\.

## References

- \[1\]V\. Aggarwal\.Parameter\-free dynamic regret under heavy\-tailed noise\.*arXiv preprint arXiv:2607\.27073*, 2026\.
- \[2\]A\. Cutkosky\.Parameter\-free, dynamic, and strongly\-adaptive online learning\.In*Proceedings of the International Conference on Machine Learning*, 2020\.
- \[3\]A\. Daniely, A\. Gonen, and S\. Shalev\-Shwartz\.Strongly adaptive online learning\.In*Proceedings of the International Conference on Machine Learning*, 2015\.
- \[4\]S\. de Rooij, T\. van Erven, P\. D\. Grünwald, and W\. M\. Koolen\.Follow the leader if you can, Hedge if you must\.*Journal of Machine Learning Research*, 15:1281–1316, 2014\.
- \[5\]J\. Duchi, E\. Hazan, and Y\. Singer\.Adaptive subgradient methods for online learning and stochastic optimization\.*Journal of Machine Learning Research*, 12:2121–2159, 2011\.
- \[6\]P\. Gaillard, G\. Stoltz, and T\. van Erven\.A second\-order bound with excess losses\.In*Proceedings of the Conference on Learning Theory*, 2014\.
- \[7\]E\. Hazan and C\. Seshadhri\.Efficient learning algorithms for changing environments\.In*Proceedings of the International Conference on Machine Learning*, 2009\.
- \[8\]S\. R\. Howard, A\. Ramdas, J\. McAuliffe, and J\. Sekhon\.Time\-uniform Chernoff bounds via nonnegative supermartingales\.*Probability Surveys*, 17:257–317, 2020\.
- \[9\]K\.\-S\. Jun, F\. Orabona, S\. Wright, and R\. Willett\.Improved strongly adaptive online learning using coin betting\.In*Proceedings of the International Conference on Artificial Intelligence and Statistics*, 2017\.
- \[10\]Z\. Liu\.Online convex optimization with heavy tails: Old algorithms, new regrets, and applications\.In*Proceedings of the International Conference on Algorithmic Learning Theory*, 2026\.
- \[11\]H\. Luo and R\. E\. Schapire\.Achieving all with no parameters: AdaNormalHedge\.In*Proceedings of the Conference on Learning Theory*, 2015\.
- \[12\]A\. Moulin, E\. Esposito, and D\. van der Hoeven\.When lower\-order terms dominate: Adaptive expert algorithms for heavy\-tailed losses\.*arXiv preprint arXiv:2506\.01722*, 2025\.
- \[13\]F\. Orabona and D\. Pál\.Scale\-free online learning\.*Theoretical Computer Science*, 716:50–69, 2018\.
- \[14\]N\. M\. Vural, L\. Yu, K\. Balasubramanian, S\. Volgushev, and M\. A\. Erdogdu\.Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance\.In*Proceedings of the Conference on Learning Theory*, 2022\.
- \[15\]Y\.\-F\. Xie, S\. Wang, P\. Zhao, and Z\.\-H\. Zhou\.Online learning with gradient\-variation interval regret\.*arXiv preprint arXiv:2606\.03831*, 2026\.
- \[16\]L\. Zhang, S\. Lu, and Z\.\-H\. Zhou\.Adaptive online learning in dynamic environments\.In*Advances in Neural Information Processing Systems*, 2018\.
- \[17\]L\. Zhang, S\. Lu, and T\. Yang\.Minimizing dynamic regret and adaptive regret simultaneously\.In*Proceedings of the International Conference on Artificial Intelligence and Statistics*, 2020\.
- \[18\]J\. Zhang and A\. Cutkosky\.Parameter\-free regret in high probability with heavy tails\.In*Advances in Neural Information Processing Systems*, 2022\.
- \[19\]M\. Zinkevich\.Online convex programming and generalized infinitesimal gradient ascent\.In*Proceedings of the International Conference on Machine Learning*, 2003\.

## Appendix APreliminaries and the base comparison

### A\-ADyadic decomposition and moment conversion

###### Proof of \([III\.5](https://arxiv.org/html/2610.02258#S3.E5)\)\.

Select the maximal untruncated dyadic intervals contained inII\. Singletons guarantee coverage and nesting guarantees disjointness\. A selected interval has a parent crossing an endpoint ofII; at each scale at most one such selected child is associated with each endpoint\. There are consequently at most two selected intervals of each size\. Putm=⌊log2⁡\|I\|⌋m=\\lfloor\\log\_\{2\}\|I\|\\rfloor\. Forγ≥1/2\\gamma\\geq 1/2,

∑J\|J\|γ\\displaystyle\\sum\_\{J\}\|J\|^\{\\gamma\}≤2​∑k=0m2k​γ≤21−2−γ​\|I\|γ\\displaystyle\\leq 2\\sum\_\{k=0\}^\{m\}2^\{k\\gamma\}\\leq\\frac\{2\}\{1\-2^\{\-\\gamma\}\}\|I\|^\{\\gamma\}≤\(4\+2​2\)​\|I\|γ≤7​\|I\|γ\.\\displaystyle\\leq\(4\+2\\sqrt\{2\}\)\|I\|^\{\\gamma\}\\leq 7\|I\|^\{\\gamma\}\.All selected windows belong to the labeled pool\. Using untruncated windows in this decomposition avoids ambiguity between labels with coinciding truncated supports\. ∎

###### Lemma A\.1\(Predictably selected moments\)\.

Letβt∈\{0,1\}\\beta\_\{t\}\\in\\\{0,1\\\}be predictable and∑t=1Tβt≤n\\sum\_\{t=1\}^\{T\}\\beta\_\{t\}\\leq nalmost surely, for deterministicn≥1n\\geq 1\. Under \([III\.1](https://arxiv.org/html/2610.02258#S3.E1)\),

𝔼​∑tβt​‖gt‖2\\displaystyle\\mathbb\{E\}\\sqrt\{\\sum\_\{t\}\\beta\_\{t\}\\\|g\_\{t\}\\\|^\{2\}\}≤G​n\+σ​n1/p,\\displaystyle\\leq G\\sqrt\{n\}\+\\sigma n^\{1/p\},𝔼maxt:βt=1∥gt∥\\displaystyle\\mathbb\{E\}\\max\_\{t:\\beta\_\{t\}=1\}\\\|g\_\{t\}\\\|≤G\+σ​n1/p\.\\displaystyle\\leq G\+\\sigma n^\{1/p\}\.\(A\.1\)The maximum of an empty set is zero\. In particular, on any fixed setSSone may taken=\|S\|n=\|S\|\.

###### Proof\.

The product\-space triangle inequality and monotonicity of finite\-dimensional scalar norms give, pathwise,

∑tβt​‖gt‖2≤G​n\+\(∑tβt​‖ϵt‖p\)1/p\.\\sqrt\{\\sum\_\{t\}\\beta\_\{t\}\\\|g\_\{t\}\\\|^\{2\}\}\\leq G\\sqrt\{n\}\+\\left\(\\sum\_\{t\}\\beta\_\{t\}\\\|\\epsilon\_\{t\}\\\|^\{p\}\\right\)^\{1/p\}\.Predictability and conditional moments imply𝔼​∑tβt​‖ϵt‖p≤σp​𝔼​∑tβt≤σp​n\\mathbb\{E\}\\sum\_\{t\}\\beta\_\{t\}\\\|\\epsilon\_\{t\}\\\|^\{p\}\\leq\\sigma^\{p\}\\mathbb\{E\}\\sum\_\{t\}\\beta\_\{t\}\\leq\\sigma^\{p\}n\. Jensen’s inequality proves the first claim\. The maximum is bounded byG\+\(∑tβt​‖ϵt‖p\)1/pG\+\(\\sum\_\{t\}\\beta\_\{t\}\\\|\\epsilon\_\{t\}\\\|^\{p\}\)^\{1/p\}, proving the second\. For a fixed set this is the marginal\-moment conversion used by[Liu \[10\]](https://arxiv.org/html/2610.02258#bib.bib10),[Aggarwal \[1\]](https://arxiv.org/html/2610.02258#bib.bib1)\. Predictable selection is the point at which the present general statement uses conditional moments\. ∎

### A\-BProof of Proposition[III\.2](https://arxiv.org/html/2610.02258#S3.Thmtheorem2)

For an actual restart blockB=\[s,e\]B=\[s,e\]or its prefix, the identical deterministic inequality in[Aggarwal \[1, Lemma 4\.3\]](https://arxiv.org/html/2610.02258#bib.bib1)states

∑t∈B⟨gt,xt\(j\)−ut⟩\\displaystyle\\sum\_\{t\\in B\}\\langle g\_\{t\},x\_\{t\}^\{\(j\)\}\-u\_\{t\}\\rangle≤2​\[D​VB\+∑t=s\+1e‖ut−ut−1‖​VB,<t\]\\displaystyle\\quad\\leq\\sqrt\{2\}\\left\[D\\sqrt\{V\_\{B\}\}\+\\sum\_\{t=s\+1\}^\{e\}\\\|u\_\{t\}\-u\_\{t\-1\}\\\|\\sqrt\{V\_\{B,<t\}\}\\right\]≤2​\(D\+PB\)​VB,\\displaystyle\\quad\\leq\\sqrt\{2\}\(D\+P\_\{B\}\)\\sqrt\{V\_\{B\}\},\(A\.2\)whereVB=∑t∈B‖gt‖2V\_\{B\}=\\sum\_\{t\\in B\}\\\|g\_\{t\}\\\|^\{2\}andVB,<t=∑r=st−1‖gr‖2V\_\{B,<t\}=\\sum\_\{r=s\}^\{t\-1\}\\\|g\_\{r\}\\\|^\{2\}\. It applies to arbitrary realized gradient vectors, so unbiasedness at the virtual trajectory is unnecessary\. We refer to that lemma for the identical pathwise proof\. The calculation below adapts its application to a sleeping window\.

FixJ∈𝒟kJ\\in\\mathcal\{D\}\_\{k\},n=\|J\|n=\|J\|, andΛ=ΛJ\\Lambda=\\Lambda\_\{J\}\. The selected restart lengthℓ=2⌊log2⁡\(n/Λ\)⌋\\ell=2^\{\\lfloor\\log\_\{2\}\(n/\\Lambda\)\\rfloor\}hasr=ℓ​Λ/n∈\(1/2,1\]r=\\ell\\Lambda/n\\in\(1/2,1\]\. Sinceℓ≤n≤2k\\ell\\leq n\\leq 2^\{k\}, its dyadic left endpoint aligns withJJ\. Thus the restriction toJJhasK=⌈n/ℓ⌉K=\\lceil n/\\ell\\rceilfresh blocks or prefixes, each of length at mostℓ\\ell\. Truncation atTTpreserves alignment, and∑BPB≤PJ\\sum\_\{B\}P\_\{B\}\\leq P\_\{J\}\. Applying \([A\.2](https://arxiv.org/html/2610.02258#A1.Ex5)\) and Lemma[A\.1](https://arxiv.org/html/2610.02258#A1.Thmtheorem1)separately on these deterministic blocks gives

𝔼​∑t∈J⟨gt,xt\(j∗\)−ut⟩\\displaystyle\\mathbb\{E\}\\sum\_\{t\\in J\}\\langle g\_\{t\},x\_\{t\}^\{\(j^\{\*\}\)\}\-u\_\{t\}\\rangle≤2​\(G​ℓ\+σ​ℓ1/p\)​\(D​K\+PJ\)\\displaystyle\\leq\\sqrt\{2\}\(G\\sqrt\{\\ell\}\+\\sigma\\ell^\{1/p\}\)\(DK\+P\_\{J\}\)≤2​D​\(G​ℓ\+σ​ℓ1/p\)​\(n/ℓ\+Λ\)\.\\displaystyle\\leq\\sqrt\{2\}D\(G\\sqrt\{\\ell\}\+\\sigma\\ell^\{1/p\}\)\(n/\\ell\+\\Lambda\)\.The coefficients relative to the two terms in \([III\.10](https://arxiv.org/html/2610.02258#S3.E10)\) are2​\(1\+r−1\)​r1/2\\sqrt\{2\}\(1\+r^\{\-1\}\)r^\{1/2\}and2​\(1\+r−1\)​r1/p\\sqrt\{2\}\(1\+r^\{\-1\}\)r^\{1/p\}\. Sincer1/p≤rr^\{1/p\}\\leq\\sqrt\{r\}andr\+1/r≤3/2\\sqrt\{r\}\+1/\\sqrt\{r\}\\leq 3/\\sqrt\{2\}on\[1/2,1\]\[1/2,1\], both are at most three\. This proves Proposition[III\.2](https://arxiv.org/html/2610.02258#S3.Thmtheorem2)and checks the additional sleeping\-window alignment explicitly\.

### A\-CExact\-gradient comparison in Table[I](https://arxiv.org/html/2610.02258#S2.T1)

We adapt the normalization of[Zhang et al\. \[17, Theorem 5\]](https://arxiv.org/html/2610.02258#bib.bib17); its regret theorem itself is used by reference\. SupposeG\>0G\>0and exact selected subgradients are available\. Fixx0∈𝒳x\_\{0\}\\in\\mathcal\{X\}, work on the translated and rescaled domainΩ=\(𝒳−x0\)/D\\Omega=\(\\mathcal\{X\}\-x\_\{0\}\)/D, and run AOA on the affine surrogate

ℓ^t​\(z\)=12\+⟨gt,z⟩2​G,z∈Ω\.\\widehat\{\\ell\}\_\{t\}\(z\)=\\frac\{1\}\{2\}\+\\frac\{\\langle g\_\{t\},z\\rangle\}\{2G\},\\qquad z\\in\\Omega\.This domain contains zero and has diameter one\. Since‖z‖≤1\\\|z\\\|\\leq 1and‖gt‖≤G\\\|g\_\{t\}\\\|\\leq G, the surrogate lies in\[0,1\]\[0,1\]and its gradient norm is at most1/21/2\. One exact query at the playedxt=x0\+D​ztx\_\{t\}=x\_\{0\}\+Dz\_\{t\}determines the entire surrogate for all AOA subroutines\. Its pathwise theorem applies to this realized sequence of affine losses\.

The rescaled comparator has path lengthPI/DP\_\{I\}/D\. Extend it constantly beyond the endpoint when using the source’s endpoint convention\. In its Theorem 5, the logarithmic quantityc′​\(s\)c^\{\\prime\}\(s\)isO⁡\(L\)O\(L\)fors≤Ts\\leq T, andlog⁡\(kI\+1\)=O⁡\(L\)\\log\(k\_\{I\}\+1\)=O\(\\sqrt\{L\}\)becausePI/D≤T−1P\_\{I\}/D\\leq T\-1\. Substituting gradient bound1/21/2and diameter one therefore gives

∑t∈I\[ℓ^t​\(zt\)−ℓ^t​\(\(ut−x0\)/D\)\]≤C​n​\[L\+PI/D\+1\]\.\\sum\_\{t\\in I\}\[\\widehat\{\\ell\}\_\{t\}\(z\_\{t\}\)\-\\widehat\{\\ell\}\_\{t\}\(\(u\_\{t\}\-x\_\{0\}\)/D\)\]\\leq C\\sqrt\{n\}\\,\[\\sqrt\{L\}\+\\sqrt\{P\_\{I\}/D\}\+1\]\.For example, the latter logarithmic estimate follows fromkI\+1≤2\+12​log2⁡\(1\+4​T/7\)k\_\{I\}\+1\\leq 2\+\\tfrac\{1\}\{2\}\\log\_\{2\}\(1\+4T/7\)andlog⁡x≤x\\log x\\leq\\sqrt\{x\}forx≥1x\\geq 1\. Multiplying by2​G​D2GDand applying the subgradient inequality yields

RegretI⁡\(u\)≤C′​G​D​n⁡\(ΛI\+L\)=C′​ℬI​\(ΛI\+L\)\|σ=0\.\\operatorname\{Regret\}\_\{I\}\(u\)\\leq C^\{\\prime\}GD\\sqrt\{n\(\\Lambda\_\{I\}\+L\)\}=C^\{\\prime\}\\mathcal\{B\}\_\{I\}\(\\Lambda\_\{I\}\+L\)\\big\|\_\{\\sigma=0\}\.ForG=0G=0the regret is zero\. This supplies the common scaling and the one\-gradient surrogate interpretation used in the table; it is an application of the cited exact\-feedback result\.

## Appendix BScore bounds and allocation identities

### B\-AThe simultaneous tangent and logarithmic bounds

ForF\(z\)=1\+clip\(z,−1/2,1/2\)F\(z\)=1\+\\operatorname\{clip\}\(z,\-1/2,1/2\), the tangent excess equals\(−1/2−z\)\+\(\-1/2\-z\)\_\{\+\}onz<−1/2z<\-1/2and is zero otherwise\. On its support it is at most\|z\|≤2​z2\|z\|\\leq 2z^\{2\}\. For\|z\|≤1/2\|z\|\\leq 1/2, integration oft/\(1\+t\)t/\(1\+t\)gives0≤z−log⁡\(1\+z\)≤z20\\leq z\-\\log\(1\+z\)\\leq z^\{2\}\. Onz≥1/2z\\geq 1/2, the positive logarithmic defect is at mostz≤2​z2z\\leq 2z^\{2\}\. Onz≤−1/2z\\leq\-1/2, it is\(z\+log⁡2\)\+\(z\+\\log 2\)\_\{\+\}, bounded by\|z\|\|z\|and by2​z22z^\{2\}\. This proves the first bound in \([IV\.6](https://arxiv.org/html/2610.02258#S4.Ex8)\) for both defects\.

If\|z\|≤1\|z\|\\leq 1, useq⁡\(a\+z\)≤2​\(a\+z\)2≤4​a2\+4​\|z\|pq\(a\+z\)\\leq 2\(a\+z\)^\{2\}\\leq 4a^\{2\}\+4\|z\|^\{p\}\. If\|z\|\>1\|z\|\>1, useq⁡\(a\+z\)≤\|a\|\+\|z\|≤a2\+1/4\+\|z\|≤4​a2\+4​\|z\|pq\(a\+z\)\\leq\|a\|\+\|z\|\\leq a^\{2\}\+1/4\+\|z\|\\leq 4a^\{2\}\+4\|z\|^\{p\}\. Now write

rt,i=μt,i\+ξt,i,μt,i=⟨vt,xt−yt,i⟩,ξt,i=⟨ϵt,xt−yt,i⟩\.r\_\{t,i\}=\\mu\_\{t,i\}\+\\xi\_\{t,i\},\\quad\\mu\_\{t,i\}=\\langle v\_\{t\},x\_\{t\}\-y\_\{t,i\}\\rangle,\\quad\\xi\_\{t,i\}=\\langle\\epsilon\_\{t\},x\_\{t\}\-y\_\{t,i\}\\rangle\.\(B\.1\)Feasibility gives\|μt,i\|≤H\|\\mu\_\{t,i\}\|\\leq H, while conditional centering and the conditionalppth moment give𝔼⁡\[ξt,i∣ℱt−1\]=0\\mathbb\{E\}\[\\xi\_\{t,i\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=0and𝔼⁡\[\|ξt,i\|p∣ℱt−1\]≤Sp\\mathbb\{E\}\[\|\\xi\_\{t,i\}\|^\{p\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq S^\{p\}\. Substitution into \([IV\.6](https://arxiv.org/html/2610.02258#S4.Ex8)\) proves \([IV\.7](https://arxiv.org/html/2610.02258#S4.E7)\) for every predictable rate\.

The score is related to bounded multiplicative updates, but its expectation need not be at most one for a centered input\. For example,Z=−2Z=\-2with probability1/91/9andZ=1/4Z=1/4otherwise has𝔼​Z=0\\mathbb\{E\}Z=0and𝔼​F​\(Z\)=7/6\\mathbb\{E\}F\(Z\)=7/6\. The calibration responds to this positive drift rather than assuming symmetry or treating truncation as unbiased\.

### B\-BComplete allocation identities

Suppress the time index\. Allui,l,Al,al,ηlu\_\{i,l\},A\_\{l\},a\_\{l\},\\eta\_\{l\}below are pre\-round quantities\. Prediction \([IV\.2](https://arxiv.org/html/2610.02258#S4.Ex2)\) gives

∑i,l​awakeui,l​zi,l=⟨g,x​∑i,lui,l​ηl−∑i,lui,l​ηl​yi⟩=0\.\\sum\_\{i,l\\text\{ awake\}\}u\_\{i,l\}z\_\{i,l\}=\\left\\langle g,x\\sum\_\{i,l\}u\_\{i,l\}\\eta\_\{l\}\-\\sum\_\{i,l\}u\_\{i,l\}\\eta\_\{l\}y\_\{i\}\\right\\rangle=0\.Sleeping wealths do not change, so the potential ratio is

Φ\+Φ−\\displaystyle\\frac\{\\Phi^\{\+\}\}\{\\Phi^\{\-\}\}=1\+∑i,l​awakeui,l​\[F⁡\(zi,l\)−1−2​al\]\\displaystyle=1\+\\sum\_\{i,l\\text\{ awake\}\}u\_\{i,l\}\[F\(z\_\{i,l\}\)\-1\-2a\_\{l\}\]=1\+C−Γ,\\displaystyle=1\+C\-\\Gamma,C\\displaystyle C=∑i,l​awakeui,l​\[F⁡\(zi,l\)−1−zi,l\],\\displaystyle=\\sum\_\{i,l\\text\{ awake\}\}u\_\{i,l\}\[F\(z\_\{i,l\}\)\-1\-z\_\{i,l\}\],Γ\\displaystyle\\Gamma=∑l2​al​Al\.\\displaystyle=\\sum\_\{l\}2a\_\{l\}A\_\{l\}\.Thus thisCCagrees with the quantity computed from the potential in \([IV\.4](https://arxiv.org/html/2610.02258#S4.E4)\)\. SinceF∈\[1/2,3/2\]F\\in\[1/2,3/2\]and all divisors are at least one,0<Φ\+/Φ−≤3/20<\\Phi^\{\+\}/\\Phi^\{\-\}\\leq 3/2\. Also

0≤Γ=∑i,l​awakeqi,l​W​\(i,l\)Φ−​2​al1\+2​al≤1\.0\\leq\\Gamma=\\sum\_\{i,l\\text\{ awake\}\}\\frac\{q\_\{i,l\}W\(i,l\)\}\{\\Phi^\{\-\}\}\\frac\{2a\_\{l\}\}\{1\+2a\_\{l\}\}\\leq 1\.It follows thatC≤3/2C\\leq 3/2, whileC\+≤dC\_\{\+\}\\leq dbecauseddsums the positive parts of the terms definingCC\. Therefored=0d=0impliesC\+=0C\_\{\+\}=0, and the zero convention for allocation is valid\. Further,0≤Zl≤dl0\\leq Z\_\{l\}\\leq d\_\{l\}and∑lZl=C\+≤3/2<2\\sum\_\{l\}Z\_\{l\}=C\_\{\+\}\\leq 3/2<2\. Taking conditional expectations gives𝔼​Zl≤Al​h​\(ηl\)\\mathbb\{E\}Z\_\{l\}\\leq A\_\{l\}h\(\\eta\_\{l\}\)by \([IV\.7](https://arxiv.org/html/2610.02258#S4.E7)\)\. Finally,

log⁡\(Φ\+/Φ−\)≤C−Γ≤C\+−Γ=∑l\(Zl−2​al​Al\)\.\\log\(\\Phi^\{\+\}/\\Phi^\{\-\}\)\\leq C\-\\Gamma\\leq C\_\{\+\}\-\\Gamma=\\sum\_\{l\}\(Z\_\{l\}\-2a\_\{l\}A\_\{l\}\)\.These are all assertions in \([IV\.8](https://arxiv.org/html/2610.02258#S4.Ex9)\)\. The allocation can depend on the current gradient becauseZl≤dlZ\_\{l\}\\leq d\_\{l\}is a pathwise domination by quantities whose coefficients are predictable\.

## Appendix CProof of the general sleeping\-master theorem

Fix a deterministic distributionν\\nuas in Theorem[IV\.3](https://arxiv.org/html/2610.02258#S4.Thmtheorem3), writen=nνn=n\_\{\\nu\}, and define

m0\\displaystyle m\_\{0\}=9,\\displaystyle=9,Kν\\displaystyle K\_\{\\nu\}=1\+KL\(ν∥π\)\+log\(Q\+1\)\\displaystyle=1\+\\KL\(\\nu\\\|\\pi\)\+\\log\(Q\+1\)\+\(Q\+1\)​\(BT\+1\)​\(κ\+2\),\\displaystyle\\quad\+\(Q\+1\)\(B\_\{T\}\+1\)\(\\kappa\+2\),𝒜ν\\displaystyle\\mathcal\{A\}\_\{\\nu\}=m0​Kν\.\\displaystyle=m\_\{0\}K\_\{\\nu\}\.\(C\.1\)ThenKν≤C\[1\+KL\(ν∥π\)\+L2\]K\_\{\\nu\}\\leq C\[1\+\\KL\(\\nu\\\|\\pi\)\+L^\{2\}\]\. Extend sleeping predictions byx0x\_\{0\}and put

wt\\displaystyle w\_\{t\}=∑iνi​αt,i,\\displaystyle=\\sum\_\{i\}\\nu\_\{i\}\\alpha\_\{t,i\},at\\displaystyle a\_\{t\}=∑iνi​αt,i​\(xt−yt,i\),\\displaystyle=\\sum\_\{i\}\\nu\_\{i\}\\alpha\_\{t,i\}\(x\_\{t\}\-y\_\{t,i\}\),‖at‖\\displaystyle\\\|a\_\{t\}\\\|≤D​wt,\\displaystyle\\leq Dw\_\{t\},r¯t\\displaystyle\\bar\{r\}\_\{t\}=⟨gt,at⟩,\\displaystyle=\\langle g\_\{t\},a\_\{t\}\\rangle,μ¯t\\displaystyle\\bar\{\\mu\}\_\{t\}=⟨vt,at⟩,\\displaystyle=\\langle v\_\{t\},a\_\{t\}\\rangle,ξ¯t\\displaystyle\\bar\{\\xi\}\_\{t\}=⟨ϵt,at⟩\.\\displaystyle=\\langle\\epsilon\_\{t\},a\_\{t\}\\rangle\.\(C\.2\)All coefficients are predictable;0≤wt≤10\\leq w\_\{t\}\\leq 1and∑twt≤n\\sum\_\{t\}w\_\{t\}\\leq nalmost surely\. In particular,

\|μ¯t\|\\displaystyle\|\\bar\{\\mu\}\_\{t\}\|≤H​wt,\\displaystyle\\leq Hw\_\{t\},𝔼⁡\[ξ¯t∣ℱt−1\]\\displaystyle\\mathbb\{E\}\[\\bar\{\\xi\}\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=0,\\displaystyle=0,𝔼⁡\[\|ξ¯t\|p∣ℱt−1\]\\displaystyle\\mathbb\{E\}\[\|\\bar\{\\xi\}\_\{t\}\|^\{p\}\\mid\\mathcal\{F\}\_\{t\-1\}\]≤Sp​wtp≤Sp​wt\.\\displaystyle\\leq S^\{p\}w\_\{t\}^\{p\}\\leq S^\{p\}w\_\{t\}\.\(C\.3\)This gives the sure upper boundH​nHnon the true comparison\.

IfG=0G=0, the true comparison is zero\. Ifσ\>G​T\\sigma\>GT, thenH​n≤S​n1/pHn\\leq Sn^\{1/p\}, sincenρ≤Tn^\{\\rho\}\\leq T\. If𝒜ν≥n\\mathcal\{A\}\_\{\\nu\}\\geq n, thenH​n≤H​n​𝒜νHn\\leq H\\sqrt\{n\\mathcal\{A\}\_\{\\nu\}\}\. Each of these cases implies \([IV\.13](https://arxiv.org/html/2610.02258#S4.E13)\)\. For the remaining proof suppose

G\>0,σ≤G​T,1≤𝒜ν<n≤T\.G\>0,\\qquad\\sigma\\leq GT,\\qquad 1\\leq\\mathcal\{A\}\_\{\\nu\}<n\\leq T\.\(C\.4\)
### C\-AThe signed comparison at small scales

Letbtb\_\{t\}be the pre\-round scale andMt=maxr≤t⁡‖gr‖M\_\{t\}=\\max\_\{r\\leq t\}\\\|g\_\{r\}\\\|, withM0=0M\_\{0\}=0\. Induction from \([IV\.5](https://arxiv.org/html/2610.02258#S4.Ex7)\) gives

bt≥Mt−1/T3\.b\_\{t\}\\geq M\_\{t\-1\}/T^\{3\}\.\(C\.5\)For a nontrigger observation,‖gt‖≤T3​bt\\\|g\_\{t\}\\\|\\leq T^\{3\}b\_\{t\}\. At a trigger, the new value2​‖gt‖/T22\\\|g\_\{t\}\\\|/T^\{2\}exceeds the previous scale and‖gt‖/T3\\\|g\_\{t\}\\\|/T^\{3\}\. These two facts prove the induction, including the initial zero scale\.

Ifbt<G/T4b\_\{t\}<G/T^\{4\}, thenMt−1<G/TM\_\{t\-1\}<G/T\. Once such a round observes‖gt‖≥G/T\\\|g\_\{t\}\\\|\\geq G/T, every subsequent round has scale at leastG/T4G/T^\{4\}\. Thus, pathwise,

∑twt∥gt∥𝟏\{bt<G/T4\}≤Gn/T\+maxtwt∥gt∥\.\\sum\_\{t\}w\_\{t\}\\\|g\_\{t\}\\\|\\mathbf\{1\}\\\{b\_\{t\}<G/T^\{4\}\\\}\\leq Gn/T\+\\max\_\{t\}w\_\{t\}\\\|g\_\{t\}\\\|\.The weighted maximum obeys

maxt⁡wt​‖gt‖≤G\+\(∑twt​‖ϵt‖p\)1/p\.\\max\_\{t\}w\_\{t\}\\\|g\_\{t\}\\\|\\leq G\+\\left\(\\sum\_\{t\}w\_\{t\}\\\|\\epsilon\_\{t\}\\\|^\{p\}\\right\)^\{1/p\}\.Indeed,wtp≤wtw\_\{t\}^\{p\}\\leq w\_\{t\}and‖vt‖≤G\\\|v\_\{t\}\\\|\\leq G\. By predictability,𝔼​∑twt​‖ϵt‖p≤σp​𝔼​∑twt≤σp​n\\mathbb\{E\}\\sum\_\{t\}w\_\{t\}\\\|\\epsilon\_\{t\}\\\|^\{p\}\\leq\\sigma^\{p\}\\mathbb\{E\}\\sum\_\{t\}w\_\{t\}\\leq\\sigma^\{p\}n\. Jensen’s inequality gives𝔼​maxt​wt​‖gt‖≤G\+σ​n1/p\\mathbb\{E\}\\max\_\{t\}w\_\{t\}\\\|g\_\{t\}\\\|\\leq G\+\\sigma n^\{1/p\}\. Both the weighted comparison and the small\-scale test are predictable before the oracle draw\. Conditional unbiasedness and‖at‖≤D​wt\\\|a\_\{t\}\\\|\\leq Dw\_\{t\}consequently imply

𝔼∑tμ¯t𝟏\{bt<G/T4\}\\displaystyle\\mathbb\{E\}\\sum\_\{t\}\\bar\{\\mu\}\_\{t\}\\mathbf\{1\}\\\{b\_\{t\}<G/T^\{4\}\\\}=𝔼∑tr¯t𝟏\{bt<G/T4\}\\displaystyle=\\mathbb\{E\}\\sum\_\{t\}\\bar\{r\}\_\{t\}\\mathbf\{1\}\\\{b\_\{t\}<G/T^\{4\}\\\}≤2​H\+S​n1/p\.\\displaystyle\\leq 2H\+Sn^\{1/p\}\.\(C\.6\)The signed comparison is bounded before introducing the exceptional event used below\. This order retains any negative contribution on its complement\.

### C\-BA constant number of relevant phases

A positive\-scale phase begins just after a trigger observation and ends with the next trigger, when one occurs\. Its scale is known before its first observation\. Consider phases whose scale satisfiesb≥G/T4b\\geq G/T^\{4\}\. Each scale increase is by a factor greater than2​T2T, and every positive scale is2​‖gt‖/T22\\\|g\_\{t\}\\\|/T^\{2\}for an earlier trigger observation\.

Lemma[A\.1](https://arxiv.org/html/2610.02258#A1.Thmtheorem1)and \([C\.4](https://arxiv.org/html/2610.02258#A3.E4)\) give

𝔼​MT≤G\+σ​T1/p≤2​G​T2\.\\mathbb\{E\}M\_\{T\}\\leq G\+\\sigma T^\{1/p\}\\leq 2GT^\{2\}\.Define

ℰ=\{MT≤GT5\},Pr\(ℰc\)≤2T−3\.\\mathcal\{E\}=\\\{M\_\{T\}\\leq GT^\{5\}\\\},\\qquad\\Pr\(\\mathcal\{E\}^\{c\}\)\\leq 2T^\{\-3\}\.\(C\.7\)Onℰ\\mathcal\{E\}, every phase under consideration has scale in\[G/T4,2​G​T3\]\[G/T^\{4\},2GT^\{3\}\]\. Growth by more than2​T2Tpermits at mostm0=9m\_\{0\}=9such phases\. On the whole probability space, geometric growth also gives

∑phases with​b≥G/T4b≤4​MT/T2\.\\sum\_\{\\text\{phases with \}b\\geq G/T^\{4\}\}b\\leq 4M\_\{T\}/T^\{2\}\.\(C\.8\)Select the firstm0m\_\{0\}phases withb≥G/T4b\\geq G/T^\{4\}, even on trajectories that contain more\. Membership in a selected phase is predictable\. Onℰ\\mathcal\{E\}, these selected phases include every round outside the small\-scale comparison\.

### C\-CPredictable rate selection and expected penalties

Fix the deterministic proof target

η∗=min\{𝒜ν400​H2​n,\(𝒜ν400​Sp​n\)1/p\},\\eta\_\{\*\}=\\min\\left\\\{\\sqrt\{\\frac\{\\mathcal\{A\}\_\{\\nu\}\}\{400H^\{2\}n\}\},\\quad\\left\(\\frac\{\\mathcal\{A\}\_\{\\nu\}\}\{400S^\{p\}n\}\\right\)^\{1/p\}\\right\\\},\(C\.9\)with the noise entry infinite forS=0S=0\. Both entries are at least1/\(400​H​T2\)1/\(400HT^\{2\}\)under \([C\.4](https://arxiv.org/html/2610.02258#A3.E4)\)\. For a selected phase, its smallest grid rate satisfies

ηQ≤T48​H​\(2​T\)−8=12048​H​T4≤1400​H​T2≤η∗\.\\eta\_\{Q\}\\leq\\frac\{T^\{4\}\}\{8H\}\(2T\)^\{\-8\}=\\frac\{1\}\{2048HT^\{4\}\}\\leq\\frac\{1\}\{400HT^\{2\}\}\\leq\\eta\_\{\*\}\.Choose the largest grid rate at mostη∗\\eta\_\{\*\}; whenη0<η∗\\eta\_\{0\}<\\eta\_\{\*\}chooseη0\\eta\_\{0\}\. The choice is measurable at the phase start, and

0<η≤η∗,1/η≤2/η∗\+8​D​b\.0<\\eta\\leq\\eta\_\{\*\},\\qquad 1/\\eta\\leq 2/\\eta\_\{\*\}\+8Db\.\(C\.10\)
For selected phasehh, apply Lemma[IV\.2](https://arxiv.org/html/2610.02258#S4.Thmtheorem2)to its chosen rate and put

Uh=\(amax,h−δ\)\+/h⁡\(ηh\)U\_\{h\}=\(a\_\{\\max,h\}\-\\delta\)\_\{\+\}/h\(\\eta\_\{h\}\)whenh⁡\(ηh\)\>0h\(\\eta\_\{h\}\)\>0, with value zero ifh⁡\(ηh\)=0h\(\\eta\_\{h\}\)=0or the phase never begins\. Conditional on an existing phase’s start,𝔼​Uh≤4\\mathbb\{E\}U\_\{h\}\\leq 4\. Therefore

R∗:=∑h=1m0Uh,𝔼​R∗≤36,at,lh≤δ\+R∗​h​\(ηh\)R\_\{\*\}:=\\sum\_\{h=1\}^\{m\_\{0\}\}U\_\{h\},\\qquad\\mathbb\{E\}R\_\{\*\}\\leq 36,\\qquad a\_\{t,l\_\{h\}\}\\leq\\delta\+R\_\{\*\}h\(\\eta\_\{h\}\)\(C\.11\)on every selected phase\. The bound applies to the predictably selected rate, and the initial penalty floor remains separate from its random excess\.

### C\-DRelative\-entropy extraction on a phase

Fix a selected phase and its rate indexll\. Every wealth starts at one at the phase reset, andW⁡\(i,l\)W\(i,l\)is updated on exactly the awake rounds of recordii\. WriteWiW\_\{i\}for its value at the phase endpoint before a reset\. The standard relative\-entropy variational inequality follows directly from Jensen’s inequality:

∑iνi​log⁡Wi\\displaystyle\\sum\_\{i\}\\nu\_\{i\}\\log W\_\{i\}=KL\(ν∥π\)\+∑i:νi\>0νilogπi​Wiνi\\displaystyle=\\KL\(\\nu\\\|\\pi\)\+\\sum\_\{i:\\nu\_\{i\}\>0\}\\nu\_\{i\}\\log\\frac\{\\pi\_\{i\}W\_\{i\}\}\{\\nu\_\{i\}\}≤KL\(ν∥π\)\+log∑i:νi\>0πiWi\\displaystyle\\leq\\KL\(\\nu\\\|\\pi\)\+\\log\\sum\_\{i:\\nu\_\{i\}\>0\}\\pi\_\{i\}W\_\{i\}≤KL\(ν∥π\)\+log\(Q\+1\)\+logΦ\.\\displaystyle\\leq\\KL\(\\nu\\\|\\pi\)\+\\log\(Q\+1\)\+\\log\\Phi\.\(C\.12\)The final step usesqi,l=πi/\(Q\+1\)q\_\{i,l\}=\\pi\_\{i\}/\(Q\+1\)and positivity of all wealths\. This is the usual mixture\-comparison step in prior\-sensitive expert aggregation\[[11](https://arxiv.org/html/2610.02258#bib.bib11)\]; the following calculation incorporates the finite\-moment calibration and stopping phases in full\.

Letnh=∑t​in phasewtn\_\{h\}=\\sum\_\{t\\text\{ in phase\}\}w\_\{t\}be the realized weighted activity of this phase\. Since the chosenη\\etais constant over it, the wealth recursion andη​r≤log⁡F⁡\(η​r\)\+𝔡⁡\(η​r\)\\eta r\\leq\\log F\(\\eta r\)\+\\mathfrak\{d\}\(\\eta r\)imply

∑t​in phaser¯t≤\\displaystyle\\sum\_\{t\\text\{ in phase\}\}\\bar\{r\}\_\{t\}\\leq\{\}Kνη\+∑t​in phase∑iνi​αt,i​𝔡⁡\(η​rt,i\)η\\displaystyle\\frac\{K\_\{\\nu\}\}\{\\eta\}\+\\sum\_\{t\\text\{ in phase\}\}\\sum\_\{i\}\\nu\_\{i\}\\alpha\_\{t,i\}\\frac\{\\mathfrak\{d\}\(\\eta r\_\{t,i\}\)\}\{\\eta\}\+8​R∗​nh​H2​η\+8​R∗​nh​Sp​ηp−1\.\\displaystyle\+8R\_\{\*\}n\_\{h\}H^\{2\}\\eta\+8R\_\{\*\}n\_\{h\}S^\{p\}\\eta^\{p\-1\}\.\(C\.13\)To verify the penalty term, \([C\.11](https://arxiv.org/html/2610.02258#A3.E11)\) gives

log⁡\(1\+2​at,l\)≤2​δ\+2​R∗​h​\(η\)=2​δ\+8​R∗​η2​H2\+8​R∗​ηp​Sp\.\\log\(1\+2a\_\{t,l\}\)\\leq 2\\delta\+2R\_\{\*\}h\(\\eta\)=2\\delta\+8R\_\{\*\}\\eta^\{2\}H^\{2\}\+8R\_\{\*\}\\eta^\{p\}S^\{p\}\.Its contribution in the averaged log wealth is multiplied bywtw\_\{t\}\. The added one inKνK\_\{\\nu\}covers2​nh​δ≤2​T−5<12n\_\{h\}\\delta\\leq 2T^\{\-5\}<1, and Lemma[IV\.1](https://arxiv.org/html/2610.02258#S4.Thmtheorem1)bounds the remaining log\-potential in \([C\.12](https://arxiv.org/html/2610.02258#A3.Ex15)\)\. All these inequalities hold pathwise at every possible phase endpoint\. In particular, the argument keeps the comparison distribution inside logarithmic extraction, preserving theKL\(ν∥π\)\\KL\(\\nu\\\|\\pi\)cost\.

### C\-EUnconditional defects, penalties, and the martingale term

Letθt\\theta\_\{t\}indicate membership in one of the firstm0m\_\{0\}selected phases\. This is predictable\. On those phases letηt\\eta\_\{t\}be the chosen rate; set it to one elsewhere\. By \([IV\.7](https://arxiv.org/html/2610.02258#S4.E7)\), predictability, and∑tθt​wt≤n\\sum\_\{t\}\\theta\_\{t\}w\_\{t\}\\leq n,

𝔼​∑tθt​∑iνi​αt,i​𝔡⁡\(ηt​rt,i\)ηt≤4​n​H2​η∗\+4​n​Sp​η∗p−1\.\\mathbb\{E\}\\sum\_\{t\}\\theta\_\{t\}\\sum\_\{i\}\\nu\_\{i\}\\alpha\_\{t,i\}\\frac\{\\mathfrak\{d\}\(\\eta\_\{t\}r\_\{t,i\}\)\}\{\\eta\_\{t\}\}\\leq 4nH^\{2\}\\eta\_\{\*\}\+4nS^\{p\}\\eta\_\{\*\}^\{p\-1\}\.\(C\.14\)Likewise,∑hnh≤n\\sum\_\{h\}n\_\{h\}\\leq npathwise, so \([C\.11](https://arxiv.org/html/2610.02258#A3.E11)\) gives

𝔼⁡\[8​R∗​∑hnh​\(H2​ηh\+Sp​ηhp−1\)\]≤288​n​\(H2​η∗\+Sp​η∗p−1\)\.\\mathbb\{E\}\\left\[8R\_\{\*\}\\sum\_\{h\}n\_\{h\}\(H^\{2\}\\eta\_\{h\}\+S^\{p\}\\eta\_\{h\}^\{p\-1\}\)\\right\]\\leq 288n\(H^\{2\}\\eta\_\{\*\}\+S^\{p\}\\eta\_\{\*\}^\{p\-1\}\)\.\(C\.15\)The almost\-sure activity budget controls the dependence betweenR∗R\_\{\*\}and the random activity counts\.

The single martingale sumM=∑tθt​ξ¯tM=\\sum\_\{t\}\\theta\_\{t\}\\bar\{\\xi\}\_\{t\}obeys

𝔼​\|M\|p≤2​Sp​n,𝔼​\|M\|≤2​S​n1/p\.\\mathbb\{E\}\|M\|^\{p\}\\leq 2S^\{p\}n,\\qquad\\mathbb\{E\}\|M\|\\leq 2Sn^\{1/p\}\.\(C\.16\)Here is a direct finite\-moment proof\. For reala,ba,band1<p≤21<p\\leq 2,

\|a\+b\|p≤\|a\|p\+p​sgn⁡\(a\)​\|a\|p−1​b\+2​\|b\|p\.\|a\+b\|^\{p\}\\leq\|a\|^\{p\}\+p\\operatorname\{sgn\}\(a\)\|a\|^\{p\-1\}b\+2\|b\|^\{p\}\.The derivativep​sgn⁡\(x\)​\|x\|p−1p\\operatorname\{sgn\}\(x\)\|x\|^\{p\-1\}is\(p−1\)\(p\-1\)\-Hölder with coefficientp​22−pp2^\{2\-p\}; integration of its difference proves the displayed inequality\. Repeated conditional expectation cancels the linear term for the martingale increments\. Using \([C\.3](https://arxiv.org/html/2610.02258#A3.Ex7)\) yields

𝔼​\|M\|p≤2​∑t𝔼​\|θt​ξ¯t\|p≤2​Sp​𝔼​∑tθt​wt≤2​Sp​n\.\\mathbb\{E\}\|M\|^\{p\}\\leq 2\\sum\_\{t\}\\mathbb\{E\}\|\\theta\_\{t\}\\bar\{\\xi\}\_\{t\}\|^\{p\}\\leq 2S^\{p\}\\mathbb\{E\}\\sum\_\{t\}\\theta\_\{t\}w\_\{t\}\\leq 2S^\{p\}n\.Hölder’s inequality justifies integrability of the linear term at each induction step\. Jensen gives the second bound in \([C\.16](https://arxiv.org/html/2610.02258#A3.E16)\)\. Aggregating the selected phases before taking the absolute value keeps a single finite\-moment term\.

### C\-FCompletion of Theorem[IV\.3](https://arxiv.org/html/2610.02258#S4.Thmtheorem3)

Onℰ\\mathcal\{E\}, selected phases contain all rounds withbt≥G/T4b\_\{t\}\\geq G/T^\{4\}\. By \([C\.10](https://arxiv.org/html/2610.02258#A3.E10)\) and \([C\.8](https://arxiv.org/html/2610.02258#A3.E8)\), the sum of their first terms in \([C\.13](https://arxiv.org/html/2610.02258#A3.E13)\) is at most

2​𝒜νη∗\+32​D​Kν​MT/T2\.\\frac\{2\\mathcal\{A\}\_\{\\nu\}\}\{\\eta\_\{\*\}\}\+32DK\_\{\\nu\}M\_\{T\}/T^\{2\}\.SubtractingMMconverts their observed comparison to the true comparison, at cost at most\|M\|\|M\|\. All terms on this upper\-bound side are nonnegative, so expectations restricted toℰ\\mathcal\{E\}are bounded by their unconditional expectations in \([C\.14](https://arxiv.org/html/2610.02258#A3.E14)\)–\([C\.16](https://arxiv.org/html/2610.02258#A3.E16)\)\. Onℰc\\mathcal\{E\}^\{c\}, the true comparison over rounds withbt≥G/T4b\_\{t\}\\geq G/T^\{4\}is at mostH​nHn\. Combining these facts with the unconditional signed small\-scale bound \([C\.6](https://arxiv.org/html/2610.02258#A3.Ex11)\) gives, using292≤400292\\leq 400,

𝔼​∑tμ¯t≤\\displaystyle\\mathbb\{E\}\\sum\_\{t\}\\bar\{\\mu\}\_\{t\}\\leq\{\}2​H\+3​S​n1/p\+2​𝒜νη∗\\displaystyle 2H\+3Sn^\{1/p\}\+\\frac\{2\\mathcal\{A\}\_\{\\nu\}\}\{\\eta\_\{\*\}\}\+400​n​H2​η∗\+400​n​Sp​η∗p−1\\displaystyle\+400nH^\{2\}\\eta\_\{\*\}\+400nS^\{p\}\\eta\_\{\*\}^\{p\-1\}\+32​Kν​H\+S​T1/pT2\+2​H​nT3\.\\displaystyle\+32K\_\{\\nu\}\\frac\{H\+ST^\{1/p\}\}\{T^\{2\}\}\+\\frac\{2Hn\}\{T^\{3\}\}\.\(C\.17\)
PutA=𝒜νA=\\mathcal\{A\}\_\{\\nu\}\. The inverse of the minimum in \([C\.9](https://arxiv.org/html/2610.02258#A3.E9)\) is at most the sum of its two inverses\. The three principal terms in \([C\.17](https://arxiv.org/html/2610.02258#A3.E17)\) are therefore bounded by

60​H​n​A\+1200​S​n1/p​Aρ\.60H\\sqrt\{nA\}\+1200Sn^\{1/p\}A^\{\\rho\}\.For the mean term, the two coefficients are2​4002\\sqrt\{400\}and400\\sqrt\{400\}\. For the noise term their sum is3⋅4001/p≤12003\\cdot 400^\{1/p\}\\leq 1200\. These constants are universal overpp\.

Under \([C\.4](https://arxiv.org/html/2610.02258#A3.E4)\),Kν≤TK\_\{\\nu\}\\leq TandT1/p≤TT^\{1/p\}\\leq T\. The residual scale terms are bounded by a universal multiple ofH\+SH\+S, and the two principal terms absorb all remaining terms becausen,A≥1n,A\\geq 1\. FinallyA≤C​𝒦νA\\leq C\\mathcal\{K\}\_\{\\nu\}with a universal constant, andρ≤1/2\\rho\\leq 1/2\. This proves the nontrivial case of \([IV\.13](https://arxiv.org/html/2610.02258#S4.E13)\)\. The sure bound and the initial case split complete the proof for every fixedν\\nu\. Choosing a point mass gives the individual\-record statement\.

## Appendix DThe supplied\-statistics algorithm and proof

### D\-AThe common nonuniform prior and one rate per record

AssumeG\>0G\>0and thatG,σ,pG,\\sigma,pare supplied\. Use the same records, base trajectories, and priorπ\\pias in \([III\.7](https://arxiv.org/html/2610.02258#S3.E7)\)\. Proposition[III\.1](https://arxiv.org/html/2610.02258#S3.Thmtheorem1)gives their normalization and selected\-record cost\. With these statistics supplied, each record uses one deterministic rate and its corresponding moment bound\.

For recordi=\(j,J\)i=\(j,J\)define deterministic quantities

ni\\displaystyle n\_\{i\}=\|J\|,\\displaystyle=\|J\|,ki\\displaystyle k\_\{i\}=1\+log⁡\(1/πi\),\\displaystyle=1\+\\log\(1/\\pi\_\{i\}\),ηi\\displaystyle\\eta\_\{i\}=min\{ki12​H2​ni,\\displaystyle=\\min\\\!\\biggl\\\{\\sqrt\{\\frac\{k\_\{i\}\}\{12H^\{2\}n\_\{i\}\}\},\(ki12​Sp​ni\)1/p\},\\displaystyle\\hskip 54\.06023pt\\left\(\\frac\{k\_\{i\}\}\{12S^\{p\}n\_\{i\}\}\\right\)^\{1/p\}\\biggr\\\},hi\\displaystyle h\_\{i\}=4​ηi2​H2\+4​ηip​Sp\.\\displaystyle=4\\eta\_\{i\}^\{2\}H^\{2\}\+4\\eta\_\{i\}^\{p\}S^\{p\}\.\(D\.1\)where the noise entry is infinite forS=0S=0\. Initialize wealthsWi=1W\_\{i\}=1andΦ=∑iπi​Wi=1\\Phi=\\sum\_\{i\}\\pi\_\{i\}W\_\{i\}=1\. On each round, for awake records use

ut,i\\displaystyle u\_\{t,i\}=πi​WiΦ−​\(1\+2​hi\),\\displaystyle=\\frac\{\\pi\_\{i\}W\_\{i\}\}\{\\Phi^\{\-\}\(1\+2h\_\{i\}\)\},xt\\displaystyle x\_\{t\}=∑i​awakeut,i​ηi​yt,i∑i​awakeut,i​ηi,\\displaystyle=\\frac\{\\sum\_\{i\\text\{ awake\}\}u\_\{t,i\}\\eta\_\{i\}y\_\{t,i\}\}\{\\sum\_\{i\\text\{ awake\}\}u\_\{t,i\}\\eta\_\{i\}\},Wi\+\\displaystyle W\_\{i\}^\{\+\}=Wi​F⁡\(ηi​rt,i\)1\+2​hi\.\\displaystyle=W\_\{i\}\\frac\{F\(\\eta\_\{i\}r\_\{t,i\}\)\}\{1\+2h\_\{i\}\}\.\(D\.2\)All other wealths remain unchanged\. The known penalties remain fixed throughout the run\. Unborn weights are one and expired contributions are frozen\. The base trajectories are still \([III\.6](https://arxiv.org/html/2610.02258#S3.E6)\)\. Each record uses its prescribed support length; the learner maintains all records regardless of which interval is later evaluated\.

There are at most\(N\+1\)​\(N\+2\)/2\(N\+1\)\(N\+2\)/2awake records andN\+1N\+1base trajectories\. Thus the algorithm has the operation and storage counts in Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1), with one shared oracle draw\. All rates and weights are predictable\.

### D\-BExpected logarithmic potential

By the tangent bound and \([IV\.7](https://arxiv.org/html/2610.02258#S4.E7)\),

𝔼⁡\[F⁡\(ηi​rt,i\)∣ℱt−1\]≤1\+ηi​μt,i\+hi\.\\mathbb\{E\}\[F\(\\eta\_\{i\}r\_\{t,i\}\)\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq 1\+\\eta\_\{i\}\\mu\_\{t,i\}\+h\_\{i\}\.The mixture in \([D\.2](https://arxiv.org/html/2610.02258#A4.Ex4)\) cancels∑iut,i​ηi​μt,i\\sum\_\{i\}u\_\{t,i\}\\eta\_\{i\}\\mu\_\{t,i\}\. The complete potential therefore obeys

𝔼⁡\[Φ\+∣ℱt−1\]≤Φ−​\(1−∑i​awakeut,i​hi\)≤Φ−\.\\mathbb\{E\}\[\\Phi^\{\+\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq\\Phi^\{\-\}\\left\(1\-\\sum\_\{i\\text\{ awake\}\}u\_\{t,i\}h\_\{i\}\\right\)\\leq\\Phi^\{\-\}\.\(D\.3\)It is a nonnegative supermartingale starting at one\. Since the finite collection ofhih\_\{i\}is deterministic and finite, andF∈\[1/2,3/2\]F\\in\[1/2,3/2\], the logarithms of all wealths and of the potential are bounded in absolute value by finite deterministic constants over the fixed run\. Consequently Jensen’s inequality is justified at a fixed endpoint:

𝔼​log⁡Φmax⁡J≤log⁡𝔼​Φmax⁡J≤0\.\\mathbb\{E\}\\log\\Phi\_\{\\max J\}\\leq\\log\\mathbb\{E\}\\Phi\_\{\\max J\}\\leq 0\.\(D\.4\)
For recordi=\(j,J\)i=\(j,J\), wealth is one at birth and is updated only onJJ\. Usingηi​r≤log⁡F⁡\(ηi​r\)\+𝔡⁡\(ηi​r\)\\eta\_\{i\}r\\leq\\log F\(\\eta\_\{i\}r\)\+\\mathfrak\{d\}\(\\eta\_\{i\}r\)andπi​Wi≤Φ\\pi\_\{i\}W\_\{i\}\\leq\\Phi, we get

ηi​∑t∈Jrt,i\\displaystyle\\eta\_\{i\}\\sum\_\{t\\in J\}r\_\{t,i\}≤log⁡Φmax⁡J\+log⁡\(1/πi\)\\displaystyle\\leq\\log\\Phi\_\{\\max J\}\+\\log\(1/\\pi\_\{i\}\)\+∑t∈J𝔡\(ηirt,i\)\+nilog\(1\+2hi\)\.\\displaystyle\\quad\+\\sum\_\{t\\in J\}\\mathfrak\{d\}\(\\eta\_\{i\}r\_\{t,i\}\)\+n\_\{i\}\\log\(1\+2h\_\{i\}\)\.Take expectations, apply conditional unbiasedness, \([D\.4](https://arxiv.org/html/2610.02258#A4.E4)\), the expected defect boundhih\_\{i\}, andlog⁡\(1\+2​hi\)≤2​hi\\log\(1\+2h\_\{i\}\)\\leq 2h\_\{i\}\. This yields

𝔼​∑t∈Jμt,i\\displaystyle\\mathbb\{E\}\\sum\_\{t\\in J\}\\mu\_\{t,i\}≤kiηi\+12​ni​H2​ηi\+12​ni​Sp​ηip−1\\displaystyle\\leq\\frac\{k\_\{i\}\}\{\\eta\_\{i\}\}\+12n\_\{i\}H^\{2\}\\eta\_\{i\}\+12n\_\{i\}S^\{p\}\\eta\_\{i\}^\{p\-1\}≤7​H​ni​ki\+24​S​ni1/p​kiρ\.\\displaystyle\\leq 7H\\sqrt\{n\_\{i\}k\_\{i\}\}\+24Sn\_\{i\}^\{1/p\}k\_\{i\}^\{\\rho\}\.For the last step use the two balancing rates in \([D\.1](https://arxiv.org/html/2610.02258#A4.E1)\); the coefficients are at most2​12<72\\sqrt\{12\}<7and2⋅121/p≤242\\cdot 12^\{1/p\}\\leq 24\. This expected\-potential argument applies for everyσ/G≥0\\sigma/G\\geq 0\.

### D\-CSelected prior cost and a weighted cover

For each untruncated pieceJJin the maximal cover ofII, Proposition[III\.1](https://arxiv.org/html/2610.02258#S3.Thmtheorem1)gives

k\(j∗,J\)≤cT​\(\|J\|,ΛJ\)≤C⁡\[χT​\(\|J\|\)\+ΛJ\]\.k\_\{\(j^\{\*\},J\)\}\\leq c\_\{T\}\(\|J\|,\\Lambda\_\{J\}\)\\leq C\[\\chi\_\{T\}\(\|J\|\)\+\\Lambda\_\{J\}\]\.\(D\.5\)For the second inequality, uselog⁡\(3\+z\)≤log⁡3\+z/3\\log\(3\+z\)\\leq\\log 3\+z/3forz≥0z\\geq 0, andlog⁡λ≤λ−1\\log\\lambda\\leq\\lambda\-1forλ≥1\\lambda\\geq 1\. Thus the scale term is bounded by a constant timesχT​\(\|J\|\)\\chi\_\{T\}\(\|J\|\)and the restart term by a constant timesΛJ\\Lambda\_\{J\}\. Taking the powerρ\\rhoafter this addition keeps the constants universal asppapproaches one\.

###### Lemma D\.1\(Weighted geometric cover\)\.

For the maximal dyadic decomposition of an interval of lengthnn, everyγ∈\[1/2,1\]\\gamma\\in\[1/2,1\]anda∈\[0,1/2\]a\\in\[0,1/2\]satisfy

∑J\|J\|γ​χT​\(\|J\|\)a\\displaystyle\\sum\_\{J\}\|J\|^\{\\gamma\}\\chi\_\{T\}\(\|J\|\)^\{a\}≤32​nγ​χT​\(n\)a,\\displaystyle\\leq 32n^\{\\gamma\}\\chi\_\{T\}\(n\)^\{a\},\(D\.6\)∑J\|J\|γ​cT​\(\|J\|,ΛJ\)a\\displaystyle\\sum\_\{J\}\|J\|^\{\\gamma\}c\_\{T\}\(\|J\|,\\Lambda\_\{J\}\)^\{a\}≤32​nγ​cT​\(n,ΛI\)a\.\\displaystyle\\leq 32n^\{\\gamma\}c\_\{T\}\(n,\\Lambda\_\{I\}\)^\{a\}\.\(D\.7\)

###### Proof\.

Putm=⌊log2⁡n⌋m=\\lfloor\\log\_\{2\}n\\rfloor\. At length2m−r2^\{m\-r\}there are at most two pieces, with\|J\|/n≤2−r\|J\|/n\\leq 2^\{\-r\}andlog⁡\(n/\|J\|\)<\(r\+1\)​log⁡2\\log\(n/\|J\|\)<\(r\+1\)\\log 2\. For \([D\.6](https://arxiv.org/html/2610.02258#A4.E6)\),

χT​\(\|J\|\)≤χT​\(n\)\+\(r\+1\)​log⁡2\.\\chi\_\{T\}\(\|J\|\)\\leq\\chi\_\{T\}\(n\)\+\(r\+1\)\\log 2\.For \([D\.7](https://arxiv.org/html/2610.02258#A4.E7)\),ΛJ≤ΛI\\Lambda\_\{J\}\\leq\\Lambda\_\{I\}\. Regarding the location\-dependent part ofcTc\_\{T\}as a function ofx=log⁡\(T/n\)x=\\log\(T/n\), its derivative is

1\+23​log⁡2\+x<2\(x≥0\)\.1\+\\frac\{2\}\{3\\log 2\+x\}<2\\qquad\(x\\geq 0\)\.Monotonicity inλ\\lambdaand integration of this derivative give

cT​\(\|J\|,ΛJ\)\\displaystyle c\_\{T\}\(\|J\|,\\Lambda\_\{J\}\)≤cT​\(n,ΛI\)\+2​log⁡\(n/\|J\|\)\\displaystyle\\leq c\_\{T\}\(n,\\Lambda\_\{I\}\)\+2\\log\(n/\|J\|\)≤cT​\(n,ΛI\)\+2​\(r\+1\)​log⁡2\.\\displaystyle\\leq c\_\{T\}\(n,\\Lambda\_\{I\}\)\+2\(r\+1\)\\log 2\.Both reference complexities are at least one\. After dividing by the corresponding right\-hand scale, the contribution of a piece is at most2−r/21\+2​\(r\+1\)​log⁡2≤2−r/2\(r\+2\)2^\{\-r/2\}\\sqrt\{1\+2\(r\+1\)\\log 2\}\\leq 2^\{\-r/2\}\(r\+2\)\. Summing at most two pieces of each length yields

2∑r≥02−r/2\(r\+2\)=16\+102<32\.2\\sum\_\{r\\geq 0\}2^\{\-r/2\}\(r\+2\)=16\+10\\sqrt\{2\}<32\.This proves both inequalities with the stated universal constant\. ∎

The geometric\-cover argument is the usual reduction of interval comparisons to dyadic pieces\[[3](https://arxiv.org/html/2610.02258#bib.bib3),[9](https://arxiv.org/html/2610.02258#bib.bib9)\], with the prior\-dependent weight retained here\. Combining the individual\-record bound, Proposition[III\.2](https://arxiv.org/html/2610.02258#S3.Thmtheorem2), and \([D\.7](https://arxiv.org/html/2610.02258#A4.E7)\) proves the refined bound \([V\.3](https://arxiv.org/html/2610.02258#S5.E3)\)\. To obtain the separated form in Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1), first use \([D\.5](https://arxiv.org/html/2610.02258#A4.E5)\) on each piece, and then \([D\.6](https://arxiv.org/html/2610.02258#A4.E6)\) with\(γ,a\)=\(1/2,1/2\)\(\\gamma,a\)=\(1/2,1/2\)and\(1/p,ρ\)\(1/p,\\rho\)\. The movement sums are exactly those in the proof of Theorem[IV\.4](https://arxiv.org/html/2610.02258#S4.Thmtheorem4)\. Finallyxa\+ya≤2​\(x\+y\)ax^\{a\}\+y^\{a\}\\leq 2\(x\+y\)^\{a\}gives \([V\.2](https://arxiv.org/html/2610.02258#S5.E2)\)\.

### D\-DProof of Corollary[V\.2](https://arxiv.org/html/2610.02258#S5.Thmtheorem2)

Use the root record\(N,\[T\]\)\(N,\[T\]\)\. Its trajectory has one uninterrupted AdaGrad block, its prior mass is at least1/41/4, and a constant comparator has zero internal movement\. The identical base inequality \([A\.2](https://arxiv.org/html/2610.02258#A1.Ex5)\) and the moment bound give base regret at most2​\(H​T\+S​T1/p\)\\sqrt\{2\}\(H\\sqrt\{T\}\+ST^\{1/p\}\)\. The record comparison above haski≤1\+log⁡4k\_\{i\}\\leq 1\+\\log 4, so the total is at most

\[2\+7​1\+log⁡4\]​H​T\+\[2\+24​\(1\+log⁡4\)ρ\]​S​T1/p\.\\bigl\[\\sqrt\{2\}\+7\\sqrt\{1\+\\log 4\}\\bigr\]H\\sqrt\{T\}\+\\bigl\[\\sqrt\{2\}\+24\(1\+\\log 4\)^\{\\rho\}\\bigr\]ST^\{1/p\}\.Both coefficients are at most4040for0<ρ≤1/20<\\rho\\leq 1/2\. Linearization and the regret ceiling complete the proof\. The same learner and oracle observations support all the interval guarantees in Theorem[V\.1](https://arxiv.org/html/2610.02258#S5.Thmtheorem1)\.