The Importance of Pessimism in Fixed-Dataset Policy Optimization
Authors: Jacob Buckman
Carles Gelada
Marc G Bellemare
Venue: ICLR 2021 Poster (2021)
Keywords: deep learning
reinforcement learning
offline reinforcement learning

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 naive 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.

Under review as a conference paper at ICLR 2021
THE IMPORTANCE OF PESSIMISM IN FIXED-DATASET POLICY OPTIMIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
We study worst-case guarantees on the expected return fixed-dataset policy optimization algorithms. Our core contribution is unified conceptual and mathe- matical framework for the study of algorithms this regime. This analysis reveals that for na've approaches, the possibility of erroneous value overestimation leads to a difficult-oo-satiffy 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 possi- ble world. We show why pessimistic algorithmss 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 tabular gridworld, and deep learning experiments on four MinAtar environments.
INTRODUCTION
We consider fixed-dataset policy optimization (FDPO), in which a dataset transitions from an envi- ronment is used to find policy with high return 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 maximize worst-case performance, good FDPO algorithm should select a policy with high worst-cas cosst-case value. We call this the pessimism principle of exploita- tion, it is analogous to the hidely-known optimism principle (Lattimore & Szepesvári 2020) of exploration
Our main contribution is theoretical justification of the pessimism principle in FDPO, based 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 the specific setting of FDPO, An example conveying the intuition behind our results can be found in Appendix G.I
set of theoretical results rigorously explaining how pessimism important in
We first analyze a family of pen--eesimmstic naive FDPO algorithms, which estimate the environ- ment from the dataset via maximum likelihood and then apply standard dynamic programming tech- niques. 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 value of every possible policy. This is caused by the outsized impact of value overestimation errors on suboptimality, sometimes called the optimizer's 's curse (Smith & Winkler 2006). 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.
We the term fixed-datase policy optimization emphasize the computational procedure: this setting has also been referred to batch RL. (Ermst al. 2005 Lange et al. 2012)) and more recently, offline RI. (Levine) ct al. 2020). We emphasize that this is a stul-studied setting, and we are simply choosing to refer to by more descriptive name.
The optimism principle states that should select policy with high best-case value.

---

Under review as a conference paper at ICLR 2021
We contrast these findings with analysis of pessimistic FDPO algorithms, which select 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 the deep learning setting. Recently, several deep-learning-basee baannnngg algorithms for fixed-dataset policy optimization have been proposed (A Aggawal
al., 2019 Fujimoto al. 2019, Kumar al., 2019 [Lrroche et al. 2019; Jaques et 2019
Kidambi ct 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
(Yonng & 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 large body of work which contains ideas related to those discussed in this paper. We discuss these works in detail in Appendix
BACKGROUND
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 Here, briefly give an informal overview of the background necessary understand the main results.
We represent the environment as Markov Decision Process (MDP), denoted M (S, R,P. Y, p). We assume without loss of generality that (((ssa)) E [o, IJ. and denote its expectation r( a(), p represents the start-state distribution. Policies π can act in the environ- ment, represented by action matrix A", which maps each state to the probability of each state-action when following æ. Value functions assign some real value to each state. We use Vi to denote the value function which assigns the sum of discounted rewards in the environment when following policy æ. dataset 1) contains transitions sampled from the environment. From a dataset, we can compute the empirical reward and transition functions, D'D and Pp. and the empirical policy, fD.
An important concept for our analysis the value uncertainty function, denoted μh.8. which returns a eigh-probability upper-boune bound the error of a value function derived from dataset D. 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 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, fixed-point equation defines a FDPE objective, which in turn defines value-based FDPO objective; we call the set of all algorithms that implement these objectives the family of algorithms defined by the fixed-poit equation.
3 OVER/UNDER DECOMPOSITION OF SUBOPTIMALITY
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 -xtasett policy evaluation algorithum & on any dataset D and any policy x. Denote Vī := E(D,T) T). We define the underestimation error as Ep[vM - vb] and overestimation error as E VV - v.l
The following lemma shows how these quantities can be used to bound suboptimality.
2

---

Under review as a conference paper at ICLR 2021
Lemma (Value-based FDPO suboptimality bound). Consider any value-based fixed-datase policy optimization algorithm O with fxed-datasee policy evaluation subroutine &. For any policy a and dataset D, denote vb == E(D, TT. The suboptimality of OVB is bounded by
SUBOPT(O" - inf (Eplv" vül E vbl)
sup E -vvll)
Proof. See Appendix C.1
This bound is tight; see Appendix overestimation on the suboptimality FDPO algorithm. To see this, we consider each its terms in isolation:
The bound highlights the potentially outsized impact of
(A
(x2)
(nl)
SUBOPT(OV"(DD S
inf
R
vil + R Vv
vb]
+ sup
R
P v
(A)
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 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 from these two terms that errors of overestimation and underestimation have differing im- pacts on suboptimality, suggesting that algorithms should be designed with this asymmetry in mind. We will see in Section[5]hov this may be done. But first, let us further understand why this is neces- sary by studying in more depth a family of algorithms which treats its errors of overestimation and underestimation equivalently.
NAÏVE ALGORITTMS
The goal of this section is to paint high-level picture of the worst-case suboptimality guarantees of specific family of non- pessimistic approaches, which we call naive FDPO algorithms. Informally, the naïve approach to take the limited dataset observations at face value, treating it as though paints fully accurate picture of the environment. Naïve algorithms construct a maximum-likede likelihood MDP from the dataset, then use standard dynamic programming approaches on this empirical MDP.
Definition 2. naive algorithm is any algorithm in the family defined by the fixed-poing function
fnavve (v") ArD )PDV")
Various FDPE and FDPO algorithms from this family could be described; in this work, we do not study these implementations detail, although we do give pseudocode for some implementations in Appendix D.
One example of a naive FDPO algorithm which can be found in the literature certainty equivalence [Tang 2019a). The core ideas behind naïve algorithms can also be found in the function approxima- tion literature, for example FQI (Ernst et al.) 2005 Jiagg 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 al.) 2015) with a fixed replay buffer is naïve value-based FDPO algorithm.
Theorem (Naive FDPO suboptimality bound). Consider any naive bastee-baeddaae
pol-
icy optimization algorithm VHI Let μs be any value uncertainty function. With probability at least 1 - 8, the suboptimality of O naive is bounded with probability at least 1 - by
naive
SUBÖPT VB nodive (D)) S inf (Bplvit - -vxl - BBlHb.ss) + sup Bp
3

---

Under review as a conference paper at ICLR 2021
Proof. This result follows directly from Lemma and Lemma]
The infimum term is small whenever there some reasonably good policy with low value uncer- tainty. In practice, this condition can typically be satisfied, for example by including expert demon- strations in the dataset. On the other hand, the supremum term will only be small if we have low value uncertainty for all policies
much more challenging requirement. This explains the behav- ior of pathological examples, e.g. in Appendix [.I] where performance is poor despite access to virtually unlimited amounts of data from 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 large.
However, although pathological examples exist, it is clear that this bound will not be tight on all environments. 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, 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 poorly most real-world environments as they do on pathological examples. Consider: there are many more policies than there is data, 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 real-world settings, overestimation has been widely observed, typically correlated with poor performance (Bellemare et al. 2016 Van Hasselt al. 2016, Fujimoto et al.) 2019).
THE PESSIMISM PRINCIPLE
"Behave as though the world was plausibly worse than you observed it to be." The pessimism prin- ciple tells us how to exploit our current knowledge to find the stationary policy with the best worst- case guarantee 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, a, controlling the amount of pessimism, interpolating from fully-naive 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-awe awwre family of methods.
5.1 UNCERTAINTY AWARE PESSIMISTIC ALGORITHMS
Our first family of pessimistic algorithms is the uncertainty--wwrre (UA) pessimistic algorithms. As the name suggests, this family of algorithms estimates the state-wise Bellman uncertainty and penalizes policies accordingly, leading pessimistic value estimate and preference for policies with low value uncertainty.
Definition 3. An uncertainty- pessimistic algorithm, with Bellmun uncertainty function u and pessimism hyperparameter E 1). is any algorithm in the family defined by the fixed-point function
fua (v AT + -
This fixed-point function is simply the na've fixed-point function penalized by the Bellman uncer- tainty. 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 [.]]] in order to get concrete algorithm. It is straightforward to construct algorithms from this family by modifying naive 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 nigh-probabiling performance guarantees are useful in the context of ensuring safety.
4

---

Under review as a conference paper at ICLR 2021
Theorem (Uncertainty-awarc pessimistic FDPO suboptimality bound). Consider uncertainty- aware pessimistic value-based fixed fixed-datasel policy optimization algorithm Dua Let 4DD be any Bellman uncertainty function, Phss
be corresponding value uncertainty function, and E [0, 1] be any pessimism hyperparameter. The suboptimality of O is bounded with probability at least 1 - 5 by
O0 (D)) inf (Eply -vål +1++(1+a)) -pplub,)) + (1 (L-a). (sup Eplub,ol
Proof. See Appendix
C.7
This bound should be contrasted with result from Theorem With 0, the family of pessimistic algorithms reduces to the family of naive algorithms, so the bound is correspondingly identical. We can add pessimism by increasing a, and this corresponds decrease in the magni- tude of the supremum term. When a = 1, there is no supremum term at all. In general, the optimal value of a 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 small number of expert trajectories but also 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 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 simi- larly to the expert data.
5.2 PROXIMAL PESSIMISTIC ALGORITHMS
The next family algorithms we study are the proximal pessimistic algorithms,, which implement pessimism by penalizing policies that deviate from the empirical policy. 'he name proximal was chosen 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-proposee deep learning algorithms (Fujimoto et al. 2019 Kumar et al. 2019; Laroche et al.) 2019 Jaques et al,, 2019 Wu al. 2019: Liu 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 condicoon action density, be found in Appendix C.9
Definition 4. A proximal pessimistic algorithm with pessimism hyperparameter E [0, 1] is any algorithu in the family defined by the fixed-point function
Sprosmmat (v") = ArD + +PDv") - ( (1-7)² (
[V)(TT
Theorem (Proximal pessimistic FDPO suboptimality bound). Consider any proximal pessimistic value-based fxed-datased policy optimization algorithm Q Opeaximatt Let μ be any state-action-wise decomposable value uncertainty function, and a [o, 1] be a pessimism hyperparameter. For any dataset D, the suboptimality of D is bounded with probability least 1 by
(V)()t
SUBOPT(O proximal D))= I inf BBIl v-ul + Ep
D.5 - a(T 771"
(1-7)²
TVD
sup x
E
1D.8 - a(I - -
(1 7)²
Proof. See Appendix C.8
Once again, see that a grows, the large supremum term shrinks; similarly, by Lemma when we have a = 1, the supremum term is guaranteed to be non-positive The primary limitation of
Initially, it will contain p. hut this can he removed since it is dependent on
5

---

Under review as a conference paper at ICLR 2021
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 -visted 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 converge the optimal policy. Also, note that when a 2 1 1-7, 7 this algorithm is identical to imitation learning.
5.3 THE RELATIONSHIP BETWEEN UNCERTAINTY-AWAR AND PROXIMAL ALGORITHMS
Though these two families may appear on the surface to be quite different, they are in fact closely related. A key insight of our thcoretical work is that it reveals the important connection between these two approaches. Concretely: proximal algorithms are uncertainty-awant algorithms which use trivial value uncertainty function.
To see this, we show how to convert an incertainty-wwar penalty into a proximal penalty, let μu be any date-action-wiss decomposable value uncertainty function. For any dataset D, we have
AD DDs DDD6 (T- PA> (1A5- - >PDMB.
(Lemma
S D + +I- (V)((T,T)) (1- (1-Mp)
(Lemma
We began with the uncertainty penalty. In the first step, we rewrote the uncertainty for ı into the sum of two terms: the uncertainty for f.. and the difference in uncertainty between т and tD on various actions. In the second step, chose state-action-we action-wise Bellman uncertainty to be T which trivial upper bound; also upper-bound bound the signed policy difference with the total variation. This results in the proximal penalty
Thus, see that proximal penalties equivalent uncertainty-awarc penalties which use spe- cific, trivial uncertainty function. This result suggests that uncertainty 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-ave -wware 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 the trivial uncertainty function. Until we discover how to compute uncertainties for neural networks, proximal pessimistic algorithms will remain the only theoretically family of algorithms.
EXPERIMENTS
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 un- certainty. This means that when the data is collected from any destriiddteriiiistiic policy, performance of this algorithm will be poor, since many states will be missing data. Stochas- tie data collection improves performance. As the size of the dataset grows, this algorithm approaches optimality.
Uncertainty-awaree This algorithm performs well when there is data on states visited by near-optimal policies. This is the case when 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 approaches optimality. This approach outperforms all other approaches.
'When constructing the penalty, we ignore the first term, which does not contain and so is irrelevant optimization.

---

Under review as a conference paper at ICLR 2021
Policy
Optimal Palicy
Imitation
FDPO
Pessimisiic FDPD
Pessimbtiic FDPO
Tabular Gindworld
Tabular Grldworld
60-
Sare
50-
0.8
cf eigrwdy data collection poicy
of Frammes dalaset
(a) Performance of FDPO algorithms on datasct of 2000 transitions, as the data collection policy is interpolated from random to optimal.
(b) Performance FDPO algorithms as dataset size increases. Data collected with an optimal e-greedy policy, with e = 50%.
Figure 1: Tabular gridworld experiments.
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 opti- mality, as the penalty persists even when the environment's 's dynamics are perfectly captured by the dataset.
Proximal.
Our experimental results qualitatively align with our predictions in both the tabular and deep learn- ing settings, giving evidence that the picture painted by our theoretical analysis truly describes the FDPO setting. See Appendix D for pscudocode of all algorithms; see Appendix 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: gi github. com/ anonymi zed
Tabular. The first tabular experiment, whose results shown in Figure I(a) compares the per- formance of the algorithms as the policy used to collect the dataset is interpolated from the uniform random policy to optimal policy using e-greedy. The second experiment, whose results shown in Figure [[b]] compares the performance of the algorithms as we increase the size of the dataset from sample 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 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 near-optimal policy, but also learns to improve upon 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 naive approach performing near-optimalyy for intermediate values e.
7 DISCUSSION AND CONCLUSION
In this work, we provided conceptual and mathematical framework for thinking about fixed-dataset policy optimization. Starting from intuitive building blocks of uncertainty and the over-under de- composition, we showed the core issue with naïve approaches, and introduced the pessimism princi- ple as the defining characteristic of solutions. We described two families pessimistic algorithms, uncertainty- aware and proximal. We see theoretically that both of these approaches have advan- tages over the naive approach, and observed these advantages empirically. Comparing these two families of pessimistic algorithms, both theoretically and empirically that uncertainty-aware

---

Under review as a conference paper at ICLR 2021
Asterix
Breakout
Frecway
Space Invadors
20
60
10-
15-
50-
60
Intation
Proximal Possimatic
30
40
20-
10
1.0
0.8
0.0
1.0
0.2
0.0
1.0
0.4 0.2
0.0
1.0
0.4 0.2 0.0
collection policy
cigreddyyy sata collection policy
data collection policy
Figure 2: Performance of deep FDPO algorithms on a dataset of 500000 transitions, as the data collection policy is interpolated from near-optimal to random. Note that here, the only pessimistic algorithm evaluated is proximal.
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- deep learning algorithms. As is evidenced by 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 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 tempting to propose various ad- hoc 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 a; however, doing the tuning requires evaluating each policy in the environment, which involves gaining information by interacting with the environment, which not permitted by the problem setting. Or, might consider e.g. 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 uncertainty function, which point we may well just use uncertainty-aware algorithm.
Stochastic policies. One surprising property of pessimsitic algorithms is that the optimal policy often stochastic. This 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 -enedeerriiiitic 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 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 replay buffer to break the correlation between samples in each minibatch (Mmih et al.) 2015). However, since these algorithms typically alternate between collecting data and training the network, the replay buffer can also be viewed as 'temporarily fixed' dataset during the training phase. These algorithms are often very sensitive to hyperparemters; poorly when the number of learning steps per interaction is large (Fedus al.) 2020). This effect can be explained by our analysis: additional steps of learning cause the policy to approach its naive FDPO fixed-poe fixed-point, which has poor worst-case suboptimality. A pessimistic algorithm with better fixed- fixed-point 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 RI..
particular, they perform
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. Striving for simplicity in off- 2019.
deep reinforcement learning. arXiv preprint
András Antos, Csaba Szepesvári, and Rémi Munos. Value-iteration based fitted policy iteration: learning with a single trajectory. In 2007 IEEE international symposium approximate dynamic programming and reinforcement learning, pp. 330-337. IEEF, 2007.
Mare Bellemare, Georg Ostrovski, Arthur Guez, Philip Thomas, and Rémi Munos. Increasing the action gap: New operators for reinforcement learning. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In Proceedings of the International Conference on Machine Learning, 2019.
Michael K Cohen and Marcus Hutter. Pessimism about unknown unknowns inspires conservatism. In Conference on Learning Theory, pp. 1344-13255 1373. PMLR, 2020.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning- Journal of Machine Learning Research, 6:503-556, 2005.
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. arXiv preprint arXiv:2007.06700, 2020.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052-2062, 2019.
Mohammad Ghavamzadeh, Marek Petrik, and Yinlam Chow. Safe policy improvement by minimiz- ing robust baseline regret. Advances in Neural Information Processing Systems, pp. 2298-2306, 2016.
Robert Givan, Sonia Leach, and Thomas Dean. Bounded parameter markov decision processes. In European Conference on Planning, pp. 234-246. Springer, 1997.
Vineet Goyal and Julien Grand-Clement. Robust markov decision process: Beyond rectangularity. arXiv preprint arXiv: 10XIv:8111.001111 2018
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in opti-
mizing deep lincar networks. arXiv preprint arXiv:2001.0500 200-0999..99,,, 2020.
Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR). 50(2):135, 2017.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv: 009900000566,.. 2019.
Nan Jiang. Note on certainty equivalence, 2019a.
Nan Jiang. Note on fqi. 2019b.
Nan Jiang and Jiawei Huang. Minimax confidence interval for off-policy evaluation and policy optimization. arXiv preprint arXiv:2002.02081, 2020.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pp. 267-274, 2002.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims, Morel: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951 2020.

---

Under review as a conference paper at ICLR 2021
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off- off-policy q-learning via bootstrapping error reduction. Advances in Neural Information Processing Sys- tems, pp. 11794, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 04779, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. Reinforcement learning, pp. 45-73, 2012.
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning, pp- 3652-36611 2019.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01644 2020.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202. 2020.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. arXiv preprint arXiv:0907.37400 2009.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):52-533. 2015.
Rémi Munos. Performance bounds in Lp-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-561, 2007.
Kimia Nadjahi, Romain Laroche, and Rémi Tachet des Combes. Safe policy improvement with soft baseline bootstrapping. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 53-68. Springer, 2019.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley &amp; Sons, 2014.
Martin Riedmiller. Neural fitted q iteration foeration-first experiences with data efficient neural reinforce- ment learning method. European Conference on Machine Learning, pp. 317-328. Springer, 2005.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization, In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy 2017.
optimization algorithms. arXiv preprint
Thiago Simão, Romain Laroche, and Rémi Tachet des Combes. Safe policy improvement with estimated baseline policy. arXiv preprint arXiv:1909.05236 2019.
James E Smith and Robert L Winkler, The optimizer's 's curse: Skepticism and postdecision surprise in decision analysis. Management Science, 52(3):311-335 2006.
Alexander L. Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-133) 2008.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1):1731-175,, 2015.
10

---

Under review as a conference paper at ICLR 2021
Majid Alkaee Taleghan, Thomas G Dietterich, Mark Crowley, Kim Hall, and H Jo Albers. Pac optimal mdp planning with application to invasive species management. The Journal of Machine Learning Research, 16(1):3877-3903, 2015. 2015.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy improvement. In International Conference on Machine Learning, pp. 2380-2388, 2015a.
Philip S Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off- policy evaluation. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015b.
Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468):999- 1004, 2019.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Thirtieth AAAI conference on artificial intelligence, 2016.
Thomas J Walsh, Daniel K Hewlett, and Clayton T Morrison. Blending autonomous exploration and apprenticeship learning. In Advances Neural Information Processing Systems, pp. 2258-2266, 2011.
Ziyu Wang, Alexander Novikov, Konrad Zoina, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, et al. Critic regularized regression. arXiv preprint arXiv:2006.15134 2020.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. In- equalities for the I1 deviation of the empirical distribution. NeeleettPackard Labs, Tech. Rep, 2003.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathe- matics of Operations Research, 38(1):153-183, 2013.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arX.v: 2019.
Kenny Young and Tian Tian. Minatar: atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv: 030000033766.. 2019.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005. 13239, 2020.
A BACKGROUND
We write vectors using bold lower-case letters, a, and matrices using upper-case letters, A. To refer to individual cells of vector or rows of a matrix, we use function notation, a(x). We write the identity matrix as I. We use the notation E-1-1 denote the average value of a function under distribution p, i.e. for any space X, distribution E Dist(X)), and function X + R, we have Ea := =..pa:=E.-ala(()))) [ax))
When applied to vectors or matrices, we use <,>, ,, to denote element-wiss comparison. Simi- larly, we use |. denote the element-wise absolute value of vector: a (x) = |a(=)). We use |a|+ to denote the dlement-wise maximum of and the zero vector. To denote the total variation distance between two probability distributions, we use TV q) p p-q/11 When P and Q are conditional probability distributions, we adopt the convention TV (p, q) ( (p(1z) - q(-[x)) : x E X), i..,
the vector of total variation distances conditioned each X.

---

Under review as a conference paper at ICLR 2021
Markov Decision Processes. We represent the environment with which are interacting Markov Decision Process (MDP), defined in standard fashion: M := (S. R. P.p.. S and A denote the state and action space, which we assume are discrete. We use 2 == SxA as the shorthand for the joint state-action space. The reward function R. 2 -> Dist (0, 1]) maps state-action pairs to distributions over the unit interval, while the transition function P: 2 + Dist(S) maps state-action pairs to distributions over next states. Finally, p E Dist(S) is the distribution over initial states. We use denote the expected reward function, r(ss, a)) := E, (s.a))[r), which can also be interpreted as a vector r E I 2 Similarly, note that P can be described as P: (Z XS) + R. which In order to emphasize that these reward and
can be represented as a stochastic matrix P E R || transition functions correspond to the true environment, we sometimes equivalently denote them as TM: 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, c.g., 1 E Rl and i E R A policy n: S + (is defines distribution over actions, conditioned on state. We denote the space of all possible policies as IT. We define an "activity matrix" for each policy, A E Sx which encodes the conditonn state-action distribution of æ. by letting A (ss, (8, a)) = (a]s) if' 8 = 5, otherwise (s, (8, a)) == O. Acting in the MDP according to π can thus be represented by A E IR Six|s| or PA E IR 22) We define a value function as any w: IT + S - I or q: IT 2 R whose output is bounded by [0, 1 Note that this is slight generalization of the standard definition (Sutton & Barto 2018) since it accepts a policy as an input. We use the shorthand v'' := v(z) 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 E R! and q" E R gl To denote the output of an arbitrary value function on an arbitrary policy, we use unadorned v and q. The expected return of an MDP M, denoted V.M or qM, is the discounted sum of rewards acquired when interacting with the environment:
8
VM = Σ (TAP)) ATT
(M(T) = Σ (yPA")r 1=0
1=0
Note that V = qM: An optimal policy of an MDP, which we denote iM is a policy for which the expected return V.M maximized under the initial state distribution:
TMM == arg max, [v The statewise expected returns of an optimal policy can be written as v "MM
VM Of particular interest
are value functions whose outputs obey fixed-point relationships, v= = =v(v") for some f (S - R) + (S + R). The Bellman consistency equation for a policy т, B% (x) == Ar (xx)) which uniquely identifies the vector of expected returns for т,, since VM is the only vector for which VM = M (v²) holds. Finally, for any state 8, the probability of being in the state s' after / time
steps when following policy is ([*s,)" s'). Furthermore, E (T)T)) (1 7
We refer to (I - P) as the discounted visitation of π.
Datasets. We next introduce basic concepts that are helpful for framing the problem of fixed- dataset policy optimization. We define dataset of d transitions D == {(s,a, a, s')] 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 aate-actions reached by following some stationary policy. We use D ~ &a to denote constructing a dataset of d tuples (s, a, r, 8'), by first sampling each {s, a) Tb and then sampling and s' i.i.d. from the environment reward
function and transition function respectively, i.e. each r ~ R(-Ks,, (s) and s' ~ P(-1(s, a) 5 We sometimes index D using function notation, using D(s, a) denote the multiset of all (r,s') such that (s, a, s')) (ss a)-- We sometimes use state-wise versions of these vectors, which we denote with up. It further useful to consider the maximum- likelhoood 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)) a)) = Er.L'E(((saa) [D((s.))) and empirical transition
D. We use ün I |1 denote the vectors of counts, that is, in a)) ==
matrix (p(s'((s,a) d)) = (r. 1(d'=s') at all state-actions for which in((s, a)) > 0. Where with üp ((s a)) = 0, there is no clear way define the maximum-likelihone estimates of
[[[[s,]]]]
'Note that this is in some sense a simplifying assumption. In practice. datasets will typically be collected using trajectory from non-stationary policy, rather than i.i.d. sampling from the stationary distribution of stationary policy. This greatly complicates the analysis, so do not consider that setting in this work.
12

---

Under review as a conference paper at ICLR 2021
do not specify them. All our results hold matter how these values are chosen, so long as rD E [0, T-y1 and PD is stochastic. The empirical policy of a dataset D is
reward and transition,
defined as (als) == [ except where (i 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 Pn replacing P. i.e. 7--AA"
[P(()))]]
Problem setting. The primary focus of this work is the properties of fixed-dataset policy op- timization (FDPO) algorithms. These algorithms take the form of function O 'D + II, which maps from dataset to a policy 66 Note that in this work, consider random variable, and therefore (D) is also a random variable. The goal of any FDPO algorithm to output policy with minimum suboptimality, i.c. maximum return. Suboptimality dom 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,
4a. the dataset is
ran-
SUBOPT(O((D) = Ep 1 Eplv M.
A related concept is the fixed-dataset policy evaluation algorithm, which is any function & 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/ value-based FDPO algorithm with FDPE subroutine Emb is any algorithm with the following structure:
O (D) arg max E (D, x)]
We define a sixed-point family of algorithms, sometimes referred to as just a family, in the following way. Any family called family is based a specific fixed-poine identity ftamily. We use the notation Etaiiyy to denote any FDPE algorithm whose output v := Etamity (D, π) obeys v = framity (v7, Finally, Ommyyy refers to any value-based FDPO algorithm whose subroutine is &tamily. We call the set of all algorithms that could implement Etamily the family of FDPE algorithms, and the set of all lamily as the family of FDPO algorithms.
algorithms that could implement O
B UNCERTAINTY
Epistemic uncertainty measures an agent's knowledge about the world, and is therefore core con- cept in reinforcement learning, both for exploration and exploitation; it plays an important role in this work. Most past analyses in the literature implicitly compute tainty 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 tion exists, and provide the remainder of our technical results under such an assumption. We also describe several approaches to computing uncertainty.
form of epistemic uncer-
function with certain properties, then assume that such a func-
Definition 5 (Uncertainty)) A function up.s Z I is state-action wise Bellman uncertainty function if for a dataset D ~ Da obeys with probability at least 1 - for all policies π and all values v:
uD,s 2 (rM +PPMv (TD + +PPpv)
"This formulation hides a dependency on p. the start-state distribution of the MDP. In general, P can be estimated from the datasct D, but this estimation introduces some error that affects the analysis. In this work, assume for analytical simplicity that p is known a priori. Technically, this means that it must be provided as input O. We hide this dependency for notational clarity.
"Intuitively, these algorithms use policy evaluation subroutine to convert a dataset into value function, and return an optimal policy according to that value function. Importantly, this definition constrains only the objective of the approach, 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 [.] Furthermore, model-based techniques can be interpreted as using model to implicitly define value function, and then optimizing that value function; our results also apply to model-based approaches.
its actual algorithmic implementation, i.e., it includes algorithms which
13

---

Under review as a conference paper at ICLR 2021
A function ub.8 S + I is state-wise Bellman uncertainty function if for dataset D
Dd
and policy n, it obeys with probability at least 1 - 8 for all policies a and all values v:
D 2 A (TM + pPMv) A (TD + +DDDv
A function DD. S - R is value uncertainty function for dataset D ~ Da and policy n, it obeys with probability al least 1 for all policies and all values v:
Σ (TA*PD) A (rM + 7PMM) A (rD+>PPVV) km
D.5
We refer to the quantity returned by an uncertainty function as uncertainty, e.g., value uncertainty refers to the quantity returned by value uncertainty function.
Given a state-action wise Bellman uncertainty function up,á. easy to verify that A up, is a state-wise Bellman uncertainty function. Similarly, given state-wise Bellman uncertainty function b, it is easy to verify that (I - - PD) D is value uncertainty function. Uncertainty functions which can be constructed in this way are called decomposable.
Definition 6 (Decomposabliltty> wise decomposable if there exists a state-action-wise Bellman uncertainty function up,5 such that p,s uD,5 A value uncertainty function μ is state-wise decomposable if there exists state- wise Bellman uncertainty function 7h,s such that μ = (1 7-7A "uh and further, it is state-action-wit decomposable if that D is itself state cnte-acctionwise decomposable.
state-wise Bellman uncertainty function D is state-action-
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 our intuitions about uncertainty? An application of the environment's '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 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 these errors over all future timesteps.
How we algorithmically implement uncertainty functions? In other words, how compute a function with the properties required for Definition [S] 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.
trivial approach to computing any uncertainty function is simply to return بيب for all 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. is very loose and so leads to poor guarantees.
In tabular environments, one way to implement Bellman uncertainty function is use concen- tration inequality. Depending which concentration inequality is used, many Bellman uncertainty functions are possible. These approaches lead to Bellman uncertainty which lower at states with more data, typically in proportion to the square root of the count. To illustrate how to do this, show Appendix B. how a basic application of Hoeffding's 's inequality can be used to derive a state-action-wis Bellman uncertainty. In Appendix B.2 show an alternative application of Ho- effding's 's which results state-wise Bellman uncertainty, which 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 neural network, is not currently known how to im- plement Bellman uncertainty function. When empirical Bellman update is applied to neural
14

---

Under review as a conference paper at ICLR 2021
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 cap- ture something analogous to an intuitive notion of uncertainty; however, none are principled enough to be useful in computing Bellman uncertainty.
B.1 STATR-ACTION-WE WISE BOUND
We seek to construct ub,s such that |A (rM +7PMV) A (rD + 2 u , with probability least 1 1 d.
Firstly, let's consider simplest possible bound. v is bounded [0, - so both A (TM + PPMV) and A (rD + 7PDv) must be as well. Thus, their difference is also bounded:
|A (rm + + A" (rD > 1-7
Next, consider that for any (s, a), the expression rD( a)) PPo((s, a))v² can be equivalently expressed as an expectation of random variables.
rd((s, a)) + 7PD((s a)) n)'ED((s..))
E
rv
each with expected value
(D((e.() +v('s)) EB Bi + = [rm + P(sy)((s.))). )'>(((().o))
Note also that each these random variables is bounded [0, --: 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 s at each of the |S A| state-actions, and taking a union bound, we see that with probability at least
2 A
(IM + 7PMV) - (rD +
6
We can left-multiply A and rearrange get:
2/5 A
A (TD + >DVM))
1ー In
A A
8
Finally, we simply intersect this bound with the probability at least 1- ō,
bound from earlier. Thus, we see that with
(A + 7PMM) - AF 7PDD+ T- min ((22 2/5 x A|
A
8
B.2 STATE-WISE BOUND
This bound similar to the previous, but uses Hoeffding's 's to bound the value at each state all at once, rather than bounding the value each state-action.
Choose a collection possible state-local policies II C (A). Each state-local policy is member of the action simplex.
For any & E S and π E T the expression [A"(rD + (PD))](s) can be equivalently expressed mean of random variables,
Taass)
[A (rD + (sv))) in(s) a.
Σ
(r rv('))). #D(a|s)
15

---

Under review as a conference paper at ICLR 2021
each with expected value
x(als) (b(a)s) (r + rv(')))
(())))
amx()1e) (()
[A PPMV)(()))
s'-P(1(8.e0)
Note also that each of these random variables is bounded [0, T-q [ Thus, Hoeffding's in- equality tells that this sum of bounded random variables must be close its expectation with high probability. By invoking Hoeffding's at each of the |S] states and [[laaal local policies, and taking a union bound, see that with probability at least -- 6,
1 <(ale)
1 - 1-
2 1laaaa (AT)o2nn)
IA (rM 7PMV) A 7
where the term (o refers to the elementwise square. Finally, we once again intersect with 1 1-7² yielding that with probability at least - -,
1 1-7
1 V In
2 x Нocal
(A7 + A
( (rD + <PDVMd
min
(A*)02nn)
8
Comparing this to the Bellman uncertainty function in Appendix B.1
two differences. Firstly,
we have replaced factor of [A]] with [[ocaal typically loosening the bound somewhat (depending on choice of considered local policies). Secondly, A has moved inside of the square root; since the square root is concave, Jensen's inequality says that
( s (2A i AT
and this represents tightening of the bound.
When Toaal is the set deterministic policies, this bound equivalent to that of Appendix [B. This can easily be seen by noting that for deterministic policy, all elements of (A*)o² are either or O, and so
V (A A
and also that the size of the set of deterministic policies 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 single state and two actions og, a1, and dataset with ip(((s, an)) = nn (s, a1)) 2. We can parameterize the policy by a single number E [0, 1] by setting т (ao) s) = <, (ails) = 1 - &. The
size of this bound will be proportional to / + (1-E)² and setting the derivative equal to zero, we see that the minimum & = 1 (Of course, we would need to increase the size of our local policy set include this, in order be able to actually select it, and doing 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 algo- rithms which leverage this bound for future work.
B.3 OTHER BOUNDS
There are few other paths by which this bound can made tighter still. The above bounds take an extra factor of I- because we bound the overall return, rather than simply bounding the reward and transition functions. This was done because bound on the transition function would add cost of O(VS). However, this can be mitigated by intersecting the above confidence interval with Good- 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 relatively deterministic. We expect this be the case for most practical MDPs.
16

---

Under review as a conference paper at ICLR 2021
Similarly, empirical Bernstein confidence intervals can be used in place of Hoeffding's 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 com- pute 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 eisitation-weighted sum. This would result in an overall tighter bound on value uncertainty by hedg- ing 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 ABpendix[B.]]ee
be seen as constructing an sa- rectangular robust MDP, whereas Appendix [8.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.
C
PROOFS
C.1 PROOF OF OVER/UNDER DECOMPOSITION
Starting from the definition of suboptimality, we see
SUBÖPT(OVB (D)) Epl Eplv
EEpl + (-vō + v + vDD
5o DD vM
(valid for any m)
- E - Eplv v6 - -V
(using BpIVD - S 0)
Since the above holds for m
SUBOPT(OVM (D))
< inf BBIV vbl) + E.IV v
< inf Eppv vbl) + sup [pplv] vūl)
(using v Tb 1I)
= inf E vill + E vbl) + sup Sup(E,113 -vx)
C.2 TIGHTNESS OF OVER/UNDER DECOMPOSITION
We show that the bound given in Lemma is tight via simple example.
Proof. Consider a bandit- structured MDP with a single state and two actions, A and B, with rewards of O and respectively, which both lead to terminal states.
First, consider the left-hand side. 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 clearly equal to 1. This is clearly the worst-case subop- timality, since it is the largest possible suboptimality in the environment.
On the right-hand side, note that term (A) is O when n is the policy that always picks B, while term (B) is when is the policy that always picks A. Thus, the left-hand and right-hand sides are equal, and the bound tight.
C.3 RESIDUAL VISITATION LEMMA
We prove a basic lemma showing that the error of any value function 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 n. consider the Bellman skedd-point& equation given by, let v be defined the unique value vector such that v
A (rş + PP PE)) and let v be any other value
17

---

Under review as a conference paper at ICLR 2021
vector. We have
VE - == (4= -v)
(1)
Vē = P[) (r; +P(p))
(2)
IV v/= =I P
-vl
(3)
Proof.
A (r + 7P&v) v A"(re + PP(V) V + V -
Ar' + .P(V) - (r + tPP(2?) + + -v
=>AFpplV -v?) + +( v)
=(vē -VV -7A"Pp(V v)
-1I->A-PE((E v)
Thus, see PA-A (A - An identical proof can be completed starting with AT(r: + PPpv). leading the desired result.
C.4 NAIVE FDPE ERROR BOUND
We show how the emror of naive FDPE algorithms is bounded by the value uncertainty of state- actions visited by the policy under evaluation. Next, in Section we use this bound to derive a suboptimality guarantee for naive FDPO.
Lemma 3 (Naive FDPE error bound). Consider any naive fixed-dataset policy evaluation algo- rithm Enoive- For any policy π and dataset D, denote vD == Enaive π). Let pb, be any value uncertainty function. The following component-wii wise bound holds with probability at least
V
4b.6
Proof. Notice that the naïve fixed-point function is equivalent to the Bellman fixed-point equation for specific MDP: the empirical MDP defined by AS, PD.7,P) Thus, invoking Lemma 2 for any values v we have
VVD (1- PA (r + +>PDv) v/-
Since VMM a value vector, this immediately implies that
Vb vul = - PD) + + - vāl-
Since VM the solution the Bellman consistency fixed-point,
|v vMl = - -1-) + 7PDv)) - A (r. + + P
Using the definition of a value uncertainty function bb, we arrive
VV v.l S 4D.5
completing the proof.
Thus, reducing value uncertainty improves guarantees evaluation enror. 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-uncertain states can be evaluated with lower error
*In 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 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.
18

---

Under review as a conference paper at ICLR 2021
Our bound differs from prior work (Jiang 2019a Ghavamzadeh et al. 2016) in that it is significantly more fine- grainedi We provide a component wise bound on error, whereas previous results bound the Lo norm. Furthermore, our bounds sensitive to the Bellman uncertainty in each individual reward and transition, rather than only relying on the most-uncertain. As 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 also be viewed an extension of work approximate dynamic programming. In that setting, the literature contains fine-grained results on the accumulation of local errors (Munos) p.07j. However, those results are typically understood as applying to errors induced by approxima- tion 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.
C.5 RELATIVE VALUE UNCERTAINTY
The key the construction of proximal pessimistic algorithms is the relationship between the value uncertainties of any two policies म; T², for any state-action-wise decomposable value function.
Lemma 4 (Relative value uncertainty). For any two policies n, ,. and any state-action-wise de- composable value uncertainty Ja. have
bb.s 1b.ss -I--7-Pp)-- ((AT ((AT-1 ( +PDDb)s)
Proof. Firstly, note that since the value uncertainty function is state-action-wise decomposable, can express it in a Bellman-like form for some state-wise Bellman uncertainty 4 as 14 = (I (p))A"Pp) uhss- Further, hhs is itself state-action-wise decomposable, so it can be written Db,5 A up,8.
We can use this to derive the following relationship.
pbD - PA> 4
Pb.5 7PD A" pb.5 ub,s
pb.5 ub,s + 7 PDDD.
Next, we bound the difference between the value uncertainty of π and n'.
DD5 PDbs (ub.s + + (4%,5 7AT PDMDD
=(ub,s -1 + PD 71² PDHT'S
= -AAT -A )up, + P PD - 7AA A + A PDMTT
= PDA"PD (Hb.S 1D. + +(1 -A" -A'')DD, +7AA" - AT ) PDH
PD 14.88 1D.5) + -AA=-A") >u')(un,s + +PPDuT.s)
This is a geometric series, so (I 7A" fb. - -bb.) (A* A AF')(u,,s + >PoHT deft-multpplying by (I Pp) we arrive the desired result.
C.6 NAIVE FDPE RELATIVE ERROR BOUND
Lemma 5 (Naive FDPE relative error bound). Consider any naive fixed-dataset policy evaluation algorithm Enavee For any policy and dataset D, denote vT := Enaive (D, Then, for any other policy n², the following bound holds with probability least 8:
VI vMl S PD. S PDD (1 PD)
TVs(T,
(1-
19

---

Under review as a conference paper at ICLR 2021
Proof. The goal of this section is construct error bound for which optimize without needing to compute any uncertainties. To do this, we must replace this quantity with a looser upper bound.
First, consider a state-actionwins decomposable value uncertainty function HD. We have WB,5 (I (1->PpA") D for some D where " = u for some up
Note that state-action action-wise Bellman uncertainty can be trivially bounded as up,s S I-7 1 1-y; any slate-action-wise decomposable value uncertainty can be trivially since (T (T->PDAAT bounded as bb6 S (1-7)²
1 i. Also,
We now invoke Lemma 4 We then substitute the above bounds into the second term, after ensuring that all coefficients are positive.
DD 4D.6 = PD) -1 (A - ( + <PDH
< (1->)""D)) -1 [14T ( +PPDMb.
(1 (1-7A"PD)*
1 1
1
i
Pp
1-9
(1 7)2
= =(I-7A"PD)*
[AT - 17
1
7
1-9
(1 7)=
= =II -
1
AA A
(1 7)2
1
= =(1-7A"PD)
TVS(T,
(1 11-7) 7)²
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 | is precisely equivalent to the state-wise total variation distance, TVs(T, x'). Thus, we have
(1-22² TVs(T,
1
4b.6 S 15,0 + (I-
Finally, invoking Lemma
we arrive at the desired result.
C.7 SUBOPTIMALITY OF UNCERTAINTY-AWAR PESSIMISTIC FDPO ALGORITHMS
Let vD (D, From the definition of the UA family, have the fixed-point property
vb = (TD + + ?PDvb) au and the standard geometric series rearrangement yields vī = (I >A"Pp) (A -au From here, we see:
vI = (I -I- P (A"DD aub.5))
= - -1->AA"Pp) -1 ATID - (1 - PA=PPp" aup.5
= Enave (D, T) a4D.5
We now use this bound overestimation and underestimation error of (m,(D, T) by invoking Lemma which holds with probability at least 1 - 8. First, for underestimation, we see:
ViM vB vM (Eniive (1, 04p1)
(VM Enive (D, (D,T)) + 04p48,8
< pD. + a4p..6
+ a)bbs
and thus, viu - vI S (1 + at (0)p 1..8 Next, for overestimation, we see:
vi viu (Ensive (D. -.)p.,)) viM
20

---

Under review as a conference paper at ICLR 2021
(E (D, TT
-v:) appi
I PD.s a44...
(1 a..55.65
and thus, vD - vi & (1 a) Substituting these bounds into Lemma gives the desired result.
C.8
SCROPTIMALITY OF PROXIMAL PESSIMSITIC FDPO ALGORITHMS
Let vD Eproximat (D, T). From the definition of the proximal family, we have the fixed-point property
vn = ArD ( +> - (Vs((T, #D)
(1 7)2
and the standard geometrie series rearrangement yields
(Vs(T, TD) (1- (1-
))
v -1= (ATD
From here,
vD = (I (1- AATDD a (TVs( 2n))
(1 (1-
(TVs(T, AD)
(I 71-AAA PD) A'TD -1=
71-
(TV)(TT
Enive (D. PD)
(11-))²
Next, we define a new family of FDPE algorithms,
Eproximal-tun (D, (D, (MO's (15:++1--000 (1-77APp)
(TV: (1-
TV (Vs( AD)
We use Lemma 3 which holds with probability at least - 5, to bound the overestimation and underestimation. First, the underestimation:
TVs(a, aD) (iii-(emmiin (Ennvel (D, un + (1-
VM Eun (D, viu -
(1 77)
(TV #D)
(vM - EDaveeD, + uD.8 + (1-
(1-
(TV)(TT #D)
S 4b.s + a + ( -1- (711-))
Next, we analagously bound the overestimation:
VM (E,niv(D, ( (1I (T (TVs(T,AD))
71 )) V
Eproximal- (D,x)
(1b's
(T 2D)
(vM - Enavee π))
1bb's + -1 (1-
(1 (1-7)2
$ 4D.8 a (1 (1 (TV)((, #DD)
We can now invoke Lemma to bound the suboptimality of any value-based FDPO algorithm which uses Eprssimal-fll- which we denote with proximal-full Crucially, note that since au4 is not depen- dent on π, it can be removed from the infimum and supremum terms, and cancels. Substituting and rearranging, we that with probability least 1 ó,
VB
-vll + E, + - (VV((T. TD)
( ))
SUBOPT(OVB 2 froximal-full (D)) & inf TE
(1-7)²
21

---

Under review as a conference paper at ICLR 2021
(TV (TVs( TD)
(1- )
Ep lubs-a(l abb-a(1-74PP3)
+ sup
Finally, we see that FDPO algorithms which use Eproximal-full their subroutine will return the same policy as FDPO algorithms which use Eproiimll- First, we once again use the property that 1D is not dependent on Second, note that since the total visitation of every policy sums to T-y.
know Ep (T PD" (:) (1-2)² for all и, and thus it also not dependent on πτ
arg max | (Epoxiimalllllll (D, m]] = arg max E. Enane (D, - HDD -a(H5' + (1 7A) -1
TVs(T, TD)
(1 7)2
7
x
arg max E, Enarve Chawe(D,,s (D, - Pp) (VV TD)) (1 712
arg max E proximal (D,
Thus, the suboptimality of arg max, Erroiimil (D, m)] must be equivalent that of arg max EppEproximatifil D, r)) leading to the desired result.
C.9 STATE-WISE PROXIMAL PESSIMISTIC ALGORITHMM
In the main body of the work, we focus on proximal pessimistic algorithms which are based on state-conditional density model, since this approach is much more common in the literature. How- ever, also possible 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, := -AT indicate the state visitation distribution of any policy π.
Definition 7. state-action-densiyy proximal pessimistic algorithm with pessimism hyperrrmmmeer E [0, 1] is any algorithm in the family defined by the fixed-point function
d d
fsad-proximal = AID + >PDD** a
(1-7)² 7)2
Theorem desate-action-eeeee proximal pessimistic FDPO suboptimality bound). Consider any state-action-density proximal pessimistic value-based fixed-dataset policy optimization algorithm Duad praximaaaama Let μ be any state-action-ue wise decomposable value uncertainty function, and a E [0, 1] be a pessimism hyperparameter. For any dataset D. the suboptimality of OYB probability at least 8 by
preximal is bounded with
1d de ++
SUBOPT(O sad-pproximal (D)) S 2E, 1 d.l + iif
EppivM vāul + (1+a) EEp
(1 (1-yATPD)-
(1 - 7)2
(a- Ep
d - d I+ (1-7)²
+ sup
(1- 7A (P)-A-P))-
Proof. First, note that for any policies x', and any state-action aatteaction-wise decomposable value uncer- tainty is with state-action Bellman uncertainty up.5 $ 1-7 1, we have
Db.5 4D.5 = (1 PA" A -1-7A" PD) -b)- up.
1
(d dx.) A up,5
<
|d= d= + upu
1
|d+ dr
(1 7)2
Ide ie-dippl+ The remainder of the (1-7)²
Invoking Lemma we see that lvī - v
< 1T S DDD
proof follows analogously to Appendix C.8
22

---

Under review as a conference paper at ICLR 2021
D ALGORITHMS
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) detail. The sets of algorithms described here are not intended to be comprchensive, but rather, few straightforward examples illustrate key concepts and inspire further research. To simplify presentation, we avoid hyperparameters, e.g. learning rate, wherever possible.
D.1 NAĪVE
The naive algorithms presented here are simply standard dynamic programming approaches applied to the empirical MDP construced from the dataset, using rD, Pp in place of P. See PPteerman (2144) for analysis of convergence, complexity, optimality, etc. the general dynamic program- ming approaches, and note that the empirical MDP is simply particular example of an MDP, so all results apply directly.
Algorithm 1: Tabular Fixed-Dataset Policy Evaluation
Input: Dataset D. policy म, discount 7 Construct rp, Pn as described in Section 2
- (T PD) A"rp;
return
Algorithm 2: Tabular Dates-Dtttset Policy Iteration
Input: Dataset discount ?. Initialize т, v Construct rD, PD as described in Section 2 while not converged do arg m A (rD + PPDD); I| argmax policy is state-wise max action
v - (1 - 7A A"rD:
end
return .,;
Algorithm 3: Tabular Fixed-Dataset Value Iteration
Input: Dataset D, discount ?. Initialize म, v Construct rp, PP as described in Section while not converged do
π + arg max A Il argmax policy is state-wise max action TD + >PDA"v;
end return
Algorithm 4: Neural Dateset Value Iteration
Input: Dataset D. discount n Initialize 0, 8' while not converged do
for each in D do
(8)) <- arg max a))
end
while 0' not converged do
Sample (s, s,)" from D; - (r + ( qo (s, a));
8' L;
end
8 4 0'
end
return m
23

---

Under review as a conference paper at ICLR 2021
D.2 PESSIMISTIC
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 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 wise and independent between states. Thus, performing a local greedy policy improvement in any 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).
D.2.1 UNCERTAINTY-AWAR
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 Dataset Policy Iteration
Input:
Dataset D, discount y, rate 8, pessimism parameter
Initialize v, π Construct rp. Pp. üp as described in Section
Compute 2D,5 described in Appendix B
while not converged do arg +ax ( a,
+ (I - >A=PA (A"rD au
end return m
Algorithm 6: Neural Uncertainty-ANe Pessimistic Fixed-Datase Value Iteration
Input: Dataset D, discount y, pessimism hyperparameter a. Initialize 0, 0', W/;
while 0 not converged do
I/ update policy
while v not converged do
Sample (s, .)) from D;
E (a (s) - au (s);
T Vo R:
end
update value function
while 0' not converged do Sample (s, a, r,,rss)) from D; (r + Eg (a (9o aa)] -au go as)
0' 0 Vo
end
0 4 0'
end
return :o:
As discussed in the main text, count-based Bellman uncertainty functions, such those derived from concentration inequalities Appendix B.T do not apply to non-tabular environments. The correct way compute epistemic uncertainty with neural networks is still an open question. There- fore, our pseudocode for a neural implementation of the UA pessimistic approach is in some sense incomplete: full implementation would need to specify a technique for computing ub,a- We hope that future work will identify such technique.
24

---

Under review as a conference paper at ICLR 2021
D.2.2 PROXIMAL
In this section, we provide pseudocode for member of the proximal pessimsitic family of algo- rithms.
Algorithm 7: Tabular Proximal Pessimistic Fixed-Dataset Policy Iteration
Input: Dataset D, discount ?s pessimism parameter a. Initialize v, π Construct r: PD, in described in Section while not converged do π f- arg a A
2(1-))a # pl): v- -1-1-AAPP (A"rD 2'-ンプア t k
end
return :
Algorithm 8: Neural Proximal Pessimistic Fixed-Datasee Value Iteration, Discrete Action Space
Input: Dataset D, discount "s pessimism hyperparameter a.
Initialize 0, 8,0', WT;
while not converged do
// update policy
while v not converged do
Sample (8, from D:
E Ea (s) 2 マ1- Tv( - f a)]];
V' Vo
end
// update value function while 0' not converged do
Sample (s, a,r,s') from D;
+ (r + (eg'wau(()))) go a') 2(1 2 (x(('ad) - #
g0 (s, a));
+ 0' Lo
end
0 0'
end
return m
One important nuance of proximal algorithms 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 select T (s) arg max, EE ((s, a); we must instead select Te- (-1s) sup v (s) sup EMEA T(als)v(s,d) a) 2ा-ュ | (als) +p(as)) which is more difficult optimization problem. Fortunately, it has closed-form solution.
Proposition 1. Consider any state-action values q and empirical policy t Let
z = max q((s, a))
a
aeA
71-
The policy Tlocalopt given by
a 5) + +(1 (1- (1- {((an))) Ap(a' |s)
ifa arg argmax.eed a((s,a)),
Toocalop (a () =
t s)
if (f(( > otherwise.
has the property
Tiocalop (a) A
Σ
2(1 7)2 Mlocntopr (als) (p)s)= 2 Σ (c()s) 2(1 7) ( IT(als) (als))
8EA
for all s E SS
Proof. We provide a brief outline of the proof. Consider any policy π + Thocalopt in some state s.
First, assume that exactly two cells of π (s) Moccllop (s) are non-zero, meaning that term
25

---

Under review as a conference paper at ICLR 2021
and the other is -z (since both distributions sum to 1). If |x| O, the change in penalized return is non-positive, so π is worse that Tiocalopt- To see this, we simply consider all possible mappings between 2, 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 any other, and that penalized return is always non-positive. Finally, if more than two cells of T(s) [ecalopp(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 sum of non- non-positive terms, and is itself non-positive.
This closed- 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 TT)
E RELATED WORK
Bandits. Bandits equivalent to single-state MDPs, and the fixed-dataset setting has been stud- ied in the bandit literature as the logged bandit feedback setting. Swaminathan & Joachims (Swami-) nathan & 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 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 re- search 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 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 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 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 (020) show that in the off-policy function approximation setting, algorithms may obey version of the pessimism principle in order to select 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 (0088 closely mirror those used in the UA pessimistic algorithms.
Imitation learning. Imitation learning (IL) (ussein 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 II algorithms map from a dataset of trajectories to a single stationary policy, which is evaluated by its suboptimality. (However, note that II. algorithms can be applied to 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 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 vari- ants of pessimism. Our contribution distinguishes itself from this line of work via its focus the
26

---

Under review as a conference paper at ICLR 2021
application of pessimism for worst-case guarantees the more standard objective of expected sub- optimality, 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 & Hl Ghaoui (2005); Weissman et al. (2003); [yengar| (2005), an object which generalizes MDPs to account for specification uncertainty 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 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 base- line policy which guarantee that the new policy will have higher value Thomas et al. (2015b a); Ghavamzadeh et al. (2016); Laroche et al. (2019); Simã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 (poten- tially non-optimal) mentor. The process of determining whether or not to imitate a mentor similar to determining whether or not to imitate the behavior policy used to collect the data. As result, the underlying principle of pessimism relevant both situations. However, the setting of apprentice- ship learning is also different from that of FDPO in several ways (availability of 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. contrast, the proximal algorithm described in this work is proximal 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. CPI- type algorithms use pessimism to ensure that the policy remains good throughout the RL procedure, guaranteeing a aomooonically-inerasiiii approached. Whereas, FDPÓ proximal approaches have guarantees on the intermediate iterates, but rather, use pessimism to ensure that the final policy selected is as close to optimal as possible.
with respect
performance as data is collected and the optimal policy is
Deep learning FDPO approaches. Recently, deep learning FDPO has received significant atten-
tion (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 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); y; Kumar et al. (2019); Jaques al. (2019); Liu 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 its core, the primary difference between these algorithms lies in the choice of regu- larizer: KL. MMD, scalar penalty, or hard constraint. This connection has also been noted in Wu al. (2099. 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 TV fD), 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 contribution due to their focus error propagation; in contrast, results show that poor suboptimality of naive algorithms is an issue even when there is no function approximation error at all.
27

---

Under review as a conference paper at ICLR 2021
Wang al. (2020) provides alternative algorithm for pessimistic FDPO, utilizing policy- gradient based algorithm instead of the value-iteration-sty// algorithms in other related work. Simi- larly to Kumar et al. 2019), this approach utilizes policy constraint to prevent boostrapping from actions which are poorly represented in the training data. However, this difference is purely algorith- mic: 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 model which defines an implicit value function (derived from applying the planner 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 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, naive algorithms are able to get good performance given an extremely large and diverse dataset, but they collapse on smaller or less ex- ploratory 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.
F EXPERIMENTAL DETAILS
F.I TABULAR
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 Bemoulli-disribured, with the mean reward for each state-action sampled from Beta(3,1); transitions are stochastic, moving a random direction with probability 0.2; the discount is .9.. This environment was selected to be simple and generic. We compare the performance of four approaches: imitation, naïve, uncertainty- 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. to implement Bellman uncertainty functions. For both pessimistic algorithms, we absorb all constants into the hyperparameter o, which we selected to be = for both algorithms by a simple manual search. For state-actions with no observations, we select rp uniformly at random in [0, 1]. Pp transitions uniformly at random, and Rp acts uniformly random. We report the average of 1000 trials. The shaded region represents a 95% % confidence interval.
pessimistic,
F.2 DEEP LEARNING
The second setting we evaluate on consists of four environments from the MinAtar suite (Young & Tian 2019). In order to derive 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 Q- Iteration (Riedmiller) 2005). In this setting, we implement only proximal pessimistic algorithms. To compute the penalty term, we must approximate tp: this can be done by training a policy net- work on the dataset to predict actions via maximum likelihood. Just as in the tabular setting, absorb all constant coefficients into our pessimism hyperparameter, here setting a = .25.
All experiments used identical hyperparameters. Hyperparameter tuning was done just two exper- imental setups: BREAKOUT using = 0, and BREAKOUT using 1. Tuning was very minimal, and done via small manual search.
28

---

Under review as a conference paper at ICLR 2021
2
1000
μ 99%
1%
1 %
1%
n
10000
1
1
1
DD 98%
0%
100%
0%
Figure 3: Bandit-like MDP, with accompanying dataset. μ gives the true mean each action. np gives the counts of the pulls used to construct dataset D, and μiD gives empirical estimate of the mean reward. On this problem, any algorithm that selects the action with the highest empirical mean reward will almost always pick suboptimal action. In contrast, pessimistic algorithm, which selects the action with the highest lower bound, will almost always pick the correct action.
G ADDITIONAL CONTENT
G.1 AN ILLUSTRATIVE EXAMPLE
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 {0, (An MDP with a single state is isomorphic to a multi-arme 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 re- ward in the dataset, and then select the arm with the highest empirical reward. However, in certain problem instances, this "naive strategy" fails. We can illustrate this with simple example (visual- ized in Figure Consider an MDP with single state and 1000 actions. Let the reward distribution of the first action have mean 0.99, while the reward distributions of all other actions have means of 0.01. Construct dataset for this bandit by pulling the first arm 10000 times, and the other arms time each.
Although this problem seems easy, the naïve algorithm achieves close to the worst possible perfor- mance. 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 I with probability 1 2 10 44 and there will be at least one other action which has empirical mean of with probability action is almost never selected.
x 10-5, Thus, the first
This issue can be resolved by identifying a fundamental failing of the naive approach: it ignores epistemic uncertainty around the expected return of each action. In order to guarantee good per- formance on all problem instances, we need to avoid playing actions that we are uncertain about. One way do this to construct 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 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. 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 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 multi--ttte 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.
29

---

Under review as a conference paper at ICLR 2021
G.2 EXTREME PESSIMSIM: VALUE LOWER BOUND ALGORITTMM
We begin with a simple corollary to Lemma | Consider any value-based FDPO algorithm whose value function is guaranteed always return values which underestimate the expected return with high probability.
FDPO suboptimality bound), Consider any salue-based fixed-datase policy optimization algorithm Q²a with internal fixed-dataset policy evaluation sub- routine &, which has the lower-bound guarantee that E(D, σ) VVM with probability at least 1 - 6. For any policy n, dataset D, denote vh == E(D, T). With probability at least 1 - Ó, the subopti- mality of QBB is bounded by
Corollary 1 (Value-lower-bouue
SUBOPT(Q & inf (Eplv vill + VVV - v3l) -Vbl)
Proof. This result follows directly from Lemma] using the fact that vD VM S 0.
This bound is identical to the term labeled (A) from Lemma [1 The term labeled (B), which con- tained a supremum over policies, has vanished, leaving only the term containing an infimum. Where the bound of Lemma [ 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.
value lower-bound algorithm is in some sense the most extreme example of a pessimistic ap- proach. Any algorithm which penalizes its predictions to decrease overestimation can be described as pessimistic. such cases, (B) will be decreased, rather than removed entirely. Still, any amount global condition, decreasing overall suboptimality.
of pessimism reduces dependence
Furthermore, blind pessimism is not helpful. For example, one could trivially construct a value dower-bounde algorithm from naïve algorithm by simply subtracting a large constant from the naive value estimate of every policy. But this would achieve nothing, as the infimum term would immedi- ately increase by this same amount. To yield productive change in policy, pessimism must instead vary across states in an intelligent way.
G.3 PRACTICAL CONSIDERATIONS
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 nommonotonic 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- 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 long duration, in order to be certain that the conclusions drawn are valid.
of results. Additionally, one common
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 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 DON (Mnih al.
30

---

Under review as a conference paper at ICLR 2021
2013). which is fairly small by modern standards. We found that this size of network 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 too small, error will not be adequately minimized. In our experiments, approximately 250,000 gradient steps per target update were required consistently minimize error enough avoid di- vergence. 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 the literature use fewer than 10,000 gra- dient steps per update.
The per-update initialization of the network. When changing the target network, we are essence beginning a new supervised learning problem. Thus, to ensure that we could reliably find 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). has been observed that certain initializations can seriously impact training: for example, if the final pa- rameters of classifier trained on randomly-relabedd CIFAR classifier are used as the initialization for the regular CIFAR classification task, the trained network will have worse test-set performance
"Chelsea Finn, Suraj Nair, Henrik Marklund; personal communication.
31


Reviews:
[{"review_id": "y1onO5W1NGG", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe 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.\n\n\nReview:\n\nThe paper provides a general description of the pessimism performance bounds.  The theorems appear to be correct and the reasoning sound.  I also like the connection to the proximal approach, which is how most model-free batch RL algorithms approach the problem (by sampling close to the collection policy).\n\nHowever, the paper does need some improvement.  Specifically, a connection should be made to more existing literature on pessimism in safe, batch, or apprenticeship RL.  In addition, the paper spends a lot of time on definitions and notation that are not explicitly used while the most interesting empirical results are relegated to the appendix, which seems backwards.\n\nOn the connections to the literature, the idea of using pessimism in situations where you are learning from a dataset collected by a non-optimal teacher has been investigated in previous works in apprenticeship RL:\nhttp://proceedings.mlr.press/v125/cohen20a/cohen20a.pdf\nor\nhttps://papers.nips.cc/paper/4240-blending-autonomous-exploration-and-apprenticeship-learning.pdf \n\nSpecifically, the first (Bayesian) paper explicitly reasons about the worst of all possible worlds mentioned in the current submission and seems to have a lot of overlap in the theory.  Can the authors distinguish their results from Cohen et al.?  The second paper is an example where model-learning agents keep track of the uncertainty in their learned transition and reward functions and use pessimism to fill in uncertainty.  So the idea here is not quite new and better connections to this literature need to be made.\n\nThe other issue with the paper is its organization and writing. The theoretical results, while general, are not particularly complicated and don’t seem to warrant the amount of notation and definitions on pages 1-3.  Specifically, the bandit example isn’t really mentioned in the paper but the figure takes up a lot of valuable space.  Over a full page is used to define basic MDP and dataset terms that are widely known and commonly used.  The footnotes are whole paragraphs that seem to be just asides.  Finally, the grid word results are presented in a figure without any real associated text except for some generalities about what algorithms worked well,  Meanwhile, the most interesting and novel contributions of the paper, including the concrete algorithms for applying pessimistic learning, and the empirical analysis on Atari games, are stashed in the (very long) appendix.  I strongly suggest the authors reorganize the paper to highlight these strengths instead of notation and footnotes that are tangential to the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eyt6C-TqAg-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:**\n\nThis 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.\n\n--------------------------------------------------------------------\n\n**Strengths:**\n\n1. A nice decomposition of suboptimality. The main workhorse of the paper is the decomposition provided in Lemma 1 which is novel and can provide some good intuition about the necessity of pessimism (although the intuition is only given in appendix G.3, which should definitely find it's way into the main text). The Lemma cleanly and formally demonstrates why we may expect over-estimation to be more damaging than under-estimation.\n2. A clear framework to examine prior work. The paper does well to capture the majority of recent work into a few broad families of algorithms: naive, proximal pessimistic, and uncertainty-aware pessimistic. The bound derived from the main Lemma for each algorithm family provide evidence to prefer uncertainty-aware algorithms. This is supported by the tabular experiments.\n3. The formal statements of Lemmas and Theorems seem to be correct and experimental methodology seems sound.\n\n--------------------------------------------------------------------\n\n**Weaknesses:**\n\n1. I am wary of the comparison of upper bounds done in the paper. Just because one algorithm has a lower upper bound does not prove superior performance. I agree that since all the proofs are derived from Lemma 1 and are very similar, the differences are indeed suggestive. However, the bound in Theorem 3 seems to be more loose than the others. For example, when $\\alpha = 0$ it does not recover the bound for the naive algorithm as would be expected. A more measured tone and careful description of these comparisons is needed. Claims like \"uncertainty-aware algorithms are strictly better than proximal algorithms\" in the conclusion are not substantiated. \n2. Lack of discussion of issues with implementation and function approximation. As the authors get into in Appendix G.6 and Appendix F.2 and briefly in the paper it is not clear how to implement the uncertainty-aware family of algorithms in a scalable way. I am not saying that this paper needs to resolve this issue (it is clearly hard), but this drawback needs to be made more clear in the main text of the paper, so as to not mislead the reader.\n3. Notation is heavy and sometimes nonstandard. I understand that the nature of this paper will lead to a lot of notation, but I think the paper could be made more accessible if the authors go back through the paper and remove notation that may only be needed in the proofs and may be unnecessary to present the main results. For example, the several different notions of uncertainty funtions might be useful in the appendix, but do not seem to all be necessary to present the main results. Similarly, the notion of decomposability is introduced and then largely forgotten for the rest of the paper. Some notation is nonstandard. For example: $d$ is used for number of datapoints (usually it would be dimension) and $ \\Phi$ is used as the data distribution (usually if would be a feature generating function or feature matrix).\n4. Abuse of the appendix. While I understant that the 8 page limit can be difficult, this paper especially abuses the appendix often sending important parts of the discussion and intuition for the results into appendix G. The paper would be stronger with some editing of the notation and organization of the main text to make room for more of the needed discussion and intuition in main body of the paper.\n\n--------------------------------------------------------------------\n\n**Recommendation:**\n\nI gave the paper a score of 7, and recommend acceptance. The paper provides a nice framing of prior work on fixed-dataset RL. While it leaves some things to be desired in terms of carefulness, scalability, and clarity, I think it provides a solid contribution that will be useful to researchers in the field.\n\nIf the authors are able to sufficiently improve the clarity of presentation as discussed in the weaknesses section, I could consider raising my score.\n\n--------------------------------------------------------------------\n\n**Questions for the authors:**\n\n1. It is natural to think that a practical proximal pessimistic algorithm would reduce the level of pessimism with the dataset size (so that it approaches the naive algorithm with infinite data). Do approaches like this resolve many of the issues that you bring up with proximal pessimistic algorithms (albeit by introducing another hyperparameter to tune)?\n\n--------------------------------------------------------------------\n\n**Additional feedback:**\n\nTypos:\n\n- The first sentence on page 4 is not grammatically correct.\n- In the statements of Lemma 1 and Theorem 1, $ \\pi^*_D$ is defined and never used.\n- In the statement of Theorem 1 $ u_{D,\\delta}^\\pi$ is defined but then only $ \\mu_{D,\\delta}^\\pi$ is used without being defined.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_NJ87T34PYO", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nThe main contribution of the paper is to decompose the sub-optimality upper bound into terms that either overestimate or underestimate the total reward that can be collected in the true MDP. The authors argue that the overestimation is especially problematic for (the many) RL algorithms that are subject to such overestimation, as there is a high chance of existence of a policy that performs poorly on the true MDP but has high reward on the empirical MDP (the MDP with empirical estimates of the reward and transitions), resulting in a large sub-optimality. \n\nAs far as I am aware, this decomposition is new. But I wonder if beyond formalizing the sub-optimality of naive algorithms, it has other theoretical or practical applications. The notion of pessimism is typical in the analysis of theoretically grounded algorithms (e.g. CPI in\nApproximately Optimal Approximate Reinforcement Learning, Kakade et al. 2002), where deviation from ‘known’ state-action pairs is typically maximally penalized with the worst possible value (i.e. a sub-optimality of 1 / (1-\\gamma)). So I wonder if the decomposition in overestimation/underestimation terms in Lemma 1 allows for new theoretical insights and algorithmic developments or if it is more of a rewriting, and similar results can be obtained by more carefully choosing the empirical MDP D, such that the overestimation term disappears with high probability even in the worst case and only the underestimation term remains. As is, I understand the reasons for exhibiting both underestimation/overestimation terms in order to analyze ‘naive’ algorithms in the sense of Sec. 4, but is there an advantage for this decomposition and for the algorithm in Sec. 5.1 compared to choosing the optimal policy without an penalty term but in a more carefully constructed MDP D’ that doesn’t allow for overestimation? Similarly, is there any benefit in not choosing \\alpha = 1 in Sec. 5.1? Is there an optimal choice for \\alpha for Sec. 5.2?\n\nAs for the practical implications, the results in Sec. 6 are quite depressing since algorithms with a proximal penalty are easier to implement than with the uncertainty penalty. What was the \\alpha in the experiments? I wonder if the results can be improved for the proximal algorithm if a better choice of \\alpha is used depending on the optimality of the data generating policy or on the size of the dataset.\n\nOverall, the paper is an interesting read and its message is well presented and supported. However, I am wondering if the theoretical contributions can serve another purpose than warning about the poor theoretical guarantees of ‘naive’ algorithms, and hope the authors can correct me if I underappreciated the importance of these derivations.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree in their positive evaluation of the paper. A weakness of the paper pointed out by several reviewers was its presentation, which has hovewer improved. Thus, I'm glad to recommend acceptance.
Decision: Accept (Poster)