Partially Observable Markov Decision Processes

Follow this topic Ask about this topic

Partially Observable Markov Decision Processes (POMDPs) model agents that must choose actions without directly observing the true state of a changing environment. A belief state—a probability distribution over possible states—turns hidden-state uncertainty into a basis for planning, using methods such as point-based value iteration, Monte Carlo tree search, and finite-state controllers. Learning approaches estimate models or beliefs from data, or use recurrent networks and world models; multi-agent and safety-critical settings add challenges such as communication limits, constraints, and risk. A central tension is making belief-space planning scalable while retaining reliable performance and guarantees, especially when observations are noisy, models are misspecified, or available histories do not identify the hidden state.

Latest papers

89 papers10 papers in the last four weeks, up 25% on the four weeks before. 0.1% of all new papers.

Performance Gaps Between Open-Loop, Certainty-Equivalent, and Optimal Control Under Action-Dependent Observations
Oct 24, 2026Leo Maynard-Zhang, Sunmook Choi, Yahya Sattar +3Stochastic Optimal Control Optimal Control
U Washington · Cornell · Imperial College London +1
Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games
Oct 19, 2026Durgam Latha, Dion Reji, Dorde Zikelic +1Partially Observable Stochastic Games Robust Partially Observable Markov Decision Processes
Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore
Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability
Oct 15, 2026Valentina Zaccaria, Philip Jordan, Tingting Ni +2Reinforcement Learning Constrained RL
University of Padova · SYCAMORE, EPFL
Planning Commitment of LLM under Partial Observability
Oct 15, 2026Cassie Huang, Zhanwei Cao, Yeawon Lee +6LLM Planning LLM Agent Safety
On Symmetry for Characterizing Agent Heterogeneity in Multi-Agent Systems
Oct 13, 2026Jianhong Wang, Jonathan LawryPartially Observable Stochastic Games Multi-Agent Systems
INFORMED-AI Hub, University of Bristol · School of Engineering Mathematics and Technology, University of Bristol
Belief Embedding Tree Search
Oct 10, 2026Christopher Solinas, Radovan Haluška, Martin Schmid +3Partially Observable RL Belief-Space Planning
University of Alberta · Charles University, Prague · EquiLibre Technologies, Inc. +1
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
Oct 10, 2026Eline M. Bovy, Caleb Probine, Marnix Suilen +2Robust Partially Observable Markov Decision Processes Partially Observable Markov Decision Processes
Radboud University Nijmegen, The Netherlands · The University of Texas at Austin Austin, USA · University of Antwerp Antwerp, Belgium +1
Does Learning Recurrent Networks Matter in Partially Observable RL?
Oct 9, 2026Zekang Wang, Zhe He, Gaojie JinPartially Observable RL Partially Observable Markov Decision Processes
University of Macau Macau SAR, China
Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Logging
Oct 4, 2026Youyu Luo, Pengzhan Zhou, Zhida Qin +4Off-Policy Evaluation Partially Observable Markov Decision Processes
Chongqing University · Beijing Institute of Technology · The Hong Kong Polytechnic University
Emergence, Not Bandwidth: Physical Coupling and the Limits of Learned Multi-Agent Communication
Sep 28, 2026Mihir Chauhan, Aniket BeraSequential MARL Partially Observable Markov Decision Processes
IDEAS Lab, Department of Computer Science Purdue University
Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees
Sep 26, 2026Yaacov Pariente, Vadim IndelmanRisk-Sensitive Planning Partially Observable Markov Decision Processes
Faculty of Mathematics Technion – Israel Institute of Technology Haifa, Israel · Stephen B. Klein Faculty of Aerospace Engineering; Faculty of Data and Decision Sciences Technion – Israel Institute of Technology Haifa, Israel
A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing
Sep 22, 2026Xiaoxing Ren, Thomas Parisini, Andreas A. MalikopoulosMarkov Decision Processes Linear Markov Decision Processes
School of Civil and Environmental Engineering, Cornell University, Ithaca, NY, USA · Dept. of Electrical and Electronic Engineering, Imperial College London, London SW7 2AZ, UK · Dept. of Electronic Systems, Aalborg University, Denmark +2
Reinforcement Learning under State and Outcome Uncertainty: A Foundational Distributional Perspective
Sep 21, 2026Larry Preuett, Qiuyi Zhang, Muhammad Aurangzeb AhmadDistributional RL Markov Decision Processes
University of Washington, Tacoma, USA · Google DeepMind, California, USA · University of Washington, Bothell, USA
SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting
Sep 17, 2026Hshmat Sahak, Aoran Jiao, Nicholas Rhinehart +1Robot Navigation Partially Observable Markov Decision Processes
University of Toronto Institute of Aerospace Studies (UTIAS)
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
Sep 16, 2026Pranaya JajooOff-Policy Evaluation Sample Complexity
University of Alberta
Adaptive Agent Design
Sep 11, 2026Raj Kiriti Velicheti, Subhonmesh Bose, Tamer BaşarReinforcement Learning Q-Learning
Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois, Urbana-Champaign, Urbana, IL 61801
Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability
Sep 9, 2026Arnab Chattopadhayay, Debdipta HalderBelief-Space Planning LLM Agents
Independent Researcher (UCL Alumni), Bangalore, India · Independent Researcher (IIT-Kharagpur Alumni), Bangalore, India
Scalable Rao-Blackwellized Online Planning for High-Dimensional POMDPs
Sep 1, 2026Jiho Lee, Nisar Ahmed, Kyle Hollins Wray +1Belief-Space Planning Partially Observable Markov Decision Processes
Ann And H.J. Smead Aerospace Engineering Sciences Department, University of Colorado Boulder, Boulder, CO, USA · Manning College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA
Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games
Aug 25, 2026Durgam Latha, Dion Reji, S. Akshay +2Robust Markov Decision Processes Partially Observable Stochastic Games
Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore
From Relaxed Indexability to Exact Indexability: A $t$ -Step Approach for Partially Observable Restless Bandits
Aug 25, 2026Keqin Liu, Qizhen JiaMulti-Armed Bandits Sequential Decision Making
The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting
Aug 18, 2026Nazlı Nur Karabulut, Tanya BraunPartially Observable Markov Decision Processes Multi-Agent Systems
Computer Science Department, University of Münster, Münster, Germany
Threshold Structure of Optimal Policies in Restart POMDPs
Aug 11, 2026Konstantin Avrachenkov, Alexey Piunovskiy, Yi ZhangSequential Decision Making Stochastic Optimal Control
Inria, France · Department of Mathematical Sciences, University of Liverpool, UK · School of Mathematics, University of Birmingham, UK
POMDPs for Autonomous Science Exploration
Aug 4, 2026Daniel Guirguis, Nathan Wallace, Hanna Kurniawati +1Belief-Space Planning AI for Science
Intention Inference Under Execution Noise: Separating Aleatoric and Epistemic Uncertainty in Social Dilemmas
Aug 3, 2026Kival Mahadew, Jonathan ShockSocial Dilemmas Partially Observable Markov Decision Processes
Dept. of Computer Science, University of Cape Town · Neuroscience Institute, University of Cape Town · Dept. of Mathematics & Applied Mathematics, University of Cape Town +2
Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes
Jul 29, 2026Zuyuan Zhang, Yongshan Chen, Mahdi Imani +1Markov Decision Processes Partially Observable RL
Department of Electrical and Computer Engineering, The George Washington University · Department of Electrical and Computer Engineering, Northeastern University
Semi-Decentralized Multi-Spacecraft Collision Avoidance under Communication Constraints
Jul 29, 2026Grace Ra Kim, Mahdi Al-Husseini, Duncan Eddy +1Collision Avoidance Partially Observable Markov Decision Processes
PhD Candidate, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305 · Post-Doctoral Researcher, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305 · Professor, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305
Beyond Fixed Goal Delivery: Online POMDP Planning for Target Interception in Crowds
Jul 20, 2026Himanshu Gupta, Kelvin Aladum, Nisar Ahmed +2Robot Navigation Safe Motion Planning
Dept. of Aerospace Engineering Sciences, University of Colorado Boulder, USA · Dept. of Computer Science, University of Colorado Boulder, USA
Learning-Driven Adaptive Audit Scheduling: A Sequential Decision Approach to Off-Chain Data Integrity
Jul 19, 2026Changting Lin, Fan Li, Weihang Yu +4Markov Decision Processes Deep Q-Learning
Hangzhou Yunphant Network Technology Co., Ltd., Hangzhou, China · Zhejiang University, Hangzhou, China · Central University of Finance and Economics, Beijing, China +2
Expected Free Energy as Belief-Dependent Utility for rho-POMDPs
Jul 18, 2026Patrick Cooper, Alvaro VelasquezFree Energy Calculation Active Inference
Department of Computer Science, University of Colorado Boulder, Boulder, CO, USA
STOCKTAKE: Measuring the Gap Between Perception and Action in LLM Agents with a Fair Oracle
Jul 15, 2026Sagar Deb, Ashwanth KrishnanInventory Control LLM Agent Evaluation
QpiAI

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

Performance Gaps Between Open-Loop, Certainty-Equivalent, and Optimal Control Under Action-Dependent Observations

Leo Maynard-Zhang, Sunmook Choi, Yahya Sattar, Yassir Jedra+2

U Washington · Cornell · Imperial College London+1

Stochastic Optimal Control Optimal Control Adaptive Control Partially Observable Markov Decision Processes Linear Quadratic Regulator

Open paper AskPDF arXiv

In dynamical systems, feedback can improve performance by allowing decisions to depend on past observations, rather than being designed a priori. Under full observation, the current state is sufficient for decision-making; under partial observation, the controller must instead estimate the state from measurements. When actions also affect observations, control can have a dual role: actions influence both the state and the information available for future decisions. This interaction can invalidate certainty-equivalent (CE) control, a widely used strategy that applies state feedback policies as if the estimated state were the true state. We ask when this suboptimality leads to a quantitative performance gap that grows with the horizon. We study this question in a linear-quadratic system with bilinear observations by comparing the optimal policy, certainty-equivalent control, and the optimal open-loop (OL) policy. We identify an instance-dependent information-strength parameter

q

and establish distinct performance regimes as

q

varies. When

q

is sufficiently small, we show that no policy can improve over OL control by more than

O(1)

cumulative cost. For large values of

q

, we find that CE achieves an

Ω(T)

advantage over OL control. Our main finding is that for intermediate values of

q

, we can construct a policy that occasionally probes for information and achieves an

Ω(T)

advantage over OL control while CE only achieves an

O(1)

advantage, establishing an

Ω(T)

gap between CE and optimal control. Our analysis relies on a regret decomposition that captures the tradeoff between the immediate cost of gathering information and its future benefit.