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

optimizationlinear programmingMarkov decision processes

Mathematics Subject Classification ID

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

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.

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)

• Dual Ascent and Primal-Dual Algorithms for Infinite-Horizon Nonstationary Markov Decision Processes
• Accelerating Primal-Dual Methods for Regularized Markov Decision Processes
• 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
• scientific article; zbMATH DE number 238320 (Why is no real title available?)
• A Moreau-Yosida regularization for 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)