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 (19)
- Solving Rubik's Cube with a Robot Hand
- Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
- Model-Based Reinforcement Learning with Value-Targeted Regression
- Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- On Lower Bounds for Regret in Reinforcement Learning
- Model-based Reinforcement Learning and the Eluder Dimension
- 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
- 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
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
- Bilinear Classes: A Structural Framework for Provable Generalization in RL
- Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
- A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
- Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
- Minimax Sample Complexity for Turn-based Stochastic Game
- Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints