Programming Exercises & MC for Control: On and Off Policy

1. Programming exercises: Angel lms.wsu.edu Submit via zip or tar Write-up, Results, Code Doodle: class presentations Student Responses First visit vs. every visit

2. MC for Control, On-Policy (soft-policies)

3. Off Policy Control Learn about while following Behavior policy vs. Estimation policy

5. = policy followed, = policy evaluating (s,a): probability that will take action a (s,a)=1 b/c is deterministic, and wouldnt consider s,a if didnt select

6. = policy followed, = policy evaluating (s,a): probability that will take action a (s,a)=1 b/c is deterministic, and wouldnt consider s,a if didnt select First, were looking at tail of episode including the exploration action

8. Example: were considering some s,a and we eventually get return of 100. Say is unlikely to reach this goal state: is 0.01 on one of the steps to the goal (the rest are 1) w = 100, N = 100*100, D = 100 Q = N/D = 100 Consider a different s,a, where we get a return of 100 but the goal state is always reached ( = 1.0 for all steps in the trajectory) W = 1, N = 100, D = 1 Q = N/D = 100

9. Example: were considering some s,a and we eventually get return of 100. Say is unlikely to reach this goal state: is 0.01 on one of the steps to the goal (the rest are 1) w = 100, N = 100*100, D = 100 Q = N/D = 100 Consider a different s,a, where we get a return of 100 but the goal state is always reached ( = 1.0 for all steps in the trajectory) W = 1, N = 100, D = 1 Q = N/D = 100 Second: the difference here is how updates for these different s,a pairs will be calculated in the future . We have to weight the updates based on how likely we are to experience them based on the sampling policy .

10. http://www.eecs.wsu.edu/~tayl orm/14_580/go.p df Achieving Master Level Play in 99 Computer Go 5 Minutes: Summary of paper? Whats interesting? How could you improve their idea?

17. DP, MC, DP Model, online/offline update, bootstrapping, on-policy/off-policy Batch updating vs. online updating

18. Ex. 6.4 V(B) =

19. Ex. 6.4 V(B) = V(A) = 0? Or ?

21. 4 is terminal state V(3) = 0.5 TD(0) here is better than MC. Why ?

22. 4 is terminal state V(3) = 0.5 TD(0) here is better than MC. Why ? Visit 2 on the kth time, state 3 visited 10k times Variance for MC will be much higher than TD(0) because of bootstrapping

23. 4 is terminal state V(3) = 0.5 Change so that R(3,a,4) was deterministic Now, MC would be faster

24. Ex 6.4, Figure 6.7. RMS goes down and up again with high learning rates. Why?

25. 6.1: Chris? The agent is driving home from work from a new work location, but enters the freeway from the same point. Thus, the second leg of our drive home is the same as it was before. But say traffic is significantly worse on the first leg of this drive than it was on the first leg before the change in work locations. With a MC approach, we'd be modifying our estimates of the time it takes to make the second leg of the drive based solely on the fact that the entire drive took longer. With a TD method, we'd only be modifying our estimates based on the next state, so this method would be able to learn that the first leg of the drive is taking longer and our estimates would reflect that. The second leg would be unaffected.

26. The above example illustrates a general difference between the estimates found by batch TD(0) and batch Monte Carlo methods. Batch Monte Carlo methods always find the estimates that minimize mean-squared error on the training set, whereas batch TD(0) always finds the estimates that would be exactly correct for the maximum-likelihood model of the Markov process. In general, the maximum-likelihood estimate of a parameter is the parameter value whose probability of generating the data is greatest. In this case, the maximum-likelihood estimate is the model of the Markov process formed in the obvious way from the observed episodes: the estimated transition probability from to is the fraction of observed transitions from that went to , and the associated expected reward is the average of the rewards observed on those transitions. Given this model, we can compute the estimate of the value function that would be exactly correct if the model were exactly correct. This is called the certainty-equivalence estimate because it is equivalent to assuming that the estimate of the underlying process was known with certainty rather than being approximated. In general, batch TD(0) converges to the certainty-equivalence estimate. This helps explain why TD methods converge more quickly than Monte Carlo methods. In batch form, TD(0) is faster than Monte Carlo methods because it computes the true certainty-equivalence estimate. This explains the advantage of TD(0) shown in the batch results on the random walk task (Figure 6.8). The relationship to the certainty-equivalence estimate may also explain in part the speed advantage of nonbatch TD(0) (e.g., Figure 6.7). Although the nonbatch methods do not achieve either the certainty-equivalence or the minimum squared-error estimates, they can be understood as moving roughly in these directions. Nonbatch TD(0) may be faster than constant- $\alpha$ MC because it is moving toward a better estimate, even though it is not getting all the way there. At the current time nothing more definite can be said about the relative efficiency of on-line TD and Monte Carlo methods. Finally, it is worth noting that although the certainty-equivalence estimate is in some sense an optimal solution, it is almost never feasible to compute it directly. If is the number of states, then just forming the maximum-likelihood estimate of the process may require memory, and computing the corresponding value function requires on the order of computational steps if done conventionally. In these terms it is indeed striking that TD methods can approximate the same solution using memory no more than and repeated computations over the training set. On tasks with large state spaces, TD methods may be the only feasible way of approximating the certainty- equivalence solution.

27. maximum-likelihood models, certainty- equivalence estimates Josh: while TD and MC use very similar methods for computing the values of states they will converge to a different values. It surprises me, I actually had to read the chapter a couple of times to come to grips with it. Example 6.4 in section 6.3 is what finally convinced me however I had to go over it several times