Basis Construction from Power Series Expansions of Value Functions

Sridhar Mahadevan, Bo LiuNeurIPS 2010 · OpenReview

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:

  1. 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.
  2. 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$.
Condition number of the matrix exploding as the discount factor approaches 1 in a Chain MDP.
  • 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 comparisons demonstrating that Drazin and BARB methods converge faster and more stably than Krylov bases.
  • 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

Abstract

This paper explores links between basis construction methods in Markov decision processes and power series expansions of value functions. This perspective provides a useful framework to analyze properties of existing bases, as well as provides insight into constructing more effective bases. Krylov and Bellman error bases are based on the Neumann series expansion. These bases incur very large initial Bellman errors, and can converge rather slowly as the discount factor approaches unity. The Laurent series expansion, which relates discounted and average-reward formulations, provides both an explanation for this slow convergence as well as suggests a way to construct more efficient basis representations. The first two terms in the Laurent series represent the scaled average-reward and the average-adjusted sum of rewards, and subsequent terms expand the discounted value function using powers of a generalized inverse called the Drazin (or group inverse) of a singular matrix derived from the transition matrix. Experiments show that Drazin bases converge considerably more quickly than several other bases, particularly for large values of the discount factor. An incremental variant of Drazin bases called Bellman average-reward bases (BARBs) is described, which provides some of the same benefits at lower computational cost.
BibTeX
@inproceedings{mahadevan2010basis,
  author = {Sridhar Mahadevan and Bo Liu},
  title = {{Basis Construction from Power Series Expansions of Value Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=SJNgSuW_ZH},
}
Figure