- 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
- 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,
- 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.
- 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
Rebuttal by Authors (Part II)
This result shows that the quadratic dependence on , cubic dependence on , and inverse dependence on are unavoidable. Our previously established complementary lower bound further shows that logarithmic dependence on is also unavoidable. Thus, through these complementary lower-bound constructions, each principal dependence in our leading gap-dependent guarantee---, , , and the logarithmic dependence on ---is individually shown to be necessary. The remaining 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 is numerically large. Its purpose is to characterize the long-run behavior on any fixed instance with , 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 and 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 for LSVI-UCB++, improving the previous dependence for LSVI-UCB. Our revised paper further establishes a general lower bound for arbitrary learning algorithms in finite-action linear MDPs, together with the complementary lower bound . These results show, through complementary lower-bound constructions, that the quadratic dependence on , cubic dependence on , inverse dependence on , and logarithmic dependence on 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 , , and is minimax-optimal up to logarithmic factors, while the complementary lower bound further shows that logarithmic dependence on is unavoidable.
(continued in the next part)
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 and dyadic scale , they identify a set of episodes in which the step- suboptimality or estimation error exceeds the corresponding threshold. Optimism and Bellman recursion then yield a relation of the schematic form and the right-hand side is controlled by propagating the estimation error from the same deterministic starting step to the end of the episode. This produces a separate counting bound for each pair , of the general form .
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 , which is aggregated as 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 , rather than assigning its regret to deterministic bins, we define the first realized positive-gap step and charge the episode only once at this random boundary. Let , , and . The performance-difference identity gives so the subsequent analysis can be localized to the random suffixes beginning at .
Define . Since every corresponds to a positive gap and the estimate is optimistic, we obtain the single global relation . We then Bellman-unroll from the episode-specific random starting points , rather than from a fixed deterministic step , and accumulate the resulting estimation, martingale, bonus, and variance terms only over . Hence, instead of deriving a family of local relations indexed by and subsequently summing them, our analysis is organized around the single self-bounding relation
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 , leading to the 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 . Combining this with the partial bonus analysis gives, up to logarithmic factors, Substituting and solving the resulting self-bounding inequality yields Thus, the improved 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)
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 d6H5 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. 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 d and H, 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(Δmind2H3+d6H5). 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). Our complete bound improves over this guarantee whenever Δmin1=Ω(d3). Indeed, our inverse-gap term is smaller by a factor of dH2, while this condition also ensures that the additive d6H5 term is no larger than the previous d3H5/Δmin bound. Second, if we compare our bound against all existing guarantees in Table 1, including the O(d2H5/Δmin) guarantee for linear mixture MDPs, a sufficient regime is Δmin1=Ω(d4), which is the condition stated in the manuscript. Finally, the inverse-gap term in our own bound dominates the additive burn-in term when Δmin1=Ω(d4H2). In this regime, the complete bound is essentially governed by the leading O(d2H3/Δ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), 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), with a suboptimal leading dependence on the horizon. Variance-reduced methods improve the leading term to the minimax order O(H2SAT), at the cost of additional lower-order terms. For example, UCB-Advantage [2] achieves a bound of the form O(H2SAT+H8S2A3/2T1/4), while the later Q-EarlySettled-Advantage [3] substantially reduces this higher-order cost while preserving the minimax leading term, obtaining O(H2SAT+H6SA). 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 H8S2A and H7SA, 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/Δmin2, any learning algorithm may incur expected regret of order Ω(d2H3/Δmin) on a d-dimensional linear MDP with minimum positive gap Δmin.
New Theorem 3.3: For any feature dimension d≥12, horizon H≥8, minimum gap Δmin∈(0,H/8), episode number K≥d2H3/Δmin2, and any learning algorithm, there exists a d-dimensional linear MDP with minimum gap Δmin such that E[Regret(T)]≥cΔmind2H3, where c>0 is a universal constant.
(continued in the next part)