  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.
