Adaptive Reward-Free Exploration

2020/06/11 by Emilie Kaufmann, Pierre Ménard, Kaufmann, Emilie +9 · 5 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2006.06294

openalex publication_date 2020/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Reward-free exploration is a reinforcement learning setting studied by Jin et al. (2020), who address it by running several algorithms with regret guarantees in parallel. In our work, we instead give a more natural adaptive approach for reward-free exploration which directly reduces upper bounds on the maximum MDP estimation error. We show that, interestingly, our reward-free UCRL algorithm can be seen as a variant of an algorithm of Fiechter from 1994, originally proposed for a different objective that we call best-policy identification. We prove that RF-UCRL needs of order (SAH⁴/ε²)(log(1/δ) + S) episodes to output, with probability 1-δ, an ε-approximation of the optimal policy for any reward function. This bound improves over existing sample-complexity bounds in both the small ε and the small δ regimes. We further investigate the relative complexities of reward-free exploration and best-policy identification.

Citations

• Information Theoretically Aided Reinforcement Learning for Embodied\n Agents
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement\n Learning
• Autonomous exploration for navigating in non-stationary CMPs
• Task-agnostic Exploration in Reinforcement Learning

Cited by

• SEMDICE: Off-policy State Entropy Maximization via Stationary Distribution Correction Estimation
• Rate optimal learning of equilibria from data
• Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design
• Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation

Related

• Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning
• Reward-Free Exploration for Reinforcement Learning
• Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL
• On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes