The Critic as an Explorer: Lightweight and Provably Efficient Exploration for Deep Reinforcement Learning

** Q1: There have been recent works that are both empirically well performing as well as have provable theoretical guarantees.**

A1:

We thank the reviewer for suggesting additional references, and we will include them in the paper. However, these works typically assume the linearity of value functions or rely on an oracle for the embedding function $\phi$. Based on these assumptions, they propose methods, derive regret bounds, and then extend these methods directly to deep RL without providing further theoretical justification—despite the fact that the linearity and oracle assumptions no longer hold in such settings.

The suggested study [1] also highlights the challenges of applying methods like LSVI-UCB and LSVI-PHE [2] in deep RL settings for practical applications. To clarify, we have included relevant statements from the literature:

Remark 6.1 [1] ... ... we use commonly used algorithms from deep RL literature as opposed to methods presented in ... ... because while these methods are provably efficient under linear MDP settings, in most cases, it is not clear how to scale them to deep RL settings. More precisely, these methods assume that a good feature is known in advance ... ... if the provided feature is not good and fixed, the empirical performance of these methods is often poor.

The primary goal of our work is to address the aforementioned issue by leveraging the embedding of the value network as features. This approach enables numerous provable methods based on linear assumptions to be seamlessly integrated into deep RL, while preserving their theoretical guarantees [3]. In essence, our aim is to make rigorous, provable methods truly applicable to real-world and complex tasks. It is not purely a theoretical paper.

Moreover, while our focus is on UCB and Thompson Sampling, our framework is flexible enough to accommodate other exploration strategies for linear multi-armed bandits. However, to ensure clarity and conciseness, we did not explore these additional strategies in this work and instead leave them as a direction for future research.

In summary, the objective of this work is not to develop a new exploration method with tighter theoretical bounds, but to make existing provable exploration methods truly applicable to real-world tasks.

Q2: $\beta(s, a)$ depends on feature parameter $\phi$. It means each time representation is updated through value network update, the bonus function needs to be recomputed based on new updated feature.

A2:

We believe this question arises from the remark [1] we cited earlier. However, our method does not require recomputing the features or the variance matrix $A$ every time the embedding network $\phi$ is updated. As specified in Algorithm 1 and Algorithm 2, it is evident that this recomputation is unnecessary, even though the embedding network continues to be trained. This is why we consider our method lightweight, efficient, and practical.

Regarding the computation of the inverse of the variance matrix $A$, as discussed in the paper, the matrix has dimensions $\tilde{d} \times \tilde{d}$, which are small. Additionally, efficient techniques such as fast rank-1 updates [4], which operate in quadratic time with respect to $\tilde{d}$, can be utilized to accelerate computation. Indeed, our experiments on MiniHack leveraged fast rank-1 updates, yielding strong performance.

Moreover, simply using the embedding from the value network is inadequate for addressing sparse reward tasks, as the value network cannot be effectively trained under such conditions. This underscores the necessity of Litee$+$. Consequently, our method remains lightweight while effectively solving both sparse and dense reward tasks in deep RL settings.

[1] Ishfaq et al. Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo. ICLR 2024.

[2] Ishfaq et al. More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling. RLC. 2024.

[3] Xu et al. Neural Contextual Bandits with Deep Representation and Shallow Exploration. ICLR, 2022.

[4] Henaff et al. Exploration via Elliptical Episodic Bonuses. Neurips, 2022.

Q1：The novelty of the work is quite low, as the algorithm is almost identical to LSVI-UCB.

A1:

As outlined in the Introduction and Related Works, linear approaches rely on strong assumptions, which can significantly constrain their application in real-world tasks. Recent studies [1] further highlight the challenges of applying methods like LSVI-UCB, LSVI-PHE, etc. in deep RL settings to practical applications. For clarity, we cite relevant statements from the literature directly:

Remark 6.1 [1] ... ... we use commonly used algorithms from deep RL literature as opposed to methods presented in ... ... because while these methods are provably efficient under linear MDP settings, in most cases, it is not clear how to scale them to deep RL settings. More precisely, these methods assume that a good feature is known in advance ... ... if the provided feature is not good and fixed, the empirical performance of these methods is often poor.

The primary goal of our work is to address the aforementioned issue by leveraging the embedding of the value network as features. This approach enables numerous provable methods based on linear assumptions to be seamlessly integrated into deep RL, while preserving their theoretical guarantees [2]. In essence, our aim is to make rigorous, provable methods truly applicable to real-world and complex tasks. It is not purely a theoretical paper.

Moreover, while our focus is on UCB and Thompson Sampling, our framework is flexible enough to accommodate other exploration strategies for linear multi-armed bandits. However, to ensure clarity and conciseness, we did not explore these additional strategies in this work and instead leave them as a direction for future research.

Furthermore, simply using the embedding from the value network is insufficient for solving sparse reward tasks, as the value network cannot be effectively trained in such scenarios. This highlights the necessity of Litee$+$. Consequently, our method remains lightweight while being capable of addressing both sparse and dense reward tasks in deep RL settings.

Q2：The authors use part of the MuJoCo benchmark, missing HalfCheetah, Ant and Humanoid.

A2:

In our paper, we reported experimental results on five tasks in MiniHack, with three presented in the main text and two in the appendix. Additionally, our method successfully solves all 16 tasks in MiniHack as reported in the E3B paper [3]. We chose not to include results for simpler tasks because the baseline E3B already achieves near-perfect success rates, close to 100%, and our method performs comparably in these cases. However, if the reviewers find it necessary, we are happy to include these results in the appendix.

We also provided additional experimental results on MuJoCo in the appendix. Following the reviewers' feedback, we have now included results for tasks such as HalfCheetah and Ant in the main text to enhance visibility, and removed those of PPO+Swimmer and TD3+Swimmer to the appendix.

We did not compare our method with SAC + RND or similar approaches, as RND was specifically designed for sparse reward tasks, and we found no prior work applying it to dense reward settings. For the sparse reward tasks in MiniHack, we directly reference the results of IMPALA + RND, IMPALA + ICM, and similar methods from existing papers [1] and released codebases [1], which confirm that our method outperforms RND, ICM, and other comparable approaches.

[1] Ishfaq et al. Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo. ICLR 2024.

[2] Xu et al. Neural Contextual Bandits with Deep Representation and Shallow Exploration. ICLR, 2022.

[3] Henaff et al. Exploration via Elliptical Episodic Bonuses. Neurips, 2022.

Q3: Computational cost is not a significant constraint in RL. DRL often employs simple architectures.

A3:

Computational cost is a critical factor in practical tasks, as it directly impacts both efficiency and scalability. In response to the assertion that "DRL often employs simple architectures", this claim does not hold true for practical applications. When states include multi-modal data like images and texts, etc. small and simple network architectures are insufficient. Instead, processing such states effectively demands substantial computational resources, as demonstrated in Table 1 of our paper.

Numerous successful DRL implementations, such as AlphaZero and Atari models, employ networks with tens of layers and tens to hundreds of millions of parameters. Moreover, several studies [7] have demonstrated that more complex network architectures can improve the robustness and performance of DRL models. As emphasized earlier, since this is not purely a theoretical paper, our primary focus is on making the method efficient and applicable to real-world, complex tasks.

Q4. The theoretical contribution is limited. The proof has fewer than five pages and does not introduce new techniques or new messages.

A4：

We acknowledge the brevity of the proof; however, we believe that the five pages allocated are sufficient to cover the theoretical analysis presented in our paper. It is important to emphasize that this is NOT a purely theoretical RL paper. Rather, our work aims to bridge the gap between theoretical rigor and practical efficiency in deep RL exploration. The theoretical analysis ensures that, even as we relax the linearity assumption of value functions in RL to make the method practically applicable, the desirable theoretical property—sublinear regret—remains intact.

As noted above, while our primary focus is on UCB and Thompson Sampling, our framework is versatile enough to support other exploration strategies for linear multi-armed bandits. This flexibility allows for the development and proof of new exploration methods within this framework; however, proposing such methods is beyond the scope of this work.

[7] Schwarzer et al. Bigger, Better, Faster: Human-Level Atari with Human-Level Efficiency. ICML, 2023.

Q1: Litee with UCB term is nearly identical to classic algorithms for linear MDP.

A1:

As outlined in the Introduction and Related Works, linear approaches rely on strong assumptions, which can significantly constrain their application in real-world tasks. Recent studies [1] further highlight the challenges of applying methods like LSVI-UCB, LSVI-PHE, etc. in deep RL settings to practical applications. For clarity, we cite relevant statements from the literature directly:

Remark 6.1 [1] ... ... we use commonly used algorithms from deep RL literature as opposed to methods presented in ... ... because while these methods are provably efficient under linear MDP settings, in most cases, it is not clear how to scale them to deep RL settings. More precisely, these methods assume that a good feature is known in advance ... ...

The primary goal of our work is to address the aforementioned issue by leveraging the embedding of the value network as features. This approach enables numerous provable methods based on linear assumptions to be seamlessly integrated into deep RL, while preserving their theoretical guarantees [2]. In essence, our aim is to make rigorous, provable methods truly applicable to real-world and complex tasks.

Moreover, while our focus is on UCB and Thompson Sampling, our framework is flexible enough to accommodate other exploration strategies for linear multi-armed bandits. However, to ensure clarity and conciseness, we did not explore these additional strategies in this work and instead leave them as a direction for future research.

Furthermore, simply using the embedding from the value network is insufficient for solving sparse reward tasks, as the value network cannot be effectively trained in such scenarios. This highlights the necessity of Litee$+$. Consequently, our method remains lightweight while being capable of addressing both sparse and dense reward tasks in deep RL settings.

Q2: The paper only presents some plots based on three or seven repetitions, with no explanation for the variation in repetition count. Additionally, this method fails to solve all tasks in MiniHack.

A2:

In DRL research, it is standard practice to compare model performance using the mean and standard deviation across 3–7 seeds [3, 4, 5, 6 ... ... and many] . We are unclear about the comment regarding "no explanation for the variation in repetition count", as this setting is widely accepted in the field.

Additionally, our method successfully solves all 16 tasks in MiniHack as reported in the E3B paper [3]. We chose not to report results for simpler tasks because the baseline method already achieves near-perfect success rates, close to 100%, and our method performs comparably in these cases. To maintain focus, we reported only the tasks where our approach demonstrates significant improvements. If the reviewer feels it is necessary, we are willing to include the omitted results in the appendix.

[1] Ishfaq et al. Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo. ICLR 2024.

[2] Xu et al. Neural Contextual Bandits with Deep Representation and Shallow Exploration. ICLR, 2022.

[3] Haarnoja et al. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor. ICML, 2018.

[4] Schulman et al. Proximal Policy Optimization Algorithms. arXiv, 2017.

[5] Henaff et al. Exploration via Elliptical Episodic Bonuses. Neurips, 2022.

[6] Espeholt et al. IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures. ICML, 2018.