Safe and Efficient Off-Policy Reinforcement Learning

Abstract

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) low variance; (2) safety, as it safely uses samples collected from any behaviour policy, whatever its degree of "off-policyness"; and (3) efficiency, as it makes the best use of samples collected from near on-policy behaviour policies. We analyse the contractive nature of the related operator under both off-policy policy evaluation and control settings and derive online sample-based algorithms. To our knowledge, 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 still an open problem. We illustrate the benefits of Retrace(λ) on a standard suite of Atari 2600 games.

Notes

In reinformcement learning, Q-learning is a technique that is commonly used. In it, a Q-function is defined which returns the discounted expected value for each state. The Q-function is updated with each iteration:

where $r_{t+1}$ is the reward observed after performing $a_t$ in $s_t$, and where $\alpha_t(s, a) \in (0, 1]$ is the learning rate.

In reinforcement learning, there is a trade-off in the definition of the update target: should one estimate Monte Carlo returns or bootstrap from an existing Q-function? Return-based methods are better behaved when combined with function approximation, and quickly respond to exploration, but bootstrap methods are easier to apply to off-policy data.

An off-policy learner learns the value of the optimal policy independently of the agent's actions. An on-policy learner learns the value of the policy being carried out by the agent. This paper shows that learning from returns can be consistent with off-policy learning.