In TD learning, we can choose any $n$ we want. The question then becomes: what is the best $n$? Which $G_t^{(n)}$ yields the best approximation of the return? A common and effective solution is to use a weighted sum over all possible n-step TD targets, rather than selecting a single “best” n. The weights decay by a factor λ with n, $\lambda^{n-1}$. The intuition mirrors why: when computing returns, we discount future rewards because the further into the future we look, the less confident we are. To ensure the total weight (as n → ∞) sums to 1, we multiply each weight by (1-λ), because:

This weighted combination of n-step returns is the λ-return $G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$. TD learning that uses the λ-return for value updates is denoted TD(λ). The original method introduced above corresponds to TD(0).

Policy Gradient

All methods introduced above learn a state-value or action-value function and then select actions accordingly. In contrast, Policy Gradient methods learn the policy directly via a parameterized function with respect to $\theta$, $\pi(a \vert s; \theta)$. Define the reward function (the opposite of a loss function) as expected return, and train the algorithm to maximize this reward function. My next post explains why the policy gradient theorem holds (including a proof) and introduces a number of policy gradient algorithms.

In discrete space:

where $S_1$ is the initial starting state.

Or in continuous space:

where $d_{\pi_\theta}(s)$ is the stationary distribution of the Markov chain for $\pi_\theta$. If the definition of “stationary distribution” is unfamiliar, see reference.

Using gradient ascent, we can search for the θ that yields the highest return. It is natural to expect that policy-based methods are more useful in continuous spaces: because there are infinitely many actions and/or states, value-based approaches require estimating values over an unbounded domain and therefore are computationally much more expensive.

Policy Gradient Theorem

We can compute the gradient numerically by perturbing θ by a small ε in the k-th dimension. This works even when $J(\theta)$ is not differentiable (nice!), but it is, unsurprisingly, very slow.

Or we can compute it analytically:

In fact, there is strong theoretical justification for replacing $d(.)$ with $d_\pi(.)$:

See Sec 13.1 in Sutton & Barto (2017) for the reasoning.

Then,

This result is called the “Policy Gradient Theorem,” and it provides the theoretical basis for many policy gradient algorithms:

REINFORCE

REINFORCE, also called the Monte Carlo policy gradient method, uses $Q_\pi(s, a)$, a return estimate from MC methods based on episode samples, to update the policy parameters $\theta$.

A widely used REINFORCE variant subtracts a baseline from the return $G_t$ to reduce the variance of the gradient estimate while leaving the bias unchanged. For example, a common baseline is the state value, in which case the gradient ascent update uses $A(s, a) = Q(s, a) - V(s)$.

1. Initialize θ randomly.
2. Generate one episode $S_1, A_1, R_2, S_2, A_2, \dots, S_T$.
3. For t=1, 2, … , T:
   1. Estimate the return G_t from time step t onward.
   2. $\theta \leftarrow \theta + \alpha \gamma^t G_t \nabla \ln \pi(A_t \vert S_t, \theta)$.

Actor-Critic

When we learn a value function in addition to the policy, we obtain the Actor-Critic algorithm.

• Critic: updates value function parameters w; depending on the specific algorithm, it can be an action-value $Q(a \vert s; w)$ or a state-value $V(s; w)$.
• Actor: updates policy parameters θ in the direction recommended by the critic, $\pi(a \vert s; \theta)$.

Below is an example of how an action-value actor-critic algorithm operates.

1. Initialize s, θ, and w randomly; sample $a \sim \pi(a \vert s; \theta)$.
2. For t = 1… T:
   1. Sample reward $r_t \sim R(s, a)$ and next state $s’ \sim P(s’ \vert s, a)$.
   2. Then sample the next action $a’ \sim \pi(s’, a’; \theta)$.
   3. Update policy parameters: $\theta \leftarrow \theta + \alpha_\theta Q(s, a; w) \nabla_\theta \ln \pi(a \vert s; \theta)$.
   4. Compute the correction for the action value at time t:
      $G_{t:t+1} = r_t + \gamma Q(s’, a’; w) - Q(s, a; w)$
      and use it to update value function parameters:
      $w \leftarrow w + \alpha_w G_{t:t+1} \nabla_w Q(s, a; w) $.
   5. Update $a \leftarrow a’$ and $s \leftarrow s’$.

$\alpha_\theta$ and $\alpha_w$ are the learning rates for updating the policy and value-function parameters, respectively.

A3C

Asynchronous Advantage Actor-Critic (Mnih et al., 2016), abbreviated A3C, is a classic policy gradient method with a particular emphasis on parallel training.

In A3C, critics learn the state-value function $V(s; w)$, while multiple actors train in parallel and periodically synchronize with global parameters. Consequently, A3C is naturally suited for parallel training, for example, on a single machine with a multi-core CPU.

The state-value loss minimizes the mean squared error $\mathcal{J}_v (w) = (G_t - V(s; w))^2$, and gradient descent is used to obtain the optimal w. This state-value function serves as the baseline for the policy gradient update.

Algorithm outline:

1. Maintain global parameters θ and w, and thread-specific parameters θ’ and w'.
2. Initialize the time step t = 1.
3. While T <= T_MAX:
   1. Reset gradients: dθ = 0 and dw = 0.
   2. Synchronize thread-specific parameters with the global ones: θ’ = θ and w’ = w.
   3. $t_\text{start}$ = t and get $s_t$.
   4. While ($s_t \neq \text{TERMINAL}$) and ($t - t_\text{start} <= t_\text{max}$):
      1. Select action $a_t \sim \pi(a_t \vert s_t; \theta’)$, then receive reward $r_t$ and new state $s_{t+1}$.
      2. Update t = t + 1 and T = T + 1.
   5. Initialize the variable holding the return estimate $R = \begin{cases} 0 & \text{if } s_t \text{ is TERMINAL} \ V(s_t; w’) & \text{otherwise} \end{cases}$.
   6. For $i = t-1, \dots, t_\text{start}$:
      1. $R \leftarrow r_i + \gamma R$; here R is an MC estimate of $G_i$.
      2. Accumulate gradients with respect to θ’: $d\theta \leftarrow d\theta + \nabla_{\theta’} \log \pi(a_i \vert s_i; \theta’)(R - V(s_i; w’))$;
         Accumulate gradients with respect to w’: $dw \leftarrow dw + \nabla_{w’} (R - V(s_i; w’))^2$.
   7. Synchronously update θ using dθ, and update w using dw.

A3C enables parallelism across multiple training agents. The gradient accumulation step (6.2) can be viewed as a reformulation of minibatch-based stochastic gradient updates: each thread independently nudges w or θ slightly in its own gradient direction.

Evolution Strategies

Evolution Strategies (ES) is a model-agnostic optimization approach. It searches for an optimal solution by imitating Darwin’s theory of evolution by natural selection. ES requires two prerequisites: (1) solutions must be able to interact with the environment to test whether they solve the problem; (2) we must be able to compute a fitness score for each solution. We do not need to know the environment configuration in order to solve the task.

Assume we begin with a population of random solutions. Each candidate can interact with the environment, and only those with high fitness scores survive (only the fittest can survive in a competition for limited resources). A new generation is produced by recombining the configurations (gene mutation) of the high-fitness survivors. This loop repeats until the solutions are sufficiently strong.

Unlike the MDP-based approaches described above, ES learns the policy parameters $\theta$ directly, without value approximation. Assume the distribution over parameters $\theta$ is an isotropic multivariate Gaussian with mean $\mu$ and fixed covariance $\sigma^2I$. The gradient of $F(\theta)$ is:

We can rewrite the expression in terms of a “mean” parameter $\theta$ (distinct from $\theta$ above; this $\theta$ is the base gene for subsequent mutation), $\epsilon \sim N(0, I)$, and thus $\theta + \epsilon \sigma \sim N(\theta, \sigma^2)$. $\epsilon$ controls the magnitude of Gaussian noise added to generate mutations:

As a black-box optimization method, ES provides another approach to RL problems (In my original writing, I used the phrase “a nice alternative”; Seita pointed me to this discussion and thus I updated my wording.). It has several advantageous properties (Salimans et al., 2017) that keep it fast and straightforward to train:

• ES does not require value function approximation.
• ES does not perform gradient back-propagation.
• ES is invariant to delayed or long-term rewards.
• ES is highly parallelizable with minimal data communication.

Known Problems

Exploration-Exploitation Dilemma

The exploration versus exploitation dilemma is discussed in my earlier post. When an RL problem involves an unknown environment, this tradeoff is particularly critical for achieving strong performance: without sufficient exploration, we cannot learn the environment well enough; without sufficient exploitation, we cannot complete the reward optimization objective.

Different RL algorithms handle the balance between exploration and exploitation in different ways. In MC methods, Q-learning, or many on-policy algorithms, exploration is commonly implemented via ε-greedy. In ES, exploration is achieved through perturbations of the policy parameters. Keep this in mind when developing a new RL algorithm.

Deadly Triad Issue

We value the efficiency and flexibility of TD methods that rely on bootstrapping. However, when off-policy learning, nonlinear function approximation, and bootstrapping are combined within a single RL algorithm, training can become unstable and difficult to converge. This phenomenon is known as the deadly triad (Sutton & Barto, 2017). Many deep-learning-based architectures have been proposed to address this issue, including DQN, which stabilizes learning via experience replay and an occasionally frozen target network.

Case Study: AlphaGo Zero

The game of Go has been an exceptionally difficult problem in Artificial Intelligence for decades, until recent years. AlphaGo and AlphaGo Zero are two programs developed by a DeepMind team. Both use deep Convolutional Neural Networks (CNN) and Monte Carlo Tree Search (MCTS), and both have been demonstrated to reach the level of professional human Go players. Unlike AlphaGo, which relied on supervised learning from expert human moves, AlphaGo Zero used only reinforcement learning and self-play, without human knowledge beyond the basic rules.

With the RL background above, we can now examine how AlphaGo Zero works. Its core component is a deep CNN over the game-board configuration (specifically, a ResNet with batch normalization and ReLU). The network produces two outputs:

• $s$: the board configuration represented as 19 x 19 x 17 stacked feature planes. There are 17 features per position: 8 past configurations (including the current one) for the current player, plus 8 past configurations for the opponent, plus 1 feature indicating color (1=black, 0=white). The color must be encoded explicitly because the network plays against itself, and the roles of current player and opponent alternate across steps.
• $p$: the probability of selecting a move among 19^2 + 1 candidates (19^2 board positions plus the pass action).
• $v$: the predicted probability of winning under the current configuration.

During self-play, MCTS further refines the action-probability distribution $\pi \sim p(.)$, and then action $a_t$ is sampled from this improved policy. The reward $z_t$ is binary, indicating whether the current player eventually wins the game. Each move yields an episode tuple $(s_t, \pi_t, z_t)$, which is stored in the replay memory. For space reasons, this post omits MCTS details; see the original paper if you would like more information.

The network is trained on samples from the replay memory by minimizing the loss:

where $c$ is a hyperparameter controlling the strength of the L2 penalty to prevent overfitting.

AlphaGo Zero simplified AlphaGo by eliminating supervised learning and combining separate policy and value networks into a single network. This design delivered significantly improved performance with substantially shorter training time. I strongly recommend reading two and papers side by side and comparing them, it is very fun.

I know this is a long read, but I hope it is worthwhile. If you notice mistakes and errors in this post, don’t hesitate to contact me at [lilian dot wengweng at gmail dot com]. See you in the next post! :)

Cited as:

@article{weng2018bandit,
  title   = "A (Long) Peek into Reinforcement Learning",
  author  = "Weng, Lilian",
  journal = "lilianweng.github.io",
  year    = "2018",
  url     = "https://lilianweng.github.io/posts/2018-02-19-rl-overview/"
}

References

[1] Yuxi Li. Deep reinforcement learning: An overview. arXiv preprint arXiv:1701.07274. 2017.

[2] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction; 2nd Edition. 2017.

[3] Volodymyr Mnih, et al. Asynchronous methods for deep reinforcement learning. ICML. 2016.

[4] Tim Salimans, et al. Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864 (2017).

[5] David Silver, et al. Mastering the game of go without human knowledge. Nature 550.7676 (2017): 354.

[6] David Silver, et al. Mastering the game of Go with deep neural networks and tree search. Nature 529.7587 (2016): 484-489.

[7] Volodymyr Mnih, et al. Human-level control through deep reinforcement learning. Nature 518.7540 (2015): 529.

[8] Ziyu Wang, et al. Dueling network architectures for deep reinforcement learning. ICML. 2016.

[9] Reinforcement Learning lectures by David Silver on YouTube.

[10] OpenAI Blog: Evolution Strategies as a Scalable Alternative to Reinforcement Learning

[11] Frank Sehnke, et al. Parameter-exploring policy gradients. Neural Networks 23.4 (2010): 551-559.

[12] Csaba Szepesvári. Algorithms for reinforcement learning. 1st Edition. Synthesis lectures on artificial intelligence and machine learning 4.1 (2010): 1-103.

If you notice mistakes and errors in this post, please don’t hesitate to contact me at [lilian dot wengweng at gmail dot com] and I would be super happy to correct them right away!