A Distributional Perspective on Reinforcement Learning

Introduction

One of the major tenets of reinforcement learning states that, when not otherwise constrained in its behaviour, an agent should aim to maximize its expected utility $Q$, or value (Sutton & Barto, 1998). Bellman’s equation succintly describes this value in terms of the expected reward and expected outcome of the random transition $(x,a)\to(X^{\prime},A^{\prime})$:

In this paper, we aim to go beyond the notion of value and argue in favour of a distributional perspective on reinforcement learning. Specifically, the main object of our study is the random return $Z$ whose expectation is the value $Q$. This random return is also described by a recursive equation, but one of a distributional nature:

The distributional Bellman equation states that the distribution of $Z$ is characterized by the interaction of three random variables: the reward $R$, the next state-action $(X^{\prime},A^{\prime})$, and its random return $Z(X^{\prime},A^{\prime})$. By analogy with the well-known case, we call this quantity the value distribution.

Although the distributional perspective is almost as old as Bellman’s equation itself (Jaquette, 1973; Sobel, 1982; White, 1988), in reinforcement learning it has thus far been subordinated to specific purposes: to model parametric uncertainty (Dearden et al., 1998), to design risk-sensitive algorithms (Morimura et al., 2010b, a), or for theoretical analysis (Azar et al., 2012; Lattimore & Hutter, 2012). By contrast, we believe the value distribution has a central role to play in reinforcement learning.

Contraction of the policy evaluation Bellman operator. Basing ourselves on results by Rösler (1992) we show that, for a fixed policy, the Bellman operator over value distributions is a contraction in a maximal form of the Wasserstein (also called Kantorovich or Mallows) metric. Our particular choice of metric matters: the same operator is not a contraction in total variation, Kullback-Leibler divergence, or Kolmogorov distance.

Instability in the control setting. We will demonstrate an instability in the distributional version of Bellman’s optimality equation, in contrast to the policy evaluation case. Specifically, although the optimality operator is a contraction in expected value (matching the usual optimality result), it is not a contraction in any metric over distributions. These results provide evidence in favour of learning algorithms that model the effects of nonstationary policies.

Better approximations. From an algorithmic standpoint, there are many benefits to learning an approximate distribution rather than its approximate expectation. The distributional Bellman operator preserves multimodality in value distributions, which we believe leads to more stable learning. Approximating the full distribution also mitigates the effects of learning from a nonstationary policy. As a whole, we argue that this approach makes approximate reinforcement learning significantly better behaved.

We will illustrate the practical benefits of the distributional perspective in the context of the Arcade Learning Environment (Bellemare et al., 2013). By modelling the value distribution within a DQN agent (Mnih et al., 2015), we obtain considerably increased performance across the gamut of benchmark Atari 2600 games, and in fact achieve state-of-the-art performance on a number of games. Our results echo those of Veness et al. (2015), who obtained extremely fast learning by predicting Monte Carlo returns.

From a supervised learning perspective, learning the full value distribution might seem obvious: why restrict ourselves to the mean? The main distinction, of course, is that in our setting there are no given targets. Instead, we use Bellman’s equation to make the learning process tractable; we must, as Sutton & Barto (1998) put it, “learn a guess from a guess”. It is our belief that this guesswork ultimately carries more benefits than costs.

Setting

We consider an agent interacting with an environment in the standard fashion: at each step, the agent selects an action based on its current state, to which the environment responds with a reward and the next state. We model this interaction as a time-homogeneous Markov Decision Process $(\mathcal{X},\mathcal{A},R,P,\gamma)$. As usual, $\mathcal{X}$ and $\mathcal{A}$ are respectively the state and action spaces, $P$ is the transition kernel $P(\cdot\,|\,x,a)$, $\gamma\in$ is the discount factor, and $R$ is the reward function, which in this work we explicitly treat as a random variable. A stationary policy $\pi$ maps each state $x\in\mathcal{X}$ to a probability distribution over the action space $\mathcal{A}$.

The return $Z^{\pi}$ is the sum of discounted rewards along the agent’s trajectory of interactions with the environment. The value function $Q^{\pi}$ of a policy $\pi$ describes the expected return from taking action $a\in\mathcal{A}$ from state $x\in\mathcal{X}$, then acting according to $\pi$:

Fundamental to reinforcement learning is the use of Bellman’s equation (Bellman, 1957) to describe the value function:

In reinforcement learning we are typically interested in acting so as to maximize the return. The most common approach for doing so involves the optimality equation

These operators are useful as they describe the expected behaviour of popular learning algorithms such as SARSA and Q-Learning. In particular they are both contraction mappings, and their repeated application to some initial $Q_{0}$ converges exponentially to $Q^{\pi}$ or $Q^{*}$, respectively (Bertsekas & Tsitsiklis, 1996).

The Distributional Bellman Operators

In this paper we take away the expectations inside Bellman’s equations and consider instead the full distribution of the random variable $Z^{\pi}$. From here on, we will view $Z^{\pi}$ as a mapping from state-action pairs to distributions over returns, and call it the value distribution.

Our first aim is to gain an understanding of the theoretical behaviour of the distributional analogues of the Bellman operators, in particular in the less well-understood control setting. The reader strictly interested in the algorithmic contribution may choose to skip this section.

A distributional equation $U\overset{D}{:=}V$ indicates that the random variable $U$ is distributed according to the same law as $V$. Without loss of generality, the reader can understand the two sides of a distributional equation as relating the distributions of two independent random variables. Distributional equations have been used in reinforcement learning by Engel et al. (2005); Morimura et al. (2010a) among others, and in operations research by White (1988).

2 The Wasserstein Metric

The main tool for our analysis is the Wasserstein metric $d_{p}$ between cumulative distribution functions (see e.g. Bickel & Freedman, 1981, where it is called the Mallows metric). For $F$, $G$ two c.d.fs over the reals, it is defined as

where the infimum is taken over all pairs of random variables $(U,V)$ with respective cumulative distributions $F$ and $G$. The infimum is attained by the inverse c.d.f. transform of a random variable $\mathcal{U}$ uniformly distributed on $$:

For $p<\infty$ this is more explicitly written as

Given two random variables $U$, $V$ with c.d.fs $F_{U}$, $F_{V}$, we will write $d_{p}(U,V):=d_{p}(F_{U},F_{V})$. We will find it convenient to conflate the random variables under consideration with their versions under the $\inf$, writing

whenever unambiguous; we believe the greater legibility justifies the technical inaccuracy. Finally, we extend this metric to vectors of random variables, such as value distributions, using the corresponding $L_{p}$ norm.

Consider a scalar $a$ and a random variable $A$ independent of $U,V$. The metric $d_{p}$ has the following properties:

We will need the following additional property, which makes no independence assumptions on its variables. Its proof, and that of later results, is given in the appendix.

Let $A_{1},A_{2},\dots$ be a set of random variables describing a partition of $\Omega$, i.e. $A_{i}(\omega)\in\{0,1\}$ and for any $\omega$ there is exactly one $A_{i}$ with $A_{i}(\omega)=1$. Let $U,V$ be two random variables. Then

Let $\mathcal{Z}$ denote the space of value distributions with bounded moments. For two value distributions $Z_{1},Z_{2}\in\mathcal{Z}$ we will make use of a maximal form of the Wasserstein metric:

We will use $\bar{d}_{p}$ to establish the convergence of the distributional Bellman operators.

$\bar{d}_{p}$ is a metric over value distributions.

3 Policy Evaluation

In the policy evaluation setting (Sutton & Barto, 1998) we are interested in the value function $V^{\pi}$ associated with a given policy $\pi$. The analogue here is the value distribution $Z^{\pi}$. In this section we characterize $Z^{\pi}$ and study the behaviour of the policy evaluation operator $\mathcal{T}^{\pi}$. We emphasize that $Z^{\pi}$ describes the intrinsic randomness of the agent’s interactions with its environment, rather than some measure of uncertainty about the environment itself.

We view the reward function as a random vector $R\in\mathcal{Z}$, and define the transition operator $P^{\pi}:\mathcal{Z}\to\mathcal{Z}$

where we use capital letters to emphasize the random nature of the next state-action pair $(X^{\prime},A^{\prime})$. We define the distributional Bellman operator $\mathcal{T}^{\pi}:\mathcal{Z}\to\mathcal{Z}$ as

While $\mathcal{T}^{\pi}$ bears a surface resemblance to the usual Bellman operator (2), it is fundamentally different. In particular, three sources of randomness define the compound distribution $\mathcal{T}^{\pi}Z$:

The randomness in the transition $P^{\pi}$, and

The next-state value distribution $Z(X^{\prime},A^{\prime})$.

In particular, we make the usual assumption that these three quantities are independent. In this section we will show that (5) is a contraction mapping whose unique fixed point is the random return $Z^{\pi}$.

Consider the process $Z_{k+1}:=\mathcal{T}^{\pi}Z_{k}$, starting with some $Z_{0}\in\mathcal{Z}$. We may expect the limiting expectation of $\{Z_{k}\}$ to converge exponentially quickly, as usual, to $Q^{\pi}$. As we now show, the process converges in a stronger sense: $\mathcal{T}^{\pi}$ is a contraction in $\bar{d}_{p}$, which implies that all moments also converge exponentially quickly.

$\mathcal{T}^{\pi}:\mathcal{Z}\to\mathcal{Z}$ is a $\gamma$-contraction in $\bar{d}_{p}$.

Using Lemma 3, we conclude using Banach’s fixed point theorem that $\mathcal{T}^{\pi}$ has a unique fixed point. By inspection, this fixed point must be $Z^{\pi}$ as defined in (1). As we assume all moments are bounded, this is sufficient to conclude that the sequence $\{Z_{k}\}$ converges to $Z^{\pi}$ in $\bar{d}_{p}$ for $1\leq p\leq\infty$.

To conclude, we remark that not all distributional metrics are equal; for example, Chung & Sobel (1987) have shown that $\mathcal{T}^{\pi}$ is not a contraction in total variation distance. Similar results can be derived for the Kullback-Leibler divergence and the Kolmogorov distance.

3.2 Contraction in Centered Moments

Observe that $d_{2}(U,V)$ (and more generally, $d_{p}$) relates to a coupling $C(\omega):=U(\omega)-V(\omega)$, in the sense that

4 Control

Thus far we have considered a fixed policy $\pi$, and studied the behaviour of its associated operator $\mathcal{T}^{\pi}$. We now set out to understand the distributional operators of the control setting – where we seek a policy $\pi$ that maximizes value – and the corresponding notion of an optimal value distribution. As with the optimal value function, this notion is intimately tied to that of an optimal policy. However, while all optimal policies attain the same value $Q^{*}$, in our case a difficulty arises: in general there are many optimal value distributions.

In this section we show that the distributional analogue of the Bellman optimality operator converges, in a weak sense, to the set of optimal value distributions. However, this operator is not a contraction in any metric between distributions, and is in general much more temperamental than the policy evaluation operators. We believe the convergence issues we outline here are a symptom of the inherent instability of greedy updates, as highlighted by e.g. Tsitsiklis (2002) and most recently Harutyunyan et al. (2016).

Let $\Pi^{*}$ be the set of optimal policies. We begin by characterizing what we mean by an optimal value distribution.

An optimal value distribution is the v.d. of an optimal policy. The set of optimal value distributions is $\mathcal{Z}^{*}:=\{Z^{\pi^{*}}:\pi^{*}\in\Pi^{*}\}$.

We emphasize that not all value distributions with expectation $Q^{*}$ are optimal: they must match the full distribution of the return under some optimal policy.

A greedy policy $\pi$ for $Z\in\mathcal{Z}$ maximizes the expectation of $Z$. The set of greedy policies for $Z$ is

Recall that the expected Bellman optimality operator $\mathcal{T}$ is

The maximization at $x^{\prime}$ corresponds to some greedy policy. Although this policy is implicit in (6), we cannot ignore it in the distributional setting. We will call a distributional Bellman optimality operator any operator $\mathcal{T}$ which implements a greedy selection rule, i.e.

By inspecting Lemma 4, we might expect that $Z_{k}$ converges quickly in $\bar{d}_{p}$ to some fixed point in $\mathcal{Z}^{*}$. Unfortunately, convergence is neither quick nor assured to reach a fixed point. In fact, the best we can hope for is pointwise convergence, not even to the set $\mathcal{Z}^{*}$ but to the larger set of nonstationary optimal value distributions.

A nonstationary optimal value distribution $Z^{**}$ is the value distribution corresponding to a sequence of optimal policies. The set of n.o.v.d. is $\mathcal{Z}^{**}$.

Let $\mathcal{X}$ be measurable and suppose that $\mathcal{A}$ is finite. Then

If $\mathcal{X}$ is finite, then $Z_{k}$ converges to $\mathcal{Z}^{**}$ uniformly. Furthermore, if there is a total ordering $\prec$ on $\Pi^{*}$, such that for any $Z^{*}\in\mathcal{Z}^{*}$,

Then $\mathcal{T}$ has a unique fixed point $Z^{*}\in\mathcal{Z}^{*}$.

Comparing Theorem 1 to Lemma 4 reveals a significant difference between the distributional framework and the usual setting of expected return. While the mean of $Z_{k}$ converges exponentially quickly to $Q^{*}$, its distribution need not be as well-behaved! To emphasize this difference, we now provide a number of negative results concerning $\mathcal{T}$.

The operator $\mathcal{T}$ is not a contraction.

Consider the following example (Figure 2, left). There are two states, $x_{1}$ and $x_{2}$; a unique transition from $x_{1}$ to $x_{2}$; from $x_{2}$, action $a_{1}$ yields no reward, while the optimal action $a_{2}$ yields $1+\epsilon$ or $-1+\epsilon$ with equal probability. Both actions are terminal. There is a unique optimal policy and therefore a unique fixed point $Z^{*}$. Now consider $Z$ as given in Figure 2 (right), and its distance to $Z^{*}$:

where we made use of the fact that $Z=Z^{*}$ everywhere except at $(x_{2},a_{2})$. When we apply $\mathcal{T}$ to $Z$, however, the greedy action $a_{1}$ is selected and $\mathcal{T}Z(x_{1})=Z(x_{2},a_{1})$. But

for a sufficiently small $\epsilon$. This shows that the undiscounted update is not a nonexpansion: $\bar{d}_{1}(\mathcal{T}Z,\mathcal{T}Z^{*})>\bar{d}_{1}(Z,Z^{*})$. With $\gamma<1$, the same proof shows it is not a contraction. Using a more technically involved argument, we can extend this result to any metric which separates $Z$ and $\mathcal{T}Z$.

Not all optimality operators have a fixed point $Z^{*}=\mathcal{T}Z^{*}$.

To see this, consider the same example, now with $\epsilon=0$, and a greedy operator $\mathcal{T}$ which breaks ties by picking $a_{2}$ if $Z(x_{1})=0$, and $a_{1}$ otherwise. Then the sequence $\mathcal{T}Z^{*}(x_{1}),(\mathcal{T})^{2}Z^{*}(x_{1}),\,\dots$ alternates between $Z^{*}(x_{2},a_{1})$ and $Z^{*}(x_{2},a_{2})$.

That $\mathcal{T}$ has a fixed point $Z^{*}=\mathcal{T}Z^{*}$ is insufficient to guarantee the convergence of $\{Z_{k}\}$ to $\mathcal{Z}^{*}$.

Theorem 1 paints a rather bleak picture of the control setting. It remains to be seen whether the dynamical eccentricies highlighted here actually arise in practice. One open question is whether theoretically more stable behaviour can be derived using stochastic policies, for example from conservative policy iteration (Kakade & Langford, 2002).

Approximate Distributional Learning

In this section we propose an algorithm based on the distributional Bellman optimality operator. In particular, this will require choosing an approximating distribution. Although the Gaussian case has previously been considered (Morimura et al., 2010a; Tamar et al., 2016), to the best of our knowledge we are the first to use a rich class of parametric distributions.

The discrete distribution has the advantages of being highly expressive and computationally friendly (see e.g. Van den Oord et al., 2016).

2 Projected Bellman Update

Using a discrete distribution poses a problem: the Bellman update $\mathcal{T}Z_{\theta}$ and our parametrization $Z_{\theta}$ almost always have disjoint supports. From the analysis of Section 3 it would seem natural to minimize the Wasserstein metric (viewed as a loss) between $\mathcal{T}Z_{\theta}$ and $Z_{\theta}$, which is also conveniently robust to discrepancies in support. However, a second issue prevents this: in practice we are typically restricted to learning from sample transitions, which is not possible under the Wasserstein loss (see Prop. 5 and toy results in the appendix).

Evaluation on Atari 2600 Games

To understand the approach in a complex setting, we applied the categorical algorithm to games from the Arcade Learning Environment (ALE; Bellemare et al., 2013). While the ALE is deterministic, stochasticity does occur in a number of guises: 1) from state aliasing, 2) learning from a nonstationary policy, and 3) from approximation errors. We used five training games (Fig 3) and 52 testing games.

Figure 4 illustrates the typical value distributions we observed in our experiments. In this example, three actions (those including the button press) lead to the agent releasing its laser too early and eventually losing the game. The corresponding distributions reflect this: they assign a significant probability to 0 (the terminal value). The safe actions have similar distributions (left, which tracks the invaders’ movement, is slightly favoured). This example helps explain why our approach is so successful: the distributional update keeps separated the low-value, “losing” event from the high-value, “survival” event, rather than average them into one (unrealizable) expectation.Video: http://youtu.be/yFBwyPuO2Vg.

One surprising fact is that the distributions are not concentrated on one or two values, in spite of the ALE’s determinism, but are often close to Gaussians. We believe this is due to our discretizing the diffusion process induced by $\gamma$.

We began by studying our algorithm’s performance on the training games in relation to the number of atoms (Figure 3). For this experiment, we set $\epsilon=0.05$. From the data, it is clear that using too few atoms can lead to poor behaviour, and that more always increases performance; this is not immediately obvious as we may have expected to saturate the network capacity. The difference in performance between the 51-atom version and DQN is particularly striking: the latter is outperformed in all five games, and in Seaquest we attain state-of-the-art performance. As an additional point of the comparison, the single-parameter Bernoulli algorithm performs better than DQN in 3 games out of 5, and is most notably more robust in Asterix.

One interesting outcome of this experiment was to find out that our method does pick up on stochasticity. Pong exhibits intrinsic randomness: the exact timing of the reward depends on internal registers and is truly unobservable. We see this clearly reflected in the agent’s prediction (Figure 5): over five consecutive frames, the value distribution shows two modes indicating the agent’s belief that it has yet to receive a reward. Interestingly, since the agent’s state does not include past rewards, it cannot even extinguish the prediction after receiving the reward, explaining the relative proportions of the modes.

2 State-of-the-Art Results

The performance of the 51-atom agent (from here onwards, C51) on the training games, presented in the last section, is particularly remarkable given that it involved none of the other algorithmic ideas present in state-of-the-art agents. We next asked whether incorporating the most common hyperparameter choice, namely a smaller training $\epsilon$, could lead to even better results. Specifically, we set $\epsilon=0.01$ (instead of $0.05$); furthermore, every 1 million frames, we evaluate our agent’s performance with $\epsilon=0.001$.

We compare our algorithm to DQN ($\epsilon=0.01$), Double DQN (van Hasselt et al., 2016), the Dueling architecture (Wang et al., 2016), and Prioritized Replay (Schaul et al., 2016), comparing the best evaluation score achieved during training. We see that C51 significantly outperforms these other algorithms (Figures 6 and 7). In fact, C51 surpasses the current state-of-the-art by a large margin in a number of games, most notably Seaquest. One particularly striking fact is the algorithm’s good performance on sparse reward games, for example Venture and Private Eye. This suggests that value distributions are better able to propagate rarely occurring events. Full results are provided in the appendix.

We also include in the appendix (Figure 12) a comparison, averaged over 3 seeds, showing the number of games in which C51’s training performance outperforms fully-trained DQN and human players. These results continue to show dramatic improvements, and are more representative of an agent’s average performance. Within 50 million frames, C51 has outperformed a fully trained DQN agent on 45 out of 57 games. This suggests that the full 200 million training frames, and its ensuing computational cost, are unnecessary for evaluating reinforcement learning algorithms within the ALE.

The most recent version of the ALE contains a stochastic execution mechanism designed to ward against trajectory overfitting.Specifically, on each frame the environment rejects the agent’s selected action with probability $p=0.25$. Although DQN is mostly robust to stochastic execution, there are a few games in which its performance is reduced. On a score scale normalized with respect to the random and DQN agents, C51 obtains mean and median score improvements of $126\%$ and $21.5\%$ respectively, confirming the benefits of C51 beyond the deterministic setting.

Discussion

In this work we sought a more complete picture of reinforcement learning, one that involves value distributions. We found that learning value distributions is a powerful notion that allows us to surpass most gains previously made on Atari 2600, without further algorithmic adjustments.

It is surprising that, when we use a policy which aims to maximize expected return, we should see any difference in performance. The distinction we wish to make is that learning distributions matters in the presence of approximation. We now outline some possible reasons.

Reduced chattering. Our results from Section 3.4 highlighted a significant instability in the Bellman optimality operator. When combined with function approximation, this instability may prevent the policy from converging, what Gordon (1995) called chattering. We believe the gradient-based categorical algorithm is able to mitigate these effects by effectively averaging the different distributions, similar to conservative policy iteration (Kakade & Langford, 2002). While the chattering persists, it is integrated to the approximate solution.

State aliasing. Even in a deterministic environment, state aliasing may result in effective stochasticity. McCallum (1995), for example, showed the importance of coupling representation learning with policy learning in partially observable domains. We saw an example of state aliasing in Pong, where the agent could not exactly predict the reward timing. Again, by explicitly modelling the resulting distribution we provide a more stable learning target.

A richer set of predictions. A recurring theme in artificial intelligence is the idea of an agent learning from a multitude of predictions (Caruana 1997; Utgoff & Stracuzzi 2002; Sutton et al. 2011; Jaderberg et al. 2017). The distributional approach naturally provides us with a rich set of auxiliary predictions, namely: the probability that the return will take on a particular value. Unlike previously proposed approaches, however, the accuracy of these predictions is tightly coupled with the agent’s performance.

Framework for inductive bias. The distributional perspective on reinforcement learning allows a more natural framework within which we can impose assumptions about the domain or the learning problem itself. In this work we used distributions with support bounded in $[V_{\textsc{min}},V_{\textsc{max}}]$. Treating this support as a hyperparameter allows us to change the optimization problem by treating all extremal returns (e.g. greater than $V_{\textsc{max}}$) as equivalent. Surprisingly, a similar value clipping in DQN significantly degrades performance in most games. To take another example: interpreting the discount factor $\gamma$ as a proper probability, as some authors have argued, leads to a different algorithm.

Well-behaved optimization. It is well-accepted that the KL divergence between categorical distributions is a reasonably easy loss to minimize. This may explain some of our empirical performance. Yet early experiments with alternative losses, such as KL divergence between continuous densities, were not fruitful, in part because the KL divergence is insensitive to the values of its outcomes. A closer minimization of the Wasserstein metric should yield even better results than what we presented here.

In closing, we believe our results highlight the need to account for distribution in the design, theoretical or otherwise, of algorithms.

Acknowledgements

The authors acknowledge the important role played by their colleagues at DeepMind throughout the development of this work. Special thanks to Yee Whye Teh, Alex Graves, Joel Veness, Guillaume Desjardins, Tom Schaul, David Silver, Andre Barreto, Max Jaderberg, Mohammad Azar, Georg Ostrovski, Bernardo Avila Pires, Olivier Pietquin, Audrunas Gruslys, Tom Stepleton, Aaron van den Oord; and particularly Chris Maddison for his comprehensive review of an earlier draft. Thanks also to Marek Petrik for pointers to the relevant literature, and Mark Rowland for fine-tuning details in the final version.

Erratum

The camera-ready copy of this paper incorrectly reported a mean score of 1010% for C51. The corrected figure stands at 701%, which remains higher than the other comparable baselines. The median score remains unchanged at 178%.

The error was due to evaluation episodes in one game (Atlantis) lasting over 30 minutes; in comparison, the other results presented here cap episodes at 30 minutes, as is standard. The previously reported score on Atlantis was 3.7 million; our 30-minute score is 841,075, which we believe is close to the achievable maximum in this time frame. Capping at 30 minutes brings our human-normalized score on Atlantis from 22824% to a mere (!) 5199%, unfortunately enough to noticeably affect the mean score, whose sensitivity to outliers is well-documented.

References

Appendix A Related Work

To the best of our knowledge, the work closest to ours are two papers (Morimura et al., 2010b, a) studying the distributional Bellman equation from the perspective of its cumulative distribution functions. The authors propose both parametric and nonparametric solutions to learn distributions for risk-sensitive reinforcement learning. They also provide some theoretical analysis for the policy evaluation setting, including a consistency result in the nonparametric case. By contrast, we also analyze the control setting, and emphasize the use of the distributional equations to improve approximate reinforcement learning.

The variance of the return has been extensively studied in the risk-sensitive setting. Of note, Tamar et al. (2016) analyze the use of linear function approximation to learn this variance for policy evaluation, and Prashanth & Ghavamzadeh (2013) estimate the return variance in the design of a risk-sensitive actor-critic algorithm. Mannor & Tsitsiklis (2011) provides negative results regarding the computation of a variance-constrained solution to the optimal control problem.

The distributional formulation also arises when modelling uncertainty. Dearden et al. (1998) considered a Gaussian approximation to the value distribution, and modelled the uncertainty over the parameters of this approximation using a Normal-Gamma prior. Engel et al. (2005) leveraged the distributional Bellman equation to define a Gaussian process over the unknown value function. More recently, Geist & Pietquin (2010) proposed an alternative solution to the same problem based on unscented Kalman filters. We believe much of the analysis we provide here, which deals with the intrinsic randomness of the environment, can also be applied to modelling uncertainty.

Our work here is based on a number of foundational results, in particular concerning alternative optimality criteria. Early on, Jaquette (1973) showed that a moment optimality criterion, which imposes a total ordering on distributions, is achievable and defines a stationary optimal policy, echoing the second part of Theorem 1. Sobel (1982) is usually cited as the first reference to Bellman equations for the higher moments (but not the distribution) of the return. Chung & Sobel (1987) provides results concerning the convergence of the distributional Bellman operator in total variation distance. White (1988) studies “nonstandard MDP criteria” from the perspective of optimizing the state-action pair occupancy.

A number of probabilistic frameworks for reinforcement learning have been proposed in recent years. The planning as inference approach (Toussaint & Storkey, 2006; Hoffman et al., 2009) embeds the return into a graphical model, and applies probabilistic inference to determine the sequence of actions leading to maximal expected reward. Wang et al. (2008) considered the dual formulation of reinforcement learning, where one optimizes the stationary distribution subject to constraints given by the transition function (Puterman, 1994), in particular its relationship to linear approximation. Related to this dual is the Compress and Control algorithm Veness et al. (2015), which describes a value function by learning a return distribution using density models. One of the aims of this work was to address the question left open by their work of whether one could be design a practical distributional algorithm based on the Bellman equation, rather than Monte Carlo estimation.

Appendix B Proofs

Let $A_{1},A_{2},\dots$ be a set of random variables describing a partition of $\Omega$, i.e. $A_{i}(\omega)\in\{0,1\}$ and for any $\omega$ there is exactly one $A_{i}$ with $A_{i}(\omega)=1$. Let $U,V$ be two random variables. Then

We will give the proof for $p<\infty$, noting that the same applies to $p=\infty$. Let $Y_{i}\overset{D}{:=}A_{i}U$ and $Z_{i}\overset{D}{:=}A_{i}V$, respectively. First note that

Now, $|A_{i}U-A_{i}V|^{p}=0$ whenever $A_{i}=0$. It follows that we can choose $Y_{i},Z_{i}$ so that also $|Y_{i}-Z_{i}|^{p}=0$ whenever $A_{i}=0$, without increasing the expected norm. Hence

Specifically, the left-hand side of the equation is an infimum over all r.v.’s whose cumulative distributions are $F_{U}$ and $F_{V}$, respectively, while the right-hand side is an infimum over sequences of r.v’s $Y_{1},Y_{2},\dots$ and $Z_{1},Z_{2},\dots$ whose cumulative distributions are $F_{A_{i}U},F_{A_{i}V}$, respectively. To prove this upper bound, consider the c.d.f. of $U$:

Hence the distribution $F_{U}$ is equivalent, in an almost sure sense, to one that first picks an element $A_{i}$ of the partition, then picks a value for $U$ conditional on the choice $A_{i}$. On the other hand, the c.d.f. of $Y_{i}\overset{D}{=}A_{i}U$ is

where (a) follows because $A_{1},A_{2},\dots$ is a partition. Using (9), this implies

because in (b) the individual components of the sum are independently minimized; and (c) from (8). ∎

$\bar{d}_{p}$ is a metric over value distributions.

The only nontrivial property is the triangle inequality. For any value distribution $Y\in\mathcal{Z}$, write

where in (a) we used the triangle inequality for $d_{p}$. ∎

$\mathcal{T}^{\pi}:\mathcal{Z}\to\mathcal{Z}$ is a $\gamma$-contraction in $\bar{d}_{p}$.

Consider $Z_{1},Z_{2}\in\mathcal{Z}$. By definition,

where the last line follows from the definition of $P^{\pi}$ (see (4)). Combining with (10) we obtain

The proof follows by linearity of expectation. Write $\mathcal{T}_{D}$ for the distributional operator and $\mathcal{T}_{E}$ for the usual operator. Then

Let $Z_{k}:=\mathcal{T}Z_{k-1}$ with $Z_{0}\in\mathcal{Z}$. Let $\mathcal{X}$ be measurable and suppose that $\mathcal{A}$ is finite. Then

If $\mathcal{X}$ is finite, then $Z_{k}$ converges to $\mathcal{Z}^{**}$ uniformly. Furthermore, if there is a total ordering $\prec$ on $\Pi^{*}$, such that for any $Z^{*}\in\mathcal{Z}^{*}$,

then $\mathcal{T}$ has a unique fixed point $Z^{*}\in\mathcal{Z}^{*}$.

Indeed, by Lemma 4, we know that after $k$ iterations

For $x\in\mathcal{X}$, write $a^{*}:=\pi^{*}(x)$. For any $a\in\mathcal{A}$, we deduce that

It follows that if $x\in\mathcal{X}_{k}$, then also $Q_{k}(x,a^{*})>Q_{k}(x,a^{\prime})$ for all $a^{\prime}\neq\pi^{*}(x)$: for these states, the greedy policy $\pi_{k}(x):=\operatorname*{arg\,max}_{a}Q_{k}(x,a)$ corresponds to the optimal policy $\pi^{*}$.

For each $x\in\mathcal{X}$ there exists a $k$ such that, for all $k^{\prime}\geq k$, $x\in\mathcal{X}_{k^{\prime}}$, and in particular $\operatorname*{arg\,max}_{a}Q_{k}(x,a)=\pi^{*}(x)$.

is attained for some strictly positive $\Delta(x)>0$. By definition, there exists a $k$ such that

and hence every $x\in\mathcal{X}$ must eventually be in $\mathcal{X}_{k}$. ∎

This lemma allows us to guarantee the existence of an iteration $k$ after which sufficiently many states are well-behaved, in the sense that the greedy policy at those states chooses the optimal action. We will call these states “solved”. We in fact require not only these states to be solved, but also most of their successors, and most of the successors of those, and so on. We formalize this notion as follows: fix some $\delta>0$, let $\mathcal{X}_{k,0}:=\mathcal{X}_{k}$, and define for $i>0$ the set

As the following lemma shows, any $x$ is eventually contained in the recursively-defined sets $\mathcal{X}_{k,i}$, for any $i$.

Fix $i$ and let us suppose that $\mathcal{X}_{k,i}\uparrow\mathcal{X}$. By Lemma 5, this is true for $i=0$. We infer that for any probability measure $P$ on $\mathcal{X}$, $P(\mathcal{X}_{k,i})\to P(\mathcal{X})=1$. In particular, for a given $x\in\mathcal{X}_{k}$, this implies that

Therefore, for any $x$, there exists a time after which it is and remains a member of $\mathcal{X}_{k,i+1}$, the set of states for which $P(\mathcal{X}_{k-1,i}\,|\,x,\pi^{*}(x))\geq 1-\delta$. We conclude that $\mathcal{X}_{k,i+1}\uparrow\mathcal{X}$ also. The statement follows by induction. ∎

Fix $i>0$ and $x\in\mathcal{X}_{k+1,i+1}\subseteq\mathcal{X}_{k}$. We begin by using Lemma 1 to separate the transition from $x$ into a solved term and an unsolved term:

where $X^{\prime}$ is the random successor from taking action $\pi_{k}(x):=\pi^{*}(x)$, and we write $S^{k}_{i}=S^{k}_{i}(X^{\prime}),\bar{S}^{k}_{i}=\bar{S}^{k}_{i}(X^{\prime})$ to ease the notation. Similarly,

Recall that $B<\infty$ is the largest attainable $\left\|Z\right\|_{\infty}$. Since also $\delta_{i}<\delta$ by our choice of $x\in\mathcal{X}_{k+1,i+1}$, we can upper bound the second term in (12) by $\gamma\delta B$. This yields

By induction on $i>0$, we conclude that for $x\in\mathcal{X}_{k+i,i}$ and some random state $X^{\prime\prime}$ $i$ steps forward,

Hence for any $x\in\mathcal{X}$, $\epsilon>0$, we can take $\delta$, $i$, and finally $k$ large enough to make $d_{p}(W_{k}(x),W^{*}(x))<\epsilon$. The proof then extends to $Z_{k}(x,a)$ by considering one additional application of $\mathcal{T}$.

We now consider the more general case where there are multiple optimal policies. We expand the definition of $\mathcal{X}_{k,i}$ as follows:

Because there are finitely many actions, Lemma 6 also holds for this new definition. As before, take $x\in\mathcal{X}_{k,i}$, but now consider the sequence of greedy policies $\pi_{k},\pi_{k-1},\dots$ selected by successive applications of $\mathcal{T}$, and write

Now denote by $\mathcal{Z}^{**}$ the set of nonstationary optimal policies. If we take any $Z^{*}\in\mathcal{Z}^{*}$, we deduce that

since $Z^{*}$ corresponds to some optimal policy $\pi^{*}$ and $\bar{\pi}_{k}$ is optimal along most of the trajectories from $(x,a)$. In effect, $\mathcal{T}^{\bar{\pi}_{k}}Z^{*}$ is close to the value distribution of the nonstationary optimal policy $\bar{\pi}_{k}\pi^{*}$. Now for this $Z^{*}$,

using the same argument as before with the newly-defined $\mathcal{X}_{k,i}$. It follows that

When $\mathcal{X}$ is finite, there exists a fixed $k$ after which $\mathcal{X}_{k}=\mathcal{X}$. The uniform convergence result then follows.

To prove the uniqueness of the fixed point $Z^{*}$ when $\mathcal{T}$ selects its actions according to the ordering $\prec$, we note that for any optimal value distribution $Z^{*}$, its set of greedy policies is $\Pi^{*}$. Denote by $\pi^{*}$ the policy coming first in the ordering over $\Pi^{*}$. Then $\mathcal{T}=\mathcal{T}^{\pi^{*}}$, which has a unique fixed point (Section 3.3). ∎

That $\mathcal{T}$ has a fixed point $Z^{*}=\mathcal{T}Z^{*}$ is insufficient to guarantee the convergence of $\{Z_{k}\}$ to $\mathcal{Z}^{*}$.

We provide here a sketch of the result. Consider a single state $x_{1}$ with two actions, $a_{1}$ and $a_{2}$ (Figure 8). The first action yields a reward of $1/2$, while the other either yields or $1$ with equal probability, and both actions are optimal. Now take $\gamma=1/2$ and write $R_{0},R_{1},\dots$ for the received rewards. Consider a stochastic policy that takes action $a_{2}$ with probability $p$. For $p=0$, the return is

For $p=1$, on the other hand, the return is random and is given by the following fractional number (in binary):

As a result, $Z_{p=1}$ is uniformly distributed between and $2$! In fact, note that

For some intermediary value of $p$, we obtain a different probability of the different digits, but always putting some probability mass on all returns in $$.

Now suppose we follow the nonstationary policy that takes $a_{1}$ on the first step, then $a_{2}$ from there on. By inspection, the return will be uniformly distributed on the interval $[1/2,3/2]$, which does not correspond to the return under any value of $p$. But now we may imagine an operator $\mathcal{T}$ which alternates between $a_{1}$ and $a_{2}$ depending on the exact value distribution it is applied to, which would in turn converge to a nonstationary optimal value distribution.

and in general the inequality is strict and

where in the penultimate line we used the independence of $I$ from $P_{i}$ and $Q$ to appeal to property P3 of the Wasserstein metric.

To show that the bound is in general strict, consider the mixture distribution depicted in Figure 9. We will simply consider the $d_{1}$ metric between this distribution $P$ and another distribution $Q$. The first distribution is

In this example, $i\in\{1,2\}$, $P_{1}=0$, and $P_{2}=1$. Now consider the distribution with the same support but that puts probability $p$ on :

This is $d_{1}(P,Q)=\frac{1}{2}$ for $p\in\{0,1\}$, and strictly less than $\frac{1}{2}$ for any other values of $p$. On the other hand, the corresponding expected distance (after sampling an outcome $x_{1}$ or $x_{2}$ with equal probability) is

Fix some next-state distribution $Z$ and policy $\pi$. Consider a parametric value distribution $Z_{\theta}$, and and define the Wasserstein loss

Let $r\sim R(x,a)$ and $x^{\prime}\sim P(\cdot\,|\,x,a)$ and consider the sample loss

Its expectation is an upper bound on the loss $\mathcal{L}_{W}$:

The result follows directly from the previous lemma.

Appendix C Algorithmic Details

While our training regime closely follows that of DQN (Mnih et al., 2015), we use Adam (Kingma & Ba, 2015) instead of RMSProp (Tieleman & Hinton, 2012) for gradient rescaling. We also performed some hyperparameter tuning for our final results. Specifically, we evaluated two hyperparameters over our five training games and choose the values that performed best. The hyperparameter values we considered were $V_{\textsc{max}}\in\{3,10,100\}$ and $\epsilon_{adam}\in\{1/L,0.1/L,0.01/L,0.001/L,0.0001/L\}$, where $L=32$ is the minibatch size. We found $V_{\textsc{max}}=10$ and $\epsilon_{adam}=0.01/L$ performed best. We used the same step-size value as DQN ($\alpha=0.00025$).

Pseudo-code for the categorical algorithm is given in Algorithm 1. We apply the Bellman update to each atom separately, and then project it into the two nearest atoms in the original support. Transitions to a terminal state are handled with $\gamma_{t}=0$.

Appendix D Comparison of Sampled Wasserstein Loss and Categorical Projection

Lemma 3 proves that for a fixed policy $\pi$ the distributional Bellman operator is a $\gamma$-contraction in $\bar{d}_{p}$, and therefore that $\mathcal{T}^{\pi}$ will converge in distribution to the true distribution of returns $Z^{\pi}$. In this section, we empirically validate these results on the CliffWalk domain shown in Figure 11. The dynamics of the problem match those given by Sutton & Barto (1998). We also study the convergence of the distributional Bellman operator under the sampled Wasserstein loss and the categorical projection (Equation 7) while following a policy that tries to take the safe path but has a 10% chance of taking another action uniformly at random.

We compute a ground-truth distribution of returns $Z^{\pi}$ using $10000$ Monte-Carlo (MC) rollouts from each state. We then perform two experiments, approximating the value distribution at each state with our discrete distributions.

In the first experiment, we perform supervised learning using either the Wasserstein loss or categorical projection (Equation 7) with cross-entropy loss. We use $Z^{\pi}$ as the supervised target and perform $5000$ sweeps over all states to ensure both approaches have converged. In the second experiment, we use the same loss functions, but the training target comes from the one-step distributional Bellman operator with sampled transitions. We use $V_{\textsc{min}}=-100$ and $V_{\textsc{max}}=-1$.Because there is a small probability of larger negative returns, some approximation error is unavoidable. However, this effect is relatively negligible in our experiments. For the sample updates we perform 10 times as many sweeps over the state space. Fundamentally, these experiments investigate how well the two training regimes (minimizing the Wasserstein or categorical loss) minimize the Wasserstein metric under both ideal (supervised target) and practical (sampled one-step Bellman target) conditions.

In Figure 10a we show the final Wasserstein distance $d_{1}(Z^{\pi},Z_{\theta})$ between the learned distributions and the ground-truth distribution as we vary the number of atoms. The graph shows that the categorical algorithm does indeed minimize the Wasserstein metric in both the supervised and sample Bellman setting. It also highlights that minimizing the Wasserstein loss with stochastic gradient descent is in general flawed, confirming the intuition given by Proposition 5. In repeat experiments the process converged to different values of $d_{1}(Z^{\pi},Z_{\theta})$, suggesting the presence of local minima (more prevalent with fewer atoms).

Figure 10 provides additional insight into why the sampled Wasserstein distance may perform poorly. Here, we see the cumulative densities for the approximations learned under these two losses for five different states along the safe path in CliffWalk. The Wasserstein has converged to a fixed-point distribution, but not one that captures the true (Monte Carlo) distribution very well. By comparison, the categorical algorithm captures the variance of the true distribution much more accurately.

Appendix E Supplemental Videos and Results

In Figure 13 we provide links to supplemental videos showing the C51 agent during training on various Atari 2600 games. Figure 12 shows the relative performance of C51 over the course of training. Figure 14 provides a table of evaluation results, comparing C51 to other state-of-the-art agents. Figures 15–18 depict particularly interesting frames.