Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations

Abstract

There have been many recent advances on provably efficient Reinforcement Learning (RL) in problems with rich observation spaces. However, all these works share a strong realizability assumption about the optimal value function of the true MDP. Such realizability assumptions are often too strong to hold in practice. In this work, we consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies $\Pi$ that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank $d$ of the underlying MDP. Specifically, our algorithm enjoys a sample complexity bound of $\tilde{O}\left((H^{4d}{K}^{3d}\log |\Pi |)/{\epsilon }^2\right)$ where $H$ is the length of episodes, $K$ is the number of actions and $\epsilon >0$ is the desired sub-optimality. We also provide a nearly matching lower bound for this agnostic setting that shows that the exponential dependence on rank is unavoidable, without further assumptions.

References in corpus (9)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation
• Model-free Representation Learning and Exploration in Low-rank MDPs

Cited by in corpus (1)

• Representation Learning for Online and Offline RL in Low-rank MDPs