Markov Decision Processes

Ask about this topic

Overview

Markov decision processes describe how an agent chooses actions as a system changes state probabilistically and rewards accumulate over time. Dynamic programming methods such as value iteration and policy iteration use Bellman equations to plan, while reinforcement learning methods such as Q-learning, policy gradients, and posterior sampling learn when transition models are unknown. Current work extends these tools to settings with constraints, risk, partial observability, non-stationarity, and large or structured state spaces, using methods such as robust optimization, state abstraction, and function approximation. A central tension is obtaining reliable safety and performance guarantees while keeping learning and planning computationally and statistically efficient beyond small tabular problems.

Latest papers

CardsList

159 papers30 papers in the last four weeks, up 150% on the four weeks before. 0.2% of all new papers.

  1. Game-Theoretic Foundations for Undiscounted Bisimulation Metrics

    Oct 28, 2026Matthew Zurek, Yudong Chen, Josiah P. HannaMarkov Decision ProcessesState Abstraction

    Department of Computer Sciences, University of Wisconsin–Madison

  2. Primal-Dual Representation Learning for Low-Rank Constrained MDPs

    Oct 22, 2026Chenhao Zhou, Chao Zhang, Wensong Bai +2Markov Decision ProcessesConstrained RL

    College of Computer Science and Technology, Zhejiang University

  3. Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions

    Oct 21, 2026Xun Shen, Yuepeng Wang, Daniyal Sajedi-Hosseini +6RL ControlMarkov Decision Processes

    Tokyo University of Agriculture and Technology, Japan · LY Corporation, Japan · Institute of Science Tokyo, Japan +2

  4. Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

    Oct 19, 2026Victor Boone, Cyrille Kone, Waris Radji +2Regret Minimization in RLMarkov Decision Processes

    IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France +1

  5. Anticipatory Gait Switching for Quadrupeds via Look-Ahead MDP Planning

    Oct 17, 2026Kelvin Aladum, Justin Peel, Nisar AhmedLegged RoboticsQuadruped Locomotion

  6. Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs

    Oct 16, 2026Maxime BaeldeMarkov Decision ProcessesPrimal-Dual Optimization

    Antvoice, Paris, France

  7. Contracting with an Agent under Model Mismatch

    Oct 16, 2026Elif Yılmaz, Jakub Tłuczek, Victor Villin +1Principal-Agent TheoryModel Misspecification

    University of Neuchâtel Neuchâtel, Switzerland

  8. Robust Counterfactuals for Markov Decision Processes under Statistical and Causal Uncertainties

    Oct 14, 2026Jessica Lally, Milad Kazemi, Nicola PaolettiCounterfactual ExplanationsMarkov Decision Processes

    King’s College London London, United Kingdom · Durham University Durham, United Kingdom

  9. Certifying Almost-Sure Reachability in Unknown MDPs

    Oct 13, 2026S Akshay, Suguman Bansal, Gaurav MahlaMarkov Decision ProcessesReachability Analysis

    Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, India · School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA

  10. Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes

    Oct 13, 2026Han Bao, Shinsaku Sakaue, Kazuki WatanabeFormal VerificationMarkov Decision Processes

    The Institute of Statistical Mathematics · Tohoku University · RIKEN AIP +2

  11. Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

    Oct 8, 2026Mingyi Li, Taira TsuchiyaRegret Minimization in RLMarkov Decision Processes

    The University of Tokyo · The University of Tokyo, The University of Osaka, and RIKEN

  12. Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

    Oct 8, 2026Qian Zuo, Francesco Emanuele StradiMarkov Decision ProcessesConstrained RL

    University of Edinburgh · Politecnico di Milano

  13. Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints

    Oct 8, 2026Jie Fu, Anamika DubeyMulti-Agent ControlMarkov Decision Processes

    Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL 32611, USA · School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA

  14. Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach

    Oct 7, 2026Huizhen Yu, Isaiah HeidtMarkov Decision ProcessesAverage-Reward RL

    Department of Computing Science University of Alberta, Canada

  15. Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

    Oct 7, 2026Zhaohua ChenOnline Resource AllocationOperations Research

    Taobao & Tmall Group of Alibaba, Renmin University of China

  16. Decision-Focused Learning in MDPs: An Occupancy Measure Approach

    Oct 6, 2026Zihao Zhao, Ashwath K. Karunakaram, Ali Eshragh +2Markov Decision ProcessesDecision-Focused Learning

    Georgia Institute of Technology, Atlanta, GA · Johns Hopkins Carey Business School, Washington, DC · International Computer Science Institute, Berkeley, CA

  17. Taylor Representations for Model-Free RL in Networked MDPs

    Oct 4, 2026Salah Chikhi, Abdelhaq Chaoui, Asuman Ozdaglar +1Markov Decision ProcessesRepresentation Learning for RL

    Massachusetts Institute of Technology

  18. Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs

    Oct 2, 2026Enes Arda, Atilla EryilmazMarkov Decision ProcessesAverage-Reward RL

    The Ohio State University

  19. On the Convergence of Success Conditioning for Policy Optimization

    Oct 2, 2026Matthew Brun, Xu Andy SunPolicy OptimizationMarkov Decision Processes

    Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139. · Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02139.

  20. Bellman Error Minimization Via Linear Programming Normalization

    Oct 2, 2026Haining YuFunction Approximation in RLDynamic Programming

    Independent Consultant

  21. Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes

    Oct 1, 2026Han Zhong, Yinyu YeRobust Markov Decision ProcessesMarkov Decision Processes

    Shanghai Jiao Tong University · Shanghai Jiao Tong University, SIMIS, and Stanford University

  22. Q-Learning for Reachability in MEC-Free MDPs

    Oct 1, 2026Lu-Chin Chang, Suguman BansalMarkov Decision ProcessesReinforcement Learning

    Georgia Institute of Technology

  23. Towards Optimal Policy Improvement

    Oct 1, 2026Yaniv Oren, Viliam Vadocz, Wiktor Zabka +7Markov Decision ProcessesPolicy Optimization

    Department of Intelligent Systems, TU Delft · Centrum Wiskunde & Informatica, Amsterdam · Department of Computer Science, ETH Zürich +3

  24. Rate-Optimal Algorithm for Adversarial Linear CMDPs

    Oct 1, 2026Kihyun Yu, Honghao Wei, Dabeen LeeRegret Minimization in RLMarkov Decision Processes

    KAIST · Washington State University · Seoul National University

  25. Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

    Sep 30, 2026Han Zhong, Yinyu YeMarkov Decision ProcessesPolicy Iteration

    Shanghai Jiao Tong University. · Shanghai Jiao Tong University, SIMIS, and Stanford University.

  26. Fast Regularized Policy Mirror Descent with One-Step TD Updates

    Sep 30, 2026Qipei Chen, Wenye Li, Yule Sun +1Markov Decision ProcessesPolicy Optimization

    School of Mathematical Sciences, Fudan University · School of Data Science, Fudan University

  27. Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

    Sep 30, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeeRegret Minimization in RLMarkov Decision Processes

    KAIST · Seoul National University

  28. Achieving an O(1/N)O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs

    Sep 29, 2026Yige Hong, Xiangcheng Zhang, Qiaomin Xie +2Markov Decision ProcessesAverage-Reward RL

    H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Department of Industrial and Systems Engineering, University of Wisconsin–Madison +2

  29. Bellman-Certified Rounding for Sparse Policy Deployment in MDPs

    Sep 29, 2026Zhaojun PengMarkov Decision ProcessesPolicy Optimization

  30. Optimal Multi-Reward Reinforcement Learning

    Sep 29, 2026Zijun Chen, Zihan ZhangMarkov Decision ProcessesSample-Efficient RL

    Department of Computer Science and Engineering Hong Kong University of Science and Technology