Off-policy Learning with Excursion Policies

AI summary

Overview

• Research area: Reinforcement learning, specifically off-policy temporal-difference (TD) learning and value estimation under a behavior/target policy mismatch.
• Technical level: Advanced. The paper builds on Bellman operators, importance-sampling corrections, contraction-mapping arguments, and eligibility traces; readers need prior familiarity with off-policy TD(λ), Retrace, V-trace, and α-trace.
• Scope (one sentence): The paper introduces "excursion policies" — a family of interpolating policies that follow the target policy for a multi-step excursion before reverting (possibly reversibly) to the behavior policy — and provides dynamic-programming theory, provably convergent off-policy TD algorithms, and an empirical comparison against mixture policies on continuous control benchmarks.

What This Paper Is About

Off-policy RL wants the value of a target policy π while data comes from a different behavior policy μ, and the standard corrections (importance sampling) trade bias against variance and stability. Most existing work smooths this trade-off by interpolating per step between μ and π, as in mixture policies. This paper proposes an alternative interpolation mechanism: instead of switching randomly at every step, the agent takes a contiguous multi-step "excursion" into π and then falls back to μ, and the paper asks whether this structured alternative is theoretically sound and empirically useful.

Key Contributions

1. A new family of excursion policies. The paper defines one-time excursion policies π→^β (the latent mode Z_t stays in the target policy with probability β each step and, once it exits, is absorbed in the behavior policy) and general excursion policies π→^(β,λ), where a behavior-persistence probability λ controls how readily new excursions begin. The authors show this family contains one-time excursions (λ = 1), mixture policies (λ = 0, with α = β), and repeated excursions (λ ∈ (0,1)).

2. Dynamic-programming foundations. Theorems establish that the excursion Bellman operator 𝒯^(β,λ)_{π→μ} ≐ β𝒯_π + (1−β)𝒯_μ^λ is an ℓ∞-contraction with a unique fixed point equal to the excursion value (Theorem 3.5), plus policy-improvement and policy-iteration results for the one-time case (Theorems 3.6 and 3.7) guaranteeing monotone improvement.

3. Provably sound off-policy TD algorithms. The paper derives Ex-TD(λ, β), whose weighting C_{t:k} = (1−β) + β ρ_t C_{t+1:k} has v_{π→^(β,λ)} as its fixed point, and Ex-trace(λ, β), which clips importance ratios as ρ̂_t = min{ρ̄, ρ_t}. Theorem 4.3 proves Ex-trace's operator is an η^β-contraction in sup-norm.

4. A principled way to compare interpolation schemes. The discounted deviation count (DDC), n_π ≐ E[Σ_t γ^t U_t], gives an explicit mapping between mixture and excursion parameters, α = β(1−γλ)/(1−βγλ), that equalizes the discount-weighted number of target-policy steps.

Main Findings

• Excursion and mixture policies are conceptually distinct, not just differently parameterized. In the Highway MDP example (slow lane reward 0.01 with destination T_A; fast lane reward 1.0 with terminal penalty −15.0 at T_B; γ = 0.9; an extended 10-state chain; switching costs c = 0 and c = −1.0), the mixture policy oscillates between lanes repeatedly, while the one-time excursion policy switches at most once. With a lane-switching penalty, the excursion policy can achieve a higher initial-state value than both μ and π; the paper notes the reverse ordering is also constructible.

• Matched DDCs hide a timing difference. With α = 0.5, λ = 1, γ = 0.9, the DDC-matched excursion parameter is β = 10/11 ≈ 0.91. The mixture policy spends on average two undiscounted steps in the target policy before switching (since 1/(1−α) = 2) and keeps alternating; the excursion policy spends on average 10 steps in the target policy from the start (β/(1−β) = 10) and never returns after switching. Both give 5 discount-weighted target steps in expectation, but the excursion takes them all up front.

• Ex-TD and Ex-trace interpolate known algorithms. With β = 0, Ex-TD's weights collapse to C_{t:k} = 1 (Uncorrected TD, estimating v_μ); with β = 1, they become full importance sampling ρ_{t:k} (Off-policy TD, estimating v_π); intermediate β estimates v_{π→^(β,λ)}. Likewise, Ex-trace interpolates between Uncorrected TD and V-trace.

• Convergence is guaranteed for the clipped variant only. Table 1 classifies Uncorrected TD(λ), V-trace(λ) and α-trace(λ) as convergence-guaranteed, and Off-policy TD(λ), α-TD(λ) and Ex-TD(λ, β) as not guaranteed; Ex-trace(λ, β) is guaranteed, converging to v_{π→^(β,λ)_{ρ̄}} (characterized in Appendix C). Assumption 4.2 (E_μ[ρ̂_0 | S_0 = s] ≥ κ > 0) ensures coverage; without it, contraction still holds for β ∈ [0,1).

• Contraction bounds mirror the DDC mapping. Theorem 4.3 gives η^β ≤ 1 − (1−γ)(1−β)/(1−γλ), and with Assumption 4.2 a tighter bound; the α-trace bound is η^α ≤ 1 − (1−γ)(1−α)/(1−γλ(1−α)). As β and α decrease from 1, the β-bound decays faster, and solving for equal bounds reproduces Equation 10 exactly — suggesting the worst-case contraction rate is governed by total discounted deviation from μ, whether produced by mixing or excursions. At β = 1 the bound matches V-trace's result from Espeholt et al. (2018).

• In spectral analysis on random MDPs, Ex-Retrace occupies a distinct region of the trade-off. Compared against α-Retrace (the action-value analogue of α-trace), n-step, and corrected n-step, Ex-Retrace's contraction rate decreases faster as its parameter decreases, giving a better bias–contraction trade-off; both Ex-Retrace and α-Retrace generally showed lower variance than n-step and corrected n-step. Across additional random MDPs and off-policyness levels (Section F.1), Ex-Retrace was Pareto efficient more often than α-Retrace and n-step in the contraction–bias trade-off.

• Continuous control shows a comparable, smooth trade-off. In dm_control on four dog and three humanoid tasks (three seeds per task, aggregated across tasks), MPO with Ex-Retrace and with α-Retrace both provided an efficiency–stability trade-off comparable to mixture policies; the paper frames the difference as conceptual rather than a clear win. The visible content truncates the α sweep list after 0.0 and 0.2, so the full sweep is not reported here.

Methodology in Plain English

The authors take the idea of "excursions" from earlier off-policy work — moments when the agent temporarily behaves like the target policy — and make the excursion length random rather than fixed or terminal-only. They add a hidden switch that says whether the agent is currently in the target mode; the switch stays on with probability β each step, and a second parameter λ controls how likely it is to turn back on once it has turned off. Setting λ = 1 gives a single excursion that ends forever; setting λ = 0 recovers the familiar per-step mixture policy.

They then treat the value of this switch-augmented policy as an ordinary value-estimation problem, writing down the Bellman operator and proving it shrinks distances between value estimates (so its fixed point is unique and reachable). From that operator they read off the importance-weighting that a TD update should use, and they check that the weighting interpolates smoothly between "no correction" and "full correction." Because full correction has unbounded variance, they also clip the importance ratios and prove the clipped version's operator is still a contraction, then argue convergence of the online algorithm.

To compare with mixture policies fairly, they define a yardstick — the expected, discount-weighted number of steps spent in the target policy — and derive the α-to-β conversion that equalizes it. Finally, they test the action-value version (Ex-Retrace) two ways: a small-scale spectral analysis on randomly generated MDPs that measures fixed-point bias, variance, and contraction rate, and a full off-policy control benchmark in dm_control using MPO as the base agent, with targets computed over truncated 20-step trajectories and λ = 1.

Why This Matters

Impact on research. The paper widens the design space of off-policy corrections beyond per-step mixing. It gives the mixture-vs-excursion comparison a common currency (the discounted deviation count) and shows that the contraction-rate bounds coincide under that currency while the actual policies can differ sharply. It also connects excursion policies to options: if μ is the agent's behavior and π is an option's policy, π→^β describes executing that option with constant termination probability, so the TD algorithms here may be useful for off-policy option evaluation where mixture-policy algorithms are less natural.

Real-world applications (illustrative, from the paper's framing):

• Settings where data collection is expensive and reuse of logged data is essential.
• Learning from data generated by past or exploratory policies, as in distributed actors feeding a learner.
• Domains requiring coherent sequences of actions rather than step-by-step oscillation — the paper's driving example penalizes repeated lane switching.
• Temporally extended behaviors or options that must be evaluated off-policy.

Industry relevance. Distributed training pipelines with one learner and several actors (the paradigm used in the experiments) are standard in production RL, and any interpolation knob that stabilizes learning from stale or off-policy data is directly useful. The single scalar β adds a tunable dial for how aggressively to trust target-policy corrections without abandoning the stability of the behavior policy.

Future Directions

1. Extending policy iteration to general λ. Theorems 3.6 and 3.7 are limited to λ = 1; the paper states that extending monotone improvement to λ ∈ (0,1) is not trivial (see Proposition C.2) and remains an open problem.
2. Theory beyond the tabular case. The convergence analysis is tabular; the control experiments only test empirically whether excursion policies help under function approximation.
3. Characterizing the clipped fixed point. The fixed point v_{π→^(β,λ)_{ρ̄}} of Ex-trace is only characterized in Appendix C, leaving open how clipping distorts excursion values in practice.
4. Where excursions beat mixtures in control. The benchmark results show a comparable trade-off rather than a dominant one, so identifying task structures (long coherent action sequences, costly switching) where excursions clearly win is a natural next step.

Target Audience

RL researchers and graduate students working on off-policy evaluation and TD learning who already know importance sampling, Retrace/V-trace, and Bellman-operator arguments; practitioners implementing distributed actor–learner systems (for example, MPO-style agents) who want a principled, tunable alternative to α-trace-style mixing; and anyone interested in temporally extended action or option evaluation.

Authors’ abstract

Off-policy reinforcement learning (RL) tries to learn the value of a target policy while data comes from a different behavior policy. This often requires trading off bias for variance or stability. One way to trade these off is to linearly interpolate between the behavior and target policies, but this represents only one point in a broader space of interpolation mechanisms. We introduce excursion policies--a structured alternative where the agent follows the target policy…