Predictive state representation

In computer science, a predictive state representation (PSR) is a way to model a state of controlled dynamical system from a history of actions taken and resulting observations. PSR captures the state of a system as a vector of predictions for future tests (experiments) that can be done on the system.[1] A test is a sequence of action-observation pairs and its prediction is the probability of the test's observation-sequence happening if the test's action-sequence were to be executed on the system. One of the advantage of using PSR is that the predictions are directly related to observable quantities. This is in contrast to other models of dynamical systems, such as partially observable Markov decision processes (POMDPs) where the state of the system is represented as a probability distribution over unobserved nominal states.[2]

## Definition

Consider a dynamic system based on a discrete set 𝒜 of actions and a discrete set 𝒪 of observations.[3] A history h is a sequence a1o1…aℓoℓ where a1,…,aℓ are the actions taken by the agent in that order and o1,…,oℓ are the observations made up by the agent. Let us write P(a1o1…aℓoℓ) to be the conditional probability of observing o1,…,oℓ given that the actions taken are a1,…,aℓ.

We now want to characterize a given hidden state reached after some history h. To do that, we introduce the notion of test. A test t is of the same type that a history: it is a sequence of action-observation pairs. The idea is now to consider a set of tests {t1,…,tn} to full characterize a hidden state. To do that, we first define the probability of a test t conditional on a history h: P(t∣h):=P(ht)P(h).

We now define the prediction vector p(h)=[P(t1∣h),…,P(tn∣h)]. We say that p(h) is a predictive state representation (PSR) if and only if it forms a sufficient statistic for the system. In other words, p(h) is a predictive state representation (PSR) if and only if for all possible tests t, there exists a function ft such that for all histories h, P(t∣h)=ft(p(h)).

The functions ft are called projection functions. We say that the PSR is linear when the function ft is linear for all possible tests t. The main theorem proved in [3] is stated as follows.

Theorem. Consider a finite POMDP with k states. Then there exists a linear PSR with a number of tests n smaller that k.

## References

1. ↑ James, Michael R.; Singh, Satinder (2004). "Learning and discovery of predictive state representations in dynamical systems with reset". Twenty-first international conference on Machine learning - ICML '04. p. 53. doi:10.1145/1015330.1015359. ISBN 978-1-58113-838-2.
2. ↑ Izadi, Masoumeh T.; Precup, Doina (9 August 2003). "A planning algorithm for predictive state representations". Proceedings of the 18th International Joint Conference on Artificial Intelligence. Ijcai'03: 1520–1521. https://dl.acm.org/doi/abs/10.5555/1630659.1630919.
3. ↑ 3.0 3.1 Littman, Michael; Sutton, Richard S (2001). "Predictive Representations of State". Advances in Neural Information Processing Systems (MIT Press) 14. https://papers.nips.cc/paper_files/paper/2001/hash/1e4d36177d71bbb3558e43af9577d70e-Abstract.html.

* "Predictive Representations of State". 2002. pp. 1555–1561. http://www.eecs.umich.edu/~baveja/Papers/psr.pdf.

* Singh, Satinder; Michael R. James; Matthew R. Rudary (2004). "Predictive State Representations: A New Theory for Modeling Dynamical Systems". pp. 512–519. http://www.eecs.umich.edu/~baveja/Papers/uai2004psr.pdf.

* Wiewiora, Eric Walter (2008), Modeling Probability Distributions with Predictive State Representations, http://cseweb.ucsd.edu/~ewiewior/dissertation.pdf

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Predictive state representation. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Predictive_state_representation&oldid=3985818"