arXiv:2609.18782v1 [cs.LG] 16 Sep 2026
A C ONVERGENCE F RAMEWORK FOR D EEP 𝑉 -L EARNING : E RROR P ROPAGATION AND S HARP ACTION -G AP B OUNDS
Yury Kolomeytsev Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University [email protected]
A BSTRACT We establish convergence bounds for deep 𝑉 -learning with horizon 𝐻. The algorithm fits a scalar value function to targets from executed transitions and selects actions using a predictive model and the learned value function. For current observed-successor targets with fresh true-kernel outcomes, the conditional mean is 𝒯 𝛽 𝑉 , which averages over the behavior policy’s actions. The Bellman optimality update is 𝒯 𝑉 . We decompose the update error into six residuals: fitting, transition reuse, target construction, replay, action selection, and exploration. Under 𝐿𝑠 concentrability, their 𝐿𝑝 norms, with 𝑝 = 𝑠/(𝑠 − 1), control expected 𝐿1 policy loss. The bound has explicit weights on residuals from only the most recent 𝐻 − 1 update blocks, plus an initialization term for shorter runs. We quantify the cost of a shared sampling distribution across horizon levels. For statistical error bounds proportional to 𝑛−𝜈 , we derive optimal continuous allocations and an integer allocation whose statistical objective is within a factor 2𝜈 of the constrained optimum. A margin condition with exponent 𝛼 gives action error of order Λ1+𝛼/𝑝 , where Λ combines network drift and score error; a matching one-step construction proves the exponent sharp. Bounds on the distance between frozen and optimal scores transfer an optimal-gap condition to frozen-iterate gap bounds while retaining the mass of optimal ties. Survival probabilities and coverage conditions at deployment yield bounds for policies selected with approximate scores. Separate spatial ReLU networks for each horizon level give a conditional neural regression rate, and the finite-state specialization gives a log-free expected fit rate. These results establish expected policy-loss consistency for the fixed-horizon generative-reset approximate-ERM procedure with exact action scores and provide an explicit residual-decay criterion for FIFO/interleaved SGD. Keywords reinforcement learning · deep learning · deep 𝑉 -learning · Markov decision processes · convergence analysis · error propagation · Bellman residuals · concentrability coefficients · action-gap regularity
1
Introduction
Deep 𝑉 -learning fits a scalar state-value function to targets from executed transitions and selects actions using a predictive model and the learned value function. Its population target can differ from the Bellman optimality target used in fitted value iteration [1]. With a frozen bootstrap 𝑉 and fresh true-kernel outcomes, its observed-successor target has population response 𝒯 𝛽 𝑉 for the acting policy 𝛽; policy improvement is governed by 𝒯 𝑉 . At any state where 𝛽 assigns positive probability to an action that does not maximize 𝑄𝑉 , the two operators differ, even with unlimited data and exact optimization. We derive a finite-horizon policy-loss bound by decomposing the error relative to the Bellman optimality update into six terms: fitting, transition reuse, target construction, replay, action selection, and exploration. The action-selection term accounts for network drift and score approximation. Bounds for a particular replay scheme, optimizer, or state representation enter the policy-loss theorem through the corresponding residuals. Model-based action selection with a scalar value function appears in CADRL and SA-CADRL [2, 3]. In the SARL pseudocode, a stored transition receives a frozen-target label when it is sampled for a minibatch, the SAMPLE/OBS
Deep 𝑉 -Learning: Convergence Framework
convention. EB-CADRL forms the corresponding observed-successor label when the transition is stored, the STORE/ OBS convention [4, 5]. These choices determine whether the bootstrap uses the current or an older target network. Building on EB-CADRL, HMP-DRL [6] uses deep 𝑉 -learning for local control in long-range navigation. It incorporates checkpoints from a graph-based global planner into the state representation and reward function. For the analysis, a full simulator or belief state is augmented with the remaining-step clock whenever it satisfies (13). Other observation vectors are treated as measurable compressions, with aliasing, closure, and score errors handled by Proposition 3.17. 1.1
Algorithms and analysis
We distinguish the replay-based algorithm Arun , the generative-reset procedure Aiid , and the residual recursion R used to bound policy loss. The recursion applies whenever the six errors satisfy their stated envelopes. For Aiid , we derive statistical fit bounds using fresh blocks from a single reset distribution. For Arun , bounds on the six residuals connect the implemented updates to the same recursion: six residual bounds
statistical fit bound
Arun −−−−−−−−−−→ R,
Aiid −−−−−−−−−−→ R.
(1)
For the matched-budget comparison, Alev iid draws samples separately at each horizon level. Statement tags identify the setting or procedure to which a result applies; G denotes the general setting. Main results. (C1) Convergence through residual propagation. The expected policy-loss bound is a weighted sum of the six residual envelopes and an initialization term. Its explicit weights vanish outside the most recent 𝐻 − 1 update blocks, and the initialization term vanishes for 𝐾 ≥ 𝐻 − 1 (Theorem 3.18). (C2) Sharp horizon coefficients and sample allocation. We characterize the horizon dependence of the shared-law propagation coefficient and construct a family that attains the bound (Theorem 3.6 and Corollary 3.7). Direct level sampling gives a separate propagation bound and an exact sample count (Theorem 3.19). Under matched label budgets, we derive the optimal continuous allocation, its constrained water-filling solution, and an integer schedule within a factor 2𝜈 of the constrained statistical optimum (Theorem 3.20). The resulting horizon orders are given in Corollary 3.21. (C3) Sharp action-gap and deployment bounds. The action-residual exponent depends on the norm used to measure error. We derive these exponents and prove one-step sharpness (Theorem 4.5 and Proposition 4.7). An optimalgap condition and bounds on score approximation yield gap bounds for the frozen iterates while accounting for optimal ties (Proposition 4.3). A separate construction shows that score error can sustain a positive policy-loss floor (Proposition 4.8). We also bound the loss of the controller selected by the implemented score (Theorem 6.1 and Corollary 6.2). (C4) Nonasymptotic neural and tabular convergence. For the generative-reset procedure, we obtain neural regression and policy-loss rates, along with a log-free expected fit rate in the tabular case (Proposition 5.5, Theorem 6.3, and Corollary 5.7). With exact action scores, the procedure achieves expected policy-loss consistency (Corollary 6.4). We verify Bellman closure and the network-class assumptions in a non-tabular finite-rank model (Propositions 5.2 and 5.3). Action-indexed regression retains the executed action as an input. Expected SARSA uses this structure and averages the next action [7, §§6.1, 6.6]. Remark 2.5 contrasts these targets with state-only regression, and Section 6.4 compares the corresponding fitted-value, neural-𝑄, action-gap, and replay analyses.
2
Model and algorithm
Algorithm 1 specifies the replay-based procedure Arun . The analysis distinguishes six design choices: (S1) a scalar value head 𝑉𝜃 ; (S2) a one-step score built from an implemented reward and transition model, (︀ )︀ ̂︀ 𝑉 (˜ ̂︀ 𝑠, 𝑎) + 𝛾𝑉 𝑃̂︀(˜ ̂︀ 𝑉 (˜ 𝑄 𝑠, 𝑎) := 𝑅(˜ 𝑠, 𝑎) , ̂︀ 𝑎⋆ (˜ 𝑠; 𝑉 ) := arg max 𝑄 𝑠, 𝑎), 𝑎∈𝒜
used in place of max𝑎 𝑄; (S3) the network, online or frozen, at which that score is evaluated for behavior; (S4) a replay law; (S5) an exploration rule; 2
(2)
Deep 𝑉 -Learning: Convergence Framework
(S6) a target construction: WHEN the bootstrap is evaluated (at sampling time, or once at storage time) and FROM which successor (the observed one, or a model prediction). Slots (S3) and (S6) generate the drift and target-construction residuals. Algorithm 1 Deep 𝑉 -learning template for Arun . 1: Input: 𝛾, {𝜀𝑘 , 𝑈𝑘 , 𝑐env 𝑘,𝑗 , 𝑔𝑘,𝑗 }, 𝐵, 𝐵mb , 𝜉𝑘 ; fix normalization and the two switches in (S6) 2: Initialize clipped 𝑉𝜃 , FIFO buffer 𝐸, and 𝑉^ ← 𝑉¯𝜃 ◁ 𝑉0 3: for target period 𝑘 = 0, 1, 2, . . . do 4: Freeze 𝑉𝑘 ← 𝑉^ ; set 𝑉𝜃𝑘,0 ← 𝑉¯𝜃 5: for round 𝑗 = 0, 1, . . . , 𝑈𝑘 − 1 do Collect 𝑐env 6: 𝑘,𝑗 transitions with the online 𝜀𝑘 -greedy score; store raw tuples or stored targets according to (S6), evicting beyond 𝐵 7: for 𝑔𝑘,𝑗 minibatches from 𝐸 do −1 ∑︀ ¯ 2 If SAMPLE, form 𝑦𝑖 = 𝑟𝑖 +𝛾(1−𝑑𝑖 )𝑉^ (succFROM (𝑥𝑖 , a𝑖 , 𝑥′𝑖 )); take one semi-gradient step on 𝐵mb 8: 𝑖 (𝑉𝜃 (𝑥𝑖 )−𝑦𝑖 ) 9: end for 10: end for 11: Copy: 𝑉^ ← 𝑉¯𝜃 ◁ 𝑉𝑘+1 12: end for
Here succOBS (𝑥, a, 𝑥′ ) = 𝑥′ , succPRED (𝑥, a, 𝑥′ ) = 𝑃̂︀(𝑥, a), and a stored target uses both the target network and, for PRED, the predictor installed at collection time. The observed mask makes terminal labels equal their observed rewards. The target network is constant within a period and treated as a constant in the semi-gradient; the behavior network may drift. Generative-reset variant. For Aiid , fix the frozen 𝑉𝑘 , an acting snapshot 𝑊𝑘 ∈ 𝒱 clip , and its 𝜀𝑘 -greedy law 𝛽𝑘 , then draw conditionally independently 𝑆𝑖 ∼ 𝜍,
a𝑖 ∼ 𝛽𝑘 (· | 𝑆𝑖 ),
(𝑟𝑖 , 𝑠˜′𝑖 , 𝑑𝑖 ) ∼ P(· | 𝑆𝑖 , a𝑖 ) fresh,
𝑌𝑖 = 𝑟𝑖 + 𝛾(1 − 𝑑𝑖 )𝑉𝑘 (˜ 𝑠′𝑖 ),
(3)
for 𝑖 ≤ 𝑛𝑘 . Each outcome is used once, and 𝑉𝑘+1 is a measurable 𝜁𝑛𝑘 -approximate ERM over ℱ𝑛𝑉,0 . Here 𝜌𝑘,𝑆 = 𝜍 𝑘 by Assumption 3.4. This defines the generative-reset procedure Aiid in (1). It fits the scalar target generated by the executed action; action-indexed FVI uses a different response [1]. The variant Alev iid samples directly from the slice laws of Theorem 3.19. Score-access convention. A reset call ∫︀ in (3) returns one observed reward–successor pair. Access to the conditional expectation 𝑄𝑉 (˜ 𝑠, 𝑎) = 𝑅(˜ 𝑠, 𝑎) + 𝛾 𝑉 𝑑𝒫(· | 𝑠˜, 𝑎) is represented by the exact-score oracle 𝑄or 𝑉 := 𝑄𝑉 , distinct or ̂︀ from the point score 𝑄𝑉 in (2). Every result using 𝑄 assumes that additional access and replaces slot (S2) by 𝑄or ; exact reward and successor maps provide it for a deterministic model. Otherwise a quantitative score estimator enters the residual bound through 𝜂sc,𝑘 ; Appendix B gives one Monte Carlo bound under the stated stronger query access. We use three histories: ℱ𝑘,𝑗 for literal rounds; ℋ𝑘 for the frozen Aiid objects before its conditionally i.i.d. block; and 𝒥𝑘 for the abstract block. The latter is pre-block information under population accounting and ℬ𝑘 under realized-buffer accounting; for Aiid , 𝒥𝑘 = ℋ𝑘 . Each history is generated by a random element taking values in a standard-Borel space. All design/replay laws and responses in one theorem application are measurable for that same history. Normalization is fixed and every network is clipped by (11). Table 1: Conditioning guide. “Deterministic” means uniform over the histories in the theorem application. Role
Principal symbols
Probability status and use
Histories and frozen objects
ℱ𝑘,𝑗 , ℋ𝑘 , 𝒥𝑘 ; 𝑉𝑘 , 𝑊𝑘 , 𝜌𝑘,𝑆 , 𝐺𝑘
Information before a literal round, a fresh block, or an abstract block; the latter objects are 𝒥𝑘 -measurable. The first two quantities are 𝒥𝑘 -measurable. The fit envelope bounds ¯ exp are a conditional mean; the other five residual envelopes and 𝐷 𝑘 deterministic almost-sure bounds. Deterministic boundary, residual weights, and coverage coefficients. Planned accepted-label allocations, validity thresholds, and statistical and floor constants in Theorem 3.20.
Responses and residuals
𝑎alias,𝑘 , Δ̄exp 𝑘 ; (𝑝)
¯ exp 𝜀fit,𝑘 , 𝜀ker,𝑘 , 𝜀tgt,𝑘 , 𝜀buf,𝑘 , 𝜀act,𝑘 , 𝜀𝑘 𝐷 𝑘 Propagation Terminal-window allocation
(𝐻)
ℬ𝐾 , 𝑤𝐾,𝑘 , 𝑑𝑠 (𝑚), 𝑐lev 2 (𝑚) 𝑛𝑖 , 𝐿𝑖 , N, 𝑏𝑖 , 𝜈, C𝜈,𝐾 , Ψ𝜈 , 𝐹𝐾
3
Deep 𝑉 -Learning: Convergence Framework
2.1
Model assumptions, clipping, and the 𝑉 -backup
Standing assumptions. Throughout, 𝐻 ∈ N,
0 < 𝛾 < 1,
(0) 𝑉max := 0,
0 < 𝑅max < ∞,
(4)
and 2 ≤ |𝒜| < ∞. The physical state space (𝒮, Σ𝒮 ) is nonempty and standard Borel, 𝒜 has the discrete 𝜎-algebra and a fixed total order, and 𝒮̃︀ = (𝒮 × {1, . . . , 𝐻}) ⊔ {˜ 𝑠term } has the corresponding disjoint-union standard-Borel structure. Observation and parameter spaces used below are also standard Borel. Put ∫︁ ∘ ∘ ∘ ̃︀ ̃︀ ̃︀ 𝒮 := 𝒮 ∖ {˜ 𝑠term }, 𝜇𝑆 (𝐵) := 𝜇𝑆 (𝐵 ∩ 𝒮 ), 𝑅(˜ 𝑠, 𝑎) := 𝑟 P(𝑑𝑟, 𝑑˜ 𝑠′ | 𝑠˜, 𝑎). (5) For the next-state marginal 𝒫 of the joint kernel in Assumption 2.1, define, for measurable 𝐵 ⊆ 𝒮̃︀∘ , ∫︁ 𝒫∘ (𝐵 | 𝑠˜, 𝑎) := 𝒫(𝐵 | 𝑠˜, 𝑎), 𝒫∘𝜋 (𝐵 | 𝑠˜) := 𝒫∘ (𝐵 | 𝑠˜, 𝑎) 𝜋(𝑑𝑎 | 𝑠˜).
(6)
𝒜
Thus 𝜇∘𝑆 is a subprobability restriction and 𝒫∘𝜋 is a substochastic kernel that integrates only over the nonterminal space. Values vanish at 𝑠˜term , so 𝐿1 (𝜇𝑆 ) and 𝐿1 (𝜇∘𝑆 ) losses coincide. Function inequalities are pointwise unless a (𝑘) measure is named. The action gap is ∆𝑄 (˜ 𝑠) := max𝑎 𝑄𝑉𝑘 (˜ 𝑠, 𝑎) − max𝑎̸=𝑎tgt (˜𝑠) 𝑄𝑉𝑘 (˜ 𝑠, 𝑎) at the frozen 𝑄𝑉𝑘 , with 𝑘
(𝑘)
𝑎tgt 𝑘 selected by the fixed Borel tie-breaking rule, so that ∆𝑄 = 0 exactly at a tie. For comparison with a fixed optimal-gap hypothesis, write ∆⋆𝑄 (˜ 𝑠) := max 𝑄𝑉 ⋆ (˜ 𝑠, 𝑎) − 𝑎
max
𝑎̸=𝑎⋆ (˜ 𝑠;𝑉 ⋆ )
𝑄𝑉 ⋆ (˜ 𝑠, 𝑎),
(7)
using the same rule; again ∆⋆𝑄 = 0 exactly at an optimal tie. The horizon is 𝐻 steps and the augmented state is 𝑠˜ = (𝑠, ℎ) with ℎ the number of steps remaining. A policy called stationary below is stationary on this augmented state; viewed on the physical state alone, its clock dependence makes it nonstationary. Rewards obey |𝑟| ≤ 𝑅max . For every measurable stationary augmented-state policy 𝜋, let 𝑉 𝜋 be the unique fixed point of 𝒯 𝜋 . Bellman optimality gives 𝑉 ⋆ ≥ 𝑉 𝜋 pointwise, so the expected discounted regret from the evaluation law is exactly ∫︁ ‖𝑉 ⋆ − 𝑉 𝜋 ‖1,𝜇𝑆 = (𝑉 ⋆ − 𝑉 𝜋 ) 𝑑𝜇𝑆 . (8) The level-ℎ value bound and its recursion are 1−𝛾ℎ (𝐻) , 𝑉max := 𝑉max , 1−𝛾 (1 − 𝛾) + 𝛾 − 𝛾 ℎ (ℎ) (ℎ−1) 𝑅max + 𝛾 𝑉max = 𝑅max = 𝑉max (1 ≤ ℎ ≤ 𝐻). 1−𝛾 (ℎ) 𝑉max := 𝑅max
(9) (10)
Equality in (10) is the recursion used to prove that the level-wise band below is 𝒯 -invariant. To agree with terminal masking, work on {︀ }︀ ̃︀ 𝒱 := 𝑉 : 𝒮̃︀ → R bounded and measurable : 𝑉 (˜ 𝑠term ) = 0 ⊂ 𝐵𝑏 (𝒮), ‖𝑉 ‖∞ := sup |𝑉 (˜ 𝑠)|. 𝑠˜
This is a closed Banach subspace of bounded measurable functions [8]. A fixed Borel tie rule supplies measurable greedy selectors. Every network is evaluated through (︀ )︀ (ℎ) (ℎ) 𝑉¯𝜃 (𝑠, ℎ) = clip 𝑉𝜃raw (𝑠, ℎ), −𝑉max , 𝑉max , (11) (ℎ)
whose image is the band 𝒱 clip := {𝑉 ∈ 𝒱 : |𝑉 (𝑠, ℎ)| ≤ 𝑉max ∀(𝑠, ℎ)}. The Bellman optimality operator and the induced one-step 𝑄-function are ∫︁ (𝒯 𝑉 )(˜ 𝑠) := max 𝑄𝑉 (˜ 𝑠, 𝑎), 𝑄𝑉 (˜ 𝑠, 𝑎) := 𝑅(˜ 𝑠, 𝑎) + 𝛾 𝑉 (˜ 𝑠′ ) 𝒫(𝑑˜ 𝑠′ | 𝑠˜, 𝑎), (12) 𝑎∈𝒜
𝜋
and 𝒯 denotes the policy operator obtained by averaging 𝑄𝑉 over 𝜋 instead of maximizing. The next three results establish the clipping property, the 𝑉 -backup identity, and existence of the fixed point 𝑉 ⋆ . 4
Deep 𝑉 -Learning: Convergence Framework
Assumption 2.1 (Markov-sufficient analysis state, joint kernel, and terminal convention [ G ]). Let ℋ𝑡sys denote the full controlled history of the underlying system, including latent variables when the analysis uses them; the resulting analysis state need not be the implemented input. The augmented representation is required to be controlled Markov for the joint reward–successor law: there are a measurable map Ψ and a measurable kernel P(𝑑𝑟, 𝑑˜ 𝑠′ | 𝑠˜, 𝑎) on R × 𝒮̃︀ such that 𝑠˜𝑡 = Ψ(ℋ𝑡sys ) includes the remaining-step clock and, under every admissible control law, for every bounded measurable 𝑓 : R × 𝒮̃︀ → R, ∫︁ sys E[𝑓 (𝑟𝑡 , 𝑠˜𝑡+1 ) | ℋ𝑡 , 𝑎𝑡 ] = 𝑓 (𝑟, 𝑠˜′ ) P(𝑑𝑟, 𝑑˜ 𝑠′ | 𝑠˜𝑡 , 𝑎𝑡 ) a.s. (13) This controlled-kernel identity includes deterministic interventions and does not condition on a possibly zero-probability event {𝑎𝑡 = 𝑎}. Thus histories with the same represented state have the same conditional joint law under every action. This is the Markov-sufficiency requirement; appending a clock supplies the temporal coordinate, while the controlled-kernel identity supplies the required state sufficiency. Rewards satisfy |𝑟| ≤ 𝑅max a.s. Write 𝒫 for the next-state marginal. Every terminating transition has successor 𝑠˜term , and P({0} × {˜ 𝑠term } | 𝑠˜term , 𝑎) = 1. Define the terminal mask as the following function of the successor: 𝑑 := 1{˜ 𝑠′ = 𝑠˜term }.
(14)
The remaining-step coordinate is a genuine clock: from (𝑠, ℎ) with ℎ > 1 every nonterminal successor lies one level lower, while the episode may terminate at any level; from ℎ = 1 absorption is certain, (︁ )︁ (︀ )︀ ⃒⃒ (︀ )︀ P R × (𝒮 × {ℎ − 1}) ∪ {˜ 𝑠term } ⃒ (𝑠, ℎ), 𝑎 = 1 (ℎ > 1), P R × {˜ 𝑠term } | (𝑠, 1), 𝑎 = 1. (15) Hence the substochastic nonterminal kernel 𝒫∘𝜋 of §3.2 is nilpotent, and so is every product of 𝐻 of them: 𝒫∘𝜋1 · · · 𝒫∘𝜋𝐻 = 0 for policies that need not coincide. Lemma 2.2 (Measurable selectors, mixtures, and conditional responses [ G ]). Under the standing standard-Borel assumptions: (i) the fixed-order maximizer of any jointly measurable real score on 𝒮̃︀∘ × 𝒜 is measurable; (ii) a finite state-dependent convex mixture of measurable Markov policies is a measurable Markov policy; ∑︀𝐽 ∑︀ ∑︀ (iii) if M(𝑑˜ 𝑠, 𝑑𝑎) = 𝑗=1 𝜔𝑗 𝜇𝑗 (𝑑˜ 𝑠)𝜋𝑗 (𝑑𝑎 | 𝑠˜) and M𝑆 = 𝑗 𝜔𝑗 𝜇𝑗 , where 𝜔𝑗 ≥ 0 and 𝑗 𝜔𝑗 = 1 (with all these measures and policies possibly depending measurably on a standard-Borel history), then jointly measurable ∑︀ versions 𝑓𝑗 = 𝑑(𝜔𝑗 𝜇𝑗 )/𝑑M𝑆 ∈ [0, 1] may be chosen. With 𝑧 = 𝑗 𝑓𝑗 and any fixed measurable reference policy 𝜋0 , {︃ ∑︀𝐽 𝑧(˜ 𝑠)−1 𝑗=1 𝑓𝑗 (˜ 𝑠)𝜋𝑗 (𝑑𝑎 | 𝑠˜), 𝑧(˜ 𝑠) > 0, 𝜋 ¯ (𝑑𝑎 | 𝑠˜) := (16) 𝜋0 (𝑑𝑎 | 𝑠˜), 𝑧(˜ 𝑠) = 0, is a Markov kernel and a version of the conditional action law M(𝑑𝑎 | 𝑠˜); (iv) every bounded measurable label generated from a standard-Borel history, state, action, and fresh kernel draw admits a measurable conditional-response version 𝐺𝑘 (˜ 𝑠) = E[𝑌𝑘 | 𝑆 = 𝑠˜, 𝒥𝑘 ]. All policies, replay disintegrations, and responses in the sequel refer to these fixed versions. Proof. For finite ordered 𝒜, each selector event is a finite intersection of measurable score comparisons, proving (i); kernel∑︀integration and finite sums give (ii). Since 𝜔𝑗 𝜇𝑗 ≤ M𝑆 , including when 𝜔𝑗 = 0, bounded density versions exist with 𝑗 𝑓𝑗 = 1 M𝑆 -a.e.; substitution against measurable rectangles proves (iii). The parameterized disintegration theorem on standard-Borel spaces supplies the jointly measurable conditional kernel (equivalently the displayed finite mixture weights) and its almost-sure uniqueness. Integrating the bounded label against this kernel proves (iv) [9, Proposition 7.27 and Corollary 7.27.1]. Lemma 2.3 (Level-wise clipping is a projection [ G ]). Let Πclip be the statewise clip of (11). For 𝑔 ∈ 𝒱 clip , |Πclip 𝑓 − 𝑔| ≤ |𝑓 − 𝑔| pointwise; hence it is the 𝐿2 (𝜌) metric projection, is nonexpansive in 𝐿2 (𝜌) and supremum norm, and does not increase covering or Bellman-approximation error. Moreover, 𝑉 ∈ 𝒱 clip
=⇒
(ℎ) |𝑄𝑉 (𝑠, ℎ, 𝑎)| ≤ 𝑉max ,
|𝑌𝑖 | ≤ 𝑉max ,
𝒯 𝑉 ∈ 𝒱 clip .
(17)
These level-wise facts follow from (10); a single global clip need not make the same score and label bounds invariant. Proof: See Appendix A. Lemma 2.4 (Bellman 𝑉 -backup through the induced 𝑄-function [ G ]). Under Assumption 2.1, for every 𝑉 ∈ 𝒱: 5
Deep 𝑉 -Learning: Convergence Framework
(i) if (𝑟, 𝑠˜′ , 𝑑) ∼ P(·, · | 𝑠˜, 𝑎) with mask 𝑑, then E[𝑟 + 𝛾(1 − 𝑑)𝑉 (˜ 𝑠′ ) | 𝑠˜, 𝑎] = 𝑄𝑉 (˜ 𝑠, 𝑎); (ii) (𝒯 𝑉 )(˜ 𝑠) = max𝑎 𝑄𝑉 (˜ 𝑠, 𝑎); (iii) if 𝑎𝑡 = 𝑎⋆ (˜ 𝑠𝑡 ; 𝑉 ) then E[𝑟𝑡 + 𝛾(1 − 𝑑𝑡 )𝑉 (˜ 𝑠𝑡+1 ) | 𝑠˜𝑡 , 𝑎𝑡 ] = (𝒯 𝑉 )(˜ 𝑠𝑡 ); (iv) if 𝑉 ∈ 𝒱 clip and 𝑎𝑡 is 𝜀-greedy for 𝑄𝑉 under exploration law 𝜈, the discrepancy equals 𝜀 times the dispersion of 𝑄𝑉 over 𝜈: ⃒ [︀ ]︀ (𝒯 𝑉 )(˜ 𝑠) − E 𝑟𝑡 + 𝛾(1 − 𝑑𝑡 )𝑉 (˜ 𝑠𝑡+1 ) ⃒ 𝑠˜𝑡 = 𝑠˜ = 𝜀 ∆exp [𝑉, 𝜈](˜ 𝑠) ≥ 0, (18) where ∆exp [𝑉, 𝜈](˜ 𝑠) := max 𝑄𝑉 (˜ 𝑠, 𝑎) −
∫︁ 𝑄𝑉 (˜ 𝑠, 𝑎) 𝜈(𝑑𝑎 | 𝑠˜),
𝑎
(ℎ) 0 ≤ ∆exp [𝑉, 𝜈](𝑠, ℎ) ≤ 2𝑉max .
𝑠term ) = 0; (ii) is the definition; and (iii) follows from (i)–(ii). For (iv), under exploration law Proof. (i) is (12) with 𝑉 (˜ 𝜈, an 𝜀-greedy rule puts mass 1 − 𝜀 on the maximizer and 𝜀 on 𝜈, so by (i) and (ii) (︀ )︀ E[𝑄𝑉 (˜ 𝑠, 𝑎) | 𝑠˜] − max 𝑄𝑉 (˜ 𝑠, 𝑎) = 𝜀 E𝜈 [𝑄𝑉 ] − max 𝑄𝑉 = −𝜀 ∆exp [𝑉, 𝜈](˜ 𝑠), 𝑎
𝑎
which is (18). Its sign is fixed because the maximum dominates any average. For the statewise range, the successor of a (ℎ−1) (ℎ) state at level ℎ lies at level ℎ−1 or is terminal, so the level recursion (10) gives |𝑄𝑉 (𝑠, ℎ, 𝑎)| ≤ 𝑅max +𝛾𝑉max = 𝑉max (ℎ) and hence ∆exp [𝑉, 𝜈](𝑠, ℎ) ∈ [0, 2𝑉max ]. Lemma 3.13 uses this identity. The upper endpoint is attained only where the (ℎ) (ℎ) maximum score equals 𝑉max and 𝜈 concentrates on actions whose score is −𝑉max . Remark 2.5 (Executed-transition targets and action-indexed heads [ R ]). The operator analysis needs only (E1) E[𝑌 | 𝑠˜, 𝑎] = 𝑄𝑢𝑘 (˜ 𝑠, 𝑎) for the executed action and (E2) a state-only regressand, whose response is 𝒯 𝛽 𝑢𝑘 = ∫︀ 𝑄𝑢𝑘 (·, 𝑎)𝛽(𝑑𝑎 | ·). It separates consistency ‖𝐺𝑘 − 𝒯 𝛽 𝑢𝑘 ‖ from optimality ‖𝒯 𝛽 𝑢𝑘 − 𝒯 𝑢𝑘 ‖. Thus the abstract results extend to any head satisfying (E1)–(E2). A 𝑄-head and Expected SARSA index the regressand by the action and therefore fall outside (E2). One-step state-value TD satisfies it and evaluates 𝒯 𝛽 unless policy improvement is added. The routed scalar-output entropy bound in Section 5 includes the 𝐻-head factor in (86) and no output-coordinate factor |𝒜|; its approximation constants may still depend on the action set. Lemma 2.6 (Existence and uniqueness of 𝑉 ⋆ [ G ]). Under Assumption 2.1 the operator 𝒯 is a 𝛾-contraction on 𝒱 (ℎ) and leaves 𝒱 clip invariant, so it has a unique fixed point 𝑉 ⋆ ∈ 𝒱 clip , with |𝑉 ⋆ (𝑠, ℎ)| ≤ 𝑉max at every level, and ∑︀ ⋆ 𝑡 𝑉 (˜ 𝑠) = sup𝜋 E𝜋 [ 𝑡≥0 𝛾 𝑅𝑡 | 𝑠˜0 = 𝑠˜]. ∫︀ Proof. For 𝑉, 𝑊 ∈ 𝒱, finiteness of 𝒜 and kernel integration give |𝒯 𝑉 (˜ 𝑠) − 𝒯 𝑊 (˜ 𝑠)| ≤ 𝛾 max𝑎 |𝑉 − 𝑊 | 𝑑𝒫 ≤ ̃︀ so Banach’s theorem gives 𝛾‖𝑉 − 𝑊 ‖∞ . The terminal convention makes 𝒱 a closed, complete subspace of 𝐵𝑏 (𝒮), a unique fixed point; invariance from Lemma 2.3 puts it in 𝒱 clip . Backward induction over the clock bounds every history-dependent randomized policy by this recursion, and the measurable greedy selector attains it [9–11].
3
Residual decomposition and policy-loss propagation
3.1
Coverage and residuals
Residuals are measured under replay marginals 𝜌𝑘,𝑆 , while policy loss is evaluated from 𝜇𝑆 . Concentrability bounds the density ratios between the state distributions reached from 𝜇𝑆 and the replay laws. One way to verify Assumption 3.3 is domination by a reset law 𝜍: 𝜇∘𝑆 𝒫∘𝜋1 · · · 𝒫∘𝜋𝑚 ≤ ¯𝑏 𝜍
for all 1 ≤ 𝑚 ≤ 𝐻 and all policy sequences,
(19)
then any replay law of the mixture form 𝜌𝑘,𝑆 := (1 − 𝜅)𝜎𝑘,𝑆 + 𝜅𝜍,
𝜅 ∈ (0, 1],
(20)
satisfies 𝜌𝑘,𝑆 ≥ 𝜅𝜍 and therefore 𝑐2,𝑘 (𝑚) ≤ ¯𝑏/𝜅. Finite coverage requires reset mass on every reachable clock slice; Proposition 3.6 quantifies the cost when one probability law covers all slices. Sampling i.i.d. from the mixture (20) requires arbitrary-state reset access or a snapshot-replay oracle; under Aiid , Assumption 3.4 fixes 𝜌𝑘,𝑆 = 𝜍. Lemma 3.10 pairs an 𝐿𝑝 (𝜌𝑘,𝑆 ) residual with an 𝐿𝑠 (𝜌𝑘,𝑆 ) density, and the same conjugate Hölder pairing determines the margin exponent in Proposition 5.6. 6
Deep 𝑉 -Learning: Convergence Framework
The residuals are defined as envelopes over one block. Let ℐ𝑘opt index the gradient updates in block 𝑘 and let ℐ𝑘act index every online-network snapshot actually used to select a collection action, including the initial and any post-update snapshots that act. Put ℐ𝑘 = ℐ𝑘opt ∪ ℐ𝑘act . With 𝒟 := 𝒮̃︀∘ × 𝒜 as the common comparison domain, sup ‖𝑉𝜃𝑘,𝑡 − 𝑉𝑘 ‖∞ ≤ 𝛿𝑉,𝑘 ,
𝑡∈ℐ𝑘act
sup
⃒ ⃒ ̂︀ 𝑉 (˜ sup ⃒𝑄 𝑠, 𝑎) − 𝑄𝑉 (˜ 𝑠, 𝑎)⃒ ≤ 𝜂sc,𝑘 ,
(21)
𝑉 ∈ℱ (˜ 𝑠,𝑎)∈𝒟
⃦ 𝛽 rep ⃦ ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘on 𝑉𝑘 ⃦ 2,𝜌
𝑘,𝑆
≤ 𝜀buf,𝑘 ,
¯ exp ≤ 𝐷 ¯ exp . ∆ 𝑘 𝑘
These are network drift, score error, replay shift, and exploration dispersion. The symmetric class ℱ ⊆ 𝒱 clip contains ⋃︀ every frozen iterate, every acting snapshot, and their negatives (e.g. ± 𝑛 ℱ𝑛𝑉 ). Restriction to ℱ is essential: over the full clipped band, fixed kernel mass away from a point prediction can make the continuation error Ω(𝑉max ) even with ̂︀ 𝑉 exact rewards. The unindexed 𝜂sc := sup𝑘 𝜂sc,𝑘 denotes a deterministic uniform envelope when finite. The notation 𝑄 suppresses a possible block index on the learned model; a fixed implemented model has constant 𝜂sc,𝑘 . In (21) and the ̂︀ denotes the score installed in slot (S2): the point score for Arun and for the point-score Aiid analysis, action section, 𝑄 or the distinct 𝑄or only in statements explicitly tagged as oracle results. Proposition 3.1 concerns the point-score case. Proposition 3.1 (Dispersion control of the implemented score [ G ]). Suppose each nonterminal clock slice carries a metric dist whose distance map is jointly measurable, the displayed conditional distances are integrable, and every 𝑉 ∈ ℱ has the same nondecreasing concave modulus 𝜔 on that slice, with 𝜔(0) = 0. Suppose also that termination condition (T) of Lemma 3.2 holds pointwise on 𝒟, and that the point model respects the clock and terminal conventions. With 𝑅(˜ 𝑠, 𝑎) := E[𝑟 | 𝑠˜, 𝑎], the block score error satisfies (︁ ⃒ ⃒ ⃒ ⃒ [︀ (︀ )︀ ⃒ ]︀)︁ ̂︀ 𝑉 (˜ ̂︀ 𝑠, 𝑎)−𝑅(˜ sup sup ⃒𝑄 𝑠, 𝑎)−𝑄𝑉 (˜ 𝑠, 𝑎)⃒ ≤ sup ⃒𝑅(˜ 𝑠, 𝑎)⃒ + 𝛾 𝜔 sup E dist 𝑠˜′ , 𝑃̂︀(˜ 𝑠, 𝑎) ⃒ 𝑠˜, 𝑎 . (22) 𝑉 ∈ℱ (˜ 𝑠,𝑎)∈𝒟
(˜ 𝑠,𝑎)∈𝒟
(˜ 𝑠,𝑎)∈𝒟
Consequently any deterministic almost-sure majorant of the right-hand side is an admissible choice of 𝜂sc,𝑘 in (21). Proof. At terminal pairs both continuations vanish. Otherwise 𝑠˜′ and 𝑃̂︀(˜ 𝑠, 𝑎) lie on the same clock slice, so for every 𝑉 ∈ ℱ, (︁ )︁ (︁ )︁ ̂︀ 𝑉 − 𝑄𝑉 | ≤ |𝑅 ̂︀ − 𝑅| + 𝛾E𝜔 dist(˜ ̂︀ − 𝑅| + 𝛾𝜔 Edist(˜ |𝑄 𝑠′ , 𝑃̂︀(˜ 𝑠, 𝑎)) ≤ |𝑅 𝑠′ , 𝑃̂︀(˜ 𝑠, 𝑎)) by concavity and Jensen. Take the suprema over 𝑉 and 𝒟. ̂︀ − 𝑅| + 𝛾𝜔(sup𝒟 ‖𝑃̂︀ − 𝐹 ‖). For stochastic dynamics, For deterministic dynamics Proposition 3.1 becomes sup𝒟 |𝑅 dispersion enlarges only this upper bound. The common modulus is an equicontinuity assumption on ℱ, imposed separately from finite ReLU representation. ¯ exp are deterministic almost-sure envelopes. Write 𝑍 = (𝑟, 𝑠˜′ , 𝑑) for a selected record’s All six residual bounds and 𝐷 𝑘 outcome and 𝑀𝑘 for its standard-Borel label-construction metadata, so that 𝑌𝑘 = ℓ𝑘 (𝑆, a, 𝑀𝑘 , 𝑍) for a bounded measurable label map fixed by 𝒥𝑘 . For stored labels, 𝑀𝑘 includes the target-copy age and the network parameters and, for PRED, predictor parameters used at writing; these are accounting variables and need not all be retained in the buffer. No independence between 𝑀𝑘 and 𝑍 is assumed. For sample-time labels whose network and predictor are fixed by 𝒥𝑘 , 𝑀𝑘 may be constant. Let 𝐺𝑘 be a chosen version of E[𝑌𝑘 | 𝑆, 𝒥𝑘 ]. Define its ideal counterpart by retaining (𝑆, a, 𝑀𝑘 ) and redrawing only the outcome: ℒ(𝑍 ∘ | 𝑆, a, 𝑀𝑘 , 𝒥𝑘 ) = P(· | 𝑆, a), 𝐺ideal (𝑆) := E[ℓ𝑘 (𝑆, a, 𝑀𝑘 , 𝑍 ∘ ) | 𝑆, 𝒥𝑘 ]. 𝑘
(23)
The laws 𝜌𝑘,𝑆 , 𝛽𝑘rep and both responses are 𝒥𝑘 -measurable. The fit link is controlled in conditional mean; the other five links are controlled almost surely by their displayed deterministic envelopes. Thus ⃒ ]︀ [︀ E ‖𝑉𝑘+1 − 𝐺𝑘 ‖2,𝜌𝑘,𝑆 ⃒ 𝒥𝑘 ≤ 𝜀fit,𝑘 (fit: the solver against its own response), (24) ⃦ ⃦ ⃦𝐺𝑘 − 𝐺ideal ⃦ ≤ 𝜀ker,𝑘 (kernel realization: reuse of realized outcomes), (25) 𝑘 2,𝜌𝑘,𝑆 ⃦ ideal ⃦ rep ⃦𝐺𝑘 − 𝒯 𝛽𝑘 𝑉𝑘 ⃦ ≤ 𝜀tgt,𝑘 (target construction: the switches of slot (S6)), (26) 2,𝜌 𝑘,𝑆
7
Deep 𝑉 -Learning: Convergence Framework
Under population-law accounting, suppose that a selected record satisfies the following conditional kernel-retention hypothesis, including the label-construction metadata: for every bounded measurable 𝑓 , ∫︁ [︀ ]︀ E 𝑓 (𝑟, 𝑠˜′ , 𝑑) | 𝑆, a, 𝑀𝑘 , 𝒥𝑘 = 𝑓 dP(· | 𝑆, a) a.s. (27) Conditioning first on (𝑆, a, 𝑀𝑘 , 𝒥𝑘 ) and then averaging shows that 𝐺𝑘 = 𝐺ideal , so 𝜀ker,𝑘 = 0. For the current 𝑘 observed-successor label, the tower property also gives the replayed operator, ⃒ [︀ ]︀ rep E 𝑟 + 𝛾(1 − 𝑑)𝑉𝑘 (˜ 𝑠′ ) ⃒ 𝑆 = 𝑠˜, 𝒥𝑘 = (𝒯 𝛽𝑘 𝑉𝑘 )(˜ 𝑠), (28) where 𝒥𝑘 is pre-block information. For sample-time labels fixed by 𝒥𝑘 , conditioning only on (𝑆, a, 𝒥𝑘 ) in (27) suffices. For stored labels it need not suffice: record age or writing-time parameters can remain correlated with the selected outcome. The full condition holds for a fresh true-kernel draw made after the metadata are fixed. A sample-splitting or outcome-independent retention argument must establish this conditional law given both the chosen history and the metadata; it must be verified for adaptive FIFO replay. Under realized-buffer accounting, 𝒥𝑘 = ℬ𝑘 and 𝜀ker,𝑘 measures the empirical response’s deviation from its fresh-outcome counterpart, ready for a process-specific replay bound. For Aiid , 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 0. Lemma 3.2 gives the target-switch accounting: (SAMPLE, OBS) has zero target residual, while STORE charges conditional target-network staleness and PRED charges current continuation-score error (plus its stated terminalmask correction). Their combination also charges any change between the writing-time and current predictors. An executed-transition target therefore pays behavior, online-action, and exploration links. A model-built target ̂︀ 𝑠, 𝑎) + 𝛾𝑉𝑘 (𝑃̂︀(˜ max𝑎 {𝑅(˜ 𝑠, 𝑎))} removes those links but inserts score error into every target; neither design is uniformly preferred. The replay residual 𝜀buf,𝑘 is a same-state operator distance. Lemma 3.2 (Target-switch envelope [ R ]). Let 𝐴 ∈ {0, . . . , 𝑘} be a replayed record’s age in target copies and 𝛿¯𝑘 (𝐴) := ‖𝑉𝑘 − 𝑉𝑘−𝐴 ‖∞ . Write 𝑃̂︀𝑘 for the current predictor fixed by 𝒥𝑘 (the block index previously suppressed) and 𝑃̂︀write for the predictor used to construct a stored prediction label, identified by 𝑀𝑘 . Its version need not be determined by 𝐴. For this cell define ⃒⃒ [︁⃒ ]︁ ⃒ ⃒ 𝐶pred,𝑘 (˜ 𝑠) := 𝛾 E ⃒𝑉𝑘 (𝑃̂︀write (𝑆, a)) − 𝑉𝑘 (𝑃̂︀𝑘 (𝑆, a))⃒ ⃒ 𝑆 = 𝑠˜, 𝒥𝑘 . (29) cont := sup𝑉 ∈ℱ ,˜𝑠,𝑎 𝛾|𝑉 (𝑃̂︀𝑘 (˜ 𝑠, 𝑎)) − This 𝑘 ∫︀ quantity vanishes for a fixed predictor; set it to zero in the other cells. Let 𝜂cont 𝑉 𝑑𝒫(· | 𝑠˜, 𝑎)|. When the point score is installed in slot (S2), symmetry gives 𝜂𝑘 ≤ 𝜂sc,𝑘 ; under other score access it remains a separate target-construction quantity. If the terminal event is determined by (˜ 𝑠, 𝑎), then the four cells of slot (S6) satisfy rep
‖𝐺ideal − 𝒯 𝛽𝑘 𝑉𝑘 ‖2,𝜌𝑘,𝑆 ≤ 1{FROM = PRED}𝜂𝑘cont 𝑘 + 1{WHEN = STORE}𝛾‖E[𝛿¯𝑘 (𝐴) | 𝑆, 𝒥𝑘 ]‖2,𝜌𝑘,𝑆
(30)
+ 1{(WHEN, FROM) = (STORE, PRED)}‖𝐶pred,𝑘 ‖2,𝜌𝑘,𝑆 . In the general termination case, the predicted-successor cells add ‖𝐶mask,𝑘 ‖2,𝜌𝑘,𝑆 , where ∫︁ 𝐶mask,𝑘 (˜ 𝑠) := 𝛾 Pr(𝑑 = 1 | 𝑠˜, 𝑎)|𝑉𝑘 (𝑃̂︀𝑘 (˜ 𝑠, 𝑎))| 𝛽𝑘rep (𝑑𝑎 | 𝑠˜). Thus the replay-action average is taken before the state norm, and both staleness quantities remain conditional on 𝑆 and 𝒥𝑘 . Any deterministic almost-sure majorant of the resulting right-hand side is an admissible 𝜀tgt,𝑘 . Proof: See Appendix A. path snap ¯ exp Finally, 𝛿𝑉,𝑘 , 𝛿𝑉,𝑘 , ∆𝑘 , and realized fit errors are random. The symbols 𝛿𝑉,𝑘 , 𝜂sc,𝑘 , 𝜂sc , and 𝜂sc,𝐾 are deterministic, (𝑟) ¯ exp , and Λ𝑘 . Random quantities enter later bounds only inside as are 𝜀fit,𝑘 , 𝜀ker,𝑘 , 𝜀tgt,𝑘 , 𝜀buf,𝑘 , 𝜀act,𝑘 for 1 ≤ 𝑟 ≤ 2, 𝐷 𝑘 expectations or through such envelopes.
3.2
Concentrability and finite-horizon propagation
Assumption 3.3 (Finite-horizon 𝐿𝑠 concentrability of population replay [ R ]). Fix 𝑠 ∈ [2, ∞] and let 𝑝 = 𝑠/(𝑠−1), with 𝑝 = 1 when 𝑠 = ∞. For every 1 ≤ 𝑚 ≤ 𝐻 and every sequence 𝜋1 , . . . , 𝜋𝑚 of randomized Markov policies (measurable kernels from 𝒮̃︀∘ into the simplex over 𝒜, including deterministic selectors), assume 𝜇∘𝑆 𝒫∘𝜋1 · · · 𝒫∘𝜋𝑚 ≪ 𝜌𝑘,𝑆 and set ⃦ ∘ 𝜋1 𝜋 𝑚 ⃦ ⃦ 𝑑(𝜇 𝒫∘ ···𝒫∘ ) ⃦ 𝑑𝑠,𝑘 (𝑚) := sup ⃦ 𝑆 𝑑𝜌 . (31) ⃦ 𝑘,𝑆 𝑠,𝜌𝑘,𝑆
𝜋1 ,...,𝜋𝑚
8
Deep 𝑉 -Learning: Convergence Framework
We assume the pathwise form (C-strong): a deterministic 𝑑𝑠 (𝑚) < ∞ with 𝑑𝑠,𝑘 (𝑚) ≤ 𝑑𝑠 (𝑚) almost surely for all 𝑘; by clock nilpotence take 𝑑𝑠 (𝐻) = 0. The supremum in (31) is pointwise over all policy sequences: after a history is fixed it therefore includes policies selected from that history, although every factor remains a Markov kernel in the current state. Define (𝐻)
𝜑𝑠,𝐾 :=
𝐻−1 ∑︁
(𝐻)
min{𝐾, 𝑚}𝛾 𝑚 𝑑𝑠 (𝑚),
𝜑(𝐻) := 𝜑𝑠,𝐻−1 = 𝑠
𝑚=1
𝐻−1 ∑︁
𝑚𝛾 𝑚 𝑑𝑠 (𝑚).
(32)
𝑚=1 (𝐻)
(𝐻)
At 𝑠 = 2 write 𝑐2,𝑘 (𝑚) := 𝑑2,𝑘 (𝑚)2 , 𝑐2 (𝑚) := 𝑑2 (𝑚)2 , and 𝜑𝜇𝑆 ,𝜌 := 𝜑2 ; at 𝑠 = ∞ write 𝑐∞ (𝑚) := 𝑑∞ (𝑚). Hölder pairs the density with an 𝐿𝑝 (𝜌𝑘,𝑆 ) residual. Existing 𝐿2 envelopes for the nonaction links remain valid because 𝑝 ≤ 2 and 𝜌𝑘,𝑆 is a probability law; the action link may use its sharper 𝑝-specific envelope. Assumption 3.4 (Generative reset access [ Aiid , Alev iid ]). For Aiid , the simulator can be reset to a state drawn from the ∘ ̃︀ designer’s single reset law 𝜍 on 𝒮 , after which one behavior-policy action is executed and one true-kernel transition is (ℎ) observed. For Alev iid , it can be reset independently to each 𝒥𝑘 -measurable clock-slice law 𝜌𝑘,𝑆 specified in Theorem 3.19. These are distinct access assumptions. If slice laws are obtained by rejection from 𝜍, rejected draws must be added to the sample count; Theorem 3.19 counts direct slice-reset draws only. Definition 3.5 (Top-slice evaluation and horizon-indexed families [ G ]). For a fixed horizon 𝐻, top-slice evaluation means 𝜇𝑆 (𝒮 × {𝐻}) = 1. (33) A horizon-indexed family {ℐ𝐻 }𝐻≥2 consists of one instance of the augmented model and its evaluation/design objects for each 𝐻, with discount 𝛾𝐻 , iteration index 𝐾𝐻 , evaluation law 𝜇𝑆,𝐻 , replay laws 𝜌𝑘,𝑆,𝐻 , survival masses 𝑞𝐻,𝑚 , and concentrability envelopes 𝑑𝑠,𝐻 (𝑚). Within a fixed member, the 𝐻 subscripts are suppressed. Every asymptotic symbol in 𝐻 refers to this family, and every constant declared uniform is independent of 𝐻. The family is near-unit-discount when (1 − 𝛾𝐻 )𝐻 → κ ∈ [0, ∞), and is fixed-discount when 𝛾𝐻 ≡ 𝛾 for one 𝛾 ∈ (0, 1). Theorem 3.6 (Finite-𝐾 𝐿𝑠 /𝐿𝑝 clock tradeoff [ R ]). Assume (C-strong), top-slice evaluation in the sense of Definition 3.5, 𝐻 ≥ 2, and 𝐾 ≥ 1. For 𝜇𝜋𝑚1:𝑚 := 𝜇∘𝑆 𝒫∘𝜋1 · · · 𝒫∘𝜋𝑚 , set 𝑞𝑚 := sup𝜋1:𝑚 𝜇𝜋𝑚1:𝑚 (𝒮̃︀∘ ), 𝑎𝐾,𝑚 := min{𝐾, 𝑚}𝛾 𝑚 , and 𝜃 := 𝑝/(𝑝 + 1) (equivalently 𝑠/(2𝑠 − 1) for finite 𝑠, and 1/2 at 𝑠 = ∞). Every shared design law satisfies {︃𝐻−1 }︃1/𝜃 𝐻−1 ∑︁ (︂ 𝑞𝑚 )︂𝑝 ∑︁ (𝐻) 𝜃 ≤ 1, 𝜑𝑠,𝐾 ≥ (𝑎𝐾,𝑚 𝑞𝑚 ) . (34) 𝑑𝑠 (𝑚) 𝑚=1 𝑚=1 Zero-survival coordinates are omitted. The second bound is an exact relaxation: on the deterministic one-state-per-level chain with 𝑞𝑚 = 1, the 𝐾-specific clock masses 𝑎𝜃𝐾,𝑚 𝑟𝐻−𝑚 = ∑︀𝐻−1 𝜃 𝑗=1 𝑎𝐾,𝑗
(35)
−1/𝑝
give 𝑑𝑠 (𝑚) = 𝑟𝐻−𝑚 and equality in (34). Proof. The depth-𝑚 law is supported on 𝐿𝑚 = 𝒮 × {𝐻 − 𝑚}. If 𝑟𝐻−𝑚 = 𝜌𝑘,𝑆 (𝐿𝑚 ) and 𝑓𝑚 is its density, slice1/𝑝 1/𝑝 supported Hölder gives 𝑞𝑚 ≤ ‖𝑓𝑚 ‖𝑠 𝑟𝐻−𝑚 ≤ 𝑑𝑠 (𝑚)𝑟𝐻−𝑚 ; summing over the disjoint slices proves the first inequality. Applying Hölder with exponents 1/𝜃 and 𝑝 + 1 to (𝑎𝐾,𝑚 𝑑𝑠 (𝑚))𝜃 (𝑞𝑚 /𝑑𝑠 (𝑚))𝜃 proves the second. On the stated chain the depth law is a point mass on its unique slice, so substitution of (35) gives equality. Corollary 3.7 (Sharp horizon regimes for the shared-law clock coefficient [ R ]). Apply Theorem 3.6 to a top-slice horizon-indexed family and assume the uniform survival floor inf 𝐻≥2 inf 1≤𝑚<𝐻 𝑞𝐻,𝑚 ≥ 𝑞 > 0. (a) In the near-unit-discount regime, if 𝐾𝐻 /𝐻 → 𝜏 ∈ (0, ∞], every shared design law obeys {︂∫︁ 1 }︂1/𝜃 (𝐻) 3−1/𝑠 𝜃 −κ𝜃𝑥 𝜑𝑠,𝐾𝐻 ≥ 𝑞𝐴𝑠,𝜏 (κ)𝐻 (1 + 𝑜(1)), 𝐴𝑠,𝜏 (κ) := min{𝜏, 𝑥} 𝑒 𝑑𝑥 ,
(36)
0
where min{∞, 𝑥} = 𝑥. (b) In the same near-unit-discount regime, if instead 1 ≤ 𝐾𝐻 = 𝑜(𝐻), every shared law obeys the order Ω(𝐾𝐻 𝐻 2−1/𝑠 ). 9
Deep 𝑉 -Learning: Convergence Framework
(c) In the fixed-discount regime, the sharp shared-law relaxation is Θ(1) for every sequence 𝐾𝐻 ≥ 1, whereas the uniform 𝐻-slice law on the one-state-per-level family has order Θ(𝐻 1−1/𝑠 ). The deterministic one-state-per-level family has 𝑞𝐻,𝑚 = 1, and its 𝐾𝐻 -specific law (35) attains the orders in (a)–(c). Thus each order is best possible for the shared-law clock-coefficient problem of Theorem 3.6. ∑︀ Proof. For (a), divide 𝑚<𝐻 𝑎𝜃𝐾𝐻 ,𝑚 by 𝐻 1+𝜃 and use the Riemann sum in (36); (1 + 𝜃)/𝜃 = 3 − 1/𝑠. For 1+𝜃 𝜃 𝐾𝐻 = 𝑜(𝐻), split at 𝑚 = 𝐾𝐻 : the tail is Θ(𝐾𝐻 𝐻) and dominates the 𝑂(𝐾𝐻 ) initial part, proving ∑︀ (b). Theorem 3.6 gives both lower bounds and its one-state family gives equality. For (c), 𝑎𝐾𝐻 ,𝑚 ≤ 𝑚𝛾 𝑚 makes 𝑚 𝑎𝜃𝐾𝐻 ,𝑚 uniformly finite and bounded away from zero. The 𝐾𝐻 -specific masses attain this constant order, while the uniform clock law has 𝑑𝑠 (𝑚) = 𝐻 1/𝑝 and a weight sum uniformly bounded above and away from zero, giving 𝐻 1/𝑝 = 𝐻 1−1/𝑠 . Corollary 3.8 (Endpoint attainment and direct-level comparison [ R ]). For the deterministic one-state-per-level family 𝑚 2/3 in the near-unit-discount regime with 𝐾𝐻 ≥ 𝐻 − 1, the attaining masses in (35) are proportional to (𝑚𝛾𝐻 ) at 𝑚 1/2 5/2 𝑠 = 2 and to (𝑚𝛾𝐻 ) at 𝑠 = ∞. These attain the optimal shared-law propagation-coefficient orders 𝐻 and 𝐻 3 , respectively. The uniform 𝐻-slice law on the same family has the same orders, with different constants. Under the distinct direct-level-reset access model, uniformly bounded 𝐿2 level coefficients give propagation coefficient 𝑂(𝐻 2 ). Theorem 3.19 formalizes the distinct sampling scheme that pairs each propagated depth with its own clock-slice law. Lemma 3.9 (Comparison kernel for the absolute Bellman difference [ G ]). Let 𝑉, 𝑊 ∈ 𝒱 and ∆𝑉,𝑊 := 𝑉 − 𝑊 . There exists a measurable substochastic Markov kernel 𝒫∘𝑉,𝑊 on 𝒮̃︀∘ such that, pointwise on 𝒮̃︀∘ , (︀ )︀ |𝒯 𝑉 − 𝒯 𝑊 |(˜ 𝑠) ≤ 𝛾 𝒫∘𝑉,𝑊 |∆𝑉,𝑊 | (˜ 𝑠). Moreover, 𝒫∘𝑉,𝑊 may be chosen as the kernel 𝒫∘𝜋 of a measurable deterministic policy 𝜋 that selects pointwise between the greedy selectors 𝑎⋆ (·; 𝑉 ) and 𝑎⋆ (·; 𝑊 ). Proof. Put 𝑎𝑉 := 𝑎⋆ (·; 𝑉 ) and 𝑎𝑊 := 𝑎⋆ (·; 𝑊 ), and write 𝑃𝑎 := 𝒫∘ (· | 𝑠˜, 𝑎). Optimality gives ∫︁ (𝒯 𝑉 − 𝒯 𝑊 )(˜ 𝑠) ≤ 𝛾 |∆𝑉,𝑊 | 𝑑𝑃𝑎𝑉 (˜𝑠) , ∫︁ (𝒯 𝑊 − 𝒯 𝑉 )(˜ 𝑠) ≤ 𝛾 |∆𝑉,𝑊 | 𝑑𝑃𝑎𝑊 (˜𝑠) . Choose at each state whichever nonnegative integral is larger. Kernel integration and the two Borel selectors make this choice measurable. The result is a deterministic policy kernel that dominates both one-sided bounds. Thus (31) covers every product formed below, although the policies in a product need not coincide. Each transition between nonterminal states reduces the remaining horizon, so a product of 𝐻 nonterminal transition kernels is zero. This truncates error propagation and gives the finite update window in the following lemma. Lemma 3.10 (Finite-horizon residual propagation [ R ]). Assume 2.1 and 3.3. Let 𝑉0 , . . . , 𝑉𝐾 ∈ 𝒱 satisfy ‖𝑉𝑘 ‖∞ ≤ 𝑉max , set 𝑒𝑘 := 𝑉𝑘+1 − 𝒯 𝑉𝑘 , let 𝐾 ≥ 1, and let 𝜋𝐾 be greedy with respect to 𝑉𝐾 . Put 𝑝ℎ := 𝜇∘𝑆 (𝒮 × {ℎ}) and choose deterministic 𝐷0,ℎ such that sup |𝑉 ⋆ (𝑠, ℎ) − 𝑉0 (𝑠, ℎ)| ≤ 𝐷0,ℎ almost surely. 𝑠∈𝒮 (ℎ)
The global bound permits 𝐷0,ℎ = 𝑉max + 𝑉max ; for deterministic 𝑉0 , one may use its actual slice error. Define the deterministic initialization envelope ℬ𝐾 := 2
𝐻 ∑︁ ℎ=1
𝑝ℎ
ℎ−1 ∑︁
𝛾 𝑚 𝐷0,ℎ−𝑚 .
(37)
𝑚=𝐾+1
With deterministic weights (𝐻)
𝑤𝐾,𝑘 := 2
∑︁
𝛾 ℓ+𝐾−𝑘 𝑑𝑠 (ℓ + 𝐾 − 𝑘),
0 ≤ 𝑘 < 𝐾,
(38)
ℓ≥0: 1≤ℓ+𝐾−𝑘<𝐻
the following bound holds pathwise: ‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 +
𝐾−1 ∑︁
(𝐻)
𝑤𝐾,𝑘 ‖𝑒𝑘 ‖𝑝,𝜌𝑘,𝑆 ,
𝑘=max{0,𝐾−𝐻+1}
10
𝐾−1 ∑︁ 𝑘=0
(𝐻)
(𝐻)
𝑤𝐾,𝑘 = 2𝜑𝑠,𝐾 .
(39)
Deep 𝑉 -Learning: Convergence Framework
For top-slice evaluation, 𝐻−1 ∑︁
ℬ𝐾 = 2 If 𝑉0 ∈ 𝒱
clip
𝛾 𝑚 𝐷0,𝐻−𝑚 .
𝑚=𝐾+1 (ℎ) almost surely, choosing 𝐷0,ℎ = 2𝑉max gives
ℬ𝐾 ≤ 4
𝐻−1 ∑︁
(𝐻−𝑚) 𝛾 𝑚 𝑉max .
𝑚=𝐾+1
In all cases, ℬ𝐾 = 0 for 𝐾 ≥ 𝐻 − 1. Proof roadmap. Lemma 3.9 gives the one-step comparison recursion. Unrolling it and applying the nonnegative loss resolvent produces two policy-kernel branches of total depth 𝑚 = ℓ + 𝐾 − 𝑘. Clock nilpotence removes 𝑚 ≥ 𝐻; Hölder and Assumption 3.3 give the stated weights, while counting the min{𝐾, 𝑚} admissible indices gives their sum. Appendix A supplies the pathwise occupancy construction and the deterministic initialization-envelope bound. 3.3
Residual definitions and composition
Assumption 3.11 (Behavior policies, the replay residual, and the online-action residual [ R ]). (Behavior.) The data of block 𝑘 is collected by 𝜀𝑘 -greedy policies whose greedy branch is the one implemented in Algorithm 1: it maximizes the ̂︀ 𝑉 of (2) at the acting network. The oracle consistency results use the separate true conditionalpoint-model score 𝑄 expectation score 𝑄or 𝑉 . The action analysis applies to either choice through its generic perturbation score 𝑞𝑘 . For Aiid there is one such policy, the snapshot law 𝛽𝑘 built from 𝑊𝑘 . For Arun there is one per round, and the period-level object 𝜋 ¯𝑘on is obtained by disintegration of the joint collection measure, ∑︁ on M𝑘 (𝑑˜ 𝑠, 𝑑𝑎) = 𝜔𝑘,𝑗 𝜇𝑘,𝑗 (𝑑˜ 𝑠) 𝜋𝑘,𝑗 (𝑑𝑎 | 𝑠˜) = M𝑘,𝑆 (𝑑˜ 𝑠) 𝜋 ¯𝑘on (𝑑𝑎 | 𝑠˜), (40) 𝑗
𝜔𝑘,𝑗 being the sample share and 𝜇𝑘,𝑗 the state law of round 𝑗. The weights of 𝜋 ¯𝑘on are state-dependent: a time average on of the 𝜋𝑘,𝑗 is in general not the conditional action law of the collected data. Fix the density-weighted version from Lemma 2.2 M𝑘,𝑆 -a.e. and its declared measurable mixture extension on the M𝑘,𝑆 -null complement; use the same convention for 𝛽𝑘rep below. If 𝜌𝑘,𝑆 charges that null complement, the disintegration identity alone imposes no relation there. Therefore, for Arun , require 𝜌𝑘,𝑆 ≪ M𝑘,𝑆 whenever 𝜋 ¯𝑘on is compared under 𝜌𝑘,𝑆 ; the fixed extension then serves only measurability and cannot change any displayed residual norm. Write 𝜋𝑘on for 𝛽𝑘 under Aiid and for 𝜋 ¯𝑘on under tgt Arun , and 𝜋𝑘 for the 𝜀𝑘 -greedy policy whose greedy branch maximizes the true 𝑄𝑉𝑘 ; all share 𝜀𝑘 and 𝜉𝑘 . (The two residuals.) Let 𝛽𝑘rep be the conditional action law of the distribution actually replayed. Every operator written rep 𝒯 𝛽𝑘 refers to this law, and 𝛽𝑘rep = 𝛽𝑘 for Aiid , whose outcomes are fresh and used once. For each block 𝑘, let the (𝑟) deterministic block-indexed envelopes 𝜀buf,𝑘 and 𝜀act,𝑘 , 1 ≤ 𝑟 ≤ 2, satisfy ⃦ 𝛽 rep ⃦ ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘on 𝑉𝑘 ⃦ ≤ 𝜀buf,𝑘 , (41) 2,𝜌𝑘,𝑆 ⃦ 𝜋on ⃦ tgt (𝑟) ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ⃦ ≤ 𝜀act,𝑘 , 1 ≤ 𝑟 ≤ 2, (42) 𝑟,𝜌 𝑘,𝑆
(2) (2) Here 𝜀act,𝑘 = 𝜀act,𝑘 ; the norm-indexed envelopes need not be equal.
together with the fit bound (24). operator distances, which is what Lemma 3.13 consumes. Remark 3.12 (A total-variation envelope for replay shift [ R ]). Write (︁∑︀ ⃦ (ℎ(·)) ⃦ (︀ (ℎ) )︀2 )︁1/2 (𝜌) 𝐻 ⃦ 𝑉max,𝑘 := ⃦𝑉max = 𝑝 𝑉max , 𝑘,ℎ ℎ=1 2,𝜌
These are
𝑘,𝑆
(𝜌) (𝜌) 𝑉max,𝑘 ≤ 𝑉 max ≤ 𝑉max
(43)
a.s. for every 𝑘,
(𝜌) ¯ exp := 2𝑉 (𝜌) is where 𝑝𝑘,ℎ := 𝜌𝑘,𝑆 (𝒮 × {ℎ}) and 𝑉 max is a deterministic uniform majorant (safely, 𝑉max ); hence 𝐷 max 𝑘 (ℎ) admissible in (21). Use the convention 𝑑TV (𝑃, 𝑄) := sup𝐴 |𝑃 (𝐴) − 𝑄(𝐴)|. Since |𝑄𝑉𝑘 (𝑠, ℎ, 𝑎)| ≤ 𝑉max , the replay link itself satisfies rep
on
(𝜌)
(ℎ(·)) ‖𝒯 𝛽𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ‖2,𝜌𝑘,𝑆 ≤ 2‖𝑉max 𝑑TV (𝛽𝑘rep , 𝜋𝑘on )‖2,𝜌𝑘,𝑆 ≤ 2𝑉max,𝑘 ess sup 𝑑TV (𝛽𝑘rep , 𝜋𝑘on ),
(44)
𝜌𝑘,𝑆
Any deterministic majorant is admissible for 𝜀buf,𝑘 ; 2𝑉max is safe. A quantitative FIFO decay rate follows from stabilization, age/mixing, or buffer-scaling control. 11
Deep 𝑉 -Learning: Convergence Framework
Lemma 3.13 (Executed-transition response versus Bellman response [ R ]). For 𝑟 ∈ [1, 2], set 𝜀̃︀𝑘,𝑟 := ‖𝑉𝑘+1 − 𝒯 𝑉𝑘 ‖𝑟,𝜌𝑘,𝑆 . Under Assumptions 2.1 and 3.11, for 0 ≤ 𝑘 < 𝐾, (𝑟)
¯ exp . E[̃︀ 𝜀𝑘,𝑟 | 𝒥𝑘 ] ≤ 𝜀fit,𝑘 + 𝜀ker,𝑘 + 𝜀tgt,𝑘 + 𝜀buf,𝑘 + 𝜀act,𝑘 + 𝜀𝑘 𝐷 𝑘
(45)
Proof. Apply the triangle inequality along rep
tgt
on
𝑉𝑘+1 → 𝐺𝑘 → 𝐺ideal → 𝒯 𝛽𝑘 𝑉𝑘 → 𝒯 𝜋𝑘 𝑉𝑘 → 𝒯 𝜋𝑘 𝑉𝑘 → 𝒯 𝑉𝑘 . 𝑘 Every link except the online-action link is first bounded by its named 𝐿2 envelope and hence by the same envelope in 𝐿𝑟 , since 𝑟 ≤ 2 and 𝜌𝑘,𝑆 is a probability law. The online-action link uses (42). The last link is exactly 𝜀𝑘 ∆exp by (18), 𝑘 where ∆exp 𝑠) := ∆exp [𝑉𝑘 , 𝜉𝑘 ](˜ 𝑠) 𝑘 (˜ ∫︁ ⃦ ⃦ (46) ¯ exp := ⃦∆exp ⃦ = max 𝑄𝑉𝑘 (˜ 𝑠, 𝑎) − 𝑄𝑉𝑘 (˜ 𝑠, 𝑎) 𝜉𝑘 (𝑑𝑎 | 𝑠˜), ∆ . 𝑘 𝑘 2,𝜌 𝑎
𝑘,𝑆
(ℎ)
|𝑄𝑉𝑘 (𝑠, ℎ, 𝑎)| ≤ 𝑉max gives ¯ exp ≤ 2𝑉 (𝜌) ≤ 2𝑉 (𝜌) ∆ max ≤ 2𝑉max 𝑘 max,𝑘
(47)
¯ exp ≤ 𝐷 ¯ exp by (21). Taking conditional expectations proves (45). and ‖∆exp 𝑘 ‖𝑟,𝜌𝑘,𝑆 ≤ ∆𝑘 𝑘 Definition 3.14 (Visible-target aliasing [ R ]). Fix one realization of 𝒥𝑘 . Let 𝑂 : 𝒮̃︀∘ → 𝒪 be the measurable representation visible to the fitted function, and let Π𝑂,𝑘 be conditional expectation given 𝜎(𝑂) under 𝜌𝑘,𝑆 . Set ⃦ ⃦ 𝑎alias,𝑘 := ⃦Π𝑂,𝑘 𝐺𝑘 − 𝐺𝑘 ⃦2,𝜌 . 𝑘,𝑆
This is the exact distance from the block response in (24) to the closed subspace of 𝜎(𝑂)-measurable 𝐿2 (𝜌𝑘,𝑆 ) functions. It is 𝒥𝑘 -measurable and is not assumed zero. When a deterministic envelope is needed, write 𝑎alias,𝑘 ≤ 𝜀alias,𝑘 almost surely. Lemma 3.15 (Aliasing is a component of the fit residual [ R ]). Suppose the regression class consists of 𝜎(𝑂)-measurable functions and the solver satisfies the regression bound relative to the best visible target, E[‖𝑉𝑘+1 − Π𝑂,𝑘 𝐺𝑘 ‖2,𝜌𝑘,𝑆 | 𝒥𝑘 ] ≤ 𝜀vis fit,𝑘 . Then ‖𝑉 − 𝐺𝑘 ‖2,𝜌𝑘,𝑆 ≥ 𝑎alias,𝑘 for every visible 𝑉 , and E[‖𝑉𝑘+1 − 𝐺𝑘 ‖2,𝜌𝑘,𝑆 | 𝒥𝑘 ] ≤ 𝜀vis fit,𝑘 + 𝜀alias,𝑘 . Thus 𝜀fit,𝑘 := 𝜀vis fit,𝑘 + 𝜀alias,𝑘 ; aliasing is not charged again. Proof. Π𝑂,𝑘 is the orthogonal projection onto the visible subspace, so ‖𝑉 −𝐺𝑘 ‖22,𝜌𝑘,𝑆 = ‖𝑉 −Π𝑂,𝑘 𝐺𝑘 ‖22,𝜌𝑘,𝑆 +𝑎2alias,𝑘 , and the upper bound follows by the triangle inequality. Remark 3.16 (What removes the floor: target sufficiency of the representation [ R ]). For the fixed history, 𝑎alias,𝑘 = 0 exactly when 𝐺𝑘 = 𝑔𝑘 ∘ 𝑂 𝜌𝑘,𝑆 -almost surely for some measurable 𝑔𝑘 : the observation determines the block target mean. Hidden reward, continuation, or clock variables can therefore leave a fit floor; augmenting the representation or passing to a belief state can remove it. Proposition 3.17 (Markov-sufficient and compressed-observation routes [ G, R ]). There are two compatible routes from an implemented input to the abstract state. (i) If the implemented input 𝑂𝑡 , including its clock, satisfies (13) with 𝑠˜𝑡 = 𝑂𝑡 , then it may be used as the analysis state. In particular, for a (SAMPLE, OBS) target, an 𝑂-measurable acting policy, and an 𝑂-measurable frozen value, the population response is 𝑂-measurable and 𝑎alias,𝑘 = 0. (ii) If 𝑂 = 𝜔(˜ 𝑠) is a measurable compression of a state satisfying Assumption 2.1, then every observation-only value ̃︀ The residual decomposition therefore applies on and policy is still a measurable value and Markov policy on 𝒮. vis the Markov analysis state with 𝜀fit,𝑘 = 𝜀fit,𝑘 + 𝜀alias,𝑘 as in Lemma 3.15. An observation-only reward/transition score is lifted in the same way, and its discrepancy from 𝑄𝑉 is charged by 𝜂sc,𝑘 ; closure and concentrability are ̃︀ likewise checked on 𝒮. A Markov-sufficient representation gives the direct convergence route, while a compressed observation gives a quantitative performance route whose representation and score floors remain visible in the policy-loss bound. 12
Deep 𝑉 -Learning: Convergence Framework
Proof. Part (i) is Assumption 2.1 on the represented state space. Conditional expectation of the observed-successor label through its joint kernel is then a measurable function of 𝑂𝑡 , so its projection onto 𝜎(𝑂) is itself. For (ii), composition ̃︀ Lemma 3.15 supplies the fit link, with 𝜔 lifts every implemented value, score, and policy to a measurable object on 𝒮; and the remaining links are exactly those in Assumption 3.11. 3.4
Finite-horizon policy-loss bound
Theorem 3.18 (Finite-𝐾 policy-loss bound under six residuals [ R ]). Assume Assumptions 2.1, 3.3 (C-strong), and 3.11, with 𝐾 ≥ 1, 𝑉0 , . . . , 𝑉𝐾 ∈ 𝒱 clip , and 𝑉 ⋆ from Lemma 2.6. Let 𝜋𝐾 be true-𝑄𝑉𝐾 greedy after 𝐾 target copies; it uses the true kernel and is not directly deployable (§6.1). Set (𝑝) ¯ exp 𝑒Bell 𝑘,𝑝 := 𝜀fit,𝑘 + 𝜀ker,𝑘 + 𝜀tgt,𝑘 + 𝜀buf,𝑘 + 𝜀act,𝑘 + 𝜀𝑘 𝐷𝑘 ,
𝑒Bell 𝐾,𝐻,𝑝 :=
max max{0,𝐾−𝐻+1}≤𝑘<𝐾
𝑒Bell 𝑘,𝑝 .
(48)
Then E[‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ] ≤ ℬ𝐾 +
𝐾−1 ∑︁
(𝐻)
(𝐻)
Bell 𝑤𝐾,𝑘 𝑒Bell 𝑘,𝑝 ≤ ℬ𝐾 + 2𝜑𝑠,𝐾 𝑒𝐾,𝐻,𝑝 .
(49)
𝑘=0
𝜀𝑘,𝑝 = E[ E[̃︀ 𝜀𝑘,𝑝 | 𝒥𝑘 ] ] ≤ 𝑒Bell Proof. Lemma 3.13 at 𝑟 = 𝑝 and the tower property give Ẽ︀ 𝑘,𝑝 . The six summands of (48) ¯ exp of (21), not the random dispersion ∆ ¯ exp . are deterministic. For the exploration link the summand is the majorant 𝐷 𝑘 𝑘 Apply Lemma 3.10 to 𝑒𝑘 = 𝑉𝑘+1 − 𝒯 𝑉𝑘 and take expectations termwise, since the weights are deterministic. The second inequality uses the active-window maximum 𝑒Bell 𝐾,𝐻,𝑝 and the weight-sum identity. Because the weights are deterministic, this step does not interchange E and max. Theorem 3.19 (Level-indexed residual propagation and sampling [ R, Alev iid ]). Assume Assumption 2.1, 𝐻 ≥ 2, and (ℎ) 𝐾 ≥ 1; let 𝜇∘𝑆 be carried by {ℎ = 𝐻}, and put 𝐿ℎ := 𝒮 × {ℎ}. For every block 𝑘 and 1 ≤ ℎ < 𝐻, let 𝜌𝑘,𝑆 be a 𝒥𝑘 -measurable probability law carried by 𝐿ℎ . For 1 ≤ 𝑚 < 𝐻, assume the level-indexed coefficient ⃦ ⃦ ⃦ 𝑑(𝜇∘ 𝒫 𝜋1 · · · 𝒫 𝜋𝑚 ) ⃦2 ⃦ ⃦ ∘ lev 𝑆 ∘ 𝑐2,𝑘 (𝑚) := sup ⃦ ≤ 𝑐lev (50) ⃦ 2 (𝑚) < ∞ (𝐻−𝑚) ⃦ (𝐻−𝑚) 𝜋1:𝑚 ⃦ 𝑑𝜌 𝑘,𝑆
2,𝜌𝑘,𝑆
almost surely, with a deterministic upper envelope uniform in 𝑘 and in the policy sequence. Define the six residual (ℎ) links levelwise by replacing each 𝐿2 (𝜌𝑘,𝑆 ) norm in (24)–(26) and Assumption 3.11 by 𝐿2 (𝜌𝑘,𝑆 ), retaining the same conditional-mean convention for fit and deterministic almost-sure convention for the other links, and write ¯ exp . 𝑒Bell (51) 𝑘,ℎ := 𝜀fit,𝑘,ℎ + 𝜀ker,𝑘,ℎ + 𝜀tgt,𝑘,ℎ + 𝜀buf,𝑘,ℎ + 𝜀act,𝑘,ℎ + 𝜀𝑘 𝐷 𝑘,ℎ
Then every clipped abstract recursion and its true-score greedy policy satisfy 𝐾−1 √︁ ∑︁ 𝐻−1 ∑︁ Bell E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 2 𝛾 𝑚 𝑐lev 2 (𝑚) 𝑒𝑘,𝐻−𝑚 𝑘=0 𝑚=𝐾−𝑘 (𝐻)
≤ ℬ𝐾 + 2𝜑lev
max 𝑒Bell 𝑘,ℎ ,
0≤𝑘<𝐾 1≤ℎ<𝐻
(𝐻)
𝜑lev :=
𝐻−1 ∑︁
𝑚𝛾 𝑚
√︁
𝑐lev 2 (𝑚).
(52)
𝑚=1 (𝐻)
Empty inner sums are zero. In particular, if 𝑐lev ¯, then 𝜑lev ≤ 2 (𝑚) ≤ 𝑐
√ √ 𝑐¯ 𝐻(𝐻 − 1)/2 = 𝑂(𝐻 2 𝑐¯).
Under the Alev iid clause of Assumption 3.4, a realization in a class closed under slice assembly draws 𝑛𝑘,ℎ conditionally (ℎ) i.i.d. states from 𝜌𝑘,𝑆 , executes the level-ℎ behavior law, observes fresh true-kernel outcomes, and fits 𝑉𝑘+1 |𝐿ℎ with a separate head or regressor. Thus only the fit slot at level ℎ is learned from those 𝑛𝑘,ℎ labels; the other five slots in (51) (ℎ) are assumed or separately bounded under the same 𝜌𝑘,𝑆 . The exact sample count is lev 𝑁0:𝐾−1 :=
𝐾−1 ∑︁ 𝐻−1 ∑︁
𝑛𝑘,ℎ ;
lev 𝑛𝑘,ℎ ≡ 𝑛 =⇒ 𝑁0:𝐾−1 = 𝐾(𝐻 − 1)𝑛.
(53)
𝑘=0 ℎ=1
This counts direct slice-reset outcomes. Rejection ∑︀sampling from a single reset law instead has an additional clock-massdependent cost. An optional top-slice fit adds 𝑘<𝐾 𝑛𝑘,𝐻 samples while leaving the propagation bound unchanged. A shared-parameter multitask implementation can use the same propagation formula once its joint fit residual is controlled. 13
Deep 𝑉 -Learning: Convergence Framework
Proof. In the proof of √︀Lemma 3.10, every depth-𝑚 occupancy lies on 𝐿𝐻−𝑚 ; Cauchy–Schwarz with (50) bounds its residual integral by 𝑐lev 2 (𝑚)‖𝑒𝑘 ‖2,𝜌(𝐻−𝑚) . The two resolvent branches and the exact count min{𝐾, 𝑚} give (52); 𝑘,𝑆
summing disjoint direct-reset blocks gives (53). 3.5
Matched-budget propagation
A shared-reset run uses one sampling distribution across horizon levels, whereas a direct-level run samples each level separately. We compare their policy-loss bounds under a common label budget for the updates that receive nonzero propagation weights. Coordinate 𝑖 has a statistical term 𝑏𝑖 𝑛−𝜈 𝑖 ; the exponent 𝜈 covers parametric, tabular, and nonparametric rates. Theorem 3.20 (Matched-budget propagation and optimal planned allocation [ Aiid , Alev iid ]). Fix a terminal copy 𝐾 and 𝜈 ∈ (0, 1], and apply Theorem 3.18 at 𝑠 = 2 to a shared-reset run and Theorem 3.19 to a direct-level-reset run on the sh same model, with the same evaluation law and initialization. Denote their terminal true-score greedy policies by 𝜋𝐾 lev and 𝜋𝐾 , respectively, and define the active index sets 𝒦𝐾 := {𝑘 : max{0, 𝐾 − 𝐻 + 1} ≤ 𝑘 < 𝐾}, ℐ𝐾 := {(𝑘, ℎ) : 0 ≤ 𝑘 < 𝐾, 1 ≤ ℎ < 𝐻, 𝐾 − 𝑘 ≤ 𝐻 − ℎ},
(54)
and, for (𝑘, ℎ) ∈ ℐ𝐾 , put 𝐻−ℎ 𝐴lev 𝑘,ℎ := 2𝛾
√︁
𝑐lev 2 (𝐻 − ℎ).
(55)
Suppose the Bellman-residual envelopes separate into deterministic floors and statistical terms, sh sh −𝜈 𝑒Bell 𝑘,2 ≤ 𝑟𝑘 + 𝑏𝑘 𝑛𝑘 ,
lev lev −𝜈 𝑒Bell 𝑘,ℎ ≤ 𝑟𝑘,ℎ + 𝑏𝑘,ℎ 𝑛𝑘,ℎ ,
(56)
on their respective active sets. The floors may contain any label-independent component of the six links. The coefficients 𝑏𝑖 are fixed before the allocation is chosen and, in particular, may not absorb a factor such as (log 𝑛𝑖 )𝑞 that varies with the coordinate allocation. Omit coordinates whose statistical objective coefficient 𝑐𝑖 is zero and define {︃ }︃1+𝜈 ∑︁ (𝐻) ∑︁ (︀ (𝐻) )︀1/(1+𝜈) sh sh sh C𝜈,𝐾 := 𝑤𝐾,𝑘 𝑏𝑘 , 𝐹𝐾 := 𝑤𝐾,𝑘 𝑟𝑘sh , (57) 𝑘∈𝒦𝐾
𝑘∈𝒦𝐾
⎧ ⎫1+𝜈 ⎨ ∑︁ (︀ ⎬ )︀ lev 1/(1+𝜈) Clev 𝐴lev , 𝜈,𝐾 := 𝑘,ℎ 𝑏𝑘,ℎ ⎩ ⎭ (𝑘,ℎ)∈ℐ𝐾
Under continuous terminal active-window budgets allocations on positive-weight coordinates are
∑︀
𝑘∈𝒦𝐾 𝑛𝑘 = Nsh and
min ∑︀
𝑛𝑖 >0:
𝑖 𝑛𝑖 =N
lev 𝐴lev 𝑘,ℎ 𝑟𝑘,ℎ .
(58)
(𝑘,ℎ)∈ℐ𝐾
∑︀
1/(1+𝜈)
𝑐 𝑛𝑖 = N ∑︀ 𝑖 1/(1+𝜈) , 𝑗 𝑐𝑗
∑︁
lev 𝐹𝐾 :=
∑︁
𝑐𝑖 𝑛−𝜈 = 𝑖
𝑖
(𝑘,ℎ)∈ℐ𝐾 𝑛𝑘,ℎ = Nlev , the unique optimal 1/(1+𝜈) )︀1+𝜈 𝑖 𝑐𝑖 , N𝜈
(︀∑︀
(59)
(𝐻)
lev lev with 𝑐𝑖 = 𝑤𝐾,𝑘 𝑏sh 𝑘 for shared reset and 𝑐𝑖 = 𝐴𝑘,ℎ 𝑏𝑘,ℎ for direct level reset. Both terminal-window budgets count observed true-kernel labels and charge only the displayed active coordinates. Labels consumed outside these sets, including earlier zero-weight blocks when 𝐾 > 𝐻 − 1, must be added separately when reporting total run cost. The quantity Nlev counts direct slice-reset outcomes, with any rejection overhead added before comparing physical simulator calls. The resulting terminal-policy bounds are sh
−𝜈 sh E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 𝐹𝐾 + Csh 𝜈,𝐾 Nsh , ⋆
E‖𝑉 − 𝑉
lev 𝜋𝐾
If the rate on coordinate 𝑖 is valid only for 𝑛𝑖 ≥ 𝐿𝑖 , let 𝐿𝑖 ∈ N with 𝐿𝑖 ≥ 1, N ≥ ∑︁ Ψ𝜈 (𝑐, 𝐿, N) := min 𝑐𝑖 𝑛−𝜈 ∑︀ 𝑖 . 𝑛𝑖 ≥𝐿𝑖 :
For N >
(60)
−𝜈 lev ‖1,𝜇𝑆 ≤ ℬ𝐾 + 𝐹𝐾 + Clev 𝜈,𝐾 Nlev .
𝑖 𝑛𝑖 =N
(61)
∑︀
𝑖 𝐿𝑖 , and define
(62)
𝑖
∑︀
𝑖 𝐿𝑖 , its unique continuous minimizer is
𝑛𝐿 𝑖 = max
{︂ 𝐿𝑖 ,
(︁ 𝜈𝑐 )︁1/(1+𝜈) }︂ 𝑖
𝜆
,
∑︁ 𝑖
14
𝑛𝐿 𝑖 = N,
(63)
Deep 𝑉 -Learning: Convergence Framework
∑︀ where the budget equation determines a unique 𝜆 > 0; if N = 𝑖 𝐿𝑖 , the unique feasible allocation is 𝑛𝐿 𝑖 = 𝐿𝑖 . When lower bounds apply, replace the last statistical term in (60) or (61) by the corresponding value Ψ𝜈 . Formula (59) and the closed forms (60)– (61) remain valid exactly when every unconstrained proportional allocation satisfies its lower bound. ∑︀ 𝐿 There is also an implementable integer schedule. Starting from ⌊𝑛𝐿 𝑖 ⌋, distribute the remaining N − 𝑖 ⌊𝑛𝑖 ⌋ labels one at a time to a coordinate with largest current marginal decrease ∆𝑖 (𝑛𝑖 ) := 𝑐𝑖 {𝑛−𝜈 − (𝑛𝑖 + 1)−𝜈 }. 𝑖
(64)
breaking ties by a fixed index order. The result is feasible, uses the full budget, and has statistical objective at most 2𝜈 Ψ𝜈 (𝑐, 𝐿, N). Here |𝒦𝐾 | = min{𝐾, 𝐻 − 1} and, with 𝐽 = min{𝐾, 𝐻 − 1}, |ℐ𝐾 | = 𝐽𝐻 − 𝐽(𝐽 + 1)/2 before zero-weight coordinates are omitted. Proof: See Appendix B. Corollary 3.21 (Matched-budget horizon geometry on the clock witness [ Aiid , Alev iid ]). Consider the one-state-per-level horizon-indexed family with unit survival, 𝐾𝐻 ≥ 𝐻 − 1, and 𝑠 = 2. Use fresh (SAMPLE, OBS) outcomes, the declared exact-score oracle, 𝑊𝑘 = 𝑉𝑘 , greedy collection with 𝜀𝑘 = 0, 𝑂 = 𝑆, and a fitted procedure with the displayed statistical envelope. Assume the unconstrained planned allocations satisfy every validity threshold 𝐿𝑖 ; otherwise the exact comparison is the constrained value Ψ𝜈 from (62). Under these choices, the kernel, target, replay, action, exploration, aliasing, and drift links vanish, the top-slice boundary is zero, and the fit link is the only nonzero term. sh lev lev Suppose its statistical constants satisfy 𝑏sh 𝑘 ≍ 𝑏𝐻 and 𝑏𝑘,ℎ ≍ 𝑏𝐻 uniformly on the active sets. For direct level reset lev take 𝑐2 (𝑚) = 1. For shared reset compare the uniform clock law with the coefficient-optimal law (35). Then: (a) In the near-unit-discount regime, sh,opt sh 𝜈+5/2 Csh,unif , 𝜈,𝐾𝐻 ≍ C𝜈,𝐾𝐻 ≍ 𝑏𝐻 𝐻
lev 2𝜈+2 Clev . (65) 𝜈,𝐾𝐻 ≍ 𝑏𝐻 𝐻 √ For the root-𝑛 case 𝜈 = 1/2, both clock geometries therefore contribute 𝐻 3 / N before their regression constants are inserted.
(b) In the fixed-discount regime, sh 1/2 Csh,unif , 𝜈,𝐾𝐻 ≍ 𝑏𝐻 𝐻
sh Csh,opt 𝜈,𝐾𝐻 ≍ 𝑏𝐻 ,
lev Clev 𝜈,𝐾𝐻 ≍ 𝑏𝐻 .
(66)
All constants are uniform in 𝐻. Direct slice access and an optimized shared clock law have the same fixed-discount budget order, while direct access achieves it without√tuning cross-slice clock masses. In the one-state-per-level tabular lev specialization, the fit bound (98) gives 𝑏sh 𝐻 ≍ 𝑉max 𝐻 and 𝑏𝐻 ≍ 𝑉max . At 𝜈 = 1/2, the near-unit statistical terms are therefore respectively )︂ (︂ )︂ (︂ 𝑉max 𝐻 3 𝑉max 𝐻 7/2 √ √ and Θ , (67) Θ Nsh Nlev √ for the displayed bounds. This is a factor- 𝐻 statistical advantage for direct slice reset under equal sufficiently large terminal-window label budgets. Proof: See Appendix B. Remark 3.22 (Routed neural specialization [ Aiid , Alev iid ]). For a fixed horizon, the neural rate of Proposition 5.5 can be compared under a common terminal-window budget while retaining its actual validity thresholds 𝐿𝑖 and allocation-dependent logarithms. One may either upper-bound each (log 𝑛𝑖 )𝑞 by the allocation-independent (log N)𝑞 before applying Theorem 3.20, or optimize the logarithmic objective directly. The regression constant may depend on 𝐻 through 𝑉max and the routed approximation and entropy constants. Corollary 3.21 therefore establishes the √ factor- 𝐻 comparison for its displayed tabular constants; an analogous growing-horizon neural comparison requires uniform-in-𝐻 approximation, entropy, and reward-normalization bounds.
4
Online-action residual
The behavior policy may score actions with a network that differs from the frozen iterate 𝑉𝑘 . Using the optimization and acting-snapshot index sets defined before (21), measure this displacement by path 𝛿𝑉,𝑘 := sup ‖𝑉𝜃𝑘,𝑡 − 𝑉𝑘 ‖∞ ,
path 𝛿𝑉,𝑘 ≤ 𝛿𝑉,𝑘
a.s. for Arun ,
snap 𝛿𝑉,𝑘 := ‖𝑊𝑘 − 𝑉𝑘 ‖∞ ,
snap 𝛿𝑉,𝑘 ≤ 𝛿𝑉,𝑘
a.s. for Aiid .
𝑡∈ℐ𝑘act
(68)
15
Deep 𝑉 -Learning: Convergence Framework
The deterministic envelope 𝛿𝑉,𝑘 bounds the appropriate displacement for each analysis object. Together with the score error 𝜂sc,𝑘 , it gives the perturbation scale Λ𝑘 := 𝛾𝛿𝑉,𝑘 + 𝜂sc,𝑘 ,
𝜂sc,𝑘 as bounded in (21).
(69)
Network drift and score error therefore enter on the same scale. A score perturbation of size Λ𝑘 can change the greedy action only at states whose action gap is at most 2Λ𝑘 . The margin condition controls how much replay probability lies in this set. We use a Mammen–Tsybakov-type condition on the frozen iterates’ action gaps and relate it to classical optimal-gap conditions [12–15]. 4.1
Margin condition
Definition 4.1 (Frozen-iterate action-gap margin: local and global forms [ R ]). The replay laws satisfy the local frozen-iterate (𝐶marg , 𝛼) margin condition at scale [𝑢0 , 𝑢 ¯] if there are deterministic constants 𝐶marg < ∞ and 𝛼 ≥ 0 such that, almost surely and for every 𝑘, {︀ }︀ (𝑘) 𝜌𝑘,𝑆 𝑠˜ : ∆𝑄 (˜ 𝑠) ≤ 𝑢 ≤ 𝐶marg 𝑢𝛼 for all 𝑢 ∈ [𝑢0 , 𝑢 ¯], (70) and the global frozen-iterate condition if the same holds for all 𝑢 > 0. This is a condition on the random pair (𝑄𝑉𝑘 , 𝜌𝑘,𝑆 ), uniform over iterations with deterministic constants; it is distinct from a margin stated only for the fixed optimal score 𝑄𝑉 ⋆ . The always-valid fallback is (𝐶marg , 𝛼) = (1, 0). Each result invokes the condition only at its displayed scale (2Λ𝑘 or 2𝜂sc,𝐾 ); a vanishing-scale claim requires a common interval (0, 𝑢 ¯]. (𝑘)
Remark 4.2 (Ties and a positive frozen-iterate exponent [ R ]). If (70) with 𝛼 > 0 holds down to zero, then 𝜌𝑘,𝑆 {∆𝑄 = 0} = 0; on a finite full-support law this forbids ties at every frozen iterate. A condition imposed at one scale has no such condition. By contrast, a fixed-𝑄⋆ positive-gap condition can exclude the zero-gap event and retain a separate optimal-tie mass, as follows. Proposition 4.3 (Transfer from a fixed optimal gap to frozen iterates [ G, R ]). For each 𝑘, suppose a deterministic 𝛿𝑘⋆ ≥ 0 satisfies ‖𝑄𝑉𝑘 − 𝑄𝑉 ⋆ ‖∞ ≤ 𝛿𝑘⋆ almost surely. (71) Suppose also that deterministic 𝜏⋆ ∈ [0, 1], 𝐶⋆ < ∞, and 𝛼⋆ ≥ 0 satisfy, almost surely and uniformly in 𝑘, 𝜌𝑘,𝑆 {∆⋆𝑄 = 0} ≤ 𝜏⋆ ,
𝜌𝑘,𝑆 {0 < ∆⋆𝑄 ≤ 𝑣} ≤ 𝐶⋆ 𝑣 𝛼⋆
(72)
at every scale 𝑣 in a declared interval. Whenever 𝑢 + 2𝛿𝑘⋆ belongs to that interval, (𝑘)
𝜌𝑘,𝑆 {∆𝑄 ≤ 𝑢} ≤ 𝜏⋆ + 𝐶⋆ (𝑢 + 2𝛿𝑘⋆ )𝛼⋆ .
(73)
In particular, if 𝜏⋆ = 0, the optimal-gap condition is available on the required enlarged scales, and 𝛿𝑘⋆ ≤ 𝑐𝑢0 uniformly for some 𝑐 ≥ 0, then the local frozen-iterate condition on [𝑢0 , 𝑢 ¯] holds with exponent 𝛼⋆ and constant 𝐶⋆ (1 + 2𝑐)𝛼⋆ . ⋆ At the action scale 𝑢 = 2Λ𝑘 , the weaker tube 𝛿𝑘 ≤ 𝑐Λ𝑘 already preserves the exponent because the right-hand side of (73) becomes 𝐶⋆ [2(1 + 𝑐)Λ𝑘 ]𝛼⋆ when 𝜏⋆ = 0. Finally, 𝛿𝑘⋆ = 𝛾𝑏𝑘
is valid whenever
‖𝑉𝑘 − 𝑉 ⋆ ‖∞ ≤ 𝑏𝑘 ,
(74)
so the transfer can be verified from a deterministic value-iterate tube. Proof. Write 𝑞 = 𝑄𝑉𝑘 and 𝑞 ⋆ = 𝑄𝑉 ⋆ . If ∆⋆𝑄 (˜ 𝑠) ≤ 2𝛿𝑘⋆ , then it already lies below 𝑢 + 2𝛿𝑘⋆ . If instead ∆⋆𝑄 (˜ 𝑠) > 2𝛿𝑘⋆ , the optimal maximizer is unique and remains the maximizer of 𝑞, while its separation from every competitor is at least ∆⋆𝑄 (˜ 𝑠) − 2𝛿𝑘⋆ . Hence (𝑘)
{∆𝑄 ≤ 𝑢} ⊆ {∆⋆𝑄 ≤ 𝑢 + 2𝛿𝑘⋆ }. Splitting the latter event into zero and positive gaps gives (73). If 𝛿𝑘⋆ ≤ 𝑐𝑢0 ≤ 𝑐𝑢, then 𝑢 + 2𝛿𝑘⋆ ≤ (1 + 2𝑐)𝑢, proving the local statement. The action-scale claim is the same calculation with 𝑢 = 2Λ𝑘 . Finally, ‖𝑄𝑉 − 𝑄𝑊 ‖∞ ≤ 𝛾‖𝑉 − 𝑊 ‖∞ proves (74). Lemma 4.4 (Exact gap identity and pointwise control [ R ]). In the notation of §4.1: ̂︀ 𝑉 − 𝑄𝑉 ‖∞ ≤ Λ𝑘 with Λ𝑘 as in (69); (i) ‖𝑄𝑉𝜃𝑘 − 𝑄𝑉𝑘 ‖∞ ≤ 𝛾𝛿𝑉,𝑘 , and hence ‖𝑄 𝜃𝑘 𝑘 (ii) if 𝜋𝑘on = (1 − 𝜀𝑘 )𝛿𝑎on + 𝜀 𝜉 is a single 𝜀𝑘 -greedy policy, then 𝑘 𝑘 𝑘 (︀ 𝜋on )︀ (︀ )︀ tgt 𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 (˜ 𝑠) = (1 − 𝜀𝑘 ) 𝑄𝑉𝑘 (˜ 𝑠, 𝑎on 𝑠, 𝑎tgt 𝑘 ) − 𝑄𝑉𝑘 (˜ 𝑘 ) . on Its absolute value is (1 − 𝜀𝑘 )subopt𝑘 (˜ 𝑠); here subopt𝑘 := 𝑄𝑉𝑘 (·, 𝑎tgt 𝑘 ) − 𝑄𝑉𝑘 (·, 𝑎𝑘 );
16
Deep 𝑉 -Learning: Convergence Framework
(iii) (generic perturbation) let 𝑞 : 𝒮̃︀∘ × 𝒜 → R be any score with ‖𝑞 − 𝑄𝑉𝑘 ‖∞ ≤ Λ for some Λ ≥ 0, and let 𝑞 𝑎𝑞 (˜ 𝑠) ∈ arg max𝑎 𝑞(˜ 𝑠, 𝑎). Then the induced suboptimality subopt𝑞𝑘 := 𝑄𝑉𝑘 (·, 𝑎tgt 𝑘 ) − 𝑄𝑉𝑘 (·, 𝑎 ) satisfies 0 ≤ subopt𝑞𝑘 (˜ 𝑠) ≤ 2Λ
(𝑘)
{subopt𝑞𝑘 > 0} ⊆ {∆𝑄 ≤ 2Λ}.
and
̂︀ 𝑉 with Λ = Λ𝑘 , this gives 0 ≤ subopt𝑘 ≤ 2Λ𝑘 and {subopt𝑘 > 0} ⊆ Applied to the implemented score 𝑞 = 𝑄 𝜃𝑘 (𝑘)
{∆𝑄 ≤ 2Λ𝑘 }; in the idealization 𝜂sc,𝑘 = 0 it gives the same statements with Λ𝑘 = 𝛾𝛿𝑉,𝑘 . ∫︀ Proof. 𝑄𝑉 − 𝑄𝑊 = 𝛾 (𝑉 − 𝑊 )𝑑𝒫 proves (i). In (ii), both policies share 𝜀𝑘 𝜉𝑘 , so exploration cancels exactly; its ¯ exp link. For (iii), apply the perturbation bound twice: 𝑄𝑉 (˜ separate difference from 𝒯 remains the 𝜀𝑘 𝐷 𝑠, 𝑎𝑞 ) ≥ 𝑘 𝑘 (𝑘) tgt tgt 𝑞 𝑞(˜ 𝑠, 𝑎𝑞 ) − Λ ≥ 𝑞(˜ 𝑠, 𝑎𝑘 ) − Λ ≥ 𝑄𝑉𝑘 (˜ 𝑠, 𝑎𝑘 ) − 2Λ, so subopt𝑘 ≤ 2Λ. If ∆𝑄 (˜ 𝑠) > 2Λ then every 𝑎 ̸= 𝑎tgt 𝑘 has tgt 𝑞 𝑞(˜ 𝑠, 𝑎) ≤ 𝑄𝑉𝑘 (˜ 𝑠, 𝑎) + Λ < max𝑎 𝑄𝑉𝑘 (˜ 𝑠, 𝑎) − Λ ≤ 𝑞(˜ 𝑠, 𝑎tgt ), so 𝑎 = 𝑎 . 𝑘 𝑘 For every 𝑉 ∈ 𝒱 clip and every Markov policy 𝜋, the elementary pointwise inequality 𝒯 𝜋 𝑉 ≤ 𝒯 𝑉 follows by averaging action scores below their maximum. 4.2
Gap identity and upper bound
Theorem 4.5 (Norm-indexed action residual for the abstract recursion [ R ]). In the notation of §4.1, let 𝑞𝑘 be measurable with ‖𝑞𝑘 − 𝑄𝑉𝑘 ‖∞ ≤ Λ𝑘 , let 𝑎𝑞𝑘 maximize 𝑞𝑘 using the fixed tie rule, and put 𝜋𝑘𝑞 = (1 − 𝜀𝑘 )𝛿𝑎𝑞𝑘 + 𝜀𝑘 𝜉𝑘 . For every 𝑟 ∈ [1, 2], ⃦ 𝜋𝑞 ⃦ tgt ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ⃦ ≤ (1 − 𝜀𝑘 )2Λ𝑘 . (75) 𝑟,𝜌 𝑘,𝑆
Under the global frozen-iterate margin (70), or its local form when 2Λ𝑘 ∈ [𝑢0 , 𝑢 ¯], ⃦ 𝜋𝑞 ⃦ tgt 1/𝑟 ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ⃦ ≤ (1 − 𝜀𝑘 )𝐶marg (2Λ𝑘 )1+𝛼/𝑟 . 𝑟,𝜌
(76)
Alternatively, under Proposition 4.3 at 𝑢 = 2Λ𝑘 , {︁ }︁1/𝑟 ⃦ 𝜋𝑞 ⃦ tgt ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ⃦ ≤ (1 − 𝜀𝑘 )2Λ𝑘 𝜏⋆ + 𝐶⋆ (2Λ𝑘 + 2𝛿𝑘⋆ )𝛼⋆ .
(77)
𝑘,𝑆
𝑟,𝜌𝑘,𝑆
1+𝛼⋆ /𝑟
Thus a zero optimal-tie mass and 𝛿𝑘⋆ ≤ 𝑐Λ𝑘 yield the same Λ𝑘 explicit constant. Consequently one may choose
exponent directly from a fixed-𝑄⋆ margin, with its
(𝑟)
1/𝑟 𝜀act,𝑘 ≤ (1 − 𝜀𝑘 ) min{2Λ𝑘 , 𝐶marg (2Λ𝑘 )1+𝛼/𝑟 }.
When the reference-gap route is used, one may instead choose {︂ [︁ ]︁1/𝑟 }︂ (𝑟) 𝜀act,𝑘 ≤ (1 − 𝜀𝑘 ) min 2Λ𝑘 , 2Λ𝑘 𝜏⋆ + 𝐶⋆ (2Λ𝑘 + 2𝛿𝑘⋆ )𝛼⋆ . (𝑝)
Taking 𝑟 = 𝑝 = 𝑠/(𝑠 − 1) supplies the propagation envelope 𝜀act,𝑘 with exponent 1 + 𝛼(1 − 1/𝑠); taking 𝑟 = 2 (2)
supplies the envelope 𝜀act,𝑘 used in the regression bound, with exponent 1 + 𝛼/2. The two coincide at 𝑠 = 2. Proof. Lemma 4.4(ii)–(iii) makes the integrand (1 − 𝜀𝑘 )subopt𝑞𝑘𝑘 , bounded by (1 − 𝜀𝑘 )2Λ𝑘 and supported, (𝑘) when nonzero, on {∆𝑄 ≤ 2Λ𝑘 }. This proves (75); under the frozen-iterate margin its 𝑟th power is at most 𝑟 𝑟+𝛼 (1 − 𝜀𝑘 ) 𝐶marg (2Λ𝑘 ) , proving (76). Replacing the support probability by (73) proves (77). Corollary 4.6 (Abstract-recursion mixtures and drift control [ Arun , Aiid ]). The unconditional bound (75) remains valid for any state-dependent convex mixture of policies sharing (𝜀𝑘 , 𝜉𝑘 ) whose greedy scores are within Λ𝑘 of 𝑄𝑉𝑘 . Under the global frozen-iterate margin, or under its local form with 2Λ𝑘 ∈ [𝑢0 , 𝑢 ¯], the margin-improved bound (76) also remains valid: convexity preserves both the pointwise 2Λ𝑘 bound and its common gap-supported set. The same argument preserves the fixed-𝑄⋆ transfer bound (77). Thus Theorem 4.5 applies directly to the snapshot law 𝛽𝑘 of ̂︀ 𝑊 , while this mixture statement applies to 𝜋 Aiid with 𝑞𝑘 = 𝑄 ¯𝑘on of Arun with the corresponding online scores; their 𝑘 distance from 𝑄𝑉𝑘 is at most Λ𝑘 = 𝛾𝛿𝑉,𝑘 + 𝜂sc,𝑘 by (69). Moreover, if 𝑉𝜃𝑘,0 = 𝑉𝑘 , 𝜃 ↦→ 𝑉𝜃 is 𝐿-Lipschitz in supremum ∑︀ path norm, and ‖𝜃𝑡+1 − 𝜃𝑡 ‖ ≤ 𝜆𝑡 𝐺, then 𝛿𝑉,𝑘 ≤ 𝐿𝐺 𝑡∈ℐ opt 𝜆𝑡 . For a general initialization, add ‖𝑉𝜃𝑘,0 − 𝑉𝑘 ‖∞ . Here 𝑘 𝐿 is an explicit regularity assumption on the parameterization. 17
Deep 𝑉 -Learning: Convergence Framework
Combining Lemma 3.10 and Theorem 4.5 gives the continuous coverage–margin tradeoff: the propagated action power (𝐻) is 1 + 𝛼(1 − 1/𝑠) and the exact finite-𝐾 clock multiplier is 2𝜑𝑠,𝐾 . This single result contains the 𝐿2 and 𝐿∞ statements as endpoint cases. The fixed-𝑄⋆ route has the same power with 𝛼 = 𝛼⋆ whenever 𝜏⋆ = 0 and 𝛿𝑘⋆ = 𝑂(Λ𝑘 ) on the active window. 4.3
One-step sharpness and lower bound
Proposition 4.7 attains the action theorem’s one-step exponent. Proposition 4.8 produces a nonzero limiting loss from a reward-score perturbation while all other residuals vanish; the harmful behavior is generated by the implemented score. Proposition 4.7 (Componentwise sharpness of the abstract one-step residual [ R ]). For every 𝛼 > 0, 𝑝 ∈ [1, 2], 𝛾 ∈ (0, 1), and sufficiently small drift 𝛿 > 0, there exist a deterministic time-augmented MDP with an exact one-step model (so that 𝜂sc,𝑘 = 0 and Λ𝑘 = 𝛾𝛿), a frozen 𝑉𝑘 , an online 𝑉𝜃𝑘 with 𝛿𝑉,𝑘 = 𝛿, and a replay marginal 𝜌𝑘,𝑆 that satisfies (70) with equality for 𝑢 ∈ (0, 𝛾𝑐Δ ], such that, when 𝜀𝑘 = 0, (︂ )︂1/𝑝 ⃦ 𝜋on ⃦ tgt 𝛼 1/𝑝 ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ⃦ = 𝐶marg (2𝛾𝛿)1+𝛼/𝑝 . 𝑝,𝜌𝑘,𝑆 𝛼+𝑝 Thus the exponent in the one-step bound (76) cannot be improved. This establishes componentwise sharpness: the clock and action constructions independently attain their respective exponents, while their joint product defines a separate end-to-end lower-bound problem. Proof. At a decision state 𝜎𝑡 , 𝑡 ∈ [0, 1], let actions 𝑎± lead deterministically to one-step states of values 𝑣0 + 𝑐Δ 𝑡 and 𝑣0 . Choose 𝑣0 , 𝑐Δ , 𝛿 > 0 with 𝑣0 + 𝑐Δ + 𝛿 ≤ 𝑅max , and shift the online successor values by ∓𝛿. Then the true gap is 𝛾𝑐Δ 𝑡, but the online action switches exactly on 𝑡 < 𝑡𝛿 := 2𝛿/𝑐Δ . Give 𝑡 density 𝛼𝑡𝛼−1 ; hence 𝐶marg = (𝛾𝑐Δ )−𝛼 . Direct integration gives ∫︁ 𝑡𝛿 ⃦ 𝜋on ⃦ tgt 𝛼 ⃦𝒯 𝑘 𝑉𝑘 − 𝒯 𝜋𝑘 𝑉𝑘 ⃦𝑝 (𝛾𝑐Δ )−𝛼 (2𝛾𝛿)𝛼+𝑝 ; = (𝛾𝑐Δ 𝑡)𝑝 𝛼𝑡𝛼−1 𝑑𝑡 = 𝑝,𝜌𝑘,𝑆 𝛼 +𝑝 0 taking 𝑝th roots proves the formula. Proposition 4.8 (Abstract-recursion loss induced by reward-score error [ R ]). Fix 𝛾 ∈ (0, 1) and normalize 𝑅max = 1. For every 𝜂 ∈ (0, 𝛾/2) and every 𝜖 > 0 there exist a deterministic time-augmented MDP with 𝐻 = 3 and |𝒜| = 2, ̂︀ of the an evaluation law 𝜇𝑆 , a replay marginal 𝜌𝑘,𝑆 ≡ 𝜌𝑆 of full support, and an implemented one-step score 𝑄 ̂︀ form (2) with ‖𝑄𝑉𝑘 − 𝑄𝑉𝑘 ‖∞ = 𝜂 for every 𝑘, such that the population recursion initialized at 𝑉0 = 0 and driven ̂︀ has zero drift, 𝛿𝑉,𝑘 = 0, and zero fit, kernel, target, replay, and exploration residuals, by the greedy branch of 𝑄 𝜀fit,𝑘 = 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 𝜀buf,𝑘 = 𝜀𝑘 = 0. The score-induced online-action residual is the sole nonzero link, and yet ⃦ ⃦ lim ⃦𝑉 ⋆ − 𝑉 𝜋𝐾 ⃦1,𝜇 ≥ 2𝛾𝜂 − 𝜖. (78) 𝑆
𝐾→∞
Thus the construction realizes the 𝛼 = 0 score floor for 0 < 𝜂 < 𝛾/2. After the finite clock transient, its harmful behavior is generated endogenously by an implemented greedy score with 𝜂sc,𝑘 = 𝜂 in every block. Construction sketch. Use the deterministic 𝐻 = 3 chain detailed in Appendix A, with terminal rewards 1, 1 − 𝑢, 𝑣, and perturb only the two modeled rewards at 𝑦1 by −𝜂, +𝜂. The score error is exactly 𝜂 and switches the choice at 𝑦1 when 𝑢 < 2𝜂/𝛾. Taking 𝑢 = 2𝜂/𝛾 − 𝜗 and 𝑣 ∈ (1 − 𝑢, 1 − 𝑢 + 𝜖/(2𝛾 2 )) makes the learned and optimal root actions different after the clock transient, with ‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 = 𝛾 2 (1 − 𝑣) > 2𝛾𝜂 − 𝜖 for sufficiently small 𝜗. Exact full-support population updates, matched collection and replay, frozen targets, and zero exploration make all other residuals vanish.
5
Neural and tabular regression rates
For Aiid , we fit one sparse-ReLU spatial network at each remaining-horizon level. A fixed router selects the corresponding output. This construction allows smoothness assumptions on the spatial coordinates without imposing smoothness across the discrete clock levels. Assumption 5.1 collects the approximation, closure, entropy, and nesting conditions. The sparse-ReLU exponent and corrected depth condition come from [16, 17]; Propositions 5.2 and 5.3 18
Deep 𝑉 -Learning: Convergence Framework
prove Bellman closure and compatibility of the network class with these conditions. The bounded-loss oracle inequality follows the covering approach of Györfi et al. [18]. The mean regression target can differ from the Bellman optimality (2) update because it averages the behavior policy. We retain this difference as 𝐷𝑘 [19–22]. Any class with the same approximation and entropy properties can replace the network class. The neural theorem fixes 𝐻; growing-horizon comparisons require Remark 3.22. Assumption 5.1 (Externally clipped clock-routed sparse ReLU class and Hölder closure [ Aiid ]). (Slice representation.) For each ℎ ∈ [𝐻] := {1, . . . , 𝐻}, fix a bi-measurable spatial embedding 𝜄ℎ : 𝒮 × {ℎ} → [0, 1]𝑑emb onto its image, through which the slice-ℎ rewards and kernel factor. The deterministic router observes the clock exactly, and the Hölder condition applies to the spatial coordinates within each slice. Any other discrete task coordinates 𝒞 are either routed in the same way or included in 𝜄ℎ . Smoothness, margin, and tube hypotheses are uniform over the resulting finitely many slices. The direct neural convergence route uses this routed input as the Markov-sufficient analysis state. If the network receives only a compression 𝑂, the same architecture can be analyzed through Proposition 3.17, with visible-target aliasing included in the fit residual and closure checked on the Markov state. (Per-head and routed classes.) For a block of size 𝑛 ≥ 2𝐻, set (79) 𝑚𝑛 := ⌊𝑛/𝐻⌋ ≥ 2. Let 𝐾𝒢 ≥ 1 be a common upper bound on the coordinatewise Hölder radii and domain endpoints used to define the finitely many target classes 𝒢0,ℎ below, and fix the raw-network envelope 𝐵net ≥ max{1, 𝑉max , 𝐾𝒢 }. (80) (ℎ)
For each ℎ, let 𝒩𝑚 be the raw scalar sparse-ReLU class on [0, 1]𝑑emb with weight and bias radius one, raw output bounded by 𝐵net , exactly 𝐿𝑚 hidden layers, width profile {𝑑𝑗,𝑚 }, and sparsity at most 𝑠𝑚 . The budgets are nondecreasing in 𝑚, dominate the constructive lower envelopes, and obey ⋆
𝑐lo log 𝑚 ≤ 𝐿𝑚 ≤ 𝑐hi (log 𝑚)𝜉 , ⋆
𝑚𝛼 ≲
⋆
min 𝑑𝑗,𝑚 ≤ max 𝑑𝑗,𝑚 ≲ 𝑚𝜉 ,
1≤𝑗≤𝐿𝑚 ⋆
1≤𝑗≤𝐿𝑚
(81)
⋆
𝑠𝑚 ≍ 𝑚𝛼 (log 𝑚)𝜉 , 𝜉 ⋆ ≥ 1. ⋃︀ (ℎ) (ℎ) 𝑚 Define the nested head class ℛ𝑚 := 𝑟=2 𝒩𝑟 . The raw clock-routed class is the finite product {︁ }︁ (ℎ) ℛclk := 𝑓 : 𝑓 (𝑠, ℎ) = 𝑓 (𝜄 (𝑠, ℎ)) , 𝑓 ∈ ℛ , ℎ ∈ [𝐻], 𝑓 (˜ 𝑠 ) = 0 . ℎ ℎ ℎ term 𝑛 𝑚𝑛
(82)
Thus the router is fixed and non-trainable, and only the selected scalar head is evaluated. A routed predictor has at most 𝐻𝑠𝑚𝑛 trainable nonzero parameters across its heads, maximum head depth 𝐿𝑚𝑛 , and no trainable gating parameter. This is still one global function class and one ERM under the mixed design law 𝜍; it is not the direct𝑉 clip clk slice sampling object Alev ℛ𝑛 , where the level-wise projection is fixed external post-processing iid . Let ℱ𝑛 := Π and contributes no trainable parameter. In particular, the ERM class is band-valued even though its raw networks use the larger envelope (80). Each finite-architecture bounded-parameter class is separable in supremum norm; choose countable dense subsets, take their finite unions and 𝐻-fold product, and then clip to obtain a fixed countable supremum-norm-dense subclass ℱ𝑛𝑉,0 ⊆ ℱ𝑛𝑉 . (Target and admissibility.) Let 𝒢0,ℎ be the slice-ℎ compositional Hölder class of [23, Assumption 4.2], intersected with (ℎ) the band ‖𝑔ℎ ‖∞ ≤ 𝑉max , with indices and radii uniformly bounded in ℎ, and define {︀ }︀ 𝒢0clk := 𝑔 ∈ 𝒱 clip : for every ℎ there is 𝑔¯ℎ ∈ 𝒢0,ℎ with 𝑔(𝑠, ℎ) = 𝑔¯ℎ (𝜄ℎ (𝑠, ℎ)) . (83) Writing distsup ∞ (𝒞, 𝒢) := sup𝑔∈𝒢 inf 𝑉 ∈𝒞 ‖𝑉 − 𝑔‖∞ , assume that there is a target-uniform 𝐶appx < ∞ such that (︀ clip (ℎ) )︀ (𝛼⋆ −1)/2 max distsup , 𝑚 ≥ 2, (84) ∞ Πℎ ℛ𝑚 , 𝒢0,ℎ ≤ 𝐶appx 𝑚 ℎ∈[𝐻]
(ℎ) (ℎ) where Πclip clips to [−𝑉max , 𝑉max ] on slice ℎ, and 𝛼⋆ = max𝑗 𝑡𝑗 /(2𝛽𝑗⋆ + 𝑡𝑗 ) ∈ (0, 1). Consequently, selecting one ℎ
approximant independently in each of the finitely many heads gives
⋆
𝑉 clk (𝛼 −1)/2 distsup . ∞ (ℱ𝑛 , 𝒢0 ) ≤ 𝐶appx 𝑚𝑛
(85)
(Closure, entropy, nesting, and uniformity.) For every 𝑛 ≥ 2𝐻 and 𝑉 ∈ ℱ𝑛𝑉 , assume 𝒯 𝑉 ∈ 𝒢0clk . Put 𝑑0,𝑚 := 𝑑emb , ∏︀𝐿𝑚 +1 𝑑𝐿𝑚 +1,𝑚 := 1, and 𝐷𝑚 := 𝑗=0 (𝑑𝑗,𝑚 + 1). The head covering bound and the product construction give, for 0 < 𝛿 ≤ 1, {︂ (︂ 2 )︂}︂ 2(𝐿𝑚𝑛 + 1)𝐷𝑚 𝑛 log 𝑁𝛿 (ℱ𝑛𝑉 ) ≤ 𝐻 log 𝑚𝑛 + (𝑠𝑚𝑛 + 1) log . (86) 𝛿 19
Deep 𝑉 -Learning: Convergence Framework
The head classes are nested in 𝑚; hence 𝑚𝑛 ≤ 𝑚𝑛′ implies ℱ𝑛𝑉 ⊆ ℱ𝑛𝑉′ . The Hölder radii, compositional indices, approximation and entropy constants are uniform in ℎ, 𝑛, 𝑘, and in the realized 𝑉𝑘 ∈ ℱ𝑛𝑉 . Constants in the results may depend on the fixed horizon 𝐻. (Corrected depth check.) Let 𝑖 = 0, . . . , 𝑞 index a head’s composition layers, with parameters (𝛽𝑖 , 𝑡𝑖 , 𝛽𝑖⋆ ). Set 𝐶SH :=
𝑞 ∑︁ 𝛽𝑖 + 𝑡 𝑖
2𝛽𝑖⋆ + 𝑡𝑖 𝑖=0
⋆
⋆
𝜑𝑚 := max 𝑚−2𝛽𝑖 /(2𝛽𝑖 +𝑡𝑖 ) .
log2 (4𝑡𝑖 ∨ 4𝛽𝑖 ),
𝑖
⋆
Then 𝑚𝜑𝑚 = 𝑚𝛼 . Consequently 𝑐lo ≥ 𝐶SH / log 2 verifies the corrected lower depth requirement 𝐶SH log2 𝑚 ≤ 𝐿𝑚 , while the polylogarithmic upper bound in (81) is eventually 𝐿𝑚 ≲ 𝑚𝜑𝑚 . The same display gives 𝑚𝜑𝑚 ≲ min𝑗 𝑑𝑗,𝑚 , and its sparsity budget contains the constructive scale 𝑠′𝑚 ≍ 𝑚𝜑𝑚 log 𝑚 ≤ 𝑠𝑚 . Together with (80), these are the output-envelope, corrected depth, width, and sparsity compatibility checks. Equation (84), Bellman closure, and uniform target-class radii remain explicit hypotheses in the general compositional setting and are verified for the finite-rank model below. Proposition 5.2 (Finite-rank smoothing implies slice-wise Bellman closure and coverage [ Aiid ]). Let each clock slice ∑︀𝐻 be [0, 1]𝑑 with reference law 𝜈ℎ , let 𝜇𝑆 = 𝜈𝐻 ⊗ 𝛿𝐻 , and use the reset law 𝜍 = 𝐻 −1 ℎ=1 𝜈ℎ ⊗ 𝛿ℎ . Suppose that, for ℎ > 1, the action-𝑎 transition has density 𝑝ℎ,𝑎 (𝑦 | 𝑥) = 1 +
𝑟 ∑︁
𝜑ℎ,𝑎,𝑗 (𝑥)𝜓ℎ,𝑎,𝑗 (𝑦)
relative to 𝜈ℎ−1 ,
𝑗=1
∫︁ 0 ≤ 𝑝ℎ,𝑎 ≤ 𝑀.
𝜓ℎ,𝑎,𝑗 𝑑𝜈ℎ−1 = 0,
and that termination occurs after level one. If, uniformly in (ℎ, 𝑎, 𝑗), 𝑅ℎ,𝑎 and 𝜑ℎ,𝑎,𝑗 lie in a fixed 𝛽-Hölder ball on [0, 1]𝑑 , 0 < 𝛽 ≤ 1, and ‖𝜓ℎ,𝑎,𝑗 ‖1 is bounded, then {𝒯 𝑉 : 𝑉 ∈ 𝒱 clip } lies in a fixed 𝛽-Hölder ball on every clock slice, with a radius uniform in ℎ and 𝑉 . Moreover, for every policy sequence and 1 ≤ 𝑚 < 𝐻, 𝑐2 (𝑚) ≤ 𝐻𝑀,
𝑐∞ (𝑚) ≤ 𝐻𝑀.
Consequently, if 𝒢0,ℎ is this common-radius Hölder ball intersected with the level-ℎ band, then {𝒯 𝑉 : 𝑉 ∈ 𝒱 clip } ⊂ 𝒢0clk , and the closure and uniform-radius clauses of Assumption 5.1 hold. This proposition makes no neural-network approximation, nesting, or entropy claim. Proof. For 𝑉 ∈ 𝒱 clip , ∫︁ (𝒫ℎ,𝑎 𝑉 )(𝑥) =
𝑉 𝑑𝜈ℎ−1 +
𝑟 ∑︁
∫︁ 𝜑ℎ,𝑎,𝑗 (𝑥)
𝜓ℎ,𝑎,𝑗 𝑉 𝑑𝜈ℎ−1 .
𝑗=1
The coefficients are bounded uniformly by 𝑉max ‖𝜓ℎ,𝑎,𝑗 ‖1 ; hence 𝑅ℎ,𝑎 + 𝛾𝒫ℎ,𝑎 𝑉 has a uniform 𝛽-Hölder radius. A finite maximum preserves that radius when 𝛽 ≤ 1, proving closure; the finite number of slices ∫︀ makes the radius uniform ′ in ℎ. If a slice law has density 𝑔 relative to 𝜈ℎ , its successor density 𝑔 is bounded by 𝑀 𝑔 𝑑𝜈ℎ = 𝑀 . Relative to 𝜍 it ∫︀ 2 is therefore at most 𝐻𝑀 , so 𝑐∞ (𝑚) ≤ 𝐻𝑀 and 𝑐2 (𝑚) ≤ 𝐻 𝑔𝑚 𝑑𝜈𝐻−𝑚 ≤ 𝐻𝑀 , where 𝑔𝑚 ≤ 𝑀 is the propagated spatial density at depth 𝑚. Proposition 5.3 (Clock-routed ReLU admissibility for the finite-rank example [ Aiid ]). Under Proposition 5.2, take 𝑑emb = 𝑑, let 𝜄ℎ be the identity on the spatial coordinate, and let every 𝒢0,ℎ be the corresponding band-intersected, common-radius 𝛽-Hölder ball. Let 𝐾𝒢 bound that radius and choose 𝐵net ≥ max{1, 𝑉max , 𝐾𝒢 }. There exist (ℎ) nondecreasing fixed-architecture budgets and nested per-head raw sparse-ReLU families {ℛ𝑚 }𝑚≥2 satisfying Assumption 5.1 with 𝑑 𝑞 = 0, 𝑡 = 𝑑, 𝛼⋆ = , 2𝛽 + 𝑑 including the global approximation (85), product entropy (86), countable dense subclasses, nesting, the output-envelope condition, the corrected depth condition, and the width and sparsity requirements. Hence the finite-rank model, together with the externally clipped clock-routed architecture, verifies all clauses of Assumption 5.1. 20
Deep 𝑉 -Learning: Convergence Framework
⋆
Proof. For this 𝑞 = 0 class, 𝛽 ⋆ = 𝛽, 𝜑𝑚 = 𝑚−2𝛽/(2𝛽+𝑑) , and 𝑚𝜑𝑚 = 𝑚𝑑/(2𝛽+𝑑) = 𝑚𝛼 . Choose the exact depth, hidden widths, and sparsity budgets nondecreasingly so that, for all sufficiently large 𝑚, 𝛽+𝑑 log2 (4𝑑 ∨ 4𝛽) log2 𝑚 ≤ 𝐿𝑚 ≲ 𝑚𝜑𝑚 , 2𝛽 + 𝑑 (87) 𝑚𝜑𝑚 ≲ min 𝑑𝑗,𝑚 , 𝑗
𝑚𝜑𝑚 log 𝑚 ≲ 𝑠𝑚 . while retaining the upper envelopes in (81). Enlarge the finitely many small-𝑚 budgets if necessary. These inequalities are mutually compatible because 𝛼⋆ ∈ (0, 1) and 𝜉 ⋆ ≥ 1. The approximation part of Schmidt–Hieber’s construction, with condition (ii’) of the correction, now applies with sample-size index 𝑚 and output envelope 𝐵net [16, 17]. Uniformly over the fixed Hölder ball it produces a unitparameter raw network 𝑓̃︀ℎ,𝑚 , bounded by 𝐵net , with ⋆ ‖𝑓̃︀ℎ,𝑚 − 𝑔ℎ ‖∞ ≤ 𝐶𝑚−𝛽/(2𝛽+𝑑) = 𝐶𝑚(𝛼 −1)/2 . The constructive network embeds into the declared fixed architecture: pad hidden layers by inactive neurons, and insert any additional identity layers before the constructive network. Inputs lie in [0, 1]𝑑 , so unit-weight, zero-bias identity layers survive ReLU unchanged; their 𝑂(𝑑𝐿𝑚 ) additional nonzero parameters are absorbed by 𝑠𝑚 . This is the standard (ℎ) width/depth embedding used in the cited construction. Thus 𝑓̃︀ℎ,𝑚 ∈ 𝒩𝑚 after padding. For the finitely many small indices, the zero network belongs to the class and the constant 𝐶 can be enlarged, so the bound holds for every 𝑚 ≥ 2. Because 𝑔ℎ lies in the level-ℎ band, Lemma 2.3 gives ̃︀ ̃︀ ‖Πclip ℎ 𝑓ℎ,𝑚 − 𝑔ℎ ‖∞ ≤ ‖𝑓ℎ,𝑚 − 𝑔ℎ ‖∞ . ⋃︀ (ℎ) (ℎ) 𝑚 This proves (84). Take the nested hull ℛ𝑚 = 𝑟=2 𝒩𝑟 ; the finite number of slices makes the approximation constant clk uniform in ℎ. For 𝑔 ∈ 𝒢0 , choose the 𝐻 clipped approximants independently and route by the observed clock. The global supremum error is the maximum of the head errors, proving (85); exact routing therefore preserves the spatial approximation rate without introducing a clock-gate approximation term. (ℎ)
For entropy, Lemma 6.4 of [23] bounds each base raw class 𝒩𝑟 ; imposing the additional raw-output envelope only takes a subclass. A union bound over 2 ≤ 𝑟 ≤ 𝑚 contributes log 𝑚 to the log covering number. Take a 𝛿-net for each resulting raw head class and then apply Πclip ℎ . The Cartesian product of the 𝐻 clipped nets is a 𝛿-net for the routed class because its metric is the maximum of the slice metrics. Summing the log covering numbers gives (86); clipping is nonexpansive by Lemma 2.3. Finite-parameter raw classes are separable, and finite unions, clipping, and the finite routed product preserve a countable dense subclass. The nested hulls and deterministic router give nesting of the global clipped classes. Equation (87) verifies the corrected depth condition and the width/sparsity embedding, while (80) verifies the output-envelope condition. Closure and its uniform radius come from Proposition 5.2, completing every clause of Assumption 5.1. Lemma 5.4 (Oracle inequality for squared loss with bounded targets [ G ]). Let 𝐵 > 0 and let 𝒞 ⊂ {𝑉 : 𝒮̃︀ → [−𝐵, 𝐵]} be deterministic and admit a fixed countable supremum-norm-dense subclass 𝒞0 . Let 𝑔 : 𝒮̃︀ → [−𝐵, 𝐵] be measurable, and let (𝑆𝑖 , 𝑌𝑖 )𝑖≤𝑛 be i.i.d. with 𝑆𝑖 ∼ 𝜌𝑘,𝑆 , |𝑌𝑖 | ≤ 𝐵 and E[𝑌𝑖 | 𝑆𝑖 ] = 𝑔(𝑆𝑖 ). Let 𝑉̂︀𝑘+1 be any measurable 𝜁𝑛 -approximate empirical risk minimizer over 𝒞0 (or over 𝒞 itself when such a measurable minimizer is supplied): ∑︀ ∑︀ 𝑛−1 𝑖≤𝑛 (𝑉̂︀𝑘+1 (𝑆𝑖 ) − 𝑌𝑖 )2 ≤ inf 𝑉 ∈𝒞0 𝑛−1 𝑖≤𝑛 (𝑉 (𝑆𝑖 ) − 𝑌𝑖 )2 + 𝜁𝑛 with 𝜁𝑛 ≥ 0, exact ERM being 𝜁𝑛 = 0. Then, for every 𝛿 ∈ (0, 2𝐵], [︀ ]︀2 𝐶1 𝐵 2 (︀ )︀ E‖𝑉̂︀𝑘+1 − 𝑔‖22,𝜌𝑘,𝑆 ≤ 2 dist2,𝜌𝑘,𝑆 (𝒞, 𝑔) + 1 + log 𝑁𝛿 (𝒞) + 𝐶1 𝐵𝛿 + 2𝜁𝑛 , (88) 𝑛 with an absolute 𝐶1 ; the proof is valid for every 𝐶1 ≥ 140 and makes no use of its value. Here dist2,𝜌𝑘,𝑆 (𝒞, 𝑔) is the 𝐿2 (𝜌𝑘,𝑆 ) distance from the class to a single target and 𝑁𝛿 (𝒞) the supremum-norm covering number, assumed finite. The same inequality holds conditionally on a sigma-algebra relative to which 𝒞, 𝑔, and 𝜌𝑘,𝑆 are fixed, provided the sample is conditionally i.i.d. and E[𝑌𝑖 | 𝑆𝑖 , 𝒦] = 𝑔(𝑆𝑖 ); it is used below with 𝒦 = ℋ𝑘 for Aiid . The approximation term is in 𝐿2 (𝜌𝑘,𝑆 ) and only the covering radius is in supremum norm; since 𝜌𝑘,𝑆 is a probability measure the statement implies, and is stronger than, its supremum-norm form. If, additionally, 𝑔 ∈ 𝒞 and 𝑉̂︀𝑘+1 is a supplied measurable exact ERM over 𝒞, then for every 𝜏 ∈ (0, 1), conditionally on the same fixed information when present, with probability at least 1 − 𝜏 , )︀ 𝐶1 𝐵 2 (︀ ‖𝑉̂︀𝑘+1 − 𝑔‖22,𝜌𝑘,𝑆 ≤ 1 + log 𝑁𝛿 (𝒞) + log(1/𝜏 ) + 𝐶1 𝐵𝛿. (89) 𝑛 21
Deep 𝑉 -Learning: Convergence Framework
Proof: See Appendix A. Proposition 5.5 (Generative-reset clock-routed scalar-𝑉 regression [ Aiid ]). Under Assumption 5.1, fix 𝑛 ≥ 2𝐻, condition on ℋ𝑘 , and let 𝑉𝑘 ∈ ℱ𝑛𝑉 . Let (𝑆𝑖 , a𝑖 , 𝑟𝑖 , 𝑠˜′𝑖 , 𝑑𝑖 )𝑖≤𝑛 be the i.i.d. sample of Aiid (3), with 𝑆𝑖 ∼ 𝜌𝑘,𝑆 ≡ 𝜍, a𝑖 ∼ 𝛽𝑘 (· | 𝑆𝑖 ), fresh true-kernel outcomes and labels 𝑌𝑖 = 𝑟𝑖 + 𝛾(1 − 𝑑𝑖 )𝑉𝑘 (˜ 𝑠′𝑖 ), and let 𝑉̂︀𝑘+1 be any measurable 𝑉,0 𝜁𝑛 -approximate ERM over the fixed countable dense subclass ℱ𝑛 . By construction, E[𝑌𝑖 | 𝑆𝑖 , ℋ𝑘 ] = 𝐺𝑘 (𝑆𝑖 ). Define the 𝐿2 policy-image defect ⃦ ⃦ (2) 𝐷𝑘 := ⃦𝐺𝑘 − 𝒯 𝑉𝑘 ⃦2,𝜌 , (90) 𝑘,𝑆
a quantity and not a hypothesis. Then there is a constant 𝐶Vreg,𝐻 , uniform in 𝑘, 𝑛, and the realized 𝑉𝑘 ∈ ℱ𝑛𝑉 under the uniformity clause of Assumption 5.1. It may depend on 𝐻, 𝛾, 𝑅max through 𝑉max , on |𝒜| through the assumed target class, and on 𝐶1 , 𝐶appx , the architecture and covering constants, the fixed router and slice embeddings, and the compositional indices and Hölder radii, but not on 𝑛, 𝑘, or the realized iterate. Then √︀ √ ⃒ [︀ ]︀ ⋆ ⋆ (2) −1)/2 (91) E ‖𝑉̂︀𝑘+1 − 𝐺𝑘 ‖2,𝜌𝑘,𝑆 ⃒ ℋ𝑘 ≤ 𝐶Vreg,𝐻 (log 𝑛)(1+2𝜉 )/2 𝑚(𝛼 + 2𝜁𝑛 + 2 𝐷𝑘 . 𝑛 (2)
Greedy collection is the case 𝐷𝑘 = 0: if a𝑖 = 𝑎⋆ (𝑆𝑖 ; 𝑉𝑘 ) then 𝐺𝑘 = 𝒯 𝑉𝑘 by Lemma 2.4(iii) and ⃒ ]︁ [︁ √︀ ⋆ ⋆ ⃒ −1)/2 + 2𝜁𝑛 . E ‖𝑉̂︀𝑘+1 − 𝒯 𝑉𝑘 ‖2,𝜌𝑘,𝑆 ⃒ ℋ𝑘 ≤ 𝐶Vreg,𝐻 (log 𝑛)(1+2𝜉 )/2 𝑚(𝛼 𝑛
(92)
The required closure is precisely the Bellman condition 𝒯 𝑉 ∈ 𝒢0clk with uniform compositional Hölder radii from Assumption 5.1. The policy-image discrepancy of 𝐺𝑘 remains in the bound: choosing the comparator in 𝐿2 (𝜌𝑘,𝑆 ) (2) produces exactly 𝐷𝑘 , which Proposition 5.6 bounds by the named residuals. Proof: See Appendix A. Proposition 5.6 (Bounding the regression defect in 𝐿2 [ R ]). For every block 𝑘, the defect in (90) satisfies (2) (2) ¯ exp 𝐷𝑘 ≤ 𝜀ker,𝑘 + 𝜀tgt,𝑘 + 𝜀buf,𝑘 + 𝜀act,𝑘 + 𝜀𝑘 𝐷 𝑘
¯ exp . ≤ 𝜀ker,𝑘 + 𝜀tgt,𝑘 + 𝜀buf,𝑘 + (1 − 𝜀𝑘 )2Λ𝑘 + 𝜀𝑘 𝐷 𝑘 If the global frozen-iterate margin holds, or its local form holds with 2Λ𝑘 ∈ [𝑢0 , 𝑢 ¯], then the sharper bound √︀ }︀ {︀ (2) ¯ exp 𝐷𝑘 ≤ 𝜀ker,𝑘 + 𝜀tgt,𝑘 + 𝜀buf,𝑘 + (1 − 𝜀𝑘 ) min 2Λ𝑘 , 𝐶marg (2Λ𝑘 )1+𝛼/2 + 𝜀𝑘 𝐷 𝑘
(93) (94)
(95)
also holds. Under Proposition 4.3, the same display holds with its action term replaced by {︁ [︀ ]︀1/2 }︁ (1 − 𝜀𝑘 ) min 2Λ𝑘 , 2Λ𝑘 𝜏⋆ + 𝐶⋆ (2Λ𝑘 + 2𝛿𝑘⋆ )𝛼⋆ . The norm choice is essential. Consider the favorable no-mismatch case 𝜀𝑘 = 0, 𝛽𝑘rep = 𝜋𝑘on , and 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 0, on so 𝐺𝑘 = 𝒯 𝜋𝑘 𝑉𝑘 . Suppose the selected action switches at 𝑠˜0 between 𝑎 and 𝑎′ , the two functions 𝑄𝑉𝑘 (·, 𝑎), 𝑄𝑉𝑘 (·, 𝑎′ ) are continuous there, and every neighborhood of 𝑠˜0 has positive 𝜌𝑘,𝑆 -mass in both selection regions. If 𝐽𝑘 := |𝑄𝑉𝑘 (˜ 𝑠0 , 𝑎) − 𝑄𝑉𝑘 (˜ 𝑠0 , 𝑎′ )| > 0, write dist∞,𝜌 (𝒞, 𝑔) := inf ess sup |𝑓 − 𝑔|. 𝑓 ∈𝒞
𝜌
Then every class 𝒞 whose members are continuous at 𝑠˜0 satisfies dist∞,𝜌𝑘,𝑆 (𝒞, 𝐺𝑘 ) ≥ 12 𝐽𝑘 .
(96)
The construction of Proposition 4.7 realizes 𝐽𝑘 = 2Λ𝑘 ; hence a continuous supremum-norm comparator remains linear in Λ𝑘 for every margin exponent. Proof. 𝐺𝑘 − 𝒯 𝑉𝑘 is the tail of the telescope of Lemma 3.13 from 𝐺𝑘 to 𝒯 𝑉𝑘 , so the triangle inequality in the common space 𝐿2 (𝜌𝑘,𝑆 ) along those links gives (93). Bound (75) at 𝑟 = 2, with Corollary 4.6 for a period-level mixture, then gives (94). Under the stated margin hypotheses, Bound (76) at 𝑟 = 2 gives the margin term; taking the smaller of the two valid action bounds proves (95). The same argument using (77) proves the reference-gap version. For (96), 𝐺𝑘 has one-sided essential limits 𝑄𝑉𝑘 (˜ 𝑠0 , 𝑎) and 𝑄𝑉𝑘 (˜ 𝑠0 , 𝑎′ ) along the two selection regions. A function continuous at 𝑠˜0 has one limit and therefore cannot lie within less than half their separation of both; the positive-mass condition turns this into an essential-supremum bound. At the switching point in Proposition 4.7, that separation is 2𝛾𝛿 = 2Λ𝑘 . 22
Deep 𝑉 -Learning: Convergence Framework
Corollary 5.7 (Tabular generative-reset bound with known envelopes [ Aiid ]). Assume 𝐻 ≥ 2. Let 𝒮̃︀∘ be finite, 𝑁 := |𝒮̃︀∘ |, and replace Assumption 5.1 by the fixed level-wise clipped tabular class ℱ tab := 𝒱 clip . This class is exactly Bellman closed and admits a measurable exact coordinatewise ERM: the label average at a visited state and zero at an unvisited state. Condition on the pre-block history and write 𝑝𝑘,𝑠 := 𝜌𝑘,𝑆 {𝑠}, 𝑔𝑘,𝑠 := E[𝑌 | 𝑆 = 𝑠, ℋ𝑘 ], 2 𝜎𝑘,𝑠 := Var(𝑌 | 𝑆 = 𝑠, ℋ𝑘 ), and 𝑁𝑘,𝑠 for the number of visits to 𝑠 in the 𝑛𝑘 -sample block. Then, with zero-mass coordinates understood to contribute zero, its exact conditional squared risk is ⃒ }︂ ]︂ [︂ {︂ [︁ ]︁ ∑︁ 1{𝑁𝑘,𝑠 > 0} ⃒⃒ 2 𝑛𝑘 2 2 E ‖𝑉𝑘+1 − 𝑔𝑘 ‖2,𝜌𝑘,𝑆 | ℋ𝑘 = 𝑝𝑘,𝑠 𝜎𝑘,𝑠 E . (97) ⃒ ℋ𝑘 + 𝑔𝑘,𝑠 (1 − 𝑝𝑘,𝑠 ) 𝑁𝑘,𝑠 𝑠∈𝒮̃︀∘
Since |𝑌 | ≤ 𝑉max , Jensen and the binomial count calculation in the proof give the log-free deterministic fit envelope √︃ √︃ 𝑛𝑘 } 𝑁 {2 + (𝑛 /(𝑛 + 1)) 5𝑁 𝑘 𝑘 stattab := 𝑉max ≤ 𝑉max , (98) 𝑘 𝑛𝑘 + 1 2(𝑛𝑘 + 1) √︃ 22𝑁 𝑛𝑘 ≥ 2 : stattab ≤ 𝑉max . 𝑘 9(𝑛𝑘 + 1) Suppose further that a fixed full-support reset law 𝜍 is also the state design law 𝜌𝑘,𝑆 ; the fresh collection and replay action laws coincide; slot (S6) uses (SAMPLE, OBS); 𝑂 = 𝑆; and 𝑊𝑘 = 𝑉𝑘 . Then 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 𝜀buf,𝑘 = 𝜀alias,𝑘 = 𝛿𝑉,𝑘 = 0,
Λ𝑘 = 𝜂sc,𝑘 ,
(99)
and, for every 𝐾 ≥ 𝐻 − 1, E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ 2𝜑(𝐻) 𝑠
max
𝐾−𝐻<𝑘<𝐾
[︀ ]︀ ¯ exp , stattab 𝑘 + 𝐴𝜂,𝑘 + 𝜀𝑘 𝐷𝑘
(100)
(𝑝)
where 𝐴𝜂,𝑘 is the chosen envelope 𝜀act,𝑘 : 𝐴𝜂,𝑘 := (1 − 𝜀𝑘 )2𝜂sc,𝑘 without a margin, while under the frozen-iterate 1/𝑝
margin at scale 2𝜂sc,𝑘 it may be replaced by (1 − 𝜀𝑘 ) min{2𝜂sc,𝑘 , 𝐶marg (2𝜂sc,𝑘 )1+𝛼/𝑝 }. Thus every residual slot is zero or explicitly bounded; if 𝜂sc,𝑘 → 0, 𝑛𝑘 → ∞, and 𝜀𝑘 → 0, the right side tends to zero. There is also a finite-confidence form whose tabular regression term has no additional minimum-state-mass factor; (𝐻) coverage in the policy bound still enters through 𝜑𝑠 . For 𝛿 ∈ (0, 1) and fixed 𝐾 ≥ 𝐻 − 1, put √︃ 𝐶1 {2 + 𝑁 log(2𝑛𝑘 + 1) + log((𝐻 − 1)/𝛿)} tab,hp stat𝑘,𝐾 (𝛿) := 𝑉max . (101) 𝑛𝑘 Then, with probability at least 1 − 𝛿 over the adaptive fresh blocks, [︁ ]︁ ¯ exp . ‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ 2𝜑(𝐻) max stattab,hp 𝑠 𝑘,𝐾 (𝛿) + 𝐴𝜂,𝑘 + 𝜀𝑘 𝐷𝑘 𝐾−𝐻<𝑘<𝐾
(102)
Proof: See Appendix A.
6
Deployment and consistency
The main bound evaluates a true-𝑄 greedy policy, whereas the deployed controller uses the implemented final score. Theorem 6.1 bounds the resulting difference, and Corollary 6.6 gives consistency when the residuals decay. 6.1
Implemented-score controller
Theorem 6.1 (Survival-aware transfer to the implemented-score controller [ R ]). Assume the hypotheses of Theorem 3.18, let 𝜋 ̂︀𝐾 = ̂︀ 𝑎⋆ (·; 𝑉𝐾 ) be the deployed policy from (2), stationary on the clock-augmented state (and generally nonstationary on the physical state alone), and let 𝜂sc,𝐾 be a deterministic upper bound on the score error at the final ̂︀ 𝑉 − 𝑄𝑉 ‖∞ ≤ 𝜂sc,𝐾 almost surely. Suppose also that deterministic 𝑞¯ℓ ∈ [0, 1] satisfy, almost frozen network, ‖𝑄 𝐾 𝐾 surely, 𝜇∘𝑆 (𝒫∘𝜋̂︀𝐾 )ℓ 1 ≤ 𝑞¯ℓ , 0 ≤ ℓ < 𝐻; (103) 23
Deep 𝑉 -Learning: Convergence Framework
the universal choice is 𝑞¯ℓ = 1. Then 𝐾−1 𝐻−1 ]︁ [︁ ∑︁ (𝐻) ∑︁ E ‖𝑉 ⋆ − 𝑉 𝜋̂︀𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 𝑤𝐾,𝑘 𝑒Bell 𝛾 ℓ 𝑞¯ℓ , 𝑘,𝑝 + 2𝜂sc,𝐾 𝑘=0
(104)
ℓ=0
that is, decomposition (49) holds for the deployed controller with a single survival-weighted score term. It is never worse than 2𝜂sc,𝐾 min{𝐻, (1 − 𝛾)−1 }, and no margin assumption is used. Proof. Let 𝑑𝐾 := 𝒯 𝑉𝐾 − 𝒯 𝜋̂︀𝐾 𝑉𝐾 . The fixed Borel rule makes 𝜋 ̂︀𝐾 measurable, deterministic and stationary, and Lemma 4.4(iii) gives pointwise 0 ≤ 𝑑𝐾 (˜ 𝑠) = 𝑄𝑉𝐾 (˜ 𝑠, 𝑎⋆ (˜ 𝑠; 𝑉𝐾 )) − 𝑄𝑉𝐾 (˜ 𝑠, 𝜋 ̂︀𝐾 (˜ 𝑠)) ≤ 2𝜂sc,𝐾 . Repeating Lemma 3.10 changes only its nonnegative Singh–Yee loss-resolvent step [24], adding after integration 𝐻−1 𝐻−1 ∑︁ ∫︁ ∑︁ 𝛾 ℓ 𝑑𝐾 𝑑{𝜇∘𝑆 (𝒫∘𝜋̂︀𝐾 )ℓ } ≤ 2𝜂sc,𝐾 𝛾 ℓ 𝑞¯ℓ . ℓ=0
ℓ=0
Clock nilpotence gives the finite sum. All other residual branches and the coverage step are unchanged because 𝜋 ̂︀𝐾 is a measurable deterministic policy, proving (104). Corollary 6.2 (Final-law coverage and margin for deployment [ R ]). In the setting of Theorem 6.1, set Γ𝐾 = 0 when 𝜂sc,𝐾 = 0, in which case no gap condition is needed. When 𝜂sc,𝐾 > 0, suppose the final true gap either satisfies the global frozen-iterate margin (70) under 𝜌𝐾,𝑆 almost surely (or its local form at 2𝜂sc,𝐾 ), or satisfies the fixed-𝑄⋆ transfer conditions of Proposition 4.3 at 𝑘 = 𝐾 and 𝑢 = 2𝜂sc,𝐾 . Set Γ𝐾 by the corresponding case: {︃ 1/𝑝 𝐶marg (2𝜂sc,𝐾 )1+𝛼/𝑝 , under the frozen-iterate margin, Γ𝐾 := (105) {︀ }︀ ⋆ 𝛼⋆ 1/𝑝 2𝜂sc,𝐾 𝜏⋆ + 𝐶⋆ (2𝜂sc,𝐾 + 2𝛿𝐾 ) , under the fixed-𝑄⋆ transfer. Assume also that, for the same 𝑠 ∈ [2, ∞] and 𝑝 = 𝑠/(𝑠 − 1) as in Assumption 3.3, deterministic envelopes 𝑑fin 𝑠 (ℓ) < ∞ satisfy ⃦ ⃦ ⃦ 𝑑{𝜇∘𝑆 𝒫∘𝜋1 · · · 𝒫∘𝜋ℓ } ⃦ ⃦ ≤ 𝑑fin 0 ≤ ℓ < 𝐻, (106) sup ⃦ 𝑠 (ℓ), ⃦ ⃦ 𝑑𝜌𝐾,𝑆 𝜋 𝑠,𝜌𝐾,𝑆
1:ℓ
almost surely, with the empty product at ℓ = 0. Then 𝐾−1 𝐻−1 [︁ ]︁ ∑︁ (𝐻) ∑︁ E ‖𝑉 ⋆ − 𝑉 𝜋̂︀𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 𝑤𝐾,𝑘 𝑒Bell + Γ 𝛾 ℓ 𝑑fin 𝐾 𝑘,𝑝 𝑠 (ℓ). 𝑘=0
(107)
ℓ=0
If both (103) and (106) hold, the final term can be sharpened depthwise to 𝐻−1 ∑︁
{︀ }︀ 𝛾 ℓ min 2𝜂sc,𝐾 𝑞¯ℓ , Γ𝐾 𝑑fin 𝑠 (ℓ) .
(108)
ℓ=0
Proof. Condition on the final history and put 𝑑𝐾 := 𝒯 𝑉𝐾 − 𝒯 𝜋̂︀𝐾 𝑉𝐾 . The score comparison gives 0 ≤ 𝑑𝐾 ≤ 2𝜂sc,𝐾 (𝐾) and {𝑑𝐾 > 0} ⊆ {∆𝑄 ≤ 2𝜂sc,𝐾 }. Hence ‖𝑑𝐾 ‖𝑝,𝜌𝐾,𝑆 ≤ Γ𝐾 : use (70) on the support event for the first route and ∫︀ ∑︀ (73) for the second. The exact extra resolvent contribution is ℓ<𝐻 𝛾 ℓ 𝑑𝐾 𝑑{𝜇∘𝑆 (𝒫∘𝜋̂︀𝐾 )ℓ }. Hölder and (106) prove (107). At each depth the same integral is also at most 2𝜂sc,𝐾 𝑞¯ℓ ; taking the smaller bound before summing gives (108). There is no additional factor two: the resolvent inserts the single defect 𝑑𝐾 . 6.2
Consistency of the abstract recursion
Theorem 6.3 (Nonasymptotic generative-reset policy-loss bound under uniform closure [ Aiid ]). Assume the hypotheses of Theorem 3.18 and Assumption 5.1, specializing Assumption 3.3 to 𝑠 = 2 (and hence 𝑝 = 2), with 𝐻 ≥ 2. In every block, additionally use the fresh-block protocol (3): conditional on ℋ𝑘 , draw 𝑛𝑘 ≥ 2𝐻 i.i.d. true-kernel outcomes with the fixed state law 𝜌𝑘,𝑆 ≡ 𝜍 and action law 𝛽𝑘 , rebuild 𝑌𝑖 = 𝑟𝑖 + 𝛾(1 − 𝑑𝑖 )𝑉𝑘 (˜ 𝑠′𝑖 ), and take a 𝑉,0 𝑉 measurable 𝜁𝑛𝑘 -approximate ERM 𝑉𝑘+1 ∈ ℱ𝑛𝑘 with 𝑉𝑘 ∈ ℱ𝑛𝑘 . These labels are conditionally unbiased for 𝐺𝑘 , 𝛼⋆ −1 √︀ 1+2𝜉⋆ Bell 2 and 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 0. Write 𝑒Bell 𝑚𝑛𝑘2 + 2𝜁𝑛𝑘 , where 𝑘,2 := 𝑒𝑘,𝑝 |𝑝=2 and stat𝑘 := 𝐶Vreg,𝐻 (log 𝑛𝑘 ) 24
Deep 𝑉 -Learning: Convergence Framework
𝑚𝑛𝑘 = ⌊𝑛𝑘 /𝐻⌋. Then the fit envelope in (24) may be chosen from Propositions 5.5 and 5.6, so for every 𝑘 the Bellman-residual envelope may be chosen to satisfy √ (︀ (2) )︀ ¯ exp , 𝑒Bell 2) 𝜀act,𝑘 + 𝜀buf,𝑘 + 𝜀𝑘 𝐷 (109) 𝑘,2 ≤ stat𝑘 + (1 + 𝑘 and hence, for every finite 𝐾 ≥ 1, (𝐻)
E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 2𝜑2,𝐾
max
𝑒Bell 𝑘,2,rhs ,
max{0,𝐾−𝐻+1}≤𝑘<𝐾
(110)
𝑒Bell 𝑘,2,rhs denoting the right-hand side of (109). Under the global frozen-iterate (𝐶marg , 𝛼) margin, or its local form √︀ (2) with 2Λ𝑘 ∈ [𝑢0 , 𝑢 ¯], 𝜀act,𝑘 may be replaced by (1 − 𝜀𝑘 ) min{2Λ𝑘 , 𝐶marg (2Λ𝑘 )1+𝛼/2 }, so the exponent reaches the √ propagated residual bound at the cost of the constant 1 + 2. The fixed-𝑄⋆ route uses the 𝑟 = 2 envelope in (77) and preserves the same propagated exponent when 𝜏⋆ = 0 and 𝛿𝑘⋆ = 𝑂(Λ𝑘 ) on the active window. Proof: See Appendix A. Corollary 6.4 (Expected policy-loss consistency with an exact-score oracle [ Aiid ]). Assume Theorem 6.3, fixed 𝐻, (𝐻) and 𝜑𝜇𝑆 ,𝜌 < ∞. Initialize 𝑉0 ∈ ℱ𝑛𝑉0 ; use a nondecreasing integer schedule 𝑛𝑘 ≥ 2𝐻 with 𝑛𝑘 → ∞ and 𝜁𝑛𝑘 → 0; set 𝑊𝑘 = 𝑉𝑘 ; use the additional exact expectation oracle 𝑄or 𝑉 = 𝑄𝑉 on ℱ with the common tie rule; draw fresh (SAMPLE, OBS) blocks; and let 𝜀𝑘 → 0. Then, for every 𝐾 ≥ 𝐻 − 1, [︁ ]︁ √ E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ 2𝜑(𝐻) max stat𝑘 + 2(1 + 2)𝑉max 𝜀𝑘 −→ 0. (111) 𝜇𝑆 ,𝜌 𝐾−𝐻<𝑘<𝐾
If the same oracle is used at deployment, its final greedy policy equals 𝜋𝐾 , so the same conclusion holds for that deployed oracle policy. Proof. By nesting, 𝑉𝑘+1 ∈ ℱ𝑛𝑉,0 ⊆ ℱ𝑛𝑉𝑘 ⊆ ℱ𝑛𝑉𝑘+1 , so the initialization closes the iterate membership required by 𝑘 Theorem 6.3. Fresh observed blocks give 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 𝜀buf,𝑘 = 0, while synchronization and the exact score give (2) ¯ exp = 2𝑉max . Substitution in (110) proves the Λ𝑘 = 𝜀act,𝑘 = 0; take the safe deterministic exploration envelope 𝐷 𝑘 ⋆ displayed bound, whose right-hand side vanishes because 𝛼 < 1, fixed 𝐻 and 𝑛𝑘 → ∞ imply 𝑚𝑛𝑘 = ⌊𝑛𝑘 /𝐻⌋ → ∞, 𝜁𝑛𝑘 → 0, and 𝜀𝑘 → 0; oracle final scoring and the common tie rule identify its deployed policy with 𝜋𝐾 . Corollary 6.5 (Known deterministic-model consistency [ Aiid ]). Assume all hypotheses of Corollary 6.4 except for its separate exact-score oracle. Suppose that the joint kernel is deterministic, (𝑟, 𝑠˜′ ) = (𝑅(˜ 𝑠, 𝑎), 𝐹 (˜ 𝑠, 𝑎)), and that ̂︀ 𝑉 (˜ 𝑠, 𝑎) = 𝑅(˜ 𝑠, 𝑎) + 𝛾𝑉 (𝐹 (˜ 𝑠, 𝑎)) equals 𝑄or the controller has the exact maps 𝑅, 𝐹 . Then the point score 𝑄 𝑉 = 𝑄𝑉 without a separate expectation oracle, so the same policy-loss consistency conclusion holds. 𝑠, 𝑎); hence 𝜂sc,𝑘 = 𝜂sc,𝐾 = 0, and Proof. The deterministic kernel makes the Bellman integral equal evaluation at 𝐹 (˜ Corollary 6.4 applies verbatim. Corollary 6.6 (Deployed-policy convergence and upper neighborhood [ R, Aiid ]). Let 𝜋 ̂︀𝐾 and 𝜂sc,𝐾 be as in Theorem 6.1, ⋆ 𝜋𝐾 and fix 𝐻. (a) [ R ] 𝑒Bell → 0 implies E‖𝑉 − 𝑉 ‖ → 0; if also 𝜂 → 0, then E‖𝑉 ⋆ − 𝑉 𝜋̂︀𝐾 ‖1,𝜇𝑆 → 0. 1,𝜇𝑆 sc,𝐾 𝑘,𝑝 (b) [ Aiid ] Assume Theorem 6.3 and either the global frozen-iterate margin or a local frozen-iterate margin whose interval contains 2Λ𝑘 for every sufficiently large 𝑘. Suppose 𝑛𝑘 → ∞, 𝜁𝑛𝑘 → 0, 𝜀buf,𝑘 , 𝜀𝑘 , 𝛿𝑉,𝑘 → 0, while eventually 𝜂sc,𝑘 ≤ 𝜂sc and 𝜂sc,𝐾 ≤ 𝜂sc . Then √ √︀ 1+𝛼/2 lim sup E[‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ] ≤ 𝑅sc , 𝑅sc := 2(1 + 2) 𝜑(𝐻) , (112) 𝜇𝑆 ,𝜌 𝐶marg (2𝜂sc ) 𝐾→∞
𝐻−1 [︁ ]︁ ∑︁ lim sup E ‖𝑉 ⋆ − 𝑉 𝜋̂︀𝐾 ‖1,𝜇𝑆 ≤ 𝑅sc + 2𝜂sc 𝛾 ℓ 𝑞¯ℓ . 𝐾→∞
(113)
ℓ=0
√ (𝐻) Without a margin the same two bounds hold with 𝑅sc := 4(1 + 2)𝜑𝜇𝑆 ,𝜌 𝜂sc . In particular, if 𝜂sc,𝑘 → 0 and 𝜂sc,𝐾 → 0, then both the true-score and deployed-policy losses converge to zero. Proof. In Theorem 3.18, the boundary vanishes for 𝐾 ≥ 𝐻 − 1 and only the last 𝐻 − 1 Bellman residuals have nonzero weights, proving the first claim in (a); Theorem 6.1 proves the second. For (b), Proposition 5.6 and (76) at 𝑟 = 2 give the true-score radius 𝑅sc after all statistical and nonaction residuals vanish; the survival term of Theorem 6.1 gives the deployed radius. Without a margin, use (75) at 𝑟 = 2 in the same calculation. If 𝜂sc,𝑘 → 0, that linear bound and the remaining hypotheses give 𝑒Bell 𝑘,2 → 0; with 𝜂sc,𝐾 → 0, part (a) then yields the last assertion. 25
Deep 𝑉 -Learning: Convergence Framework
6.3
Convergence conditions for implementations
To apply the policy-loss bounds to Arun , we bound its six residuals and the final score error, as indicated in (1). For observation-based navigation, Proposition 3.17 permits either a Markov-sufficient simulator or belief state with an exposed clock, or a measurable compression whose visible-target aliasing and score errors are controlled by the corresponding residuals. Sufficient conditions for FIFO/interleaved SGD. For fixed 𝐻, the same policy-loss theory applies to a concrete FIFO/interleaved-SGD implementation when: (i) its state satisfies the standard-Borel controlled Markov condition or its compression residuals are controlled; (ii) finite concentrability constants hold uniformly over its induced replay laws; and (iii) (︁ )︁ (𝑝) ¯ exp −→ 0, max 𝜀fit,𝑘 + 𝜀ker,𝑘 + 𝜀tgt,𝑘 + 𝜀buf,𝑘 + 𝜀act,𝑘 + 𝜀𝑘 𝐷 𝜂sc,𝐾 −→ 0. (114) 𝑘 𝐾−𝐻<𝑘<𝐾
The unconditional linear bound gives action-residual decay when 𝛿𝑉,𝑘 → 0 and 𝜂sc,𝑘 → 0, while the margin condition upgrades this decay to the sharp exponent. For stored prediction labels, 𝜀tgt,𝑘 must also cover the predictor staleness in (29); current score accuracy and target-network staleness alone do not control it. Setting 𝜀ker,𝑘 = 0 for stored labels requires a justification such as the metadata-conditioned law (27). Bounds for a particular replay scheme, optimizer, score estimator, or state representation enter the propagation and deployment theorems through the corresponding residuals. Their decay gives convergence through (114). 6.4
Related work
Fitted value iteration. Munos and Szepesvári analyze fitted value iteration by estimating every action’s continuation and then maximizing [1]. The population response in our state-only reset construction instead averages the executed action and carries a finite clock. It also differs from the action-indexed response used in fitted 𝑄 regression [25, 26]. Once this operator distinction is isolated, the propagation analysis follows the 𝐿𝑝 approximate-dynamic- programming tradition [27–29]. As in that literature, stability depends on the sampling and update structure [30, 31]. SARSA and Expected SARSA. SARSA provides the closest target semantics. A current observed-successor statevalue target under fresh sampling averages the acting law, whereas Expected SARSA updates 𝑄(𝑠, 𝑎) and averages the next action [7]. Convergence results for SARSA with function approximation require smooth improvement, ergodicity, or linear approximation [32–34]. Here the acting law’s same-state departure from its frozen-target greedy comparator remains a separate residual. Neural 𝑄 and TD analyses. Neural fitted 𝑄-iteration separates statistical and iterative error [23]. Its action-indexed response and the scalar executed-action response studied here define distinct population operators. Neural TD treats fixed-policy evaluation [35], while neural 𝑄-learning and DQN use different heads and sampling or update hypotheses [36, 37]. Our analysis identifies replay, scalar-target, and policy-drift residuals as the additional quantities for a deep-𝑉 implementation analysis. DQN, Double 𝑄 bias correction, and residual-gradient TD address related algorithmic objects [31, 38, 39]. Action gaps. Action-gap regularity can convert uniform value or score approximation into superlinear greedy-policy bounds [14, 15]. The classical fixed-optimal positive-gap law controls {0 < ∆⋆𝑄 ≤ 𝑢} and can retain mass on optimal (𝑘)
ties. The condition used here controls {∆𝑄 ≤ 𝑢}, including ties, uniformly over the random frozen iterates and replay laws. Proposition 4.3 connects the two: a fixed-𝑄⋆ margin and an iterate score tube yield a shifted frozen-gap bound. When the tie mass is zero and the tube is on the action-error scale, the exponent is preserved. The resulting Tsybakov-type bound [13] has one-step exponent 1 + 𝛼/𝑝 under conjugate 𝐿𝑠 /𝐿𝑝 coverage; Proposition 4.7 attains each intermediate exponent. Replay and dependent data. Antos et al. require a stationary exponentially mixing path for their dependent fitted-policy analysis [40]. Replay-buffer, 𝑄-learning, and TD analyses impose different processes [41–43]. Their process-specific techniques provide tools for bounding the named FIFO and SGD residuals in (1). In our notation, 𝜀buf,𝑘 measures a same-state operator distance, while concentrability controls the relation between replay and evaluation occupancy laws [44]. 26
Deep 𝑉 -Learning: Convergence Framework
7
Conclusion
We established a finite-horizon convergence framework that converts the six deep-𝑉 -learning residuals into expected policy loss. For fixed 𝐻, only the last 𝐻 − 1 update blocks carry residual weight, together with an initialization term for shorter runs. For 𝐾𝐻 ≥ 𝐻 − 1, the near-unit one-state-per-level witness attains the optimal shared-law propagation-coefficient order Θ(𝐻 5/2 ) at 𝑠 = 2; bounded direct-level coefficients give 𝑂(𝐻 2 ). A frozen-gap margin changes the action term to exponent 1 + 𝛼(1 − 1/𝑠), and the one-step construction attains that exponent. The fixed-𝑄⋆ transfer keeps the tie mass visible. Survival and final-law arguments extend the bound to the policy selected by the implemented score. The matched-budget result gives the unconstrained continuous optimum, the constrained water-filling solution, and an integer schedule within a factor 2𝜈 of the latter. On the near-unit one-state-per-level witness, root-𝑛 rates give a clock √ 3 term 𝐻 / N before regression constants; under equal, sufficiently large terminal-window label budgets, direct tabular √ reset improves the statistical bound by a factor of order 𝐻 compared with a shared 𝐻-state fit. Bellman–Hölder closure and the clock-routed ReLU class give the fixed-𝐻 neural rate, while the tabular case gives a log-free expected fit rate. These results prove expected policy-loss consistency for the exact-score generative-reset approximate-ERM procedure at fixed 𝐻. For FIFO/interleaved SGD, (114) gives an explicit residual-decay criterion linking replay, optimization, score-estimation, and representation rates to full policy-loss convergence.
References [1] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9:815–857, 2008. [2] Yu Fan Chen, Miao Liu, Michael Everett, and Jonathan P. How. Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning. In Proceedings of the IEEE International Conference on Robotics and Automation, pages 285–292, 2017. [3] Yu Fan Chen, Michael Everett, Miao Liu, and Jonathan P. How. Socially aware motion planning with deep reinforcement learning. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2017. URL https://arxiv.org/abs/1703.08862. [4] Changan Chen, Yuejiang Liu, Sven Kreiss, and Alexandre Alahi. Crowd-robot interaction: Crowd-aware robot navigation with attention-based deep reinforcement learning. In Proceedings of the IEEE International Conference on Robotics and Automation, pages 6015–6022, 2019. [5] Yury Kolomeytsev and Dmitry Golembiovsky. Robot navigation with entity-based collision avoidance using deep reinforcement learning. arXiv preprint arXiv:2408.14183, 2024. URL https://arxiv.org/abs/2408.14183. [6] Yury Kolomeytsev and Dmitry Golembiovsky. Hybrid motion planning with deep reinforcement learning for mobile robot navigation. arXiv preprint arXiv:2512.24651, 2025. URL https://arxiv.org/abs/2512.24651. [7] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2 edition, 2018. [8] Erwin Kreyszig. Introductory Functional Analysis with Applications. Wiley, 1989. [9] Dimitri P. Bertsekas and Steven E. Shreve. Stochastic Optimal Control: The Discrete-Time Case. Academic Press, 1978. [10] Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996. [11] Onésimo Hernández-Lerma and Jean B. Lasserre. Discrete-Time Markov Control Processes: Basic Optimality Criteria. Springer, 1996. [12] Enno Mammen and Alexandre B. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6): 1808–1829, 1999. doi: 10.1214/aos/1017939240. [13] Alexandre B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1): 135–166, 2004. doi: 10.1214/aos/1079120131. [14] Amir-massoud Farahmand. Action-gap phenomenon in reinforcement learning. In Advances in Neural Information Processing Systems, volume 24, pages 172–180, 2011. [15] Marc G. Bellemare, Georg Ostrovski, Arthur Guez, Philip S. Thomas, and Rémi Munos. Increasing the action gap: New operators for reinforcement learning. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1476–1483, 2016. [16] Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 48(4):1875–1897, 2020. doi: 10.1214/19-AOS1875. 27
Deep 𝑉 -Learning: Convergence Framework
[17] Johannes Schmidt-Hieber and Don Vu. Correction to “nonparametric regression using deep neural networks with relu activation function”. The Annals of Statistics, 52(1):413–414, 2024. doi: 10.1214/24-AOS2351. [18] László Györfi, Michael Kohler, Adam Krzyżak, and Harro Walk. A Distribution-Free Theory of Nonparametric Regression. Springer Series in Statistics. Springer, 2002. [19] Ruosong Wang, Dean P. Foster, and Sham M. Kakade. What are the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations, 2021. URL https: //arxiv.org/abs/2010.11895. [20] Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch RL can be exponentially harder than online RL. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12287–12297. PMLR, 2021. [21] Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1042–1051. PMLR, 2019. URL https://proceedings.mlr.press/v97/chen19e.html. [22] Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11404–11413. PMLR, 2021. [23] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep Q-learning, 2020. URL https://arxiv.org/abs/1901.00137v3. arXiv:1901.00137v3. [24] Satinder P. Singh and Richard C. Yee. An upper bound on the loss from approximate optimal-value functions. Machine Learning, 16(3):227–233, 1994. [25] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503–556, 2005. URL https://jmlr.org/papers/v6/ernst05a.html. [26] Martin Riedmiller. Neural fitted q iteration: First experiences with a data efficient neural reinforcement learning method. In Proceedings of the European Conference on Machine Learning, pages 317–328, 2005. doi: 10.1007/ 11564096_32. [27] Amir-massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, volume 23, pages 568–576, 2010. [28] Rémi Munos. Performance bounds in 𝑙𝑝 -norm for approximate value iteration. SIAM Journal on Control and Optimization, 46(2):541–561, 2007. doi: 10.1137/040614384. [29] Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game of Tetris. Journal of Machine Learning Research, 16: 1629–1676, 2015. URL https://jmlr.org/papers/v16/scherrer15a.html. [30] John N. Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674–690, 1997. doi: 10.1109/9.580874. [31] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning, pages 30–37. Morgan Kaufmann, 1995. [32] Theodore J. Perkins and Doina Precup. A convergent form of approximate policy iteration. In Advances in Neural Information Processing Systems, volume 15, pages 1627–1634, 2002. [33] Francisco S. Melo, Sean P. Meyn, and M. Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th International Conference on Machine Learning, pages 664–671. ACM, 2008. doi: 10.1145/1390156.1390240. [34] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems, volume 32, 2019. [35] Qi Cai, Zhuoran Yang, Jason D. Lee, and Zhaoran Wang. Neural temporal-difference learning converges to global optima. In Advances in Neural Information Processing Systems, volume 32, 2019. [36] Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function approximation. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10555–10565. PMLR, 2020. URL https://proceedings.mlr.press/ v119/xu20c.html. [37] Shuai Zhang, Hongkang Li, Meng Wang, Miao Liu, Pin-Yu Chen, Songtao Lu, Sijia Liu, Keerthiram Murugesan, and Subhajit Chaudhury. On the convergence and sample complexity analysis of deep q-networks with 𝜖-greedy exploration. In Advances in Neural Information Processing Systems, volume 36, 2023. 28
Deep 𝑉 -Learning: Convergence Framework
[38] Volodymyr Mnih et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015. doi: 10.1038/nature14236. [39] Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 2094–2100, 2016. URL https: //arxiv.org/abs/1509.06461. [40] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89–129, 2008. [41] Shirli Di Castro Shashua, Shie Mannor, and Dotan Di Castro. Analysis of stochastic processes through replay buffers. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5039–5060. PMLR, 2022. [42] Liran Szlak and Ohad Shamir. Convergence results for q-learning with experience replay, 2021. URL https: //arxiv.org/abs/2112.04213. [43] Han-Dong Lim and Donghwan Lee. Finite-time analysis of temporal difference learning with experience replay. Transactions on Machine Learning Research, 2024. URL https://openreview.net/forum?id=A5ulGfDBON. [44] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267–274, 2002.
A
Deferred proofs
Structural and target calculations. Proof of Lemma 2.3. At level ℎ the map projects R onto (ℎ) (ℎ) [−𝑉max , 𝑉max ].
It is therefore 1-Lipschitz and idempotent. If 𝑔 lies in the interval, the scalar projection inequality gives | clipℎ (𝑥) − 𝑔| ≤ |𝑥 − 𝑔| pointwise; integration proves the 𝐿2 metric-projection assertion, up to the usual a.e. identification. Applying the scalar Lipschitz inequality statewise proves the supremum- and 𝐿2 -nonexpansiveness claims. The score bound follows from (10) and (ℎ−1) (ℎ) |𝑄𝑉 (𝑠, ℎ, 𝑎)| ≤ 𝑅max + 𝛾𝑉max = 𝑉max . The same recursion bounds every observed-transition label and, after maximization over actions, places 𝒯 𝑉 in the level-wise band. Nonexpansiveness maps every supremum-norm 𝛿-net of a raw class to a 𝛿-net of its clipped image, proving the covering-number assertion. Finally, because every Bellman target 𝒯 𝑉 lies in the band, the pointwise projection inequality proves the Bellman-approximation assertion. The statewise version of the disintegration (Assumption 3.11). A disintegration is determined only M𝑘,𝑆 -a.e., whereas (𝑟) 𝜀buf,𝑘 and 𝜀act,𝑘 are norms under 𝜌𝑘,𝑆 , so a version must be fixed on all of 𝒮̃︀∘ . Each round’s policy is 𝜀𝑘 -greedy for a score defined at every state, so 𝑑(𝜔𝑘,𝑗 𝜇𝑘,𝑗 ) , 𝑑M𝑘,𝑆 ∑︁ on 𝜋 ¯𝑘on (· | 𝑠˜) := 𝑤𝑘,𝑗 (˜ 𝑠) 𝜋𝑘,𝑗 (· | 𝑠˜), 𝑓𝑘,𝑗 :=
𝑓𝑘,𝑗 (˜ 𝑠) 𝑤𝑘,𝑗 (˜ 𝑠) := ∑︀ , 𝑠) 𝑖 𝑓𝑘,𝑖 (˜
(115)
𝑗
using the bounded density versions of Lemma 2.2 and 𝑤𝑘,𝑗 (˜ 𝑠) := 𝜔𝑘,𝑗 where the denominator vanishes. This is a statewise Markov kernel agreeing with the disintegration M𝑘,𝑆 -a.e.; the same convention fixes 𝛽𝑘rep . Without it, a residual norm under a law not dominated by M𝑘,𝑆 would depend on values on an M𝑘,𝑆 -null set, which the disintegration does not determine; this is why Assumption 3.11 requires 𝜌𝑘,𝑆 ≪ M𝑘,𝑆 for the Arun comparison. Corollary 4.6 is stated for exactly this state-dependent mixture. Lemma A.1 (Detailed target table for Lemma 3.2 [ R ]). Let 𝐴 ∈ {0, . . . , 𝑘} be the record’s age, the number of target copies between the writing of a replayed record and the current block, and 𝛿¯𝑘 (𝐴) := ‖𝑉𝑘 − 𝑉𝑘−𝐴 ‖∞ ; 𝐴 is a function of the record and hence in general state-dependent. Use the current and writing-time predictors 𝑃̂︀𝑘 and 𝑃̂︀write and the 29
Deep 𝑉 -Learning: Convergence Framework
metadata 𝑀𝑘 of Lemma 3.2. The four cells of slot (S6) are WHEN SAMPLE
FROM OBS
SAMPLE STORE
PRED OBS
STORE
PRED
𝑌 𝑟 + 𝛾(1 − 𝑑)𝑉𝑘 (˜ 𝑠′ ) 𝑟 + 𝛾(1 − 𝑑)𝑉𝑘 (𝑃̂︀𝑘 (˜ 𝑠, 𝑎)) 𝑟 + 𝛾(1 − 𝑑)𝑉𝑘−𝐴 (˜ 𝑠′ ) 𝑟 + 𝛾(1 − 𝑑)𝑉𝑘−𝐴 (𝑃̂︀write (˜ 𝑠, 𝑎))
(116)
in each of which the reward 𝑟 and the mask 𝑑 are the observed ones; only the bootstrapping network and evaluation successor change. The ideal response uses the same row with 𝑍 ∘ in place of 𝑍, retaining the writing-time parameters and age as in (23). Define the continuation component of the score error by ⃒ ⃒ ∫︁ ⃒ ⃒ 𝜂𝑘cont := sup sup 𝛾 ⃒⃒𝑉 (𝑃̂︀𝑘 (˜ 𝑠, 𝑎)) − 𝑉 𝑑𝒫(· | 𝑠˜, 𝑎)⃒⃒ . 𝑉 ∈ℱ 𝑠˜,𝑎
Then 𝜂𝑘cont ≤ 𝜂sc,𝑘 , without a factor 2, whenever the point score is the score bounded in (21). Under a different slot (S2) score, retain 𝜂𝑘cont separately. For the two PRED cells, and only those, assume in addition that the terminal event is decided by the state and action, ⃒ [︀ ]︀ (T) P 𝑑 = 1 ⃒ 𝑠˜, 𝑎 ∈ {0, 1}, (117) for 𝜌𝑘,𝑆 (𝑑˜ 𝑠)𝛽𝑘rep (𝑑𝑎 | 𝑠˜)-almost every (˜ 𝑠, 𝑎), which requires the full conditioning state and joint dynamics to determine the terminal event. Condition (T) is therefore an explicit assumption on this joint structure. Then the actual targetconstruction distance obeys ⃦ ideal ⃦ rep ⃦𝐺𝑘 − 𝒯 𝛽𝑘 𝑉𝑘 ⃦ ≤ 1{FROM = PRED}𝜂𝑘cont 2,𝜌𝑘,𝑆 ⃦ ⃦ + 1{WHEN = STORE}𝛾 ⃦E[𝛿¯𝑘 (𝐴) | 𝑆, 𝒥𝑘 ]⃦ (118) 2,𝜌𝑘,𝑆
+ 1{(WHEN, FROM) = (STORE, PRED)}‖𝐶pred,𝑘 ‖2,𝜌𝑘,𝑆 . so (26) holds with 𝜀tgt,𝑘 equal to any deterministic almost-sure majorant of the right-hand side. Without (T), set 𝑝𝑇 (˜ 𝑠, 𝑎) := P[𝑑 = 1 | 𝑠˜, 𝑎] and ∫︁ ⃒ (︀ )︀⃒ 𝐶mask,𝑘 (˜ 𝑠) := 𝛾 𝑝𝑇 (˜ 𝑠, 𝑎)⃒𝑉𝑘 𝑃̂︀𝑘 (˜ 𝑠, 𝑎) ⃒ 𝛽𝑘rep (𝑑𝑎 | 𝑠˜), ⃦∫︁ ⃦ ⃦ ⃦ rep ⃦ ‖𝐶mask,𝑘 ‖2,𝜌𝑘,𝑆 ≤ 𝛾𝑉max ⃦ 𝑝𝑇 (·, 𝑎)𝛽𝑘 (𝑑𝑎 | ·)⃦ . (119) ⃦ 2,𝜌𝑘,𝑆
The right side of (118) then acquires 1{FROM = PRED}‖𝐶mask,𝑘 ‖2,𝜌𝑘,𝑆 , which 𝜂𝑘cont does not cover. Thus the replayaction average is taken before the 𝐿2 (𝜌𝑘,𝑆 ) norm. The conditional expectation in either staleness term may not be replaced by an unconditional one, since the age and writing-time predictor can depend on the replayed state. For the target-network term, conditional Jensen gives the 𝒥𝑘 -measurable majorant 𝛾(E[𝛿¯𝑘 (𝐴)2 | 𝒥𝑘 ])1/2 ; the conditional essential supremum of 𝛾 𝛿¯𝑘 (𝐴) is another. A deterministic envelope must dominate either choice almost surely. Proof of Lemma A.1. When the point score is installed, 𝜂𝑘cont ≤ 𝜂sc,𝑘 without the factor 2 that the triangle inequality ∫︀ ̂︀ 𝑉 − 𝑄𝑉 = (𝑅 ̂︀ − 𝑅) + 𝛾(𝑉 ∘ 𝑃̂︀𝑘 − 𝑉 𝑑𝒫) and ℱ is symmetric under 𝑉 ↦→ −𝑉 by construction, would give: since 𝑄 ∫︀ evaluating at 𝑉 and at −𝑉 and subtracting cancels the reward term, leaving 2𝛾|𝑉 ∘ 𝑃̂︀𝑘 − 𝑉 𝑑𝒫| ≤ 2𝜂sc,𝑘 by (21). Fix a cell of (116) and condition on (𝑆, 𝒥𝑘 ). Under (SAMPLE, OBS) the ideal fresh-redraw label’s conditional mean rep rep under the true kernel is (𝒯 𝛽𝑘 𝑉𝑘 )(˜ 𝑠) by (23) and the terminal convention, so 𝐺ideal = 𝒯 𝛽𝑘 𝑉𝑘 and the left-hand side 𝑘 vanishes. In the ideal redraw, changing FROM to PRED leaves 𝑟∘ and 𝑑∘ untouched. Both objects compared are conditional means, so the comparison is made after conditioning, and the redrawn mask∫︀is random: the PRED label has conditional mean 𝑅(˜ 𝑠, 𝑎)+𝛾(1−𝑝𝑇 (˜ 𝑠, 𝑎))𝑉𝑘 (𝑃̂︀𝑘 (˜ 𝑠, 𝑎)) and the OBS label 𝑅(˜ 𝑠, 𝑎)+𝛾 𝑉𝑘 𝑑𝒫, the terminal convention having absorbed ̂︀ the mask on that side. Adding and subtracting 𝛾𝑉𝑘 (𝑃𝑘 (˜ 𝑠, 𝑎)) bounds their difference by 𝜂𝑘cont +𝛾𝑝𝑇 (˜ 𝑠, 𝑎)|𝑉𝑘 (𝑃̂︀𝑘 (˜ 𝑠, 𝑎))|, whose average under 𝛽𝑘rep (𝑑𝑎 | 𝑠˜) is bounded by 𝜂𝑘cont + 𝐶mask,𝑘 (˜ 𝑠). Taking the state norm gives (119). Under (T) a direct cellwise comparison removes∫︀ this correction: where 𝑝𝑇 (˜ 𝑠, 𝑎) = 0 by inspection, and where it is 1 the fresh successor is 𝑠˜term almost surely, so 𝑉𝑘 𝑑𝒫 = 0 while (1 − 𝑑∘ ) annihilates the predicted continuation. Only the continuation component of the score error is charged, the reward being observed and not modelled. 30
Deep 𝑉 -Learning: Convergence Framework
For STORE/OBS, condition first on (𝑆, a, 𝑀𝑘 , 𝒥𝑘 ) and use the same fresh outcome for the stored and sample-time labels. Their pointwise difference is at most 𝛾 𝛿¯𝑘 (𝐴), since |1 − 𝑑∘ | ≤ 1. For STORE/PRED, there is also a change of predictor: 𝑉𝑘−𝐴 (𝑃̂︀write (𝑆, a)) − 𝑉𝑘 (𝑃̂︀𝑘 (𝑆, a)) = [𝑉𝑘−𝐴 − 𝑉𝑘 ](𝑃̂︀write (𝑆, a)) + 𝑉𝑘 (𝑃̂︀write (𝑆, a)) − 𝑉𝑘 (𝑃̂︀𝑘 (𝑆, a)). Multiplication by 𝛾(1 − 𝑑∘ ), the triangle inequality, and |1 − 𝑑∘ | ≤ 1 bound the conditional mean of the absolute label difference by 𝛾E[𝛿¯𝑘 (𝐴) | 𝑆, 𝒥𝑘 ] + 𝐶pred,𝑘 (𝑆). Here the action and metadata are averaged conditional on (𝑆, 𝒥𝑘 ). Taking the state norm gives the second and third terms of (118). The stated target-network majorants follow from conditional Jensen and the essential supremum bound. Combining with the sample-time comparison proves the result, including the general terminal-mask correction. Why both stored-label corrections are needed. Two finite-state examples isolate the issues. Take 𝐻 = 2, 𝑅max = 1, a level-two state 𝑥, zero reward there, and identical actions; all level-one states terminate at the next step. First, let the true successor of 𝑥 be 𝑣, let the writing-time predictor return 𝑢, and let the current predictor be exact. Set rep 𝑉𝑘−𝐴 = 𝑉𝑘 = 𝑉 with 𝑉 (𝑢) = 1 and 𝑉 (𝑣) = −1. Then a stored prediction label is 𝛾 while (𝒯 𝛽𝑘 𝑉𝑘 )(𝑥) = −𝛾. Both current continuation error and target-network staleness vanish, but 𝐶pred,𝑘 (𝑥) = 2𝛾, exactly the missing distance. Second, take 𝑘 ≥ 1, let the true successor law at 𝑥 be uniform on 𝑧+ and 𝑧− , let 𝑉𝑘 = 0, and set 𝑉𝑘−1 (𝑧+ ) = 1, 𝑉𝑘−1 (𝑧− ) = −1. With fixed 𝒥𝑘 , suppose a selected stored observation record has (𝐴, 𝑠˜′ ) = (1, 𝑧+ ) or (0, 𝑧− ), each with probability 1/2. Its outcome marginal given (𝑆, a, 𝒥𝑘 ) is the true kernel, but 𝐺𝑘 (𝑥) = 𝛾/2. Retaining 𝐴 and independently redrawing the successor gives 𝐺ideal (𝑥) = 0. Thus conditioning without metadata cannot justify a zero 𝑘 kernel residual. For Aiid , the label parameters are fixed before each fresh draw and the switches are SAMPLE/OBS, so both residuals remain zero. Proof of Lemma 3.10. The decomposition follows the standard fitted-value-iteration argument [1, Lemmas 3–4]; specific here are the truncation of Step 3 and the weight sum of Step 4. Step 1 (recursion). Let 𝑧𝑘 := 𝑉 ⋆ − 𝑉𝑘 , so 𝑧𝑘+1 = (𝒯 𝑉 ⋆ − 𝒯 𝑉𝑘 ) − 𝑒𝑘 . Lemma 3.9 at (𝑉, 𝑊 ) = (𝑉 ⋆ , 𝑉𝑘 ) gives a ⋆ (𝑘) (𝑘) (𝑘) substochastic 𝒫∘ := 𝒫∘𝑉 ,𝑉𝑘 with |𝒯 𝑉 ⋆ − 𝒯 𝑉𝑘 | ≤ 𝛾𝒫∘ |𝑧𝑘 |, so |𝑧𝑘+1 | ≤ 𝛾𝒫∘ |𝑧𝑘 | + |𝑒𝑘 | pointwise, and unrolling from 𝐾 to 0, 𝐾−1 ∑︁ (𝐾−1) (0) (𝐾−1) (𝑘+1) |𝑧𝐾 | ≤ 𝛾 𝐾 𝒫∘ · · · 𝒫∘ |𝑧0 | + 𝛾 𝐾−1−𝑘 𝒫∘ · · · 𝒫∘ |𝑒𝑘 |. (120) 𝑘=0 ⋆
Step 2 (loss resolvent). With 𝜋𝐾 greedy for 𝑉𝐾 and 𝜋 ⋆ for 𝑉 ⋆ : from 𝑉 ⋆ = 𝒯 𝜋 𝑉 ⋆ , 𝑉 𝜋𝐾 = 𝒯 𝜋𝐾 𝑉 𝜋𝐾 , the greedy ⋆ inequality 𝒯 𝜋 𝑉𝐾 ≤ 𝒯 𝑉𝐾 = 𝒯 𝜋𝐾 𝑉𝐾 and the splitting 𝑉𝐾 − ∑︀ 𝑉 𝜋𝐾 = (𝑉𝐾 − 𝑉 ⋆ ) + (𝑉 ⋆ − 𝑉 𝜋𝐾 ), (𝐼 − 𝛾𝒫∘𝜋𝐾 )(𝑉 ⋆ − 𝜋𝐾 𝜋⋆ 𝜋𝐾 𝜋𝐾 −1 𝑉 ) ≤ 𝛾(𝒫∘ − 𝒫∘ )𝑧𝐾 . The resolvent (𝐼 − 𝛾𝒫∘ ) = ℓ≥0 𝛾 ℓ (𝒫∘𝜋𝐾 )ℓ is nonnegative; applying it and ±𝑧𝐾 ≤ ∑︀ ⋆ |𝑧𝐾 | yields the standard loss-resolvent bound in substochastic form, 𝑉 ⋆ −𝑉 𝜋𝐾 ≤ ℓ≥0 𝛾 ℓ+1 (𝒫∘𝜋𝐾 )ℓ (𝒫∘𝜋 +𝒫∘𝜋𝐾 )|𝑧𝐾 |. Step 3 (truncation). Substituting (120) gives, for each |𝑒𝑘 |, two families of kernel products of length 𝑚 = ℓ + (𝐾 − 𝑘) and weight 𝛾 𝑚 . By the clock decrement (15) every 𝒫∘𝜋 strictly decreases ℎ, so products of length 𝑚 ≥ 𝐻 vanish (the policies need not coincide), and the weight range is 𝑚 < 𝐻. The families multiplying |𝑧0 | have length at least 𝐾 + 1 and vanish once 𝐾 ≥ 𝐻 − 1. Step 4 (the exact realized occupancies). For 𝑚 = ℓ + 𝐾 − 𝑘 < 𝐻, define the two subprobability measures ⋆
(𝐾−1)
1 𝜈𝐾,𝑘,ℓ := 𝜇∘𝑆 (𝒫∘𝜋𝐾 )ℓ 𝒫∘𝜋 𝒫∘
(𝑘+1)
· · · 𝒫∘
,
(𝐾−1) (𝑘+1) 2 𝜈𝐾,𝑘,ℓ := 𝜇∘𝑆 (𝒫∘𝜋𝐾 )ℓ+1 𝒫∘ · · · 𝒫∘ ,
where the final product is the identity for 𝑘 = 𝐾 − 1. For conjugate 𝑠 ∈ [2, ∞] and 𝑝 = 𝑠/(𝑠 − 1), suppose only these 𝑏 realized measures are absolutely continuous with respect to 𝜌𝑘,𝑆 , and put 𝑑𝑏𝐾,𝑘,ℓ,𝑠 := ‖𝑑𝜈𝐾,𝑘,ℓ /𝑑𝜌𝑘,𝑆 ‖𝑠,𝜌𝑘,𝑆 . Hölder’s inequality applied separately to the two branches gives the exact pathwise coefficient form ∑︁ ∑︁ (︀ )︀ ‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 𝛾 ℓ+𝐾−𝑘 𝑑1𝐾,𝑘,ℓ,𝑠 + 𝑑2𝐾,𝑘,ℓ,𝑠 ‖𝑒𝑘 ‖𝑝,𝜌𝑘,𝑆 . (121) 𝑘<𝐾
ℓ≥0: ℓ+𝐾−𝑘<𝐻
31
Deep 𝑉 -Learning: Convergence Framework
Thus the proof consumes coverage only for the two displayed families. Their coefficients remain multiplied by the residual norms; no independence or product-of-expectations step is valid in general. Step 5 (deterministic envelope, boundary, and count). Every constructed kernel is a measurable policy kernel (Lemma 3.9). Assumption 3.3 gives 𝑑1𝐾,𝑘,ℓ,𝑠 , 𝑑2𝐾,𝑘,ℓ,𝑠 ≤ 𝑑𝑠 (𝑚), which reduces (121) to the residual sum in (39). For the initialization term, start on clock slice ℎ. A branch of total length 𝑚 vanishes for 𝑚 ≥ ℎ and otherwise ends on slice ℎ − 𝑚, where |𝑧0 | ≤ 𝐷0,ℎ−𝑚 almost surely. Summing the two branches against the initial masses 𝑝ℎ bounds (𝑗) their contribution by the deterministic ℬ𝐾 in (37). Level-wise clipping permits the choice 𝐷0,𝑗 = 2𝑉max ; the boundary vanishes for 𝐾 ≥ 𝐻 − 1 regardless of that choice. (𝐻)
Finally, the coefficient of ‖𝑒𝑘 ‖𝑝,𝜌𝑘,𝑆 is 𝑤𝐾,𝑘 . With 𝑚 = ℓ + 𝐾 − 𝑘, a fixed 1 ≤ 𝑚 < 𝐻 admits exactly min{𝐾, 𝑚} ∑︀ ∑︀ (𝐻) (𝐻) indices 𝑘. Fubini–Tonelli therefore gives 𝑘<𝐾 𝑤𝐾,𝑘 = 2 𝑚<𝐻 min{𝐾, 𝑚}𝛾 𝑚 𝑑𝑠 (𝑚) = 2𝜑𝑠,𝐾 . The weights are deterministic, so expectations pass term by term. Proof of Proposition 4.8. MDP and laws. All unspecified rewards are zero. Use 𝑂 = 𝑆, the full clipped tabular class, and exact fresh population (SAMPLE, OBS) updates at every nonterminal state. Nonterminal states are 𝑠 at ℎ = 3, 𝑦1 , 𝑦2 at ℎ = 2, and 𝑧1 , 𝑧2 , 𝑤 at ℎ = 1. Transitions are deterministic and rewards are nonzero only at ℎ = 1: 𝑠 : 𝑢1 → 𝑦1 , 𝑠 : 𝑢2 → 𝑦2 ; 𝑦1 : 𝑏1 → 𝑧1 , 𝑦1 : 𝑏2 → 𝑧2 ; and both actions at 𝑦2 lead to 𝑤. At 𝑧1 , 𝑧2 , 𝑤, every action enters the zero-reward absorbing terminal state after receiving, respectively, 𝑅(𝑧1 ) = 1, 𝑅(𝑧2 ) = 1 − 𝑢, and 𝑅(𝑤) = 𝑣, with 𝑢, 𝑣 ∈ (0, 1) fixed below. Take 𝜇𝑆 = 𝛿𝑠 and let 𝜌𝑆 be uniform on these six nonterminal states; thus every nonterminal state has replay probability 1/6 and 𝜌𝑆 has full support. Initialize the population recursion at 𝑉0 = 0. Frozen values and the true gap. At ℎ = 1 the target carries no bootstrap, so exact population regression gives 𝑉𝑘 (𝑧1 ) = 1, 𝑉𝑘 (𝑧2 ) = 1 − 𝑢, 𝑉𝑘 (𝑤) = 𝑣 for 𝑘 ≥ 1; hence 𝑄𝑉𝑘 (𝑦1 , 𝑏1 ) = 𝛾 and 𝑄𝑉𝑘 (𝑦1 , 𝑏2 ) = 𝛾(1 − 𝑢), so 𝑏1 is (𝑘) target-greedy and ∆𝑄 (𝑦1 ) = 𝛾𝑢. ̂︀ = 𝑅 except 𝑅(𝑦 ̂︀ 1 , 𝑏1 ) = −𝜂, 𝑅(𝑦 ̂︀ 1 , 𝑏2 ) = +𝜂. Then A pure reward-model error of size 𝜂. Let 𝑃̂︀ be exact and 𝑅 ̂︀ ̂︀ ̂︀ ‖𝑄𝑉𝑘 − 𝑄𝑉𝑘 ‖∞ = ‖𝑅 − 𝑅‖∞ = 𝜂 for every 𝑘. Because the error is placed in 𝑅 alone, it does not interact with the bootstrap. The implemented branch prefers 𝑏2 at 𝑦1 exactly when 𝛾(1 − 𝑢) + 𝜂 > 𝛾 − 𝜂, i.e. 𝑢 < 2𝜂/𝛾. Take 0 < 𝜗 < min{𝜂/𝛾, 𝜖/(2𝛾 2 )} and set 𝑢 := 2𝜂/𝛾 − 𝜗, which lies in (0, 1) because 𝜂 < 𝛾/2. The acting network is the frozen target, so 𝛿𝑉,𝑘 = 0 and Λ𝑘 = 𝜂sc,𝑘 = 𝜂: the harmful behavior is produced by the named score error, not stipulated. Limit and loss. For every 𝑘 ≥ 1, the recursion gives 𝑉𝑘+1 (𝑦1 ) = 𝛾(1 − 𝑢) and 𝑉𝑘+1 (𝑦2 ) = 𝛾𝑣; the clock makes all relevant values exact after 𝐻 = 3 sweeps. Choose 𝑣 ∈ (1 − 𝑢, min{1, 1 − 𝑢 + 𝜖/(2𝛾 2 )}); then 𝑄𝑉𝐾 (𝑠, 𝑢1 ) = 𝛾 2 (1 − 𝑢) < 𝛾 2 𝑣 = 𝑄𝑉𝐾 (𝑠, 𝑢2 ), so 𝜋𝐾 (𝑠) = 𝑢2 strictly. Meanwhile 𝑉 ⋆ (𝑦1 ) = 𝛾 through 𝑏1 , 𝑉 ⋆ (𝑦2 ) = 𝛾𝑣 and 𝑉 ⋆ (𝑠) = 𝛾 2 max(1, 𝑣) = 𝛾 2 since 𝑣 < 1, while 𝑉 𝜋𝐾 (𝑠) = 𝛾𝑉 ⋆ (𝑦2 ) = 𝛾 2 𝑣; hence ‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 = 𝛾 2 (1 − 𝑣) > 𝛾 2 𝑢 − 𝜖/2 = 2𝛾𝜂 − 𝛾 2 𝜗 − 𝜖/2 > 2𝛾𝜂 − 𝜖, which is (78). Other residuals. At each block the same current policy collects the fresh data and is its replay law, so 𝜀buf,𝑘 = 0; the population update is exact in the full tabular class, so 𝜀fit,𝑘 = 0; fresh true-kernel outcomes with the default rep (SAMPLE, OBS) target give 𝐺𝑘 = 𝐺ideal = 𝒯 𝛽𝑘 𝑉𝑘 , hence 𝜀ker,𝑘 = 𝜀tgt,𝑘 = 0; collection is greedy, so 𝜀𝑘 = 0. Full 𝑘 support of 𝜌𝑆 gives finite 𝑐2 (𝑚) on this finite MDP. Statistical and consequence calculations. Proof of Lemma 5.4. Write 𝑃 and 𝑃𝑛 for the population and the empirical measure and, for 𝑉 ∈ 𝒞, let ℓ𝑉 := (𝑉 − 𝑌 )2 − (𝑔 − 𝑌 )2 be the excess loss. Expanding and using E[𝑌 | 𝑆] = 𝑔(𝑆), the cross term vanishes, so 𝑃 ℓ𝑉 = ‖𝑉 − 𝑔‖22,𝜌𝑘,𝑆 =: ℰ(𝑉 ) ≥ 0. Step 1 (three elementary bounds). Since ℓ𝑉 = (𝑉 − 𝑔)(𝑉 + 𝑔 − 2𝑌 ) with |𝑉 − 𝑔| ≤ 2𝐵 and |𝑉 + 𝑔 − 2𝑌 | ≤ 4𝐵, and since ℓ𝑉 is a difference of two quantities lying in [0, 4𝐵 2 ], |ℓ𝑉 | ≤ 4𝐵 2 ,
E[ℓ2𝑉 ] ≤ 16𝐵 2 ℰ(𝑉 ),
|ℓ𝑉 − ℓ𝑉 ′ | ≤ 4𝐵‖𝑉 − 𝑉 ′ ‖∞ ,
(122)
the last because ℓ𝑉 − ℓ𝑉 ′ = (𝑉 − 𝑉 ′ )(𝑉 + 𝑉 ′ − 2𝑌 ). Step 2 (reduction to a finite net). Let {𝑉1 , . . . , 𝑉𝑁 }, 𝑁 = 𝑁𝛿 (𝒞), be a 𝛿-net of 𝒞 in supremum norm and, for 𝑉 ∈ 𝒞, let 𝑗(𝑉 ) index a net point with ‖𝑉 − 𝑉𝑗(𝑉 ) ‖∞ ≤ 𝛿. By the third bound in (122), the empirical-process difference is at most 32
Deep 𝑉 -Learning: Convergence Framework
√︀ √︀ 8𝐵𝛿. The reverse triangle inequality for ℰ(𝑉 ) = ‖𝑉 − 𝑔‖2,𝜌𝑘,𝑆 gives, after separating the cases ℰ(𝑉𝑗(𝑉 ) ) ⋛ 𝛿, −ℰ(𝑉 )/2 ≤ −ℰ(𝑉𝑗(𝑉 ) )/2 + 2𝐵𝛿. Hence, pointwise, [︁ ]︁ (123) (𝑃 − 𝑃𝑛 )ℓ𝑉 − 12 ℰ(𝑉 ) ≤ max (𝑃 − 𝑃𝑛 )ℓ𝑉𝑗 − 12 ℰ(𝑉𝑗 ) + 10𝐵𝛿. 𝑗≤𝑁
The right-hand side is a maximum of finitely many measurable functions. Step 3 (Bernstein with a shifted threshold). The standard localization device for bounded squared-loss regression [18, Ch. 11]. Fix 𝑗 and put ℰ𝑗 := ℰ(𝑉𝑗 ). By (122), each centered summand is bounded above by 8𝐵 2 and has variance at most 16𝐵 2 ℰ𝑗 . Bernstein’s inequality at threshold 𝑡 + ℰ𝑗 /2, followed by a union bound, yields P(max𝑗 [(𝑃 − 𝑃𝑛 )ℓ𝑉𝑗 − ℰ𝑗 /2] > 𝑡) ≤ 𝑁 exp{−𝑛𝑡/(70𝐵 2 )}. Integrating gives [︁ )︀]︁ (︀ )︀ 70𝐵 2 (︀ ≤ E max (𝑃 − 𝑃𝑛 )ℓ𝑉𝑗 − 12 ℰ𝑗 1 + log 𝑁 . 𝑗≤𝑁 𝑛 + Step 4 (assembly). Enumerate the fixed countable class 𝒞0 and let 𝑉 ⋆ be the first element satisfying ‖𝑉 ⋆ − 𝑔‖2,𝜌𝑘,𝑆 ≤ dist2,𝜌𝑘,𝑆 (𝒞, 𝑔) + 𝜏 for a slack 𝜏 > 0. Supremum-norm density ensures existence and the first-index rule is measurable. The 𝐿2 choice is essential because ℰ(𝑉 ) = ‖𝑉 − 𝑔‖22,𝜌𝑘,𝑆 . Approximate empirical optimality gives 𝑃𝑛 ℓ𝑉̂︀𝑘+1 ≤ 𝑃𝑛 ℓ𝑉 ⋆ + 𝜁𝑛 , so [︁ ]︁ ⋆ 1 1 ̂︀ ̂︀ ̂︀𝑘+1 − 2 ℰ(𝑉𝑘+1 ) + (𝑃𝑛 − 𝑃 )ℓ𝑉 ⋆ + ℰ(𝑉 ) + 𝜁𝑛 . 2 ℰ(𝑉𝑘+1 ) ≤ (𝑃 − 𝑃𝑛 )ℓ𝑉 Taking expectations, applying (123) and Step 3, and using E(𝑃𝑛 − 𝑃 )ℓ𝑉 ⋆ = 0 (conditionally on 𝒦 in the conditional form), yields 2 (︀ )︀ [︀ ]︀ 1 ̂︀𝑘+1 ) ≤ 70𝐵 1 + log 𝑁𝛿 (𝒞) + 10𝐵𝛿 + dist2,𝜌 (𝒞, 𝑔) + 𝜏 2 + 𝜁𝑛 . Eℰ( 𝑉 𝑘,𝑆 2 𝑛 Multiplying by 2 and letting 𝜏 ↓ 0 gives (88) for 𝐶1 ≥ 140. Only boundedness and the conditional mean of 𝑌 were used, so bounded label noise is covered. For (89), use a fresh symbol 𝑢 ∈ (0, 1) for the confidence level during this proof. Since 𝑔 ∈ 𝒞 and the supplied ERM is exact over 𝒞, comparison with 𝑔 gives 𝑃𝑛 ℓ𝑉̂︀𝑘+1 ≤ 𝑃𝑛 ℓ𝑔 = 0. Hence 1 1 ̂︀ ̂︀ ̂︀𝑘+1 − 2 ℰ(𝑉𝑘+1 ). 2 ℰ(𝑉𝑘+1 ) ≤ (𝑃 − 𝑃𝑛 )ℓ𝑉
By (123) and the tail bound of Step 3, with conditional probability at least 1 − 𝑢 the right-hand side is at most 70𝐵 2 {log 𝑁𝛿 (𝒞) + log(1/𝑢)}/𝑛 + 10𝐵𝛿. Multiplication by 2, enlargement to 𝐶1 ≥ 140, and renaming 𝑢 as 𝜏 prove (89). This argument does not divide by any state probability. Proof of Proposition 5.5. Throughout 𝑔 := 𝐺𝑘 , so ‖𝑔‖∞ ≤ 𝑉max by (10), |𝑌𝑖 | ≤ 𝑉max and E[𝑌𝑖 | 𝑆𝑖 ] = 𝑔(𝑆𝑖 ); Lemma 5.4 applies with 𝐵 = 𝑉max and 𝒞 = ℱ𝑛𝑉 , being stated for an arbitrary bounded measurable 𝑔 and not requiring 𝑔 ∈ 𝒢0clk . Step 1 (approximation). The routed approximation bound (85) already applies to the externally clipped class: ⋆
𝑉 clk (𝛼 −1)/2 distsup . ∞ (ℱ𝑛 , 𝒢0 ) ≤ 𝐶appx 𝑚𝑛
Its proof uses Lemma 2.3 head by head, exploiting that every target in 𝒢0clk lies in the level-wise band. Step 2 (covering). If 𝑉max = 0 the claim is trivial. Otherwise set 𝛿𝑛 = (1 ∧ 𝑉max )/𝑛. The product entropy bound (86) gives {︂ (︂ 2 )︂}︂ 2(𝐿𝑚𝑛 + 1)𝐷𝑚 𝑛 log 𝑁𝛿𝑛 (ℱ𝑛𝑉 ) ≤ 𝐻 log 𝑚𝑛 + (𝑠𝑚𝑛 + 1) log 𝛿𝑛 (124) ⋆
⋆
≲ 𝐻𝑚𝑛𝛼 (log 𝑛)1+2𝜉 . Step 3 (combination, comparator in 𝐿2 (𝜌𝑘,𝑆 )). Since 𝒯 𝑉𝑘 ∈ 𝒢0clk and ‖ · ‖2,𝜌𝑘,𝑆 ≤ ‖ · ‖∞ , the triangle inequality in 𝐿2 (𝜌𝑘,𝑆 ) gives ⃦ ⃦ ⋆ (2) 𝑉 clk −1)/2 ⃦ ⃦ dist2,𝜌𝑘,𝑆 (ℱ𝑛𝑉 , 𝑔) ≤ distsup ≤ 𝐶appx 𝑚(𝛼 + 𝐷𝑘 . (125) ∞ (ℱ𝑛 , 𝒢0 ) + 𝒯 𝑉𝑘 − 𝐺𝑘 2,𝜌 𝑛 𝑘,𝑆
33
Deep 𝑉 -Learning: Convergence Framework √ Step 4 (take the square root before splitting). Apply Jensen, then subadditivity of ·, to the four summands of (88) at the radius 𝛿𝑛 = (1 ∧ 𝑉max )/𝑛: ⃒ [︀ ]︀ √ E ‖𝑉̂︀𝑘+1 − 𝑔‖2,𝜌𝑘,𝑆 ⃒ ℋ𝑘 ≤ 2 dist2,𝜌𝑘,𝑆 (ℱ𝑛𝑉 , 𝑔) (︁ 2 (︀ )︀)︁1/2 𝐶1 𝑉max + 1 + log 𝑁𝛿𝑛 (ℱ𝑛𝑉 ) 𝑛 (︀ )︀1/2 √︀ + 𝐶1 𝑉max 𝛿𝑛 + 2𝜁𝑛 . By (125) the first summand is at most
√
(𝛼⋆ −1)/2
2𝐶appx 𝑚𝑛 (︂
𝐻𝑚𝛼 𝑛 𝑛
⋆
)︂1/2
+
√
(2)
2𝐷𝑘 . Since 𝑛 ≥ 𝐻𝑚𝑛 , equation (124) yields ⋆
−1)/2 ≤ 𝑚(𝛼 . 𝑛
The remaining 𝑛−1/2 terms are no larger than a constant times this rate. Collecting constants gives (91). For fixed 𝐻, 𝑚𝑛 ≍ 𝑛/𝐻, so this has the same exponent in 𝑛 as the one-head rate; the displayed 𝑚𝑛 records the router’s 𝐻-head complexity cost. Step 5 (greedy collection). If a𝑖 = 𝑎⋆ (𝑆𝑖 ; 𝑉𝑘 ) then 𝐺𝑘 = 𝒯 𝑉𝑘 by Lemma 2.4(iii), so (2) 𝐷𝑘 = 0 and (91) reduces to (92). Noisy targets are covered because Lemma 5.4 requires only E[𝑌𝑖 | 𝑆𝑖 ] = 𝑔(𝑆𝑖 ) with |𝑌𝑖 | ≤ 𝑉max . Proof of Corollary 5.7. Lemma 2.3 gives exact closure. Empirical means at visited states (zero at unvisited states) give (ℎ−1) (ℎ) a measurable exact ERM in the level-wise band because every label at level ℎ is bounded by 𝑅max + 𝛾𝑉max = 𝑉max . 2 Condition on ℋ𝑘 . Given 𝑁𝑘,𝑠 = 𝑟 > 0, the coordinatewise sample mean is unbiased with squared error 𝜎𝑘,𝑠 /𝑟; when 2 𝑟 = 0, its squared error is 𝑔𝑘,𝑠 . Multiplying by 𝑝𝑘,𝑠 and summing proves the exact identity (97); coordinates with 𝑝𝑘,𝑠 = 0 vanish. For 𝑟 ≥ 1, 1/𝑟 ≤ 2/(𝑟 + 1). If 𝑀 ∼ Bin(𝑛, 𝑝), then ∫︁ 1 1 − (1 − 𝑝)𝑛+1 1 = (1 − 𝑝 + 𝑝𝑥)𝑛 𝑑𝑥 = , E 𝑀 +1 (𝑛 + 1)𝑝 0 so 𝑝E[1{𝑀 > 0}/𝑀 ] ≤ 2/(𝑛 + 1). Also 𝑝 Pr(𝑀 = 0) = 𝑝(1 − 𝑝)𝑛 ≤ (𝑛/(𝑛 + 1))𝑛 /(𝑛 + 1), by maximizing over 2 2 2 𝑝. Using 𝜎𝑘,𝑠 , 𝑔𝑘,𝑠 ≤ 𝑉max , summing over the 𝑁 states and applying Jensen proves the first bound in (98). Finally 𝑛 (1 + 1/𝑛) ≥ 2, and for 𝑛 ≥ 2 its first three binomial terms are at least 9/4, giving the constants 5/2 and 22/9. These bounds are deterministic after conditioning, so they also hold unconditionally. The additional design choices respectively remove kernel, target, replay, aliasing, and drift links; full support makes every finite-state density coefficient finite. Since 𝐺𝑘 ∈ ℱ tab , no policy-image approximation term is needed, so the composition chain charges the action and exploration links only once. Substitution of (98) and Theorem 4.5 at 𝑟 = 𝑝 into Theorem 3.18, with 𝐾 ≥ 𝐻 − 1, gives (100). For fixed 𝐾, name the 𝑘th confidence event {︁ }︁ ℰ𝑘,𝐾 (𝛿) := ‖𝑉𝑘+1 − 𝐺𝑘 ‖2,𝜌𝑘,𝑆 ≤ stattab,hp 𝑘,𝐾 (𝛿) . Apply (89) conditionally on ℋ𝑘 with confidence 1 − 𝛿/(𝐻 − 1) and covering radius 𝑉max /𝑛𝑘 . It gives P(ℰ𝑘,𝐾 (𝛿)𝑐 | ℋ𝑘 ) ≤ 𝛿/(𝐻 − 1) directly in population 𝐿2 , including the zero values assigned to unvisited states, so no minimumstate-mass factor occurs. The tower property and a union bound over the at most 𝐻 − 1 relevant blocks make all these events simultaneous with probability at least 1 − 𝛿, despite adaptive histories. On their intersection, the pathwise triangle chain of Lemma 3.13 and Lemma 3.10 gives (102); no cross-block independence is used. Proof of Theorem 6.3. Substitution of Proposition 5.6 into Proposition 5.5 gives √ (︀ )︀ (2) ¯ exp , 𝜀fit,𝑘 ≤ stat𝑘 + 2 𝜀buf,𝑘 + 𝜀 + 𝜀𝑘 𝐷 act,𝑘 (𝑝)
𝑘
(2)
the omitted kernel and target links being zero. Since 𝑝 = 2 here, 𝜀act,𝑘 = 𝜀act,𝑘 ; adding the remaining terms of 𝑒Bell 𝑘,2 ∑︀ (𝐻) (𝐻) (𝐻) proves (109). Equation (110) follows from (49), since 𝑤𝐾,𝑘 = 0 for 𝑘 ≤ 𝐾 − 𝐻 and 𝑘 𝑤𝐾,𝑘 = 2𝜑2,𝐾 . 34
Deep 𝑉 -Learning: Convergence Framework
B
Further refinements
Proposition B.1 (One-sided propagation). Under Theorem 3.18, suppose additionally that, almost surely, 𝑉0 ≤ 𝑉 ⋆ ,
pointwise on 𝒮̃︀∘ , for every 𝑘 < 𝐾.
𝑒𝑘 := 𝑉𝑘+1 − 𝒯 𝑉𝑘 ≤ 0
(126)
⋆
Then 𝑉𝑘 ≤ 𝑉 for every 𝑘 ≤ 𝐾, and 𝐾−1
⋆
E‖𝑉 − 𝑉
𝜋𝐾
1 ∑︁ (𝐻) Bell ℬ𝐾 ℬ𝐾 (𝐻) + 𝑤𝐾,𝑘 𝑒𝑘,𝑝 ≤ + 𝜑𝑠,𝐾 𝑒Bell ‖1,𝜇𝑆 ≤ 𝐾,𝐻,𝑝 . 2 2 2
(127)
𝑘=0
The sign premise is pointwise; an 𝐿𝑝 or replay-almost-everywhere sign condition is insufficient. ⋆
Proof. For 𝑧𝑘 := 𝑉 ⋆ − 𝑉𝑘 , monotonicity and (126) give 𝑧𝑘 ≥ 0 inductively and 𝑧𝑘+1 ≤ 𝛾𝒫∘𝜋 𝑧𝑘 + |𝑒𝑘 |, so only the 𝜋 ⋆ ⋆ ⋆ branch propagates. At the loss-resolvent step, 𝛾(𝒫∘𝜋 − 𝒫∘𝜋𝐾 )𝑧𝐾 ≤ 𝛾𝒫∘𝜋 𝑧𝐾 . Thus the pathwise proof of Lemma 3.10 has half the initialization boundary and half every residual coefficient; the conditional envelopes of Theorem 3.18 give (127). Corollary B.2 (𝐿2 final-score transfer). In the setting of Theorem 6.1, define ̂︀ 𝑉 (˜ 𝐸𝐾 (˜ 𝑠) := max |𝑄 𝑠, 𝑎) − 𝑄𝑉𝐾 (˜ 𝑠, 𝑎)|, 𝐾 𝑎∈𝒜
𝜂𝐾,2 := ‖𝐸𝐾 ‖2,𝜌𝐾,𝑆 .
Assume the final-law density bound (106) at 𝑠 = 2, and let the deterministic 𝜂¯𝐾,2 satisfy 𝜂𝐾,2 ≤ 𝜂¯𝐾,2 almost surely. Then 𝐾−1 𝐻−1 ∑︁ (𝐻) ∑︁ E‖𝑉 ⋆ − 𝑉 𝜋̂︀𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + 𝑤𝐾,𝑘 𝑒Bell + 2¯ 𝜂 𝛾 ℓ 𝑑fin (128) 𝐾,2 𝑘,𝑝 2 (ℓ). 𝑘=0
ℓ=0
If 𝜂𝐾,2 is integrable, the last term may instead retain 2E[𝜂𝐾,2 ] times the same deterministic sum. 𝜋 ̂︀𝐾 Proof. after integration is ∫︀ comparison gives 0 ≤ 𝒯 𝑉𝐾 − 𝒯 𝑉𝐾 ≤ 2𝐸𝐾 , whose resolvent contribution ∑︀ Score ∑︀ 2 ℓ<𝐻 𝛾 ℓ 𝐸𝐾 𝑑{𝜇∘𝑆 (𝒫∘𝜋̂︀𝐾 )ℓ }. Cauchy–Schwarz and (106) bound it pathwise by 2𝜂𝐾,2 ℓ<𝐻 𝛾 ℓ 𝑑fin 2 (ℓ). Use either its deterministic majorant or its expectation to conclude.
OA.1: History-space moment coverage For the two realized occupancy branches in the proof of Lemma 3.10, define ∑︁ (︀ )︀ 𝐴𝐾,𝑘 := 𝛾 ℓ+𝐾−𝑘 𝑑1𝐾,𝑘,ℓ,𝑠 + 𝑑2𝐾,𝑘,ℓ,𝑠 ,
𝑅𝑘 := ‖𝑒𝑘 ‖𝑝,𝜌𝑘,𝑆 .
(129)
ℓ≥0:ℓ+𝐾−𝑘<𝐻
The exact pathwise proof gives ‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 + exponents 𝑢, 𝑣 ∈ [1, ∞],
∑︀
E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 ≤ ℬ𝐾 +
∑︁
𝑘<𝐾 𝐴𝐾,𝑘 𝑅𝑘 . Consequently, for conjugate history-space
‖𝐴𝐾,𝑘 ‖𝐿𝑢 (Ω) ‖𝑅𝑘 ‖𝐿𝑣 (Ω) .
(130)
𝑘<𝐾
This is Hölder’s inequality on the history probability space. Because 𝐴𝐾,𝑘 generally depends on future iterates through 𝜋𝐾 and the comparison kernels, factorizing E[𝐴𝐾,𝑘 𝑅𝑘 ] is invalid; the deterministic worst-policy theorem is the 𝑢 = ∞ case. Realized coverage is strictly weaker: in an 𝐻 = 2 deterministic MDP, let both constructed branches select a covered bottom state 𝑥, set the design law to 𝛿𝑥 , and add an unused action leading to 𝑦. All realized measures are covered, whereas the unused policy produces 𝛿𝑦 ̸≪ 𝛿𝑥 ; hence the all-policy supremum assumption fails. OA.2: Geometric verification of the margin Proposition B.3 (Tube and transverse-growth criterion for one gap law). Let Σ be a measurable switching set. Suppose, for constants 𝑐, 𝑟, 𝑇, 𝜅, 𝑢0 > 0, ∆𝑄 (𝑥) ≥ min{𝑐 dist(𝑥, Σ)𝑟 , 𝑢0 },
𝜌{dist(𝑥, Σ) ≤ 𝜖} ≤ 𝑇 𝜖𝜅
whenever 0 < 𝜖 ≤ (𝑢0 /𝑐)1/𝑟 . Then the global action-gap margin holds with 𝛼 = 𝜅/𝑟,
−𝜅/𝑟
𝐶marg = max{𝑇 𝑐−𝜅/𝑟 , 𝑢0 35
}.
(131)
Deep 𝑉 -Learning: Convergence Framework
Proof. For 0 < 𝑢 < 𝑢0 , the event {∆𝑄 ≤ 𝑢} lies in the tube of radius (𝑢/𝑐)1/𝑟 and has probability at most 𝑇 𝑐−𝜅/𝑟 𝑢𝜅/𝑟 . −𝜅/𝑟 𝜅/𝑟 For 𝑢 ≥ 𝑢0 , use 1 ≤ 𝑢0 𝑢 . The tube condition also makes the zero-gap switching set null. For Definition 4.1, require this criterion almost surely for each (𝑄𝑉𝑘 , 𝜌𝑘,𝑆 ); alternatively verify it uniformly for (𝑄𝑉 ⋆ , 𝜌𝑘,𝑆 ) and apply Proposition 4.3. OA.3: Matched-budget allocation and horizon calculations Proof of Theorem 3.20. Substitute (56) into the first inequalities of Theorems 3.18 and 3.19. Inactive∑︀coordinates have sh lev zero propagation weight, while the nonstatistical terms give 𝐹𝐾 and 𝐹𝐾 . It remains to minimize 𝑖 𝑐𝑖 𝑛−𝜈 under a 𝑖 common terminal-window budget. For positive 𝑐𝑖 , the objective is strictly convex on the positive orthant. The Lagrange equations −𝜈𝑐𝑖 𝑛−𝜈−1 +𝜆=0 𝑖 1/(1+𝜈)
give 𝑛𝑖 ∝ 𝑐𝑖
. Normalizing by the budget and substituting back proves (59), hence (60)–(61).
With lower bounds, strict convexity still gives a unique minimizer. The KKT conditions say that an interior coordinate satisfies 𝑛𝑖 = (𝜈𝑐𝑖 /𝜆)1/(1+𝜈) , whereas a coordinate whose unconstrained value is at most 𝐿𝑖 is fixed at 𝐿𝑖 . This is ∑︀ exactly (63). For N > 𝑖 𝐿𝑖 , the sum ∑︀ of its right-hand side is continuous and strictly decreasing in 𝜆 over the range relevant to the budget, from infinity to 𝑖 𝐿𝑖 ; hence the required 𝜆 is unique. Substitution defines (62) and proves the stated constrained bounds. The unconstrained closed form applies precisely when none of its coordinates violates a lower bound. 𝐿 For integer ∑︀ 𝐿𝐿𝑖 ≥ 1 and integer N, each ⌊𝑛𝑖 ⌋ ≥ 𝐿𝑖 , and the number of undistributed labels is the nonnegative integer N − 𝑖 ⌊𝑛𝑖 ⌋. Allocating each one according to (64) preserves feasibility and uses the entire budget. Moreover, 𝐿 𝐿 ⌊𝑛𝐿 𝑖 ⌋ ≥ 𝑛𝑖 /2 because 𝑛𝑖 ≥ 1, while adding labels can only decrease the objective. Therefore the final integer allocation obeys ∑︁ ∑︁ −𝜈 𝑐𝑖 𝑛−𝜈 ≤ 2𝜈 𝑐𝑖 (𝑛𝐿 = 2𝜈 Ψ𝜈 (𝑐, 𝐿, N). 𝑖 ) 𝑖 𝑖
𝑖
Finally, setting 𝑗 = 𝐾−𝑘 gives |𝒦𝐾 | = 𝐽 and |ℐ𝐾 | =
∑︀𝐽
𝑗=1 (𝐻 −𝑗) = 𝐽𝐻 −𝐽(𝐽 +1)/2 for 𝐽 = min{𝐾, 𝐻 −1}.
Proof of Corollary 3.21. Put 𝑞 := 1/(1+𝜈) and index the active shared-reset √ blocks by 𝑗 = 𝐾𝐻 −𝑘 ∈ {1, . . . , 𝐻 −1}. On the one-state-per-level chain, the uniform clock law has 𝑑2,𝐻 (𝑚) = 𝐻, and therefore ∑︁ √ 𝐻−1 unif 𝑚 𝑤𝐻,𝑗 =2 𝐻 𝛾𝐻 .
(132)
𝑚=𝑗 𝑚 unif In the near-unit regime, 𝛾𝐻 is bounded above and below by positive constants uniformly for 𝑚 < 𝐻. Thus 𝑤𝐻,𝑗 = 3/2 3/2 Θ(𝐻 ) for 𝑗 ≤ 𝐻/2 and is 𝑂(𝐻 ) everywhere. Consequently ⎧ ⎫1/𝑞 ⎬ ⎨𝐻−1 ∑︁ (︀ )︀ unif 𝑞 𝜈+5/2 (𝑏sh = Θ 𝑏sh . 𝐻 𝑤𝐻,𝑗 ) 𝐻𝐻 ⎩ ⎭ 𝑗=1
For the coefficient-optimal shared law at 𝑠 = 2 and 𝐾𝐻 ≥ 𝐻 − 1, write 𝑆𝐻 :=
𝐻−1 ∑︁
𝑚 2/3 (𝑚𝛾𝐻 ) ,
𝑟𝐻−𝑚 =
𝑚=1
𝑚 2/3 (𝑚𝛾𝐻 ) . 𝑆𝐻
1/2 𝑚 −1/3 Then 𝑑2,𝐻 (𝑚) = 𝑆𝐻 (𝑚𝛾𝐻 ) and 1/2
opt 𝑤𝐻,𝑗 = 2𝑆𝐻
𝐻−1 ∑︁
2𝑚/3
𝑚−1/3 𝛾𝐻
.
(133)
𝑚=𝑗
Near unit, 𝑆𝐻 = Θ(𝐻 5/3 ); the last sum is Θ(𝐻 2/3 ) for 𝑗 ≤ 𝐻/2 and 𝑂(𝐻 2/3 ) everywhere. Hence the same sh 𝜈+5/2 calculation gives Csh,opt ). 𝜈,𝐾𝐻 = Θ(𝑏𝐻 𝐻 36
Deep 𝑉 -Learning: Convergence Framework
𝑚 For direct reset, a fixed depth 𝑚 occurs in exactly 𝑚 active pairs and 𝐴lev 𝑘,𝐻−𝑚 = 2𝛾𝐻 . Therefore, in the near-unit regime, (︃𝐻−1 )︃1/𝑞 ∑︁ (︀ )︀ lev lev 2𝜈+2 C𝜈,𝐾𝐻 ≍ 𝑏𝐻 𝑚 = Θ 𝑏lev , 𝐻 𝐻 𝑚=1
proving (65).
√ √ Under fixed discount, (132) is Θ( 𝐻 𝛾 𝑗 ), so its 𝑞th-power sum gives Θ(𝑏sh 𝐻 𝐻). In (133), 𝑆𝐻 is bounded above and weights decay geometrically; their 𝑞th-power sum is finite and bounded away from zero. Likewise ∑︀ below and𝑚the 𝑏lev )𝑞 is finite and positive. This proves (66). Finally, the tabular fit envelope (98) has statistical constant 𝐻 𝑚≥1 𝑚(2𝛾 √ Θ(𝑉max 𝐻) for a shared 𝐻-state clock law and Θ(𝑉max ) on each singleton slice. Substitution at 𝜈 = 1/2 proves (67). OA.4: Tie-sensitive equality at the score floor In Proposition 4.8, take 𝑢 = 2𝜂/𝛾 and 𝑣 = 1 − 𝑢, 0 < 𝜂 < 𝛾/2. If the harmful actions win the resulting ties at 𝑦1 and the root, exact population updates give 𝑉 ⋆ (𝑠) − 𝑉 𝜋𝐾 (𝑠) = 𝛾 2 (1 − 𝑣) = 𝛾 2 𝑢 = 2𝛾𝜂.
(134)
All other residuals vanish; without coordinated tie-breaking, use the main 2𝛾𝜂 − 𝜖 bound. OA.5: Polynomial-schedule consistency rate Let 𝑎 = (1 − 𝛼⋆ )/2 and 𝑏 = (1 + 2𝜉 ⋆ )/2. In the setting of Corollary 6.4, suppose 𝑛𝑘 ≍ 𝑘 𝑟 , 𝜁𝑛𝑘 = 𝑂(𝑛−𝑡 𝑘 ), and 𝜀𝑘 = 𝑂(𝑘 −𝑠0 ), with 𝑟, 𝑡, 𝑠0 > 0. For fixed 𝐻 and 𝐾 ≥ 2𝐻, (︁ [︁ ]︁)︁ (𝐻) E‖𝑉 ⋆ − 𝑉 𝜋𝐾 ‖1,𝜇𝑆 = 𝑂 𝜑2 (log 𝐾)𝑏 𝐾 −𝑟𝑎 + 𝐾 −𝑟𝑡/2 + 𝐾 −𝑠0 . (135) For 𝐾 ≥ 2𝐻, the boundary vanishes and active 𝑘 ≍ 𝐾; 𝑚𝑛𝑘 ≍ 𝑛𝑘 at fixed 𝐻, so (111) applies. The statistical term governs if 𝑡 ≥ 2𝑎 and 𝑠0 ≥ 𝑟𝑎. OA.6: Monte Carlo score bound Assume arbitrary-query access, and let 𝐴 := |𝒜|. For each action, let 𝑍𝑎 be a centered 𝑀 -sample average of conditionally independent variables in [−𝑉max , 𝑉max ]; dependence across actions is allowed. With deterministic reward error 𝜂𝑅 , the score error 𝑒𝑀 satisfies {︁√ √︀ }︁ (︀ 𝑀 2 )︀1/2 𝛾𝑉max min 𝐴, 2{log(2𝐴) + 1} . (136) E[𝑒 (𝑠) ] ≤ 𝜂𝑅 + √ 𝑀 2 Hoeffding and a union bound give Pr(max𝑎 |𝑍𝑎 | ≥ 𝑡) ≤ min{1, 2𝐴 exp[−𝑀 𝑡2 /(2𝑉max )]}. at 𝑡20 = ∑︀ Integrating 2 2 2 2 2 2 2𝑉max log(2𝐴)/𝑀 yields E max𝑎 |𝑍𝑎 | ≤ 2𝑉max {log(2𝐴) + 1}/𝑀 ; also E max𝑎 |𝑍𝑎 | ≤ 𝑎 E𝑍𝑎 ≤ 𝐴𝑉max /𝑀 . 𝑀 Minkowski and 𝑒 ≤ 𝜂𝑅 + 𝛾 max𝑎 |𝑍𝑎 | prove (136). The reward error is added once, not per action. OA.7: Moment-localized score perturbations Let 𝐸(𝑥) := max𝑎 |𝑞(𝑥, 𝑎) − 𝑄𝑉 (𝑥, 𝑎)| and let 𝐷(𝑥) be the true regret of the 𝑞-greedy action. Assume ‖𝐸‖𝑟,𝜌 ≤ 𝛿𝑟 with 𝑝 < 𝑟 < ∞. For every 𝑡 > 0 at which the margin is valid at scale 2𝑡, ‖𝐷‖𝑝𝑝,𝜌 ≤ 𝐶marg (2𝑡)𝑝+𝛼 + 2𝑝 𝛿𝑟𝑟 𝑡𝑝−𝑟 .
(137)
Indeed, on {𝐸 ≤ 𝑡}, 𝐷 ≤ 2𝑡 and 𝐷 > 0 implies ∆𝑄 ≤ 2𝑡; on {𝐸 > 𝑡}, 𝐷 ≤ 2𝐸 and E[𝐸 𝑝 1{𝐸 > 𝑡}] ≤ 𝛿𝑟𝑟 𝑡𝑝−𝑟 . For 𝐶marg , 𝛿𝑟 > 0, optimizing the right-hand side gives [︂ ]︂1/(𝑟+𝛼) (𝑟 − 𝑝)𝛿𝑟𝑟 𝑡* = 𝛼 , 2 (𝑝 + 𝛼)𝐶marg
(138)
(𝑟−𝑝)/(𝑝(𝑟+𝛼)) 𝑟(𝑝+𝛼)/(𝑝(𝑟+𝛼)) ‖𝐷‖𝑝,𝜌 ≲𝑝,𝑟,𝛼 𝐶marg 𝛿𝑟 .
This optimized bound requires the margin at scale 2𝑡* ; otherwise minimize (137) over admissible thresholds and compare with ‖𝐷‖𝑝,𝜌 ≤ 2𝛿𝑟 . If 𝛿𝑟 = 0, then 𝐷 = 0 almost everywhere. At 𝑟 = 𝑝 the split gives no improved power; the formal 𝑟 → ∞ limit recovers the uniform-error exponents only with 𝐿∞ control. 37