Revisit Policy Optimization in Matrix Form

Sitao Luan, Xiao-Wen Chang, Doina PrecuparXiv 2019 · OpenReview

Abstract

Traditional Reinforcement Learning (RL) notation often obscures the relationship between an agent's policy and the environment's dynamics by coupling them within transition matrices. This paper presents a refined matrix framework that disentangles these components, providing a transparent mathematical foundation for policy optimization. By isolating the policy matrix from the environment's physics, the authors demonstrate that prominent algorithms, such as Trust Region Policy Optimization (TRPO) and Policy Gradient, are specific instances of a broader family of matrix-based approximations. This unified view simplifies the derivation of error bounds and offers new insights into the decomposition of policy gradients.

Introduction

In the tabular Reinforcement Learning setting, the value of a policy is typically derived from the Bellman equation, expressed as $V_\pi = (I - \gamma P_\pi)^{-1} r_\pi$. While mathematically sound, this notation presents a significant challenge for optimization: both the transition matrix ($P_\pi$) and the reward vector ($r_\pi$) are functions of the policy $\pi$. Consequently, any update to the policy simultaneously alters the entire mathematical structure of the environment's dynamics as perceived by the agent. This coupling makes it difficult to isolate the direct impact of a policy change on long-term value.

This research addresses this complexity by leveraging a matrix notation that separates the agent's behavior from the environment's transitions. By doing so, the authors transform policy optimization into a more intuitive exercise in matrix calculus, allowing for a clearer analysis of surrogate objectives and their convergence properties.

The Matrix Framework: Disentangling Policy and Dynamics

The core of the proposed method involves a structural split of the standard transition matrix. Instead of using a policy-dependent state-to-state transition matrix $P_\pi$, the authors define two distinct entities:

  1. The Environment Matrix ($P$): A fixed matrix mapping state-action pairs to the next state, representing the "physics" of the world.
  2. The Policy Matrix ($\Pi$): A variable matrix mapping states to actions, representing the agent's strategy.

Under this formulation, the transition matrix is expressed as $P_\pi = \Pi P$. By rewriting the expected discounted reward $\eta(\pi)$ using these separate matrices, the objective function becomes an explicit function of $\Pi$. This separation allows researchers to take derivatives with respect to the policy matrix directly, treating the environment dynamics as a constant operator.

A Unified View of Surrogate Objectives

Using this disentangled notation, the authors identify six distinct ways to construct "surrogate functions"—local approximations used to iteratively update policies. This "Six Ways" analysis provides a unified mathematical umbrella for several landmark RL algorithms:

  • $L^1$ (Policy Gradient): The authors show that the standard Policy Gradient objective corresponds to the simplest linear approximation within this framework.
  • $L^4$ (TRPO): The surrogate objective used in Trust Region Policy Optimization is revealed to be a specific matrix-based approximation of the value function.
  • $L^2$ and $L^3$ (Gradient Decompositions): The authors introduce intermediate approximations and discover that the gradients of $L^2$ and $L^3$ sum exactly to the gradient of the TRPO objective ($L^4$). This suggests that TRPO effectively captures multiple facets of the policy update simultaneously.

Theoretical Insights and Error Bounds

One of the primary contributions of this framework is the simplification of complex RL proofs. The authors utilize pure matrix algebra to derive the error bounds for TRPO, showing that the approximation's deviation from the true value function is bounded by the KL divergence between the old and new policies, scaled by the environment's discount factor and advantage values.

This approach provides a more concise proof for the Monotonic Improvement Theorem, a cornerstone of stable RL that guarantees a new policy will perform at least as well as the old one if certain conditions are met. By expressing these bounds through matrix norms, the research clarifies how "drift" occurs when using local surrogates instead of the true value function.

Discussion and Future Directions

While the current framework provides significant clarity, it is primarily focused on the tabular case (finite states and actions). In modern RL applications involving continuous state spaces, such as robotics, these matrices would transition into infinite-dimensional operators. Extending this matrix notation to function approximation remains a key area for future study.

Furthermore, the isolation of the environment dynamics ($P$) suggests significant potential for Model-Based RL. If an agent can learn an accurate estimate of the matrix $P$ from data, these matrix equations could allow for direct policy updates without the need for extensive environment sampling. This framework also paves the way for a more precise mapping of policy updates to specific neural network parameter changes, potentially leading to more efficient optimization techniques.

Summary updated

Abstract

In tabular case, when the reward and environment dynamics are known, policy evaluation can be written as $\bm{V}_{\bm{\pi}} = (I - \gamma P_{\bm{\pi}})^{-1} \bm{r}_{\bm{\pi}}$, where $P_{\bm{\pi}}$ is the state transition matrix given policy ${\bm{\pi}}$ and $\bm{r}_{\bm{\pi}}$ is the reward signal given ${\bm{\pi}}$. What annoys us is that $P_{\bm{\pi}}$ and $\bm{r}_{\bm{\pi}}$ are both mixed with ${\bm{\pi}}$, which means every time when we update ${\bm{\pi}}$, they will change together. In this paper, we leverage the notation from \cite{wang2007dual} to disentangle ${\bm{\pi}}$ and environment dynamics which makes optimization over policy more straightforward. We show that policy gradient theorem \cite{sutton2018reinforcement} and TRPO \cite{schulman2015trust} can be put into a more general framework and such notation has good potential to be extended to model-based reinforcement learning.
BibTeX
@misc{luan2019revisit,
  author = {Sitao Luan and Xiao-Wen Chang and Doina Precup},
  title = {{Revisit Policy Optimization in Matrix Form}},
  year = {2019},
  eprint = {1909.09186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.09186},
}
Figure