We thank the reviewer for their valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of the reviewer's points.

Tightness of regret bound.

We thank the reviewer for pointing this out. After the submission, we realized that a minimal change in the proof of Lemma B.4 (Lemma B.5 in the original submission) results in improving the bound by a factor of $H$. We refer the reviewer to our Overall Response for more detail on this improvement. Regarding the dependency on $d$, as mentioned in the main paper, ”the gap of $\sqrt{d}$ in worst-case regret between UCB and TS-based methods is a long standing open problem, even in a simpler setting of linear bandit.” due to Hamidi and Bayati (2020) and is yet to be addressed. In the revised version, LMC-LSVI achieves a $\tilde{O}(d^{3/2}H^{3/2}\sqrt{T})$ online regret which matches the best known bound for any randomized algorithm for linear MDP.

Why must the failure probability $\delta$ be larger than a certain quantity?

Indeed, for the frequentist regret analysis we would ideally hope that the regret bound can hold for a small failure probability. This mentioned interval arises from Lemma B.7 (Lemma B.8 in the original submission), where we get an optimistic estimation with a constant probability of $\frac{1}{2\sqrt{2e\pi}}$. This is addressed and improved by using the optimistic reward sampling scheme proposed in [4]. Concretely, we can generate $M$ estimates for Q function $\\{Q\_h^{k, m}\\}\_{m \\in[M]}$ through maintaining $M$ samples of $w$: $\\{w\_h^{k, J\_k, m}\\}\_{m \\in [M]}$ throughout the LMC. Then, we can make an optimistic estimate of Q function by setting $Q\_h^{k}(\\cdot, \\cdot)= \\min\\{\\max\_{m \\in [M]}\\{Q\_h^{k, m}(\\cdot, \\cdot)\\}, H-h+1\\}.$ However, for the simplicity of the algorithm design we keep the current algorithm. We added a discussion of this in the revised version. Please refer to Remark 4.3 on page 5.

There are other works trying to achieve sample efficiency while being compatible with practical deep RL methods.

We thank the reviewer for bringing these works to our attention, as they were inadvertently overlooked in our literature survey. We have cited them in our revision and slightly revised our discussion accordingly. The revised paragraph looks as follows:

Unlike many other provably efficient algorithms with linear function approximations (Yang and Wang, 2020; Cai et al., 2020; Zanette et al., 2020a; Ayoub et al., 2020; Zanette et al., 2020b; Zhou et al., 2021; He et al., 2023), LMC-LSVI can easily be extended to deep RL settings (Adam LMCDQN). We emphasize that such unification of theory and practice is rare (Feng et al., 2021; Kitamura et al., 2023; Liu et al., 2023) in the current literature of both theoretical RL and deep RL.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them. Finally, we are grateful for the reviewer’s positive support on our paper. Given our updated regret bound and comment regarding how to address the failure probability constraint, if the reviewer thinks the work is worthy of a higher score to be highlighted, we would be immensely grateful.

[1] Feng, Fei, et al. "Provably Correct Optimization and Exploration with Non-linear Policies." International Conference on Machine Learning. PMLR, 2021.

[2] Kitamura, Toshinori, et al. "Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice." International Conference on Machine Learning. PMLR, 2023.

[3] Liu, Zhihan, et al. "One Objective to Rule Them All: A Maximization Objective Fusing Estimation and Planning for Exploration." arXiv preprint arXiv:2305.18258 (2023).

[4] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, 2021.

We thank the reviewer for their valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of the reviewer's points.

1. Why do you say the method is provable and practical?

We would like to clarify that in our submission, we claim LMC-LSVI (Algorithm 1) as provable and propose Adam LMCDQN (Algorithm 2) as a ”practical variant” of LMC-LSVI which is more well-suited for deep RL due to its usage of Adam based adaptive SGLD. Moreover, the proposed two algorithms can be viewed as a whole framework, which shows us how to provably conduct randomized exploration (under linear function approximation), and is easily generalized to practical implementation.

While it’s interesting to have convergence and regret guarantee for Adam LMCDQN (Algorithm 2), as shown in [1], Adam has issues in convergence and theoretically it has been shown that it may not converge to an optimal solution. We propose the Adam based extension of LMC-LSVI due to its many observed empirical advantages, and leave the theoretical convergence of it for future study.

[1] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In Proceedings of the 6th International Conference on Learning Representations, 2018.

2. What are the definitions of computational tractability and scalability in Table 1?

Thanks a lot for your suggestion. By computational tractability in Table 1, we meant whether the algorithm is “implementable”. By “scalability” we mean whether the algorithm can be easily extended to deep RL setup. In the revision, we precisely defined these terms more formally in the caption of Table 1. The caption currently says the following:

Regret upper bound for episodic, non-stationary, linear MDPs. Here, computational tractability refers to the ability of a computational problem to be solved in a reasonable amount of time using a feasible amount of computational resources. An algorithm is scalable if it can be easily extended to deep RL setup.

3. Why do you say OPT-RLSVI and LSVI-PHE lack scalability in Table 1?

Thanks for asking the questions and providing your insight on the comparison. We added more discussion in Remark 6.1 and the caption of Table 1 to explain our comparison.

Note that the proposed LMC-LSVI algorithm can be easily extended to deep RL by plugging in neural network function approximation of the Q-function, without any change of the algorithm framework. In contrast, one major disadvantage of LSVI-PHE is that it needs to maintain many ensembles of Q-function approximators that are fitted using independent copies of perturbed datasets at each round. This is computationally heavy and memory-wise extremely burdensome. Without changing the algorithm framework of LSVI-PHE, it will be computationally impractical for environments like Atari, for which we may require many ensemble models. Regarding OPT-RLSVI, we believe even with heuristics, it is not clear how to provide its practical implementation for the reasons outlined in Remark 6.1. Concretely, OPT-RLSVI relies on the feature norm with respect to the inverse covariance matrix. When the features are updated over iterations in deep RL, the computational complexity becomes unbearable as it needs to compute the feature covariance matrix repeatedly.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?

We thank the reviewer for their valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of the reviewer's points.

1. The theory and applications seem to serve two different purposes?

In this paper, along with providing theoretical analysis of LMC-LSVI (Algorithm 1) under linear MDP, we also provide experimental results for it in Appendix E.1 in simulated linear MDPs and the riverswim environment. We later show that we can readily extend the proposed algorithm to deep RL. This is a favorable property of the proposed algorithms that is inspired by stochastic gradient descent and can be generalized to deep learning settings. The theoretical analysis serves as an inspiration to develop the practical methods.

Concretely, the proposed Adam LMCDQN (Algorithm 2) is an instantiation of LMC-LSVI in deep RL by using Adam based adaptive SGLD with DQN as a backbone. DQN being a canonical value based learning method, it makes sense to incorporate Langevin monte carlo based exploration with it when instantiating LMC-LSVI for deep RL setting.

2. Why analyzing it for linear MDPs instead of other models?

For the study in the paper, we choose linear MDP for its relative generality and potential to provide insights for practical algorithms. We agree that the mentioned variants are more general; however, they also lack the generality needed for real application. As the reviewer knows, there is always a more general setting to be studied. We would also like to highlight that the theoretical analysis of RL algorithms in the linear MDP setting is itself a challenging task, especially for randomized exploration based algorithms such as LMC-LSVI. Nevertheless, analyzing LMC based approaches in newer models like [1], [2], [3] is certainly an interesting direction for future extensions and we have included them in our revised conclusion (Page 9, Section 8) . We provide a copy of the modified version here:

We proposed the LMC-LSVI algorithm for reinforcement learning that uses Langevin Monte Carlo to directly sample a Q function from the posterior distribution with arbitrary precision. LMC-LSVI achieves the best-available regret bound for randomized algorithms in the linear MDP setting. Furthermore, we proposed Adam LMCDQN, a practical variant of LMC-LSVI, that demonstrates competitive empirical performance in challenging exploration tasks. There are several avenues for future research. It would be interesting to explore if one can improve the suboptimal dependence on H for randomized algorithms. Extending the current results to more practical and general settings (Zhang et al., 2022; Ouhamma et al., 2023; Weisz et al., 2023) is also an exciting future direction.

3. Why is the regret of LMC-LSVI loose in terms of both $d$ and $H$?

We thank the reviewer for pointing this out. After the submission, we realized that a minimal change in the proof of Lemma B.4 (Lemma B.5 in the original submission) results in improving the bound by a factor of $H$. We refer the reviewer to our Overall Response for more details on this improvement. Regarding the dependency on $d$, as mentioned in the main paper (Section 4, page 5), ”the gap of $\sqrt{d}$ in worst-case regret between UCB and TS-based methods is a long standing open problem, even in a simpler setting of linear bandit.” due to Hamidi and Bayati (2020) and is yet to be addressed. In the revised version, LMC-LSVI achieves a $\tilde{O}(d^{3/2}H^{3/2}\sqrt{T})$ online regret, which matches the best known bound for any randomized algorithm for linear MDP.

Here we provide the updated comment from the revised paper (Section 4, page 5)

“We compare the regret bound of our algorithm with the state-of-the-art results in the literature of theoretical reinforcement learning in Table 1. Compared to the lower bound $\Omega(dH\sqrt{T})$ proved in Zhou et al. (2021), our regret bound is worse off by a factor of $\sqrt{dH}$ under the linear MDP setting. However, the gap of $\sqrt{d}$ in worst-case regret between UCB and TS-based methods is a long standing open problem, even in a simpler setting of linear bandit (Hamidi and Bayati 2020). When converted to linear bandits by setting $H = 1$, our regret bound matches that of LMCTS (Xu et al., 2022) and the best-known regret upper bound for LinTS from Agrawal and Goyal (2013) and Abeille et al. (2017).”

Once again, we thank all the reviewers for their insightful comments and engaging questions. We have further updated the paper (Appendix F, Page 41- 45 in revision) with in depth description and theoretical results on how to remove the interval constraint on $\delta$ in Theorem 4.2 by incorporating the optimistic reward sampling scheme proposed in [1] into LMC-LSVI. We call this variant Multi-Sampling LMC-LSVI or MS-LMC-LSVI in short. We believe with this additional detail, the paper further provides a complete picture of Langevin Monte Carlo for linear MDP.

In Appendix F.1 we expanded on Remark 4.3 and described in detail how with minimal modification of LMC-LSVI (Algorithm 1), we can get MS-LMC-LSVI.

In Appendix F.2, we laid out the supporting lemmas used to prove its regret bound. Each supporting lemma has one to one correspondence with supporting lemmas in Appendix B.1 that are used to prove the regret bound for LMC-LSVI (Algorithm 1). Moreover, for most of them we omit the proofs as they are identical to that of corresponding lemmas in Appendix B.1. We provided some details where necessary for clarity. The only notable difference is in Lemma F.5 (corresponding to Lemma B.7 for LMC-LSVI) on Page 43. After following the same proof and conclusion of Lemma B.7, we derive some probabilistic inequalities and apply union bound to complete the proof.

In Appendix F.3, we provide the final regret bound result (Theorem F.7) for MS-LMC-LSVI that holds with probability $1-\delta$ for any $\delta \in (0,1)$. The proof is the same as that of Theorem B.8 with some minor differences at the end when we put everything together using union bound.

[1] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, 2021.