Greedy-Step Off-Policy Reinforcement Learning
This addresses a key bottleneck in reinforcement learning for researchers and practitioners by enabling reliable, efficient off-policy learning without correction, though it appears incremental as it builds on existing value iteration frameworks.
The paper tackles the challenge of multi-step bootstrapping in off-policy reinforcement learning, which often suffers from high variance in policy iteration methods, and introduces a novel multi-step Bellman Optimality Equation that leads to algorithms achieving state-of-the-art performance on standard benchmarks with exponential contraction rates and linear computational complexity.
Most of the policy evaluation algorithms are based on the theories of Bellman Expectation and Optimality Equation, which derive two popular approaches - Policy Iteration (PI) and Value Iteration (VI). However, multi-step bootstrapping is often at cross-purposes with and off-policy learning in PI-based methods due to the large variance of multi-step off-policy correction. In contrast, VI-based methods are naturally off-policy but subject to one-step learning.In this paper, we deduce a novel multi-step Bellman Optimality Equation by utilizing a latent structure of multi-step bootstrapping with the optimal value function. Via this new equation, we derive a new multi-step value iteration method that converges to the optimal value function with exponential contraction rate $\mathcal{O}(γ^n)$ but only linear computational complexity. Moreover, it can naturally derive a suite of multi-step off-policy algorithms that can safely utilize data collected by arbitrary policies without correction.Experiments reveal that the proposed methods are reliable, easy to implement and achieve state-of-the-art performance on a series of standard benchmark datasets.