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. Physics-Informed Causal MDPs for Sequential Constraint Repair in Engineering Simulation Pipelines

    Apr 20, 2026Chuhan QiaoMarkov Decision ProcessesReinforcement Learning

    Beijing JiaoTong University

  2. Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration

    Apr 19, 2026Donghwan LeeMarkov Decision ProcessesReinforcement Learning

    Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon 34141, South Korea

  3. DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

    Apr 17, 2026Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. VeeravalliNon-Stationary RLRegret Minimization in RL

    ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign

  4. Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

    Apr 17, 2026Jean Tarbouriech, Matteo Pirotta, Michal Valko +1Markov Decision ProcessesPolicy Learning

    Facebook AI Research Paris & Inria Lille · Facebook AI Research Paris · DeepMind Paris

  5. Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning

    Apr 16, 2026Jean-Bastien Grill, Michal Valko, Rémi MunosMarkov Decision ProcessesMarkov Models

    SequeL team, INRIA Lille - Nord Europe, France · Google DeepMind, UK∗

  6. Offline-Online Reinforcement Learning for Linear Mixture MDPs

    Apr 13, 2026Zhongjun Zhang, Sean R. SinclairOffline-To-Online RLMarkov Decision Processes

    Department of Industrial Engineering and Management Sciences, Northwestern University

  7. When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs

    Apr 11, 2026Jose Efraim Aguilar Escamilla, Haoyang Hong, Jiawei Li +4Markov Decision ProcessesAdversarial Attacks

    Oregon State University, OR, USA · University of Illinois Urbana–Champaign, IL, USA · Princeton University, NJ, USA +1

  8. Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem

    Apr 8, 2026Hyukjun Yang, Han-Dong Lim, Donghwan LeeFunction Approximation in RLMarkov Decision Processes

    the Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, 34141, South Korea

  9. Value Mirror Descent for Reinforcement Learning

    Apr 7, 2026Zhichao Jia, Guanghui LanMarkov Decision ProcessesReinforcement Learning

    H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332.

  10. Nash Approximation Gap in Truncated Infinite-horizon Partially Observable Markov Games

    Apr 6, 2026Lan Sang, Chinmay MaheshwariPartially Observable Stochastic GamesImperfect-Information Games

    Applied Mathematics and Statistics at Johns Hopkins University, Baltimore, MD, USA · Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD, USA

  11. Delayed homomorphic reinforcement learning for environments with delayed feedback

    Apr 4, 2026Jongsoo Lee, Jangwon Kim, Soohee HanDelayed RLReinforcement Learning

    Department of Convergence IT Engineering, POSTECH, Pohang, 37673, South Korea · Department of Electrical Engineering, POSTECH, Pohang, 37673, South Korea

  12. Multi-Robot Multi-Queue Control via Exhaustive Assignment Actor-Critic Learning

    Apr 4, 2026Mohammad Merati, H. M. Sabbir Ahmad, Wenchao Li +1Multi-Robot Task AllocationRobot Policy Learning

    Divisions of Systems Engineering, Boston University, 8 St Mary’s St, Boston, MA 02215, United States. · Department of Electrical and Computer Engineering, Boston University, 8 St Mary’s St, Boston, MA 02215, United States.

  13. Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes

    Apr 2, 2026Jiping Luo, Nikolaos PappasMarkov Decision ProcessesPareto Optimization

    Department of Computer and Information Science, Linköping University, Linköping 58183, Sweden.

  14. Efficient Constraint Generation for Stochastic Shortest Path Problems

    Apr 2, 2026Johannes Schmalz, Felipe TrevizanMarkov Decision Processes

    Australian National University, Australia · Saarland University, Germany

  15. Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards

    Mar 29, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeeAdversarial MARLReinforcement Learning

    Department of Industrial and Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University · Research Institute of Mathematics, Seoul National University +2

  16. Beyond Freshness and Semantics: A Coupon-Collector Framework for Effective Status Updates

    Mar 27, 2026Youssef Ahmed, Arnob Ghosh, Chih-Chun Wang +1Age of InformationWireless Resource Allocation

    Department of ECE, The Ohio State University, Columbus, OH, USA · Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, USA · Elmore Family School of ECE, Purdue University, West Lafayette, IN, USA +1

  17. Operator-Theoretic Foundations and Policy Gradient Methods for General MDPs with Unbounded Costs

    Mar 18, 2026Abhishek Gupta, Aditya MahajanMarkov Decision ProcessesPolicy Gradient Methods

    The Ohio State University, Columbus, Ohio. · McGill University, Montreal, Canada.

  18. Weakly Time-Coupled Approximation of Markov Decision Processes

    Mar 13, 2026Negar Soheili, Selvaprabu Nadarajah, Bo YangMarkov Decision ProcessesSequential Decision Making

    Information and Decision Sciences Department, University of Illinois at Chicago, Chicago, IL, 60607 · Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong SAR

  19. Impact of Markov Decision Process Design on Sim-to-Real Reinforcement Learning

    Mar 10, 2026Tatjana Krau, Jorge Mandlmaier, Tobias Damm +1Sim-to-Real TransferMarkov Decision Processes

    Institute of Production and Informatics, 87527 Sonthofen, Germany · Department of Mathematics, RPTU University Kaiserslautern-Landau, 67663 Kaiserslautern, Germany

  20. Relating Reinforcement Learning to Dynamic Programming-Based Planning

    Mar 8, 2026Filip V. Georgiev, Kalle G. Timperi, Başak Sakçak +1Markov Decision ProcessesDynamic Programming

    Center for Applied Computing, Faculty of Information Technology and Electrical Engineering, University of Oulu, Finland · Dept. of Advanced Computing Sciences, Maastricht University, the Netherlands

  21. Joint MDPs and Reinforcement Learning in Coupled-Dynamics Environments

    Mar 6, 2026Ege C. Kaya, Mahsa Ghasemi, Abolfazl HashemiSemi-Markov Decision ProcessMarkov Decision Processes

    Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA

  22. Learning in Markov Decision Processes with Exogenous Dynamics

    Mar 3, 2026Davide Maran, Davide Salaorni, Marcello RestelliMarkov Decision ProcessesSample-Efficient RL

    Department of DEIB, Politecnico di Milano, Milan, Italy.

  23. κκ-Explorer: Minimax Active Model Estimation in MDPs

    Feb 23, 2026Xihe Gu, Urbashi Mitra, Tara JavidiFrank-Wolfe AlgorithmsRL Exploration

    Department of Electrical and Computer Engineering, University of California, San Diego · Department of Electrical and Computer Engineering, University of Southern California

  24. MDP Planning as Policy Inference

    Feb 19, 2026David TolpinVariational Monte CarloMarkov Decision Processes

    Offtopia

  25. Calculating Mutual Information between a Reward Maximizer and its Environment

    Feb 13, 2026Alfred Harwood, Jose Faustino, Alex AltairMarkov Decision ProcessesReinforcement Learning

    1Dovetail Research · University of Sao Paulo

  26. Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

    Feb 3, 2026Aneri Muni, Vincent Taboga, Esther Derman +2Markov Decision ProcessesQ-Learning

    Universit´e de Montr´eal, Quebec, Canada · Mila - Quebec AI Institute, Quebec, Canada · GERAD & Department of Decision Sciences, HEC Montr´eal, Quebec, Canada

  27. Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

    Feb 2, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RLMarkov Decision Processes

    Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan

  28. Poincaré Meets Bellman: Revisable Memory, Operational Quotients, and Evidence-Supported Learning in Changing Environments

    Nov 28, 2025Xin LiMarkov Decision ProcessesDynamic Programming

    Department of Computer Science University at Albany

  29. On the Hardness of Reinforcement Learning with Transition Look-Ahead

    Oct 22, 2025Corentin Pla, Hugo Richard, Marc Abeille +2Reinforcement LearningModel-Based Planning

    CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team +1

  30. Optimization-Based Robust Permissive Synthesis for Interval MDPs

    Oct 3, 2025Khang Vo Huynh, David Parker, Lu FengRobust Markov Decision ProcessesMarkov Decision Processes

    Department of Computer Science, University of Virginia, Charlottesville, VA, USA · Department of Computer Science, University of Oxford, Oxford, UK