Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
  We study the offline reinforcement learning (offline RL) problem, where the
goal is to learn a reward-maximizing policy in an unknown Markov Decision
Process (MDP) using the data coming from a policy $\mu$. In particular, we
consider the sample complexity problems of offline RL for finite-horizon MDPs.
Prior works study this problem based on different data-coverage assumptions,
and their learning guarantees are expressed by the covering coefficients which
lack the explicit characterization of system quantities. In this work, we
analyze the Adaptive Pessimistic Value Iteration (APVI) algorithm and derive
the suboptimality upper bound that nearly matches \[
O\left(\sum_{h=1}^H\sum_{s_h,a_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{\mathrm{Var}_{P_{s_h,a_h}}{(V^\star_{h+1}+r_h)}}{d^\mu_h(s_h,a_h)}}\sqrt{\frac{1}{n}}\right).
\] In complementary, we also prove a per-instance information-theoretical lower
bound under the weak assumption that $d^\mu_h(s_h,a_h)>0$ if
$d^{\pi^\star}_h(s_h,a_h)>0$. Different from the previous minimax lower bounds,
the per-instance lower bound (via local minimaxity) is a much stronger
criterion as it applies to individual instances separately. Here $\pi^\star$ is
a optimal policy, $\mu$ is the behavior policy and $d_h^\mu$ is the marginal
state-action probability. We call the above equation the intrinsic offline
reinforcement learning bound since it directly implies all the existing optimal
results: minimax rate under uniform data-coverage assumption, horizon-free
setting, single policy concentrability, and the tight problem-dependent
results. Later, we extend the result to the assumption-free regime (where we
make no assumption on $ \mu$) and obtain the assumption-free intrinsic bound.
Due to its generic form, we believe the intrinsic bound could help illuminate
what makes a specific problem hard and reveal the fundamental challenges in
offline RL.
