Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning

# Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning
Source: [https://arxiv.org/html/2605.29148](https://arxiv.org/html/2605.29148)
Tommaso Cesari School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada tcesari@uottawa\.caRoberto Colomboni School of Mathematics University of Bristol Bristol, United Kingdom roberto\.colomboni@bristol\.ac\.uk

###### Abstract

We study stochastic decision\-theoretic online learning with full information and event\-level pure differential privacy\. A COLT open problem of\[[6](https://arxiv.org/html/2605.29148#bib.bib9)\]asks to determine the optimal gap\-dependent regret rate for stochastic decision\-theoretic online learning under pure event\-level differential privacy\. ForKKactions, losses in\[0,1\]\[0,1\], and a unique best action separated from the second\-best action by gapΔmin\\Delta\_\{\\min\}, the known lower bound is of orderlog⁡Kmin⁡\{Δmin,ε\},\\frac\{\\log K\}\{\\min\\\{\\Delta\_\{\\min\},\\varepsilon\\\}\},or equivalently, up to universal constants, of order

log⁡KΔmin\+log⁡Kε\.\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\.We give a horizon\-free pure\-DP algorithm and prove the explicit regret bound

RegT≤1000⋅\(log⁡KΔmin\+log⁡Kε\)\\operatorname\{Reg\}\_\{T\}\\leq 1000\\cdot\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\\right\)for every horizonTT\. The numerical constant is not optimized\. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data\-independent random prefix of the previous block\. The random prefix converts block regret into a sum, over all prefix lengths, of softmax selection errors\. A single entropy\-potential argument controls all privacy\-dominated large\-gap actions at costlog⁡K/ε\\log K/\\varepsilon\.

## 1Introduction

Decision\-theoretic online learning\[[3](https://arxiv.org/html/2605.29148#bib.bib5)\]with stochastic full\-information feedback is among the cleanest models where one can study the statistical cost of online decision making\. There areKKactions\. At each round, the learner chooses one action, suffers its loss, and observes the full loss vector\. When the loss vectors are i\.i\.d\. and the best action is separated from the others by a gap, the optimal non\-private gap\-dependent regret isΘ​\(log⁡K/Δmin\)\\Theta\(\\log K/\\Delta\_\{\\min\}\)\[[7](https://arxiv.org/html/2605.29148#bib.bib6),[9](https://arxiv.org/html/2605.29148#bib.bib7)\]\.

The differentially private version is more delicate\.[Huet al\.](https://arxiv.org/html/2605.29148#bib.bib8)\[[5](https://arxiv.org/html/2605.29148#bib.bib8)\]proved a lower bound of order

log⁡Kmin⁡\{Δmin,ε\},\\frac\{\\log K\}\{\\min\\\{\\Delta\_\{\\min\},\\varepsilon\\\}\},which is equivalent up to universal constants tolog⁡K/Δmin\+log⁡K/ε\\log K/\\Delta\_\{\\min\}\+\\log K/\\varepsilon\.[Hu and Mehta](https://arxiv.org/html/2605.29148#bib.bib9)\[[6](https://arxiv.org/html/2605.29148#bib.bib9)\]isolated the remaining question as a COLT open problem: determine the optimal instance\-dependent regret rate under pure event\-level differential privacy\.[Wu and Wang](https://arxiv.org/html/2605.29148#bib.bib10)\[[10](https://arxiv.org/html/2605.29148#bib.bib10)\]recently made substantial progress and partially addressed the open problem by removing the horizon dependence and proving

O​\(log⁡KΔmin\+log2⁡Kε\)O\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log^\{2\}K\}\{\\varepsilon\}\\right\)for the stochastic problem, together with a tightΘ​\(log⁡K/ε\)\\Theta\(\\log K/\\varepsilon\)analysis in a deterministic special case\.

We close the remaining logarithmic gap in the stochastic problem\. Our algorithm is a randomized\-prefix version of private Follow\-The\-Leader\. Time is partitioned into dyadic blocks\. During a block, the learner repeats one action\. At the end of the block, the learner samples a random prefix length from the second half of the block and applies the exponential mechanism to the cumulative losses over that prefix\. The selected action is then used throughout the next block\. Because each event is used only for the private selection of the following block, privacy follows from a direct factorization of the output law\. We give a direct factorization proof rather than relying on parallel composition\.

The proof has two ingredients\. First, randomizing the prefix length removes the dyadic clock from the analysis: the regret over all blocks is bounded by a constant times

∑m≥1𝔼​\[∑j=1KΔj​Pm,j\],\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{K\}\\Delta\_\{j\}P\_\{m,j\}\\right\],wherePm,jP\_\{m,j\}is the random softmax probability of actionjjaftermmi\.i\.d\. samples\. Second, this prefix\-length softmax\-error sum splits into small\-gap and large\-gap terms\. The small\-gap part is controlled by Hoeffding’s inequality and dyadic grouping, givinglog⁡K/Δmin\\log K/\\Delta\_\{\\min\}\. The large\-gap part is controlled without summing over actions separately: a restricted softmax potential telescopes and costs only its initial entropy,log⁡K\\log K, divided by the privacy scale\. This is the step that removes the extra logarithm\.

*Thus, the proof also gives a conceptual explanation for the two terms in the optimal rate\.*The termlog⁡K/Δmin\\log K/\\Delta\_\{\\min\}is the statistical cost of identifying the best action among near\-optimal competitors\. The termlog⁡K/ε\\log K/\\varepsilonis the privacy cost of privately eliminating clearly suboptimal actions: once the gaps are large, concentration is no longer the bottleneck, and the only remaining resource being spent is the initial softmax entropy\.*In this sense, the proof does not merely match the lower bound; it separates the statistical price from the privacy price and shows exactly where each one enters\.*

#### Contributions\.

We give a constructive horizon\-freeε\\varepsilon\-DP algorithm for stochastic DTOL and prove the explicit regret bound

RegT≤1000⋅\(log⁡KΔmin\+log⁡Kε\)\.\\operatorname\{Reg\}\_\{T\}\\leq 1000\\cdot\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\\right\)\.Together with the lower bound of\[[5](https://arxiv.org/html/2605.29148#bib.bib8)\], this resolves the gap\-dependent pure\-DP rate posed by\[[6](https://arxiv.org/html/2605.29148#bib.bib9)\]\. Although the open problem is stated for the usual product\-over\-actions stochastic model, our proof only uses independence across time\. Thus it applies to i\.i\.d\. loss vectors with arbitrary dependence among coordinates within each round; the product\-over\-actions model is a special case\.

## 2Related Work

#### Decision\-theoretic online learning\.

Decision\-theoretic online learning was introduced by[Freund and Schapire](https://arxiv.org/html/2605.29148#bib.bib5)\[[3](https://arxiv.org/html/2605.29148#bib.bib5)\]as a general full\-information online decision model\. In the stochastic regime, Follow\-The\-Leader and exponentially weighted algorithms exhibit gap\-dependent behavior governed by the separation between the best and second\-best actions\. The sharp non\-private rate isΘ​\(log⁡K/Δmin\)\\Theta\(\\log K/\\Delta\_\{\\min\}\); see, for instance, the Follow\-The\-Leader upper bounds of[Kotłowski](https://arxiv.org/html/2605.29148#bib.bib6)\[[7](https://arxiv.org/html/2605.29148#bib.bib6)\]and the optimality results of[Mourtada and Gaïffas](https://arxiv.org/html/2605.29148#bib.bib7)\[[9](https://arxiv.org/html/2605.29148#bib.bib7)\]\. Our result preserves this statistical term and identifies the additional cost forced by pure event\-level differential privacy\.

#### Differential privacy and private selection\.

Differential privacy was introduced by[Dwork](https://arxiv.org/html/2605.29148#bib.bib3)\[[2](https://arxiv.org/html/2605.29148#bib.bib3)\]\. Our algorithm uses the exponential mechanism of[McSherry and Talwar](https://arxiv.org/html/2605.29148#bib.bib4)\[[8](https://arxiv.org/html/2605.29148#bib.bib4)\]to select the next action after each block, by sampling from a softmax distribution over cumulative losses\. In contrast with standard one\-shot private selection, the online setting requires the entire released action prefix to be private\. Our block construction is designed so that each event affects only one private selection\. The played actions inside the following block are deterministic post\-processing of that selection\.

#### Private stochastic online learning\.

[Huet al\.](https://arxiv.org/html/2605.29148#bib.bib8)\[[5](https://arxiv.org/html/2605.29148#bib.bib8)\]studied the differentially private stochastic online\-learning setting most relevant here, including the full\-information stochastic DTOL problem\. For full\-information stochastic DTOL, their lower bound is of order

log⁡Kmin⁡\{Δmin,ε\}\.\\frac\{\\log K\}\{\\min\\\{\\Delta\_\{\\min\},\\varepsilon\\\}\}\.This is equivalent up to universal constants tolog⁡K/Δmin\+log⁡K/ε\\log K/\\Delta\_\{\\min\}\+\\log K/\\varepsilon\. Their upper bound matches the statistical term but can pay an additionallog⁡T\\log Tfactor in the privacy term\.[Hu and Mehta](https://arxiv.org/html/2605.29148#bib.bib9)\[[6](https://arxiv.org/html/2605.29148#bib.bib9)\]then formulated the remaining gap as a COLT open problem: determine the optimal gap\-dependent regret rate for stochastic DTOL under pure differential privacy\.

#### Partial progress on the open problem\.

[Wu and Wang](https://arxiv.org/html/2605.29148#bib.bib10)\[[10](https://arxiv.org/html/2605.29148#bib.bib10)\]partially addressed the open problem\. They removed the horizon dependence in the stochastic upper bound and obtained

O​\(log⁡KΔmin\+log2⁡Kε\),O\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log^\{2\}K\}\{\\varepsilon\}\\right\),and they proved the tightΘ​\(log⁡K/ε\)\\Theta\(\\log K/\\varepsilon\)rate in a deterministic special case\. Their stochastic analysis still pays an additionallog⁡K\\log Kin the privacy term\. At a technical level, their proof uses Bernoulli resampling and a monotonicity property, followed by a summation over actions that leaves the extra logarithm\.

#### This work\.

The present algorithm remains in the pure\-DP, stochastic, full\-information DTOL setting of\[[6](https://arxiv.org/html/2605.29148#bib.bib9),[10](https://arxiv.org/html/2605.29148#bib.bib10)\]\. The new ingredient is a data\-independent random prefix in each dyadic block\. This randomization converts block regret into a prefix\-length sum of softmax selection errors\. For large\-gap actions, the sum is controlled directly by a single softmax potential, whose initial value is at mostlog⁡K\\log K\. This removes the remaining logarithmic factor and yields the matching privacy termlog⁡K/ε\\log K/\\varepsilon\.

## 3Model

Fix an integerK≥2K\\geq 2and write\[K\]=\{1,…,K\}\[K\]=\\\{1,\\ldots,K\\\}\. All random variables are defined on one probability space\(Ω,ℱ,ℙ\)\(\\Omega,\\mathcal\{F\},\\mathbb\{P\}\)\. The loss process is a sequence\(Xt\)t≥1\(X\_\{t\}\)\_\{t\\geq 1\}of i\.i\.d\. random variables with values in\[0,1\]K\[0,1\]^\{K\}\. We write

Xt=\(Xt,1,…,Xt,K\)\.X\_\{t\}=\(X\_\{t,1\},\\ldots,X\_\{t,K\}\)\.The coordinates ofXtX\_\{t\}may be dependent\. Only independence across different times is used\.

At roundtt, the learner chooses an actionIt∈\[K\]I\_\{t\}\\in\[K\]before observingXtX\_\{t\}, suffers lossXt,ItX\_\{t,I\_\{t\}\}, and then observes the whole vectorXtX\_\{t\}\. The actionItI\_\{t\}is therefore measurable with respect to the learner’s internal randomization and the past loss vectorsX1,…,Xt−1X\_\{1\},\\ldots,X\_\{t\-1\}\. The full\-information assumption is important here: the future observations do not depend on which action was played\.

Let

μj=𝔼​\[X1,j\],j∈\[K\]\.\\mu\_\{j\}=\\mathbb\{E\}\[X\_\{1,j\}\],\\qquad j\\in\[K\]\.After relabeling actions, assume

μ1<μ2≤⋯≤μK\.\\mu\_\{1\}<\\mu\_\{2\}\\leq\\cdots\\leq\\mu\_\{K\}\.Define the pointwise expected\-loss gaps

Δ1=0,Δj=μj−μ1\(j∈\{2,…,K\}\),\\Delta\_\{1\}=0,\\qquad\\Delta\_\{j\}=\\mu\_\{j\}\-\\mu\_\{1\}\\quad\(j\\in\\\{2,\\ldots,K\\\}\),and define

Δmin=Δ2\.\\Delta\_\{\\min\}=\\Delta\_\{2\}\.Since losses belong to\[0,1\]\[0,1\], one has0<Δmin≤10<\\Delta\_\{\\min\}\\leq 1and0≤Δj≤10\\leq\\Delta\_\{j\}\\leq 1for alljj\.

The expected pseudoregret up to horizonTTis

RegT=𝔼​\[∑t=1T\(Xt,It−Xt,1\)\]=∑t=1T𝔼​\[ΔIt\]\.\\operatorname\{Reg\}\_\{T\}=\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\bigl\(X\_\{t,I\_\{t\}\}\-X\_\{t,1\}\\bigr\)\\right\]=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\Delta\_\{I\_\{t\}\}\]\.
###### Definition 1\(Event\-level pure differential privacy\)\.

Fixt≥1t\\geq 1\. Two deterministic prefixesx1:t,x1:t′∈\(\[0,1\]K\)tx\_\{1:t\},x^\{\\prime\}\_\{1:t\}\\in\(\[0,1\]^\{K\}\)^\{t\}are called neighboring if they differ in at most one whole loss vector\. A randomized online algorithm isε\\varepsilon\-differentially private if, for everyt≥1t\\geq 1, every neighboring pairx1:t,x1:t′x\_\{1:t\},x^\{\\prime\}\_\{1:t\}, and every subsetS⊆\[K\]tS\\subseteq\[K\]^\{t\},

ℙ​\(\(I1,…,It\)∈S∣x1:t\)≤eε​ℙ​\(\(I1,…,It\)∈S∣x1:t′\)\.\\mathbb\{P\}\\bigl\(\(I\_\{1\},\\ldots,I\_\{t\}\)\\in S\\mid x\_\{1:t\}\\bigr\)\\leq e^\{\\varepsilon\}\\mathbb\{P\}\\bigl\(\(I\_\{1\},\\ldots,I\_\{t\}\)\\in S\\mid x^\{\\prime\}\_\{1:t\}\\bigr\)\.Equivalently, for every fixed input prefix, the algorithm defines a probability measure on\[K\]t\[K\]^\{t\}, and the two measures associated with neighboring prefixes are within multiplicative factoreεe^\{\\varepsilon\}on every event\.

## 4Algorithm and Main Result

All equalities involving conditional expectations are understoodℙ\\mathbb\{P\}\-almost surely\.

Fixε\>0\\varepsilon\>0and set

η=min⁡\{ε/2,1/8\}\.\\eta=\\min\\\{\\varepsilon/2,1/8\\\}\.For eachr≥0r\\geq 0, define the dyadic block

Br=\{2r,2r\+1,…,2r\+1−1\}\.B\_\{r\}=\\\{2^\{r\},2^\{r\}\+1,\\ldots,2^\{r\+1\}\-1\\\}\.Thus\|Br\|=2r\|B\_\{r\}\|=2^\{r\}\. The algorithm plays one action throughout each block\. LetArA\_\{r\}be the action played on every round inBrB\_\{r\}\. The initial actionA0A\_\{0\}is sampled from any distribution on\[K\]\[K\]that does not depend on the loss sequence\. For concreteness, one may takeA0A\_\{0\}uniform on\[K\]\[K\]\.

After blockBrB\_\{r\}has been observed, the algorithm samples the actionAr\+1A\_\{r\+1\}used in the next block\. Forr=0r=0, setM0=1M\_\{0\}=1\. Forr≥1r\\geq 1, the learner samples an internal random index

Mr∼Unif⁡\{2r−1\+1,…,2r\},M\_\{r\}\\sim\\operatorname\{Unif\}\\\{2^\{r\-1\}\+1,\\ldots,2^\{r\}\\\},independently of the loss vectors and of all other randomization\. Fors∈\{1,…,2r\}s\\in\\\{1,\\ldots,2^\{r\}\\\}write

X\(r,s\)=X2r−1\+s\.X^\{\(r,s\)\}=X\_\{2^\{r\}\-1\+s\}\.This is thessth loss vector in blockBrB\_\{r\}\. Forj∈\[K\]j\\in\[K\]andm∈\{1,…,2r\}m\\in\\\{1,\\ldots,2^\{r\}\\\}define the cumulative block\-prefix loss

Lr,j​\(m\)=∑s=1mXj\(r,s\)\.L\_\{r,j\}\(m\)=\\sum\_\{s=1\}^\{m\}X^\{\(r,s\)\}\_\{j\}\.GivenMrM\_\{r\}and the observed prefixX\(r,1\),…,X\(r,Mr\)X^\{\(r,1\)\},\\ldots,X^\{\(r,M\_\{r\}\)\}, the next action is sampled according to the exponential\-weights distribution

ℙ​\(Ar\+1=j∣Mr,X\(r,1\),…,X\(r,Mr\)\)=exp⁡\(−η​Lr,j​\(Mr\)\)∑i=1Kexp⁡\(−η​Lr,i​\(Mr\)\)\.\\mathbb\{P\}\(A\_\{r\+1\}=j\\mid M\_\{r\},X^\{\(r,1\)\},\\ldots,X^\{\(r,M\_\{r\}\)\}\)=\\frac\{\\exp\(\-\\eta L\_\{r,j\}\(M\_\{r\}\)\)\}\{\\sum\_\{i=1\}^\{K\}\\exp\(\-\\eta L\_\{r,i\}\(M\_\{r\}\)\)\}\.Equivalently, this is the softmax of the negative cumulative losses−Lr,j​\(Mr\)\-L\_\{r,j\}\(M\_\{r\}\)with inverse temperatureη\\eta\.

###### Theorem 1\(Explicit gap\-dependent private regret\)\.

For everyK≥2K\\geq 2, everyε\>0\\varepsilon\>0, every horizonT≥1T\\geq 1, and every i\.i\.d\. loss process with marginal distribution supported on\[0,1\]K\[0,1\]^\{K\}with a unique best action, the randomized\-prefix softmax algorithm isε\\varepsilon\-differentially private and satisfies

RegT≤1\+800​log⁡KΔmin\+16​log⁡Kη,η=min⁡\{ε/2,1/8\}\.\\operatorname\{Reg\}\_\{T\}\\leq 1\+800\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+16\\frac\{\\log K\}\{\\eta\},\\qquad\\eta=\\min\\\{\\varepsilon/2,1/8\\\}\.\(1\)
In particular,

RegT≤1000​\(log⁡KΔmin\+log⁡Kε\)\.\\operatorname\{Reg\}\_\{T\}\\leq 1000\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\\right\)\.\(2\)The constant10001000is explicit and universal, but it is not optimized\.

###### Corollary 1\(Matching rate\)\.

Combining[Theorem1](https://arxiv.org/html/2605.29148#Thmtheorem1)with the lower bound of\[[5](https://arxiv.org/html/2605.29148#bib.bib8)\]gives the optimal gap\-dependent rate

Θ​\(log⁡KΔmin\+log⁡Kε\)\.\\Theta\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\\right\)\.

## 5Proofs

### 5\.1Auxiliary facts used in the proof

###### Lemma 1\(Hoeffding bound with the constants used below\)\.

LetU1,…,UmU\_\{1\},\\ldots,U\_\{m\}be independent random variables with values in\[−1,1\]\[\-1,1\]and common expectation𝔼​\[Us\]=μ\>0\\mathbb\{E\}\[U\_\{s\}\]=\\mu\>0\. Then

ℙ​\(∑s=1mUs≤m​μ2\)≤exp⁡\(−m​μ28\)\.\\mathbb\{P\}\\left\(\\sum\_\{s=1\}^\{m\}U\_\{s\}\\leq\\frac\{m\\mu\}\{2\}\\right\)\\leq\\exp\\left\(\-\\frac\{m\\mu^\{2\}\}\{8\}\\right\)\.

###### Proof\.

Hoeffding’s inequality for independent variablesUs∈\[as,bs\]U\_\{s\}\\in\[a\_\{s\},b\_\{s\}\]states that, for everyu\>0u\>0,

ℙ​\(∑s=1m\(Us−𝔼​\[Us\]\)≤−u\)≤exp⁡\(−2​u2∑s=1m\(bs−as\)2\)\.\\mathbb\{P\}\\left\(\\sum\_\{s=1\}^\{m\}\(U\_\{s\}\-\\mathbb\{E\}\[U\_\{s\}\]\)\\leq\-u\\right\)\\leq\\exp\\left\(\-\\frac\{2u^\{2\}\}\{\\sum\_\{s=1\}^\{m\}\(b\_\{s\}\-a\_\{s\}\)^\{2\}\}\\right\)\.This is\[[4](https://arxiv.org/html/2605.29148#bib.bib2), Theorem 2\]\. Hereas=−1a\_\{s\}=\-1,bs=1b\_\{s\}=1, andu=m​μ/2u=m\\mu/2\. Therefore

2​u2∑s=1m\(bs−as\)2=2​\(m​μ/2\)24​m=m​μ28,\\frac\{2u^\{2\}\}\{\\sum\_\{s=1\}^\{m\}\(b\_\{s\}\-a\_\{s\}\)^\{2\}\}=\\frac\{2\(m\\mu/2\)^\{2\}\}\{4m\}=\\frac\{m\\mu^\{2\}\}\{8\},which proves the claim\. ∎

###### Lemma 2\(Elementary inequalities\)\.

The following inequalities hold\.

1. \(i\)1−e−x≥x/21\-e^\{\-x\}\\geq x/2, for everyx∈\[0,1\]x\\in\[0,1\]\.
2. \(ii\)e−x≤1−x/2e^\{\-x\}\\leq 1\-x/2, for everyx∈\[0,1\]x\\in\[0,1\]\.
3. \(iii\)log⁡\(1−u\)≤−u\\log\(1\-u\)\\leq\-u, for everyu∈\[0,1\)u\\in\[0,1\)\.
4. \(iv\)∑m\>ne−m​x≤2​e−n​xx\\sum\_\{m\>n\}e^\{\-mx\}\\leq\\frac\{2e^\{\-nx\}\}\{x\}, for everyx∈\(0,1\]x\\in\(0,1\]and every integern≥0n\\geq 0\.
5. \(v\)log⁡\(K\+1\)≤2​log⁡K\\log\(K\+1\)\\leq 2\\log K, for every integerK≥2K\\geq 2\.

###### Proof\.

For \(i\), defineg​\(x\)=1−e−x−x/2g\(x\)=1\-e^\{\-x\}\-x/2\. Theng​\(0\)=0g\(0\)=0,g′​\(x\)=e−x−1/2g^\{\\prime\}\(x\)=e^\{\-x\}\-1/2, andg​\(1\)=1−e−1−1/2\>0g\(1\)=1\-e^\{\-1\}\-1/2\>0\. The function increases on\[0,log⁡2\]\[0,\\log 2\]and decreases on\[log⁡2,1\]\[\\log 2,1\], so its minimum on\[0,1\]\[0,1\]is nonnegative\. This proves \(i\)\. Item \(ii\) is the same inequality rearranged\. For \(iii\), defineh​\(u\)=−u−log⁡\(1−u\)h\(u\)=\-u\-\\log\(1\-u\)\. Thenh​\(0\)=0h\(0\)=0andh′​\(u\)=u/\(1−u\)≥0h^\{\\prime\}\(u\)=u/\(1\-u\)\\geq 0foru∈\[0,1\)u\\in\[0,1\)\. For \(iv\),

∑m\>ne−m​x=e−\(n\+1\)​x1−e−x≤e−n​x1−e−x≤2​e−n​xx,\\sum\_\{m\>n\}e^\{\-mx\}=\\frac\{e^\{\-\(n\+1\)x\}\}\{1\-e^\{\-x\}\}\\leq\\frac\{e^\{\-nx\}\}\{1\-e^\{\-x\}\}\\leq\\frac\{2e^\{\-nx\}\}\{x\},where the last inequality uses \(i\)\. For \(v\),K\+1≤K2K\+1\\leq K^\{2\}forK≥2K\\geq 2, hencelog⁡\(K\+1\)≤2​log⁡K\\log\(K\+1\)\\leq 2\\log K\. ∎

### 5\.2Privacy

We first prove privacy for the one\-block selector as an ordinary randomized map on deterministic datasets\.

###### Definition 2\(Differential privacy for a randomized map\)\.

Fix an integern≥1n\\geq 1\. A randomized map𝖬:\(\[0,1\]K\)n→\[K\]\\mathsf\{M\}:\(\[0,1\]^\{K\}\)^\{n\}\\to\[K\]isα\\alpha\-differentially private if, for every pair of deterministic datasetsd,d′∈\(\[0,1\]K\)nd,d^\{\\prime\}\\in\(\[0,1\]^\{K\}\)^\{n\}that differ in at most one coordinate vector and everyS⊆\[K\]S\\subseteq\[K\],

ℙ​\(𝖬​\(d\)∈S\)≤eα​ℙ​\(𝖬​\(d′\)∈S\)\.\\mathbb\{P\}\(\\mathsf\{M\}\(d\)\\in S\)\\leq e^\{\\alpha\}\\mathbb\{P\}\(\\mathsf\{M\}\(d^\{\\prime\}\)\\in S\)\.

###### Lemma 3\(Privacy of the softmax map\)\.

Fixn≥1n\\geq 1, and letNNbe a random variable on\{1,…,n\}\\\{1,\\ldots,n\\\}whose distribution does not depend on the dataset\. Given a deterministic datasetd=\(x1,…,xn\)∈\(\[0,1\]K\)nd=\(x\_\{1\},\\ldots,x\_\{n\}\)\\in\(\[0,1\]^\{K\}\)^\{n\}, define

Ljd​\(m\)=∑s=1mxs,j,j∈\[K\],m∈\{1,…,n\}\.L\_\{j\}^\{d\}\(m\)=\\sum\_\{s=1\}^\{m\}x\_\{s,j\},\\qquad j\\in\[K\],\\quad m\\in\\\{1,\\ldots,n\\\}\.After samplingNN, outputJ∈\[K\]J\\in\[K\]with conditional law

ℙ\(J=j∣N=m,d\)=exp⁡\(−η​Ljd​\(m\)\)∑i=1Kexp⁡\(−η​Lid​\(m\)\)\.\\mathbb\{P\}\(J=j\\mid N=m,d\)=\\frac\{\\exp\(\-\\eta L\_\{j\}^\{d\}\(m\)\)\}\{\\sum\_\{i=1\}^\{K\}\\exp\(\-\\eta L\_\{i\}^\{d\}\(m\)\)\}\.Then the randomized mapd↦Jd\\mapsto Jis2​η2\\eta\-differentially private in the sense of Definition 2\.

###### Proof\.

Letd=\(x1,…,xn\)d=\(x\_\{1\},\\ldots,x\_\{n\}\)andd′=\(x1′,…,xn′\)d^\{\\prime\}=\(x^\{\\prime\}\_\{1\},\\ldots,x^\{\\prime\}\_\{n\}\)differ in at most one vector\. Fixm∈\{1,…,n\}m\\in\\\{1,\\ldots,n\\\}\. For everyj∈\[K\]j\\in\[K\],

\|Ljd​\(m\)−Ljd′​\(m\)\|≤1,\|L\_\{j\}^\{d\}\(m\)\-L\_\{j\}^\{d^\{\\prime\}\}\(m\)\|\\leq 1,because the two prefixes either are identical or differ in one vector whosejjth coordinate lies in\[0,1\]\[0,1\]\. Write

Zd​\(m\)≔∑i=1Kexp⁡\(−η​Lid​\(m\)\)\.Z^\{d\}\(m\)\\coloneqq\\sum\_\{i=1\}^\{K\}\\exp\(\-\\eta L\_\{i\}^\{d\}\(m\)\)\.For everyii,

exp⁡\(−η​Lid′​\(m\)\)≤eη​exp⁡\(−η​Lid​\(m\)\),\\exp\(\-\\eta L\_\{i\}^\{d^\{\\prime\}\}\(m\)\)\\leq e^\{\\eta\}\\exp\(\-\\eta L\_\{i\}^\{d\}\(m\)\),and therefore

Zd′​\(m\)≤eη​Zd​\(m\)\.Z^\{d^\{\\prime\}\}\(m\)\\leq e^\{\\eta\}Z^\{d\}\(m\)\.For everyj∈\[K\]j\\in\[K\],

ℙ\(J=j∣N=m,d\)ℙ\(J=j∣N=m,d′\)\\displaystyle\\frac\{\\mathbb\{P\}\(J=j\\mid N=m,d\)\}\{\\mathbb\{P\}\(J=j\\mid N=m,d^\{\\prime\}\)\}=exp⁡\{−η​\(Ljd​\(m\)−Ljd′​\(m\)\)\}​Zd′​\(m\)Zd​\(m\)≤eη​eη=e2​η\.\\displaystyle=\\exp\\\{\-\\eta\(L\_\{j\}^\{d\}\(m\)\-L\_\{j\}^\{d^\{\\prime\}\}\(m\)\)\\\}\\frac\{Z^\{d^\{\\prime\}\}\(m\)\}\{Z^\{d\}\(m\)\}\\leq e^\{\\eta\}e^\{\\eta\}=e^\{2\\eta\}\.Summing this pointwise bound overj∈Sj\\in Sgives

ℙ\(J∈S∣N=m,d\)≤e2​ηℙ\(J∈S∣N=m,d′\)\\mathbb\{P\}\(J\\in S\\mid N=m,d\)\\leq e^\{2\\eta\}\\mathbb\{P\}\(J\\in S\\mid N=m,d^\{\\prime\}\)for everyS⊆\[K\]S\\subseteq\[K\]\. Now average overNN\. Since the law ofNNis the same underddandd′d^\{\\prime\},

ℙ​\(J∈S∣d\)\\displaystyle\\mathbb\{P\}\(J\\in S\\mid d\)=∑m=1nℙ\(N=m\)ℙ\(J∈S∣N=m,d\)\\displaystyle=\\sum\_\{m=1\}^\{n\}\\mathbb\{P\}\(N=m\)\\mathbb\{P\}\(J\\in S\\mid N=m,d\)≤e2​η∑m=1nℙ\(N=m\)ℙ\(J∈S∣N=m,d′\)\\displaystyle\\leq e^\{2\\eta\}\\sum\_\{m=1\}^\{n\}\\mathbb\{P\}\(N=m\)\\mathbb\{P\}\(J\\in S\\mid N=m,d^\{\\prime\}\)=e2​η​ℙ​\(J∈S∣d′\)\.\\displaystyle=e^\{2\\eta\}\\mathbb\{P\}\(J\\in S\\mid d^\{\\prime\}\)\.This is exactly2​η2\\eta\-differential privacy for the softmax map\. ∎

###### Proposition 1\(Global event\-level privacy\)\.

The randomized\-prefix softmax algorithm isε\\varepsilon\-differentially private\.

###### Proof\.

Fix a horizont≥1t\\geq 1, and lets=s​\(t\)s=s\(t\)be the unique integer such thatt∈Bst\\in B\_\{s\}\. The action prefix\(I1,…,It\)\(I\_\{1\},\\ldots,I\_\{t\}\)is a deterministic function of the block actions

A0,A1,…,As\.A\_\{0\},A\_\{1\},\\ldots,A\_\{s\}\.Indeed, ifu∈Bru\\in B\_\{r\}andu≤tu\\leq t, thenIu=ArI\_\{u\}=A\_\{r\}\.

Fix a deterministic prefixy1:ty\_\{1:t\}\. SinceA0A\_\{0\}is sampled independently of the data, and since for eachℓ∈\{0,…,s−1\}\\ell\\in\\\{0,\\ldots,s\-1\\\}the actionAℓ\+1A\_\{\\ell\+1\}is sampled using only the data in blockBℓB\_\{\\ell\}, the law of\(A0,…,As\)\(A\_\{0\},\\ldots,A\_\{s\}\)under the fixed input prefixy1:ty\_\{1:t\}factorizes as follows: for everya0:s∈\[K\]s\+1a\_\{0:s\}\\in\[K\]^\{s\+1\},

ℙ​\(\(A0,…,As\)=a0:s∣y1:t\)\\displaystyle\\mathbb\{P\}\\left\(\(A\_\{0\},\\ldots,A\_\{s\}\)=a\_\{0:s\}\\mid y\_\{1:t\}\\right\)=ℙ​\(A0=a0\)​∏ℓ=0s−1ℙ​\(Aℓ\+1=aℓ\+1∣yBℓ\)\.\\displaystyle\\quad=\\mathbb\{P\}\\left\(A\_\{0\}=a\_\{0\}\\right\)\\prod\_\{\\ell=0\}^\{s\-1\}\\mathbb\{P\}\\left\(A\_\{\\ell\+1\}=a\_\{\\ell\+1\}\\mid y\_\{B\_\{\\ell\}\}\\right\)\.HereyBℓy\_\{B\_\{\\ell\}\}denotes the restriction of the deterministic prefixy1:ty\_\{1:t\}to the blockBℓB\_\{\\ell\}\. The product is empty whens=0s=0\.

Now fix two deterministic prefixesx1:tx\_\{1:t\}andx1:t′x^\{\\prime\}\_\{1:t\}that differ in at most one time index\. If the differing vector lies in the current blockBsB\_\{s\}, then it does not appear in any of the blocksB0,…,Bs−1B\_\{0\},\\ldots,B\_\{s\-1\}\. Hence all factors in the above product are identical forx1:tx\_\{1:t\}andx1:t′x^\{\\prime\}\_\{1:t\}, and therefore the two laws of\(A0,…,As\)\(A\_\{0\},\\ldots,A\_\{s\}\)are identical\.

Otherwise, the differing vector lies in a previous blockBrB\_\{r\}, for somer≤s−1r\\leq s\-1\. Then all factors in the product are identical except possibly the factor

ℙ​\(Ar\+1=ar\+1∣xBr\)\.\\mathbb\{P\}\\left\(A\_\{r\+1\}=a\_\{r\+1\}\\mid x\_\{B\_\{r\}\}\\right\)\.By[Lemma3](https://arxiv.org/html/2605.29148#Thmlemma3), applied to the two deterministic block datasetsxBrx\_\{B\_\{r\}\}andxBr′x^\{\\prime\}\_\{B\_\{r\}\}, changing one loss vector inBrB\_\{r\}changes the law ofAr\+1A\_\{r\+1\}by at most a multiplicative factore2​ηe^\{2\\eta\}\. In particular, for everyar\+1∈\[K\]a\_\{r\+1\}\\in\[K\],

ℙ​\(Ar\+1=ar\+1∣xBr\)≤e2​η​ℙ​\(Ar\+1=ar\+1∣xBr′\)\.\\mathbb\{P\}\\left\(A\_\{r\+1\}=a\_\{r\+1\}\\mid x\_\{B\_\{r\}\}\\right\)\\leq e^\{2\\eta\}\\mathbb\{P\}\\left\(A\_\{r\+1\}=a\_\{r\+1\}\\mid x^\{\\prime\}\_\{B\_\{r\}\}\\right\)\.Combining this inequality with the product factorization gives, for everya0:s∈\[K\]s\+1a\_\{0:s\}\\in\[K\]^\{s\+1\},

ℙ​\(\(A0,…,As\)=a0:s∣x1:t\)≤e2​η​ℙ​\(\(A0,…,As\)=a0:s∣x1:t′\)\.\\mathbb\{P\}\\left\(\(A\_\{0\},\\ldots,A\_\{s\}\)=a\_\{0:s\}\\mid x\_\{1:t\}\\right\)\\leq e^\{2\\eta\}\\mathbb\{P\}\\left\(\(A\_\{0\},\\ldots,A\_\{s\}\)=a\_\{0:s\}\\mid x^\{\\prime\}\_\{1:t\}\\right\)\.Summing overa0:s∈Ea\_\{0:s\}\\in Eyields, for everyE⊆\[K\]s\+1E\\subseteq\[K\]^\{s\+1\},

ℙ​\(\(A0,…,As\)∈E∣x1:t\)≤e2​η​ℙ​\(\(A0,…,As\)∈E∣x1:t′\)\.\\mathbb\{P\}\\left\(\(A\_\{0\},\\ldots,A\_\{s\}\)\\in E\\mid x\_\{1:t\}\\right\)\\leq e^\{2\\eta\}\\mathbb\{P\}\\left\(\(A\_\{0\},\\ldots,A\_\{s\}\)\\in E\\mid x^\{\\prime\}\_\{1:t\}\\right\)\.
Finally, define the deterministic mapϕt:\[K\]s\+1→\[K\]t\\phi\_\{t\}:\[K\]^\{s\+1\}\\to\[K\]^\{t\}by

ϕt​\(a0,…,as\)​\(u\)=as​\(u\),u∈\[t\],\\phi\_\{t\}\(a\_\{0\},\\ldots,a\_\{s\}\)\(u\)=a\_\{s\(u\)\},\\qquad u\\in\[t\],wheres​\(u\)s\(u\)is the unique integer such thatu∈Bs​\(u\)u\\in B\_\{s\(u\)\}\. Then

\(I1,…,It\)=ϕt​\(A0,…,As\)\.\(I\_\{1\},\\ldots,I\_\{t\}\)=\\phi\_\{t\}\(A\_\{0\},\\ldots,A\_\{s\}\)\.For anyS⊆\[K\]tS\\subseteq\[K\]^\{t\}, apply the preceding inequality withE=ϕt−1​\(S\)E=\\phi\_\{t\}^\{\-1\}\(S\)\. This gives

ℙ​\(\(I1,…,It\)∈S∣x1:t\)≤e2​η​ℙ​\(\(I1,…,It\)∈S∣x1:t′\)\.\\mathbb\{P\}\\left\(\(I\_\{1\},\\ldots,I\_\{t\}\)\\in S\\mid x\_\{1:t\}\\right\)\\leq e^\{2\\eta\}\\mathbb\{P\}\\left\(\(I\_\{1\},\\ldots,I\_\{t\}\)\\in S\\mid x^\{\\prime\}\_\{1:t\}\\right\)\.Since2​η≤ε2\\eta\\leq\\varepsilon, the algorithm isε\\varepsilon\-differentially private\. ∎

### 5\.3Randomized\-prefix clock

Let\(Xs\)s≥1\(X\_\{s\}\)\_\{s\\geq 1\}be the loss\-vector process\. Form≥1m\\geq 1andj∈\[K\]j\\in\[K\], define the cumulative loss

Lm,j=∑s=1mXs,j\.L\_\{m,j\}=\\sum\_\{s=1\}^\{m\}X\_\{s,j\}\.Forj∈\{2,…,K\}j\\in\\\{2,\\ldots,K\\\}define the cumulative empirical gap

Dm,j=Lm,j−Lm,1=∑s=1m\(Xs,j−Xs,1\)\.D\_\{m,j\}=L\_\{m,j\}\-L\_\{m,1\}=\\sum\_\{s=1\}^\{m\}\(X\_\{s,j\}\-X\_\{s,1\}\)\.Form≥1m\\geq 1, define the random softmax weights

Pm,1≔11\+∑i=2Ke−η​Dm,i,Pm,j≔e−η​Dm,j1\+∑i=2Ke−η​Dm,i\(j≥2\)\.P\_\{m,1\}\\coloneqq\\frac\{1\}\{1\+\\sum\_\{i=2\}^\{K\}e^\{\-\\eta D\_\{m,i\}\}\},\\qquad P\_\{m,j\}\\coloneqq\\frac\{e^\{\-\\eta D\_\{m,j\}\}\}\{1\+\\sum\_\{i=2\}^\{K\}e^\{\-\\eta D\_\{m,i\}\}\}\\quad\(j\\geq 2\)\.Finally define the deterministic number

Fm≔𝔼​\[∑j=1KΔj​Pm,j\]=𝔼​\[∑j=2KΔj​Pm,j\]\.F\_\{m\}\\coloneqq\\mathbb\{E\}\\left\[\\sum\_\{j=1\}^\{K\}\\Delta\_\{j\}P\_\{m,j\}\\right\]=\\mathbb\{E\}\\left\[\\sum\_\{j=2\}^\{K\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\.
###### Lemma 4\(Clock reduction with explicit constant\)\.

For every horizonT≥1T\\geq 1,

RegT≤1\+4​∑m≥1Fm\.\\operatorname\{Reg\}\_\{T\}\\leq 1\+4\\sum\_\{m\\geq 1\}F\_\{m\}\.

###### Proof\.

The initial blockB0=\{1\}B\_\{0\}=\\\{1\\\}has length one\. Since every gap is at most11, its regret contribution is at most11\.

Fixr≥0r\\geq 0\. The actionAr\+1A\_\{r\+1\}is played during blockBr\+1B\_\{r\+1\}\. If the horizonTTcontains the whole blockBr\+1B\_\{r\+1\}, then this action is played\|Br\+1\|=2r\+1\|B\_\{r\+1\}\|=2^\{r\+1\}times\. IfTTcuts the blockBr\+1B\_\{r\+1\}, then it is played fewer times\. In both cases, the number of rounds in whichAr\+1A\_\{r\+1\}is played is at most2r\+12^\{r\+1\}\.

Moreover, conditionally onMr=mM\_\{r\}=m, the data used to sampleAr\+1A\_\{r\+1\}are the firstmmloss vectors of blockBrB\_\{r\}\. Since the loss process is i\.i\.d\. andMrM\_\{r\}is independent of the losses, thesemmvectors have the same distribution asX1,…,XmX\_\{1\},\\ldots,X\_\{m\}\. Therefore

𝔼​\[ΔAr\+1∣Mr=m\]=Fm\.\\mathbb\{E\}\[\\Delta\_\{A\_\{r\+1\}\}\\mid M\_\{r\}=m\]=F\_\{m\}\.Taking expectation overMrM\_\{r\}gives

𝔼​\[ΔAr\+1\]=𝔼​\[FMr\]\.\\mathbb\{E\}\[\\Delta\_\{A\_\{r\+1\}\}\]=\\mathbb\{E\}\[F\_\{M\_\{r\}\}\]\.Thus the regret charged to blockBr\+1B\_\{r\+1\}is at most

2r\+1​𝔼​\[FMr\]\.2^\{r\+1\}\\mathbb\{E\}\[F\_\{M\_\{r\}\}\]\.Forr=0r=0,M0=1M\_\{0\}=1, hence this is2​F12F\_\{1\}, which is no greater than4​F14F\_\{1\}\. Forr≥1r\\geq 1,MrM\_\{r\}is uniform on\{2r−1\+1,…,2r\}\\\{2^\{r\-1\}\+1,\\ldots,2^\{r\}\\\}, a set of cardinality2r−12^\{r\-1\}\. Therefore

2r\+1​𝔼​\[FMr\]=2r\+1​12r−1​∑m=2r−1\+12rFm=4​∑m=2r−1\+12rFm\.2^\{r\+1\}\\mathbb\{E\}\[F\_\{M\_\{r\}\}\]=2^\{r\+1\}\\frac\{1\}\{2^\{r\-1\}\}\\sum\_\{m=2^\{r\-1\}\+1\}^\{2^\{r\}\}F\_\{m\}=4\\sum\_\{m=2^\{r\-1\}\+1\}^\{2^\{r\}\}F\_\{m\}\.The intervals\{2r−1\+1,…,2r\}\\\{2^\{r\-1\}\+1,\\ldots,2^\{r\}\\\}forr≥1r\\geq 1are disjoint and cover all integersm≥2m\\geq 2\. Adding the initial block contribution and all following block contributions gives

RegT≤1\+4​F1\+4​∑m≥2Fm=1\+4​∑m≥1Fm\.\\operatorname\{Reg\}\_\{T\}\\leq 1\+4F\_\{1\}\+4\\sum\_\{m\\geq 2\}F\_\{m\}=1\+4\\sum\_\{m\\geq 1\}F\_\{m\}\.∎

### 5\.4Prefix\-length softmax\-error bound

###### Lemma 5\(Cumulative softmax\-error bound with explicit constants\)\.

Forη≤1/8\\eta\\leq 1/8,

∑m≥1Fm≤200​log⁡KΔmin\+4​log⁡Kη\.\\sum\_\{m\\geq 1\}F\_\{m\}\\leq 200\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+4\\frac\{\\log K\}\{\\eta\}\.

###### Proof\.

Recall that, form≥1m\\geq 1,

Fm=𝔼​\[∑j=2KΔj​Pm,j\]\.F\_\{m\}=\\mathbb\{E\}\\left\[\\sum\_\{j=2\}^\{K\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\.Therefore

∑m≥1Fm\\displaystyle\\sum\_\{m\\geq 1\}F\_\{m\}=∑m≥1𝔼​\[∑j∈\{2,…,K\}Δj≤4​ηΔj​Pm,j\]\+∑m≥1𝔼​\[∑j∈\{2,…,K\}Δj\>4​ηΔj​Pm,j\]\.\\displaystyle=\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\\leq 4\\eta\\end\{subarray\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\+\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\.\(3\)
We bound the two terms separately\.

#### Small\-gap contribution\.

If there is no gapΔj≤4​η\\Delta\_\{j\}\\leq 4\\eta, then the first sum is trivially bounded by0\. Otherwise, fixj∈\{2,…,K\}j\\in\\\{2,\\ldots,K\\\}withΔj≤4​η\\Delta\_\{j\}\\leq 4\\eta\. For everym≥1m\\geq 1,

Pm,j≤e−η​Dm,j,P\_\{m,j\}\\leq e^\{\-\\eta D\_\{m,j\}\},because the denominator in the definition ofPm,jP\_\{m,j\}is at least11\. Therefore

𝔼​\[Pm,j\]\\displaystyle\\mathbb\{E\}\\left\[P\_\{m,j\}\\right\]=𝔼​\[Pm,j​𝕀​\{Dm,j≤m​Δj2\}\]\+𝔼​\[Pm,j​𝕀​\{Dm,j\>m​Δj2\}\]\\displaystyle=\\mathbb\{E\}\\left\[P\_\{m,j\}\\mathbb\{I\}\\left\\\{D\_\{m,j\}\\leq\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\\\}\\right\]\+\\mathbb\{E\}\\left\[P\_\{m,j\}\\mathbb\{I\}\\left\\\{D\_\{m,j\}\>\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\\\}\\right\]≤𝔼​\[𝕀​\{Dm,j≤m​Δj2\}\]\+𝔼​\[e−η​Dm,j​𝕀​\{Dm,j\>m​Δj2\}\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\mathbb\{I\}\\left\\\{D\_\{m,j\}\\leq\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\\\}\\right\]\+\\mathbb\{E\}\\left\[e^\{\-\\eta D\_\{m,j\}\}\\mathbb\{I\}\\left\\\{D\_\{m,j\}\>\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\\\}\\right\]=ℙ​\(Dm,j≤m​Δj2\)\+𝔼​\[e−η​Dm,j​𝕀​\{Dm,j\>m​Δj2\}\]\\displaystyle=\\mathbb\{P\}\\left\(D\_\{m,j\}\\leq\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\)\+\\mathbb\{E\}\\left\[e^\{\-\\eta D\_\{m,j\}\}\\mathbb\{I\}\\left\\\{D\_\{m,j\}\>\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\\\}\\right\]≤ℙ​\(Dm,j≤m​Δj2\)\+𝔼​\[e−η​m​Δj/2​𝕀​\{Dm,j\>m​Δj2\}\]\\displaystyle\\leq\\mathbb\{P\}\\left\(D\_\{m,j\}\\leq\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\)\+\\mathbb\{E\}\\left\[e^\{\-\\eta m\\Delta\_\{j\}/2\}\\mathbb\{I\}\\left\\\{D\_\{m,j\}\>\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\\\}\\right\]≤ℙ​\(Dm,j≤m​Δj2\)\+e−η​m​Δj/2\.\\displaystyle\\leq\\mathbb\{P\}\\left\(D\_\{m,j\}\\leq\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\)\+e^\{\-\\eta m\\Delta\_\{j\}/2\}\.The random variablesXs,j−Xs,1X\_\{s,j\}\-X\_\{s,1\}are independent acrossss, take values in\[−1,1\]\[\-1,1\], and have expectationΔj\\Delta\_\{j\}\. By[Lemma1](https://arxiv.org/html/2605.29148#Thmlemma1),

ℙ​\(Dm,j≤m​Δj2\)≤exp⁡\(−m​Δj28\)\.\\mathbb\{P\}\\left\(D\_\{m,j\}\\leq\\frac\{m\\Delta\_\{j\}\}\{2\}\\right\)\\leq\\exp\\left\(\-\\frac\{m\\Delta\_\{j\}^\{2\}\}\{8\}\\right\)\.SinceΔj≤4​η\\Delta\_\{j\}\\leq 4\\eta, we haveη≥Δj/4\\eta\\geq\\Delta\_\{j\}/4, and thus

exp⁡\(−η​m​Δj2\)≤exp⁡\(−m​Δj28\)\.\\exp\\left\(\-\\frac\{\\eta m\\Delta\_\{j\}\}\{2\}\\right\)\\leq\\exp\\left\(\-\\frac\{m\\Delta\_\{j\}^\{2\}\}\{8\}\\right\)\.Consequently,

𝔼​\[Pm,j\]≤2​exp⁡\(−m​Δj28\)\.\\mathbb\{E\}\[P\_\{m,j\}\]\\leq 2\\exp\\left\(\-\\frac\{m\\Delta\_\{j\}^\{2\}\}\{8\}\\right\)\.\(4\)
For each integerℓ≥1\\ell\\geq 1, define

Hℓ=\{j∈\{2,…,K\}:Δj≤4​η,2ℓ−1​Δmin≤Δj<2ℓ​Δmin\}\.H\_\{\\ell\}=\\left\\\{j\\in\\\{2,\\ldots,K\\\}:\\Delta\_\{j\}\\leq 4\\eta,\\quad 2^\{\\ell\-1\}\\Delta\_\{\\min\}\\leq\\Delta\_\{j\}<2^\{\\ell\}\\Delta\_\{\\min\}\\right\\\}\.Fixℓ\\ellwithHℓ≠∅H\_\{\\ell\}\\neq\\varnothingand define

τℓ=⌈16​log⁡\(\|Hℓ\|\+1\)\(2ℓ−1​Δmin\)2⌉\.\\tau\_\{\\ell\}=\\left\\lceil\\frac\{16\\log\(\|H\_\{\\ell\}\|\+1\)\}\{\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}\}\\right\\rceil\.Form≤τℓm\\leq\\tau\_\{\\ell\}, usingΔj<2ℓ​Δmin\\Delta\_\{j\}<2^\{\\ell\}\\Delta\_\{\\min\}forj∈Hℓj\\in H\_\{\\ell\}and∑j∈HℓPm,j≤1\\sum\_\{j\\in H\_\{\\ell\}\}P\_\{m,j\}\\leq 1, we get the pathwise bound

∑j∈HℓΔj​Pm,j≤2ℓ​Δmin​∑j∈HℓPm,j≤2ℓ​Δmin\.\\sum\_\{j\\in H\_\{\\ell\}\}\\Delta\_\{j\}P\_\{m,j\}\\leq 2^\{\\ell\}\\Delta\_\{\\min\}\\sum\_\{j\\in H\_\{\\ell\}\}P\_\{m,j\}\\leq 2^\{\\ell\}\\Delta\_\{\\min\}\.Therefore the early part of groupHℓH\_\{\\ell\}is at most

∑m=1τℓ𝔼​\[∑j∈HℓΔj​Pm,j\]\\displaystyle\\sum\_\{m=1\}^\{\\tau\_\{\\ell\}\}\\mathbb\{E\}\\left\[\\sum\_\{j\\in H\_\{\\ell\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]≤2ℓ​Δmin​τℓ\\displaystyle\\leq 2^\{\\ell\}\\Delta\_\{\\min\}\\tau\_\{\\ell\}≤32​log⁡\(\|Hℓ\|\+1\)2ℓ−1​Δmin\+2ℓ​Δmin\\displaystyle\\leq\\frac\{32\\log\(\|H\_\{\\ell\}\|\+1\)\}\{2^\{\\ell\-1\}\\Delta\_\{\\min\}\}\+2^\{\\ell\}\\Delta\_\{\\min\}≤32​log⁡\(\|Hℓ\|\+1\)\+22ℓ−1​Δmin\.\\displaystyle\\leq\\frac\{32\\log\(\|H\_\{\\ell\}\|\+1\)\+2\}\{2^\{\\ell\-1\}\\Delta\_\{\\min\}\}\.The last step uses2ℓ−1​Δmin≤12^\{\\ell\-1\}\\Delta\_\{\\min\}\\leq 1, which follows fromHℓ≠∅H\_\{\\ell\}\\neq\\varnothingandΔj≤1\\Delta\_\{j\}\\leq 1\.

Form\>τℓm\>\\tau\_\{\\ell\}, use \([4](https://arxiv.org/html/2605.29148#S5.E4)\) andΔj<2ℓ​Δmin\\Delta\_\{j\}<2^\{\\ell\}\\Delta\_\{\\min\}to obtain

∑m\>τℓ𝔼​\[∑j∈HℓΔj​Pm,j\]\\displaystyle\\sum\_\{m\>\\tau\_\{\\ell\}\}\\mathbb\{E\}\\left\[\\sum\_\{j\\in H\_\{\\ell\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]≤∑m\>τℓ∑j∈Hℓ4​\(2ℓ−1​Δmin\)​exp⁡\(−m​\(2ℓ−1​Δmin\)28\)\.\\displaystyle\\leq\\sum\_\{m\>\\tau\_\{\\ell\}\}\\sum\_\{j\\in H\_\{\\ell\}\}4\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)\\exp\\left\(\-\\frac\{m\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}\}\{8\}\\right\)\.For nonemptyHℓH\_\{\\ell\}, the inequality2ℓ−1​Δmin≤Δj≤4​η2^\{\\ell\-1\}\\Delta\_\{\\min\}\\leq\\Delta\_\{j\}\\leq 4\\etaandη≤1/8\\eta\\leq 1/8imply2ℓ−1​Δmin≤1/22^\{\\ell\-1\}\\Delta\_\{\\min\}\\leq 1/2\. Setx=\(2ℓ−1​Δmin\)2/8x=\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}/8\. Thenx∈\(0,1\]x\\in\(0,1\]\. By[\(iv\)](https://arxiv.org/html/2605.29148#S5.I1.i4)in[Lemma2](https://arxiv.org/html/2605.29148#Thmlemma2),

∑m\>τℓexp⁡\(−m​\(2ℓ−1​Δmin\)28\)≤16\(2ℓ−1​Δmin\)2​exp⁡\(−τℓ​\(2ℓ−1​Δmin\)28\)\.\\sum\_\{m\>\\tau\_\{\\ell\}\}\\exp\\left\(\-\\frac\{m\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}\}\{8\}\\right\)\\leq\\frac\{16\}\{\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}\}\\exp\\left\(\-\\frac\{\\tau\_\{\\ell\}\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}\}\{8\}\\right\)\.The definition ofτℓ\\tau\_\{\\ell\}gives

exp⁡\(−τℓ​\(2ℓ−1​Δmin\)28\)≤1\(\|Hℓ\|\+1\)2\.\\exp\\left\(\-\\frac\{\\tau\_\{\\ell\}\(2^\{\\ell\-1\}\\Delta\_\{\\min\}\)^\{2\}\}\{8\}\\right\)\\leq\\frac\{1\}\{\(\|H\_\{\\ell\}\|\+1\)^\{2\}\}\.Hence

∑m\>τℓ𝔼​\[∑j∈HℓΔj​Pm,j\]\\displaystyle\\sum\_\{m\>\\tau\_\{\\ell\}\}\\mathbb\{E\}\\left\[\\sum\_\{j\\in H\_\{\\ell\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]≤64​\|Hℓ\|2ℓ−1​Δmin​1\(\|Hℓ\|\+1\)2≤162ℓ−1​Δmin,\\displaystyle\\leq\\frac\{64\|H\_\{\\ell\}\|\}\{2^\{\\ell\-1\}\\Delta\_\{\\min\}\}\\frac\{1\}\{\(\|H\_\{\\ell\}\|\+1\)^\{2\}\}\\leq\\frac\{16\}\{2^\{\\ell\-1\}\\Delta\_\{\\min\}\},becausea/\(a\+1\)2≤1/4a/\(a\+1\)^\{2\}\\leq 1/4for every integera≥1a\\geq 1\. Combining the early and late parts yields

∑m≥1𝔼​\[∑j∈HℓΔj​Pm,j\]≤32​log⁡\(\|Hℓ\|\+1\)\+182ℓ−1​Δmin\.\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{j\\in H\_\{\\ell\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\\leq\\frac\{32\\log\(\|H\_\{\\ell\}\|\+1\)\+18\}\{2^\{\\ell\-1\}\\Delta\_\{\\min\}\}\.Now sum overℓ≥1\\ell\\geq 1\. Since\|Hℓ\|≤K\|H\_\{\\ell\}\|\\leq KandK≥2K\\geq 2,

∑m≥1𝔼​\[∑j∈\{2,…,K\}Δj≤4​ηΔj​Pm,j\]\\displaystyle\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\\leq 4\\eta\\end\{subarray\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]=∑ℓ≥1Hℓ≠∅∑m≥1𝔼​\[∑j∈HℓΔj​Pm,j\]\\displaystyle=\\sum\_\{\\begin\{subarray\}\{c\}\\ell\\geq 1\\\\ H\_\{\\ell\}\\neq\\varnothing\\end\{subarray\}\}\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{j\\in H\_\{\\ell\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]≤∑ℓ≥1Hℓ≠∅32​log⁡\(\|Hℓ\|\+1\)\+182ℓ−1​Δmin\\displaystyle\\leq\\sum\_\{\\begin\{subarray\}\{c\}\\ell\\geq 1\\\\ H\_\{\\ell\}\\neq\\varnothing\\end\{subarray\}\}\\frac\{32\\log\(\|H\_\{\\ell\}\|\+1\)\+18\}\{2^\{\\ell\-1\}\\Delta\_\{\\min\}\}≤1Δmin​∑ℓ≥132​log⁡\(K\+1\)\+182ℓ−1\\displaystyle\\leq\\frac\{1\}\{\\Delta\_\{\\min\}\}\\sum\_\{\\ell\\geq 1\}\\frac\{32\\log\(K\+1\)\+18\}\{2^\{\\ell\-1\}\}≤64​log⁡\(K\+1\)\+36Δmin\\displaystyle\\leq\\frac\{64\\log\(K\+1\)\+36\}\{\\Delta\_\{\\min\}\}≤200​log⁡KΔmin,\\displaystyle\\leq 200\\frac\{\\log K\}\{\\Delta\_\{\\min\}\},\(5\)where the last inequality uses[\(v\)](https://arxiv.org/html/2605.29148#S5.I1.i5)in[Lemma2](https://arxiv.org/html/2605.29148#Thmlemma2)and36≤\(36/log⁡2\)​log⁡K≤72​log⁡K36\\leq\(36/\\log 2\)\\log K\\leq 72\\log KforK≥2K\\geq 2\.

#### Large\-gap contribution\.

If there is no gapΔj\>4​η\\Delta\_\{j\}\>4\\eta, then the second sum is trivially bounded by0\. Assume then that there is at least one gapΔj\\Delta\_\{j\}such thatΔj\>4​η\\Delta\_\{j\}\>4\\eta\. Form≥0m\\geq 0andj≥2j\\geq 2, define

For the large\-gap actionsjjwithΔj\>4​η\\Delta\_\{j\}\>4\\eta, define

Zm=1\+∑j∈\{2,…,K\}Δj\>4​ηe−η​Dm,j\.Z\_\{m\}=1\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}e^\{\-\\eta D\_\{m,j\}\}\.Also define the random weights

Qm,1=1Zm,Qm,j=e−η​Dm,jZmfor​j∈\{2,…,K\}​with​Δj\>4​η\.Q\_\{m,1\}=\\frac\{1\}\{Z\_\{m\}\},\\qquad Q\_\{m,j\}=\\frac\{e^\{\-\\eta D\_\{m,j\}\}\}\{Z\_\{m\}\}\\quad\\text\{for \}j\\in\\\{2,\\ldots,K\\\}\\text\{ with \}\\Delta\_\{j\}\>4\\eta\.Finally define the random large\-gap weighted gap

Vm=∑j∈\{2,…,K\}Δj\>4​ηΔj​Qm,j\.V\_\{m\}=\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}Q\_\{m,j\}\.Notice that

Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j=1,∑j∈\{2,…,K\}Δj\>4​ηQm,j≤1\.Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}=1,\\qquad\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\leq 1\.For every large\-gap actionjj, the denominator definingPm,jP\_\{m,j\}contains all terms appearing inZmZ\_\{m\}and possibly more positive terms\. Thus

Pm,j≤Qm,jfor every​m≥1​and every​j​with​Δj\>4​η,P\_\{m,j\}\\leq Q\_\{m,j\}\\qquad\\text\{for every \}m\\geq 1\\text\{ and every \}j\\text\{ with \}\\Delta\_\{j\}\>4\\eta,which implies

∑m≥1∑j∈\{2,…,K\}Δj\>4​ηΔj​Pm,j≤∑m≥1∑j∈\{2,…,K\}Δj\>4​ηΔj​Qm,j≤∑m≥0∑j∈\{2,…,K\}Δj\>4​ηΔj​Qm,j=∑m≥0Vm,\\sum\_\{m\\geq 1\}\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}P\_\{m,j\}\\leq\\sum\_\{m\\geq 1\}\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}Q\_\{m,j\}\\leq\\sum\_\{m\\geq 0\}\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}Q\_\{m,j\}=\\sum\_\{m\\geq 0\}V\_\{m\},and hence, taking expectations, noticing that all the addends are positive, and using Tonelli’s theorem twice, we get

∑m≥1𝔼​\[∑j∈\{2,…,K\}Δj\>4​ηΔj​Pm,j\]≤∑m≥0𝔼​\[Vm\]\.\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\\leq\\sum\_\{m\\geq 0\}\\mathbb\{E\}\[V\_\{m\}\]\.We now prove that

∑m≥0𝔼​\[Vm\]≤4​log⁡Kη,\\sum\_\{m\\geq 0\}\\mathbb\{E\}\[V\_\{m\}\]\\leq 4\\frac\{\\log K\}\{\\eta\},to obtain

∑m≥1𝔼​\[∑j∈\{2,…,K\}Δj\>4​ηΔj​Pm,j\]≤4​log⁡Kη\.\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\\leq 4\\frac\{\\log K\}\{\\eta\}\.\(6\)
Form≥0m\\geq 0and every large\-gap actionjj, set

Ym\+1,j=Xm\+1,j−Xm\+1,1\.Y\_\{m\+1,j\}=X\_\{m\+1,j\}\-X\_\{m\+1,1\}\.Then

Dm\+1,j=Dm,j\+Ym\+1,j,Ym\+1,j∈\[−1,1\],𝔼​\[Ym\+1,j\]=Δj\.D\_\{m\+1,j\}=D\_\{m,j\}\+Y\_\{m\+1,j\},\\qquad Y\_\{m\+1,j\}\\in\[\-1,1\],\\qquad\\mathbb\{E\}\[Y\_\{m\+1,j\}\]=\\Delta\_\{j\}\.Form=0m=0,ℱ0\\mathcal\{F\}\_\{0\}is the trivial sigma\-algebra\. Letℱm=σ​\(X1,…,Xm\)\\mathcal\{F\}\_\{m\}=\\sigma\(X\_\{1\},\\ldots,X\_\{m\}\)\. The weightsQm,jQ\_\{m,j\}andZmZ\_\{m\}areℱm\\mathcal\{F\}\_\{m\}\-measurable\. Moreover, since the loss vectors are i\.i\.d\.,Xm\+1X\_\{m\+1\}is independent ofℱm\\mathcal\{F\}\_\{m\}, and thereforeYm\+1,jY\_\{m\+1,j\}is independent ofℱm\\mathcal\{F\}\_\{m\}for everyj∈\[K\]j\\in\[K\]\.

Using

Zm\+1Zm=Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​exp⁡\(−η​Ym\+1,j\),\\frac\{Z\_\{m\+1\}\}\{Z\_\{m\}\}=Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\exp\(\-\\eta Y\_\{m\+1,j\}\),and the concavity of the logarithm, conditional Jensen gives

𝔼​\[log⁡Zm\+1−log⁡Zm∣ℱm\]\\displaystyle\\mathbb\{E\}\\left\[\\log Z\_\{m\+1\}\-\\log Z\_\{m\}\\mid\\mathcal\{F\}\_\{m\}\\right\]=𝔼​\[log⁡\(Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​exp⁡\(−η​Ym\+1,j\)\)∣ℱm\]\\displaystyle=\\mathbb\{E\}\\left\[\\log\\left\(Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\exp\(\-\\eta Y\_\{m\+1,j\}\)\\right\)\\mid\\mathcal\{F\}\_\{m\}\\right\]≤log⁡𝔼​\[Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​exp⁡\(−η​Ym\+1,j\)∣ℱm\]\\displaystyle\\leq\\log\\mathbb\{E\}\\left\[Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\exp\(\-\\eta Y\_\{m\+1,j\}\)\\mid\\mathcal\{F\}\_\{m\}\\right\]=log⁡\(Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​𝔼​\[exp⁡\(−η​Ym\+1,j\)∣ℱm\]\)\\displaystyle=\\log\\left\(Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\mathbb\{E\}\\left\[\\exp\(\-\\eta Y\_\{m\+1,j\}\)\\mid\\mathcal\{F\}\_\{m\}\\right\]\\right\)=log⁡\(Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​𝔼​\[exp⁡\(−η​Ym\+1,j\)\]\)\.\\displaystyle=\\log\\left\(Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\mathbb\{E\}\\left\[\\exp\(\-\\eta Y\_\{m\+1,j\}\)\\right\]\\right\)\.
For each large\-gap actionjj, Hoeffding’s lemma\[[1](https://arxiv.org/html/2605.29148#bib.bib1), Lemma 2\.2\]for a random variable in an interval of length22gives

𝔼​\[e−η​Ym\+1,j\]≤exp⁡\(−η​Δj\+η22\)\.\\mathbb\{E\}\[e^\{\-\\eta Y\_\{m\+1,j\}\}\]\\leq\\exp\\left\(\-\\eta\\Delta\_\{j\}\+\\frac\{\\eta^\{2\}\}\{2\}\\right\)\.SinceΔj\>4​η\\Delta\_\{j\}\>4\\eta, we haveη2/2≤η​Δj/8\\eta^\{2\}/2\\leq\\eta\\Delta\_\{j\}/8\. Thus

𝔼​\[e−η​Ym\+1,j\]≤exp⁡\(−7​η​Δj8\)\.\\mathbb\{E\}\[e^\{\-\\eta Y\_\{m\+1,j\}\}\]\\leq\\exp\\left\(\-\\frac\{7\\eta\\Delta\_\{j\}\}\{8\}\\right\)\.BecauseΔj≤1\\Delta\_\{j\}\\leq 1andη≤1/8\\eta\\leq 1/8, the numberη​Δj\\eta\\Delta\_\{j\}belongs to\[0,1\]\[0,1\]\. Using[\(ii\)](https://arxiv.org/html/2605.29148#S5.I1.i2)in[Lemma2](https://arxiv.org/html/2605.29148#Thmlemma2)withx=7​η​Δj/8x=7\\eta\\Delta\_\{j\}/8gives

exp⁡\(−7​η​Δj8\)≤1−7​η​Δj16≤1−η​Δj4\.\\exp\\left\(\-\\frac\{7\\eta\\Delta\_\{j\}\}\{8\}\\right\)\\leq 1\-\\frac\{7\\eta\\Delta\_\{j\}\}\{16\}\\leq 1\-\\frac\{\\eta\\Delta\_\{j\}\}\{4\}\.Consequently,

Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​𝔼​\[e−η​Ym\+1,j\]\\displaystyle Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\mathbb\{E\}\[e^\{\-\\eta Y\_\{m\+1,j\}\}\]≤Qm,1\+∑j∈\{2,…,K\}Δj\>4​ηQm,j​\(1−η​Δj4\)=1−η​Vm4\.\\displaystyle\\leq Q\_\{m,1\}\+\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\\{2,\\dots,K\\\}\\\\ \\Delta\_\{j\}\>4\\eta\\end\{subarray\}\}Q\_\{m,j\}\\left\(1\-\\frac\{\\eta\\Delta\_\{j\}\}\{4\}\\right\)=1\-\\frac\{\\eta V\_\{m\}\}\{4\}\.SinceQm,j≥0Q\_\{m,j\}\\geq 0, since

Qm,1\+∑j:Δj\>4​ηQm,j=1,Q\_\{m,1\}\+\\sum\_\{j:\\Delta\_\{j\}\>4\\eta\}Q\_\{m,j\}=1,and since0≤Δj≤10\\leq\\Delta\_\{j\}\\leq 1, we have

0≤Vm=∑j:Δj\>4​ηΔj​Qm,j≤∑j:Δj\>4​ηQm,j≤1\.0\\leq V\_\{m\}=\\sum\_\{j:\\Delta\_\{j\}\>4\\eta\}\\Delta\_\{j\}Q\_\{m,j\}\\leq\\sum\_\{j:\\Delta\_\{j\}\>4\\eta\}Q\_\{m,j\}\\leq 1\.Hence, becauseη≤1/8\\eta\\leq 1/8,

0≤η​Vm4≤η4≤132<1\.0\\leq\\frac\{\\eta V\_\{m\}\}\{4\}\\leq\\frac\{\\eta\}\{4\}\\leq\\frac\{1\}\{32\}<1\.By[\(iii\)](https://arxiv.org/html/2605.29148#S5.I1.i3)of Lemma 2, applied withu=η​Vm/4u=\\eta V\_\{m\}/4, we get

log⁡\(1−η​Vm4\)≤−η​Vm4\.\\log\\left\(1\-\\frac\{\\eta V\_\{m\}\}\{4\}\\right\)\\leq\-\\frac\{\\eta V\_\{m\}\}\{4\}\.Combining the previous displays gives

𝔼​\[log⁡Zm\+1−log⁡Zm∣ℱm\]≤−η​Vm4\.\\mathbb\{E\}\[\\log Z\_\{m\+1\}\-\\log Z\_\{m\}\\mid\\mathcal\{F\}\_\{m\}\]\\leq\-\\frac\{\\eta V\_\{m\}\}\{4\}\.Taking expectations,

𝔼​\[log⁡Zm\+1\]−𝔼​\[log⁡Zm\]≤−η4​𝔼​\[Vm\]\.\\mathbb\{E\}\[\\log Z\_\{m\+1\}\]\-\\mathbb\{E\}\[\\log Z\_\{m\}\]\\leq\-\\frac\{\\eta\}\{4\}\\mathbb\{E\}\[V\_\{m\}\]\.Summing fromm=0m=0toNNyields

η4​∑m=0N𝔼​\[Vm\]≤𝔼​\[log⁡Z0\]−𝔼​\[log⁡ZN\+1\]\.\\frac\{\\eta\}\{4\}\\sum\_\{m=0\}^\{N\}\\mathbb\{E\}\[V\_\{m\}\]\\leq\\mathbb\{E\}\[\\log Z\_\{0\}\]\-\\mathbb\{E\}\[\\log Z\_\{N\+1\}\]\.SinceZN\+1≥1Z\_\{N\+1\}\\geq 1, we havelog⁡ZN\+1≥0\\log Z\_\{N\+1\}\\geq 0\. SinceD0,j=0D\_\{0,j\}=0,

Z0=1\+\|\{j∈\{2,…,K\}:Δj\>4​η\}\|≤K\.Z\_\{0\}=1\+\\left\|\\\{j\\in\\\{2,\\ldots,K\\\}:\\Delta\_\{j\}\>4\\eta\\\}\\right\|\\leq K\.Thus

η4​∑m=0N𝔼​\[Vm\]≤log⁡K\.\\frac\{\\eta\}\{4\}\\sum\_\{m=0\}^\{N\}\\mathbb\{E\}\[V\_\{m\}\]\\leq\\log K\.LettingN→∞N\\to\\inftygives \([6](https://arxiv.org/html/2605.29148#S5.E6)\)\.

Combining \([5\.4](https://arxiv.org/html/2605.29148#S5.Ex72)\) and \([6](https://arxiv.org/html/2605.29148#S5.E6)\) proves the lemma\. ∎

### 5\.5Proof of the main theorem

###### Proof of[Theorem1](https://arxiv.org/html/2605.29148#Thmtheorem1)\.

Privacy follows from[Proposition1](https://arxiv.org/html/2605.29148#Thmproposition1)\. For regret, combine[Lemma4](https://arxiv.org/html/2605.29148#Thmlemma4)and[Lemma5](https://arxiv.org/html/2605.29148#Thmlemma5):

RegT≤1\+4​∑m≥1Fm≤1\+800​log⁡KΔmin\+16​log⁡Kη\.\\displaystyle\\operatorname\{Reg\}\_\{T\}\\leq 1\+4\\sum\_\{m\\geq 1\}F\_\{m\}\\leq 1\+00\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+6\\frac\{\\log K\}\{\\eta\}\.This proves \([1](https://arxiv.org/html/2605.29148#S4.E1)\)\. It remains only to express the bound in terms ofε\\varepsilon\.

Ifε≤1/4\\varepsilon\\leq 1/4, thenη=ε/2\\eta=\\varepsilon/2, and hence

16​log⁡Kη=32​log⁡Kε\.16\\frac\{\\log K\}\{\\eta\}=32\\frac\{\\log K\}\{\\varepsilon\}\.SinceK≥2K\\geq 2andΔmin≤1\\Delta\_\{\\min\}\\leq 1,

1≤1log⁡2​log⁡KΔmin≤2​log⁡KΔmin\.1\\leq\\frac\{1\}\{\\log 2\}\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\\leq 2\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\.Therefore

RegT≤802​log⁡KΔmin\+32​log⁡Kε≤1000​\(log⁡KΔmin\+log⁡Kε\)\.\\operatorname\{Reg\}\_\{T\}\\leq 802\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+32\\frac\{\\log K\}\{\\varepsilon\}\\leq 1000\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\\right\)\.
Ifε\>1/4\\varepsilon\>1/4, thenη=1/8\\eta=1/8, and hence

16​log⁡Kη=128​log⁡K≤128​log⁡KΔmin\.16\\frac\{\\log K\}\{\\eta\}=128\\log K\\leq 128\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\.Again1≤2​log⁡K/Δmin1\\leq 2\\log K/\\Delta\_\{\\min\}\. Thus

RegT≤930​log⁡KΔmin≤1000​\(log⁡KΔmin\+log⁡Kε\)\.\\operatorname\{Reg\}\_\{T\}\\leq 930\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\\leq 1000\\left\(\\frac\{\\log K\}\{\\Delta\_\{\\min\}\}\+\\frac\{\\log K\}\{\\varepsilon\}\\right\)\.This proves \([2](https://arxiv.org/html/2605.29148#S4.E2)\), and concludes the proof\. ∎

## 6Why the Extra Logarithm Disappears

Wu and Wang \[[10](https://arxiv.org/html/2605.29148#bib.bib10)\]build on the dyadic report\-noisy\-max/follow\-the\-noisy\-leader algorithm ofHuet al\.\[[5](https://arxiv.org/html/2605.29148#bib.bib8)\]\. The algorithm ofHuet al\.\[[5](https://arxiv.org/html/2605.29148#bib.bib8)\]accumulates losses over an epoch and then uses report\-noisy\-max with Laplace noise to choose the action played in the next epoch\. The analysis ofWu and Wang \[[10](https://arxiv.org/html/2605.29148#bib.bib10)\]removes the horizon dependence from the regret bound, but their proof still controls suboptimal actions separately through pairwise tail bounds\. In the large\-gap privacy\-dominated regime, their per\-action accounting produces a harmonic summation over action indices, which yields the extra factorlog⁡K\\log Kin their privacy term\.

Our randomized\-prefix proof removes the per\-action accounting\. After reducing the analysis from played rounds to block actions, the regret contribution of the privacy\-dominated actions becomes a prefix\-length sum of softmax errors:

∑m≥1𝔼​\[∑j:Δj\>4​ηΔj​Pm,j\]\.\\sum\_\{m\\geq 1\}\\mathbb\{E\}\\left\[\\sum\_\{j:\\Delta\_\{j\}\>4\\eta\}\\Delta\_\{j\}P\_\{m,j\}\\right\]\.We control this prefix\-length softmax sum through the restricted softmax potentiallog⁡Zm\\log Z\_\{m\}, rather than by separate tail bounds for each action\. The potential argument telescopes overmm, and the whole large\-gap contribution is paid by the initial value

log⁡Z0≤log⁡K,\\log Z\_\{0\}\\leq\\log K,divided by the privacy scaleη\\eta\.

Consequently, our privacy term is of orderlog⁡K/η\\log K/\\eta, and hencelog⁡K/ε\\log K/\\varepsilon, rather thanlog2⁡K/ε\\log^\{2\}K/\\varepsilon\. The random prefix is the mechanism behind the improvement: it turns the dyadic block regret into a prefix\-length sum of softmax errors, and the potential argument controls this sum without action\-by\-action tail bounds\.

## 7Conclusion

The randomized\-prefix clock turns the analysis of the dyadic private online\-learning algorithm into a prefix\-length sum of softmax errors\. This small change exposes an entropy potential that controls all large\-gap actions simultaneously, giving the optimallog⁡K/ε\\log K/\\varepsilonprivacy cost instead of thelog2⁡K/ε\\log^\{2\}K/\\varepsiloncost left by previous stochastic analyses\. Together with the known lower bound, the result gives the optimal gap\-dependent rate for pure\-DP stochastic decision\-theoretic online learning, up to the trivial cap by the horizon\.

## References

- \[1\]S\. Boucheron, G\. Lugosi, and P\. Massart\(2013\-02\)Concentration inequalities: a nonasymptotic theory of independence\.Oxford University Press\.External Links:ISBN 9780199535255,[Document](https://dx.doi.org/10.1093/acprof%3Aoso/9780199535255.001.0001),[Link](https://doi.org/10.1093/acprof:oso/9780199535255.001.0001)Cited by:[§5\.4](https://arxiv.org/html/2605.29148#S5.SS4.SSS0.Px2.p4.2)\.
- \[2\]C\. Dwork\(2006\)Differential privacy\. automata, languages and programming\.Springer, Berlin\.Cited by:[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px2.p1.1)\.
- \[3\]Y\. Freund and R\. E\. Schapire\(1997\)A decision\-theoretic generalization of on\-line learning and an application to boosting\.Journal of computer and system sciences55\(1\),pp\. 119–139\.Cited by:[§1](https://arxiv.org/html/2605.29148#S1.p1.2),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px1.p1.1)\.
- \[4\]W\. Hoeffding\(1963\)Probability inequalities for sums of bounded random variables\.Journal of the American statistical association58\(301\),pp\. 13–30\.Cited by:[§5\.1](https://arxiv.org/html/2605.29148#S5.SS1.1.p1.5)\.
- \[5\]B\. Hu, Z\. Huang, N\. A\. Mehta, and N\. Hegde\(2021\)Near\-optimal algorithms for differentially private online learning in a stochastic environment\.arXiv preprint arXiv:2102\.07929\.Cited by:[§1](https://arxiv.org/html/2605.29148#S1.SS0.SSS0.Px1.p1.2),[§1](https://arxiv.org/html/2605.29148#S1.p2.3),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px3.p1.3),[§6](https://arxiv.org/html/2605.29148#S6.p1.1),[Corollary 1](https://arxiv.org/html/2605.29148#Thmcorollary1.p1.1.1)\.
- \[6\]B\. Hu and N\. A\. Mehta\(2024\-30 Jun–03 Jul\)Open problem: optimal rates for stochastic decision\-theoretic online learning under differentially privacy\.InProceedings of Thirty Seventh Conference on Learning Theory,S\. Agrawal and A\. Roth \(Eds\.\),Proceedings of Machine Learning Research, Vol\.247,pp\. 5330–5334\.External Links:[Link](https://proceedings.mlr.press/v247/hu24a.html)Cited by:[§1](https://arxiv.org/html/2605.29148#S1.SS0.SSS0.Px1.p1.2),[§1](https://arxiv.org/html/2605.29148#S1.p2.1),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px3.p1.2),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px5.p1.2)\.
- \[7\]W\. Kotłowski\(2018\)On minimaxity of follow the leader strategy in the stochastic setting\.Theoretical Computer Science742,pp\. 50–65\.Cited by:[§1](https://arxiv.org/html/2605.29148#S1.p1.2),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px1.p1.1)\.
- \[8\]F\. McSherry and K\. Talwar\(2007\)Mechanism design via differential privacy\.In48th Annual IEEE Symposium on Foundations of Computer Science \(FOCS’07\),pp\. 94–103\.Cited by:[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px2.p1.1)\.
- \[9\]J\. Mourtada and S\. Gaïffas\(2019\)On the optimality of the hedge algorithm in the stochastic regime\.Journal of Machine Learning Research20\(83\),pp\. 1–28\.Cited by:[§1](https://arxiv.org/html/2605.29148#S1.p1.2),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px1.p1.1)\.
- \[10\]R\. Wu and Y\. Wang\(2026\-23–26 Feb\)Improved regret in stochastic decision\-theoretic online learning under differential privacy\.InProceedings of The 37th International Conference on Algorithmic Learning Theory,M\. Telgarsky and J\. Ullman \(Eds\.\),Proceedings of Machine Learning Research, Vol\.313,pp\. 1–22\.External Links:[Link](https://proceedings.mlr.press/v313/wu26a.html)Cited by:[§1](https://arxiv.org/html/2605.29148#S1.p2.1),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px4.p1.3),[§2](https://arxiv.org/html/2605.29148#S2.SS0.SSS0.Px5.p1.2),[§6](https://arxiv.org/html/2605.29148#S6.p1.1),[Remark 1](https://arxiv.org/html/2605.29148#Thmremark1),[Remark 1](https://arxiv.org/html/2605.29148#Thmremark1.p1.3)\.