Operator Splitting Value Iteration

Amin Rakhsha, Andrew Wang, Mohammad Ghavamzadeh, Amir-massoud Farahmand

Abstract

We introduce new planning and reinforcement learning algorithms for discounted MDPs that utilize an approximate model of the environment to accelerate the convergence of the value function. Inspired by the splitting approach in numerical linear algebra, we introduce Operator Splitting Value Iteration (OS-VI) for both Policy Evaluation and Control problems. OS-VI achieves a much faster convergence rate when the model is accurate enough. We also introduce a sample-based version of the algorithm called OS-Dyna. Unlike the traditional Dyna architecture, OS-Dyna still converges to the correct value function in presence of model approximation error.

Introduction

In Reinforcement Learning (RL), Value Iteration (VI) is a foundational algorithm used to determine optimal policies. However, VI is notoriously slow when the discount factor ($\gamma$) is close to 1, as the agent must account for long-term rewards over many iterations. This results in a convergence rate of $O(\gamma^k)$, which often requires a prohibitive number of interactions with the environment.

To address this, researchers frequently turn to Model-Based RL, such as the Dyna architecture, which learns a simulator of the environment to speed up learning. The primary drawback of these methods is model bias: if the learned model is inaccurate, the agent converges to a biased, incorrect solution. This paper introduces Operator Splitting Value Iteration (OS-VI), a new class of algorithms that utilizes an approximate model to accelerate computation while maintaining a mathematical guarantee to find the true value function.

Methodology

The authors draw inspiration from numerical linear algebra, specifically matrix splitting techniques used to solve large-scale systems of equations. By treating the Bellman equation as a linear system, they "split" the operator into two distinct parts: one based on an approximate, computationally cheap model $\hat{\mathcal{P}}$, and a correction term based on the true model $\mathcal{P}$.

OS-VI (The Planning Version)

In the planning setting, the algorithm iteratively solves an auxiliary MDP based on the approximate model. This process creates the Varga operator, which effectively pre-conditions the problem. If the approximate model is accurate, the convergence rate is governed by a new "effective" discount factor $\gamma'$ that can be significantly smaller than the original $\gamma$.

OS-Dyna (The RL Version)

Since the true model is rarely known in RL, the authors propose OS-Dyna, a sample-based version of the algorithm. Unlike standard Dyna, which uses a model to replace the real world, OS-Dyna uses the model to pre-condition the learning process. It utilizes real-world samples to estimate a "correction reward" that offsets any errors in the approximate model, ensuring the agent is constantly steered back toward the ground truth.

Experimental Evaluation

The algorithms were evaluated on several benchmarks, including a 2-State MDP, a 6x6 Modified Cliffwalk gridworld, Random MDPs (Garnet), and a 3x3 Maze. These environments tested the algorithms' ability to handle model inaccuracies and dangerous states.

Key Results

  • Exponential Speedup: In the Cliffwalk and Maze environments, OS-VI reached the optimal value function in significantly fewer iterations than standard VI. In cases where VI required over 20 iterations, OS-VI often converged in fewer than 5 iterations given a reasonably accurate model.
  • Unbiased Learning: In RL experiments, OS-Dyna outperformed both Q-learning and standard Dyna. While Q-learning was slow and standard Dyna converged to biased solutions, OS-Dyna achieved fast convergence to the correct value function.
  • Theoretical Guarantees: The authors provide a rigorous proof showing that OS-VI is guaranteed to be faster than standard VI as long as the model error remains below a specific threshold: $\| \mathcal{P} - \hat{\mathcal{P}} \|_\infty < 1 - \gamma$.

Discussion and Future Work

OS-VI represents a significant bridge between 70-year-old linear solver theory (such as Jacobi and Gauss-Seidel iterations) and modern Markov Decision Processes. The most striking insight is the reduction of the effective discount factor; a good model can make a long-horizon problem behave like a short-horizon one.

However, the method is not without limitations. Each "outer" iteration of OS-VI requires solving an "inner" MDP using the approximate model, which is only beneficial if the approximate model is much cheaper to solve than the real environment. Furthermore, while the algorithm is robust to bias, a very poor model can potentially slow down convergence or cause divergence. Future work will focus on scaling these principles to Deep RL and high-dimensional state spaces using function approximation.

Summary updated

Abstract

We introduce new planning and reinforcement learning algorithms for discounted MDPs that utilize an approximate model of the environment to accelerate the convergence of the value function. Inspired by the splitting approach in numerical linear algebra, we introduce Operator Splitting Value Iteration (OS-VI) for both Policy Evaluation and Control problems. OS-VI achieves a much faster convergence rate when the model is accurate enough. We also introduce a sample-based version of the algorithm called OS-Dyna. Unlike the traditional Dyna architecture, OS-Dyna still converges to the correct value function in presence of model approximation error.
BibTeX
@inproceedings{rakhsha2022operator,
  author = {Amin Rakhsha and Andrew Wang and Mohammad Ghavamzadeh and Amir-massoud Farahmand},
  title = {{Operator Splitting Value Iteration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=WSckK3nl8G},
}
Figure