Reward-Free Exploration for Reinforcement Learning

Abstract

Exploration is widely regarded as one of the most challenging aspects of reinforcement learning (RL), with many naive approaches succumbing to exponential sample complexity. To isolate the challenges of exploration, we propose a new "reward-free RL" framework. In the exploration phase, the agent first collects trajectories from an MDP $\mathcal{M}$ without a pre-specified reward function. After exploration, it is tasked with computing near-optimal policies under for $\mathcal{M}$ for a collection of given reward functions. This framework is particularly suitable when there are many reward functions of interest, or when the reward function is shaped by an external agent to elicit desired behavior. We give an efficient algorithm that conducts $\tilde{\mathcal{O}}(S^{2}A\mathrm{poly}(H)/{\epsilon }^2)$ episodes of exploration and returns $\epsilon$-suboptimal policies for an arbitrary number of reward functions. We achieve this by finding exploratory policies that visit each "significant" state with probability proportional to its maximum visitation probability under any possible policy. Moreover, our planning procedure can be instantiated by any black-box approximate planner, such as value iteration or natural policy gradient. We also give a nearly-matching $\Omega (S^{2}A{H}^2/{\epsilon }^2)$ lower bound, demonstrating the near-optimality of our algorithm in this setting.

References in corpus (7)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Reward Constrained Policy Optimization
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Reinforcement Learning with Convex Constraints
• On Bayes Risk Lower Bounds

Cited by in corpus (31)

• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Fast active learning for pure exploration in reinforcement learning
• Active Learning for Nonlinear System Identification with Guarantees
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Model-based Adversarial Meta-Reinforcement Learning
• Task-agnostic Exploration in Reinforcement Learning
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Adaptive Reward-Free Exploration
• Geometric Entropic Exploration
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments
• Online Model Selection for Reinforcement Learning with Function Approximation
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback
• Randomized Value Functions via Posterior State-Abstraction Sampling
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Active Model Estimation in Markov Decision Processes
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Reinforcement Learning with Feedback Graphs
• Exploration by Maximizing Rényi Entropy for Reward-Free RL Framework
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Reinforcement Learning in Reward-Mixing MDPs
• Adaptive Multi-Goal Exploration