Q-Learning

Q-Learning is the off-policy implementation of TD Control. I first went through this with Flappy Bird Q-Learning.

Even though it’s off-policy, we don’t need Importance Sampling!

• We now consider off-policy learning of action-values $Q(s,a)$
• Next action is chosen using behaviour policy $A_{t+1}\sim \mu (\cdot |S_t)$
• But we consider alternative successor action $A^{\prime }\sim \pi (\cdot |S_t)$
• And update $Q(S_t,A_t)$ towards value of alternative action $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha (R_{t+1}+\gamma Q(S_{t+1},A^{\prime })-Q(S_t,A_t))$

Q-Learning Properties (Off-policy learning)

Q-Learning converges to optimal policy - even if you’re acting suboptimally.

Off-Policy Control with Q-Learning

• We now allow both behaviour and target policies to improve
• The target policy $\pi$ is greedy with respect to $Q(s,a)$ $\pi (S_{t+1})=\underset{a^{\prime }}{\mathrm{argmax}}Q(S_{t+1},a^{\prime })$

Q-Learning Control Algorithm $Q(S,A)\leftarrow Q(S,A)+\alpha (R+\gamma \underset{a^{\prime }}{\max }Q(S^{\prime },a^{\prime })-Q(S,A))$

From Pieter Abbeel Foundation of Deep RL:

• the notation hear is much clearer, the $k$ subscript shows how the value of Q updates over each iteration, similarly see Value Iteration

Related

When there are too many states, to generate the table Q(s,a), we can try Deep Q-Learning. Also see Double Q-Learning.