Observation Adaptation via Annealed Importance Resampling for Partially Observable Markov Decision Processes

Yunuo Zhang, Baiting Luo, Ayan Mukhopadhyay, Abhishek Dubey · 2025

Read Observation Adaptation via Annealed Importance Resampling for Partially Observable Markov Decision Processes by Yunuo Zhang, Baiting Luo, Ayan Mukhopadhyay, Abhishek Dubey (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19302.txt.

Introduction

Yunuo Zhang, Baiting Luo, Ayan Mukhopadhyay, and Abhishek Dubey improve decision making under uncertainty in this 2025 paper. Their setting is the POMDP, a standard model for acting when the true state is hidden and only partial observations arrive.

Online solvers track a belief about the state with particle filters, but a sharp new observation can wreck the particle set, leaving it poor and repetitive. The authors build a bridge of distributions between the predicted state and the ideal one, crossed in small Monte Carlo steps. Their method beat leading alternatives in tests across settings. Better belief tracking means safer plans for robots and systems that must act on noisy data.

Catalog record

CREATORYunuo Zhang, Baiting Luo, Ayan Mukhopadhyay, Abhishek Dubey
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19302

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Observation Adaptation via Annealed Importance Resampling for Partially Observable Markov Decision Processes Yunuo Zhang, Baiting Luo, Ayan Mukhopadhyay, Abhishek Dubey Abstract Partially observable Markov decision processes (POMDPs) are a general mathematical model for sequential decision-making in stochastic environments under state uncertainty. POMDPs are often solved online , which enables the algorithm to adapt to new information in real time. Online solvers typically use bootstrap particle filters based on importance resampling for updating the belief distribution. Since directly sampling from the ideal state distribution given the latest observation and previous state is infeasible, particle filters approximate the posterior belief distribution by propagating states and adjusting weights through prediction and resampling steps. However, in practice, the importance resampling technique often leads to particle degeneracy and sample impoverishment when the state transition model poorly aligns with the posterior belief distribution, especially when the received observation is highly informative. We propose an approach that constructs a sequence of bridge distributions between the state-transition and optimal distributions through iterative Monte Carlo steps, better accommodating noisy observations in online POMDP solvers. Our algorithm demonstrates significantly superior performance compared to state-of-the-art methods when evaluated across multiple challenging POMDP domains. Introduction Partially observable Markov decision processes (POMDPs) provide a general mathematical framework for modeling decision-making problems under uncertainty, where the true state of the environment is not fully observable and actions have probabilistic outcomes ( Kaelbling, Littman, and Cassandra 1998 ) . These models have been successfully applied to various real-world scenarios, including time-critical UAV search and rescue operations where efficient path planning must balance computational constraints with effective decision-making ( Zhang et al. 2024 ) . However, POMDPs face challenges to solve exactly due to the “curse of dimensionality” and the “curse of history”, which make the computation of optimal policies non-scalable ( Papadimitriou and Tsitsiklis 1987 ) . To address these computational and scalability issues, online planning algorithms have emerged as a prominent approach. Instead of computing a full policy offline, online planning interleaves planning and execution by focusing computational resources on the current belief state and the immediate decisions to be made ( Ross et al. 2008 ) . A critical component of online planning algorithms is the belief update process where belief denotes a distribution over the possible states. At each node in the search tree, the algorithm needs to update the belief state based on simulated actions and observations. However, performing exact belief updates is computationally infeasible in large state spaces due to the high dimensionality of the belief space ( Rodriguez, Parr, and Koller 1999 ) . To manage this, online planning algorithms approximate the belief state using sampling-based methods. They represent the belief state as a collection of sampled states, or particles, rather than as explicit probability distributions ( Silver and Veness 2010 ) . During the planning process, belief updates are performed by propagating these particles through the state-transition and observation models, using methods such as direct sampling and sequential importance sampling ( Doucet and Johansen 2009 ) . However, these approximation methods face a significant issue: the variance of their estimations increases exponentially with the search depth. This variance escalation is primarily due to the accumulation of uncertainty from observations, which provide imperfect information about the true current state. As the search depth increases, the divergence between the sampled belief and the target posterior can grow substantially, potentially limiting the effectiveness of these planning algorithms, especially in deeper searches where precise belief representation is crucial. Recognizing this challenge, we propose an approach, AIROAS (Annealed Importance Resampling for Observation Adaptation Search), a novel approach for POMDP planning that combines tree search with particle-based belief representation and annealed importance resampling. It aims to reduce the increasing variance by gradually refining the sampled states. Instead of relying solely on samples drawn from the state-transition distribution, we implement an annealed importance sampling process that incrementally transforms these samples. The goal is to shift the distribution of these samples closer to the ideal state distribution, which would be conditioned on the latest observation and the previous state. While directly sampling from this ideal distribution is impossible, our approach approximates it by using Markov Chain Monte-Carlo approximation. By aligning the sampled states more closely with the most probable current states given the available information, we improve the quality of the belief representation. This enhancement leads to more accurate state estimations, particularly at greater search depths. Background POMDPs Partially observable Markov decision processes (POMDPs) are a framework for modeling decision-making under uncertainty, defined by the tuple (S,A,T,R,\Omega,O) . Here, S is the set of states, A the set of actions, T(s^{\prime}|s,a) the transition function, R(s,a) the reward function, \Omega the set of observations, and O(o|s^{\prime},a) the observation function. In POMDPs, at time t, the agent maintains a belief state b_{t} , a probability distribution over states. This distribution is updated after action a_{t} and observation o_{t+1} using the equation: b_{t+1}(s^{\prime})=\eta O(o_{t+1}|s^{\prime},a_{t})\sum_{s\in S}T(s^{\prime}|s,a_{t})b_{t}(s) , where \eta is a normalizing factor. This belief update process enables the agent to estimate its current state despite partial observability, facilitating informed decision-making in uncertain environments. Particle Filters Particle filters ( Arulampalam et al. 2002 ) , also known as sequential Monte Carlo (SMC) methods, are computational algorithms used to estimate the state of a dynamic system when it is observed through noisy measurements. In the context of Partially observable Markov decision processes (POMDPs), particle filters offer an efficient way to approximate the belief state by maintaining a set of weighted samples (particles) that represent the probability distribution over possible states. The widely-known bootstrap particle filter algorithm ( Gordon, Salmond, and Smith 1993 ) works by recursively propagating these particles through the state transition model and updating their weights based on new observations. In POMDPs, at each time step t , the particle filter aims to approximate the optimal posterior distribution: p(s_{t}|o_{t},s_{t-1},a)\propto p(o_{t}|s_{t},a)\cdot p(s_{t}|s_{t-1},a) (1) where s_{t} is the current state, o_{t} is the current observation, s_{t-1} is the previous state, and a is the action taken. A crucial step in bootstrap particle filter is resampling ( Kitagawa 1996 ) , which addresses the problem of particle degeneracy. Over time, some particles may have negligible weights, leading to poor representation of the state space. Resampling involves randomly drawing particles with replacement from the current set, with probabilities proportional to their weights, and then resetting all weights to 1/N , where N is the number of particles. However overly frequent resampling can lead to sample impoverishment, where the particle set loses diversity and fails to adequately represent the full state space. To determine when to resample, the Effective Sample Size (ESS) ( Forthofer, Lee, and Hernandez 2007 ) is often used: ESS=\frac{1}{\sum_{i=1}^{N}(w_{i}^{n})^{2}} (2) where w_{i}^{n} are the normalized weights. When the ESS falls below a predefined threshold (typically N/2 ), resampling is triggered. Although the bootstrap particle filter is relatively easy to implement, its accuracy can be significantly compromised when there is a substantial discrepancy between the optimal posterior distribution described in equation ( 1 ) and the state-transition distribution. This limitation becomes particularly pronounced in scenarios where the one-step received observation is highly informative about the true state, leading to a sharply peaked posterior distribution. In such cases, the bootstrap filter’s reliance

Read the complete text