# From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2021.

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

- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Deflated Dynamics Value Iteration](https://mlsanity.com/paper/2407.10454/) (2024)
- [From Optimization to Control: Quasi Policy Iteration](https://mlsanity.com/paper/2311.11166/) (2023)
- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)
- [Rank-One Modified Value Iteration](https://mlsanity.com/paper/2505.01828/) (2025)
- [Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap](https://mlsanity.com/paper/2306.11271/) (2023)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)

## Abstract (arXiv)

In this paper we present a review of the connections between classical algorithms for solving Markov Decision Processes (MDPs) and classical gradient-based algorithms in convex optimization. Some of these connections date as far back as the 1980s, but they have gained momentum in recent years and have lead to faster algorithms for solving MDPs. In particular, two of the most popular methods for solving MDPs, Value Iteration and Policy Iteration, can be linked to first-order and second-order methods in convex optimization. In addition, recent results in quasi-Newton methods lead to novel algorithms for MDPs, such as Anderson acceleration. By explicitly classifying algorithms for MDPs as first-order, second-order, and quasi-Newton methods, we hope to provide a better understanding of these algorithms, and, further expanding this analogy, to help to develop novel algorithms for MDPs, based on recent advances in convex optimization.