Online Sub-Sampling for Reinforcement Learning with General Function Approximation
arXiv:2106.07203
Abstract
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 times for running the RL algorithm for episodes while still achieving a small near-optimal regret bound. In contrast to existing approaches that update the policy for at least times, our approach drastically reduces the number of optimization calls in solving for a policy. When applied to settings in \cite{wang2020reinforcement} or \cite{jin2021bellman}, we improve the overall time complexity by at least a factor of . 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.
References in corpus (31)
- Playing Atari with Deep Reinforcement Learning
- Solving Rubik's Cube with a Robot Hand
- Provably Efficient Reinforcement Learning with Linear Function Approximation
- Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
- Model-Based Reinforcement Learning with Value-Targeted Regression
- Learning Near Optimal Policies with Low Inherent Bellman Error
- What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
- Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- On Lower Bounds for Regret in Reinforcement Learning
- Practical Contextual Bandits with Regression Oracles
- Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
- Model-based Reinforcement Learning and the Eluder Dimension
- Active Learning for Cost-Sensitive Classification
- FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
- On Reward-Free Reinforcement Learning with Linear Function Approximation
- Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
- Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
- Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
- Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
- Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
- Reward-Free Exploration for Reinforcement Learning
- Provably Efficient Q-Learning with Low Switching Cost
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
- Bilinear Classes: A Structural Framework for Provable Generalization in RL
- Scalable Coordinated Exploration in Concurrent Reinforcement Learning
- Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
- Adaptive Reward-Free Exploration
- A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
- Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
- Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
- Minimax Sample Complexity for Turn-based Stochastic Game