# Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods

arXiv: https://arxiv.org/abs/2202.06922 · HTML: https://mlsanity.com/paper/2202.06922/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 14 Feb 2022.

## Builds on (most cited first, 27 of 27)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [A General Analysis of the Convergence of ADMM](https://mlsanity.com/paper/1502.02009/) (2015)
- [Dissipativity Theory for Nesterov's Accelerated Method](https://mlsanity.com/paper/1706.04381/) (2017)
- [Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems](https://mlsanity.com/paper/1705.03615/) (2017)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [A Universally Optimal Multistage Accelerated Stochastic Gradient Method](https://mlsanity.com/paper/1901.08022/) (2019)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [A Robust Accelerated Optimization Algorithm for Strongly Convex Functions](https://mlsanity.com/paper/1710.04753/) (2017)
- [Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions](https://mlsanity.com/paper/1805.10579/) (2018)
- [Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs](https://mlsanity.com/paper/1711.00987/) (2017)
- [Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1911.00934/) (2019)
- [Control Interpretations for First-Order Optimization Methods](https://mlsanity.com/paper/1703.01670/) (2017)
- [Analysis and Design of First-Order Distributed Optimization Algorithms over Time-Varying Graphs](https://mlsanity.com/paper/1907.05448/) (2019)
- [A frequency-domain analysis of inexact gradient methods](https://mlsanity.com/paper/1912.13494/) (2019)
- [A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints](https://mlsanity.com/paper/1706.08141/) (2017)
- [Robustness of accelerated first-order algorithms for strongly convex optimization problems](https://mlsanity.com/paper/1905.11011/) (2019)
- [Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach](https://mlsanity.com/paper/1905.00279/) (2019)
- [Passivity-Based Distributed Optimization with Communication Delays Using PI Consensus Algorithm](https://mlsanity.com/paper/1609.04666/) (2016)
- [Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs](https://mlsanity.com/paper/1806.03677/) (2018)
- [Analytical Convergence Regions of Accelerated Gradient Descent in Nonconvex Optimization under Regularity Condition](https://mlsanity.com/paper/1810.03229/) (2018)
- [An integral quadratic constraint framework for real-time steady-state optimization of linear time-invariant systems](https://mlsanity.com/paper/1710.10204/) (2017)
- [Design of First-Order Optimization Algorithms via Sum-of-Squares Programming](https://mlsanity.com/paper/1803.10928/) (2018)
- [Systematic Design of Decentralized Algorithms for Consensus Optimization](https://mlsanity.com/paper/1903.01023/) (2019)

## Built on by (most cited first, 3 of 3)

- [Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration](https://mlsanity.com/paper/2504.10865/) (2025)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2204.09801/) (2022)

## Abstract (arXiv)

Value-based methods play a fundamental role in Markov decision processes (MDPs) and reinforcement learning (RL). In this paper, we present a unified control-theoretic framework for analyzing valued-based methods such as value computation (VC), value iteration (VI), and temporal difference (TD) learning (with linear function approximation). Built upon an intrinsic connection between value-based methods and dynamic systems, we can directly use existing convex testing conditions in control theory to derive various convergence results for the aforementioned value-based methods. These testing conditions are convex programs in form of either linear programming (LP) or semidefinite programming (SDP), and can be solved to construct Lyapunov functions in a straightforward manner. Our analysis reveals some intriguing connections between feedback control systems and RL algorithms. It is our hope that such connections can inspire more work at the intersection of system/control theory and RL.