Model free learning

Question 1

Does MC use bootstrapping?

Answer 1

No, MC learns from complete episodes, no bootstrapping.

Question 2

What is the idea behind the mote carlo approach for policy evaluation?

Answer 2

Our goal is to estimate the value function for each state. The idea of MC is to estimate that value function (expected returns) by average sample traces (empirical means).

Question 3

Describe the first visit monte carlo algorithm for policy evaluation

Answer 3

for each trace t,
for all s in t,
1)append return from the first appearance of s in t to to Returns(s)
2) set V(s) = average(Returns(s))

Question 4

What is the difference between the first and every visit method of monte-carlo.

Answer 4

Every visist calculates the return each time s appears in a trace and averages all of them. First visit only calculates the return of the first time we visit s in the trace.

Question 5

What is the formula for a running mean

Answer 5

mu_new = mu + alpha(x - mu)

Question 6

When should we use the running mean instead of actual mean?

Answer 6

If the world is non-stationary the running mean incorporates the effect that “old” episodes count less then new episodes. Also in case of the running mean we don’t have to store k_s, the number of times we have “seen” s.

Question 7

What is the main advantage of TD (Temporal Difference) learnging?

Answer 7

It combines the sampling from monte carlo and bootstrapping from dynamic programming.

Question 8

What is the value update method for TD?

Answer 8

V(S_t)

Question 9

What is the:

1) Temporal difference error?
2) Temporal differece target?

Answer 9

1) r_t + gamma*V(S_t+1) - V(S_t)

2) r_t + gamma*V(S_t+1)

Question 10

What are the main advantages of TD?

Answer 10

1) TD can before the final outcome
2) TD can learn without a final outcome
3) TD can learn from incomplete episodes

Question 11

How is the bias and variance of TD and MC?

Answer 11

MC high variance, no bias

TD low variance, some bias

Question 12

Give a comparision of MC and TD?

Answer 12

MC:
1) Good convergence
2) Good convergence for function approx.
3) Not very sensitive to inital value
4) Simple
5) Usually more efficent in non-markov environments
TD:
1) Usually more efficient than MC
2) Converges to V_pi(S)
3) Convergense not guarnateed for function approx.
4) more sensitive to inital values
5) Usually more efficent in markov environments