CS代考计算机代写 algorithm Reinforcement Learning
Reinforcement Learning
Maria-Florina Balcan Carnegie Mellon University
April 20, 2015
Readings:
• Mitchell, chapter 13
• Kaelbling, et al., Reinforcement Learning: A Survey
Today:
• Learning of control policies
• Markov Decision Processes
• Temporal difference learning
• Q learning
Slides courtesy: Tom Mitchell
Tom Mitchell, April 2011
Overview
• Different from ML pbs so far: decisions we make will be about actions to take, such as a robot deciding which way to move next, which will influence what we see next.
• Our decisions influence the next example we see.
• Goal will be not just to predict (say, whether there is a door in front of us or not) but to decide what to do.
• Model: Markov Decision Processes.
Tom Mitchell, April 2011
Reinforcement Learning
Main impact of our actions will not come right away but instead that will only come later.
V*(s)E[r γr γ2r …] t t1 t2
[Sutton and Barto 1981; Samuel 1957; …]
Tom Mitchell, April 2011
Reinforcement Learning: Backgammon
Learning task:
• chose move at arbitrary board states
Training signal:
• final win or loss at the end of the game
Training:
• played 300,000 games against itself
Algorithm:
• reinforcement learning + neural network
Result:
• World-class Backgammon player
[Tessauro, 1995]
Tom Mitchell, April 2011
Outline
• Learning control strategies
– Credit assignment and delayed reward – Discountedrewards
• Markov Decision Processes – Solving a known MDP
• Online learning of control strategies
– When next-state function is known: value function V*(s) – When next-state function unknown: learning Q*(s,a)
• Role in modeling reward learning in animals
Tom Mitchell, April 2011
Agent lives in some environment; in some state:
• Robot: where robot
is, what direction it is
pointing, etc.
• Backgammon, state
of the board (where all pieces are).
Goal: Maximize long term discounted reward. I.e.: want a lot of reward, prefer getting it earlier to getting it later.
Tom Mitchell, April 2011
Markov Decision Process = Reinforcement Learning Setting
• Set of states S
• Set of actions A
• At each time, agent observes state st S, then chooses action at A
• Then receives reward rt , and state changes to st+1
• Markov assumption: P(st+1 | st, at, st-1, at-1, …) = P(st+1 | st, at)
• Also assume reward Markov: P(rt | st, at, st-1, at-1,…) = P(rt | st, at)
E.g., if tell robot to move forward one meter, maybe it ends up moving forward 1.5 meters by mistake, so where the robot is at time t+1 can be a probabilistic function of where it was at time t and the action taken, but shouldn’t depend on how we got to that state.
• The task: learn a policy : S A for choosing actions that maximizes for every possible starting state s0
Tom Mitchell, April 2011
Reinforcement Learning Task for Autonomous Agent
Execute actions in environment, observe results, and • Learn control policy : SA that maximizes
from every state s S
Example: Robot grid world, deterministic reward r(s,a)
• Actions: move up, down, left, and right
[except when you are in the top-right you stay there, and say any action that bumps you into a wall leaves you were you were]]
• reward fns r(s,a) is deterministic with reward 100 for entering the top-right and 0 everywhere else.
Tom Mitchell, April 2011
Reinforcement Learning Task for Autonomous Agent
Execute actions in environment, observe results, and • Learn control policy : SA that maximizes
from every state s S
Yikes!!
• Function to be learned is : SA
• But training examples are not of the form
• They are instead of the form <
Tom Mitchell, April 2011
Value Function for each Policy
• Given a policy : SA, define
assuming action sequence chosen
according to , starting at state s expected discounted reward we will get starting from state s if we follow policy π.
• Goal: find the optimal policy * where
• For any MDP, such a policy exists!
• We’ll abbreviate V *(s) as V*(s)
policy whose value function is the maximum out of all policies simultaneously for all states
• Note if we have V*(s) and P(st+1|st,a), we can compute *(s)
Tom Mitchell, April 2011
Value Function – what are the V(s) values?
Tom Mitchell, April 2011
Value Function – what are the V(s) values?
Tom Mitchell, April 2011
Value Function – what are the V*(s) values?
Tom Mitchell, April 2011
Immediate rewards r(s,a) State values V*(s)
Tom Mitchell, April 2011
Recursive definition for V*(S)
assuming actions are chosen according to the optimal policy, *
Value 𝑉∗(𝑠1) of performing optimal policy from 𝑠1, is expected reward of the first action 𝑎1 taken plus 𝛾 times the expected value, over states 𝑠2 reached by performing action 𝑎1 from 𝑠1, of the value 𝑉∗(𝑠2) of performing the optimal policy from then on.
optimal value of any state s is the expected reward of performing 𝜋∗(𝑠) from s plus
𝛾 times the expected value, over states s’ reached by performing that action from state s, of the optimal value of s’.
Tom Mitchell, April 2011
Value Iteration for learning V* : assumes P(St+1|St, A) known
Initialize V(s) to 0 [optimal value can get in zero steps] For t=1, 2, … [Loop until policy good enough]
Loop for s in S Inductively, if V is optimal discounted reward can get in t-1 steps, Q(s,a) is value of performing action a from state s and then being
Loop for a in A •
End loop End loop
optimal from then on for the next t-1 steps.
Optimal expected discounted reward can get by taking an action and then being optimal for t-1 steps= optimal expected discounted reward can get in t steps.
V(s) converges to V*(s) Dynamic programming
Tom Mitchell, April 2011
Value Iteration for learning V* : assumes P(St+1|St, A) known
Initialize V(s) to 0 [optimal value can get in zero steps] For t=1, 2, … [Loop until policy good enough]
Loop for s in S Loop for a in A
•
End loop End loop
each round we are computing the value of performing the optimal t-step policy starting from t=0, then t=1, t=2, etc, and since 𝛾𝑡 goes to 0, once t is large enough this will be close to the optimal value 𝑉∗ for the infinite-horizon case.
V(s) converges to V*(s) Dynamic programming
Tom Mitchell, April 2011
Value Iteration for learning V* : assumes P(St+1|St, A) known
Initialize V(s) to 0 [optimal value can get in zero steps] For t=1, 2, … [Loop until policy good enough]
Loop for s in S Loop for a in A
•
End loop End loop
• •
• •
Round t=0 we have V(s)=0 for all s.
After round t=1, a top-row of 0, 100, 0 and a bottom-row of 0, 0, 100.
After the next round (t=2), a top row of 90, 100, 0 and a bottom row of 0, 90, 100.
After the next round (t=3) we will have a top-row of 90, 100, 0 and a bottom row of 81, 90, 100, and it will then stay there forever
Tom Mitchell, April 2011
Value Iteration
So far, in our DP, each round we cycled through each state exactly once.
Interestingly, value iteration works even if we randomly traverse the environment instead of looping through each state and action methodically
• but we must still visit each state infinitely often on an infinite run
• For details: [Bertsekas 1989]
• Implications: online learning as agent randomly roams
If for our DP, max (over states) difference between two successive value function estimates is less than , then the value of the greedy policy differs from the optimal policy by no more than
Tom Mitchell, April 2011
So far: learning optimal policy when we know P(st | st-1, at-1)
What if we don’t?
Tom Mitchell, April 2011
Q learning
Define new function, closely related to V*
V*(s) is the expected discounted reward of following the optimal policy from time 0 onward.
Q(s,a) is the expected discounted reward of first doing action a and then following the optimal policy from the next step onward.
If agent knows Q(s,a), it can choose optimal action without knowing P(st+1|st,a) !
Just chose the action that maximizes the Q value
And, it can learn Q without knowing P(st+1|st,a) using something very much like the dynamic programming algorithm we used to compute V*.
Tom Mitchell, April 2011
Bellman equation.
Consider first the case where P(s’| s,a) is deterministic
Immediate rewards r(s,a) State values V*(s) State-action values Q*(s,a)
Tom Mitchell, April 2011
[simplicity assume the transitions and rewards are deterministic. ]
Optimal value of a state s is the maximum, over actions a’ of Q(s,a’).
Given current approx 𝑄 to Q, if we are in state s and perform action a and get to state s’, update our estimate 𝑄(𝑠, 𝑎) to the reward r we got plus gamma times the maximum over a’ of 𝑄(𝑠′, 𝑎′)
Tom Mitchell, April 2011
Tom Mitchell, April 2011
Tom Mitchell, April 2011
Use general fact:
Tom Mitchell, April 2011
Rather than replacing the old estimate with the new estimate, you want to compute a weighted average of them: (1 − α𝑛) times your old estimate plus α𝑛 times your new estimate. This way you average out the probabilistic fluctuations, and one can show that this still converges.
Tom Mitchell, April 2011
MDP’s and RL: What You Should Know
• Learning to choose optimal actions A
• From delayed reward
• By learning evaluation functions like V(S), Q(S,A)
Key ideas:
• If next state function St x At St+1 is known
– can use dynamic programming to learn V(S)
– once learned, choose action At that maximizes V(St+1)
• If next state function St x At St+1 unknown
– learn Q(St,At) = E[V(St+1)]
– to learn, sample St x At St+1 in actual world
– once learned, choose action At that maximizes Q(St,At)
Tom Mitchell, April 2011
