Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
Haochen Zhang, Zhong Zheng, Lingzhou Xue · 2026
Read Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation by Haochen Zhang, Zhong Zheng, Lingzhou Xue (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-20297.txt.
Introduction
Haochen Zhang and two co-authors sharpen regret theory for reinforcement learning with linear function approximation. Earlier gap-dependent guarantees did not cover algorithms that reach nearly minimax-optimal worst-case regret. This 2026 paper closes that gap for the optimism-based algorithm LSVI-UCB++. It gives the first gap-dependent regret bound for it, improving the dependence on feature dimension and horizon over prior results.
To explain the cost of optimism, they also prove a lower bound for algorithms built on persistent ellipsoidal optimism. For LSVI-UCB++, it shows the leading terms of their upper bound are tight up to logarithmic factors. A further lower bound for arbitrary algorithms shows the logarithmic dependence on episode count and the cubic dependence on horizon are intrinsic to gap-dependent regret in linear settings. The bounds narrow the gap between upper and lower limits and clarify optimism-based exploration.
Catalog record
| CREATOR | Haochen Zhang, Zhong Zheng, Lingzhou Xue |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-20297
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation Haochen Zhang, Zhong Zheng, Lingzhou Xue 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 O ~ ( d H 3 K ) \widetilde{O}(d\sqrt{H^{3}K}) , where d d is the feature dimension, H H is the horizon length, and K 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++ ( 15 ) . Our analysis yields improved dependencies on both d d and H 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 respect to the number of agents. 1 Introduction Reinforcement learning (RL) ( 35 ) provides a formal framework for sequential decision-making, where an agent learns to maximize cumulative rewards through iterative interaction with a dynamic environment. In modern RL, the design of efficient algorithms for problems with large state and action spaces has become a central challenge. A widely adopted approach is function approximation, which enables efficient learning by representing value functions using a restricted function class. Recently, a large body of literature has focused on establishing regret upper bounds for RL with linear function approximation, where the value function is represented as a linear function of known features. These works can be broadly categorized into two main classes. The first class considers the model-free setting ( 16 ) or the linear Markov decision process (MDP) ( 22 ) , where the transition dynamics and reward functions are assumed to be linear with regard to the known features. In particular, 22 proposed the first provably efficient algorithm, LSVI-UCB. It is based on the principle of optimism in the face of uncertainty, and achieves the regret bound \widetilde{O}(\sqrt{d^{3}H^{4}K}) . Here, \widetilde{O}(\cdot) hides logarithmic factors, d denotes the feature dimension, H is the horizon length, and K is the number of episodes. Subsequently, 15 proposed the LSVI-UCB++ algorithm, which leverages adaptive weighted ridge regression and pessimism techniques, and improves the regret bound to the nearly minimax-optimal rate \widetilde{O}(d\sqrt{H^{3}K}) ( 58 ) . 2 achieved similar near-optimal results in the time-homogeneous setting. The second class focuses on the model-based setting ( 16 ) or the linear mixture MDPs ( 8 ; 58 ; 59 ) , where the transition probability is modeled as a linear combination of multiple base models. 8 proposed the UCRL-VTR algorithm with a regret bound O(d\sqrt{H^{4}K}) . Later, 58 developed a near-optimal algorithm for time-inhomogeneous linear mixture MDPs. Furthermore, 59 proposed a near-optimal, horizon-free algorithm for time-homogeneous linear mixture MDPs. In practice, RL algorithms often outperform their worst-case guarantees when a positive suboptimality gap exists (i.e., the optimal action at each state is better than suboptimal actions by a non-negligible margin). The gap-dependent analysis is well studied in the tabular setting ( 34 ; 13 ; 43 ; 42 ; 57 ; 47 ; 48 ; 11 ) , and it has also gained traction in RL with linear function approximation. 16 pioneered this direction, showing that LSVI-UCB ( 22 ) achieves an expected regret bound \widetilde{O}(d^{3}H^{5}/\Delta_{\textnormal{min}}) under linear MDPs, and UCRL-VTR ( 8 ) attains an expected regret bound \widetilde{O}(d^{2}H^{5}/\Delta_{\textnormal{min}}) under linear mixture MDPs, where the minimum gap \Delta_{\textnormal{min}} is defined as the infimum of the positive suboptimality gap \Delta_{h}(s,a) over all state-action-step triples (s,a,h) . 33 ; 50 also established the same logarithmic guarantees for the expected regret of different algorithms. Collectively, these results demonstrate that RL with linear function approximation can achieve logarithmic regret. Despite these advances, existing gap-dependent analyses do not yet cover algorithms that achieve the nearly minimax-optimal worst-case regret bound \widetilde{O}(d\sqrt{H^{3}K}) , e.g., LSVI-UCB++ ( 15 ) or UCRL-VTR+ ( 58 ) . As a result, current gap-dependent regret bounds exhibit a loose dependence on the feature dimension d and horizon length H , i.e., \widetilde{O}(d^{3}H^{5}/\Delta_{\textnormal{min}}) under linear MDPs or \widetilde{O}(d^{2}H^{5}/\Delta_{\textnormal{min}}) under linear mixture MDPs, failing to reflect their superior efficiency. This suggests that existing analyses may not fully capture the potential of minimax-optimal algorithms in the presence of suboptimality gaps. Consequently, this gap leads to the following open question: Can we establish improved gap-dependent regret upper bounds for nearly minimax-optimal algorithms in RL with linear function approximation? Improving the dependence on the feature dimension d and the horizon length H in regret bounds is not only of theoretical interest but also carries significant practical implications. In domains such as robotics and healthcare, agents often operate in complex, high-dimensional environments, where function approximation is essential for tractable learning and control. For instance, in robotic manipulation and grasping tasks, the state space often consists of high-dimensional continuous observations, including robot joint configurations, object positions, and other environmental variables ( 25 ; 37 ) . Similarly, in healthcare applications such as optimizing cell growth conditions or sequential treatment planning, agents must handle rich biological state representations and long sequences of decisions, making effective function approximation critical for practical deployment ( 5 ) . These applications illustrate that reducing the theoretical dependence on d and H in regret guarantees can directly enhance both the sample efficiency and the practical feasibility of RL algorithms in high-dimensional, long-horizon tasks. In this paper, we provide an affirmative answer to the open question above by establishing an improved gap-dependent regret upper bound for the nearly minimax-optimal LSVI-UCB++ ( 15 ) in the linear MDP setting. Beyond its regret guarantees, LSVI-UCB++ also exhibits infrequent policy updates, which is particularly advantageous for real-world applications where a single agent’s data collection capacity is inherently limited and multi-agent collaboration is required. While multi-agent reinforcement learning (MARL) can improve sample efficiency through parallel exploration, a primary challenge is the high communication cost associated with policy synchronization. The low policy-switching property of LSVI-UCB++ suggests that it can serve as a foundation for a concurrent variant where agents explore in parallel with infrequent synchronizations. This insight motivates the development of our concurrent RL variant, which seeks to accelerate learning without compromising communication efficiency. Our Contributions. Our contributions are summarized as: (i) Improved Gap-Dependent Regret Bound: We establish the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ with linear function approximation. Our results significantly improve the dependence on the feature dimension d and the horizon length H relative to existing literature (see Table 1 for a detailed comparison). Moreover, we show that our refined regret bound implies an improved Probably Approximately Correct (PAC) sample complexity ( 23 ) , reducing the dependence on the accuracy parameter \epsilon of the number of episodes required to identify an \epsilon -optimal policy, from the worst-case rate of \widetilde{O}(1/\epsilon^{2}) to \widetilde{O}(1/\epsilon) . Algorithm \mathbb{E}[\text{Regret}(T)] LSVI-UCB \widehat{O}(d^{3}H^{5}/\Delta_{\textnormal{min}}) ( 16 ) UCRL-VTR \widehat{O}(d^{2}H^{5}/\Delta_{\textnormal{min}}) ( 16 ) LSVI-UCB \widehat{O}(d^{3}H^{5}/\Delta_{\textnormal{min}}) ( 33 ) Cert-LSVI-UCB \widehat{O}(d^{3}H^{5}/\Delta_{\textnormal{min}}) ( 50 ) LSVI-UCB++ \widehat{O}(d^{2}H^{4}/\Delta_{\textnormal{min}}) (Ours) Table 1 : Comparison of gap-dependent regret bounds