PID Accelerated Value Iteration Algorithm

Amir Massoud Farahmand, Mohammad GhavamzadehICML 2021 · OpenReview

TL;DR

This paper introduces PID Accelerated Value Iteration, a novel approach that treats the classic Value Iteration (VI) algorithm as a dynamical system. By applying Proportional-Integral-Derivative (PID) control techniques, the authors significantly speed up convergence in Markov Decision Processes (MDPs), especially when the discount factor is close to one.

The Problem with Value Iteration

Value Iteration (VI) is a cornerstone of dynamic programming and reinforcement learning. It works by repeatedly applying a Bellman operator to estimate the value of states. However, VI has a notorious "speed limit": its convergence rate is strictly tied to the discount factor $\gamma$.

When $\gamma$ is close to 1 (meaning the agent cares deeply about long-term rewards), VI becomes painfully slow, converging at a rate of $O(\gamma^k)$. In many real-world problems, we want $\gamma$ to be high to capture long-term dependencies, but this makes the computation expensive. The authors set out to break this bottleneck by looking at VI through the lens of control theory.

Methodology: VI as a Dynamical System

The core innovation is viewing the sequence of value function approximations $(V_k)$ as the state of a dynamical system. In this view, standard VI is just a simple "Proportional" (P) controller with a gain of 1.

The authors propose three accelerated variants:

  1. PD-VI (Proportional-Derivative): Adds a "momentum" term based on the difference between the current and previous value functions ($V_k - V_{k-1}$). This extrapolates the trend of the updates to reach the fixed point faster.
  2. PI-VI (Proportional-Integral): Introduces an "integrator" state that accumulates past Bellman residuals. This helps the algorithm "remember" the direction of previous errors to correct the current trajectory.
  3. PID-VI: Combines both derivative and integral terms for maximum flexibility.

Crucially, because the optimal gains for these controllers depend on the specific MDP (which we usually don't know upfront), the authors developed a Gain Adaptation mechanism. This algorithm automatically tunes the PID parameters during the iteration process by performing gradient descent on a normalized Bellman error loss function.

Experimental Setup

The researchers evaluated their algorithms on two main types of environments:

  • Chain Walk (50 states): A standard benchmark where an agent moves along a line. It’s simple enough for deep analysis but complex enough to show the limitations of standard VI.
  • Garnet Problems: These are "Generic Average Reward Non-stationary Environments," essentially randomly generated MDPs. They serve as a stress test to ensure the acceleration isn't just a fluke of one specific environment design.

Key Insights and Results

Realizing that $V_{k+1} = T V_k$ is a linear dynamical system (in the policy evaluation case) allows us to use decades of control theory to manipulate its "eigenvalues." By shifting these eigenvalues, we can make the system reach its equilibrium (the true value function) much faster.

The results show that PID acceleration isn't just a marginal improvement—it can be a game-changer.

Orders of Magnitude Speedup: In the Chain Walk environment, the PI-VI variant reached an error level of $10^{-7}$ in the same time it took standard VI to reach only $10^{-3}$ during policy evaluation.

Convergence behavior of different PID variants for Policy Evaluation. Note how the PI and PID versions drop much faster than standard VI.

This acceleration is not limited to just evaluating a fixed policy. It extends powerfully to the full control setting (finding the optimal policy), where the PID variants continue to significantly outperform the conventional approach.

Convergence behavior of different PID variants for the Control setting, demonstrating robust acceleration when finding the optimal policy.

The Power of the Integral: While "momentum" (the D-term) is common in optimization, the "Integral" term is less common in RL. The paper shows that for policy evaluation, the PI variant can be incredibly potent, sometimes outperforming PD.

Robustness via Adaptation: The gain adaptation mechanism successfully found effective parameters across a wide range of random Garnet MDPs, proving that you don't need to be a control theory expert to use these tools. To prevent the learning rate for the gains from shrinking to zero as the Bellman error naturally shrinks, the authors successfully utilized a normalized loss function.

Limitations and Future Work

While the results are promising, there are a few hurdles to clear before this becomes a standard tool in every RL library:

  • Theoretical Scope: Much of the formal convergence analysis is currently limited to finite state spaces and linear operators (policy evaluation). Extending the full proof of stability to the non-linear "Control" case is more complex.
  • Sample-Based RL: The paper focuses on the "planning" setting where the MDP model is known. The authors suggest that extending this to "model-free" RL (where we only have samples) is feasible, but they haven't demonstrated it at scale yet.
  • Hyper-parameters: Although gain adaptation helps, it introduces its own "meta-learning" rate ($\eta$). Finding a truly "tuning-free" version remains an open challenge.

In summary, this work provides a beautiful bridge between two fields, showing that the "old" wisdom of PID control can still teach "new" tricks to modern reinforcement learning algorithms.

Summary updated

Abstract

The convergence rate of Value Iteration (VI), a fundamental procedure in dynamic programming and reinforcement learning, for solving MDPs can be slow when the discount factor is close to one. We pr...
BibTeX
@inproceedings{farahmand2021pid,
  author = {Amir Massoud Farahmand and Mohammad Ghavamzadeh},
  title = {{PID Accelerated Value Iteration Algorithm}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=fLsTJ1Bxsgs},
}
Figure