Predictive State Representation
Predictive State Representation (PSR)
An alternative to Belief States for handling Partial Observability in POMDPs. Instead of maintaining a probability distribution over hidden states, a PSR defines the internal state as a vector of predictions about future observations (test probabilities).
Core Idea
Predict the Future, Not the Hidden Present
Belief states answer: “What hidden state am I likely in?” PSRs answer: “What would I observe if I did certain things?” Both are valid Markov representations, but PSRs don’t require knowledge of the hidden state space or transition/observation models.
Definition
Define a “test” as a sequence of actions and observations. The test probability is:
Test Probability
For a set of core tests , the PSR is:
It can be proven that for special sets of core tests, this vector is a Markov state — it satisfies the Markov criterion by definition, since it fully characterizes the distribution of future observations.
Tiger Problem Example
In the Tiger problem, all information can be captured by just two tests:
- — probability of hearing left if we listen
- — probability of hearing right if we listen
These probabilities can be learned from data (e.g., with an LSTM classifier).
Advantages and Disadvantages
| Advantages | Disadvantages |
|---|---|
| Test probabilities learnable from data | Limited to tabular setting (extensions exist) |
| As compact or more so than belief states | Finding core tests can be difficult |
| Can still be updated recursively | Less intuitive than belief states |
| No model of hidden states needed |
Connections
- Alternative to Belief State for POMDPs
- Both satisfy the Markov criterion for Partial Observability
- More practical when the hidden state model is unknown
- Can be learned with methods like LSTM classifiers
Appears In
- RL-L13 - Partial Observability
- RL-Book Ch17 - Frontiers (§17.3)
- Littman, Sutton & Singh, “Predictive Representations of State” (2001)