The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimation
Theoretical guarantees in reinforcement learning (RL) are known to suffer multiplicative blow-up factors with respect to the misspecification error of function approximation. Yet, the nature of such \emph{approximation factors} -- especially their optimal form in a given learning problem -- is poorly understood. In this paper we study this question in linear off-policy value function estimation, where many open questions remain. We study the approximation factor in a broad spectrum of settings, such as with the weighted $L_2$-norm (where the weighting is the offline state distribution), the $L_\infty$ norm, the presence vs. absence of state aliasing, and full vs. partial coverage of the state space. We establish the optimal asymptotic approximation factors (up to constants) for all of these settings. In particular, our bounds identify two instance-dependent factors for the $L_2(\mu)$ norm and only one for the $L_\infty$ norm, which are shown to dictate the hardness of off-policy evaluation under misspecification.
Code (0)
등록된 구현이 없습니다.
Tasks
Off-policy evaluationReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error
The recent work by Dong & Yang (2023) showed for misspecified sparse linear bandits, one can obtain an $O\left(\epsilon\right)$-optimal policy using a polynomial number of samples when the sparsity is a constant, where $…
Q-LearningIterative Hierarchical Optimization for Misspecified Problems (IHOMP)
For complex, high-dimensional Markov Decision Processes (MDPs), it may be necessary to represent the policy with function approximation. A problem is misspecified whenever, the representation cannot express any policy wi…
On the Value of Interaction and Function Approximation in Imitation Learning
We study the statistical guarantees for the Imitation Learning (IL) problem in episodic MDPs.Rajaraman et al. (2020) show an information theoretic lower bound that in the worst case, a learner which can even actively que…
Imitation LearningMulti-class ClassificationStatistical Inference for Misspecified Contextual Bandits
Contextual bandit algorithms have transformed modern experimentation by enabling real-time adaptation for personalized treatment. Yet these advantages create challenges for statistical inference due to adaptivity. We stu…
Bad Values but Good Behavior: Learning Highly Misspecified Bandits and MDPs
Parametric, feature-based reward models are employed by a variety of algorithms in decision-making settings such as bandits and Markov decision processes (MDPs). The typical assumption under which the algorithms are anal…
Decision MakingMulti-Armed BanditsQ-Learning