TL;DR
This paper introduces excursion policies, a novel framework for off-policy reinforcement learning that interpolates between behavior and target policies by following the target policy for multi-step "excursions." Unlike standard mixture policies that switch at every step, excursion policies provide a more structured approach that improves stability and efficiency, particularly in environments where coherent action sequences are critical.
What Problem Does This Paper Address?
Off-policy reinforcement learning (RL)—learning about a "target" policy while following a different "behavior" policy—is a cornerstone of modern RL, enabling the use of historical data and exploration. However, it faces a fundamental challenge: the bias-variance-stability trade-off.
Standard importance-sampling corrections often suffer from explosive variance. Conversely, techniques that clip these ratios to maintain stability can introduce significant bias and shorten the "bootstrapping horizon," making the agent more vulnerable to the "deadly triad" (the instability arising from combining off-policy learning, function approximation, and bootstrapping).
Existing methods often use mixture policies, which randomly choose between the behavior and target policy at every single time step. While effective, this "uniform spreading" of deviations can be suboptimal for tasks where switching policies frequently is costly or where a sequence of coherent actions is required to achieve a goal.
Methods
The authors propose excursion policies as a structured alternative. Instead of switching at every step, the agent follows the target policy for a multi-step "excursion" before reverting to the behavior policy.
- Formalization: They define these policies on an augmented state space using a latent variable $Z_t \in \{0, 1\}$, where $Z_t=1$ indicates the agent is currently in an excursion (following the target policy $\pi$) and $Z_t=0$ indicates it has reverted to the behavior policy $\mu$.
- One-time Excursions: The simplest case where an excursion starts, continues with probability $\beta$, and once it ends, the agent stays with the behavior policy indefinitely.
- General Excursions: A more flexible version that allows for multiple excursions, controlled by a persistence parameter $\lambda$.
- Algorithms: The paper derives new Temporal-Difference (TD) algorithms:
- Ex-TD($\lambda, \beta$): A theoretically sound estimator for excursion values.
- Ex-trace($\lambda, \beta$): A variance-reduced version that clips importance ratios, analogous to the popular V-trace algorithm.
- Ex-Retrace: An action-value counterpart designed for control settings.
Datasets
The researchers evaluated their approach across three distinct settings:
- Didactic MDPs: A custom "Highway MDP" designed to highlight the conceptual differences between excursions and mixtures.
- Randomly Generated MDPs: Used for a rigorous spectral analysis of the contraction-bias-variance trade-offs.
- DeepMind Control Suite (dm_control): High-dimensional continuous control benchmarks, specifically focusing on the most challenging "dog" and "humanoid" tasks to test the algorithms under function approximation.
Key Insights and Ideas
-
Temporal Clustering vs. Uniform Spreading: The core conceptual difference is how deviations from the behavior policy are distributed. Mixture policies spread them out evenly, while excursion policies cluster them into coherent blocks. Discounted deviation equivalence: An example of discounted timelines for a random mixture and a random excursion.
-
Coherence Matters: In the Highway MDP example, switching lanes incurs a penalty. A mixture policy oscillates frequently between lanes, racking up costs. An excursion policy switches once and stays, potentially achieving a higher value than either the pure behavior or target policies. Analysis of the Highway MDP example.
-
Theoretical Soundness: The authors prove that the Bellman operator for excursion policies is a contraction mapping. This provides a solid theoretical foundation, ensuring that their TD algorithms will converge to a unique fixed point in tabular settings.
- Pareto Efficiency: Spectral analysis shows that Ex-Retrace often occupies a more favorable region of the bias-contraction trade-off compared to mixture policies ($\alpha$-Retrace) or simple $n$-step returns.
Key Results
- Efficiency-Stability Trade-off: In continuous control experiments, Ex-Retrace with intermediate values of $\beta$ (the excursion continuation probability) significantly outperformed both pure Retrace (which was often unstable) and uncorrected TD (which was stable but learned very slowly).
- Robustness to Off-policyness: As the data becomes more "off-policy" (measured by the Samples-Per-Insert ratio), the benefits of the excursion-based interpolation become more pronounced, providing a smooth bridge between stability and performance.
- Comparable Performance: While conceptually distinct, excursion policies achieve an empirical efficiency-stability trade-off comparable to mixture policies on standard benchmarks, suggesting they are a viable and sometimes superior alternative for off-policy learning.
Limitations and Future Work
- Hyperparameter Tuning: Like mixture policies, excursion policies introduce a new parameter ($\beta$) that requires tuning. The authors suggest future work could involve adapting $\beta$ online via meta-gradients.
- Identifying "Excursion-Friendly" Tasks: While the Highway example is intuitive, standard benchmarks like
dm_controldon't always penalize policy switching explicitly. Finding real-world tasks where temporally extended excursions offer a clear win is an open area of research. - Theoretical Extensions: The current policy iteration guarantees are limited to one-time excursions ($\lambda=1$). Extending these proofs to the general case ($\lambda \in (0, 1)$) remains a theoretical challenge.
- Deep RL Gap: The theoretical analysis is primarily tabular, while the most impactful applications are in deep RL. Bridging this gap with instance-dependent convergence guarantees under function approximation is a priority for future study.
Summary updated