Consider a POMDP with a finite number of environment states, $|\mathcal{S}| = N$, but the number of belief states is uncountably infinite. The belief state space is the convex hull of an $N$ simplex. Each turn this space is sampled with a flat probability distribution. As you are sampling from an uncountably infinite set of belief states, the probability of a belief state recurring in a finite number of samples is zero.

Now, let's suppose that there are a finite number of episodes, and each episode ends after 1-time step. At the only time step of the episode, the agent receives a belief state $b(s)$ over some fixed set of contexts $s$, selects a single action, and receives a single reward, before the episode ends.

I understand that the belief state value function, $V(b)$, is piecewise linear and convex, with a single hyperplane for each action (see e.g. [1]).

My question is, given that I only observe the belief states and the sampled rewards, how do I identify the value function, given that a belief state $b(s)$ has an infinitesimally small probability of occuring again?

The expected reward for a given belief state $b$ is just a linear function $\alpha \cdot b$, where $\alpha$ is the vector of the rewards for each state of the environment. But I cannot simply learn a linear model here because $\alpha \cdot b$ gives me the expected reward for a given belief state, but I may never start with this belief state again and so cannot simply calculate the sample mean expected reward.


Your Answer


Browse other questions tagged or ask your own question.