A Matrix Splitting Perspective on Planning with Options

Pierre-Luc Bacon, Doina PrecuparXiv 2016 · OpenReview

TL;DR

This paper bridges the gap between reinforcement learning (RL) and numerical linear algebra by proving that the options framework—which uses temporally extended actions—is mathematically equivalent to matrix splitting. This perspective reveals that choosing "good" options is essentially the same as designing a good preconditioner for a linear system, creating a formal trade-off between the cost of building options and the speed of planning.

What Problem Does This Paper Address?

In reinforcement learning, "planning" often involves solving a Markov Decision Process (MDP) to find a value function. As problems grow larger, standard one-step methods (like basic Value Iteration) become computationally expensive. The options framework was introduced to allow agents to plan using "macro-actions" that last for multiple time steps, potentially speeding up the process.

However, despite years of research, the field lacked a rigorous way to define what makes an option "good" for planning. Researchers knew intuitively that longer-lasting options seemed to help, but there was no unified theoretical tool to measure this benefit. Bacon and Precup address this by mapping the Bellman equations used in RL onto the well-studied world of iterative linear solvers.

Methods

The authors employ two main mathematical frameworks:

  1. Matrix Splitting: In linear algebra, to solve a system $Ax = b$, you can "split" the matrix $A$ into two parts ($M - N$). You then solve the system iteratively using the formula $x_{k+1} = M^{-1}Nx_k + M^{-1}b$. The speed of convergence depends on the "spectral radius" (the largest eigenvalue) of the matrix $M^{-1}N$.
  2. Generalized Bellman Operators: The authors rewrite the Bellman equation for options. They define a "continuation" transition matrix ($P_7$) and a "termination" transition matrix ($P_K$).

By combining these, they show that the operator for planning with options ($L$) can be decomposed exactly into a matrix splitting where $M = (I - \gamma P_7)$ and $N = \gamma P_K$. They analyze two execution models:

  • Gating Execution: Where the choice of option is reconsidered at every step.
  • Call-and-Return Execution: The standard model where an option is chosen and followed until it terminates. They show this also fits the splitting framework if you augment the state space to include the current option.

Datasets

Not discussed in the paper. This is a theoretical paper focused on mathematical proofs and framework unification; it does not perform empirical tests on specific RL benchmarks or datasets.

Key Insights and Ideas

  • Options are Preconditioners: The most significant "aha moment" is that a set of options acts as a preconditioner. In numerical analysis, preconditioning transforms a difficult linear system into one that is easier (faster) to solve. The paper argues that "good" options are simply those that induce a preconditioning matrix $M$ that is close to the original system matrix.
  • Predict Further, Plan Faster: The authors provide a formal proof (Theorem 3) for the intuition that longer-lived options lead to faster planning. Specifically, if you decrease the probability of an option terminating ($\beta$), you decrease the spectral radius of the iteration matrix, which mathematically guarantees faster asymptotic convergence.
  • The Fundamental Trade-off: There is no "free lunch." An option that lasts forever and perfectly predicts the future would allow you to solve the MDP in a single iteration. However, computing such an option is just as hard as solving the original MDP. This highlights a tension between the upfront cost of building/learning options and the savings gained during the planning phase.
  • Connection to TD($\lambda$): The authors note that the choice of timescale for options mirrors the classic bias-variance tradeoff found in the $\lambda$-operator in temporal difference learning.

Key Results

  • Theorem 1 (Regular Splitting): Proves that the matrices induced by the gating model form a "regular splitting," which guarantees that the iterative planning process will always converge to a unique solution.
  • Theorem 2 (Consistency): Confirms that planning with options converges to the correct value function of the target policy, provided the options' policies match the target policy's marginal actions.
  • Convergence Rate: The paper mathematically demonstrates that as options become more temporally extended (lower termination values), the spectral radius $\rho(M^{-1}N)$ decreases, leading to faster convergence.

Limitations and Future Work

  • Asymptotic vs. Real-world Speed: The results focus on asymptotic convergence rates. In practice, the "wall-clock" time might be dominated by the overhead of managing complex options or the initial cost of learning their models, which this paper doesn't quantify.
  • Finite State Spaces: The proofs rely on finite state and action spaces. Extending this matrix splitting perspective to continuous state spaces (using function approximation) remains a challenge.
  • Sample Complexity: While the paper explains how options help planning (given a model), it doesn't address the learning side—specifically, how many samples are needed to build these "preconditioning" options in an unknown environment.
  • Future Direction: The authors suggest using these tools to automatically optimize option structures to minimize total computational effort, potentially using the "bounded rationality" framework.

Summary updated

Abstract

We show that the Bellman operator underlying the options framework leads to a matrix splitting, an approach traditionally used to speed up convergence of iterative solvers for large linear systems of equations. Based on standard comparison theorems for matrix splittings, we then show how the asymptotic rate of convergence varies as a function of the inherent timescales of the options. This new perspective highlights a trade-off between asymptotic performance and the cost of computation associated with building a good set of options.
BibTeX
@misc{bacon2016matrix,
  author = {Pierre-Luc Bacon and Doina Precup},
  title = {{A Matrix Splitting Perspective on Planning with Options}},
  year = {2016},
  eprint = {1612.00916},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.00916},
}
Figure