MarkovDecisionProcessesReinforcementLearning创新.pptVIP

Markov Decision Processes Reinforcement Learning Megan Smith Lehigh University, Fall 2006 Outline Stochastic Process Markov Property Markov Chain Markov Decision Process Reinforcement Learning RL Techniques Example Applications Stochastic Process Quick definition: A Random Process Often viewed as a collection of indexed random variables Useful to us: Set of states with probabilities of being in those states indexed over time We’ll deal with discrete stochastic processes Stochastic Process Example Classic: Random Walk Start at state X0 at time t0 At time ti, move a step Zi where P(Zi = -1) = p and P(Zi = 1) = 1 - p At time ti, state Xi = X0 + Z1 +…+ Zi Markov Property Also thought of as the “memoryless” property A stochastic process is said to have the Markov property if the probability of state Xn+1 having any given value depends only upon state Xn Very much depends on description of states Markov Property Example Checkers: Current State: The current configuration of the board Contains all information needed for transition to next state Thus, each configuration can be said to have the Markov property Markov Chain Discrete-time stochastic process with the Markov property Industry Example: Google’s PageRank algorithm Probability distribution representing likelihood of random linking ending up on a page Markov Decision Process (MDP) Discrete time stochastic control process Extension of Markov chains Differences: Addition of actions (choice) Addition of rewards (motivation) If the actions are fixed, an MDP reduces to a Markov chain Description of MDPs Tuple (S, A, P(.,.), R(.))) S - state space A - action space Pa(s, s’) = Pr(st+1 = s’ | st = s, at = a) R(s) = immediate reward at state s Goal is to maximize some cumulative function of the rewards Finite MDPs have finite state and action spaces Simple MDP Example Recycling MDP Robot Can search for trashcan, wait for someone to bring a trashcan, or go home and recharge battery Has two energy levels – high and low Search