MINT: Meeting-time Indicators for Truncation in Multi-Step Off-Policy RL
Organizations: Seoul National University · Korea University
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.
Figures & tables
| Operator | Trace / return rule | Conservative? | Fixed point | |
|---|---|---|---|---|
| Retrace [ 31 ] | Yes | |||
| Peng’s [ 24 ] | No | |||
| Uncorrected -step | No | -dependent | ||
| MINT | No |
| Stops before cap (%) | ||
|---|---|---|
| 5 | ||
| 50 |
| RMSE | Intrinsic variance | ||||
|---|---|---|---|---|---|
| Dataset | Dynamics | MINT | Retrace | MINT | Shuffled- |
| Large–navigate | Deterministic | ||||
| Large–stitch | Deterministic | ||||
| Teleport–navigate | Stochastic | ||||
| Teleport–stitch | Stochastic | ||||
Appendix figures & tables61 assets
Supplementary material from the paper’s appendix.
Appendix
| Result | Required assumptions | Additional conditions |
|---|---|---|
| State-coupled results and chain bounds | ||
| Lemma 3.3 Variance | Adapted joint law | Bounded TD error |
| Theorem 4.1 Contraction | State coupling | in Equation 9 |
| Corollary B.1 Closed form | Cross-Doeblin; kernel TV | — |
| Lemma B.2 Disagreement | Cross-Doeblin; kernel TV | — |
| Lemma B.5 Perturbation | Kernel TV ; Assumption B.3 | Stationary laws; explicit |
| Regime | ( ) | ( ) | ||
|---|---|---|---|---|
| (A) | any | |||
| (A) | any | |||
| (B) | ||||
| (B) | ||||
| (B) | ||||
| (B) |
| measured | MINT LHS | Reference LHS | ||
|---|---|---|---|---|
| 0.20 | 0.200 | |||
| Variant | Variance | Backup MSE | ||
|---|---|---|---|---|
| Surrogate, no additional cap | ||||
| Surrogate, cap | ||||
| Surrogate, no additional cap | ||||
| Surrogate, cap |
| Method | Target or continuation rule |
|---|---|
| One-step | . |
| Uncorrected -step | . |
| Retrace | with ; use Equation 62 . |
| Peng’s | ; for ; return . |
| MINT | with , ; equivalently . |
| Hyperparameter | Value |
| Actor learning rate | |
| Critic learning rate | |
| Batch size | 100 |
| Replay buffer size | |
| Discount factor | 0.99 |
| Polyak averaging coefficient ( ) | 0.995 |
| Hyperparameter | Value |
|---|---|
| Actor learning rate | |
| Critic learning rate | |
| Entropy coefficient | (fixed; no automatic tuning) |
| Batch size | 100 |
| Replay buffer size | |
| Discount factor | 0.99 |
| Environment | Random Score | Expert Score |
|---|---|---|
| Hopper | ||
| HalfCheetah | ||
| Walker 2d | ||
| Ant | ||
| Humanoid |
| task | |||||
|---|---|---|---|---|---|
| Ant-v2 | |||||
| Hopper-v2 |
| Evaluation | Steps and seeds | Target settings | Score window |
|---|---|---|---|
| Primary eleven-task | 500K; five seeds per method/task | Cap , , automatic ; MINT | Last five evaluations; aggregate return/ |
| Supplementary five-task | 1M; three-seed table, separate five-seed curves and CartPole re-run | Cap on CartPole , elsewhere; on sparse tasks, on Hopper-Stand ; automatic , MINT | Last 100K steps (mean 10 ); raw returns |
| Task | SAC 1-step | SAC 10-step | SAC- MINT |
|---|---|---|---|
| Rare ( ; 2 tasks) | |||
| Cartpole swingup sparse | |||
| Pendulum swingup | |||
| Occasional ( – ; 4 tasks) | |||
| Finger turn easy | |||
| Finger turn hard | |||
| Task | 100K | 200K | 300K | 500K |
|---|---|---|---|---|
| Cartpole sparse | 5 | 5 | 5 | 5 |
| Pendulum | 5 | 4 (2) | 3 (2,3) | 1 (1,2,3,4) |
| Finger easy | 4 (1) | 5 | 5 | 4 (2) |
| Finger hard | 3 (0,1) | 3 (0,4) | 4 (3) | 2 (0,1,2) |
| Hopper stand | 5 | 5 | 4 (1) | 4 (1) |
| Hopper hop | 5 | 4 (1) | 4 (1) | 4 (1) |
| Task | SAC- MINT | SAC-multistep | Vanilla SAC |
|---|---|---|---|
| Discriminative | |||
| CartPole-Swingup-Sparse | |||
| Hopper-Stand | — | ||
| Finger-Turn-Easy | — | ||
| Scope (non-discriminative) | |||
| Ball-in-Cup-Catch | — | ||
| Method | Runs/game | Median | IQM | Mean | Gap |
|---|---|---|---|---|---|
| MINT ( ) | 5 | ||||
| DER | 100 | ||||
| DrQ( ) | 100 | ||||
| SPR | 100 | ||||
| EfficientZero | 3 | ||||
| BBF (author scores) | 50 |
| Metric | MINT (5 runs/game) | BBF (50 runs/game) |
|---|---|---|
| Median | ||
| IQM | ||
| Mean | ||
| Optimality Gap |
| Nominal steps | Median | IQM | Mean | Gap |
|---|---|---|---|---|
| 10K | ||||
| 50K | ||||
| 100K |
| Wins | Mean | Median | IQM | |||
|---|---|---|---|---|---|---|
| Group | /games | MINT | DrQ | MINT | DrQ | MINT |
| E/H | 7/11 | |||||
| E/X | 2/6 | |||||
| H/D | 1/7 | |||||
| H/S | 2/2 | |||||
| Group | Mean difference | Contribution to suite mean |
|---|---|---|
| Easy/human | ||
| Easy/exploit | ||
| Hard/dense | ||
| Hard/sparse | ||
| Total |
| Game | MINT return | DrQ return | MINT HNS | DrQ HNS | HNS |
|---|---|---|---|---|---|
| E/H: easy/human-optimal | |||||
| Assault | |||||
| Asterix | |||||
| BattleZone | |||||
| Boxing | |||||
| Breakout | |||||
| 5 | ||
|---|---|---|
| 50 |
| learned | |||
|---|---|---|---|
| 5 | |||
| 10 | |||
| 50 | – |
| pooled ( ) |
|---|
| return | return | |||
|---|---|---|---|---|
| 50 | — | — | ||
| 10 | ||||
| 5 |
| / age (K) | Mean | Median | Cut at 50 (%) | Censored (%) | ||
|---|---|---|---|---|---|---|
| checkpoint | matching diagnostic | |
|---|---|---|
| 29% | ||
| 57% | ||
| 71% | ||
| 100% |
| coefficients | mean | median | s.d. | |
|---|---|---|---|---|
| (deployed, Section 5 ) | ||||
| (training coefficients) | ||||
| at | mean | |||
| (effective ) | ||||
| gate: |
| Dataset | Bias: MINT | Bias: Retrace | |
|---|---|---|---|
| large-navigate (det.) | |||
| large-stitch (det.) | |||
| teleport-navigate (stoch.) | |||
| teleport-stitch (stoch.) |
| dataset | operator | median | mean s.d. | unstable seeds | |
|---|---|---|---|---|---|
| large-navigate (det.) | 1.0 | MINT | 0/5 | ||
| Retrace | 0/4 | ||||
| shuffled- | 0/5 | ||||
| teleport-navigate (stoch.) | 1.0 | MINT | 0/5 | ||
| Retrace | 0/5 | ||||
| shuffled- | 0/5 |
Temporal-Difference Learning
Temporal-difference learning estimates values by bootstrapping from later predictions, enabling online learning and control from sequential experience.
See all 93 papers