Online Sub-Sampling for Reinforcement Learning with General Function Approximation
Not on the map. Why?
Abstract (arXiv)
Most of the existing works for reinforcement learning (RL) with general function approximation (FA) focus on understanding the statistical complexity or regret bounds. However, the computation complexity of such approaches is far from being understood -- indeed, a simple optimization problem over the function class might be as well intractable. In this paper, we tackle this problem by establishing an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm and uses the measurement to guide exploration. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for proptooperatornamepolylog(K) times for running the RL algorithm for K episodes while still achieving a small near-optimal regret bound. In contrast to existing approaches that update the policy for at least Omega(K) times, our approach drastically reduces the number of optimization calls in solving for a policy. When applied to settings in citewang2020reinforcement or citejin2021bellman, we improve the overall time complexity by at least a factor of K. Finally, we show the generality of our online sub-sampling technique by applying it to the reward-free RL setting and multi-agent RL setting.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 48 of its 92 references that are in the map. First posted on arXiv 14 Jun 2021.
Builds on
48 of 92 references.
References · 48
- 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
- 2019Solving Rubik's Cube with a Robot Handcited by 699
- 2020MOPO: Model-based Offline Policy Optimizationcited by 630
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2018Is Q-learning Provably Efficient?cited by 485
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
36 more
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
- 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
- 2021Reinforcement learning based recommender systems: A surveycited by 187
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
- 2020Reward-Free Exploration for Reinforcement Learningcited by 177
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
- 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
- 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
- 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
- 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
- 2018Practical Contextual Bandits with Regression Oraclescited by 92
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
- 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
- 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
- 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
- 2020Adaptive Reward-Free Explorationcited by 77
- 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 69
- 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
- 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
- 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
- 2017Active Learning for Cost-Sensitive Classificationcited by 40
- 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
- 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
- 2016Online Row Samplingcited by 15
- 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
- 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
- 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9
Built on by
Citing papers per year: 2023: 1.
1 paper.