Mixing Regularization for Average-Reward $Q$-Learning and $Q$-Planning

Julien Roger; Sam Bodmer; Jian Qian; Benjamin Riviere

Source-linked AI summary

Mixing Regularization for Average-Reward $Q$-Learning and $Q$-Planning

Julien Roger, Sam Bodmer, Jian Qian, Benjamin Riviere

arXiv:2610.14988v1Oct 10, 2026cs.LGcs.AImath.OCstat.ML

TL;DR

Average-reward learning without discounting depends on mixing for Bellman contraction, while using a known strongly mixing policy to improve learning remains understudied. The paper analyzes finite-time Q-learning with regularization toward a reward-agnostic m-step mixing policy. Its experiments report improved convergence and exploration as bottlenecks grow more severe, and agreement between theory and observed regularizer rankings.

Problem
Using knowledge of a strongly mixing policy to improve convergence and exploration remains relatively understudied, despite its relevance to learning new tasks from existing policies.
Source: §1 · p. 1
Method
The paper analyzes finite-time average-reward Q-learning algorithms that regularize toward a reward-agnostic m-step mixing policy to control contraction and exploration.
Source: §1 · p. 2
Results
Knowledge of a strong mixing policy improves convergence and exploration, with a larger advantage as bottleneck severity increases; theory predicts the convergence and bias rankings of α-divergence regularizers.
Source: §1 · p. 2
Takeaways & Limitations
Regularizer-dependent quantities characterize contraction, exploration, and operator bias, exposing a trade-off between faster contraction and larger bias.
Source: §1 · p. 2
The Doeblin pair and domination profile are uniform over states, so a bottleneck anywhere dictates the rate everywhere; uniform accuracy also favors exploration with the reference policy.
Source: §7 · p. 10

Abstract

from arXiv · show

The average-reward setting for reinforcement learning is challenging because its Bellman operator is known to contract in span only when the underlying Markov chain is mixing. Whereas existing work typically assumes a contraction property, e.g., through environment mixing, we consider the setting where we are given a reward-agnostic $m$-step mixing policy, and we control the contraction and exploration properties of the learned policy by regularizing toward the mixing policy. We provide finite-time analysis of $Q$-learning algorithms that can be instantiated with multiple choices of regularization, with guarantees measured with respect to the regularized fixed point. Our framework exposes novel regularizer-dependent objects that control contraction, exploration, and operator bias. In the one-step setting, our rates match the best known rates for $Q$-iteration and synchronous $Q$-learning, and for $m$-step mixing we derive new rates. We also study $Q$-planning variants, and show that planning acts as time-localized learning, where the planning horizon $H$ trades off the bias from the boundary value against the sample complexity. Finally, we present numerical studies validating the analysis: (i) knowledge of a strong mixing policy improves convergence and exploration, and its advantage increases with bottleneck severity and, (ii) our theory predicts the convergence and bias rankings of regularizers from the $\alpha$-divergence family.

1 Introduction

Without discounting, average-reward Bellman contraction depends on the transition-policy dynamics, and using a strongly mixing policy to improve learning remains understudied. The paper analyzes regularization toward a reward-agnostic mixing policy and reports finite-time guarantees and empirical validation.

1 Introduction

Without discounting, Bellman contraction is determined solely by closed-loop dynamics formed by transitions and policy.When the MDP is communicating and its transition graph is aperiodic, every full-support policy mixes, though at potentially different rates.Source: §1 · p. 1
The paper asks how regularization toward a mixing policy controls contraction, exploration, bias, and sample complexity, and informs regularization design.This setting is described as natural in robotics and fine-tuning, where new tasks begin from an existing policy.Source: §1 · p. 1
Regularization toward a reward-agnostic policy that mixes in m steps provides both Bellman contraction and the exploration needed for average-reward Q-learning.The analysis identifies regularizer-dependent quantities governing contraction, exploration, and bias.Source: §1 · p. 2
The framework analyzes regularized Q-iteration, synchronous and epoch Q-learning, and Q-planning, with guarantees measured against regularized fixed points.For one-step mixing, the rates match the best known rates for Q-iteration and synchronous Q-learning; the paper derives new rates for m-step mixing.Source: §1 · p. 2
Knowledge of a strong mixing policy improves convergence and exploration, with a larger advantage as bottleneck severity increases.The experiments also find that the theory predicts convergence and bias rankings among α-divergence regularizers.Source: §1 · p. 2

2 Background on Regularized Average-Reward MDPs

The background defines finite average-reward MDPs and their span-based optimality equation, then introduces regularized value functions and policies. Regularization replaces the hard maximum in the Bellman operator with a convex-conjugate value function.

2.1 Average-Reward MDPs

An average-reward MDP has finite state and action spaces, transition probabilities, deterministic rewards, and action-value functions over state-action pairs.Policies induce state-action transition kernels, and the Bellman operator adds expected next-state maximum value to the immediate reward.Source: §2.1 · p. 2
Without discounting, the Bellman operator is not a contraction; for communicating MDPs, the optimality equation is T(Q*) = Q* + ρ*1 with constant optimal gain.Translation invariance motivates the span seminorm, which measures the difference between maximum and minimum values.Source: §2.1 · p. 2

2.2 Regularized MDPs

Regularized MDPs use a temperature and a strongly convex function on each state's action distributions to define regularized values and greedy policies.The regularized Bellman operator uses the convex-conjugate value at the next state; examples include α-divergences to a policy such as forward and reverse KL.Source: §2.2 · pp. 2–3

3 Mixing-Regularized MDPs

The framework assumes a reward-agnostic policy with m-step Doeblin mixing and defines regularizer-dependent quantities for contraction, exploration, and bias. These properties expose a trade-off: stronger contraction and coverage can come with greater operator bias.

3.1 Assumptions

The m-step Doeblin assumption requires a stationary full-support reference policy and a full-support minorizing distribution, making the MDP communicating.The framework also assumes positive temperature, strongly convex closed proper regularizers, and that the reference policy lies in each regularizer's effective domain.Source: §3.1 · p. 3

3.2 Mixing Properties

The domination profile is the largest uniform factor by which every greedy policy with bounded action span dominates the reference policy; the modulus measures regularization gap.The radius is the largest action span along a segment of value functions; the domination profile is non-increasing in radius, and the modulus is non-decreasing.Source: §3.2 · p. 3
Finite-time results require full-support greedy policies; α-divergences with α≤1 satisfy this, while sparse policies such as α>1 can be floored with the reference policy.Strict convexity suffices for the results; strong convexity supplies the greedy-map Lipschitz constant.Source: §3.2 · p. 3

3 Mixing-Regularized MDPs

Under the stated assumptions, the regularized optimality equation has a solution unique up to an additive constant.The mixing objects are introduced to characterize how regularization affects contraction, exploration, and bias.Source: §3.2 · p. 3, §3 · p. 3

3.2 Mixing Properties

The domination profile controls both span contraction and trajectory coverage, while the regularization modulus bounds the one-step operator gap.The averaged greedy policy inherits domination by the reference policy, allowing the m-step Doeblin condition to yield contraction and coverage.Source: §3.2 · pp. 3–4
The framework's bias bound is an operator gap controlled by the regularization modulus, and bounded regularizers have a modulus bounded by temperature times their range.Increasing temperature raises the domination profile and thus contraction and coverage rates, but weakens modulus control; for bounded regularizers, the gain gap vanishes linearly as temperature tends to zero.Source: §3.2 · p. 4

4 Algorithms and Finite-Time Analysis

The section analyzes increasingly realistic algorithms, each isolating contraction, statistical error, exploration, or localization. Under its stated assumptions, the regularized Bellman operator contracts in span at a rate determined by the mixing policy and the regularizer.

4.1 Synchronous Ω-Regularized 𝑄-Iteration

For m = 1, synchronous Q-iteration contracts at rate 1 − β1 per sweep, with O(|S|^2|A| β1^-1 log(e0/ε)) model queries.The span error is non-increasing; for m > 1, the contraction rate depends on the domination profile γΩ.Source: §4.1 · pp. 4–5

4.2 Synchronous Ω-Regularized 𝑄-Learning

Synchronous Q-learning isolates statistical error by updating every state-action pair; its sample-complexity dependence on contraction is β̃^-3.For m = 1 and unit rewards, the passage says its rate matches Zhang et al. (2021).Source: §4.2 · p. 5

4.3 Epoch Ω-Regularized 𝑄-Learning

Epoch Q-learning uses a single trajectory, and its sample complexity worsens over synchronous learning by (γ̄ β̃ ηmin)^-1/|S||A|.The passage attributes this exploration price to the per-pair visitation probability under greedy rollout; rolling out μ lowers the price to βmηmin but does not optimize reward.Source: §4.3 · pp. 5–6

4.4 Ω-Regularized 𝑄-Planning

The single backward sweep is root-level ε-accurate for Q*Ω when H ≥ h1 + m + Heff log+(ΔB/ε), using O(H(max_h|S_h|)^2|A|) model queries.If H is too small, there is insufficient backup information relative to the boundary mismatch ΔB.Source: §4.4 · p. 6
Planning replaces the stationary learning update with depth-shifted updates, so each level uses the next level from the preceding epoch.The planning solution is defined by the finite-horizon recursion and boundary value, and targets the best update possible with information from the first H steps; root error is damped every m levels.Source: §4.4 · p. 6

5 Instances and Experiments

The section instantiates regularization with α-divergences and evaluates how the reference policy and regularizer choice affect convergence, exploration, and bias. The experiments show that benefits depend on targeting an actual bottleneck, while equal-bias comparisons favor smaller α.

5.1 Instances of Base Regularizers

For 0 < α ≤ 1, the α-divergences have a modulus bounded uniformly in R and a full-support greedy policy.The regularizers are defined as Ωα,s := Dα(·∥μs).Source: §5.1 · p. 7, Table 1 · p. 7

5.2 Experiments

Biasing μ toward a difficult doorway reduces the convergence iteration rate by up to ×2.4 when pcross = 0.05, but has no effect without a bottleneck.Convergence is measured with synchronous regularized Q-iteration to isolate contraction from sampling noise.Source: §5.2 · p. 7, Figure 1 · p. 8
Biasing μ toward the doorway shortens exploration epochs by up to ×5 when pcross = 0.05, but triples them when pcross = 1.The coverage constant tracks the shape of this dependence, but not its scale.Source: §5.2 · p. 7, Figure 1 · p. 8
At equal bias, convergence slows as α increases, favoring smaller α; the unregularized epoch algorithm never completes an epoch, and asynchronous RVI Q-learning escapes its local reward trap after ∼108 steps.Figure 2 compares span error against environment steps, using each regularized method’s own target.Source: §5.2 · p. 8, Figure 2 · p. 8
On RiverSwim, value bias decreases with α at a fixed temperature, vanishes fastest as temperature approaches zero for bounded regularizers with α > 0, and coincides across policies at large temperature.The ε-floor restores full support for α > 1 at the price of slightly larger bias at small temperature.Source: §5.2 · p. 8

6 Related Work

Prior average-reward analyses obtain contraction through assumptions, altered dynamics, or discounted approximations, while this work derives regularizer-dependent contraction from a supplied mixing policy. The paper also distinguishes its use of a reference policy from prior uses and relates planning depth to mixing and regularization bias.

6 Related Work

Regularization toward a supplied mixing policy yields regularizer-dependent contraction and coverage, with ε^-2 sample complexity, at the price of bounded bias.The same policy supplies coverage that asynchronous analyses often pay for through behavior-policy covering or mixing time.Source: §6 · p. 9
Unlike prior average-reward reference-policy work using the policy for stability, prior knowledge, conservatism, or conditioning, this paper uses it to make the dynamics mix.The closest α-divergence reference-policy comparison cited is discounted policy-gradient work by Labbi et al. (2026).Source: §6 · pp. 9–10
For average-reward planning, effective depth H_eff = m/β̃ plays the role of 1/(1 − γ), while regularization bias is controlled separately.This makes the depth needed for a given accuracy explicit in the mixing and regularizer.Source: §6 · p. 10

7 Discussion and Limitations

The discussion identifies uniform, state-independent mixing and domination constants as a limitation, since a bottleneck anywhere can dictate the rate everywhere. The appendices provide a notation table and describe learning and planning procedures.

7 Discussion and Limitations

Uniform Doeblin and domination-profile constants make a bottleneck anywhere dictate the rate everywhere; state-dependent constants could yield faster rates.Uniform accuracy over all state-action pairs favors exploring with μ and does not credit acting with the learned policy.Source: §7 · p. 10

A Notation Summary

Table 3 collects notation used across sections.Source: Table 3 · p. 16

B.1 Learning

The learning algorithms center Q iterates by subtracting their mean, a constant shift that does not affect span-seminorm analysis.The appendix also gives Q-iteration and synchronous Q-learning pseudocode.Source: §B.1 · p. 17

B.2 Planning

Planning procedures use reachable layers and a boundary value, then compute values backward across the finite horizon or collect rollout samples for updates.The pseudocode describes both model-based planning and sampled planning variants.Source: §B.2 · pp. 17–18

C.1 Two Rooms: experimental details and bias

The Two Rooms experiments examine convergence and exploration under different doorway probabilities, while Figure 3 reports the exact regularized-value bias as the reference policy’s doorway mass changes.

C.1 Two Rooms: experimental details and bias

The reference policy assigns μ(DOOR) to entering actions at the two doorway entrances and splits the remaining mass equally across the other three actions.The regularizer is ε-floored reverse KL with τ = 2 and ε = 0.05 in all panels.Source: §C.1 · p. 18
Settled convergence rates are fitted where 10^-9 < ∥Q_k − Q*_Ω∥sp < 10^-3, since early iterates converge more slowly as their sharper policies have smaller domination profiles.For p_cross = 0.05 with uniform μ, the first e-fold takes about 170 iterations versus 54.5 once settled.Source: §C.1 · p. 18
Exploration epochs collect one accepted sample per state-action pair, with a cap of 4 · 10^5 transitions; uniform-μ epochs cost 12,304, 3,096, and 1,901 transitions at p_cross = 0.05, 0.3, and 1.The coverage constant is compared by shape because it exceeds these costs by 69, 52, and 39 times, respectively.Source: §C.1 · p. 18
Bias falls from 36.8 to 4.7 when the doorway is a bottleneck, but rises again beyond μ(DOOR) ≈ 0.7.The authors suggest the increase may occur because more doorway mass also sends the agent from the goal room back through the doorway.Source: §C.1 · pp. 18–19, Figure 3 · p. 18

C.2 Choice of the regularizer

The regularizer determines a trade-off between contraction and bias, with its domination profile and regularization modulus governing those effects. The accompanying discussion relates the mixing assumption and proof tools to graph structure, visitation, and span contraction.

C.2 Choice of the regularizer

No α-divergence dominates across contraction, coverage, and bias: 0 < α ≤ 1 keeps the profile positive and modulus bounded, while Hellinger retains a larger profile at large R/τ and reverse KL has a smaller modulus for balanced μ.For α ≤ 0 the modulus is unbounded; for α > 1 the profile vanishes at a finite radius, while ε-flooring restores the profile condition at slightly greater small-temperature bias.Source: §C.2 · p. 19

D Discussion on Assumption 1

Assumption 1 holds for some horizon under every full-support μ exactly when the union transition graph is primitive, equivalently when the MDP is communicating and the graph is aperiodic.The threshold m* depends on the transition graph; larger valid horizons improve mixing and coverage constants but weaken transfer factors.Source: D Discussion on Assumption 1 · p. 20

E.1 Concentration inequalities

The analysis controls visitation counts with a multiplicative lower-tail bound and Bellman-target noise with a maximal martingale bound.The visitation bound keeps cover times linear in the inverse lower bound on pair-visit probability.Source: §E.1 · p. 21

E.2 On span seminorms and the Dobrushin coefficient

The mixing minorization supplies a contraction bound, while the regularizer’s domination profile transfers that bound to greedy policies and supports exploration.The profile therefore links contraction and exploration.Source: §E.2 · p. 22

E Mathematical Background

A Doeblin minorization bounds the Dobrushin coefficient by 1 − β, which bounds the row-stochastic kernel’s contraction in span seminorm by the same factor.The span seminorm of a row-stochastic matrix equals its Dobrushin coefficient.Source: §E.2 · pp. 22–23

E.3 A mean value inequality for the span seminorm

For the regularized Bellman operator, averaging its Jacobian along a segment gives an exact averaged kernel, enabling a mean-value argument in span seminorm.The Jacobian is the state-action kernel of the greedy policy, and row-stochasticity gives it constant row sums.Source: §E.3 · pp. 23–24

F Proofs for Section 2

The proofs establish regularity properties of the regularized value and Bellman operators that support span-based convergence analysis. They also show that strict convexity suffices for the finite-time results and explain how centering relates span convergence to sup-norm convergence.

F Proofs for Section 2

For τ > 0, the gradient of Ω*(Q)(s) is the unique greedy policy, and strong convexity makes this policy Lipschitz in Q.The policy’s ℓ1 change is bounded by the action-span change in Q divided by 2τσ.Source: F Proofs for Section 2 · p. 24
Strict convexity alone suffices for the finite-time bounds and fixed-point existence, although strong convexity supplies the Lipschitz constant.The results also apply to ε-floored α-divergences with α > 2, despite their base regularizers not being strongly convex.Source: F Proofs for Section 2 · p. 25
The greedy policy depends on Q only modulo constants, and centering converts span convergence into sup-norm convergence to the centered fixed-point representative.For centered differences, the sup norm is bounded by the span seminorm.Source: F Proofs for Section 2 · p. 25
The regularized Bellman operator is monotone, translation equivariant, and non-expansive in both sup and span norms; its Jacobian is the greedy-policy state-action kernel.For divergences to μ, the regularizer’s minimum is zero at μ for every state.Source: F Proofs for Section 2 · p. 25

G.1 Proofs for Subsection 3.2

The proofs establish conditions for solvability and uniqueness of the regularized average-reward optimality equation and its fixed points. They formalize how regularization connects mixing and exploration with operator bias, and characterize the regularized gain’s optimality.

G.1 Proofs for Subsection 3.2

Ω-regularization’s domination profile controls mixing-driven contraction and exploration, while its modulus bounds operator bias; m-step minorization yields coverage, with only the last m steps needing regularization.Source: §G.1 · pp. 25, 26, 28

G.2 Strict domination

Property (P1) holds exactly when every regularized greedy policy assigns positive probability to every state-action pair; it holds for α-divergences with α ≤ 1 and floor-wrapped regularizers.It fails for α > 1, while floor-wrapped regularizers satisfy γ_Ω,ε ≥ ε.Source: §G.2 · p. 29

G.3 Existence and uniqueness of the fixed point of 𝒯Ω

Under Assumptions 1–3, Theorem G.1 establishes a regularized fixed point with a unique optimal gain; under (P1), its Q-function is unique up to an additive constant.Source: §G.3 · p. 29

G.3.1 The discounted regularized problem

For each discount factor λ in (0, 1), the discounted regularized operator is a contraction with a unique fixed point, and its unique maximizing policy attains the discounted regularized return.Source: §G.3.1 · p. 30

G.3.2 A necessary and sufficient condition for the existence of the regularized fixed point

Under Assumptions 2, G.1, and G.2, Theorem G.2 establishes existence of a regularized fixed point when discounted relative values are uniformly bounded.The subsection presents this condition as necessary and sufficient, without requiring Assumption 1.Source: §G.3 · p. 29, §G.3.2 · p. 31
Assumption G.2 exactly characterizes solvability of the regularized average-reward optimality equation, as in the unregularized case (Schweitzer and Federgruen, 1978; Puterman, 1994, §8.10).Proposition G.1 proves necessity as well as sufficiency.Source: §G.3.2 · p. 31

G.3.3 Sufficient structural conditions

Weak communication implies Assumption G.2 with finite K* and p* constants; Assumptions 1–3 specialize this result using K*=m and p*=β^mν_min.The corollary identifies the mixing policy μ and gives ν_min := min_s ν(s) > 0.Source: §G.3.3 · pp. 32–33
Assumption G.2 is strictly weaker than weak communication because it is stated for the reward at hand, and it is necessary as well as sufficient.The passage gives equal-reward isolated states as an example where weak communication fails but the fixed point exists.Source: §G.3.3 · p. 33

G.3.4 Uniqueness and interpretation of the gain

The regularized gain is unique without structural assumptions, while the fixed point is unique up to an additive constant under a unique terminal class and full-support greedy policies.For sparse-greedy regularizers, including α>1 and χ², the gain remains unique but the fixed point need not be.Source: §G.3.4 · p. 34
The optimal regularized gain is constant across states, and its maximizing policy is gain-optimal.The proof uses the state-wise maximizing property of the optimal policy and a verification argument.Source: §G.3.4 · p. 34

G.4 Control of the bias

This section analyzes how regularization affects bias and gain loss, and how an ε-floor enables global contraction and coverage at a tunable bias cost. It establishes high-probability radius and finite-time error bounds for synchronous Q-learning by controlling contraction, stochastic noise, and the tracking of a noiseless flow, with lazy updates supporting the learning analyses.

G.4 Control of the bias

The regularized fixed point’s span bias is controlled by the regularization modulus and an effective horizon, while its gain gap vanishes linearly with τ and nearby greedy policies are near-optimal.The effective horizon is m/(β_m γΩ(R*)^(m−1)); this bound is informative only when γΩ(R*) is not too small, whereas the gain-gap bound has no such limitation. The greedy-policy guarantee applies when Q is close to Q*Ω in span.Source: §G.4 · p. 36

G.5 𝜖-Floor-Wrapped Regularization

An ε-floor mixes the base greedy policy with the mixing policy, ensuring global contraction and coverage while adding bias of order εR*.The floor gives a domination profile at least ε and a global contraction rate β_m ε^(m−1); small ε reduces bias but slows contraction, while large ε does the opposite.Source: §G.5 · pp. 36, 38, 39

H Proofs for the learning algorithms of Section 4

The proof framework transfers mixing-policy domination through average-path kernels, uses step-size laziness to obtain block contraction, and controls radius-dependent rates with a stopping-time argument.The step-size transformation yields contraction over blocks even though the one-step operator contracts only over m steps.Source: H Proofs for the learning algorithms… · p. 39

H.1 Proof of Corollary 1

Synchronous regularized Q-iteration has non-increasing span error and reaches a target error geometrically in blocks.The proof bounds the number of sweeps needed using the block contraction rate; each sweep evaluates transitions for all state-action-next-state triples.Source: §H.1 · pp. 39–40

H.2.1 Synchronous full-knowledge updates

In the noiseless synchronous update, the step size makes the linearized dynamics a lazy version of the greedy state-action kernel, enabling block contraction from m-step minorization.The stochastic analysis tracks this deterministic flow.Source: §H.2.1 · p. 40
For m-step mixing, each global block contracts the span error; when m = 1, each update contracts by 1 − α_tβ_1, and Q-iteration contracts by 1 − β_1 per sweep.The radius-adaptive rate improves as the error decreases, approaching a rate governed by the fixed point’s local geometry; a Chernoff bound gives a sharper large-m estimate when κ_0 > 1.Source: §H.2.1 · pp. 41–43

H.2.2 Setting and localized constants

Localized radii bound both the noise scale and the contraction rate, keeping contraction positive even when γ_Ω may vanish at infinity.Before the exit time, the noise scale is bounded by w̄(R), which grows linearly with R, while the localized contraction constant β̄(R) is non-increasing in R and positive.Source: §H.2.2 · p. 44

H.2.3 The noiseless flow before the exit time

Before the exit time, the noiseless virtual flow is non-increasing in span error and contracts by at least 1 − β̄(R) over each global block.This blockwise bound applies when the block starts with error at most R.Source: §H.2.3 · p. 44

H.2.4 Localized noise control

The localized good event has probability at least 1 − δ, controlling stopped noise across the state-action pairs and update intervals.The bound uses a maximal Azuma–Hoeffding inequality and a union bound over pairs and intervals.Source: §H.2.4 · p. 45

H.2.5 Tracking before the exit time

On the localized good event, the stochastic iterates track the noiseless virtual flow up to the exit time, with span error bounded by ε_𝒦(δ′) on each block.The tracking estimate also applies to the final incomplete block.Source: §H.2.5 · p. 45

H.2.6 No escape before the horizon

Under the radius admissibility condition, the good event guarantees no escape before T: σ_R > T and sup_{0≤t≤T} e_t ≤ R.The proposition also gives a blockwise error guarantee for every completed or final incomplete block.Source: §H.2.6 · p. 46
The no-escape argument uses blockwise contraction and deviation bounds to show the error cannot cross R within any block or the residual interval before T.A hypothetical first crossing contradicts the radius definition; the residual interval is handled with the same comparison.Source: §H.2.6 · p. 46

H.2.7 Main result

With probability at least 1 − δ, Theorem H.1 guarantees sup_{0≤t≤T} e_t ≤ R under Assumption H.1, R ≥ e_0, and admissibility condition (H.14).The theorem permits any positive sub-block budget κ_0 and assumes T ≥ 1.Source: §H.2.7 · p. 46
Corollary H.2 specializes Theorem H.1 to a constant step size α ∈ (0, 1) under the same assumptions.The supplied passage introduces C_κ but does not include the corollary’s resulting bound.Source: §H.2.7 · p. 47

H.2.8 Proof of Theorem 1

The proof establishes a high-probability finite-time error guarantee for synchronous Ω-regularized Q-learning by combining epoch-wise localized contraction, coverage, and noise bounds with control of escape before the horizon.

H.2.8 Proof of Theorem 1

With probability at least 1−δ, the proof bounds all iterates within 2e0; choosing α=α(ε/2) balances noise and contraction at ε/2 each.The step-size choice has scaling α(ε/2)=~Θ(β̃^2ε^2/(m^3w̄^2)).Source: §H.2.8 · pp. 47–48

H.3 Proofs for Subsection 4.3 (Epoch Ω-regularized Q-learning)

The epoch analysis uses radius-dependent domination constants to control contraction and exploration, and compares batch and block-martingale bounds for noise.Neither noise bound dominates: batch bounds are tighter for unit step sizes, while block-martingale bounds help with small step sizes and batches, including batch size one.Source: §H.3 · p. 48

H.3.1 Setting, terminology and the epoch update

Each epoch update combines the full-knowledge operator update with a noise term, after the frozen behavior policy gathers the prescribed batch of visits for every state-action pair.The update is Q_{j+1}=F_j(Q_j)+α_jW_{j+1}, with F_j(Q)=(1−α_j)Q+α_jT_Ω(Q).Source: §H.3.1 · p. 49

H.3.2 Exit time, well-posedness and epoch length

Every epoch has finite length almost surely, and the conditional cover-time bound ensures each state-action pair receives its batch of visits with high probability.The stated bound also gives ℓ_j≤mK+1 with conditional probability at least 1−δ′.Source: §H.3.2 · p. 50

H.3.3 The noiseless flow before the exit time

The virtual sequence applies full-knowledge synchronous updates and contracts pathwise within a block when its starting error satisfies e_{b_i}≤R.Source: §H.3.3 · p. 51

H.3.4 Localized noise control

Localization bounds noise increments by the radius-dependent scale w̄(R), enabling high-probability controls both per epoch and across blocks and their prefixes.The analysis uses batch and block-martingale noise bounds; the latter also applies to any block prefix, including the last incomplete block.Source: §H.3 · p. 48, §H.3.4 · p. 52
The localized-noise proof uses a span-non-expansive recursion and a decomposition to bound the span error by ε_mg.The supplied proof fragment invokes Lemma H.13 with localized noise and variance terms substituted for their global counterparts.Source: §H.3.4 · p. 53

H.3.5 No escape before the horizon

On the good event, the radius exit time exceeds J(T), so the error remains at most R through the horizon and epoch lengths satisfy the stated bounds.The good event has probability at least 1−δ.Source: §H.3.5 · pp. 53–54

H.3.6 Main result

With probability at least 1−δ, Theorem H.2 guarantees sup_{0≤j≤J(T)} e_j≤R under Assumption H.1 and the radius admissibility condition.The theorem also gives an additional bound, but its expression is not fully visible in the supplied passage.Source: §H.3.6 · p. 54

H.3.7 The case 𝛼𝑗≡1 and proof of Theorem 2

Theorem 2 analyzes epoch Ω-regularized Q-learning with constant step parameter α_j≡1, giving a finite-time guarantee under the stated assumptions. For m=1, the domination profile affects coverage rather than contraction, yielding a specialized sample-complexity rate.

H.3.7 The case α_j≡1 and proof of Theorem 2

Theorem 2 bounds the iterates with probability at least 1−δ over completed epochs, under Assumptions 1–3 and (P1).The theorem uses a constant batch size and α_j≡1.Source: §H.3.7 · p. 55
With batch size B=⌈B(ε/2)⌉ and T≥mL⌈β̃⁻¹ log(2e₀/ε)⌉, the stated error bound is obtained for ε∈(0,e₀).The sample-complexity argument splits the error into contraction and residual terms, each bounded by ε/2.Source: §H.3.7 · p. 55
For m-step mixing, the epoch length depends on coverage q_R=γ̄β̃η_min, while the contraction factor is β̃.The proof relates the number of completed epochs to the transition budget through the epoch-length bound.Source: §H.3.7 · p. 55
For m=1, the sample complexity is ˜O( w̄²/(β₁³ γ̄ η_min ε²) ), with the domination profile entering through coverage.The contraction rate is independent of the radius in this case.Source: §H.3.7 · p. 55
The update is off-policy, so actions may be drawn from μ instead of greedy policies; this replaces γ̄ with 1 in the coverage factor.For greedy actions, coverage costs at most a factor γ̄^m.Source: §H.3.7 · p. 55
Uniform accuracy on all tabular state-action pairs favors fixed well-mixing behavior and does not credit rewards collected or data concentrated by the learned policy.The stated criterion also does not capture on-policy distribution stability under function approximation.Source: §H.3.7 · p. 55

I Planning: Setting and Main Results

The planning section formulates regularized finite-horizon planning from a reset distribution and analyzes its bias, coverage, and sample requirements. Its depth-wise recursion localizes computation to reachable states and levels, while mixing contracts errors across sufficiently deep levels.

I Planning: Setting and Main Results

Planning computes a regularized H-step solution bootstrapped by boundary value Q_B and uses its root level to approximate Q*_Ω.Only states reachable from the reset distribution are visited, and the levels closest to the root matter most.Source: I Planning: Setting and Main Results · p. 56

J.1 Reachability and the extended target

Reachable layers are formed recursively from supp(ξ); the target extends uniquely to transient reachable states, whose accessibility graph is acyclic.The extension permits comparison with the target at depths before the recurrent core.Source: I Planning: Setting and Main Results · p. 56, §J.1 · p. 57

J.2 Depth-dependent objects

Depth-dependent Bellman operators map values at level h+1 to level h, defining the planning solution by backward recursion.The reachable-set restriction is well-defined, and the planners need no centering projection.Source: I Planning: Setting and Main Results · p. 56

I Planning: Setting and Main Results

The epoch planner uses depth-shifted updates, and without noise forgets its initialization exactly after H−h epochs at level h.Theorem I.1 gives a high-probability planning guarantee; its stated choices of H, J, and B bound the root-level error.Source: I Planning: Setting and Main Results · pp. 56–57

J.3 The master lemma

The master lemma bounds depth-h error using deeper-level Bellman residuals, damped by mixing contraction, so noise does not accumulate across the horizon.The effective horizon plays the role of the discounted planning horizon, and boundary mismatch enters required depth logarithmically.Source: §J.3 · p. 59

J.4 Coverage

Planning coverage comes from resets at shallow levels and mixing at deep levels; greedy-policy coverage pays a factor γΩ(A)^(h₁+m).That factor disappears when behavior follows μ, though shallow states reachable only through narrow paths may still be covered slowly.Source: §J.4 · p. 60

J.5 Model-based planning

Model-based planning performs a backward sweep, with horizon bias controlled by the boundary mismatch; restricting iteration to reachable states can save model queries when the core is a strict subset.The noiseless epoch recursion forgets initialization after exactly H iterations at the root.Source: §J.5 · p. 60

J.6 Epoch planning

Epoch planning separates updates by depth and epoch, yielding finite-time guarantees while trading additional propagation cost for independent samples. Merging depth-indexed tables into reset-based epoch Q-learning removes that planning overhead but changes the fixed point being solved.

J.6 Epoch planning

Epoch j+1 uses level h+1 from epoch j, keeping its input independent of epoch j’s rollout data and preserving the noise martingale structure.A single backward sweep over the same stored transitions would lose that structure; restoring independence would require H disjoint rollout groups.Source: §J.6 · p. 61
With probability at least 1−δ, the epoch-planning bounds control epoch lengths and span error, and initialization vanishes exactly once j≥H−h.The bound applies under the stated radius-admissibility condition; the epoch length is at most N_jH transitions.Source: §J.6 · p. 62
The depth-indexed recursion forgets initialization exactly after H−h epochs, rather than geometrically, because each profile depends on earlier-epoch data along finite diagonals.This contrasts with the geometric initialization factors in the cited H-section bounds.Source: §J.6 · p. 62
For 0<ε<e0, the stated choices of batch size and horizon bound noise and bias by ε/2 each, with total transition cost H·N_H.The passage gives B=˜Θ(M^2w̄^2/ε^2) and H=˜Θ(h1+H_eff).Source: §J.6 · p. 62
At equal coverage, epoch planning costs ˜O(m^4 w̄^2/(β̃^4qε^2)) versus ˜O(m^4 w̄^2/(β̃^3qRε^2)) for Theorem 2, making it a factor 1/β̃ more expensive; merging tables removes this factor.The planning overhead reflects propagation both across depth and across epochs; per table, planning is m times more efficient because resets remove subsampling.Source: §J.6 · p. 62

J.7 Merging the tables: epoch Q-learning with resets

Reset-based epoch Q-learning merges tables on S∞, saves the factor 1/β̃, and has no horizon bias, but its single table no longer solves the exact regularized fixed point.The boundary value acts as initialization; the algorithm uses a centering projection, and the depth profile has no counterpart.Source: §J.7 · pp. 63–64

K The 𝛼-divergence regularizers

The section characterizes α-divergence regularizers through their greedy policies, domination profiles, and regularization moduli. These quantities show how the choice of α affects policy coverage and bias, including a robustness advantage for Hellinger regularization when the reference policy has small minimum mass.

The α-divergence regularizer

The section identifies the domination profile and regularization modulus as its contributions for this family, while collecting several domain, convexity, and greedy-map properties in the paper’s notation.For uniform μ, the regularizer corresponds to Tsallis negentropy up to scaling and an additive constant.Source: K The 𝛼-divergence regularizers · p. 64
For α≤2, Ω_α,s is μ^(1−α)+-strongly convex in the stated norm; for α>2 it is strictly but not strongly convex.The greedy policy and conjugate are also characterized, with truncation active only for α>1.Source: K The 𝛼-divergence regularizers · p. 64
The α-divergence family has a domination profile bounded below by exp2−α(−R/τ); the required uniform domination property holds if and only if α≤1.For α>1 with at least two actions, the profile is zero beyond the stated threshold.Source: K The 𝛼-divergence regularizers · p. 64
The regularization modulus is bounded in R if and only if α>0.For α=0, the relevant rate contains log(1/ε), while the rates described for the family are attained.Source: K The 𝛼-divergence regularizers · p. 64
As μ_min approaches zero, Hellinger regularization has the smallest limiting modulus constant, 4, among 0<α<1, while reverse KL can be smaller for balanced μ.For uniform μ, the passage gives the reverse-KL comparison when |A|≤24.Source: K The 𝛼-divergence regularizers · p. 66