Instabilities of Offline RL with Pre-Trained Neural Representation

Introduction

Offline reinforcement learning (RL) seeks to utilize offline data to alleviate the sample complexity burden in challenging sequential decision making settings where sample-efficiency is crucial (Mandel et al., 2014; Gottesman et al., 2018; Wang et al., 2018; Yu et al., 2019); it is seeing much recent interest due to the large amounts of offline data already available in numerous scientific and engineering domains. The goal is to efficiently evaluate (or learn) policies, in scenarios where the data are collected from a distribution that (potentially) substantially differs from that of the target policy to be evaluated. Broadly, an important question here is to better understand the practical challenges we face in offline RL problems and how to address them.

Let us start by considering when we expect offline RL to be successful from a theoretical perspective (Munos, 2003; Szepesvári and Munos, 2005; Antos et al., 2008; Munos and Szepesvári, 2008; Tosatto et al., 2017; Chen and Jiang, 2019; Duan et al., 2020). For the purpose of evaluating a given target policy, Duan et al. (2020) showed that under a (somewhat stringent) policy completeness assumption with regards to a linear feature mappingA linear feature mapping is said to be complete if Bellman backup of a linear function remains in the span of the given features. See Assumption 2 for a formal definition. along with data coverage assumption, then Fitted-Q iteration (FQI) (Gordon, 1999) — a classical offline Bellman backup based method — can provably evaluate a policy with low sample complexity (in the dimension of the feature mapping). While the coverage assumptions here are mild, the representational conditions for such settings to be successful are more concerning; they go well beyond simple realizability assumptions, which only requires the representation to be able to approximate the state-value function of the given target policy.

Recent theoretical advances (Wang et al., 2021) show that without such a strong representation condition, there are lower bounds exhibiting exponential error amplification (in the problem horizon) unless the data collection distribution has only a mild distribution shift relative to the target policy.We discuss these issues in more depth in Section 4, where we give a characterization of FQI in the discounted setting It is worthwhile to emphasize that this “low distribution condition” is a problematic restriction, since in offline RL, we seek to utilize diverse data collection distributions. As an intuitive example to contrast the issue of distribution shift vs. coverage, consider offline RL for spatial navigation tasks (e.g. Chang et al. (2020)): coverage in our offline dataset would seek that our dataset has example transitions from a diverse set of spatial locations, while a low distribution shift condition would seek that our dataset closely resembles that of the target policy itself for which we desire to evaluate.

From a practical point of view, it is natural to ask to what extent these worst-case characterizations are reflective of the scenarios that arise in practical applications because, in fact, modern deep learning methods often produce representations that are extremely effective, say for transfer learning (computer vision Yosinski et al. (2014) and NLP Peters et al. (2018); Devlin et al. (2018); Radford et al. (2018) have both witnessed remarkable successes using pre-trained features on downstreams tasks of interest). Furthermore, there are number of offline RL methods with promising performance on certain benchmark tasks (Laroche et al., 2019; Fujimoto et al., 2019; Jaques et al., 2020; Kumar et al., 2019; Agarwal et al., 2020; Wu et al., 2020; Kidambi et al., 2020; Ross and Bagnell, 2012). There are (at least) two reasons which support further empirical investigations over these current works: (i) the extent to which these data collection distributions are diverse has not been carefully controlledThe data collection in many benchmarks tasks are often taken from the data obtain when training an online policy, say with deep Q-learning or policy gradient methods. and (ii) the hyperparameter tuning in these approaches are done in an interactive manner tuned on how the policy actually behaves in the world as opposed to being tuned on the offline data itself (thus limiting the scope of these methods).

In this work we provide a careful empirical investigation to further understand how sensitive offline RL methods are to distribution shift. Along this line of inquiry, One specific question to answer is to what extent we should be concerned about the error amplification effects as suggested by worst-case theoretical considerations.

We study these questions on a range of standard tasks ($6$ tasks from the OpenAI gym benchmark suite), using offline datasets with features from pre-trained neural networks trained on the task itself. Our offline datasets are a mixture of trajectories from the target policy itself, along the data from other policies (random or lower performance policies). Note that this is favorable setting in that we would not expect realistic offline datasets to have a large number of trajectories from the target policy itself.

The motivation for using pre-trained features are both conceptual and technical. First, we may hope that such features are powerful enough to permit sample-efficient offline RL because they were learned in an online manner on the task itself. Also, practically, while we are not able to verify if certain theoretical assumptions hold, we may optimistically hope that such pre-trained features will perform well under distribution shift (indeed, as discussed earlier, using pre-trained features has had remarkable successes in other domains). Second, using pre-trained features allows us to decouple practical representational learning questions from the offline RL question, where we can focus on offline RL with a given representation. We provide further discussion on our methodologies in Section 6. We also utilize random Fourier features (Rahimi et al., 2007) as a point of comparison.

The main conclusion of this work, through extensive experiments on a number of tasks, is that: we do in fact observe substantial error amplification, even when using pre-trained representations, even we tune hyper-parameters, regardless of what the distribution was shifted to; furthermore, this amplification even occurs under relatively mild distribution shift. As an example, Figure 1 shows the performance of FQI on Walker-2d v2 when our offline dataset has $1$ millions samples generated by the target policy itself, with additional samples from random policies.

These experiments also complement the recent hardness results in Wang et al. (2021) showing the issue of error amplification is a real practical concern. From a practical point of view, our experiments demonstrate that the definition of a good representation is more subtle than in supervised learning. These results also raise a number of concerns about empirical practices employed in a number of benchmarks, and they also have a number of implications for moving forward (see Section 7 with regards to these two points).

Finally, it is worth emphasizing that our findings are not suggesting that offline RL is not possible. Nor does it suggest that there are no offline RL successes, as there have been some successes in realistic domains (e.g. (Mandel et al., 2014; Chang et al., 2020)). Instead, our emphasis is that the conditions for success in offline RL, both from a theoretical and an empirical perspective, are substantially stronger than those in supervised learning settings.

Related Work

Offline RL is closely related to the theory of Approximate Dynamic Programming (Bertsekas and Tsitsiklis, 1995). Existing theoretical work (Munos, 2003; Szepesvári and Munos, 2005; Antos et al., 2008; Munos and Szepesvári, 2008; Tosatto et al., 2017; Duan et al., 2020) usually makes strong representation conditions. In offline RL, the most natural assumption would be realizability, which only assumes the value function of the policy to be evaluated lies in the function class, and existing theoretical work usually make assumptions stronger than realizability. For example, Szepesvári and Munos (2005); Duan et al. (2020); Wang et al. (2021) assume (approximate) closedness under Bellman updates, which is much stronger than realizability. Polynomial sample complexity results are also obtained under the realizability assumption, albeit under coverage conditions Xie and Jiang (2020) or stringent distribution shift conditions (Wang et al., 2021). Technically, our characterization of FQI (in Section 4) is similar to the characterization of LSPE by Wang et al. (2021), although we work in the more practical discounted case while Wang et al. (2021) work in the finite-horizon setting.

Error amplification induced by distribution shift is a known issue in the theoretical analysis of RL algorithms. See (Gordon, 1995, 1996; Munos and Moore, 1999; Ormoneit and Sen, 2002; Kakade, 2003; Zanette et al., 2019) for discussion on this topic. Recently, Wang et al. (2021) show that in the finite-horizon setting, without a strong representation condition, there are lower bounds exhibiting exponential error amplification unless the data collection distribution has only a mild distribution shift relative to the target policy. Such lower bound was later generalized to the discounted setting by Amortila et al. (2020). Similar hardness results are also obtained by Zanette (2020), showing that offline RL could be exponentially harder than online RL.

Empirical Work.

Error amplification in offline RL has been observed in empirical work (Fujimoto et al., 2019; Kumar et al., 2019) and was called “extrapolation error” in these work. For example, it has been observed in (Fujimoto et al., 2019) that DDPG (Lillicrap et al., 2015) trained on the replay buffer of online RL methods performs significantly worse than the behavioral agent. Compared to previous empirical study on the error amplification issue, in this work, we use pre-trained features which allow us to decouple practical representational learning questions from the offline RL question, where we can focus on offline RL with a given representation. We also carefully control the data collection distributions, with different styles of shifted distributions (those induced by random trajectories or induced by lower performance policies) and different levels of noise.

To mitigate the issue of error amplification, prior empirical work usually constrains the learned policy to be closer to the behavioral policy (Fujimoto et al., 2019; Kumar et al., 2019; Wu et al., 2020; Jaques et al., 2020; Nachum et al., 2019b; Peng et al., 2019; Siegel et al., 2020; Kumar et al., 2020; Yu et al., 2021) and utilizes uncertainty quantification (Agarwal et al., 2019; Yu et al., 2020; Kidambi et al., 2020; Rafailov et al., 2020). We refer interested readers to the survey by Levine et al. (2020) for recent developments on this topic.

Background

Value Function.

Given a policy $\pi$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, define

Offline Reinforcement Learning.

Linear Function Approximation.

Notation.

An Analysis of Fitted Q-Iteration in the Discounted Setting

In order to illustrate the error amplification issue and discuss conditions that permit sample-efficient offline RL, in this section, we analyze Fitted Q-Iteration (FQI) (Gordon, 1999) when applied to the offline policy evaluation problem under the realizability assumption. Here we focus on FQI since it is the prototype of many practical algorithms. For example, when DQN (Mnih et al., 2015) is run on off-policy data, and the target network is updated slowly, it can be viewed as an analog of FQI, with neural networks being the function approximator. We give a description of FQI in Algorithm 1. We also perform experiments on temporal difference methods in our experiments (Section 5). For simplicity, we assume a deterministic target policy $\pi$.

We remark that the issue of error amplification discussed here is similar to that in Wang et al. (2021), which shows that if one just assumes realizability, geometric error amplification is inherent in offline RL in the finite-horizon setting. Here we focus on the discounted case which exhibit some subtle differences (see, e.g., Amortila et al. (2020)).

Now we present a general lemma that characterizes the estimation error of Algorithm 1 by an equality. Later, we apply this general lemma to special cases.

where $L=\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi}/N$.

By Lemma 4.1, to achieve a bounded error, the matrix $L=\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi}/N$ should satisfy certain non-expansive properties. Otherwise, the estimation error grows exponentially as $t$ increases, and geometric error amplification occurs. Now we discuss two cases when geometric error amplification does not occur, in which case the estimation error can be bounded with a polynomial number of samples.

Policy Completeness.

The policy completeness assumption (Szepesvári and Munos, 2005; Duan et al., 2020) assumes the feature mapping is complete under bellman updates.

Now we show that under Assumption 2, FQI achieves bounded error with polynomial number of samples.

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.

In the formal proof, we combine the above with standard concentration arguments to obtain a finite-sample rate. ∎

We remark that variants of Lemma 4.2 have been known in the literature (see, e.g., (Duan et al., 2020) for a similar analysis in the finite-horizon setting). Here we present Lemma 4.2 mainly to illustrate the versatility of Lemma 4.1.

Low Distribution Shift.

Now we focus on the case where the distribution shift between the data distributions and the distribution induced by the target policy is low. Here, our low distribution shift condition is similar to that in Wang et al. (2021), though we focus on the discounted case while Wang et al. (2021) focus on the finite-horizon case.

To measure the distribution shift, our main assumption is as follows.

Now we show that under Assumption 3, FQI achieves bounded error with polynomial number of samples. The proof can be found in the appendix.

1 Simulation Results

We now provide simulation results on a synethic environment to better illustrate the issue of error amplification and the tightness of our characterization of FQI in Lemma 4.1.

In our construction, the number of data points is $|D|=N$, where $N=100$ or $N=200$. The feature dimension is fixed to be $d=100$ and the discount factor $\gamma=0.99$. We draw $\theta^{*}$ from $\mathcal{N}(0,I_{d})$. The data distribution, the transition operator and the rewards are all deterministic in this environment. For each $(s_{i},a_{i},r_{i},s_{i}^{\prime})\in D$, $\phi(s_{i},a_{i})$ and $\phi(s_{i}^{\prime},\pi(s_{i}^{\prime}))$ are independently drawn from $\mathcal{N}(0,I_{d})$, and $r_{i}=\phi(s,a)^{\top}\theta^{*}-\gamma\phi(s^{\prime},\pi(s^{\prime}))^{\top}\theta^{*}$ so that Assumption 1 holds. We then run FQI in Algorithm 1, by setting $T=100$ and $\lambda=10^{-4}$ or $10^{-3}$. In Figure 2, we plot the estimation error $\|\theta_{t}-\theta^{*}\|_{2}$ and the Frobenius norm of $(\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi})^{t}$, for $t=1,2,\ldots,100$. We repeat the experiment for $100$ times and report the mean estimation error and the mean Frobenius norm of $(\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi})^{t}$.

We remark that our dataset $D$ has sufficient coverage over the feature space, both when $N=100$ and $N=200$. This is because the feature covariance matrix has lower bounded eigenvalue with high probability in both cases, according to standard random matrix theory (Chen and Dongarra, 2005).

Results.

For deterministic environments, by Lemma 4.1, the estimation error is dominated by $(\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi})^{t}\theta^{*}$. As shown in Figure 2, geometric error amplification does occur, and the norm of $(\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi})^{t}$ grows exponentially as $t$ increases. Moreover, the norm of $(\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi})^{t}$ has almost the same growth trend as $\|\theta_{t}-\theta^{*}\|_{2}$. E.g., when $N=200$, the estimation error $\|\theta_{t}-\theta^{*}\|_{2}$ grows exponentially, although much slower than the case when $N=100$. In that case, the norm of $(\hat{\Lambda}^{-1}\Phi^{\top}\overline{\Phi})^{t}$ also increases much slower than the case when $N=200$. Our simulation results show that the issue of error amplification could occur even in simple environments, and our theoretical result in Lemma 4.1 gives a tight characterization of the estimation error.

Experiments

The goal of our experimental evaluation is to understand whether offline RL methods are sensitive to distribution shift in practical tasks, given a good representation (features extracted from pre-trained neural networks or random features). Our experiments are performed on a range of challenging tasks from the OpenAI gym benchmark suite (Brockman et al., 2016), including two environments with discrete action space (MountainCar-v0, CartPole-v0) and four environments with continuous action space (Ant-v2, HalfCheetah-v2, Hopper-v2, Walker2d-v2). We also provide further discussion on our methodologies in Section 6.

Our methodology proceeds according to the following steps:

We decide on a (target) policy to be evaluated, along with a good feature mapping for this policy.

Collect offline data using trajectories that are a mixture of the target policy along with another distribution.

Run offline RL methods to evaluate the target policy using the feature mapping found in Step 1 and the offline data obtained in Step 2.

We now give a detailed description for each step.

To find a policy to be evaluated together with a good representation, we run classical online RL methods. For environments with discrete action space (MountainCar-v0, CartPole-v0), we run Deep Q-learning (DQN) (Mnih et al., 2015), while for environments with continuous action space (Ant-v2, HalfCheetah-v2, Hopper-v2, Walker2d-v2), we run Twin Delayed Deep Deterministic policy gradient (TD3) (Fujimoto et al., 2018). The hyperparameters used can be found in Section B. The target policy is set to be the final policy output by DQN or TD3. We also set the feature mapping to be the output of the last hidden layer of the learned value function networks, extracted in the final stage of the online RL methods. Since the target policy is set to be the final policy output by the online RL methods, such feature mapping contains sufficient information to represent the value functions of the target policy. We also perform experiments using random Fourier features (Rahimi et al., 2007).

Step 2: Collect Offline Data.

Step 3: Run Offline RL Methods.

With the collected offline data and the target policy (together with a good representation), we can now run offline RL methods to evaluate the (discounted) value of the target policy. In our experiments, we run FQI (described in Section 4) and Least-Squares Temporal DifferenceSee the Section B for a description of LSTD. (LSTD, a temporal difference offline RL method) (Bradtke and Barto, 1996). For both algorithms, the only hyperparameter is the regularization parameter $\lambda$ (cf. Algorithm 1), which we choose from $\{10^{-1},10^{-2},10^{-3},10^{-4},10^{-8}\}$. In our experiments, we report the performance of the best-performing $\lambda$ (measured in terms of the square root of the mean squared estimation error in the final stage of the algorithm, taking average over all repetitions of the experiment); such favorable hyperparameter tuning is clearly not possible in practice (unless we have interactive access to the environment). See Section 5.2 for more discussion on hyperparameter tuning.

In our experiments, we repeat this whole process $5$ times. For each FQI round, we report the square root of the mean squared evaluation error, taking average over $100$ randomly chosen states. We also report the values ($V^{\pi}(s)$) of those randomly chosen states in Table 2. We note that in our experiments, the randomness combines both from the feature generation process (representation uncertainty, Step 1) and the dataset (Step 2). Even though we draw millions of samples in Step 2, the estimation of FQI could still have high variance. Note that this is consistent with our theory in Lemma 4.1, which shows that the variance can also be exponentially amplified without strong representation conditions and low distribution shift conditions. We provide more discussion regarding this point in Section B.3.

2 Results and Analysis

Due to space limitations, we present experiment results on Walker2d-v2, Hopper-v2 and CartPole-v0. Other experimental results are provided in Section C.

We first present the performance of FQI with features from pre-trained neural networks and distributions induced by random policies. The results are reported in Figure 6. Perhaps surprisingly, compared to the result on $D^{\star}$, adding more data (from random trajectories) into the dataset generally hurts the performance. With more data added into the dataset, the performance generally becomes worse. Thus, even with features from pre-trained neural networks, the performance of offline RL methods is still sensitive to data distribution.

Distributions Induced by Lower Performance Polices.

Random Fourier Features.

Now we present the performance of FQI with random Fourier features and distributions induced by random policies. The results are reported in Figure 6. Here we tune the hyperparameters of the random Fourier features so that FQI achieves reasonable performance on $D^{\star}$. Again, with more data from random trajectories added into the dataset, the performance generally becomes worse. This implies our observations above hold not only for features from pre-trained neural networks, but also for random features. On the other hand, it is known random features achieve reasonable performance in policy gradient methods (Rajeswaran et al., 2017) in the online setting. This suggests that the representation condition required by offline policy evaluation could be stronger than that of policy gradient methods in online setting.

Policy Comparison.

Sensitivity to Hyperparameters.

In previous experiments, we tune the regularization parameter $\lambda$ and report the performance of the best-performing $\lambda$. However, we remark that in practice, without access to online samples, hyperparameter tuning is hard in offline RL. Here we investigate how sensitive FQI is to different regularization parameters $\lambda$. The results are reported in Figure 6. Here we fix the environment to be Walker2d-v2 and vary the number of additional samples from random trajectories and the regularization parameter $\lambda$. As observed in experiments, the regularization parameter $\lambda$ significantly affects the performance of FQI, as long as there are random trajectories added into the dataset.

Performance of LSTD.

Finally, we present the performance of LSTD with features from pre-trained neural networks and distributions induced by random policies. The results are reported in Table 1. With more data from random trajectories added into the dataset, the performance of LSTD becomes worse. This means the sensitivity to distribution shift is not specific to FQI, but also holds for LSTD.

Further Methodological Discussion

We now expand on a few methodological motivations over the previous section, because these points merit further discussion.

As mentioned in Section 2, there are a number of algorithms for offline RL (Fujimoto et al., 2019; Kumar et al., 2019; Wu et al., 2020; Jaques et al., 2020; Nachum et al., 2019b; Peng et al., 2019; Siegel et al., 2020; Kumar et al., 2020; Agarwal et al., 2019; Yu et al., 2020; Kidambi et al., 2020; Rafailov et al., 2020). In this work, our focus is on the more basic policy evaluation problem, rather than policy improvement, and because of this, we focus on FQI and LSTD due to that these other methodologies are designed for the further challenges associated with policy improvement. Specifically, let us discuss two specific reasons why our current methodology is well motivated, in light of the broader set of neural approaches for offline policy improvement. First, the main techniques in these prior empirical approaches largely focus on constraining the learned policy to be close to the behavioral policy, which is achieved by adding a penalty (by uncertainty quantification); in our setting, the target policy is given and such constraints are not needed due to that the target policy is not being updated. Furthermore, since we mainly focus on policy evaluation in this paper, it is not evident how to even impose such penalties (or constraints) for a fixed policy. Second, in this work, in order to better understand offline RL methods when combined with function approximation schemes, we decouple practical representational learning questions from the offline RL methods because this allows for us to directly examine if the given neural representation, which is sufficient to represent the value of the target policy, is sufficient for effective offline RL. By doing so, we can better understand if the error amplification effects (suggested by worst-case theoretical analysis) occur when combining pre-trained features with offline RL methods. An interesting further question is how to couple the representational learning with offline RL (for the simpler question of policy evaluation) — see the discussion in Section 7.

What about importance sampling approaches?

One other approach we did not consider for policy evaluation is importance sampling (Dudík et al., 2011; Mandel et al., 2014; Thomas et al., 2015; Li et al., 2015; Jiang and Li, 2016; Thomas and Brunskill, 2016; Guo et al., 2017; Wang et al., 2017; Liu et al., 2018; Farajtabar et al., 2018; Xie et al., 2019; Kallus and Uehara, 2019; Liu et al., 2019; Uehara and Jiang, 2019; Kallus and Uehara, 2020; Jiang and Huang, 2020; Feng et al., 2020; Yang et al., 2020; Nachum et al., 2019a; Zhang et al., 2020a, b). There is a precise sense in which importance sampling would in fact be successful in our setting, and we view this as a point in favor of our approach, which we now explain. First, to see that importance sampling will be successful, note that due to the simplicity of our data collection procedure, we have that all our experiments contain at least $30\%$ of the trajectories collected from the target policy itself, so if we have access to the correct importance weights, then importance sampling can be easily seen to have low variance. However, here, importance sampling has low variance only due to our highly favorable (and unrealistic) scenario where our data collection has such a high fraction of trajectories from the target policy itself. If we consider a setting where the distribution shift is low in a spectral sense, as in Section 4, but where the the data collection does not have such a high fraction of trajectories collected from the target policy, it is not evident how to effectively implement the importance sampling approach because there is no demonstrably (or provably) robust method for combining function approximation with importance sampling. In fact, methods which combine importance sampling and function approximation are an active and important area of research.

Discussion and Implications

The main conclusion of this work, through extensive experiments on a number of tasks, is that we observe substantial error amplification, even when using pre-trained representations, even we (unrealistically) tune hyper-parameters, regardless of what the distribution was shifted to. Furthermore, this amplification even occurs under relatively mild distribution shift. Our experiments complement the recent hardness results in Wang et al. (2021) showing the issue of error amplification is a real practical concern.

The implications of these results, both from a theoretical and an empirical perspective, are that successful offline RL (where we seek to go beyond the constraining, low distribution shift regime) requires substantially stronger conditions beyond those which suffice for successful supervised learning. These results also raise a number of concerns about empirical practices employed in a number of benchmarks. We now discuss these two points further.

Our experiments demonstrate that the definition of a good representation in offline RL is more subtle than in supervised learning, since features extracted from pre-trained neural networks are usually extremely effective in supervised learning. Certainly, features extracted from pre-trained neural networks and random features satisfy the realizability assumption (Assumption 1) approximately. However, from our empirical findings, these features do not seem to satisfy strong representation conditions (e.g. Assumption 2) that permits sample-efficient offline RL. This suggests that better representation learning process (feature learning methods that differs from those used in supervised learning) could be a route for achieving better performance in offline RL.

Implications for Empirical Practices and Benchmarks.

Our empirical findings suggests a closer inspection of certain empirical practices used in the evaluation of offline RL algorithms.

Offline Data Collection. Many empirical settings create an offline dataset under a distribution which contains a large fraction from the target policy itself (e.g. creating the dataset using an online RL algorithm). This may substantially limit the methodology to only testing algorithms in a low distribution shift regime; our results suggests this may not be reflective of what would occur with more realistic and diverse datasets.

Hyperparameter Tuning in Offline RL. A number of methodologies tune hyperparameters using interactive access to the environment, a practice that is clearly not possible with the given offline dataset (e.g. see (Paine et al., 2020) for further discussion). The instability of hyperparameter tuning, as observed in our experiments, suggests that hyperparameter tuning in offline RL may be a substantial hurdle.

Finally, we should remark that the broader motivation of our results (and this discussion) is to help with advancing the field of offline RL through better linking our theoretical understanding with the empirical practices. It is also worth noting that there are notable empirical successes in more realistic settings, e.g. (Mandel et al., 2014; Chang et al., 2020).

Acknowledgements

The authors would like to thank Alekh Agarwal, Akshay Krishnamurthy, Aditya Kusupati, and Nan Jiang for helpful discussions. Sham M. Kakade acknowledges funding from the ONR award N00014-18-1-2247. Ruosong Wang and Ruslan Salakhutdinov are supported in part by NSF IIS1763562, AFRL CogDeCON FA875018C0014, and DARPA SAGAMORE HR00111990016. Part of this work was done while Ruosong Wang was visiting the Simons Institute for the Theory of Computing.

References

Appendix A Omitted Proofs

A.2 Proof of Lemma 4.2

Therefore, for any $(s,a)\in\mathcal{S}\times\mathcal{A}$,

since $\|\phi(s,a)\|_{2}\leq 1$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.

By Cauchy–Schwarz inequality, this implies

Moreover, by Equation (1) and Hölder’s inequality

By union bound and the fact that the operator norm of a matrix is upper bounded its Frobenius norm, with probability $1-\delta/2$, we have

Since $\lambda\leq\sigma_{\min}^{3}(\Lambda)/(20T)$,

Now we use Lemma A.1 and Lemma A.2 to prove the following lemma.

As a result, for each $i\in\{0,1,2,\ldots,t\}$, there are $\binom{t}{i}$ terms in

By taking $N\geq C_{1}T^{2}d^{2}\log(d/\delta)/\sigma_{\min}^{6}(\Lambda)$ and $N\geq C_{2}T^{4}d\log(1/\delta)/(\varepsilon^{2}\sigma_{\min}(\Lambda)(1-\gamma)^{2})$ for some constants $C_{1}>0$ and $C_{2}>0$, with probability $1-\delta/2$,

According to the argument in the proof of Lemma A.2, with probability $1-\delta/4$, $\|\hat{\Lambda}^{-1}\|_{2}\leq 2/\sigma_{\min}(\Lambda)$. Clearly,

According to [Hsu et al., 2012], with probability $1-\delta/4$, there exists a constant $C_{3}>0$ such that

Therefore, conditioned on the two events defined above,

Moreover, conditioned on the event above, since $\|\theta^{*}\|_{2}\leq\sqrt{d}/(1-\gamma)$ and $\lambda\leq\varepsilon(1-\gamma)\sigma_{\min}(\Lambda)/(8T^{2}\sqrt{d})$, we also have

We finish the proof by applying the triangle inequality. ∎

According to Lemma 4.1, we only need to prove that for any $(s,a)\in\mathcal{S}\times\mathcal{A}$,

Conditioned on the events in Lemma A.2 and Lemma A.4, by Lemma A.3 and Lemma A.4, for any $(s,a)\in\mathcal{S}\times\mathcal{A}$,

Moreover, by taking $T=C_{T}\log(d/(\varepsilon(1-\gamma)))/(1-\gamma)$ for some constant $C_{T}>0$, for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

Therefore, for any $(s,a)\in\mathcal{S}\times\mathcal{A}$,

A.3 Proof of Lemma 4.3

By standard matrix concentration inequalities [Tropp, 2015], we can show that $\Phi^{\top}\Phi/N$ (and $\overline{\Phi}^{\top}\overline{\Phi}/N$) concentrates around $\Lambda$ (and $\overline{\Lambda}$).

With probability $1-\delta/2$, for some constant $C_{4}>0$, we have

Conditioned on the event above, since $\lambda=C_{\lambda}T\sqrt{d\log(d/\delta)/N}/\lambda$, we have

Now we are ready to prove Lemma 4.3. By Lemma 4.1, we have

Conditioned on the event in Lemma A.5, we have $\hat{\Lambda}\succeq\Lambda$ and $N\hat{\Lambda}\succeq\Phi^{\top}\Phi$. This implies

since $\lambda=C_{\lambda}T\sqrt{d\log(d/\delta)/N}/\lambda$ for sufficiently large constant $C_{\lambda}$. Therefore,

According to [Hsu et al., 2012], with probability $1-\delta/2$, there exists a constant $C_{5}>0$ such that

Hence, there exists a constant $C_{6}>0$, such that for each $t\in\{1,2,\ldots,T\}$,

Similarly, for each $t\in\{1,2,\ldots,T\}$,

Appendix B Additional Experiment Details

In this section, we provide more details about our experiments.

In this section, we provide details of the first step of our experiments (i.e., the step for deciding on a target policy to be evaluated, along with a good feature mapping for this policy).

When running DQN and TD3, the number of hidden layers is always set to be $3$. The activation function is always set to be leaky ReLU with slop $0.1$, i.e.,

When running DQN and TD3, there is no bias term in the output layer.

For TD3, we use the official implementation released by the authors [Fujimoto et al., 2018]https://github.com/sfujim/TD3. Except for hyperparameters explicitly mentioned above, we use the default hyperparameters in the implementation released by the authors. For DQN, we write our own implementation (using the PyTorch package), and the choices of hyperparameters are reported in Table 4.

We also report the learning curves of both algorithm in Figure 7.

When running DQN on MountainCar-v0, we slightly modify the reward function to facilitate exploration. It is known that without exploration bonus, exploration in MountainCar-v0 is a hard problem (see e.g. [Houthooft et al., 2016]), and using exploration bonus potentially leads to a representation that is incompatible with the original problem. To mitigate the issue of exploration, we slightly modify the reward function. Suppose the current position of the car is $x$. In the original problem, the reward is set to be $-1$ if $x<0.5$, and is set to be if $x\geq 0.5$. In our case, we set the reward to be $\max\{-1,x-0.5\}$. Using such a modified reward function, the reward values are still in $$, while being smoother (with respect to the current position of the car) and therefore facilitates exploration. All of our experiments are performed on this modified version of MountainCar-v0.

Details of Random Fourier Features.

B.2 Details in Step 2

B.3 Details in Step 3

Here we give a description of the LSTD algorithm (proposed in [Bradtke and Barto, 1996]) in Algorithm 2.

Evaluating Offline RL Methods.

Recall that when evaluating the performance of offline RL methods, we report the square root of the mean squared evaluation error, taking average over $100$ randomly chosen states. In order to have a diverse set of states with a wide range of values when evaluating the performance, we sample $100$ trajectories using the target policy, and randomly choose a state from the first $100$ time steps on each sampled trajectory. We also report the values ($V^{\pi}(s)$) of those randomly chosen states in Table 6 for all the six environments. When evaluating the performance of FQI, we report the evaluation error after every $10$ rounds of FQI.

Variance of Step 3.

Here we stress that the offline RL step (Step 3) itself could also have high variance. Here we plot the performance of FQI on Ant-v2, HalfCheetah-v2, Hopper-v2 and Walker2d-v2 when using a fixed policy and a fixed representation. Here we repeat the setting in Figure 6, but use a random $10\%$ subset of the original dataset and repeat for $5$ times. Therefore, in this setting, there is no randomness coming from the choice of the target policy or the representation, and instead all randomness comes from the offline methods themselves. The results are reported in Figure 8. Here, even if the policy and the representation are fixed, the variance of the estimation could still be high. Moreover, adding more data into the dataset generally results in higher variance. Note that this is consistent with our theory in Lemma 4.1, which shows that the variance can also be exponentially amplified without strong representation conditions and low distribution shift conditions.

Appendix C Additional Experiment Results

In Figure 10, we present the full version of Figure 6, where we plot of the performance of FQI with features from pre-trained neural networks and datasets induced by random policies, on all the six environments.

Full Version of Figure 6.

In Figure 10, we present the full version of Figure 6, where we plot of the performance of FQI with features from pre-trained neural networks and datasets induced by lower performing policies, on all the six environments.

Full Version of Figure 6.

In Figure 13, we present the full version of Figure 6, where we plot of the performance of FQI with random Fourier features and datasets induced by random policies, on all the six environments.

Full Version of Figure 6.

In Figure 13 to Figure 17, we present the full version of Figure 6, where we plot of the performance of FQI with features from pre-trained neural networks, datasets induced by random policies, and different regularization parameter $\lambda$, on all the six environments. Here we vary the number of additional samples from random trajectories and the regularization parameter $\lambda$.

Full Version of Table 1

In Table 8, we present the full version of Table 1, where we provide the performance of LSTD with features from pre-trained neural networks and distributions induced by random policies, on all the six environments.