Partially Observable Markov Decision Processes

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 75% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 53

Oct 4, 2026cs.LG

Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Logging

Multi-step revealing can make off-policy evaluation tractable under memoryless logging. With history-dependent logging, state decodability and target-relevant evidence can separate. For every horizon

H\ge3

, we construct two exactly realizable POMDPs with four actions, at most four states per layer, a known logger, and a memoryless target. Action overlap, history coverage, and observation-only revealing remain bounded independently of

H

, yet the target values differ by

1/2

and the KL divergence between the logged laws is

Θ(4^{-(H-1)})

, forcing exponential sample complexity. Logger memory makes states distinguishable, while reset erases the model-distinguishing evidence preserved by the target. A separate construction retains this barrier with common, known observation-only revealing operators. Under action and history coverage, we give a finite-class OPE guarantee using common observable value representations that remain valid at every history. The sample bound depends polynomially on their second-moment cost. In the common-operator construction, the same value direction has constant marginal decoding cost but exponential history-conditioned cost. Finally, on a fixed four-action continuum, we derive matching passive and budgeted readout rates. With one known channel and unit read cost, early reads are optimal. With unknown sensor bias, early reads alone remain exponentially costly. Combining them with post-reset calibration gives sample complexity independent of

H

when both read types receive fixed positive expected budgets per trajectory.

Youyu Luo, Pengzhan Zhou, Zhida Qin +4

Chongqing University · Beijing Institute of Technology · The Hong Kong Polytechnic University

Off-Policy Evaluation Partially Observable Markov Decision Processes

Sep 28, 2026cs.LG

Emergence, Not Bandwidth: Physical Coupling and the Limits of Learned Multi-Agent Communication

Rate-limited multi-agent teams raise three questions the emergent-communication literature has answered only empirically: what an optimal message should encode, what compression costs over a horizon, and when a learned protocol is unique enough for a teammate to read. We answer them for rate-limited Dec-POMDPs, then measure how far reinforcement learning falls short of the optimum. Our theorems fix what is achievable independently of any learner, so a gap between an engineered and a learned sender at the same bit budget is an optimization fact, not an information-theoretic one. We instantiate this on three MuJoCo arenas spanning zero, partial and rigid physical coupling, charging every condition exactly 2 bits per decision, and create the discriminating regime by closing a physical side channel within one arena, holding bodies, task and reward fixed. Communication value is governed by coupling: under rigid coupling through a shared object, no channel beats silence (+0.001 +/- 0.001, p = 0.982, n = 25), since proprioception already carries that information; without coupling, every condition solves the task; under partial coupling, the engineered 2-bit sender reaches an interquartile mean of 1.000 but the learned one reaches 0.482, indistinguishable from silence (p = 0.400, n = 25). With a shared alphabet, bandwidth cannot explain the gap. Warm-starting from an engineered receiver localizes the failure: the same channel reaches 0.857 versus 0.562 cold-started (p < 0.001), so it is neither representational nor one of maintenance; reinforcement learning fails to discover the protocol. Cross-play shows learned protocols are individually meaningful but mutually unintelligible: self-play 0.980 collapses to 0.144 across seeds, and our best constructed alignment leaves at least 77% of that gap. All headline results use 25 seeds per arena and seven published baselines at matched rate.

Mihir Chauhan, Aniket Bera

IDEAS Lab, Department of Computer Science Purdue University

Sequential MARL Partially Observable Markov Decision Processes Multi-Agent Communication Cooperative MARL Emergent Communication

Sep 22, 2026math.OC

A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing

We study decentralized partially observable team decision problems with low-rank latent dynamics and unknown system models. The proposed framework combines team-theoretic equivalence with low-rank model representations to address cooperative decision-making in partially observable Markov decision processes without prior knowledge of the transition model. Each team member makes decisions based on local private information and delayed common information shared across the team. Using only this available information, each member learns an approximate low-rank Markov decision process and applies least-squares value iteration to compute its policy. This yields a fully decentralized learning and planning algorithm that requires neither a centralized coordinator nor centralized training. We show that the resulting member-side solutions approximate the centralized team solution: despite partial observability, unknown dynamics, and delayed common information, each member recovers the corresponding component of an approximate team-optimal policy. We further establish finite-sample performance guarantees and derive a corresponding sample-complexity bound for the proposed algorithm.

Xiaoxing Ren, Thomas Parisini, Andreas A. Malikopoulos

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

Markov Decision Processes Linear Markov Decision Processes Partially Observable Markov Decision Processes Decentralized MARL Cooperative MARL

Sep 21, 2026cs.LG

Reinforcement Learning under State and Outcome Uncertainty: A Foundational Distributional Perspective

In many real-world planning tasks, agents must tackle uncertainty about the environment's state and variability in the outcomes of any chosen policy. We address both forms of uncertainty as a first step toward safer algorithms in partially observable settings. Specifically, we extend Distributional Reinforcement Learning (DistRL)-which models the entire return distribution for fully observable domains-to Partially Observable Markov Decision Processes (POMDPs), allowing an agent to learn the distribution of returns for each conditional plan. Concretely, we introduce new distributional Bellman operators for partial observability and prove their convergence under the supremum p-Wasserstein metric. We also propose a finite representation of these return distributions via psi-vectors, generalizing the classical alpha-vectors in POMDP solvers. Building on this, we develop Distributional Point-Based Value Iteration (DPBVI), which integrates psi-vectors into a standard point-based backup procedure-bridging DistRL and POMDP planning. By tracking return distributions, DPBVI lays the foundation for future risk-sensitive control in domains where rare, high-impact events must be carefully managed. We provide source code to foster further research in robust decision-making under partial observability.

Larry Preuett, Qiuyi Zhang, Muhammad Aurangzeb Ahmad

University of Washington, Tacoma, USA · Google DeepMind, California, USA · University of Washington, Bothell, USA

Distributional RL Markov Decision Processes Partially Observable RL Partially Observable Markov Decision Processes

Sep 16, 2026cs.LG

Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? We show that it can when the logger depends on history. For every horizon

H \ge 3

, we construct two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states. Action coverage, belief coverage, and two behavior-marginal outcome-revealing conditions all have constants independent of

H

. Nevertheless, evaluating a known deterministic target policy to accuracy

1/8

requires

Θ((3/2)^H \log(1/δ))

logged episodes at confidence

1-δ

, for

0 < δ\le 1/4

, even when both candidate models are known. The mechanism is simple: a reset erases the unknown transition that determines the target value. We characterize the resulting statistical experiment exactly and obtain a matching optimal estimator. A directed two-lane gridworld realizes the construction, and trajectory simulations agree with its finite-sample prediction. The result establishes intractability for the history-dependent-logging, model-based case posed by Zhang and Jiang (2025, arXiv:2503.01134), under their behavior-marginal definition of revealing.

Pranaya Jajoo

University of Alberta

Off-Policy Evaluation Sample Complexity Partially Observable Markov Decision Processes

Sep 14, 2026eess.SY

Adaptive Agent Design

We consider an agent acting against a general non-Markovian environment. The agent maintains its agent states, but is free to choose a transition kernel across those states and optimize its state-feedback control policies. We study the bi-level agent design problem that optimizes the transition kernel and the policy it induces, given said kernel with offline data of observations and actions obtained via a behavioral policy. For general environments, we show that a soft

Q

-learning algorithm converges almost surely to the fixed point of a soft Bellman equation defined by the stationary averages that the behavioral policy and the chosen kernel induce, and we delineate what separates the resulting policy from an optimal one. In partially observed Markov decision problems, we analyze convergence properties of parametrized transition kernel design via zero-th order and Bayesian optimization techniques.

Raj Kiriti Velicheti, Subhonmesh Bose, Tamer Başar

Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois, Urbana-Champaign, Urbana, IL 61801

Reinforcement Learning Q-Learning Offline RL Partially Observable Markov Decision Processes Policy Learning

Sep 9, 2026cs.AI

Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability

Large language model agents produce fluent action sequences across a wide range of tasks, yet they fail in characteristic ways once the environment becomes partially observable. Ambiguous feedback pushes them into premature commitments. A single informative observation can collapse their uncertainty onto the wrong hypothesis. Policies drift as the history grows. We trace these symptoms to a common structural cause. An LLM agent, as commonly deployed, is a history-conditioned policy with no explicit belief over hidden state. We propose an architectural fix. The Belief-State Engine (BSE) is an inference module placed outside the LLM. It maintains a Bayesian posterior over the latent states of a given POMDP (Partially Observable Markov Decision Process) model, and at each decision step it exposes only that posterior to the LLM. The raw action-observation log is not shown. We set out a minimal four-axiom specification of what a belief-consistent internal state must satisfy, and prove that the LLM paired with the BSE is a sound Markov policy on the belief MDP induced by the underlying POMDP. It therefore inherits the Bellman optimality guarantees of classical POMDP theory, provided the LLM is never exposed to the raw history. We evaluate the architecture on the Tiger POMDP and a red-team attack-graph task, against six baselines: a reactive LLM, Chain-of-Thought, ReAct, a natural-language belief tracker, QMDP, and POMCP. Across both domains, the BSE-augmented agent improves task return, belief calibration, and decision consistency. Ten targeted ablations isolate the contribution of each architectural choice confirms that the effect is not specific to any one model. Code, environment specifications, prompt templates, and seed logs accompany this paper.

Arnab Chattopadhayay, Debdipta Halder

Independent Researcher (UCL Alumni), Bangalore, India · Independent Researcher (IIT-Kharagpur Alumni), Bangalore, India

Belief-Space Planning LLM Agents Belief Updating in LLMs Partially Observable Markov Decision Processes

Sep 1, 2026cs.RO

Scalable Rao-Blackwellized Online Planning for High-Dimensional POMDPs

Online planning under uncertainty remains a fundamental challenge for robotic systems operating in partially observable environments with high-dimensional state spaces. While sampling-based POMDP solvers enable approximate decision-making in large or continuous domains, their performance degrades as belief dimensionality increases due to the high variance inherent in Monte Carlo-based estimation. In this work, we extend the Rao-Blackwellized online POMDP (RB-POMDP) framework to improve its generalizability in high-dimensional settings through hybrid continuous-discrete belief representations. By analytically propagating uncertainty associated with marginalized state components during tree-based planning, the proposed approach reduces sampling-induced variance in value estimation. We demonstrate the effectiveness of this framework in a robotic search-and-rescue task by integrating it with FastSLAM 2.0. Experimental results show that the proposed planner achieves higher cumulative rewards using significantly fewer particles and planning simulations than purely sampling-based methods under equivalent computational budgets. These results suggest that structured high-dimensional robotic problems admitting tractable sufficient statistics can be effectively leveraged within the RB-POMDP framework for computationally feasible online decision-making.

Jiho Lee, Nisar Ahmed, Kyle Hollins Wray +1

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

Belief-Space Planning Partially Observable Markov Decision Processes Decision-Making under Uncertainty

Aug 25, 2026cs.AI

Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

Robust POMDPs (RPOMDPs) generalize classical POMDPs to the setting where exact transition probabilities are not known -- rather, they are only known to belong to some uncertainty set of values. In this work, we study the problem of solving RPOMDPs with general omega-regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under omega-regular objectives can be reduced to solving partially observable stochastic games (POSGs) under omega-regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs. This allows us to derive a range of new computational complexity results, including both upper and lower complexity bounds, on solving RPOMDPs with different omega-regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.

Durgam Latha, Dion Reji, S. Akshay +2

Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore

Robust Markov Decision Processes Partially Observable Markov Decision Processes

Aug 25, 2026cs.LG

From Relaxed Indexability to Exact Indexability: A $t$ -Step Approach for Partially Observable Restless Bandits

Whittle index policies offer a scalable method for restless multi-armed bandits, but under partial observability even determining the indifference subsidy at a single belief requires solving an infinite-horizon belief-state problem with no closed-form value function. Liu [10] addresses this difficulty by linearizing the unknown decision boundary, leading to a linear system and a closed-form approximate Whittle index. However, the resulting threshold uses only a one-step active--passive comparison and does not account for longer-horizon continuation values. We extend this framework to a \emph{

t

-step lookahead threshold policy}. For each subsidy

m

, the threshold is defined by the active-minus-passive advantage under

t

-step finite-horizon value iteration. At

t=1

, the threshold is

m

-independent and recovers the linear threshold of Liu [10]; for

t>1

, it becomes subsidy-dependent through the induced first-crossing structure and tracks the exact decision boundary more closely. The proposed algorithm does not require indexability as an input and includes an indexability verification. Under the original Whittle indexability, we prove that the

t

-step approximate Whittle index converges geometrically to the exact Whittle index,

|\widehat W_t(ω)-W(ω)|=O(β^t).

Numerically, all 2,715 tested three-state instances are verified as indexable according to the proposed criterion. The P95 index error decreases from

2.18\times10^{-2}

at

t=1

to

8.93\times10^{-4}

at

t=8

. In an exact-comparable instance with

β=0.9999

,

t=2

already recovers the exact Whittle-index ordering. Moderate-depth threshold policies also outperform the one-step baseline and remain close to the optimal dynamic-programming benchmark, while runtime grows mildly with

t

.

Qizhen Jia, Keqin Liu

School of Mathematics and Physics · Xi’an Jiaotong-Liverpool University · Suzhou 215123, China

Multi-Armed Bandits Sequential Decision Making Partially Observable Markov Decision Processes

Aug 11, 2026math.OC

Threshold Structure of Optimal Policies in Restart POMDPs

We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space, where the controller either lets the hidden state evolve unobserved or restarts the system and observes the new state. Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP. Under a natural one-step cost deterioration condition, we prove that optimal policies have a threshold structure in the elapsed time for both the discounted and total undiscounted cost criteria. When the state space is partially ordered and the kernel is stochastically monotone, we further show that the optimal threshold is nonincreasing in the state. For the average cost criterion, under additional assumptions of geometric ergodicity and domination of the transient gain, we establish analogous threshold results via the vanishing discount approach, after showing the uniform boundedness of the optimal thresholds and relative value functions.

Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang

Inria, France · Department of Mathematical Sciences, University of Liverpool, UK · School of Mathematics, University of Birmingham, UK

Sequential Decision Making Stochastic Optimal Control Partially Observable Markov Decision Processes

Aug 4, 2026cs.RO

POMDPs for Autonomous Science Exploration

Autonomous exploration missions require decision-making under sensor uncertainty and computational constraints, yet integrating scientific representations into POMDP planning has remained intractable due to high-dimensional observation spaces. Information-theoretic planners overcome this by assuming deterministic observations, sacrificing the principled uncertainty quantification that POMDPs provide. We introduce the Science Hypothesis Map POMDP (SHM-POMDP), which makes science-driven belief-space planning more tractable by branching on inferred physical properties rather than raw sensor data. This preserves full sensor information through learned observation models while enabling the planner to reason jointly about navigation and scientific properties under uncertainty. On an extended RockSample domain with 50-dimensional observations, SHM-POMDP achieves 18.6% higher rewards and 32.9% reduced computation time per step than continuous-observation baselines. On realistic geologic exploration using Cuprite hyperspectral data, SHM-POMDP achieves 2.5

\times

higher information gain than the best information-theoretic baseline by maintaining beliefs and replanning adaptively---reaching 80% of oracle performance using only uniform priors. These results demonstrate that integrating hierarchical probabilistic models into belief-space planning enables tractable, principled autonomous science that outperforms both traditional POMDP methods and science-aware information-theoretic approaches.

Daniel Guirguis, Nathan Wallace, Hanna Kurniawati +1

Belief-Space Planning AI for Science Autonomous Scientific Discovery Partially Observable Markov Decision Processes

Aug 3, 2026cs.GT

Intention Inference Under Execution Noise: Separating Aleatoric and Epistemic Uncertainty in Social Dilemmas

In noisy social dilemmas, intended actions are stochastically corrupted before execution, so an observed defection may reflect hostile intent or action error. Standard Markov Decision Process (MDP) formulations treat executed actions as states, structurally precluding this distinction and causing systematic over-retaliation. We introduce a Partially Observable MDP (POMDP) formulation encoding opponent intentions as latent states and executed actions as noisy observations, solved within the active inference (AIF) framework with a cost function that decomposes into epistemic and pragmatic components that jointly address inferring current intent and learning how intent evolves. In the Iterated Prisoner's Dilemma with symmetric noise, we derive a critical noise threshold governing cooperation collapse, connecting it to a fixed-point condition on learned priors. Experiments reveal that the value of intention inference is context-dependent: the POMDP provides consistent advantages against conditionally cooperative opponents, but mutual intention inference under sufficient noise produces correlated belief-driven collapse. The advantage is specific to games where intent attribution is decision-relevant.

Kival Mahadew, Jonathan Shock

Dept. of Computer Science, University of Cape Town · Neuroscience Institute, University of Cape Town · Dept. of Mathematics & Applied Mathematics, University of Cape Town +2

Social Dilemmas Partially Observable Markov Decision Processes Epistemic Uncertainty

Jul 29, 2026cs.LG

Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes

An agent acting under partial observability must retain a recursively updateable statistic of history that restores the Markov property, but the smallest such statistic is generally unknown. We characterize this minimal Markov sufficient statistic for holonomy-cover decision processes, a structured POMDP class in which the visible dynamics are Markov and every realized visible transition applies a fixed permutation to a hidden mode. In particular, we construct the stable quotient, the coarsest observation-wise abstraction preserving one-step rewards and quotient successors, and prove that the pair of the current observation and stable class forms an exact finite Markov state. When the current class is correctly initialized, exact class tracking requires exactly the minimal memory symbols, in the sense that under reachability and pairwise decision separation at a maximizing observation, no arbitrary finite-memory controller can use fewer. Under resettable diagnostics, nearest-prototype class inference has exponentially decaying error, and a calibrate-then-restart reduction transfers finite-MDP guarantees to the recovered state. The results enable \emph{Holonomy Memory Reinforcement Learning}. It represents memory by the current stable class, updates it through ordered edge transports, identifies local class coordinates when diagnostics are available, and applies a standard finite-MDP RL backbone after synchronization. Experiments recover an exact compression from raw states to quotient states and achieve perfect paired-order accuracy with three decision-time memory states, matching the quotient oracle and outperforming the non-oracle baselines.

Zuyuan Zhang, Yongshan Chen, Mahdi Imani +1

Department of Electrical and Computer Engineering, The George Washington University · Department of Electrical and Computer Engineering, Northeastern University

Markov Decision Processes Partially Observable RL Markov Models State Abstraction State Tracking Partially Observable Markov Decision Processes+1

Jul 29, 2026cs.RO

Semi-Decentralized Multi-Spacecraft Collision Avoidance under Communication Constraints

Current spacecraft collision-avoidance operations rely on intermittent ground-station contacts, requiring operators to plan with delayed and asynchronously updated information. Consequently, maneuvers must be planned with only intermittent information sharing between operators, raising the question of how much coordination is needed to achieve collision-avoidance performance comparable to centralized planning. Although decision-theoretic approaches such as partially observable Markov decision processes (POMDPs) capture the sequential and uncertain nature of collision avoidance, existing multiagent extensions typically assume either continuous information sharing or communication models that do not reflect operational ground-station constraints. To explicitly model this intermittent information availability, we formulate the spacecraft-to-spacecraft collision avoidance problem as a semi-decentralized POMDP (SDec-POMDP), where we govern information propagation directly by realistic ground-station visibility windows. Joint maneuver policies are computed using approximate Recursive Small-Step Semi-Decentralized A* (RS-SDA*), following the state-of-the-art A*-based lineage for decentralized multiagent planning. Across a representative suite of conjunction scenarios, semi-decentralized planning recovers near-centralized maneuver quality while requiring 28.5% fewer synchronization events than continuous coordination. Comparisons with representative rule-based operator heuristics further show that communication-aware planning more consistently achieves the desired operational miss-distance band while minimizing unnecessary trajectory deviation. Together, these results establish a practical planning framework for autonomous collision avoidance under realistic intermittent communication, bridging the gap between idealized centralized coordination and fully decentralized planning execution.

Grace Ra Kim, Mahdi Al-Husseini, Duncan Eddy +1

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

Collision Avoidance Partially Observable Markov Decision Processes Multi-Agent Planning Multi-Agent Communication

Jul 20, 2026cs.RO

Beyond Fixed Goal Delivery: Online POMDP Planning for Target Interception in Crowds

Target interception in crowded environments requires reaching a moving objective while navigating among multiple uncertain human agents. Since human navigation intent is not directly observable, the robot must reason over multiple possible future interaction outcomes. We formulate interception in crowds as a partially observable Markov decision process and solve it online using tree search under a fixed computational budget. In this setting, the action-space structure directly shapes the search tree and how computational effort is allocated. We perform a controlled comparison between a sequential path-speed planner, which first plans a spatial path and then modulates speed along it, and a unified planner that jointly branches over steering and speed within tree search. Across simulations with up to 200 humans, both approaches perform similarly at low crowd density but diverge sharply as density increases. At the highest crowd density, the sequential planner has a safe-interception rate 31 percentage points lower and requires 44% more time than the unified steering-speed planner, revealing a structural limitation of spatial restriction. Project webpage: https://tic-planning.github.io/

Himanshu Gupta, Kelvin Aladum, Nisar Ahmed +2

Dept. of Aerospace Engineering Sciences, University of Colorado Boulder, USA · Dept. of Computer Science, University of Colorado Boulder, USA

Robot Navigation Safe Motion Planning Partially Observable Markov Decision Processes

Jul 19, 2026cs.AI

Learning-Driven Adaptive Audit Scheduling: A Sequential Decision Approach to Off-Chain Data Integrity

We model cryptographic auditing of off-chain data as a Constrained MDP (CMDP) under partial observability: the storage node's hidden type and corruption state make the problem a POMDP, while a miss-rate ceiling rho imposes an explicit security constraint. We propose DRQN-CMDP, a Deep Recurrent Q-Network whose GRU layer maintains a belief over the latent node type, paired with Lagrangian dual ascent that adapts the miss-rate penalty lambda automatically. A pairing-free homomorphic-MAC primitive supplies O(1) on-chain verification cost. Across 13 methods--four DQN variants, PPO, A2C, PPO-Lagrangian, a stateful Bayesian heuristic, three fixed-rule baselines, and an oracle-informed heuristic--DRQN-CMDP achieves a favourable balance: 83% lower gas than fixed high-frequency auditing, single-digit miss rate (7.5%), and moderate detection latency--a combination no other method matches across all three objectives simultaneously.

Changting Lin, Fan Li, Weihang Yu +4

Hangzhou Yunphant Network Technology Co., Ltd., Hangzhou, China · Zhejiang University, Hangzhou, China · Central University of Finance and Economics, Beijing, China +2

Markov Decision Processes Deep Q-Learning Partially Observable Markov Decision Processes

Jul 18, 2026cs.AI

Expected Free Energy as Belief-Dependent Utility for rho-POMDPs

An agent acting under partial observability must decide when to gather information and which observations are worth their cost. Standard POMDPs value information only through its eventual effect on reward. The

ρ

-POMDP framework instead rewards uncertainty reduction directly, through a belief-dependent utility

ρ

, but in practice both the choice of

ρ

and the weight placed on it are tuned by hand for every task. We show that active inference removes this tuning entirely. Minimizing Expected Free Energy (EFE) is exactly equivalent to solving a

ρ

-POMDP whose utility is expected information gain, and the exploration weight is fixed at

w=1

because the variational bound expresses pragmatic and epistemic value in the same units (nats). We prove this equivalence for observe-then-commit POMDPs and extend it to factored observation POMDPs, a broader class that covers interleaved observe-act problems such as non-destructive testing and mobile sensing, where gathering information leaves the hidden state unchanged. Experiments support the theory. Across environments ranging from the classic Tiger problem to RockSample and a new Structural Inspection benchmark with over 65,000 states, the untuned weight matches or outperforms reward-only planning at the same horizon, avoids the over-exploration of bonuses tuned per task, and sits near the reward-maximizing knee of the success-reward Pareto frontier. The practical payoff is an exploration objective that works out of the box. In applications such as fault detection and medical screening, where every test has a price and every missed fault has a cost, EFE supplies a belief-dependent utility that is derived rather than tuned.

Patrick Cooper, Alvaro Velasquez

Department of Computer Science, University of Colorado Boulder, Boulder, CO, USA

Free Energy Calculation Active Inference Value of Information Free Energy Principle Partially Observable Markov Decision Processes Decision-Making under Uncertainty

Jul 15, 2026cs.AI

STOCKTAKE: Measuring the Gap Between Perception and Action in LLM Agents with a Fair Oracle

LLM agents are increasingly evaluated on multi-week decision tasks in which the state that drives cost is never directly observed. On such tasks the final cost cannot say why an agent failed: it may have misread the world, or read it correctly and still failed to act (the knowing-doing gap). Existing evaluations cannot separate these two failures; their reference policies either read privileged information the agent never sees, or are missing altogether. We introduce STOCKTAKE, a 26-week supply-chain replenishment benchmark built as a factored partially observable Markov decision process with six hidden factor processes, designed so that a fair reference policy is computable: an exact Bayes filter per factor drives a rollout policy on the identical observation stream the agent receives. Scoring each run between a symptom-blind base-stock floor (0) and this oracle (1) yields a skill score, and grading each week's written rationale yields a stated-belief detection lag and a knowing-doing rate, so state estimation and control are measured separately. On fifty seeds with curated stress profiles, Claude Sonnet 5, GPT-5.4, DeepSeek-V4-Pro, and Grok 4.5 detect 84-88% of hidden failures, typically within a week of onset, yet span skill scores from 0.62 to -0.23: two of the four end below the symptom-blind floor while naming factors slightly faster than the two that beat it. The failure has two faces. Where stress persists, 34-43% of correctly diagnosed stress weeks still end in stockout for every model, a rate that partly reflects the severity of the weeks models notice. That rate also runs opposite to skill: the two models under the floor stock out least on diagnosed weeks, so under-response is only one face of the gap, and their traces point to the other, responses whose cost exceeds what they protect. STOCKTAKE measures both directions of that failure.

Sagar Deb, Ashwanth Krishnan

QpiAI

Inventory Control LLM Agent Evaluation Long-Horizon Agent Evaluation Partially Observable Markov Decision Processes

Jul 13, 2026math.OC

LQG solution for POMDP without estimating states: A minimum variance approach

This paper investigates the control of discrete-time linear time-invariant (LTI) systems subject to incomplete and corrupted measurements. Specifically, we focus on designing a Linear Quadratic Gaussian (LQG) controller without relying on explicit state estimation. By leveraging minimum variance duality, our approach allows the current control input to be represented as a linear function of available measurements and previously applied inputs, successfully reducing the task to a tractable deterministic optimization problem. We provide theoretical justification for this framework and demonstrate its practical effectiveness through numerical experiments.

Ranjan Sarkar, Prabhat K. Mishra

Department of Artificial Intelligence at Indian Institute of Technology Kharagpur, West Bengal, India

Stochastic Optimal Control Feedback Control Partially Observable Markov Decision Processes

Jul 13, 2026eess.SY

Active Noise Floor Estimation for Reliability-Optimal POMDPs: A Value-of-Noise-Information Approach

Finite Reliability Representations (FRR) certify when a cell-constant policy is sufficient for reliable decision-making in a partially observed system with a known physical noise floor. In practice, however, sensing and execution noise can be latent and context-dependent. This paper develops a certificate-aware active disambiguation framework for an unknown physical noise parameter theta = (sigma_y, sigma_u), with the sensor-only case obtained by fixing sigma_u. We define the Value of Noise Information (VoNI) as the expected excess FRR certificate gap caused by using a reliability cover calibrated to the current estimate rather than to the realized noise parameter. We bound VoNI using action-value model mismatch and FRR radius inflation, showing that noise estimation has low decision value in sub-crossover regimes where the FRR certificate is insensitive to theta, but becomes valuable when posterior uncertainty can invalidate the current cover. A bi-level decision maker uses a posterior over theta, obtained from innovation statistics, execution residuals, or another online estimator, and triggers diagnostic probing only when uncertainty threatens the FRR certificate. We also interpret VoNI as a tractable, certificate-aware approximation to a high-level finite POMDP for latent sensing-execution regime disambiguation. Under stationary, identifiable, and persistently exciting regimes, we establish posterior consistency and convergence of the induced policy loss to the FRR approximation floor. Closed-loop UGV simulations with EKF-based innovation residuals show earlier detection of abrupt sensing-noise jumps, lower drift-tracking error, and substantially fewer probing actions than posterior-entropy exploration over 50 Monte Carlo trials.

Hyung-Jin Yoon

Department of Mechanical and Nuclear Engineering, Tennessee Technological University, Cookeville, TN 37135, USA

Value of Information Active Sensing Partially Observable Markov Decision Processes Decision-Making under Uncertainty

Jul 11, 2026cs.RO

Interleaved POMDP Planning for Multi-Object Search in Unknown Multi-Room Household Environments

Multi-object search in unknown household environments requires planning under extensive uncertainty - from unknown object locations to cluttered spaces with unobserved obstacles. POMDPs offer a principled framework for such problems but remain intractable in large domains. We propose Inter-POMDP, a novel interleaved POMDP planning algorithm that decomposes this challenge into two interacting levels: a high-level POUCT planner reasons over object distributions using LLM-informed histogram beliefs, while a low-level motion planner models navigation uncertainty with obstacle-aware particle beliefs as domain knowledge to guide high-level POUCT. This interleaved design balances planning quality and efficiency despite the large search space across unknown multi-room environments. Both simulation and real-world experiments show that our Inter-POMDP algorithm reduces collision counts by up to 63%, navigation steps by up to 35%, and detection counts by up to 32% compared with baseline methods. Full videos are https://sites.google.com/view/inter-pomdp

Ruochu Yang, Ziyi Xia, Huibo Zhang +6

Georgia Institute of Technology, USA · The Hong Kong University of Science and Technology, China · Ising AI, China +2

Belief-Space Planning Partially Observable Markov Decision Processes Robot Motion Planning

Jul 7, 2026cs.AI

QANTIS: Hardware-Calibrated Sequential POMDP Belief Updates on IBM Heron

Autonomous systems under partial observability act on beliefs, not raw sensor events. QANTIS treats the quantum processor as a calibrated belief-update service in that loop: it receives a prior and an observation model, estimates the rare-event evidence term, and returns an ordinary posterior to a classical planner. This paper asks whether that service can be reused across a sequential Tiger POMDP horizon on present IBM Heron hardware without corrupting the planner-facing posterior. We answer with a controlled hardware case study rather than an end-to-end autonomy or wall-clock speedup claim. The study compares no amplification, guarded Grover amplification, and all-step fixed-point amplification on the same trajectory, then checks whether the returned posterior would change the downstream action. All-step FPAA preserves the Tiger posterior across the reported 8-step and 12-step primary runs, and the 20-step and 32-step controls remain inside the same operating band. In every reported decision check, the hardware posterior and the exact Bayes posterior select the same immediate action. Boundary-aware BIQAE stabilizes amplitude estimation near zero and near one, while a rare-event sweep maps the logical sample-complexity envelope for one-in-a-million evidence. The result is an operating envelope for a hardware-calibrated belief-update primitive, not a standalone hardware-advantage claim.

Bayram Yuksel Eker, Suayb S. Arslan, Ozgur Nazli +2

Neura Parse Ltd. London, United Kingdom · Dept. of Computer Engineering Boğaziçi University Istanbul, Turkey · Dept. of Physics Izmir University of Economics Izmir, Turkey +2

Belief-Space Planning Bayesian Filtering Partially Observable Markov Decision Processes

Jul 4, 2026eess.SY

Finite Reliability Representations: Noise-Calibrated Belief-Space Covers for Reliable Decision-Making

Physical sensing and actuation noise floors should inform how much belief resolution a decision-making system can reliably use. We introduce Finite Reliability Representations (FRR), a framework for covering belief spaces by reliability cells: regions within which the optimal action-value function Q*(b,u) varies by at most a tolerance epsilon, uniformly over actions. The framework is formulated on beliefs rather than states and uses a cover rather than an equivalence quotient, because approximate decision-closeness is not transitive in general. A central technical point is that noisy Bayesian updates should not be treated as globally contractive on arbitrary beliefs. We therefore separate three objects: the fixed-observation filter map, the predictive observation law, and the controlled belief-transition kernel. For nonlinear continuous-state systems, FRR is obtained under a reachable-set Lipschitz modulus for the belief-transition kernel. For finite-state POMDPs, the same construction becomes exact on the belief simplex: prediction is linear, Bayesian correction is a normalized positive linear map, sensor noise enters through observation-distribution distinguishability, and actuation uncertainty enters through an action-execution channel. Under the corresponding action-value Lipschitz condition, an FRR cover supports a cell-constant policy whose suboptimality is bounded by 2 epsilon/(1 - gamma). We also introduce reliability entropy, the logarithm of the minimal number of reliability cells, as a measure of certified decision-relevant belief complexity. The framework distinguishes representation sufficiency from fundamental performance floors imposed by sensing, process, and actuation noise. It applies to finite POMDPs, linear-Gaussian filters, locally linearized nonlinear filters, and particle-filter implementations through analytic or empirical certification of reliability cells.

Hyung-Jin Yoon, Hunmin Kim

Belief-Space Planning Partially Observable Markov Decision Processes Decision-Making under Uncertainty

Jun 20, 2026cs.AI

REBA: A Revealed Belief Automaton Framework for Online Planning in Continuous POMDPs

Online planning in continuous partially observable Markov decision processes (POMDPs) using

ω

-regular specifications requires handling continuous belief dynamics within the finite symbolic memory in order to track temporal progress. Existing methods based on either direct search in belief space or predefined discrete abstractions suffer from drawbacks, e.g., lack of symbolic memory for long-horizon logical progress or difficult to certify from noisy online beliefs. As such, obtaining reliable symbolic states online from continuous observations remains a challenge. To address this issue, we introduce the Revealed Belief Automaton (REBA), an event-driven framework that advances the research from global belief-space discretization to a fundamental new way of thinking, namely online certification of revelation events. Specifically, we propose an online revelation method that, through information-theoretic gates, can dynamically analyse and establish belief abstraction from the continuous belief space by discovering reliable anchors among noisy beliefs. We then develop an incremental topology adaptation mechanism over the certified anchors to realise the online finite Belief Automaton. By combining with the

ω

-regular specification, REBA is able to support formal parity policy synthesis without a predefined discrete abstraction, which in turn can guide the Monte Carlo Tree Search process to perform online search beyond its local horizon. In addition, we design an error decomposition analysis which can assess the effectiveness and reliability of this discrete guidance for the underlying continuous POMDP. Empirical evaluations in patrolling and navigation scenarios show that REBA matches or exceeds all evaluated baselines, with primary metric gains of +17.0% to +47.4% over state-of-the-art approaches.

Xiangwei Chen, Lingling Fang, Andreas Holzinger +1

School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China · School of Computer Science and Artificial Intelligence, Liaoning Normal University, Dalian 116029, China · Human-Centered AI Lab, Department of Ecosystem Management, Climate and Biodiversity, BOKU University, Vienna, 1190, Austria +1

Belief-Space Planning Partially Observable Markov Decision Processes

Jun 18, 2026cs.RO

VOiLA: Vectorized Online Planning with Learned Diffusion Models for POMDP Agents

Planning under uncertainty is an essential capability for autonomous robots. The Partially Observable Markov Decision Process (POMDP) provides a powerful framework for such a capability. Although POMDP-based planning has advanced significantly, its application to real-world problems is often limited by the difficulty of obtaining faithful POMDP models. We present Vectorized Online planning wIth Learned diffusion model for POMDP Agents (VOiLA), a framework that learns task-agnostic POMDP models for online planning under uncertainty. VOiLA learns transition and observation samplers using conditional diffusion models and learns observation-likelihood models for particle-based belief updates. To enable efficient online planning, the diffusion samplers are distilled into compact feedforward generators and integrated with Vectorized Online POMDP Planner (VOPP), an online POMDP planner designed to leverage GPU parallelization. Experimental results indicate the distillation strategy reduces sampling cost by up to nearly three orders of magnitude, making learned generative POMDP models practical for online planning. Evaluation of VOiLA on three benchmark problems indicate that VOiLA achieves equal or better performance than Recurrent Soft Actor Critic while using less than 10% training data, and generalizes much better to unseen environment configurations. Physical robot evaluation indicates VOiLA uses the models learned using only simulated data and generates a policy that successfully accomplish the task in 10 of 10 runs.

Marcus Hoerger, Rishikesh Joshi, Rahul Shome +2

Australian National University, Canberra, ACT, Australia · The University of Sydney, Sydney, NSW, Australia

Belief-Space Planning Diffusion-Based Planning Model-Based Planning Partially Observable Markov Decision Processes

Jun 17, 2026cs.AI

Generative-Model Predictive Planning for Navigation in Partially Observable Environments

Navigation in partially observable environments presents a significant challenge for autonomous agents, requiring effective decision-making with limited sensory information in unknown environments. Belief-based methods, particularly those using neural networks to approximate the belief space, often fail to capture the inherent multimodality of belief spaces, especially in high-dimensional cases with perceptual aliasing. While generative models present a compelling alternative, they typically require substantial data or expert demonstrations and lack explicit mechanisms for long-term planning. In this paper, we introduce BeliefDiffusion, a novel framework that combines the benefits of both generation and planning. BeliefDiffusion leverages diffusion models to explicitly characterize multimodal belief distributions and utilizes Model Predictive Control (MPC) to simultaneously plan ahead. It consists of two steps: (1) Imagining plausible environment configurations based on observation history and (2) Planning efficient navigation strategies across an aggregated configurations. Through extensive experiments in synthetic map environments, we demonstrate that BeliefDiffusion significantly outperforms both model-free reinforcement learning baselines and other generative approaches in navigation success rate and path efficiency. Our results validate that explicitly incorporating multimodal belief representations into planning enables more robust navigation in partially observable settings.

Thomas Quilter, Yifan Zhu, Guorui Quan +2

Department of Computer Science Aalto University Espoo, Finland

Belief-Space Planning Diffusion-Based Planning Robot Navigation Partially Observable Markov Decision Processes

Jun 14, 2026cs.RO

PO-PDDL: Learning Symbolic POMDPs from Visual Demonstrations for Robot Planning Under Uncertainty

Real-world robot task planning must operate under both stochastic action execution and partial observability, yet constructing Partially Observable Markov Decision Process (POMDP) models for real robotics domains remains difficult and labor-intensive. We introduce PO-PDDL, a symbolic formulation of POMDPs that preserves the relational structure and LLM-friendly syntax of the Planning Domain Definition Language (PDDL), while explicitly modeling partial observability, stochasticity, and beliefs. Building on this formulation, we propose a demonstration-driven pipeline for learning PO-PDDL models. The proposed method reconstructs latent symbolic state trajectories from real-robot execution videos, identifies partial observability via inconsistencies between inferred states and visual observations, and learns stochastic transition and observation models accordingly. The resulting PO-PDDL domains are reusable across tasks and enable online belief-space planning under both perception and execution uncertainty. Experiments on real-world long-horizon manipulation tasks show that our method consistently outperforms existing PDDL and POMDP model-learning approaches, achieving robust task planning under uncertainty with significantly lower planning cost.

Wenjing Tang, Xuanjin Jin, Yuan Liu +3

Shanghai Jiao Tong University · Shanghai Innovation Institute

Belief-Space Planning Symbolic Planning Robot Task Planning Learning from Demonstration Partially Observable Markov Decision Processes

Jun 3, 2026cs.RO

Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling

Partially Observable Markov Decision Processes (POMDPs) are a general and principled framework for motion planning under uncertainty. Despite tremendous improvement in the scalability of POMDP solvers, long-horizon POMDPs remain difficult to solve. To alleviate the difficulty, this paper proposes a new approximate online POMDP solver, called Reference-Based Online POMDP Planning via Rapid State Space Sampling (ROP-RAS3). ROP-RAS3 uses novel extremely fast sampling-based motion planning techniques to sample the state space and generate a diverse set of macro actions online, which are then used to bias belief-space sampling and infer high-quality policies without requiring exhaustive enumeration of the action space -- a fundamental constraint for modern online POMDP solvers. ROP-RAS3 converges to a near-optimal reference-based solution at a rate that depends on the number of sampled actions, rather than the size of the action space. ROP-RAS3 is evaluated on various long-horizon POMDPs with up to 3000 lookahead steps and 35-dimensional state spaces, where the state, action and observation spaces can be continuous, discrete, or a hybrid of discrete and continuous. Although the reference-based optimal solution may not be the same as the optimal POMDP solution, empirical results indicate that in all of these problems, in terms of success rate, ROP-RAS3 outperforms other state-of-the-art methods by up to multiple folds. We also demonstrate the capability of our approach on a physical robot demonstration. This work extends the theory and empirical results of our ISRR24 paper. Code can be found at \texttt{https://github.com/RDLLab/ROPRAS3}.

Yuanchu Liang, Edward Kim, J. Arden Knoll +4

Australian National University, Canberra ACT 2601, Australia. · Rice University, Houston TX 77005, USA.

Belief-Space Planning Partially Observable Markov Decision Processes

May 29, 2026cs.LG

Why Linear Recurrent Memory Works in Partially Observable Reinforcement Learning

The family of linear recurrent neural networks has shown strong performance as recurrent memory units in partially observable reinforcement learning. We provide a theoretical justification for their empirical effectiveness by constructing and studying two linear filters: (i) the first exactly reproduces the pre-softmax logits of the belief vector in a hidden Markov model (HMM) under a deterministic transition matrix, thereby serving as a sufficient statistic for optimal policy learning, (ii) the second achieves vanishing state-decoding error under a nearly deterministic transition matrix, thus reducing state ambiguity to near zero. The results extend to action-controlled HMMs, where the corresponding linear filters become time-varying with action-dependent dynamics. We illustrate our main results through numerical experiments and further show that the constructed linear filter serves as a strong feature extractor in a small reinforcement learning game.

Yike Zhao, Onno Eberhard, Malek Khammassi +2

EPFL, Lausanne, Switzerland · Max Planck Institute for Intelligent Systems, Tübingen, Germany

Partially Observable RL Markov Models Recurrent Neural Networks Partially Observable Markov Decision Processes State Representation Learning Linear RNNs+1