Diagnosing Bottlenecks in Deep Q-learning Algorithms

Introduction

Q-learning algorithms, which are based on approximating state-action value functions, are an efficient and commonly used class of RL methods. In recent years, such methods have been applied to great effect in domains such as playing video games from raw pixels (Mnih et al., 2015) and continuous control in robotics (Kalashnikov et al., 2018). Methods based on approximate dynamic programming and Q-function estimation have several very appealing properties: they are generally moderately sample-efficient, when compared to policy gradient methods, they are simple to use, and they allow for off-policy learning. This makes them an appealing choice for a wide range of tasks, from robotic control (Kalashnikov et al., 2018) to off-policy learning from historical data for recommender (Shani et al., 2005) systems and other applications. However, although the basic tabular Q-learning algorithm is convergent and admits theoretical analysis (Sutton & Barto, 2018), its non-linear counterpart with function approximation (such as with deep neural networks) is poorly understood theoretically. In this paper, we aim to investigate the degree to which the theoretical issues with Q-learning actually manifest in practice. Thus, we empirically analyze aspects of the Q-learning method in a unit testing framework, where we can employ oracle solvers to obtain ground truth Q-functions and distributions for exact analysis. We investigate the following questions:

2) What is the effect of sampling error and overfitting? Q-learning is used to solve problems where we do not have access to the transition function of the MDP. Thus, Q-learning methods need to learn by collecting samples in the environment, and training on these samples incurs sampling error, potentially leading to overfitting. This causes errors in the computation of the Bellman backup, which degrades the quality of the solution. We experimentally show that overfitting exists in practice by performing ablation studies on the number of gradient steps, and by demonstrating that oracle based early stopping techniques can be used to improve performance of Q-learning algorithms. (Section 5). Thus, in our experiments we quantify the amount of overfitting which happens in practice, incorporating a variety of metrics, an performing a number of ablations and investigate methods to mitigate its effects.

3) What is the effect of distribution shift and a moving target? The standard formulation of Q-learning prescribes an update rule, with no corresponding objective function (Sutton et al., 2009a). This results in a process which optimizes an objective that is non-stationary in two ways: the target values are updated during training, and the distribution under which the Bellman error is optimized changes, as samples are drawn from different policies. We refer to these problems as the moving target and distribution shift problems, respectively. These properties can make convergence behavior difficult to understand, and prior works have hypothesized that nonstationarity is a source of instability (Mnih et al., 2015; Lillicrap et al., 2015). In our experiments, we develop metrics to quantify the amount of distribution shift and performance change due to non-stationary targets. Surprisingly, we find that in a controlled experiment, distributional shift and non-stationary targets do not in fact correlate with reduction in performance. In fact, sampling strategies with large distributional shift often perform very well.

4) What is the best sampling or weighting distribution? Deeply tied to the distribution shift problem is the choice of which distribution to sample from. Do moving distributions cause instability, as Q-values trained on one distribution are evaluated under another in subsequent iterations? Researchers have often noted that on-policy samples are typically superior to off-policy samples (Sutton & Barto, 2018), and there are several theoretical results that highlight favorable convergence properties under on-policy samples. However, there is little theoretical guidance on how to pick distributions so as to maximize learning rate. To this end, we investigate several choices for the sampling distribution. Surprisingly, we find that on-policy training distributions are not always preferable, and that a clear pattern in performance with respect to training distribution is that broader, higher-entropy distributions perform better, regardless of distributional shift. Motivated by our findings, we propose a novel weighting distribution, adversarial feature matching (AFM), which is explicitly compensates for function approximator error, while still producing high-entropy sampling distributions.

Our contributions are as follows: We introduce a unit testing framework for Q-learning to disentangle issues related to function approximation, sampling, and distributional shift where approximate components are replaced by oracles. This allows for controlled analysis of different sources of error. We perform a detailed experimental analysis of many hypothesized sources of instability, error, and slow training in Q-learning algorithms on tabular domains, and show that many of these trends hold true in high dimensional domains. We propose novel choices of sampling distributions which lead to improved performance even on high-dimensional tasks. Our overall aim is to offer practical guidance for designing RL algorithms, as well as to identify important issues to solve in future research.

Preliminaries

Q-learning algorithms aim to solve a Markov decision process (MDP) by learning the optimal state-action value function, or Q-function. We define an MDP as a tuple $(\mathcal{S},\mathcal{A},T,R,\gamma)$. $\mathcal{S},\mathcal{A}$ represent the state and action spaces, respectively. $T(s^{\prime}|s,a)$ and $R(s,a)$ represent the dynamics (transition distribution) and reward function, and $\gamma\in(0,1)$ represents the discount factor. The goal in RL is to find a policy $\pi(a|s)$ that maximizes the expected cumulative discounted rewards, known as the returns:

The quantity of interest in Q-learning methods are state-action value functions, which give the expected future return starting from a particular state-action tuple, denoted $Q^{\pi}(s,a)$. The state value function can also be denoted as $V^{\pi}(s,a)$. Q-learning algorithms are based on iterating the Bellman backup operator $\mathcal{T}$, defined as

The (tabular) Q-iteration algorithm is a dynamic programming algorithm that iterates the Bellman backup $Q^{t+1}\leftarrow\mathcal{T}Q^{t}$. Because the Bellman backup is a $\gamma$-contraction in the L-$\infty$ norm, and $Q^{*}$ (the Q-values of $\pi^{*}$) is its fixed point, Q-iteration can be shown to converge to $Q^{*}$ (Sutton & Barto, 2018). A deterministic optimal policy can then be obtained as $\pi^{*}(s)=\underset{a}{\textrm{argmax}}\ Q^{*}(s,a)$.

When state spaces cannot be enumerated in a tabular format, function approximators can be used to represent the Q-values. An important class of such Q-learning methods are fitted Q-iteration (FQI) (Ernst et al., 2005), or approximate dynamic programming (ADP) methods, which form the basis of modern deep RL methods such as DQN (Mnih et al., 2015). FQI projects the values of the Bellman backup onto a family of Q-function approximators $\mathcal{Q}$:

Here, $\Pi_{\mu}$ denotes a $\mu$-weighted L2 projection, which minimizes the Bellman error via supervised learning:

The values produced by the Bellman backup, $(\mathcal{T}Q^{t})(s,a)$ are commonly referred to as target values, and when neural networks are used for function approximation, the previous Q-function $Q^{t}(s,a)$ is referred to as the target network. In this work, we distinguish between the cases when the Bellman error is estimated with Monte-Carlo sampling or computed exactly (see Section 3.1). The sampled variant corresponds to FQI as described in the literature (Ernst et al., 2005; Riedmiller, 2005), while the exact variant is analogous to conventional ADP (Bertsekas & Tsitsiklis, 1996).

A related branch of Q-learning methods are online Q-learning methods, in which Q-values are updated while samples are being collected in the MDP. This includes classic algorithms such as Watkin’s Q-learning (Watkins & Dayan, 1992). Online Q-learning methods can be viewed as a form of stochastic approximation (such as Robbins-Monro) applied to Q-iteration and FQI (Bertsekas & Tsitsiklis, 1996), and share many of its theoretical properties (Szepesvári, 1998). Modern deep RL algorithms such as DQN (Mnih et al., 2015) have characteristics of both online Q-learning and FQI – using replay buffers means the sampling distribution $\mu$ changes very little between target updates (see Section 6.3), and target networks are justified from the viewpoint of FQI. Because FQI corresponds to the case when the sampling distribution is static between target updates, the behavior of modern deep RL methods more closely resembles FQI than a true online method without target networks.

Experimental Setup

Our experimental setup is centered around unit-testing. We first introduce a spectrum of Q-learning algorithms, starting with exact approximate dynamic programming and gradually replacing oracle components, such as knowledge of dynamics, until the algorithm resembles modern deep Q-learning methods. We then introduce a suite of tabular environments where oracle solutions can be computed and compared against, to aid in diagnosis, as well as testing in high-dimensional environments to verify our hypotheses.

In order to provide consistent metrics across domains, we normalize returns and errors involving Q-functions (such as Bellman error) by the returns of the expert policy $\pi^{*}$ on each environment.

In the analysis presented in Section 4, 5, 6 and 7, we will use three different Q-learning variants, each of which remove some of the approximations in the standard Q-learning method used in the literature – Exact-FQI, Sampling-FQI, and Replay-FQI. Although FQI is not exactly identical to commonly used deep RL methods, such as DQN (Mnih et al., 2015), DDPG (Lillicrap et al., 2015), and SAC (Haarnoja et al., 2017), it is structurally similar and, when the replay buffer for the commonly used methods becomes large, the difference becomes negligible, since the sampling distribution changes very little between target network updates. However, FQI methods are much more amenable for controlled analysis, since we can separately isolate target values, update rates, and the number of samples used for each iteration. We therefore use variants of FQI as the basis for our analysis, but we also confirm that similar trends hold with more commonly used algorithms on standard benchmark problems.

Exact-FQI (Algorithm 1): Exact-FQI computes the backup and projection on all state-action tuples without any sampling error. It also assumes knowledge of dynamics and reward function to compute Bellman backups exactly. We use Exact-FQI to study convergence, distribution shift (by varying weighting distributions on transitions), and function approximation in the absence of sampling error. Exact-FQI eliminates errors due to sampling states, and computing inexact, sampled backups.

Sampled-FQI (Algorithm 2): Sampled-FQI is a special case of Exact-FQI, where the Bellman error is approximated with Monte-Carlo estimates from a sampling distribution $\mu$, and the Bellman backup is approximated with samples from the dynamics as $r(s,a)+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})$. We use Sampled-FQI to study effects of overfitting. Sampled-FQI incorporates all sources of error – arising from function approximation, sampling and also distribution shift.

Replay-FQI (Algorithm 3): Replay-FQI is a special case of Sampled-FQI that uses a replay buffer (Lin, 1992), that saves past transition samples $(s,a,s^{\prime},r)$, which are used for computing Bellman error. Replay-FQI strongle resembles DQN (Mnih et al., 2015), lacking the online updates that allow $\mu$ to change within an FQI iteration. With large replay buffers, we expect the difference between Replay-FQI and DQN to be minimal as $\mu$ changes slowly.

We additionally investigate the following choices of weighting distributions ($\mu$) for the Bellman error. When sampling the Bellman error, these can be implemented by sampling directly from the distribution, or via importance sampling.

Unif$(s,a)$: Uniform weights over state-action space. This is the weighting distribution typically used by dynamic programming algorithms, such as FQI.

$\pi(s,a)$: The on-policy state-action marginal induced by $\pi$.

$\pi^{*}(s,a)$: The state-action marginal induced by $\pi^{*}$.

Random$(s,a)$: State-action marginal induced by executing uniformly random actions.

Prioritized(s,a): Weights Bellman errors proportional to $|Q(s,a)-\mathcal{T}Q(s,a)|$. This is similar to prioritized replay (Schaul et al., 2015) without importance sampling.

Replay$(s,a)$ and Replay10$(s,a)$: Averaged state-action marginal of all policies (or the previous 10) produced during training. This simulates sampling uniformly from a replay buffer where infinite samples are collected from each policy.

2 Domains

We evaluate our methods on suite of tabular environments where we can compute oracle values. This will help us compare, analyze and fix various sources of error by means of comparing the learned Q-functions to the true, oracle-compute Q-functions. We selected 8 tabular domains, each with different qualitative attributes, including: gridworlds of varying sizes and observations, blind Cliffwalk (Schaul et al., 2015), discretized Pendulum and Mountain Car based on implementations in OpenAI Gym (Plappert et al., 2018), and a random sparsely connected graph. We give full details of these environments in Appendix A, as well as their motivation for inclusion.

3 Function Approximators

Throughout our experiments, we use 2-layer ReLU networks, denoted by a tuple $(N,N)$ where N represents the number of units in a layer. The “Tabular” architecture refers to the case when no function approximation is used.

4 High-Dimensional Testing

In addition to diagnostic experiments on tabular domains, we also wish to see if the observed trends hold true on high-dimensional environments. To this end, we include experiments on continuous control tasks in the OpenAI Gym benchmark (Plappert et al., 2018) (HalfCheetah-v2, Hopper-v2, Ant-v2, Walker2d-v2). In continuous domains, computing the maximum over actions of the Q-value is difficult ($\max_{a}Q(s,a)$). A common choice in this case is to use a second “actor” neural network to approximate $\arg\max_{a}Q(s,a)$ (Lillicrap et al., 2015; Fujimoto et al., 2018; Haarnoja et al., 2018). This approach most closely resembles Replay-FQI, but using the actor network in place of the max.

Function Approximation and Convergence

The first issue we investigate is the connection between function approximation and convergence properties.

As discussed in Section 2, when function approximation is introduced to Q-learning, convergence guarantees are lost. This interaction between approximation and convergence has been a long-studied topic in reinforcement learning. In the control literature, it is closely related to the problems of state-aliasing or interference (Farrell & Berger, 1995). Baird (1995) introduces a simple counterexample in which Watkin’s Q-learning with linear approximators can cause unbounded divergence. In the policy evaluation scenario, Tsitsiklis & Van Roy (1997) prove that on-policy TD-learning with linear function approximators converge, and methods such as GTD (Sutton et al., 2009a) and ETD (Sutton et al., 2016) have extended results to off-policy cases. In the control scenario, convergent algorithms such as SBEED (Dai et al., 2018) and Greedy-GQ (Maei et al., 2010) have been developed. However, several works have noted that divergence need not occur. Munos (2005) theoretically addresses the norm-mismatch problem, which show that unbounded divergence is impossible provided $\mu$ has adequate support and projections are non-expansive in p-norms. Concurrently to us, Van Hasselt et al. (2018) experimentally find that unbounded divergence rarely occurs with DQN variants on Atari games.

2 How does function approximation affect convergence properties and suboptimality of solutions?

We first note the obvious trend that smaller architectures produce lower returns, and converge to more suboptimal solutions. However, we also find that smaller architectures introduce significant bias in the learning process, and there is often a significant gap between the solution found by Exact-FQI and the best solution within the model class. This gap may be due to the fact that when the target is bootstrapped, we must be able to represent all Q-function along the path to the solution, and not just the final result (Bertsekas & Tsitsiklis, 1996). This observation implies that using large architectures is crucial not only because they have capacity to represent a better solution, but also because they are significantly easier to train using bootstrapping, and suffer less from nonconvergence issues. We also note that divergence rarely happens in practice. We observed divergence in 0.9% of our experiments using function approximation, measured by the largest Q-value growing larger than 10 times that of $Q^{*}$.

For high-dimensional problems, we present experiments on varying the architecture of the Q-network in SAC (Haarnoja et al., 2018) in Appendix Fig. 13. We still observe that large networks have the best performance, and that divergence rarely happens even in high-dimensional continuous spaces. We briefly discuss theoretical intuitions on apparent discrepancy between the lack of unbounded divergence in relation known counterexamples in Appendix B.

Sampling Error and Overfitting

A second source of error in minimizing the Bellman error, orthogonal to function approximation, is that of sampling or generalization error. The next issue we investigate is the effect of sampling error on Q-learning methods.

Approximate dynamic programming assumes that the projection of the Bellman backup (Eqn. 1) is computed exactly, but in reinforcement learning we can normally only compute the empirical Bellman error over a finite set of samples. In the PAC framework, overfitting can be quantified by a bounded error in between the empirical and expected loss with high probability, which decays with sample size (Shalev-Shwartz & Ben-David, 2014). Munos & Szepesvári (2008); Maillard et al. (2010); Tosatto et al. (2017) provide such PAC-bounds which account for sampling error in the context of Q-learning and value-based methods, and quantify the quality of the final solution in terms of sample complexity.

We analyze several key points that relate to sampling error. First, we show that Q-learning is prone to overfitting, and that this overfitting has a real impact on performance, in both tabular and high-dimensional settings. We also show that the replay buffer is in fact a very effective technique in addressing this issue, and discuss several methods to migitate the effects of overfitting in practice.

2 Quantifying Overfitting

We first quantify the amount of overfitting that happens during training, by varying the number of samples. In order provide comparable validation errors across different experiments, we fix a reference sequence of Q-functions, $Q^{1},...,Q^{N}$, obtained during a normal training run. We then retrace the training sequence, and minimize the projection error $\Pi_{\mu}(Q^{t})$ for each training iteration, using varying amounts of on-policy data or sampling from a replay buffer. We measure the exact validation error (the expected Bellman error) at each iteration under the on-policy distribution, plotted in Fig. 3. We note the obvious trend that more samples leads to lower validation loss, confirming that overfitting can in fact occur. A more interesting observation is that sampling from the replay buffer results in the lowest on-policy validation loss, despite bias due to distribution mismatch from sampling off-policy data. As we discuss in Section 6, we believe that replay buffers are mainly effective because they greatly reduce the effect of overfitting and create relatively good coverage over the state space, not necessarily due to reducing the effects of distribution shift.

Next, Fig. 2 shows the relationship between number of samples and returns. We see a clear trend that higher sample count leads to improved learning speed and a better final solution, confirming our hypothesis that overfitting has a significant effect on the performance of Q-learning. A full sweep including architectures is presented in Appendix Fig. 14. We observe that despite overfitting being an issue, larger architectures still perform better because the bias introduced by smaller architectures dominates.

3 What methods can be used to compensate for overfitting?

Finally, we discuss methods to compensate for overfitting. One common method for reducing overfitting is to regularize the function approximator to reduce its capacity. However, as we have seen before that weaker architectures can give rise to suboptimal convergence, we instead study early stopping methods to mitigate overfitting without reducing model size. First, we observe that the number of gradient steps taken per sample in the projection step has an important effect on performance – too few steps and the algorithm learns slowly, but too many steps and the algorithm may initially learn quickly but overfit. To show this, we run a hyperparameter sweep over the number of gradient steps taken per environment step in Replay-FQI and TD3 (TD3 uses 1 by default). Results for FQI are shown in Fig. 4, and for TD3 in Appendix Fig. 15.

In order to understand whether better early stopping criteria can possibly help with overfitting, we employ oracle early stopping rules. While neither of these rules can be used to solve overfitting in practice, these experiments can provide guidance for future methods and an “upper bound” on the best improvement that can be obtained from optimal stopping. We investigate two oracle early stopping criteria for setting the number of gradient steps: using the expected Bellman error and the expected returns of the greedy policy w.r.t. the current Q-function (oracle returns). We implement both methods by running the projection step of Replay-FQI to convergence using gradient descent, and afterwards selecting the intermediate Q-function which is judged best by the evaluation metric (lowest Bellman error or highest returns). Using such oracle stopping metrics results in a modest boost in performance in tabular domains (Fig. 5). Thus, we believe that there is promise in further improving such early-stopping methods for reducing overfitting in deep RL algorithms.

We might draw a few actionable conclusions from these experiments. First, overfitting is indeed a serious issue with Q-learning, and too many gradient steps or too few samples can lead to poor performance. Second, replay buffers and early stopping can be used to mitigate the effects of overfitting. Third, although overfitting is a problem, large architectures are still preferred, because the harm from function approximation bias outweighs the harm from increased overfitting with large models.

Non-Stationarity

In this section, we discuss issues related to the non-stationarity of the Q-learning process (relating to the Bellman backup and Bellman error minimization).

Instability in Q-learning methods is often attributed to the nonstationarity of the regression objective (Lillicrap et al., 2015; Mnih et al., 2015). Nonstationarity occurs in two places: in the changing target values $\mathcal{T}Q$, and in a changing weighting distribution $\mu$ (“distribution shift”) (i.e., due to samples being taken from different policies). Note that a non-stationary objective, by itself, is not indicative of instability. For example, gradient descent can be viewed as successively minimizing linear approximations to a function: for gradient descent on $f$ with parameter $\theta$ and learning rate $\alpha$, we have the “moving” objective $\theta^{t+1}=\underset{\theta}{\textrm{argmin}}\ \{\theta^{T}\nabla_{\theta}f(\theta^{t})-\frac{1}{2\alpha}\left\lVert\theta-\theta^{t}\right\rVert^{2}_{2}\}=\theta^{t}-\alpha\nabla_{\theta}f(\theta^{t})$. However, the fact that the Q-learning algorithm prescribes an update rule and not a stationary objective complicates analysis. Indeed, the motivation behind algorithms such as GTD (Sutton et al., 2009b, a) and residual methods (Baird, 1995; Scherrer, 2010) can be seen as introducing a stationary objective that can be optimized with standard procedures such as gradient descent for increased stability. Therefore, a key question to investigate is whether these non-stationarities are detrimental to the learning process.

2 Does a moving target cause instability in the absence of a moving distribution?

To study the moving target problem, we must first isolate the effects of a moving target, and study how the rate at which the target changes impacts performance. To control the rate at which the target changes, we introduce an additional smoothing parameter $\alpha$ to Q-iteration, where the target values are now computed as an $\alpha$-moving average over previous targets. We define the $\alpha$-smoothed Bellman backup, $\mathcal{T}^{\alpha}$, as follows:

This scheme is inspired by the soft target update used in algorithms such as DDPG (Lillicrap et al., 2015) and SAC (Haarnoja et al., 2017) to improve the stability of learning. Standard Q-iteration uses a “hard” update where $\alpha=1$. A soft target update weakens the contraction of Q-iteration from $\gamma$ to $1-\alpha+\alpha\gamma$ (See Appendix C), so we expect slower convergence, but perhaps it is more stable under heavy function approximation error. We performed experiments with this modified backup using Exact-FQI under the $\text{Unif}(s,a)$ weighting distribution.

Our results are presented in Appendix Fig. 12. We find that the most cases, the hard update with $\alpha=1$ results in the fastest convergence and highest asymptotic performance. However, for the smallest two architectures we used, $4\times 4$ and $16\times 16$, lower values of $\alpha$ (such as 0.1) achieve slightly higher asymptotic performance. Thus, while more expressive architectures are still stable under fast-changing targets, we believe that a slowly moving target may have benefits under heavy approximation error. This evidence points to either using large function approximators, in line with the conclusions drawn in the previous sections, or adaptively slowing the target updates when the architecture is weak (relative to the problem difficulty) and the projected Bellman error is therefore high.

3 Does distribution shift impact performance?

To study the distribution shift problem, we exactly compute the amount of distribution shift between iterations in total-variation distance, $D_{TV}(\mu^{t+1}||\mu^{t})$ and the “loss shift”:

The loss shift quantifies the Bellman error objective when evaluated under a new distribution - if the distribution shifts to previously unseen or low support states, we would expect a highly inaccurate Q-value in such states, and a correspondingly high loss shift.

We run our experiments using Exact-FQI with a 256x256 layer architecture, and plot the distribution discrepancy and the loss discrepancy in Fig. 6. We find that Prioritized$(s,a)$ has the greatest shift, followed by on-policy variants. Replay buffers greatly reduce distribution shift compared to on-policy learning, which is similar to the de-correlation argument cited for its use by Mnih et al. (2015). However, we find that this metric correlates very little with the actual performance of the algorithm (Fig. 7). For example, prioritized weighting performs well yet has high distribution shift.

Overall, our experiments indicate that nonstationarities in both distributions and target values, when isolated, do not cause significant stability issues. Instead, other factors such as sampling error and function approximation appear to have more significant effects on performance. In the light of these findings, we might therefore ask: can we design a better sampling distribution, without regard for distributional shift and with regard for high-entropy, that results in better final performance, and is realizable in practice? We investigate this in the following section.

Sampling Distributions

As alluded to in Section 6, the choice of sampling distribution $\mu$ is an important design decision can have a large impact on performance. Indeed, it is not immediately clear which distribution is ideal for Q-learning. In this section, we hope to shed some light on this issue.

Off-policy data has been cited as one of the “deadly triads” for Q-learning (Sutton & Barto, 2018), which has potential to cause instabilities in learning. On-policy distributions (Tsitsiklis & Van Roy, 1997) and fixed behavior distributions (Sutton et al., 2009b; Maei et al., 2010) have often been targeted for theoretical convergence analysis, and many works use importance sampling to correct for off-policyness (Precup et al., 2001; Munos et al., 2016) However, to our knowledge, there is relatively little guidance which compares how different weighting distributions compare in terms of convergence rate and final solutions.

Nevertheless, several works give hypotheses on good choices for weighting distributions. (Munos, 2005) provides an error bound which suggests that “more uniform” weighting distributions can guarantee better worst-case performance. (Geist et al., 2017) suggests that when the state-distribution is fixed, the action distribution should be weighted by the optimal policy for residual Bellman errors. In deep RL, several methods have been developed to prevent instabilities in Q-Learning, such as prioritized replay (Schaul et al., 2015), and mixing replay buffer with on-policy data (Hausknecht & Stone, 2016; Zhang & Sutton, 2017) have been found to be beneficial. In our experiments, we aim to empirically analyze multiple choices for weighting distributions to determine which are the most effective.

2 What Are the Best Weighting Distributions in Absence of Sampling Error?

We begin by studying the effect of weighting distributions when disentangled from sampling error. We run Exact-FQI with varying choices of architectures and weighting distributions and report our results in Fig. 8. $\text{Unif}(s,a)$ $Replay(s,a)$, and $\text{Prioritized}(s,a)$ consistently result in the highest returns across all architectures. We believe that these results are in favor of the uniformity hypothesis: the top performing distributions spread weight across larger support of the state-action space. For example, a replay buffer contains state-action tuples from many policies, and therefore would be expected to have wider support than the state-action distribution of a single policy. We can see this general trend in Fig. 9. These distributions generally result in the tightest contraction rates, and allow the Q-function to focus on locations where the error is high. In the sampled setting, this observation motivates exploration algorithms that maximize state coverage (for example, Hazan et al. (2018) solve an exploration objective which maximizes state-space entropy). However, note that in this particular experiment, there is no sampling. All states are observed, just with different weights, thus isolating the issue of distributions from the issue of sampling.

3 Designing a Better Off-Policy Distribution: Adversarial Feature Matching

Note that $\Phi(s)$ is a function of $\theta$ but, while solving the maximization, $\theta$ is assumed to be a constant. This is equivalent to solving only the inner maximization with a constraint, and empirically provides better stability. Implementation details for AFM are provided in Appendix D. The $\frac{\sum_{i}\Phi(s_{i})}{N}$ denotes an estimator for the true expectation under some sampling distribution, such as a uniform distribution over all states and actions (in exact FQI) or the replay buffer distribution. So, $\frac{\sum_{i}\Phi(s_{i})}{N}\approx E_{p_{rb}}[\Phi]$ holds when using a replay buffer.

While both AFM and PER tend to upweight samples in the buffer with a high Bellman error, PER explicitly attempts to reduce distribution shift via importance sampling. As we observed in Section 7, distributional shift is not actually harmful in practice, and AFM dispenses with this goal, instead explicitly aiming to rebalance the buffer to attain better coverage via adversarial optimization. In our experiments, this results in substantially better performance, consistent with the hypothesis that coverage, rather than reduction of distributional shift, is the most important property in a sampling distribution.

In tabular domains with Exact-FQI, we find that AFM performs at par with the top performing weighting distributions, such as $\text{Unif}(s,a)$ and better than $\text{Prioritized}(s,a)$ (Fig. 8). This confirms that adaptive prioritization works better than Prioritized($s,a$). Another benefit of AFM is its robustness to function approximation and the performance gains in the case of small architectures (say, $(4,4)$) are particularly noticeable. (Fig. 8)

In tabular domains with Replay-FQI (Table 1), we also compare AFM to prioritized replay (PER) (Schaul et al., 2015), where AFM and PER perform similarly in terms of normalized returns. Note that AFM reweights samples drawn uniformly from the buffer, whereas PER changes which samples are actually drawn. We also evaluate a variant of AFM (AFM+Sampling in Table 1) which changes which samples instead of reweighting. Essentially, in this version we sample from the replay buffer using probabilities determined by the AFM optimization, rather than using importance sampling while making bellman updates. We note that, in Table 1, AFM+Sampling performs strictly better than AFM and PER.

We further evaluate AFM on MuJoCo tasks with the TD3 algorithm (Fujimoto et al., 2018) and the entropy constrained SAC algorithm (Haarnoja et al., 2018). We find that in all 3 tested domains (Half-Cheetah, Hopper and Ant), AFM yields substantial empirical improvement in the case of TD3 (Fig. 10) and performs slightly better than entropy constrained SAC (Fig. 11). Surprisingly, we found PER to not work very well in these domains. In light of these results, we conclude that: (1) the choice of sampling distribution is very important for performance, and (2) considerations such as incorporating knowledge about the function approximator (for example, through $\Phi$) into the choice of $\mu$ (the sampling/weighting distribution) can be very effective.

Conclusions and Discussion

From our analysis, we have several broad takeaways for the design of deep Q-learning algorithms.

Potential convergence issues with Q-learning do not seem to be endemic empirically, but function approximation still has a strong impact on the solution to which these methods converge. This impact goes beyond just approximation error, suggesting that Q-learning methods do find suboptimal solutions (within the given function class) with smaller function approximators. However, expressive architectures largely mitigate this problem, suffer less from bootstrapping error, converge faster, and more stable with moving targets.

Sampling error can cause substantial overfitting problems with Q-learning. However, replay buffers and early stopping can mitigate this problem, and the biases incurred from small function approximators outweigh any benefits they may have in terms of overfitting. We believe the best strategy is to keep large architectures but carefully select the number of gradient steps used per sample. We showed that employing oracle early stopping techniques can provide huge benefits in the performance in Q-learning. This motivates the future research direction of devising early stopping techniques to dynamically control the number of gradient steps in Q-learning, rather than setting it as a hyperparameter as this can give rise to big difference in performance.

The choice of sampling or weighting distribution has significant effect on solution quality, even in the absence of sampling error. Surprisingly, we do not find on-policy distributions to be the most performant, but rather methods which have high state-entropy and spread mass uniformly among state-action pairs, seem to be highly effective for training. Based on these insights, we propose a new weighting distribution which balances high-entropy and state aliasing, AFM, that yields fair improvements in both tabular and continuous domains with state-of-the-art off-policy RL algorithms.

Finally, we note that there are many other topics in Q-learning that we did not investigate, such as overestimation bias and multi-step returns. We believe that these issues too could be studied in future work with our oracle-based analysis framework.

Acknowledgements

We thank Vitchyr Pong and Kristian Hartikainen for providing us with implementations of RL algorithms. We thank Chelsea Finn for comments on an earlier draft of this paper. SL thanks George Tucker for helpful discussion. We thank Google, NVIDIA, and Amazon for providing computational resources. This research was supported by Berkeley DeepDrive, NSF IIS-1651843 and IIS-1614653, the DARPA Assured Autonomy program, and ARL DCIST CRA W911NF-17-2-0181.

References

Appendices

Appendix A Benchmark Tabular Domains

We evaluate on a benchmark of 8 tabular domains, selected for qualitative differences.

4 Gridworlds. The Gridworld environment is an NxN grid with randomly placed walls. The reward is proportional to Manhattan distance to a goal state (1 at the goal, 0 at the initial position), and there is a 5% chance the agent travels in a different direction than commanded. We vary two parameters: the size ($16\times 16$ and $64\times 64$), and the state representations. We use a “one-hot” representation, an (X, Y) coordinate tuple (represented as two one-hot vectors), and a “random” representation, a vector drawn from $\mathcal{N}(0,1)^{N}$, where N is the width or height of the Gridworld. The random observation significantly increases the challenge of function approximation, as significant state aliasing occurs.

Cliffwalk: Cliffwalk is a toy example from Schaul et al. (2015). It consists of a sequence of states, where each state has two allowed actions: advance to the next state or return to the initial state. A reward of 1.0 is obtained when the agent reaches the final state. Observations consist of vectors drawn from $\mathcal{N}(0,1)^{16}$.

InvertedPendulum and MountainCar: InvertedPendulum and MountainCar are discretized versions of continuous control tasks found in OpenAI gym (Plappert et al., 2018), and are based on problems from classical RL literature. In the InvertedPendulum task, an agent must swing up an pendulum and hold it in its upright position. The state consists of the angle and angular velocity of the pendulum. Maximum reward is given when the pendulum is upright. The observation consists of the $\sin$ and $\cos$ of the pendulum angle, and the angular velocity. In the MountainCar task, the agent must push a vehicle up a hill, but the hill is steep enough that the agent must gather momentum by swinging back and forth within a valley in order to reach the top. The state consists of the position and velocity of the vehicle.

SparseGraph: The SparseGraph environment is a 256-state graph with randomly drawn edges. Each state has two edges, each corresponding to an action. One state is chosen as the goal state, where the agent receives a reward of one.

Appendix B Fitted Q-iteration with Bounded Projection Error

When function approximation is introduced to Q-iteration, we lose guarantees that our solution will converge to the optimal solution $Q^{*}$, because the composition of projection and backup is no longer guaranteed to be a contraction under any norm. However, this does not imply divergence, and in most cases it merely degrades the quality of solution found.

Let the projection or Bellman error at each iteration of FQI be uniformly bounded by $\delta$, i.e. $\lVert\hat{Q}_{i+1}-\mathcal{T}\hat{Q}_{i}\rVert_{\infty}\leq\delta\ \forall\ i$. Then, the error in the final solution is bounded as

See of Chapter 6 of Bertsekas & Tsitsiklis (1996). ∎

We can use this statement to provide a bound on the performance of the final policy.

Suppose we run fitted Q-iteration, and let the projection error at each iteration be uniformly bounded by $\delta$, i.e. $\lVert\hat{Q}_{i+1}-\mathcal{T}\hat{Q}_{i}\rVert_{\infty}\leq\delta\ \forall\ i$. Letting $\eta(\pi)$ denote the returns of a policy $\pi$, the the performance of the final policy is bounded as:

This result is obtained by substituting Thm. B.1 into Propositon 6.1 of Bertsekas & Tsitsiklis (1996). ∎

When the weighting distribution $\mu$ does not have support over all states and actions, divergence can still occur, as noted in the counterexamples such as Section 11.2 of Sutton & Barto (2018). In this case, we consider two states (state 1 and 2) with feature vectors 1 and 2, respectively, and a linear approximator with parameter $w$. There exists a single action with a deterministic transition from state 1 to state 2, and we only sample the transition from state 1 to state 2 (i.e. $\mu(s,a)$ is 1 for state 1 and 0 for state 2). All rewards are 0. In this case, the projected Bellman backup takes the form:

Which will cause unbounded growth $\lim_{t\to\infty}w_{t}=\infty$ when iterated, provided $\gamma>0.5$. However, if we add a transition from state 2 back to itself or to state 1, and place nonzero probability on sampling these transitions, divergence can be avoided.

Appendix C α𝛼\alpha-smoothed Q-iteration

In this section we show that the $\alpha$-smoothed Bellman backup introduced in Section 6 is still a valid Q-iteration method, in that it is a contraction (for $1\geq\alpha>0$) and thus converges to $Q^{*}$.

We define the $\alpha$-smoothed Bellman backup as:

$\mathcal{T}^{\alpha}$ is a $1-\alpha+\gamma\alpha$-contraction:

This statement follows from straightforward application of the triangle rule and the fact that $\mathcal{T}$ is a $\gamma$-contraction:

Appendix D Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation

As described in section 7.3, we devise a novel weighting scheme for the Bellman error objective based on an adversarial minimax game. The adversary computes weights $p_{\phi}(s,a)$ (representing the weighting distribution $\mu$), for the Bellman error: $(Q_{\theta,w}(s,a)-y(s,a))^{2}$. Recalling from Section 7.3, the optimization problem is given by:

where $\Phi(s)$ are the state features learned by the Q-function approximator. $\Phi(s)$ is easy to extract out of the multiheaded $Q(s,a)$ ($Q(s,a)=w_{a}^{T}\Phi(s)$) model typically used for discrete action control, as one choice is to let $\Phi(s)$ be the output of the penultimate layer of the Q-network. For continuous control tasks, however, we model $\Phi(s,a)$ (which is a function of the actions as well) as state-only features are unavailable, unless separately modeled. This can also be interpreted as modelling a feature matching constraint on the gradient of $Q(s,a)$ with respect to the last linear parameters $w_{a}$. A possible extension is to take into account the entire gradient as the features in the feature matching constraint, that is, $\nabla_{w,\theta}Q_{w,\theta}(s,a)$.

We solve this saddle point problem using alternating dual gradient descent. We first solve the inner maximization problem, and then use its solution to then solve the outer minimization problem. We first compute the Lagrangian for the maximization, $\mathcal{L}_{\text{inner}}({\phi;\lambda,\theta})$ by introducing a dual variable $\lambda$,

(Note that this Lagrangian is flipped in sign because we first convert the maximization problem to standard minimization form.) We now solve the inner problem using dual gradient descent. We then plug in the solutions (approximate solutions obtained after gradient descent), $(p^{*},\lambda^{*})$ into the Lagrangian, to then solve the outside minimization over $\theta$. Note that while $\Phi$ depends on $\theta$ (as it is the feature layer of the Q-network), we don not backpropagate through $\Phi$ while solving the minimization. This improves stability of the Q-network training in practice and to makes sure that Q-function is only affected by FQI updates. In practice, we take up to 10 gradient steps for the inner problem every 1 gradient step of the outer problem. The algorithm is summarized in Algorithm 4. Our results provided in the main paper and here don’t particularly assume any other tricks like Optimistic Gradient (Daskalakis et al., 2018), using exponential moving average of the parameters (Yazıcı et al., 2019). Our tabular experiments seemed to benefit some what using these tricks.

Practical implementation with replay buffers

Appendix E Function approximation analysis on Mujoco Tasks

As discussed in Section 4, we validate our findings on the effect of function approximation on 3 MuJoCo tasks from OpenAI Gym with the SAC algorithm from the author’s implementation at (Tuomas Haarnoja & Levine, 2018). We observe that bigger networks learn faster and better in general.

Appendix F Additional Plots