KEA: Keeping Exploration Alive by Proactively Coordinating Exploration Strategies

We are grateful to Reviewer Numr for the valuable feedback and insightful questions.

• Theoretical Explanation

We have provided the theoretical explanation in our response to Reviewer hH71. Please refer to that section for a detailed discussion.

• Why the Agent Cannot Identify Unvisited States

Thank you for the insightful question. You are correct that unvisited states yield high intrinsic rewards under RND. However, since SAC updates from transitions stored in the replay buffer, unvisited states--by definition--do not appear in it. As a result, their high intrinsic rewards cannot influence the Q-values or policy updates until the agent actually reaches them. We will revise the text to make this point clearer.

• Comparison with RND-SAC

Thank you for the question. We did include RND-SAC results—please refer to Figure 3 and Table 1. The baseline labeled "RND" in our experiments is exactly SAC with RND (i.e., RND-SAC). As shown in Section 3.1, KEA (KEA-RND) improves the learning efficiency over RND-SAC. We will revise the notation in the final version to improve clarity and avoid confusion.

• Task-Specific Threshold Selection

The thresholds for Walker Run Sparse (0.3) and Cheetah Run Sparse (0.35) were set by us, not defined in the original tasks. We chose them to ensure the tasks are sufficiently challenging to highlight differences in exploration ability, without making them so difficult that all methods fail or require excessive training time. These thresholds were not tuned based on experimental results.

• Justification for Excluding RIDE

Thank you for the suggestion. We chose NovelD as a baseline because it outperforms RIDE in the original paper, and our focus was on evaluating coordination strategies rather than comparing a wide range of exploration methods. Due to space and time constraints, we were unable to include RIDE, but we believe our comparison with NovelD sufficiently demonstrates the effectiveness of KEA.

• Clarification on Supplementary Material

Thank you for the comment. We do include supplementary material, which provides an analysis of varying UTD ratios and a visualization of intrinsic rewards, entropy, and action probabilities over time to illustrate how exploration behavior evolves during training.

• Novelty and Contribution Beyond Existing Methods

Thank you for the feedback. KEA indeed builds on existing exploration methods like RND and NovelD, but our contribution lies in identifying and addressing the coordination issue that arises when combining these with off-policy algorithms like SAC. KEA introduces a lightweight and general switching mechanism that improves exploration efficiency without modifying intrinsic rewards or learning objectives. While threshold-based, the mechanism is simple, effective, and easy to integrate with existing methods. We believe this addresses a practical gap that has been largely overlooked.

• Clarification on Implementation Details

We have provided the implementation details in our response to Reviewer nUkT. In the final version, we will include additional implementation details in the Appendix to ensure clarity and reproducibility.

• Update Mechanism for $\mathcal{A}^B$

We have provided details on the update mechanism for $\mathcal{A}^B$ in our response to Reviewer nUkT. Please refer to that section for a complete explanation.

• Handling Outdated Intrinsic Rewards

Thank you for the insightful question. To address the issue of outdated intrinsic rewards in off-policy settings, we recompute the intrinsic reward for each sampled transition during training, rather than using stored values. This keeps the novelty estimates up to date and mitigates potential negative effects on performance.

We greatly appreciate Reviewer CNJg for the helpful comments and thoughtful suggestions.

• Theoretical Explanation

We have provided the theoretical explanation in our response to Reviewer hH71. Please refer to that section for a detailed discussion.

• Broader Contribution Beyond the Switching Mechanism

Thank you for the feedback. Our contribution goes beyond proposing a switching mechanism--we identify and analyze a core inefficiency in combining SAC with novelty-based exploration, and design KEA as a practical coordination solution. The method improves exploration consistency, is lightweight, and integrates easily with existing approaches.

• Faster Convergence as a Key Strength of KEA

Thank you for the comment. While final returns in some tasks (e.g., 2D Navigation, Reacher Hard Sparse) are similar between KEA-NovelD and NovelD, KEA-NovelD consistently achieves faster convergence. For instance, in 2D Navigation, KEA-NovelD reaches a return of 0.6 around 190k steps, whereas NovelD requires 250k steps, as shown in the experimental results. This demonstrates KEA’s advantage in sample efficiency, even when final performance is close.

• Comparison with Recent State-of-the-Art Methods in DeepSea

Thank you for the helpful suggestion. We agree that comparing against recent state-of-the-art exploration methods is important to demonstrate the effectiveness of KEA. To address this, we conducted additional experiments in the DeepSea environment [1], evaluating our method (KEA-RND-SAC) against the recently proposed SOFE (Castanyer et al., 2024), as well as DeRL (Schäfer et al., 2021).

DeepSea is a hard-exploration benchmark defined on an $N \times N$ grid, where only penalized rightward actions lead to the goal—posing a significant credit assignment challenge for agents relying solely on extrinsic rewards.

Following the setup in SOFE, the table below summarizes average returns and one standard deviations over 100,000 evaluation episodes:

These results show that KEA-RND-SAC achieves comparable or superior performance to SOFE across varying levels of difficulty in the DeepSea environment. We will include these new results in the final version to strengthen the empirical evaluation and highlight KEA’s effectiveness in addressing complex exploration challenges.

---

[1] Behaviour suite for reinforcement learning, Osband et al., 2019

[2] Improving Intrinsic Exploration by Creating Stationary Objectives, Castanyer et al, 2024

[3] Decoupled Reinforcement Learning to Stabilise Intrinsically-Motivated Exploration, Schäfer, Lukas, et al., 2021

• Improving the Clarity of Figure 1

Thank you for the valuable feedback. We agree that additional explanation would improve the clarity of Figure 1. In the final version, we will clarify the meaning of the color map, the gray bar (which represents an obstacle), and the differences between each subfigure. Each subfigure shows the agent’s behavior in a specific region at different time stages, illustrating how intrinsic rewards and policy entropy shape exploration. We will revise the figure and caption to make this clearer.

• Clarification on Update Mechanism for $\mathcal{A}^B$

Thank you for the comment. During training, we set the loss weight for $\mathcal{A}^B$ to zero until extrinsic rewards are obtained, effectively freezing its updates and maintaining high action variance. Once extrinsic rewards are observed, we set the loss weight to one to gradually train $\mathcal{A}^B$. This allows $\mathcal{A}^B$ to remain exploratory early on and focus on task optimization later. We agree that providing a formal statement and clearer explanation will improve clarity, and we will revise this part accordingly in the final version.

• Correction of Typographical Error

Thank you. We will correct the sentence in L152.

We are grateful to Reviewer hH71 for the constructive and valuable feedback.

• Theoretical Explanation of Exploration Strategy Interaction Problem

Problem Setup and Assumptions

Consider an MDP with states $S=$ { $s_0, s_1, s_2$ }, actions $A=$ { $a_1, a_2$ }, and deterministic transitions: $T(s_1|s_0, a_1)=1$, $T(s_2|s_0, a_2)=1$.. Rewards combine sparse extrinsic and intrinsic novelty-based components:

$$r(s, a, s') = r^{ext}(s, a, s') + \beta \ r^{int}(s')\ ,$$

with $r^{int}(s')=1/N(s')$, where $N(s')$ counts state visits. We assume Soft Actor-Critic (SAC) with entropy coefficient $\alpha$, uniform initial Q-values ($Q^0(s_i,a_j)=\epsilon$), uniform initial policy ($\pi^0(a_j|s_i)=0.5$), and single-step episodes.

Definitions and Policy Structure

The soft Q-function, denoted as $Q(s, a)$, is updated according to the following soft Bellman operator, which incorporates both intrinsic and extrinsic rewards:

$$Q^{t+1}(s, a) = r^{ext}(s, a, s') + \beta \ r^{int}(s') + \gamma\ V(s')$$

where the soft value function $V(s)$ is given by:

$$V(s) = \sum_a \pi(a|s)\ [Q(s, a) - \alpha\ \log \pi(a|s)]$$

The policy probabilities are given by a softmax of the Q-values:

$$\pi^{t}(a|s) = \frac{exp(Q^{t}(s, a)/ \alpha)}{\sum_{a'} exp(Q^{t}(s, a')/ \alpha)}$$

Interaction of Exploration Methods

Initially at state $s_0$, $Q^0(s_0,a_1)=Q^0(s_0,a_2)=\epsilon$, thus $\pi^0(a_j|s_0)=0.5$. After taking action $a_1$ and transitioning deterministically to $s_1$, the updated Q-value becomes:

$$Q^{1}(s_0, a_1) = \beta \ r^{int}(s_1) + \gamma\ V(s_1) = \beta + \gamma\ (\epsilon + \alpha \log2)$$

assuming $r^{ext}(s_0,a_1,s_1)=0$, and initial intrinsic reward $r^{int}(s_1)=1 / N(s_1)=1$.

The updated policy probabilities at $s_0$ are then:

$$\pi^{1}(a_1|s_0) = \frac{exp(Q^{1}(s_0, a_1)/ \alpha)}{\sum_{a'} exp(Q^{1}(s_0, a')/ \alpha)}\ ,\ \ \pi^{1}(a_2|s_0) = 1 - \pi^{1}(a_1|s_0)$$

Analytical Derivation of Step Count $k$

Define the action probability ratio at step as:

$$\eta^k = \frac{\pi^{k}(a_1|s_0)}{\pi^{k}(a_2|s_0)} = exp(\frac{Q^{k}(s_0, a_1) - Q^{k}(s_0, a_2)}{\alpha})$$

With repeated visits to state , intrinsic rewards reduces as $r^{int}(s_1) = 1/k$, giving:

$$Q^{k}(s_0, a_1) = \frac{\beta}{k}+\gamma\ (\epsilon+\alpha \log(2)), \ \ Q^{k}(s_0, a_2) = \epsilon$$

For equal probabilities ($\eta^k = 1$), solving explicitly yields:

$$k^* = \frac{\beta}{(1-\gamma)\epsilon-\gamma \alpha \log(2)}$$

Interpretation

The derived equation explicitly demonstrates how the intrinsic reward factor ($\beta$) influences equilibrium behavior and highlights constraints on valid parameter ranges.

Initially, intrinsic rewards increase the probability of revisiting novel states, resulting in repeated collection of similar transitions. This effect reduces as the state novelty decays, and action probabilities return to equilibrium (0.5). The delayed shift from novelty-driven to entropy-driven exploration may thus introduce inefficiencies and slow down learning. Despite the simplified setup, this dynamic is likely broadly relevant, including cases with longer episodes and more complex novelty-based intrinsic rewards.

• Explanation of How KEA Addresses the Interaction Problem

As discussed in our theoretical explanation, combining SAC with novelty-based exploration can lead to inefficiencies—such as repeatedly visiting a state (e.g., $s_1$) to reduce its novelty and lower the action probability ratio $\eta$. KEA addresses this by switching to the co-behavior agent, whose $\eta$ is already close to 1, enabling more efficient coordination without excessive additional sampling.

• On-policy Limitation

Thank you for the suggestion. We focused KEA on off-policy RL due to challenges in combining novelty-based exploration with off-policy methods, especially in transfer across continuous control tasks. KEA addresses these issues by coordinating exploration strategies, improving efficiency and performance. Adapting KEA to on-policy settings would require reconsidering or redesigning the interaction between $\mathcal{A}^{SAC}$ and $\mathcal{A}^{B}$, especially since a shared replay buffer is no longer available in such frameworks.

• Comparison with Recent State-of-the-Art Methods in DeepSea

To further strengthen our empirical evaluation, we performed additional experiments in the DeepSea environment—an established benchmark for hard-exploration tasks. The results show that KEA-RND-SAC performs on par with or better than recent state-of-the-art methods. For more details, please refer to our response to Reviewer CNJg.

We thank Reviewer Acaj for the valuable suggestions and helpful comments.

• Theoretical Explanation

We have provided the theoretical explanation in our response to Reviewer hH71. Please refer to that section for a detailed discussion.

• Computational Overhead of the Additional Agent

Both agents share a unified replay buffer, which improves data efficiency and limits memory overhead. Training is slightly slower due to computing losses for both $\mathcal{A}^{SAC}$ and $\mathcal{A}^B$. At inference time, only one agent ($\mathcal{A}^B$) is active, and the action computation is equivalent to a standard SAC policy, so runtime and memory overhead remain minimal.

• Comparison with Recent State-of-the-Art Methods in DeepSea

Thank you for the suggestion. We conducted additional experiments in the DeepSea environment, a well-established hard-exploration benchmark. In these experiments, KEA-RND-SAC was compared against recent state-of-the-art methods and demonstrated comparable or superior performance. For more details, please refer to our response to Reviewer CNJg.

• Clarification on Missing SAC Results in Figure 5

Thank you for the feedback. SAC results in Figure 5 are always remain zero. Without novelty-based exploration, SAC fails in these hard exploration tasks.

• Clarification on Notation of Agents

Thank you for the suggestion. We agree that the current naming could be confusing and will revise the notation in the final version to improve clarity and readability.

• Clarification on the Relationship Between Exploration and Convergence

Thank you for the suggestion. We agree that the faster convergence observed in our method is a result of improved exploration. We will revise the sentence accordingly in the final version to better reflect this relationship.

• Limitations and Future Directions in Threshold Selection

Lower thresholds encourage more stochastic exploration, while higher ones rely more on novelty-based exploration. The threshold balances these two strategies and is task-dependent. In our experiments, we hand-tuned the threshold to keep the usage of $\mathcal{A}^{SAC}$ around 85–90%. While automated methods (e.g., grid search, Bayesian optimization) could optimize this threshold, defining a general and adaptive selection mechanism remains a non-trivial challenge and a promising direction for future work.

We sincerely thank Reviewer nUkT for the thoughtful and detail feedback.

• Theoretical Explanation

We have provided the theoretical explanation in our response to Reviewer hH71. Please refer to that section for a detailed discussion.

• Rationale Behind the Threshold-Based Switching Mechanism

We provide a detailed theoretical explanation in our response to Reviewer hH71. Instead of requiring repeated visits to reduce the action probability ratio $\eta$ (e.g., visiting $s_1$ multiple times), KEA switches to the co-behavior agent, which already maintains a high $\eta$ value. This allows for more efficient and timely coordination between exploration strategies without the need for additional sampling.

• Comparison with Recent State-of-the-Art Methods in DeepSea

Thank you for the thoughtful feedback. We agree that broader evaluation is important to support the effectiveness and generality of KEA. To address this, we conducted additional experiments in the DeepSea environment, a widely used benchmark for hard-exploration tasks. These experiments evaluate KEA-RND-SAC against recent state-of-the-art methods, including SOFE (Castanyer et al., 2024) and DeRL (Schäfer et al., 2021). The results show that KEA achieves comparable or superior performance across increasing levels of task difficulty, reinforcing the value of its coordination mechanism in challenging exploration settings. For detailed results and discussion, please refer to our response to Reviewer CNJg.

• Why KEA Is Not Effective with DQN

In DQN, $\epsilon$-greedy exploration is independent of Q-values, so the issue KEA addresses—delayed shifting from novelty-driven to method's original exploration—does not arise. Therefore, KEA is not expected to provide benefits in this case. We included DQN mainly to highlight this contrast and emphasize that KEA is more suited to methods, where exploration is influenced by intrinsic reward-driven Q-values.

• Clarification on the 2D Navigation Task Setup

Thank you for the feedback. The task description is provided in Section 3.1. To clarify further: the environment is a 41×41 grid with a 4×34 obstacle in the center; the goal is fixed at (10, 0), and the agent starts randomly in the left half. The maximum episode length is 100 steps and the episode terminated when reach the goal, the boundary, or the obstacle. A reward is given only when reaching the goal. We will improve clarity and reproducibility in the final version.

• Limitations and Future Directions in Threshold Selection

Lower thresholds encourage more stochastic exploration, while higher ones rely more on novelty-based exploration. The threshold balances these two strategies and is task-dependent. In our experiments, we hand-tuned the threshold to keep the usage of $\mathcal{A}^{SAC}$ around 85–90%. While automated methods (e.g., grid search, Bayesian optimization) could optimize this threshold, defining a general and adaptive selection mechanism remains a non-trivial challenge and a promising direction for future work.

• Relation to CAT-SAC and Distinction from KEA

Thank you for pointing out CAT-SAC, which we will cite. While both methods aim to improve coordination in novelty-driven SAC, CAT-SAC modulates entropy temperature based on novelty, whereas KEA introduces a co-behavior agent and a switching mechanisum. A key advantage of KEA is that the co-behavior agent is trained without intrinsic rewards and thus reliably converges to the optimal policy for the extrinsic task.

• Clarification on Implementation Details

Thank you for the feedback. Both $A^B$ and $\mathcal{A}^{SAC}$ use Fully connected(256, 256) actor and Q-network. Learning rates are 0.0003 for Actors and 0.001 for Q-networks, with a discount factor of 0.99. We will include full configuration details for $A^B$, $\mathcal{A}^{SAC}$, and novelty-based models in the Appendix in the final version.

• Update Mechanism for $\mathcal{A}^B$

Thank you for the question. $\mathcal{A}^B$ is updated jointly with $\mathcal{A}^{SAC}$. In each update step, we sample a batch from the replay buffer and compute the soft Q-value losses and policy losses for both $\mathcal{A}^{SAC}$ and $\mathcal{A}^B$ separately, then sum them for optimization. Notably, before any extrinsic reward is received (i.e., before task completion), the loss weight for $\mathcal{A}^B$ is set to zero.

• Mechanism for Maintaining High Variance in $\mathcal{A}^B$

During training, we set the loss weight for $\mathcal{A}^B$ to zero until extrinsic rewards are obtained, effectively freezing its updates and maintaining high action variance. Once extrinsic rewards are observed, we set the loss weight to one to gradually train $\mathcal{A}^B$. This allows $\mathcal{A}^B$ to remain exploratory early on and focus on task optimization later.

• Including Pseudocode

Thank you for the feedback! We will add pseudocode for KEA in the final version.