Q-Learning

tags

Machine Learning Algorithms, Temporal Difference Learning, Reinforcement Learning ⭐

The Actor-Critic algorithm fits 2 function approximators: one for the policy, and one for the value function. A key problem with the policy gradient method is the high variance in the gradient update. Can we omit Policy Gradients completely?

Key Ideas

1. If we have a policy $\pi$, and we know $Q^{\pi }(s_t,a_t)$, then we can improve $\pi$ by setting ${\pi }^{\prime }(a|s)=1$ where $a={\mathrm{argmax}}_a{Q}^{\pi }(s,a)$.
2. We can compute the gradient to increase the probability of good actions $a$: if $Q^{\pi }(s,a)>V^{\pi }(s)$, then a is better than average ($V$ is expectation of $Q$ over $\pi (a|s)$).
3. It can be shown that in a fully-observed MDP, there is a policy that is both deterministic and optimal

Policy Iteration

1. evaluate $A^{\pi }(s,a)$
2. set $\pi \leftarrow {\pi }^{\prime }$ where ${\pi }^{\prime }=1$ if $a_t={\mathrm{argmax}}_{a_t}{A}^{\pi }(s_t,a_t)$ and $0$ otherwise

Value Iteration

Skips the explicit policy representation altogether. Key idea: argmax of advantage function is the same as argmax of Q-function.

1. set $Q(s,a)\leftarrow r(s,a)+\gamma E[V(s^{\prime })]$
2. set $V(s)\leftarrow {\mathrm{argmax}}_{a}Q(s,a)$

This simplifies the dynamic programming problem in policy iteration.

Fitted Value Iteration

We can use any most function approximators to represent $V(s)$.

1. set $y_i\leftarrow {\max }_{a_i}(r(s_i,a_i)+\gamma E[V_{\varphi }(s_i^{\prime })])$
2. set $\varphi \leftarrow {\mathrm{argmin}}_{\varphi }\frac{1}{2}\sum _i|V_{\varphi }(s_i)-y_i{|}^2$

This algorithm suffers from the curse of dimensionality. When the state space is large, the algorithm is computationally expensive. To get around this, we may sample states instead, with little change to the algorithm.

Fitted Q Iteration

Notice the $\max$ over $a_i$. This means that we need to know the outcomes for different actions! But what if we don’t know the transition dynamics? If we use a Q-table, then we arrive at an algorithm without needing to know the transition dynamics!

1. set $y_i\leftarrow r(s_i,a_i)+\gamma E[V_{\varphi }(s_i^{\prime })]$
2. set $\varphi \leftarrow {\mathrm{argmin}}_{\varphi }\frac{1}{2}\sum _i|Q_{\varphi }(s_i,a_i)-y_i{|}^2$

There is still a “max” hiding in $V_{\varphi }(s_i^{\prime })$. To get around this, we approximate $E[V(s_i^{\prime })]\approx {\max }_{a^{\prime }}Q(s_i^{\prime },a_i^{\prime })$:

1. Collect dataset $\{(s_i,a_i,s_i^{\prime },r_i)\}$ using some policy 1.1. set $y_i\leftarrow r(s_i,a_i)+\gamma {\max }_{a^{\prime }}Q(s_i^{\prime },a_i^{\prime })$ 1.2. set $\varphi \leftarrow {\mathrm{argmin}}_{\varphi }\frac{1}{2}\sum _i|Q_{\varphi }(s_i,a_i)-y_i{|}^2$ 1.3. goto 1.1 or 1

This works, even for off-policy samples (unlike Actor-Critic). In addition, there is only one network, hence no high-variance policy gradient methods. However, there are no convergence guarantees with non-linear function approximators!

Why is it off-policy? The algorithm doesn’t assume anything about the policy: given $s$ and $a$, the transition is independent of $\pi$.

In step 1.3, if the algorithm is off-policy, why would we ever need to go back to collect more samples in step 1? This is because on a random, poorly performing policy, we might not access some interesting states, that we would get after learning a better policy through Q-iteration.

Exploration in Q-learning

The policy used in Q-learning is deterministic. To get around this, we use a different, stochastic policy in step 1, when sampling actions to take. An example of such a policy is the epsilon-greedy, or Boltzmann exploration policy.

Non-Tabular Value Function Learning

In the tabular case, we have a Bellman contraction $BV$ such that $B$ is a contraction w.r.t. tho infinity-norm:

$$|BV-B\bar{V}|\le \gamma |V-\bar{V}{|}_{\mathrm{\infty }}$$

When we do fitted value iteration, we have another contraction $\mathrm{\Pi }$ that is a contraction wr.t. the $l_2$ norm (if we do the l2 norm regression):

$$|\mathrm{\Pi }V-\mathrm{\Pi }\bar{V}|\le |V-\bar{V}{|}_{\mathrm{\infty }}$$

However, $\mathrm{\Pi }B$ is not a contraction of any kind! All convergence guarantees is lost!

Q-learning is not gradient descent!

There are several problems with the regular Q-iteration algorithm:

1. Samples are temporally correlated
2. Target values are always changing
3. There is a no gradient through the target value, even though it seems we are doing a single gradient update step.
4. Single-sample updates

With 1 and 2, it’s possible to repeatedly overfit to the current sample.

Dealing with correlated samples

We can follow the same technique from actor-critic (synchronous/asynchronous parallel Q-learning) to alleviate correlated samples. The samples are however still temporally correlated. A better solution is to use a replay buffer.

Replay buffer

We have a buffer $B$ that stores samples of $(s_i,a_i,s_i^{\prime },r_i)$ Each time we do an update, we sample a batch i.i.d from $B$, resulting in a lower-variance gradient. The i.i.d results in decorrelated samples. In practice, we periodically update the replay buffer.

Dealing with the moving target

In the online Q-learning algorithm, the target Q moves. To resolve this we can use a target network:

$$\varphi \leftarrow \varphi -\alpha \sum _i\frac{d{Q}_{\varphi }}{d\varphi }(s_i,a_i)(Q_{\varphi }(s_i,a_i)-[r(s_i,a_i)+\gamma Q_{\varphi ‘}(s_i^{\prime },a_i^{\prime })])$$

The use of the target network $Q_{\varphi ‘}$ results in targets not changing in the inner loop.

DQN

DQN is the result of using a replay buffer, target network and some gradient clipping. See Playing Atari with Deep RL.

Double DQN

It has been shown imperatively that the learnt Q-values are numerically much higher than the true Q-values. Practically, this isn’t much of an issue: as the predicted Q-value increases, performance also increases.

The intuition behind why this happens, is that our target value $y_j$ is given by:

$$y_j=r_j+\gamma {\max }_{a_j^{\prime }}{Q}_{\varphi ‘}(s_j^{\prime },a_j^{\prime })$$

It is easy to show that:

$$E[\max (X_1,X_2)]\ge \max (E[X_1],E[X_2])$$

$Q_{\varphi ‘}(s^{\prime },a^{\prime })$ overestimates the next value, because it is noisy! The solution is to use 2 Q-functions, decorrelating the errors:

$${\max }_{a^{\prime }}{Q}_{\varphi ‘}(s^{\prime },a^{\prime })=Q_{\varphi ‘}(s^{\prime },{\mathrm{argmax}}_{a^{\prime }}(s^{\prime },a^{\prime }))$$

becomes:

$$Q_{{\varphi }_A}(s,a)\leftarrow r+\gamma Q_{{\varphi }_B}(s^{\prime },{\mathrm{argmax}}_{a^{\prime }}{Q}_{{\varphi }_A}(s^{\prime },a^{\prime }))$$

$$Q_{{\varphi }_B}(s,a)\leftarrow r+\gamma Q_{{\varphi }_A}(s^{\prime },{\mathrm{argmax}}_{a^{\prime }}{Q}_{{\varphi }_B}(s^{\prime },a^{\prime }))$$

To get 2 Q-functions, we use the current and target networks:

$$y=r+\gamma Q_{\varphi ‘}(s^{\prime },{\mathrm{argmax}}_{a^{\prime }}{Q}_{\varphi }(s^{\prime },a^{\prime }))$$

Q-learning with stochastic optimization

Taking max over a continuous action space can be expensive. A simple approximation is:

$${\max }_{a}Q(s,a)\approx \max \{Q(s,a_1),\dots ,Q(s,a_N)\}$$

where $(a_1,\dots ,a_N)$ is sampled from some distribution. A more accurate solution is to use the cross-entropy method.

Another option is to use a function class that is easy to maximize (e.g. using a quadratic function). This option is simple, but loses representational power.

The final option is to learn an approximate maximizer (e.g. DDPG). The idea is to train another network ${\mu }_{\varphi }(s)\approx {\mathrm{argmax}}_a{Q}_{\varphi }(s,a)$, by solving $\theta \leftarrow \mathrm{argmax}{Q}_{\varphi }(s,{\mu }_{\theta }(s))$

Q-learning

Q-learning learns an action-utility representation instead of learning utilities. We will use the notation $Q(s,a)$ to denote the value of doing action $a$ in state $s$.

$$U=ma{x}_{a}Q(s,a)$$

A TD agent that learns a Q-function does not need a model of the form $P(s^{\prime }|s,a)$, either for learning or for action selection. Q-learning is hence called a model-free method. We can write a constraint equation as follows:

$$Q(s,a)=R(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })$$

However, this equation requires a model to be learnt, since it depends on $P(s^{\prime }|s,a)$. The TD approach requires no model of state transitions.

The updated equation for TD Q-learning is:

$$Q(s,a)\leftarrow Q(s,a)+\alpha (R(s)+\gamma ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a))$$

which is calculated whenever action $a$ is executed in state $s$ leading to state $s^{\prime }$.

Q-learning has a close relative called SARSA (State-Action-Reward-State-Action). The update rule for SARSA is as follows:

$$Q(s,a)\leftarrow Q(s,a)+\alpha (R(s)+\gamma Q(s^{\prime },a^{\prime })-Q(s,a))$$

where $a^{\prime }$ is the action actually taken in state $s^{\prime }$. The rule is applied at the end of each $s,a,r,s^{\prime },a^{\prime }$ quintuplet, hence the name.

Whereas Q-learning backs up the best Q-value from the state reached in the observed transition, SARSA waits until an action is actually taken and backs up the Q-value for that action. For a greedy agent that always takes the action with best Q-value, the two algorithms are identical. When exploration is happening, they differ significanty.

Because Q-learning uses the best Q-value, it pays no attention to the actual policy being followed - it is an off-policy learning algorithm. However, SARSA is an on-policy algorithm.

Q-learning is more flexible in the sense that a Q-learning agent can learn how to behave well even when guided by a random or adversarial exploration policy. On the other hand, SARSA is more realistic: for example if the overall policy is even partly controlled by other agents, it is better to learn a Q-function for what will actually happen rather than what the agent would like to happen.

Q-learning has been shown to be sample efficient in the tabular setting (Jin et al., n.d.).

Q-learning with function approximation

To generalize over states and actions, parameterize Q with a function approximator, e.g. a neural net:

$$\delta =r_t+\gamma {\max }_{a}Q(s_{t+1},a;\theta )-Q(s_t,a;\theta )$$

and turn this into an optimization problem minimizing the loss on the TD error:

$$J(\theta )={\left|\delta \right|}^2$$

The key problem with Q-learning is stability, coined the “deadly triad”.

1. Off-policy learning
2. flexible function approximation
3. Bootstrapping

In the presence of all three, learning is unstable. DQN is the first algorithm that stabilized deep Q-learning (Playing Atari with Deep RL).

Bibliography

Jin, Chi, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. n.d. “Is Q-Learning Provably Efficient?” In Advances in Neural Information Processing Systems 31, edited by S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, 4863–73. Curran Associates, Inc. http://papers.nips.cc/paper/7735-is-q-learning-provably-efficient.pdf.