A Note on Optimization Formulations of Markov Decision Processes

2020/12/17 by Lexing Ying, Ying, Lexing, Yuhua Zhu +1 · 3 citations
Computer Science · Economics, Econometrics and Finance · #Climate Change Policy and Economics #Economic theories and models #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2012.09417

openalex publication_date 2020/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Optimizing Predictive Maintenance in Intelligent Manufacturing: An Integrated FNO-DAE-GNN-PPO MDP Framework
• Analysis of approximate linear programming solution to Markov decision problem with log barrier function
• A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance

Related

• An Analysis of Primal-Dual Algorithms for Discounted Markov Decision Processes
• Algorithm for Constrained Markov Decision Process with Linear Convergence
• From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process
• Mean field for Markov Decision Processes: from Discrete to Continuous Optimization