Year: 2020

Abstract:
We study worst-case guarantees on the expected return of fixed-dataset policy optimization algorithms. Our core contribution is a unified conceptual and mathematical framework for the study of algorithms in this regime. This analysis reveals that for naı̈ve approaches, the possibility of erroneous value overestimation leads to a difficult-to-satisfy requirement: in order to guarantee that we select a policy which is near-optimal, we may need the dataset to be informative of the value of every policy. To avoid this, algorithms can follow the pessimism principle, which states that we should choose the policy which acts optimally in the worst possible world. We show why pessimistic algorithms can achieve good performance even when the dataset is not informative of every policy, and derive families of algorithms which follow this principle. These theoretical findings are validated by experiments on a tabular gridworld, and deep learning experiments on four MinAtar environments.

text: We study worst-case guarantees on the expected return of fixed-dataset policy optimization algorithms. Our core contribution is a unified conceptual and mathematical framework for the study of algorithms in this regime. This analysis reveals that for naı̈ve approaches, the possibility of erroneous value overestimation leads to a difficult-to-satisfy requirement: in order to guarantee that we select a policy which is near-optimal, we may need the dataset to be informative of the value of every policy. To avoid this, algorithms can follow the pessimism principle, which states that we should choose the policy which acts optimally in the worst possible world. We show why pessimistic algorithms can achieve good performance even when the dataset is not informative of every policy, and derive families of algorithms which follow this principle. These theoretical findings are validated by experiments on a tabular gridworld, and deep learning experiments on four MinAtar environments.

heading: 1 INTRODUCTION
text: We consider fixed-dataset policy optimization (FDPO), in which a dataset of transitions from an environment is used to find a policy with high return.1 We compare FDPO algorithms by their worst-case performance, expressed as high-probability guarantees on the suboptimality of the learned policy. It is perhaps obvious that in order to maximize worst-case performance, a good FDPO algorithm should select a policy with high worst-case value. We call this the pessimism principle of exploitation, as it is analogous to the widely-known optimism principle (Lattimore & Szepesvári, 2020) of exploration.2
Our main contribution is a theoretical justification of the pessimism principle in FDPO, based on a bound that characterizes the suboptimality incurred by an FDPO algorithm. We further demonstrate how this bound may be used to derive principled algorithms. Note that the core novelty of our work is not the idea of pessimism, which is an intuitive concept that appears in a variety of contexts; rather, our contribution is a set of theoretical results rigorously explaining how pessimism is important in the specific setting of FDPO. An example conveying the intuition behind our results can be found in Appendix G.1.
We first analyze a family of non-pessimistic naı̈ve FDPO algorithms, which estimate the environment from the dataset via maximum likelihood and then apply standard dynamic programming techniques. We prove a bound which shows that the worst-case suboptimality of these algorithms is guaranteed to be small when the dataset contains enough data that we are certain about the value of every possible policy. This is caused by the outsized impact of value overestimation errors on suboptimality, sometimes called the optimizer’s curse (Smith & Winkler, 2006). It is a fundamental consequence of ignoring the disconnect between the true environment and the picture painted by our limited observations. Importantly, it is not reliant on errors introduced by function approximation.
1We use the term fixed-dataset policy optimization to emphasize the computational procedure; this setting has also been referred to as batch RL (Ernst et al., 2005; Lange et al., 2012) and more recently, offline RL (Levine et al., 2020). We emphasize that this is a well-studied setting, and we are simply choosing to refer to it by a more descriptive name.
2The optimism principle states that we should select a policy with high best-case value.
We contrast these findings with an analysis of pessimistic FDPO algorithms, which select a policy that maximizes some notion of worst-case expected return. We show that these algorithms do not require datasets which inform us about the value of every policy to achieve small suboptimality, due to the critical role that pessimism plays in preventing overestimation. Our analysis naturally leads to two families of principled pessimistic FDPO algorithms. We prove their improved suboptimality guarantees, and confirm our claims with experiments on a gridworld.
Finally, we extend one of our pessimistic algorithms to the deep learning setting. Recently, several deep-learning-based algorithms for fixed-dataset policy optimization have been proposed (Agarwal et al., 2019; Fujimoto et al., 2019; Kumar et al., 2019; Laroche et al., 2019; Jaques et al., 2019; Kidambi et al., 2020; Yu et al., 2020; Wu et al., 2019; Wang et al., 2020; Kumar et al., 2020; Liu et al., 2020). Our work is complementary to these results, as our contributions are conceptual, rather than algorithmic. Our primary goal is to theoretically unify existing approaches and motivate the design of pessimistic algorithms more broadly. Using experiments in the MinAtar game suite (Young & Tian, 2019), we provide empirical validation for the predictions of our analysis.
The problem of fixed-dataset policy optimization is closely related to the problem of reinforcement learning, and as such, there is a large body of work which contains ideas related to those discussed in this paper. We discuss these works in detail in Appendix E.

heading: 2 BACKGROUND
text: We anticipate most readers will be familiar with the concepts and notation, which is fairly standard in the reinforcement learning literature. In the interest of space, we relegate a full presentation to Appendix A. Here, we briefly give an informal overview of the background necessary to understand the main results.
We represent the environment as a Markov Decision Process (MDP), denoted M := 〈S,A,R, P, γ, ρ〉. We assume without loss of generality that R(〈s, a〉) ∈ [0, 1], and denote its expectation as r(〈s, a〉). ρ represents the start-state distribution. Policies π can act in the environment, represented by action matrix Aπ , which maps each state to the probability of each state-action when following π. Value functions v assign some real value to each state. We use vπM to denote the value function which assigns the sum of discounted rewards in the environment when following policy π. A dataset D contains transitions sampled from the environment. From a dataset, we can compute the empirical reward and transition functions, rD and PD, and the empirical policy, π̂D.
An important concept for our analysis is the value uncertainty function, denoted µπD,δ , which returns a high-probability upper-bound to the error of a value function derived from datasetD. Certain value uncertainty functions are decomposable by states or state-actions, meaning they can be written as the weighted sum of more local uncertainties. See Appendix B for more detail.
Our goal is to analyze the suboptimality of a specific class of FDPO algorithms, called value-based FDPO algorithms, which have a straightforward structure: they use a fixed-dataset policy evaluation (FDPE) algorithm to assign a value to each policy, and then select the policy with the maximum value. Furthermore, we consider FDPE algorithms whose solutions satisfy a fixed-point equation. Thus, a fixed-point equation defines a FDPE objective, which in turn defines a value-based FDPO objective; we call the set of all algorithms that implement these objectives the family of algorithms defined by the fixed-point equation.

heading: 3 OVER/UNDER DECOMPOSITION OF SUBOPTIMALITY
text: Our first theoretical contribution is a simple but informative bound on the suboptimality of any value-based FDPO algorithm. Next, in Section 4, we make this concrete by defining the family of naı̈ve algorithms and invoking this bound. This bound is insightful because it distinguishes the impact of errors of value overestimation from errors of value underestimation, defined as: Definition 1. Consider any fixed-dataset policy evaluation algorithm E on any dataset D and any policy π. Denote vπD := E(D,π). We define the underestimation error as Eρ[vπM − vπD] and overestimation error as Eρ[vπD − vπM].
The following lemma shows how these quantities can be used to bound suboptimality.
Lemma 1 (Value-based FDPO suboptimality bound). Consider any value-based fixed-dataset policy optimization algorithmOVB, with fixed-dataset policy evaluation subroutine E . For any policy π and dataset D, denote vπD := E(D,π). The suboptimality of OVB is bounded by
SUBOPT(OVB(D)) ≤ inf π
( Eρ[v π∗M M − v π M] + Eρ[vπM − vπD] ) + sup
π
( Eρ[vπD − vπM] ) Proof. See Appendix C.1.
This bound is tight; see Appendix C.2. The bound highlights the potentially outsized impact of overestimation on the suboptimality of a FDPO algorithm. To see this, we consider each of its terms in isolation:
SUBOPT(OVB(D)) ≤ inf π
( (A1)︷ ︸︸ ︷ Eρ[v π∗M M − v π M] + (A2)︷ ︸︸ ︷ Eρ[vπM − vπD] ) ︸ ︷︷ ︸
(A)
+ sup π
( (B1)︷ ︸︸ ︷ Eρ[vπD − vπM] ) ︸ ︷︷ ︸
(B)
The term labeled (A) reflects the degree to which the dataset informs us of a near-optimal policy. For any policy π, (A1) captures the suboptimality of that policy, and (A2) captures its underestimation error. Since (A) takes an infimum, this term will be small whenever there is at least one reasonable policy whose value is not very underestimated.
On the other hand, the term labeled (B) corresponds to the largest overestimation error on any policy. Because it consists of a supremum over all policies, it will be small only when no policies are overestimated at all. Even a single overestimation can lead to significant suboptimality.
We see from these two terms that errors of overestimation and underestimation have differing impacts on suboptimality, suggesting that algorithms should be designed with this asymmetry in mind. We will see in Section 5 how this may be done. But first, let us further understand why this is necessary by studying in more depth a family of algorithms which treats its errors of overestimation and underestimation equivalently.

heading: 4 NAÏVE ALGORITHMS
text: The goal of this section is to paint a high-level picture of the worst-case suboptimality guarantees of a specific family of non-pessimistic approaches, which we call naı̈ve FDPO algorithms. Informally, the naı̈ve approach is to take the limited dataset of observations at face value, treating it as though it paints a fully accurate picture of the environment. Naı̈ve algorithms construct a maximum-likelihood MDP from the dataset, then use standard dynamic programming approaches on this empirical MDP. Definition 2. A naı̈ve algorithm is any algorithm in the family defined by the fixed-point function
fnaı̈ve(v π) := Aπ(rD + γPDv π).
Various FDPE and FDPO algorithms from this family could be described; in this work, we do not study these implementations in detail, although we do give pseudocode for some implementations in Appendix D.1.
One example of a naı̈ve FDPO algorithm which can be found in the literature is certainty equivalence (Jiang, 2019a). The core ideas behind naı̈ve algorithms can also be found in the function approximation literature, for example in FQI (Ernst et al., 2005; Jiang, 2019b). Additionally, when available data is held fixed, nearly all existing deep reinforcement learning algorithms are transformed into naı̈ve value-based FDPO algorithms. For example, DQN (Mnih et al., 2015) with a fixed replay buffer is a naı̈ve value-based FDPO algorithm. Theorem 1 (Naı̈ve FDPO suboptimality bound). Consider any naı̈ve value-based fixed-dataset policy optimization algorithm OVBnaı̈ve. Let µ be any value uncertainty function. With probability at least 1− δ, the suboptimality of OVBnaı̈ve is bounded with probability at least 1− δ by
SUBOPT(OVBnaı̈ve(D)) ≤ inf π
( Eρ[v π∗M M − v π M] + Eρ[µπD,δ] ) + sup
π Eρ[µπD,δ]
Proof. This result follows directly from Lemma 1 and Lemma 3.
The infimum term is small whenever there is some reasonably good policy with low value uncertainty. In practice, this condition can typically be satisfied, for example by including expert demonstrations in the dataset. On the other hand, the supremum term will only be small if we have low value uncertainty for all policies – a much more challenging requirement. This explains the behavior of pathological examples, e.g. in Appendix G.1, where performance is poor despite access to virtually unlimited amounts of data from a near-optimal policy. Such a dataset ensures that the first term will be small by reducing value uncertainty of the near-optimal data collection policy, but does little to reduce the value uncertainty of any other policy, leading the second term to be large.
However, although pathological examples exist, it is clear that this bound will not be tight on all environments. It is reasonable to ask: is it likely that this bound will be tight on real-world examples? We argue that it likely will be. We identify two properties that most real-world tasks share: (1) The set of policies is pyramidal: there are an enormous number of bad policies, many mediocre policies, a few good policies, etc. (2) Due to the size of the state space and cost of data collection, most policies have high value uncertainty.
Given that these assumptions hold, naı̈ve algorithms will perform as poorly on most real-world environments as they do on pathological examples. Consider: there are many more policies than there is data, so there will be many policies with high value uncertainty; naı̈ve algorithms will likely overestimate several of these policies, and erroneously select one; since good policies are rare, the selected policy will likely be bad. It follows that running naı̈ve algorithms on real-world problems will typically yield suboptimality close to our worst-case bound. And, indeed, on deep RL benchmarks, which are selected due to their similarity to real-world settings, overestimation has been widely observed, typically correlated with poor performance (Bellemare et al., 2016; Van Hasselt et al., 2016; Fujimoto et al., 2019).

heading: 5 THE PESSIMISM PRINCIPLE
text: “Behave as though the world was plausibly worse than you observed it to be.” The pessimism principle tells us how to exploit our current knowledge to find the stationary policy with the best worstcase guarantee on expected return. We consider two specific families of pessimistic algorithms, the uncertainty-aware pessimistic algorithms and proximal pessimistic algorithms, and bound the worst-case suboptimality of each. These algorithms each include a hyperparameter, α, controlling the amount of pessimism, interpolating from fully-naı̈ve to fully-pessimistic. (For a discussion of the implications of the latter extreme, see Appendix G.2.) Then, we will compare the two families, and see how the proximal family is simply a trivial special case of the more general uncertainty-aware family of methods.

heading: 5.1 UNCERTAINTY-AWARE PESSIMISTIC ALGORITHMS
text: Our first family of pessimistic algorithms is the uncertainty-aware (UA) pessimistic algorithms. As the name suggests, this family of algorithms estimates the state-wise Bellman uncertainty and penalizes policies accordingly, leading to a pessimistic value estimate and a preference for policies with low value uncertainty. Definition 3. An uncertainty-aware pessimistic algorithm, with a Bellman uncertainty function uπD,δ and pessimism hyperparameter α ∈ [0, 1], is any algorithm in the family defined by the fixed-point function
fua(v π) = Aπ(rD + γPDv π)− αuπD,δ This fixed-point function is simply the naı̈ve fixed-point function penalized by the Bellman uncertainty. This can be interpreted as being pessimistic about the outcome of every action. Note that it remains to specify a technique to compute the Bellman uncertainty function, e.g. Appendix B.1, in order to get a concrete algorithm. It is straightforward to construct algorithms from this family by modifying naı̈ve algorithms to subtract the penalty term. Similar algorithms have been explored in the safe RL literature (Ghavamzadeh et al., 2016; Laroche et al., 2019) and the robust MDP literature (Givan et al., 1997), where algorithms with high-probability performance guarantees are useful in the context of ensuring safety.
Theorem 2 (Uncertainty-aware pessimistic FDPO suboptimality bound). Consider an uncertaintyaware pessimistic value-based fixed-dataset policy optimization algorithm OVBua . Let uπD,δ be any Bellman uncertainty function, µπD,δ be a corresponding value uncertainty function, and α ∈ [0, 1] be any pessimism hyperparameter. The suboptimality of OVBua is bounded with probability at least 1− δ by
SUBOPT(OVBua (D)) ≤ inf π
( Eρ[v π∗M M − v π M] + (1 + α) · Eρ[µπD,δ] ) + (1− α) · ( sup π Eρ[µπD,δ] )
Proof. See Appendix C.7.
This bound should be contrasted with our result from Theorem 1. With α = 0, the family of pessimistic algorithms reduces to the family of naı̈ve algorithms, so the bound is correspondingly identical. We can add pessimism by increasing α, and this corresponds to a decrease in the magnitude of the supremum term. When α = 1, there is no supremum term at all. In general, the optimal value of α lies between the two extremes.
To further understand the power of this approach, it is illustrative to compare it to imitation learning. Consider the case where the dataset contains a small number of expert trajectories but also a large number of interactions from a random policy, i.e. when learning from suboptimal demonstrations (Brown et al., 2019). If the dataset contained only a small amount of expert data, then both an UA pessimistic FDPO algorithm and an imitation learning algorithm would return a high-value policy. However, the injection of sufficiently many random interactions would degrade the performance of imitation learning algorithms, whereas UA pessimistic algorithms would continue to behave similarly to the expert data.

heading: 5.2 PROXIMAL PESSIMISTIC ALGORITHMS
text: The next family of algorithms we study are the proximal pessimistic algorithms, which implement pessimism by penalizing policies that deviate from the empirical policy. The name proximal was chosen to reflect the idea that these algorithms prefer policies which stay “nearby” to the empirical policy. Many FDPO algorithms in the literature, and in particular several recently-proposed deep learning algorithms (Fujimoto et al., 2019; Kumar et al., 2019; Laroche et al., 2019; Jaques et al., 2019; Wu et al., 2019; Liu et al., 2020), resemble members of the family of proximal pessimistic algorithms; see Appendix E. Also, another variant of the proximal pessimistic family, which uses state density instead of state-conditional action density, can be found in Appendix C.9.
Definition 4. A proximal pessimistic algorithm with pessimism hyperparameter α ∈ [0, 1] is any algorithm in the family defined by the fixed-point function
fproximal(v π) = Aπ(rD + γPDv π)− α (
TVS(π, π̂D) (1− γ)2 ) Theorem 3 (Proximal pessimistic FDPO suboptimality bound). Consider any proximal pessimistic value-based fixed-dataset policy optimization algorithm OVBproximal. Let µ be any state-action-wise decomposable value uncertainty function, and α ∈ [0, 1] be a pessimism hyperparameter. For any dataset D, the suboptimality of OVBproximal is bounded with probability at least 1− δ by
SUBOPT(Oproximal(D)) ≤ inf π
( Eρ[v π∗M M − v π M] + Eρ [ µπD,δ + α(I − γAπPD)−1 ( TVS(π, π̂D)
(1− γ)2 )]) + sup
π
( Eρ [ µπD,δ − α(I − γAπPD)−1 ( TVS(π, π̂D)
(1− γ)2 )]) Proof. See Appendix C.8.
Once again, we see that as α grows, the large supremum term shrinks; similarly, by Lemma 5, when we have α = 1, the supremum term is guaranteed to be non-positive.3 The primary limitation of
3Initially, it will contain µπ ′
D,δ , but this can be removed since it is not dependent on π.
the proximal approach is the looseness of the value lower-bound. Intuitively, this algorithm can be understood as performing imitation learning, but permitting minor deviations. Constraining the policy to be near in distribution to the empirical policy can fail to take advantage of highly-visited states which are reached via many trajectories. In fact, in contrast to both the naı̈ve approach and the UA pessimistic approach, in the limit of infinite data this approach is not guaranteed to converge to the optimal policy. Also, note that when α ≥ 1− γ, this algorithm is identical to imitation learning.

heading: 5.3 THE RELATIONSHIP BETWEEN UNCERTAINTY-AWARE AND PROXIMAL ALGORITHMS
text: Though these two families may appear on the surface to be quite different, they are in fact closely related. A key insight of our theoretical work is that it reveals the important connection between these two approaches. Concretely: proximal algorithms are uncertainty-aware algorithms which use a trivial value uncertainty function.
To see this, we show how to convert an uncertainty-aware penalty into a proximal penalty. let µ be any state-action-wise decomposable value uncertainty function. For any dataset D, we have
µπD,δ = µ π̂D D,δ + (I − γA πPD) −1 ( (Aπ −Aπ̂D )(uD,δ + γPDµπ̂DD,δ) )
(Lemma 4)
≤ µπ̂DD,δ + (I − γA πPD)
−1 ( TVS(π, π′) (
1
(1− γ)2
)) . (Lemma 5)
We began with the uncertainty penalty. In the first step, we rewrote the uncertainty for π into the sum of two terms: the uncertainty for π̂D, and the difference in uncertainty between π and π̂D on various actions. In the second step, we chose our state-action-wise Bellman uncertainty to be 11−γ , which is a trivial upper bound; we also upper-bound the signed policy difference with the total variation. This results in the proximal penalty.4
Thus, we see that proximal penalties are equivalent to uncertainty-aware penalties which use a specific, trivial uncertainty function. This result suggests that uncertainty-aware algorithms are strictly better than their proximal counterparts. There is no looseness in this result: for any proximal penalty, we will always be able to find a tighter uncertainty-aware penalty by replacing the trivial uncertainty function with something tighter.
However, currently, proximal algorithms are quite useful in the context of deep learning. This is because the only uncertainty function that can currently be implemented for neural networks is the trivial uncertainty function. Until we discover how to compute uncertainties for neural networks, proximal pessimistic algorithms will remain the only theoretically-motivated family of algorithms.

heading: 6 EXPERIMENTS
text: We implement algorithms from each family to empirically investigate whether their performance of follows the predictions of our bounds. Below, we summarize the key predictions of our theory.
• Imitation. This algorithm simply learns to copy the empirical policy. It performs well if and only if the data collection policy performs well.
• Naı̈ve. This algorithm performs well only when almost no policies have high value uncertainty. This means that when the data is collected from any mostly-deterministic policy, performance of this algorithm will be poor, since many states will be missing data. Stochastic data collection improves performance. As the size of the dataset grows, this algorithm approaches optimality.
• Uncertainty-aware. This algorithm performs well when there is data on states visited by near-optimal policies. This is the case when a small amount of data has been collected from a near-optimal policy, or a large amount of data has been collected from a worse policy. As the size of the dataset grows, this algorithm to approaches optimality. This approach outperforms all other approaches.
4When constructing the penalty, we can ignore the first term, which does not contain π, and so is irrelevant to optimization.
• Proximal. This algorithm roughly mirrors the performance of the imitation approach, but improves upon it. As the size of the dataset grows, this algorithm does not approach optimality, as the penalty persists even when the environment’s dynamics are perfectly captured by the dataset.
Our experimental results qualitatively align with our predictions in both the tabular and deep learning settings, giving evidence that the picture painted by our theoretical analysis truly describes the FDPO setting. See Appendix D for pseudocode of all algorithms; see Appendix F for details on the experimental setup; see Appendix G.3 for additional experimental considerations for deep learning experiments that will be of interest to practicioners. For an open-source implementation, including full details suitable for replication, please refer to the code in the accompanying GitHub repository: github.com/anonymized
Tabular. The first tabular experiment, whose results are shown in Figure 1(a), compares the performance of the algorithms as the policy used to collect the dataset is interpolated from the uniform random policy to an optimal policy using -greedy. The second experiment, whose results are shown in Figure 1(b), compares the performance of the algorithms as we increase the size of the dataset from 1 sample to 200000 samples. In both experiments, we notice a qualitative difference between the trends of the various algorithms, which aligns with the predictions of our theory.
Neural network. The results of these experiments can be seen in Figure 2. Similarly to the tabular experiments, we see that the naı̈ve approach performs well when data is fully exploratory, and poorly when data is collected via an optimal policy; the pure imitation approach performs better when the data collection policy is closer to optimal. The pessimistic approach achieves the best of both worlds: it correctly imitates a near-optimal policy, but also learns to improve upon it somewhat when the data is more exploratory. One notable failure case is in FREEWAY, where the performance of the pessimistic approach barely improves upon the imitation policy, despite the naı̈ve approach performing near-optimally for intermediate values of .

heading: 7 DISCUSSION AND CONCLUSION
text: In this work, we provided a conceptual and mathematical framework for thinking about fixed-dataset policy optimization. Starting from intuitive building blocks of uncertainty and the over-under decomposition, we showed the core issue with naı̈ve approaches, and introduced the pessimism principle as the defining characteristic of solutions. We described two families of pessimistic algorithms, uncertainty-aware and proximal. We see theoretically that both of these approaches have advantages over the naı̈ve approach, and observed these advantages empirically. Comparing these two families of pessimistic algorithms, we see both theoretically and empirically that uncertainty-aware
algorithms are strictly better than proximal algorithms, and that proximal algorithms may not yield the optimal policy, even with infinite data.
Future directions. Our results indicate that research in FDPO should not focus on proximal algorithms. The development of neural uncertainty estimation techniques will enable principled uncertainty-aware deep learning algorithms. As is evidenced by our tabular results, we expect these approaches to yield dramatic performance improvements, rendering algorithms derived from the proximal family (Kumar et al., 2019; Fujimoto et al., 2019; Laroche et al., 2019; Kumar et al., 2020) obsolete.
On ad-hoc solutions. It is undoubtably disappointing to see that proximal algorithms, which are far easier to implement, are fundamentally limited in this way. It is tempting to propose various adhoc solutions to mitigate the flaws of proximal pessimistic algorithms in practice. However, in order to ensure that the resulting algorithm is principled, one must be careful. For example, one might consider tuning α; however, doing the tuning requires evaluating each policy in the environment, which involves gaining information by interacting with the environment, which is not permitted by the problem setting. Or, one might consider e.g. an adaptive pessimism hyperparameter which decays with the size of the dataset; however, in order for such a penalty to be principled, it must be based on an uncertainty function, at which point we may as well just use an uncertainty-aware algorithm.
Stochastic policies. One surprising property of pessimsitic algorithms is that the optimal policy is often stochastic. This is because the penalty term included in their fixed-point objective is often minimized by stochastic policies. For the penalty of proximal pessimistic algorithms, it is easy to see that this will be the case for any non-deterministic empirical policy; for UA pessimsitic algorithms, it is dependent on the choice of Bellman uncertainty function, but often still holds (see Appendix B.2 for the derivation of a Bellman uncertainty function with this property). This observation lends mathematical rigor to the intuition that agents should ‘hedge their bets’ in the face of epistemic uncertainty. This property also means that the simple approach of selecting the argmax action is no longer adequate for policy improvement. In Appendix D.2.2 we discuss a policy improvement procedure that takes into account the proximal penalty to find the stochastic optimal policy.
Implications for RL. Finally, due to the close connection between the FDPO and RL settings, this work has implications for deep reinforcement learning. Many popular deep RL algorithms utilize a replay buffer to break the correlation between samples in each minibatch (Mnih et al., 2015). However, since these algorithms typically alternate between collecting data and training the network, the replay buffer can also be viewed as a ‘temporarily fixed’ dataset during the training phase. These algorithms are often very sensitive to hyperparemters; in particular, they perform poorly when the number of learning steps per interaction is large (Fedus et al., 2020). This effect can be explained by our analysis: additional steps of learning cause the policy to approach its naı̈ve FDPO fixed-point, which has poor worst-case suboptimality. A pessimistic algorithm with a better fixed-point could therefore allow us to train more per interaction, improving sample efficiency. A potential direction of future work is therefore to incorporate pessimism into deep RL.

heading: A BACKGROUND
text: We write vectors using bold lower-case letters, a, and matrices using upper-case letters, A. To refer to individual cells of a vector or rows of a matrix, we use function notation, a(x). We write the identity matrix as I . We use the notation Ep[·] to denote the average value of a function under a distribution p, i.e. for any space X , distribution p ∈ Dist(X ), and function a : X → R, we have Ep[a] := Ex∼p[a(x)].
When applied to vectors or matrices, we use <,>,≤,≥ to denote element-wise comparison. Similarly, we use | · | to denote the element-wise absolute value of a vector: |a|(x) = |a(x)|. We use |a|+ to denote the element-wise maximum of a and the zero vector. To denote the total variation distance between two probability distributions, we use TV(p,q) = 12 |p−q|1. When P andQ are conditional probability distributions, we adopt the convention TVX (p,q) = 〈 12 |p(·|x)−q(·|x)|1 : x ∈ X〉, i.e., the vector of total variation distances conditioned on each x ∈ X .
Markov Decision Processes. We represent the environment with which we are interacting as a Markov Decision Process (MDP), defined in standard fashion: M := 〈S,A,R, P, γ, ρ〉. S and A denote the state and action space, which we assume are discrete. We useZ := S×A as the shorthand for the joint state-action space. The reward functionR : Z → Dist([0, 1]) maps state-action pairs to distributions over the unit interval, while the transition function P : Z → Dist(S) maps state-action pairs to distributions over next states. Finally, ρ ∈ Dist(S) is the distribution over initial states. We use r to denote the expected reward function, r(〈s, a〉) := Er∼R(·|〈s,a〉)[r], which can also be interpreted as a vector r ∈ R|Z|. Similarly, note that P can be described as P : (Z×S)→ R, which can be represented as a stochastic matrix P ∈ R|Z|×|S|. In order to emphasize that these reward and transition functions correspond to the true environment, we sometimes equivalently denote them as rM, PM. To denote the vectors of a constant whose sizes are the state and state-action space, we use a single dot to mean state and two dots to mean state-action, e.g., 1̇ ∈ R|S| and 1̈ ∈ R|Z|. A policy π : S → Dist(A) defines a distribution over actions, conditioned on a state. We denote the space of all possible policies as Π. We define an “activity matrix” for each policy, Aπ ∈ RS×Z , which encodes the state-conditional state-action distribution of π, by letting Aπ(s, 〈ṡ, a〉) := π(a|s) if s = ṡ, otherwise Aπ(s, 〈ṡ, a〉) := 0. Acting in the MDP according to π can thus be represented by AπP ∈ R|S|×|S| or PAπ ∈ R|Z|×|Z|. We define a value function as any v : Π → S → R or q : Π → Z → R whose output is bounded by [0, 11−γ ]. Note that this is a slight generalization of the standard definition (Sutton & Barto, 2018) since it accepts a policy as an input. We use the shorthand vπ := v(π) and qπ := q(π) to denote the result of applying a value function to a specific policy, which can also be represented as a vector, vπ ∈ R|S| and qπ ∈ R|Z|. To denote the output of an arbitrary value function on an arbitrary policy, we use unadorned v and q. The expected return of an MDPM, denoted vM or qM, is the discounted sum of rewards acquired when interacting with the environment:
vM(π) := ∞∑ t=0 (γAπP ) t Aπr qM(π) := ∞∑ t=0 (γPAπ) t r
Note that vπM = A πqπM. An optimal policy of an MDP, which we denote π ∗ M, is a policy for which the expected return vM is maximized under the initial state distribution: π∗M := arg maxπ Eρ[vπM]. The statewise expected returns of an optimal policy can be written as vπ ∗ M M . Of particular interest are value functions whose outputs obey fixed-point relationships, vπ = f(vπ) for some f : (S → R) → (S → R). The Bellman consistency equation for a policy π, BπM(x) := Aπ(r + γPx), which uniquely identifies the vector of expected returns for π, since vπM is the only vector for which vπM = BπM(vπM) holds. Finally, for any state s, the probability of being in the state s′ after t time steps when following policy π is [(AπP )t](s, s′). Furthermore, ∑∞ t=0 (γA πP ) t
= (I − γAπP )−1. We refer to (I − γAπP )−1 as the discounted visitation of π.
Datasets. We next introduce basic concepts that are helpful for framing the problem of fixeddataset policy optimization. We define a dataset of d transitions D := {〈s, a, r, s′〉}d, and denote the space of all datasets as D. In this work, we specifically consider datasets sampled from a data distribution Φ : Dist(Z); for example, the distribution of state-actions reached by following some stationary policy. We use D ∼ Φd to denote constructing a dataset of d tuples 〈s, a, r, s′〉, by first sampling each 〈s, a〉 ∼ Φ, and then sampling r and s′ i.i.d. from the environment reward function and transition function respectively, i.e. each r ∼ R(·|〈s, a〉) and s′ ∼ P (·|〈s, a〉).5 We sometimes index D using function notation, using D(s, a) to denote the multiset of all 〈r, s′〉 such that 〈s, a, r, s′〉 ∈ D. We use n̈D ∈ R|Z| to denote the vectors of counts, that is, n̈D(〈s, a〉) := |D(s, a)|. We sometimes use state-wise versions of these vectors, which we denote with ṅD. It is further useful to consider the maximum-likelihood reward and transition functions, computed by averaging all rewards and transitions observed in the dataset for each state-action. To this end, we define empirical reward vector rD(〈s, a〉) := ∑ r,s′∈D(〈s,a〉) r |D(〈s,a〉)| and empirical transition
matrix PD(s′|〈s, a〉) := ∑ r,ṡ′∈D(〈s,a〉) I(ṡ′=s′) |D(〈s,a〉)| at all state-actions for which n̈D(〈s, a〉) > 0. Where with n̈D(〈s, a〉) = 0, there is no clear way to define the maximum-likelihood estimates of 5Note that this is in some sense a simplifying assumption. In practice, datasets will typically be collected using a trajectory from a non-stationary policy, rather than i.i.d. sampling from the stationary distribution of a stationary policy. This greatly complicates the analysis, so we do not consider that setting in this work.
reward and transition, so we do not specify them. All our results hold no matter how these values are chosen, so long as rD ∈ [0, 11−γ ] and PD is stochastic. The empirical policy of a dataset D is defined as π̂D(a|s) := |D(〈s,a〉)||D(〈s,·〉)| except where n̈D(〈s, a〉) = 0, where it can similarly be any valid action distribution. The empirical visitation distribution of a dataset D is computed in the same way as the visitation distribution, but with PD replacing P , i.e. (I − γAπPD)−1.
Problem setting. The primary focus of this work is on the properties of fixed-dataset policy optimization (FDPO) algorithms. These algorithms take the form of a function O : D → Π, which maps from a dataset to a policy.6 Note that in this work, we consider D ∼ Φd, so the dataset is a random variable, and therefore O(D) is also a random variable. The goal of any FDPO algorithm is to output a policy with minimum suboptimality, i.e. maximum return. Suboptimality is a random variable dependent on D, computed by taking the difference between the expected return of an optimal policy and the learned policy under the initial state distribution,
SUBOPT(O(D)) = Eρ[v π∗M M ]− Eρ[v O(D) M ].
A related concept is the fixed-dataset policy evaluation algorithm, which is any function E : D → Π→ S → R, which uses a dataset to compute a value function. In this work, we focus our analysis on value-based FDPO algorithms, the subset of FDPO algorithms that utilize FDPE algorithms.7 A value-based FDPO algorithm with FDPE subroutine Esub is any algorithm with the following structure:
OVBsub (D) := arg max π Eρ[Esub(D,π)].
We define a fixed-point family of algorithms, sometimes referred to as just a family, in the following way. Any family called family is based on a specific fixed-point identity ffamily. We use the notation Efamily to denote any FDPE algorithm whose output vπD := Efamily(D,π) obeys vπD = ffamily(vπD). Finally, OVBfamily refers to any value-based FDPO algorithm whose subroutine is Efamily. We call the set of all algorithms that could implement Efamily the family of FDPE algorithms, and the set of all algorithms that could implement OVBfamily as the family of FDPO algorithms.

heading: B UNCERTAINTY
text: Epistemic uncertainty measures an agent’s knowledge about the world, and is therefore a core concept in reinforcement learning, both for exploration and exploitation; it plays an important role in this work. Most past analyses in the literature implicitly compute some form of epistemic uncertainty to derive their bounds. An important analytical choice in this work is to cleanly separate the estimation of epistemic uncertainty from the problem of decision making. Our approach is to first define a notion of uncertainty as a function with certain properties, then assume that such a function exists, and provide the remainder of our technical results under such an assumption. We also describe several approaches to computing uncertainty.
Definition 5 (Uncertainty). A function uD,δ : Z → R is a state-action-wise Bellman uncertainty function if for a dataset D ∼ Φd, it obeys with probability at least 1 − δ for all policies π and all values v:
uD,δ ≥ |(rM + γPMv)− (rD + γPDv)|
6This formulation hides a dependency on ρ, the start-state distribution of the MDP. In general, ρ can be estimated from the dataset D, but this estimation introduces some error that affects the analysis. In this work, we assume for analytical simplicity that ρ is known a priori. Technically, this means that it must be provided as an input to O. We hide this dependency for notational clarity.
7Intuitively, these algorithms use a policy evaluation subroutine to convert a dataset into a value function, and return an optimal policy according to that value function. Importantly, this definition constrains only the objective of the approach, not its actual algorithmic implementation, i.e., it includes algorithms which never actually invoke the FDPE subroutine. For many online model-free reinforcement learning algorithms, including policy iteration, value iteration, and Q-learning, we can construct closely analogous value-based FDPO algorithms; see Appendix D.1. Furthermore, model-based techniques can be interpreted as using a model to implicitly define a value function, and then optimizing that value function; our results also apply to model-based approaches.
A function uπD,δ : S → R is a state-wise Bellman uncertainty function if for a dataset D ∼ Φd and policy π, it obeys with probability at least 1− δ for all policies π and all values v:
uπD,δ ≥ |Aπ (rM + γPMv)−Aπ (rD + γPDv)| A function µπD,δ : S → R is a value uncertainty function if for a dataset D ∼ Φd and policy π, it obeys with probability at least 1− δ for all policies π and all values v:
µπD,δ ≥ ∞∑ t=0 (γAπPD) t |Aπ (rM + γPMv)−Aπ (rD + γPDv)|
We refer to the quantity returned by an uncertainty function as uncertainty, e.g., value uncertainty refers to the quantity returned by a value uncertainty function.
Given a state-action-wise Bellman uncertainty function uD,δ , it is easy to verify that AπuD,δ is a state-wise Bellman uncertainty function. Similarly, given a state-wise Bellman uncertainty function uπD,δ , it is easy to verify that (I − γAπPD) −1 uπD,δ is a value uncertainty function. Uncertainty functions which can be constructed in this way are called decomposable. Definition 6 (Decomposablility). A state-wise Bellman uncertainty function uπD,δ is state-actionwise decomposable if there exists a state-action-wise Bellman uncertainty function uD,δ such that uπD,δ = A
πuD,δ . A value uncertainty function µ is state-wise decomposable if there exists a statewise Bellman uncertainty function uπD,δ such that µ = (I − γAπPD) −1 uπD,δ , and further, it is state-action-wise decomposable if that uπD,δ is itself state-action-wise decomposable.
Our definition of Bellman uncertainty captures the intuitive notion that the uncertainty at each state captures how well an approximate Bellman update matches the true environment. Value uncertainty represents the accumulation of these errors over all future timesteps.
How do these definitions correspond to our intuitions about uncertainty? An application of the environment’s true Bellman update can be viewed as updating the value of each state to reflect information about its future. However, no algorithm in the FDPO setting can apply such an update, because the true environment dynamics are unknown. We may use the dataset to estimate what such an update would look like, but since the limited information in the dataset may not fully specify the properties of the environment, this update will be slightly wrong. It is intuitive to say that the uncertainty at each state corresponds to how well the approximate update matches the truth. Our definition of Bellman uncertainty captures precisely this notion. Further, value uncertainty represents the accumulation of these errors over all future timesteps.
How can we algorithmically implement uncertainty functions? In other words, how can we compute a function with the properties required for Definition 5, using only the information in the dataset? All forms of uncertainty are upper-bounds to a quantity, and a tighter upper-bound means that other results down the line which leverage this quantity will be improved. Therefore, it is worth considering this question carefully.
A trivial approach to computing any uncertainty function is simply to return 11−γ for all s and 〈s, a〉. But although this is technically a valid uncertainty function, it is not very useful, because it does not concentrate with data and does not distinguish between certain and uncertain states. It is very loose and so leads to poor guarantees.
In tabular environments, one way to implement a Bellman uncertainty function is to use a concentration inequality. Depending on which concentration inequality is used, many Bellman uncertainty functions are possible. These approaches lead to Bellman uncertainty which is lower at states with more data, typically in proportion to the square root of the count. To illustrate how to do this, we show in Appendix B.1 how a basic application of Hoeffding’s inequality can be used to derive a state-action-wise Bellman uncertainty. In Appendix B.2, we show an alternative application of Hoeffding’s which results in a state-wise Bellman uncertainty, which is a tighter bound on error. In Appendix B.3, we discuss other techniques which may be useful in tightening further.
When the value function is represented by a neural network, it is not currently known how to implement a Bellman uncertainty function. When an empirical Bellman update is applied to a neural
network, the change in value of any given state is impacted by generalization from other states. Therefore, the counts are not meaningful, and concentration inequalities are not applicable. In the neural network literature, many “uncertainty estimation techniques” have been proposed, which capture something analogous to an intuitive notion of uncertainty; however, none are principled enough to be useful in computing Bellman uncertainty.

heading: B.1 STATE-ACTION-WISE BOUND
text: We seek to construct an uπD,δ such that |Aπ (rM + γPMv)−Aπ (rD + γPDv)| ≤ uπD,δ with probability at least 1− δ. Firstly, let’s consider the simplest possible bound. v is bounded in [0, 11−γ ], so both Aπ (rM + γPMv) and Aπ (rD + γPDv) must be as well. Thus, their difference is also bounded:
|Aπ (rM + γPMv)−Aπ (rD + γPDv)| ≤ 1
1− γ
Next, consider that for any 〈s, a〉, the expression rD(〈s, a〉) + γPD(〈s, a〉)vπ can be equivalently expressed as an expectation of random variables,
rD(〈s, a〉) + γPD(〈s, a〉)v = 1 n̈D(〈s, a〉) ∑
r,s′∈D(〈s,a〉)
r + γv(s′),
each with expected value
Er,s′∈D(〈s,a〉)[r + γv(s′)] = Er∼R(·|〈s,a〉) s′∼P (·|〈s,a〉) [r + γv(s′)] = [rM + γPMv](〈s, a〉).
Note also that each of these random variables is bounded [0, 11−γ ]. Thus, Hoeffding’s inequality tells us that this mean of bounded random variables must be close to their expectation with high probability. By invoking Hoeffding’s at each of the |S ×A| state-actions, and taking a union bound, we see that with probability at least 1− δ,
|(rM + γPMv)− (rD + γPDv)| ≤ 1
1− γ
√ 1
2 ln 2|S × A| δ n̈−1D
We can left-multiply Aπ and rearrange to get:
|Aπ(rM + γPMv)−Aπ (rD + γPDvπM)| ≤
( 1
1− γ
√ 1
2 ln 2|S × A| δ
) Aπn̈
− 12 D
Finally, we simply intersect this bound with the 11−γ bound from earlier. Thus, we see that with probability at least 1− δ,
|Aπ(rM + γPMv)−Aπ (rD + γPDvπM)| ≤ 1
1− γ ·min
((√ 1
2 ln 2|S × A| δ
) Aπn̈
− 12 D , 1
)

heading: B.2 STATE-WISE BOUND
text: This bound is similar to the previous, but uses Hoeffding’s to bound the value at each state all at once, rather than bounding the value at each state-action.
Choose a collection of possible state-local policies Πlocal ⊆ Dist(A). Each state-local policy is a member of the action simplex.
For any s ∈ S and π ∈ Πlocal, the expression [Aπ(rD + γPDv)](s) can be equivalently expressed as a mean of random variables,
[Aπ(rD + γPDv)](s) = 1
ṅD(s) ∑ a,r,s′∈D(s) π(a|s) π̂D(a|s) (r + γv(s′)),
each with expected value Ea,r,s′∈D(s) [ π(a|s) π̂D(a|s) (r + γv(s′)) ] = E a∼π(·|s)
r∼R(·|〈s,a〉) s′∼P (·|〈s,a〉)
[r + γv(s′)] = [Aπ(rM + γPMv)](s).
Note also that each of these random variables is bounded [0, 11−γ π(a|s) π̂D(a|s) ]. Thus, Hoeffding’s inequality tells us that this sum of bounded random variables must be close to its expectation with high probability. By invoking Hoeffding’s at each of the |S| states and |Πlocal| local policies, and taking a union bound, we see that with probability at least 1− δ,
|Aπ(rM + γPMv)−Aπ (rD + γPDvπM)| ≤ 1
1− γ
√ 1
2 ln 2|S ×Πlocal| δ (Aπ)◦2n̈−1D
where the term (Aπ)◦2 refers to the elementwise square. Finally, we once again intersect with 11−γ , yielding that with probability at least 1− δ,
|Aπ(rM + γPMv)−Aπ (rD + γPDvπM)| ≤ 1
1− γ ·min
(√ 1
2 ln 2|S ×Πlocal| δ (Aπ)◦2n̈−1D , 1
)
Comparing this to the Bellman uncertainty function in Appendix B.1, we see two differences. Firstly, we have replaced a factor of |A| with |Πlocal|, typically loosening the bound somewhat (depending on choice of considered local policies). Secondly, Aπ has now moved inside of the square root; since the square root is concave, Jensen’s inequality says that√
(Aπ)◦2n̈−1D ≤ √ (Aπ)◦2 √ n̈−1D = A πn̈ − 12 D
and so this represents a tightening of the bound.
When Πlocal is the set of deterministic policies, this bound is equivalent to that of Appendix B.1. This can easily be seen by noting that for a deterministic policy, all elements of (Aπ)◦2 are either 1 or 0, and so √
(Aπ)◦2n̈−1D = A πn̈ − 12 D
and also that the size of the set of deterministic policies is exactly |A|. An important property of this bound is that it shows that stochastic policies can be often be evaluated with lower error than deterministic policies. We prove this by example. Consider an MDP with a single state s and two actions a0, a1, and a dataset with n̈D(〈s, a0〉) = n̈D(〈s, a1〉) = 2. We can parameterize the policy by a single number ξ ∈ [0, 1] by setting π(a0|s) = ξ, π(a1|s) = 1− ξ. The size of this bound will be proportional to √ ξ2
2 + (1−ξ)2
2 , and setting the derivative equal to zero, we see that the minimum is ξ = 12 . (Of course, we would need to increase the size of our local policy set to include this, in order to be able to actually select it, and doing so will increase the overall bound; this example only shows that for a given policy set, the selected policy may in general be stochastic.)
Finding the optimum for larger local policy sets is non-trivial, so we leave a full treatment of algorithms which leverage this bound for future work.

heading: B.3 OTHER BOUNDS
text: There are a few other paths by which this bound can be made tighter still. The above bounds take an extra factor of 11−γ because we bound the overall return, rather than simply bounding the reward and transition functions. This was done because a bound on the transition function would add a cost of O( √ S). However, this can be mitigated by intersecting the above confidence interval with a Good-Turing interval, as proposed in Taleghan et al. (2015). Doing so will cause the bound to concentrate much more quickly in MDPs where the transition function is relatively deterministic. We expect this to be the case for most practical MDPs.
Similarly, empirical Bernstein confidence intervals can be used in place of Hoeffding’s, to increase the rate of concentration for low-variance rewards and transitions (Maurer & Pontil, 2009), leading to improved performance in MDPs where these are common.
Finally, we may be able to apply a concentration inequality in a more advanced fashion to compute a value uncertainty function which is not statewise decomposable: we bound some useful notion of value error directly, rather than computing the Bellman uncertainty function and taking the visitation-weighted sum. This would result in an overall tighter bound on value uncertainty by hedging over data across multiple timesteps. However, in doing so, we would sacrifice the monotonic improvement property needed for convergence of algorithms like policy iteration. This idea has a parallel in the robust MDP literature. The bounds in Appendix B.1 can be seen as constructing an sarectangular robust MDP, whereas Appendix B.2 is similar to constructing an s-rectangular robust MDP Wiesemann et al. (2013). More recently, approaches have been proposed which go beyond s-rectangular (Goyal & Grand-Clement, 2018), and such approaches likely have natural parallels in implementing value uncertainty functions.

heading: C PROOFS

heading: C.1 PROOF OF OVER/UNDER DECOMPOSITION
text: Starting from the definition of suboptimality, we see
SUBOPT(OVB(D)) = Eρ[v π∗M M ]− Eρ[v π∗D M ]
= Eρ[v π∗M M + (−v π D + v π D) + (−v π∗D D + v π∗D D )− v π∗D M ] (valid for any π) ≤ Eρ[v∗M − vπD] + Eρ[v π∗D D − v π∗D M ] (using Eρ[v π D − v π∗D D ] ≤ 0)
Since the above holds for all π,
SUBOPT(OVB(D)) ≤ inf π
( Eρ[v π∗M M − v π D] ) + Eρ[v π∗D D − v π∗D M ]
≤ inf π
( Eρ[v π∗M M − v π D] )
+ sup π
( Eρ[vπD − vπM] ) (using vπ ∗ D D ∈ Π)
= inf π
( Eρ[v π∗M M − v π M] + Eρ[vπM − vπD] ) + sup
π
( Eρ[vπD − vπM] )

heading: C.2 TIGHTNESS OF OVER/UNDER DECOMPOSITION
text: We show that the bound given in Lemma 1 is tight via a simple example.
Proof. Consider a bandit-structured MDP with a single state and two actions, A and B, with rewards of 0 and 1 respectively, which both lead to terminal states.
First, consider the left-hand side. If an FDPE subroutine estimates the value of both arms to be 1, then the policy which always selects arm A is an optimal policy of the corresponding FDPO algorithm. In this case, the suboptimality is clearly equal to 1. This is clearly the worst-case suboptimality, since it is the largest possible suboptimality in the environment.
On the right-hand side, note that term (A) is 0 when π is the policy that always picks B, while term (B) is 1 when π is the policy that always picks A. Thus, the left-hand and right-hand sides are equal, and the bound is tight.

heading: C.3 RESIDUAL VISITATION LEMMA
text: We prove a basic lemma showing that the error of any value function is equal to its one-step Bellman residual, summed over its visitation distribution. Though this result is well-known, it is not clearly stated elsewhere in the literature, so we prove it here for clarity. Lemma 2. For any MDP ξ and policy π, consider the Bellman fixed-point equation given by, let vπξ be defined as the unique value vector such that vπξ = A π(rξ +γPξv π ξ ), and let v be any other value
vector. We have
vπξ − v = (I − γAπPξ)−1(Aπ(rξ + γPξv)− v) (1) v − vπξ = (I − γAπPξ)−1(v −Aπ(rξ + γPξv)) (2) |vπξ − v| = (I − γAπPξ)−1|Aπ(rξ + γPξv)− v| (3)

heading: Proof.
text: Aπ(rξ + γPξv)− v = Aπ(rξ + γPξv)− vπξ + vπξ − v = Aπ(rξ + γPξv)−Aπ(rξ + γPξvπξ ) + vπξ − v = γAπPξ(v − vπξ ) + (vπξ − v) = (vπξ − v)− γAπPξ(vπξ − v) = (I − γAπPξ)(vπξ − v)
Thus, we see (I−γAπPξ)−1(Aπ(rξ +γPξv)−v) = vπξ −v. An identical proof can be completed starting with v −Aπ(rξ + γPξv), leading to the desired result.

heading: C.4 NAÏVE FDPE ERROR BOUND
text: We show how the error of naı̈ve FDPE algorithms is bounded by the value uncertainty of stateactions visited by the policy under evaluation. Next, in Section 4, we use this bound to derive a suboptimality guarantee for naı̈ve FDPO. Lemma 3 (Naı̈ve FDPE error bound). Consider any naı̈ve fixed-dataset policy evaluation algorithm Enaı̈ve. For any policy π and dataset D, denote vπD := Enaı̈ve(D,π). Let µπD,δ be any value uncertainty function. The following component-wise bound holds with probability at least 1− δ:
|vπM − vπD| ≤ µπD,δ
Proof. Notice that the naı̈ve fixed-point function is equivalent to the Bellman fixed-point equation for a specific MDP: the empirical MDP defined by 〈S,A, rD, PD, γ, ρ〉. Thus, invoking Lemma 2, for any values v we have
|vπD − v| = (I − γAπPD)−1|Aπ(rD + γPDv)− v|.
Since vπM is a value vector, this immediately implies that
|vπD − vπM| = (I − γAπPD)−1|Aπ(rD + γPDvπM)− vπM|.
Since vπM is the solution to the Bellman consistency fixed-point,
|vπD − vπM| = (I − γAπPD)−1|Aπ(rD + γPDvπM)−Aπ(rM + γPMvπM)|.
Using the definition of a value uncertainty function µπD,δ , we arrive at
|vπD − vπM| ≤ µπD,δ completing the proof.
Thus, reducing value uncertainty improves our guarantees on evaluation error. For any fixed policy, value uncertainty can be reduced by reducing the Bellman uncertainty on states visited by that policy. In the tabular setting this means observing more interactions from the state-actions that that policy visits frequently. Conversely, for any fixed dataset, we will have a certain Bellman uncertainty in each state, and policies mostly visit low-Bellman-uncertainty states can be evaluated with lower error.8
8In the function approximation setting, we do not necessarily need to observe an interaction with a particular state-action to reduce our Bellman uncertainty on it. This is because observing other state-actions may allow us to reduce Bellman uncertainty through generalization. Similarly, the most-certain policy for a fixed dataset may not be the policy for which we have the most data, but rather, the policy which our dataset informs us about the most.
Our bound differs from prior work (Jiang, 2019a; Ghavamzadeh et al., 2016) in that it is significantly more fine-grained. We provide a component-wise bound on error, whereas previous results bound the l∞ norm. Furthermore, our bounds are sensitive to the Bellman uncertainty in each individual reward and transition, rather than only relying on the most-uncertain. As a result, our bound does not require all states to have the same number of samples, and is non-vacuous even in the case where some state-actions have no data.
Our bound can also be viewed as an extension of work on approximate dynamic programming. In that setting, the literature contains fine-grained results on the accumulation of local errors (Munos, 2007). However, those results are typically understood as applying to errors induced by approximation via some limited function class. Our bound can be seen as an application of those ideas to the case where errors are induced by limited observations.

heading: C.5 RELATIVE VALUE UNCERTAINTY
text: The key to the construction of proximal pessimistic algorithms is the relationship between the value uncertainties of any two policies π, π′, for any state-action-wise decomposable value function.
Lemma 4 (Relative value uncertainty). For any two policies π, π′, and any state-action-wise decomposable value uncertainty µ, we have
µπD,δ − µπ ′ D,δ = (I − γAπPD)−1 ( (Aπ −Aπ ′ )(uD,δ + γPDµ π′ D,δ) )
Proof. Firstly, note that since the value uncertainty function is state-action-wise decomposable, we can express it in a Bellman-like form for some state-wise Bellman uncertainty uπD,δ as µ π D,δ = (I − γAπPD)−1 uπD,δ . Further, uπD,δ is itself state-action-wise decomposable, so it can be written as uπD,δ = A πuD,δ .
We can use this to derive the following relationship.
µπD,δ = (I − γAπPD) −1 uπD,δ
µπD,δ − γPDAπµπD,δ = uπD,δ µπD,δ = u π D,δ + γA πPDµ π D,δ
Next, we bound the difference between the value uncertainty of π and π′.
µπD,δ − µπ ′ D,δ = (u π D,δ + γA πPDµ π D,δ)− (uπ ′ D,δ + γA π′PDµ π′ D,δ)
= (uπD,δ − uπ ′ D,δ) + γA πPDµ π D,δ − γAπ ′ PDµ π′ D,δ = (Aπ −Aπ ′ )uD,δ + γA πPDµ π D,δ − γ(Aπ ′ −Aπ +Aπ)PDµπ ′ D,δ
= γAπPD ( µπD,δ − µπ ′ D,δ ) + (Aπ −Aπ ′ )uD,δ + γ(A π −Aπ ′ )PDµ π′ D,δ
= γAπPD ( µπD,δ − µπ ′ D,δ ) + (Aπ −Aπ ′ )(uD,δ + γPDµ π′ D,δ)
This is a geometric series, so (I − γAπPD) ( µπD,δ − µπ ′ D,δ ) = (Aπ − Aπ′)(uD,δ + γPDµπ ′ D,δ). Left-multiplying by (I − γAπPD)−1 we arrive at the desired result.

heading: C.6 NAÏVE FDPE RELATIVE ERROR BOUND
text: Lemma 5 (Naı̈ve FDPE relative error bound). Consider any naı̈ve fixed-dataset policy evaluation algorithm Enaı̈ve. For any policy π and dataset D, denote vπD := Enaı̈ve(D,π). Then, for any other policy π′, the following bound holds with probability at least 1− δ:
|vπD − vπM| ≤ µπD,δ ≤ µπ ′ D,δ + (I − γAπPD)−1 (
1
(1− γ)2
) TVS(π, π′)
Proof. The goal of this section is to construct an error bound for which we can optimize π without needing to compute any uncertainties. To do this, we must replace this quantity with a looser upper bound.
First, consider a state-action-wise decomposable value uncertainty function µπD,δ . We have µ π D,δ = (I − γPDAπ)−1uπD,δ for some uπD,δ , where uπD,δ = AπuD,δ for some uD,δ .
Note that state-action-wise Bellman uncertainty can be trivially bounded as uD,δ ≤ 11−γ 1̈. Also, since (I−γPDAπ)−1 ≤ 11−γ , any state-action-wise decomposable value uncertainty can be trivially bounded as µπD,δ ≤ 1(1−γ)2 1̇.
We now invoke Lemma 4. We then substitute the above bounds into the second term, after ensuring that all coefficients are positive.
µπD,δ − µπ ′ D,δ = (I − γAπPD)−1 ( (Aπ −Aπ ′ )(uD,δ + γPDµ π′ D,δ) )
≤ (I − γAπPD)−1 ( |Aπ −Aπ ′ |+(uD,δ + γPDµπ ′ D,δ) )
≤ (I − γAπPD)−1 ( |Aπ −Aπ ′ |+ ( 1
1− γ 1̈ + γPD
1
(1− γ)2 1̇ )) = (I − γAπPD)−1 ( |Aπ −Aπ ′ |+ ( 1
1− γ 1̈ +
γ
(1− γ)2 1̈ )) = (I − γAπPD)−1 ( 1
(1− γ)2
) |Aπ −Aπ ′ |+1̈
= (I − γAπPD)−1 (
1
(1− γ)2
) TVS(π, π′)
The third-to-last step follows from the fact that PD is stochastic. The final step follows from the fact that the positive and negative components of the state-wise difference between policies must be symmetric, so |Aπ − Aπ′ |+1̈ is precisely equivalent to the state-wise total variation distance, TVS(π, π′). Thus, we have
µπD,δ ≤ µπ ′ D,δ + (I − γAπPD)−1 (
1
(1− γ)2
) TVS(π, π′).
Finally, invoking Lemma 3, we arrive at the desired result.

heading: C.7 SUBOPTIMALITY OF UNCERTAINTY-AWARE PESSIMISTIC FDPO ALGORITHMS
text: Let vπD := Eua(D,π). From the definition of the UA family, we have the fixed-point property vπD = A π(rD + γPDv π D) − αuπD,δ , and the standard geometric series rearrangement yields vπD = (I − γAπPD)−1 (AπrD − αuπD,δ). From here, we see:
vπD = (I − γAπPD) −1 (AπrD − αuπD,δ)
= (I − γAπPD)−1AπrD − (I − γAπPD)−1 αuπD,δ = Enaı̈ve(D,π)− αµπD,δ
We now use this to bound overestimation and underestimation error of Eua(D,π) by invoking Lemma 3, which holds with probability at least 1− δ. First, for underestimation, we see:
vπM − vπD = vπM − ( Enaı̈ve(D,π)− αµπD,δ ) = (vπM − Enaı̈ve(D,π)) + αµπD,δ ≤ µπD,δ + αµπD,δ = (1 + α)µπD,δ
and thus, vπM − vπD ≤ (1 + α)µπD,δ . Next, for overestimation, we see: vπD − vπM = ( Enaı̈ve(D,π)− αµπD,δ ) − vπM
= (Enaı̈ve(D,π)− vπM)− αµπD,δ ≤ µπD,δ − αµπD,δ = (1− α)µπD,δ
and thus, vπD − vπM ≤ (1 − α)µπD,δ . Substituting these bounds into Lemma 1 gives the desired result.

heading: C.8 SUBOPTIMALITY OF PROXIMAL PESSIMSITIC FDPO ALGORITHMS
text: Let vπD := Eproximal(D,π). From the definition of the proximal family, we have the fixed-point property
vπD = A π(rD + γPDv π D)− α
( TVS(π, π̂D)
(1− γ)2 ) and the standard geometric series rearrangement yields
vπD = (I − γAπPD) −1 ( AπrD − α ( TVS(π, π̂D)
(1− γ)2 )) From here, we see:
vπD = (I − γAπPD) −1 ( AπrD − α ( TVS(π, π̂D)
(1− γ)2 )) = (I − γAπPD)−1AπrD − (I − γAπPD)−1 α ( TVS(π, π̂D)
(1− γ)2 ) = Enaı̈ve(D,π)− (I − γAπPD)−1 α ( TVS(π, π̂D)
(1− γ)2 ) Next, we define a new family of FDPE algorithms,
Eproximal-full(D,π) := Enaı̈ve(D,π)− α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2
)) .
We use Lemma 3, which holds with probability at least 1 − δ, to bound the overestimation and underestimation. First, the underestimation:
vπM − Eproximal-full(D,π) = vπM − ( Enaı̈ve(D,π)− α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2 ))) = (vπM − Enaı̈ve(D,π)) + α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2 )) ≤ µπD,δ + α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2 )) Next, we analagously bound the overestimation:
Eproximal-full(D,π)− vπM = ( Enaı̈ve(D,π)− α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2
))) − vπM
= (vπM − Enaı̈ve(D,π))− α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2 )) ≤ µπD,δ − α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2 )) We can now invoke Lemma 1 to bound the suboptimality of any value-based FDPO algorithm which uses Eproximal-full, which we denote with O VB proximal-full. Crucially, note that since αµ π′
D,δ is not dependent on π, it can be removed from the infimum and supremum terms, and cancels. Substituting and rearranging, we see that with probability at least 1− δ,
SUBOPT(OVBproximal-full(D)) ≤ inf π
( Eρ[v π∗M M − v π M] + Eρ [ µπD,δ + α(I − γAπPD)−1 ( TVS(π, π̂D)
(1− γ)2
)])
+ sup π
( Eρ [ µπD,δ − α(I − γAπPD)−1 ( TVS(π, π̂D)
(1− γ)2 )]) Finally, we see that FDPO algorithms which use Eproximal-full as their subroutine will return the same policy as FDPO algorithms which use Eproximal. First, we once again use the property that µπ ′
D,δ is not dependent on π. Second, we note that since the total visitation of every policy sums to 11−γ , we
know Eρ [ (I − γAπPD)−1 ( 1 γ )] = 1(1−γ)2 for all π, and thus it is also not dependent on π.
arg max π Eρ[Eproximal-full(D,π)] = arg max π
Eρ [ Enaı̈ve(D,π)− α ( µπ ′ D,δ + (I − γAπPD)−1 (
TVS(π, π̂D) (1− γ)2 ))] = arg max π Eρ [ Enaı̈ve(D,π)− (I − γAπPD)−1α ( TVS(π, π̂D) (1− γ)2
)] = arg max
π Eρ[Eproximal(D,π)]
Thus, the suboptimality of arg maxπ Eρ[Eproximal(D,π)] must be equivalent to that of arg maxπ Eρ[Eproximal-full(D,π)], leading to the desired result.

heading: C.9 STATE-WISE PROXIMAL PESSIMISTIC ALGORITHMS
text: In the main body of the work, we focus on proximal pessimistic algorithms which are based on a state-conditional density model, since this approach is much more common in the literature. However, it is also possible to derive proximal pessimistic algorithms which use state-action densities, which have essentially the same properties. In this section we briefly provide the main results.
In this section, we use dπ := (1− γ)(I − γAπPD)−1 to indicate the state visitation distribution of any policy π. Definition 7. A state-action-density proximal pessimistic algorithm with pessimism hyperparameter α ∈ [0, 1] is any algorithm in the family defined by the fixed-point function
fsad-proximal(v π) = Aπ(rD + γPDv π)− α ( |dπ − dπ̂D | (1− γ)2 ) Theorem 4 (State-action-density proximal pessimistic FDPO suboptimality bound). Consider any state-action-density proximal pessimistic value-based fixed-dataset policy optimization algorithm OVBsad-proximal. Let µ be any state-action-wise decomposable value uncertainty function, and α ∈ [0, 1] be a pessimism hyperparameter. For any datasetD, the suboptimality ofOVBsad-proximal is bounded with probability at least 1− δ by
SUBOPT(Osad-proximal(D)) ≤ 2Eρ[µπ̂DD,δ] + infπ
( Eρ[v π∗M M − v π M] + (1 + α) · Eρ [ (I − γAπPD)−1 ( |dπ − dπ̂D |+
(1− γ)2 )]) + sup
π
( (1− α) · Eρ [ (I − γAπPD)−1 ( |dπ − dπ̂D |+
(1− γ)2 )]) Proof. First, note that for any policies π, π′, and any state-action-wise decomposable value uncertainty µ with state-action-wise Bellman uncertainty uD,δ ≤ 11−γ 1̈, we have
µπD,δ − µπ ′ D,δ = (I − γAπPD)−1AπuD,δ − (I − γAπ ′ PD) −1Aπ ′ uD,δ
= 1
1− γ (dπ − dπ′)AπuD,δ
≤ 1 1− γ |dπ − dπ′ |+AπuD,δ
≤ |dπ − dπ ′ |+
(1− γ)2
Invoking Lemma 3 we see that |vπD − vπM| ≤ µπD,δ ≤ µ π̂D D,δ + |dπ−dπ̂D |+ (1−γ)2 . The remainder of the proof follows analogously to Appendix C.8.

heading: D ALGORITHMS
text: In the main body of the text, we primarily focus on families of algorithms, rather than specific members. In this section, we provide pseudocode from example algorithms in each family. The majority of these algorithms are simple empirical extensions of well-studied algorithms, so we do not study their properties (e.g. convergence) in detail. The sets of algorithms described here are not intended to be comprehensive, but rather, a few straightforward examples to illustrate key concepts and inspire further research. To simplify presentation, we avoid hyperparameters, e.g. learning rate, wherever possible.

heading: D.1 NAÏVE
text: The naı̈ve algorithms presented here are simply standard dynamic programming approaches applied to the empirical MDP construced from the dataset, using rD, PD in place of r, P . See Puterman (2014) for analysis of convergence, complexity, optimality, etc. of the general dynamic programming approaches, and note that the empirical MDP is simply a particular example of an MDP, so all results apply directly.
Algorithm 1: Tabular Fixed-Dataset Policy Evaluation Input: Dataset D, policy π, discount γ. Construct rD, PD as described in Section 2; v← (I − γAπPD)−1AπrD; return v;
Algorithm 2: Tabular Fixed-Dataset Policy Iteration Input: Dataset D, discount γ. Initialize π, v Construct rD, PD as described in Section 2; while π not converged do
π ← arg maxπ̇∈ΠAπ̇(rD + γPDv); // argmax policy is state-wise max action v← (I − γAπPD)−1AπrD;
end return π;
Algorithm 3: Tabular Fixed-Dataset Value Iteration Input: Dataset D, discount γ. Initialize π,v Construct rD, PD as described in Section 2; while v not converged do
π ← arg maxπ̇∈ΠAπ̇v; // argmax policy is state-wise max action v← rD + γPDAπv;
end return π;
Algorithm 4: Neural Fixed-Dataset Value Iteration Input: Dataset D, discount γ. Initialize θ, θ′ while θ not converged do
for each s in D do π(s)← arg maxa∈A qθ(s, a) ; end while θ′ not converged do
Sample 〈s, a, r, s′〉 from D; L← (r + γqθ(s′, π(s′))− qθ′(s, a))2; θ′ ← θ′ −∇θ′L;
end θ ← θ′
end return π;

heading: D.2 PESSIMISTIC
text: In this section, we provide pseudocode for concrete implementations of algorithms in the pessimistic families we have discussed. Since the algorithms are not the focus of this work, we do not provide an in-depth analysis of these algorithms. We briefly note that, at a high level, the standard proof technique used to show convergence of policy iteration (Sutton & Barto, 2018) can be applied to all of these approaches. These algorithms utilize a penalized Bellman update, and the penalty is state-wise and independent between states. Thus, performing a local greedy policy improvement in any one state will strictly increase the value of all states. Thus, policy iteration guarantees strict monotonic improvement of the values of all states, and thus eventual convergence to an optimal policy (as measured by the penalized values).

heading: D.2.1 UNCERTAINTY-AWARE
text: In this section, we provide pseudocode for a member of the the UA pessimsitic family of algorithms.
Algorithm 5: Tabular Uncertainty-Aware Pessimistic Fixed-Dataset Policy Iteration Input: Dataset D, discount γ, error rate δ, pessimism parameter α. Initialize v, π Construct rD, PD, n̈D as described in Section 2; Compute uπD,δ as described in Appendix B; while π not converged do
π ← arg maxπ̇∈ΠAπ̇(v − αuπ̇D,δ); v← (I − γAπPD)−1 (AπrD − αuπD,δ);
end return π;
Algorithm 6: Neural Uncertainty-Aware Pessimistic Fixed-Dataset Value Iteration Input: Dataset D, discount γ, pessimism hyperparameter α. Initialize θ, θ′,Ψ; while θ not converged do
// update policy while Ψ not converged do
Sample 〈s, ·, ·, ·〉 from D; R← Ea∼πΨ(·|s)[qθ(s, a)]− αu πΨ D,δ(s);
Ψ′ ← Ψ′ +∇θ′R; end // update value function while θ′ not converged do
Sample 〈s, a, r, s′〉 from D; L← (r + γ ( Ea′∼πΨ(·|s′)[qθ(s′, a′)]− αu πΨ D,δ(s ′) ) − qθ′(s, a))2;
θ′ ← θ′ −∇θ′L; end θ ← θ′
end return πΨ;
As discussed in the main text, count-based Bellman uncertainty functions, such as those derived from concentration inequalities in Appendix B.1, do not apply to non-tabular environments. The correct way to compute epistemic uncertainty with neural networks is still an open question. Therefore, our pseudocode for a neural implementation of the UA pessimistic approach is in some sense incomplete: a full implementation would need to specify a technique for computing uπD,δ . We hope that future work will identify such a technique.

heading: D.2.2 PROXIMAL
text: In this section, we provide pseudocode for a member of the proximal pessimsitic family of algorithms.
Algorithm 7: Tabular Proximal Pessimistic Fixed-Dataset Policy Iteration Input: Dataset D, discount γ, pessimism parameter α. Initialize v, π Construct rD, PD, n̈D as described in Section 2; while π not converged do
π ← arg maxπ̇∈ΠAπ̇(v − α2(1−γ)2 |π̇ − π̂D|); v← (I − γAπPD)−1 (AπrD − α2(1−γ)2 |π̇ − π̂D|);
end return π;
Algorithm 8: Neural Proximal Pessimistic Fixed-Dataset Value Iteration, Discrete Action Space Input: Dataset D, discount γ, pessimism hyperparameter α. Initialize θ, θ′,Ψ; while θ not converged do
// update policy while Ψ not converged do
Sample 〈s, ·, ·, ·〉 from D; R← Ea∼πΨ(·|s)[qθ(s, a)− α2(1−γ)2 |πΨ(s, a)− π̂D(s, a)|]; Ψ′ ← Ψ′ +∇θ′R;
end // update value function while θ′ not converged do
Sample 〈s, a, r, s′〉 from D; L← (r + γEa′∼πΨ(·|s′) [ qθ(s ′, a′)− α2(1−γ)2 |πΨ(s ′, a′)− π̂D(s′, a′)| ] − qθ′(s, a))2;
θ′ ← θ′ −∇θ′L; end θ ← θ′
end return π;
One important nuance of proximal algorithms is that the optimal policy may not be deterministic, since the penalty term is minimized when the policy matches the empirical policy, which may itself be stochastic. It is not enough to select πt+1(s) = arg maxa∈A v(s, a); we must instead select πt+1(·|s) = supπ∈Π vπ(s) = supπ∈Π ∑ a∈A π(a|s)v(s, a)− α 2(1−γ)2 |π(a|s)− π̂D(a|s)|, which is a more difficult optimization problem. Fortunately, it has a closed-form solution. Proposition 1. Consider any state-action values q and empirical policy π̂D. Let
z := max a∈A q(〈s, a〉)− α (1− γ)2
. The policy πlocalopt given by πlocalopt(a | s) = { π̂D(a | s) + (1−∑a′ s.t. q(〈s,a′〉)>z π̂D(a′ | s)) if a = arg maxa′∈A q(〈s, a〉), π̂D(a | s) if q(〈s, a〉) > z, 0 otherwise.
has the property∑ a∈A πlocalopt(a|s)q(〈s, a〉)− α 2(1− γ)2 |πlocalopt(a|s)−π̂D(a|s)| ≥ ∑ a∈A π(a|s)q(〈s, a〉)− α 2(1− γ)2 |π(a|s)−π̂D(a|s)|
for all s ∈ S, π ∈ Π.
Proof. We provide a brief outline of the proof. Consider any policy π 6= πlocalopt in some state s. First, assume that exactly two cells of π(s) − πlocalopt(s) are non-zero, meaning that one term is x
and the other is −x (since both distributions sum to 1). If |x| > 0, the change in penalized return is non-positive, so π is worse that πlocalopt. To see this, we simply consider all possible mappings between x,−x and actions. Actions fall into three categories, corresponding to the three cases of the construction: argmax-actions, empirical-actions, and zero-actions, respectively. It’s easy to check each case, moving probability mass from any category of action to any other, and see that penalized return is always non-positive. Finally, if more than two cells of π(s)− πlocalopt(s) are non-zero, we can always rewrite it as a sum of positive/negative pairs, and thus the overall change in penalized return is a sum of non-positive terms, and is itself non-positive.
This closed-form can be used anytime the action space is discrete, in both the tabular and neural proximal algorithms. (In the neural algorithm, it replaces the need to optimize Ψ for a parameterized policy πΨ.)

heading: E RELATED WORK
text: Bandits. Bandits are equivalent to single-state MDPs, and the fixed-dataset setting has been studied in the bandit literature as the logged bandit feedback setting. Swaminathan & Joachims (Swaminathan & Joachims, 2015) describe the Counterfactual Risk Minimization principle, and propose algorithms for maximizing the exploitation-only return. The UA pessimistic approach discussed in this work can be viewed as an extension of these ideas to the many-state MDP setting.
Approximate dynamic programming. Some work in the approximate dynamic programming (ADP) literature (Munos, 2007) bears resemblance to ours. The setting is very similar; both FDPO and ADP are a modified version of dynamic programming in which errors are introduced, and research on algorithms in these settings studies the emergence and propagation of those errors. The key difference between the two settings lies in the origin of the errors. In ADP, the source of these errors is unspecified. In contrast, in this work, we focus specifically on statistical errors: where they emerge and what their implications are.
Off-policy evaluation and optimization. The problem of off-policy reinforcement learning is typically posed as the setting where the data is being collected by a fixed stationary policy, but an infinite stream of data is being collected, so statistical issues introduced by finiteness of data can be safely ignored. This is clearly closely related to FDPO, but the focus of our work lies precisely on the statistical issues. However, there are close connections; for example, Jiang and Huang Jiang & Huang (2020) show that in the off-policy function approximation setting, algorithms may obey a version of the pessimism principle in order to select a good approximation.
Exploration. Since acting pessimistically is the symmetric opposite of acting optimistically, many papers which study exploration leverage math which is nearly identical (though of course used in an entirely different way). For example, the confidence intervals, modified Bellman equation, and dynamic programming approach of Strehl & Littman (2008) closely mirror those used in the UA pessimistic algorithms.
Imitation learning. Imitation learning (IL) (Hussein et al., 2017) algorithms learn a policy which mimics expert demonstrations. The setting in which these algorithms can be applied is closely related to the FDPO setting, in that IL algorithms map from a dataset of trajectories to a single stationary policy, which is evaluated by its suboptimality. (However, note that IL algorithms can be applied to a somewhat more general class of problems; for example, when no rewards are available.) In the FDPO setting, IL algorithms are limited by the fact that they can never improve on the quality of the empirical policy. In contrast, pessimistic FDPO algorithms will imitate the dataset when other actions are uncertain, but are also sometimes able to deviate and improve.
Safe reinforcement learning. The sub-field of safe reinforcement learning studies reinforcement learning algorithms with constraints or guarantees that prevent bad behavior from occurring, or reduce it below a certain level (Thomas et al., 2019). To this end, many algorithms utilize variants of pessimism. Our contribution distinguishes itself from this line of work via its focus on the
application of pessimism for worst-case guarantees on the more standard objective of expected suboptimality, rather than for guarantees on safety. However, there is a close relationship between our work and the algorithms and theory used for Safe RL. One popular framework is that of robust MDPs Givan et al. (1997); Nilim & El Ghaoui (2005); Weissman et al. (2003); Iyengar (2005), an object which generalizes MDPs to account for specification uncertainty in the transition functions. This framework is closely related to the pessimistic approaches described in this work. In fact, the UA pessimistic approach is precisely equivalent to constructing a robust MDP from data using concentration inequalities, and then solving it for the policy with the optimal performance under an adversarial choice of parameters; this algorithm has been used as a baseline in the literature but not studied in detail Ghavamzadeh et al. (2016); Laroche et al. (2019). Additionally, the sub-problem of Safe RL known as conservative policy improvement focuses on making small changes to a baseline policy which guarantee that the new policy will have higher value Thomas et al. (2015b;a); Ghavamzadeh et al. (2016); Laroche et al. (2019); Simão et al. (2019); Nadjahi et al. (2019), which bears strong resemblance to the proximal pessimistic algorithms discussed in this work.
Apprenticeship learning. In the apprenticeship-learning setting (Walsh et al., 2011; Cohen & Hutter, 2020), an agent has the choice to take an action of its own selection, or to imitate a (potentially non-optimal) mentor. The process of determining whether or not to imitate a mentor is similar to determining whether or not to imitate the behavior policy used to collect the data. As a result, the underlying principle of pessimism is relevant in both situations. However, the setting of apprenticeship learning is also different from that of FDPO in several ways (availability of a mentor, ability to collect data), and so prior works do not provide a clear analysis of the importance of pessimism in FDPO.
Proximal algorithms. Several approaches to online deep reinforcement learning, including TRPO and PPO, have been described as “proximal” (Schulman et al., 2015; 2017). These algorithms are derived from CPI (Kakade & Langford, 2002), which also introduces a notion of conservatism. In that body of work, this refers to the notion that, after each policy update, the resulting policy is close to the previous iterate. In contrast, the proximal algorithm described in this work is proximal with respect to a fixed policy (typically, the empirical policy defined by the dataset). The contrast between the importance of pessimism in these two cases can be seen by comparing the settings. CPItype algorithms use pessimism to ensure that the policy remains good throughout the RL procedure, guaranteeing a monotonically-increasing performance as data is collected and the optimal policy is approached. Whereas, FDPO proximal approaches have no guarantees on the intermediate iterates, but rather, use pessimism to ensure that the final policy selected is as close to optimal as possible.
Deep learning FDPO approaches. Recently, deep learning FDPO has received significant attention (Agarwal et al., 2019; Fujimoto et al., 2019; Kumar et al., 2019; Laroche et al., 2019; Jaques et al., 2019; Wu et al., 2019; Kidambi et al., 2020; Yu et al., 2020; Wang et al., 2020; Kumar et al., 2020; Liu et al., 2020). At a high level, these works are each primarily focused around proposing and analyzing some specific method. In contrast, the objective of this work is theoretical: we focus on providing a clean mathematical framework through which to understand this setting. We now provide specific details for how our contribution relates to each of these works.
The algorithms introduced in Fujimoto et al. (2019); Laroche et al. (2019); Kumar et al. (2019); Jaques et al. (2019); Liu et al. (2020); Kumar et al. (2020) can all be viewed as variants of the proximal pessimistic approach described in this paper. The implementations vary in a number of ways, but at its core, the primary difference between these algorithms lies in the choice of regularizer: KL, MMD, scalar penalty, or hard constraint. This connection has also been noted in Wu et al. (2019), which provides a unifying algorihtmic framework for these approaches, BRAC, and also performs various empirical ablations. Interestingly, all of these regularizers can be expressed as upper-bounds to TVS(π, π̂D), and as such, our proof of the suboptimality of proximal pessimistic algorithms can be used to justify all of these approaches. One aspect of our contribution is therefore providing the theoretical framework justifying BRAC. Furthermore, conceptually, these works differ from our contribution due to their focus on error propagation; in contrast, our results show that poor suboptimality of naı̈ve algorithms is an issue even when there is no function approximation error at all.
Wang et al. (2020) provides an alternative algorithm for pessimistic FDPO, utilizing a policygradient based algorithm instead of the value-iteration-style algorithms in other related work. Similarly to Kumar et al. (2019), this approach utilizes a policy constraint to prevent boostrapping from actions which are poorly represented in the training data. However, this difference is purely algorithmic: since the fixed-point found by the optimization is the same, this algorithm can also be justified by our proximal pessimistic suboptimality bounds.
Model-based methods (Yu et al., 2020; Kidambi et al., 2020) have recently been proposed which implement pessimism via planning in a pessimistic model. This procedure can be viewed as learning a model which defines an implicit value function (derived from applying the planner to the model), and from there defines an implicit policy (which is greedy with respect to the implicit value function). The implicit value functions learned by the algorithms in Yu et al. (2020); Kidambi et al. (2020) obey the same fixed-point identity as the solutions to the UA pessimistic approach discussed in our work. Thus, both of these works are implementations of UA pessimistic approaches, and our UA pessimistic suboptimality bound can be viewed as justification for this family of algorithms. However, both of these works rely on ensembles to compute the uncertainty penalty, which is not a theoretically well-motivated technique.
The work of Agarwal et al. (2019) provides empirical evidence supporting the claims in this paper. The authors demonstrate that on realistic tasks like Atari, naı̈ve algorithms are able to get good performance given an extremely large and diverse dataset, but they collapse on smaller or less exploratory datasets. It also highlights the difficulties that emerge when function approximation is introduced. Certain naı̈ve algorithms can be seen to still sometimes collapse when datasets are large and diverse, because of other instabilities associated with function approximation.

heading: F EXPERIMENTAL DETAILS

heading: F.1 TABULAR
text: The first set of experiments utilize a simple tabular gridworld. The state space is 8x8, and the action space is {UP, DOWN, LEFT, RIGHT}. Rewards are Bernoulli-distributed, with the mean reward for each state-action sampled from Beta(3,1); transitions are stochastic, moving in a random direction with probability 0.2; the discount is .99. This environment was selected to be simple and generic. We compare the performance of four approaches: imitation, naı̈ve, uncertainty-aware pessimistic, and proximal pessimistic. The imitation algorithm simply returns the policy which takes actions in proportion to their observed frequencies in the dataset. For the UA pessimistic algorithm, we use the technique described in Appendix B.1 to implement Bellman uncertainty functions. For both pessimistic algorithms, we absorb all constants into the hyperparameter α, which we selected to be α = 1 for both algorithms by a simple manual search. For state-actions with no observations, we select rD uniformly at random in [0, 1], PD transitions uniformly at random, and π̂D acts uniformly at random. We report the average of 1000 trials. The shaded region represents a 95% confidence interval.

heading: F.2 DEEP LEARNING
text: The second setting we evaluate on consists of four environments from the MinAtar suite (Young & Tian, 2019). In order to derive a near-optimal policy on each environment, we run DQN to convergence and save the resulting policy. We report the average of 3 trials. The shaded area represents the range between the maximum and minimum values.
We implement deep learning versions of the above algorithms in the style of Neural Fitted QIteration (Riedmiller, 2005). In this setting, we implement only proximal pessimistic algorithms. To compute the penalty term, we must approximate π̂D; this can be done by training a policy network on the dataset to predict actions via maximum likelihood. Just as in the tabular setting, we absorb all constant coefficients into our pessimism hyperparameter, here setting α = .25.
All experiments used identical hyperparameters. Hyperparameter tuning was done on just two experimental setups: BREAKOUT using = 0, and BREAKOUT using = 1. Tuning was very minimal, and done via a small manual search.

heading: G ADDITIONAL CONTENT

heading: G.1 AN ILLUSTRATIVE EXAMPLE
text: Consider the following problem setting. We are given an MDP with a single state and some number of actions, each of which return rewards sampled from a Bernoulli distribution on {0, 1}. (An MDP with a single state is isomorphic to a multi-armed bandit.) Furthermore, for each action, we are given a dataset containing the outcomes of some number of pulls. We are now given the opportunity to take an action, with the goal of maximizing our expected reward. What strategy should we use?
One obvious strategy is to estimate the expected reward for each action by computing its mean reward in the dataset, and then select the arm with the highest empirical reward. However, in certain problem instances, this “naı̈ve strategy” fails. We can illustrate this with a simple example (visualized in Figure 3). Consider an MDP with a single state and 1000 actions. Let the reward distribution of the first action have mean of 0.99, while the reward distributions of all other actions have means of 0.01. Construct a dataset for this bandit by pulling the first arm 10000 times, and the other arms 1 time each.
Although this problem seems easy, the naı̈ve algorithm achieves close to the worst possible performance. It’s clear that in this problem, the best policy selects the first action. The empirical estimate of the mean of the first action will be less than 1 with probability 1− 2× 10−44, and there will be at least one other action which has empirical mean of 1 with probability 1− 4× 10−5. Thus, the first action is almost never selected.
This issue can be resolved by identifying a fundamental failing of the naı̈ve approach: it ignores epistemic uncertainty around the expected return of each action. In order to guarantee good performance on all problem instances, we need to avoid playing actions that we are uncertain about. One way to do this is to construct a high-probability lower bound on the value of each action (for example using concentration inequalities), and select the action with the highest lower bound. If we consider the upper and lower bounds as defining the set of possible “worlds” that we could be in, acting according to the lower bound of every arm means acting as though we are in the worst possible world. In other words: being pessimistic.
The above example may seem somewhat contrived, due to the enormous size of the action space and skewed data collection procedure. However, we argue that it serves as a good analogy for the more common setting of an MDP with many states and a small number of actions at each state. Roughly speaking, selecting an action in a one-state MDP is analogous to selecting a deterministic policy in a multi-state MDP, and the number of policies is exponentially large in the size of the state space. Additionally, it’s very plausible in practical situations that data is collected according to only a small set of similar policies, e.g. expert demonstrations, leading to skewed data coverage.

heading: G.2 EXTREME PESSIMSIM: VALUE LOWER BOUND ALGORITHMS
text: We begin with a simple corollary to Lemma 1. Consider any value-based FDPO algorithm whose value function is guaranteed to always return values which underestimate the expected return with high probability.
Corollary 1 (Value-lower-bound-based FDPO suboptimality bound). Consider any value-based fixed-dataset policy optimization algorithm OVB, with internal fixed-dataset policy evaluation subroutine E , which has the lower-bound guarantee that E(D,π) ≤ vπM with probability at least 1− δ. For any policy π, dataset D, denote vπD := E(D,π). With probability at least 1 − δ , the suboptimality of OVB is bounded by
SUBOPT(OVB(D)) ≤ inf π
( Eρ[v π∗M M − v π M] + Eρ[vπM − vπD] ) Proof. This result follows directly from Lemma 1, using the fact that vπD − vπM ≤ 0.
This bound is identical to the term labeled (A) from Lemma 1. The term labeled (B), which contained a supremum over policies, has vanished, leaving only the term containing an infimum. Where the bound of Lemma 1 demands that some condition hold for all policies, we now only require that there exists any single suitable policy. It is clear that this condition is much easier to satisfy, and thus, this suboptimality bound will typically be much smaller.
A value lower-bound algorithm is in some sense the most extreme example of a pessimistic approach. Any algorithm which penalizes its predictions to decrease overestimation can be described as pessimistic. In such cases, (B) will be decreased, rather than removed entirely. Still, any amount of pessimism reduces dependence on a global condition, decreasing overall suboptimality.
Furthermore, blind pessimism is not helpful. For example, one could trivially construct a value lower-bound algorithm from a naı̈ve algorithm by simply subtracting a large constant from the naı̈ve value estimate of every policy. But this would achieve nothing, as the infimum term would immediately increase by this same amount. To yield a productive change in policy, pessimism must instead vary across states in an intelligent way.

heading: G.3 PRACTICAL CONSIDERATIONS
text: Through the process of running experiments in the deep learning setting, the authors noted that several aspects of the experimental setup, which have not been addressed in previous work, had surprisingly large impacts on the results. In this section, we informally report some of our findings, which future researchers may find useful. Additionally, we hope these effects will be studied more rigorously in future work.
The first consideration is that performance is highly nonmonotonic with respect to training time. In almost all experiments, it was observed that with every target-network update, the performance of the policy would oscillate wildly. Even after performing many Bellman updates, few experiments showed anything resembling convergence. It is therefore important that the total number of steps be selected beforehand, to avoid unintentional cherry-picking of results. Additionally, one common trend was for algorithms to have high performance early on, and then eventually crash. For this reason, it is important that algorithms be run for a long duration, in order to be certain that the conclusions drawn are valid.
The second consideration is the degree to which the inner-loop optimization process succeeds. If throughout training, whenever we update the target network, its error is low, convergence near to the fixed point is guaranteed (Antos et al., 2007). However, computational restrictions force us to make tradeoffs about the degree to which this condition is satisfied. Experimentally, we found this property to be very important: when the error was not properly minimized, performance was negatively impacted, sometimes even leading to divergence. There are three notable algorithmic decisions which we found were required to ensure that the error was adequately minimized.
The size of the network. It is important to ensure that the network is large enough to reasonably fit the values at all points throughout training. Most prior works (Kumar et al., 2019; Fujimoto et al., 2019; Kumar et al., 2020) utilize the same network architecture as the original DQN (Mnih et al.,
2015), which is fairly small by modern standards. We found that this size of network was adequate to fit MinAtar environments, but that decreasing the size of the network further led to significant performance degradation. Preliminary experiments indicated that since the full Atari environment is much more complex than MinAtar, a larger network may be required.
The amount of training steps in the inner loop of Neural Fitted Q-Iteration. If the number of steps is too small, error will not be adequately minimized. In our experiments, approximately 250,000 gradient steps per target update were required to consistently minimize error enough to avoid divergence. We note that many prior works (Kumar et al., 2019; Fujimoto et al., 2019; Kumar et al., 2020) do not adjust this hyperparameter; typical results in the literature use fewer than 10,000 gradient steps per update.
The per-update initialization of the network. When changing the target network, we are in essence beginning a new supervised learning problem. Thus, to ensure that we could reliably find a good solution, we found that we needed to fully reinitialize the neural network whenever we updated the target network. The dynamics of training neural networks via gradient descent are still not fully understood, but it is well known that the initialization is of great importance (Hu et al., 2020). It has been observed that certain initializations can seriously impact training: for example, if the final parameters of a classifier trained on randomly-relabeled CIFAR classifier are used as the initialization for the regular CIFAR classification task, the trained network will have worse test-set performance.9
9Chelsea Finn, Suraj Nair, Henrik Marklund; personal communication.

Review summaries:
The paper proposes a theoretical framework for analyzing the error of reinforcement learning algorithms in a fixed dataset policy optimization (FDPO) setting.  In such settings, data has been collected by a single policy that may not be optimal and the learner puts together a model or value function that will have explicit or implicit uncertainty in areas where the data is not dense enough.  The authors provide bounds connecting the uncertainty to the loss.  They then show that explicitly pessimistic algorithms that fill in the uncertainty with the worst case can minimize the worst case error.  Similarly, proximal algorithms that attempt to adhere to the collection policy (as often the case in model-free batch RL) have improved error compared to a naive approach but not as good as an explicitly pessimistic approach.

The message of this paper is that naive policy evaluations common in current (deep) RL algorithms, can lead to a dangerous overestimation of the value function. This overestimation of the value function can then lead to policy improvements with poor theoretical guarantees. To combat overestimation, the authors propose to penalize state-action pairs that are rarely visited. As an easier to implement alternative, and closer to existing algorithms in the literature, the authors also study another penalty term that penalizes deviation from the data generating policy. The authors show on a numerical example that the more principled penalty term that depends on visitation counts is better performing, and that the proximal penalty term only yields minor improvements over imitation learning (i.e. returning the data generating policy).

This paper attempts to unify prior work on fixed-dataset (aka "batch" or "offline") reinforcement learning. Specifically, it emphasizes the importance of pessimism to account for faulty over-estimation from finite datasets. The paper shows that naive algorithms (with no pessimism) can recover the optimal policy with enough data, but do so more efficiently. The pessimistic algorithms are divided into "uncertainty-aware" and "proximal" algorithms where the uncertainty-aware algorithms are shown to be more principled, but most prior work falls into the computationally easier proximal family of algorithms that is closer to imitation learning. These insights are proven both theoretically and with some small experiments.