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.

提出了一种名为 Monotone-ADP 的算法，利用价值函数的单调性来提高收敛速度，在三个应用领域中展示了数值结果，可以用比计算最优解所需计算量少两个数量级的迭代次数获得高质量解决方案。