Safe and efficient off-policy reinforcement learning
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.
One fundamental trade-off in reinforcement learning lies in the definition of the update target: should one estimate Monte Carlo returns or bootstrap from an existing Q-function? Return-based methods (where return refers to the sum of discounted rewards � t γ t r t ) offer some advantages over value bootstrap methods: they are better behaved when combined with function approximation, and quickly propagate the fruits of exploration (Sutton, 1996). On the other hand, value bootstrap methods are more readily applied to off-policy data, a common use case. In this paper we show that learning from returns need not be at cross-purposes with off-policy learning.
We start from the recent work of Harutyunyan et al. (2016), who show that naive off-policy policy evaluation, without correcting for the "off-policyness" of a trajectory, still converges to the desired Q π value function provided the behavior µ and target π policies are not too far apart (the maximum allowed distance depends on the λ parameter). Their Q π (λ) algorithm learns from trajectories generated by µ simply by summing discounted off-policy corrected rewards at each time step. Unfortunately, the assumption that µ and π are close is restrictive, as well as difficult to uphold in the control case, where the target policy is greedy with respect to the current Q-function. In that sense this algorithm is not safe: it does not handle the case of arbitrary "off-policyness".
Alternatively, the Tree-backup (TB(λ)) algorithm (Precup et al., 2000) tolerates arbitrary target/behavior discrepancies by scaling information (here called traces) from future temporal differences by the product of target policy probabilities. TB(λ) is not efficient in the "near on-policy" case (similar µ and π), though, as traces may be cut prematurely, blocking learning from full returns.
In this work, we express several off-policy, return-based algorithms in a common form. From this we derive an improved algorithm, Retrace(λ), which is both safe and efficient, enjoying convergence guarantees for off-policy policy evaluation and -more importantly -for the control setting.
Retrace(λ) can learn from full returns retrieved from past policy data, as in the context of experience replay (Lin, 1993), which has returned to favour with advances in deep reinforcement learning (Mnih et al., 2015;Schaul et al., 2016). Off-policy learning is also desirable for exploration, since it allows the agent to deviate from the target policy currently under evaluation.
To the best of our knowledge, this is the first online return-based off-policy control algorithm which does not require the GLIE (Greedy in the Limit with Infinite Exploration) assumption . In addition, we provide as a corollary the first proof of convergence of Watkins' Q(λ) (see, e.g., Watkins, 1989;Sutton and Barto, 1998).
Finally, we illustrate the significance of Retrace(λ) in a deep learning setting by applying it to the suite of Atari 2600 games provided by the Arcade Learning Environment (Bellemare et al., 2013).
The paper introduces a new algorithm called Retrace(\lambda) that is meant to achieve a trade-off between efficiency and stability. In the process, it proves convergence of a large class of off-policy value function algorithms (including Q-learning with eligibility traces) in finite state spaces. The theoretical analysis is underpinned by a new general way of writing off-policy value function updates with eligibility traces (eq. 4).  Experimental results show the Retrace algorithm performing better than DQN and the tree backup algorithm on the Atari domain.  
***** UPDATE *****  I have lowered my scores for novelty and impact because I just came across the paper "High Confidence Off-Policy Evaluation" by Thomas, Theocharous and Ghavamzadeh (not referenced paper 602), which deals with some very similar issues. In particular, it bounds the performance of off-policy importance sampling as a function of a truncation coefficient, and discusses how to choose that coefficient based on the bound they propose. The lack of a discussion of the relationship to that work makes paper 602 considerably weaker in my opinion. I would still lean towards acceptance, but only as a poster.  *******************   The paper is a great starting point for a theoretical understanding of current off-policy value-based methods and for developing new ones. Analyzing the convergence of the general-form off-policy updates in Equation 4 is novel and important. The theory is limited to finite state spaces (something that should be stated in the abstract) for discounted MDPs, but the empirical results show that the new Retrace algorithm can perform well in conjunction with value function approximation. The theoretical results are sound as far as I can tell.  Retrace as the combination of truncated importance sampling and eligibility traces is a new method, however the authors should cite existing work on reducing the variance of importance sampling by truncating coefficients, e.g. "Truncated Importance Sampling" (Ionides, 2008).   The paper suffers in clarity to some extent because a lot of content is being crammed within the bounds of a conference paper. In particular, some of the theory takes a while to read through as several steps are condensed into one, and the experimental results at the end feel a bit rushed. Also at several points the text is begging for more discussion (e.g. about the asymptotic commutativity assumption vs GLIE, or why limit the upper bound for c_s at 1 as opposed to some other value). Perhaps a good solution would be for the paper to only include the theory and discussion, and to reference an extended version containing a more in-depth examination of the experimental results - my feeling is that a few years down the road the theory in this paper will be of a lot more interest than the experiments.  Several comments regarding clarity (some of them minor): - in the equation above line 62, the operator definition is missing something (it becomes equal to zero when lambda=1) - line 131: i would say that it is more obvious that Q^\pi is the fixed point from Lemma 1 than from Equation 4 - typo in lines 219-220 - the equation after line 262 doesn't look like a Q-function target, but rather as part of a gradient update - line 270: Figure 1 does not show that Q* diverges for lambda=1