# An Approximate Dynamic Programming Algorithm for Monotone Value Functions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2014.

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

- [Weakly Coupled Deep Q-Networks](https://mlsanity.com/paper/2310.18803/) (2023)
- [Model Based Reinforcement Learning for Personalized Heparin Dosing](https://mlsanity.com/paper/2304.10000/) (2023)
- [Transferable Energy Storage Bidder](https://mlsanity.com/paper/2301.01233/) (2023)
- [Learning Not to Optimize: Physics-Informed Action-Space Reshaping for Intent-Based Network Control](https://mlsanity.com/paper/2608.00908/) (2026)
- [A Monotone Approximate Dynamic Programming Approach for the Stochastic Scheduling, Allocation, and Inventory Replenishment Problem: Applications to Drone and Electric Vehicle Battery Swap Stations](https://mlsanity.com/paper/2105.07026/) (2021)
- [Sequential Stochastic Optimization in Separable Learning Environments](https://mlsanity.com/paper/2108.09585/) (2021)
- [Minimizing Age of Information for Mobile Edge Computing Systems: A Nested Index Approach](https://mlsanity.com/paper/2307.01366/) (2023)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)

## Abstract (arXiv)

Many sequential decision problems can be formulated as Markov Decision Processes (MDPs) where the optimal value function (or cost-to-go function) can be shown to satisfy a monotone structure in some or all of its dimensions. When the state space becomes large, traditional techniques, such as the backward dynamic programming algorithm (i.e., backward induction or value iteration), may no longer be effective in finding a solution within a reasonable time frame, and thus we are forced to consider other approaches, such as approximate dynamic programming (ADP). We propose a provably convergent ADP algorithm called Monotone-ADP that exploits the monotonicity of the value functions in order to increase the rate of convergence. In this paper, we describe a general finite-horizon problem setting where the optimal value function is monotone, present a convergence proof for Monotone-ADP under various technical assumptions, and show numerical results for three application domains: optimal stopping, energy storage/allocation, and glycemic control for diabetes patients. The empirical results indicate that by taking advantage of monotonicity, we can attain high quality solutions within a relatively small number of iterations, using up to two orders of magnitude less computation than is needed to compute the optimal solution exactly.