Learning Factored Representations for PartiallyObservable Markov Decision Processes

Abstract The problem of reinforcement learning in a non-Markov environment isexplored using a dynamic Bayesian network, where conditional independence assumptions between random variables are compactly representedby network parameters. The parameters are learned on-line, and approximations are used to perform inference and to compute the optimal valuefunction. The relative effects of inference and value function approximations on the quality of the final policy are investigated, by learning tosolve a moderately difficult driving task. The two value function approximations, linear and quadratic, were found to perform similarly, but thequadratic model was more sensitive to initialization. Both performed below the level of human performance on the task. The dynamic Bayesiannetwork performed comparably to a model using a localist hidden state representation, while requiring exponentially fewer parameters. 1 Introduction Reinforcement learning (RL) addresses the problem of learning to act so as to maximizea reward signal provided by the environment. Online RL algorithms try to find a policy which maximizes the expected time-discounted reward. They do this through experienceby performing sample backups to learn a value function over states or state-action pairs. If the decision problem is Markov in the observable states, then the optimal value functionover state-action pairs yields all of the information required to find the optimal policy for the decision problem. When complete knowledge of the environment is not available, stateswhich are different may look the same; this uncertainty is called perceptual aliasing [1], and causes decision problems to have dynamics which are non-Markov in the perceivedstate