Partially Observable Markov Decision Processes

Ask about this topic

Overview

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

CardsList

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

Apr 16, 2026

POMDP-based Object Search with Growing State Space and Hybrid Action Domain

Efficiently locating target objects in complex indoor environments with diverse furniture, such as shelves, tables, and beds, is a significant challenge for mobile robots. This difficulty arises from factors like localization errors, limited fields of view, and visual occlusion. We address this by framing the object-search task as a highdimensional Partially Observable Markov Decision Process (POMDP) with a growing state space and hybrid (continuous and discrete) action spaces in 3D environments. Based on a meticulously designed perception module, a novel online POMDP solver named the growing neural process filtered k-center clustering tree (GNPF-kCT) is proposed to tackle this problem. Optimal actions are selected using Monte Carlo Tree Search (MCTS) with belief tree reuse for growing state space, a neural process network to filter useless primitive actions, and k-center clustering hypersphere discretization for efficient refinement of high-dimensional action spaces. A modified upper-confidence bound (UCB), informed by belief differences and action value functions within cells of estimated diameters, guides MCTS expansion. Theoretical analysis validates the convergence and performance potential of our method. To address scenarios with limited information or rewards, we also introduce a guessed target object with a grid-world model as a key strategy to enhance search efficiency. Extensive Gazebo simulations with Fetch and Stretch robots demonstrate faster and more reliable target localization than POMDP-based baselines and state-of-the-art (SOTA) non-POMDP-based solvers, especially large language model (LLM) based methods, in object search under the same computational constraints and perception systems. Real-world tests in office environments confirm the practical applicability of our approach. Project page: https://sites.google.com/view/gnpfkct.

Yongbo Chen, Hesheng Wang, Shoudong Huang +1

School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai, 200240, People’s Republic of China · School of Computing, Australian National University (ANU), Canberra, ACT, 2601, Australia (The main part of this work is completed at ANU) · Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, 200240, People’s Republic of China +1

Mobile RoboticsMonte Carlo Tree SearchRoboticsPartially Observable Markov Decision ProcessesRobotic Object Search
AskPDF
Apr 13, 2026

Olfactory pursuit: catching a moving odor source in complex flows

Locating and intercepting a moving target from possibly delayed, intermittent sensory signals is a paradigmatic problem in decision-making under uncertainty, and a fundamental challenge for, e.g., animals seeking prey or mates and autonomous robotic systems. Odor signals are intermittent, strongly mixed by turbulent-like transport, and typically lag behind the true target position, thereby complicating localization. Here, we formulate olfactory pursuit as a partially observable Markov decision process in which an agent maintains a joint belief over the target's position and velocity. Using a discrete run-and-tumble model, we compute quasi-optimal policies by numerically solving the Bellman equation and benchmark them against well-established information-theoretic strategies such as Infotaxis. We show that purely exploratory policies are near-optimal when the target frequently reorients, but fail dramatically when the target exhibits persistent motion. We thus introduce a computationally efficient hybrid policy that combines the information-gain drive of Infotaxis with a "greedy" value function derived from an associated fully observable control problem. Our heuristic achieves near-optimal performance across all persistence times and substantially outperforms purely exploratory approaches. Moreover, our proposal demonstrates strong robustness even in more complex search scenarios, including continuous run-and-tumble prey motion with moderate persistence time, model mismatch, and more accurate plume dynamics representation. Our results identify predictive inference of target motion as the key ingredient for effective olfactory pursuit and provide a general framework for search in information-poor, dynamically evolving environments.

Maurizio Carbone, Lorenzo Piro, Robin A. Heinonen +3

Istituto dei Sistemi Complessi, CNR, Via dei Taurini 19, 00185 Rome, Italy and INFN “Tor Vergata", Via della Ricerca Scientifica 1, 00133 Rome, Italy · Department of Physics & INFN, Tor Vergata University of Rome, Via della Ricerca Scientifica 1, 00133 Rome, Italy · Machine Learning Genoa Center (MaLGa) & Department of Civil, Chemical and Environmental Engineering, University of Genoa, Genoa, Italy +2

Policy OptimizationPartially Observable Markov Decision Processes
AskPDF
Apr 10, 2026

Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment

When two agents of different computational capacities interact with the same environment, they need not compress a common semantic alphabet differently; they can induce different semantic alphabets altogether. We show that the quotient POMDP Qm,T(M)Q_{m,T}(M) - the unique coarsest abstraction consistent with an agent's capacity - serves as a capacity-derived semantic space for any bounded agent, and that communication between heterogeneous agents exhibits a sharp structural phase transition. Below a critical rate RcritR_{\text{crit}} determined by the quotient mismatch, intent-preserving communication is structurally impossible. In the supported one-way memoryless regime, classical side-information coding then yields exponential decay above the induced benchmark. Classical coding theorems tell you the rate once the source alphabet is fixed; our contribution is to derive that alphabet from bounded interaction itself. Concretely, we prove: (1) a fixed-ε\varepsilon structural phase-transition theorem whose lower bound is fully general on the common-history quotient comparison; (2) a one-way Wyner-Ziv benchmark identification on quotient alphabets, with exact converse, exact operational equality for memoryless quotient sources, and an ergodic long-run bridge via explicit mixing bounds; (3) an asymptotic one-way converse in the shrinking-distortion regime ε=O(1/T)\varepsilon = O(1/T), proved from the message stream and decoder side information; and (4) alignment traversal bounds enabling compositional communication through intermediate capacity levels. Experiments on eight POMDP environments (including RockSample(4,4)) illustrate the phase transition, a structured-policy benchmark shows the one-way rate can drop by up to 19×19\times relative to the counting bound, and a shrinking-distortion sweep matches the regime of the asymptotic converse.

Anthony T. Nixon

Multi-Agent CommunicationTask-Oriented Semantic CommunicationRate-Distortion TheoryPartially Observable Markov Decision Processes
AskPDF
Apr 10, 2026

Risk-seeking conservative policy iteration with agent-state based policies for Dec-POMDPs with guaranteed convergence

Optimally solving decentralized decision-making problems modeled as Dec-POMDPs is known to be NEXP-complete. These optimal solutions are policies based on the entire history of observations and actions of an agent. However, some applications may require more compact policies because of limited compute capabilities, which can be modeled by considering a limited number of memory states (or agent states). While such an agent-state based policy class may not contain the optimal solution, it is still of practical interest to find the best agent-state policy within the class. We focus on an iterated best response style algorithm which guarantees monotonic improvements and convergence to a local optimum in polynomial runtime in the Dec-POMDP model size. In order to obtain a better local optimum, we use a modified objective which incentivizes risk-seeking alongside a conservative policy iteration update. Our empirical results show that our approach performs as well as state-of-the-art approaches on several benchmark Dec-POMDPs, achieving near-optimal performance while having polynomial runtime despite the limited memory. We also show that using more agent states (a larger memory) leads to greater performance. Our approach provides a novel way of incorporating memory constraints on the agents in the Dec-POMDP problem.

Amit Sinha, Matthieu Geist, Aditya Mahajan

Department of Electrical and Computer Engineering, McGill University, Montreal, Quebec · Earth Species Project

Partially Observable Markov Decision ProcessesPolicy Iteration
AskPDF
Apr 9, 2026

PriPG-RL: Privileged Planner-Guided Reinforcement Learning for Partially Observable Systems with Anytime-Feasible MPC

This paper addresses the problem of training a reinforcement learning (RL) policy under partial observability by exploiting a privileged, anytime-feasible planner agent available exclusively during training. We formalize this as a Partially Observable Markov Decision Process (POMDP) in which a planner agent with access to an approximate dynamical model and privileged state information guides a learning agent that observes only a lossy projection of the true state. To realize this framework, we introduce an anytime-feasible Model Predictive Control (MPC) algorithm that serves as the planner agent. For the learning agent, we propose Planner-to-Policy Soft Actor-Critic (P2P-SAC), a method that distills the planner agent's privileged knowledge to mitigate partial observability and thereby improve both sample efficiency and final policy performance. We support this framework with rigorous theoretical analysis. Finally, we validate our approach in simulation using NVIDIA Isaac Lab and successfully deploy it on a real-world Unitree Go2 quadruped navigating complex, obstacle-rich environments.

Mohsen Amiri, Mohsen Amiri, Ali Beikmohammadi +2

The authors are with the Department of Computer and System Science, Stockholm University, 11419 Stockholm, Sweden · The authors are with the School of Mechanical and Material Engineering, Washington State University, Pullman, WA 99164, USA

Partially Observable RLLearning Using Privileged InformationPartially Observable Markov Decision ProcessesModel Predictive Control
AskPDF
Apr 8, 2026

Generating Local Shields for Decentralised Partially Observable Markov Decision Processes

Multi-agent systems under partial observation often struggle to maintain safety because each agent's locally chosen action does not, in general, determine the resulting joint action. Shielding addresses this by filtering actions based on the current state, but most existing techniques either assume access to a shared centralised global state or employ memoryless local filters that cannot consider interaction history. We introduce a shield process algebra with guarded choice and recursion for specifying safe global behaviour in communication-free Dec-POMDP settings. From a shield process, we compile a process automaton, then a global Mealy machine as a safe joint-action filter, and finally project it to local Mealy machines whose states are belief-style subsets of the global Mealy machine states consistent with each agent's observations, and which output per-agent safe action sets. We implement the pipeline in Rust and integrate PRISM, the Probabilistic Symbolic Model Checker, to compute best- and worst-case safety probabilities independently of the agents' policies. A multi-agent path-finding case study demonstrates how different shield processes substantially reduce collisions compared to the unshielded baseline while exhibiting varying levels of expressiveness and conservatism.

Haoran Yang, Nobuko Yoshida

University of Oxford

Partially Observable Markov Decision ProcessesFormal Verification
AskPDF
Apr 6, 2026

Cross-fitted Proximal Learning for Model-Based Reinforcement Learning

Model-based reinforcement learning is attractive for sequential decision-making because it explicitly estimates reward and transition models and then supports planning through simulated rollouts. In offline settings with hidden confounding, however, models learned directly from observational data may be biased. This challenge is especially pronounced in partially observable systems, where latent factors may jointly affect actions, rewards, and future observations. Recent work has shown that policy evaluation in such confounded partially observable Markov decision processes (POMDPs) can be reduced to estimating reward-emission and observation-transition bridge functions satisfying conditional moment restrictions (CMRs). In this paper, we study the statistical estimation of these bridge functions. We formulate bridge learning as a CMR problem with nuisance objects given by a conditional mean embedding and a conditional density. We then develop a KK-fold cross-fitted extension of the existing two-stage bridge estimator. The proposed procedure preserves the original bridge-based identification strategy while using the available data more efficiently than a single sample split. We also derive an oracle-comparator bound for the cross-fitted estimator and decompose the resulting error into a Stage I term induced by nuisance estimation and a Stage II term induced by empirical averaging.

Nishanth Venkatesh, Andreas A. Malikopoulos

Department of Systems Engineering, Cornell University, Ithaca, NY, USA · Applied Mathematics, Systems Engineering, Mechanical Engineering, Electrical & Computer Engineering, and School of Civil & Environmental Engineering, Cornell University, Ithaca, NY, USA

Cross-FittingReinforcement LearningModel-Based RLOffline RLPartially Observable Markov Decision Processes
AskPDF
Apr 4, 2026

Communication Gain and Delay Cost Under Cross-Timestep Delays in Cooperative Multi-Agent Reinforcement Learning

Communication is essential for coordination in cooperative multi-agent reinforcement learning under partial observability, yet cross-timestep delays cause messages to arrive multiple timesteps after generation, inducing temporal misalignment and making information stale when consumed. We formalize this setting as a delayed-communication partially observable Markov game (DeComm-POMG) and decompose a message's effect into communication gain and delay cost, yielding the Communication Gain and Delay Cost (CGDC) metric. We further establish a value-loss bound showing that the degradation induced by delayed messages is upper-bounded by a discounted accumulation of an information gap between the action distributions induced by timely versus delayed messages. Guided by CGDC, we propose CDCMA, an actor--critic framework that requests messages only when predicted CGDC is positive, predicts future observations to reduce misalignment at consumption, and fuses delayed messages via CGDC-guided attention. Experiments on no-teammate-vision variants of Cooperative Navigation and Predator Prey, and on SMAC maps across multiple delay levels show consistent improvements in performance, robustness, and generalization, with ablations validating each component.

Zihong Gao, Hongjian Liang, Lei Hao +1

The State Key Laboratory for Manufacturing Systems Engineering School of Automation Science and Engineering, Xi’an Jiaotong University

Partially Observable Markov Decision ProcessesMulti-Agent CommunicationCooperative MARL
AskPDF
Apr 1, 2026

Belief-State RWKV for Reinforcement Learning under Partial Observability

We propose a stronger formulation of RL on top of RWKV-style recurrent sequence models, in which the fixed-size recurrent state is explicitly interpreted as a belief state rather than an opaque hidden vector. Instead of conditioning policy and value on a single summary h_t, we maintain a compact uncertainty-aware state b_t = (μ_t, Σ_t) derived from RWKV-style recurrent statistics and let control depend on both memory and uncertainty. This design targets a key weakness of plain fixed-state policies in partially observed settings: they may store evidence, but not necessarily confidence. We present the method, a theoretical program, and a pilot RL experiment with hidden episode-level observation noise together with a test-time noise sweep. The pilot shows that belief-state policies nearly match the best recurrent baseline overall while slightly improving return on the hardest in-distribution regime and under a held-out noise shift. Additional ablations show that this simple belief readout is currently stronger than two more structured extensions, namely gated memory control and privileged belief targets, underscoring the need for richer benchmarks.

Liu Xiao

Reinforcement LearningPartially Observable RLPartially Observable Markov Decision Processes
AskPDF
Apr 1, 2026

Leveraging the Value of Information in POMDP Planning

Partially observable Markov decision processes (POMDPs) offer a principled formalism for planning under state and transition uncertainty. Despite advances made towards solving large POMDPs, obtaining performant policies under limited planning time remains a major challenge due to the curse of dimensionality and the curse of history. For many POMDP problems, the value of information (VOI) - the expected performance gain from reasoning about observations - varies over the belief space. We introduce a dynamic programming framework that exploits this structure by conditionally processing observations based on the value of information at each belief. Building on this framework, we propose Value of Information Monte Carlo planning (VOIMCP), a Monte Carlo Tree Search algorithm that allocates computational effort more efficiently by selectively disregarding observation information when the VOI is low, avoiding unnecessary branching of observations. We provide theoretical guarantees on the near-optimality of our VOI reasoning framework and derive non-asymptotic convergence bounds for VOIMCP. Simulation evaluations demonstrate that VOIMCP outperforms baselines on several POMDP benchmarks.

Zakariya Laouar, Qi Heng Ho, Zachary Sunberg

Department of Aerospace Engineering Sciences, University of Colorado Boulder · Kevin T. Crofton Department of Aerospace and Ocean Engineering, Virginia Tech

Partially Observable Markov Decision ProcessesBelief-Space PlanningValue of InformationMonte Carlo Tree SearchDynamic Programming
AskPDF
Apr 1, 2026

Open-loop POMDP Simplification and Safe Skipping of Replanning with Formal Performance Guarantees

Partially Observable Markov Decision Processes (POMDPs) provide a principled mathematical framework for decision-making under uncertainty. However, the exact solution to POMDPs is computationally intractable. In this paper, we address the computational intractability by introducing a novel framework for adaptive open-loop simplification with formal performance guarantees. Our method adaptively interleaves open-loop and closed-loop planning via a topology-based belief tree, enabling a significant reduction in planning complexity. The key contribution lies in the derivation of efficiently computable bounds which provide formal guarantees and can be used to ensure that our simplification can identify the immediate optimal action of the original POMDP problem. Our framework therefore provides computationally tractable performance guarantees for macro-actions within POMDPs. Furthermore, we propose a novel framework for safely skipping replanning during execution, supported by theoretical guarantees on multi-step open-loop action sequences. To the best of our knowledge, this framework is the first to address skipping replanning with formal performance guarantees. Practical online solvers for our proposed simplification are developed, including a sampling-based solver and an anytime solver. Empirical results demonstrate substantial computational speedups while maintaining provable performance guarantees, advancing the tractability and efficiency of POMDP planning.

Da Kong, Vadim Indelman

Technion - Israel Institute of Technology

Partially Observable Markov Decision ProcessesModel-Based PlanningBelief-Space Planning
AskPDF
Apr 1, 2026

Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs

We study model-based learning of finite-window policies in tabular partially observable Markov decision processes (POMDPs). A common approach to learning under partial observability is to approximate unbounded history dependencies using finite action-observation windows. This induces a finite-state Markov decision process (MDP) over histories, referred to as the superstate MDP. Once a model of this superstate MDP is available, standard MDP algorithms can be used to compute optimal policies, motivating the need for sample-efficient model estimation. Estimating the superstate MDP model is challenging because trajectories are generated by interaction with the original POMDP, creating a mismatch between the sampling process and target model. We propose a model estimation procedure for tabular POMDPs and analyze its sample complexity. Our analysis exploits a connection between filter stability and concentration inequalities for weakly dependent random variables. As a result, we obtain tight sample complexity guarantees for estimating the superstate MDP model from a single trajectory. Combined with value iteration, this yields approximately optimal finite-window policies for the POMDP.

Philip Jordan, Maryam Kamgarpour

SYCAMORE group, Institute of Mechanical Engineering, EPFL Switzerland.

Partially Observable Markov Decision ProcessesPolicy LearningModel-Based RLSample-Efficient RL
AskPDF
Apr 1, 2026

Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games

This letter studies multi-agent reinforcement learning in partially observable Markov potential games. Solving this problem is challenging due to partial observability, decentralized information, and the curse of dimensionality. First, to address the first two challenges, we leverage the common information framework, which allows agents to act based on both shared and local information. Second, to ensure tractability, we study an internal state that compresses accumulated information, preventing it from growing unboundedly over time. We then implement an internal state-based natural policy gradient method to find Nash equilibria of the Markov potential game. Our main contribution is to establish a non-asymptotic convergence bound for this method. Our theoretical bound decomposes into two interpretable components: a statistical error term that also arises in standard Markov potential games, and an approximation error capturing the use of finite-state controllers. Finally, simulations across multiple partially observable environments demonstrate that the proposed method using finite-state controllers achieves consistent improvements in performance compared to the setting where only the current observation is used.

Wonseok Yang, Thinh T. Doan

University of Texas at Austin, Austin, TX, 78712 USA

Natural Policy GradientMulti-Agent Reinforcement LearningPartially Observable Stochastic GamesPolicy GradientGame TheoryPartially Observable Markov Decision Processes
AskPDF
Mar 22, 2026

The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability

Any capacity-limited observer induces a canonical quotient on its environment: two situations that no bounded agent can distinguish are, for that agent, the same. We formalise this for finite POMDPs. A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories and a probe-exact quotient merging histories that no controller in the family can distinguish. The quotient is canonical, minimal, and unique-a bounded-interaction analogue of the Myhill-Nerode theorem. For clock-aware probes, it is exactly decision-sufficient for objectives that depend only on the agent's observations and actions; for latent-state rewards, we use an observation-Lipschitz approximation bound. The main theorem object is the clock-aware quotient; scalable deterministic-stationary experiments study a tractable coarsening with gap measured on small exact cases and explored empirically at larger scale. We validate theorem-level claims on Tiger and GridWorld. We also report operational case studies on Tiger, GridWorld, and RockSample as exploratory diagnostics of approximation behavior and runtime, not as theorem-facing evidence when no exact cross-family certificate is available; heavier stress tests are archived in the appendix and artifact package.

Anthony T. Nixon

DefSig

Partially Observable Markov Decision Processes
AskPDF
Mar 19, 2026

Fundamental Limits for Sensor-Based Control via the Gibbs Variational Principle

Fundamental limits on the performance of feedback controllers are essential for benchmarking algorithms, guiding sensor selection, and certifying task feasibility -- yet few general-purpose tools exist for computing them. Existing information-theoretic approaches overestimate the information a sensor must provide by evaluating it against the uncontrolled system, producing bounds that degrade precisely when feedback is most valuable. We derive a lower bound on the minimum expected cost of any causal feedback controller under partial observations by applying the Gibbs variational principle to the joint path measure over states and observations. The bound applies to nonlinear, nonholonomic, and hybrid dynamics with unbounded costs and admits a self-consistent refinement: any good controller concentrates the state, which limits the information the sensor can extract, which tightens the bound. The resulting fixed-point equation has a unique solution computable by bisection, and we provide conditions under which the free energy minimization is provably convex, yielding a certifiably correct numerical bound. On a scalar LQG problem the self-consistent bound captures over 80% of the known optimal cost at moderate sensor noise, and on a nonlinear Dubins car tracking problem it remains informative across all noise levels where a bound using the uncontrolled state distribution is vacuous.

Vincent Pacelli, Evangelos A. Theodorou

Daniel Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA, 30308

Feedback ControlPartially Observable Markov Decision ProcessesOptimal Control
AskPDF
Mar 12, 2026

A Semi-Decentralized Approach to Multiagent Control

We introduce an expressive framework and algorithms for the semi-decentralized control of cooperative agents in environments with communication uncertainty. Whereas semi-Markov control admits a distribution over time for agent actions, semi-Markov communication, or what we refer to as semi-decentralization, gives a distribution over time for what actions and observations agents can store in their histories. We extend semi-decentralization to the partially observable Markov decision process (POMDP). The resulting SDec-POMDP unifies decentralized and multiagent POMDPs and several existing explicit communication mechanisms. We present recursive small-step semi-decentralized A* (RS-SDA*), an exact algorithm for generating optimal SDec-POMDP policies. RS-SDA* is evaluated on semi-decentralized versions of several standard benchmarks and a maritime medical evacuation scenario. This paper provides a well-defined theoretical foundation for exploring many classes of multiagent communication problems through the lens of semi-decentralization.

Mahdi Al-Husseini, Mykel J. Kochenderfer, Kyle H. Wray

Stanford University Stanford, United States · Northeastern University Boston, United States

Multi-Agent ControlMulti-Agent CommunicationPartially Observable Markov Decision Processes
AskPDF
Mar 11, 2026

Safety-critical Control Under Partial Observability: Reach-Avoid POMDP meets Belief Space Control

Partially Observable Markov Decision Processes (POMDPs) provide a principled framework for robot decision-making under uncertainty. Solving reach-avoid POMDPs, however, requires coordinating three distinct behaviors: goal reaching, safety, and active information gathering to reduce uncertainty. Existing online POMDP solvers attempt to address all three within a single belief tree search, but this unified approach struggles with the conflicting time scales inherent to these objectives. We propose a layered, certificate-based control architecture that operates directly in belief space, decoupling goal reaching, information gathering, and safety into modular components. We introduce Belief Control Lyapunov Functions (BCLFs) that formalize information gathering as a Lyapunov convergence problem in belief space, and show how they can be learned via reinforcement learning. For safety, we develop Belief Control Barrier Functions (BCBFs) that leverage conformal prediction to provide probabilistic safety guarantees over finite horizons. The resulting control synthesis reduces to lightweight quadratic programs solvable in real time, even for non-Gaussian belief representations with dimension >104>10^4. Experiments in simulation and on a space-robotics platform demonstrate real-time performance and improved safety and task success compared to state-of-the-art constrained POMDP solvers.

Matti Vahs, Joris Verhagen, Jana Tumova

Division of Robotics, Perception and Learning, KTH Royal Institute of Technology, Stockholm, Sweden · Digital Futures

Control Lyapunov FunctionsPartially Observable Markov Decision ProcessesBelief-Space PlanningControl Barrier FunctionsLyapunov-Based Control
AskPDF
Mar 5, 2026

LEGS-POMDP: Language and Gesture-Guided Object Search in Partially Observable Environments

To assist humans in open-world environments, robots must interpret ambiguous instructions to locate desired objects. Foundation model-based approaches excel at multimodal grounding, but they lack a principled mechanism for modeling uncertainty in long-horizon tasks. In contrast, Partially Observable Markov Decision Processes (POMDPs) provide a systematic framework for planning under uncertainty but are often limited in supported modalities and rely on restrictive environment assumptions. We introduce LanguagE and Gesture-Guided Object Search in Partially Observable Environments (LEGS-POMDP), a modular POMDP system that integrates language, gesture, and visual observations for open-world object search. Unlike prior work, LEGS-POMDP explicitly models two sources of partial observability: uncertainty over the target object's identity and its spatial location. In simulation, multimodal fusion significantly outperforms unimodal baselines, achieving an average success rate of 89% across challenging environments and object categories. Finally, we demonstrate the full system on a quadruped mobile manipulator, where real-world experiments qualitatively validate robust multimodal perception and uncertainty reduction under ambiguous instructions.

Ivy Xiao He, Stefanie Tellex, Jason Xinyu Liu

Brown University Providence, USA

Partially Observable Markov Decision ProcessesUncertainty-Aware Multimodal FusionMobile RoboticsRobotic Perception
AskPDF
Mar 4, 2026

Principled Learning-to-Communicate with Quasi-Classical Information Structures

Learning-to-communicate (LTC) in partially observable environments has received increasing attention in deep multi-agent reinforcement learning, where the control and communication strategies are jointly learned. Meanwhile, the impact of communication on decision-making has been extensively studied in control theory. In this paper, we seek to formalize and better understand LTC by bridging these two lines of work, through the lens of information structures (ISs). To this end, we formalize LTC in decentralized partially observable Markov decision processes (Dec-POMDPs) under the common-information-based framework from decentralized stochastic control, and classify LTC problems based on the ISs before (additional) information sharing. We first show that non-classical LTCs are computationally intractable in general, and thus focus on quasi-classical (QC) LTCs. We then propose a series of conditions for QC LTCs, under which LTC preserves the QC IS after information sharing, whereas violating them can cause computational hardness in general. Further, we develop provable planning and learning algorithms for QC LTCs, and establish quasi-polynomial time and sample complexities for several QC LTC examples that satisfy the above conditions. Along the way, we also establish new results on a relationship between (strictly) QC IS and the condition of having strategy-independent common-information-based beliefs (SI-CIBs), as well as on solving Dec-POMDPs without computationally intractable oracles but beyond those with SI-CIBs, which may be of independent interest.

Xiangyu Liu, Haoyi You, Kaiqing Zhang

University of Maryland, College Park, MD, USA, 20742

Multi-Agent CommunicationDecentralized MARLPartially Observable Markov Decision ProcessesEmergent Communication
AskPDF
Mar 3, 2026

A Covering Framework for Offline POMDPs Learning using Belief Space Metric

In off policy evaluation (OPE) for partially observable Markov decision processes (POMDPs), an agent must infer hidden states from past observations, which exacerbates both the curse of horizon and the curse of memory in existing OPE methods. This paper introduces a novel covering analysis framework that exploits the intrinsic metric structure of the belief space (distributions over latent states) to relax traditional coverage assumptions. By assuming value relevant functions are Lipschitz continuous in the belief space, we derive error bounds that mitigate exponential blow ups in horizon and memory length. Our unified analysis technique applies to a broad class of OPE algorithms, yielding concrete error bounds and coverage requirements expressed in terms of belief space metrics rather than raw history coverage. We illustrate the improved sample efficiency of this framework via case studies: the double sampling Bellman error minimization algorithm, and the memory based future dependent value functions (FDVF). In both cases, our coverage definition based on the belief space metric yields tighter bounds.

Youheng Zhu, Yiping Lu

Northwestern University

Off-Policy EvaluationOffline RLPartially Observable Markov Decision ProcessesSample-Efficient RL
AskPDF
Mar 2, 2026

Strategic Shaping of Human Prosociality: A Latent-State POMDP Framework

We propose a decision-theoretic framework in which a robot strategically can shape inferred human's prosocial state during repeated interactions. Modeling the human's prosociality as a latent state that evolves over time, the robot learns to infer and influence this state through its own actions, including helping and signaling. We formalize this as a latent-state POMDP with limited observations and learn the transition and observation dynamics using expectation maximization. The resulting belief-based policy balances task and social objectives, selecting actions that maximize long-term cooperative outcomes. We evaluate the model using data from user studies and show that the learned policy outperforms baseline strategies in both team performance and increasing observed human cooperative behavior.

Zahra Zahedi, Xinyue Hu, Shashank Mehrotra +2

Honda Research Institute USA, Inc. · Department of Cognitive Science, University of California, Irvine.

Human-Robot CollaborationPartially Observable Markov Decision Processes
AskPDF
Feb 28, 2026

QANTIS: A Hardware-Validated Quantum Platform for POMDP Planning and Multi-Target Data Association

Autonomous navigation under uncertainty requires solving partially observable Markov decision processes (POMDPs) for planning and assigning sensor measurements to tracked targets--a task known as multi-target data association (MTDA). Both problems become computationally demanding at scale: belief conditioning costs O(P(e)−1)\mathcal{O}(P(e)^{-1}) per node under rare evidence, while MTDA is NP-hard. Quantum amplitude amplification can quadratically reduce the belief-update query cost to O(P(e)−1/2)\mathcal{O}(P(e)^{-1/2}), while QUBO reformulations expose MTDA to quantum and quantum-inspired optimisation heuristics. We present QANTIS, a modular platform that integrates quantum belief update (Grover amplitude amplification and BIQAE), QUBO-based data association via FPC-QAOA, and composable error mitigation, and we report a 45-experiment hardware study on three IBM Heron backends. On hardware, a single Grover iterate applied to a Tiger belief oracle amplifies a rare observation probability from 0.1790.179 to 0.9070.907 (5.1×5.1\times; ISA 18) while preserving the Bayesian posterior (Hellinger 0.00150.0015), increasing usable-shot yield from 1,463 to 7,429. We interpret this as a hardware validation of the quadratic query-complexity mechanism at k=1k=1 with posterior preservation, rather than a wall-clock advantage claim. We further demonstrate, to our knowledge, the first closed-loop hybrid quantum-classical Tiger POMDP on superconducting hardware (T=8T=8, max Hellinger below 0.0150.015), and empirically characterise NISQ feasibility boundaries: ZNE-based error mitigation is beneficial below ISA ≈100\approx 100 and harmful above ISA ≳1,000\gtrsim 1{,}000; FPC-QAOA is meaningful at ≤15\leq 15 QUBO variables (ISA ≲450\lesssim 450). These results characterise practical operating regimes on current superconducting hardware rather than wall-clock quantum advantage at today's problem scales.

Bayram Yüksel Eker, Suayb S. Arslan, Özgür Nazlı +2

Neura Parse Ltd., London, United Kingdom · Department of Computer Engineering, Boğaziçi University, Istanbul, Turkey · İzmir Ekonomi Üniversitesi, İzmir, Turkey +2

Partially Observable Markov Decision ProcessesMulti-Object TrackingQuantum Approximate Optimization AlgorithmQuantum Error Mitigation
AskPDF
Feb 26, 2026

Planning under Distribution Shifts with Causal POMDPs

In the real world, planning is often challenged by distribution shifts. As such, a model of the environment obtained under one set of conditions may no longer remain valid as the distribution of states or the environment dynamics change, which in turn causes previously learned strategies to fail. In this work, we propose a theoretical framework for planning under partial observability using Partially Observable Markov Decision Processes (POMDPs) formulated using causal knowledge. By representing shifts in the environment as interventions on this causal POMDP, the framework enables evaluating plans under hypothesized changes and actively identifying which components of the environment have been altered. We show how to maintain and update a belief over both the latent state and the underlying domain, and we prove that the value function remains piecewise linear and convex (PWLC) in this augmented belief space. Preservation of PWLC under distribution shifts has the advantage of maintaining the tractability of planning via αα-vector-based POMDP methods.

Matteo Ceriscioli, Karthika Mohan

Causal Intelligence and Reasoning Lab, Oregon State University, Corvallis, OR 97331, USA

Partially Observable Markov Decision ProcessesBelief-Space Planning
AskPDF
Feb 26, 2026

Accelerated Online Risk-Averse Policy Evaluation in POMDPs with Theoretical Guarantees and Novel CVaR Bounds

Risk-averse decision-making under uncertainty in partially observable domains is a central challenge in artificial intelligence and is essential for developing reliable autonomous agents. The formal framework for such problems is the partially observable Markov decision process (POMDP), where risk sensitivity is introduced through a risk measure applied to the value function, with Conditional Value-at-Risk (CVaR) being a particularly significant criterion. However, solving POMDPs is computationally intractable in general, and approximate methods rely on computationally expensive simulations of future agent trajectories. This work introduces a theoretical framework for accelerating CVaR value function evaluation in POMDPs with formal performance guarantees. We derive new bounds on the CVaR of a random variable X using an auxiliary random variable Y, under assumptions relating their cumulative distribution and density functions; these bounds yield interpretable concentration inequalities and converge as the distributional discrepancy vanishes. Building on this, we establish upper and lower bounds on the CVaR value function computable from a simplified belief-MDP, accommodating general simplifications of the transition dynamics. We develop estimators for these bounds within a particle-belief MDP framework with probabilistic guarantees, and employ them for acceleration via action elimination: actions whose bounds indicate suboptimality under the simplified model are safely discarded while ensuring consistency with the original POMDP. Empirical evaluation across multiple POMDP domains confirms that the bounds reliably separate safe from dangerous policies while achieving substantial computational speedups under the simplified model.

Yaacov Pariente, Vadim Indelman

Technion - Israel Institute of Technology, Israel

Partially Observable Markov Decision ProcessesPolicy EvaluationRisk-Sensitive RLConditional Value-at-Risk
AskPDF
Feb 24, 2026

POMDPPlanners: Open-Source Package for POMDP Planning

We present POMDPPlanners, an open-source Python package for empirical evaluation of Partially Observable Markov Decision Process (POMDP) planning algorithms. The package integrates state-of-the-art planning algorithms, a suite of benchmark environments with safety-critical variants, automated hyperparameter optimization via Optuna, persistent caching with failure recovery, and configurable parallel simulation -- reducing the overhead of extensive simulation studies. POMDPPlanners is designed to enable scalable, reproducible research on decision-making under uncertainty, with particular emphasis on risk-sensitive settings where standard toolkits fall short.

Yaacov Pariente, Vadim Indelman

Faculty of Mathematics, Technion - Israel Institute of Technology, Haifa 3200003, Israel · Stephen B. Klein Faculty of Aerospace Engineering, Faculty of Data and Decision Sciences, Technion - Israel Institute of Technology, Haifa 3200003, Israel

Partially Observable Markov Decision ProcessesDecision-Making under UncertaintyBelief-Space Planning
AskPDF
Feb 24, 2026

Probing Dec-POMDP Reasoning in Cooperative MARL

Cooperative multi-agent reinforcement learning (MARL) is typically framed as a decentralised partially observable Markov decision process (Dec-POMDP), a setting whose hardness stems from two key challenges: partial observability and decentralised coordination. Genuinely solving such tasks requires Dec-POMDP reasoning, where agents use history to infer hidden states and coordinate based on local information. Yet it remains unclear whether popular benchmarks actually demand this reasoning or permit success via simpler strategies. We introduce a diagnostic suite combining statistically grounded performance comparisons and information-theoretic probes to audit the behavioural complexity of baseline policies (IPPO and MAPPO) across 37 scenarios spanning MPE, SMAX, Overcooked, Hanabi, and MaBrax. Our diagnostics reveal that success on these benchmarks rarely requires genuine Dec-POMDP reasoning. Reactive policies match the performance of memory-based agents in over half the scenarios, and emergent coordination frequently relies on brittle, synchronous action coupling rather than robust temporal influence. These findings suggest that some widely used benchmarks may not adequately test core Dec-POMDP assumptions under current training paradigms, potentially leading to over-optimistic assessments of progress. We release our diagnostic tooling to support more rigorous environment design and evaluation in cooperative MARL.

Kale-ab Tessera, Leonard Hinckeldey, Riccardo Zamboni +2

University of Edinburgh, Edinburgh, United Kingdom · Politecnico di Milano, Milan, Italy

Cooperative MARLMulti-Agent ReasoningMulti-Agent CoordinationPartially Observable Markov Decision ProcessesAI Agent Benchmarks
AskPDF
Jan 26, 2026

Toward Learning POMDPs Beyond Full-Rank Actions and State Observability

We are interested in enabling autonomous agents to learn and reason about systems with hidden states, such as locking mechanisms. We cast this problem as learning the parameters of a discrete Partially Observable Markov Decision Process (POMDP). The agent begins with knowledge of the POMDP's actions and observation spaces, but not its state space, transitions, or observation models. These properties must be constructed from a sequence of actions and observations. Spectral approaches to learning models of partially observable domains, such as Predictive State Representations (PSRs), learn representations of state that are sufficient to predict future outcomes. PSR models, however, do not have explicit transition and observation system models that can be used with different reward functions to solve different planning problems. Under a mild set of rankness assumptions on the products of transition and observation matrices, we show how PSRs learn POMDP matrices up to a similarity transform, and this transform may be estimated via tensor decomposition methods. Our method learns observation matrices and transition matrices up to a partition of states, where the states in a single partition have the same observation distributions corresponding to actions whose transition matrices are full-rank. Our numerical experiments suggest that explicit observation and transition likelihoods can be leveraged to generate new plans for different goals and reward functions after the model has been learned. We also show that learning a POMDP beyond a partition of states is impossible from sequential data by constructing two POMDPs that agree on all observation distributions but differ in their transition dynamics.

Seiji Shaw, Travis Manderson, Chad Kessens +1

MIT Computer Science and Artificial Intelligence Lab, 51 Vassar St, Cambridge, MA 02139, USA · DEVCOM Army Research Laboratory 2800 Powder Mill Road, Adelphi, MD 20783, USA

Partially Observable Markov Decision ProcessesPredictive State Representations
AskPDF
Oct 7, 2025

How Well Do Latent World Models Understand Partially Observable Safety Constraints?

Latent world models are a promising approach for learning state representations and dynamics directly from high-dimensional observations, enabling robot control in hard-to-model settings. However, control performance ultimately depends on the latent representation encoding the required information for the task. In this work, we study latent-space safe control problems and show how partial observability can induce control failures when safety-relevant information is not preserved in the latent state. Specifically, we identify two world model failure modes: estimation gaps, where current observations do not reveal safety-critical quantities (e.g., temperature in a cooking task), and prediction gaps, where failures are observable once they occur but cannot be reliably anticipated from available observations. We introduce two diagnostics for these gaps: a mutual-information-based measure of safety observability and a rollout-based measure of future safety predictability. Finally, we present mitigation strategies for each failure mode: privileged multimodal supervision for estimation gaps and conformal risk calibration for prediction gaps. Across two hardware case studies -- using unimodal RGB world models and multimodal RGB+Tactile and RGB+Thermal variants -- we show that these mitigation strategies improve the safety of a Franka Research 3 manipulator on challenging cooking tasks under partial observability, albeit with increased conservativeness. More broadly, our work raises the question of when world model state representations are sufficient for reliable robot control

Matthew Kim, Kensuke Nakamura, Andrea Bajcsy

UC San Diego · Carnegie Mellon University

Latent World ModelsRobot SafetyPartially Observable Markov Decision Processes
AskPDF
Oct 7, 2022

Stackelberg POMDP: Learning to Lead via Reinforcement Learning

Many real-world domains--including e-commerce platform design, security planning, and multi-agent coordination--feature leader-follower problems where one decision-maker commits to a policy and others react strategically. We develop a reinforcement learning framework for such interactions in sequential environments with partial observations and multiple followers. Followers may adapt through no-regret learning or reinforcement learning, potentially departing from equilibrium behavior. The framework embeds follower adaptation into the leader's environment to construct a single-agent partially observable Markov decision process--the Stackelberg POMDP. For policy-interactive response algorithms, which access the leader's policy through queries, we prove that an optimal policy based only on the leader's game history yields an optimal commitment under the specified response procedure. We use proximal policy optimization with a centralized critic and train contextual meta-followers to respond across leader policies. In indirect mechanism design, mechanisms using buyer messages achieve higher social welfare than optimal standard sequential price mechanisms across all tested type counts, with responses certified as approximate Bayesian coarse correlated equilibria. In platform design, learned display rules increase mean consumer surplus by 8.4% over an optimized fixed price cap while accommodating hidden seller costs. In Atari bilateral trade, meta-learned follower responses support joint learning of visual gameplay and economic decisions; assigning leadership to the seller or buyer shifts transaction prices and payoffs in that agent's favor. Controlled ablations examine how response credit, policy consistency, and reward timing affect learning.

Matthias Gerstgrasser, Gianluca Brero, Alon Eden +6

John A. Paulson School of Engineering and Applied Sciences, Harvard University · Data Science Initiative, Brown University · School of Computer Science and Engineering, Hebrew University of Jerusalem +2

Game-Theoretic RLReinforcement LearningMulti-Agent Reinforcement LearningPartially Observable Markov Decision ProcessesMechanism Design
AskPDF