mlsanityData to 7 Oct 2026

On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game

arXiv 2110.09771 ↗First posted 19 Oct 2021cs.LG cs.GT stat.MLcited by 20

Not on the map. Why?

Abstract (arXiv)

To achieve sample efficiency in reinforcement learning (RL), it necessitates efficiently exploring the underlying environment. Under the offline setting, addressing the exploration challenge lies in collecting an offline dataset with sufficient coverage. Motivated by such a challenge, we study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. Then, given any extrinsic reward, the agent computes the policy via a planning algorithm with offline data collected in the exploration phase. Moreover, we tackle this problem under the context of function approximation, leveraging powerful function approximators. Specifically, we propose to explore via an optimistic variant of the value-iteration algorithm incorporating kernel and neural function approximations, where we adopt the associated exploration bonus as the exploration reward. Moreover, we design exploration and planning algorithms for both single-agent MDPs and zero-sum Markov games and prove that our methods can achieve widetildeO(1 /varepsilon2) sample complexity for generating a varepsilon-suboptimal policy or varepsilon-approximate Nash equilibrium when given an arbitrary extrinsic reward. To the best of our knowledge, we establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 27 of its 48 references that are in the map. First posted on arXiv 19 Oct 2021.

Builds on

27 of 48 references.

References · 27

  1. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  2. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  3. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  4. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  5. 2017On Kernelized Multi-armed Banditscited by 348
  6. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  10. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
15 more
  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  8. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  9. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  10. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  11. 2020Adaptive Reward-Free Explorationcited by 77
  12. 2019Convergence of Adversarial Training in Overparametrized Neural Networkscited by 58
  13. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  14. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  15. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 6; 2024: 4; 2025: 1; 2026: 2.

20 papers.

Sort:

By area:

  1. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  2. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  3. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  4. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  5. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  6. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  7. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  8. 2022Learning General World Models in a Handful of Reward-Free Deploymentscited by 12
  9. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  10. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  11. 2022Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approachcited by 5
  12. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
8 more
  1. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  2. 2024Efficient Reinforcement Learning in Probabilistic Reward Machinescited by 4
  3. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  4. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  5. 2026A Reward-Free Viewpoint on Multi-Objective Reinforcement Learningcited by 2
  6. 2022Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcited by 1
  7. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  8. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0