TD Learning

Question 1

What are the three main categories of RL algorithms?

Answer 1

Model based (most information required, but generally easy)
Value function based/model free 
Policy search (most general/simple, but generally difficult)

Question 2

Describe model based learning

Answer 2

Model based learning attempts to derive the overall model for the MDP and compute Q* and Pi from the model using an MDP solver (such as VI/PI)
(s,a,r)* -> model learner <->T/R -> MDP Solve -> Q* -> argmax - Policy

Question 3

Describe value function (model free) based learning

Answer 3

Attempts to directly learn the value function based on states, actions, and rewards.
(s,a,r)* -> Value update <-> Q -> argmax -> Policy

Question 4

Describe policy search learning

Answer 4

Attempts to directly derive the optimal policy by updating the policy directly.
(s,a,r)* -> policy update <-> policy

Question 5

Under what criteria does the value function estimate Vt(S) converge to the true value V(s) as t -> inf? In general what values satisfy these criteria?

Answer 5

1. Sum(alpha_t) -> inf
2. Sum(alpha_t^2) < inf

alpha_t = 1/t^n where n in (1/2, 1]

Question 6

What is the TD(lambda) update rule?

Answer 6

Episode T
For all s, e(s) = 0 at start of episode, V_t(s) = V_t-1(s)
After s_t-1 -> r_t -> s_t (step t):
e(s_t-1) = e(s_t-1) +1
For all s:
V_t(s) = V_t(s) + alpha_t (r_t + gamma*V_t-1(s_t) - V_t-1(s_t-1)) e(s)
e(s) = lambda * gamma * e(s)

Question 7

What are some issues with TD(1)?

Answer 7

TD(1) does not use all data that is available. It can get stuck with bad estimates for a long time if it does not see certain paths. Inefficient, high variance.

Question 8

Which TD(lambda) version is equivalent to maximum likelihood? Under which criteria?

Answer 8

TD(0), if finite data is presented infinitely

Question 9

Empirically, how does TD(lambda) tend to behave when varying lambda?

Answer 9

Error decreases initially as lambda increases but eventually increases as lambda approaches one.

Question 10

What are some issues with TD(0)

Answer 10

We get a biased estimate because we are using one step estimation