Model-Misspecified Offline Reinforcement Learning

Abstract

We study offline reinforcement learning (RL) with linear function approximation, a common technique often employed to lift the dependence on the size of the state space. A great volume of existing literature has studied this problem under the realizability assumption, i.e., the underlying transition/value function is indeed a linear function of given features. However, such an assumption rarely holds in practice. In sharp contrast, classic learning theory in supervised learning provides agnostic generalization bound that holds regardless of whether the given function approximation is realizable or not. In an attempt to theoretically understand the learnability question when the model is outside of the linear realm, we propose a variant of the standard Least Square Value Iteration (LSVI) algorithm and theoretically prove its efficiency. Specifically, we examine the case where the transition model of the MDP is close to having a low rank decomposition but not exactly linear. In contrast to existing works that measure model misspecification by the point-wise error, our result scales only with the expected error under the offline data distribution, a significantly weaker notion that can be much smaller than the point-wise error. Provided with a bound on this population error, we establish a data-dependent upper bound on the suboptimality of Constrained-LSVI for approximately linear MDPs. The upper bound is further accompanied by a lower bound discussion which provides some insight on the information-theoretic limits of the learning process.