Policy Iteration for Factored MDPs

Abstract

Many large MDPs can be represented compactly using a dynamic Bayesian network. Although the structure of the value function does not retain the structure of the process, recent work has shown that value functions in factored MDPs can often be approximated well using a decomposed value function: a linear combination of <I>restricted</I> basis functions, each of which refers only to a small subset of variables. An approximate value function for a particular policy can be computed using approximate dynamic programming, but this approach (and others) can only produce an approximation relative to a distance metric which is weighted by the stationary distribution of the current policy. This type of weighted projection is ill-suited to policy improvement. We present a new approach to value determination, that uses a simple closed-form computation to directly compute a least-squares decomposed approximation to the value function <I>for any weights</I>. We then use this value determination algorithm as a subroutine in a policy iteration process. We show that, under reasonable restrictions, the policies induced by a factored value function are compactly represented, and can be manipulated efficiently in a policy iteration process. We also present a method for computing error bounds for decomposed value functions using a variable-elimination algorithm for function optimization. The complexity of all of our algorithms depends on the factorization of system dynamics and of the approximate value function.

Appears in Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI2000)

Cited by in corpus (21)

• Nonapproximability Results for Partially Observable Markov Decision Processes
• Value Function Approximation in Zero-Sum Markov Games
• Near-optimal Reinforcement Learning in Factored MDPs
• Representation Policy Iteration
• VIREL: A Variational Inference Framework for Reinforcement Learning
• Factored Value Iteration Converges
• Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures
• Restricted Value Iteration: Theory and Algorithms
• Risk-Sensitive Compact Decision Trees for Autonomous Execution in Presence of Simulated Market Response
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
• A Clustering Approach to Solving Large Stochastic Matching Problems
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
• Open Problems in Universal Induction & Intelligence
• Decision Making Agent Searching for Markov Models in Near-Deterministic World
• Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games
• Preconditioned Temporal Difference Learning
• Feature Dynamic Bayesian Networks
• Recursive Optimization of Finite Blocklength Allocation to Mitigate Age-of-Information Outage