Multiscale Reward Hedging from Correct Demonstrations

# Multiscale Reward Hedging from Correct Demonstrations
Source: [https://arxiv.org/html/2608.06825](https://arxiv.org/html/2608.06825)
###### Abstract

Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward\. Existing reward\-hedging guarantees consequently assume a finite reward class\. We give the first horizon\-free guarantee for continuous classes\. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale\. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy\. This yields the simultaneous tail bound

\|\{t:ℓt\>2−j\}\|≤log2⁡𝒩​\(𝒢,2−j−1\)\+j,\|\\\{t:\\ell\_\{t\}\>2^\{\-j\}\\\}\|\\leq\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\-1\}\)\+j,where𝒢\\mathcal\{G\}is the class of optimality\-gap functions\. Integrating the tails gives cumulative hidden gap bounded by a metric\-entropy integral, independently of the number of rounds\. Polynomial entropy\(A/ϵ\)d\(A/\\epsilon\)^\{d\}givesO​\(d​log⁡A\)O\(d\\log A\)total gap and a fastO​\(d/m\)O\(d/m\)statistical rate\. For bounded linear contextual recommendation, the result isO​\(d\)O\(d\)regret for arbitrary compact menus\. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction\. Although the general vote can be expensive, it is exactly polynomial\-time for one\-dimensional Lipschitz parameter curves\. Fixed\-radius rank\-two recommendation takesO​\(K​T2\)O\(KT^\{2\}\)time for menus of sizeKK\. We also prove anΩ​\(d\)\\Omega\(d\)lower bound, low\-rank and bounded ReLU\-network corollaries, and a robust theorem that adds only the demonstrator’s cumulative suboptimality\. A reproducible adaptive stress test illustrates the predicted scale adaptation\. After factorization, an exact MovieLens audit runs in 1\.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated\-rating policy and a proper online baseline\. The learner uses only action demonstrations and never observes a reward or a loss\.

## 1Introduction

A question can have many correct answers\. A recommendation menu can have several optimal items\. An expert demonstration reveals one of them, but it does not reveal the reward function, the full set of good answers, or whether a learner’s different answer was also good\. This is the feedback pattern of supervised fine\-tuning when utility, rather than cloning one demonstrator’s distribution, is the objective\. It is also the one\-step form of apprenticeship learning\(Abbeel and Ng,[2004](https://arxiv.org/html/2608.06825#bib.bib19); Syed and Schapire,[2007](https://arxiv.org/html/2608.06825#bib.bib18)\)\.

Joshiet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib1)\)formalized this problem as learning to answer from correct demonstrations\. For a finite reward classℛ\\mathcal\{R\}, their reward\-hedging rule achievesO​\(log⁡\|ℛ\|\)O\(\\log\|\\mathcal\{R\}\|\)cumulative gap against an optimal demonstrator and a correspondingO​\(log⁡\|ℛ\|/m\)O\(\\log\|\\mathcal\{R\}\|/m\)statistical rate\. Their main open question asks for continuous reward classes, naming generalized linear rewards, low\-rank bilinear scores, and neural rewards as motivating examples\. Applying a single fine discretization does not answer the question\. Anϵ\\epsilon\-cover gives the familiar tradeoffT​ϵ\+log⁡𝒩​\(ϵ\)T\\epsilon\+\\log\\mathcal\{N\}\(\\epsilon\), which isΘ​\(d​log⁡T\)\\Theta\(d\\log T\)for add\-parameter class\.

The same barrier appears independently in contextual recommendation\. Proper algorithms progressed fromO​\(T\)O\(\\sqrt\{T\}\)regret\(Bärmannet al\.,[2017](https://arxiv.org/html/2608.06825#bib.bib2)\)to polynomial\-timeO​\(d4​log⁡T\)O\(d^\{4\}\\log T\)regret\(Besbeset al\.,[2025](https://arxiv.org/html/2608.06825#bib.bib3)\)\. More recent work sharpens the dimension dependence\. Here a learner sees a menuXt⊂ℝdX\_\{t\}\\subset\\mathbb\{R\}^\{d\}, recommendsx^t\\hat\{x\}\_\{t\}, and then observes a user’s optimal choicext∗x\_\{t\}^\{\*\}for an unknown linear utility\. The best general bounds have beenO​\(d​log⁡T\)O\(d\\log T\)orexp⁡\(O​\(d​log⁡d\)\)\\exp\(O\(d\\log d\)\)\(Gollapudiet al\.,[2021](https://arxiv.org/html/2608.06825#bib.bib14); Sakaueet al\.,[2025](https://arxiv.org/html/2608.06825#bib.bib15)\)\. A 2026 result obtains finiteO​\(d​log⁡d\)O\(d\\log d\)regret for M\-convex menus and identifies a general polynomial finite bound as open\(Oki and Sakaue,[2026](https://arxiv.org/html/2608.06825#bib.bib16)\)\. We resolve the menu\-aware, improper version of this question withO​\(d\)O\(d\)regret for arbitrary bounded menus\.

Our algorithm starts from a simple observation\. At accuracyϵ\\epsilon, every reward\-gap modelggdefines a binary proxy that calls an action good wheng​\(x,a\)≤ϵg\(x,a\)\\leq\\epsilon\. A cover element withinϵ\\epsilonof the target always calls an optimal demonstration good\. If it also calls the learner’s action good, that action has target gap at most2​ϵ2\\epsilon\. Thus every larger\-gap round can multiply the proxy’s weight\. Running this argument separately at each scale would produce incompatible actions\. Instead, we put all proxies at all scales into one weighted vote, with scale prior2−j2^\{\-j\}\. One potential controls the whole hierarchy\. The resulting mistake bound holds at every threshold simultaneously, and layer\-cake integration converts it into a finite entropy sum\.

Our contributions are:

- •We introduce a deterministic multiscale reward\-hedging algorithm for continuous reward classes\. For the decision\-relevant gap metric, its total unobserved loss is at most ∑j≥12−j​log2⁡𝒩​\(𝒢,2−j−1\)\+2\.\\sum\_\{j\\geq 1\}2^\{\-j\}\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\-1\}\)\+2\.\(1\)The guarantee is adversarial, horizon\-free, and invariant to context\-dependent reward offsets\. A finite version uses only⌈log2⁡T⌉\\lceil\\log\_\{2\}T\\rceilscales and loses at most one more\.
- •If the normalized gap class has covering numbers at most\(A/ϵ\)d\(A/\\epsilon\)^\{d\}, the bound isd​\(log2⁡A\+3\)\+2d\(\\log\_\{2\}A\+3\)\+2\. Bounded linear contextual recommendation therefore hasO​\(B​K​d\)O\(BKd\)regret when parameters have radiusBBand each menu has diameterKK\. Low\-rankm×nm\\times nbilinear rewards haveO​\(B​K​r​\(m\+n\)\)O\(BKr\(m\+n\)\)regret\. For app\-parameter depth\-LLbounded ReLU reward network, we obtain an explicitO​\(G​p​\[1\+log⁡\(1\+B​R​SL−1​L/G\)\]\)O\(Gp\[1\+\\log\(1\+BRS^\{L\-1\}\\sqrt\{L\}/G\)\]\)bound\.
- •The finite algorithm is exact and polynomial\-time when the gap functions follow a one\-dimensional Lipschitz curve\. It usesO​\(T\)O\(T\)proxies,O​\(K​T2\)O\(KT^\{2\}\)total time, andO​\(T\)O\(T\)memory for fixed geometric constants\. This includes fixed\-radius rank\-two recommendation with arbitrary finite menus\.
- •We prove a matchingΩ​\(d\)\\Omega\(d\)lower bound for a continuous class with entropy exponentdd\. Under i\.i\.d\. contexts, online\-to\-batch conversion gives population gapO​\(\(d\+log⁡\(1/δ\)\)/m\)O\(\(d\+\\log\(1/\\delta\)\)/m\)with high probability\.
- •A soft multiscale update handles suboptimal demonstrations\. If their cumulative target gap isΔT\\Delta\_\{T\}, the learner incursO​\(ΔT\+d\)O\(\\Delta\_\{T\}\+d\)for polynomial\-entropy classes\. No reward or correctness bit is observed in either algorithm\. A finite stress test verifies the scale\-adaptive behavior\. A second deterministic audit uses actual MovieLens ratings as suboptimal demonstrations for ten rank\-two preference circles\.

The general\-dimensional result is information\-theoretic\. Cover enumeration can be expensive and the action predictor is improper\. Section[5\.1](https://arxiv.org/html/2608.06825#S5.SS1)isolates a nontrivial case where the same exact algorithm is polynomial\-time\. Proper objective estimation remains distinct\(Sakaueet al\.,[2025](https://arxiv.org/html/2608.06825#bib.bib15); Sakaue,[2026](https://arxiv.org/html/2608.06825#bib.bib17)\)\.

## 2Problem and closest work

Let𝒳\\mathcal\{X\}be a context space and let𝒜​\(x\)\\mathcal\{A\}\(x\)be the nonempty action menu atxx\. A rewardr∈ℛr\\in\\mathcal\{R\}assigns values to context\-action pairs\. Its decision\-relevant object is the*optimality\-gap function*

gr​\(x,a\)=supb∈𝒜​\(x\)r​\(x,b\)−r​\(x,a\)\.g\_\{r\}\(x,a\)=\\sup\_\{b\\in\\mathcal\{A\}\(x\)\}r\(x,b\)\-r\(x,a\)\.\(2\)We first normalize sogr∈\[0,1\]g\_\{r\}\\in\[0,1\], and restore scale in applications\. Write𝒢=\{gr:r∈ℛ\}\\mathcal\{G\}=\\\{g\_\{r\}:r\\in\\mathcal\{R\}\\\}and equip it with

dgap​\(r,s\)=‖gr−gs‖∞\.d\_\{\\operatorname\{gap\}\}\(r,s\)=\\\|g\_\{r\}\-g\_\{s\}\\\|\_\{\\infty\}\.This pseudometric ignores arbitrary context\-dependent reward offsets\. It is also no larger than2​‖r−s‖∞2\\\|r\-s\\\|\_\{\\infty\}, so ordinary reward covers remain valid\.

The gap metric can be much sharper than the reward sup metric\. For example, ifrθ​\(x,a\)=uθ​\(x\)\+v​\(x,a\)r\_\{\\theta\}\(x,a\)=u\_\{\\theta\}\(x\)\+v\(x,a\)with an arbitrarily rich class of context offsetsuθu\_\{\\theta\}, then every member has the same gap function\. Its decision\-relevant covering number is one even when the raw reward class is not totally bounded\. This quotient geometry is necessary for utility claims, since demonstrations cannot identify an offset that changes no decision\.

On roundtt, the learner receivesxtx\_\{t\}, predictsa^t∈𝒜​\(xt\)\\hat\{a\}\_\{t\}\\in\\mathcal\{A\}\(x\_\{t\}\), then observes one demonstrationat∗a\_\{t\}^\{\*\}\. There is a fixed unknownr∗∈ℛr\_\{\*\}\\in\\mathcal\{R\}\. In the realizable case,gr∗​\(xt,at∗\)=0g\_\{r\_\{\*\}\}\(x\_\{t\},a\_\{t\}^\{\*\}\)=0, but the learner does not observe this value or its own loss

ℓt=gr∗​\(xt,a^t\)\.\\ell\_\{t\}=g\_\{r\_\{\*\}\}\(x\_\{t\},\\hat\{a\}\_\{t\}\)\.\(3\)Contexts and the choice among optimal demonstrations may be adaptive\. Let𝒩​\(𝒢,ϵ\)\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)denote the minimum cardinality of a properϵ\\epsilon\-cover under the sup metric, and assume these covering numbers are finite\.

#### Closest feedback models\.

The finite\-class rule ofJoshiet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib1)\)is the direct starting point\. A countable\-class extension assigns a summable prior and obtains a target\-specificlog⁡\(1/w0\)\\log\(1/w\_\{0\}\)bound\(Kleinberget al\.,[2026](https://arxiv.org/html/2608.06825#bib.bib6)\)\. It cannot assign positive mass to every member of an uncountable class\.Shaoet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib8)\)characterize 0–1 learning when only one member of a hidden acceptable set is shown, using partial\-feedback Littlestone dimensions over collections of policy hypotheses\. Their result does not control real\-valued reward gap or connect reward\-parameter entropy to regret\. In the same 0–1 setting,Pouret al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib9)\)give exact tree\-dimension characterizations for mistake\-unknown, mistake\-known, and set\-valued feedback, including infinite multi\-label classes\. Their tree dimensions do not grade reward gap or connect parameter entropy\.Ramanet al\.\([2024](https://arxiv.org/html/2608.06825#bib.bib10)\)reveal the entire acceptable set\.Cohenet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib7)\)instead predict sets and receive sampled precision or recall membership bits, rather than one demonstrated action with hidden correctness\.

#### Closest multiscale result\.

Attiaset al\.\([2023](https://arxiv.org/html/2608.06825#bib.bib4)\)characterize minimax realizable online regression by a scaled\-Littlestone dimension\. Building on that characterization,Doron\-Aradet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib11)\)bound the dimension by a Dudley\-type entropy potential\. Both protocols reveal the exact numeric label after every prediction\. In our protocol, the numeric target gap and even the correctness of the prediction stay hidden\. Our entropy shape is related, but the tolerant\-proxy reduction and its one\-vote potential are specific to action\-only feedback\.

#### Online inverse optimization\.

Bärmannet al\.\([2017](https://arxiv.org/html/2608.06825#bib.bib2)\)give a proper exponential\-weights learner withO​\(T\)O\(\\sqrt\{T\}\)regret over arbitrary optimization\-oracle menus\.Besbeset al\.\([2025](https://arxiv.org/html/2608.06825#bib.bib3)\)introduce inverse exploration and a polynomial\-time ellipsoidal\-cone method withO​\(d4​log⁡T\)O\(d^\{4\}\\log T\)general regret\. The line culminating inO​\(d​log⁡T\)O\(d\\log T\)and structured finite bounds is summarized in Table[1](https://arxiv.org/html/2608.06825#S2.T1)\. Our generalO​\(d\)O\(d\)result is improper and expensive, while Section[5\.1](https://arxiv.org/html/2608.06825#S5.SS1)gives an exact polynomial\-time slice when the intrinsic parameter dimension is one\.

Two concurrent preprints clarify complementary frontiers\.Jimenezet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib12)\)give polynomial\-time mistake\-bounded generators for conjunctions, parities, and monotone Boolean functions with polynomially many maxterms\. Their discrete language\-generation algorithms do not address real\-valued gap entropy\. Their positive results underscore the importance of finding efficient special cases of our vote\.Fatemiet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib13)\)prove tightO​\(d/T\)O\(d/T\)mismatch andO​\(d​log⁡T\)O\(d\\log T\)cumulative regret for noiseless inverse optimization under i\.i\.d\. contexts, using proper consistency or incenter estimators\. Our objective is different: total target reward gap under adversarial menus, without estimating a reward parameter\. Their convex estimators and experiments provide a useful computational counterpart to our information\-theoretic result\.

Table 1:Cumulative hidden reward gap\. Our general bound permits arbitrary bounded menus but is improper and can be inefficient\. Its rank\-two fixed\-radius slice is exact and polynomial\-time\.

## 3One vote across all scales

Forj≥1j\\geq 1, set

ϵj=2−j−1,θj=2−j,αj=2−j\.\\epsilon\_\{j\}=2^\{\-j\-1\},\\qquad\\theta\_\{j\}=2^\{\-j\},\\qquad\\alpha\_\{j\}=2^\{\-j\}\.Choose a properϵj\\epsilon\_\{j\}\-coverCj⊂𝒢C\_\{j\}\\subset\\mathcal\{G\}\. Everyh∈Cjh\\in C\_\{j\}induces the tolerant binary proxy

qj,h​\(x,a\)=𝟏​\{h​\(x,a\)≤ϵj\}\.q\_\{j,h\}\(x,a\)=\\mathbf\{1\}\\\{h\(x,a\)\\leq\\epsilon\_\{j\}\\\}\.\(4\)Initializew1​\(j,h\)=αj/\|Cj\|w\_\{1\}\(j,h\)=\\alpha\_\{j\}/\|C\_\{j\}\|, so the total initial weight is one\. At roundtt, predict an action maximizing the shared vote

a^t∈arg⁡maxa∈𝒜​\(xt\)⁡St​\(a\),St​\(a\)=∑j≥1∑h∈Cjwt​\(j,h\)​qj,h​\(xt,a\)\.\\hat\{a\}\_\{t\}\\in\\arg\\max\_\{a\\in\\mathcal\{A\}\(x\_\{t\}\)\}S\_\{t\}\(a\),\\qquad S\_\{t\}\(a\)=\\sum\_\{j\\geq 1\}\\sum\_\{h\\in C\_\{j\}\}w\_\{t\}\(j,h\)q\_\{j,h\}\(x\_\{t\},a\)\.\(5\)After observingat∗a\_\{t\}^\{\*\}, update each proxy by

wt\+1​\(j,h\)=\{0,qj,h​\(xt,at∗\)=0,2​wt​\(j,h\),qj,h​\(xt,at∗\)=1,qj,h​\(xt,a^t\)=0,wt​\(j,h\),otherwise\.w\_\{t\+1\}\(j,h\)=\\begin\{cases\}0,&q\_\{j,h\}\(x\_\{t\},a\_\{t\}^\{\*\}\)=0,\\\\ 2w\_\{t\}\(j,h\),&q\_\{j,h\}\(x\_\{t\},a\_\{t\}^\{\*\}\)=1,\\ q\_\{j,h\}\(x\_\{t\},\\hat\{a\}\_\{t\}\)=0,\\\\ w\_\{t\}\(j,h\),&\\text\{otherwise\}\.\\end\{cases\}\(6\)For finite menus, the maximum exists\. Section[B](https://arxiv.org/html/2608.06825#A2)gives two alternatives: a finite hierarchy for a known horizon, and summably approximate maximization for arbitrary menus\.

The update is “mistake unaware\.” It never usesℓt\\ell\_\{t\}or checks whethera^t\\hat\{a\}\_\{t\}is good\. It only compares each known proxy’s two binary judgments\. Importantly, the vote is global\. Running one learner per scale and choosing among their actions would not give the potential below\.

#### Why one discretization stalls\.

At a single toleranceϵ\\epsilon, the same argument gives at mostlog2⁡𝒩​\(𝒢,ϵ\)\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)rounds with gap above2​ϵ2\\epsilon\. Bounding every other round by2​ϵ2\\epsilonyields

∑t≤Tℓt≤log2⁡𝒩​\(𝒢,ϵ\)\+2​T​ϵ\.\\sum\_\{t\\leq T\}\\ell\_\{t\}\\leq\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)\+2T\\epsilon\.For polynomial entropy, optimizingϵ\\epsilonleaves aΘ​\(d​log⁡T\)\\Theta\(d\\log T\)term\. The shared vote does not select one resolution\. It pays each scale’s complexity only on the loss interval represented by that scale\.

###### Lemma 1\(Shared potential\)\.

The total proxy weightWt=∑j,hwt​\(j,h\)W\_\{t\}=\\sum\_\{j,h\}w\_\{t\}\(j,h\)never increases\.

###### Proof\.

Partition current weight according to the pair\(q​\(xt,at∗\),q​\(xt,a^t\)\)∈\{0,1\}2\(q\(x\_\{t\},a\_\{t\}^\{\*\}\),q\(x\_\{t\},\\hat\{a\}\_\{t\}\)\)\\in\\\{0,1\\\}^\{2\}, and call the four partsW00,W01,W10,W11W\_\{00\},W\_\{01\},W\_\{10\},W\_\{11\}\. Vote maximality against the demonstrated action givesW01\+W11≥W10\+W11W\_\{01\}\+W\_\{11\}\\geq W\_\{10\}\+W\_\{11\}, henceW10≤W01W\_\{10\}\\leq W\_\{01\}\. The update changes total weight byW10−W01−W00≤0W\_\{10\}\-W\_\{01\}\-W\_\{00\}\\leq 0\. ∎

###### Lemma 2\(One surviving witness per scale\)\.

Fixjjand choosehj∈Cjh\_\{j\}\\in C\_\{j\}with‖hj−gr∗‖∞≤ϵj\\\|h\_\{j\}\-g\_\{r\_\{\*\}\}\\\|\_\{\\infty\}\\leq\\epsilon\_\{j\}\. This proxy is never deleted\. Wheneverℓt\>θj\\ell\_\{t\}\>\\theta\_\{j\}, its weight doubles\.

###### Proof\.

Optimality of the demonstration givesgr∗​\(xt,at∗\)=0g\_\{r\_\{\*\}\}\(x\_\{t\},a\_\{t\}^\{\*\}\)=0, sohj​\(xt,at∗\)≤ϵjh\_\{j\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\\leq\\epsilon\_\{j\}and its proxy calls the demonstration good\. If the proxy also callsa^t\\hat\{a\}\_\{t\}good, then

ℓt≤hj​\(xt,a^t\)\+ϵj≤2​ϵj=θj\.\\ell\_\{t\}\\leq h\_\{j\}\(x\_\{t\},\\hat\{a\}\_\{t\}\)\+\\epsilon\_\{j\}\\leq 2\\epsilon\_\{j\}=\\theta\_\{j\}\.The contrapositive gives the doubling claim\. ∎

## 4Horizon\-free entropy bounds

LetMT​\(u\)=\|\{t≤T:ℓt\>u\}\|M\_\{T\}\(u\)=\|\\\{t\\leq T:\\ell\_\{t\}\>u\\\}\|\.

###### Theorem 3\(Multiscale demonstration bound\)\.

For every realizable adaptive sequence and everyT,j≥1T,j\\geq 1, the algorithm satisfies

MT​\(2−j\)≤log2⁡𝒩​\(𝒢,2−j−1\)\+j\.M\_\{T\}\(2^\{\-j\}\)\\leq\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\-1\}\)\+j\.\(7\)Consequently,

∑t=1Tℓt≤∑j≥12−j​log2⁡𝒩​\(𝒢,2−j−1\)⏟ℌdyad​\(𝒢\)\+2\.\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\\leq\\underbrace\{\\sum\_\{j\\geq 1\}2^\{\-j\}\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\-1\}\)\}\_\{\\mathfrak\{H\}\_\{\\rm dyad\}\(\\mathcal\{G\}\)\}\+2\.\(8\)Moreover,

ℌdyad​\(𝒢\)≤4​∫01/4log2⁡𝒩​\(𝒢,ϵ\)​𝑑ϵ\.\\mathfrak\{H\}\_\{\\rm dyad\}\(\\mathcal\{G\}\)\\leq 4\\int\_\{0\}^\{1/4\}\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)\\,d\\epsilon\.\(9\)

###### Proof\.

The witness at scalejjstarts with weight2−j/\|Cj\|2^\{\-j\}/\|C\_\{j\}\|\. Lemmas[1](https://arxiv.org/html/2608.06825#Thmtheorem1)and[2](https://arxiv.org/html/2608.06825#Thmtheorem2)give

2−j\|Cj\|​2MT​\(2−j\)≤wT\+1​\(j,hj\)≤WT\+1≤1,\\frac\{2^\{\-j\}\}\{\|C\_\{j\}\|\}2^\{M\_\{T\}\(2^\{\-j\}\)\}\\leq w\_\{T\+1\}\(j,h\_\{j\}\)\\leq W\_\{T\+1\}\\leq 1,which proves \([7](https://arxiv.org/html/2608.06825#S4.E7)\)\. Sinceℓt∈\[0,1\]\\ell\_\{t\}\\in\[0,1\], layer cake gives∑tℓt=∫01MT​\(u\)​𝑑u\\sum\_\{t\}\\ell\_\{t\}=\\int\_\{0\}^\{1\}M\_\{T\}\(u\)du\. Onu∈\(2−j,2−j\+1\]u\\in\(2^\{\-j\},2^\{\-j\+1\}\], monotonicity givesMT​\(u\)≤MT​\(2−j\)M\_\{T\}\(u\)\\leq M\_\{T\}\(2^\{\-j\}\)\. The interval has width2−j2^\{\-j\}\. Summing \([7](https://arxiv.org/html/2608.06825#S4.E7)\) over these intervals proves \([8](https://arxiv.org/html/2608.06825#S4.E8)\), using∑j≥1j​2−j=2\\sum\_\{j\\geq 1\}j2^\{\-j\}=2\. Finally, monotonicity of covering numbers gives

2−j​log2⁡𝒩​\(𝒢,2−j−1\)≤4​∫2−j−22−j−1log2⁡𝒩​\(𝒢,ϵ\)​𝑑ϵ\.2^\{\-j\}\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\-1\}\)\\leq 4\\int\_\{2^\{\-j\-2\}\}^\{2^\{\-j\-1\}\}\\log\_\{2\}\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)d\\epsilon\.The intervals partition\(0,1/4\]\(0,1/4\], proving \([9](https://arxiv.org/html/2608.06825#S4.E9)\)\. ∎

The dyadic bound is primary\. Unlike a single discretization, no term proportional toT​ϵT\\epsilonremains\. The integral form makes its effective\-dimension content transparent\.

###### Corollary 4\(Polynomial entropy\)\.

If𝒩​\(𝒢,ϵ\)≤\(A/ϵ\)d\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)\\leq\(A/\\epsilon\)^\{d\}for allϵ≤1/4\\epsilon\\leq 1/4, withA≥1A\\geq 1, then

∑t=1Tℓt≤d​\(log2⁡A\+3\)\+2\.\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\\leq d\(\\log\_\{2\}A\+3\)\+2\.\(10\)

###### Proof\.

At scalejj, the logarithm in \([8](https://arxiv.org/html/2608.06825#S4.E8)\) is at mostd​\(log2⁡A\+j\+1\)d\(\\log\_\{2\}A\+j\+1\)\. Use∑j2−j=1\\sum\_\{j\}2^\{\-j\}=1and∑jj​2−j=2\\sum\_\{j\}j2^\{\-j\}=2\. ∎

This dependence cannot be improved in general\.

###### Theorem 5\(Dimension lower bound\)\.

For everydd, there is a continuous reward class withlog⁡𝒩​\(𝒢,ϵ\)=Θ​\(d​log⁡\(1/ϵ\)\)\\log\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)=\\Theta\(d\\log\(1/\\epsilon\)\)for which every randomized learner has worst\-case expected cumulative gap at leastd/2d/2\.

###### Construction\.

Let𝒳=\[d\]\\mathcal\{X\}=\[d\],𝒜=\{−1,\+1\}\\mathcal\{A\}=\\\{\-1,\+1\\\},w∈\[−1,1\]dw\\in\[\-1,1\]^\{d\}, andrw​\(i,a\)=\(1\+a​wi\)/2r\_\{w\}\(i,a\)=\(1\+aw\_\{i\}\)/2\. Drawwwuniformly from\{−1,\+1\}d\\\{\-1,\+1\\\}^\{d\}and present contexts1,…,d1,\\ldots,d\. Before the first demonstration at contextii, the transcript is independent ofwiw\_\{i\}\. Every prediction is wrong with probability1/21/2, and a wrong action has unit gap\. Yao’s principle\(Yao,[1977](https://arxiv.org/html/2608.06825#bib.bib20)\)proves the lower bound\. On the positive subcube, the gap metric equals theℓ∞\\ell\_\{\\infty\}parameter metric, which gives the entropy claim\. Full details are in Appendix[E](https://arxiv.org/html/2608.06825#A5)\. ∎

## 5Continuous reward classes

We state results at their natural gap scale\. If0≤gr≤G0\\leq g\_\{r\}\\leq G, apply the preceding theorem togr/Gg\_\{r\}/Gand multiply the bound byGG\.

###### Corollary 6\(Linear contextual recommendation\)\.

Letrw​\(x,a\)=⟨w,ϕ​\(x,a\)⟩r\_\{w\}\(x,a\)=\\left\\langle w,\\phi\(x,a\)\\right\\rangle, with‖w‖2≤B\\\|w\\\|\_\{2\}\\leq B, and suppose each feature menu has Euclidean diameter at mostKK\. There is a deterministic menu\-aware action predictor with

∑t=1T\[maxa∈𝒜​\(xt\)⁡⟨w∗,ϕ​\(xt,a\)⟩−⟨w∗,ϕ​\(xt,a^t\)⟩\]≤B​K​\{d​\(log2⁡3\+3\)\+3\}\.\\sum\_\{t=1\}^\{T\}\\left\[\\max\_\{a\\in\\mathcal\{A\}\(x\_\{t\}\)\}\\left\\langle w\_\{\*\},\\phi\(x\_\{t\},a\)\\right\\rangle\-\\left\\langle w\_\{\*\},\\phi\(x\_\{t\},\\hat\{a\}\_\{t\}\)\\right\\rangle\\right\]\\leq BK\\\{d\(\\log\_\{2\}3\+3\)\+3\\\}\.\(11\)The bound holds for arbitrary compact feature menus\. For finite menus, the final additive constant in \([11](https://arxiv.org/html/2608.06825#S5.E11)\) improves from three to two\.

###### Proof\.

The gap range is at mostB​KBK\. Rewriting the gap as a maximum of⟨w,ϕ​\(x,b\)−ϕ​\(x,a\)⟩\\left\\langle w,\\phi\(x,b\)\-\\phi\(x,a\)\\right\\ranglegives

‖gw−gv‖∞≤K​‖w−v‖2\.\\\|g\_\{w\}\-g\_\{v\}\\\|\_\{\\infty\}\\leq K\\\|w\-v\\\|\_\{2\}\.After normalizing byB​KBK, anϵ​B\\epsilon B\-cover of the parameter ball is enough\. The volumetric bound is\(1\+2/ϵ\)d≤\(3/ϵ\)d\(1\+2/\\epsilon\)^\{d\}\\leq\(3/\\epsilon\)^\{d\}forϵ≤1\\epsilon\\leq 1\. The finite compact\-menu implementation in Appendix[B](https://arxiv.org/html/2608.06825#A2)adds one to Corollary[4](https://arxiv.org/html/2608.06825#Thmtheorem4)\. ∎

In the standard normalizationB=1B=1and𝒜​\(x\)⊆\{a:‖a‖2≤1\}\\mathcal\{A\}\(x\)\\subseteq\\\{a:\\\|a\\\|\_\{2\}\\leq 1\\\}, one hasK≤2K\\leq 2, givingO​\(d\)O\(d\)regret\. This improves both general bounds in Table[1](https://arxiv.org/html/2608.06825#S2.T1)and answers the polynomial finite\-regret question for the original menu\-aware recommendation protocol\. The distinction from proper online inverse optimization is important\. Our vote need not be maximized by any singleww, while proper methods output an objective estimate and take its optimal action\(Sakaueet al\.,[2025](https://arxiv.org/html/2608.06825#bib.bib15); Oki and Sakaue,[2026](https://arxiv.org/html/2608.06825#bib.bib16)\)\. We do not improve their computational guarantees\.

### 5\.1An exact polynomial\-time slice

The exponential dependence above is not unavoidable\. It disappears when the gap class has one\-dimensional intrinsic geometry\.

###### Proposition 7\(Exact runtime on a Lipschitz curve\)\.

Suppose every normalized gap function isgsg\_\{s\}for somes∈\[0,Q\]s\\in\[0,Q\]and‖gs−gs′‖∞≤L​\|s−s′\|\\\|g\_\{s\}\-g\_\{s^\{\\prime\}\}\\\|\_\{\\infty\}\\leq L\|s\-s^\{\\prime\}\|\. Assume finite menus of size at mostkkand reward evaluation costCC, withT≥2T\\geq 2\. The known\-horizon hard algorithm is exact, uses at most

PT≤⌈log2⁡T⌉\+8​L​Q​TP\_\{T\}\\leq\\lceil\\log\_\{2\}T\\rceil\+8LQT\(12\)proxies, and takesO​\(k​C​T​PT\)O\(kCTP\_\{T\}\)total time andO​\(PT\+k\)O\(P\_\{T\}\+k\)memory\. The robust algorithm has the same guarantees with88replaced by1212\.

###### Proof\.

Partitioning\[0,Q\]\[0,Q\]into equal subintervals and taking their midpoints gives a properϵ\\epsilon\-cover of size at most1\+L​Q/ϵ1\+LQ/\\epsilon\. For the hard hierarchy, summing atϵj=2−j−1\\epsilon\_\{j\}=2^\{\-j\-1\}overj≤J=⌈log2⁡T⌉j\\leq J=\\lceil\\log\_\{2\}T\\rceilgivesPT≤J\+L​Q​\(2J\+2−4\)≤J\+8​L​Q​TP\_\{T\}\\leq J\+LQ\(2^\{J\+2\}\-4\)\\leq J\+8LQT\. At each round, evaluating allkkrewards for one proxy gives its gaps and tolerant set inO​\(k​C\)O\(kC\)time\. Streaming over proxies computes all votes and updates\. The robust cover radius2−j/32^\{\-j\}/3givesJ\+12​L​Q​TJ\+12LQTproxies\. ∎

###### Corollary 8\(Efficient fixed\-radius rank\-two recommendation\)\.

Letrϑ​\(x,a\)=b​\(x,a\)\+⟨B​\(cos⁡ϑ,sin⁡ϑ\),ϕ​\(x,a\)⟩r\_\{\\vartheta\}\(x,a\)=b\(x,a\)\+\\left\\langle B\(\\cos\\vartheta,\\sin\\vartheta\),\\phi\(x,a\)\\right\\rangle, whereϑ∈\[0,2​π\]\\vartheta\\in\[0,2\\pi\], feature\-menu diameter is at mostDD, menu cardinality is at mostkk, and all gaps are at mostG\>0G\>0\. The exact finite algorithm has cumulative gap at most

G​\{log2⁡\(1\+2​π​B​DG\)\+6\}G\\left\\\{\\log\_\{2\}\\left\(1\+\\frac\{2\\pi BD\}\{G\}\\right\)\+6\\right\\\}\(13\)and total timeO​\(k​C​\[1\+B​D/G\]​T2\)O\(kC\[1\+BD/G\]T^\{2\}\)\. The robust version is also exact and polynomial\-time, with cumulative gapOγ​\(ΔT\+G​\[1\+log⁡\(1\+B​D/G\)\]\)O\_\{\\gamma\}\(\\Delta\_\{T\}\+G\[1\+\\log\(1\+BD/G\)\]\)\.

Indeed, changing the angle byuuchanges the normalized gap by at most\(B​D/G\)​\|u\|\(BD/G\)\|u\|\. Thus Proposition[7](https://arxiv.org/html/2608.06825#Thmtheorem7)applies withQ=2​πQ=2\\pi, while the circle has normalized covering number at most\(1\+2​π​B​D/G\)/ϵ\(1\+2\\pi BD/G\)/\\epsilon\. Corollary[4](https://arxiv.org/html/2608.06825#Thmtheorem4)and the one\-unit finite\-hierarchy truncation prove \([13](https://arxiv.org/html/2608.06825#S5.E13)\)\. The menus remain arbitrary\. The vote is still potentially improper, but it is enumerated exactly rather than approximated by a surrogate\.

###### Corollary 9\(Low\-rank bilinear rewards\)\.

LetrW​\(x,a\)=⟨W,Φ​\(x,a\)⟩Fr\_\{W\}\(x,a\)=\\left\\langle W,\\Phi\(x,a\)\\right\\rangle\_\{F\}form×nm\\times nmatrices withrank⁡\(W\)≤r\\operatorname\{rank\}\(W\)\\leq rand‖W‖F≤B\\\|W\\\|\_\{F\}\\leq B\. If every feature menu has Frobenius diameter at mostKK, then cumulative gap isO​\(B​K​r​\(m\+n\)\)O\(BKr\(m\+n\)\)\.

The proof uses the standard\(C/ϵ\)\(m\+n\+1\)​r\(C/\\epsilon\)^\{\(m\+n\+1\)r\}cover of the rank\-rrFrobenius ball and appears in Appendix[D](https://arxiv.org/html/2608.06825#A4)\. The same calculation givesO​\(G​p​log⁡\(1\+L\)\)O\(Gp\\log\(1\+L\)\)for a boundedpp\-parameter class whose normalized gap map has parameter Lipschitz constantLL\.

###### Corollary 10\(Generalized linear rewards\)\.

Letrw​\(x,a\)=σ​\(⟨w,ϕ​\(x,a\)⟩\)∈\[0,G\]r\_\{w\}\(x,a\)=\\sigma\(\\left\\langle w,\\phi\(x,a\)\\right\\rangle\)\\in\[0,G\], where‖w‖2≤B\\\|w\\\|\_\{2\}\\leq B,‖ϕ​\(x,a\)‖2≤R\\\|\\phi\(x,a\)\\\|\_\{2\}\\leq R, andσ\\sigmaisLL\-Lipschitz\. Then cumulative gap is

O​\(G​d​\[1\+log⁡\(1\+B​L​RG\)\]\)\.O\\left\(Gd\\left\[1\+\\log\\left\(1\+\\frac\{BLR\}\{G\}\\right\)\\right\]\\right\)\.

Changingwwtovvchanges the optimal value and the chosen action’s value by at mostL​R​‖w−v‖2LR\\\|w\-v\\\|\_\{2\}each\. Thus the gap map is2​L​R2LR\-Lipschitz, and the generic parameter\-cover calculation in Appendix[D](https://arxiv.org/html/2608.06825#A4)applies\. This covers another continuous family posed byJoshiet al\.\([2026](https://arxiv.org/html/2608.06825#bib.bib1)\)\.

###### Corollary 11\(Bounded ReLU reward networks\)\.

Letz​\(x,a\)∈ℝd0z\(x,a\)\\in\\mathbb\{R\}^\{d\_\{0\}\}satisfy‖z​\(x,a\)‖2≤R\\\|z\(x,a\)\\\|\_\{2\}\\leq R\. Consider depth\-LLscalar ReLU networks withppweights, no biases, layer spectral norms at mostSS, concatenated parameter norm at mostBB, and output clipped to\[0,G\]\[0,G\]\. There is a demonstration learner whose cumulative target gap is at most

G​\{p​\[log2⁡\(1\+4​B​R​SL−1​LG\)\+3\]\+2\}\.G\\left\\\{p\\left\[\\log\_\{2\}\\left\(1\+\\frac\{4BRS^\{L\-1\}\\sqrt\{L\}\}\{G\}\\right\)\+3\\right\]\+2\\right\\\}\.\(14\)The same statement covers bounded biases after the standard constant\-coordinate augmentation\.

The proof in Appendix[D\.4](https://arxiv.org/html/2608.06825#A4.SS4)telescopes perturbations through the layers\. This is an explicit finite\-gap result for neural rewards, rather than an assumption that their entropy integral is finite\. It is parameter\-count dependent and information\-theoretic\. It does not assert that the exponentially large proxy vote is a practical neural\-network training algorithm\.

## 6Suboptimal demonstrations

Suppose now that the observed action has target gapδt=gr∗​\(xt,at∗\)\\delta\_\{t\}=g\_\{r\_\{\*\}\}\(x\_\{t\},a\_\{t\}^\{\*\}\), and letΔT=∑tδt\\Delta\_\{T\}=\\sum\_\{t\}\\delta\_\{t\}\. At scalejj, setρj=2−j/3\\rho\_\{j\}=2^\{\-j\}/3, take aρj\\rho\_\{j\}\-cover, and use the more tolerant proxyqj,h​\(x,a\)=𝟏​\{h​\(x,a\)≤2​ρj\}q\_\{j,h\}\(x,a\)=\\mathbf\{1\}\\\{h\(x,a\)\\leq 2\\rho\_\{j\}\\\}\. Initialize with the same priors and predict by the shared vote\. For fixedγ∈\(0,1\)\\gamma\\in\(0,1\), replace \([6](https://arxiv.org/html/2608.06825#S3.E6)\) by

wt\+1=wt​\(1\+γ\)1−q​\(xt,a^t\)​\(1−γ\)1−q​\(xt,at∗\)\.w\_\{t\+1\}=w\_\{t\}\(1\+\\gamma\)^\{1\-q\(x\_\{t\},\\hat\{a\}\_\{t\}\)\}\(1\-\\gamma\)^\{1\-q\(x\_\{t\},a\_\{t\}^\{\*\}\)\}\.\(15\)
###### Theorem 12\(Robust multiscale hedging\)\.

Let

Aγ=ln⁡\(1/\(1−γ\)\)ln⁡\(1\+γ\),ℌγ​\(𝒢\)=∑j≥12−j​ln⁡𝒩​\(𝒢,2−j/3\)\.A\_\{\\gamma\}=\\frac\{\\ln\(1/\(1\-\\gamma\)\)\}\{\\ln\(1\+\\gamma\)\},\\qquad\\mathfrak\{H\}\_\{\\gamma\}\(\\mathcal\{G\}\)=\\sum\_\{j\\geq 1\}2^\{\-j\}\\ln\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\}/3\)\.For every sequence of demonstrations,

∑t=1Tℓt≤6​Aγ​ΔT\+ℌγ​\(𝒢\)\+2​ln⁡2ln⁡\(1\+γ\)\.\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\\leq 6A\_\{\\gamma\}\\Delta\_\{T\}\+\\frac\{\\mathfrak\{H\}\_\{\\gamma\}\(\\mathcal\{G\}\)\+2\\ln 2\}\{\\ln\(1\+\\gamma\)\}\.\(16\)Thus fixedγ\\gamma, polynomial entropy, and bounded gap giveO​\(ΔT\+d\)O\(\\Delta\_\{T\}\+d\)cumulative gap\.

###### Proof sketch\.

Using the same four weight categories as Lemma[1](https://arxiv.org/html/2608.06825#Thmtheorem1), the exact potential change isγ​W10−γ​W01−γ2​W00≤0\\gamma W\_\{10\}\-\\gamma W\_\{01\}\-\\gamma^\{2\}W\_\{00\}\\leq 0\. A target proxy withinρj\\rho\_\{j\}calls every action of target gap at mostρj\\rho\_\{j\}good\. If it calls the prediction good, thenℓt≤3​ρj=2−j\\ell\_\{t\}\\leq 3\\rho\_\{j\}=2^\{\-j\}\. If it calls the demonstration bad, thenδt\>ρj\\delta\_\{t\}\>\\rho\_\{j\}\. Taking logs of its final weight gives

MT​\(2−j\)≤Aγ​MTdem​\(2−j/3\)\+ln⁡𝒩​\(𝒢,2−j/3\)\+j​ln⁡2ln⁡\(1\+γ\)\.M\_\{T\}\(2^\{\-j\}\)\\leq A\_\{\\gamma\}M\_\{T\}^\{\\rm dem\}\(2^\{\-j\}/3\)\+\\frac\{\\ln\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\}/3\)\+j\\ln 2\}\{\\ln\(1\+\\gamma\)\}\.Layer cake and∑j2−j​MTdem​\(2−j/3\)≤6​ΔT\\sum\_\{j\}2^\{\-j\}M\_\{T\}^\{\\rm dem\}\(2^\{\-j\}/3\)\\leq 6\\Delta\_\{T\}prove the result\. Appendix[C](https://arxiv.org/html/2608.06825#A3)gives all details\. ∎

The coefficient on demonstrator gap can be made arbitrarily close to one\. This requires a finer geometric scale grid and wider proxy tolerance, which increase only the entropy term\.

###### Corollary 13\(Near\-unit optimistic comparison\)\.

For everyη∈\(0,1\]\\eta\\in\(0,1\], there is a choice of scales, tolerance, and soft\-update rate such that

∑t=1Tℓt≤\(1\+η\)​ΔT\+O​\(d​ln⁡\(A/η\)\+ln⁡\(1/η\)η\)\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\\leq\(1\+\\eta\)\\Delta\_\{T\}\+O\\left\(\\frac\{d\\ln\(A/\\eta\)\+\\ln\(1/\\eta\)\}\{\\eta\}\\right\)\(17\)whenever𝒩​\(𝒢,ϵ\)≤\(A/ϵ\)d\\mathcal\{N\}\(\\mathcal\{G\},\\epsilon\)\\leq\(A/\\epsilon\)^\{d\}andA≥1A\\geq 1\.

Appendix[C\.1](https://arxiv.org/html/2608.06825#A3.SS1)proves a more general entropy form\. In particular, the learner can compete nearly one\-for\-one with a suboptimal demonstrator while retaining a horizon\-free complexity penalty\.

This is optimistic robustness: exact demonstrations recover a finite bound, while errors cost their actual reward gap rather than their count\. The theorem is incomparable computationally with the efficientO​\(d​log⁡T\)O\(d\\log T\)robust linear methods ofSakaueet al\.\([2025](https://arxiv.org/html/2608.06825#bib.bib15)\); Sakaue \([2026](https://arxiv.org/html/2608.06825#bib.bib17)\)and the structured M\-convex result ofOki and Sakaue \([2026](https://arxiv.org/html/2608.06825#bib.bib16)\)\.

## 7Finite audits

### 7\.1Adaptive stress test

We instantiate the finite algorithm on a two\-action continuous class\. Letrw​\(φ,a\)=a​⟨w,vφ⟩/2r\_\{w\}\(\\varphi,a\)=a\\left\\langle w,v\_\{\\varphi\}\\right\\rangle/2for unit vectorsw,vφ∈ℝ2w,v\_\{\\varphi\}\\in\\mathbb\{R\}^\{2\}anda∈\{−1,\+1\}a\\in\\\{\-1,\+1\\\}\. Uniform circular nets are proper gap covers\. On every round, an adaptive adversary selects the largest\-gap current error from a fixed set of probes placed geometrically around the target’s two decision boundaries\. If no probe is an error, it supplies an uninformative singleton menu\. Each method faces its own adversary, so this is a white\-box stress test rather than a common\-transcript performance comparison\.

The left panel of Figure[1](https://arxiv.org/html/2608.06825#S7.F1)reports 12 target rotations withT=512T=512andJ=9J=9\. The multiscale learner uses 6,427 proxies\. Its mean cumulative gap is 2\.07 and its observed maximum is 2\.54, below the executable finite\-hierarchy certificate 7\.67\. Single\-tolerance learners atϵ∈\{1/4,1/32\}\\epsilon\\in\\\{1/4,1/32\\\}use 13 and 101 proxies and have mean gaps 88\.92 and 21\.32\. An oracle that selects, separately for each target and after seeing the final losses, the best of all nine hierarchy tolerances has mean gap 2\.00\. It selectsϵ=1/512\\epsilon=1/512or1/10241/1024and uses 1,609 or 3,217 proxies\. Thus multiscale is within 3\.3% of this in\-hindsight comparator without choosing a tolerance\. The point is not that an enumerated vote is efficient\. It is that one hierarchy adapts to losses spanning all displayed resolutions, in the precise finite setting used by the proof\.

### 7\.2MovieLens rank\-two audit

We next instantiate Corollary[8](https://arxiv.org/html/2608.06825#Thmtheorem8)on MovieLens 100K, which contains 100,000 integer ratings from 943 users on 1,682 movies\(Harper and Konstan,[2015](https://arxiv.org/html/2608.06825#bib.bib5)\)\. A deterministic biased rank\-two matrix factorization has training RMSE0\.85040\.8504\. For each of the ten users with most ratings, we freeze the item biases and factors, fix the fitted user\-vector norm, and hide only its direction on the circle\. We normalize the entire resulting reward family to gap range one\. Each of 256 rounds draws a ten\-movie menu from that user’s rated movies\. The demonstrated action is the movie with highest actual rating, with identifier tie\-breaking independent of the hidden target\. It need not maximize the fitted latent reward, so we run the robust hierarchy withγ=1/4\\gamma=1/4\.

Each user has 4,810 proper proxies\. After factorization, the full ten\-user online audit, including a baseline, takes 1\.62 CPU seconds\. Mean cumulative latent gap is3\.533\.53for multiscale,14\.8214\.82for the demonstrated\-rating policy, and7\.747\.74for a proper pairwise\-hinge learner with unit\-circle retraction\. The corresponding medians are2\.902\.90,13\.7813\.78, and5\.495\.49\. Multiscale improves on the demonstrator for all ten users and on the proper learner for seven\. Every potential stays at most one, and every run is below its executable robust certificate\. Figure[1](https://arxiv.org/html/2608.06825#S7.F1)shows both audits\.

![Refer to caption](https://arxiv.org/html/2608.06825v1/x1.png)

![Refer to caption](https://arxiv.org/html/2608.06825v1/x2.png)

Figure 1:Left:adaptive boundary stress test, with means and 10th–90th percentiles over target rotations\.Right:MovieLens audit, with means and 10th–90th percentiles over ten users\. All gaps are hidden from the learners\.This audit is deliberately modest\. The fitted model defines the latent target and is not evaluated for held\-out prediction\. Menus are resampled from historical ratings, whose exposure is shaped by the MovieLens interface and prior recommenders\(Harper and Konstan,[2015](https://arxiv.org/html/2608.06825#bib.bib5)\)\. The experiment tests the exact algorithm on non\-synthetic menus and noisy demonstrations\. It is not a production recommender benchmark\.

## 8Fast statistical rates and limitations

Let contexts be i\.i\.d\. from a distributionDD, while the optimal demonstration may be chosen adaptively after seeing each context\. Run the online learner formmrounds and return the uniform mixture of its round policies\.

###### Corollary 14\(Online to batch\)\.

LetB𝒢=ℌdyad​\(𝒢\)\+2B\_\{\\mathcal\{G\}\}=\\mathfrak\{H\}\_\{\\rm dyad\}\(\\mathcal\{G\}\)\+2\. The mixtureπ¯m\\bar\{\\pi\}\_\{m\}satisfies𝔼​\[gapD⁡\(π¯m\)\]≤B𝒢/m\\mathbb\{E\}\[\\operatorname\{gap\}\_\{D\}\(\\bar\{\\pi\}\_\{m\}\)\]\\leq B\_\{\\mathcal\{G\}\}/m\. With probability at least1−δ1\-\\delta,

gapD⁡\(π¯m\)≤B𝒢\+ln⁡\(1/δ\)\(1−e−1\)​m\.\\operatorname\{gap\}\_\{D\}\(\\bar\{\\pi\}\_\{m\}\)\\leq\\frac\{B\_\{\\mathcal\{G\}\}\+\\ln\(1/\\delta\)\}\{\(1\-e^\{\-1\}\)m\}\.\(18\)

HeregapD\\operatorname\{gap\}\_\{D\}is expected target suboptimality on a fresh context\. The proof in Appendix[F](https://arxiv.org/html/2608.06825#A6)uses the conditional inequality𝔼​\[e−ℓt∣ℱt−1\]≤exp⁡\(−\(1−e−1\)​𝔼​\[ℓt∣ℱt−1\]\)\\mathbb\{E\}\[e^\{\-\\ell\_\{t\}\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq\\exp\(\-\(1\-e^\{\-1\}\)\\mathbb\{E\}\[\\ell\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\)\. Thus polynomial entropy yields the fastO​\(\(d\+log⁡\(1/δ\)\)/m\)O\(\(d\+\\log\(1/\\delta\)\)/m\)rate asked for by the continuous\-class problem\.

Three limitations delimit the result\. First, the class must be totally bounded in the uniform gap metric, which is stronger than distribution\-dependent entropy\. Second, the finite implementation may containTΘ​\(d\)T^\{\\Theta\(d\)\}proxies and optimize a nonconvex vote\. Finding a polynomial\-time surrogate is open beyond tractable geometries such as Proposition[7](https://arxiv.org/html/2608.06825#Thmtheorem7)\. Third, an improper recommendation need not reveal a coherent estimate of the user’s objective\. If parameter recovery or properness is required, our contextual\-recommendation corollary does not apply\. Within this scope, integrable gap entropy yields finite total hidden gap from action\-only demonstrations\.

## Reproducibility statement

Every formal claim is proved in the main text or appendix\. The supplement contains fixed\-seed scripts for both update invariants and both panels of Figure[1](https://arxiv.org/html/2608.06825#S7.F1), together with exact reference JSON\. The synthetic audit needs no downloaded data\. The MovieLens script fetches the public 100K release from GroupLens and uses no specialized hardware\.

## References

- P\. Abbeel and A\. Y\. Ng \(2004\)Apprenticeship learning via inverse reinforcement learning\.InProceedings of the Twenty\-First International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p1.1)\.
- I\. Attias, S\. Hanneke, A\. Kalavasis, A\. Karbasi, and G\. Velegkas \(2023\)Optimal learners for realizable regression: PAC learning and online learning\.InAdvances in Neural Information Processing Systems,Vol\.36\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/hash/8c22e5e918198702765ecff4b20d0a90-Abstract-Conference.html)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px2.p1.1)\.
- A\. Bärmann, S\. Pokutta, and O\. Schneider \(2017\)Emulating the expert: inverse optimization through online learning\.InProceedings of the 34th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.70,pp\. 400–410\.External Links:[Link](https://proceedings.mlr.press/v70/barmann17a.html)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p3.9),[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px3.p1.4)\.
- O\. Besbes, Y\. Fonseca, and I\. Lobel \(2025\)Contextual inverse optimization: offline and online learning\.Operations Research73\(1\),pp\. 424–443\.External Links:[Document](https://dx.doi.org/10.1287/opre.2021.0369),[Link](https://arxiv.org/abs/2106.14015)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p3.9),[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px3.p1.4)\.
- L\. Cohen, Y\. Mansour, S\. Moran, and H\. Shao \(2026\)Online set learning from precision and recall feedback\.arXiv preprint arXiv:2605\.09565\.External Links:[Link](https://arxiv.org/abs/2605.09565)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px1.p1.1)\.
- I\. Doron\-Arad, I\. Mehalel, and E\. Mossel \(2026\)Online realizable regression and applications for ReLU networks\.InProceedings of the Thirty\-Ninth Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.336,pp\. 2105–2106\.External Links:[Link](https://proceedings.mlr.press/v336/doron-arad26a.html)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px2.p1.1)\.
- P\. Fatemi, H\. Maskan, S\. Sra, and P\. M\. Esfahani \(2026\)Tight generalization bounds for noiseless inverse optimization\.arXiv preprint arXiv:2605\.08866\.External Links:[Link](https://arxiv.org/abs/2605.08866)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px3.p2.2)\.
- S\. Gollapudi, G\. Guruganesh, K\. Kollias, P\. Manurangsi, R\. P\. Leme, and J\. Schneider \(2021\)Contextual recommendations and low\-regret cutting\-plane algorithms\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 22498–22508\.External Links:[Link](https://proceedings.neurips.cc/paper/2021/hash/bdc6c33585d0cf5d2a8cb83141cd037f-Abstract.html)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p3.9)\.
- F\. M\. Harper and J\. A\. Konstan \(2015\)The MovieLens datasets: history and context\.ACM Transactions on Interactive Intelligent Systems5\(4\),pp\. 19:1–19:19\.External Links:[Document](https://dx.doi.org/10.1145/2827872),[Link](https://doi.org/10.1145/2827872)Cited by:[§7\.2](https://arxiv.org/html/2608.06825#S7.SS2.p1.2),[§7\.2](https://arxiv.org/html/2608.06825#S7.SS2.p3.1)\.
- H\. Jimenez, A\. Kozachinskiy, and V\. Opazo \(2026\)Polynomial\-time mistake\-bounded language generation\.arXiv preprint arXiv:2606\.16077\.External Links:[Link](https://arxiv.org/abs/2606.16077)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px3.p2.2)\.
- N\. Joshi, G\. Li, S\. Bhandari, S\. P\. Kasiviswanathan, C\. Ma, and N\. Srebro \(2026\)Learning to answer from correct demonstrations\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=69fIHgLjyH)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p2.7),[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2608.06825#S5.SS1.p4.4)\.
- J\. Kleinberg, C\. Peale, and O\. Reingold \(2026\)Mistake\-bounded language generation\.arXiv preprint arXiv:2605\.10809\.External Links:[Link](https://arxiv.org/abs/2605.10809)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px1.p1.1)\.
- T\. Oki and S\. Sakaue \(2026\)Finite and corruption\-robust regret bounds in online inverse linear optimization under M\-convex action sets\.arXiv preprint arXiv:2602\.01682\.External Links:[Link](https://arxiv.org/abs/2602.01682)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p3.9),[§5](https://arxiv.org/html/2608.06825#S5.p2.5),[§6](https://arxiv.org/html/2608.06825#S6.p4.1)\.
- A\. F\. Pour, F\. Mansouri, and S\. Ben\-David \(2026\)Learning with multiple correct answers: regret bounds under different feedback models\.arXiv preprint arXiv:2602\.09402\.External Links:[Link](https://arxiv.org/abs/2602.09402)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px1.p1.1)\.
- V\. Raman, U\. Subedi, and A\. Tewari \(2024\)Online learning with set\-valued feedback\.InProceedings of the Thirty\-Seventh Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.247,pp\. 4381–4412\.External Links:[Link](https://proceedings.mlr.press/v247/raman24b.html)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Sakaue, T\. Tsuchiya, H\. Bao, and T\. Oki \(2025\)Online inverse linear optimization: efficient logarithmic\-regret algorithm, robustness to suboptimality, and lower bound\.InAdvances in Neural Information Processing Systems,External Links:2501\.14349,[Link](https://arxiv.org/abs/2501.14349)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p3.9),[§1](https://arxiv.org/html/2608.06825#S1.p6.1),[§5](https://arxiv.org/html/2608.06825#S5.p2.5),[§6](https://arxiv.org/html/2608.06825#S6.p4.1)\.
- S\. Sakaue \(2026\)Simple projection\-free algorithm for contextual recommendation with logarithmic regret and robustness\.arXiv preprint arXiv:2603\.20826\.External Links:[Link](https://arxiv.org/abs/2603.20826)Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p6.1),[§6](https://arxiv.org/html/2608.06825#S6.p4.1)\.
- S\. Shao, C\. Fang, Z\. Lin, and D\. Tao \(2026\)Partial feedback online learning\.arXiv preprint arXiv:2601\.21462\.External Links:[Link](https://arxiv.org/abs/2601.21462)Cited by:[§2](https://arxiv.org/html/2608.06825#S2.SS0.SSS0.Px1.p1.1)\.
- U\. Syed and R\. E\. Schapire \(2007\)A game\-theoretic approach to apprenticeship learning\.InAdvances in Neural Information Processing Systems,Vol\.20\.Cited by:[§1](https://arxiv.org/html/2608.06825#S1.p1.1)\.
- A\. C\. Yao \(1977\)Probabilistic computations: toward a unified measure of complexity\.Proceedings of the 18th Annual Symposium on Foundations of Computer Science,pp\. 222–227\.Cited by:[§4](https://arxiv.org/html/2608.06825#S4.3.p1.11)\.

## Appendix AAI Usage Declaration

LLM\-based tools were used for assistance with proof checking and prose editing\.

## Appendix BTechnical variants of the main algorithm

### B\.1A finite hierarchy for a known horizon

For horizonT≥2T\\geq 2, letJ=⌈log2⁡T⌉J=\\lceil\\log\_\{2\}T\\rceiland retain only scales1,…,J1,\\ldots,J\. Normalize the priors as

α~j=2−jZJ,ZJ=∑k=1J2−k=1−2−J\.\\widetilde\{\\alpha\}\_\{j\}=\\frac\{2^\{\-j\}\}\{Z\_\{J\}\},\\qquad Z\_\{J\}=\\sum\_\{k=1\}^\{J\}2^\{\-k\}=1\-2^\{\-J\}\.Sinceα~j≥2−j\\widetilde\{\\alpha\}\_\{j\}\\geq 2^\{\-j\}, the proof of \([7](https://arxiv.org/html/2608.06825#S4.E7)\) is unchanged forj≤Jj\\leq J\. Layer cake above2−J2^\{\-J\}is therefore bounded by the truncated sum in \([8](https://arxiv.org/html/2608.06825#S4.E8)\)\. The remaining interval contributes at mostT​2−J≤1T2^\{\-J\}\\leq 1\. Hence the fully finite algorithm satisfies

∑t=1Tℓt≤ℌdyad​\(𝒢\)\+3\.\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\\leq\\mathfrak\{H\}\_\{\\rm dyad\}\(\\mathcal\{G\}\)\+3\.\(19\)It uses∑j=1J𝒩​\(𝒢,2−j−1\)\\sum\_\{j=1\}^\{J\}\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\-1\}\)proxies\. For polynomial entropy this can be polynomial inTTbut exponential indd\. The same truncation adds at most one to Theorem[12](https://arxiv.org/html/2608.06825#Thmtheorem12)\.

### B\.2Approximate vote maximization

The infinite vote in \([5](https://arxiv.org/html/2608.06825#S3.E5)\) is absolutely convergent wheneverWt<∞W\_\{t\}<\\infty\. Suppose the learner selects an action whose score is withinηt\\eta\_\{t\}of the supremum, whereηt≥0\\eta\_\{t\}\\geq 0andE=∑tηt<∞E=\\sum\_\{t\}\\eta\_\{t\}<\\infty\. The proof of Lemma[1](https://arxiv.org/html/2608.06825#Thmtheorem1)becomes

Wt\+1−Wt≤W10−W01≤ηt,W\_\{t\+1\}\-W\_\{t\}\\leq W\_\{10\}\-W\_\{01\}\\leq\\eta\_\{t\},soWT\+1≤1\+EW\_\{T\+1\}\\leq 1\+E\. The threshold bound incurs an additivelog2⁡\(1\+E\)\\log\_\{2\}\(1\+E\), which integrates to the same additive constant in cumulative loss\. TakingE≤1E\\leq 1givesℌdyad\+3\\mathfrak\{H\}\_\{\\rm dyad\}\+3\. This also covers nonattained vote suprema\. All sums can be justified by monotone convergence because the summands are nonnegative and total weight is finite\.

For compact menus and the finite known\-horizon algorithm, no approximation is needed when the gap functions are continuous\. Each set\{a:h​\(x,a\)≤ϵj\}\\\{a:h\(x,a\)\\leq\\epsilon\_\{j\}\\\}is closed, its indicator is upper semicontinuous, and a finite nonnegative weighted sum of these indicators attains a maximum\.

## Appendix CComplete proof of robust hedging

Writebd=q​\(xt,at∗\)b\_\{d\}=q\(x\_\{t\},a\_\{t\}^\{\*\}\)andbp=q​\(xt,a^t\)b\_\{p\}=q\(x\_\{t\},\\hat\{a\}\_\{t\}\)\. LetWbd​bpW\_\{b\_\{d\}b\_\{p\}\}denote current weight in each category\. Vote maximality givesW10≤W01W\_\{10\}\\leq W\_\{01\}\. Under \([15](https://arxiv.org/html/2608.06825#S6.E15)\), the four multiplicative factors are

\(1−γ2\),\(1−γ\),\(1\+γ\),1\(1\-\\gamma^\{2\}\),\\quad\(1\-\\gamma\),\\quad\(1\+\\gamma\),\\quad 1for categories00,01,10,1100,01,10,11, respectively\. Therefore

Wt\+1−Wt=−γ2​W00−γ​W01\+γ​W10≤0\.W\_\{t\+1\}\-W\_\{t\}=\-\\gamma^\{2\}W\_\{00\}\-\\gamma W\_\{01\}\+\\gamma W\_\{10\}\\leq 0\.
Fix scalejjand a centerhjh\_\{j\}with‖hj−gr∗‖∞≤ρj\\\|h\_\{j\}\-g\_\{r\_\{\*\}\}\\\|\_\{\\infty\}\\leq\\rho\_\{j\}\. If its proxy callsa^t\\hat\{a\}\_\{t\}good, then

ℓt≤hj​\(xt,a^t\)\+ρj≤3​ρj=2−j\.\\ell\_\{t\}\\leq h\_\{j\}\(x\_\{t\},\\hat\{a\}\_\{t\}\)\+\\rho\_\{j\}\\leq 3\\rho\_\{j\}=2^\{\-j\}\.If it callsat∗a\_\{t\}^\{\*\}bad, thengr∗​\(xt,at∗\)≥hj​\(xt,at∗\)−ρj\>ρjg\_\{r\_\{\*\}\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\\geq h\_\{j\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-\\rho\_\{j\}\>\\rho\_\{j\}\. LetPjP\_\{j\}andDjD\_\{j\}count rounds on which this target proxy calls the prediction and demonstration bad\. Its final weight is exactly

2−j\|Cj\|​\(1\+γ\)Pj​\(1−γ\)Dj≤1\.\\frac\{2^\{\-j\}\}\{\|C\_\{j\}\|\}\(1\+\\gamma\)^\{P\_\{j\}\}\(1\-\\gamma\)^\{D\_\{j\}\}\\leq 1\.Consequently,

MT​\(2−j\)\\displaystyle M\_\{T\}\(2^\{\-j\}\)≤Pj\\displaystyle\\leq P\_\{j\}\(20\)≤ln⁡\|Cj\|\+j​ln⁡2\+Dj​ln⁡\(1/\(1−γ\)\)ln⁡\(1\+γ\)\\displaystyle\\leq\\frac\{\\ln\|C\_\{j\}\|\+j\\ln 2\+D\_\{j\}\\ln\(1/\(1\-\\gamma\)\)\}\{\\ln\(1\+\\gamma\)\}\(21\)≤Aγ​MTdem​\(2−j/3\)\+ln⁡𝒩​\(𝒢,2−j/3\)\+j​ln⁡2ln⁡\(1\+γ\)\.\\displaystyle\\leq A\_\{\\gamma\}M\_\{T\}^\{\\rm dem\}\(2^\{\-j\}/3\)\+\\frac\{\\ln\\mathcal\{N\}\(\\mathcal\{G\},2^\{\-j\}/3\)\+j\\ln 2\}\{\\ln\(1\+\\gamma\)\}\.\(22\)For anyz∈\[0,1\]z\\in\[0,1\], ifj0j\_\{0\}is the first integer with2−j0<3​z2^\{\-j\_\{0\}\}<3z, then

∑j≥12−j​𝟏​\{z\>2−j/3\}≤∑j≥j02−j=2−j0\+1<6​z\.\\sum\_\{j\\geq 1\}2^\{\-j\}\\mathbf\{1\}\\\{z\>2^\{\-j\}/3\\\}\\leq\\sum\_\{j\\geq j\_\{0\}\}2^\{\-j\}=2^\{\-j\_\{0\}\+1\}<6z\.Summing this inequality over demonstration gaps proves

∑j≥12−j​MTdem​\(2−j/3\)≤6​ΔT\.\\sum\_\{j\\geq 1\}2^\{\-j\}M\_\{T\}^\{\\rm dem\}\(2^\{\-j\}/3\)\\leq 6\\Delta\_\{T\}\.Integrating \([22](https://arxiv.org/html/2608.06825#A3.E22)\) over dyadic loss intervals and using∑jj​2−j=2\\sum\_\{j\}j2^\{\-j\}=2proves \([16](https://arxiv.org/html/2608.06825#S6.E16)\)\.

### C\.1General grid and near\-unit comparison

Fix a geometric ratioβ\>1\\beta\>1and a proxy\-width parameterc\>1c\>1\. Set

θj=β−j,αj=\(β−1\)​β−j,ρj=θjc\+1\.\\theta\_\{j\}=\\beta^\{\-j\},\\qquad\\alpha\_\{j\}=\(\\beta\-1\)\\beta^\{\-j\},\\qquad\\rho\_\{j\}=\\frac\{\\theta\_\{j\}\}\{c\+1\}\.The priors sum to one\. Use aρj\\rho\_\{j\}\-cover and let a proxy call an action good when its center gap is at mostc​ρjc\\rho\_\{j\}\. The soft update remains \([15](https://arxiv.org/html/2608.06825#S6.E15)\)\. A target proxy that calls the prediction good certifies target gap at most\(c\+1\)​ρj=θj\(c\+1\)\\rho\_\{j\}=\\theta\_\{j\}\. If it calls the demonstration bad, that demonstration has target gap greater than\(c−1\)​ρj=κ​θj\(c\-1\)\\rho\_\{j\}=\\kappa\\theta\_\{j\}, whereκ=\(c−1\)/\(c\+1\)\\kappa=\(c\-1\)/\(c\+1\)\. The target\-weight argument therefore gives

MT​\(θj\)≤Aγ​MTdem​\(κ​θj\)\+ln⁡𝒩​\(𝒢,ρj\)\+ln⁡\(1/αj\)ln⁡\(1\+γ\)\.M\_\{T\}\(\\theta\_\{j\}\)\\leq A\_\{\\gamma\}M\_\{T\}^\{\\rm dem\}\(\\kappa\\theta\_\{j\}\)\+\\frac\{\\ln\\mathcal\{N\}\(\\mathcal\{G\},\\rho\_\{j\}\)\+\\ln\(1/\\alpha\_\{j\}\)\}\{\\ln\(1\+\\gamma\)\}\.\(23\)The width of the layer\(θj,θj−1\]\(\\theta\_\{j\},\\theta\_\{j\-1\}\]is exactlyαj\\alpha\_\{j\}\. For anyz∈\[0,1\]z\\in\[0,1\], the geometric tail telescopes to

∑j≥1αj​𝟏​\{z\>κ​θj\}<βκ​z\.\\sum\_\{j\\geq 1\}\\alpha\_\{j\}\\mathbf\{1\}\\\{z\>\\kappa\\theta\_\{j\}\\\}<\\frac\{\\beta\}\{\\kappa\}z\.Consequently,

∑t=1Tℓt≤β​Aγκ​ΔT\+ℌβ,c​\(𝒢\)\+Pβln⁡\(1\+γ\),\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\\leq\\frac\{\\beta A\_\{\\gamma\}\}\{\\kappa\}\\Delta\_\{T\}\+\\frac\{\\mathfrak\{H\}\_\{\\beta,c\}\(\\mathcal\{G\}\)\+P\_\{\\beta\}\}\{\\ln\(1\+\\gamma\)\},\(24\)where

ℌβ,c​\(𝒢\)\\displaystyle\\mathfrak\{H\}\_\{\\beta,c\}\(\\mathcal\{G\}\)=∑j≥1αj​ln⁡𝒩​\(𝒢,β−jc\+1\),\\displaystyle=\\sum\_\{j\\geq 1\}\\alpha\_\{j\}\\ln\\mathcal\{N\}\\left\(\\mathcal\{G\},\\frac\{\\beta^\{\-j\}\}\{c\+1\}\\right\),Pβ\\displaystyle P\_\{\\beta\}=∑j≥1αj​ln⁡\(1/αj\)=ln⁡ββ−1\+ln⁡ββ−1\.\\displaystyle=\\sum\_\{j\\geq 1\}\\alpha\_\{j\}\\ln\(1/\\alpha\_\{j\}\)=\\ln\\frac\{\\beta\}\{\\beta\-1\}\+\\frac\{\\ln\\beta\}\{\\beta\-1\}\.Theorem[12](https://arxiv.org/html/2608.06825#Thmtheorem12)is the special caseβ=c=2\\beta=c=2\.

To prove Corollary[13](https://arxiv.org/html/2608.06825#Thmtheorem13), choose

γ=η16,β=1\+η16,c=1\+16η\.\\gamma=\\frac\{\\eta\}\{16\},\\qquad\\beta=1\+\\frac\{\\eta\}\{16\},\\qquad c=1\+\\frac\{16\}\{\\eta\}\.Forγ≤1/2\\gamma\\leq 1/2,

Aγ≤1\+γ1−γ≤1\+η4\.A\_\{\\gamma\}\\leq\\frac\{1\+\\gamma\}\{1\-\\gamma\}\\leq 1\+\\frac\{\\eta\}\{4\}\.Also1/κ=1\+η/81/\\kappa=1\+\\eta/8\. Multiplying the three factors showsβ​Aγ/κ≤1\+η\\beta A\_\{\\gamma\}/\\kappa\\leq 1\+\\etaforη∈\(0,1\]\\eta\\in\(0,1\]\. Under the polynomial entropy assumption,

ℌβ,c​\(𝒢\)\\displaystyle\\mathfrak\{H\}\_\{\\beta,c\}\(\\mathcal\{G\}\)≤d​\[ln⁡\(A​\(c\+1\)\)\+β​ln⁡ββ−1\]≤d​\[ln⁡\(18​A/η\)\+2\],\\displaystyle\\leq d\\left\[\\ln\(A\(c\+1\)\)\+\\frac\{\\beta\\ln\\beta\}\{\\beta\-1\}\\right\]\\leq d\[\\ln\(18A/\\eta\)\+2\],Pβ\\displaystyle P\_\{\\beta\}≤ln⁡\(17/η\)\+1,\\displaystyle\\leq\\ln\(17/\\eta\)\+1,1ln⁡\(1\+γ\)\\displaystyle\\frac\{1\}\{\\ln\(1\+\\gamma\)\}≤17η\.\\displaystyle\\leq\\frac\{17\}\{\\eta\}\.Substitution into \([24](https://arxiv.org/html/2608.06825#A3.E24)\) proves \([17](https://arxiv.org/html/2608.06825#S6.E17)\)\.

## Appendix DCovering calculations

### D\.1Linear rewards and gap geometry

For completeness, fix an actionaaand write

gw​\(x,a\)=maxb∈𝒜​\(x\)⁡⟨w,ϕ​\(x,b\)−ϕ​\(x,a\)⟩\.g\_\{w\}\(x,a\)=\\max\_\{b\\in\\mathcal\{A\}\(x\)\}\\left\\langle w,\\phi\(x,b\)\-\\phi\(x,a\)\\right\\rangle\.For anyw,vw,v, the elementary inequality\|maxb⁡fb−maxb⁡kb\|≤maxb⁡\|fb−kb\|\|\\max\_\{b\}f\_\{b\}\-\\max\_\{b\}k\_\{b\}\|\\leq\\max\_\{b\}\|f\_\{b\}\-k\_\{b\}\|gives

\|gw​\(x,a\)−gv​\(x,a\)\|\\displaystyle\|g\_\{w\}\(x,a\)\-g\_\{v\}\(x,a\)\|≤maxb∈𝒜​\(x\)⁡\|⟨w−v,ϕ​\(x,b\)−ϕ​\(x,a\)⟩\|\\displaystyle\\leq\\max\_\{b\\in\\mathcal\{A\}\(x\)\}\|\\left\\langle w\-v,\\phi\(x,b\)\-\\phi\(x,a\)\\right\\rangle\|≤K​‖w−v‖2\.\\displaystyle\\leq K\\\|w\-v\\\|\_\{2\}\.The same expression givesgw​\(x,a\)≤B​Kg\_\{w\}\(x,a\)\\leq BK\. The Euclidean ball of radiusBBhas anη​B\\eta B\-net with cardinality at most\(1\+2/η\)d\(1\+2/\\eta\)^\{d\}, by comparing volumes of disjointη​B/2\\eta B/2balls around a maximal separated set\. This proves Corollary[6](https://arxiv.org/html/2608.06825#Thmtheorem6)\.

### D\.2Low\-rank bilinear rewards

The set

\{W∈ℝm×n:rank⁡\(W\)≤r,‖W‖F≤B\}\\\{W\\in\\mathbb\{R\}^\{m\\times n\}:\\operatorname\{rank\}\(W\)\\leq r,\\ \\\|W\\\|\_\{F\}\\leq B\\\}has anη​B\\eta B\-net in Frobenius norm of cardinality at most\(9/η\)\(m\+n\+1\)​r\(9/\\eta\)^\{\(m\+n\+1\)r\}\. One way to obtain this standard bound is to cover the two Stiefel factors and therrsingular values in a compact singular\-value decomposition, then combine the three approximation errors\. The same maximum\-difference calculation as above gives

‖gW−gV‖∞≤K​‖W−V‖F,0≤gW≤B​K\.\\\|g\_\{W\}\-g\_\{V\}\\\|\_\{\\infty\}\\leq K\\\|W\-V\\\|\_\{F\},\\qquad 0\\leq g\_\{W\}\\leq BK\.Corollary[4](https://arxiv.org/html/2608.06825#Thmtheorem4)with entropy exponent\(m\+n\+1\)​r\(m\+n\+1\)randA=9A=9proves Corollary[9](https://arxiv.org/html/2608.06825#Thmtheorem9)\.

### D\.3Generic parameterization

LetΘ⊂ℝp\\Theta\\subset\\mathbb\{R\}^\{p\}have anη\\eta\-cover of size at most\(C/η\)p\(C/\\eta\)^\{p\}\. Suppose gaps lie in\[0,G\]\[0,G\]and‖gθ−gθ′‖∞≤L​‖θ−θ′‖\\\|g\_\{\\theta\}\-g\_\{\\theta^\{\\prime\}\}\\\|\_\{\\infty\}\\leq L\\\|\\theta\-\\theta^\{\\prime\}\\\|\. If the parameter set has radiusBB, then a normalized gap cover at accuracyϵ\\epsilonis induced by a parameter cover at radiusG​ϵ/LG\\epsilon/L\. Thus

𝒩​\(𝒢/G,ϵ\)≤\(C​B​LG​ϵ\)p\\mathcal\{N\}\(\\mathcal\{G\}/G,\\epsilon\)\\leq\\left\(\\frac\{CBL\}\{G\\epsilon\}\\right\)^\{p\}wheneverB​L/G≥1BL/G\\geq 1, and the harmless replacement byC​\(1\+B​L/G\)/ϵC\(1\+BL/G\)/\\epsiloncovers all cases\. Corollary[4](https://arxiv.org/html/2608.06825#Thmtheorem4)givesO​\(G​p​\[1\+log⁡\(1\+B​L/G\)\]\)O\(Gp\[1\+\\log\(1\+BL/G\)\]\)\.

### D\.4Bounded ReLU networks

Write the unclipped depth\-LLnetwork as

fW​\(z\)=WL​σ​\(WL−1​σ​\(⋯​σ​\(W1​z\)\)\),f\_\{W\}\(z\)=W\_\{L\}\\sigma\\bigl\(W\_\{L\-1\}\\sigma\(\\cdots\\sigma\(W\_\{1\}z\)\)\\bigr\),whereWLW\_\{L\}has one row andσ​\(u\)=max⁡\{u,0\}\\sigma\(u\)=\\max\\\{u,0\\\}coordinatewise\. Clipping to\[0,G\]\[0,G\]is nonexpansive\. For two parameter tuplesW,VW,V, insert one layer at a time\. ReLU is 1\-Lipschitz and fixes zero, while every layer has spectral norm at mostSS\. Thus

\|fW​\(z\)−fV​\(z\)\|\\displaystyle\|f\_\{W\}\(z\)\-f\_\{V\}\(z\)\|≤R​SL−1​∑l=1L‖Wl−Vl‖F\\displaystyle\\leq RS^\{L\-1\}\\sum\_\{l=1\}^\{L\}\\\|W\_\{l\}\-V\_\{l\}\\\|\_\{F\}≤R​SL−1​L​‖W−V‖2\.\\displaystyle\\leq RS^\{L\-1\}\\sqrt\{L\}\\,\\\|W\-V\\\|\_\{2\}\.The first line follows because the perturbation at any one layer is preceded and followed byL−1L\-1maps whose product Lipschitz constant is at mostSL−1S^\{L\-1\}\. Maximization and subtraction then give

‖gW−gV‖∞≤2​R​SL−1​L​‖W−V‖2\.\\\|g\_\{W\}\-g\_\{V\}\\\|\_\{\\infty\}\\leq 2RS^\{L\-1\}\\sqrt\{L\}\\,\\\|W\-V\\\|\_\{2\}\.The allowed parameter set lies in a Euclideanpp\-ball of radiusBB\. Its radius\-uucovering number is at most\(1\+2​B/u\)p\(1\+2B/u\)^\{p\}\. Takingu=G​ϵ/\(2​R​SL−1​L\)u=G\\epsilon/\(2RS^\{L\-1\}\\sqrt\{L\}\)yields

𝒩​\(𝒢/G,ϵ\)≤\(1\+4​B​R​SL−1​L/Gϵ\)p,ϵ≤1\.\\mathcal\{N\}\(\\mathcal\{G\}/G,\\epsilon\)\\leq\\left\(\\frac\{1\+4BRS^\{L\-1\}\\sqrt\{L\}/G\}\{\\epsilon\}\\right\)^\{p\},\\qquad\\epsilon\\leq 1\.Corollary[4](https://arxiv.org/html/2608.06825#Thmtheorem4)proves \([14](https://arxiv.org/html/2608.06825#S5.E14)\)\. Bias vectors can be represented by adding a constant coordinate at each layer\. The same calculation then applies with the corresponding augmented input and operator\-norm bounds\.

## Appendix ELower\-bound details

Forw∈\[−1,1\]dw\\in\[\-1,1\]^\{d\}, define

rw​\(i,a\)=1\+a​wi2,gw​\(i,a\)=\|wi\|−a​wi2\.r\_\{w\}\(i,a\)=\\frac\{1\+aw\_\{i\}\}\{2\},\\qquad g\_\{w\}\(i,a\)=\\frac\{\|w\_\{i\}\|\-aw\_\{i\}\}\{2\}\.At a vertex, the two rewards are one and zero, hence a wrong action has gap one\.

Forw,v∈\[1/2,1\]dw,v\\in\[1/2,1\]^\{d\}, action\+1\+1is optimal at every context, and

supi,a\|gw​\(i,a\)−gv​\(i,a\)\|=‖w−v‖∞\.\\sup\_\{i,a\}\|g\_\{w\}\(i,a\)\-g\_\{v\}\(i,a\)\|=\\\|w\-v\\\|\_\{\\infty\}\.Therefore the positive subcube requires at least\(c/ϵ\)d\(c/\\epsilon\)^\{d\}balls and admits at most\(C/ϵ\)d\(C/\\epsilon\)^\{d\}balls for numerical constantsc,Cc,C\. The full cube also admits such an upper bound because the displayed gap map is Lipschitz inℓ∞\\ell\_\{\\infty\}\. This proves the entropy order\.

Under a uniform prior on the vertices, the observable history before roundiicontains onlyw1,…,wi−1w\_\{1\},\\ldots,w\_\{i\-1\}\. It is independent ofwiw\_\{i\}\. Conditional on any learner randomness, either action is therefore wrong with probability1/21/2\. The firstddcontexts contribute expected lossd/2d/2\. Yao’s minimax principle converts this distributional lower bound for deterministic learners to a worst\-case expected lower bound for randomized learners\.

## Appendix FOnline\-to\-batch proof

Letπt\\pi\_\{t\}be the policy used on roundtt, based on the firstt−1t\-1samples, and letLt∈\[0,1\]L\_\{t\}\\in\[0,1\]be its realized target gap\. Write

μt=𝔼​\[Lt∣ℱt−1\]=gapD⁡\(πt\)\.\\mu\_\{t\}=\\mathbb\{E\}\[L\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=\\operatorname\{gap\}\_\{D\}\(\\pi\_\{t\}\)\.Convexity ofe−xe^\{\-x\}on\[0,1\]\[0,1\]givese−x≤1−\(1−e−1\)​xe^\{\-x\}\\leq 1\-\(1\-e^\{\-1\}\)x\. Hence, withc=1−e−1c=1\-e^\{\-1\},

𝔼​\[e−Lt∣ℱt−1\]≤1−c​μt≤e−c​μt\.\\mathbb\{E\}\[e^\{\-L\_\{t\}\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq 1\-c\\mu\_\{t\}\\leq e^\{\-c\\mu\_\{t\}\}\.It follows that

Zs=exp⁡\(c​∑t=1sμt−∑t=1sLt\)Z\_\{s\}=\\exp\\left\(c\\sum\_\{t=1\}^\{s\}\\mu\_\{t\}\-\\sum\_\{t=1\}^\{s\}L\_\{t\}\\right\)is a nonnegative supermartingale with𝔼​Z0=1\\mathbb\{E\}Z\_\{0\}=1\. Markov’s inequality gives, with probability at least1−δ1\-\\delta,

c​∑t=1mμt≤∑t=1mLt\+ln⁡\(1/δ\)≤B𝒢\+ln⁡\(1/δ\)\.c\\sum\_\{t=1\}^\{m\}\\mu\_\{t\}\\leq\\sum\_\{t=1\}^\{m\}L\_\{t\}\+\\ln\(1/\\delta\)\\leq B\_\{\\mathcal\{G\}\}\+\\ln\(1/\\delta\)\.The population gap of the uniform mixture ism−1​∑tμtm^\{\-1\}\\sum\_\{t\}\\mu\_\{t\}, proving \([18](https://arxiv.org/html/2608.06825#S8.E18)\)\. Taking expectations and using the independence of each freshxtx\_\{t\}fromπt\\pi\_\{t\}gives the expectation statement directly\.

## Appendix GExecutable invariant checks

The supplementary artifact contains four small NumPy programs\. The first constructs finite linear reward covers and checks, round by round, that total weight never increases, every target proxy survives, every large target gap doubles it, each threshold count obeys its proof bound, and cumulative gap obeys the truncated entropy sum\. The second injects suboptimal demonstrations and checks the soft potential, target\-proxy log inequality, and robust cumulative bound\. The third reproduces the left panel of Figure[1](https://arxiv.org/html/2608.06825#S7.F1), its proxy counts, and its numeric values\. The fourth downloads MovieLens 100K and reproduces the right panel, runtimes, per\-user results, and robust certificates\. All use fixed random seeds\. These scripts are finite\-precision consistency checks, not evidence in place of the proofs\.