Introduction
This paper introduces Operator Splitting Value Iteration (OS-VI), a novel algorithm that uses an approximate model of the environment to exponentially accelerate the convergence of Value Iteration. Unlike traditional model-based methods like Dyna, the proposed OS-Dyna variant is robust to model errors and is guaranteed to converge to the true value function even when the learned model is inaccurate.
The Problem: Slow Convergence and the Model-Based Trap
In Reinforcement Learning (RL), the Value Iteration (VI) algorithm is a cornerstone for finding optimal policies. However, it suffers from two major practical hurdles:
- Slow Convergence: When the discount factor ($\gamma$) is close to 1—meaning the agent cares deeply about long-term rewards—VI converges very slowly, specifically at a rate of $O(\gamma^k)$.
- The Model-Based Trap: Model-based RL (like the famous Dyna architecture) tries to speed things up by planning with a learned model ($\hat{P}$). However, if that model is even slightly inaccurate, which is almost always the case in complex real-world systems, the agent will converge to a biased, incorrect value function.
The authors ask a critical question: Can we use a "fast but potentially inaccurate" model to accelerate computation without sacrificing the accuracy of the final solution?
The Solution: Operator Splitting
The researchers look toward numerical linear algebra for the answer, specifically matrix splitting methods used to solve large systems of equations.
The Core Idea
Standard Policy Evaluation is essentially solving the linear system $(I - \gamma P^\pi)V^\pi = r^\pi$. The authors "split" this operator into two parts:
- The Approximate Part: $(I - \gamma \hat{P}^\pi)$, handled by the fast, approximate model.
- The Correction Part: $\gamma(P^\pi - \hat{P}^\pi)$, handled by the true (but expensive) environment.
OS-VI and the Varga Operator
They define the Varga operator ($S^\pi$), which solves an auxiliary Markov Decision Process (MDP). In each iteration, the algorithm uses the approximate model to perform the "heavy lifting" of planning, but it adjusts the reward function using a correction term derived from the true environment. This ensures that the fixed point of the iteration remains the true value function $V^\pi$.
OS-Dyna
For the RL setting where the true dynamics are unknown, they introduce OS-Dyna. This algorithm uses samples from the real environment to estimate the "correction" needed for the approximate model. Crucially, while standard Dyna converges to the value function of the model, OS-Dyna converges to the value function of the real world.
Visualizing the Convergence
To demonstrate how OS-VI reaches the correct solution while model-based VI misses the mark, the authors visualize value function trajectories in a 2-State MDP.
As shown above, standard true VI (blue) takes a long, slow path to the true value $V^\pi$. Model-based VI (red) is fast but converges to the wrong, biased value $\hat{V}^\pi$. OS-VI (green) successfully leverages the model for speed while using true environment corrections to steer directly to the correct $V^\pi$, regardless of whether the model is highly accurate or less accurate.
Key Insights and Results
- Effective Discount Factor: The most striking insight is that OS-VI changes the convergence rate from $\gamma$ to an "effective" discount factor $\gamma'$. If the approximate model is reasonably accurate, $\gamma'$ can be much smaller than $\gamma$, leading to massive speedups in planning.
- Bias-Free Model-Based RL: OS-Dyna represents a significant theoretical shift. It treats the model as a preconditioner rather than a replacement for reality. This allows it to reap the speed benefits of model-based RL while maintaining the convergence guarantees of model-free RL.
- Exponential Speedup: In gridworld Control tasks (like a Modified Cliffwalk), OS-VI converged in roughly 5 iterations, whereas standard VI required over 20 iterations to reach the same error level.
- Robustness to Error: In the RL setting, when the model was artificially made inaccurate, standard Dyna failed to find the optimal policy, plateauing at a suboptimal return. In contrast, OS-Dyna successfully converged to the optimal policy, outperforming both Dyna and Q-Learning in terms of sample efficiency.
Limitations and Future Work
While promising, the approach has a few limitations to address in future research:
- Computational Overhead: Each step of OS-VI requires solving an auxiliary MDP. This is only efficient if solving that auxiliary MDP (using the fast model) is significantly cheaper than querying the true environment.
- Scaling to Deep RL: The current experiments focus on finite, discrete state spaces. The authors acknowledge that the next major challenge is implementing OS-Dyna with high-dimensional function approximators like Deep Neural Networks (DNNs).
- Model Quality Sensitivity: While the algorithm is robust to bias, if the approximate model is extremely poor, the "effective" discount factor $\gamma'$ could theoretically be worse than the original $\gamma$. However, the paper primarily explores the practical regime where the model provides at least some useful structural information.
Summary updated