A Paradox on Sampling Trajectories with Approximate Belief States

As mentioned on X, I got interested in a POMDP question more than 1 year ago, and discovered many interesting results against my initial intuition. After procrastinating forever, I eventually found time to write things down,¹ and decided to share a piece of the counterintuitive results here as a teaser for the paper. The answer can be found in the paper, and I will post the link here after it appears on arXiv. (Update 11/26: paper link)

---

Background

Suppose we have a simulator modeled as a finite-horizon POMDP $\Gamma$. When sampling a trajectory in the simulator, we sample latent states from the latent transition $P$ and generate observations from the emission process $E$, and the record of an episode includes $o_{0:H}, a_{0:H}, s_{0:H}$, i.e., the observations, the actions, and the latent states. The task is to use Monte-Carlo roll-outs to estimate the Q-value for any given $(\tau_t, a_t)$ pair and target policy $\pi$, where $\tau_t = (o_{0:t}, a_{0:t-1})$ is the prefix of an observable trajectory, or history. Note that the Q-function for a POMDP can be defined through the corresponding history-based MDP, i.e., the POMDP induces a conditional distribution of $\tau_{t+1} \mid \tau_t, a_t$, which can be treated as the transition dynamics of an MDP with $\tau_t$ as the state.²

In an MDP, we can roll-out multiple trajectories from a given $(s_t, a_t)$ pair to estimate $Q^\pi(s_t, a_t)$. Similarly, for the POMDP, we want to roll-out trajectories from $(\tau_t, a_t)$ to estimate $Q^\pi(\tau_t, a_t)$. The problem is that the given $(\tau_t, a_t)$ does not include the value of $s_t$, without which we cannot roll-out the simulation. The POMCP paper ran into this problem when they tried to apply MCTS to POMDPs, and suggested that the correct approach is to sample $s_t$ from the belief state, $\mathbf{b}^\star = \mathbb{P}[s_t \mid \tau_t]$. That is, if we have access to $\mathbf{b}^\star$, below is the correct way to sample an unbiased estimate of $Q^\pi(\tau_t, a_t)$:

1. Sample $s_t \sim \mathbf{b}^\star(\cdot \mid \tau_t)$.

2. Take given action $a_t$, and sample $s_{t+1} \sim P(\cdot\mid s_t,a_t)$, $o_{t+1} \sim E(\cdot \mid s_{t+1})$.

3. Repeat Step 2 by taking actions according to $\pi$ till the end of the trajectory. Take the sum of rewards (assume they are functions of the observations) as the Monte-Carlo return.

---

Roll-out using an Inaccurate Belief State

The problem is that $\mathbf{b}^\star$ is not directly available, and must be approximated via various techniques in Bayesian inference.³ So let’s consider the setting where we are given some candidates $\mathcal{B} = \{\mathbf{b}^{(i)}\}$, and we want to select an appropriate $\mathbf{b} \in \mathcal{B}$ so that we can produce the correct roll-out for estimating Q-values.

There are many ways to perform the selection (this is what the paper is about!), one of which is the following: note that

1. The value function for a POMDP is defined through the induced history-based MDP, which we denote as $M_{\Gamma}$.

2. Every $\mathbf{b} \in \mathcal{B}$ also induces a history-based MDP from which we can efficiently sample: given any $\tau_t, a_t$, we can sample $\tau_{t+1}$ as $s_t \sim \mathbf{b}(\cdot \mid \tau_t), s_{t+1} \sim P(\cdot\mid s_t, a_t), o_{t+1} \sim E(\cdot \mid s_{t+1}), \tau_{t+1} = \tau_t \circ a_t \circ o_{t+1}$. We denote this MDP as $M_{\Gamma, \mathbf{b}}$.

In general, if $\mathbf{b}$ is incorrect we would have $M_{\Gamma} \ne M_{\Gamma, \mathbf{b}}$, so a natural selection criterion is to choose $\mathbf{b}$ such that $M_{\Gamma} \approx M_{\Gamma, \mathbf{b}}$.⁴ This way, we can hope that the Q-functions defined in the two history-based MDPs are close to each other.

---

The Paradox

Suppose we successfully choose a $\mathbf{b}$ such that $M_{\Gamma}$ and $M_{\Gamma, \mathbf{b}}$ are exactly the same. Then their corresponding Q-functions should also be identical. This should imply that our earlier roll-out procedure using $\Gamma$ and $\mathbf{b}$ should produce the right Monte-Carlo return, right?

The answer is no! And questions for you (answer can be found in the paper):

1. Which step of the above reasoning went wrong?

2. It is possible to fix this by changing the roll-out method. How? Note that we only have efficient sampling access to $\mathbf{b}, P, E, \pi$.

Footnote Remarks