Thank you for your positive assessment and insightful questions. We appreciate your recognition of our work's value and address your questions below.

Regarding Hyper’s efficiency

Our claim that "Hyper is efficient" operates on two complementary levels:

1. Theoretical guarantees: Hyper is provably guaranteed to sufficiently explore the environment and converge to an optimal policy, as demonstrated by our theoretical analysis providing a worst-case sample complexity bound.
2. Empirical efficiency: Hyper demonstrates significantly greater empirical efficiency and robustness to the curiosity coefficient $\beta$ compared to baseline methods, as conclusively shown in our experimental evaluation in Section 6.

While our theoretical sample complexity appears similar to existing methods in the worst case, our empirical results consistently demonstrate superior practical efficiency. This pattern of theoretical bounds appearing similar while practical performance differs substantially, this is common in reinforcement learning research, where worst-case bounds often don't fully capture the advantages of sophisticated exploration strategies in real environments.

Regarding $\epsilon$ in Theorem 4.2

It represents the optimality gap: the maximum distance between the value of the current policy and the optimal policy. Specifically, a policy $\pi$ is $\epsilon$-optimal if it satisfies: $V^*(s) - V^{\pi}(s) < \epsilon, \forall s \in \mathcal{S}$. This is standard notation in RL theory.

Regarding comparison to recent methods

Curiosity-based exploration remains the dominant paradigm in the field due to its empirical effectiveness, particularly in sparse-reward environments. Hyper is designed as a general framework compatible with any off-policy RL algorithm and any curiosity method. This extensible design allows Hyper to leverage advances in both RL algorithms and curiosity methods, ensuring its continued relevance as the field progresses.

In our main experiments (Section 6), we use TD3 as the RL algorithm and Disagreement as the curiosity method for all methods (including baselines) for fair comparison. Additionally, in Appendix A.5, we compare with LESSON, an advanced recent method. For this comparison, we follow LESSON's original implementation using DQN as the RL algorithm and RND as the curiosity method. Hyper consistently outperforms LESSON on the MiniGrid environments used in their original paper, demonstrating its state-of-the-art performance.

Regarding truncation probability parameter $\gamma$ and $p$

The discount factor $\gamma=0.99$ is fixed across all environments, as is standard in RL research. For the truncation probability $p$, we use a unified decay schedule from 0.01 to 0.001 across all environments, as described in Section 5.2 and Appendix A.1.

This consistent parameterization across diverse environments highlights Hyper's robustness—it maintains strong performance without environment-specific tuning, unlike traditional curiosity-driven methods that require extensive hyperparameter adjustment for each new environment.

We appreciate your feedback, though we must respectfully note that your summary appears to significantly mischaracterize our paper's contributions and scope. Your summary focuses narrowly on a single implementation detail (the bounded geometric distribution) without acknowledging our paper's core contribution: addressing the fundamental hyperparameter sensitivity problem in curiosity-driven exploration. While the other three reviewers correctly identified this primary contribution along with our theoretical analysis and empirical validation, your assessment seems to overlook these central aspects. While our algorithm is elegantly simple, its design required substantial analysis to identify why existing methods fail in certain cases and how our approach resolves these limitations. This fundamental misunderstanding appears to have colored your assessment, as evidenced by your subsequent questions. Nevertheless, we address your specific concerns below.

Difficulty of Understanding the Meaning of $\beta$

In Algorithm 1, I cannot find $\beta$. I am wondering whether the proposed method explicitly incorporates $\beta$ in its design loop. From Figures 1 and 6, it appears that $\beta$ is part of the algorithm loop.

In Fig. 1, you should illustrate what $\beta$ represents.

$\beta$ is the coefficient controlling the scale of curiosity reward, as explained in detail in Section 1 (Introduction). This is standard notation in the field. For clarity, we will explicitly include $\beta$ in Algorithm 1 in the camera-ready version, though it is implicitly present in the "with intrinsic reward" training step (line 16).

The core contribution of our paper is precisely that Hyper significantly reduces sensitivity to $\beta$, as conclusively demonstrated in Figure 6. This addresses a central challenge in curiosity-driven exploration methods that has limited their practical applicability.

Difficulty of Understanding Section 5

The writing quality of the paper is moderate. The core design choice revolves around the repositioning-and-exploration mechanism, which requires a balanced approach. The paper needs substantial revision to improve clarity and readability.

Section 5.3 is the core of the paper. However, it is wordy and lacks informativeness, making it difficult to follow the method clearly. - Currently, Algorithm 1 provides the most concrete description of the method. The authors should refine Section 5.3 to offer a clearer explanation.

We will refine Section 5.3 for clarity while maintaining its informative content. It's worth noting that other reviewers (L37S, 3vGR, and QGsd) did not express difficulty understanding our method or Section 5, suggesting the explanation is generally effective. We will strengthen this section by more explicitly connecting the theoretical insights to the practical implementation.

The comparison with LESSON is questionable, as it is based on a single comparison in specific MiniGrid tasks.

Our comparison with LESSON follows standard scientific practice by evaluating on the environments used in the original LESSON paper. Fetch8x8, UnlockPickup, and LavaCrossingS9N1 are specifically tasks where LESSON demonstrated its strong performance compared to previous option-based and curiosity-driven methods. Hyper's superior performance on these same tasks provides strong evidence of its effectiveness. This approach to comparison is fair, rigorous, and follows established standards in the field.

The first equation in Section 3 is unclear, as there is no indication that a discount is applied to the intrinsic reward. Use vector graphics for the figure plots.

The discount is indeed applied to the intrinsic reward $b(s, a, s')$, as indicated by its placement within the brackets. This follows standard notation in the field. We will use vector graphics for all figures in the camera-ready version.

The title is quite broad. To make it more explicit, consider including terms like "Repositioning & Exploration" for greater clarity.

The current title accurately reflects our paper's primary contribution: achieving hyperparameter robustness in RL exploration. "Repositioning & Exploration" is the mechanism we developed to achieve this goal, not the goal itself. The title appropriately emphasizes our main contribution rather than the specific technique used.

Lines 16 and 17 in Algorithm 1 are unclear. It is not evident whether the method uses only one type of reward or if both types of rewards are used in each phase.

We will clarify this in the camera-ready version. "With intrinsic reward" means training uses both task reward and intrinsic reward together, while "Without intrinsic reward" means using task reward only.

We respectfully request that you reconsider your assessment in light of our clarifications above, as your review appears to have overlooked our paper's primary contribution that was correctly identified by all other reviewers.

Thank you for recognizing the strengths of our work, particularly our careful experiment design and comprehensive literature review.

Regarding your concerns about theoretical aspects, we want to clarify that the theoretical analysis serves as a convergence guarantee. Hyper's exploration framework deliberately diverges from traditional curiosity-driven exploration approaches by utilizing an exploitive policy for part of the buffer collection. The LinearMDP framework analysis demonstrates that even with this novel approach, we achieve robust exploration efficiency in worst-case scenarios. We address your specific points below.

Regarding truncation probability $p$ dependency in sample complexity

The sample complexity result is explicitly $O\left(\frac{d^3 H^4}{\epsilon^2 p}\right)$, which clearly shows how $p$ affects theoretical performance. This parameter provides valuable flexibility in exploration-exploitation balance:

• When $p = 0$: The algorithm operates exclusively in exploitation mode. This will bring the theoretical sample complexity to infinity.
• When $p = 1$: The algorithm commits fully to exploratory data collection, effectively functioning as Decouple algorithm. As Decouple algorithm exclusively uses exploration policy to collect the data, the sample complexity reduces to $O\left(\frac{d^3 H^4}{\epsilon^2 }\right)$, which exactly matches the bound in Jin et al. (2020).

Regarding the tightness of the bound

Our upper bound matches bound in Jin et al. (2020). Regarding tightness, recent work by He et al. (2023) established a minimax-optimal bound of $O(d\sqrt{TH^3})$ for the linear setting, which aligns with the lower bound presented by Zhou et al. (2021). Our follow-up work is already exploring the integration of He et al.'s techniques to derive tighter bounds for Hyper, which would further strengthen our theoretical guarantees.

Regarding the regret bound

Our sample complexity result derives directly from the regret bound $\tilde{O}(\sqrt{d^3 H^4 T \iota^2})$, or $O(\frac{\sqrt{d^3 H^4 T \iota^2}}{p})$, currently presented in the appendix. We will incorporate this regret bound into the main theorem in the revised version to provide a more complete theoretical picture, while maintaining our sample complexity result which better aligns with our empirical evaluation metrics.

Regarding the paper flow

Thank you for this organizational suggestion. We will restructure the paper to place Algorithm 1 before the analysis section and condense Section 3 to focus on essential background information. This reorganization will allow us to expand our experimental results and visualization sections.

Following your suggestion and Reviewer 3vGR's feedback, we've added visualizations of agent behavior, available at https://imgur.com/a/agent-behavior-8wQXtay. These visitation maps demonstrate that Hyper achieves similar exploration capability as Curiosity and Decouple, but learns to exploit the exploratory data significantly faster. This visual evidence further validates our algorithm's effectiveness in balancing exploration and exploitation without requiring extensive hyperparameter tuning.

Regarding the finite horizon & discounted setting

We agree that theoretical RL research typically adopts either finite-horizon with $\gamma = 1$ or infinite-horizon with $\gamma < 1$, however, practical RL implementations frequently combine both elements. Our framework uses a fixed episode length $H$ with discount factor $\gamma$ to better reflect real-world applications where both immediate rewards and long-term planning are important. This approach maintains conceptual alignment with the finite-horizon framework while incorporating the practical benefits of discounting. The superior empirical results across diverse environments validate this design choice.

In light of our responses and planned improvements, we believe our work represents a significant contribution. Our theoretical guarantees coupled with exceptional empirical performance across diverse environments establish Hyper as an important advancement in resolving the exploitation & exploration dilemma. The algorithmic improvements and visualizations we've added further strengthen our paper's impact.

References

• Jin et al. (2020). Provably efficient reinforcement learning with linear function approximation. In COLT
• He et al. (2023). Nearly minimax optimal reinforcement learning for linear Markov decision processes. In ICML
• Zhou et al. (2021). Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In COLT

Thank you for your detailed feedback, and we appreciate your positive comments. We will address your concerns below.

Regarding relevant literatures

Thank you for the valuable suggestion. We will incorporate discussions on the references you suggested in the camera-ready version.

Regarding partially observable environments

We would like to refer you to Figure 9 in our paper, which shows the experimental results on MiniGrid environments, where the agent observes limited field-of-view (partially observable) observations. Hyper outperforms LESSON by Kim et al. (2023) in MiniGrid (Figure 9), which itself was already shown superior to standard curiosity approaches. This suggests Hyper's mechanisms transfer effectively to partially observable settings.

Regarding baseline fairness

We used $\beta=1.0$ following the official Disagreement implementation by Pathak et al. (2019) to ensure fair comparison with the baselines.

Regarding experiment analysis and metric consistency

We believe that our experimental results can demonstrate Hyper's superior sample efficiency. The performance curves in Figures 5,8,9 show that Hyper consistently achieves faster learning across all environments compared to baseline methods. This demonstrates how quickly an algorithm reaches a given performance level, which is precisely the definition of sample efficiency in reinforcement learning.

Regarding $p$-robustness

Hyper is much less sensitive to hyperparameters than existing methods as shown in Figure 6. Unlike $\beta$, the truncation probability $p$ requires no environment specific tuning. We use the same $p$ schedule across all experiments with consistently strong performance. Our truncated geometric distribution design ensures phase lengths adapt appropriately to different environment horizons. At extreme values, Hyper smoothly transitions between pure exploitation ($p=0$) and full exploration/Decouple ($p=1$).

Regarding interaction between the repositioning and exploration phases

Section 5 comprehensively explains Hyper's key mechanisms:

1. The repositioning phase strategically places the agent in promising regions, preventing over-exploration demonstrated in our warm-up example
2. The truncated geometric distribution ensures sufficient exploration while focusing resources on promising areas
3. By limiting exploration to regions informed by the exploitation policy, Hyper collects data that aligns with the exploitation policy's distribution, preventing distribution shift problems (Figure 3) and enabling more efficient learning.

Regarding the choices of environments

Our experiments demonstrate Hyper's performance across different challenges: diverse reward structures (dense-reward locomotion, sparse-reward locomotion, sparse-reward navigation), variable horizons (200-1000), and different state/action complexities. Hyper consistently excels across all settings, which provides compelling evidence for Hyper's generality and effectiveness.

Regarding the limitations & future works

We appreciate this suggestion and will expand the limitations discussion in our revised paper. The primary limitations include:

1. Computational cost: Like Decouple, Hyper requires maintaining and training an additional exploitation policy, increasing computational overhead compared to traditional curiosity-driven methods.
2. Potential for flexibility improvements: While Hyper's exploration paradigm of alternating between repositioning and exploration phases proves highly effective, it can be further improved by dynamically switching between phases based on environment feedback.

We will incorporate this into discussion in the camera-ready version.

Regarding the visualization of agent behavior

Thank you for this valuable and insightful suggestion. We agree this visualization will strengthen the paper and have implemented it as suggested. The state-visitation plots can be found in this anonymous link: https://imgur.com/a/agent-behavior-8wQXtay.

The visualizations clearly illustrate Hyper's advantage over baseline methods and provide further evidence of Hyper's exploration-exploitation balance.

Regarding the connection between theory and practice

Hyper represents a general RL exploration paradigm that can be integrated with various off-policy algorithms and curiosity methods. Algo2 is a realization of Algo1 with linear function approximation and UCB intrinsic reward. Under necessary assumptions, our theoretical analysis for Algo2 demonstrates convergence guarantees under function approximation, while Algo 1 shows how the framework can be implemented with modern deep RL methods.

Reference

Kim et al. (2023) LESSON: Learning to Integrate Exploration Strategies for Reinforcement Learning via an Option Framework. In ICML

Pathak et al. (2019) Self-Supervised Exploration via Disagreement. In ICML