![[2602.20297] Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.20297] Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
Summary
This paper presents gap-dependent performance guarantees for nearly minimax-optimal reinforcement learning algorithms using linear function approximation, addressing limitations of prior analyses.
Why It Matters
The findings enhance understanding of reinforcement learning efficiency, particularly in multi-agent settings, and provide improved regret bounds that could lead to better algorithm designs in practical applications. This research is crucial for advancing machine learning techniques in complex environments.
Key Takeaways
- Introduces gap-dependent regret bounds for nearly minimax-optimal algorithms.
- Improves dependencies on feature dimension and horizon length.
- Presents a variant of LSVI-UCB++ for efficient parallel exploration.
- Establishes the first gap-dependent sample complexity upper bound for online multi-agent RL.
- Achieves linear speedup with respect to the number of agents.
Statistics > Machine Learning arXiv:2602.20297 (stat) [Submitted on 23 Feb 2026] Title:Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation Authors:Haochen Zhang, Zhong Zheng, Lingzhou Xue View a PDF of the paper titled Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation, by Haochen Zhang and 2 other authors View PDF HTML (experimental) Abstract:We study gap-dependent performance guarantees for nearly minimax-optimal algorithms in reinforcement learning with linear function approximation. While prior works have established gap-dependent regret bounds in this setting, existing analyses do not apply to algorithms that achieve the nearly minimax-optimal worst-case regret bound $\tilde{O}(d\sqrt{H^3K})$, where $d$ is the feature dimension, $H$ is the horizon length, and $K$ is the number of episodes. We bridge this gap by providing the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ (He et al., 2023). Our analysis yields improved dependencies on both $d$ and $H$ compared to previous gap-dependent results. Moreover, leveraging the low policy-switching property of LSVI-UCB++, we introduce a concurrent variant that enables efficient parallel exploration across multiple agents and establish the first gap-dependent sample complexity upper bound for online multi-agent RL with linear function approximation, achieving linear speedup with respe...