Abstract
This paper establishes a formal bridge between Reinforcement Learning (RL) and constrained convex optimization. By identifying the state-action value function ($q_\pi$) as the natural gradient of the RL objective, the authors demonstrate that several classic RL algorithms are structurally equivalent to well-known optimization methods. Specifically, Conservative Policy Iteration is mapped to Frank-Wolfe, MD-MPI to Mirror Descent, and Politex to Dual Averaging. This unified framework facilitates the transfer of theoretical insights and algorithmic techniques between the two fields.
Introduction
Reinforcement Learning (RL) and convex optimization have historically developed in parallel, often using distinct terminologies and frameworks. While RL focuses on finding optimal policies in Markov Decision Processes (MDPs) through dynamic programming, convex optimization seeks to maximize objective functions under constraints. This paper aims to unify these perspectives by showing that standard RL updates can be viewed as specific instances of constrained optimization.
The Gradient Analogy
The core insight of this work is the mathematical mapping between RL components and optimization primitives. In the tabular case, the expected value of a policy $J(\pi)$ serves as the objective function. Crucially, the authors show that the state-action value function, $q_\pi$, acts as the natural gradient of $J(\pi)$. This substitution allows for a direct translation of optimization algorithms into the RL domain.
Algorithmic Equivalences
Using the natural gradient analogy, the paper identifies three fundamental equivalences between optimization and RL algorithms. These mappings are summarized in the table below:
1. Frank-Wolfe and Conservative Policy Iteration (CPI)
Frank-Wolfe (or Conditional Gradient) optimizes by finding the most collinear element within a constraint set and taking a convex mixture. In RL, Conservative Policy Iteration (CPI) implements this by creating a stochastic mixture of the current policy and a new greedy policy, effectively "softening" the update to ensure stability.
2. Mirror Descent and MD-MPI
Mirror Descent incorporates a Bregman divergence penalty (such as KL divergence) to regularize steps. Mirror Descent Modified Policy Iteration (MD-MPI) applies this concept to RL, regularizing policy updates to prevent drastic changes, a concept closely related to modern algorithms like Trust Region Policy Optimization (TRPO).
3. Dual Averaging and Politex
Dual Averaging is a "lazy" version of Mirror Descent that aggregates historical gradients to determine the next step. Politex (Policy Iteration Using Expert Prediction) mirrors this by using a softmax over the sum of all previous $q$-values to update the policy, effectively leveraging the entire history of the agent's experience.
Conclusion and Future Work
This theoretical mapping provides a "Rosetta Stone" for cross-disciplinary research. While currently limited to the exact tabular setting, it opens doors for applying optimization theory—such as convergence proofs based on smoothness or convexity—to RL. Future work involves extending these connections to function approximation and deep RL settings, where estimation errors must be accounted for, potentially leading to more stable and theoretically grounded algorithms.
Summary updated