mdp-tutorial

An Introduction toMarkov Decision ProcessesBob Givan Ron ParrPurdue University Duke UniversityMDP Tutorial - 1OutlineMarkov Decision Processes defined (Bob)• Objective functions• PoliciesFinding Optimal Solutions (Ron)• Dynamic programming• Linear programmingRefinements to the basic model (Bob)• Partial observability• Factored representationsMDP Tutorial - 2Stochastic Automata with UtilitiesA Markov Decision Process (MDP) modelcontains:• A set of possible world states S• A set of possible actions A• A real valued reward function R(s,a)• A description T of each action’s effects in each state.We assume the Markov Property: the effects of an actiontaken in a state depend only on that state and not on theprior history.MDP Tutorial - 3Stochastic Automata with UtilitiesA Markov Decision Process (MDP) modelcontains:• A set of possible world states S• A set of possible actions A• A real valued reward function R(s,a)• A description T of each action’s effects in each state.We assume the Markov Property: the effects of an actiontaken in a state depend only on that state and not on theprior history.MDP Tutorial - 4·fi·fiRepresenting ActionsDeterministic Actions:• T :SA S For each state and action we specify a new state.0.60.4Stochastic Actions:• T :SA Prob()S For each state and action wespecify a probability distribution over next states.Represents the distribution P(s’ | s, a).MDP Tutorial - 5·fifi·Representing ...