Beyond the One Step Greedy Approach in Reinforcement Learning

Abstract

The famous Policy Iteration algorithm alternates between policy improvement and policy evaluation. Implementations of this algorithm with several variants of the latter evaluation stage, e.g, $n$-step and trace-based returns, have been analyzed in previous works. However, the case of multiple-step lookahead policy improvement, despite the recent increase in empirical evidence of its strength, has to our knowledge not been carefully analyzed yet. In this work, we introduce the first such analysis. Namely, we formulate variants of multiple-step policy improvement, derive new algorithms using these definitions and prove their convergence. Moreover, we show that recent prominent Reinforcement Learning algorithms are, in fact, instances of our framework. We thus shed light on their empirical success and give a recipe for deriving new algorithms for future study.

arXiv commentICML 2018

References in corpus (6)

• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• On-line Policy Improvement using Monte-Carlo Search
• How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies
• Performance Bounds for Lambda Policy Iteration and Application to the Game of Tetris
• Lambda-Policy Iteration: A Review and a New Implementation

Cited by in corpus (5)

• Heuristic-Guided Reinforcement Learning
• Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning
• Reward Tweaking: Maximizing the Total Reward While Planning for Short Horizons
• Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods
• Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction