  Offline reinforcement learning (RL) aims at learning an optimal strategy
using a pre-collected dataset without further interactions with the
environment. While various algorithms have been proposed for offline RL in the
previous literature, the minimax optimality has only been (nearly) established
for tabular Markov decision processes (MDPs). In this paper, we focus on
offline RL with linear function approximation and propose a new pessimism-based
algorithm for offline linear MDP. At the core of our algorithm is the
uncertainty decomposition via a reference function, which is new in the
literature of offline RL under linear function approximation. Theoretical
analysis demonstrates that our algorithm can match the performance lower bound
up to logarithmic factors. We also extend our techniques to the two-player
zero-sum Markov games (MGs), and establish a new performance lower bound for
MGs, which tightens the existing result, and verifies the nearly minimax
optimality of the proposed algorithm. To the best of our knowledge, these are
the first computationally efficient and nearly minimax optimal algorithms for
offline single-agent MDPs and MGs with linear function approximation.
