A Planning Algorithm for Predictive State Representations

1 Predictive State Representation

We assume that we are given a system consisting of a dis­ crete, finite set of n states S, a discrete finite set of actions A, and a discrete finite set of observations 0. The interaction with the system takes place at discrete time intervals. The initial state of the system s0 is drawn from an initial probabil­ ity distribution over states I. On every time step t, an action at is chosen according to some policy. Then the underlying state changes to St+l and a next observation Ot+l is gener­ ated. The system is Markovian, in the sense that for every action, the transition to the next state is generated according to a probability distribution described by an (n x n) transition matrix ya. Similarly, for a given observation o and action a, the next observation is generated according to an ( n x n) diag­ onal observation matrix oao, where Oft is the probability of observation o when action a is selected and state i is reached. Since we are interested in optimal control, rather than predic­ tion, we also assume that there exists a set of reward vectors Ra for each action a, where Rf is the reward for taking action a in underlying state i.

PSRs are based on the notion of tests. A test is an ordered sequence of action-observation pairs q = a1 o1 ... akok. The prediction for test q is the probability of the sequence of ob­ servations o1 .. . ok being generated, given the sequence of actions a1 ... ak. The prediction for a test q given prior history h, denoted p(qlh), is the probability of seeing the sequence of observations of q after seeing history h and taking the se­ quence of actions specified by q. For any set of tests Q, its prediction vector is:

A set of tests Q is a PSR if its prediction vector forms a suffi­ cient statistic for the dynamical system, i.e., if all tests can be predicted based on p( Q I h) . Of particular interest is the case of linear PSRs, in which there exists a projection vector mq for any test q such that

Littman et al. also define an outcome function u map­ ping tests into n-dimensional vectors defined recursively by: u(t:) = en and u(aoq) = (Taoa,ou(q)T)T, where t: repre­ sents a null test and en is the (1 x n) vector of all Is. Each component u; ( q) indicates the probability of the test q when its sequence of actions is applied from state s;. A set of tests Q = { qili = 1, 2, .. k} is called linearly independent if the outcome vectors of its tests u(q1 ), u(q2 ), ... u(qk) are linearly independent. Using this definition, such a set Q can be found by a simple search algorithm in polynomial time, given the POMDP model of the environment. Littman, Sut­ ton and Singh (2002) showed that the outcome vectors of the tests in Q can be linearly combined to produce the outcome vector for any test.

2 Policy evaluation using PSRs

We assume that we are given a policy 1r : 1{ --+ A and that the initial start state of the system, s0 , is drawn according to the staring probability distribution I. If we consider a given horizon t, only a finite number of tests of length t are possible when starting from I. Let Wt be this set of possible tests.

The value of a memory less policy 1r with respect to a given start state distribution I is the expected return over all possi­ ble tests that can occur when the starting state is drawn form I and then behavior is generated according to policy 1r:

where R(qii, 1r) is the expected return for test q given that the initial state is drawn from I and policy 1r is followed.

Let U be the (lSI x lll'ti) matrix formed by concatenating the outcome vectors for all tests in Ill t, and u+ be its pseu­ doinverse. The columns of U define the probability of each test in Ill t when applied from each underlying state. Conse­ quently, IU represents the probability of the tests in Ill t when starting in I.

For each action-observation combination ao, we can define a (Ill' tl x Ill' t I) projection matrix:

and a projection vector:

Considering the probability distribution over tests that 1r generates and the expected return of a test q given I and 1r, we have:

This evaluation method requires a large amount of precom­ putation, but it can be useful if a small horizon suffices to get a good policy.

3 Policy iteration for PSRs

Similar to POMDPs in PSRs we can define action-value func­ tions on the level of tests. The action-value function for tak­ ing action a after test q can be computed as:

Then, the policy of the agent can be improved by choosing an action greedily with respect to this action-value function:

The agent must, in other words, select the best pol­ icy tree rooted at each decision point and each time step. Therefore the total running time of the algorithm is 0(151 3 (IAIIOI)h) and the complexity of the algorithm is only single-exponential in the horizon time.

4 Experimental results

We experimented with a standard gridworld navigation task used in the POMDP literature (Cassandra, 1994; Parr& Rus­ sell, I996). The environment is a ( 4 x 4) grid. The agent has four actions, N, S, E, and W, which change its location deterministically to one of the four neighboring states. There is one goal state, in the lower right comer, which generates a distinct observation and a reward of +I. All the other states are perceptually aliased and generate no reward. The initial probability distribution is uniform over all states except the goal. Taking any action in the goal state moves the agent uni­ formly randomly to one of the other states.

For this problem we have 6 possible combinations of action-observation (ao) pairs: I-Nnothing,2-Wnothing,3Enothing,4-Snothing,5-Egoal,6-Sgoal. The set of core tests Q found consists of I61inearly independent tests: 4, 5, 6, 15, 36, 46, 436, 446, 4436, 3336, I336, 44336, 43336, 31336. We tried this problem for finite horizon case with a discount factor 1 = 0.8. Figure I indicates the performance of the algorithm on this problem.

5 Conclusion and future work

The key difficulty for our planning algorithm is that the num­ ber of possible tests grows exponentially with the horizon length. Hence, the algorithm cannot be used for large prob­ lems or for the infinite horizon case. However, this is not worse than other existing exact solution methods for solving POMDPs. Our hope is that good approximations of the opti­ mal solution can be found efficiently.