Computing Library › Reinforcement Learning
Reinforcement Learning

POMDPs and Belief States

When the agent cannot observe the full state, it must act on a belief, a probability distribution over states.

Partial observability

A Markov Decision Process assumes the agent sees the true state. A Partially Observable MDP (POMDP) drops this: the agent receives only observations that depend probabilistically on the hidden state, via an observation model O(o | s, a). Sensor noise, occlusion, and hidden intentions all make real problems POMDPs.

The belief state

Kronos motion — when

The right sufficient statistic is the belief b(s), a probability distribution over states given the entire history of actions and observations. The belief is updated by Bayes' rule after each step. Remarkably, a POMDP over states becomes a fully observed MDP over beliefs: the belief is Markov even though the observations are not.

python
# Bayesian belief update after action a, observation o
# b'(s') proportional to O(o|s',a) * sum_s T(s'|s,a) * b(s)
def update(b, a, o, T, O):
    b2 = {s2: O[o][s2][a] * sum(T[s][s2][a]*b[s] for s in b)
          for s2 in b}
    Z = sum(b2.values())
    return {s: v/Z for s, v in b2.items()}

Why solving is hard

The belief space is continuous (a simplex over states), so exact planning is intractable in general, formally PSPACE-hard for finite horizons. The optimal value function over beliefs is piecewise-linear and convex, represented by a set of alpha-vectors; point-based solvers (PBVI, SARSOP) approximate it by focusing on reachable beliefs.

POMDPs in deep RL

Deep RL rarely maintains an explicit belief. Instead a recurrent network (LSTM or GRU) compresses the observation-action history into a hidden state that plays the role of an approximate belief. This lets agents handle partial observability, from memory tasks to control with noisy sensors, without ever writing down the observation model.

Related

Thompson Sampling →Meta-RL →Safe RL →