Deep RL with Q-Functions

Replay buffers: decorrelating the data

Last time ended on a sour note — value-based methods with function approximation are “not guaranteed to converge” — but “in practice we can actually get some very powerful and very useful reinforcement learning algorithms out of them.” The starting point is fitted Q-iteration: collect transitions $(s_i, a_i, s'_i, r_i)$ with any broad-support policy (these are off-policy methods), compute targets $y_i = r_i + \gamma \max_{a'} Q_\phi(s'_i, a')$, then regress $\phi \leftarrow \arg\min_\phi \frac{1}{2}\sum_i \|Q_\phi(s_i, a_i) - y_i\|^2$. Set every loop count to one — one transition, one target, one gradient step — and you get online Q-learning: “if you hear someone say Q-learning, they really mean this method.”

Two things are wrong with it. First, the update in step 3 “is not actually the gradient of any well-defined objective” — $Q_\phi$ appears inside $y_i$ but no gradient flows through it, so “Q-learning is not gradient descent.” (Differentiating properly gives residual gradient methods, so ill-conditioned they work poorly in practice.) Second, sequential transitions are highly correlated: $s_{t+1}$ looks a lot like $s_t$, so the network locally overfits each little window of trajectory in turn, never seeing enough broader context to fit the whole function. Parallel workers, as in online actor-critic, mitigate the correlation; but the fix that is easy and works very well is older — from the 1990s.

The buffer still needs feeding: an initial bad policy won’t have visited the interesting regions, so periodically the latest greedy policy — with epsilon-greedy exploration — is deployed back into the world to refresh $\mathcal{B}$ with better coverage. The resulting loop: collect data into the buffer, then repeat $K$ times (with $K = 1$ very common) sample a batch and take the gradient step $\phi \leftarrow \phi - \alpha \sum_i \frac{dQ_\phi}{d\phi}(s_i, a_i)\left(Q_\phi(s_i, a_i) - y_i\right)$.

Target networks: stop chasing your own tail

The other problem remains: the target $y_i$ contains $Q_\phi$, so every gradient step moves the target. The regression “is kind of chasing its own tail — it’s trying to catch up to itself and then changing out from under itself,” and the gradient does not account for the change. Full fitted Q-iteration doesn’t have this problem within step 3 — it regresses to convergence against frozen targets — but training to convergence on the wrong targets isn’t obviously good either. What we want is something in between.

Specializing to $K = 1$ recovers the classic deep Q-learning algorithm — DQN — which you will implement in homework 3:

One strangeness: right after a flip the target is zero steps stale, right before the next flip it is $N-1$ — the lag is uneven. A popular alternative updates $\phi' \leftarrow \tau \phi' + (1 - \tau)\phi$ at every step, with $\tau = 0.999$, so every step is lagged by the same amount. Interpolating network parameters sounds like it should produce garbage — networks are not linear in their parameters — but since $\phi'$ is just a lagged version of $\phi$ that stays close to it, the connection to Polyak averaging gives the trick some informal justification.

One algorithm, three processes

All the variants — online Q-learning, DQN, fitted Q-iteration — unify into one picture: a replay buffer at the center, with three processes running at different rates. Process 1, data collection, builds a policy from the current $\phi$ (epsilon-greedy or Boltzmann), runs it in the world, and streams transitions into the buffer (a ring buffer of, say, a million transitions, evicting the oldest). Process 2, the target update, periodically copies $\phi$ into $\phi'$ — or Polyak-averages — and is typically very slow. Process 3, the main learning loop, samples batches, computes targets with $\phi'$, and updates $\phi$. Online Q-learning: buffer of size one, all three processes at the same speed. DQN: processes 1 and 3 at the same speed (“a slightly arbitrary choice when you think about it”), process 2 slow, buffer large. Fitted Q-iteration: process 3 nested inside process 2 nested inside process 1.

Are the Q-values accurate? Overestimation and double Q-learning

A Q-function is not just an internal object — it is a prediction of total future discounted reward, so we can check it against reality. On Atari the qualitative picture is excellent: predicted Q rises as return rises; in Breakout the value spikes just before tunneling through to the ceiling; in Pong the Q-values for all actions agree while the ball is far away (many actions still recover) and sharply diverge at the moment only up saves the point. But the absolute numbers are systematically wrong: the predicted Q-value runs consistently above the actual discounted return — a pattern you will reproduce in homework 3.

The route to a fix is noticing where the max comes from: $\max_{a'} Q_{\phi'}(s', a') = Q_{\phi'}(s', \arg\max_{a'} Q_{\phi'}(s', a'))$. The same noisy network selects the action and evaluates it — if noise makes some action look erroneously good, that action gets picked and its inflated value gets used. Double Q-learning decorrelates the two roles: network $A$ selects the action, network $B$ evaluates it (and symmetrically for updating $B$), so an action selected for its positive noise under $A$ gets a sober evaluation from $B$ — the system is self-correcting. In practice you don’t add a new network; you use the two you already have:

$y = r + \gamma\, Q_{\phi'}\!\left(s', \arg\max_{a'} Q_{\phi}(s', a')\right)$

— the current network selects the action, the target network still evaluates it. This isn’t a perfect decorrelation, since $\phi'$ is periodically set to $\phi$, but “it actually mitigates a large fraction of the problems with overestimation.”

Multi-step returns

Where does learning signal come from in the target $y_{j,t} = r_{j,t} + \gamma \max_{a'} Q_{\phi'}(s_{j,t+1}, a')$? Early in training the Q-function is garbage, so the second term is mostly noise and the reward does all the work; later the Q-values dominate. Exactly as in actor-critic, we can trade bias for variance with an $n$-step target:

$y_{j,t} = \sum_{t'=t}^{t+n-1} \gamma^{t'-t}\, r_{j,t'} + \gamma^{n} \max_{a'} Q_{\phi'}(s_{j,t+n}, a')$

Less biased — the wrong Q-value is multiplied by $\gamma^n$, which is small — and typically much faster early in training, when the summed rewards carry the signal. The catch: for $n$ greater than 1 this is only correct with on-policy data, because the intermediate actions come from the sample, not your current policy. Fixes: ignore the problem (often works very well); dynamically cut the trace, choosing the largest $n$ for which the sampled actions all match the current greedy policy; or importance-sample the estimator (Munos et al., “Safe and efficient off-policy reinforcement learning”). Levine also leaves a thought exercise: there is a way to make $n$-step returns off-policy by learning a Q-like object conditioned on additional information — worth puzzling out.

Continuous actions: three ways to take the max

Everything so far assumed the $\max_{a'}$ is easy — enumerate the discrete actions. With continuous actions the max appears in two places, and the one inside the target computation sits in the inner loop of training, so it must be fast. Option one: stochastic optimization. The dead-simple version approximates $\max_a Q(s,a) \approx \max\left(Q(s, a_1), \ldots, Q(s, a_N)\right)$ over randomly sampled actions — crude, trivially parallelizable on a GPU, and if overestimation is your worry, a worse max may even help. The cross-entropy method (CEM) iteratively refines the sampling distribution toward the good regions, and CMA-ES is its fancier cousin; these “work okay for up to about 40-dimensional action spaces.” Option two: a function class whose max is closed-form. The NAF architecture outputs $V_\phi(s)$, $\mu_\phi(s)$, and a matrix $P_\phi(s)$ defining a Q-function quadratic in the action — arbitrarily nonlinear in the state, but with $\arg\max_a Q_\phi = \mu_\phi(s)$ and $\max_a Q_\phi = V_\phi(s)$ for free, at the cost of representational capacity when the true Q-function isn’t quadratic in $a$.

Option three: learn the maximizer. Train a second network $\mu_\theta(s)$ such that $\mu_\theta(s) \approx \arg\max_a Q_\phi(s, a)$, by solving $\theta \leftarrow \arg\max_\theta Q_\phi(s, \mu_\theta(s))$ — backpropagate through the Q-function into $\mu_\theta$ via $\frac{dQ_\phi}{d\theta} = \frac{d\mu_\theta}{d\theta}\frac{dQ_\phi}{da}$. This is DDPG (essentially the much earlier NFQCA), interpretable as a deterministic actor-critic method but “simplest to think of conceptually as a Q-learning algorithm”:

Making it work in practice

Q-learning methods are “quite a bit more finicky to use than policy gradient methods.” Debug on easy, reliable problems first — separate bug-hunting from hyperparameter tuning. Expect wild variation across problems and seeds: on Pong every seed produces a near-identical curve; on Venture some seeds work and some fail completely — run several, and remember flukes come in both directions. Large replay buffers (around a million transitions) improve stability — the algorithm looks more like fitted Q-iteration. Be patient: performance “might be no better than random for a long time” while exploration finds the good transitions, so schedule epsilon from high to low (early on the Q-function is garbage anyway, so random exploration does the heavy lifting), schedule learning rates, and use Adam.

Finally: double Q-learning “helps a lot in practice, is very simple to implement, and basically has no downsides” — use it. $n$-step returns help a lot early but bias the objective, especially for large $n$ — use with care.

Check yourself

Work these on paper, in the spirit of the lecture’s derivations and back-of-envelope arguments.

Problem 8.1 overestimation arithmetic

Two actions at state $s'$ have true Q-values $Q(s', a_1) = Q(s', a_2) = 0$. Your target network’s estimates carry independent noise: each is $+\epsilon$ or $-\epsilon$ with probability $\tfrac{1}{2}$. Compute $\mathbb{E}\left[\max_{a'} Q_{\phi'}(s', a')\right]$ and compare to the true value $\max_{a'} Q(s', a') = 0$. What happens with $k$ actions instead of 2?

Show solution

Enumerate the four equally likely noise outcomes: $(+,+) \to \max = +\epsilon$; $(+,-) \to +\epsilon$; $(-,+) \to +\epsilon$; $(-,-) \to -\epsilon$. So $\mathbb{E}[\max] = \tfrac{3}{4}\epsilon - \tfrac{1}{4}\epsilon = \tfrac{1}{2}\epsilon > 0$ — exactly the lecture’s “75 percent chance at least one noise is positive” argument made quantitative. With $k$ actions, the max is $-\epsilon$ only if all noises are negative, probability $2^{-k}$, so $\mathbb{E}[\max] = (1 - 2^{-k})\epsilon - 2^{-k}\epsilon = (1 - 2^{1-k})\epsilon$, which approaches $\epsilon$ as $k$ grows: the more actions you max over, the worse the overestimation. The bias then compounds, since each overestimated target inflates the Q-values used to compute the next targets.

Problem 8.2 double-Q mechanics

At $s'$ the true Q-values are $Q(s', a_1) = 1$, $Q(s', a_2) = 0$. The current network reports $Q_\phi(s', a_1) = 0.9$, $Q_\phi(s', a_2) = 1.4$ (noise made $a_2$ look great); the target network reports $Q_{\phi'}(s', a_1) = 1.1$, $Q_{\phi'}(s', a_2) = 0.2$. With $r = 0$ and $\gamma = 1$, compute the standard Q-learning target (using only $\phi'$) and the double Q-learning target. Which is closer to the true next value of 1?

Show solution

Standard: select and evaluate with $\phi'$, so $y = \max(1.1, 0.2) = 1.1$ — a modest overestimate, and had the noise pattern been flipped it would pick up whichever action $\phi'$ inflated. Double: $\arg\max_{a'} Q_\phi(s', a') = a_2$ (the current network’s noise picks the wrong action), but the evaluation comes from $\phi'$: $y = Q_{\phi'}(s', a_2) = 0.2$. Here the decorrelated noises punish the inflated pick — the selected action’s value is judged by a network that doesn’t share the flattering error, which is the self-correction mechanism. Note double-Q is not uniformly closer on every single sample (here it underestimates); the claim is about the systematic bias: standard Q-learning’s error is always pushed positive by the shared max, while double-Q’s errors can land on either side and largely cancel in expectation.

Problem 8.3 cutting the trace

Your deterministic greedy policy would take actions $(a^\star_t, a^\star_{t+1}, a^\star_{t+2}, a^\star_{t+3})$ at the states along a stored trajectory, and the stored actions match at steps $t$ and $t+1$ but differ at $t+2$. You want an $n$-step target for time $t$. What is the largest $n$ that keeps the target valid off-policy, and why does $n = 1$ never have this problem?

Show solution

The $n$-step target uses the stored rewards $r_t, \ldots, r_{t+n-1}$, which are only correct for your policy if the stored actions at steps $t+1, \ldots, t+n-1$ are the ones your policy would take ($a_t$ itself is fine — the Q-function conditions on it). Stored actions match at $t+1$ but not $t+2$, so rewards through $r_{t+2}$ would be off-policy: the largest valid choice is $n = 2$, using $r_t + \gamma r_{t+1} + \gamma^2 \max_{a'} Q_{\phi'}(s_{t+2}, a')$. For $n = 1$ the target $r_t + \gamma \max_{a'} Q_{\phi'}(s_{t+1}, a')$ uses no sampled action beyond $a_t$: the reward is conditioned on $(s_t, a_t)$, and the next step is handled by the max rather than the logged action — which is precisely the mechanism that makes one-step Q-learning off-policy in the first place. This dynamic trace-cutting works well when data is mostly on-policy and the action space is small, so matches are common.

Problem 8.4 target-network lag

With the flip-every-$N$ scheme, a target computed right after a flip uses parameters 0 steps stale, and one computed just before the next flip uses parameters $N-1$ steps stale. Polyak averaging $\phi' \leftarrow \tau \phi' + (1-\tau)\phi$ instead mixes a fraction of the current parameters in every step. With $\tau = 0.999$, roughly how many steps until the target network is “half new” — i.e., the total weight on parameters older than the switchover drops below one half? Compare to $N = 10{,}000$.

Show solution

After $m$ Polyak steps, the weight remaining on the original $\phi'$ is $\tau^m$ (each step keeps fraction $\tau$ of the old mixture). Setting $\tau^m = \tfrac{1}{2}$: $m = \ln(1/2) / \ln(0.999) \approx 0.693 / 0.001 = 693$ steps. So $\tau = 0.999$ gives an effective time constant of about $1/(1-\tau) = 1000$ steps, with a half-life near 700 — every target is lagged by the same effective amount, removing the uneven staleness of the flip scheme (0 to $N-1$ steps, averaging around $N/2 = 5000$). The interpolation of nonlinear network parameters is defensible here exactly because $\phi'$ is a gradually lagged version of $\phi$ and never strays far from it — the Polyak-averaging connection Levine cites; mixing two independently trained networks this way would be meaningless.

Problem 8.5 random-sampling max

The dead-simple continuous-action max approximates $\max_a Q(s, a)$ by the best of $N$ uniformly sampled actions. Suppose “good” actions — those within the top $\epsilon$ fraction of Q-values — occupy a fraction $\epsilon$ of the action space. What is the probability that at least one of $N$ samples is good, and how many samples do you need for 95 percent confidence when $\epsilon = 0.01$? Why does this scheme degrade in high-dimensional action spaces, and why might its sloppiness even help?

Show solution

Each sample misses the good set with probability $1 - \epsilon$, so $P(\text{at least one good}) = 1 - (1-\epsilon)^N$. For 95 percent: $(0.99)^N \le 0.05$, so $N \ge \ln(0.05)/\ln(0.99) \approx 298$ — about 300 samples, an easily parallelized mini-batch. The degradation is that this analysis is about quantiles, not distances: in $d$ dimensions the region within a small distance of the single best action has volume shrinking exponentially in $d$, so hitting a nearly-optimal action requires exponentially many samples — which is why sampling-based maxes (and refinements like CEM and CMA-ES) are only recommended “up to about 40 dimensions.” The sloppiness can help because the target’s max is exactly what drives overestimation (Problem 8.1): a weaker max selects noise less aggressively, so a cheaper, approximate maximization can act as a mild regularizer against overestimated targets.