A note on optimization formulations of Markov decision processes

DOI10.4310/CMS.2022.V20.N3.A5MaRDI QIDQ2129661zbMATH OpenOpenAlexFDO

Authors Lexing Ying, Yuhua Zhu

Publication date 22 April 2022

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.09417

zbMATH Keywords

linear programmingMarkov decision processesoptimization

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational methods in Markov chains (60J22) Linear programming (90C05)

Abstract: This note summarizes the optimization formulations used in the study of Markov decision processes. We consider both the discounted and undiscounted processes under the standard and the entropy-regularized settings. For each setting, we first summarize the primal, dual, and primal-dual problems of the linear programming formulation. We then detail the connections between these problems and other formulations for Markov decision processes such as the Bellman equation and the policy gradient method.

Review text

The paper summarizes the primal, primal-dual and dual problems for discounted standard Markov decision processes, discounted regularized Markov decision processes, undiscounted standard Markov decision processes and undiscounted regularized Markov decision processes. Moreover, the paper shows the equivalence between the dual problem and policy gradient as well as the equivalence between the primal problem and Bellman equation for the above four Markov decision processes. These optimization formulations are helpful for the theoretical study of Markov decision processes algorithms.

Recommendations

• Linear programming formulations of Markov decision processes
• Linear programming formulation for non-stationary, finite-horizon Markov decision process models
• A note on policy algorithms for discounted Markov decision problems
• Computational complexity in Markov decision theory
• scientific article; zbMATH DE number 700091

Cited in

(6)

• Optimization of a special case of continuous-time Markov decision processes with compact action set
• A class of procedures to compute the optimal value f unction in a Markovian decision problem
• A Moreau-Yosida regularization for Markov decision processes
• scientific article; zbMATH DE number 238320 (Why is no real title available?)
• Dual Ascent and Primal-Dual Algorithms for Infinite-Horizon Nonstationary Markov Decision Processes
• Accelerating Primal-Dual Methods for Regularized Markov Decision Processes

This page was built for publication: A note on optimization formulations of Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2129661)