acceptodds
Under review as a conference paper at ICLR 2027

Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation

Abstract

We study gap-dependent regret for reinforcement learning with linear function approximation. While prior works have established gap-dependent guarantees in this setting, existing analyses do not apply to algorithms that achieve the nearly minimax-optimal worst-case regret bound , where is the feature dimension, is the horizon length, and is the number of episodes. We bridge this gap by establishing the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ he2023nearly, with an expected regret bound , improving the dependence on both and in the leading gap-dependent term compared with previous results. To understand the exploration cost induced by optimism, we establish a structural lower bound for a broad class of algorithms based on persistent ellipsoidal optimism. When specialized to LSVI-UCB++, this result shows that the leading dependence of our upper bound on , , and is tight up to logarithmic factors. Beyond this algorithmic class, we establish a general gap-dependent lower bound for arbitrary learning algorithms, showing that the logarithmic dependence on and the cubic dependence on are intrinsic to gap-dependent expected regret in linear MDPs. Together, our results substantially narrow the gap between upper and lower bounds and provide a sharper characterization of gap-dependent learning and optimism-based exploration with linear function approximation.

Primary area:
reinforcement learning
Keywords:
Linear Function Approximation, Suboptimality Gap, Regret

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_6aFLOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies episodic MDPs with linear function approximation. It considers UCB type algorithms (based on optimism), and derives instance (gap) dependent regret bounds.

This bound grows as (order) d^2 H^3/Δmin + d^6 H^5.

Here H = episode length, and d = feature dimension.

The previously "best known" instance-dependent bounds grow as d^3 H^5/Δmin, or d^2 H^5 / Δmin.

Hence, if one were to focus only on terms with Δmin dependence, then this is an improvement.

The algorithm itself is not new. It is a minor modification of LSVI-UCB++.

Critical strengths

This paper studies episodic MDPs with linear function approximation. It considers UCB type algorithms (based on optimism), and derives instance (gap) dependent regret bounds.

This bound grows as (order) d^2 H^3/Δmin + d^6 H^5.

Here H = episode length, and d = feature dimension.

The previously "best known" instance-dependent bounds grow as d^3 H^5/Δmin, or d^2 H^5 / Δmin.

Hence, if one were to focus only on terms with Δmin dependence, then this is an improvement.

The proofs seem to be correct, though the key arguments are borrowed from He et. al, or are standard steps in any UCB analysis (e.g. optimism proof).

Critical weaknesses

Overall, I find this work to be incremental, and am not impressed by its findings. I am sorry but I cannot recommend this paper for publication.

I find it hard to digest that d^2 H^3/Δmin + d^6 H^5 is better than d^3 H^5/Δmin , especially given the fact that such instance (or rather gap) dependent bounds are usefulfor "easier problems" (and hence large values of gap). In this regime, clearly the second term d^6 H^5 is supposed to be dominant, thereby engulfing any claimed gains.

The algorithm is also not new (it is essentially LSVI-UCB++ with some minor modifications).

The proof steps and techniques are fundamentally the same as that of existing UCB based analysis of linear MDPs. The key arguments are taken from He et. al. and standard UCB analysis (e.g. optimism proof).

Questions for authors
  1. Can you explain the logic behind your argument that A leads to B? It seems contradictory to the idea behind instance-dependent bounds. Minimax guarantees insure against "bad problem instances". Hence, an algorithm mightbe doing good on most of the problems, but still is not minimax optimal. This suggests exact opposite of what you are hinting here.

A: Despite these advances, existing gap-dependent analyses do not yet cover algorithms that achieve the nearly minimax-optimal worst-case regret bound ˜O (d√H3K), e.g., LSVI-UCB++ (He et al.,2023) or UCRL-VTR+ (Zhou et al., 2021a).

B: As a result, current gap-dependent regret bounds exhibit a loose dependence on the feature dimension d and horizon length H, i.e., ˜O(d3H5/Δmin) under linear MDPs or ˜O(d2H5/Δmin) under linear mixture MDPs,

  1. Similarly, the logic behind this "However, it remains unclear how much gap-dependent regret is intrinsically induced by such optimism-based exploration mechanisms and whether a nearly minimax-optimal optimism-based algorithm can attain a matching upper bound." ?

This statement is even more confusing.

  1. Can you identify the key steps (exact lemma, or proposition or equation number) in the proofs which allow you to reduce dependence upon d and H?
9 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our point-by-point responses.

W1: Burn-in cost

We thank the reviewer for raising this point. We agree that the additive d6H5d^6H^5 term should be retained when comparing the complete finite-sample bounds, and we do not claim that our bound is uniformly smaller than previous guarantees for every value of Δmin⁡\Delta_{\min}. In particular, when the gap is very large, the additive term may dominate our bound. Our claim is instead that the leading gap-dependent term has substantially sharper dependence on dd and HH, and that there are explicit regimes in which this improvement also translates into a sharper complete bound.

Suppressing logarithmic factors as in the manuscript, our bound is O~(d2H3Δmin⁡+d6H5).\widetilde O\left(\frac{d^2H^3}{\Delta_{\min}}+d^6H^5\right). There are three useful regimes for interpreting this bound. First, in the directly comparable linear-MDP setting, the best existing guarantee is O~(d3H5/Δmin⁡)\widetilde O(d^3H^5/\Delta_{\min}). Our complete bound improves over this guarantee whenever 1Δmin⁡=Ω~(d3).\frac{1}{\Delta_{\min}}=\widetilde\Omega(d^3). Indeed, our inverse-gap term is smaller by a factor of dH2dH^2, while this condition also ensures that the additive d6H5d^6H^5 term is no larger than the previous d3H5/Δmin⁡d^3H^5/\Delta_{\min} bound. Second, if we compare our bound against all existing guarantees in Table 1, including the O~(d2H5/Δmin⁡)\widetilde O(d^2H^5/\Delta_{\min}) guarantee for linear mixture MDPs, a sufficient regime is 1Δmin⁡=Ω~(d4),\frac{1}{\Delta_{\min}}=\widetilde\Omega(d^4), which is the condition stated in the manuscript. Finally, the inverse-gap term in our own bound dominates the additive burn-in term when 1Δmin⁡=Ω~(d4H2).\frac{1}{\Delta_{\min}}=\widetilde\Omega(d^4H^2). In this regime, the complete bound is essentially governed by the leading O~(d2H3/Δmin⁡)\widetilde O(d^2H^3/\Delta_{\min}) term. Thus, the additive term affects the finite-sample crossover, but does not engulf the improvement: our complete guarantee already becomes sharper than previous results in a substantially broader regime than the one in which the inverse-gap term dominates our own burn-in cost.

We also want to clarify the role of this additive term. A polynomial higher-order cost is already present in the original worst-case analysis of LSVI-UCB++. Its nearly minimax-optimal worst-case guarantee has the form O~(dH3K+d7H8),\widetilde O\left(d\sqrt{H^3K}+d^7H^8\right), where the first term captures the nearly minimax-optimal statistical dependence, while the second is a gap-independent higher-order cost. Thus, the appearance of a polynomial burn-in term in our gap-dependent guarantee is consistent with the behavior of the underlying LSVI-UCB++ algorithm and is not a phenomenon introduced specifically by our gap-dependent analysis.

More generally, this tradeoff between a sharper leading statistical term and a larger polynomial burn-in is common in RL. A representative example already appears in tabular model-free RL. UCB-Hoeffding [1] has regret of order O~(H4SAT)\widetilde O(\sqrt{H^4SAT}), with a suboptimal leading dependence on the horizon. Variance-reduced methods improve the leading term to the minimax order O~(H2SAT)\widetilde O(\sqrt{H^2SAT}), at the cost of additional lower-order terms. For example, UCB-Advantage [2] achieves a bound of the form O~(H2SAT+H8S2A3/2T1/4)\widetilde O(\sqrt{H^2SAT}+H^8S^2A^{3/2}T^{1/4}), while the later Q-EarlySettled-Advantage [3] substantially reduces this higher-order cost while preserving the minimax leading term, obtaining O~(H2SAT+H6SA)\widetilde O(\sqrt{H^2SAT}+H^6SA). Hence, even in the tabular setting, achieving the optimal leading statistical dependence does not imply the absence of a polynomial burn-in term. Similar burn-in costs also appear in gap-dependent analyses for tabular RL: [4] and [5], for example, contain gap-independent higher-order terms of orders H8S2AH^8S^2A and H7SAH^7SA, respectively. These examples illustrate that polynomial burn-in terms are a recurring feature of both worst-case and gap-dependent RL analyses.

More importantly, our new lower bounds show that the principal dependences appearing in our leading term are unavoidable. Specifically, our new Theorem 3.3 shows that, whenever K≥d2H3/Δmin⁡2K\ge d^2H^3/\Delta_{\min}^2, any learning algorithm may incur expected regret of order Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) on a dd-dimensional linear MDP with minimum positive gap Δmin⁡\Delta_{\min}.

New Theorem 3.3: For any feature dimension d≥12d\geq12, horizon H≥8H\geq8, minimum gap Δmin⁡∈(0,H/8)\Delta_{\min}\in(0,H/8), episode number K≥d2H3/Δmin⁡2K\geq d^2H^3/\Delta_{\min}^2, and any learning algorithm, there exists a dd-dimensional linear MDP with minimum gap Δmin⁡\Delta_{\min} such that E[Regret⁡(T)]≥cd2H3Δmin⁡,\mathbb E[\operatorname{Regret}(T)]\geq c\frac{d^2H^3}{\Delta_{\min}}, where c>0c>0 is a universal constant.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

This result shows that the quadratic dependence on dd, cubic dependence on HH, and inverse dependence on Δmin⁡\Delta_{\min} are unavoidable. Our previously established complementary lower bound Ω(dH3log⁡KΔmin⁡)\Omega\left(\frac{dH^3\log K}{\Delta_{\min}}\right) further shows that logarithmic dependence on KK is also unavoidable. Thus, through these complementary lower-bound constructions, each principal dependence in our leading gap-dependent guarantee---d2d^2, H3H^3, 1/Δmin⁡1/\Delta_{\min}, and the logarithmic dependence on KK---is individually shown to be necessary. The remaining d6H5d^6H^5 term is therefore more naturally interpreted as a burn-in overhead that remains to be reduced, rather than as evidence that the sharper leading dependence is vacuous.

Finally, we agree that in the extreme large-gap regime the previous bound can be numerically smaller because our burn-in term dominates. However, gap-dependent analysis is not useful only when Δmin⁡\Delta_{\min} is numerically large. Its purpose is to characterize the long-run behavior on any fixed instance with Δmin⁡>0\Delta_{\min}>0, for which regret can grow only polylogarithmically rather than at the worst-case square-root rate. Our result provides a sharper characterization of this behavior for a nearly minimax-optimal algorithm, while the regimes above explicitly identify when the improved dependence on dd and HH also translates into a sharper complete finite-sample guarantee.

[1] Li, Gen, et al. "Is Q-learning minimax optimal? a tight sample complexity analysis." Operations Research 72.1 (2024): 222-236.

[2] Zhang, Zihan, Yuan Zhou, and Xiangyang Ji. "Almost optimal model-free reinforcement learningvia reference-advantage decomposition." Advances in Neural Information Processing Systems 33 (2020): 15198-15207.

[3] Li, Gen, et al. "Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 17762-17776.

[4] Zheng, Zhong, Haochen Zhang, and Lingzhou Xue. "Gap-dependent bounds for q-learning using reference-advantage decomposition." International Conference on Learning Representations. Vol. 2025. 2025.

[5] Zhang, Haochen, Zhong Zheng, and Lingzhou Xue. "Regret-optimal q-learning with low cost for single-agent and federated reinforcement learning." Advances in Neural Information Processing Systems 38 (2026): 128711-128799.

W2 and W3: Algorithmic and technical novelty

Our primary goal is not to introduce a substantially new RL algorithm, but to resolve a previously open theoretical question about the instance-dependent behavior of nearly minimax-optimal algorithms. Existing gap-dependent results for RL with linear function approximation apply to algorithms whose worst-case regret has suboptimal dependence on the feature dimension and horizon. In contrast, LSVI-UCB++ achieves nearly minimax-optimal worst-case regret, but whether such an algorithm can simultaneously admit a sharp gap-dependent guarantee was previously unknown. We also emphasize that the two modifications we make to LSVI-UCB++ are minor technical/implementation adjustments and are not claimed as algorithmic contributions; they preserve the essential exploration and estimation structure of LSVI-UCB++. Our contribution instead lies in sharply characterizing the instance-dependent behavior of this nearly minimax-optimal algorithm and in developing the analytical framework needed to obtain this characterization.

On the theoretical side, we establish a gap-dependent regret bound with leading term O~(d2H3/Δmin⁡)\widetilde O(d^2H^3/\Delta_{\min}) for LSVI-UCB++, improving the previous O~(d3H5/Δmin⁡)\widetilde O(d^3H^5/\Delta_{\min}) dependence for LSVI-UCB. Our revised paper further establishes a general lower bound Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) for arbitrary learning algorithms in finite-action linear MDPs, together with the complementary lower bound Ω(dH3log⁡K/Δmin⁡)\Omega(dH^3\log K/\Delta_{\min}). These results show, through complementary lower-bound constructions, that the quadratic dependence on dd, cubic dependence on HH, inverse dependence on Δmin⁡\Delta_{\min}, and logarithmic dependence on KK appearing in our leading guarantee are all necessary. Thus, beyond obtaining an improved upper bound for LSVI-UCB++, our results substantially narrow the gap between upper and lower bounds and show that the leading polynomial dependence on dd, HH, and Δmin⁡\Delta_{\min} is minimax-optimal up to logarithmic factors, while the complementary lower bound further shows that logarithmic dependence on KK is unavoidable.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part III)

On the analytical side, we agree that several basic ingredients, including optimism, Bellman recursion, confidence sets, concentration inequalities, and elliptical-potential arguments, are standard and also appear in He et al., and other UCB analyses. Our contribution is not to replace these basic tools, but to develop a different framework for organizing the gap-dependent analysis: first-positive-gap localization and random trajectory suffixes.

More concretely, representative prior gap-dependent analyses, including the tabular analysis of Yang et al. (2021) and the linear-MDP analysis of He et al. (2021), are organized around fixed-step threshold counting and peeling. For each deterministic horizon step hh and dyadic scale 2nΔmin⁡2^n\Delta_{\min}, they identify a set of episodes Kh,n\mathcal K_{h,n} in which the step-hh suboptimality or estimation error exceeds the corresponding threshold. Optimism and Bellman recursion then yield a relation of the schematic form 2nΔmin⁡∣Kh,n∣≲∑k∈Kh,n(Qk,h−Qhπk)(shk,ahk),2^n\Delta_{\min}|\mathcal K_{h,n}|\lesssim\sum_{k\in\mathcal K_{h,n}}\bigl(Q_{k,h}-Q_h^{\pi_k}\bigr)(s_h^k,a_h^k), and the right-hand side is controlled by propagating the estimation error from the same deterministic starting step hh to the end of the episode. This produces a separate counting bound for each pair (h,n)(h,n), of the general form ∣Kh,n∣≲poly⁡(d,H)polylog⁡(K)/(4nΔmin⁡2)|\mathcal K_{h,n}|\lesssim \operatorname{poly}(d,H)\operatorname{polylog}(K)/(4^n\Delta_{\min}^2).

The final regret is then obtained by multiplying each count by its corresponding gap scale and summing over both the dyadic levels and the horizon steps. In particular, the linear-MDP analysis of He et al. (2021) gives, up to logarithmic factors, a per-step threshold count of order d3H4/(4nΔmin⁡2)d^3H^4/(4^n\Delta_{\min}^2), which is aggregated as Regret⁡(T)≲∑h=1H∑n2nΔmin⁡∣Kh,n∣=O~(d3H5Δmin⁡).\operatorname{Regret}(T)\lesssim\sum_{h=1}^H\sum_n 2^n\Delta_{\min}|\mathcal K_{h,n}|=\widetilde O\left(\frac{d^3H^5}{\Delta_{\min}}\right). Thus, the basic object of the proof is a collection of local large-error events indexed by a deterministic step and a gap threshold, and the final regret bound is obtained by separately summing these local controls across the horizon.

Our framework changes this basic object of analysis. For each suboptimal episode kk, rather than assigning its regret to deterministic (h,n)(h,n) bins, we define the first realized positive-gap step τk:=inf⁡h:Δh(shk,ahk)>0\tau_k:=\inf\\{h:\Delta_h(s_h^k,a_h^k)>0\\} and charge the episode only once at this random boundary. Let Kτ:=k:τk≤H\mathcal K_\tau:=\\{k:\tau_k\le H\\}, L:=∣Kτ∣L:=|\mathcal K_\tau|, and Jτ:=(k,h):k∈Kτ, τk≤h≤H\mathcal J_\tau:=\\{(k,h):k\in\mathcal K_\tau,\ \tau_k\le h\le H\\}. The performance-difference identity gives E[Regret⁡(T)]=E[∑k∈Kτ(Vτk⋆−Vτkπk)(sτkk)],\mathbb E[\operatorname{Regret}(T)]=\mathbb E\left[\sum_{k\in\mathcal K_\tau}\bigl(V_{\tau_k}^\star-V_{\tau_k}^{\pi_k}\bigr)(s_{\tau_k}^k)\right], so the subsequent analysis can be localized to the random suffixes beginning at τk\tau_k.

Define X:=∑k∈Kτ(Qk,τk−Qτkπk)(sτkk,aτkk)X:=\sum_{k\in\mathcal K_\tau}(Q_{k,\tau_k}-Q_{\tau_k}^{\pi_k})(s_{\tau_k}^k,a_{\tau_k}^k). Since every τk\tau_k corresponds to a positive gap and the estimate is optimistic, we obtain the single global relation Δmin⁡L≤X\Delta_{\min}L\le X. We then Bellman-unroll from the episode-specific random starting points τk\tau_k, rather than from a fixed deterministic step hh, and accumulate the resulting estimation, martingale, bonus, and variance terms only over Jτ\mathcal J_\tau. Hence, instead of deriving a family of local relations indexed by (h,n)(h,n) and subsequently summing them, our analysis is organized around the single self-bounding relation Δmin⁡L≤X≲random-suffix bonus and variance terms.\Delta_{\min}L\le X\lesssim \text{random-suffix bonus and variance terms}.

This distinction is also directly reflected in the horizon dependence. In the fixed-step peeling framework, the analysis first obtains a separate control for every deterministic step and then sums these controls over h∈[H]h\in[H], leading to the H5H^5 dependence in the previous linear-MDP result. In our framework, each suboptimal episode is localized only once, while the remaining trajectory is handled jointly through its random suffix. The key suffix-level variance control is of the form Sτ:=∑(k,h)∈Jτσk,h2=O~(H2L+poly⁡(d,H))S_\tau:=\sum_{(k,h)\in\mathcal J_\tau}\sigma_{k,h}^2=\widetilde O(H^2L+\operatorname{poly}(d,H)). Combining this with the partial bonus analysis gives, up to logarithmic factors, X≲d6H5+dH3L.X\lesssim d^6H^5+d\sqrt{H^3L}. Substituting L≤X/Δmin⁡L\le X/\Delta_{\min} and solving the resulting self-bounding inequality yields X≤O~(d2H3Δmin⁡+d6H5).X\le\widetilde O\left(\frac{d^2H^3}{\Delta_{\min}}+d^6H^5\right). Thus, the improved H3H^3 dependence arises from localizing each episode once and controlling the variance jointly over its random suffix, rather than from separately counting and aggregating large-error events at every deterministic horizon step.

(continued in the next part)

Reviewer_Hu4cOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies gap-dependent regret bounds for linear MDPs.

The authors proposed a modified version of LSVI-UCB++, which improves d and H factors in the previously best known gap-dependent regret bounds for linear MDPs. The authors also give lower bounds for specific class of algorithms (those based on persistent ellipsoidal optimism), and general ones.

Critical strengths

The new algorithm gives best known regret bounds for linear MDPs, together with lower bounds for specific class of algorithms and general ones, which demonstrate the tightness of the bound.

To achieves goal, a random-suffix framework for gap-dependent regret analysis in linear MDPs, which seems interesting.

Critical weaknesses

The introduction part needs more work. Linear mixture MDPs was mentioned several times in the introduction. However, as far as I can tell, this paper does not give any new regret bounds for linear mixture MDPs. In that case, I would suggest mentioning linear mixture MDPs results later in the introduction or even removing them.

Also, the authors claim that improving the dependence on feature dimension has practical implications, and the authors justify that claim by using robotics and healthcare as examples. Such justification might be valid, say, 5 years ago, at which point we have little understand of the potential of these provably efficient RL algorithms. However, at this point, we now understand that these provably efficient RL algorithms are rarely superior to empirical ones in terms of practical performance. In that case, I won't say improving regret bounds has practical implications, since the authors did not justify the practical superiority of their algorithms on practical task anyways.

The main novelty seems to come from analytical tools instead of new algorithmic ideas. The proposed algorithm seems to be tweaked version of LSVI-UCB++ (so that the theoretical analysis would go through). In that case, I would suspect how much value this work would bring to practical RL systems. Indeed, the random-suffix framework itself might be interesting, but it does not say much about how to improve practical RL algorithms. Moreover, even the random-suffix framework itself was not highlighted enough to justify its technical novelty. What are the new ideas behind this new framework? How many new technical tools it brings compared to previous tabular / linear MDP gap-dependent analysis? Instead of giving proof sketches, I believe should have been used to compare the new analytical tools/ideas with existing ones.

Given the above weakness and the extremely high bar of ICLR, I would recommend rejection.

Questions for authors

See weaknesses above.

6 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our point-by-point responses.

W1: Discussion of linear mixture MDPs in the introduction.

Thank you for the comment. We agree that linear MDPs and linear mixture MDPs are distinct model classes, and all new theoretical results in our paper concern linear MDPs. We nevertheless include both in the introduction because they are two closely related and standard formulations of reinforcement learning with linear function approximation. Discussing the two settings together also allows us to clarify their different modeling assumptions and algorithmic formulations for readers, and to distinguish precisely which setting our results address. This practice is also common in the literature on RL with linear function approximation; for example, [1], [2] and [3], while focusing on linear MDPs, explicitly discuss linear mixture MDPs as a distinct parallel formulation and compare the two settings. In particular, [4], which is the most directly related prior work on gap-dependent regret, studies the two settings in parallel: LSVI-UCB under the linear-MDP assumption is treated as the model-free setting, while UCRL-VTR under the linear-mixture assumption is treated as the model-based setting. Their corresponding gap-dependent bounds also form the main benchmarks summarized in our Table 1.

Therefore, our discussion of linear mixture MDPs is intended both to distinguish the two standard linear-function-approximation settings and to position our result within the broader literature on gap-dependent RL with linear function approximation, rather than to suggest that our new results extend to the linear-mixture setting. We believe this comparison is useful because it makes clear how the dependence on dd and HH in our linear-MDP result compares with the closest existing gap-dependent guarantees under linear function approximation.

[1] He, Jiafan, et al. "Nearly minimax optimal reinforcement learning for linear markov decision processes." International Conference on Machine Learning. PMLR, 2023.

[2] Zhang, Zihan, et al. "Horizon-free regret for linear markov decision processes." International Conference on Learning Representations. Vol. 2024. 2024.

[3] Dai, Yan, et al. "Refined regret for adversarial mdps with linear function approximation." International Conference on Machine Learning. PMLR, 2023.

[4] He, Jiafan, Dongruo Zhou, and Quanquan Gu. "Logarithmic regret for reinforcement learning with linear function approximation." International Conference on Machine Learning. PMLR, 2021.

W2: Practical motivation for improving the dependence on dd and HH.

Thank you for raising this point. We would like to clarify that our statement concerns the potential practical significance of improving the dependence on the feature dimension dd and horizon HH; it is not a claim that LSVI-UCB++ is already empirically superior to modern deep-RL methods on large-scale practical tasks. Our motivation is that high-dimensional representations and long decision horizons arise naturally in applications such as robotics and healthcare, so understanding how the statistical difficulty of reinforcement learning scales with dd and HH remains relevant when assessing the sample efficiency of theoretically grounded RL methods.

We also do not believe that the practical relevance of theoretically analyzable RL algorithms can be dismissed on the grounds that such methods are no longer used with real data. There are recent examples where theoretically grounded RL methods are combined directly with real-world datasets. For example, [5] use electronic health records from more than 80,000 patients to construct a digital-twin environment and apply tabular Q-learning to learn COVID-19 booster-vaccination policies. In their application, tabular Q-learning is also reported to be more stable than the deep Q-learning alternatives considered. As another example, [6] develop a federated offline-RL method with explicit sample-complexity and suboptimality guarantees and apply it to multi-site sepsis data to illustrate its use in clinical settings.

[5] Ma, Guoxuan, et al. "Development of Public Health Policy by Digital Twin Microsimulation and Q-learning: A COVID-19 Booster Case Study." Journal of the American Statistical Association just-accepted (2026): 1-18.

[6] Zhou, Doudou, et al. "Federated offline reinforcement learning." Journal of the American Statistical Association 119.548 (2024): 3152-3163.

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

W3.1: Algorithmic novelty and practical relevance

Our primary goal is not to introduce a substantially new RL algorithm, but to resolve a previously open theoretical question about the instance-dependent behavior of nearly minimax-optimal algorithms. Existing gap-dependent results for RL with linear function approximation apply to algorithms whose worst-case regret has suboptimal dependence on the feature dimension and horizon. In contrast, LSVI-UCB++ achieves nearly minimax-optimal worst-case regret, but whether it can simultaneously enjoy a sharp gap-dependent guarantee was previously unknown. This is the main motivation of our work. The two modifications we make to LSVI-UCB++ are minor technical/implementation adjustments and are not claimed as algorithmic contributions; they preserve its essential exploration and estimation structure. Our contribution instead lies in characterizing its instance-dependent behavior and developing the analytical tools required for a sharp characterization.

Our main result establishes a gap-dependent regret bound with leading term O~(d2H3/Δmin⁡)\widetilde O(d^2H^3/\Delta_{\min}) for LSVI-UCB++. Importantly, our revised paper further establishes a general lower bound Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) for arbitrary learning algorithms in finite-action linear MDPs. Specifically, our new Theorem 3.3 shows that, whenever K≥d2H3/Δmin⁡2K\ge d^2H^3/\Delta_{\min}^2, any learning algorithm may incur expected regret of order Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) on a dd-dimensional linear MDP with minimum positive gap Δmin⁡\Delta_{\min}.

New Theorem 3.3: For any feature dimension d≥12d\geq12, horizon H≥8H\geq8, minimum gap Δmin⁡∈(0,H/8)\Delta_{\min}\in(0,H/8), episode number K≥d2H3/Δmin⁡2K\geq d^2H^3/\Delta_{\min}^2, and any learning algorithm, there exists a dd-dimensional linear MDP with minimum gap Δmin⁡\Delta_{\min} such that E[Regret⁡(T)]≥cd2H3Δmin⁡,\mathbb E[\operatorname{Regret}(T)]\geq c\frac{d^2H^3}{\Delta_{\min}}, where c>0c>0 is a universal constant.

Together with our complementary lower bound Ω(dH3log⁡K/Δmin⁡)\Omega(dH^3\log K/\Delta_{\min}), these results show that the quadratic dependence on dd, cubic dependence on HH, inverse dependence on Δmin⁡\Delta_{\min}, and logarithmic dependence on KK are each unavoidable through complementary lower-bound constructions. Thus, the principal dependencies in the leading term of our upper bound are supported by corresponding information-theoretic lower bounds.

Regarding practical relevance, gap-dependent analysis provides a more informative characterization of an algorithm's behavior on the particular instance it encounters. Worst-case regret guarantees must hold uniformly over all admissible MDPs, including instances with vanishingly small action gaps. In practice, however, an agent typically interacts with a fixed environment whose feature dimension, horizon, and gap structure are fixed. The minimum gap Δmin⁡\Delta_{\min} is not required by the algorithm, but is an instance-dependent quantity characterizing the difficulty of distinguishing optimal from suboptimal decisions. This distinction is important because the fixed-instance behavior can be substantially more favorable than the worst-case behavior. A gap-dependent guarantee therefore explains why the same algorithm can perform substantially better on a fixed instance than suggested by its uniform worst-case guarantee.

Our contribution makes this instance-dependent characterization substantially sharper for modern nearly minimax-optimal algorithms. Previous gap-dependent guarantees for linear MDPs have relatively loose dependence on the feature dimension and horizon, e.g., O~(d3H5/Δmin⁡)\widetilde O(d^3H^5/\Delta_{\min}) for LSVI-UCB. Our analysis improves this to O~(d2H3/Δmin⁡)\widetilde O(d^2H^3/\Delta_{\min}) for LSVI-UCB++, while our new general lower bound Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) shows that this polynomial dependence reflects an intrinsic difficulty of the general finite-action linear-MDP class. Thus, our analysis provides a more accurate description of how a strong optimism-based algorithm behaves on a given instance, rather than only under an adversarial worst-case instance.

More broadly, the random-suffix argument is not merely a proof device specific to LSVI-UCB++. It systematically sharpens gap-dependent analyses by localizing the regret, bonus, and variance calculations to the random trajectory suffix following the first realized positive-gap decision. This avoids paying for trajectory portions that do not contribute to suboptimality and enables finer use of the variance structure. The same localization principle can in principle be applied to the gap-dependent analysis of LSVI-UCB in He et al. (2021), suggesting that its horizon dependence can also be sharpened. We therefore view the framework as useful not only for understanding LSVI-UCB++, but also as an analytical tool for obtaining more precise instance-dependent guarantees for a broader class of optimism-based RL algorithms.

AuthorsOpenReview ↗

Rebuttal by Authors (Part III)

W3.2: Technical novelty

Technically, the random-suffix framework contains three main analytical ingredients.

First, \textbf{first-positive-gap localization and random-suffix decomposition}. Lemma 4.1 (formalized as Lemma G.1) rewrites the expected regret in terms of the value difference at the first realized positive-gap step of each suboptimal episode. The main difficulty is that this localization introduces a trajectory-dependent random boundary τk\tau_k: for each episode, the relevant quantities must be controlled only on the suffix (k,h):h≥τk\\{(k,h):h\ge \tau_k\\} rather than over the entire trajectory. Consequently, both the exploration bonuses and the conditional variance terms are accumulated over data-dependent random subsets that are coupled with the realized states, actions, and confidence estimates. Standard full-trajectory bonus and total-variance arguments therefore cannot be applied directly. The random-suffix decomposition provides the basic structure that allows us to localize these quantities to the portion of each trajectory that is relevant to the realized suboptimality.

Second, \textbf{partial bonus control through a surrogate covariance sequence}. After restricting the analysis to the episodes selected by the random suffixes, the covariance subsequence Σk,h:k∈Kh\\{\Sigma_{k,h}:k\in K_h\\} no longer satisfies the one-step recursive update required by the standard elliptical-potential argument. Lemma 4.3 (formalized as Lemma F.3) resolves this issue by constructing a surrogate covariance sequence using only the selected episodes together with recursively defined surrogate variance weights. The surrogate matrices are ordered against the original covariance matrices so that each original bonus is controlled by a corresponding surrogate bonus, while restoring the recursive structure needed for the elliptical-potential argument. This is what allows the variance-weighted bonus analysis of LSVI-UCB++ to be localized to a data-dependent subsequence, rather than summed over all episodes as in the usual worst-case analysis.

Third, \textbf{random-suffix variance control through recursive value-estimation errors}. Lemma 4.4 (formalized as Lemma G.2) establishes a variance bound over the same random suffix set. Its proof relies on Lemmas F.4 and F.5, which relate the partial variance terms to partial optimistic/pessimistic value-estimation errors and develop a recursive control of these errors across horizon steps. This gives a suffix analogue of the total-variance argument used in worst-case analyses and is crucial for reducing the horizon dependence from the H5H^5-type dependence appearing in previous gap-dependent analyses to H3H^3.

These three ingredients are then combined with the gap relation between the number of relevant suffixes and their cumulative optimistic error to obtain Theorem 3.1. We have revised the ``Technical novelty'' discussion and Section 4 to distinguish more explicitly the components inherited from prior gap-dependent analyses from the new tools required for variance-weighted linear MDPs. We also added a direct comparison with representative tabular and linear-MDP gap-dependent analyses, summarized below.

Comparison with prior gap-dependent analyses. The main difference from prior gap-dependent analyses is the way in which gap-dependent regret is localized and controlled. Representative tabular analyses such as Yang et al. (2021) and the linear-MDP analysis of He et al. (2021) can both be viewed through a step-wise threshold-counting framework. For each deterministic horizon step hh and dyadic gap scale 2nΔmin⁡2^n\Delta_{\min}, they identify a set of episodes Kh,n\mathcal K_{h,n} in which the suboptimality or estimation error at step hh exceeds the corresponding threshold, and derive a counting relation of the schematic form 2nΔmin⁡∣Kh,n∣≲∑k∈Kh,n(Qk,h−Qhπk)(shk,ahk).2^n\Delta_{\min}|\mathcal K_{h,n}|\lesssim \sum_{k\in\mathcal K_{h,n}}\bigl(Q_{k,h}-Q_h^{\pi_k}\bigr)(s_h^k,a_h^k). The right-hand side is then controlled by recursively propagating the estimation error from the fixed starting step hh to the end of the episode, yielding a bound of the form ∣Kh,n∣≲poly⁡(d,H)polylog⁡(K)/(4nΔmin⁡2)|\mathcal K_{h,n}|\lesssim \operatorname{poly}(d,H)\operatorname{polylog}(K)/(4^n\Delta_{\min}^2).

(continued in the next part)

Reviewer_WxrKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies gap dependent regret bound of LSVI-UCB++, for linear Markov Decision Process. The paper show that, up to minor modification, LSVI-UCB++ achieves a regret upper bound of O~(d2H3/Δmin)\tilde{O}(d^2H^3/\Delta_{\text{min}}) regret. The paper further considered two types of lower bounds. In particular, the paper first presents an algorithm-specific lower bound, showing that a regret of Ω~(d2H3/Δmin)\tilde{\Omega}(d^2H^3/\Delta_{\text{min}}) for algorithms using the ellipsoidal bonus for exploration, indicating that the obtained rate for LSVI-UCB++ cannot be improved in general. For general algorithms, the paper also provides a Ω~(dH3/Δmin)\tilde{\Omega}(dH^3/\Delta_{\text{min}}) lower bound, improving a factor of Ω(H2log⁡K)\Omega(H^2\log K) compared to previous results.

Critical strengths
  1. The paper provides a gap-dependent analysis of LSVI-UCB, which improves the previous best known gap-dependent results for linear MDP. The paper also shows that the rate cannot be improved for algorithms with ellipsoidal bonus
  2. The paper is generally clearly writen and easy to follow, and expose somewhat the rigth amount of technical details
Critical weaknesses

I do not see any specific weaknesses in this paper, and only have some general concerns. It would be helpful if the paper could provide more discussions regarding the follows

  1. The paper motivates improving the dependence on dd and HH by listing examples like domains in robotics and healthcare. Nevertheless, the paper should clarify how Δmin\Delta_{\text{min}} is instantiated in these problems, and the practical interest of studying such gap-dependent bounds in these scenarios

  2. The paper should discuss more about why LSVI-UCB++ is selected for the gap-dependent analysis. While it is indeed the state-of-the-art minimax optimal algorithm, as discussed in Chapter 25.2 of [1], optimism-based algorithm is hard to achieve asymptotical optimal in linear setting. Therefore, focusing on LSVI-UCB++ does not sound like a reasonable choice if the goal is to achieving an optimal gap-dependent rate for linear MDP. This is also suggested by the results in the paper, as the general lower bound is weaker compared to the optimism-specific lower bound by a factor of Θ(d)\Theta(d).

[1] Lattimore, Tor, and Csaba Szepesvári. "Bandit algorithms." Cambridge University 355 (2019).

Questions for authors

N/A

4 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our point-by-point responses.

W1: Practical Application

Thank you for this suggestion. We agree that the practical interpretation of Δmin⁡\Delta_{\min} deserves further clarification. In our setting, Δmin⁡\Delta_{\min} is not an externally chosen parameter, but an instance-dependent quantity determined by the underlying MDP: it is the minimum positive value gap between an optimal action and a suboptimal action over all state-action-step triples. In the robotics examples discussed in the paper, such a gap can be interpreted as the difference in expected long-term task return between the best control or manipulation action and a suboptimal alternative at a given robot and object state; for example, two grasping or control actions may induce different probabilities of task success and hence different continuation values. In healthcare, the gap can similarly represent the difference in expected long-term clinical outcome between the optimal treatment decision and a suboptimal alternative for a given patient state and treatment history. Accordingly, Δmin⁡\Delta_{\min} represents the smallest such positive separation across the relevant decision states and stages, i.e., the most difficult optimal--suboptimal decision pair to distinguish in the given application instance.

This is precisely the type of setting that gap-dependent analysis is designed to characterize. In practical applications, one typically interacts with a particular environment or a particular population-specific MDP rather than an adversarially chosen worst-case instance. Once this MDP is fixed, its feature dimension dd, horizon HH, and gap structure, including Δmin⁡\Delta_{\min}, are also fixed. Gap-dependent analysis therefore characterizes how the algorithm performs on this particular instance as a function of its intrinsic difficulty, rather than only how it performs uniformly over the entire class of admissible MDPs. Importantly, LSVI-UCB++ does not require prior knowledge of Δmin⁡\Delta_{\min}; the gap enters only the theoretical guarantee as an instance-dependent quantity describing the difficulty of distinguishing optimal from suboptimal decisions.

This contrasts with worst-case regret guarantees, which must hold uniformly over all admissible MDPs, including instances with arbitrarily small action gaps, and therefore typically exhibit square-root dependence on the number of interactions. When Δmin⁡>0\Delta_{\min}>0 is fixed, however, suboptimal actions are separated from optimal ones by a persistent margin and can eventually be distinguished and eliminated. Our analysis captures this instance-adaptive behavior: for fixed dd, HH, and Δmin⁡\Delta_{\min}, the same algorithm enjoys regret that is only polylogarithmic in the number of episodes. Thus, the practical interest of Δmin⁡\Delta_{\min} is to provide a more informative characterization of the algorithm's realized performance on a particular problem instance, which can be substantially better than what is suggested by its uniform worst-case guarantee. This phenomenon is also reflected in our simulations in Appendix B: on fixed generated MDP instances, the curves of Regret⁡(T)/log⁡(K+1)\operatorname{Regret}(T)/\log(K+1) become nearly flat toward the end of the tested range, suggesting polylogarithmic regret growth over that range.

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

W2: Optimism

Thank you for this comment. Our motivation for studying LSVI-UCB++ is not to assume a priori that optimism must be asymptotically optimal in the gap-dependent setting. Rather, optimism is one of the most widely used exploration principles in reinforcement learning: it leads to tractable confidence-based exploration, supports clean algorithmic design and analysis, and, importantly, is already sufficient to achieve nearly minimax-optimal worst-case regret in linear MDPs. In fact, representative computationally efficient algorithms achieving nearly minimax-optimal worst-case regret for linear MDPs, including LSVI-UCB++ and VOQL, are based on optimistic exploration. LSVI-UCB++ is a representative state-of-the-art algorithm in this class, while previous gap-dependent analyses only covered algorithms with substantially worse dependence on dd and HH. This naturally motivates asking whether the strong worst-case efficiency achieved by such optimism-based algorithms can also translate into sharper gap-dependent performance.

We agree that, based on the previous version of our lower bounds, one possible interpretation was that the additional factor of dd in the LSVI-UCB++ upper bound might be a price specific to optimism, since the previous general lower bound was smaller by a factor of dd. Our revised results rule out this interpretation. Specifically, our new Theorem 3.3 in the revised manuscript shows that, whenever K≥d2H3/Δmin⁡2K\ge d^2H^3/\Delta_{\min}^2, any learning algorithm may incur expected regret of order Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) on a dd-dimensional linear MDP with minimum positive gap Δmin⁡\Delta_{\min}.

New Theorem 3.3: For any feature dimension d≥12d\geq12, horizon H≥8H\geq8, minimum gap Δmin⁡∈(0,H/8)\Delta_{\min}\in(0,H/8), episode number K≥d2H3/Δmin⁡2K\geq d^2H^3/\Delta_{\min}^2, and any learning algorithm, there exists a dd-dimensional linear MDP with minimum gap Δmin⁡\Delta_{\min} such that E[Regret⁡(T)]≥cd2H3Δmin⁡,\mathbb E[\operatorname{Regret}(T)]\geq c\frac{d^2H^3}{\Delta_{\min}}, where c>0c>0 is a universal constant.

Therefore, the quadratic dependence on dd is not an artifact of optimism-based exploration; rather, it reflects an information-theoretic difficulty of the general finite-action linear-MDP problem. Combined with our upper bound O~(d2H3/Δmin⁡+d6H5)\widetilde{O}(d^2H^3/\Delta_{\min}+d^6H^5) for LSVI-UCB++, this shows that the leading polynomial dependence on dd, HH, and Δmin⁡\Delta_{\min} is minimax-optimal up to logarithmic factors.

I thank the authors for their responses. While the revised manuscript introduces new results (Theorem 3.3) that looks promising, its correctness and significance may be difficult to thoroughly assess within the limited author–reviewer discussion period. Nevertheless, I believe that the merits of the original submission already warrant a weak accept recommendation. I will revisit my rating if necessary after completing my evaluation of the new results.

AuthorsOpenReview ↗

Follow-up on Theorem 3.3

Thank you very much for your thoughtful follow-up and for your positive assessment of the original submission. We also appreciate your willingness to take another look at the new Theorem 3.3.

We fully understand that the discussion period provides limited time to assess a newly added lower-bound result. For completeness, the revised manuscript contains the full statement and proof of Theorem 3.3. If any specific questions or concerns arise while you evaluate the new result, we would be very happy to clarify them promptly. If your evaluation does not raise further concerns, we would also be grateful if the new result could be taken into account in your final assessment.

Reviewer_Ei3ROpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper discusses the gap-dependent regret of LSVI-UCB++ in linear MDPs, claiming to improve the leading gap-dependent term to O~(d2H3/Δmin⁡)\widetilde O(d^2H^3/\Delta_{\min}). The authors segment episodes at the first occurrence of a positive action gap and subsequently control the exploration bonus and variance on the suffix of the random trajectory. I agree with this line of reasoning, but upon examining the full upper bound, the first thing I noticed was a significant d6H5d^6H^5 additive burn-in term.

Critical strengths

S1: I believe the components involving the random suffix, surrogate covariance, and local variance bound are not simply a direct application of UCB arguments. They address a specific challenge: when summing only over the suffixes of randomly selected episodes, the original covariance recurrence no longer applies directly. To address this, the authors reconstructed a structure suitable for elliptical-potential analysis, which represents at least a substantial theoretical effort.

Critical weaknesses

W1: I was initially reluctant to compare only the term preceding 1/Δmin⁡1/\Delta_{\min}. Under the original experimental parameters, d6H5d^6H^5 is approximately 82,000 to 328,000 times larger than the main term; if the full bound and log factor were written out, the new bound might not necessarily be smaller than that of He et al. (2021). I asked the authors to specify the ranges of d,H,Δmin⁡,Kd, H, \Delta_{\min}, K within which the complete finite-sample bound actually improves.

W2: I also had doubts about the interpretation of the structural lower bound. The early proof used unreachable probe states to constrain the regression error, which led me to suspect that the additional dd factor might simply be the cost of a global optimistic certificate. Would the conclusion still hold if calibration were performed only on reachable states?

Questions for authors

Q1: I would like the authors to compare the complete regret upper bound, rather than just the leading term.

Q2: I want to confirm whether the additional dimensionality factor is truly unavoidable in a more general class of RL algorithms.

6 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our point-by-point responses.

W1 and Q1: Full-bound improvement regime.

We thank the reviewer for raising this point. We first clarify the role of the additive d6H5d^6H^5 term in our bound. This term is gap-independent and represents a burn-in cost arising from the variance-aware regression, variance-estimation errors, and rare-switching confidence control. Importantly, such a polynomial higher-order cost is already present in the original worst-case analysis of LSVI-UCB++. Its nearly minimax-optimal worst-case guarantee has the form O~(dH3K+d7H8)\widetilde O\left(d\sqrt{H^3K}+d^7H^8\right), where the first term captures the nearly minimax-optimal statistical dependence, while the second is a gap-independent burn-in term. Thus, the polynomial burn-in term in our gap-dependent guarantee is consistent with the behavior of the underlying LSVI-UCB++ algorithm and is not introduced specifically by our gap-dependent analysis.

More generally, a tradeoff between a sharper leading statistical term and a polynomial higher-order cost is common in RL. For example, in tabular model-free RL, variance-reduced methods improve the leading horizon dependence from the O~(H4SAT)\widetilde O(\sqrt{H^4SAT}) rate of UCB-Hoeffding [1] to the minimax order O~(H2SAT)\widetilde O(\sqrt{H^2SAT}), while introducing additional higher-order terms; representative examples include UCB-Advantage [2] and Q-EarlySettled-Advantage [3]. Similar gap-independent burn-in terms of orders H8S2AH^8S^2A and H7SAH^7SA also appear in existing gap-dependent analyses for tabular RL [4,5]. These examples illustrate that the presence of a polynomial burn-in term does not by itself negate an improvement in the leading statistical dependence.

Nevertheless, we agree with the reviewer that the additive term must be retained when comparing complete finite-sample guarantees. We therefore do not claim that our bound is uniformly smaller than previous results for every value of Δmin⁡\Delta_{\min}. Instead, we explicitly characterize below the parameter regimes in which the improvement in the leading term also translates into an improvement in the complete bound.

In the current manuscript, we already characterize this regime when logarithmic factors are suppressed. In particular, the condition 1Δmin⁡=Ω~(d4)\frac{1}{\Delta_{\min}}=\widetilde{\Omega}(d^4) is sufficient for our bound to improve over all the results reported in Table 1. Retaining the logarithmic factors gives the following more precise characterization.

We first consider the directly comparable linear-MDP setting. We use He et al. (2021), the benchmark cited by the reviewer in Weakness 1, for the following comparison with all logarithmic factors retained. With the confidence level δ=12K(K+1)H3\delta=\frac{1}{2K(K+1)H^3} chosen in Remark 4.5 of He et al. (2021), their Theorem 4.4 gives the principal expected-regret term O(d3H5Δmin⁡log⁡(4dK2(K+1)H4)log⁡(Cd3H4log⁡(4dK2(K+1)H4)Δmin⁡2)),O\left(\frac{d^3H^5}{\Delta_{\min}}\log\bigl(4dK^2(K+1)H^4\bigr)\log\left(\frac{Cd^3H^4\log\bigl(4dK^2(K+1)H^4\bigr)}{\Delta_{\min}^2}\right)\right), up to lower-order confidence/failure terms, where C>0C>0 is a universal constant.

Our bound, with the logarithmic factors stated explicitly as in Theorem 3.1, is O(d2H3log⁡3(1+dHK)Δmin⁡+d6H5log⁡3(1+dHK)).O\left(\frac{d^2H^3\log^3(1+dHK)}{\Delta_{\min}}+d^6H^5\log^3(1+dHK)\right). Comparing the additive term in our bound with the inverse-gap term of He et al. (2021) gives the explicit crossover condition

=\Omega\left(\frac{d^3\log^3(1+dHK)}{\log\bigl(4dK^2(K+1)H^4\bigr)\log\left(\frac{Cd^3H^4\log\bigl(4dK^2(K+1)H^4\bigr)}{\Delta_{\min}^2}\right)}\right).$$ In addition, comparison of the two inverse-gap terms requires $$\log^3(1+dHK)\lesssim dH^2\log\bigl(4dK^2(K+1)H^4\bigr)\log\left(\frac{Cd^3H^4\log\bigl(4dK^2(K+1)H^4\bigr)}{\Delta_{\min}^2}\right).$$ These two conditions together provide an explicit sufficient regime in which our complete bound improves over the existing linear-MDP bound with all logarithmic factors retained. Suppressing logarithmic factors recovers the polynomial-level crossover condition $$\frac{1}{\Delta_{\min}}=\widetilde{\Omega}(d^3)$$ within the same linear-MDP model. For completeness, Table 1 also compares with UCRL-VTR, although this result is for the different linear mixture MDP model rather than the linear MDP model considered in our paper. He et al. (2021, Theorem 5.2 and Remark 5.3) give, up to the model-radius constant $C_\theta^2$, the principal expected-regret term $$O\left(\frac{C_\theta^2d^2H^5}{\Delta_{\min}}\log^3\bigl(4dK^2(K+1)H^4\bigr)\log\left(\frac{512C_\theta^2d^2H^4\log^3\bigl(4dK^2(K+1)H^4\bigr)}{\Delta_{\min}^2}\right)\right).$$ Taking $C_\theta=O(1)$, as in the comparison in Table 1, comparison with our additive term gives the explicit crossover condition $$\frac{1}{\Delta_{\min}}=\Omega\left(\frac{d^4\log^3(1+dHK)}{\log^3\bigl(4dK^2(K+1)H^4\bigr)\log\left(\frac{512d^2H^4\log^3\bigl(4dK^2(K+1)H^4\bigr)}{\Delta_{\min}^2}\right)}\right).$$ (continued in the next part)
AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

Since log⁡(4dK2(K+1)H4)≥log⁡(1+dHK)\log(4dK^2(K+1)H^4)\geq\log(1+dHK) and the remaining logarithmic factor is at least a constant, the ratio of logarithmic factors in the preceding display is at most a constant. Moreover, comparison of the inverse-gap terms is automatically satisfied up to universal constants, since log⁡3(1+dHK)≲H2log⁡3(4dK2(K+1)H4)log⁡(512d2H4log⁡3(4dK2(K+1)H4)Δmin⁡2).\log^3(1+dHK)\lesssim H^2\log^3\bigl(4dK^2(K+1)H^4\bigr)\log\left(\frac{512d^2H^4\log^3\bigl(4dK^2(K+1)H^4\bigr)}{\Delta_{\min}^2}\right). Consequently, the simpler condition 1Δmin⁡=Ω(d4)\frac{1}{\Delta_{\min}}=\Omega(d^4) is sufficient for our complete bound to improve over the UCRL-VTR bound even after retaining the explicit logarithmic factors. Suppressing logarithmic factors gives the previously stated regime 1Δmin⁡=Ω~(d4),\frac{1}{\Delta_{\min}}=\widetilde{\Omega}(d^4), which is precisely the regime stated in the current manuscript for improvement over \emph{all} bounds reported in Table 1.

W2 and Q2: Calibration Assumption

Thank you for pointing out this issue. We have strengthened the revision in two complementary ways.

First, we establish the same Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) lower bound for arbitrary learning algorithms, without imposing any optimism, confidence-set, or calibration assumption. Specifically, our new Theorem 3.3 in the revised manuscript shows that, whenever K≥d2H3/Δmin⁡2K\ge d^2H^3/\Delta_{\min}^2, any learning algorithm may incur expected regret of order Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) on a dd-dimensional linear MDP with minimum positive gap Δmin⁡\Delta_{\min}.

New Theorem 3.3: For any feature dimension d≥12d\geq12, horizon H≥8H\geq8, minimum gap Δmin⁡∈(0,H/8)\Delta_{\min}\in(0,H/8), episode number K≥d2H3/Δmin⁡2K\geq d^2H^3/\Delta_{\min}^2, and any learning algorithm, there exists a dd-dimensional linear MDP with minimum gap Δmin⁡\Delta_{\min} such that E[Regret⁡(T)]≥cd2H3Δmin⁡,\mathbb E[\operatorname{Regret}(T)]\geq c\frac{d^2H^3}{\Delta_{\min}}, where c>0c>0 is a universal constant.

The result applies to arbitrary randomized, history-dependent algorithms. Thus, the lower bound does not rely on ellipsoidal optimism or calibration at all; instead, the quadratic dependence on dd arises from the information required to distinguish among exponentially many possible transition directions. See Theorem 3.3 and Appendix I for details.

Second, we strengthen the structural lower bound for persistent ellipsoidal optimism itself by weakening the calibration assumption from full-domain calibration to calibration only on reachable states. In the revised hard-instance construction, the auxiliary probe states used to derive the joint regression-error bound are made reachable from the initial state with positive probability. Their reach probabilities are chosen independently of the hard-instance parameter and sufficiently small so that they do not affect either the minimum positive gap or the order of the regret lower bound. We accordingly modify the hard-instance construction and calibration argument so that the Bellman calibration inequality is invoked only at reachable state-action pairs. The remaining exploration--estimation argument changes only by constant factors and yields the same Ω(d2H3/Δmin⁡)\Omega(d^2H^3/\Delta_{\min}) structural lower bound. See Appendix H for details.

Together, these revisions address both aspects of the concern. The revised structural argument shows that full-domain calibration is unnecessary for the optimism-specific lower bound, while the new general lower bound shows more broadly that the quadratic dependence on dd persists even without any optimism or calibration assumption.

[1] Li, Gen, et al. "Is Q-learning minimax optimal? a tight sample complexity analysis." Operations Research 72.1 (2024): 222-236.

[2] Zhang, Zihan, Yuan Zhou, and Xiangyang Ji. "Almost optimal model-free reinforcement learningvia reference-advantage decomposition." Advances in Neural Information Processing Systems 33 (2020): 15198-15207.

[3] Li, Gen, et al. "Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 17762-17776.

[4] Zheng, Zhong, Haochen Zhang, and Lingzhou Xue. "Gap-dependent bounds for q-learning using reference-advantage decomposition." International Conference on Learning Representations. Vol. 2025. 2025.

[5] Zhang, Haochen, Zhong Zheng, and Lingzhou Xue. "Regret-optimal q-learning with low cost for single-agent and federated reinforcement learning." Advances in Neural Information Processing Systems 38 (2026): 128711-128799.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Dear Reviewer Ei3R,

As the discussion stage is approaching its end, we would like to kindly follow up on our response. We sincerely appreciate the time and attention you have devoted to reviewing our submission and considering our rebuttal.

We hope that our responses have clarified the main concerns raised in your review. If any concerns remain unresolved, we would be grateful for the opportunity to provide further clarification before the discussion period ends.

Thank you again for your time and thoughtful feedback.

Best regards,

Authors of Submission 9345

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.