  In this paper, we study the offline RL problem with linear function
approximation. Our main structural assumption is that the MDP has low inherent
Bellman error, which stipulates that linear value functions have linear Bellman
backups with respect to the greedy policy. This assumption is natural in that
it is essentially the minimal assumption required for value iteration to
succeed. We give a computationally efficient algorithm which succeeds under a
single-policy coverage condition on the dataset, namely which outputs a policy
whose value is at least that of any policy which is well-covered by the
dataset. Even in the setting when the inherent Bellman error is 0 (termed
linear Bellman completeness), our algorithm yields the first known guarantee
under single-policy coverage.
  In the setting of positive inherent Bellman error
${\varepsilon_{\mathrm{BE}}} > 0$, we show that the suboptimality error of our
algorithm scales with $\sqrt{\varepsilon_{\mathrm{BE}}}$. Furthermore, we prove
that the scaling of the suboptimality with $\sqrt{\varepsilon_{\mathrm{BE}}}$
cannot be improved for any algorithm. Our lower bound stands in contrast to
many other settings in reinforcement learning with misspecification, where one
can typically obtain performance that degrades linearly with the
misspecification error.
