  Sample-efficient offline reinforcement learning (RL) with linear function
approximation has recently been studied extensively. Much of prior work has
yielded the minimax-optimal bound of $\tilde{\mathcal{O}}(\frac{1}{\sqrt{K}})$,
with $K$ being the number of episodes in the offline data. In this work, we
seek to understand instance-dependent bounds for offline RL with function
approximation. We present an algorithm called Bootstrapped and Constrained
Pessimistic Value Iteration (BCP-VI), which leverages data bootstrapping and
constrained optimization on top of pessimism. We show that under a partial data
coverage assumption, that of \emph{concentrability} with respect to an optimal
policy, the proposed algorithm yields a fast rate of
$\tilde{\mathcal{O}}(\frac{1}{K})$ for offline RL when there is a positive gap
in the optimal Q-value functions, even when the offline data were adaptively
collected. Moreover, when the linear features of the optimal actions in the
states reachable by an optimal policy span those reachable by the behavior
policy and the optimal actions are unique, offline RL achieves absolute zero
sub-optimality error when $K$ exceeds a (finite) instance-dependent threshold.
To the best of our knowledge, these are the first
$\tilde{\mathcal{O}}(\frac{1}{K})$ bound and absolute zero sub-optimality bound
respectively for offline RL with linear function approximation from adaptive
data with partial coverage. We also provide instance-agnostic and
instance-dependent information-theoretical lower bounds to complement our upper
bounds.
