This paper, "Basis Construction from Power Series Expansions of Value Functions" by Sridhar Mahadevan and Bo Liu, provides a deep mathematical bridge between classical matrix theory and modern reinforcement learning (RL). It rethinks how we build the "building blocks" (basis functions) used to approximate value functions in Markov Decision Processes (MDPs).
TL;DR
The authors demonstrate that standard basis construction methods (like Krylov bases) are tied to the Neumann series, which fails as the discount factor $\gamma$ approaches 1. By instead leveraging the Laurent series and the Drazin inverse, they introduce Drazin bases and Bellman Average-Reward Bases (BARBs), which provide significantly more stable and accurate value function approximations in long-horizon tasks.
What Problem Does This Paper Address?
In RL, we rarely represent every single state individually; instead, we use a low-dimensional basis ($\Phi$) to approximate the value function ($V \approx \Phi w$). There are two traditional ways to build these bases:
- Reward-sensitive (e.g., Krylov bases): These use powers of the transition matrix and the reward function. They are great at capturing local, immediate rewards but struggle with long-term global behavior.
- Reward-invariant (e.g., Proto-Value Functions): These use eigenvectors of the state-space graph. They capture global topology but ignore where the actual rewards are.
The "fundamental dilemma" is that Krylov-based methods degrade rapidly as the discount factor $\gamma \to 1$. In these scenarios, the "horizon" of the problem becomes very long, and the mathematical matrices involved become nearly singular (hard to invert), leading to slow convergence and high error.
Methods
The authors move beyond the standard Neumann series—the power series $V = \sum (\gamma P)^i R$ that underlies most RL algorithms—and look toward the Laurent series.
- The Laurent Series Expansion: This expansion relates discounted rewards to average rewards. It explicitly separates the "gain" (the steady-state average reward) from the "bias" (the transient fluctuations).
- Drazin Bases: The authors derive a new basis using the Drazin inverse (a generalized matrix inverse). Unlike standard inverses, the Drazin inverse can handle the singular matrices that appear when $\gamma = 1$. This basis naturally includes the "gain" as its first vector, ensuring the long-term average behavior is captured immediately.
- BARBs (Bellman Average-Reward Bases): Recognizing that computing a Drazin inverse is expensive, the authors propose BARBs. This is an incremental algorithm that dilates the reward function using an "average-adjusted" transition matrix. It offers the benefits of the Laurent expansion at a computational cost similar to standard Krylov methods.
Key Insights and Ideas
- The Singularity Problem: The paper explains why Krylov bases fail at high $\gamma$: the condition number of the matrix $(I - \gamma P)$ explodes. The Laurent series bypasses this by centering the expansion around $\gamma = 1$ rather than $\gamma = 0$.
- Gain as the Foundation: By making the "average reward" (gain) the first basis vector, the approximation starts with a global understanding of the policy's value, rather than trying to build it up from local reward spikes.
- Bridging Discounted and Average Reward: The math shows that discounted RL and average-reward RL aren't just different frameworks—they are different terms in the same Laurent series. This allows researchers to use tools from one to solve problems in the other.
Key Results
The paper evaluates these methods on several classic MDP benchmarks designed to test long-horizon reasoning, including a 50-State Chain MDP, a Two-Room Gridworld, and Random MDPs.
- Superior Convergence: In experiments with $\gamma = 0.99$ and $\gamma = 0.999$, Drazin bases and BARBs converged much faster and reached lower error than Krylov bases or Proto-Value Functions.
- Error Decomposition: The authors proved a new decomposition of Bellman error into three parts: reward error, average-reward error, and feature prediction error. This provides a clearer "diagnostic" for why an RL agent might be failing.
- Stability: While Krylov bases showed "spiky" error patterns as they struggled to capture long-term features, BARBs showed a much smoother and more monotonic reduction in error.
Limitations and Future Work
- Computational Scaling: While BARBs are more efficient than full Drazin inverses, they still require handling the transition matrix. Scaling this to massive state spaces (like those in Deep RL) remains a challenge.
- Model-Free Implementation: The current work assumes some knowledge of the transition dynamics or a fixed policy. The authors suggest that future work should focus on purely sample-based versions of these Laurent-inspired bases.
- Factored MDPs: The authors note that exploiting structure in the transition matrix (e.g., through factored representations) could make Drazin-based methods even more powerful for complex, multi-variable problems.
Summary updated