10. Deep Reinforcement Learning › 10.4 Deep Reinforcement Learning

Section 10.4
Deep Reinforcement Learning

The big picture idea of deep reinforcement learning is to replace the large lookup tables (i.e., \(V\) or \(Q\)) required by traditional reinforcement learning algorithms and replace them with neural networks. This opens up the possibility of problem domains with much larger state spaces and also the ability to share information across related domains (e.g., through pre-training and fine tuning) or take advantage of inherent symmetries in the problem.

The ultimate goal is still to find a policy \(\pi_\theta\) that maximizes the expected sum of rewards, i.e.,

\begin{align} \text{maximize}_{\theta} \quad E_{\tau \sim P_\theta(\tau)} \left[ \sum_{t=1}^{T} \gamma^{t-1} R(s_t, a_t) \right] \tag{307}\end{align}

where \(P_\theta(\tau) = P(s_1) \prod_{t=1}^{T} \pi_\theta(a_t \mid s_t) P(s_{t+1} \mid s_t, a_t)\), and there have been many methods developed to this end. These can be broadly classified into the following five categories:

10.4.1 Imitation Learning

Imitation learning treats the problem of finding a policy as a classic supervised machine learning problem. The policy \(\pi_\theta: \cS \to P(\cA)\) is approximated by a neural network of appropriate architecture. A dataset of training examples is then collected. The examples represent trajectories from a good policy, which typically come from observing an expert. The goal is then to learn a policy that reproduces the actions taken by the expert,

\begin{align} \begin{array}{ll} \text{minimize (over $\theta$)} & -\sum_{(s, a) \in \cD} \log \pi_\theta(a \mid s) \end{array} \tag{308}\end{align}

where \(\cD\) is a dataset of (observed) state-action pairs.

Imitation learning is conceptually simple but suffers from several limitations. First, it can be susceptible to distributional shift. That is, states encountered by agent may differ from those appearing in training dataset of expert demonstrations. A good example of this is learning to drive. If an expert driver never gets into dangerous situations then a self-driving car will never learn how to get out of such situations. The second limitation is causal confusion where the agent may correlate actions with irrelevant cues and therefore not generalise well to unseen states. Last, since there are no rewards, the agent is unlikely to improve beyond the level of the expert demonstrator.

10.4.2 Policy Gradient

Policy gradient methods also approximates \(\pi_\theta: \cS \to P(\cA)\) with a neural network. However, unlike imitation learning they run the (current) policy to collect \(N\) trajectories: \((s_{i,1}, a_{i,1}, s_{i,2}, a_{i,2}, \ldots, s_{i,T}, a_{i,T})\) for \(i = 1, \ldots, N\). Rewards are measured along the way. The trajectories and associated rewards are then used to improve policy

\begin{align} \nabla_\theta L(\theta) = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_\theta \overbrace{\log \pi_\theta(a_{i,t} \mid s_{i,t})}^{\text{policy log-likelihood}} \left( \underbrace{\left(\sum_{\tau=t}^{T} \gamma^{\tau-t} r_{i,\tau}\right) - b}_{\substack{\text{reward to go, $G$,} \\ \text{relative to baseline}}}\right) \tag{309}\end{align}

where the baseline \(b\) is used to reduce the variance of the gradient estimator. A common choice for \(b\) is a guess for the value of state \(s_{i,t}\) (see the discussion of Actor-Critic methods later in the lecture).

Unfortunately policy gradient methods are very inefficient and suffer from unstable training due to noisy gradients. They are highly susceptible to getting stuck in pool local minima.

10.4.3 Deep Q-Learning

Instead of directly learning a policy, deep Q-learning (DQN) approximates the q-function \(Q_\pi: \cS \times \cA \to \reals\) with a neural network.2 The method optimizes a loss reminiscent of TD learning discussed above using stochastic gradient descent (SGD),

\begin{align} L(\theta) &= \sum_{(s,a,r,s') \in \cD} \left(r + \gamma \max_{a'} Q(s', a'; \theta^{\text{prev}}) - Q(s,a; \theta) \right)^2 \tag{310}\end{align}

where \(\theta^{\text{prev}}\) are the network parameters from a previous training step. These parameters are updated every \(C\) steps and held fixed between updates.

The DQN approach was initially demonstrated on having agents learn to play Atari 2600 games [73, 74]. The state of the game is represented as a stack of the last four greyscale frames rescaled to 64-by-64 pixels. The actions are known in advance and vary in number from 4 to 18 depending on the game. A simple CNN architecture with three convolutional layers is used to learn the q-function for each game, and trained for about 38 days of game experience (50 million frames).

One of the problems that DQN had to resolve was that sequential interactions are highly correlated and hence lead to poor learning. So instead of directly learning from immediate interactions (where actions are taken via a \(\epsilon\)-greedy policy) the DQN algorithm stores experiences in a replay buffer,

\begin{align} \cD &= \{(s, a, r, s')\} \tag{311}\end{align}

It then randomly samples mini-batches for SGD from this buffer. Each \((s, a, r, s')\) tuple in the buffer can be used multiple times leading to better sample efficiency. Together with the slowly moving target network (i.e., \(Q(\cdot, \cdot; \theta^{\text{prev}})\)) in the loss, experience replay helped to stabilize training making deep Q-learning effective. In fact DQN achieved remarkable performance and was even able to discover novel strategies to maximize its score on certain games such as breakout. It set in motion a line of work that eventually led to AlphaGo, AlphaZero and AlphaFold, though these later models use a mix of methods and are not pure \(Q\)-learning.

10.4.4 Actor-Critic Models

Actor-critic models combine policy gradient and value-based approaches such as DQN resulting in a method that is faster, more stable, and learns an explicit policy that can be deterministic or stochastic.

Recall that the baseline \(b\) from the policy update equation reduces variance,

\begin{align} \nabla_\theta L(\theta) = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t}) \left( \left(\sum_{\tau=t}^{T} \gamma^{\tau-t} r_{i,\tau}\right) - b \right) \tag{312}\end{align}

Well, it turns out that a good choice for \(b\) is the average reward for state \(s\), so we can write

\begin{align} \nabla_\theta L(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t}) \big( Q_\pi(s_{i,t}, a_{i,t}) - V_\pi(s_{i,t}) \big) \tag{313}\end{align}

where we have also replaced the reward to go with \(Q_\pi\), its expectation.

Define advantage to be the difference in expected reward between taking action \(a\) in state \(s\) and the average from taking all possible actions,

\begin{align} A_\pi(s, a) &= Q_\pi(s, a) - V_\pi(s) \tag{314}\\ &\approx R(s, a) + \gamma V_\pi(s') - V_\pi(s) \tag{315}\end{align}

where the second line is since \(Q_\pi(s, a) = R(s, a) + \gamma E_{s' \sim P(\cdot \mid s, a)} \left[ V_\pi(s') \right] \approx R(s, a) + \gamma V_\pi(s')\). Intuitively this measures the relative merit of choosing action \(a\) over all other actions.

The above shows that we can estimate advantage from the value function alone,

\begin{align} A_\pi(s_{i,t}, a_{i,t}) &\approx r_{i,t} + \gamma V_\pi(s_{i,t+1}) - V_\pi(s_{i,t}) \tag{316}\end{align}

which substituting back into the gradient of the loss gives

\begin{align} \nabla_\theta L(\theta) &\approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t}) \big( r_{i,t} + \gamma V_\pi(s_{i,t+1}) - V_\pi(s_{i,t}) \big) \tag{317}\end{align}

Actor-critic models train one network to estimate \(\pi_\theta\) and another to estimate \(V_\pi\). We collect trajectories into a dataset, \(\{(s_{i,t}, y_{i,t})\}\) where \(y_{i,t} = \sum_{\tau=t}^T \gamma^{\tau-t} r_{i,\tau}\) is the discounted sum of rewards, and then use supervised learning for neural network with parameters \(\phi\) to estimate \(V_\pi\). Here the loss is defined to regress the value function to the measured discounted sum of rewards

\begin{align} L(\phi) = \frac{1}{2} \sum_{i=1}^{N} \sum_{t=1}^{T} \|\hat{V}_\pi(s_{i,t}; \phi) - y_{i,t}\|^2 \tag{318}\end{align}

This approach is sometimes called basic Monte Carlo estimation. An alternative known as bootstrapping uses the previous learned value function as an estimate of future rewards and hence does not need full trajectories,

\begin{align} L(\phi) &= \frac{1}{2} \sum_{i=1}^{N} \sum_{t=1}^{T} \|\hat{V}_\pi(s_{i,t}; \phi) - (r_{i,t} + \gamma \hat{V}_\pi(s_{i,t+1}; \phi^{\text{prev}}) \|^2 \tag{319}\end{align}

In both approaches we alternate between updating the parameters \(\theta\) of the policy model and updating the parameters \(\phi\) of the value function model.

10.4.5 Proximal Policy Optimization

The final method that we will discuss is proximal policy optimization (PPO) [91], which is a state-of-the-art method for deep reinforcement learning. The central idea is to stabilize training by limiting how much a policy can change during each update.

Define the probability ratio \(\rho_t(\theta)\) relative to some previous model \(\theta_{\text{prev}}\) as

\begin{align} \rho_t(\theta) &= \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{prev}}}(a_t \mid s_t)} \tag{320}\end{align}

The PPO method the implements a clipped loss

\begin{align} L(\theta) &= E \left[ \min \{ \rho_t(\theta) A_\pi(s_t, a_t),\, \text{clip}_{[1-\epsilon, 1+\epsilon]}(\rho_t(\theta)) A_\pi(s_t, a_t) \} \right] \tag{321}\end{align}

for learning the parameters of the policy network. Other loss variants are possible (e.g., using a KL divergence penalty) but the details are beyond the scope of this lecture.

A variant of this approach called group relative policy optimization (GRPO) [92] developed by DeepSeek is the current de facto standard approach used in the final stages of LLM finetuning. However, much like other areas of deep learning, the research on deep reinforcement learning is very active and new variants are being proposed all the time.

  1. 1. Technically not really a reinforcement learning method since it has no exploration or exploitation, but can still be used to learn policies.
  2. 2. For small action spaces this is often implemented as a function from \(\cS\) to \(\reals^{|\cA|}\), i.e., from states to a vector of values for each action. The Q-function value can then be determined by reading off the appropriate component in the output for any given action.