# Generalized Second Order Value Iteration in Markov Decision Processes

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2019.

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

- [From Optimization to Control: Quasi Policy Iteration](https://mlsanity.com/paper/2311.11166/) (2023)
- [Rank-One Modified Value Iteration](https://mlsanity.com/paper/2505.01828/) (2025)
- [Two-Step Q-Learning](https://mlsanity.com/paper/2407.02369/) (2024)
- [Simultaneous Training of First- and Second-Order Optimizers in Population-Based Reinforcement Learning](https://mlsanity.com/paper/2408.15421/) (2024)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)

## Abstract (arXiv)

Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore it may take a large number of iterations to converge to the optimal solution. Successive relaxation is a popular technique that can be applied to solve a fixed point equation. It has been shown in the literature that, under a special structure of the MDP, successive over-relaxation technique computes the optimal value function faster than standard value iteration. In this work, we propose a second order value iteration procedure that is obtained by applying the Newton-Raphson method to the successive relaxation value iteration scheme. We prove the global convergence of our algorithm to the optimal solution asymptotically and show the second order convergence. Through experiments, we demonstrate the effectiveness of our proposed approach.