next up previous
Next: Policies with Internal State Up: Partially Observable Environments Previous: State-Free Deterministic Policies

State-Free Stochastic Policies

Some improvement can be gained by considering stochastic policies; these are mappings from observations to probability distributions over actions. If there is randomness in the agent's actions, it will not get stuck in the hall forever. Jaakkola, Singh, and Jordan [50] have developed an algorithm for finding locally-optimal stochastic policies, but finding a globally optimal policy is still NP hard.

In our example, it turns out that the optimal stochastic policy is for the agent, when in a state that looks like a hall, to go east with probability tex2html_wrap_inline2374 and west with probability tex2html_wrap_inline2376 . This policy can be found by solving a simple (in this case) quadratic program. The fact that such a simple example can produce irrational numbers gives some indication that it is a difficult problem to solve exactly.

Leslie Pack Kaelbling
Wed May 1 13:19:13 EDT 1996