Interval Markov Decision Processes

Follow this topic Ask about this topic

Interval Markov decision processes represent uncertain dynamics by assigning lower and upper bounds to transition probabilities, then ask how to act safely or achieve goals across all distributions allowed by those bounds. Common approaches use robust Bellman updates and policy iteration for value optimization, or linear and mixed-integer programs for policy synthesis and verification. These methods apply to tasks such as maximizing reward while guaranteeing reachability, and synthesis can seek permissive controllers that retain multiple safe actions. A key tension is scaling computation to large models while accurately handling uncertainty and preserving useful choice for the controller.

Latest papers

10 papers2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Robust Counterfactuals for Markov Decision Processes under Statistical and Causal Uncertainties
Oct 14, 2026Jessica Lally, Milad Kazemi, Nicola PaolettiCounterfactual Explanations Markov Decision Processes
King’s College London London, United Kingdom · Durham University Durham, United Kingdom
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Oct 1, 2026Han Zhong, Yinyu YeRobust Markov Decision Processes Markov Decision Processes
Shanghai Jiao Tong University · Shanghai Jiao Tong University, SIMIS, and Stanford University
Risk-Aware General-Utility Markov Decision Processes
Jul 10, 2026Pedro P. Santos, Fábio Vital, Alberto Sardinha +1Markov Decision Processes Markov Models
INESC-ID · Instituto Superior Técnico, University of Lisbon · Pontifical Catholic University of Rio de Janeiro
Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Jun 23, 2026Corentin Pla, Hugo Richard, Marc Abeille +1Markov Decision Processes Reinforcement Learning
CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team
Context-Aware Optimization of Follow-Up Intervals for Type 2 Diabetes Care Using Markov Decision Processes
Jun 17, 2026Parisa Lotfibagha, Kristen Miller, William J. Gallagher +2Markov Decision Processes Healthcare
University of Massachusetts Amherst, United States · MedStar Health Center for Diagnostic Systems Safety, United States · National Center for Human Factors in Healthcare, MedStar Health Research Institute, United States +2
Maturing Markov Decision Processes: Decision Making under Increasing Information and Shrinking Action Sets
Jun 17, 2026Jiaxi Liu, Aiping Yang, Yuhang Yang +4Markov Decision Processes Markov Models
Ant International · School of Economics, Sichuan University · School of Economics, Fudan University
MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings
May 17, 2026Himchan Hwang, Hyeokju Jeong, Gene Chung +3Markov Decision Processes Meta-Reinforcement Learning
Seoul National University · Saige · Ulsan National Institute of Science and Technology (UNIST)
On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
May 6, 2026Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir +1Markov Decision Processes Markov Models
Indian Institute of Technology Bombay · Mumbai, India
Adaptive Estimation and Optimal Control in Offline Contextual MDPs without Stationarity
May 5, 2026Riddhiman Bhattacharyya, Sayak Chakrabarty, Imon BanerjeeNon-Stationary RL Markov Decision Processes
Department of Statistics, University of California, Santa Cruz Santa Cruz, California, USA · Department of Computer Science Northwestern University Evanston, IL, USA · Department of Industrial Engineering and Management Sciences Northwestern University Evanston, IL, USA
Optimization-Based Robust Permissive Synthesis for Interval MDPs
Oct 3, 2025Khang Vo Huynh, David Parker, Lu FengRobust Markov Decision Processes Markov Decision Processes
Department of Computer Science, University of Virginia, Charlottesville, VA, USA · Department of Computer Science, University of Oxford, Oxford, UK

Oct 14, 2026J/K move · Enter open · S save

Robust Counterfactuals for Markov Decision Processes under Statistical and Causal Uncertainties

Jessica Lally, Milad Kazemi, Nicola Paoletti

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

Counterfactual Explanations Markov Decision Processes Robust Markov Decision Processes Interval Markov Decision Processes

Open paper AskPDF arXiv

Counterfactual reasoning (asking what would have happened, had a decision been different) is a powerful tool for identifying causes of failure and explaining the behaviour of AI systems in sequential decision-making tasks. In Markov Decision Processes (MDPs), two sources of uncertainty complicate counterfactual inference: statistical uncertainty in the MDP transitions when the MDP is estimated from trajectory data, and uncertainty about the unknown causal model, as there are multiple structural causal models (SCMs) compatible with each MDP. Existing work addresses these two challenges in isolation. We address both simultaneously by introducing a framework for partial counterfactual inference in MDPs that is robust to both statistical and causal uncertainty. Our approach provides: 1) closed-form analytical bounds for the counterfactual probabilities that are valid across all SCMs entailed by a given interval MDP (IMDP); 2) a method to compute minimal robust interventions to achieve a desired counterfactual outcome via pessimistic value iteration on the induced counterfactual IMDP. Since the latter is constructed using our analytical bounds, our approach remains efficient and scalable to realistic MDP environments. Experiments across multiple case studies demonstrate our method's robustness and practical utility for identifying minimal sets of actions that, if changed, would have led to improved outcomes.