Online Sub-Sampling for Reinforcement Learning with General Function Approximation
This addresses a computational bottleneck for researchers and practitioners in reinforcement learning, offering a significant speed-up for value-based methods with general function approximation, though it is incremental in optimizing existing frameworks.
The paper tackles the high computational complexity of reinforcement learning with general function approximation by proposing an online sub-sampling framework that measures information gain to guide exploration, reducing policy updates to poly-logarithmic times in episodes and improving time complexity by at least a factor of K compared to existing methods.
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 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 $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.