betaFeedback

WorksComputer Science

MINT: Meeting-time Indicators for Truncation in Multi-Step Off-Policy RL

Abstract

Many multi-step off-policy temporal-difference methods handle policy mismatch through products of per-step trace coefficients, leading to a trade-off between variance control and long-horizon signal. The maximum trace length consequently becomes a sensitive hyperparameter. We propose MINT (Meeting-time INdicators for Truncation), which replaces these products with a binary stopping indicator: one until coupled behavior and target trajectories first meet, zero thereafter. At the true value function, the indicator's idempotence yields a variance bound governed by meeting-time survival. For practical implementation, a single sampled action provides a model-free surrogate for the stopping rule, requiring no transition model or mixing-time estimate. We derive separate sufficient conditions for contraction of the state-coupled operator and its practical surrogate under fixed-policy evaluation. On MuJoCo and DeepMind Control tasks, MINT outperforms the reported multi-step baselines; the main MuJoCo comparison uses a common cap without per-task cap-length tuning. We also demonstrate the effectiveness of MINT on Atari 100k, RWRL, and OGBench experiments; MINT adapts the backup horizon to reduce target variability relative to long fixed-horizon backups across tasks and dynamics.

Introduction

Multi-step temporal-difference (TD) learning propagates rewards over longer horizons, making it a central tool for policy evaluation and credit assignment in reinforcement learning [28, 4, 18, 41, 34]. In off-policy learning, however, longer backups also accumulate the effects of mismatch between the behavior and target policies. Many methods handle this mismatch through products of per-step trace coefficients. Unclipped importance-sampling ratios can amplify variance, while clipping controls the weights but can weaken long-horizon learning signals [31, 35]. Methods such as Retrace and Peng’s Q(λ)Q(\lambda) make different compromises between signal retention, fixed-point bias, and convergence conditions [31, 24, 15]. These trade-offs make the maximum trace length, or cap length, a consequential choice and motivate adapting the backup horizon to the encountered policy mismatch. Prior on-policy analysis offers a complementary perspective by relating sufficient backup length to temporal dependence [10]. Estimating the relevant mixing properties can be difficult, and the corresponding guarantees do not directly extend to off-policy sampling. This motivates a sample-based stopping rule that adapts the backup horizon without estimating mixing time:

Can idempotent coupling indicators enable adaptive backups that better balance long-horizon learning signals and target variability?

We introduce MINT (Meeting-time INdicators for Truncation). In its theoretical construction, behavior and target state processes are coupled, and a binary mask retains the trace until their first agreement. The cumulative mask remains zero thereafter, turning the backup into a randomly truncated sum of TD errors. For model-free implementation, an action-level surrogate uses the policy ratio at a single sampled action to decide whether to continue. This surrogate defines its own stopping process and requires neither transition-kernel access nor a mixing-time estimate. Figure 1 illustrates the empirical motivation on MuJoCo Hopper. Across the tested caps, MINT exhibits a favorable empirical bias–variance balance and maintains high returns. This motivates examining how stochastic truncation changes both learning performance and the resulting target estimates.

Figure 1. Cap-length sensitivity on MuJoCo Hopper (SAC). (a) Bias and variance at 100K and 1M steps for caps {3,5,10,20}\{3, 5, 10, 20\} (darker shades indicate shorter caps). MINT exhibits a favorable empirical bias–variance balance across the tested caps; several baseline configurations have higher variance at longer caps. (b) Learning curves for the same caps. MINT attains high returns across the tested values, whereas baseline performance varies more with the cap.

Contributions. We provide (i) a coupling-based formulation of stochastic truncation and a model-free action-level implementation (§ 3); (ii) a survival-based variance bound at QπQ^{\pi} for the state-coupled estimator and separate sufficient contraction conditions for the state-coupled and practical surrogate operators under fixed-policy evaluation (Lemma 3.3 and Theorems B.9 and 4.1); and (iii) comparative evaluations demonstrating gains over multi-step baselines on MuJoCo and DMC, using a common cap without per-task cap tuning in the main MuJoCo comparison, alongside task-dependent benefits on Atari 100k, RWRL, and OGBench (§ 5).

Preliminaries

We consider a Markov decision process (MDP) (S,A,P,P0,r,γ)(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{P}_0, r, \gamma) with finite state and action spaces, transition kernel P:S×A→Δ(S)\mathcal{P} : \mathcal{S} \times\mathcal{A} \to\Delta(\mathcal{S}), initial distribution P0\mathcal{P}_0, bounded reward r:S×A→[−rmax⁡,rmax⁡]r : \mathcal{S} \times\mathcal{A} \to[-r_{\max}, r_{\max}], and discount γ∈[0,1)\gamma\in[0,1) [40]. For a policy π\pi, the Bellman operator is TπQ:=r+γPπQT^{\pi}Q := r + \gamma\mathcal{P}^{\pi}Q, where (PπQ)(s,a):=Es′∼P(⋅∣s,a), a′∼π(⋅∣s′)[Q(s′,a′)](\mathcal{P}^{\pi}Q)(s,a) := \mathbb{E}_{s' \sim\mathcal{P}(\cdot\mid s,a),\,a' \sim\pi(\cdot\mid s')}[Q(s',a')]. Trajectories (st,at,rt)t≥0(s_t,a_t,r_t)_{t \ge0} are generated by a behavior policy β\beta, and our goal is to estimate the action-value function QπQ^{\pi} of a target policy π≠β\pi\ne\beta from these off-policy samples [34, 41].

The Retrace Operator and the Variance Explosion Problem

A central challenge in multi-step off-policy evaluation is correcting the distributional mismatch between β\beta and π\pi without inflating the variance of the multi-step return. The general Retrace operator [31] formalizes this correction through a sequence of per-step trace coefficients ci:=c(si,ai)c_i := c(s_i,a_i):

RQ=Q+Eβ[∑t=0∞(γλ)t(∏i=1tci)δtQ],δtQ:=rt+γEπ[Q(st+1,⋅)]−Q(st,at),(1)\mathcal{R}Q = Q + \mathbb{E}_{\beta}\left[\sum_{t=0}^{\infty}(\gamma\lambda)^t\left(\prod_{i=1}^{t}c_i\right)\delta_t^Q\right], \qquad\delta_t^Q := r_t + \gamma\mathbb{E}_{\pi}[Q(s_{t+1},\cdot)] - Q(s_t,a_t), \tag*{(1)}

with the convention ∏i=10ci=1\prod_{i=1}^{0} c_i = 1 and λ∈[0,1]\lambda\in[0,1] controlling the geometric decay of the trace [7]. Existing multi-step off-policy methods instantiate Equation (1) by a choice of cic_i: Retrace [31] uses ci=min⁡(1,π(ai∣si)/β(ai∣si))c_i = \min(1,\pi(a_i \mid s_i)/\beta(a_i \mid s_i)); Harutyunyan’s Qπ(λ)Q^{\pi}(\lambda) uses ci=1c_i = 1 [19]. A sufficient conservative constraint is 0≤ci≤π(ai∣si)/β(ai∣si)0 \le c_i \le\pi(a_i \mid s_i)/\beta(a_i \mid s_i), which guarantees contraction of the expected evaluation operator toward QπQ^{\pi} for fixed policies [31].

The variance explosion problem. For a finite cap LL, write Zt:=(γλ)t(∏i=1tci)δtQZ_t := (\gamma\lambda)^t \left(\prod_{i=1}^{t} c_i\right)\delta_t^Q. The estimator’s second moment has the exact expansion

E[(∑t=0L−1Zt)2]=∑t=0L−1(γλ)2tE[(∏i=1tci2)(δtQ)2]⏟diagonal terms E[Zt2]+2∑0≤u<t<LE[ZuZt].(2)\mathbb{E}\left[\left(\sum_{t=0}^{L-1} Z_t\right)^2\right] = \underbrace{\sum_{t=0}^{L-1}(\gamma\lambda)^{2t}\mathbb{E}\left[\left(\prod_{i=1}^{t}c_i^2\right)(\delta_t^Q)^2\right]}_{\text{diagonal terms }\mathbb{E}[Z_t^2]} + 2\sum_{0\le u<t<L}\mathbb{E}[Z_uZ_t]. \tag*{(2)}

Trace weights and TD errors can be dependent, and cross terms need not vanish at arbitrary QQ. Unclipped importance-sampling ratios can amplify second moments over long traces; clipped coefficients need not exhibit this growth. Table 1 summarizes representative operators using the classification of Kozuno et al. [24]. Conservative methods such as Retrace bound coefficient products but may weaken long-horizon signals. Non-conservative methods can retain more signal but may introduce off-policy bias or require additional stability conditions [24, 35]. These trade-offs can make performance sensitive to cap length, motivating task-specific tuning [20].

OperatorTrace / return ruleE[Wt2]\mathbb{E}[W_t^2]Conservative?Fixed point
Retrace [31]ci=min⁡(1,π/β)c_i=\min(1,\pi/\beta)E[∏i=1tci2]\mathbb{E}[\prod_{i=1}^{t}c_i^2]YesQπQ^\pi
Peng’s Q(λ)Q(\lambda) [24]ci=1†c_i=1^{\dagger}11NoQπλQ^{\pi_\lambda}
Uncorrected nn-stepTn\sqrt[n]{\vphantom{T}}1{t<n}\mathbf{1}\{t<n\}Noβ\beta-dependent
MINTci=Ai∈{0,1}c_i=A_i\in\{0,1\}Pr⁡(T>t)\Pr(T>t)NoQπQ^\pi

Table 1. Multi-step off-policy operators for behavior and target policies. WtW_t excludes (γλ)t(\gamma\lambda)^t; E[Wt2]\mathbb{E}[W_t^2] describes squared weights, not the full estimator variance.

Mixing Time and Effective Horizon

Mixing time describes how quickly a Markov chain forgets its initial state. For an ergodic behavior chain with transition kernel Pβ\mathcal{P}^{\beta} and stationary distribution μβ\mu_{\beta}, the total-variation (TV) mixing time is

τmixβ:=min⁡{t≥0:sup⁡s∥(Pβ)t(s,⋅)−μβ∥TV≤14}.\tau_{\mathrm{mix}}^{\beta} := \min\left\{t\ge0:\sup_s\left\lVert(\mathcal{P}^{\beta})^t(s,\cdot)-\mu_{\beta}\right\rVert_{\mathrm{TV}}\le\frac{1}{4}\right\}.

It measures convergence to stationarity uniformly over initial states [26], but can be difficult to estimate directly from trajectories [46]. For on-policy evaluation (β=π\beta=\pi) with bounded rewards, Duan and Wainwright [10, Section 3.3.2, Eq. (29b)] obtain finite-sample bounds for multi-step kernel least-squares TD under their assumptions and the look-ahead condition

K≳min⁡{H,τ⋆β},H:=(1−γ)−1.(3)K \gtrsim\min\{H,\tau_{\star}^{\beta}\}, \qquad H := (1-\gamma)^{-1}. \tag*{(3)}

Here τ⋆β\tau_{\star}^{\beta} denotes the mixing parameter used in their analysis, whose definition differs from the TV mixing time τmixβ\tau_{\mathrm{mix}}^{\beta} above; see Appendix § 8.1.§ 7 for its definition and the detailed assumptions. This condition links the backup horizon to chain-level temporal dependence, but applying it requires knowledge of mixing properties. Moreover, the guarantees of Duan and Wainwright [10] rely on on-policy sampling and do not directly extend to β≠π\beta\ne\pi. These limitations motivate our sample-based stopping rule for off-policy multi-step evaluation (§ 3).

The MINT Operator

We introduce MINT, which replaces products of real-valued trace coefficients with a binary stopping rule. We first define the state-coupled operator, then establish a variance bound at QπQ^\pi, and finally describe its model-free action-level surrogate. Let Stβ,StπS_t^\beta,S_t^\pi start from a shared state. At policy-generated steps, maximally couple their policy-induced next-state kernels. Write Ht\mathcal{H}_t for the joint pre-action history and Gt=Ht∨σ(at)\mathcal{G}_t=\mathcal{H}_t\vee\sigma(a_t). At such steps, the behavior action has conditional law β(⋅∣Stβ)\beta(\cdot\mid S_t^\beta) given Ht\mathcal{H}_t. The conditional environment law of (rt,St+1β)(r_t,S_{t+1}^\beta) given Gt\mathcal{G}_t must equal its law given (Stβ,at)(S_t^\beta,a_t). The filtration and initial-action conditioning are specified in Appendix § 8.2.§ 1.

References

  1. [1]Y. Abbasi-Yadkori, P. Bartlett, K. Bhatia, N. Lazic, C. Szepesvari, and G. Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692–3702. PMLR, 2019.
  2. [2]J. Achiam. Spinning up in deep reinforcement learning, 2018.
  3. [3]R. Agarwal, M. C. Machado, P. S. Castro, and M. G. Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In Advances in Neural Information Processing Systems, volume 34, 2021.arxiv.org/abs/2108.13264
  4. [4]K. D. Asis and R. S. Sutton. Per-decision multi-step temporal difference learning with control variates. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pages 786–794. AUAI Press, 2018.arxiv.org/abs/1807.01830
  5. [5]A. P. Badia, B. Piot, S. Kapturowski, P. Sprechmann, A. Vitvitskyi, Z. D. Guo, and C. Blundell. Agent57: Outperforming the Atari human benchmark. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 507–517, 2020. URL https://proceedings.mlr.press/v119/badia20a.html.arxiv.org/abs/2003.13350
  6. [6]M. G. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, volume 29, 2016. URL https://arxiv.org/abs/1606.01868.
  7. [7]D. P. Bertsekas and S. Ioffe. Temporal differences-based policy iteration and applications in neuro-dynamic programming. Lab. for Info. and Decision Systems Report LIDS-P-2349, MIT, Cambridge, MA, 14:8, 1996.
  8. [8]P. S. Castro, S. Moitra, C. Gelada, S. Kumar, and M. G. Bellemare. Dopamine: A Research Framework for Deep Reinforcement Learning. arXiv preprint arXiv:1812.06110, 2018. URL http://arxiv.org/abs/1812.06110.
  9. [9]B. Daley, M. White, C. Amato, and M. C. Machado. Trajectory-aware eligibility traces for off-policy reinforcement learning. In International Conference on Machine Learning, pages 6818–6835. PMLR, 2023.arxiv.org/abs/2301.11321
  10. [10]Y. Duan and M. J. Wainwright. Policy evaluation from a single path: Multi-step methods, mixing and mis-specification. arXiv preprint arXiv:2211.03899, 2022. URL https://arxiv.org/abs/2211.03899.
  11. [11]G. Dulac-Arnold, N. Levine, D. J. Mankowitz, J. Li, C. Paduraru, S. Gowal, and T. Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 110(9):2419–2468, 2021. doi: 10.1007/s10994-021-05961-4.
  12. [12]Farama Foundation. Minari: A dataset interface for offline reinforcement learning. https://github.com/Farama-Foundation/Minari, 2022.
  13. [13]J. Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.arxiv.org/abs/2004.07219
  14. [14]S. Fujimoto, H. van Hoof, and D. Meger. Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning, pages 1587–1596, 2018.
  15. [15]M. Geist, B. Scherrer, et al. Off-policy learning with eligibility traces: a survey. J. Mach. Learn. Res., 15(1):289–333, 2014.
  16. [16]T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pages 1861–1870. PMLR, 2018.arxiv.org/abs/1801.01290
  17. [17]B. Hao, N. Lazic, Y. Abbasi-Yadkori, P. Joulani, and C. Szepesvari. Provably efficient adaptive approximate policy iteration. arXiv preprint arXiv:2002.03069, 2020.arxiv.org/abs/2002.03069
  18. [18]A. Harutyunyan. Beyond Single-Step Temporal Difference Learning. PhD thesis, Ph. D. thesis, Vrije Universiteit Brussel (VUB), 2018.
  19. [19]A. Harutyunyan, M. G. Bellemare, T. Stepleton, and R. Munos. Q(λ) with off-policy corrections. In Proceedings of the 27th International Conference on Algorithmic Learning Theory, volume 9925 of Lecture Notes in Computer Science, pages 305–320. Springer, 2016.DOI
  20. [20]M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.arxiv.org/abs/1710.02298
  21. [21]J. E. Johndrow and J. C. Mattingly. Coupling and decoupling to bound an approximating markov chain. arXiv preprint arXiv:1706.02040, 2017.arxiv.org/abs/1706.02040
  22. [22]J. E. Johndrow and J. C. Mattingly. Error bounds for approximations of markov chains used in bayesian sampling. arXiv preprint arXiv:1711.05382, 2017.arxiv.org/abs/1711.05382
  23. [23]L. Kaiser, M. Babaeizadeh, P. Milos, B. Osinski, R. H. Campbell, K. Czechowski, D. Erhan, C. Finn, P. Kozakowski, S. Levine, A. Mohiuddin, R. Sepassi, G. Tucker, and H. Michalewski. Model-based reinforcement learning for atari. In International Conference on Learning Representations, 2020.
  24. [24]T. Kozuno, Y. Tang, M. Rowland, R. Munos, S. Kapturowski, W. Dabney, M. Valko, and D. Abel. Revisiting peng’s q (λ) for modern reinforcement learning. In International Conference on Machine Learning, pages 5794–5804. PMLR, 2021.arxiv.org/abs/2103.00107
  25. [25]H. Lee, D. Hwang, D. Kim, H. Kim, J. J. Tai, K. Subramanian, P. R. Wurman, J. Choo, P. Stone, and T. Seno. Simba: Simplicity bias for scaling up parameters in deep reinforcement learning. In International Conference on Learning Representations, 2025. URL https://proceedings.iclr.cc/paper_files/paper/2025/hash/741aab8b41a2987867acc9939ad50383-Abstract-Conference.html.arxiv.org/abs/2410.09754
  26. [26]D. A. Levin and Y. Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
  27. [27]T. Lindvall. Lectures on the Coupling Method. Wiley, New York, 1992.
  28. [28]A. R. Mahmood, H. Yu, and R. S. Sutton. Multi-step off-policy learning without importance sampling ratios. arXiv preprint arXiv:1702.03006, 2017.arxiv.org/abs/1702.03006
  29. [29]S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
  30. [30]A. Y. Mitrophanov. Sensitivity and convergence of uniformly ergodic markov chains. Journal of Applied Probability, 42(4):1003–1014, 2005.DOI
  31. [31]R. Munos, T. Stepleton, A. Harutyunyan, and M. G. Bellemare. Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems, volume 29, 2016.arxiv.org/abs/1606.02647
  32. [32]G. Neu and J. Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. Advances in Neural Information Processing Systems, 34:10407–10417, 2021.arxiv.org/abs/2007.01612
  33. [33]S. Park, K. Frans, B. Eysenbach, and S. Levine. OGBench: Benchmarking offline goal-conditioned RL. In International Conference on Learning Representations, 2025. arXiv:2410.20092.arxiv.org/abs/2410.20092
  34. [34]D. Precup, R. S. Sutton, and S. Dasgupta. Off-policy temporal-difference learning with function approximation. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 417–424. Morgan Kaufmann, 2001.
  35. [35]M. Rowland, W. Dabney, and R. Munos. Adaptive trade-offs in off-policy learning. In International Conference on Artificial Intelligence and Statistics, pages 34–44. PMLR, 2020.arxiv.org/abs/1910.07478
  36. [36]M. Schlegel, W. Chung, D. Graves, J. Qian, and M. White. Importance resampling for off-policy prediction. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1906.04328
  37. [37]M. Schwarzer, J. S. Obando Ceron, A. Courville, M. G. Bellemare, R. Agarwal, and P. S. Castro. Bigger, better, faster: Human-level Atari with human-level efficiency. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of the Machine Learning Research, pages 30365–30380, 2023. URL https://proceedings.mlr.press/v202/schwarzer23a.html.arxiv.org/abs/2305.19452
  38. [38]E. Solan and N. Vieille. Perturbed markov chains. Journal of applied probability, 40(1): 107–122, 2003.DOI
  39. [39]W. A. Suttle, A. Bedi, B. Patel, B. M. Sadler, A. Koppel, and D. Manocha. Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level monte carlo actor-critic. In International Conference on Machine Learning, pages 33240–33267. PMLR, 2023.arxiv.org/abs/2301.12083
  40. [40]R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
  41. [41]R. S. Sutton, D. Precup, and S. Singh. Intra-option learning about temporally abstract actions. In Proceedings of the Fifteenth International Conference on Machine Learning, pages 556–564. Morgan Kaufmann, 1998.
  42. [42]Y. Tassa, Y. Doron, A. Muldal, T. Erez, Y. Li, D. de Las Casas, D. Budden, A. Abdolmaleki, J. Merel, A. Lefrancq, T. Lillicrap, and M. Riedmiller. Deepmind control suite, 2018.arxiv.org/abs/1801.00690
  43. [43]E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026–5033. IEEE, 2012.DOI
  44. [44]H. van Hasselt. Double q-learning. Advances in Neural Information Processing Systems, 23, 2010.
  45. [45]C.-Y. Wei, M. J. Jahromi, H. Luo, and R. Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007–3015. PMLR, 2021.arxiv.org/abs/2007.11849
  46. [46]G. Wolfer and A. Kontorovich. Estimating the mixing time of ergodic markov chains. In Conference on Learning Theory, pages 3120–3159. PMLR, 2019.arxiv.org/abs/1902.01224
  47. [47]D. Yarats, I. Kostrikov, and R. Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. In International Conference on Learning Representations, 2021.

Paper details

vlnc:W_e3vxuh5z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents