TD Control

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 behavior policy $a_{t+1}\sim \mu (\cdot |s_t)$
• But we consider alternative successor action $a^{\prime }\sim \pi (\cdot |s_t)$
  • As you’ll see below, we let $a^{\prime }=\arg {\max }_{a}Q(s_{t+1},a)$
• 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)]$
• Learned from here

Q-Learning Properties (Off-policy learning)

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

• Sarsa is the on-policy version of q-learning

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_t,a_t)\leftarrow Q(s_t,a_t)+\alpha [r_{t+1}+\gamma \underset{a^{\prime }}{\max }Q(s_{t+1},a^{\prime })-Q(s_t,a_t)]$

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.