On Reward-Free Reinforcement Learning with Linear Function Approximation

Abstract

Reward-free reinforcement learning (RL) is a framework which is suitable for both the batch RL setting and the setting where there are many reward functions of interest. During the exploration phase, an agent collects samples without using a pre-specified reward function. After the exploration phase, a reward function is given, and the agent uses samples collected during the exploration phase to compute a near-optimal policy. Jin et al. [2020] showed that in the tabular setting, the agent only needs to collect polynomial number of samples (in terms of the number states, the number of actions, and the planning horizon) for reward-free RL. However, in practice, the number of states and actions can be large, and thus function approximation schemes are required for generalization. In this work, we give both positive and negative results for reward-free RL with linear function approximation. We give an algorithm for reward-free RL in the linear Markov decision process setting where both the transition and the reward admit linear representations. The sample complexity of our algorithm is polynomial in the feature dimension and the planning horizon, and is completely independent of the number of states and actions. We further give an exponential lower bound for reward-free RL in the setting where only the optimal $Q$-function admits a linear representation. Our results imply several interesting exponential separations on the sample complexity of reward-free RL.

References in corpus (11)

• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Reward Constrained Policy Optimization
• Exploration by Random Network Distillation
• Provably Efficient Maximum Entropy Exploration
• Self-Consistent Trajectory Autoencoder: Hierarchical Reinforcement Learning with Trajectory Embeddings
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Skew-Fit: State-Covering Self-Supervised Reinforcement Learning
• Provably efficient RL with Rich Observations via Latent State Decoding
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning

Cited by in corpus (20)

• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Fast active learning for pure exploration in reinforcement learning
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Exploration and preference satisfaction trade-off in reward-free learning
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Adaptive Reward-Free Exploration
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• When Is Generalizable Reinforcement Learning Tractable?
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Online Model Selection for Reinforcement Learning with Function Approximation
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings