A Fast and Reliable Policy Improvement Algorithm

Yasin Abbasi-Yadkori, Peter L. Bartlett, Stephen J. WrightAISTATS 2016 · OpenReview

Abstract: We introduce a simple, efficient method that improves stochastic policies for Markov decision processes. The computational complexity is the same as that of the value estimation problem. We prove that when the value estimation error is small, this method gives an improvement in performance that increases with certain variance properties of the initial policy and transition dynamics. Performance in numerical experiments compares favorably with previous policy improvement algorithms.

Introduction

In Reinforcement Learning (RL), the goal is to find a policy that maximizes cumulative rewards within a Markov Decision Process (MDP). While standard Approximate Policy Iteration (API) methods offer speed, they are often unstable; small errors in value estimation can lead to policy degradation or oscillation. To mitigate this, Conservative Policy Iteration (CPI) was developed to guarantee monotonic improvement by taking small, global steps toward a target policy. However, CPI's reliance on a single, global step size often results in prohibitively slow convergence, as the entire update is limited by the most "difficult" state in the system.

Linearized Policy Improvement (LPI)

This paper introduces the Linearized Policy Improvement (LPI) algorithm, which offers a more aggressive yet theoretically sound approach. Unlike CPI, LPI utilizes state-dependent update coefficients, allowing the algorithm to vary its "aggressiveness" across the state space.

Core Mechanisms

  • State-Dependent Updates: LPI reshapes the policy based on the specific variance of $Q$-values (state-action values) at each state. This allows the agent to "sprint" in states where the optimal action is clear and "tread carefully" where value estimates are uncertain.
  • The Scaling Factor ($s$): A parameter $s$ controls the trust placed in the new policy. While larger values of $s$ accelerate improvement, they must be managed to avoid mathematically invalid "negative probabilities."
  • Adaptive Iterative LPI (AILPI): To automate parameter selection, the authors proposed AILPI. This variant begins with an aggressive step size and adaptively shrinks it only when encountering states that would violate probability constraints.

Theoretical Foundation: Exploiting Variance

The mathematical advantage of LPI lies in the distinction between the "expectation of quadratics" and the "quadratic of an expectation." The authors demonstrate that while CPI’s improvement is proportional to the square of an average, LPI’s improvement is proportional to the average of the squares. By Jensen’s Inequality, the latter is almost always larger, providing a theoretical basis for LPI's superior speed.

Empirical Results

The algorithm was evaluated on standard benchmarks, including Chain Walk environments and the Inverted Pendulum task.

Figure 2: Comparison of Total Return across iterations for LPI variants versus the baseline CPI.

Key Performance Metrics

  • Speed and Convergence: On the 50-state Chain Walk, the iterative LPI (ILPI) found the optimal policy in under 10 iterations, whereas previous state-of-the-art methods required over 270. As shown in the performance plots, LPI variants significantly outperform the flat progress curve of CPI.
  • Stability: In environments known to cause oscillations in other algorithms (like the 4-state Chain Walk), ILPI remained stable and converged to the optimum.
  • Continuous Control: On the Inverted Pendulum task, the difference was most pronounced. While CPI showed negligible progress after 100 iterations, LPI achieved near-instant convergence.
Figure 6: Performance of ILPI and AILPI variants. Panel (c) highlights the rapid convergence on the Inverted Pendulum task, reaching maximum steps in just 2 iterations.

Conclusion and Future Work

LPI demonstrates that global conservatism is not a prerequisite for safety in policy improvement. By being conservative only where necessary, LPI achieves significant speedups over traditional methods. Future research directions include extending the algorithm to handle action-dependent rewards and integrating LPI with Deep Learning architectures to automate feature engineering in complex, high-dimensional state spaces.

Summary updated

Abstract

We introduce a simple, efficient method that improves stochastic policies for Markov decision processes. The computational complexity is the same as that of the value estimation problem. We prove that when the value estimation error is small, this method gives an improvement in performance that increases with certain variance properties of the initial policy and transition dynamics. Performance in numerical experiments compares favorably with previous policy improvement algorithms.
BibTeX
@inproceedings{abbasiyadkori2016fast,
  author = {Yasin Abbasi-Yadkori and Peter L. Bartlett and Stephen J. Wright},
  title = {{A Fast and Reliable Policy Improvement Algorithm}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=NCRoDrzzRep},
}
Figure