Thank you for your reply. We addressed your questions and concerns as follows.
**Q1. When considering an infinite time horizon, it seems unlikely that it would not scale with the horizon as this means we can incur linear regret with constant probability.**
**A1.** We would like to emphasize that the constant failure probability (e.g., $\delta = 10^{-6}$) is acceptable in practice since it is highly unlikely to enter the “bad events” in a realistic RL task. Moreover, the high-probability bounds are well studied and acknowledged in literature (Jin et al., 2020) and cannot be viewed as some “intermediate” result towards the expected result. Therefore, we believe our result is a direct improvement of these works (Jin et al., 2020, Vial et al., 2022) to achieve the constant regret in this regime.
Secondly, we would like to highlight that the constant regret bound is important because it reveals a PAC-type (w.p. $1 - \delta$, gap $\Delta$, $\text{Regret} \le O(d^3H^5\Delta^{-1}\log (1 / \delta))$) guarantee of the regret distribution, which cannot be obtained from expected regret.
---
**Q2. The correctness of the work.**
**A2.** We would like to first acknowledge that it is indeed important to improve on factors $d$ and $H$, where we mentioned a few potential directions in the future work. However, we would like to point out that achieving a constant regret is as important as shaving off other dependence because the factors $d, H$ and $K$ are independent from each other. For the case that $d, H$ is small and the $K$ is large, removing $\log K$ is significant. We would also like to emphasize that the future potentials for shaving off $d, H$ factors does not imply our algorithm is **incorrect** because these results are all upper bounds. We have also double checked the proof before and during the rebuttal, and we are confident that our analysis is correct.
---
**Q4. Is there a lower bound showing this is impossible?**
**A4.** In tabular setting, Simchowitz et al. 2019, Xu et al., 2021 provided the gap dependent upper bound by (Theorem 1.1, Xu et al., 2021)
$$\text{Regret}(K) = \tilde{O}\left( \left( \sum_{(s,a,h) \in \mathcal{S} \times \mathcal{A} \times [H]: \Delta_h(s,a) > 0} \frac{1}{\Delta_h(s,a)} + \frac{|Z_{\text{mul}}|}{\Delta_{\min}} + SA \right) \text{poly}(H)\log K \right), \ \ (1)$$
where $Z_{mul}$ is the set of state-action pairs (s, a)’s satisfying a is an non-unique optimal action for s. The upper bound (1) contains both the averaged inverse gap $\sum \Delta_h^{-1}(s, a)$ and the minimal gap $\Delta_\min$. Only when the optimal action for each state is unique (i.e., $Z_{mul} = 0$), (1) can be reduced to
$$\text{Regret}(K) = \tilde{O}\left( \left( \sum_{(s,a,h) \in \mathcal{S} \times \mathcal{A} \times [H]: \Delta_h(s,a) > 0} \frac{1}{\Delta_h(s,a)} + SA \right) \text{poly}(H)\log K \right),$$
In the general case where the optimal action is not necessary unique, we would like to point out that Xu et al., 2021 proved a **lower bound** (Theorem 1.3) suggesting **no algorithm** `ALG` can achieve a regret such that for all MDPs $M$ and $K$ approaches infinity,
$$\text{Regret}(K, M, \text{ALG}) = O\left( \left( \sum_{(s,a,h) \in \mathcal{S} \times \mathcal{A} \times [H]: \Delta_h(s,a) > 0} \frac{1}{\Delta_h(s,a)}\right)\log K \right), \ \ (3)$$
As discussed in Xu et al,. 2021, this suggests that it is **not possible** to achieve a regret bound that **solely** depends on the sum of the inverse of the gaps, even in the tabular MDP setting. Xu et al,. 2021 also mentioned that this is a separation between RL and contextual bandits since such a ‘averaged inverse gap’ can be achieved in contextual bandits (Bubeck et al, 2012, Lattimore et al., 2020)
Therefore, in linear MDPs, such a lower bound presented as (3) also suggests that it is impossible to achieve a gap-dependent bound that is solely depend on the average inverse gap $\sum \Delta_h^{-1}$ since any tabular MDP can be translated into a linear MDP (Example 2.1, Jin et al. 2020).
In short, given the results from literature, we believe that getting such a bound solely depends on the average inverse gap without other dependencies like minimal sub-optimal gap $\Delta_\min$ or $SA$ is impossible in linear MDPs.
---
- Vial, Daniel, et al. "Improved algorithms for misspecified linear markov decision processes." AISTATS, 2022
- Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." COLT, 2020
- Xu, Haike et al. "Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap." COLT, 2021
- Simchowitz, Max et al. "Non-asymptotic gap-dependent regret bounds for tabular mdps." NeurIPS, 2019
- Bubeck, Sébastien et al. "Regret analysis of stochastic and nonstochastic multi-armed bandit problems." Foundations and Trends® in Machine Learning 5.1 (2012): 1-122.
- Lattimore, Tor et al. Bandit algorithms. Cambridge University Press, 2020