Information Routing across Batch Boundaries: Memory--Batch Tradeoffs in Lipschitz Bandits

# Memory–Batch Tradeoffs in Lipschitz Bandits
Source: [https://arxiv.org/html/2608.07922](https://arxiv.org/html/2608.07922)
## Information Routing across Batch Boundaries: Memory–Batch Tradeoffs in Lipschitz Bandits

Zengfeng Huang Fudan University Shanghai Innovation Institute Shanghai, China huangzf@fudan\.edu\.cnCorresponding author\.

###### Abstract

Adaptive learning needs both a state that preserves what observations imply and opportunities to act on that state\. We study this width–depth tradeoff in stochastic Lipschitz bandits\. After each pull, the learner retains at mostWWbits of live reward\-dependent state and organizes its pulls into at mostBBcommitted batches\. ForW≳dlog⁡\(e​T\)W\\gtrsim\_\{d\}\\log\(eT\), we characterize minimax expected pseudo\-regret up to logarithmic factors; the lower bounds hold for everyWW\. Besides the classical sequential and unrestricted\-memory batch costs, the frontier contains the new penalty

Td\+2d\+3​\(1\+\(B−1\)​W\)−1d​\(d\+3\),T^\{\\frac\{d\+2\}\{d\+3\}\}\\bigl\(1\+\(B\-1\)W\\bigr\)^\{\-\\frac\{1\}\{d\(d\+3\)\}\},proving that state width and update depth are not interchangeable\. The interaction is an information\-routing constraint: at regional scaless, low regret forces the committed action transcript to encodeΘd​\(s−d\)\\Theta\_\{d\}\(s^\{\-d\}\)regional decisions, while the collected boundary states carry at most\(B−1\)​W\(B\-1\)Wbits of entropy\. Matching policies stream and erase verification statistics while retaining a mask of a safe active set, either in memory or fragment by fragment\. The theorem recovers the full\-dimensional worst\-case batch\-only frontier and logarithmic\-memory achievability in the fully sequential specialization; static batch boundaries match predictable adaptive ones\.

## 1Introduction

Sequential decision making is adaptive because observations are summarized into a reward\-dependent state that determines later experiments\. Two resources govern this feedback loop: how much learned information can persist, and how often that information can be converted into a new sampling rule\. Standard sequential bandit models leave both unrestricted, whereas batched, finite\-memory, and joint resource models constrain one or both\(Perchetet al\.,[2016](https://arxiv.org/html/2608.07922#bib.bib10); Cover,[1968](https://arxiv.org/html/2608.07922#bib.bib17); Liauet al\.,[2018](https://arxiv.org/html/2608.07922#bib.bib19); Huanget al\.,[2026](https://arxiv.org/html/2608.07922#bib.bib25)\)\. A learner may therefore have a wide state but few opportunities to use it, or many update opportunities but only a narrow state\. Understanding their joint value is a structural question about adaptivity, rather than merely an implementation detail\.

We study this question in stochastic Lipschitz bandits, a canonical nonparametric optimization problem\. The action space is𝒳=\[0,1\]d\\mathcal\{X\}=\[0,1\]^\{d\}, and the unknown mean rewardf:𝒳→\[0,1\]f:\\mathcal\{X\}\\to\[0,1\]is one\-Lipschitz in the sup norm\. At roundtt, the learner pullsAt∈𝒳A\_\{t\}\\in\\mathcal\{X\}, observes a bounded reward of meanf​\(At\)f\(A\_\{t\}\), and incurs pseudo\-regret

RegT​\(f\):=∑t=1T\(f⋆−f​\(At\)\),f⋆:=supx∈𝒳f​\(x\)\.\\mathrm\{Reg\}\_\{T\}\(f\):=\\sum\_\{t=1\}^\{T\}\\bigl\(f^\{\\star\}\-f\(A\_\{t\}\)\\bigr\),\\qquad f^\{\\star\}:=\\sup\_\{x\\in\\mathcal\{X\}\}f\(x\)\.With unrestricted sequential adaptation, the minimax rate isΘ~d​\(T\(d\+1\)/\(d\+2\)\)\\widetilde\{\\Theta\}\_\{d\}\(T^\{\(d\+1\)/\(d\+2\)\}\)\(Agrawal,[1995](https://arxiv.org/html/2608.07922#bib.bib1); Kleinberg,[2004](https://arxiv.org/html/2608.07922#bib.bib2); Aueret al\.,[2007](https://arxiv.org/html/2608.07922#bib.bib3); Bubecket al\.,[2011](https://arxiv.org/html/2608.07922#bib.bib6)\)\. This rate balances the number of spatial locations at a given resolution with the samples needed to test each location: accuracyrrcreates orderr−dr^\{\-d\}candidate regions, while a local test costs orderr−2r^\{\-2\}samples\.

Our learner retains at mostWWbits of complete mutable reward\-dependent state after every pull\. Its actions are divided into at mostBBbatches\. At a batch boundary, the current state commits both the next batch boundary and the entire within\-batch action tape\. Rewards arriving inside the batch may update the state online, but they cannot alter pulls that were already committed\. There is no additional reward\-dependent workspace, batch buffer, or accumulating external transcript\. Only reward\-dependent state that reaches a boundary can alter later experiments\. ThusWWcontrols the*state width*, whileBBcontrols the*update depth*of the feedback–action loop\.

The two one\-resource specializations are understood separately\. Removing the memory cap gives standard batched Lipschitz bandits, for whichFenget al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib15)\)identify theΘd​\(log⁡log⁡T\)\\Theta\_\{d\}\(\\log\\log T\)threshold for attaining the sequential rate\. TakingB=TB=Tgives fully sequential finite\-state learning, for whichZhu and Huang \([2025](https://arxiv.org/html/2608.07922#bib.bib16)\)show that logarithmic memory is both sufficient and necessary for optimal Lipschitz regret; see alsoLiet al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib38)\)\. These results do not determine the joint frontier: the batch\-only model may preserve an arbitrarily detailed history, whereas the memory\-only model may act on its state after every sample\. Nor can the two resources be collapsed into their product\. The same boundary\-state entropy budget can be arranged as a few wide states or many narrow updates, and these arrangements need not support the same sequence of refinements\. For finitely many arms,Huanget al\.\([2026](https://arxiv.org/html/2608.07922#bib.bib25)\)study essentially the same persistent\-state/committed\-batch interface and show that near\-minimax regret forces a thresholded sampling profile to revealΘ​\(K\)\\Theta\(K\)bits about a hidden good\-arm membership vector\. The continuum is different because the number of relevant routing coordinates is not fixed in advance: it grows with the target resolution\.

Lipschitz optimization makes this distinction unavoidable\. A finite\-dimensional parametric class may admit one compact global estimate\. A generic Lipschitz function can instead hide independent local alternatives inΘd​\(s−d\)\\Theta\_\{d\}\(s^\{\-d\}\)separated regions at spatial resolutionss\. As the target resolution becomes finer, the learner must not only acquire more evidence; it must also preserve a growing collection of decisions about where future experiments should be sent\. We call this causal transport of reward\-dependent decisions across batch boundaries*information routing*\. This leads to our central question:*how do state width and update depth jointly determine minimax regret?*

###### Theorem 1\.1\(Informal frontier\)\.

Ignoring logarithmic factors, regret is governed by the worst of three barriers: ordinary Lipschitz estimation, being restricted to at mostBBcommitted batches, and the new width–depth interaction

Td\+2d\+3​\(1\+\(B−1\)​W\)−1d​\(d\+3\)\.T^\{\\frac\{d\+2\}\{d\+3\}\}\\bigl\(1\+\(B\-1\)W\\bigr\)^\{\-\\frac\{1\}\{d\(d\+3\)\}\}\.The lower bound holds for every memory budget\. Once the live state can store ordinary counters and confidence estimates—Od​\(log⁡T\)O\_\{d\}\(\\log T\)bits—matching policies exist with static batch boundaries\.

The new joint penalty is the main point\. Memory and batches are complements, not substitutes: one wide state used by very few future experiments cannot in general replace a sequence of narrower states recomputed between rounds of exploration\. The product\(B−1\)​W\(B\-1\)Wappears because the successive nonterminal boundary states carry at most that many bits in total, whereasBBseparately controls when newly learned information can change the experiment\. The formal rate, including the unrestricted\-memoryBB\-batch branch, is stated in Section[3\.3](https://arxiv.org/html/2608.07922#S3.SS3)\.

This gives a simple threshold picture\. Near\-sequential performance needs on the order oflog⁡log⁡T\\log\\log Tbatches and enough information in the boundary states to distinguish roughlyTd/\(d\+2\)T^\{d/\(d\+2\)\}relevant regions; onceW≳dlog⁡\(e​T\)W\\gtrsim\_\{d\}\\log\(eT\), these requirements are also sufficient up to logarithmic factors\. With unrestricted memory, the theorem gives the full\-dimensional worst\-case frontier for every batch budget\. When every pull forms its own batch, it recovers sequential minimax regret with logarithmic memory\. The sharper zooming\-dimension results and the sequentialΩ​\(log⁡T\)\\Omega\(\\log T\)instantaneous\-memory lower bound remain complementary; see Section[2](https://arxiv.org/html/2608.07922#S2)\. Predictable adaptive boundaries do not improve the worst\-case order over static ones\.

#### Contributions\.

- •We characterize, up to logarithmic factors, the joint memory–batch frontier once the live state is logarithmic inTT, with lower bounds for every memory budget\. The policy class specializes exactly to the batch\-only and fully sequential finite\-memory models; the theorem recovers the full\-dimensional worst\-case batch frontier and sequential logarithmic\-memory achievability\.
- •We give one regional hard family with two independent requirements\. The horizon limits how many local alternatives can be verified, while the boundary states limit how many resulting regional decisions can guide later experiments\. The same family yields the classical sequential term and the new joint penalty\.
- •We give matching policies with static batch boundaries\. Verification statistics are streamed and erased; the only scale\-dependent persistent object is an active\-set mask, maintained either in memory or regenerated and consumed in memory\-sized fragments\.

### 1\.1Technical overview: what must persist across a boundary

The proof asks which reward\-dependent decisions must remain available when a future batch is committed\. At regional scaless, the relevant decision is which regions remain eligible for verification at a finer scalerr\. The verification statistics can be processed and discarded, but the resulting regional decisions must reach a boundary before they can alter future pulls\. The lower bound proves that any low\-regret transcript encodes these decisions; the upper bound stores them in an active\-set mask of matching spatial order\.

Two direct strategies fail for complementary reasons: retaining all verification statistics exceeds the live\-memory budget, while compressing them into one terminal summary comes too late to redirect batches committed before that summary exists\.

#### 1\. Boundary states are the causal bottleneck\.

Condition on the algorithmic seed and writeℱ0:=σ​\(ω\)\\mathcal\{F\}\_\{0\}:=\\sigma\(\\omega\)\. Let𝐌\\mathbf\{M\}be the tuple of nonterminal boundary states collected by the analyst, and let𝖳\\mathsf\{T\}be the committed batch boundaries and action sequence\. The components of𝐌\\mathbf\{M\}are not simultaneously available to the learner\. Conditionally onℱ0\\mathcal\{F\}\_\{0\}, every reward\-dependent choice in𝖳\\mathsf\{T\}factors through this tuple, so for any latent instance variableVVindependent ofℱ0\\mathcal\{F\}\_\{0\},

V⟶𝐌⟶𝖳,I​\(V;𝖳∣ℱ0\)≤H​\(𝐌∣ℱ0\)≤\(B−1\)​W\.V\\longrightarrow\\mathbf\{M\}\\longrightarrow\\mathsf\{T\},\\qquad I\(V;\\mathsf\{T\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq H\(\\mathbf\{M\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\(B\-1\)W\.More locally, the transcript committed through batchjjcontains at most\(j−1\)​W\(j\-1\)Wbits aboutVV\. State width limits how much information can reach one redesign, whileBBseparately limits how many redesigns can occur\. The same factorization bounds the number of terminal transcript realizations and yields a sharper codebook lower bound in the very\-low\-entropy regime\.

#### 2\. One regional family exposes two budgets\.

Fix0<r≤s/160<r\\leq s/16\. The hard family containsm≍ds−dm\\asymp\_\{d\}s^\{\-d\}separated pairs of scale\-ssregions, with one coordinate of the latent routing vector selecting one side of each pair\. Every selected region containsq≍d\(s/r\)dq\\asymp\_\{d\}\(s/r\)^\{d\}disjoint radius\-rrprobes, and distinguishing a local improvement at one probe requiresn≍r−2n\\asymp r^\{\-2\}visits\. Hence

m≍ds−d,m​q≍dr−d,m​q​n≍dr−d−2\.m\\asymp\_\{d\}s^\{\-d\},\\qquad mq\\asymp\_\{d\}r^\{\-d\},\\qquad mqn\\asymp\_\{d\}r^\{\-d\-2\}\.These quantities count latent regional decisions, verification probes, and verification pulls, respectively\. Figure[1](https://arxiv.org/html/2608.07922#S1.F1)shows the geometry\.

\(a\) Regional decisions8​s8sj=1j=1j=2j=2⋯\\cdotsj=mj=mm≍ds−dm\\asymp\_\{d\}s^\{\-d\}\(b\) Verification probesradius\-ssregionk∈\[q\]k\\in\[q\]bump heightr/2r/24​r4rq≍d\(s/r\)d,n≍r−2q\\asymp\_\{d\}\(s/r\)^\{d\},\\qquad n\\asymp r^\{\-2\}Figure 1:One hard family exposes both resource budgets\. Every scale\-sspair contributes one coordinate of the latent routing vector\. A local improvement can occur in any of theq≍d\(s/r\)dq\\asymp\_\{d\}\(s/r\)^\{d\}probes on the selected side, and each probe needsn≍r−2n\\asymp r^\{\-2\}visits to verify\. Comparable exploration on the unselected side incurs gapΘ​\(s\)\\Theta\(s\)\.If regret iso​\(T​r\)o\(Tr\)on every local alternative, a stopped change\-of\-measure argument forces every selected probe to receiveΘ​\(r−2\)\\Theta\(r^\{\-2\}\)visits with constant probability\. Because the probes are disjoint, the horizon must satisfy

r−d−2≲dT,r^\{\-d\-2\}\\lesssim\_\{d\}T,which recovers the sequential resolution floorr≳dT−1/\(d\+2\)r\\gtrsim\_\{d\}T^\{\-1/\(d\+2\)\}\. The same tests also encode the latent regional decisions\. Sending comparable effort to the unselected side of a constant fraction of the pairs costs

m⋅s⋅q⋅n≍ds​r−d−2\.m\\cdot s\\cdot q\\cdot n\\asymp\_\{d\}sr^\{\-d\-2\}\.Regret below bothT​rTrands​r−d−2sr^\{\-d\-2\}therefore lets a decoder recoverV∈\{0,1\}mV\\in\\\{0,1\\\}^\{m\}at constant average Hamming distortion\. Such recovery needsΩ​\(m\)=Ωd​\(s−d\)\\Omega\(m\)=\\Omega\_\{d\}\(s^\{\-d\}\)bits, while the boundary\-state factorization supplies at most\(B−1\)​W\(B\-1\)Wbits\. Thus the regional scale cannot be smaller thans≍d\(1\+\(B−1\)​W\)−1/ds\\asymp\_\{d\}\(1\+\(B\-1\)W\)^\{\-1/d\}\.

#### 3\. The upper bound stores only an active\-set mask\.

At scaless, the algorithm constructs a safe active set that contains a maximizer and excludes regions more thanOd​\(s\)O\_\{d\}\(s\)below optimal\. A fixed radius\-rrrefinement layout then scansOd​\(r−d\)O\_\{d\}\(r^\{\-d\}\)child probes and satisfies

𝔼​RegT​\(f\)≲ds​r−d−2​polylog⁡\(T\)\+T​r\.\\mathbb\{E\}\\mathrm\{Reg\}\_\{T\}\(f\)\\lesssim\_\{d\}sr^\{\-d\-2\}\\operatorname\{polylog\}\(T\)\+Tr\.Each verification estimate is accumulated online, compared with one resident best\-arm record, and erased\. The active\-set mask is the only scale\-dependent persistent object\. It is not the latent lower\-bound vectorVV, but both haveΘd​\(s−d\)\\Theta\_\{d\}\(s^\{\-d\}\)regional coordinates\. If the mask fits, an in\-memory hierarchy updates all coordinates together\. Otherwise Algorithm[1](https://arxiv.org/html/2608.07922#alg1)regenerates one memory\-sized fragment, uses it immediately to commit the corresponding child probes, updates the resident record, and erases the fragment\. Up to logarithmic control and replay overhead, serialization obeys

mask size≲dfragment width×number of fragments consumed\.\\text\{mask size\}\\ \\lesssim\_\{d\}\\ \\text\{fragment width\}\\times\\text\{number of fragments consumed\}\.

#### 4\. Scale balance and update depth\.

At fixed\(s,r\)\(s,r\), the converse givesmin⁡\{T​r,s​r−d−2\}\\min\\\{Tr,sr^\{\-d\-2\}\\\}, whereas refinement pays the corresponding sum up to logarithmic factors\. Balancing the two terms yields

r≍d\(s/T\)1/\(d\+3\),regret≍dTd\+2d\+3​s1d\+3\.r\\asymp\_\{d\}\(s/T\)^\{1/\(d\+3\)\},\\qquad\\text\{regret\}\\asymp\_\{d\}T^\{\\frac\{d\+2\}\{d\+3\}\}s^\{\\frac\{1\}\{d\+3\}\}\.The horizon imposes the statistical floors≳dT−1/\(d\+2\)s\\gtrsim\_\{d\}T^\{\-1/\(d\+2\)\}, while the boundary\-state entropy budget imposess≳d\(1\+\(B−1\)​W\)−1/ds\\gtrsim\_\{d\}\(1\+\(B\-1\)W\)^\{\-1/d\}\. Evaluating the fixed\-scale regret at the larger floor gives the sequential and memory\-dependent branches of the theorem\. A separate adaptive\-grid obstruction and the matching in\-memory hierarchy produce the unrestricted\-memoryBB\-batch branch: even an arbitrarily wide state cannot be sharpened without enough redesign opportunities\. The frontier is therefore governed by three primitive resources—samples for verification, state for regional routing, and depth for adaptive refinement\.

## 2Related work

#### Continuum\-armed bandits\.

Classical continuum and metric bandits exploit smoothness through uniform covers, hierarchical partitions, optimism, zooming, and near\-optimality dimension\(Agrawal,[1995](https://arxiv.org/html/2608.07922#bib.bib1); Kleinberg,[2004](https://arxiv.org/html/2608.07922#bib.bib2); Aueret al\.,[2007](https://arxiv.org/html/2608.07922#bib.bib3); Kleinberget al\.,[2008](https://arxiv.org/html/2608.07922#bib.bib4); Coquelin and Munos,[2007](https://arxiv.org/html/2608.07922#bib.bib5); Bubecket al\.,[2011](https://arxiv.org/html/2608.07922#bib.bib6); Munos,[2011](https://arxiv.org/html/2608.07922#bib.bib7); Magureanuet al\.,[2014](https://arxiv.org/html/2608.07922#bib.bib8); Podimata and Slivkins,[2021](https://arxiv.org/html/2608.07922#bib.bib9)\)\. Our upper bound uses the same primitives—empirical means, confidence bounds, elimination, and geometric refinement—under a per\-pull memory constraint\. The lower bound adds separated local alternatives for which the committed action transcript must reveal a latent routing vector\.

#### Batched and limited\-adaptivity learning\.

Batched feedback has been studied for finite arms and structured action spaces\(Perchetet al\.,[2016](https://arxiv.org/html/2608.07922#bib.bib10); Gaoet al\.,[2019](https://arxiv.org/html/2608.07922#bib.bib11); Jinet al\.,[2021b](https://arxiv.org/html/2608.07922#bib.bib12); Esfandiariet al\.,[2021](https://arxiv.org/html/2608.07922#bib.bib13); Ruanet al\.,[2021](https://arxiv.org/html/2608.07922#bib.bib14); Hannaet al\.,[2023](https://arxiv.org/html/2608.07922#bib.bib28); Sawarniet al\.,[2024](https://arxiv.org/html/2608.07922#bib.bib27)\)\. The closest unrestricted\-memory continuum result isFenget al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib15)\)\. Their adaptive\-grid lower bound supplies theBB\-dependent exponent in our converse, and their BLiN construction attains the sequential rate withOd​\(log⁡log⁡T\)O\_\{d\}\(\\log\\log T\)batches\. In the full\-dimensional class, the unrestricted\-memory specialization of our model is exactly the batch\-only specialization, and Corollary[3\.6](https://arxiv.org/html/2608.07922#S3.Thmtheorem6)matches the adaptive\-grid lower exponent for everyBB, up to logarithmic factors\. This fixed\-dimensional worst\-case corollary does not replace their zooming\-dimension\-adaptive guarantee\. Our finite\-memory upper bounds use static batch boundaries, so adaptive batch boundaries do not improve the minimax order\. One\-bit\-per\-batch linear bandits instead constrain messages returned at batch boundaries, not the learner’s complete live state\(Lauet al\.,[2026](https://arxiv.org/html/2608.07922#bib.bib40)\)\. More broadly, limited\-round learning treats interaction depth as a resource distinct from sample complexity\(Agarwalet al\.,[2017](https://arxiv.org/html/2608.07922#bib.bib31); Ruanet al\.,[2021](https://arxiv.org/html/2608.07922#bib.bib14)\)\.

#### Memory\-constrained and streaming bandits\.

Finite\-memory bandits bound the number of memory configurations\(Cover,[1968](https://arxiv.org/html/2608.07922#bib.bib17); Cover and Hellman,[1970](https://arxiv.org/html/2608.07922#bib.bib18); Liauet al\.,[2018](https://arxiv.org/html/2608.07922#bib.bib19)\), while arm\-memory and multi\-pass models constrain which arms or observations remain available\(Chaudhuri and Kalyanakrishnan,[2020](https://arxiv.org/html/2608.07922#bib.bib32); Maitiet al\.,[2021](https://arxiv.org/html/2608.07922#bib.bib33); Assadi and Wang,[2020](https://arxiv.org/html/2608.07922#bib.bib20); Agarwalet al\.,[2022](https://arxiv.org/html/2608.07922#bib.bib21); Wang,[2023](https://arxiv.org/html/2608.07922#bib.bib30); Assadi and Wang,[2024](https://arxiv.org/html/2608.07922#bib.bib22)\)\. Related memory–regret tradeoffs appear in prediction with experts, online learning, and streaming bandits\(Srinivaset al\.,[2022](https://arxiv.org/html/2608.07922#bib.bib35); Peng and Zhang,[2023](https://arxiv.org/html/2608.07922#bib.bib36); Peng and Rubinstein,[2023](https://arxiv.org/html/2608.07922#bib.bib37); Jinet al\.,[2021a](https://arxiv.org/html/2608.07922#bib.bib34); Liet al\.,[2023](https://arxiv.org/html/2608.07922#bib.bib29)\)\. For sequential Lipschitz optimization,Liet al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib38)\)give efficient low\-space algorithms, whileZhu and Huang \([2025](https://arxiv.org/html/2608.07922#bib.bib16)\)prove that logarithmic bit memory is both sufficient and necessary for optimal regret\. SettingB=TB=Tin our model recovers the fully sequential specialization and Corollary[3\.7](https://arxiv.org/html/2608.07922#S3.Thmtheorem7)recovers its full\-dimensional logarithmic\-space achievability\. Our joint lower bound does not recover theΩ​\(log⁡T\)\\Omega\(\\log T\)memory threshold because it controls the boundary\-state entropy budget rather than the instantaneous state alone; that sequential lower bound therefore remains complementary\.

#### Joint memory and batch constraints\.

Time–space lower bounds view retained memory as an independent statistical resource\(Raz,[2016](https://arxiv.org/html/2608.07922#bib.bib23); Garget al\.,[2018](https://arxiv.org/html/2608.07922#bib.bib24)\), andShufaroet al\.\([2025](https://arxiv.org/html/2608.07922#bib.bib39)\)study regret as a function of accumulated information\. The closest joint model isHuanget al\.\([2026](https://arxiv.org/html/2608.07922#bib.bib25)\): up to inessential encoding conventions, their finite\-arm learner has the same persistent\-state/committed\-batch interface\. Their hard prior hides aK/2K/2\-element good\-arm set; near\-minimax regret makes a thresholded sampling profile revealΩ​\(K\)\\Omega\(K\)bits about its membership vector, whereas the boundary states transmit onlyO​\(B​W\)O\(BW\)bits\. A localized under\-sampling change\-of\-measure argument and an incumbent–challenger protocol yield a nearly matchingΘ~​\(K/W\)\\widetilde\{\\Theta\}\(K/W\)batch threshold\.

Our theorem object is different\. In the continuum, the numberm≍ds−dm\\asymp\_\{d\}s^\{\-d\}of regional routing coordinates is endogenous, and each coordinate is certified through finerrr\-scale probes\. Optimizing these two resolutions yields the full constrained minimax regret frontier below the near\-sequential threshold, together with an independent unrestricted\-memory update\-depth branch\. The upper bound maintains a safe active\-set mask of the same spatial order, in memory or as regenerated fragments, while streaming and erasing the finer verification statistics\. The termsT​rTrands​r−d−2sr^\{\-d\-2\}quantify missed local improvements and verification misrouted to unselected regions: the converse takes their minimum, while refinement pays their sum\.

## 3Model and minimax frontier

For an integern≥1n\\geq 1, write\[n\]=\{1,…,n\}\[n\]=\\\{1,\\ldots,n\\\}\. Unsubscripted logarithms are natural, whilelog2\\log\_\{2\}is binary\. Relative entropy is measured in nats; Shannon entropy and mutual information are measured in bits\. The symbols≲d\\lesssim\_\{d\},≳d\\gtrsim\_\{d\}, and≍d\\asymp\_\{d\}hide constants depending only ondd, and a tilde additionally hides powers oflog⁡\(e​T\)\\log\(eT\)\. Unless a formal statement fixes them,cd,Cd\>0c\_\{d\},C\_\{d\}\>0denote dimension\-dependent constants that may change from one display to the next\. Define

ℓT:=log⁡\(e​T\)\.\\ell\_\{T\}:=\\log\(eT\)\.\(1\)We use*state width*for the liveWW\-bit state and*update depth*for the batch budgetBB\. The symbolsssandrralways denote the regional and verification scales, respectively\. In the lower bound,VVdenotes a latent routing vector; in the upper bound,𝒞\\mathcal\{C\}denotes a safe active set andZZits binary mask\. These lower\- and upper\-bound objects are kept distinct throughout\.

### 3\.1Memory\-constrained committed\-batch policies

Throughout,𝒳=\[0,1\]d\\mathcal\{X\}=\[0,1\]^\{d\}with the sup norm, andLip1​\(𝒳\)\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)is the class of\[0,1\]\[0,1\]\-valued one\-Lipschitz functions\. Forg:𝒳→ℝg:\\mathcal\{X\}\\to\\mathbb\{R\}, write

Lip​\(g\):=supx≠y\|g​\(x\)−g​\(y\)\|‖x−y‖∞\.\\mathrm\{Lip\}\(g\):=\\sup\_\{x\\neq y\}\\frac\{\|g\(x\)\-g\(y\)\|\}\{\\\|x\-y\\\|\_\{\\infty\}\}\.At roundtt, the learner pullsAt∈𝒳A\_\{t\}\\in\\mathcal\{X\}and observesYt∈\[0,1\]Y\_\{t\}\\in\[0,1\]\. Forf∈Lip1​\(𝒳\)f\\in\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\), let𝔇​\(f\)\\mathfrak\{D\}\(f\)be the collection of Borel Markov kernelsν=\(νx\)x∈𝒳\\nu=\(\\nu\_\{x\}\)\_\{x\\in\\mathcal\{X\}\}on\[0,1\]\[0,1\]satisfying

∫01y​νx​\(d​y\)=f​\(x\)\.\\int\_\{0\}^\{1\}y\\,\\nu\_\{x\}\(dy\)=f\(x\)\.Rewards are conditionally independent withYt∣At=x∼νxY\_\{t\}\\mid A\_\{t\}=x\\sim\\nu\_\{x\}\. Write

f⋆:=supx∈𝒳f​\(x\),Δf​\(x\):=f⋆−f​\(x\),RegT​\(f\):=∑t=1TΔf​\(At\)\.f^\{\\star\}:=\\sup\_\{x\\in\\mathcal\{X\}\}f\(x\),\\qquad\\Delta\_\{f\}\(x\):=f^\{\\star\}\-f\(x\),\\qquad\\mathrm\{Reg\}\_\{T\}\(f\):=\\sum\_\{t=1\}^\{T\}\\Delta\_\{f\}\(A\_\{t\}\)\.
The integersd≥1d\\geq 1,T≥1T\\geq 1,1≤B≤T1\\leq B\\leq T, andW≥0W\\geq 0are known\. The learner has an algorithmic seedω\\omega, independent of the environment and reward noise, and we setℱ0:=σ​\(ω\)\\mathcal\{F\}\_\{0\}:=\\sigma\(\\omega\)\. Conditional onℱ0\\mathcal\{F\}\_\{0\}, all geometric covers, traversals, batch layouts, and numerical schedules are fixed\. We use the public arm

x∘:=\(0,…,0\)∈𝒳x\_\{\\circ\}:=\(0,\\ldots,0\)\\in\\mathcal\{X\}for transcript padding and as a deterministic fallback whenever a construction has not yet recorded a candidate\.

A\(B,W\)\(B,W\)\-policy maintains, after every pull,

Mt∈\{0,1\}W,0≤t≤T,M\_\{t\}\\in\\\{0,1\\\}^\{W\},\\qquad 0\\leq t\\leq T,which is its complete mutable reward\-dependent state\. It uses boundaries

0=τ0<τ1<⋯<τB^=T,B^≤B\.0=\\tau\_\{0\}<\\tau\_\{1\}<\\cdots<\\tau\_\{\\widehat\{B\}\}=T,\\qquad\\widehat\{B\}\\leq B\.At boundaryτb\\tau\_\{b\}, the current stateMτbM\_\{\\tau\_\{b\}\}commits both the next batch boundaryτb\+1\\tau\_\{b\+1\}and every actionAtA\_\{t\}forτb<t≤τb\+1\\tau\_\{b\}<t\\leq\\tau\_\{b\+1\}\. Rewards observed in that batch updateMtM\_\{t\}online, one pull at a time, but cannot change the batch boundary or action tape already committed\. All maps are Borel measurable; Appendix[A](https://arxiv.org/html/2608.07922#A1)gives the complete map\-level definition used in the reconstruction proof\. Apart from the continuum action space, the use of at most rather than exactlyBBbatches, and the explicit bit\-string state, this is the persistent\-state/committed\-batch resource interface ofHuanget al\.\([2026](https://arxiv.org/html/2608.07922#bib.bib25)\)\.

There is no separate persistent reward\-dependent workspace or accumulating external transcript\. A fixed action tape may replay information already encoded in the precedingWW\-bit boundary state, but it is read\-only and cannot record rewards generated after that boundary\. Fixed geometric objects may be regenerated from\(T,B,W,d,ω\)\(T,B,W,d,\\omega\), and arithmetic complexity is unrestricted\. The model includes predictable adaptive batch boundaries: the next boundary and action tape may depend on all earlier rewards through the current memory, but a batch cannot stop in response to rewards observed after it begins\.

Let𝔄B,W\\mathfrak\{A\}\_\{B,W\}be this policy class and define

ℜT​\(B,W\):=inf𝒜∈𝔄B,Wsupf∈Lip1​\(𝒳\)ν∈𝔇​\(f\)𝔼ν,𝒜​RegT​\(f\)\.\\mathfrak\{R\}\_\{T\}\(B,W\):=\\inf\_\{\\mathcal\{A\}\\in\\mathfrak\{A\}\_\{B,W\}\}\\sup\_\{\\begin\{subarray\}\{c\}f\\in\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)\\\\ \\nu\\in\\mathfrak\{D\}\(f\)\\end\{subarray\}\}\\mathbb\{E\}\_\{\\nu,\\mathcal\{A\}\}\\mathrm\{Reg\}\_\{T\}\(f\)\.

### 3\.2Boundary states and committed transcripts

Only states present at boundaries can change future pulls\. Pad unused boundaries by

τ¯b:=\{τb,b<B^,T,b≥B^,M¯b:=\{Mτb,b<B^,M0,b≥B^,b∈\[B−1\]\.\\bar\{\\tau\}\_\{b\}:=\\begin\{cases\}\\tau\_\{b\},&b<\\widehat\{B\},\\\\ T,&b\\geq\\widehat\{B\},\\end\{cases\}\\qquad\\bar\{M\}\_\{b\}:=\\begin\{cases\}M\_\{\\tau\_\{b\}\},&b<\\widehat\{B\},\\\\ M\_\{0\},&b\\geq\\widehat\{B\},\\end\{cases\}\\qquad b\\in\[B\-1\]\.Setτ¯0=0\\bar\{\\tau\}\_\{0\}=0,τ¯B=T\\bar\{\\tau\}\_\{B\}=T, and define

𝐌:=\(M¯1,…,M¯B−1\),𝖳:=\(τ¯1,…,τ¯B−1,A1,…,AT\),χ:=\(B−1\)​W\.\\mathbf\{M\}:=\(\\bar\{M\}\_\{1\},\\ldots,\\bar\{M\}\_\{B\-1\}\),\\qquad\\mathsf\{T\}:=\(\\bar\{\\tau\}\_\{1\},\\ldots,\\bar\{\\tau\}\_\{B\-1\},A\_\{1\},\\ldots,A\_\{T\}\),\\qquad\\chi:=\(B\-1\)W\.The tuple𝐌\\mathbf\{M\}is an analyst’s proof object: its components are not simultaneously available to the learner\. We callχ\\chithe boundary\-state entropy budget\. It upper\-bounds the conditional entropy of this collected boundary\-state tuple; it is not the learner’s operational workspace at any one time\.

For the causal prefix statement, forj∈\[B\]j\\in\[B\]let𝖳\[j\]\\mathsf\{T\}^\{\[j\]\}consist of the batch boundaries committed through batchjjand the action sequence throughτ¯j\\bar\{\\tau\}\_\{j\}, padded afterward byx∘x\_\{\\circ\}\. Thus𝖳\[B\]\\mathsf\{T\}^\{\[B\]\}and𝖳\\mathsf\{T\}contain the same information\.

###### Lemma 3\.2\(Reconstruction from boundary states\)\.

For every fixed policy andj∈\[B\]j\\in\[B\], there is a policy\-dependent Borel map𝖱𝖾𝖼𝒜,j\\mathsf\{Rec\}\_\{\\mathcal\{A\},j\}such that

𝖳\[j\]=𝖱𝖾𝖼𝒜,j​\(ω,M¯1,…,M¯j−1\)almost surely\.\\mathsf\{T\}^\{\[j\]\}=\\mathsf\{Rec\}\_\{\\mathcal\{A\},j\}\(\\omega,\\bar\{M\}\_\{1\},\\ldots,\\bar\{M\}\_\{j\-1\}\)\\qquad\\text\{almost surely\}\.For every fixed seed, its range has cardinality at most2\(j−1\)​W2^\{\(j\-1\)W\}\. In particular,

𝖳=𝖱𝖾𝖼𝒜​\(ω,𝐌\)\\mathsf\{T\}=\\mathsf\{Rec\}\_\{\\mathcal\{A\}\}\(\\omega,\\mathbf\{M\}\)for a Borel map whose conditional range has cardinality at most2χ2^\{\\chi\}\.

LetVVbe a latent instance variable independent ofℱ0\\mathcal\{F\}\_\{0\}\. LetRRbe obtained from𝖳\\mathsf\{T\}and fresh randomization independent of\(V,ω,𝐌,𝖳\)\(V,\\omega,\\mathbf\{M\},\\mathsf\{T\}\)\.

###### Lemma 3\.3\(Boundary\-state information profile\)\.

For everyj∈\[B\]j\\in\[B\],

I​\(V;𝖳\[j\]∣ℱ0\)≤\(j−1\)​W\.I\(V;\\mathsf\{T\}^\{\[j\]\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\(j\-1\)W\.For the terminal transcript, conditionally onℱ0\\mathcal\{F\}\_\{0\}the variables form the Markov chain

V⟶𝐌⟶𝖳⟶R,V\\longrightarrow\\mathbf\{M\}\\longrightarrow\\mathsf\{T\}\\longrightarrow R,and

I​\(V;𝖳,R∣ℱ0\)=I​\(V;𝖳∣ℱ0\)≤H​\(𝐌∣ℱ0\)≤χ\.I\(V;\\mathsf\{T\},R\\mid\\mathcal\{F\}\_\{0\}\)=I\(V;\\mathsf\{T\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq H\(\\mathbf\{M\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\\chi\.In particular,I​\(V;R∣ℱ0\)≤χI\(V;R\\mid\\mathcal\{F\}\_\{0\}\)\\leq\\chi\.

Lemma[3\.2](https://arxiv.org/html/2608.07922#S3.Thmtheorem2)bounds the number of reward\-dependent transcript realizations, while Lemma[3\.3](https://arxiv.org/html/2608.07922#S3.Thmtheorem3)bounds the information available before each redesign\. The lower bound uses the terminal case; the prefix profile records the timing\. Neither statement limits how many times the sampling rule may be redesigned, soBBremains a separate resource\. Appendix[A](https://arxiv.org/html/2608.07922#A1)proves both lemmas\.

### 3\.3Formal frontier and effective regional scale

Put

αd:=d\+1d\+2,βd,B:=αd1−\(d\+2\)−B,\\alpha\_\{d\}:=\\frac\{d\+1\}\{d\+2\},\\qquad\\beta\_\{d,B\}:=\\frac\{\\alpha\_\{d\}\}\{1\-\(d\+2\)^\{\-B\}\},and define

ΨT​\(s\):=Td\+2d\+3​s1d\+3,sstat:=T−1d\+2,smem:=\(1\+χ\)−1d,sT,χ:=sstat∨smem\.\\Psi\_\{T\}\(s\):=T^\{\\frac\{d\+2\}\{d\+3\}\}s^\{\\frac\{1\}\{d\+3\}\},\\qquad s\_\{\\mathrm\{stat\}\}:=T^\{\-\\frac\{1\}\{d\+2\}\},\\qquad s\_\{\\mathrm\{mem\}\}:=\(1\+\\chi\)^\{\-\\frac\{1\}\{d\}\},\\qquad s\_\{T,\\chi\}:=s\_\{\\mathrm\{stat\}\}\\vee s\_\{\\mathrm\{mem\}\}\.\(2\)A direct exponent calculation gives

ΨT​\(sT,χ\)=Tαd∨Td\+2d\+3\(1\+χ\)1d​\(d\+3\)\.\\Psi\_\{T\}\(s\_\{T,\\chi\}\)=T^\{\\alpha\_\{d\}\}\\ \\vee\\ \\frac\{T^\{\\frac\{d\+2\}\{d\+3\}\}\}\{\(1\+\\chi\)^\{\\frac\{1\}\{d\(d\+3\)\}\}\}\.\(3\)Thus the statistical and memory\-dependent branches are two regimes of one fixed\-scale envelope\.

###### Theorem 3\.4\(Memory–batch frontier\)\.

Fixd≥1d\\geq 1\. There exist constantscd,Cd,Td\>0c\_\{d\},C\_\{d\},T\_\{d\}\>0such that, for all integersT≥TdT\\geq T\_\{d\},B∈\[T\]B\\in\[T\], andW≥0W\\geq 0,

ℜT​\(B,W\)≥cd​\[ΨT​\(sT,χ\)∨Tβd,BB2\]\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}\\left\[\\Psi\_\{T\}\(s\_\{T,\\chi\}\)\\ \\vee\\ \\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\\right\]\.\(4\)IfW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\}, then

ℜT​\(B,W\)≤Cd​ℓT​\[ΨT​\(sT,χ\)∨Tβd,BB2\]\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\leq C\_\{d\}\\ell\_\{T\}\\left\[\\Psi\_\{T\}\(s\_\{T,\\chi\}\)\\ \\vee\\ \\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\\right\]\.\(5\)The upper bound is attained with static batch boundaries\.

By \([3](https://arxiv.org/html/2608.07922#S3.E3)\), this is equivalent to the explicit three\-term form summarized in Theorem[1\.1](https://arxiv.org/html/2608.07922#S1.Thmtheorem1)\. The two resolution floors have different origins:sstats\_\{\\mathrm\{stat\}\}comes from the total number of fine verification samples available in the horizon, whereassmems\_\{\\mathrm\{mem\}\}comes from the number of regional decisions that can be reconstructed from boundary states\. TheBB\-dependent term is an independent update\-depth obstruction\.

Let𝔄B,∞\\mathfrak\{A\}\_\{B,\\infty\}denote the same committed\-batch class without a memory restriction\. By Remark[3\.1](https://arxiv.org/html/2608.07922#S3.Thmtheorem1), it is the usual end\-of\-batch feedback model\. Define

ℜTbat​\(B\):=inf𝒜∈𝔄B,∞supf∈Lip1​\(𝒳\)ν∈𝔇​\(f\)𝔼ν,𝒜​RegT​\(f\)\.\\mathfrak\{R\}\_\{T\}^\{\\mathrm\{bat\}\}\(B\):=\\inf\_\{\\mathcal\{A\}\\in\\mathfrak\{A\}\_\{B,\\infty\}\}\\sup\_\{\\begin\{subarray\}\{c\}f\\in\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)\\\\ \\nu\\in\\mathfrak\{D\}\(f\)\\end\{subarray\}\}\\mathbb\{E\}\_\{\\nu,\\mathcal\{A\}\}\\mathrm\{Reg\}\_\{T\}\(f\)\.
###### Corollary 3\.6\(Unrestricted\-memoryBB\-batch frontier\)\.

For every fixedd≥1d\\geq 1, there existcd,Cd,Td\>0c\_\{d\},C\_\{d\},T\_\{d\}\>0such that, for allT≥TdT\\geq T\_\{d\}and1≤B≤T1\\leq B\\leq T,

cd​\[Tαd∨Tβd,BB2\]≤ℜTbat​\(B\)≤Cd​ℓT​\[Tαd∨Tβd,BB2\]\.c\_\{d\}\\left\[T^\{\\alpha\_\{d\}\}\\vee\\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\\right\]\\leq\\mathfrak\{R\}\_\{T\}^\{\\mathrm\{bat\}\}\(B\)\\leq C\_\{d\}\\ell\_\{T\}\\left\[T^\{\\alpha\_\{d\}\}\\vee\\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\\right\]\.The upper bound uses static batch boundaries\.

###### Proof\.

The sequential lower bound follows from the regional family in Corollary[4\.2](https://arxiv.org/html/2608.07922#S4.Thmtheorem2)\. ForB≥2B\\geq 2, Lemma[B\.7](https://arxiv.org/html/2608.07922#A2.Thmtheorem7)gives the second term; forB=1B=1, the one\-codeword case of Proposition[4\.4](https://arxiv.org/html/2608.07922#S4.Thmtheorem4)gives linear regret\. For the upper bound, apply Theorem[3\.4](https://arxiv.org/html/2608.07922#S3.Thmtheorem4)withWT≍dTd/\(d\+2\)\+ℓTW\_\{T\}\\asymp\_\{d\}T^\{d/\(d\+2\)\}\+\\ell\_\{T\}\. WhenB≥2B\\geq 2, its memory resolution is no larger than the statistical resolution; whenB=1B=1, the update\-depth term is already linear\. The resulting policy belongs to𝔄B,∞\\mathfrak\{A\}\_\{B,\\infty\}and has static batch boundaries\. ∎

###### Corollary 3\.7\(Fully sequential logarithmic\-memory specialization\)\.

For every fixedd≥1d\\geq 1, there exist constantscd,Cd,Td\>0c\_\{d\},C\_\{d\},T\_\{d\}\>0such that, for allT≥TdT\\geq T\_\{d\}andW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\},

cd​Tαd≤ℜT​\(T,W\)≤Cd​ℓT​Tαd\.c\_\{d\}T^\{\\alpha\_\{d\}\}\\leq\\mathfrak\{R\}\_\{T\}\(T,W\)\\leq C\_\{d\}\\ell\_\{T\}T^\{\\alpha\_\{d\}\}\.

###### Proof\.

ForB=TB=T, one may use one\-pull batches, so the model is fully sequential\. Moreover,χ=\(T−1\)​W≳T\\chi=\(T\-1\)W\\gtrsim Timpliessmem≤sstats\_\{\\mathrm\{mem\}\}\\leq s\_\{\\mathrm\{stat\}\}for all sufficiently largeTT, andβd,T≤1\\beta\_\{d,T\}\\leq 1givesTβd,T/T2≤TαdT^\{\\beta\_\{d,T\}\}/T^\{2\}\\leq T^\{\\alpha\_\{d\}\}\. The claim follows from Theorem[3\.4](https://arxiv.org/html/2608.07922#S3.Thmtheorem4)\. ∎

This recovers, in the full\-dimensional worst\-case class, logarithmic\-space achievability ofZhu and Huang \([2025](https://arxiv.org/html/2608.07922#bib.bib16)\); see alsoLiet al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib38)\)\. Their zooming\-dimension\-adaptive guarantees and theΩ​\(log⁡T\)\\Omega\(\\log T\)memory lower bound ofZhu and Huang \([2025](https://arxiv.org/html/2608.07922#bib.bib16)\)are not consequences of our boundary\-state entropy converse and remain complementary\.

Forϱ\>0\\varrho\>0, define the batch complexity at target factorϱ\\varrhoby

ℬT​\(W;ϱ\):=min⁡\{B∈\[T\]:ℜT​\(B,W\)≤ϱ​ℓT​Tαd\},min⁡∅:=\+∞\.\\mathcal\{B\}\_\{T\}\(W;\\varrho\):=\\min\\left\\\{B\\in\[T\]:\\mathfrak\{R\}\_\{T\}\(B,W\)\\leq\\varrho\\ell\_\{T\}T^\{\\alpha\_\{d\}\}\\right\\\},\\qquad\\min\\varnothing:=\+\\infty\.
###### Corollary 3\.8\(Batch complexity of near\-sequential regret\)\.

For every fixedd≥1d\\geq 1, there existcd,Cd,Td,ϱd\>0c\_\{d\},C\_\{d\},T\_\{d\},\\varrho\_\{d\}\>0such that, forT≥TdT\\geq T\_\{d\}andW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\},

cd​\[log⁡log⁡T∨Td/\(d\+2\)W​ℓTd​\(d\+3\)\]≤ℬT​\(W;ϱd\)≤Cd​\[log⁡log⁡T∨Td/\(d\+2\)W\]\.c\_\{d\}\\left\[\\log\\log T\\ \\vee\\ \\frac\{T^\{d/\(d\+2\)\}\}\{W\\ell\_\{T\}^\{d\(d\+3\)\}\}\\right\]\\leq\\mathcal\{B\}\_\{T\}\(W;\\varrho\_\{d\}\)\\leq C\_\{d\}\\left\[\\log\\log T\\ \\vee\\ \\frac\{T^\{d/\(d\+2\)\}\}\{W\}\\right\]\.\(6\)In particular,

ℬT​\(W;ϱd\)=Θ~d​\(log⁡log⁡T∨Td/\(d\+2\)W\)\.\\mathcal\{B\}\_\{T\}\(W;\\varrho\_\{d\}\)=\\widetilde\{\\Theta\}\_\{d\}\\\!\\left\(\\log\\log T\\ \\vee\\ \\frac\{T^\{d/\(d\+2\)\}\}\{W\}\\right\)\.\(7\)

Appendix[F](https://arxiv.org/html/2608.07922#A6)proves the corollary\. It formalizes the separation between state width and update depth: concentrating the same boundary\-state entropy budget into too few redesigns cannot reproduce the required sequence of refinements\.

## 4Lower bound

The lower frontier is the maximum of three obstructions\. A single regional family yields the statistical and memory\-dependent terms: the horizon limits the total verification sample budget, while the boundary\-state entropy budget limits the number of regional decisions that can determine later experiments\. A separate adaptive\-grid construction supplies the update\-depth term\.

### 4\.1One regional family, two budgets

Fix0<r≤s/160<r\\leq s/16\. Choosem≍ds−dm\\asymp\_\{d\}s^\{\-d\}pairs of radius\-sscellsCj,0,Cj,1C\_\{j,0\},C\_\{j,1\}, with all cells well separated\. Inside each cell placeq≍d\(s/r\)dq\\asymp\_\{d\}\(s/r\)^\{d\}disjoint radius\-rrprobesGj,a,kG\_\{j,a,k\}, as in Figure[1](https://arxiv.org/html/2608.07922#S1.F1)\. A vectorv∈\{0,1\}mv\\in\\\{0,1\\\}^\{m\}selects one cell from each pair\. Withd∞​\(x,C\):=infy∈C‖x−y‖∞d\_\{\\infty\}\(x,C\):=\\inf\_\{y\\in C\}\\\|x\-y\\\|\_\{\\infty\}and\(u\)\+:=max⁡\{u,0\}\(u\)\_\{\+\}:=\\max\\\{u,0\\\}, define

fv\(x\):=14\+maxj∈\[m\]\(s4−12d∞\(x,Cj,vj\)\)\+f\_\{v\}\(x\):=\\frac\{1\}\{4\}\+\\max\_\{j\\in\[m\]\}\\left\(\\frac\{s\}\{4\}\-\\frac\{1\}\{2\}d\_\{\\infty\}\(x,C\_\{j,v\_\{j\}\}\)\\right\)\_\{\+\}and, forj∈\[m\]j\\in\[m\],k∈\[q\]k\\in\[q\],

fv,j,k\+​\(x\):=fv​\(x\)\+12​\(r−‖x−zj,vj,k‖∞\)\+\.f^\{\+\}\_\{v,j,k\}\(x\):=f\_\{v\}\(x\)\+\\frac\{1\}\{2\}\\left\(r\-\\\|x\-z\_\{j,v\_\{j\},k\}\\\|\_\{\\infty\}\\right\)\_\{\+\}\.The rewards are Bernoulli with these means\. Every selected cell lies on the optimal plateau offvf\_\{v\}; every unselected cell has gap at leasts/4s/4\. The comparison instancefv,j,k\+f^\{\+\}\_\{v,j,k\}differs fromfvf\_\{v\}only onGj,vj,kG\_\{j,v\_\{j\},k\}, raises its center byr/2r/2, and leaves every arm outside that probe at gap at leastr/2r/2\. Appendix[B\.2](https://arxiv.org/html/2608.07922#A2.SS2)verifies the packing and Lipschitz properties\.

The family has three basic counts:

m≍ds−d,m​q≍dr−d,m​q​n≍dr−d−2,n≍r−2\.m\\asymp\_\{d\}s^\{\-d\},\\qquad mq\\asymp\_\{d\}r^\{\-d\},\\qquad mqn\\asymp\_\{d\}r^\{\-d\-2\},\\qquad n\\asymp r^\{\-2\}\.\(8\)The first is the number of regional decisions, the second the total number of selected verification probes, and the third the number of pulls needed to verify all those probes\.

#### Local verification\.

Writeℙv\\mathbb\{P\}\_\{v\}for the interaction law underfvf\_\{v\}\. For a probeGj,a,kG\_\{j,a,k\}, letNj,a,k​\(T\)N\_\{j,a,k\}\(T\)be its number of visits and setn=⌊c0​r−2⌋n=\\lfloor c\_\{0\}r^\{\-2\}\\rfloor\. If a policy has regreto​\(T​r\)o\(Tr\)on the comparison instancefv,j,k\+f^\{\+\}\_\{v,j,k\}, then a stopped change\-of\-measure argument implies

ℙv​\(Nj,vj,k​\(T\)≥n\)≥c\\mathbb\{P\}\_\{v\}\\\!\\left\(N\_\{j,v\_\{j\},k\}\(T\)\\geq n\\right\)\\geq cfor a numerical constantc\>0c\>0\. The stopping time is thennth visit to the probe, so the relevant KL divergence isO​\(n​r2\)=O​\(1\)O\(nr^\{2\}\)=O\(1\)rather than a potentially large full\-horizon divergence\.

###### Lemma 4\.1\(Verification\-budget obstruction\)\.

Fixd≥1d\\geq 1\. There are constantscd,Cd,sd\>0c\_\{d\},C\_\{d\},s\_\{d\}\>0such that, whenever0<s≤sd0<s\\leq s\_\{d\},0<r≤s/160<r\\leq s/16,T​r2≥CdTr^\{2\}\\geq C\_\{d\}, and

r−d−2≥Cd​T,r^\{\-d\-2\}\\geq C\_\{d\}T,one has

ℜT​\(B,W\)≥cd​T​r\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}Trfor everyBBandWW\.

Indeed, low regret would force a constant probability ofnnvisits to every selected probe\. Since those probes are disjoint, \([8](https://arxiv.org/html/2608.07922#S4.E8)\) makes their expected total number of visitsΩd​\(m​q​n\)=Ωd​\(r−d−2\)\\Omega\_\{d\}\(mqn\)=\\Omega\_\{d\}\(r^\{\-d\-2\}\), exceeding the horizon\. The proof is in Appendix[B\.4](https://arxiv.org/html/2608.07922#A2.SS4)\.

###### Corollary 4\.2\(Sequential statistical obstruction\)\.

For every fixedd≥1d\\geq 1, there arecd,Td\>0c\_\{d\},T\_\{d\}\>0such that, for allT≥TdT\\geq T\_\{d\},BB, andWW,

ℜT​\(B,W\)≥cd​Tαd\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}T^\{\\alpha\_\{d\}\}\.

This follows from Lemma[4\.1](https://arxiv.org/html/2608.07922#S4.Thmtheorem1)withr≍dT−1/\(d\+2\)r\\asymp\_\{d\}T^\{\-1/\(d\+2\)\}ands≍drs\\asymp\_\{d\}r\. Thus the sequential term and the boundary\-state term below arise from the same hard family\.

### 4\.2Routing regional decisions through boundary states

LetVVbe uniform on\{0,1\}m\\\{0,1\\\}^\{m\}, independently ofℱ0\\mathcal\{F\}\_\{0\}, and run the base instancefVf\_\{V\}\. The local alternatives are used only for comparison\. Define

ρj,a:=1q​∑k=1q𝟏\{Nj,a,k​\(T\)≥n\}\.\\rho\_\{j,a\}:=\\frac\{1\}\{q\}\\sum\_\{k=1\}^\{q\}\\mathbf\{1\}\_\{\\\{N\_\{j,a,k\}\(T\)\\geq n\\\}\}\.After the transcript is generated, decode coordinatejjas the unique side withρj,a≥1/4\\rho\_\{j,a\}\\geq 1/4, breaking all other cases with a fresh independent fair coin\. The decoder is obtained from the committed action transcript and randomness independent of the learner, seed, instance, and transcript\.

Low regret on every local alternative makes the selected side cross the threshold with constant probability\. Low regret on the base instances prevents the same pattern on many unselected sides: wheneverρj,1−vj≥1/4\\rho\_\{j,1\-v\_\{j\}\}\\geq 1/4, at leastq​n/4qn/4pulls have incurred gap at leasts/4s/4\. Consequently, if regret is sufficiently smaller than bothT​rTrands​r−d−2sr^\{\-d\-2\}, then under the base\-prior law

1m​∑j=1mℙ¯​\(ρj,Vj≥1/4\)≥12,𝔼¯​∑j=1m𝟏\{ρj,1−Vj≥1/4\}≤m8\.\\frac\{1\}\{m\}\\sum\_\{j=1\}^\{m\}\\overline\{\\mathbb\{P\}\}\(\\rho\_\{j,V\_\{j\}\}\\geq 1/4\)\\geq\\frac\{1\}\{2\},\\qquad\\overline\{\\mathbb\{E\}\}\\sum\_\{j=1\}^\{m\}\\mathbf\{1\}\_\{\\\{\\rho\_\{j,1\-V\_\{j\}\}\\geq 1/4\\\}\}\\leq\\frac\{m\}\{8\}\.\(9\)The decoder therefore has average coordinate error at most5/165/16\. Writingh2h\_\{2\}for binary entropy,

I​\(V;V^∣ℱ0\)≥\[1−h2​\(5/16\)\]​m≳ds−d\.I\(V;\\widehat\{V\}\\mid\\mathcal\{F\}\_\{0\}\)\\geq\[1\-h\_\{2\}\(5/16\)\]m\\gtrsim\_\{d\}s^\{\-d\}\.On the other hand, Lemma[3\.3](https://arxiv.org/html/2608.07922#S3.Thmtheorem3)gives

I​\(V;V^∣ℱ0\)≤I​\(V;𝖳∣ℱ0\)≤χ\.I\(V;\\widehat\{V\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq I\(V;\\mathsf\{T\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\\chi\.This yields the boundary\-state obstruction\.

###### Lemma 4\.3\(Regional\-routing obstruction\)\.

Fixd≥1d\\geq 1\. There are constantscd,Cd,sd\>0c\_\{d\},C\_\{d\},s\_\{d\}\>0such that, whenever0<s≤sd0<s\\leq s\_\{d\},0<r≤s/160<r\\leq s/16,T​r2≥CdTr^\{2\}\\geq C\_\{d\}, and

χ≤cd​s−d,\\chi\\leq c\_\{d\}s^\{\-d\},\(10\)one has

ℜT​\(B,W\)≥cd​min⁡\{T​r,s​r−d−2\}\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}\\min\\\{Tr,\\;sr^\{\-d\-2\}\\\}\.

Appendix[B\.4](https://arxiv.org/html/2608.07922#A2.SS4)gives the stopped comparison, pathwise misrouted\-verification charge, decoder calculation, and entropy bound\. The two regret branches have direct meanings:T​rTris the cost of missing a local improvement, whereass​r−d−2sr^\{\-d\-2\}is the cost of sending comparable verification effort to unselected regions\.

#### Effective regional scale\.

At fixedss, balancing the two branches gives

r≍d\(s/T\)1/\(d\+3\),min⁡\{T​r,s​r−d−2\}≍dΨT​\(s\)\.r\\asymp\_\{d\}\(s/T\)^\{1/\(d\+3\)\},\\qquad\\min\\\{Tr,sr^\{\-d\-2\}\\\}\\asymp\_\{d\}\\Psi\_\{T\}\(s\)\.Ifsmems\_\{\\mathrm\{mem\}\}is above the statistical floor, chooses≍dsmems\\asymp\_\{d\}s\_\{\\mathrm\{mem\}\}and apply Lemma[4\.3](https://arxiv.org/html/2608.07922#S4.Thmtheorem3)\. If the statistical floor is larger, apply Corollary[4\.2](https://arxiv.org/html/2608.07922#S4.Thmtheorem2)\. After clipping the constant and very\-low\-entropy regimes, Appendix[B\.5](https://arxiv.org/html/2608.07922#A2.SS5)obtains

ℜT​\(B,W\)≥cd​ΨT​\(sT,χ\)=cd​\[Tαd∨Td\+2d\+3\(1\+χ\)1d​\(d\+3\)\]\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}\\Psi\_\{T\}\(s\_\{T,\\chi\}\)=c\_\{d\}\\left\[T^\{\\alpha\_\{d\}\}\\ \\vee\\ \\frac\{T^\{\\frac\{d\+2\}\{d\+3\}\}\}\{\(1\+\\chi\)^\{\\frac\{1\}\{d\(d\+3\)\}\}\}\\right\]\.\(11\)

### 4\.3Update depth and the very\-low\-entropy regime

#### Independent update\-depth obstruction\.

ForB≥2B\\geq 2, Appendix[B\.6](https://arxiv.org/html/2608.07922#A2.SS6)transfers the predictable adaptive\-grid lower bound ofFenget al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib15)\)from Gaussian to bounded Bernoulli rewards\. An at\-most\-BBpolicy can be embedded into their exact\-BBgrid by predictably subdividing committed tapes; at a dummy boundary the remaining tape is recommitted unchanged\. Thresholding a uniformly bounded Gaussian hard instance gives Bernoulli meanΦ​\(μ\)\\Phi\(\\mu\); on the relevant interval,Φ\\Phiis Lipschitz and has derivative bounded away from zero, so both smoothness and regret gaps are preserved up to constants\. The transfer proves

ℜT​\(B,W\)≥cd​Tβd,BB2\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}\\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\.\(12\)This obstruction persists with unrestricted memory: it limits how many times a reward\-dependent state can be recomputed, not how wide that state is\.

#### Very low boundary\-state entropy\.

The deterministic factorization in Lemma[3\.2](https://arxiv.org/html/2608.07922#S3.Thmtheorem2)says that, conditional on the seed, the committed transcript has at most2χ2^\{\\chi\}reward\-dependent realizations\. Placing more separated peaks than transcript codewords yields the following sharper bound\.

###### Proposition 4\.4\(Universal low\-memory obstruction\)\.

For everyd≥1d\\geq 1, there iscd\>0c\_\{d\}\>0such that, for all integersT≥1T\\geq 1,1≤B≤T1\\leq B\\leq T, andW≥0W\\geq 0,

ℜT​\(B,W\)≥cd​T​2−χ/d\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}T2^\{\-\\chi/d\}\.

Appendix[B\.1](https://arxiv.org/html/2608.07922#A2.SS1)contains the packing and decoding proof\. ForB=1B=1,χ=0\\chi=0and the proposition gives linear regret, which closes the one\-batch case of \([4](https://arxiv.org/html/2608.07922#S3.E4)\)\. ForB≥2B\\geq 2, taking the maximum of \([11](https://arxiv.org/html/2608.07922#S4.E11)\) and \([12](https://arxiv.org/html/2608.07922#S4.E12)\) proves the theorem\. The codebook proposition also records a sharper bound throughout the very\-low\-entropy regime\.

## 5Upper bound

The upper bound realizes the fixed\-scale calculus from the converse\. At regional scaless, it retains a binary active\-set mask withOd​\(s−d\)O\_\{d\}\(s^\{\-d\}\)possible coordinates\. At verification scalerr, it scansOd​\(r−d\)O\_\{d\}\(r^\{\-d\}\)predetermined child probes, usingOd​\(r−2​log⁡T\)O\_\{d\}\(r^\{\-2\}\\log T\)pulls per probe\. Each fine statistic is consumed once and erased; only the active\-set mask and a constant number of logarithmic control records persist\.

Both constructions use the same confidence rule\. If a lower\-confidence benchmarkλ\\lambdasatisfiesf⋆−ε≤λ≤f⋆f^\{\\star\}\-\\varepsilon\\leq\\lambda\\leq f^\{\\star\}and a candidate hasUCB⁡\(x\)≤f​\(x\)\+2​a\\operatorname\{UCB\}\(x\)\\leq f\(x\)\+2a, then

UCB⁡\(x\)≥λ−ζ⟹Δf​\(x\)≤ε\+ζ\+2​a\.\\operatorname\{UCB\}\(x\)\\geq\\lambda\-\\zeta\\quad\\Longrightarrow\\quad\\Delta\_\{f\}\(x\)\\leq\\varepsilon\+\\zeta\+2a\.The serialized construction obtainsλ\\lambdafrom a pass\-frozen incumbent; the in\-memory hierarchy uses the largest first\-sweep LCB\. All slot layouts and batch boundaries are fixed from\(T,B,W,d,ω\)\(T,B,W,d,\\omega\); at a boundary, the resident mask only instantiates candidate\-versus\-filler choices on that predetermined tape\.

### 5\.1Fixed\-scale refinement interface

Fix0<r≤s0<r\\leq s\. Let𝒫s=\{Pk:k∈\[K\]\}\\mathcal\{P\}\_\{s\}=\\\{P\_\{k\}:k\\in\[K\]\\\}be a fixed scale\-sspartition of\[0,1\]d\[0,1\]^\{d\}, withK≤Cd​s−dK\\leq C\_\{d\}s^\{\-d\}and cell diameter at mostss\. For everyPkP\_\{k\}, fix anrr\-net𝒩r​\(Pk\)\\mathcal\{N\}\_\{r\}\(P\_\{k\}\)of size at mostCd​\(s/r\)dC\_\{d\}\(s/r\)^\{d\}\. Put

ℓr:=log⁡\(e/r\),nr:=⌈Adref​r−2​ℓr⌉,\\ell\_\{r\}:=\\log\(e/r\),\\qquad n\_\{r\}:=\\left\\lceil A\_\{d\}^\{\\mathrm\{ref\}\}r^\{\-2\}\\ell\_\{r\}\\right\\rceil,whereAdrefA\_\{d\}^\{\\mathrm\{ref\}\}is sufficiently large\.

###### Definition 5\.1\(Safe active set\)\.

A collection𝒞⊆𝒫s\\mathcal\{C\}\\subseteq\\mathcal\{P\}\_\{s\}is a safe scale\-ssactive set if it contains a cell with a maximizer and

supP∈𝒞supx∈PΔf​\(x\)≤κd​s\\sup\_\{P\\in\\mathcal\{C\}\}\\sup\_\{x\\in P\}\\Delta\_\{f\}\(x\)\\leq\\kappa\_\{d\}sfor a fixed dimension\-dependent constantκd\\kappa\_\{d\}\.

The geometric set𝒞\\mathcal\{C\}is represented by a binary maskZZ\. The mask may arrive as one complete state or as disjoint fragments\. For each represented cell, the refinement tape allocates one segment to every arm in its fixedrr\-net; nonrepresented cells use a certifiedOd​\(s\)O\_\{d\}\(s\)\-optimal incumbent in the same slots\. Hence commitment fixes the tape but not action diversity\.

There are at most

K​\(s/r\)d≲dr−dK\(s/r\)^\{d\}\\lesssim\_\{d\}r^\{\-d\}child slots\. Usingnr=Od​\(r−2​ℓr\)n\_\{r\}=O\_\{d\}\(r^\{\-2\}\\ell\_\{r\}\)pulls per slot costsOd​\(r−d−2​ℓr\)O\_\{d\}\(r^\{\-d\-2\}\\ell\_\{r\}\)pulls\. On the safety event, every real or filler pull has gapOd​\(s\)O\_\{d\}\(s\), while exploiting the best refined arm incursOd​\(T​r\)O\_\{d\}\(Tr\)regret\.

###### Lemma 5\.2\(Refinement from a safe active set\)\.

There isCd\>0C\_\{d\}\>0such that, under the preceding fragment assumptions, if

Cd​r−d−2​ℓr≤T/2,C\_\{d\}r^\{\-d\-2\}\\ell\_\{r\}\\leq T/2,then one refinement batch per scheduled fragment uses at mostCd​r−d−2​ℓrC\_\{d\}r^\{\-d\-2\}\\ell\_\{r\}pulls andCd​ℓrC\_\{d\}\\ell\_\{r\}bits beyond the resident mask\. Refinement followed by exploitation has expected regret at most

Cd​\[s​r−d−2​ℓr\+T​r\]\.C\_\{d\}\\left\[sr^\{\-d\-2\}\\ell\_\{r\}\+Tr\\right\]\.\(13\)

The contract in \([13](https://arxiv.org/html/2608.07922#S5.E13)\) is realized with one quantized mean accumulator and one resident best\-child record; every segment statistic is erased after comparison\. Appendix[C](https://arxiv.org/html/2608.07922#A3)proves a stronger conditional version for random active sets and gives the exact finite\-precision implementation\.

Balancing the two terms in \([13](https://arxiv.org/html/2608.07922#S5.E13)\), fors≥\(ℓT/T\)1/\(d\+2\)s\\geq\(\\ell\_\{T\}/T\)^\{1/\(d\+2\)\}choose

rs:=\(s​ℓTT\)1/\(d\+3\)\.r\_\{s\}:=\\left\(\\frac\{s\\ell\_\{T\}\}\{T\}\\right\)^\{1/\(d\+3\)\}\.Thenrs≤sr\_\{s\}\\leq sand

s​rs−d−2​ℓT=T​rs=Td\+2d\+3​s1d\+3​ℓT1d\+3\.sr\_\{s\}^\{\-d\-2\}\\ell\_\{T\}=Tr\_\{s\}=T^\{\\frac\{d\+2\}\{d\+3\}\}s^\{\\frac\{1\}\{d\+3\}\}\\ell\_\{T\}^\{\\frac\{1\}\{d\+3\}\}\.Thus, up to logarithms, the algorithm pays the same envelopeΨT​\(s\)\\Psi\_\{T\}\(s\)as the fixed\-scale converse\. The remaining task is to construct the finest safe scale\-ssmask permitted by\(B,W\)\(B,W\)\.

### 5\.2Serialized active\-set construction

When the complete mask does not fit in memory, the learner realizes it as a stream\. It regenerates one memory\-sized fragment, immediately uses that fragment to commit the corresponding child probes, updates a resident global best child, erases the fragment, and continues\. Because fragments are never co\-resident, every pass uses a common reference: a freshly estimated incumbent is frozen throughout the pass, and candidate UCBs are compared with its LCB\. Nonfinal passes improve the incumbent; the final pass emits masks for immediate refinement\.

Fix sufficiently largeAdser,Cdctl\>0A\_\{d\}^\{\\mathrm\{ser\}\},C\_\{d\}^\{\\mathrm\{ctl\}\}\>0and define

ns:=⌈Adser​s−2​ℓT⌉,Lser:=⌈log2⁡log2⁡\(4​ns\)⌉∨1,Hser:=Lser​\(Lser\+1\)2\+1,wctl:=⌈Cdctl​ℓT⌉\.\\begin\{gathered\}n\_\{s\}:=\\left\\lceil A\_\{d\}^\{\\mathrm\{ser\}\}s^\{\-2\}\\ell\_\{T\}\\right\\rceil,\\\\ L\_\{\\mathrm\{ser\}\}:=\\left\\lceil\\log\_\{2\}\\log\_\{2\}\(4n\_\{s\}\)\\right\\rceil\\vee 1,\\\\ H\_\{\\mathrm\{ser\}\}:=\\frac\{L\_\{\\mathrm\{ser\}\}\(L\_\{\\mathrm\{ser\}\}\+1\)\}\{2\}\+1,\\qquad w\_\{\\mathrm\{ctl\}\}:=\\left\\lceil C\_\{d\}^\{\\mathrm\{ctl\}\}\\ell\_\{T\}\\right\\rceil\.\\end\{gathered\}\(14\)LetK=\|𝒫s\|K=\|\\mathcal\{P\}\_\{s\}\|, assumeW≥wctl\+1W\\geq w\_\{\\mathrm\{ctl\}\}\+1, and set

S:=min⁡\{K,W−wctl\},Js:=⌈KS⌉\.S:=\\min\\\{K,W\-w\_\{\\mathrm\{ctl\}\}\\\},\\qquad J\_\{s\}:=\\left\\lceil\\frac\{K\}\{S\}\\right\\rceil\.Only oneSS\-bit mask fragment is resident\. Reconstructing a fragment throughLserL\_\{\\mathrm\{ser\}\}tournament levels costsHserH\_\{\\mathrm\{ser\}\}batch slots, so the exact serialization law is

Js​Hser\+1≤B,equivalentlyK≤\(W−wctl\)​⌊B−1Hser⌋\.J\_\{s\}H\_\{\\mathrm\{ser\}\}\+1\\leq B,\\qquad\\text\{equivalently\}\\qquad K\\leq\(W\-w\_\{\\mathrm\{ctl\}\}\)\\left\\lfloor\\frac\{B\-1\}\{H\_\{\\mathrm\{ser\}\}\}\\right\\rfloor\.The first factor is fragment width; the second is the number of fragments that can be regenerated and consumed before final exploitation\. The replay factorHserH\_\{\\mathrm\{ser\}\}is an implementation overhead, not part of the information lower bound\. The phase\-specific reward\-dependent state consists of the frozen incumbentk¯\\bar\{k\}, its benchmarkλ\\lambda, one fragment maskZZ, and either the current pass champion\(kc,λc\)\(k\_\{c\},\\lambda\_\{c\}\)or the global refined\-arm record\(xbest,f^best\)\(x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\); all geometry and tape layouts are public\. Algorithm[1](https://arxiv.org/html/2608.07922#alg1)gives the policy, and Appendix[D](https://arxiv.org/html/2608.07922#A4)specifies its committed tapes, streaming registers, and confidence updates\.

Algorithm 1Serialized active\-set construction and refinement1:Budgets

\(T,B,W\)\(T,B,W\); dyadic radii

0<r≤s≤1/160<r\\leq s\\leq 1/16; fixed fragments, child nets, and confidence schedules determined from

\(T,B,W,d,ω\)\(T,B,W,d,\\omega\)\.

2:Choose an arbitrary parent representative

k0k\_\{0\}\.

3:for

i=1,…,Lser−1i=1,\\ldots,L\_\{\\mathrm\{ser\}\}\-1do⊳\\trianglerightconstruct a common reference

4:Freeze

k¯←k0\\bar\{k\}\\leftarrow k\_\{0\}; set

λ←⊥\\lambda\\leftarrow\\botand

\(kc,λc\)←\(∅,−∞\)\(k\_\{c\},\\lambda\_\{c\}\)\\leftarrow\(\\varnothing,\-\\infty\)\.

5:for

j=1,…,Jsj=1,\\ldots,J\_\{s\}do

6:

\(Z,λ,kc,λc\)←\(Z,\\lambda,k\_\{c\},\\lambda\_\{c\}\)\\leftarrowEliminateSelect\(

ℐj,i,k¯,λ;kc,λc\\mathcal\{I\}\_\{j\},i,\\bar\{k\},\\lambda;k\_\{c\},\\lambda\_\{c\}\)\.

7:Erase

ZZ\.

8:endfor

9:if

kc≠∅k\_\{c\}\\neq\\varnothingthen

10:

k0←kck\_\{0\}\\leftarrow k\_\{c\}\.

11:endif

12:endfor

13:Freeze

k¯←k0\\bar\{k\}\\leftarrow k\_\{0\}; set

λ←⊥\\lambda\\leftarrow\\botand

\(xbest,f^best\)←\(∅,−∞\)\(x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\)\\leftarrow\(\\varnothing,\-\\infty\)\.

14:for

j=1,…,Jsj=1,\\ldots,J\_\{s\}do⊳\\trianglerightemit, consume, and erase one mask fragment

15:

\(Z,λ\)←\(Z,\\lambda\)\\leftarrowEliminateMask\(

ℐj,Lser,k¯,λ,s\\mathcal\{I\}\_\{j\},L\_\{\\mathrm\{ser\}\},\\bar\{k\},\\lambda,s\)\.

16:

\(xbest,f^best\)←\(x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\)\\leftarrowRefineFragment\(

ℐj,Z,k¯;xbest,f^best\\mathcal\{I\}\_\{j\},Z,\\bar\{k\};x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\)\.

17:Erase

ZZ\.

18:endfor

19:Commit all remaining pulls to

xbestx\_\{\\mathrm\{best\}\}; use

x∘x\_\{\\circ\}if no child was recorded\.

20:The arm used in the final exploitation batch\.

The three subroutines update their resident records in place\.EliminateSelectreconstructs one fragment throughiiconfidence levels and updates the pass champion;EliminateMaskemits the final safe mask; andRefineFragmentexecutes the fixed child tape and updates the global best\-child record\. No fragment\-local score vector is stored\.

###### Proposition 5\.3\(Fixed\-scale serialized guarantee\)\.

There isCd\>0C\_\{d\}\>0such that, ifW−wctl≥1W\-w\_\{\\mathrm\{ctl\}\}\\geq 1,

Js​Hser\+1≤B,Cd​r−d−2​ℓT≤T/2,J\_\{s\}H\_\{\\mathrm\{ser\}\}\+1\\leq B,\\qquad C\_\{d\}r^\{\-d\-2\}\\ell\_\{T\}\\leq T/2,then Algorithm[1](https://arxiv.org/html/2608.07922#alg1)uses exactlyJs​Hser\+1J\_\{s\}H\_\{\\mathrm\{ser\}\}\+1batches, at mostS\+wctl≤WS\+w\_\{\\mathrm\{ctl\}\}\\leq Wmemory bits after every pull, and at mostCd​r−d−2​ℓTC\_\{d\}r^\{\-d\-2\}\\ell\_\{T\}exploratory pulls\. Uniformly overf∈Lip1​\(𝒳\)f\\in\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)andν∈𝔇​\(f\)\\nu\\in\\mathfrak\{D\}\(f\),

𝔼ν​RegT​\(f\)≤Cd​\[s​r−d−2​ℓT\+T​r\]\.\\mathbb\{E\}\_\{\\nu\}\\mathrm\{Reg\}\_\{T\}\(f\)\\leq C\_\{d\}\\left\[sr^\{\-d\-2\}\\ell\_\{T\}\+Tr\\right\]\.\(15\)

The active\-set tournament itself usesOd​\(s−d−2​ℓT\)O\_\{d\}\(s^\{\-d\-2\}\\ell\_\{T\}\)pulls and incursOd​\(s−d−1​ℓT\)O\_\{d\}\(s^\{\-d\-1\}\\ell\_\{T\}\)regret, both dominated by \([15](https://arxiv.org/html/2608.07922#S5.E15)\) becauser≤sr\\leq s\. Thus serialization changes only the finest feasibless, not the polynomial fixed\-scale cost\.

For a uniform horizon envelope, set

LTser:=⌈log2⁡\(8​ℓT\)⌉∨1,ΓT:=LTser​\(LTser\+1\)2\+1≍\(log⁡log⁡\(e​T\)\)2\.L\_\{T\}^\{\\mathrm\{ser\}\}:=\\left\\lceil\\log\_\{2\}\(8\\ell\_\{T\}\)\\right\\rceil\\vee 1,\\qquad\\Gamma\_\{T\}:=\\frac\{L\_\{T\}^\{\\mathrm\{ser\}\}\(L\_\{T\}^\{\\mathrm\{ser\}\}\+1\)\}\{2\}\+1\\asymp\(\\log\\log\(eT\)\)^\{2\}\.\(16\)WhenW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\}andB≥Cd​ΓTB\\geq C\_\{d\}\\Gamma\_\{T\}, the resource law reduces to

s−d≲d1\+χΓT\.s^\{\-d\}\\lesssim\_\{d\}1\+\\frac\{\\chi\}\{\\Gamma\_\{T\}\}\.Choosingssat the larger of the statistical floor and this serialized memory floor, then takingr=rsr=r\_\{s\}, gives the sequential and memory\-dependent branches up to the theorem’s outer logarithmic factor\. Appendix[D](https://arxiv.org/html/2608.07922#A4)proves the proposition and its optimized envelope\.

### 5\.3In\-memory hierarchical construction

Serialization converts boundaries into active\-set throughput, but its replay cost does not recover the sharp moderate\-BBexponent\. When the complete scale\-ssmask fits in memory, nested dyadic partitions update all active coordinates simultaneously\. At hierarchy levelℓ\\ell, representatives at radiusuℓu\_\{\\ell\}receiveO​\(uℓ−2​ℓT\)O\(u\_\{\\ell\}^\{\-2\}\\ell\_\{T\}\)pulls, while every active representative has gapOd​\(uℓ−1\)O\_\{d\}\(u\_\{\\ell\-1\}\)\. The narrowing regret is therefore

Od​\(ℓT​uℓ−1​uℓ−\(d\+2\)\)\.O\_\{d\}\\\!\\left\(\\ell\_\{T\}u\_\{\\ell\-1\}u\_\{\\ell\}^\{\-\(d\+2\)\}\\right\)\.The old mask commits two predetermined sweeps in one batch\. The first sweep forms the largest candidate LCB; the second compares every candidate UCB with that benchmark and writes the next mask online\. First\-sweep rewards affect the comparison benchmark but not the already committed second\-sweep actions\.

ForL≥1L\\geq 1, the equalized radii

θℓ:=1−\(d\+2\)−ℓ1−\(d\+2\)−L,uℓ≍sθℓ\\theta\_\{\\ell\}:=\\frac\{1\-\(d\+2\)^\{\-\\ell\}\}\{1\-\(d\+2\)^\{\-L\}\},\\qquad u\_\{\\ell\}\\asymp s^\{\\theta\_\{\\ell\}\}satisfy

∑ℓ=1Luℓ−1​uℓ−\(d\+2\)≤Cd​L​s−γd​\(L\),γd​\(L\):=d\+11−\(d\+2\)−L\.\\sum\_\{\\ell=1\}^\{L\}u\_\{\\ell\-1\}u\_\{\\ell\}^\{\-\(d\+2\)\}\\leq C\_\{d\}Ls^\{\-\\gamma\_\{d\}\(L\)\},\\qquad\\gamma\_\{d\}\(L\):=\\frac\{d\+1\}\{1\-\(d\+2\)^\{\-L\}\}\.ForB≥3B\\geq 3and0<r≤s≤1/160<r\\leq s\\leq 1/16, take

L=LB​\(s\):=min⁡\{B−2,⌊\(d\+1\)​log⁡\(1/s\)log⁡\(d\+2\)⌋\}≥1\.L=L\_\{B\}\(s\):=\\min\\left\\\{B\-2,\\left\\lfloor\\frac\{\(d\+1\)\\log\(1/s\)\}\{\\log\(d\+2\)\}\\right\\rfloor\\right\\\}\\geq 1\.Lemma[E\.1](https://arxiv.org/html/2608.07922#A5.Thmtheorem1)in Appendix[E](https://arxiv.org/html/2608.07922#A5)gives feasibility when

LB​\(s\)\+2≤B,Cd​\(s−d\+ℓT\)≤W,Cd​LB​\(s\)​ℓT​r−d−2≤T/2,L\_\{B\}\(s\)\+2\\leq B,\\qquad C\_\{d\}\(s^\{\-d\}\+\\ell\_\{T\}\)\\leq W,\\qquad C\_\{d\}L\_\{B\}\(s\)\\ell\_\{T\}r^\{\-d\-2\}\\leq T/2,and then, uniformly overf∈Lip1​\(𝒳\)f\\in\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)andν∈𝔇​\(f\)\\nu\\in\\mathfrak\{D\}\(f\),

𝔼ν​RegT​\(f\)≤Cd​\[LB​\(s\)​ℓT​s−γd​\(LB​\(s\)\)\+ℓT​s​r−d−2\+T​r\]\.\\mathbb\{E\}\_\{\\nu\}\\mathrm\{Reg\}\_\{T\}\(f\)\\leq C\_\{d\}\\left\[L\_\{B\}\(s\)\\ell\_\{T\}s^\{\-\\gamma\_\{d\}\(L\_\{B\}\(s\)\)\}\+\\ell\_\{T\}sr^\{\-d\-2\}\+Tr\\right\]\.\(17\)The first term is the cost of limited update depth; the last two are the same fixed\-scale refinement envelope as in the serialized branch\.

#### Regime assembly\.

The policy is selected deterministically from\(T,B,W\)\(T,B,W\)\. ForB=1B=1it playsx∘x\_\{\\circ\}\. ForB=2B=2, the unique root cell is already a safe active set, so one root\-refinement batch followed by exploitation gives the two\-batch branch\. For3≤B<Cd​ΓT3\\leq B<C\_\{d\}\\Gamma\_\{T\}it uses the in\-memory hierarchy, and forB≥Cd​ΓTB\\geq C\_\{d\}\\Gamma\_\{T\}it uses the serialized construction\. In the serialized regime, up to dyadic rounding,

s≍dmax⁡\{\(ℓTT\)1/\(d\+2\),\(ΓTΓT\+χ\)1/d\},r≍drs\.s\\asymp\_\{d\}\\max\\left\\\{\\left\(\\frac\{\\ell\_\{T\}\}\{T\}\\right\)^\{1/\(d\+2\)\},\\left\(\\frac\{\\Gamma\_\{T\}\}\{\\Gamma\_\{T\}\+\\chi\}\\right\)^\{1/d\}\\right\\\},\\qquad r\\asymp\_\{d\}r\_\{s\}\.In the in\-memory regime, optimizing \([17](https://arxiv.org/html/2608.07922#S5.E17)\) with the equalized hierarchy producesTβd,B/B2T^\{\\beta\_\{d,B\}\}/B^\{2\}together with the same statistical and memory envelopes\. The factorsLB​\(s\)L\_\{B\}\(s\)andΓT\\Gamma\_\{T\}are absorbed by the outerℓT\\ell\_\{T\}in Theorem[3\.4](https://arxiv.org/html/2608.07922#S3.Thmtheorem4)\. Appendices[D](https://arxiv.org/html/2608.07922#A4)and[E](https://arxiv.org/html/2608.07922#A5)give the exact finite\-precision state inventories, schedules, and uniform regime calculation proving \([5](https://arxiv.org/html/2608.07922#S3.E5)\)\.

## 6Conclusion

We determine the minimax memory–batch frontier for stochastic Lipschitz bandits up to logarithmic factors whenW≳dlog⁡\(e​T\)W\\gtrsim\_\{d\}\\log\(eT\), with lower bounds valid for every memory budget\. The framework contains both one\-resource specializations: unrestricted memory gives the full\-dimensional worst\-case batch\-only frontier, whileB=TB=Trecovers optimal sequential regret with logarithmic live memory\. The statistical and memory\-dependent branches form one fixed\-scale envelope: the horizon limits verification, boundary states limit how many regional decisions reach later experiments, andBBseparately limits update depth\. Matching policies erase verification statistics while retaining an active\-set mask, either simultaneously or as regenerated fragments\. Static batch boundaries match predictable adaptive ones\.

The main open problems are to remove logarithmic losses, characterize the sublogarithmic\-memory regime, obtain instance\-dependent analogues, and turn the prefix information profile into a time\-resolved regret converse\.

## References

- A\. Agarwal, S\. Agarwal, S\. Assadi, and S\. Khanna \(2017\)Learning with limited rounds of adaptivity: coin tossing, multi\-armed bandits, and ranking from pairwise comparisons\.InProceedings of the 30th Conference on Learning Theory,pp\. 39–75\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- A\. Agarwal, S\. Khanna, and P\. Patil \(2022\)A sharp memory\-regret trade\-off for multi\-pass streaming bandits\.InProceedings of the 35th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.178,pp\. 1423–1462\.External Links:[Link](https://proceedings.mlr.press/v178/agarwal22a.html)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- R\. Agrawal \(1995\)The continuum\-armed bandit problem\.SIAM Journal on Control and Optimization33\(6\),pp\. 1926–1951\.External Links:[Document](https://dx.doi.org/10.1137/S0363012992237273)Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p2.9),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Assadi and C\. Wang \(2020\)Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi\-armed bandits\.InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,pp\. 1237–1250\.External Links:[Document](https://dx.doi.org/10.1145/3357713.3384341)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- S\. Assadi and C\. Wang \(2024\)The best arm evades: near\-optimal multi\-pass streaming lower bounds for pure exploration in multi\-armed bandits\.InProceedings of the 37th Conference on Learning Theory,pp\. 311–358\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- P\. Auer, R\. Ortner, and C\. Szepesvari \(2007\)Improved rates for the stochastic continuum\-armed bandit problem\.InProceedings of the 20th Conference on Learning Theory,pp\. 454–468\.Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p2.9),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Bubeck, R\. Munos, G\. Stoltz, and C\. Szepesvari \(2011\)X\-armed bandits\.Journal of Machine Learning Research12,pp\. 1655–1695\.Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p2.9),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- A\. R\. Chaudhuri and S\. Kalyanakrishnan \(2020\)Regret minimisation in multi\-armed bandits using bounded arm memory\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 10085–10092\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v34i06.6566)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- P\. Coquelin and R\. Munos \(2007\)Bandit algorithms for tree search\.InProceedings of the Twenty\-Third Conference on Uncertainty in Artificial Intelligence,pp\. 67–74\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- T\. M\. Cover and M\. E\. Hellman \(1970\)The two\-armed\-bandit problem with time\-invariant finite memory\.IEEE Transactions on Information Theory16\(2\),pp\. 185–195\.External Links:[Document](https://dx.doi.org/10.1109/TIT.1970.1054427)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- T\. M\. Cover and J\. A\. Thomas \(2006\)Elements of information theory\.2 edition,Wiley\.Cited by:[§A\.3](https://arxiv.org/html/2608.07922#A1.SS3.2.p2.8)\.
- T\. M\. Cover \(1968\)A note on the two\-armed bandit problem with finite memory\.Information and Control12\(5\),pp\. 371–377\.External Links:[Document](https://dx.doi.org/10.1016/S0019-9958%2868%2990382-3)Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p1.1),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- H\. Esfandiari, A\. Karbasi, A\. Mehrabian, and V\. Mirrokni \(2021\)Regret bounds for batched bandits\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.35,pp\. 7340–7348\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v35i8.16901)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- Y\. Feng, Z\. Huang, and T\. Wang \(2024\)Lipschitz bandits with batched feedback\.IEEE Transactions on Information Theory70\(3\),pp\. 2154–2176\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2023.3312308),2110\.09722Cited by:[§B\.6](https://arxiv.org/html/2608.07922#A2.SS6.5.p1.3),[§B\.6](https://arxiv.org/html/2608.07922#A2.SS6.7.p3.2),[§B\.6](https://arxiv.org/html/2608.07922#A2.SS6.p1.2),[§1](https://arxiv.org/html/2608.07922#S1.p4.3),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3),[§4\.3](https://arxiv.org/html/2608.07922#S4.SS3.SSS0.Px1.p1.5)\.
- Z\. Gao, Y\. Han, Z\. Ren, and Z\. Zhou \(2019\)Batched multi\-armed bandits problem\.InAdvances in Neural Information Processing Systems,Vol\.32\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- S\. Garg, R\. Raz, and A\. Tal \(2018\)Extractor\-based time\-space lower bounds for learning\.InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing,pp\. 990–1002\.External Links:[Document](https://dx.doi.org/10.1145/3188745.3188962)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px4.p1.4)\.
- O\. Hanna, L\. Yang, and C\. Fragouli \(2023\)Efficient batched algorithm for contextual linear bandits with large action space via soft elimination\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 56772–56783\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- R\. Huang, Z\. Lyu, X\. Zhu, and Z\. Huang \(2026\)Few batches or little memory, but not both: simultaneous space and adaptivity constraints in stochastic bandits\.arXiv preprint arXiv:2603\.13742\.External Links:2603\.13742,[Document](https://dx.doi.org/10.48550/arXiv.2603.13742)Cited by:[§B\.3](https://arxiv.org/html/2608.07922#A2.SS3.p1.1),[§1](https://arxiv.org/html/2608.07922#S1.p1.1),[§1](https://arxiv.org/html/2608.07922#S1.p4.3),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px4.p1.4),[§3\.1](https://arxiv.org/html/2608.07922#S3.SS1.p3.8)\.
- T\. Jin, K\. Huang, J\. Tang, and X\. Xiao \(2021a\)Optimal streaming algorithms for multi\-armed bandits\.InProceedings of the 38th International Conference on Machine Learning,pp\. 5045–5054\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- T\. Jin, J\. Tang, P\. Xu, K\. Huang, X\. Xiao, and Q\. Gu \(2021b\)Almost optimal anytime algorithm for batched multi\-armed bandits\.InProceedings of the 38th International Conference on Machine Learning,pp\. 5065–5073\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- R\. Kleinberg, A\. Slivkins, and E\. Upfal \(2008\)Multi\-armed bandits in metric spaces\.InProceedings of the Fortieth Annual ACM Symposium on Theory of Computing,pp\. 681–690\.External Links:[Document](https://dx.doi.org/10.1145/1374376.1374475)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- R\. Kleinberg \(2004\)Nearly tight bounds for the continuum\-armed bandit problem\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p2.9),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- I\. Lau, D\. McMorrow, K\. Jamieson, and J\. Scarlett \(2026\)Batched stochastic linear bandits with 1\-Bit communication constraints\.arXiv preprint arXiv:2605\.30976\.External Links:2605\.30976,[Document](https://dx.doi.org/10.48550/arXiv.2605.30976)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- S\. Li, L\. Zhang, and X\. Li \(2024\)Efficient algorithms for lipschitz bandits\.Note:OpenReview manuscript submitted to NeurIPS 2024External Links:[Link](https://openreview.net/forum?id=SOxxGATGsl)Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p4.3),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2),[§3\.3](https://arxiv.org/html/2608.07922#S3.SS3.p4.1)\.
- S\. Li, L\. Zhang, J\. Wang, and X\. Li \(2023\)Tight memory\-regret lower bounds for streaming bandits\.arXiv preprint arXiv:2306\.07903\.External Links:2306\.07903Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- D\. Liau, Z\. Song, E\. Price, and G\. Yang \(2018\)Stochastic multi\-armed bandits in constant space\.InProceedings of the 21st International Conference on Artificial Intelligence and Statistics,pp\. 386–394\.Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p1.1),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- S\. Magureanu, R\. Combes, and A\. Proutiere \(2014\)Lipschitz bandits: regret lower bound and optimal algorithms\.InProceedings of the 27th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.35,pp\. 975–999\.External Links:[Link](https://proceedings.mlr.press/v35/magureanu14.html)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Maiti, V\. Patil, and A\. Khan \(2021\)Multi\-armed bandits with bounded arm\-memory: near\-optimal guarantees for best\-arm identification and regret minimization\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 19553–19565\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- R\. Munos \(2011\)Optimistic optimization of a deterministic function without the knowledge of its smoothness\.InAdvances in Neural Information Processing Systems,Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- B\. Peng and A\. Rubinstein \(2023\)Near optimal memory\-regret tradeoff for online learning\.InProceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science,pp\. 1171–1194\.External Links:[Document](https://dx.doi.org/10.1109/FOCS57990.2023.00069)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- B\. Peng and F\. Zhang \(2023\)Online prediction in sub\-linear space\.InProceedings of the 2023 Annual ACM\-SIAM Symposium on Discrete Algorithms,pp\. 1611–1634\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611977554.ch60)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- V\. Perchet, P\. Rigollet, S\. Chassang, and E\. Snowberg \(2016\)Batched bandit problems\.The Annals of Statistics44\(2\),pp\. 660–681\.External Links:[Document](https://dx.doi.org/10.1214/15-AOS1381)Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p1.1),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- C\. Podimata and A\. Slivkins \(2021\)Adaptive discretization for adversarial lipschitz bandits\.InProceedings of the 34th Conference on Learning Theory,pp\. 3788–3805\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px1.p1.1)\.
- R\. Raz \(2016\)Fast learning requires good memory: a time\-space lower bound for parity learning\.InProceedings of the 57th IEEE Symposium on Foundations of Computer Science,pp\. 266–275\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2016.36)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px4.p1.4)\.
- Y\. Ruan, J\. Yang, and Y\. Zhou \(2021\)Linear bandits with limited adaptivity and learning distributional optimal design\.InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing,pp\. 74–87\.External Links:[Document](https://dx.doi.org/10.1145/3406325.3451004)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- A\. Sawarni, N\. Das, S\. Barman, and G\. Sinha \(2024\)Generalized linear bandits with limited adaptivity\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 8329–8369\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px2.p1.3)\.
- I\. Shufaro, N\. Merlis, N\. Weinberger, and S\. Mannor \(2025\)On bits and bandits: quantifying the regret–information trade\-off\.InInternational Conference on Learning Representations,External Links:2405\.16581,[Document](https://dx.doi.org/10.48550/arXiv.2405.16581)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px4.p1.4)\.
- V\. Srinivas, D\. P\. Woodruff, Z\. Xu, and S\. Zhou \(2022\)Memory bounds for the experts problem\.InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing,pp\. 1158–1171\.External Links:[Document](https://dx.doi.org/10.1145/3519935.3520069)Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- C\. Wang \(2023\)Tight regret bounds for single\-pass streaming multi\-armed bandits\.InProceedings of the 40th International Conference on Machine Learning,pp\. 35525–35547\.Cited by:[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2)\.
- X\. Zhu and Z\. Huang \(2025\)Lipschitz bandits in optimal space\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.07922#S1.p4.3),[§2](https://arxiv.org/html/2608.07922#S2.SS0.SSS0.Px3.p1.2),[§3\.3](https://arxiv.org/html/2608.07922#S3.SS3.p4.1)\.

## Appendix AFormal policy maps and boundary\-state reconstruction

### A\.1Formal committed\-batch policy maps

This subsection gives the map\-level realization of the operational policy model in Section[3\.1](https://arxiv.org/html/2608.07922#S3.SS1)\. Let\(Ω0,𝒢0\)\(\\Omega\_\{0\},\\mathcal\{G\}\_\{0\}\)be the standard Borel seed space\. Initialization is a Borel mapι:Ω0→\{0,1\}W\\iota:\\Omega\_\{0\}\\to\\\{0,1\\\}^\{W\}, withM0=ι​\(ω\)M\_\{0\}=\\iota\(\\omega\)\. For everyb∈\{0,…,B−1\}b\\in\\\{0,\\ldots,B\-1\\\}andu∈\[T\]u\\in\[T\], let

ψb:Ω0×\{0,…,T\}×\{0,1\}W⟶\{0,…,T\},ϕb,u:Ω0×\{0,…,T\}×\{0,1\}W⟶𝒳\\psi\_\{b\}:\\Omega\_\{0\}\\times\\\{0,\\ldots,T\\\}\\times\\\{0,1\\\}^\{W\}\\longrightarrow\\\{0,\\ldots,T\\\},\\qquad\\phi\_\{b,u\}:\\Omega\_\{0\}\\times\\\{0,\\ldots,T\\\}\\times\\\{0,1\\\}^\{W\}\\longrightarrow\\mathcal\{X\}be total Borel maps\. For every seedww, timett, and memory wordmm, require

ψb​\(w,t,m\)∈\{\{t\+1,…,T\},t<T,\{T\},t=T,ψB−1​\(w,t,m\)=T\(t<T\)\.\\psi\_\{b\}\(w,t,m\)\\in\\begin\{cases\}\\\{t\+1,\\ldots,T\\\},&t<T,\\\\ \\\{T\\\},&t=T,\\end\{cases\}\\qquad\\psi\_\{B\-1\}\(w,t,m\)=T\\quad\(t<T\)\.On the realized trajectory,

τb\+1\\displaystyle\\tau\_\{b\+1\}=ψb​\(ω,τb,Mτb\),\\displaystyle=\\psi\_\{b\}\(\\omega,\\tau\_\{b\},M\_\{\\tau\_\{b\}\}\),\(18\)At\\displaystyle A\_\{t\}=ϕb,t​\(ω,τb,Mτb\),τb<t≤τb\+1\.\\displaystyle=\\phi\_\{b,t\}\(\\omega,\\tau\_\{b\},M\_\{\\tau\_\{b\}\}\),\\qquad\\tau\_\{b\}<t\\leq\\tau\_\{b\+1\}\.\(19\)Values ofϕb,u\\phi\_\{b,u\}outside the selected batch and values on unreachable memory words are immaterial\. For eachb,tb,t, let

𝒰b,t:Ω0×\{0,1\}W×𝒳×\[0,1\]⟶\{0,1\}W\\mathcal\{U\}\_\{b,t\}:\\Omega\_\{0\}\\times\\\{0,1\\\}^\{W\}\\times\\mathcal\{X\}\\times\[0,1\]\\longrightarrow\\\{0,1\\\}^\{W\}be a Borel update map, and set

Mt=𝒰b,t​\(ω,Mt−1,At,Yt\),τb<t≤τb\+1\.M\_\{t\}=\\mathcal\{U\}\_\{b,t\}\(\\omega,M\_\{t\-1\},A\_\{t\},Y\_\{t\}\),\\qquad\\tau\_\{b\}<t\\leq\\tau\_\{b\+1\}\.These maps formalize a predictable adaptive batch boundary and a complete action tape chosen at the preceding boundary, followed by online memory updates that cannot alter that tape\.

### A\.2Prefix transcript reconstruction

###### Proof of Lemma[3\.2](https://arxiv.org/html/2608.07922#S3.Thmtheorem2)\.

Fixj∈\[B\]j\\in\[B\]and\(w,m1:j−1\)∈Ω0×\(\{0,1\}W\)j−1\(w,m\_\{1:j\-1\}\)\\in\\Omega\_\{0\}\\times\(\\\{0,1\\\}^\{W\}\)^\{j\-1\}\. Set

t0=0,m0=ι​\(w\)\.t\_\{0\}=0,\\qquad m\_\{0\}=\\iota\(w\)\.Forb=0,…,j−1b=0,\\ldots,j\-1, define recursively

tb\+1\\displaystyle t\_\{b\+1\}=ψb​\(w,tb,mb\),\\displaystyle=\\psi\_\{b\}\(w,t\_\{b\},m\_\{b\}\),au\\displaystyle a\_\{u\}=ϕb,u​\(w,tb,mb\),tb<u≤tb\+1,\\displaystyle=\\phi\_\{b,u\}\(w,t\_\{b\},m\_\{b\}\),\\qquad t\_\{b\}<u\\leq t\_\{b\+1\},wherembm\_\{b\}forb≥1b\\geq 1is the corresponding input word\. Setau=x∘a\_\{u\}=x\_\{\\circ\}foru\>tju\>t\_\{j\}\. The totality conditions above imply0=t0≤t1≤⋯≤tj≤T0=t\_\{0\}\\leq t\_\{1\}\\leq\\cdots\\leq t\_\{j\}\\leq T, with strict increase until the first visit toTT\. Finite composition of Borel maps therefore yields a Borel map

𝖱𝖾𝖼𝒜,j​\(w,m1:j−1\):=\(t1:j,a1:T\)\.\\mathsf\{Rec\}\_\{\\mathcal\{A\},j\}\(w,m\_\{1:j\-1\}\):=\(t\_\{1:j\},a\_\{1:T\}\)\.
For the padded boundary states generated by the policy, induction overbband \([18](https://arxiv.org/html/2608.07922#A1.E18)\)–\([19](https://arxiv.org/html/2608.07922#A1.E19)\) give

tb=τ¯b\(0≤b≤j\),au=Au\(1≤u≤τ¯j\)\.t\_\{b\}=\\bar\{\\tau\}\_\{b\}\\quad\(0\\leq b\\leq j\),\\qquad a\_\{u\}=A\_\{u\}\\quad\(1\\leq u\\leq\\bar\{\\tau\}\_\{j\}\)\.Afterτ¯j\\bar\{\\tau\}\_\{j\}, both the definition of𝖳\[j\]\\mathsf\{T\}^\{\[j\]\}and the recursion usex∘x\_\{\\circ\}\. Hence

𝖳\[j\]=𝖱𝖾𝖼𝒜,j​\(ω,M¯1,…,M¯j−1\)almost surely\.\\mathsf\{T\}^\{\[j\]\}=\\mathsf\{Rec\}\_\{\\mathcal\{A\},j\}\(\\omega,\\bar\{M\}\_\{1\},\\ldots,\\bar\{M\}\_\{j\-1\}\)\\qquad\\text\{almost surely\}\.For fixedww,

\|range⁡𝖱𝖾𝖼𝒜,j​\(w,⋅\)\|≤\|\(\{0,1\}W\)j−1\|=2\(j−1\)​W\.\\bigl\|\\operatorname\{range\}\\mathsf\{Rec\}\_\{\\mathcal\{A\},j\}\(w,\\cdot\)\\bigr\|\\leq\\bigl\|\(\\\{0,1\\\}^\{W\}\)^\{j\-1\}\\bigr\|=2^\{\(j\-1\)W\}\.Whenj=Bj=B, the terminal endpoint is deterministic\. Deleting it defines𝖱𝖾𝖼𝒜\\mathsf\{Rec\}\_\{\\mathcal\{A\}\}, gives𝖳=𝖱𝖾𝖼𝒜​\(ω,𝐌\)\\mathsf\{T\}=\\mathsf\{Rec\}\_\{\\mathcal\{A\}\}\(\\omega,\\mathbf\{M\}\), and preserves the range bound2\(B−1\)​W=2χ2^\{\(B\-1\)W\}=2^\{\\chi\}\. ∎

### A\.3Prefix information profile

###### Proof of Lemma[3\.3](https://arxiv.org/html/2608.07922#S3.Thmtheorem3)\.

Fixj∈\[B\]j\\in\[B\]and write𝐌<j:=\(M¯1,…,M¯j−1\)\\mathbf\{M\}\_\{<j\}:=\(\\bar\{M\}\_\{1\},\\ldots,\\bar\{M\}\_\{j\-1\}\)\. By Lemma[3\.2](https://arxiv.org/html/2608.07922#S3.Thmtheorem2), conditional onℱ0\\mathcal\{F\}\_\{0\},

V⟶𝐌<j⟶𝖳\[j\]V\\longrightarrow\\mathbf\{M\}\_\{<j\}\\longrightarrow\\mathsf\{T\}^\{\[j\]\}is a Markov chain\. The conditional chain rule and theWW\-bit alphabet of each boundary state give

H​\(𝐌<j∣ℱ0\)=∑b=1j−1H​\(M¯b∣ℱ0,M¯1:b−1\)≤\(j−1\)​W\.H\(\\mathbf\{M\}\_\{<j\}\\mid\\mathcal\{F\}\_\{0\}\)=\\sum\_\{b=1\}^\{j\-1\}H\(\\bar\{M\}\_\{b\}\\mid\\mathcal\{F\}\_\{0\},\\bar\{M\}\_\{1:b\-1\}\)\\leq\(j\-1\)W\.Conditional data processing therefore yields

I​\(V;𝖳\[j\]∣ℱ0\)≤I​\(V;𝐌<j∣ℱ0\)≤\(j−1\)​W\.I\(V;\\mathsf\{T\}^\{\[j\]\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq I\(V;\\mathbf\{M\}\_\{<j\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\(j\-1\)W\.
Forj=Bj=B,𝐌<B=𝐌\\mathbf\{M\}\_\{<B\}=\\mathbf\{M\}and𝖳\[B\]\\mathsf\{T\}^\{\[B\]\}contains the same information as𝖳\\mathsf\{T\}\. SinceRRis generated from the transcript and fresh randomization independent of all experiment variables, conditional onℱ0\\mathcal\{F\}\_\{0\},

V⟶𝐌⟶𝖳⟶R\.V\\longrightarrow\\mathbf\{M\}\\longrightarrow\\mathsf\{T\}\\longrightarrow R\.Hence

I​\(V;𝖳,R∣ℱ0\)=I​\(V;𝖳∣ℱ0\)≤I​\(V;𝐌∣ℱ0\)≤H​\(𝐌∣ℱ0\)≤\(B−1\)​W=χ\.I\(V;\\mathsf\{T\},R\\mid\\mathcal\{F\}\_\{0\}\)=I\(V;\\mathsf\{T\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq I\(V;\\mathbf\{M\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq H\(\\mathbf\{M\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\(B\-1\)W=\\chi\.A final application of data processing givesI​\(V;R∣ℱ0\)≤χI\(V;R\\mid\\mathcal\{F\}\_\{0\}\)\\leq\\chi\. ForB=1B=1, all memory tuples are empty and the corresponding bounds are zero\(Cover and Thomas,[2006](https://arxiv.org/html/2608.07922#bib.bib26), Chapters 2–3\)\. ∎

## Appendix BLower\-bound proofs

This appendix proves the transcript\-codebook lemma, verifies the additive cell–probe geometry, derives both the verification\-budget and routing\-memory obstructions from one stopped comparison, optimizes the effective regional scale, and transfers the independent Gaussian batch\-depth lower bound to bounded Bernoulli rewards by thresholding the observations\. Discrete information quantities are measured in bits and are conditional onℱ0\\mathcal\{F\}\_\{0\}when indicated\. Foru∈ℝu\\in\\mathbb\{R\}, write\(u\)\+:=max⁡\{u,0\}\(u\)\_\{\+\}:=\\max\\\{u,0\\\}; forx∈ℝdx\\in\\mathbb\{R\}^\{d\},a\>0a\>0, and nonemptyS⊆ℝdS\\subseteq\\mathbb\{R\}^\{d\}, write

B∞​\(x,a\):=\{y:‖x−y‖∞≤a\},d∞​\(x,S\):=infy∈S‖x−y‖∞\.B\_\{\\infty\}\(x,a\):=\\\{y:\\\|x\-y\\\|\_\{\\infty\}\\leq a\\\},\\qquad d\_\{\\infty\}\(x,S\):=\\inf\_\{y\\in S\}\\\|x\-y\\\|\_\{\\infty\}\.We denote the all\-ones vector inℝd\\mathbb\{R\}^\{d\}by𝟏d\\boldsymbol\{1\}\_\{d\}; the Lipschitz seminormLip​\(g\)\\mathrm\{Lip\}\(g\)is defined in Section[3\.1](https://arxiv.org/html/2608.07922#S3.SS1)\.

### B\.1Boundary codebook

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

Fix𝒜∈𝔄B,W\\mathcal\{A\}\\in\\mathfrak\{A\}\_\{B,W\}\. Put

N0=2\(B−1\)​W,N=2​N0\.N\_\{0\}=2^\{\(B\-1\)W\},\\qquad N=2N\_\{0\}\.SinceN≥2N\\geq 2, the integerg=⌈N1/d⌉g=\\lceil N^\{1/d\}\\rceilsatisfiesg≥2g\\geq 2\. The regulargdg^\{d\}\-point grid in\[1/4,3/4\]d\[1/4,3/4\]^\{d\}has spacing1/\[2​\(g−1\)\]1/\[2\(g\-1\)\]\. Select anyNNgrid pointsz1,…,zNz\_\{1\},\\ldots,z\_\{N\}and set

r0=18​\(g−1\)\.r\_\{0\}=\\frac\{1\}\{8\(g\-1\)\}\.\(20\)Their pairwise distances are at least4​r04r\_\{0\}, while

r0≥18​N−1/d\.r\_\{0\}\\geq\\frac\{1\}\{8\}N^\{\-1/d\}\.\(21\)Forv∈\[N\]v\\in\[N\], define the Bernoulli mean

gv​\(x\)=14\+\(r0−‖x−zv‖∞\)\+,Gv=B∞​\(zv,r0/2\)\.g\_\{v\}\(x\)=\\frac\{1\}\{4\}\+\\bigl\(r\_\{0\}\-\\\|x\-z\_\{v\}\\\|\_\{\\infty\}\\bigr\)\_\{\+\},\\qquad G\_\{v\}=B\_\{\\infty\}\(z\_\{v\},r\_\{0\}/2\)\.\(22\)Writeℙv∘,𝔼v∘\\mathbb\{P\}\_\{v\}^\{\\circ\},\\mathbb\{E\}\_\{v\}^\{\\circ\}for the interaction law and expectation under meangvg\_\{v\}\. The functions are one\-Lipschitz and take values in\[1/4,3/8\]\[1/4,3/8\]\. The setsG1,…,GNG\_\{1\},\\ldots,G\_\{N\}are disjoint, and everyx∉Gvx\\notin G\_\{v\}satisfies

gv⋆−gv​\(x\)≥r0/2\.g\_\{v\}^\{\\star\}\-g\_\{v\}\(x\)\\geq r\_\{0\}/2\.\(23\)
LetV0V\_\{0\}be uniform on\[N\]\[N\]and independent ofℱ0\\mathcal\{F\}\_\{0\}, and letℙ∘\\mathbb\{P\}^\{\\circ\}denote the resulting mixture law\. WriteNv​\(T\)=∑t=1T𝟏\{At∈Gv\}N\_\{v\}\(T\)=\\sum\_\{t=1\}^\{T\}\\mathbf\{1\}\_\{\\\{A\_\{t\}\\in G\_\{v\}\\\}\}\. Averaging \([23](https://arxiv.org/html/2608.07922#A2.E23)\) over the prior gives

1N​∑v=1N𝔼v∘​RegT​\(gv\)≥r02​\[T−1N​∑v=1N𝔼v∘​Nv​\(T\)\]\.\\frac\{1\}\{N\}\\sum\_\{v=1\}^\{N\}\\mathbb\{E\}\_\{v\}^\{\\circ\}\\mathrm\{Reg\}\_\{T\}\(g\_\{v\}\)\\geq\\frac\{r\_\{0\}\}\{2\}\\left\[T\-\\frac\{1\}\{N\}\\sum\_\{v=1\}^\{N\}\\mathbb\{E\}\_\{v\}^\{\\circ\}N\_\{v\}\(T\)\\right\]\.\(24\)
For almost every seed realizationww, Lemma[3\.2](https://arxiv.org/html/2608.07922#S3.Thmtheorem2)gives the transcript codebook

ℭ​\(w\):=𝖱𝖾𝖼𝒜​\(w,\(\{0,1\}W\)B−1\),\|ℭ​\(w\)\|≤N0\.\\mathfrak\{C\}\(w\):=\\mathsf\{Rec\}\_\{\\mathcal\{A\}\}\\bigl\(w,\(\\\{0,1\\\}^\{W\}\)^\{B\-1\}\\bigr\),\\qquad\|\\mathfrak\{C\}\(w\)\|\\leq N\_\{0\}\.Condition onω=w\\omega=wand define a randomized decoder fromA1:TA\_\{1:T\}: drawUUuniformly from\[T\]\[T\], output the uniquejjfor whichAU∈GjA\_\{U\}\\in G\_\{j\}when such ajjexists, and output an arbitrary index otherwise\. Its conditional success probability satisfies

ℙ∘​\(V^0=V0∣ω=w\)≥1N​T​∑v=1N𝔼v∘​\[Nv​\(T\)∣ω=w\]\.\\mathbb\{P\}^\{\\circ\}\(\\widehat\{V\}\_\{0\}=V\_\{0\}\\mid\\omega=w\)\\geq\\frac\{1\}\{NT\}\\sum\_\{v=1\}^\{N\}\\mathbb\{E\}\_\{v\}^\{\\circ\}\\\!\\left\[N\_\{v\}\(T\)\\mid\\omega=w\\right\]\.\(25\)On the other hand, any randomized decoder based on an observation with at mostN0N\_\{0\}values has average success probability at mostN0/N=1/2N\_\{0\}/N=1/2\. Letpv∘​\(𝔱∣w\)p\_\{v\}^\{\\circ\}\(\\mathfrak\{t\}\\mid w\)be a version of the conditional transcript law under hypothesisvv, and let𝖰​\(v∣𝔱,w\)\\mathsf\{Q\}\(v\\mid\\mathfrak\{t\},w\)be the decoder\. Then, for almost everyww,

ℙ∘​\(V^0=V0∣ω=w\)\\displaystyle\\mathbb\{P\}^\{\\circ\}\(\\widehat\{V\}\_\{0\}=V\_\{0\}\\mid\\omega=w\)=1N​∑𝔱∈ℭ​\(w\)∑v=1Npv∘​\(𝔱∣w\)​𝖰​\(v∣𝔱,w\)\\displaystyle=\\frac\{1\}\{N\}\\sum\_\{\\mathfrak\{t\}\\in\\mathfrak\{C\}\(w\)\}\\sum\_\{v=1\}^\{N\}p\_\{v\}^\{\\circ\}\(\\mathfrak\{t\}\\mid w\)\\mathsf\{Q\}\(v\\mid\\mathfrak\{t\},w\)\(26\)≤\|ℭ​\(w\)\|N≤N0N=12\.\\displaystyle\\leq\\frac\{\|\\mathfrak\{C\}\(w\)\|\}\{N\}\\leq\\frac\{N\_\{0\}\}\{N\}=\\frac\{1\}\{2\}\.\(27\)Integrating \([25](https://arxiv.org/html/2608.07922#A2.E25)\)– \([27](https://arxiv.org/html/2608.07922#A2.E27)\) overwwgivesN−1​∑v𝔼v∘​Nv​\(T\)≤T/2N^\{\-1\}\\sum\_\{v\}\\mathbb\{E\}\_\{v\}^\{\\circ\}N\_\{v\}\(T\)\\leq T/2\. Substituting into \([24](https://arxiv.org/html/2608.07922#A2.E24)\) and using \([21](https://arxiv.org/html/2608.07922#A2.E21)\) gives

supv𝔼v∘​RegT​\(gv\)≥r0​T4≥cd​T​N−1/d=cd​T​2−χ/d\.\\sup\_\{v\}\\mathbb\{E\}\_\{v\}^\{\\circ\}\\mathrm\{Reg\}\_\{T\}\(g\_\{v\}\)\\geq\\frac\{r\_\{0\}T\}\{4\}\\geq c\_\{d\}TN^\{\-1/d\}=c\_\{d\}T2^\{\-\\chi/d\}\.∎

### B\.2Geometry of the regional\-routing hard family

For indexed centersuj,au\_\{j,a\}andzj,a,kz\_\{j,a,k\}, use the geometric notation

Cj,a:=B∞​\(uj,a,s\),Gj,a,k:=B∞​\(zj,a,k,r\)\.C\_\{j,a\}:=B\_\{\\infty\}\(u\_\{j,a\},s\),\\qquad G\_\{j,a,k\}:=B\_\{\\infty\}\(z\_\{j,a,k\},r\)\.
###### Lemma B\.1\(Separated regional packing\)\.

For everyd≥1d\\geq 1, there exist constantscd,Cd,sd\>0c\_\{d\},C\_\{d\},s\_\{d\}\>0such that, for0<s≤sd0<s\\leq s\_\{d\}and0<r≤s/160<r\\leq s/16, one can choose integersm,qm,q, centersuj,a∈\[1/4,3/4\]du\_\{j,a\}\\in\[1/4,3/4\]^\{d\}, and centerszj,a,kz\_\{j,a,k\}satisfying

cd​s−d≤m≤Cd​s−d,\\displaystyle c\_\{d\}s^\{\-d\}\\leq m\\leq C\_\{d\}s^\{\-d\},cd​\(s/r\)d≤q≤Cd​\(s/r\)d,\\displaystyle\\qquad c\_\{d\}\(s/r\)^\{d\}\\leq q\\leq C\_\{d\}\(s/r\)^\{d\},‖uj,a−uj′,a′‖∞≥8​s\\displaystyle\\\|u\_\{j,a\}\-u\_\{j^\{\\prime\},a^\{\\prime\}\}\\\|\_\{\\infty\}\\geq 8s\(\(j,a\)≠\(j′,a′\)\),\\displaystyle\\qquad\(\(j,a\)\\neq\(j^\{\\prime\},a^\{\\prime\}\)\),zj,a,k∈B∞​\(uj,a,s/4\),\\displaystyle z\_\{j,a,k\}\\in B\_\{\\infty\}\(u\_\{j,a\},s/4\),‖zj,a,k−zj,a,k′‖∞≥4​r\(k≠k′\)\.\\displaystyle\\qquad\\\|z\_\{j,a,k\}\-z\_\{j,a,k^\{\\prime\}\}\\\|\_\{\\infty\}\\geq 4r\\quad\(k\\neq k^\{\\prime\}\)\.The associated sets satisfyGj,a,k⊂Cj,aG\_\{j,a,k\}\\subset C\_\{j,a\}, and the family\{Gj,a,k:j∈\[m\],a∈\{0,1\},k∈\[q\]\}\\\{G\_\{j,a,k\}:j\\in\[m\],\\ a\\in\\\{0,1\\\},\\ k\\in\[q\]\\\}is pairwise disjoint\.

###### Proof of Lemma[B\.1](https://arxiv.org/html/2608.07922#A2.Thmtheorem1)\.

Set

Ms:=⌊\(16​s\)−1⌋,𝒰:=14​𝟏d\+8​s​\{0,1,…,Ms\}d\.M\_\{s\}:=\\left\\lfloor\(16s\)^\{\-1\}\\right\\rfloor,\\qquad\\mathcal\{U\}:=\\frac\{1\}\{4\}\\boldsymbol\{1\}\_\{d\}\+8s\\\{0,1,\\ldots,M\_\{s\}\\\}^\{d\}\.Forsds\_\{d\}sufficiently small,

𝒰\\displaystyle\\mathcal\{U\}⊂\[1/4,3/4\]d,\\displaystyle\\subset\[1/4,3/4\]^\{d\},minu≠u′⁡‖u−u′‖∞\\displaystyle\\min\_\{u\\neq u^\{\\prime\}\}\\\|u\-u^\{\\prime\}\\\|\_\{\\infty\}≥8​s,\\displaystyle\\geq 8s,\(Ms\+1\)d\\displaystyle\(M\_\{s\}\+1\)^\{d\}≍ds−d\.\\displaystyle\\asymp\_\{d\}s^\{\-d\}\.Choose an even subset of𝒰\\mathcal\{U\}of cardinality2​m≍ds−d2m\\asymp\_\{d\}s^\{\-d\}and pair its elements as\(uj,0,uj,1\)j=1m\(u\_\{j,0\},u\_\{j,1\}\)\_\{j=1\}^\{m\}\.

For eachu∈𝒰u\\in\\mathcal\{U\}, set

Ms,r:=⌊s8​r⌋,𝒵​\(u\):=u−s4​𝟏d\+4​r​\{0,1,…,Ms,r\}d\.M\_\{s,r\}:=\\left\\lfloor\\frac\{s\}\{8r\}\\right\\rfloor,\\qquad\\mathcal\{Z\}\(u\):=u\-\\frac\{s\}\{4\}\\boldsymbol\{1\}\_\{d\}\+4r\\\{0,1,\\ldots,M\_\{s,r\}\\\}^\{d\}\.Sincer≤s/16r\\leq s/16,

𝒵​\(u\)\\displaystyle\\mathcal\{Z\}\(u\)⊂B∞​\(u,s/4\),\\displaystyle\\subset B\_\{\\infty\}\(u,s/4\),\|𝒵​\(u\)\|\\displaystyle\|\\mathcal\{Z\}\(u\)\|=\(Ms,r\+1\)d≍d\(s/r\)d,\\displaystyle=\(M\_\{s,r\}\+1\)^\{d\}\\asymp\_\{d\}\(s/r\)^\{d\},minz≠z′∈𝒵​\(u\)⁡‖z−z′‖∞\\displaystyle\\min\_\{z\\neq z^\{\\prime\}\\in\\mathcal\{Z\}\(u\)\}\\\|z\-z^\{\\prime\}\\\|\_\{\\infty\}≥4​r\.\\displaystyle\\geq 4r\.Retain the same numberq≍d\(s/r\)dq\\asymp\_\{d\}\(s/r\)^\{d\}of points from every𝒵​\(uj,a\)\\mathcal\{Z\}\(u\_\{j,a\}\)\. For each retained center,

‖zj,a,k−uj,a‖∞\+r≤s4\+s16<s,\\\|z\_\{j,a,k\}\-u\_\{j,a\}\\\|\_\{\\infty\}\+r\\leq\\frac\{s\}\{4\}\+\\frac\{s\}\{16\}<s,soGj,a,k⊂Cj,aG\_\{j,a,k\}\\subset C\_\{j,a\}\. If two probes have the same parent, their centers are at distance at least4​r4r, hence their radius\-rrballs are disjoint\. If their parents differ, then

‖zj,a,k−zj′,a′,k′‖∞≥8​s−s4−s4=15​s2\>2​r,\\\|z\_\{j,a,k\}\-z\_\{j^\{\\prime\},a^\{\\prime\},k^\{\\prime\}\}\\\|\_\{\\infty\}\\geq 8s\-\\frac\{s\}\{4\}\-\\frac\{s\}\{4\}=\\frac\{15s\}\{2\}\>2r,which proves disjointness across parents\. ∎

The disjoint packing has two consequences used throughout the proof\. First, KL divergence between a base instance and a local comparison instance is supported only on the visited probe\. Second, pulls in distinct unselected\-side probes contribute additively to the pathwise regret charge\.

###### Definition B\.2\(Base and local Bernoulli instances\)\.

Fix a packing from Lemma[B\.1](https://arxiv.org/html/2608.07922#A2.Thmtheorem1)\. Forv∈\{0,1\}mv\\in\\\{0,1\\\}^\{m\}, define the base mean

fv\(x\):=14\+maxj∈\[m\]\(s4−12d∞\(x,Cj,vj\)\)\+\.f\_\{v\}\(x\):=\\frac\{1\}\{4\}\+\\max\_\{j\\in\[m\]\}\\left\(\\frac\{s\}\{4\}\-\\frac\{1\}\{2\}d\_\{\\infty\}\(x,C\_\{j,v\_\{j\}\}\)\\right\)\_\{\+\}\.Forj∈\[m\]j\\in\[m\]andk∈\[q\]k\\in\[q\], define the local alternative

fv,j,k\+​\(x\):=fv​\(x\)\+12​\(r−‖x−zj,vj,k‖∞\)\+\.f^\{\+\}\_\{v,j,k\}\(x\):=f\_\{v\}\(x\)\+\\frac\{1\}\{2\}\\left\(r\-\\\|x\-z\_\{j,v\_\{j\},k\}\\\|\_\{\\infty\}\\right\)\_\{\+\}\.\(28\)The associated bandit instances have independent Bernoulli rewards with these means\. Writeℙv,𝔼v\\mathbb\{P\}\_\{v\},\\mathbb\{E\}\_\{v\}for the law and expectation underfvf\_\{v\}, andℙv,j,k\+,𝔼v,j,k\+\\mathbb\{P\}^\{\+\}\_\{v,j,k\},\\mathbb\{E\}^\{\+\}\_\{v,j,k\}for those underfv,j,k\+f^\{\+\}\_\{v,j,k\}\. The bitvjv\_\{j\}selects the cellCj,vjC\_\{j,v\_\{j\}\}that lies on the optimal plateau; alternative\(v,j,k\)\(v,j,k\)changes only probeGj,vj,kG\_\{j,v\_\{j\},k\}inside that selected cell\.

###### Lemma B\.3\(Geometry of the hard family\)\.

Every mean in Definition[B\.2](https://arxiv.org/html/2608.07922#A2.Thmtheorem2)belongs toLip1​\(𝒳\)\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)and takes values in\[1/4,3/4\]\[1/4,3/4\]\. Moreover,

fv⋆=14\+s4,\(fv,j,k\+\)⋆=14\+s4\+r2\.f\_\{v\}^\{\\star\}=\\frac\{1\}\{4\}\+\\frac\{s\}\{4\},\\qquad\(f^\{\+\}\_\{v,j,k\}\)^\{\\star\}=\\frac\{1\}\{4\}\+\\frac\{s\}\{4\}\+\\frac\{r\}\{2\}\.For all admissible indices,

fv⋆−fv​\(x\)\\displaystyle f\_\{v\}^\{\\star\}\-f\_\{v\}\(x\)≥s/4,\\displaystyle\\geq s/4,x∈Cj,1−vj,\\displaystyle x\\in C\_\{j,1\-v\_\{j\}\},\(29\)\(fv,j,k\+\)⋆−fv,j,k\+​\(x\)\\displaystyle\(f^\{\+\}\_\{v,j,k\}\)^\{\\star\}\-f^\{\+\}\_\{v,j,k\}\(x\)≥r/2,\\displaystyle\\geq r/2,x∉Gj,vj,k,\\displaystyle x\\notin G\_\{j,v\_\{j\},k\},\(30\)0≤fv,j,k\+​\(x\)−fv​\(x\)\\displaystyle 0\\leq f^\{\+\}\_\{v,j,k\}\(x\)\-f\_\{v\}\(x\)≤r/2,\\displaystyle\\leq r/2,x∈𝒳,\\displaystyle x\\in\\mathcal\{X\},\(31\)fv,j,k\+​\(x\)\\displaystyle f^\{\+\}\_\{v,j,k\}\(x\)=fv​\(x\),\\displaystyle=f\_\{v\}\(x\),x∉Gj,vj,k\.\\displaystyle x\\notin G\_\{j,v\_\{j\},k\}\.\(32\)

###### Proof of Lemma[B\.3](https://arxiv.org/html/2608.07922#A2.Thmtheorem3)\.

For every nonemptyC⊆ℝdC\\subseteq\\mathbb\{R\}^\{d\},

\|d∞​\(x,C\)−d∞​\(y,C\)\|≤‖x−y‖∞\.\|d\_\{\\infty\}\(x,C\)\-d\_\{\\infty\}\(y,C\)\|\\leq\\\|x\-y\\\|\_\{\\infty\}\.Sinceu↦\(u\)\+u\\mapsto\(u\)\_\{\+\}is one\-Lipschitz,

Lip​\[\(s4−12​d∞​\(⋅,C\)\)\+\]\\displaystyle\\mathrm\{Lip\}\\\!\\left\[\\left\(\\frac\{s\}\{4\}\-\\frac\{1\}\{2\}d\_\{\\infty\}\(\\cdot,C\)\\right\)\_\{\+\}\\right\]≤12,\\displaystyle\\leq\\frac\{1\}\{2\},Lip\[12\(r−∥⋅−z∥∞\)\+\]\\displaystyle\\mathrm\{Lip\}\\\!\\left\[\\frac\{1\}\{2\}\\left\(r\-\\\|\\cdot\-z\\\|\_\{\\infty\}\\right\)\_\{\+\}\\right\]≤12\.\\displaystyle\\leq\\frac\{1\}\{2\}\.The maximum of1/21/2\-Lipschitz functions is1/21/2\-Lipschitz, so

Lip​\(fv\)≤12,Lip​\(fv,j,k\+\)≤1\.\\mathrm\{Lip\}\(f\_\{v\}\)\\leq\\frac\{1\}\{2\},\\qquad\\mathrm\{Lip\}\(f^\{\+\}\_\{v,j,k\}\)\\leq 1\.Moreover,

14≤fv≤14\+s4,14≤fv,j,k\+≤14\+s4\+r2≤34\\frac\{1\}\{4\}\\leq f\_\{v\}\\leq\\frac\{1\}\{4\}\+\\frac\{s\}\{4\},\\qquad\\frac\{1\}\{4\}\\leq f^\{\+\}\_\{v,j,k\}\\leq\\frac\{1\}\{4\}\+\\frac\{s\}\{4\}\+\\frac\{r\}\{2\}\\leq\\frac\{3\}\{4\}after fixingsds\_\{d\}sufficiently small\.

For every selected cellCi,viC\_\{i,v\_\{i\}\},fv=1/4\+s/4f\_\{v\}=1/4\+s/4on that cell; hence

fv⋆=14\+s4\.f\_\{v\}^\{\\star\}=\\frac\{1\}\{4\}\+\\frac\{s\}\{4\}\.Ifx∈Cj,1−vjx\\in C\_\{j,1\-v\_\{j\}\}, parent separation gives, for everyii,

d∞​\(x,Ci,vi\)≥8​s−s−s=6​s,d\_\{\\infty\}\(x,C\_\{i,v\_\{i\}\}\)\\geq 8s\-s\-s=6s,and therefore

fv​\(x\)=14,fv⋆−fv​\(x\)=s4\.f\_\{v\}\(x\)=\\frac\{1\}\{4\},\\qquad f\_\{v\}^\{\\star\}\-f\_\{v\}\(x\)=\\frac\{s\}\{4\}\.This proves \([29](https://arxiv.org/html/2608.07922#A2.E29)\)\.

By \([28](https://arxiv.org/html/2608.07922#A2.E28)\), atzj,vj,kz\_\{j,v\_\{j\},k\}the base mean equals1/4\+s/41/4\+s/4and the bump equalsr/2r/2; thus

\(fv,j,k\+\)⋆=14\+s4\+r2\.\(f^\{\+\}\_\{v,j,k\}\)^\{\\star\}=\\frac\{1\}\{4\}\+\\frac\{s\}\{4\}\+\\frac\{r\}\{2\}\.For everyx∉Gj,vj,kx\\notin G\_\{j,v\_\{j\},k\},

fv,j,k\+​\(x\)=fv​\(x\)≤14\+s4,f^\{\+\}\_\{v,j,k\}\(x\)=f\_\{v\}\(x\)\\leq\\frac\{1\}\{4\}\+\\frac\{s\}\{4\},which gives \([30](https://arxiv.org/html/2608.07922#A2.E30)\) and \([32](https://arxiv.org/html/2608.07922#A2.E32)\)\. Finally,

0≤fv,j,k\+​\(x\)−fv​\(x\)=12​\(r−‖x−zj,vj,k‖∞\)\+≤r2,0\\leq f^\{\+\}\_\{v,j,k\}\(x\)\-f\_\{v\}\(x\)=\\frac\{1\}\{2\}\\left\(r\-\\\|x\-z\_\{j,v\_\{j\},k\}\\\|\_\{\\infty\}\\right\)\_\{\+\}\\leq\\frac\{r\}\{2\},completing the proof\. ∎

The geometry supplies the three parameters needed by the comparison argument: the one\-step mean perturbation isO​\(r\)O\(r\), the alternative gap outside its probe isΘ​\(r\)\\Theta\(r\), and every pull in the unselected cell pays gapΘ​\(s\)\\Theta\(s\)\. Together with Bernoulli quadratic KL, these become a one\-step divergenceO​\(r2\)O\(r^\{2\}\), a testing thresholdΘ​\(r−2\)\\Theta\(r^\{\-2\}\), and anss\-scale misrouting regret charge\.

### B\.3Stopped local comparison

The following lemma adapts the localized under\-sampling change\-of\-measure principle ofHuanget al\.\([2026](https://arxiv.org/html/2608.07922#bib.bib25)\)from one finite arm to a measurable spatial probe with location\-dependent reward kernels\.

Fix a measurable setG⊆𝒳G\\subseteq\\mathcal\{X\}and two reward kernelsνi=\(νi,x\)x∈𝒳\\nu\_\{i\}=\(\\nu\_\{i,x\}\)\_\{x\\in\\mathcal\{X\}\},i∈\{0,1\}i\\in\\\{0,1\\\}\. Under a fixed adaptive policy, denote the induced interaction laws and expectations byℙi,𝔼i\\mathbb\{P\}\_\{i\},\\mathbb\{E\}\_\{i\}, and set

NG​\(t\):=∑u=1t𝟏\{Au∈G\}\.N\_\{G\}\(t\):=\\sum\_\{u=1\}^\{t\}\\mathbf\{1\}\_\{\\\{A\_\{u\}\\in G\\\}\}\.Ifμ1​\(x\):=𝔼ν1,x​Y\\mu\_\{1\}\(x\):=\\mathbb\{E\}\_\{\\nu\_\{1,x\}\}Yandμ1⋆:=supxμ1​\(x\)\\mu\_\{1\}^\{\\star\}:=\\sup\_\{x\}\\mu\_\{1\}\(x\), writeΔ1​\(x\):=μ1⋆−μ1​\(x\)\\Delta\_\{1\}\(x\):=\\mu\_\{1\}^\{\\star\}\-\\mu\_\{1\}\(x\)andRegT\(1\):=∑t=1TΔ1​\(At\)\\mathrm\{Reg\}\_\{T\}^\{\(1\)\}:=\\sum\_\{t=1\}^\{T\}\\Delta\_\{1\}\(A\_\{t\}\)\.

###### Lemma B\.4\(Stopped local comparison\)\.

Assume

ν1,x=ν0,x\(x∉G\),supx∈GD​\(ν1,x∥ν0,x\)≤κ,\\nu\_\{1,x\}=\\nu\_\{0,x\}\\quad\(x\\notin G\),\\qquad\\sup\_\{x\\in G\}D\(\\nu\_\{1,x\}\\\|\\nu\_\{0,x\}\)\\leq\\kappa,andinfx∉GΔ1​\(x\)≥Δ\>0\\inf\_\{x\\notin G\}\\Delta\_\{1\}\(x\)\\geq\\Delta\>0\. Then, for every integer1≤n<T1\\leq n<T,

ℙ0​\(NG​\(T\)≥n\)≥1−𝔼1​RegT\(1\)Δ​\(T−n\)−n​κ/2\.\\mathbb\{P\}\_\{0\}\\\!\\left\(N\_\{G\}\(T\)\\geq n\\right\)\\geq 1\-\\frac\{\\mathbb\{E\}\_\{1\}\\mathrm\{Reg\}\_\{T\}^\{\(1\)\}\}\{\\Delta\(T\-n\)\}\-\\sqrt\{n\\kappa/2\}\.\(33\)

###### Proof of Lemma[B\.4](https://arxiv.org/html/2608.07922#A2.Thmtheorem4)\.

Let\(ℱt\)t=0T\(\\mathcal\{F\}\_\{t\}\)\_\{t=0\}^\{T\}be the transcript filtration including the algorithmic seed, and set

τn:=inf\{t≤T:NG​\(t\)≥n\}∧T,En:=\{NG​\(T\)≥n\}\.\\tau\_\{n\}:=\\inf\\\{t\\leq T:N\_\{G\}\(t\)\\geq n\\\}\\wedge T,\\qquad E\_\{n\}:=\\\{N\_\{G\}\(T\)\\geq n\\\}\.Predictability ofAtA\_\{t\}and the stopped chain rule give

D\(ℙ1\|ℱτn∥ℙ0\|ℱτn\)\\displaystyle D\\\!\\left\(\\left\.\\mathbb\{P\}\_\{1\}\\right\|\_\{\\mathcal\{F\}\_\{\\tau\_\{n\}\}\}\\middle\\\|\\left\.\\mathbb\{P\}\_\{0\}\\right\|\_\{\\mathcal\{F\}\_\{\\tau\_\{n\}\}\}\\right\)=𝔼1​\[∑t=1τnD​\(ν1,At∥ν0,At\)\]\\displaystyle=\\mathbb\{E\}\_\{1\}\\\!\\left\[\\sum\_\{t=1\}^\{\\tau\_\{n\}\}D\(\\nu\_\{1,A\_\{t\}\}\\\|\\nu\_\{0,A\_\{t\}\}\)\\right\]\(34\)≤κ​𝔼1​NG​\(τn\)≤n​κ\.\\displaystyle\\leq\\kappa\\mathbb\{E\}\_\{1\}N\_\{G\}\(\\tau\_\{n\}\)\\leq n\\kappa\.\(35\)SinceEn∈ℱτnE\_\{n\}\\in\\mathcal\{F\}\_\{\\tau\_\{n\}\}, Pinsker’s inequality and \([35](https://arxiv.org/html/2608.07922#A2.E35)\) imply

ℙ0​\(En\)≥ℙ1​\(En\)−n​κ/2\.\\mathbb\{P\}\_\{0\}\(E\_\{n\}\)\\geq\\mathbb\{P\}\_\{1\}\(E\_\{n\}\)\-\\sqrt\{n\\kappa/2\}\.\(36\)OnEn∁E\_\{n\}^\{\\complement\},

RegT\(1\)=∑t=1TΔ1​\(At\)≥Δ​∑t=1T𝟏\{At∉G\}=Δ​\(T−NG​\(T\)\)≥Δ​\(T−n\)\.\\mathrm\{Reg\}\_\{T\}^\{\(1\)\}=\\sum\_\{t=1\}^\{T\}\\Delta\_\{1\}\(A\_\{t\}\)\\geq\\Delta\\sum\_\{t=1\}^\{T\}\\mathbf\{1\}\_\{\\\{A\_\{t\}\\notin G\\\}\}=\\Delta\\bigl\(T\-N\_\{G\}\(T\)\\bigr\)\\geq\\Delta\(T\-n\)\.Therefore

ℙ1​\(En∁\)≤𝔼1​RegT\(1\)Δ​\(T−n\)\.\\mathbb\{P\}\_\{1\}\(E\_\{n\}^\{\\complement\}\)\\leq\\frac\{\\mathbb\{E\}\_\{1\}\\mathrm\{Reg\}\_\{T\}^\{\(1\)\}\}\{\\Delta\(T\-n\)\}\.\(37\)Substitution of \([37](https://arxiv.org/html/2608.07922#A2.E37)\) into \([36](https://arxiv.org/html/2608.07922#A2.E36)\) proves \([33](https://arxiv.org/html/2608.07922#A2.E33)\)\. ∎

For the hard family, substitutingn≍r−2n\\asymp r^\{\-2\},κ≍r2\\kappa\\asymp r^\{2\}, andΔ≍r\\Delta\\asymp rmakes both error terms in \([33](https://arxiv.org/html/2608.07922#A2.E33)\) bounded away from one whenever the comparison\-instance regret iso​\(T​r\)o\(Tr\)\. Thus each selected probe crosses the threshold with constant probability under the corresponding base law\.

Foru,v∈\[1/4,3/4\]u,v\\in\[1/4,3/4\], the elementary Bernoulli bound gives

d​\(u∥v\)≤\(u−v\)2v​\(1−v\)≤163​\(u−v\)2\.d\(u\\\|v\)\\leq\\frac\{\(u\-v\)^\{2\}\}\{v\(1\-v\)\}\\leq\\frac\{16\}\{3\}\(u\-v\)^\{2\}\.\(38\)The additive bump changes a mean by at mostr/2r/2, so its one\-step divergence is at most4​r2/34r^\{2\}/3\. Withn≍r−2n\\asymp r^\{\-2\}, the stopped transcript KL is therefore bounded by a numerical constant\. Low regret under a local alternative must consequently produce a constant probability of crossing the probe\-count threshold under the corresponding base instance\.

### B\.4Verification and routing from the regional family

###### Proof of Lemma[4\.1](https://arxiv.org/html/2608.07922#S4.Thmtheorem1)\.

Fix an arbitrary policy and letℛ\\mathcal\{R\}be its largest expected regret over the base instances and local alternatives in the regional family\. Supposeℛ<cd​T​r\\mathcal\{R\}<c\_\{d\}Trfor a sufficiently small constant\. Choosen=⌊c0​r−2⌋n=\\lfloor c\_\{0\}r^\{\-2\}\\rfloorwithc0\>0c\_\{0\}\>0sufficiently small\. By shrinkingsds\_\{d\}and enlarging the constant inT​r2≥CdTr^\{2\}\\geq C\_\{d\}, we may assume2≤n≤T/42\\leq n\\leq T/4\.

For everyv,j,kv,j,k, letEv,j,k=\{Nj,vj,k​\(T\)≥n\}E\_\{v,j,k\}=\\\{N\_\{j,v\_\{j\},k\}\(T\)\\geq n\\\}\. Apply Lemma[B\.4](https://arxiv.org/html/2608.07922#A2.Thmtheorem4)with

G=Gj,vj,k,κ=43​r2,Δ=r/2\.G=G\_\{j,v\_\{j\},k\},\\qquad\\kappa=\\frac\{4\}\{3\}r^\{2\},\\qquad\\Delta=r/2\.Equations \([30](https://arxiv.org/html/2608.07922#A2.E30)\)–\([32](https://arxiv.org/html/2608.07922#A2.E32)\) and \([38](https://arxiv.org/html/2608.07922#A2.E38)\) give

ℙv​\(Ev,j,k\)≥1−2​ℛr​\(T−n\)−23​n​r2≥58\.\\mathbb\{P\}\_\{v\}\(E\_\{v,j,k\}\)\\geq 1\-\\frac\{2\\mathcal\{R\}\}\{r\(T\-n\)\}\-\\sqrt\{\\frac\{2\}\{3\}nr^\{2\}\}\\geq\\frac\{5\}\{8\}\.\(39\)For fixedvv, the selected probes\{Gj,vj,k:j∈\[m\],k∈\[q\]\}\\\{G\_\{j,v\_\{j\},k\}:j\\in\[m\],k\\in\[q\]\\\}are pairwise disjoint\. Therefore

T\\displaystyle T≥𝔼v​∑j=1m∑k=1qNj,vj,k​\(T\)\\displaystyle\\geq\\mathbb\{E\}\_\{v\}\\sum\_\{j=1\}^\{m\}\\sum\_\{k=1\}^\{q\}N\_\{j,v\_\{j\},k\}\(T\)≥n​∑j=1m∑k=1qℙv​\(Ev,j,k\)\\displaystyle\\geq n\\sum\_\{j=1\}^\{m\}\\sum\_\{k=1\}^\{q\}\\mathbb\{P\}\_\{v\}\(E\_\{v,j,k\}\)≥58​m​q​n≥cd​r−d−2,\\displaystyle\\geq\\frac\{5\}\{8\}mqn\\geq c\_\{d\}r^\{\-d\-2\},where the last inequality uses Lemma[B\.1](https://arxiv.org/html/2608.07922#A2.Thmtheorem1)andn≍r−2n\\asymp r^\{\-2\}\. This contradictsr−d−2≥Cd​Tr^\{\-d\-2\}\\geq C\_\{d\}TwhenCdC\_\{d\}is chosen large enough\. Hence some instance in the family has expected regret at leastcd​T​rc\_\{d\}Tr, uniformly overBBandWW\. ∎

###### Proof of Corollary[4\.2](https://arxiv.org/html/2608.07922#S4.Thmtheorem2)\.

Choose a sufficiently small constantad\>0a\_\{d\}\>0and set

r=ad​T−1/\(d\+2\),s=16​r\.r=a\_\{d\}T^\{\-1/\(d\+2\)\},\\qquad s=16r\.ForT≥TdT\\geq T\_\{d\}, these scales satisfys≤sds\\leq s\_\{d\}andT​r2≥CdTr^\{2\}\\geq C\_\{d\}\. Takingada\_\{d\}small enough also ensuresr−d−2=ad−\(d\+2\)​T≥Cd​Tr^\{\-d\-2\}=a\_\{d\}^\{\-\(d\+2\)\}T\\geq C\_\{d\}T\. Lemma[4\.1](https://arxiv.org/html/2608.07922#S4.Thmtheorem1)then gives

ℜT​\(B,W\)≥cd​T​r=cd​T\(d\+1\)/\(d\+2\)\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}Tr=c\_\{d\}T^\{\(d\+1\)/\(d\+2\)\}for everyBBandWW\. ∎

###### Definition B\.5\(Prior and randomized transcript decoder\)\.

LetVVbe uniform on\{0,1\}m\\\{0,1\\\}^\{m\}and independent ofℱ0\\mathcal\{F\}\_\{0\}, and run the base Bernoulli instance with meanfVf\_\{V\}\. Writeℙ¯\\overline\{\\mathbb\{P\}\}and𝔼¯\\overline\{\\mathbb\{E\}\}for the resulting mixture law and expectation\. The local alternatives are comparison instances and are not sampled by this prior\. Fixn=⌊c0​r−2⌋n=\\lfloor c\_\{0\}r^\{\-2\}\\rfloorfor the same sufficiently small numerical constant\. Forj∈\[m\]j\\in\[m\],a∈\{0,1\}a\\in\\\{0,1\\\}, andk∈\[q\]k\\in\[q\], define

Nj,a,k​\(t\):=∑t′=1t𝟏\{At′∈Gj,a,k\},ρj,a:=1q​∑k=1q𝟏\{Nj,a,k​\(T\)≥n\}\.N\_\{j,a,k\}\(t\):=\\sum\_\{t^\{\\prime\}=1\}^\{t\}\\mathbf\{1\}\_\{\\\{A\_\{t^\{\\prime\}\}\\in G\_\{j,a,k\}\\\}\},\\qquad\\rho\_\{j,a\}:=\\frac\{1\}\{q\}\\sum\_\{k=1\}^\{q\}\\mathbf\{1\}\_\{\\\{N\_\{j,a,k\}\(T\)\\geq n\\\}\}\.After the action transcript is generated, sample fresh independent fair bitsξ1,…,ξm\\xi\_\{1\},\\ldots,\\xi\_\{m\}, independent of the learner, latent routing vector, seed, and transcript\. If exactly one sidea∈\{0,1\}a\\in\\\{0,1\\\}satisfiesρj,a≥1/4\\rho\_\{j,a\}\\geq 1/4, setV^j=a\\widehat\{V\}\_\{j\}=a; otherwise setV^j=ξj\\widehat\{V\}\_\{j\}=\\xi\_\{j\}\. ThusV^\\widehat\{V\}is randomized post\-processing of\(A1:T,ℱ0\)\(A\_\{1:T\},\\mathcal\{F\}\_\{0\}\)\.

###### Proof of Lemma[4\.3](https://arxiv.org/html/2608.07922#S4.Thmtheorem3)\.

Fix a policy𝒜∈𝔄B,W\\mathcal\{A\}\\in\\mathfrak\{A\}\_\{B,W\}and letℛ\\mathcal\{R\}be its largest expected regret over the base instances and all local alternatives\. Suppose, toward a contradiction, that

ℛ<cd​min⁡\{T​r,s​r−d−2\}\\mathcal\{R\}<c\_\{d\}\\min\\\{Tr,sr^\{\-d\-2\}\\\}\(40\)for a sufficiently small constant\. Setn=⌊c0​r−2⌋n=\\lfloor c\_\{0\}r^\{\-2\}\\rflooras in Definition[B\.5](https://arxiv.org/html/2608.07922#A2.Thmtheorem5)\. After shrinkingsds\_\{d\}and enlarging the threshold onT​r2Tr^\{2\}, we have2≤n≤T/42\\leq n\\leq T/4\.

Selected\-region verification\.The stopped\-comparison calculation in the proof of Lemma[4\.1](https://arxiv.org/html/2608.07922#S4.Thmtheorem1)applies verbatim under \([40](https://arxiv.org/html/2608.07922#A2.E40)\)\. Thus, for everyv,j,kv,j,k, \([39](https://arxiv.org/html/2608.07922#A2.E39)\) holds\. Sinceρj,vj∈\[0,1\]\\rho\_\{j,v\_\{j\}\}\\in\[0,1\]and𝔼v​ρj,vj≥5/8\\mathbb\{E\}\_\{v\}\\rho\_\{j,v\_\{j\}\}\\geq 5/8,

ℙv​\(ρj,vj≥1/4\)≥𝔼v​ρj,vj−1/43/4≥12\.\\mathbb\{P\}\_\{v\}\(\\rho\_\{j,v\_\{j\}\}\\geq 1/4\)\\geq\\frac\{\\mathbb\{E\}\_\{v\}\\rho\_\{j,v\_\{j\}\}\-1/4\}\{3/4\}\\geq\\frac\{1\}\{2\}\.Averaging overvvandjjproves the first inequality in \([9](https://arxiv.org/html/2608.07922#S4.E9)\)\.

Misrouted\-verification charge\.Ifρj,1−vj≥1/4\\rho\_\{j,1\-v\_\{j\}\}\\geq 1/4, then

∑k=1qNj,1−vj,k​\(T\)≥q​n4\.\\sum\_\{k=1\}^\{q\}N\_\{j,1\-v\_\{j\},k\}\(T\)\\geq\\frac\{qn\}\{4\}\.The unselected probes are pairwise disjoint, and every pull in them has gap at leasts/4s/4\. Hence, pathwise,

RegT​\(fv\)≥s​q​n16​∑j=1m𝟏\{ρj,1−vj≥1/4\}\.\\mathrm\{Reg\}\_\{T\}\(f\_\{v\}\)\\geq\\frac\{sqn\}\{16\}\\sum\_\{j=1\}^\{m\}\\mathbf\{1\}\_\{\\\{\\rho\_\{j,1\-v\_\{j\}\}\\geq 1/4\\\}\}\.Taking expectations and averaging overvvgives

𝔼¯​∑j=1m𝟏\{ρj,1−Vj≥1/4\}≤16​ℛs​q​n≤m8,\\overline\{\\mathbb\{E\}\}\\sum\_\{j=1\}^\{m\}\\mathbf\{1\}\_\{\\\{\\rho\_\{j,1\-V\_\{j\}\}\\geq 1/4\\\}\}\\leq\\frac\{16\\mathcal\{R\}\}\{sqn\}\\leq\\frac\{m\}\{8\},becausem​s​q​n≍ds​r−d−2msqn\\asymp\_\{d\}sr^\{\-d\-2\}\. This proves the second inequality in \([9](https://arxiv.org/html/2608.07922#S4.E9)\)\.

Constant\-distortion routing recovery\.Forp∈\[0,1\]p\\in\[0,1\], let

h2​\(p\):=−p​log2⁡p−\(1−p\)​log2⁡\(1−p\),h\_\{2\}\(p\):=\-p\\log\_\{2\}p\-\(1\-p\)\\log\_\{2\}\(1\-p\),with0​log2⁡0:=00\\log\_\{2\}0:=0\. PutHj,a:=𝟏\{ρj,a≥1/4\}H\_\{j,a\}:=\\mathbf\{1\}\_\{\\\{\\rho\_\{j,a\}\\geq 1/4\\\}\}\. Since the decoder coin is independent after the transcript,

ℙ¯​\(V^j≠Vj\)=12​ℙ¯​\(Hj,Vj=0\)\+12​ℙ¯​\(Hj,1−Vj=1\)\.\\overline\{\\mathbb\{P\}\}\(\\widehat\{V\}\_\{j\}\\neq V\_\{j\}\)=\\frac\{1\}\{2\}\\overline\{\\mathbb\{P\}\}\(H\_\{j,V\_\{j\}\}=0\)\+\\frac\{1\}\{2\}\\overline\{\\mathbb\{P\}\}\(H\_\{j,1\-V\_\{j\}\}=1\)\.Consequently,

1m​∑j=1mℙ¯​\(V^j≠Vj\)≤14\+116=516\.\\frac\{1\}\{m\}\\sum\_\{j=1\}^\{m\}\\overline\{\\mathbb\{P\}\}\(\\widehat\{V\}\_\{j\}\\neq V\_\{j\}\)\\leq\\frac\{1\}\{4\}\+\\frac\{1\}\{16\}=\\frac\{5\}\{16\}\.BecauseVVis uniform and independent ofℱ0\\mathcal\{F\}\_\{0\}, the entropy step can be carried out conditionally on the public seed\. For each coordinate, let

ej:=ℙ¯​\(V^j≠Vj∣ℱ0\)\.e\_\{j\}:=\\overline\{\\mathbb\{P\}\}\(\\widehat\{V\}\_\{j\}\\neq V\_\{j\}\\mid\\mathcal\{F\}\_\{0\}\)\.Binary Fano’s inequality conditional onℱ0\\mathcal\{F\}\_\{0\}, followed by Jensen’s inequality, gives

H​\(Vj∣V^j,ℱ0\)≤𝔼¯​h2​\(ej\)≤h2​\(ℙ¯​\(V^j≠Vj\)\)\.H\(V\_\{j\}\\mid\\widehat\{V\}\_\{j\},\\mathcal\{F\}\_\{0\}\)\\leq\\overline\{\\mathbb\{E\}\}h\_\{2\}\(e\_\{j\}\)\\leq h\_\{2\}\\\!\\left\(\\overline\{\\mathbb\{P\}\}\(\\widehat\{V\}\_\{j\}\\neq V\_\{j\}\)\\right\)\.Subadditivity of conditional entropy and concavity ofh2h\_\{2\}across coordinates therefore imply

H​\(V∣V^,ℱ0\)\\displaystyle H\(V\\mid\\widehat\{V\},\\mathcal\{F\}\_\{0\}\)≤∑j=1mH​\(Vj∣V^j,ℱ0\)\\displaystyle\\leq\\sum\_\{j=1\}^\{m\}H\(V\_\{j\}\\mid\\widehat\{V\}\_\{j\},\\mathcal\{F\}\_\{0\}\)≤∑j=1mh2​\(ℙ¯​\(V^j≠Vj\)\)\\displaystyle\\leq\\sum\_\{j=1\}^\{m\}h\_\{2\}\\\!\\left\(\\overline\{\\mathbb\{P\}\}\(\\widehat\{V\}\_\{j\}\\neq V\_\{j\}\)\\right\)≤m​h2​\(1m​∑j=1mℙ¯​\(V^j≠Vj\)\)\\displaystyle\\leq mh\_\{2\}\\\!\\left\(\\frac\{1\}\{m\}\\sum\_\{j=1\}^\{m\}\\overline\{\\mathbb\{P\}\}\(\\widehat\{V\}\_\{j\}\\neq V\_\{j\}\)\\right\)≤m​h2​\(5/16\)\.\\displaystyle\\leq mh\_\{2\}\(5/16\)\.Thus

I​\(V;V^∣ℱ0\)≥\[1−h2​\(5/16\)\]​m≥cd​s−d\.I\(V;\\widehat\{V\}\\mid\\mathcal\{F\}\_\{0\}\)\\geq\[1\-h\_\{2\}\(5/16\)\]m\\geq c\_\{d\}s^\{\-d\}\.\(41\)The decoder coins are independent of the experiment, so randomized data processing and Lemma[3\.3](https://arxiv.org/html/2608.07922#S3.Thmtheorem3)yield

I​\(V;V^∣ℱ0\)≤I​\(V;𝖳∣ℱ0\)≤χ\.I\(V;\\widehat\{V\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq I\(V;\\mathsf\{T\}\\mid\\mathcal\{F\}\_\{0\}\)\\leq\\chi\.Comparing this bound with \([41](https://arxiv.org/html/2608.07922#A2.E41)\) contradicts \([10](https://arxiv.org/html/2608.07922#S4.E10)\) after fixing its constant sufficiently small\. Hence \([40](https://arxiv.org/html/2608.07922#A2.E40)\) is impossible and the lemma follows\. ∎

### B\.5Effective\-resolution optimization

RecallΨT\\Psi\_\{T\},sstats\_\{\\mathrm\{stat\}\},smems\_\{\\mathrm\{mem\}\}, andsT,χs\_\{T,\\chi\}from \([2](https://arxiv.org/html/2608.07922#S3.E2)\)\. The evidence obstruction in Lemma[4\.1](https://arxiv.org/html/2608.07922#S4.Thmtheorem1), specialized as in Corollary[4\.2](https://arxiv.org/html/2608.07922#S4.Thmtheorem2), gives

ℜT​\(B,W\)≥cd​Tαd=cd​ΨT​\(sstat\)\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}T^\{\\alpha\_\{d\}\}=c\_\{d\}\\Psi\_\{T\}\(s\_\{\\mathrm\{stat\}\}\)\(42\)for everyχ\\chi\.

It remains to obtain the memory floor when it is larger\. Ifχ≤Cd\\chi\\leq C\_\{d\}, Proposition[4\.4](https://arxiv.org/html/2608.07922#S4.Thmtheorem4)gives linear regret, which dominatesΨT​\(sT,χ\)\\Psi\_\{T\}\(s\_\{T,\\chi\}\)\. Suppose next that

Cd<χ<cd​Td/\(d\+2\)\.C\_\{d\}<\\chi<c\_\{d\}T^\{d/\(d\+2\)\}\.Choose dyadic radii

s≍d\(1\+χ\)−1/d,r≍d\(s/T\)1/\(d\+3\),s\\asymp\_\{d\}\(1\+\\chi\)^\{\-1/d\},\\qquad r\\asymp\_\{d\}\(s/T\)^\{1/\(d\+3\)\},with the constant insschosen so that \([10](https://arxiv.org/html/2608.07922#S4.E10)\) holds\. The upper endpoint of this range ensuresr≤s/16r\\leq s/16andT​r2≥CdTr^\{2\}\\geq C\_\{d\}\. Lemma[4\.3](https://arxiv.org/html/2608.07922#S4.Thmtheorem3)then yields

ℜT​\(B,W\)≥cd​min⁡\{T​r,s​r−d−2\}≍dΨT​\(s\)≍dTd\+2d\+3​\(1\+χ\)−1d​\(d\+3\)\.\\mathfrak\{R\}\_\{T\}\(B,W\)\\geq c\_\{d\}\\min\\\{Tr,sr^\{\-d\-2\}\\\}\\asymp\_\{d\}\\Psi\_\{T\}\(s\)\\asymp\_\{d\}T^\{\\frac\{d\+2\}\{d\+3\}\}\(1\+\\chi\)^\{\-\\frac\{1\}\{d\(d\+3\)\}\}\.This quantity dominatesTαdT^\{\\alpha\_\{d\}\}throughout the intermediate range\. Ifχ≥cd​Td/\(d\+2\)\\chi\\geq c\_\{d\}T^\{d/\(d\+2\)\}, thensmem≲dsstats\_\{\\mathrm\{mem\}\}\\lesssim\_\{d\}s\_\{\\mathrm\{stat\}\}and \([42](https://arxiv.org/html/2608.07922#A2.E42)\) already gives the effective envelope\. Combining the ranges proves \([11](https://arxiv.org/html/2608.07922#S4.E11)\)\. In particular, any guaranteeℜT​\(B,W\)≤Λ​Tαd\\mathfrak\{R\}\_\{T\}\(B,W\)\\leq\\Lambda T^\{\\alpha\_\{d\}\}implies

1\+χ≥cd​Tdd\+2​Λ−d​\(d\+3\)\.1\+\\chi\\geq c\_\{d\}T^\{\\frac\{d\}\{d\+2\}\}\\Lambda^\{\-d\(d\+3\)\}\.

### B\.6Batch\-depth compatibility

Let𝔊B\\mathfrak\{G\}\_\{B\}denote the predictable adaptive\-grid policy class in the adaptive\-grid lower bound ofFenget al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib15)\); we retain their term “adaptive grid” for the sequence of batch boundaries\. Every pull in a source interval is measurable at its preceding boundary, and the source theorem uses exactlyBBnonempty intervals\.

###### Lemma B\.6\(Exact\-BBsubdivision\)\.

Every committed\-batch policy withB^≤B\\widehat\{B\}\\leq Bnonempty batches induces a policy in𝔊B\\mathfrak\{G\}\_\{B\}with exactlyBBnonempty intervals and the same action sequence and regret\.

###### Proof\.

Simulate the original policy and retain the endpointτ\\tauof its currently committed batch\. Suppose thebbth source interval starts attb−1<τt\_\{b\-1\}<\\tau\. Set

tb:=min⁡\{τ,T−\(B−b\)\},b=1,…,B\.t\_\{b\}:=\\min\\\{\\tau,\\,T\-\(B\-b\)\\\},\\qquad b=1,\\ldots,B\.\(43\)Inductively,T−tb−1≥B−b\+1T\-t\_\{b\-1\}\\geq B\-b\+1\. Both arguments of the minimum in \([43](https://arxiv.org/html/2608.07922#A2.E43)\) are therefore strictly larger thantb−1t\_\{b\-1\}, so the new interval is nonempty, andtbt\_\{b\}is predictable becauseτ\\tauwas fixed when the current original batch was committed\.

Iftb<τt\_\{b\}<\\tau, declare a dummy boundary: process the newly revealed rewards through the simulated state in chronological order, but recommit the unplayed suffix of the same read\-only tape\. Iftb=τt\_\{b\}=\\tau, process the completed batch, invoke the simulated policy’s boundary map, and commit its next tape\. Thus no source interval crosses an original boundary and every original boundary is retained\.

LetDbD\_\{b\}be the number of dummy boundaries amongt1,…,tbt\_\{1\},\\ldots,t\_\{b\}\. We claimDb≤B−B^D\_\{b\}\\leq B\-\\widehat\{B\}pathwise\. Once equality holds before intervalbb, the number of remaining source intervals equals the number of remaining original batches\. Since every original batch is nonempty, its current endpoint obeysτ≤T−\(B−b\)\\tau\\leq T\-\(B\-b\), so \([43](https://arxiv.org/html/2608.07922#A2.E43)\) choosestb=τt\_\{b\}=\\tauand no further dummy boundary is possible\. Atb=Bb=B, there areBBsource endpoints, at mostB−B^B\-\\widehat\{B\}of which are dummy and at mostB^\\widehat\{B\}of which are original\. Hence equality holds in both counts, every original endpoint has been used, andtB=Tt\_\{B\}=T\.

Dummy boundaries never change the already committed actions\. Chronological processing ensures that the simulated state at each original boundary is exactly the state of the original policy\. The action sequence and regret are therefore unchanged\. ∎

###### Lemma B\.7\(Bernoulli transfer of the adaptive\-grid batch lower bound\)\.

Fixd≥1d\\geq 1\. There exist constantscd,Td\>0c\_\{d\},T\_\{d\}\>0such that, for everyT≥TdT\\geq T\_\{d\}and2≤B≤T2\\leq B\\leq T,

ℜTbat​\(B\)≥cd​Tβd,BB2\.\\mathfrak\{R\}\_\{T\}^\{\\mathrm\{bat\}\}\(B\)\\geq c\_\{d\}\\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\.Consequently, the same lower bound holds forℜT​\(B,W\)\\mathfrak\{R\}\_\{T\}\(B,W\)for every integerW≥0W\\geq 0\.

###### Proof\.

Fix𝒜∈𝔄B,∞\\mathcal\{A\}\\in\\mathfrak\{A\}\_\{B,\\infty\}\. We construct a policy𝒜♯∈𝔊B\\mathcal\{A\}^\{\\sharp\}\\in\\mathfrak\{G\}\_\{B\}for the Gaussian experiment ofFenget al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib15)\), using Lemma[B\.6](https://arxiv.org/html/2608.07922#A2.Thmtheorem6)\. When a completed grid interval reveals Gaussian observationsYtGY\_\{t\}^\{\\mathrm\{G\}\}, the policy processes them in chronological order, forms

Y~t=𝟏\{YtG≥0\},\\widetilde\{Y\}\_\{t\}=\\mathbf\{1\}\_\{\\\{Y\_\{t\}^\{\\mathrm\{G\}\}\\geq 0\\\}\},and applies the state updates of𝒜\\mathcal\{A\}to the binary observationsY~t\\widetilde\{Y\}\_\{t\}\. At an original boundary it uses the resulting state to invoke𝒜\\mathcal\{A\}’s boundary map; at a dummy boundary it recommits the unplayed suffix of the same tape\. This is a valid predictable adaptive\-grid policy because every action in the completed interval was fixed at its preceding boundary\. No memory restriction is used in this simulation\.

Let𝔉d,T,B\\mathfrak\{F\}\_\{d,T,B\}be the explicit full\-dimensional hard family in the proof of that adaptive\-grid lower bound\. Its mean functions are one\-Lipschitz, and the displayed base levels and peak heights place every value in a fixed compact intervalId⊂ℝI\_\{d\}\\subset\\mathbb\{R\}, uniformly overTTandBB\. LetΦ\\Phiandφ\\varphidenote the standard normal distribution function and density, and writeμ⋆:=supx∈\[0,1\]dμ​\(x\)\\mu^\{\\star\}:=\\sup\_\{x\\in\[0,1\]^\{d\}\}\\mu\(x\)\. Define

fμ​\(x\):=Φ​\(μ​\(x\)\),cΦ,d:=minz∈Id⁡φ​\(z\)\>0\.f\_\{\\mu\}\(x\):=\\Phi\(\\mu\(x\)\),\\qquad c\_\{\\Phi,d\}:=\\min\_\{z\\in I\_\{d\}\}\\varphi\(z\)\>0\.SinceΦ\\Phiis increasing and‖φ‖∞<1\\\|\\varphi\\\|\_\{\\infty\}<1,

fμ∈Lip1​\(\[0,1\]d\),fμ⋆−fμ​\(x\)≥cΦ,d​\(μ⋆−μ​\(x\)\)\.f\_\{\\mu\}\\in\\mathrm\{Lip\}\_\{1\}\(\[0,1\]^\{d\}\),\\qquad f\_\{\\mu\}^\{\\star\}\-f\_\{\\mu\}\(x\)\\geq c\_\{\\Phi,d\}\\bigl\(\\mu^\{\\star\}\-\\mu\(x\)\\bigr\)\.\(44\)Moreover, conditional onAt=xA\_\{t\}=x,

Y~t∼Ber⁡\(Φ​\(μ​\(x\)\)\)=Ber⁡\(fμ​\(x\)\)\.\\widetilde\{Y\}\_\{t\}\\sim\\operatorname\{Ber\}\(\\Phi\(\\mu\(x\)\)\)=\\operatorname\{Ber\}\(f\_\{\\mu\}\(x\)\)\.An induction over source intervals therefore shows that the simulated state of𝒜\\mathcal\{A\}after every processed pull, its embedded original boundaries, and the action sequence under\(𝒜♯,μ\)\(\\mathcal\{A\}^\{\\sharp\},\\mu\)have the same joint law as under𝒜\\mathcal\{A\}on the admissible Bernoulli instancefμf\_\{\\mu\}\. The full grids are not identical:𝒜♯\\mathcal\{A\}^\{\\sharp\}may contain the dummy subdivision boundaries from Lemma[B\.6](https://arxiv.org/html/2608.07922#A2.Thmtheorem6), which do not change actions or regret\.

Applying the adaptive\-grid lower bound ofFenget al\.\([2024](https://arxiv.org/html/2608.07922#bib.bib15)\)in full dimensionddgives someμ∈𝔉d,T,B\\mu\\in\\mathfrak\{F\}\_\{d,T,B\}with regret exponent

1−a1−aB=\(d\+1\)/\(d\+2\)1−\(d\+2\)−B=βd,B,a:=1d\+2,\\frac\{1\-a\}\{1\-a^\{B\}\}=\\frac\{\(d\+1\)/\(d\+2\)\}\{1\-\(d\+2\)^\{\-B\}\}=\\beta\_\{d,B\},\\qquad a:=\\frac\{1\}\{d\+2\},and hence

𝔼μ𝒜♯​∑t=1T\(μ⋆−μ​\(At\)\)≥cd​Tβd,BB2\.\\mathbb\{E\}\_\{\\mu\}^\{\\mathcal\{A\}^\{\\sharp\}\}\\sum\_\{t=1\}^\{T\}\\bigl\(\\mu^\{\\star\}\-\\mu\(A\_\{t\}\)\\bigr\)\\geq c\_\{d\}\\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\.Combining the equality of action laws with \([44](https://arxiv.org/html/2608.07922#A2.E44)\) yields

𝔼fμ𝒜​RegT​\(fμ\)\\displaystyle\\mathbb\{E\}\_\{f\_\{\\mu\}\}^\{\\mathcal\{A\}\}\\mathrm\{Reg\}\_\{T\}\(f\_\{\\mu\}\)=𝔼μ𝒜♯​∑t=1T\(fμ⋆−fμ​\(At\)\)\\displaystyle=\\mathbb\{E\}\_\{\\mu\}^\{\\mathcal\{A\}^\{\\sharp\}\}\\sum\_\{t=1\}^\{T\}\\bigl\(f\_\{\\mu\}^\{\\star\}\-f\_\{\\mu\}\(A\_\{t\}\)\\bigr\)≥cΦ,d​𝔼μ𝒜♯​∑t=1T\(μ⋆−μ​\(At\)\)\\displaystyle\\geq c\_\{\\Phi,d\}\\mathbb\{E\}\_\{\\mu\}^\{\\mathcal\{A\}^\{\\sharp\}\}\\sum\_\{t=1\}^\{T\}\\bigl\(\\mu^\{\\star\}\-\\mu\(A\_\{t\}\)\\bigr\)≥cd​Tβd,BB2\.\\displaystyle\\geq c\_\{d\}\\frac\{T^\{\\beta\_\{d,B\}\}\}\{B^\{2\}\}\.Taking the supremum over admissible Bernoulli instances and the infimum over𝒜∈𝔄B,∞\\mathcal\{A\}\\in\\mathfrak\{A\}\_\{B,\\infty\}proves the unrestricted\-memory claim\. Since𝔄B,W⊆𝔄B,∞\\mathfrak\{A\}\_\{B,W\}\\subseteq\\mathfrak\{A\}\_\{B,\\infty\}, the finite\-memory claim follows as well\. ∎

## Appendix CDyadic geometry and streaming refinement

This appendix gives the fixed dyadic geometry, the one\-pass refinement interface, and the two\-batch root case\. All batch lengths and slot layouts are reward\-independent, and rewards are processed once in slot order\.

### C\.1Fixed dyadic geometry and finite precision

Forz\>0z\>0, define the integer bit length

bl⁡\(z\):=2\+⌈log2⁡\(1∨z\)⌉\.\\operatorname\{bl\}\(z\):=2\+\\lceil\\log\_\{2\}\(1\\vee z\)\\rceil\.Forz∈\(0,1\]z\\in\(0,1\], let⌈z⌉2\\lceil z\\rceil\_\{2\}denote the smallest dyadic number no smaller thanzz\. Then

bl⁡\(z\)≍log⁡\(e​z\)\(z≥1\),z≤⌈z⌉2<2​z\.\\operatorname\{bl\}\(z\)\\asymp\\log\(ez\)\\quad\(z\\geq 1\),\\qquad z\\leq\\lceil z\\rceil\_\{2\}<2z\.\(45\)All geometric objects, traversal orders, and numerical schedules below are measurable functions of the problem parameters and the algorithmic seed\. They are therefore fixed conditional onℱ0\\mathcal\{F\}\_\{0\}and can be regenerated without a stored table; arithmetic running time is outside the resource model\.

###### Lemma C\.1\(Fixed dyadic geometry\)\.

Fixd≥1d\\geq 1\. For every0<r≤s≤10<r\\leq s\\leq 1, there are nested fixed partitions of\[0,1\]d\[0,1\]^\{d\}, a scale\-ssparent cover𝒫s\\mathcal\{P\}\_\{s\}, and anrr\-net𝒩r​\(P\)\\mathcal\{N\}\_\{r\}\(P\)for everyP∈𝒫sP\\in\\mathcal\{P\}\_\{s\}such that

\|𝒫s\|≤Cd​s−d,\|𝒩r​\(P\)\|≤Cd​\(s/r\)d\.\|\\mathcal\{P\}\_\{s\}\|\\leq C\_\{d\}s^\{\-d\},\\qquad\|\\mathcal\{N\}\_\{r\}\(P\)\|\\leq C\_\{d\}\(s/r\)^\{d\}\.For every pair of levels0≤j′≤j0\\leq j^\{\\prime\}\\leq j, each level\-jjcell has a unique level\-j′j^\{\\prime\}ancestor\. Every representative and traversal position has anOd​\(log⁡\(1/r\)\)O\_\{d\}\(\\log\(1/r\)\)\-bit address, and all objects are generated uniformly from\(d,r,s\)\(d,r,s\)without a stored geometric table\.

###### Proof\.

Forj≥0j\\geq 0and0≤k<2j0\\leq k<2^\{j\}, letIj,kI\_\{j,k\}be the half\-open dyadic interval\[k​2−j,\(k\+1\)​2−j\)\[k2^\{\-j\},\(k\+1\)2^\{\-j\}\), with the right endpoint included whenk=2j−1k=2^\{j\}\-1\. The products

Pj,k1,…,kd=∏a=1dIj,kaP\_\{j,k\_\{1\},\\ldots,k\_\{d\}\}=\\prod\_\{a=1\}^\{d\}I\_\{j,k\_\{a\}\}form a partition of\[0,1\]d\[0,1\]^\{d\}; use their coordinatewise midpoints as representatives\. For0≤j′≤j0\\leq j^\{\\prime\}\\leq j, the unique level\-j′j^\{\\prime\}ancestor has address

\(j′,⌊k12j−j′⌋,…,⌊kd2j−j′⌋\)\.\\left\(j^\{\\prime\},\\left\\lfloor\\frac\{k\_\{1\}\}\{2^\{j\-j^\{\\prime\}\}\}\\right\\rfloor,\\ldots,\\left\\lfloor\\frac\{k\_\{d\}\}\{2^\{j\-j^\{\\prime\}\}\}\\right\\rfloor\\right\)\.\(46\)Setjs=⌈log2⁡\(1/s\)⌉j\_\{s\}=\\lceil\\log\_\{2\}\(1/s\)\\rceilandjr=⌈log2⁡\(1/r\)⌉j\_\{r\}=\\lceil\\log\_\{2\}\(1/r\)\\rceil\. The level\-jsj\_\{s\}cells have diameter at mostssand

\|𝒫s\|=2d​js≤\(2/s\)d\.\|\\mathcal\{P\}\_\{s\}\|=2^\{dj\_\{s\}\}\\leq\(2/s\)^\{d\}\.ForP∈𝒫sP\\in\\mathcal\{P\}\_\{s\}, let𝒩r​\(P\)\\mathcal\{N\}\_\{r\}\(P\)be the midpoints of its level\-jrj\_\{r\}descendants\. They form anrr\-net and

\|𝒩r​\(P\)\|=2d​\(jr−js\)≤\(2​s/r\)d\.\|\\mathcal\{N\}\_\{r\}\(P\)\|=2^\{d\(j\_\{r\}\-j\_\{s\}\)\}\\leq\(2s/r\)^\{d\}\.A cell address contains one level andddintegers of at mostjrj\_\{r\}bits; lexicographic traversal, midpoint generation, and ancestor computation require no stored geometric table\. This proves the lemma\. ∎

For0<ε≤10<\\varepsilon\\leq 1, writeQε​\(y\)=⌊y/ε⌋Q\_\{\\varepsilon\}\(y\)=\\lfloor y/\\varepsilon\\rfloor\.

###### Lemma C\.2\(Streaming mean primitive\)\.

Fix a prescribed segment lengthn≥1n\\geq 1and precision0<ε≤10<\\varepsilon\\leq 1\. A one\-pass deterministic update using

⌈log2⁡\(n​⌊1/ε⌋\+1\)⌉\\left\\lceil\\log\_\{2\}\\\!\\left\(n\\lfloor 1/\\varepsilon\\rfloor\+1\\right\)\\right\\rceilbits returns a rounded empirical meanμ^\\widehat\{\\mu\}satisfying

\|μ^−1n​∑i=1nYi\|<ε\.\\left\|\\widehat\{\\mu\}\-\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}Y\_\{i\}\\right\|<\\varepsilon\.\(47\)

###### Proof\.

Maintain

St=∑i=1t⌊Yi/ε⌋,0≤St≤n​⌊1/ε⌋\.S\_\{t\}=\\sum\_\{i=1\}^\{t\}\\left\\lfloor Y\_\{i\}/\\varepsilon\\right\\rfloor,\\qquad 0\\leq S\_\{t\}\\leq n\\lfloor 1/\\varepsilon\\rfloor\.The displayed register size therefore suffices\. Withμ^=ε​Sn/n\\widehat\{\\mu\}=\\varepsilon S\_\{n\}/n,

0≤1n​∑i=1nYi−μ^=1n​∑i=1n\(Yi−ε​⌊Yi/ε⌋\)<ε\.0\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}Y\_\{i\}\-\\widehat\{\\mu\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\left\(Y\_\{i\}\-\\varepsilon\\left\\lfloor Y\_\{i\}/\\varepsilon\\right\\rfloor\\right\)<\\varepsilon\.∎

Use the public fallback actionx∘x\_\{\\circ\}from Section[3\.1](https://arxiv.org/html/2608.07922#S3.SS1)and deterministic lexicographic tie\-breaking\.

### C\.2Streaming refinement from a safe active set

Recallℓr=log⁡\(e/r\)\\ell\_\{r\}=\\log\(e/r\)and the prescribed segment lengthnr=⌈Adref​r−2​ℓr⌉n\_\{r\}=\\lceil A\_\{d\}^\{\\mathrm\{ref\}\}r^\{\-2\}\\ell\_\{r\}\\rceilfrom Section[5\.1](https://arxiv.org/html/2608.07922#S5.SS1)\. During terminal refinement, the parent mask and best\-child record remain resident while one child mean is accumulated\. Since

bl⁡\(nr\)\+bl⁡\(r−d−1\)≤Cd​ℓr,\\operatorname\{bl\}\(n\_\{r\}\)\+\\operatorname\{bl\}\(r^\{\-d\-1\}\)\\leq C\_\{d\}\\ell\_\{r\},Lemma[C\.2](https://arxiv.org/html/2608.07922#A3.Thmtheorem2)usesOd​\(ℓr\)O\_\{d\}\(\\ell\_\{r\}\)auxiliary bits, after which the segment statistic is erased\.

Enumerate𝒫s=\{Pk:k∈\[K\]\}\\mathcal\{P\}\_\{s\}=\\\{P\_\{k\}:k\\in\[K\]\\\}and fix pairwise disjoint scheduled index fragmentsℐ1,…,ℐJ0⊆\[K\]\\mathcal\{I\}\_\{1\},\\ldots,\\mathcal\{I\}\_\{J\_\{0\}\}\\subseteq\[K\]\. Lettjt\_\{j\}be the boundary immediately before refinement fragmentjjis committed, and set

ℋj:=σ​\(ω,\(At,Yt\)1≤t≤tj\)\.\\mathcal\{H\}\_\{j\}:=\\sigma\\\!\\left\(\\omega,\(A\_\{t\},Y\_\{t\}\)\_\{1\\leq t\\leq t\_\{j\}\}\\right\)\.A maskZ\(j\)∈\{0,1\}ℐjZ^\{\(j\)\}\\in\\\{0,1\\\}^\{\\mathcal\{I\}\_\{j\}\}, an incumbent armx¯j\\bar\{x\}\_\{j\}, and an event𝒢j\\mathcal\{G\}\_\{j\}areℋj\\mathcal\{H\}\_\{j\}\-measurable\. Set

𝒞j:=\{Pk:k∈ℐj,Zk\(j\)=1\},𝒞:=⨆j=1J0𝒞j,𝒢:=⋂j=1J0𝒢j\.\\mathcal\{C\}\_\{j\}:=\\\{P\_\{k\}:k\\in\\mathcal\{I\}\_\{j\},\\ Z\_\{k\}^\{\(j\)\}=1\\\},\\qquad\\mathcal\{C\}:=\\bigsqcup\_\{j=1\}^\{J\_\{0\}\}\\mathcal\{C\}\_\{j\},\\qquad\\mathcal\{G\}:=\\bigcap\_\{j=1\}^\{J\_\{0\}\}\\mathcal\{G\}\_\{j\}\.Assume that, on𝒢j\\mathcal\{G\}\_\{j\}, every retained parent in𝒞j\\mathcal\{C\}\_\{j\}and the incumbentx¯j\\bar\{x\}\_\{j\}have gap at mostκd​s\\kappa\_\{d\}s, and that, on𝒢\\mathcal\{G\}, some cell in𝒞\\mathcal\{C\}contains a maximizer\.

###### Lemma C\.3\(Conditional streaming refinement\)\.

There existsCd\>0C\_\{d\}\>0such that, ifCd​r−d−2​ℓr≤T/2C\_\{d\}r^\{\-d\-2\}\\ell\_\{r\}\\leq T/2, then one refinement batch per scheduled fragment returns an armx^\\widehat\{x\}satisfying

\#​\{refinement pulls\}\\displaystyle\\\#\\\{\\text\{refinement pulls\}\\\}≤Cd​r−d−2​ℓr,\\displaystyle\\leq C\_\{d\}r^\{\-d\-2\}\\ell\_\{r\},\(48\)ℙ​\(𝒢∩\{Δf​\(x^\)\>Cd​r\}\)\\displaystyle\\mathbb\{P\}\\\!\\left\(\\mathcal\{G\}\\cap\\\{\\Delta\_\{f\}\(\\widehat\{x\}\)\>C\_\{d\}r\\\}\\right\)≤r\.\\displaystyle\\leq r\.\(49\)Refinement followed by exploitation has expected regret at most

Cd​\[s​r−d−2​ℓr\+T​r\]\+T​ℙ​\(𝒢∁\),C\_\{d\}\\left\[sr^\{\-d\-2\}\\ell\_\{r\}\+Tr\\right\]\+T\\mathbb\{P\}\(\\mathcal\{G\}^\{\\complement\}\),\(50\)and uses at mostCd​ℓrC\_\{d\}\\ell\_\{r\}memory bits beyond the resident parent mask after every reward\.

###### Proof of Lemma[C\.3](https://arxiv.org/html/2608.07922#A3.Thmtheorem3)\.

Concatenate the fixed parent–child layouts over the scheduled fragments and index the resulting slot stream byi=1,…,Ni=1,\\ldots,N\. Disjointness and Lemma[C\.1](https://arxiv.org/html/2608.07922#A3.Thmtheorem1)give

N=∑j=1J0∑k∈ℐj\|𝒩r​\(Pk\)\|≤Cd​\(s/r\)d​∑j=1J0\|ℐj\|≤Cd​\(s/r\)d​K≤Cd​r−d\.N=\\sum\_\{j=1\}^\{J\_\{0\}\}\\sum\_\{k\\in\\mathcal\{I\}\_\{j\}\}\|\\mathcal\{N\}\_\{r\}\(P\_\{k\}\)\|\\leq C\_\{d\}\(s/r\)^\{d\}\\sum\_\{j=1\}^\{J\_\{0\}\}\|\\mathcal\{I\}\_\{j\}\|\\leq C\_\{d\}\(s/r\)^\{d\}K\\leq C\_\{d\}r^\{\-d\}\.A slotiihas an associated triple\(j,k,u\)\(j,k,u\)withk∈ℐjk\\in\\mathcal\{I\}\_\{j\}andu∈𝒩r​\(Pk\)u\\in\\mathcal\{N\}\_\{r\}\(P\_\{k\}\)\. SetRi=Zk\(j\)R\_\{i\}=Z\_\{k\}^\{\(j\)\}\. IfRi=1R\_\{i\}=1, the scheduled action isui=uu\_\{i\}=u; ifRi=0R\_\{i\}=0, it is the fragment incumbentx¯j\\bar\{x\}\_\{j\}\. The slot count and batch boundary are fixed, while the resident mask determines only whether each slot is real or filler\. Use the prescribed segment lengthnrn\_\{r\}and the mesh

ε=r/512,\\varepsilon=r/512,\(51\)and define the rounded score

μ^i=εnr​∑t=1nrQε​\(Yi,t\)\.\\widehat\{\\mu\}\_\{i\}=\\frac\{\\varepsilon\}\{n\_\{r\}\}\\sum\_\{t=1\}^\{n\_\{r\}\}Q\_\{\\varepsilon\}\(Y\_\{i,t\}\)\.All child scores use the same predetermined quantization mesh\.

Initialize\(x^0,η^0\)=\(x∘,−1\)\(\\widehat\{x\}\_\{0\},\\widehat\{\\eta\}\_\{0\}\)=\(x\_\{\\circ\},\-1\)and update

\(x^i,η^i\)=\{\(ui,μ^i\),Ri=1​and​μ^i\>η^i−1,\(x^i−1,η^i−1\),otherwise\.\(\\widehat\{x\}\_\{i\},\\widehat\{\\eta\}\_\{i\}\)=\\begin\{cases\}\(u\_\{i\},\\widehat\{\\mu\}\_\{i\}\),&R\_\{i\}=1\\text\{ and \}\\widehat\{\\mu\}\_\{i\}\>\\widehat\{\\eta\}\_\{i\-1\},\\\\ \(\\widehat\{x\}\_\{i\-1\},\\widehat\{\\eta\}\_\{i\-1\}\),&\\text\{otherwise\}\.\\end\{cases\}\(52\)Thusη^i\\widehat\{\\eta\}\_\{i\}is the largest score among real slots1,…,i1,\\ldots,i, with lexicographic tie\-breaking; filler scores never affect the output, and the record passes unchanged between fragments\.

For each scheduled slotiiin fragmentjj, the indicatorRiR\_\{i\}, the child armuiu\_\{i\}, and𝒢j\\mathcal\{G\}\_\{j\}areℋj\\mathcal\{H\}\_\{j\}\-measurable\. On\{Ri=1\}\\\{R\_\{i\}=1\\\}the segment pullsuiu\_\{i\}\. Conditional Hoeffding and \([47](https://arxiv.org/html/2608.07922#A3.E47)\) therefore give, after choosingAdrefA\_\{d\}^\{\\mathrm\{ref\}\}sufficiently large,

ℙ​\(𝒢j∩\{Ri=1\}∩\{\|μ^i−f​\(ui\)\|\>r/32\}\)\\displaystyle\\mathbb\{P\}\\\!\\left\(\\mathcal\{G\}\_\{j\}\\cap\\\{R\_\{i\}=1\\\}\\cap\\\{\|\\widehat\{\\mu\}\_\{i\}\-f\(u\_\{i\}\)\|\>r/32\\\}\\right\)=𝔼​\[𝟏𝒢j​𝟏\{Ri=1\}​ℙ​\(\|μ^i−f​\(ui\)\|\>r/32∣ℋj\)\]≤rN\.\\displaystyle\\quad=\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{j\}\}\\mathbf\{1\}\_\{\\\{R\_\{i\}=1\\\}\}\\mathbb\{P\}\\\!\\left\(\|\\widehat\{\\mu\}\_\{i\}\-f\(u\_\{i\}\)\|\>r/32\\mid\\mathcal\{H\}\_\{j\}\\right\)\\right\]\\leq\\frac\{r\}\{N\}\.\(53\)A union bound over theNNscheduled slots yields an eventℰ\\mathcal\{E\}such that

ℙ​\(𝒢∩ℰ∁\)≤r,\|μ^i−f​\(ui\)\|≤r/32for every real slot on​𝒢∩ℰ\.\\mathbb\{P\}\(\\mathcal\{G\}\\cap\\mathcal\{E\}^\{\\complement\}\)\\leq r,\\qquad\|\\widehat\{\\mu\}\_\{i\}\-f\(u\_\{i\}\)\|\\leq r/32\\quad\\text\{for every real slot on \}\\mathcal\{G\}\\cap\\mathcal\{E\}\.\(54\)The pull count is deterministic and satisfies

N​nr≤Cd​r−d−2​ℓr,Nn\_\{r\}\\leq C\_\{d\}r^\{\-d\-2\}\\ell\_\{r\},\(55\)which proves \([48](https://arxiv.org/html/2608.07922#A3.E48)\)\. On𝒢\\mathcal\{G\}, every real child and every incumbent action has gap at mostCd​sC\_\{d\}s, so the refinement charge is pathwise at mostCd​s​r−d−2​ℓrC\_\{d\}sr^\{\-d\-2\}\\ell\_\{r\}\. Moreover, on𝒢\\mathcal\{G\}there is a retained parentP⋆P^\{\\star\}containing a maximizerx⋆x^\{\\star\}\. Lemma[C\.1](https://arxiv.org/html/2608.07922#A3.Thmtheorem1)supplies a real childu⋆∈𝒩r​\(P⋆\)u^\{\\star\}\\in\\mathcal\{N\}\_\{r\}\(P^\{\\star\}\)with

f⋆−f​\(u⋆\)≤r\.f^\{\\star\}\-f\(u^\{\\star\}\)\\leq r\.\(56\)Leti⋆i^\{\\star\}be the real slot associated withu⋆u^\{\\star\}\. On𝒢∩ℰ\\mathcal\{G\}\\cap\\mathcal\{E\}, the running\-maximum invariant givesη^N≥μ^i⋆\\widehat\{\\eta\}\_\{N\}\\geq\\widehat\{\\mu\}\_\{i^\{\\star\}\}andx^N\\widehat\{x\}\_\{N\}is a real child\. Therefore

f⋆−f​\(x^N\)\\displaystyle f^\{\\star\}\-f\(\\widehat\{x\}\_\{N\}\)=f⋆−f​\(u⋆\)\+f​\(u⋆\)−μ^i⋆\\displaystyle=f^\{\\star\}\-f\(u^\{\\star\}\)\+f\(u^\{\\star\}\)\-\\widehat\{\\mu\}\_\{i^\{\\star\}\}\+μ^i⋆−η^N\+η^N−f​\(x^N\)\\displaystyle\\quad\+\\widehat\{\\mu\}\_\{i^\{\\star\}\}\-\\widehat\{\\eta\}\_\{N\}\+\\widehat\{\\eta\}\_\{N\}\-f\(\\widehat\{x\}\_\{N\}\)≤r\+r32\+0\+r32=1716​r\.\\displaystyle\\leq r\+\\frac\{r\}\{32\}\+0\+\\frac\{r\}\{32\}=\\frac\{17\}\{16\}r\.\(57\)This proves \([49](https://arxiv.org/html/2608.07922#A3.E49)\)\. If the remaining rounds exploitx^N\\widehat\{x\}\_\{N\}, the total refinement\-and\-exploitation regret is at most

Cd​\[s​r−d−2​ℓr\+T​r\]\+T​ℙ​\(𝒢∁\),C\_\{d\}\\left\[sr^\{\-d\-2\}\\ell\_\{r\}\+Tr\\right\]\+T\\mathbb\{P\}\(\\mathcal\{G\}^\{\\complement\}\),\(58\)becauseℙ​\(𝒢∩ℰ∁\)≤r\\mathbb\{P\}\(\\mathcal\{G\}\\cap\\mathcal\{E\}^\{\\complement\}\)\\leq rand the complete horizon contributes at mostTTon𝒢∁\\mathcal\{G\}^\{\\complement\}\. This proves \([50](https://arxiv.org/html/2608.07922#A3.E50)\)\.

After every pull, the auxiliary memory consists of the slot address, a counter, the integer sum, and the global point–score pair\. The address usesOd​\(log⁡\(1/r\)\)O\_\{d\}\(\\log\(1/r\)\)bits, while \([47](https://arxiv.org/html/2608.07922#A3.E47)\) and \([51](https://arxiv.org/html/2608.07922#A3.E51)\) give

log2⁡nr\+log2⁡\(1/ε\)≤Cd​ℓr\.\\log\_\{2\}n\_\{r\}\+\\log\_\{2\}\(1/\\varepsilon\)\\leq C\_\{d\}\\ell\_\{r\}\.\(59\)The accumulator is erased after comparison\. Each fragment is one batch because its action sequence and real/filler indicators are determined at its boundary; the resident mask is erased afterward\. ∎

###### Proof of Lemma[5\.2](https://arxiv.org/html/2608.07922#S5.Thmtheorem2)\.

Apply Lemma[C\.3](https://arxiv.org/html/2608.07922#A3.Thmtheorem3)with𝒢j\\mathcal\{G\}\_\{j\}equal to the whole sample space for every fragment\. Its pull, memory, and regret bounds are exactly those stated in Lemma[5\.2](https://arxiv.org/html/2608.07922#S5.Thmtheorem2)\. ∎

###### Corollary C\.4\(Two\-batch root case\)\.

There exist constantsCd,cd,Td\>0C\_\{d\},c\_\{d\},T\_\{d\}\>0such that, forT≥TdT\\geq T\_\{d\}and every integerW≥0W\\geq 0,

ℜT​\(2,W\)≤Cd​T​min⁡\{1,max⁡\{\(log⁡\(4​T\)T\)1/\(d\+3\),2−cd​W\}\}\.\\mathfrak\{R\}\_\{T\}\(2,W\)\\leq C\_\{d\}T\\min\\left\\\{1,\\max\\left\\\{\\left\(\\frac\{\\log\(4T\)\}\{T\}\\right\)^\{1/\(d\+3\)\},2^\{\-c\_\{d\}W\}\\right\\\}\\right\\\}\.\(60\)

###### Proof\.

The root cube is a safe scale\-11active set\. For largeAdrootA\_\{d\}^\{\\mathrm\{root\}\}and smallξd\>0\\xi\_\{d\}\>0, put

r~=max⁡\{\(Adroot​log⁡\(4​T\)/T\)1/\(d\+3\),2−ξd​W\}\.\\widetilde\{r\}=\\max\\left\\\{\(A\_\{d\}^\{\\mathrm\{root\}\}\\log\(4T\)/T\)^\{1/\(d\+3\)\},2^\{\-\\xi\_\{d\}W\}\\right\\\}\.\(61\)Letrrbe the smallest dyadic radius at leastr~\\widetilde\{r\}\. If it exceeds a fixed small cutoff, a fixed arm gives the claim\. Otherwiser<2​r~r<2\\widetilde\{r\},ℓr≤Cd​log⁡\(4​T\)\\ell\_\{r\}\\leq C\_\{d\}\\log\(4T\), and the choice ofAdrootA\_\{d\}^\{\\mathrm\{root\}\}gives

Cd​r−d−2​ℓr≤CdAdroot​T​r≤T/2\.C\_\{d\}r^\{\-d\-2\}\\ell\_\{r\}\\leq\\frac\{C\_\{d\}\}\{A\_\{d\}^\{\\mathrm\{root\}\}\}Tr\\leq T/2\.\(62\)Alsor≥2−ξd​Wr\\geq 2^\{\-\\xi\_\{d\}W\}givesCd​ℓr≤WC\_\{d\}\\ell\_\{r\}\\leq Wafter choosingξd\\xi\_\{d\}and the cutoff sufficiently small\. Thus Lemma[5\.2](https://arxiv.org/html/2608.07922#S5.Thmtheorem2)applies to the one\-fragment root stream and uses one refinement batch followed by one exploitation batch\. Its regret is at most

Cd​\[r−d−2​ℓr\+T​r\]≤Cd​T​r\.C\_\{d\}\\left\[r^\{\-d\-2\}\\ell\_\{r\}\+Tr\\right\]\\leq C\_\{d\}Tr\.\(63\)Substitutingr<2​r~r<2\\widetilde\{r\}proves \([60](https://arxiv.org/html/2608.07922#A3.E60)\)\. ∎

## Appendix DSerialized active\-set construction

This appendix proves the serialized active\-set guarantee\. A pass\-frozen tournament finds a safe incumbent; the final pass emits, refines, and erases one active\-set fragment at a time\. RecallℓT\\ell\_\{T\},LserL\_\{\\mathrm\{ser\}\},HserH\_\{\\mathrm\{ser\}\}, andΓT\\Gamma\_\{T\}from \([1](https://arxiv.org/html/2608.07922#S3.E1)\), \([14](https://arxiv.org/html/2608.07922#S5.E14)\), and \([16](https://arxiv.org/html/2608.07922#S5.E16)\)\. The balanced schedule sharpens only logarithmic factors: the simpler choice

nℓ=⌈N1−2−ℓ⌉,Lpf≍log⁡log⁡N,n\_\{\\ell\}=\\left\\lceil N^\{1\-2^\{\-\\ell\}\}\\right\\rceil,\\qquad L\_\{\\mathrm\{pf\}\}\\asymp\\log\\log N,already gives the same frontier exponents up to powers oflog⁡log⁡N\\log\\log N\.

### D\.1Pass\-frozen confidence\-bound tournament

At passii, the routine forms and freezes a fresh incumbent estimate, scans every fragment through levels1,…,i1,\\ldots,i, and compares candidate UCBs with the frozen incumbent LCB\. A nonfinal pass selects the representative with the largest final\-level LCB after all fragments; the final pass adds slackζ\\zetaand emits masks for immediate refinement\. The incumbent segment is prepended to the first level\-one batch\.

Fix prescribed actionsx1,…,xKx\_\{1\},\\ldots,x\_\{K\}, integers1≤S≤K1\\leq S\\leq KandN≥16N\\geq 16, a slackζ≥0\\zeta\\geq 0, and0<δ≤1/20<\\delta\\leq 1/2\. Partition\[K\]\[K\]into fixed fragmentsℐ1,…,ℐJ\\mathcal\{I\}\_\{1\},\\ldots,\\mathcal\{I\}\_\{J\}of size at mostSS, where

J:=⌈KS⌉,fK⋆:=maxk≤K⁡f​\(xk\),𝒦⋆:=arg​maxk≤K⁡f​\(xk\)\.J:=\\left\\lceil\\frac\{K\}\{S\}\\right\\rceil,\\qquad f\_\{K\}^\{\\star\}:=\\max\_\{k\\leq K\}f\(x\_\{k\}\),\\qquad\\mathcal\{K\}^\{\\star\}:=\\operatorname\*\{arg\\,max\}\_\{k\\leq K\}f\(x\_\{k\}\)\.Letc⋄≥64c\_\{\\diamond\}\\geq 64be fixed and define

Lpf\\displaystyle L\_\{\\mathrm\{pf\}\}:=⌈log2⁡log2⁡\(4​N\)⌉∨1,\\displaystyle:=\\left\\lceil\\log\_\{2\}\\log\_\{2\}\(4N\)\\right\\rceil\\vee 1,n0\\displaystyle n\_\{0\}:=1,cℓ:=2ℓ−Lpf\+1,nℓ:=⌈cℓ​N​nℓ−1⌉,1≤ℓ≤Lpf,\\displaystyle:=1,\\qquad c\_\{\\ell\}:=2^\{\\ell\-L\_\{\\mathrm\{pf\}\}\+1\},\\qquad n\_\{\\ell\}:=\\left\\lceil c\_\{\\ell\}\\sqrt\{Nn\_\{\\ell\-1\}\}\\right\\rceil,\\quad 1\\leq\\ell\\leq L\_\{\\mathrm\{pf\}\},ε\\displaystyle\\varepsilon:=2−10−⌈12​log2⁡N⌉,aℓ:=2​log⁡\(c⋄​K​Lpf2/δ\)nℓ\+2​ε\.\\displaystyle:=2^\{\-10\-\\lceil\\frac\{1\}\{2\}\\log\_\{2\}N\\rceil\},\\qquad a\_\{\\ell\}:=\\sqrt\{\\frac\{2\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{pf\}\}^\{2\}/\\delta\)\}\{n\_\{\\ell\}\}\}\+2\\varepsilon\.The tournament is the pass\-frozen procedure described above with these parameters\. During the final pass, letZ\(j\)∈\{0,1\}ℐjZ^\{\(j\)\}\\in\\\{0,1\\\}^\{\\mathcal\{I\}\_\{j\}\}denote the mask emitted for fragmentℐj\\mathcal\{I\}\_\{j\}\.

###### Lemma D\.1\(Pass\-frozen confidence\-bound tournament\)\.

Fixd≥1d\\geq 1\. There exist constantsCd,Nd\>0C\_\{d\},N\_\{d\}\>0such that, ifNd≤N≤TN\_\{d\}\\leq N\\leq TandCd​K​N≤TC\_\{d\}KN\\leq T, then the tournament uses

J​Lpf​\(Lpf\+1\)2J\\frac\{L\_\{\\mathrm\{pf\}\}\(L\_\{\\mathrm\{pf\}\}\+1\)\}\{2\}\(64\)batches, at most

pulls, and at most

S\+Cd​\(log2⁡K\+log2⁡T\)S\+C\_\{d\}\(\\log\_\{2\}K\+\\log\_\{2\}T\)\(66\)memory bits after every pull\. With probability at least1−δ1\-\\delta, the incumbent entering the final pass, denotedkfink\_\{\\mathrm\{fin\}\}, satisfies

fK⋆−f​\(xkfin\)≤Cd​log⁡\(c⋄​K​Lpf2/δ\)N,f\_\{K\}^\{\\star\}\-f\(x\_\{k\_\{\\mathrm\{fin\}\}\}\)\\leq C\_\{d\}\\sqrt\{\\frac\{\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{pf\}\}^\{2\}/\\delta\)\}\{N\}\},\(67\)and the regret relative tofK⋆f\_\{K\}^\{\\star\}is at most

Cd​K​\[N​log⁡\(c⋄​K​Lpf2/δ\)\+ζ​N\]\.C\_\{d\}K\\left\[\\sqrt\{N\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{pf\}\}^\{2\}/\\delta\)\}\+\\zeta N\\right\]\.\(68\)For everyj∈\[J\]j\\in\[J\], the mask emitted for fragmentℐj\\mathcal\{I\}\_\{j\}during the final pass satisfies

k∈ℐj,fK⋆−f​\(xk\)≤ζ\\displaystyle k\\in\\mathcal\{I\}\_\{j\},\\quad f\_\{K\}^\{\\star\}\-f\(x\_\{k\}\)\\leq\\zeta⟹Zk\(j\)=1,\\displaystyle\\ \\Longrightarrow\\ Z\_\{k\}^\{\(j\)\}=1,\(69\)k∈ℐj,Zk\(j\)=1\\displaystyle k\\in\\mathcal\{I\}\_\{j\},\\quad Z\_\{k\}^\{\(j\)\}=1⟹fK⋆−f​\(xk\)≤ζ\+Cd​aLpf−1\.\\displaystyle\\ \\Longrightarrow\\ f\_\{K\}^\{\\star\}\-f\(x\_\{k\}\)\\leq\\zeta\+C\_\{d\}a\_\{L\_\{\\mathrm\{pf\}\}\-1\}\.

###### Proof\.

Balanced interpolation schedule\.ChooseNdN\_\{d\}so thatLpf≥2L\_\{\\mathrm\{pf\}\}\\geq 2,log2⁡N≥2​Lpf\\log\_\{2\}N\\geq 2L\_\{\\mathrm\{pf\}\}, andLpf2≤NL\_\{\\mathrm\{pf\}\}^\{2\}\\leq\\sqrt\{N\}\. Forv0=1v\_\{0\}=1andvℓ=cℓ​N​vℓ−1v\_\{\\ell\}=c\_\{\\ell\}\\sqrt\{Nv\_\{\\ell\-1\}\}, direct iteration gives

vℓ=N1−2−ℓ​2−2​\(Lpf−ℓ\)\+Lpf​21−ℓ,log2⁡vℓvℓ−1=2\+2−ℓ​\(log2⁡N−2​Lpf\)≥2\.v\_\{\\ell\}=N^\{1\-2^\{\-\\ell\}\}2^\{\-2\(L\_\{\\mathrm\{pf\}\}\-\\ell\)\+L\_\{\\mathrm\{pf\}\}2^\{1\-\\ell\}\},\\qquad\\log\_\{2\}\\frac\{v\_\{\\ell\}\}\{v\_\{\\ell\-1\}\}=2\+2^\{\-\\ell\}\(\\log\_\{2\}N\-2L\_\{\\mathrm\{pf\}\}\)\\geq 2\.Thusvℓ≤nℓ≤2​vℓv\_\{\\ell\}\\leq n\_\{\\ell\}\\leq 2v\_\{\\ell\}andnℓ≥2​nℓ−1n\_\{\\ell\}\\geq 2n\_\{\\ell\-1\}, while the definition ofLpfL\_\{\\mathrm\{pf\}\}implies

N2≤nLpf≤2​N,nLpf−1≥N16,nℓ≤2​N​4−\(Lpf−ℓ\)\.\\frac\{N\}\{2\}\\leq n\_\{L\_\{\\mathrm\{pf\}\}\}\\leq 2N,\\qquad n\_\{L\_\{\\mathrm\{pf\}\}\-1\}\\geq\\frac\{N\}\{16\},\\qquad n\_\{\\ell\}\\leq 2N4^\{\-\(L\_\{\\mathrm\{pf\}\}\-\\ell\)\}\.\(70\)Consequently,

∑i=1Lpf∑ℓ=1inℓ\\displaystyle\\sum\_\{i=1\}^\{L\_\{\\mathrm\{pf\}\}\}\\sum\_\{\\ell=1\}^\{i\}n\_\{\\ell\}=∑ℓ=1Lpf\(Lpf−ℓ\+1\)​nℓ≤C​N,\\displaystyle=\\sum\_\{\\ell=1\}^\{L\_\{\\mathrm\{pf\}\}\}\(L\_\{\\mathrm\{pf\}\}\-\\ell\+1\)n\_\{\\ell\}\\leq CN,\(71\)Lpf​n1\+∑i=1Lpf∑ℓ=2inℓnℓ−1\\displaystyle L\_\{\\mathrm\{pf\}\}n\_\{1\}\+\\sum\_\{i=1\}^\{L\_\{\\mathrm\{pf\}\}\}\\sum\_\{\\ell=2\}^\{i\}\\frac\{n\_\{\\ell\}\}\{\\sqrt\{n\_\{\\ell\-1\}\}\}≤C​N\.\\displaystyle\\leq C\\sqrt\{N\}\.\(72\)Herenℓ/nℓ−1≤cℓ​N\+1n\_\{\\ell\}/\\sqrt\{n\_\{\\ell\-1\}\}\\leq c\_\{\\ell\}\\sqrt\{N\}\+1,∑ℓ=2Lpf\(Lpf−ℓ\+1\)​cℓ≤8\\sum\_\{\\ell=2\}^\{L\_\{\\mathrm\{pf\}\}\}\(L\_\{\\mathrm\{pf\}\}\-\\ell\+1\)c\_\{\\ell\}\\leq 8, andLpf2≤NL\_\{\\mathrm\{pf\}\}^\{2\}\\leq\\sqrt\{N\}\.

Committed passes and memory\.Initializek0=1k\_\{0\}=1\. At the start of passii, letk¯:=ki−1\\bar\{k\}:=k\_\{i\-1\}be the frozen incumbent entering that pass\. Prependnin\_\{i\}fresh pulls ofxk¯x\_\{\\bar\{k\}\}to the first level\-one batch\. Letμ¯i\\bar\{\\mu\}\_\{i\}be the rounded mean of this segment and set

λi:=μ¯i−ai\.\\lambda\_\{i\}:=\\bar\{\\mu\}\_\{i\}\-a\_\{i\}\.At the start of each fragment setZk,0=1Z\_\{k,0\}=1\. Letμ^k,ℓ\\widehat\{\\mu\}\_\{k,\\ell\}be the rounded empirical mean of coordinatekk’s level\-ℓ\\ellsegment and define

LCBk,ℓ:=μ^k,ℓ−aℓ,UCBk,ℓ:=μ^k,ℓ\+aℓ\.\\operatorname\{LCB\}\_\{k,\\ell\}:=\\widehat\{\\mu\}\_\{k,\\ell\}\-a\_\{\\ell\},\\qquad\\operatorname\{UCB\}\_\{k,\\ell\}:=\\widehat\{\\mu\}\_\{k,\\ell\}\+a\_\{\\ell\}\.At levelℓ≤i\\ell\\leq i, coordinatekkuses

Xk,ℓ=\{xk,Zk,ℓ−1=1,xk¯,Zk,ℓ−1=0,X\_\{k,\\ell\}=\\begin\{cases\}x\_\{k\},&Z\_\{k,\\ell\-1\}=1,\\\\ x\_\{\\bar\{k\}\},&Z\_\{k,\\ell\-1\}=0,\\end\{cases\}and updates

Zk,ℓ=Zk,ℓ−1​𝟏\{UCBk,ℓ≥λi−ζi\},ζi:=ζ​𝟏\{i=Lpf\}\.Z\_\{k,\\ell\}=Z\_\{k,\\ell\-1\}\\mathbf\{1\}\_\{\\\{\\operatorname\{UCB\}\_\{k,\\ell\}\\geq\\lambda\_\{i\}\-\\zeta\_\{i\}\\\}\},\\qquad\\zeta\_\{i\}:=\\zeta\\mathbf\{1\}\_\{\\\{i=L\_\{\\mathrm\{pf\}\}\\\}\}\.\(73\)A nonfinal pass sets the next incumbent to the surviving representative with largest final\-level LCB; if none survives, it retains the current incumbent\. The final pass has no incumbent update\.

Passiihas exactlyJ​iJitournament batches, proving \([64](https://arxiv.org/html/2608.07922#A4.E64)\)\. Sinceni≥2​ni−1n\_\{i\}\\geq 2n\_\{i\-1\},

∑i=1Lpfni≤2​nLpf≤4​N\.\\sum\_\{i=1\}^\{L\_\{\\mathrm\{pf\}\}\}n\_\{i\}\\leq 2n\_\{L\_\{\\mathrm\{pf\}\}\}\\leq 4N\.The fragment pulls are bounded by a constant timesK​∑i∑ℓ≤inℓK\\sum\_\{i\}\\sum\_\{\\ell\\leq i\}n\_\{\\ell\}, so \([71](https://arxiv.org/html/2608.07922#A4.E71)\) proves \([65](https://arxiv.org/html/2608.07922#A4.E65)\)\. At any time the routine stores oneSS\-bit mask, the frozen incumbent address–benchmark pair, either one pass\-champion record or no champion, and one segment accumulator\. Addresses, counters, and quantized scores haveO​\(log⁡K\+log⁡T\)O\(\\log K\+\\log T\)bits by Lemmas[C\.1](https://arxiv.org/html/2608.07922#A3.Thmtheorem1)and[C\.2](https://arxiv.org/html/2608.07922#A3.Thmtheorem2)\. This proves \([66](https://arxiv.org/html/2608.07922#A4.E66)\)\.

Good event and incumbent invariant\.Let𝒢\\mathcal\{G\}be the event that every rounded score from a real candidate segment at levelℓ\\ellis withinaℓa\_\{\\ell\}off​\(xk\)f\(x\_\{k\}\)and every fresh incumbent score in passiiis withinaia\_\{i\}off​\(xk¯\)f\(x\_\{\\bar\{k\}\}\)\. Conditional Hoeffding, deterministic rounding, and a union bound give

ℙ​\(𝒢∁\)≤δ\.\\mathbb\{P\}\(\\mathcal\{G\}^\{\\complement\}\)\\leq\\delta\.Fix𝒢\\mathcal\{G\}\. For every pass,

f​\(xk¯\)−2​ai≤λi≤f​\(xk¯\),f\(x\_\{\\bar\{k\}\}\)\-2a\_\{i\}\\leq\\lambda\_\{i\}\\leq f\(x\_\{\\bar\{k\}\}\),\(74\)and every real candidate segment satisfies

f​\(xk\)−2​aℓ≤LCBk,ℓ≤f​\(xk\)≤UCBk,ℓ≤f​\(xk\)\+2​aℓ\.f\(x\_\{k\}\)\-2a\_\{\\ell\}\\leq\\operatorname\{LCB\}\_\{k,\\ell\}\\leq f\(x\_\{k\}\)\\leq\\operatorname\{UCB\}\_\{k,\\ell\}\\leq f\(x\_\{k\}\)\+2a\_\{\\ell\}\.\(75\)
Letkik\_\{i\}be the incumbent index after nonfinal passii\. We prove

fK⋆−f​\(xki\)≤2​ai,1≤i<Lpf\.f\_\{K\}^\{\\star\}\-f\(x\_\{k\_\{i\}\}\)\\leq 2a\_\{i\},\\qquad 1\\leq i<L\_\{\\mathrm\{pf\}\}\.\(76\)Fixk⋆∈𝒦⋆k^\{\\star\}\\in\\mathcal\{K\}^\{\\star\}\. Sinceλi≤f​\(xk¯\)≤fK⋆\\lambda\_\{i\}\\leq f\(x\_\{\\bar\{k\}\}\)\\leq f\_\{K\}^\{\\star\}andUCBk⋆,ℓ≥fK⋆\\operatorname\{UCB\}\_\{k^\{\\star\},\\ell\}\\geq f\_\{K\}^\{\\star\}, coordinatek⋆k^\{\\star\}survives every level\. Consequently the pass championkik\_\{i\}satisfies

LCBki,i≥LCBk⋆,i≥fK⋆−2​ai\.\\operatorname\{LCB\}\_\{k\_\{i\},i\}\\geq\\operatorname\{LCB\}\_\{k^\{\\star\},i\}\\geq f\_\{K\}^\{\\star\}\-2a\_\{i\}\.Equation \([75](https://arxiv.org/html/2608.07922#A4.E75)\) yields \([76](https://arxiv.org/html/2608.07922#A4.E76)\)\. The same benchmark bracket holds in the final pass\. Setkfin:=kLpf−1k\_\{\\mathrm\{fin\}\}:=k\_\{L\_\{\\mathrm\{pf\}\}\-1\}\. Finally, \([70](https://arxiv.org/html/2608.07922#A4.E70)\) implies \([67](https://arxiv.org/html/2608.07922#A4.E67)\)\.

Final masks\.The incumbent entering the final pass obeys

fK⋆−f​\(xk¯\)≤2​aLpf−1\.f\_\{K\}^\{\\star\}\-f\(x\_\{\\bar\{k\}\}\)\\leq 2a\_\{L\_\{\\mathrm\{pf\}\}\-1\}\.Ifk∈ℐjk\\in\\mathcal\{I\}\_\{j\}satisfiesfK⋆−f​\(xk\)≤ζf\_\{K\}^\{\\star\}\-f\(x\_\{k\}\)\\leq\\zeta, then

UCBk,ℓ≥f​\(xk\)≥fK⋆−ζ≥λLpf−ζ,\\operatorname\{UCB\}\_\{k,\\ell\}\\geq f\(x\_\{k\}\)\\geq f\_\{K\}^\{\\star\}\-\\zeta\\geq\\lambda\_\{L\_\{\\mathrm\{pf\}\}\}\-\\zeta,so \([73](https://arxiv.org/html/2608.07922#A4.E73)\) retains it at every level\. Conversely, ifkksurvives the final level, then \([74](https://arxiv.org/html/2608.07922#A4.E74)\)–\([75](https://arxiv.org/html/2608.07922#A4.E75)\) give

fK⋆−f​\(xk\)≤2​aLpf−1\+ζ\+4​aLpf≤ζ\+6​aLpf−1\.f\_\{K\}^\{\\star\}\-f\(x\_\{k\}\)\\leq 2a\_\{L\_\{\\mathrm\{pf\}\}\-1\}\+\\zeta\+4a\_\{L\_\{\\mathrm\{pf\}\}\}\\leq\\zeta\+6a\_\{L\_\{\\mathrm\{pf\}\}\-1\}\.This proves \([69](https://arxiv.org/html/2608.07922#A4.E69)\) after changingCdC\_\{d\}\.

Regret\.Letℛ\\mathcal\{R\}denote the tournament regret relative tofK⋆f\_\{K\}^\{\\star\}\. Level\-one candidate pulls over all passes contribute at mostK​Lpf​n1KL\_\{\\mathrm\{pf\}\}n\_\{1\}\. Fori≥2i\\geq 2and2≤ℓ≤i2\\leq\\ell\\leq i, an active candidate survived levelℓ−1\\ell\-1\. Equations \([74](https://arxiv.org/html/2608.07922#A4.E74)\)–\([75](https://arxiv.org/html/2608.07922#A4.E75)\) and \([76](https://arxiv.org/html/2608.07922#A4.E76)\) give

fK⋆−f​\(xk\)≤Cd​\(aℓ−1\+ζi\)\.f\_\{K\}^\{\\star\}\-f\(x\_\{k\}\)\\leq C\_\{d\}\(a\_\{\\ell\-1\}\+\\zeta\_\{i\}\)\.Every incumbent filler in passiihas gap at most2​ai−12a\_\{i\-1\}fori≥2i\\geq 2, and the same is true of the fresh incumbent segment\. The first\-pass incumbent segment is absorbed by the level\-one term\. Sinceai−1≤C​aℓ−1a\_\{i\-1\}\\leq Ca\_\{\\ell\-1\}whenever2≤ℓ≤i2\\leq\\ell\\leq iandK≥1K\\geq 1, these incumbent charges are bounded by the same interpolation sums as the active\-candidate charges\. Therefore

ℛ\\displaystyle\\mathcal\{R\}≤Cd​K​\[Lpf​n1\+∑i=2Lpf∑ℓ=2inℓ​aℓ−1\+ζ​∑ℓ=1Lpfnℓ\]\+Cd​ε​K​N\\displaystyle\\leq C\_\{d\}K\\left\[L\_\{\\mathrm\{pf\}\}n\_\{1\}\+\\sum\_\{i=2\}^\{L\_\{\\mathrm\{pf\}\}\}\\sum\_\{\\ell=2\}^\{i\}n\_\{\\ell\}a\_\{\\ell\-1\}\+\\zeta\\sum\_\{\\ell=1\}^\{L\_\{\\mathrm\{pf\}\}\}n\_\{\\ell\}\\right\]\+C\_\{d\}\\varepsilon KN≤Cd​K​\[N​log⁡\(c⋄​K​Lpf2/δ\)\+ζ​N\]\.\\displaystyle\\leq C\_\{d\}K\\left\[\\sqrt\{N\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{pf\}\}^\{2\}/\\delta\)\}\+\\zeta N\\right\]\.The last step uses \([71](https://arxiv.org/html/2608.07922#A4.E71)\)– \([72](https://arxiv.org/html/2608.07922#A4.E72)\)\. This proves \([68](https://arxiv.org/html/2608.07922#A4.E68)\) and completes the lemma\. ∎

#### Common\-reference confidence rule\.

Partition the scale\-sscells into fixed index fragmentsℐ1,…,ℐJs\\mathcal\{I\}\_\{1\},\\ldots,\\mathcal\{I\}\_\{J\_\{s\}\}of size at mostSS, and letxkx\_\{k\}be the representative of cellPkP\_\{k\}\. Instantiate Lemma[D\.1](https://arxiv.org/html/2608.07922#A4.Thmtheorem1)with terminal targetN=nsN=n\_\{s\}, failure levelδ=r\\delta=r, and final\-pass slackζ=s\\zeta=s\. Its depth isLpf=LserL\_\{\\mathrm\{pf\}\}=L\_\{\\mathrm\{ser\}\}\. Let\(nℓ,aℓ\)ℓ=1Lser\(n\_\{\\ell\},a\_\{\\ell\}\)\_\{\\ell=1\}^\{L\_\{\\mathrm\{ser\}\}\}be the resulting predetermined schedule; it satisfiesns/2≤nLser≤2​nsn\_\{s\}/2\\leq n\_\{L\_\{\\mathrm\{ser\}\}\}\\leq 2n\_\{s\}\. At the beginning of passii, the learner takesnin\_\{i\}fresh pulls of the frozen incumbent\. Ifμ¯i\\bar\{\\mu\}\_\{i\}is the resulting rounded mean, define the incumbent benchmark

λi:=μ¯i−ai\.\\lambda\_\{i\}:=\\bar\{\\mu\}\_\{i\}\-a\_\{i\}\.On the common concentration event, both this fresh incumbent estimate and a level\-iicandidate estimate have confidence radiusaia\_\{i\}\. For a rounded candidate meanμ^k,ℓ\\widehat\{\\mu\}\_\{k,\\ell\}, define its lower and upper confidence bounds \(LCB and UCB\) by

LCBk,ℓ:=μ^k,ℓ−aℓ,UCBk,ℓ:=μ^k,ℓ\+aℓ\.\\operatorname\{LCB\}\_\{k,\\ell\}:=\\widehat\{\\mu\}\_\{k,\\ell\}\-a\_\{\\ell\},\\qquad\\operatorname\{UCB\}\_\{k,\\ell\}:=\\widehat\{\\mu\}\_\{k,\\ell\}\+a\_\{\\ell\}\.The same confidence\-bound update is used in every pass\. Setζi:=s​𝟏\{i=Lser\}\\zeta\_\{i\}:=s\\mathbf\{1\}\_\{\\\{i=L\_\{\\mathrm\{ser\}\}\\\}\}and, after a level\-ℓ\\ellbatch in passii, update all active bits by

Zk←Zk​𝟏\{UCBk,ℓ≥λi−ζi\}\.Z\_\{k\}\\leftarrow Z\_\{k\}\\mathbf\{1\}\_\{\\\{\\operatorname\{UCB\}\_\{k,\\ell\}\\geq\\lambda\_\{i\}\-\\zeta\_\{i\}\\\}\}\.\(77\)Thus nonfinal passes use no slack, whereas the final pass uses exactly the scale\-ssgeometric slack\. At the end of a nonfinal pass, the surviving final\-level representative with the largest LCB becomes the next incumbent\. This max\-LCB update closes the incumbent invariant directly\. For eachPkP\_\{k\}, let𝒩r​\(Pk\)\\mathcal\{N\}\_\{r\}\(P\_\{k\}\)be its fixed radius\-rrnet\. During refinement, every arm in𝒩r​\(Pk\)\\mathcal\{N\}\_\{r\}\(P\_\{k\}\)is pulled fornrn\_\{r\}rounds whenPkP\_\{k\}survives, while an eliminated cell uses the incumbent in the corresponding slots\.

#### Active\-set subroutines\.

For readability, Algorithm[1](https://arxiv.org/html/2608.07922#alg1)packages the repeated batch operations into three routines\. The candidate\-bearing routines update the unique resident record in place\.*Selection\.*EliminateSelect​\(ℐ,i,k¯,λ;kc,λc\)\\textsc\{EliminateSelect\}\(\\mathcal\{I\},i,\\bar\{k\},\\lambda;k\_\{c\},\\lambda\_\{c\}\)uses exactlyiibatches\. It initializes every index inℐ\\mathcal\{I\}as active; at levelℓ\\ell, active slots pull their representatives fornℓn\_\{\\ell\}rounds and inactive slots pull the frozen incumbent, after which the mask is updated by \([77](https://arxiv.org/html/2608.07922#A4.E77)\)\. Ifλ=⊥\\lambda=\\bot, the first batch also containsnin\_\{i\}fresh incumbent pulls and returns the resulting benchmark\. As final\-level LCBs are produced, the routine compares them directly with the resident pass champion\(kc,λc\)\(k\_\{c\},\\lambda\_\{c\}\)and updates that pair in place\. It returns the final mask, benchmark, and updated resident champion; no fragment\-local address–score record is stored\.*Mask construction\.*EliminateMask​\(ℐ,Lser,k¯,λ,s\)\\textsc\{EliminateMask\}\(\\mathcal\{I\},L\_\{\\mathrm\{ser\}\},\\bar\{k\},\\lambda,s\)performs the same elimination without a champion update and returns only the final mask and benchmark\.*Refinement\.*RefineFragment​\(ℐ,Z,k¯;xbest,f^best\)\\textsc\{RefineFragment\}\(\\mathcal\{I\},Z,\\bar\{k\};x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\)uses one batch: retained cells pull their radius\-rrchild nets, eliminated cells use incumbent fillers, and every real child score is compared directly with the resident global best\-child record\(xbest,f^best\)\(x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\)\. The routine returns the updated resident record and stores no fragment\-local best child\.

#### State variables\.

The algorithm keeps one active\-set maskZZ; a frozen incumbent indexk¯\\bar\{k\}and its LCB benchmarkλ\\lambda; a pass champion\(kc,λc\)\(k\_\{c\},\\lambda\_\{c\}\)during nonfinal passes; and a global refined\-arm record\(xbest,f^best\)\(x\_\{\\mathrm\{best\}\},\\widehat\{f\}\_\{\\mathrm\{best\}\}\)during the final pass\. The symbols⊥\\botand∅\\varnothingdenote an uninitialized benchmark and address, respectively\.

#### Batch structure and invariants\.

The balanced schedule satisfies∑i=1Lserni≤2​nLser≤4​ns\\sum\_\{i=1\}^\{L\_\{\\mathrm\{ser\}\}\}n\_\{i\}\\leq 2n\_\{L\_\{\\mathrm\{ser\}\}\}\\leq 4n\_\{s\}\. Each fresh incumbent estimate is embedded in the first elimination batch of its pass and therefore requires no additional batch\. The three phases of Algorithm[1](https://arxiv.org/html/2608.07922#alg1)use respectivelyJs​Lser​\(Lser−1\)/2J\_\{s\}L\_\{\\mathrm\{ser\}\}\(L\_\{\\mathrm\{ser\}\}\-1\)/2,Js​\(Lser\+1\)J\_\{s\}\(L\_\{\\mathrm\{ser\}\}\+1\), and one batch, for a total ofJs​Hser\+1J\_\{s\}H\_\{\\mathrm\{ser\}\}\+1\. Their analysis maintains three invariants: after nonfinal passii, the incumbent is2​ai2a\_\{i\}\-optimal among the parent representatives; the final masks retain a parent containing a maximizer and onlyOd​\(s\)O\_\{d\}\(s\)\-optimal parents; and after every pull the mutable memory consists of one resident mask, one incumbent address–benchmark pair, one streaming accumulator, and either the pass champion or the global best child\.

Algorithm[1](https://arxiv.org/html/2608.07922#alg1)in the main text uses these routines and state variables\. The remainder of this appendix verifies its exact batch, memory, pull, and regret bounds\.

### D\.2Detailed realization and fixed\-scale guarantee

Algorithm[1](https://arxiv.org/html/2608.07922#alg1)interleaves the final tournament pass with child refinement, using one freshnLsern\_\{L\_\{\\mathrm\{ser\}\}\}\-sample incumbent estimate for all fragments\. Lemma[D\.1](https://arxiv.org/html/2608.07922#A4.Thmtheorem1)remains valid under this interleaving: the inserted refinement batches do not modify the frozen incumbent, its benchmark, or any tournament mask, and the lemma’s concentration and regret arguments use only the chronological order of the tournament segments\. UnderCd​r−d−2​ℓT≤T/2C\_\{d\}r^\{\-d\-2\}\\ell\_\{T\}\\leq T/2andr≤sr\\leq s, one haslog⁡K\+log⁡\(1/r\)≤Cd​ℓT\\log K\+\\log\(1/r\)\\leq C\_\{d\}\\ell\_\{T\}\. ChoosingCdctlC\_\{d\}^\{\\mathrm\{ctl\}\}larger than the constants in Lemmas[D\.1](https://arxiv.org/html/2608.07922#A4.Thmtheorem1)and[C\.2](https://arxiv.org/html/2608.07922#A3.Thmtheorem2)therefore bounds every address, score, counter, and accumulator bywctl=⌈Cdctl​ℓT⌉w\_\{\\mathrm\{ctl\}\}=\\lceil C\_\{d\}^\{\\mathrm\{ctl\}\}\\ell\_\{T\}\\rceilbits in total\. Together with the resident mask, the phase\-specific memory is at mostS\+wctlS\+w\_\{\\mathrm\{ctl\}\}bits\.

###### Proof of Proposition[5\.3](https://arxiv.org/html/2608.07922#S5.Thmtheorem3)\.

Use the parameters in \([14](https://arxiv.org/html/2608.07922#S5.E14)\), setN:=nsN:=n\_\{s\}, and chooseAdserA\_\{d\}^\{\\mathrm\{ser\}\}large enough thatN≥NdN\\geq N\_\{d\}\. Apply Lemma[D\.1](https://arxiv.org/html/2608.07922#A4.Thmtheorem1)with terminal targetNN, slack

ζ=s,δ=r\.\\zeta=s,\\qquad\\delta=r\.Letk⋆k^\{\\star\}index a parent containing a maximizer, and letj⋆j^\{\\star\}be the unique fragment index satisfyingk⋆∈ℐj⋆k^\{\\star\}\\in\\mathcal\{I\}\_\{j^\{\\star\}\}\. By Lemma[C\.1](https://arxiv.org/html/2608.07922#A3.Thmtheorem1),

f​\(xk⋆\)≥f⋆−s,0≤f⋆−fK⋆≤s\.f\(x\_\{k^\{\\star\}\}\)\\geq f^\{\\star\}\-s,\\qquad 0\\leq f^\{\\star\}\-f\_\{K\}^\{\\star\}\\leq s\.\(78\)The terminal confidence radius satisfies

aLser−1\\displaystyle a\_\{L\_\{\\mathrm\{ser\}\}\-1\}≤Cd​\[log⁡\(c⋄​K​Lser2/r\)N\+s\]≤Cd​s,\\displaystyle\\leq C\_\{d\}\\left\[\\sqrt\{\\frac\{\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{ser\}\}^\{2\}/r\)\}\{N\}\}\+s\\right\]\\leq C\_\{d\}s,\(79\)where the last inequality follows fromN=ns=⌈Adser​s−2​ℓT⌉N=n\_\{s\}=\\lceil A\_\{d\}^\{\\mathrm\{ser\}\}s^\{\-2\}\\ell\_\{T\}\\rceilandlog⁡\(c⋄​K​Lser2/r\)≤Cd​ℓT\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{ser\}\}^\{2\}/r\)\\leq C\_\{d\}\\ell\_\{T\}\.

Good event and safe active set\.Forj∈\[Js\]j\\in\[J\_\{s\}\], let𝒢j\\mathcal\{G\}\_\{j\}be the event that every tournament estimate revealed through the completion of final\-pass fragmentjjis within its prescribed radius, and set𝒢=𝒢Js\\mathcal\{G\}=\\mathcal\{G\}\_\{J\_\{s\}\}\. The union bound in Lemma[D\.1](https://arxiv.org/html/2608.07922#A4.Thmtheorem1)gives

𝒢1⊇⋯⊇𝒢Js,ℙ​\(𝒢∁\)≤r\.\\mathcal\{G\}\_\{1\}\\supseteq\\cdots\\supseteq\\mathcal\{G\}\_\{J\_\{s\}\},\\qquad\\mathbb\{P\}\(\\mathcal\{G\}^\{\\complement\}\)\\leq r\.The mask argument is fragment\-local\. On𝒢j\\mathcal\{G\}\_\{j\}, the final incumbent has gap at mostCd​sC\_\{d\}s, and every retained cell from fragmentjjsatisfies

sup\{k∈ℐj:Zk\(j\)=1\}supx∈PkΔf​\(x\)≤κd​s\.\\sup\_\{\\\{k\\in\\mathcal\{I\}\_\{j\}:Z\_\{k\}^\{\(j\)\}=1\\\}\}\\sup\_\{x\\in P\_\{k\}\}\\Delta\_\{f\}\(x\)\\leq\\kappa\_\{d\}s\.On𝒢\\mathcal\{G\}, the incumbent entering the final pass obeys

f⋆−f​\(xk¯\)\\displaystyle f^\{\\star\}\-f\(x\_\{\\bar\{k\}\}\)=\(f⋆−fK⋆\)\+\(fK⋆−f​\(xk¯\)\)\\displaystyle=\(f^\{\\star\}\-f\_\{K\}^\{\\star\}\)\+\(f\_\{K\}^\{\\star\}\-f\(x\_\{\\bar\{k\}\}\)\)≤s\+2​aLser−1≤Cd​s\.\\displaystyle\\leq s\+2a\_\{L\_\{\\mathrm\{ser\}\}\-1\}\\leq C\_\{d\}s\.Equation \([78](https://arxiv.org/html/2608.07922#A4.E78)\) givesfK⋆−f​\(xk⋆\)≤s=ζf\_\{K\}^\{\\star\}\-f\(x\_\{k^\{\\star\}\}\)\\leq s=\\zeta\. Hence the first implication in \([69](https://arxiv.org/html/2608.07922#A4.E69)\) yieldsZk⋆\(j⋆\)=1Z\_\{k^\{\\star\}\}^\{\(j^\{\\star\}\)\}=1\. The second implication in \([69](https://arxiv.org/html/2608.07922#A4.E69)\), together with \([78](https://arxiv.org/html/2608.07922#A4.E78)\) and \([79](https://arxiv.org/html/2608.07922#A4.E79)\), gives

Zk⋆\(j⋆\)=1,supj∈\[Js\]sup\{k∈ℐj:Zk\(j\)=1\}supx∈PkΔf​\(x\)≤κd​s\.Z\_\{k^\{\\star\}\}^\{\(j^\{\\star\}\)\}=1,\\qquad\\sup\_\{j\\in\[J\_\{s\}\]\}\\sup\_\{\\\{k\\in\\mathcal\{I\}\_\{j\}:Z\_\{k\}^\{\(j\)\}=1\\\}\}\\sup\_\{x\\in P\_\{k\}\}\\Delta\_\{f\}\(x\)\\leq\\kappa\_\{d\}s\.\(80\)For refinement batchjj, use the scheduled cell fragment\{Pk:k∈ℐj\}\\\{P\_\{k\}:k\\in\\mathcal\{I\}\_\{j\}\\\}, the maskZ\(j\)Z^\{\(j\)\}, and retained subset\{Pk:k∈ℐj,Zk\(j\)=1\}\\\{P\_\{k\}:k\\in\\mathcal\{I\}\_\{j\},\\ Z\_\{k\}^\{\(j\)\}=1\\\}\. The scheduled fragments are disjoint\. The fragment\-local bounds above, together with \([80](https://arxiv.org/html/2608.07922#A4.E80)\) on the intersection𝒢\\mathcal\{G\}, verify the hypotheses of Lemma[C\.3](https://arxiv.org/html/2608.07922#A3.Thmtheorem3)for\(𝒢j\)j=1Js\(\\mathcal\{G\}\_\{j\}\)\_\{j=1\}^\{J\_\{s\}\}\.

Batch, memory, and pull identities\.The batch count satisfies

Js​∑i=1Lser−1i\+Js​Lser\+Js\+1\\displaystyle J\_\{s\}\\sum\_\{i=1\}^\{L\_\{\\mathrm\{ser\}\}\-1\}i\+J\_\{s\}L\_\{\\mathrm\{ser\}\}\+J\_\{s\}\+1=Js​\(Lser​\(Lser\+1\)2\+1\)\+1\\displaystyle=J\_\{s\}\\left\(\\frac\{L\_\{\\mathrm\{ser\}\}\(L\_\{\\mathrm\{ser\}\}\+1\)\}\{2\}\+1\\right\)\+1=Js​Hser\+1≤B\.\\displaystyle=J\_\{s\}H\_\{\\mathrm\{ser\}\}\+1\\leq B\.After every pull the resident objects are oneSS\-bit mask and registers totaling at mostwctlw\_\{\\mathrm\{ctl\}\}bits; thus

S\+wctl≤W\.S\+w\_\{\\mathrm\{ctl\}\}\\leq W\.WriteT1T\_\{1\}andT2T\_\{2\}for the tournament and refinement pull counts\. SinceK≤Cd​s−dK\\leq C\_\{d\}s^\{\-d\},N=ns≤Cd​s−2​ℓTN=n\_\{s\}\\leq C\_\{d\}s^\{\-2\}\\ell\_\{T\}, andr≤sr\\leq s,

T1\\displaystyle T\_\{1\}≤Cd​K​N≤Cd​s−d−2​ℓT≤Cd​r−d−2​ℓT,\\displaystyle\\leq C\_\{d\}KN\\leq C\_\{d\}s^\{\-d\-2\}\\ell\_\{T\}\\leq C\_\{d\}r^\{\-d\-2\}\\ell\_\{T\},T2\\displaystyle T\_\{2\}≤Cd​r−d−2​ℓr≤Cd​r−d−2​ℓT\.\\displaystyle\\leq C\_\{d\}r^\{\-d\-2\}\\ell\_\{r\}\\leq C\_\{d\}r^\{\-d\-2\}\\ell\_\{T\}\.Hence

T1\+T2≤Cd​r−d−2​ℓT≤T/2T\_\{1\}\+T\_\{2\}\\leq C\_\{d\}r^\{\-d\-2\}\\ell\_\{T\}\\leq T/2after fixing the constant in Proposition[5\.3](https://arxiv.org/html/2608.07922#S5.Thmtheorem3)\.

Regret decomposition\.Letℰ\\mathcal\{E\}be the set of elimination rounds\. On𝒢\\mathcal\{G\}, Lemma[D\.1](https://arxiv.org/html/2608.07922#A4.Thmtheorem1)yields

∑t∈ℰΔf​\(At\)\\displaystyle\\sum\_\{t\\in\\mathcal\{E\}\}\\Delta\_\{f\}\(A\_\{t\}\)=\|ℰ\|​\(f⋆−fK⋆\)\+∑t∈ℰ\(fK⋆−f​\(At\)\)\\displaystyle=\|\\mathcal\{E\}\|\(f^\{\\star\}\-f\_\{K\}^\{\\star\}\)\+\\sum\_\{t\\in\\mathcal\{E\}\}\(f\_\{K\}^\{\\star\}\-f\(A\_\{t\}\)\)\(81\)≤s​\|ℰ\|\+Cd​K​\[N​log⁡\(c⋄​K​Lser2/r\)\+s​N\]\\displaystyle\\leq s\|\\mathcal\{E\}\|\+C\_\{d\}K\\left\[\\sqrt\{N\\log\(c\_\{\\diamond\}KL\_\{\\mathrm\{ser\}\}^\{2\}/r\)\}\+sN\\right\]\(82\)≤Cd​K​s−1​ℓT≤Cd​s−d−1​ℓT,\\displaystyle\\leq C\_\{d\}Ks^\{\-1\}\\ell\_\{T\}\\leq C\_\{d\}s^\{\-d\-1\}\\ell\_\{T\},\(83\)using\|ℰ\|≤Cd​K​N\|\\mathcal\{E\}\|\\leq C\_\{d\}KN,N≍ds−2​ℓTN\\asymp\_\{d\}s^\{\-2\}\\ell\_\{T\}, andK≤Cd​s−dK\\leq C\_\{d\}s^\{\-d\}\. Conditional streaming refinement gives

𝔼​\[∑t∉ℰΔf​\(At\)​𝟏𝒢\]≤Cd​\[s​r−d−2​ℓT\+T​r\]\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t\\notin\\mathcal\{E\}\}\\Delta\_\{f\}\(A\_\{t\}\)\\mathbf\{1\}\_\{\\mathcal\{G\}\}\\right\]\\leq C\_\{d\}\\left\[sr^\{\-d\-2\}\\ell\_\{T\}\+Tr\\right\]\.Finally,

𝔼​\[RegT​\(f\)​𝟏𝒢∁\]≤T​ℙ​\(𝒢∁\)≤T​r\.\\mathbb\{E\}\\\!\\left\[\\mathrm\{Reg\}\_\{T\}\(f\)\\mathbf\{1\}\_\{\\mathcal\{G\}^\{\\complement\}\}\\right\]\\leq T\\mathbb\{P\}\(\\mathcal\{G\}^\{\\complement\}\)\\leq Tr\.\(84\)Sincer≤sr\\leq s,

s−d−1​ℓT≤s​r−d−2​ℓT\.s^\{\-d\-1\}\\ell\_\{T\}\\leq sr^\{\-d\-2\}\\ell\_\{T\}\.Combining \([83](https://arxiv.org/html/2608.07922#A4.E83)\)– \([84](https://arxiv.org/html/2608.07922#A4.E84)\) therefore proves \([15](https://arxiv.org/html/2608.07922#S5.E15)\) and the proposition\. ∎

###### Lemma D\.2\(Optimized serialized active\-set branch\)\.

Fixd≥1d\\geq 1\. There exist constantsCd,Td\>0C\_\{d\},T\_\{d\}\>0such that, forT≥TdT\\geq T\_\{d\}, integerW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\}, andB≥Cd​ΓTB\\geq C\_\{d\}\\Gamma\_\{T\}, a learner using at mostBBcommitted batches and at mostWWbits after every pull satisfies

supf∈Lip1​\(\[0,1\]d\)ν∈𝔇​\(f\)𝔼ν​RegT​\(f\)≤Cd​Td\+2d\+3​ℓT1d\+3​\[\(TℓT\)dd\+2∧\(1\+\(B−1\)​WΓT\)\]−1d​\(d\+3\)\.\\sup\_\{\\begin\{subarray\}\{c\}f\\in\\mathrm\{Lip\}\_\{1\}\(\[0,1\]^\{d\}\)\\\\ \\nu\\in\\mathfrak\{D\}\(f\)\\end\{subarray\}\}\\mathbb\{E\}\_\{\\nu\}\\mathrm\{Reg\}\_\{T\}\(f\)\\leq C\_\{d\}T^\{\\frac\{d\+2\}\{d\+3\}\}\\ell\_\{T\}^\{\\frac\{1\}\{d\+3\}\}\\left\[\\left\(\\frac\{T\}\{\\ell\_\{T\}\}\\right\)^\{\\frac\{d\}\{d\+2\}\}\\wedge\\left\(1\+\\frac\{\(B\-1\)W\}\{\\Gamma\_\{T\}\}\\right\)\\right\]^\{\-\\frac\{1\}\{d\(d\+3\)\}\}\.\(85\)

###### Proof\.

In the nontrivial branch, the construction uses the exact batch count from Proposition[5\.3](https://arxiv.org/html/2608.07922#S5.Thmtheorem3)\. Putp=d\+2p=d\+2and fix a sufficiently large dimension\-dependent constantAdoptA\_\{d\}^\{\\mathrm\{opt\}\}\. Recallχ=\(B−1\)​W\\chi=\(B\-1\)Wand define

σT=\(Adopt​ℓTT\)1/p,Ξ=\(TℓT\)d/p∧\(1\+χAdopt​ΓT\)\.\\sigma\_\{T\}=\\left\(\\frac\{A\_\{d\}^\{\\mathrm\{opt\}\}\\ell\_\{T\}\}\{T\}\\right\)^\{1/p\},\\qquad\\Xi=\\left\(\\frac\{T\}\{\\ell\_\{T\}\}\\right\)^\{d/p\}\\wedge\\left\(1\+\\frac\{\\chi\}\{A\_\{d\}^\{\\mathrm\{opt\}\}\\Gamma\_\{T\}\}\\right\)\.\(86\)The first term is the statistically useful number of active\-region coordinates, whereas the second is the number that can be serialized under the memory–batch budget\. Thus the active\-set radius is of orderΞ−1/d\\Xi^\{\-1/d\}, clipped at the sequential resolution\. IfΞ\\Xiis below a sufficiently large dimension\-dependent constant, the root active set bound in Corollary[C\.4](https://arxiv.org/html/2608.07922#A3.Thmtheorem4)is at most the right side of \([85](https://arxiv.org/html/2608.07922#A4.E85)\)\. Otherwise define

s~=max⁡\{σT,Ξ−1/d\},r~=\(s~​ℓTT\)1/\(p\+1\),s=⌈s~⌉2,r=⌈r~⌉2\.\\widetilde\{s\}=\\max\\\{\\sigma\_\{T\},\\Xi^\{\-1/d\}\\\},\\qquad\\widetilde\{r\}=\\left\(\\frac\{\\widetilde\{s\}\\ell\_\{T\}\}\{T\}\\right\)^\{1/\(p\+1\)\},\\qquad s=\\lceil\\widetilde\{s\}\\rceil\_\{2\},\\qquad r=\\lceil\\widetilde\{r\}\\rceil\_\{2\}\.\(87\)After increasing the threshold andTdT\_\{d\}, these radii lie in\(0,1/16\]\(0,1/16\]and satisfyr≤sr\\leq s\.

Construct \([14](https://arxiv.org/html/2608.07922#S5.E14)\)\. Sincewctl=⌈Cdctl​ℓT⌉w\_\{\\mathrm\{ctl\}\}=\\lceil C\_\{d\}^\{\\mathrm\{ctl\}\}\\ell\_\{T\}\\rceilandW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\},

wctl≤W/2,Js≤Cd​\(1\+K/W\),Hser≤Cd​ΓT\.w\_\{\\mathrm\{ctl\}\}\\leq W/2,\\qquad J\_\{s\}\\leq C\_\{d\}\(1\+K/W\),\\qquad H\_\{\\mathrm\{ser\}\}\\leq C\_\{d\}\\Gamma\_\{T\}\.In the nontrivial branchχ/\(Adopt​ΓT\)\>1\\chi/\(A\_\{d\}^\{\\mathrm\{opt\}\}\\Gamma\_\{T\}\)\>1\. SinceK≤Cd​s−d≤Cd​ΞK\\leq C\_\{d\}s^\{\-d\}\\leq C\_\{d\}\\Xi, the hypothesisB≥Cd​ΓTB\\geq C\_\{d\}\\Gamma\_\{T\}and sufficiently large constants give

Js​Hser\\displaystyle J\_\{s\}H\_\{\\mathrm\{ser\}\}≤Cd​Js​ΓT≤Cd​\(1\+KW\)​ΓT\\displaystyle\\leq C\_\{d\}J\_\{s\}\\Gamma\_\{T\}\\leq C\_\{d\}\\left\(1\+\\frac\{K\}\{W\}\\right\)\\Gamma\_\{T\}≤Cd​ΓT\+Cd​Ξ​ΓTW\\displaystyle\\leq C\_\{d\}\\Gamma\_\{T\}\+\\frac\{C\_\{d\}\\Xi\\Gamma\_\{T\}\}\{W\}≤Cd​ΓT\+Cd​ΓTW\+Cd​\(B−1\)Adopt≤B−1\.\\displaystyle\\leq C\_\{d\}\\Gamma\_\{T\}\+\\frac\{C\_\{d\}\\Gamma\_\{T\}\}\{W\}\+\\frac\{C\_\{d\}\(B\-1\)\}\{A\_\{d\}^\{\\mathrm\{opt\}\}\}\\leq B\-1\.\(88\)The last inequality follows by first fixingAdoptA\_\{d\}^\{\\mathrm\{opt\}\}and then the constant inB≥Cd​ΓTB\\geq C\_\{d\}\\Gamma\_\{T\}sufficiently large\. HenceJs​Hser\+1≤BJ\_\{s\}H\_\{\\mathrm\{ser\}\}\+1\\leq B\.

The choices≥σTs\\geq\\sigma\_\{T\}andrp\+1≍s​ℓT/Tr^\{p\+1\}\\asymp s\\ell\_\{T\}/Tgive

r−p​ℓT≤Cd​T​\(Adopt\)−1/\(p\+1\)\.r^\{\-p\}\\ell\_\{T\}\\leq C\_\{d\}T\\bigl\(A\_\{d\}^\{\\mathrm\{opt\}\}\\bigr\)^\{\-1/\(p\+1\)\}\.Thus the exploratory\-pull condition in Proposition[5\.3](https://arxiv.org/html/2608.07922#S5.Thmtheorem3)holds after increasingAdoptA\_\{d\}^\{\\mathrm\{opt\}\}, and the proposition applies\. Moreover,

s​r−p​ℓT≍T​r\.sr^\{\-p\}\\ell\_\{T\}\\asymp Tr\.\(89\)Substitution of \([87](https://arxiv.org/html/2608.07922#A4.E87)\) intoT​rTrgives

supf∈Lip1​\(\[0,1\]d\)ν∈𝔇​\(f\)𝔼ν​RegT​\(f\)≤Cd​Td\+2d\+3​ℓT1d\+3​Ξ−1d​\(d\+3\),\\sup\_\{\\begin\{subarray\}\{c\}f\\in\\mathrm\{Lip\}\_\{1\}\(\[0,1\]^\{d\}\)\\\\ \\nu\\in\\mathfrak\{D\}\(f\)\\end\{subarray\}\}\\mathbb\{E\}\_\{\\nu\}\\mathrm\{Reg\}\_\{T\}\(f\)\\leq C\_\{d\}T^\{\\frac\{d\+2\}\{d\+3\}\}\\ell\_\{T\}^\{\\frac\{1\}\{d\+3\}\}\\Xi^\{\-\\frac\{1\}\{d\(d\+3\)\}\},which is \([85](https://arxiv.org/html/2608.07922#A4.E85)\)\. At statistical saturation it specializes toCd​T\(d\+1\)/\(d\+2\)​ℓT1/\(d\+2\)C\_\{d\}T^\{\(d\+1\)/\(d\+2\)\}\\ell\_\{T\}^\{1/\(d\+2\)\}\. ∎

## Appendix EIn\-memory hierarchical active sets and the joint upper bound

Fixd≥1d\\geq 1and putp:=d\+2p:=d\+2\. This appendix analyzes the in\-memory hierarchy used when the complete active\-set mask fits in memory\. ForL≥1L\\geq 1, define

γd​\(L\):=p−11−p−L\.\\gamma\_\{d\}\(L\):=\\frac\{p\-1\}\{1\-p^\{\-L\}\}\.The construction uses explicit equalized radii\. For an integerL≥1L\\geq 1and a dyadic terminal radiuss=2−jss=2^\{\-j\_\{s\}\}, set

θℓ:=1−p−ℓ1−p−L,jℓ:=⌈θℓ​js⌉,uℓ:=2−jℓ,0≤ℓ≤L\.\\theta\_\{\\ell\}:=\\frac\{1\-p^\{\-\\ell\}\}\{1\-p^\{\-L\}\},\\qquad j\_\{\\ell\}:=\\lceil\\theta\_\{\\ell\}j\_\{s\}\\rceil,\\qquad u\_\{\\ell\}:=2^\{\-j\_\{\\ell\}\},\\qquad 0\\leq\\ell\\leq L\.Then1=u0≥⋯≥uL=s1=u\_\{0\}\\geq\\cdots\\geq u\_\{L\}=s\. For the ideal radiiu~ℓ=sθℓ\\widetilde\{u\}\_\{\\ell\}=s^\{\\theta\_\{\\ell\}\},

u~ℓ−1​u~ℓ−p=s−γd​\(L\)\.\\widetilde\{u\}\_\{\\ell\-1\}\\widetilde\{u\}\_\{\\ell\}^\{\-p\}=s^\{\-\\gamma\_\{d\}\(L\)\}\.Becausejℓ=⌈θℓ​js⌉j\_\{\\ell\}=\\lceil\\theta\_\{\\ell\}j\_\{s\}\\rceil,u~ℓ/2<uℓ≤u~ℓ\\widetilde\{u\}\_\{\\ell\}/2<u\_\{\\ell\}\\leq\\widetilde\{u\}\_\{\\ell\}anduℓ≥su\_\{\\ell\}\\geq s\. Consequently dyadic rounding changes every productuℓ−1​uℓ−pu\_\{\\ell\-1\}u\_\{\\ell\}^\{\-p\}by at most the factor2p2^\{p\}, and

∑ℓ=1Luℓ−1​uℓ−p≤Cd​L​s−γd​\(L\),∑ℓ=1Luℓ−p≤L​s−p\.\\sum\_\{\\ell=1\}^\{L\}u\_\{\\ell\-1\}u\_\{\\ell\}^\{\-p\}\\leq C\_\{d\}Ls^\{\-\\gamma\_\{d\}\(L\)\},\\qquad\\sum\_\{\\ell=1\}^\{L\}u\_\{\\ell\}^\{\-p\}\\leq Ls^\{\-p\}\.\(90\)The factorLLis polylogarithmic in the regime where this branch is used and is absorbed by the logarithmic envelope of Theorem[3\.4](https://arxiv.org/html/2608.07922#S3.Thmtheorem4)\.

Fix sufficiently large constantsAdhier,Adsamp≥1A\_\{d\}^\{\\mathrm\{hier\}\},A\_\{d\}^\{\\mathrm\{samp\}\}\\geq 1\. For3≤B≤T3\\leq B\\leq Tand dyadic0<r≤s≤1/160<r\\leq s\\leq 1/16, set

LB​\(s\)\\displaystyle L\_\{B\}\(s\):=min⁡\{B−2,⌊\(d\+1\)​log⁡\(1/s\)log⁡\(d\+2\)⌋\},\\displaystyle:=\\min\\left\\\{B\-2,\\left\\lfloor\\frac\{\(d\+1\)\\log\(1/s\)\}\{\\log\(d\+2\)\}\\right\\rfloor\\right\\\},bB,r\\displaystyle b\_\{B,r\}:=bl⁡\(Adhier​B​r−d−1\),bB,T:=bl⁡\(8​B​T\)\.\\displaystyle:=\\operatorname\{bl\}\(A\_\{d\}^\{\\mathrm\{hier\}\}Br^\{\-d\-1\}\),\\qquad b\_\{B,T\}:=\\operatorname\{bl\}\(8BT\)\.
###### Lemma E\.1\(In\-memory hierarchical active\-set branch\)\.

There exist constantsCd,Td\>0C\_\{d\},T\_\{d\}\>0such that, forT≥TdT\\geq T\_\{d\}, the resource conditions

Cd​LB​\(s\)​bB,r​r−d−2≤T/2,W≥Cd​\(s−d\+bB,r\)C\_\{d\}L\_\{B\}\(s\)b\_\{B,r\}r^\{\-d\-2\}\\leq T/2,\\qquad W\\geq C\_\{d\}\\left\(s^\{\-d\}\+b\_\{B,r\}\\right\)\(91\)imply the existence of a learner using at mostLB​\(s\)\+2≤BL\_\{B\}\(s\)\+2\\leq Bbatches and at mostWWmemory bits after every pull, such that

supf∈Lip1​\(𝒳\)ν∈𝔇​\(f\)𝔼ν​RegT​\(f\)≤Cd​\[LB​\(s\)​bB,r​s−γd​\(LB​\(s\)\)\+bB,r​s​r−d−2\+T​r\]\.\\sup\_\{\\begin\{subarray\}\{c\}f\\in\\mathrm\{Lip\}\_\{1\}\(\\mathcal\{X\}\)\\\\ \\nu\\in\\mathfrak\{D\}\(f\)\\end\{subarray\}\}\\mathbb\{E\}\_\{\\nu\}\\mathrm\{Reg\}\_\{T\}\(f\)\\leq C\_\{d\}\\left\[L\_\{B\}\(s\)b\_\{B,r\}s^\{\-\\gamma\_\{d\}\(L\_\{B\}\(s\)\)\}\+b\_\{B,r\}sr^\{\-d\-2\}\+Tr\\right\]\.\(92\)

###### Proof\.

SetL:=LB​\(s\)L:=L\_\{B\}\(s\)\. Sinces≤1/16s\\leq 1/16,L≥1L\\geq 1\. Apply the equalized construction above to obtain nested dyadic radii

1=u0≥u1≥⋯≥uL=s1=u\_\{0\}\\geq u\_\{1\}\\geq\\cdots\\geq u\_\{L\}=ssatisfying \([90](https://arxiv.org/html/2608.07922#A5.E90)\)\. The associated dyadic partitions are nested\. Index the terminal partition as𝒫s=\{Pk:k∈\[K\]\}\\mathcal\{P\}\_\{s\}=\\\{P\_\{k\}:k\\in\[K\]\\\}\. Initialize the unique level\-zero root bit to one\.

Committed level update\.For every dyadic cellCC, letxCx\_\{C\}be its midpoint representative\. At levelℓ\\ell, the complete two\-sweep schedule is committed from the old mask as one batch\. The second\-sweep actions depend only on that old mask; the first\-sweep benchmark affects only the state update after the corresponding rewards arrive\. Thus using the benchmark within the batch does not redesign any committed action\. A real level\-ℓ\\ellcell receives

nℓ=⌈Adsamp​uℓ−2​bB,r⌉n\_\{\\ell\}=\\left\\lceil A\_\{d\}^\{\\mathrm\{samp\}\}u\_\{\\ell\}^\{\-2\}b\_\{B,r\}\\right\\rceilpulls in each sweep, with quantization meshεℓ=uℓ/512\\varepsilon\_\{\\ell\}=u\_\{\\ell\}/512and confidence half\-width

aℓ:=uℓ/32\.a\_\{\\ell\}:=u\_\{\\ell\}/32\.Letμ^C,i\\widehat\{\\mu\}\_\{C,i\}be the rounded empirical mean of cellCCin sweepi∈\{1,2\}i\\in\\\{1,2\\\}\. IfCCis a level\-ℓ\\ellcell, letancℓ⁡\(C\)\\operatorname\{anc\}\_\{\\ell\}\(C\)be its unique ancestor at the preceding selected level, as in \([46](https://arxiv.org/html/2608.07922#A3.E46)\)\. A cell whose ancestor is inactive uses as filler the representative of the lexicographically first active cell at the preceding selected level; if the old mask is empty, it usesx∘x\_\{\\circ\}\.

The first sweep forms the benchmark

λℓ:=max\{C:Zℓ−1,ancℓ⁡\(C\)=1\}⁡\{μ^C,1−aℓ\},\\lambda\_\{\\ell\}:=\\max\_\{\\\{C:Z\_\{\\ell\-1,\\operatorname\{anc\}\_\{\\ell\}\(C\)\}=1\\\}\}\\\{\\widehat\{\\mu\}\_\{C,1\}\-a\_\{\\ell\}\\\},withλℓ=−1\\lambda\_\{\\ell\}=\-1when the old mask is empty\. The second sweep writes

Zℓ,C=Zℓ−1,ancℓ⁡\(C\)​𝟏\{μ^C,2\+aℓ≥λℓ−uℓ\}\.Z\_\{\\ell,C\}=Z\_\{\\ell\-1,\\operatorname\{anc\}\_\{\\ell\}\(C\)\}\\mathbf\{1\}\_\{\\\{\\widehat\{\\mu\}\_\{C,2\}\+a\_\{\\ell\}\\geq\\lambda\_\{\\ell\}\-u\_\{\\ell\}\\\}\}\.\(93\)Thus \([93](https://arxiv.org/html/2608.07922#A5.E93)\) uses the same LCB–UCB comparison as the serialized branch, with geometric slackuℓu\_\{\\ell\}\. A filler can never create an active cell, and the old mask is erased only after the new mask is complete\.

Concentration and active\-set invariant\.Across all levels and both sweeps there are at most

Cd​L​r−d≤Cd​B​r−dC\_\{d\}Lr^\{\-d\}\\leq C\_\{d\}Br^\{\-d\}potential real segments\. For each level\-ℓ\\ellcellCCand sweepi∈\{1,2\}i\\in\\\{1,2\\\}, letℋℓ,C,i\\mathcal\{H\}\_\{\\ell,C,i\}be the interaction sigma\-field before that segment begins\. The indicatorZℓ−1,ancℓ⁡\(C\)Z\_\{\\ell\-1,\\operatorname\{anc\}\_\{\\ell\}\(C\)\}and the segment arm areℋℓ,C,i\\mathcal\{H\}\_\{\\ell,C,i\}\-measurable; on\{Zℓ−1,ancℓ⁡\(C\)=1\}\\\{Z\_\{\\ell\-1,\\operatorname\{anc\}\_\{\\ell\}\(C\)\}=1\\\}the segment pullsxCx\_\{C\}\. Conditional Hoeffding and quantization give, almost surely,

𝟏\{Zℓ−1,ancℓ⁡\(C\)=1\}​ℙ​\(\|μ^C,i−f​\(xC\)\|\>aℓ∣ℋℓ,C,i\)≤2​e−cd​bB,r\.\\mathbf\{1\}\_\{\\\{Z\_\{\\ell\-1,\\operatorname\{anc\}\_\{\\ell\}\(C\)\}=1\\\}\}\\mathbb\{P\}\\\!\\left\(\|\\widehat\{\\mu\}\_\{C,i\}\-f\(x\_\{C\}\)\|\>a\_\{\\ell\}\\mid\\mathcal\{H\}\_\{\\ell,C,i\}\\right\)\\leq 2e^\{\-c\_\{d\}b\_\{B,r\}\}\.The definition ofbB,rb\_\{B,r\}and a sufficiently large choice ofAdsampA\_\{d\}^\{\\mathrm\{samp\}\}therefore give an eventℰ0\\mathcal\{E\}\_\{0\}with

ℙ​\(ℰ0∁\)≤r/2\\mathbb\{P\}\(\\mathcal\{E\}\_\{0\}^\{\\complement\}\)\\leq r/2on which every realized real score is accurate at its level\.

Fixx⋆∈arg​maxx∈𝒳⁡f​\(x\)x^\{\\star\}\\in\\operatorname\*\{arg\\,max\}\_\{x\\in\\mathcal\{X\}\}f\(x\)\. We prove by induction that

∃Cℓ⋆:x⋆∈Cℓ⋆,Zℓ,Cℓ⋆=1,sup\{C:Zℓ,C=1\}supx∈C\(f⋆−f\(x\)\)≤κduℓ\.\\exists C\_\{\\ell\}^\{\\star\}:\\quad x^\{\\star\}\\in C\_\{\\ell\}^\{\\star\},\\quad Z\_\{\\ell,C\_\{\\ell\}^\{\\star\}\}=1,\\qquad\\sup\_\{\\\{C:Z\_\{\\ell,C\}=1\\\}\}\\sup\_\{x\\in C\}\\bigl\(f^\{\\star\}\-f\(x\)\\bigr\)\\leq\\kappa\_\{d\}u\_\{\\ell\}\.\(94\)The claim is immediate at level zero\. Assume it holds at levelℓ−1\\ell\-1, and letCℓ⋆C\_\{\\ell\}^\{\\star\}be the unique level\-ℓ\\ellcell containingx⋆x^\{\\star\}\. Its ancestor is active\. Onℰ0\\mathcal\{E\}\_\{0\},

λℓ≤f⋆,λℓ≥μ^Cℓ⋆,1−aℓ≥f⋆−uℓ−2​aℓ\.\\lambda\_\{\\ell\}\\leq f^\{\\star\},\\qquad\\lambda\_\{\\ell\}\\geq\\widehat\{\\mu\}\_\{C\_\{\\ell\}^\{\\star\},1\}\-a\_\{\\ell\}\\geq f^\{\\star\}\-u\_\{\\ell\}\-2a\_\{\\ell\}\.Moreover,

μ^Cℓ⋆,2\+aℓ≥f​\(xCℓ⋆\)≥f⋆−uℓ≥λℓ−uℓ,\\widehat\{\\mu\}\_\{C\_\{\\ell\}^\{\\star\},2\}\+a\_\{\\ell\}\\geq f\(x\_\{C\_\{\\ell\}^\{\\star\}\}\)\\geq f^\{\\star\}\-u\_\{\\ell\}\\geq\\lambda\_\{\\ell\}\-u\_\{\\ell\},soCℓ⋆C\_\{\\ell\}^\{\\star\}survives\. Conversely, ifCCsurvives, then \([93](https://arxiv.org/html/2608.07922#A5.E93)\) gives

f​\(xC\)\\displaystyle f\(x\_\{C\}\)≥μ^C,2−aℓ\\displaystyle\\geq\\widehat\{\\mu\}\_\{C,2\}\-a\_\{\\ell\}≥λℓ−uℓ−2​aℓ\\displaystyle\\geq\\lambda\_\{\\ell\}\-u\_\{\\ell\}\-2a\_\{\\ell\}≥f⋆−2​uℓ−4​aℓ\.\\displaystyle\\geq f^\{\\star\}\-2u\_\{\\ell\}\-4a\_\{\\ell\}\.For everyx∈Cx\\in C, Lipschitzness and the diameter bound add at mostuℓu\_\{\\ell\}\. Sinceaℓ=uℓ/32a\_\{\\ell\}=u\_\{\\ell\}/32, every active cell is pointwise\(3\+1/8\)​uℓ\(3\+1/8\)u\_\{\\ell\}\-optimal, which is at mostκd​uℓ\\kappa\_\{d\}u\_\{\\ell\}by the fixed choice of the active\-set constant\. In particular, the old mask is nonempty onℰ0\\mathcal\{E\}\_\{0\}, and every filler used at levelℓ\\elllies in an active level\-\(ℓ−1\)\(\\ell\-1\)cell\.

Regret and resources\.Letℛℓ\\mathcal\{R\}\_\{\\ell\}denote the regret incurred by the two level\-ℓ\\ellsweeps\. Onℰ0\\mathcal\{E\}\_\{0\}, every real action and every filler at levelℓ\\elllies in an active level\-\(ℓ−1\)\(\\ell\-1\)cell and has gap at mostCd​uℓ−1C\_\{d\}u\_\{\\ell\-1\}\. Thus

ℛℓ​𝟏ℰ0≤Cd​bB,r​uℓ−1​uℓ−p\.\\mathcal\{R\}\_\{\\ell\}\\mathbf\{1\}\_\{\\mathcal\{E\}\_\{0\}\}\\leq C\_\{d\}b\_\{B,r\}\\,u\_\{\\ell\-1\}u\_\{\\ell\}^\{\-p\}\.\(95\)Summing and using \([90](https://arxiv.org/html/2608.07922#A5.E90)\) gives

∑ℓ=1Lℛℓ​𝟏ℰ0≤Cd​L​bB,r​s−γd​\(L\)\.\\sum\_\{\\ell=1\}^\{L\}\\mathcal\{R\}\_\{\\ell\}\\mathbf\{1\}\_\{\\mathcal\{E\}\_\{0\}\}\\leq C\_\{d\}Lb\_\{B,r\}s^\{\-\\gamma\_\{d\}\(L\)\}\.\(96\)The total number of narrowing pulls is at mostCd​L​bB,r​s−p≤Cd​L​bB,r​r−pC\_\{d\}Lb\_\{B,r\}s^\{\-p\}\\leq C\_\{d\}Lb\_\{B,r\}r^\{\-p\}\.

At levelLL, the active cells form a valid safe scale\-ssactive set on the boundary\-history\-measurable eventℰ0\\mathcal\{E\}\_\{0\}\. Enumerate the terminal partition as𝒫s=\{Pk:k∈\[K\]\}\\mathcal\{P\}\_\{s\}=\\\{P\_\{k\}:k\\in\[K\]\\\}and setZk:=ZL,PkZ\_\{k\}:=Z\_\{L,P\_\{k\}\}\. For terminal refinement, use the single scheduled index fragment\[K\]\[K\], retain exactly the cells selected byZZ, and use the representative of the lexicographically first active cell in filler slots\. Onℰ0\\mathcal\{E\}\_\{0\}, that incumbent has gap at mostκd​s\\kappa\_\{d\}s\. Lemma[C\.3](https://arxiv.org/html/2608.07922#A3.Thmtheorem3)therefore applies with validity eventℰ0\\mathcal\{E\}\_\{0\}\. It uses one additional committed batch, andℓr≤Cd​bB,r\\ell\_\{r\}\\leq C\_\{d\}b\_\{B,r\}\. One final batch exploits its output\. The construction therefore usesL\+2≤BL\+2\\leq Bbatches\. The old and new masks useCd​s−dC\_\{d\}s^\{\-d\}bits, while addresses, counters, quantized sums,λℓ\\lambda\_\{\\ell\}, and the global point–score pair useCd​bB,rC\_\{d\}b\_\{B,r\}bits\. Under \([91](https://arxiv.org/html/2608.07922#A5.E91)\), all pulls fit before a nonempty exploitation batch and the memory uses at mostWWbits after every pull\. The narrowing phase contributes at mostT​ℙ​\(ℰ0∁\)T\\mathbb\{P\}\(\\mathcal\{E\}\_\{0\}^\{\\complement\}\)outsideℰ0\\mathcal\{E\}\_\{0\}, while the conditional refinement lemma contributes anotherT​ℙ​\(ℰ0∁\)T\\mathbb\{P\}\(\\mathcal\{E\}\_\{0\}^\{\\complement\}\)in addition to its ownO​\(T​r\)O\(Tr\)score\-failure charge\. Since2​T​ℙ​\(ℰ0∁\)≤T​r2T\\mathbb\{P\}\(\\mathcal\{E\}\_\{0\}^\{\\complement\}\)\\leq Tr, combining these bounds with \([96](https://arxiv.org/html/2608.07922#A5.E96)\) proves \([92](https://arxiv.org/html/2608.07922#A5.E92)\)\.

∎

### E\.1Proof of the joint upper bound

###### Proof of the upper bound in Theorem[3\.4](https://arxiv.org/html/2608.07922#S3.Thmtheorem4)\.

ForB=1B=1, the fixed\-action policy has regret at mostTT, whileβd,1=1\\beta\_\{d,1\}=1\. Fix a sufficiently large constantAdenv\>0A\_\{d\}^\{\\mathrm\{env\}\}\>0\. Recallχ=\(B−1\)​W\\chi=\(B\-1\)Wand put

B0=⌈Adenv​ΓT⌉,υd=1d​\(d\+3\)\.B\_\{0\}=\\lceil A\_\{d\}^\{\\mathrm\{env\}\}\\Gamma\_\{T\}\\rceil,\\qquad\\upsilon\_\{d\}=\\frac\{1\}\{d\(d\+3\)\}\.We use the root construction forB=2B=2, the in\-memory construction for3≤B<B03\\leq B<B\_\{0\}, and the serialized construction forB≥B0B\\geq B\_\{0\}\. Every choice is measurable with respect to the known parameters andℱ0\\mathcal\{F\}\_\{0\}\.

Two batches\.ForB=2B=2, Corollary[C\.4](https://arxiv.org/html/2608.07922#A3.Thmtheorem4), the identityβd,2=d\+2d\+3\\beta\_\{d,2\}=\\frac\{d\+2\}\{d\+3\}, andW≥Cd​ℓTW\\geq C\_\{d\}\\ell\_\{T\}give

ℜT​\(2,W\)≤Cd​Td\+2d\+3​ℓT1/\(d\+3\)≤Cd​ℓT​Tβd,222\.\\mathfrak\{R\}\_\{T\}\(2,W\)\\leq C\_\{d\}T^\{\\frac\{d\+2\}\{d\+3\}\}\\ell\_\{T\}^\{1/\(d\+3\)\}\\leq C\_\{d\}\\ell\_\{T\}\\frac\{T^\{\\beta\_\{d,2\}\}\}\{2^\{2\}\}\.The memory\-limited term in \([60](https://arxiv.org/html/2608.07922#A3.E60)\) is at mostTαdT^\{\\alpha\_\{d\}\}after increasing the logarithmic\-memory constant\. Hence this regime is bounded by the right side of \([5](https://arxiv.org/html/2608.07922#S3.E5)\)\.

Moderate batch complexity\.Suppose3≤B<B03\\leq B<B\_\{0\}\. Putb¯T=bB,T\\bar\{b\}\_\{T\}=b\_\{B,T\}and

ηT:=Adenv​ΓT​b¯TT,γ⋆:=p−11−p−\(B−2\),ϑ:=p\(p\+1\)​γ⋆\+1\.\\eta\_\{T\}:=\\frac\{A\_\{d\}^\{\\mathrm\{env\}\}\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\}\{T\},\\qquad\\gamma\_\{\\star\}:=\\frac\{p\-1\}\{1\-p^\{\-\(B\-2\)\}\},\\qquad\\vartheta:=\\frac\{p\}\{\(p\+1\)\\gamma\_\{\\star\}\+1\}\.Then

γ⋆​ϑ=βd,B,1−1\+ϑp\+1=βd,B,ϑ≤1p\.\\gamma\_\{\\star\}\\vartheta=\\beta\_\{d,B\},\\qquad 1\-\\frac\{1\+\\vartheta\}\{p\+1\}=\\beta\_\{d,B\},\\qquad\\vartheta\\leq\\frac\{1\}\{p\}\.HeresBs\_\{B\}is the radius dictated byBB\-level narrowing,sWs\_\{W\}is the smallest radius whose complete mask fits in memory, andr~\\widetilde\{r\}balances fine refinement with exploitation\. Set

sB:=ηTϑ,sW:=\(Adenv1∨W\)1/d,s~:=sB∨sW,r~:=\(ηT​s~\)1/\(p\+1\)\.s\_\{B\}:=\\eta\_\{T\}^\{\\vartheta\},\\qquad s\_\{W\}:=\\left\(\\frac\{A\_\{d\}^\{\\mathrm\{env\}\}\}\{1\\vee W\}\\right\)^\{1/d\},\\qquad\\widetilde\{s\}:=s\_\{B\}\\vee s\_\{W\},\\qquad\\widetilde\{r\}:=\(\\eta\_\{T\}\\widetilde\{s\}\)^\{1/\(p\+1\)\}\.ForTTlarge enough,ηT≤1\\eta\_\{T\}\\leq 1\. Sincep​ϑ≤1p\\vartheta\\leq 1ands~≥sB=ηTϑ\\widetilde\{s\}\\geq s\_\{B\}=\\eta\_\{T\}^\{\\vartheta\},

ηT≤s~p,r~=\(ηT​s~\)1/\(p\+1\)≤s~\.\\eta\_\{T\}\\leq\\widetilde\{s\}^\{p\},\\qquad\\widetilde\{r\}=\(\\eta\_\{T\}\\widetilde\{s\}\)^\{1/\(p\+1\)\}\\leq\\widetilde\{s\}\.\(97\)After increasing the logarithmic\-memory constant andTdT\_\{d\}, uniformly over3≤B<B03\\leq B<B\_\{0\}we also haves~≤1/32\\widetilde\{s\}\\leq 1/32\. Take the smallest dyadics≥s~s\\geq\\widetilde\{s\}andr≥r~r\\geq\\widetilde\{r\}\. Dyadic rounding is monotone, so0<r≤s≤1/160<r\\leq s\\leq 1/16\.

The lower boundr~≥ηT1/p\\widetilde\{r\}\\geq\\eta\_\{T\}^\{1/p\}from \([97](https://arxiv.org/html/2608.07922#A5.E97)\) implieslog⁡\(1/r\)≤Cd​log⁡T\\log\(1/r\)\\leq C\_\{d\}\\log Tand hencebB,r≤Cd​b¯Tb\_\{B,r\}\\leq C\_\{d\}\\bar\{b\}\_\{T\}\. Moreover,s≥sWs\\geq s\_\{W\}givess−d≤\(1∨W\)/Adenvs^\{\-d\}\\leq\(1\\vee W\)/A\_\{d\}^\{\\mathrm\{env\}\}; together withbB,r≤Cd​ℓT≤W/Adenvb\_\{B,r\}\\leq C\_\{d\}\\ell\_\{T\}\\leq W/A\_\{d\}^\{\\mathrm\{env\}\}this verifies the memory condition in \([91](https://arxiv.org/html/2608.07922#A5.E91)\)\. WithL=LB​\(s\)≤B<B0≤Cd​ΓTL=L\_\{B\}\(s\)\\leq B<B\_\{0\}\\leq C\_\{d\}\\Gamma\_\{T\}, the same scale relation givesr−p≤Cd​ηT−1r^\{\-p\}\\leq C\_\{d\}\\eta\_\{T\}^\{\-1\}and therefore

L​bB,r​r−p≤Cd​ΓT​b¯T​ηT−1≤T/2Lb\_\{B,r\}r^\{\-p\}\\leq C\_\{d\}\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\\eta\_\{T\}^\{\-1\}\\leq T/2after increasingAdenvA\_\{d\}^\{\\mathrm\{env\}\}\. Lemma[E\.1](https://arxiv.org/html/2608.07922#A5.Thmtheorem1)therefore applies\. Sincerp\+1≍ηT​sr^\{p\+1\}\\asymp\\eta\_\{T\}sandbB,r≤Cd​b¯Tb\_\{B,r\}\\leq C\_\{d\}\\bar\{b\}\_\{T\}, its terminal refinement term satisfies

bB,r​s​r−p≍bB,rηT​r≤Cd​T​r\.b\_\{B,r\}sr^\{\-p\}\\asymp\\frac\{b\_\{B,r\}\}\{\\eta\_\{T\}\}r\\leq C\_\{d\}Tr\.
IfL=B−2L=B\-2, thenγd​\(L\)=γ⋆\\gamma\_\{d\}\(L\)=\\gamma\_\{\\star\}ands≥sBs\\geq s\_\{B\}, so

L​bB,r​s−γd​\(L\)≤Cd​ΓT​b¯T​ηT−γ⋆​ϑ≤Cd​Tβd,B​\(ΓT​b¯T\)1−βd,B\.Lb\_\{B,r\}s^\{\-\\gamma\_\{d\}\(L\)\}\\leq C\_\{d\}\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\\eta\_\{T\}^\{\-\\gamma\_\{\\star\}\\vartheta\}\\leq C\_\{d\}T^\{\\beta\_\{d,B\}\}\(\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\)^\{1\-\\beta\_\{d,B\}\}\.IfL<B−2L<B\-2, then

L=⌊\(p−1\)​log⁡\(1/s\)log⁡p⌋\.L=\\left\\lfloor\\frac\{\(p\-1\)\\log\(1/s\)\}\{\\log p\}\\right\\rfloor\.Writingq=p−Lq=p^\{\-L\}givesq≤p​sp−1q\\leq ps^\{p\-1\}andq≤1/pq\\leq 1/p\. Therefore

γd​\(L\)−\(p−1\)=\(p−1\)​q1−q≤Cd​sp−1,\\gamma\_\{d\}\(L\)\-\(p\-1\)=\\frac\{\(p\-1\)q\}\{1\-q\}\\leq C\_\{d\}s^\{p\-1\},and the boundedness ofsp−1​log⁡\(1/s\)s^\{p\-1\}\\log\(1/s\)yields

s−γd​\(L\)=s−\(p−1\)​exp⁡\(\(γd​\(L\)−\(p−1\)\)​log⁡\(1/s\)\)≤Cd​s−\(p−1\)\.s^\{\-\\gamma\_\{d\}\(L\)\}=s^\{\-\(p\-1\)\}\\exp\\\!\\left\(\(\\gamma\_\{d\}\(L\)\-\(p\-1\)\)\\log\(1/s\)\\right\)\\leq C\_\{d\}s^\{\-\(p\-1\)\}\.UsingηT≤sp\\eta\_\{T\}\\leq s^\{p\}from \([97](https://arxiv.org/html/2608.07922#A5.E97)\),

L​bB,r​s−γd​\(L\)≤Cd​ΓT​b¯T​s−\(p−1\)≤Cd​T​ηT​s−\(p−1\)≤Cd​T​\(ηT​s\)1/\(p\+1\)≤Cd​T​r\.Lb\_\{B,r\}s^\{\-\\gamma\_\{d\}\(L\)\}\\leq C\_\{d\}\\Gamma\_\{T\}\\bar\{b\}\_\{T\}s^\{\-\(p\-1\)\}\\leq C\_\{d\}T\\eta\_\{T\}s^\{\-\(p\-1\)\}\\leq C\_\{d\}T\(\\eta\_\{T\}s\)^\{1/\(p\+1\)\}\\leq C\_\{d\}Tr\.Finally,s=sB∨sWs=s\_\{B\}\\vee s\_\{W\}up to a factor two andr≍\(ηT​s\)1/\(p\+1\)r\\asymp\(\\eta\_\{T\}s\)^\{1/\(p\+1\)\}imply

T​r≤Cd​max⁡\{Tβd,B​\(ΓT​b¯T\)1−βd,B,Td\+2d\+3​\(ΓT​b¯T\)1/\(p\+1\)​\(1∨W\)−υd\}\.Tr\\leq C\_\{d\}\\max\\left\\\{T^\{\\beta\_\{d,B\}\}\(\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\)^\{1\-\\beta\_\{d,B\}\},T^\{\\frac\{d\+2\}\{d\+3\}\}\(\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\)^\{1/\(p\+1\)\}\(1\\vee W\)^\{\-\\upsilon\_\{d\}\}\\right\\\}\.SinceB≤Cd​ΓTB\\leq C\_\{d\}\\Gamma\_\{T\},b¯T≤Cd​ℓT\\bar\{b\}\_\{T\}\\leq C\_\{d\}\\ell\_\{T\},ΓT=O​\(\(log⁡ℓT\)2\)\\Gamma\_\{T\}=O\(\(\\log\\ell\_\{T\}\)^\{2\}\), and1−βd,B≤1−αd=1/p1\-\\beta\_\{d,B\}\\leq 1\-\\alpha\_\{d\}=1/p,

B2​\(ΓT​b¯T\)1−βd,B≤Cd​ℓT,\(ΓT​b¯T\)1/\(p\+1\)​Bυd≤Cd​ℓTB^\{2\}\(\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\)^\{1\-\\beta\_\{d,B\}\}\\leq C\_\{d\}\\ell\_\{T\},\\qquad\(\\Gamma\_\{T\}\\bar\{b\}\_\{T\}\)^\{1/\(p\+1\)\}B^\{\\upsilon\_\{d\}\}\\leq C\_\{d\}\\ell\_\{T\}forT≥TdT\\geq T\_\{d\}\. Using1\+χ≤B​\(1∨W\)1\+\\chi\\leq B\(1\\vee W\)proves that the in\-memory construction is bounded by the right side of \([5](https://arxiv.org/html/2608.07922#S3.E5)\)\.

Large batch complexity\.SupposeB≥B0B\\geq B\_\{0\}and use Lemma[D\.2](https://arxiv.org/html/2608.07922#A4.Thmtheorem2)\. Define

ΞT=\(TℓT\)d/\(d\+2\),Ξχ=1\+χAdenv​ΓT\.\\Xi\_\{T\}=\\left\(\\frac\{T\}\{\\ell\_\{T\}\}\\right\)^\{d/\(d\+2\)\},\\qquad\\Xi\_\{\\chi\}=1\+\\frac\{\\chi\}\{A\_\{d\}^\{\\mathrm\{env\}\}\\Gamma\_\{T\}\}\.For the statistically saturated branch,

Td\+2d\+3​ℓT1/\(d\+3\)​ΞT−υd=Tαd​ℓT1/\(d\+2\)≤ℓT​Tαd\.T^\{\\frac\{d\+2\}\{d\+3\}\}\\ell\_\{T\}^\{1/\(d\+3\)\}\\Xi\_\{T\}^\{\-\\upsilon\_\{d\}\}=T^\{\\alpha\_\{d\}\}\\ell\_\{T\}^\{1/\(d\+2\)\}\\leq\\ell\_\{T\}T^\{\\alpha\_\{d\}\}\.For the boundary\-information branch,Ξχ≥cd​\(1\+χ\)/ΓT\\Xi\_\{\\chi\}\\geq c\_\{d\}\(1\+\\chi\)/\\Gamma\_\{T\}, hence

Td\+2d\+3​ℓT1/\(d\+3\)​Ξχ−υd\\displaystyle T^\{\\frac\{d\+2\}\{d\+3\}\}\\ell\_\{T\}^\{1/\(d\+3\)\}\\Xi\_\{\\chi\}^\{\-\\upsilon\_\{d\}\}≤Cd​Td\+2d\+3​\(1\+χ\)−υd​ℓT1/\(d\+3\)​ΓTυd\\displaystyle\\leq C\_\{d\}T^\{\\frac\{d\+2\}\{d\+3\}\}\(1\+\\chi\)^\{\-\\upsilon\_\{d\}\}\\ell\_\{T\}^\{1/\(d\+3\)\}\\Gamma\_\{T\}^\{\\upsilon\_\{d\}\}≤Cd​ℓT​Td\+2d\+3​\(1\+χ\)−υd\.\\displaystyle\\leq C\_\{d\}\\ell\_\{T\}T^\{\\frac\{d\+2\}\{d\+3\}\}\(1\+\\chi\)^\{\-\\upsilon\_\{d\}\}\.The serialized construction is therefore bounded by the right side of \([5](https://arxiv.org/html/2608.07922#S3.E5)\)\. Combining the three fixed regimes proves the claim\. ∎

## Appendix FProof of the batch\-complexity corollary

###### Proof of Corollary[3\.8](https://arxiv.org/html/2608.07922#S3.Thmtheorem8)\.

Putp=d\+2p=d\+2, chooseϱd\\varrho\_\{d\}larger than the constant in \([5](https://arxiv.org/html/2608.07922#S3.E5)\), and set

B\+:=T∧⌈Cd​\[log⁡log⁡T∨Td/pW\]⌉\.B\_\{\+\}:=T\\wedge\\left\\lceil C\_\{d\}\\left\[\\log\\log T\\ \\vee\\ \\frac\{T^\{d/p\}\}\{W\}\\right\]\\right\\rceil\.ForT≥TdT\\geq T\_\{d\}, the cap is inactive and, after increasingCdC\_\{d\},

\(B\+−1\)​W≥cd​Td/p,Tβd,B\+−αd=exp⁡\(αd​p−B\+1−p−B\+​log⁡T\)≤Cd\.\(B\_\{\+\}\-1\)W\\geq c\_\{d\}T^\{d/p\},\\qquad T^\{\\beta\_\{d,B\_\{\+\}\}\-\\alpha\_\{d\}\}=\\exp\\\!\\left\(\\frac\{\\alpha\_\{d\}p^\{\-B\_\{\+\}\}\}\{1\-p^\{\-B\_\{\+\}\}\}\\log T\\right\)\\leq C\_\{d\}\.Substitution into \([5](https://arxiv.org/html/2608.07922#S3.E5)\) givesℜT​\(B\+,W\)≤ϱd​ℓT​Tαd\\mathfrak\{R\}\_\{T\}\(B\_\{\+\},W\)\\leq\\varrho\_\{d\}\\ell\_\{T\}T^\{\\alpha\_\{d\}\}and therefore the upper bound in \([6](https://arxiv.org/html/2608.07922#S3.E6)\)\.

Conversely, supposeℜT​\(B,W\)≤ϱd​ℓT​Tαd\\mathfrak\{R\}\_\{T\}\(B,W\)\\leq\\varrho\_\{d\}\\ell\_\{T\}T^\{\\alpha\_\{d\}\}\. The memory floor in \([3](https://arxiv.org/html/2608.07922#S3.E3)\) and the lower bound \([4](https://arxiv.org/html/2608.07922#S3.E4)\) imply

1\+\(B−1\)​W≥cd​Td/\(d\+2\)​ℓT−d​\(d\+3\),B≥cd​Td/\(d\+2\)W​ℓTd​\(d\+3\)\.1\+\(B\-1\)W\\geq c\_\{d\}T^\{d/\(d\+2\)\}\\ell\_\{T\}^\{\-d\(d\+3\)\},\\qquad B\\geq c\_\{d\}\\frac\{T^\{d/\(d\+2\)\}\}\{W\\ell\_\{T\}^\{d\(d\+3\)\}\}\.The update\-depth branch also requiresB−2​euB≤Cd​ℓTB^\{\-2\}e^\{u\_\{B\}\}\\leq C\_\{d\}\\ell\_\{T\}, whereuB:=αd​p−B​log⁡T/\(1−p−B\)u\_\{B\}:=\\alpha\_\{d\}p^\{\-B\}\\log T/\(1\-p^\{\-B\}\)\. IfB≤cd​log⁡log⁡TB\\leq c\_\{d\}\\log\\log T, thenp−B≥\(log⁡T\)−1/2p^\{\-B\}\\geq\(\\log T\)^\{\-1/2\}, souB≥cd​log⁡Tu\_\{B\}\\geq c\_\{d\}\\sqrt\{\\log T\}and the requirement fails\. HenceB≥cd​log⁡log⁡TB\\geq c\_\{d\}\\log\\log T\. Combining the two necessary conditions proves \([6](https://arxiv.org/html/2608.07922#S3.E6)\); \([7](https://arxiv.org/html/2608.07922#S3.E7)\) follows after suppressing powers ofℓT\\ell\_\{T\}\. ∎