Q-learning

Following the pattern of state values, then action values, the one-step temporal difference update for action values

is called SARSA. Presumably you can define multi-step versions of SARSA analogous to $n$-step TD updates, and SARSA($\lambda$) analogous to TD($\lambda$).

Both TD state-value estimation methods and SARSA are considered on-policy, because they expect that the transition is representative of the policy $\pi$ under evaluation, and they converge to the state and action values of that policy. We can modify SARSA to be off-policy by replacing the action $a_{t+1}$ actually taken by the optimal choice:

This is the Q-learning update.

Deep Q-learning

(references: original Atari paper, Julien Vitay's notes)

Like all TD updates, Q-learning and SARSA can also be derived as stochastic gradient descent steps on a squared loss, for example,

so that each step attempts to bring our approximation $Q_\phi$ closer to an improved target. Unfortunately we lose the standard SGD convergence guarantees because the state transitions we see are not iid---they are typically correlated over time---and because the the target changes as we update the parameters $\phi$ so we are not actually optimizing any fixed objective. This leads to instability. But this can be addressed with two tricks: experience replay and by using an infrequently-updated target network.

Architecture of $Q$-networks. We can have a deep network take as input both $s_t$ and $a_t$ and produce a single estimated $Q$-value, or it can just take $s_t$ and produce estimated $Q$-values for all possible actions $a_t$.Insofar as these correspond to feeding in the action at the first layer versus the last layer, respectively, we could in principle also consider schemes that feed in the action at some intermediate layer. This could be used to support a richer action space while still sharing some of the state representation across actions from the same state. The latter is usually preferred when we have a small number of discrete actions, since we can maximize over $Q$-values using a single forward pass.

An even better approach is the 'duelling network' architecture: have the second-to-last layer of the network separately predict $V(s)$ and the advantages for each action $A(s, a)$, and then define a final parameterless layer to simply combine the two,

subtracting the mean advantage so that the value function is identifiable (otherwise we could add a constant to $V$ and subtract the same constant from $A$ without changing the results).

The original Deep Q-learning worked impressively well in Atari games but was very sample-inefficient. Some improvements proposed in later papers were to use duelling networks, prioritized experience replay, and double Q-learning, described below.

Double Q-learning

(references: Double Q-learning (van Hasselt 2010) and Deep RL with Double Q-learning (van Hasselt, Suez, Silver 2015))

In noisy environments, $Q$-learning tends to overestimate values because it targets the maximum of the estimated $Q$-values, and noise affects these asymmetrically.

To see this, suppose that all actions from some state have true value $Q^*(s, a) = 1$, but that we only see unbiased estimates of their values. We expect that some of these estimates will be less than 1 and a roughly equal number will be greater than 1. Importantly, it is extremely unlikely that they are all less than 1, meaning that, with high probability, their maximum will be greater than 1. So we'll overestimate the maximum $Q$-value even if our individual estimates were totally unbiased.More rigorously, this follows from Jensen's inequality and the convexity of the $\max$ function.

It's not obvious that this is a problem: it would be fine if the overestimation were uniform, and indeed we know that overestimating values can be useful to encourage exploration. But the practical evidence is that the overestimation is not uniform, and that addressing the issue helps in practice.

One way to do this is to use the double estimator, which requires two independent unbiased estimators of the action values. We pick an action using the first, but evaluate it using the second. This ensures that we get an unbiased estimate of the value of whatever action we pick. In the example above, we would pick whatever action $a^*$ maximizes our first noisy estimates, but then report an unbiased estimate of its value (which is just $1$), so the double estimator is unbiased. It can be shown that the double estimator is not unbiased in general---it tends to slightly underestimate the maximum---but is unbiased if the quantities being estimated are iid (van Hasselt, 2010).

In the deep RL setting where we are already maintaining a target network in addition to our online network, we can just use these as our two sources of estimates (von Hasselt, Suez, Silver 2015). That is, instead of targeting

we target

still using the target network to compute the target value, but for an action selected by the online network. We are fudging things slightly from the 'pure' double Q-learning setting, because the online and target networks are not totally independent of each other, but apparently this still works pretty well.