2014/01/08 by Daniel Jiang, Jiang, Daniel R., Warren B. Powell +1 · 2 citations
Business, Management and Accounting · Engineering · Medicine · #Cardiovascular Function and Risk Factors #FOS: Mathematics #Mechanical Circulatory Support Devices #Optimization and Control (math.OC) #Smart Grid Energy Management #Supply Chain and Inventory Management
paper · pdf · doi:10.48550/arxiv.1401.1590
openalex publication_date 2014/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many sequential decision problems can be formulated as Markov Decision\nProcesses (MDPs) where the optimal value function (or cost-to-go function) can\nbe shown to satisfy a monotone structure in some or all of its dimensions. When\nthe state space becomes large, traditional techniques, such as the backward\ndynamic programming algorithm (i.e., backward induction or value iteration),\nmay no longer be effective in finding a solution within a reasonable time\nframe, and thus we are forced to consider other approaches, such as approximate\ndynamic programming (ADP). We propose a provably convergent ADP algorithm\ncalled Monotone-ADP that exploits the monotonicity of the value functions in\norder to increase the rate of convergence. In this paper, we describe a general\nfinite-horizon problem setting where the optimal value function is monotone,\npresent a convergence proof for Monotone-ADP under various technical\nassumptions, and show numerical results for three application domains: optimal\nstopping, energy storage/allocation, and glycemic control for diabetes\npatients. The empirical results indicate that by taking advantage of\nmonotonicity, we can attain high quality solutions within a relatively small\nnumber of iterations, using up to two orders of magnitude less computation than\nis needed to compute the optimal solution exactly.\n