PaperlayerView exact revision on arXiv

Source-linked AI summary

Limiting-Kernel Q($\lambda$): Bridging Short and Long Horizons

Tolga Ok, Arman Sharifi Kolarijani, Peyman Mohajerin Esfahani, Mohamad Amin Sharifi Kolarijani

arXiv:2609.27741v1cs.LGmath.OC

TL;DR

Policy evaluation can require solving a linear system whose dimension is the number of state-action pairs. LKQL combines n-step truncation with a limiting-kernel tail approximation. On MuJoCo, it outperforms GAE on-policy and THQL off-policy across most rollout lengths, particularly on long-horizon tasks.

  • Problem

    Applying the policy-evaluation preconditioner requires solving a linear system whose dimension is the number of state-action pairs.

    Source: §1 · p. 2

  • Method

    LKQL retains the first n terms of an n-step series and approximates the truncated tail using the limiting kernel, with an LK correction to off-policy HQL.

    Source: §1 · p. 2

  • Results

    On MuJoCo, LKQL outperforms GAE on-policy and THQL off-policy across most rollout lengths, particularly on long-horizon tasks.

    Source: §1 · p. 3, §5 · p. 18

  • Takeaways & Limitations

    A double-backup implementation maintains separate critic and LK-term value functions, allowing straightforward integration into existing actor-critic frameworks.

    Source: §5 · p. 18

    Control convergence analysis assumes a fixed behavior policy; practically, the second critic increases memory and update costs and adds hyperparameters.

    Source: §5 · p. 19

Abstract

from arXiv · show

In value-based reinforcement learning, improving the accuracy of policy evaluation has been shown to improve downstream policy optimization performance. The widely adopted family of approximations relying on $n$-step truncation yields computationally efficient value estimators but is inherently limited to a short evaluation horizon. In contrast, methods that exploit the global structure of the transition dynamics can accelerate policy evaluation, but their memory and computational requirements often limit scalability to large or continuous state spaces. To reconcile these limitations, we introduce Limiting-Kernel Q($\lambda$) (LKQL), an off-policy value estimator that combines $n$-step truncation with a long-horizon approximation based on the limiting kernel (LK). LKQL has the same order of complexity as $n$-step estimators and integrates directly into both on- and off-policy actor-critic algorithms. We prove that, under aperiodicity and in the near-on-policy regime, the operator underlying LKQL improves the policy evaluation convergence rate over its truncated counterpart for sufficiently large $n$, and that LKQL itself converges almost surely to the optimal values in finite Markov decision processes (MDPs) under a fixed behavior policy. On the MuJoCo continuous-control benchmark, we show that LKQL improves over $n$-step baselines in most settings, particularly on long-horizon tasks.

1. Introduction

Policy evaluation needs accurate value targets, but existing approaches trade short-horizon, rollout-efficient estimates against global methods that can be difficult to scale. LKQL combines n-step truncation with a limiting-kernel tail approximation, using a double backup to support long-horizon estimation with return-estimator-like per-sample complexity.

1. Introduction

  • Policy evaluation accuracy matters because it governs Bellman-solve convergence in finite MDPs and bounds the suboptimality of greedy policies formed from learned targets.More accurate targets are also reported as effective design choices in practice.Source: §1 · p. 1
  • Directly applying the exact preconditioner requires solving a state-action-sized linear system; n-step estimators are rollout-efficient, while global preconditioner methods often do not scale to large or continuous spaces.Global methods may require updates across the full state-action space or superlinear matrix operations.Source: §1 · p. 2
  • Tail completion keeps the first n terms of the evaluation series and approximates the remaining terms with the limiting kernel, which approaches the transition-power tail for aperiodic chains.The limiting kernel increasingly approximates higher powers of the transition operator.Source: §1 · p. 2
  • LKQL realizes the estimator with a double backup: one TD backup for values and another for the LK term, enabling on- and off-policy actor-critic integration.The value and LK-term backups maintain separate functions.Source: §1 · p. 3
  • The LK operator can improve convergence over its truncated counterpart in a characterized regime; LKQL converges almost surely and outperforms GAE and truncated HQL in most MuJoCo settings.The reported gains are particularly evident on long-horizon tasks.Source: §1 · p. 3

2. Preliminaries

The preliminaries frame value learning as Bellman fixed-point computation and contrast partial, truncated evaluation with full policy iteration. They formalize behavior-policy off-policy operators, truncation-dependent convergence, and limiting-kernel properties.

2.1. MDPs, policy evaluation, and control

  • Policy evaluation and control are Bellman fixed-point problems, and repeated application of their contraction operators converges to the corresponding values.Source: §2.1 · p. 4
  • Policy iteration fully propagates the Bellman residual through its preconditioner, whereas value iteration uses the identity and performs partial policy evaluation.Source: §2.1 · pp. 4–5
  • Off-policy operators propagate target-policy Bellman residuals under behavior-policy dynamics, with correction choices distinguishing conservative from non-conservative methods.Source: §2.1 · pp. 5–6

2.2. Truncated Harutyunyan operator

  • Shorter n increases convergence-condition bounds, stabilizing iterations and allowing larger policy discrepancies; n = 1 recovers rate γ, while n → ∞ recovers the original non-truncated behavior.Source: §2.2 · p. 7
  • For policy evaluation, truncation improves the rate when ε > 1−γ but worsens it when ε < 1−γ; in control, truncation always improves the rate.Source: §2.2 · p. 7

2.3. Limiting kernel, aperiodicity, and unichains

  • For aperiodic chains, transition powers converge to a limiting kernel composed of stationary averages over reachable recurrent classes, with convergence characterized geometrically.Source: §2.3 · p. 8

3. Tail-completed operators

The section completes truncated operator tails with a limiting-kernel approximation, then analyzes when this improves convergence and how to estimate it from samples. It presents LKQL as a double-backup learner with finite-MDP convergence guarantees.

3.1. Limiting-kernel preconditioner

  • For aperiodic Pπ, its powers approach the limiting kernel, making tail approximation more accurate as n grows; the surrogate is tractably invertible and sample-estimable.The section introduces the limiting-kernel preconditioner as a tail-completion approximation to the omitted terms.Source: §3 · p. 8, §3.1 · pp. 9–10

3.2. Off-policy operators

  • Aperiodic behavior chains and policy discrepancy ε < 1 − γ permit LKHI to beat truncated HI for sufficiently large n.The strongest gain is on-policy: for λ = 1, improvement holds when n is at least the mixing time.Source: §3.2 · pp. 11–12
  • In control, LKHI matches non-truncated HQL’s convergence rate and conditions; greedy-policy discontinuity prevents a proven rate gain over HI.The analysis must allow worst-case policy discrepancy across iterations.Source: §3.2 · p. 12

3.3. Value estimation with a double backup

  • LKQL estimates the behavior-chain limiting-kernel contribution through auxiliary U, whose fixed point tracks long-run average TD error.As τ approaches 1, U more accurately approximates the limiting-kernel propagation of the Bellman error.Source: §3.3 · p. 12
  • Despite the LK preconditioner’s spectral structure, LKQL updates one sampled state-action pair per step, supporting extension to continuous state-action spaces.This contrasts with methods that estimate a full preconditioner or low-rank approximation and update all state-action pairs simultaneously.Source: §3.3 · p. 13
  • Under finite MDPs, fixed μ, i.i.d. starts, full reset coverage, and λ < 1 − γ, LKQL converges almost surely to Q*.The authors describe i.i.d. sampling as an analytical idealization, while full reset coverage ensures every state-action pair is visited infinitely often.Source: §3.3 · pp. 13–14

4. Evaluation

The evaluation studies LKQL on finite Garnet MDPs and MuJoCo continuous-control tasks, comparing it with truncated operators and value-estimator baselines. It reports stronger results in near-on-policy settings and across most tested continuous-control rollout lengths, with important qualifications at λ = 1.

4.1. Finite MDP

  • For exact-model policy evaluation, LKHI(π) has a lower error-operator rate than HI(π) at small ϵ and large λ, while the ranking reverses at larger ϵ.The lower-rate regime is the near-on-policy region identified by Theorem 3.2; the two operators nearly coincide at small λ.Source: §4.1 · p. 14, Figure 2 · p. 15
  • For λ < 1, LKQL has lower value error than THQL at every rollout length; at λ = 1, it is not uniformly better and has higher error for n ∈ {5, 6, 7}.The gap for λ < 1 is largest at large λ and short n, and narrows as n grows.Source: §4.1 · p. 15, Figure 2 · p. 15

4.2. Continuous control

  • In the on-policy PPO extension, the policy retains PPO’s clipped surrogate objective, while LKQL supplies value targets computed before and held fixed through inner-loop updates.The fixed targets implement a fitted Q-iteration scheme.Source: §4.2 · p. 16
  • In the off-policy NAF extension, Q-values use a state-value baseline and quadratic advantage, while the LK-term update remains on-policy under the behavior policy.The NAF representation makes policy improvement implicit; the LK-term update uses the behavior-policy trace coefficient.Source: §4.2 · p. 17
  • The continuous-control benchmark covers Hopper, Walker2d, and HalfCheetah, using PPO with GAE on-policy and NAF with THQL off-policy over several rollout lengths.Each method is trained for 500 outer iterations with 16 parallel actors; final cumulative episodic rewards are averaged over 32 seeds.Source: §4.2 · p. 17, Figure 3 · p. 18
  • LKQL achieves higher returns than GAE and THQL across most tested rollout lengths on Hopper, Walker2d, and HalfCheetah, with the largest improvement on HalfCheetah.Figure 3 compares LKQL with each baseline within its actor-critic backbone; the reported evaluation averages 32 seeds.Source: §4.2 · p. 17, Figure 3 · p. 18

5. Conclusion

The conclusion presents LKQL as a double-backup extension that combines n-step truncation with a limiting-kernel tail approximation. It summarizes the operator’s conditional rate advantage, the algorithm’s finite-MDP convergence and MuJoCo results, and boundaries on the analysis and extensions.

5. Conclusion

  • For an aperiodic behavior chain in the near-on-policy regime, the LK Harutyunyan operator improves policy-evaluation convergence over truncated HQL for sufficiently large n.The method approximates the omitted tail of the n-step truncation using the behavior transition operator’s limiting kernel.Source: §5 · p. 18
  • LKQL uses a double backup with separate critic and LK-term value functions, converges almost surely to Q⋆ in finite MDPs under fixed behavior and i.i.d. initial pairs, and beats GAE and THQL on most tested MuJoCo rollout lengths.The separate value functions support integration into actor-critic frameworks.Source: §5 · p. 18
  • The limiting-kernel extension also applies to Peng & Williams’ Q(λ), while extending it to Retrace or Tree-Backup requires a suitable tail approximation and auxiliary estimators.The latter extension is left for future work.Source: §5 · pp. 18–19
  • LKQL’s control convergence analysis assumes a fixed behavior policy, and its separate LK-term critic increases memory and update cost while adding hyperparameters.The added hyperparameters include τ, βU, and λU, as well as optimizer settings for that critic.Source: §5 · p. 19

Appendix A. Technical Proofs

The appendix gathers notation and identities used throughout the proofs, including a decomposition of the operator terms and quantities characterizing the limiting-kernel tail and policy mismatch.

A.1. Notation and Preliminaries

  • The appendix defines X as the component aligned with the behavior chain and W as capturing off-policy mismatch and λ-discounting.The text connects X to the Bellman-residual component absorbed by the preconditioner through a telescoping identity.Source: §A.1 · p. 19
  • It records ξ as the infinity norm of the LK tail-completion operator and ϵ as the maximum statewise L1 discrepancy between behavior and target policies.These quantities are introduced among the proof notation and preliminaries.Source: §A.1 · pp. 19–20
  • The appendix states that the listed identities are reused by name in later proofs and recalls a row-sum identity for a non-negative finite operator.The row-sum identity is then used for the preconditioner Cµ.Source: §A.1 · p. 20

A.2. Proof of Lemma 2.1

The proof of Lemma 2.1 analyzes policy evaluation and control through their value-error operators. It factors the Bellman residual for evaluation and uses contraction bounds to establish error reduction for control.

A.2. Proof of Lemma 2.1

  • For policy evaluation, the Bellman residual factors as (γPπ − I)(Q − Qπ), and the resulting HI(π) error operator is bounded to yield geometric error decay.The passage identifies the operator norm bound as the route to the stated error bound.Source: §A.2 · p. 20
  • The evaluation error operator is rewritten using a telescoping identity as (γλPµ)^n plus the preconditioner applied to W.Its recursion yields the bound mn+1 ≤ (1 − γλ)ηϵ + γλmn.Source: §A.2 · p. 20
  • For control, the proof establishes a one-step infinity-norm error contraction with factor βc, then derives the corresponding condition on λ.The argument uses that the greedy-policy Bellman operator equals the optimality operator and that the latter is a γ-contraction.Source: §A.2 · p. 21

A.3. Proof of Lemma 3.1

The proof bounds the finite-horizon limiting-kernel residual using aperiodicity and establishes a threshold after which the residual remains below one.

A.3. Proof of Lemma 3.1

  • The finite-horizon limiting-kernel residual is the quantity whose bound is established in this proof.The supplied passage introduces this residual but does not provide its full expression.Source: §A.3 · p. 22
  • The proof bounds the residual using the triangle inequality and the aperiodicity bound.Source: §A.3 · p. 22
  • At k = nπ the residual drops below one and, by monotonicity, stays below one for every k ≥ nπ.Source: §A.3 · p. 22

A.4. Proof of Theorem 3.2

The proof analyzes LKHI(π) through its error operator, bounds its norm, and derives a convergence condition expressed as an upper bound on policy discrepancy.

A.4. Proof of Theorem 3.2

  • The LKHI(π) error operator is used to express the iteration’s value error as Eℓ+1 = f Mn Eℓ.Source: §A.4 · p. 22
  • The proof expands the error operator into four terms and simplifies terms using telescoping and absorption identities.Source: §A.4 · p. 22
  • Convergence requires ηϵ < 1 − (γλ)^nδµ, which the proof rearranges into the upper bound ϵ < eϵmax.Source: §A.4 · p. 23

A.5. Proof of Corollary 3.3

The corollary’s result is derived from Theorem 3.2 together with the aperiodicity bound.

A.5. Proof of Corollary 3.3

  • The corollary’s result follows from Theorem 3.2 and the aperiodicity bound.Source: §A.5 · p. 23

A.6. Proof of Theorem 3.5

The proof bounds the value-error iteration for LKHI in control and gives a condition on λ for convergence.

A.6. Proof of Theorem 3.5

  • For the control problem, the proof bounds the next LKHI value error by η2 times the current error.Source: §A.6 · p. 23
  • The derivation uses that T is a γ-contraction.Source: §A.6 · p. 24
  • Requiring η2 < 1 yields the convergence condition λ < (1 − γ)/(2γ).Source: §A.6 · p. 24

A.7. Proof of Theorem 3.6

The proof applies a two-timescale stochastic-approximation theorem by verifying its conditions for LKQL and establishing stability of the fast and slow ODEs. It concludes that the iterates converge almost surely to the optimal action values and the corresponding fast-timescale equilibrium.

A.7. Proof of Theorem 3.6

  • The remaining stochastic-approximation conditions include positive step sizes, Lipschitz drifts, and globally asymptotically stable fast and slow ODE equilibria.The proof verifies the fast equilibrium’s Lipschitz dependence on Q and applies the slow-scale stability result.Source: §A.7 · pp. 24, 25, 26, 28
  • Conditional expectations define martingale-difference noise for the full-vector LKQL recursion, whose second moments are bounded by a finite constant times the iterates’ squared norms.The TD errors are bounded by ∥r∥∞ + (1 + γ)∥Qk∥∞.Source: §A.7 · pp. 26–27
  • The proof casts the LKQL recursion as two-timescale stochastic approximation with expected drifts H = Bρh and G = Bρg.The diagonal operator Bρ weights the drifts according to the reset distribution ρ.Source: §A.7 · pp. 25–26
  • The proof establishes almost-sure boundedness of both iterates using a two-timescale stability theorem and scaled-drift conditions.The scaled fast and slow ODEs have globally asymptotically stable equilibria, including the origin for the scaled slow ODE.Source: §A.7 · p. 27
  • The fast ODE has a unique globally asymptotically stable equilibrium, and the slow ODE has Q⋆ as its unique globally asymptotically stable equilibrium.The fast equilibrium is U⋆(Q) = Aµτ(TQ − Q); the slow ODE is analyzed with the fast iterate at equilibrium.Source: §A.7 · pp. 25, 28
  • Qk converges almost surely to Q⋆, while Uk converges to U⋆(Q⋆) = 0.This follows after verifying the two-timescale theorem's conditions.Source: §A.7 · p. 28

Appendix B. Experimental Setup

The experiments use shared actor-critic sampling and backbone structures, with the LK term disabled to recover GAE or THQL baselines. They vary rollout length, tune LKQL-specific settings, and report final deterministic-policy returns averaged over seeds.

Appendix B. Experimental Setup

  • LKQL and its baselines share the actor-critic backbone and sampling loop, with the baselines recovered by disabling the LK term.This yields GAE for on-policy learning and THQL for off-policy learning.Source: Appendix B · p. 28
  • The on-policy networks use (64, 64) policy and (128, 128) value hidden sizes; the off-policy NAF uses (64, 64) for its mean and (128, 128) for value and precision.The LK-term network is separate and uses (128, 128) hidden sizes in both estimators.Source: Appendix B · p. 29
  • Each run uses 16 actors for 500 iterations, varies rollout length from 32 to 512, and reports deterministic-policy return averaged over 32 seeds.Each iteration performs 10 update epochs with minibatches of 32; longer rollouts increase total environment steps.Source: Appendix B · p. 29
  • Baselines are tuned over rollout length and, for NAF, exploration noise; LKQL inherits the best settings and tunes its LK-specific parameters.Final evaluation uses selected hyperparameters on separate seeds to prevent tuning bias.Source: Appendix B · p. 29

Related papers

Loading 2609.27741v1…