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.

本研究提出了一种基于 Bootstrapped and Constrained Pessimistic Value Iteration 算法的离线强化学习方法，该算法结合数据自举、约束优化和悲观主义。在局部数据覆盖的假设下，该算法提供了一个快速率，即使在自适应采集的离线数据中，也能够实现绝对零的次优误差和 O（1 / K）的较低界限。