Online Sub-sampling For Reinforcement Learning With General Function Approximation

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 \(\propto\operatorname\{poly\}log(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 \(Ω(K)\) times, our approach drastically reduces the number of optimization calls in solvin

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykong2021online

Related papers

• Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00
• Optimal Conservative Offline RL With General Function Approximation Via Augmented Lagrangian (2022)0.00
• Distributionally Robust Offline Reinforcement Learning With Linear Function Approximation (2022)0.00
• Provably Efficient Reinforcement Learning With Linear Function Approximation (2019)11.76
• A Nearly Optimal And Low-switching Algorithm For Reinforcement Learning With General Function Approximation (2023)0.00
• Online Model Selection For Reinforcement Learning With Function Approximation (2020)0.00
• Prior-dependent Analysis Of Posterior Sampling Reinforcement Learning With Function Approximation (2024)0.00
• Posterior Sampling With Delayed Feedback For Reinforcement Learning With Linear Function Approximation (2023)0.00