Source-linked AI summary
Safe and Efficient Off-Policy Reinforcement Learning
Rémi Munos, Tom Stepleton, Anna Harutyunyan, Marc G. Bellemare
TL;DR
Off-policy reinforcement learning needs return-based methods that remain reliable when data come from a different behavior policy. The paper unifies return-based algorithms and derives Retrace(λ), whose online control version converges without GLIE; it also proves Watkins’ Q(λ) convergence and reports Atari results.
Problem
The paper addresses off-policy policy evaluation and control, seeking Qπ or Q∗ from trajectories generated by behavior policies that may differ from the target policies.
Method
The paper expresses return-based off-policy algorithms in a common operator form and analyzes Retrace(λ), using truncated importance ratios and online sample-based updates.
Results
Retrace(λ) converges almost surely to Q∗ without the GLIE assumption, while Watkins’ Q(λ) also converges almost surely under the stated commutation condition; on Atari, Retrace(λ) was best on 30 games.
Takeaways & Limitations
Retrace(λ) automatically adjusts return length to the off-policyness of available data, combining safe off-policy use with efficient near-on-policy learning.
Takeaways & Limitations
The online control convergence result assumes asymptotic commutation of target and truncated-transition operators, along with infinite visitation, finite trajectory-length second moments, and Robbins–Monro stepsizes.
Abstract
from arXiv · showhide
In this work, we take a fresh look at some old and new algorithms for off-policy, return-based reinforcement learning. Expressing these in a common form, we derive a novel algorithm, Retrace($λ$), with three desired properties: (1) it has low variance; (2) it safely uses samples collected from any behaviour policy, whatever its degree of "off-policyness"; and (3) it is efficient as it makes the best use of samples collected from near on-policy behaviour policies. We analyze the contractive nature of the related operator under both off-policy policy evaluation and control settings and derive online sample-based algorithms. We believe this is the first return-based off-policy control algorithm converging a.s. to $Q^*$ without the GLIE assumption (Greedy in the Limit with Infinite Exploration). As a corollary, we prove the convergence of Watkins' Q($λ$), which was an open problem since 1989. We illustrate the benefits of Retrace($λ$) on a standard suite of Atari 2600 games.
1 Notation
The paper formulates reinforcement-learning environments with finite states, actions, transitions, rewards, and discounting, then defines policy values and λ-returns. These constructs support evaluating a target policy from trajectories generated by a behavior policy.
- MDP and value notation: An MDP is specified by state space X, action space A, discount factor γ ∈ [0, 1), transition function P, and bounded reward function r.The paper assumes finite action spaces for notation, while noting that Retrace(λ) also handles possibly continuous action spaces.
- MDP and value notation: A policy π maps states to action distributions, while a Q-function maps each state-action pair to a value.
- MDP and value notation: Qπ is the expected discounted reward sum obtained by following policy π from a given state-action pair.
- Bellman operators: The Bellman operator TπQ := r + γPπQ has fixed point Qπ, while the Bellman optimality operator has fixed point Q∗.The control setting seeks Q∗, the unique optimal value function.
- λ-returns: λ-return operators exponentially weight n-step returns, interpolating between the Bellman operator at λ = 0 and policy evaluation at λ = 1.At λ = 1, Qλ equals Qπ and can be estimated with Monte Carlo methods; intermediate λ values trade estimation bias against sample variance.
- Off-policy trajectories: Off-policy evaluation estimates a target policy π from trajectories generated by behavior policy µ, with on-policy learning occurring when π = µ.The trajectories contain states, actions, rewards, and transitions sampled according to µ and the MDP dynamics.
2 Off-Policy Algorithms
The paper places several return-based off-policy algorithms in a common operator framework and derives Retrace(λ) to combine variance control, arbitrary policy-discrepancy safety, and near-on-policy efficiency. Its theory establishes contraction and control-convergence guarantees, including results for Watkins’ Q(λ).
- Problem setting: The paper studies off-policy policy evaluation of Qπ and control, where policies depend on evolving Q-functions and the goal is Q∗.
- Common operator: A general return operator represents multiple algorithms through trace coefficients cs, which scale future temporal-difference information.The coefficients can depend on actions and trajectory history.
- Existing algorithms: Importance sampling corrects behavior-target mismatch with products of likelihood ratios, but its estimates can have very large or infinite variance.Using a Q-baseline turns the return operator into a variance-reduction technique.
- Existing algorithms: Qπ(λ) avoids importance-sampling variance blow-up but is safe only when behavior and target policies are sufficiently close.Its contraction conditions depend on the off-policyness level and λ, so it does not guarantee convergence for arbitrary policies.
- Existing algorithms: Tree-backup is safe for arbitrary target and behavior policies but inefficient near on-policy because it unnecessarily cuts traces and loses full returns.
- Retrace(λ): Retrace(λ) truncates importance ratios at 1, avoids variance explosion, preserves traces on-policy, and safely cuts them off-policy.The resulting operator is presented as both safe and efficient relative to the prior alternatives.
- Guarantees: For allowable trace coefficients, the return operator is a γ-contraction around Qπ for arbitrary behavior and target policies, while the control algorithm converges almost surely to Q∗ without GLIE.The paper also states almost-sure convergence of Watkins’ Q(λ) as a corollary.
3 Analysis of Retrace(λ)
The analysis proves contraction of Retrace(λ) for policy evaluation and derives control convergence under increasingly greedy policies and explicit technical assumptions. Online Retrace(λ) converges almost surely to Q∗ when visitation, trajectory-length, stepsize, and asymptotic-commutation conditions hold.
- Analysis overview: The expected return operator is analyzed as a contraction in both policy evaluation and control, with a mild additional assumption for control.
- Policy evaluation: For fixed target policy π, the analysis permits a fixed behavior policy µ and notes that the result extends to sequences of behavior policies.
- Policy evaluation: Theorem 1 gives the return operator a unique fixed point Qπ and establishes γ-contraction when trace coefficients satisfy the stated nonnegative upper bound.The proof represents the error as a nonnegative weighted combination whose total weight is at most γ.
- Policy evaluation: The contraction coefficient η(x, a) lies in [0, γ], equals γ when traces are cut immediately, and can approach zero when learning from full returns.
- Control analysis: In control, target policies form increasingly greedy sequences, including ε-greedy policies with non-increasing ε and softmax policies with non-increasing temperature.
- Control analysis: Control convergence additionally assumes Markovian traces, an initially pessimistic Bellman condition, and target policies that become increasingly greedy with errors εk → 0.The theorem allows arbitrary behavior-policy sequences under these assumptions.
- Control analysis: The proof bounds successive errors by γ∥Qk − Q∗∥ plus εk∥Qk∥, yielding Qk → Q∗ as εk → 0.
- Online algorithms: Online Retrace(λ) uses c = λ min(1, π/µ) and an every-visit update over sample trajectories.The online analysis focuses on control while noting that policy evaluation admits a similar, simpler result.
4 Discussion of the results
The analysis links convergence to admissible trace coefficients with a trade-off between estimator variance and contraction speed. Retrace(λ) balances these concerns while supporting arbitrary behaviour policies, no-GLIE control convergence, and extensions or open questions around behaviour-policy estimation and trace assumptions.
- Convergence: Trace coefficients in [0, π(a_s|x_s)/µ(a_s|x_s)] ensure convergence to Qπ and Q∗.
- Variance: Importance sampling can have unbounded variance, motivating the choice c_s ≤ 1 for numerical stability.
- Contraction speed: Contraction is faster when traces are cut less, because uncut traces can exploit full returns whereas c_1 = 0 reduces R to the one-step Bellman operator.
- Retrace(λ): Retrace(λ) offers a trade-off between low variance from small trace coefficients and faster contraction from larger coefficients.
- Control: Control convergence to Q∗ holds for arbitrary behaviour policies without the GLIE assumption, and Watkins’ Q(λ) convergence follows as a corollary under an asymptotic commutation condition.
- Further discussion: Increasingly greedy target policies may improve efficiency by cutting traces less frequently, while unresolved issues include non-Markov traces in control and technical commutation assumptions.
5 Experimental Results
The experiments evaluate Retrace(λ) with replayed sequences on 60 Atari 2600 games and find strong performance advantages over the baselines. Retrace(λ) also adapts return length to the data’s degree of off-policyness.
- Experimental setup: Retrace(λ) is evaluated in experience replay, where stored transitions may come from policies differing from the current policy.This setting directly compares algorithms under off-policy replay data.
- Experimental setup: The agent adapts DQN to replay short sequences rather than single transitions for its Q-function target updates.The target is computed from sample sequences xt, at, rt, · · ·, xt+k.
- Evaluation: The comparison covers 60 Atari 2600 games using inter-algorithm score distributions normalized separately for each game.A higher score-distribution curve generally indicates a better algorithm.
- Results: Retrace(λ) is the best performer on 30 games, while TB(λ) wins 15 of the remaining games.Both methods substantially outperform Q-Learning early and retain their advantage throughout.
- Interpretation: Retrace(λ) efficiently and safely adjusts return length according to the degree of off-policyness in available data.Its traces remain uncut near on-policy behavior and are safely shortened off-policy.
A Proof of Lemma 1
The proof introduces an error function relative to Qπ and begins by rewriting the preceding relation before deriving the needed consequence.
- Proof setup: The proof defines the error as ∆Q := Q − Qπ.
- Proof setup: It then rewrites equation (3) in terms of this error.
- Deduction: The rewritten expression is used to deduce the next proof relation.
B Increasingly greedy policies
The paper generalizes greedy policy sequences to increasingly greedy ones and proves that both decreasing-ε ε-greedy and increasing-β soft-max sequences satisfy this property.
- Greedy policies: Every sequence of policies greedy with respect to its corresponding Q-function is increasingly greedy.The result follows because the greedy Bellman operator dominates any policy operator.
- Boundary: The property does not hold for every policy sequence, including policies that choose actions minimizing Qk.
- ε-greedy policies: Non-increasing ε values ensure that εk-greedy policies form an increasingly greedy sequence.
- Soft-max policies: Non-decreasing soft-max parameters ensure that the corresponding soft-max policies form an increasingly greedy sequence.
C Proof of Theorem 2
The proof establishes contraction-style bounds for the Retrace operator by showing its auxiliary coefficients are nonnegative and row-sums are bounded by γ. These bounds support convergence toward Q*.
- Operator construction: The proof uses the Markovian nature of cs to define a sub-probability transition operator.
- Proof strategy: The proof analyzes Qk+1 − Q* by deriving separate lower and upper bounds.
- Operator bound: The auxiliary operator Ak has nonnegative elements whose row sums are at most γ.This property is established using the discounted transition operator P cµk.
- Upper bound: Consequently, Qk+1 − Q* is upper-bounded by a sub-convex combination of components of Qk − Q*.The total coefficient weight in that combination is at most γ.
- Lower bound: Increasing greediness yields a lower bound involving γPπ*(Qk − Q*) and the error term εk∥Qk∥.
- Convergence: When εk tends to zero, the sequence Qk is bounded and its limit superior equals Q*.The boundedness argument applies once εk is sufficiently small.
D Proof of Theorem 3
The proof establishes almost-sure convergence of the online control iterates to Q* by rewriting updates into a stochastic approximation form and exploiting contraction properties under asymptotic policy conditions.
- Stochastic approximation: The proof rewrites the online update in stochastic approximation form with a contraction term, centered noise, and a vanishing error term.The update is expressed as Qk+1(x, a) = (1 − αk(x, a))Qk(x, a) + αk(x, a)(RkQk(x, a) + ωk(x, a) + υk(x, a)).
- Contraction argument: The matrices Ak are γ-contraction mappings because they are non-negative and their row sums are bounded by γ.This gives Ak a common fixed point at zero for the error sequence.
- Contraction argument: Asymptotic commutation of P^πk and P^(πk∧µk) relates the potentially non-contractive Bk matrices to the contractive Ak matrices.The required commutation condition is expressed as ||P^πkP^(πk∧µk) − P^(πk∧µk)P^πk|| = o(1).
- Noise and assumptions: The proof verifies bounded-variance noise and a vanishing upper-bound condition for the additional error term under the theorem’s assumptions.The boundedness arguments rely on bounded rewards and eligibility coefficients.
- Conclusion: Qk converges almost surely to Q* after combining the derived upper and lower bounds with the stochastic approximation theorem.The same conclusion is stated for the online iterates after applying Theorem 4.
F Experimental Methods
The experiments evaluate the algorithms on 60 Atari 2600 games in a multi-threaded CPU framework, using minibatched sequences and standardized reward and target clipping.
- Evaluation setting: Sixteen threads with private environment instances train simultaneously in the multi-threaded framework.The framework was selected to obtain ample result data from affordable CPU resources.
- Evaluation setting: The experiments use 60 Atari 2600 games from the Arcade Learning Environment, treating loss of a life as episode termination.The setup uses 64 transitions per minibatch.
- Algorithms and batching: Retrace, TB, and Q* use minibatches of four 16-step sequences, while one-step Q-learning provides the control baseline.The current exploration policy is used as the target policy for the return-based algorithms.
- Optimization details: All trials clamp rewards to [−1, 1], and control Q-function targets are clamped to [−1, 1] before gradient calculation.
F.1 Algorithmic Performance in Function of λ
Performance is compared across λ values using DQN as a baseline and inter-algorithm scores averaged over games; Retrace remains consistently strong and outperforms TB.
- Performance comparison: Retrace always achieves a higher average inter-algorithm score than TB across the tested λ values.The scores use DQN as a baseline and are computed per game before averaging across games.
- Choice of λ: λ = 1 performs best across values of λ, except for Q*(λ), where λ = 0.5 is slightly superior.Q*(λ) is sensitive to λ and begins to fail above λ = 0.5.
- Performance comparison: Retrace(λ) and TB(λ) achieve dramatically higher performance than Q-Learning early and maintain their advantage throughout.
- Choice of λ: For Retrace(λ), λ = 1 is recommended at least in deterministic environments because min(1, π/µ) handles trace cutting for off-policy learning.