View Full Document

Max-norm Projections for Factored MDPs



View the full content.
View Full Document
View Full Document

4 views

Unformatted text preview:

International Joint Conference on Artificial Intelligence IJCAI 01 vol 1 pp 673 680 Seattle Washington August 2001 Max norm Projections for Factored MDPs Carlos Guestrin Computer Science Dept Stanford University guestrin cs stanford edu Daphne Koller Computer Science Dept Stanford University koller cs stanford edu Abstract Markov Decision Processes MDPs provide a coherent mathematical framework for planning under uncertainty However exact MDP solution algorithms require the manipulation of a value function which specifies a value for each state in the system Most real world MDPs are too large for such a representation to be feasible preventing the use of exact MDP algorithms Various approximate solution algorithms have been proposed many of which use a linear combination of basis functions as a compact approximation to the value function Almost all of these algorithms use an approximation based on the weighted norm Euclidean distance this approach prevents the application of standard convergence results for MDP algorithms all of which are based on max norm This paper makes two contributions First it presents the first approximate MDP solution algorithms both value and policy iteration that use maxnorm projection thereby directly optimizing the quantity required to obtain the best error bounds Second it shows how these algorithms can be applied efficiently in the context of factored MDPs where the transition model is specified using a dynamic Bayesian network 1 Introduction Over the last few years Markov Decision Processes MDPs have been used as the basic semantics for optimal planning for decision theoretic agents in stochastic environments In the MDP framework the system is modeled via a set of states which evolve stochastically The key problem with this representation is that in virtually any real life domain the state space is quite large However many large MDPs have significant internal structure and can be modeled compactly if the structure is exploited in the



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Max-norm Projections for Factored MDPs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Max-norm Projections for Factored MDPs and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?