Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Authors: Yiran Wang
Chenshu Liu
Yunfan Li
Sanae Amani
Bolei Zhou
Lin Yang
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Exploration
Provably Efficient
Hyperparameter Robustness
Primary area: reinforcement_learning
TL;DR: We propose Hyper, a novel reinforcement learning exploration algorithm that is theoretically efficient, empirically performant and hyperparameter robust.

Abstract: The exploration \& exploitation dilemma poses significant challenges in reinforcement learning (RL). Recently, curiosity-based exploration methods achieved great success in tackling hard-exploration problems. However, they necessitate extensive hyperparameter tuning on different environments, which heavily limits the applicability and accessibility of this line of methods. In this paper, we characterize this problem via analysis of the agent behavior, concluding the fundamental difficulty of choosing a proper hyperparameter. We then identify the difficulty and the instability of the optimization when the agent learns with curiosity. We propose our method, hyperparameter robust exploration (\textbf{Hyper}), which extensively mitigates the problem by effectively regularizing the visitation of the exploration and decoupling the exploitation to ensure stable training. We theoretically justify that \textbf{Hyper} is provably efficient under function approximation setting and empirically demonstrate its appealing performance and robustness in various environments.

Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Yiran Wang" 1
Chenshu Liu 22
Yunfan Li!
Sanae Amani' Bolei Zhou? Lin F. Yang
Abstract
2016; 2017; Berner et al., 2019; Arulkumaran et al., 2019), RL is vulnerable to sub-optimal policies when presented with insufficient reward signals. To resolve this dilemma, curiosity -riven exploration methods provide a promising solution (Bellemare et al., 2016; Pathak et al., 2017: Ostro- vski et al., 2017; Burda et al., 2018; Machado al., 2020; Pathak al., 2019).
The exploration & exploitation dilemma poses significant challenges in reinforcement learn- ing (RL). Recently, curiosity- based exploration methods achieved great success in tackling hard- exploration problems. However, they necessitate extensive hyperparameter tuning on different en- vironments, which heavily limits the upplicability and accessibility of this line of methods. In this paper, we characterize this problem via analysis of the agent behavior, concluding the fundamen- tal difficulty of choosing proper hyperparameter. We then identify the difficulty and the instability of the optimization when the agent learns with curiosity. We propose our method, hyperparame- ter robust exploration (Hyper), which extensively mitigates the problem by effectively regularizing the visitation of the exploration and decoupling the exploitation to ensure stable training. We the- oretically justify that Hyper is provably efficient under function approximation setting and empiri- cally demonstrate its appealing performance and
1.0
0.8
Average Value
0.6
Q-Learning UCB-Hyper(Ours)
UCB-Q
0.4
02
0.0
robustness in various environments.
5e 1e
Se
10-2
Se
10
Se
10.0 100.0
B
1. Introduction
Figure I. Performance of pure exploitation. curiosity-driven explo- ration, and our algorithm with diffcrent choices of 3, each data point is the averaged performance after 1M steps training over 5 runs. Curiosity-driven (UCB-Q) is very sensitive to hyperparame- 3. We propose Hyper, which is empirically robust to B, and theoretically efficient.
Reinforcement learning (RL.) is paradigm that solves se- quential decision-making problems by maximizing the pected cumulative reward r, which is composed of both ex- plorations, the process of the agent discovering new features from the environment, and exploitations, the process by which the agent learns to tackle the task using the knowledge already gained. Despite the astonishing success achieved with this paradigm (Mnih al., 2013; 2015; Silver al.,
Curiosity algorithms, which originate from solving the bandit problem (Auer, 2002), enhance the exploration by intrinsically rewarding the agent for exploring the environ- ment. These algorithms optimize the policy æ to maximize the joint reward function r ,b, where is the explicit task reward, b is the intrinsic reward for exploration, and 3 is the curiosity hyperparameter that scales the intrinsic reward. When designing curiosity-based algorithms, the intrinsic reward is often quantized by the uncertainty of the transition that the agent takes (Bellemare et al., 2016; Azar et al., 2017: Jin al., 2018; Yang & Wang, 2020; Jin et al., 2020). The
Eqqull contribution 'Department Electrical & Computer Engineering, University of California, Los Angeles, California, USA TTeasaki Institute for Biomedical Innovation, Los Angeles, California, USA 'Department of Computer Science, University of Califomia, Los Angeles, California, USA. Correspondence to: Yiran Wang <yiranwang 1027 @ucla.edu>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
agent is then encouraged to take uncertain transitions and explore the whole environment besides maximizing the task reward (Bellemare et al., 2016). As the agent visits a transi- tion more often, the intrinsic reward decays and eventually becomes negligible, thereby making the extrinsic reward dominate the joint reward function, and the agent can then learn to exploit.
We identify the sensitivity of the curiosity-driver explo- ration the coefficient, /3 through a delicately designed example, and accordingly design a novel algorithm Hy- per to resolve the challenges.
We theoretically justify the efficiency of Hyper through rigorous analysis, and empirically demonstrate Hyper performs comparable, even favorable perfor- mance compared to both exploration and exploitation policies.
Curiosity-based algorithms have achieved great success in ipploration-intenivvv problems in recent advancements, which supersedes all previous RL algorithms that solely maximize task reward (Bellemare et al., 2016; Burda et al., 2018; Pathak et al., 2019), and is proven to be theoreti- cally efficient, according to (Auer, 2002). However, their empirical efficiency is highly dependent on the choice of hyperparameter 3. The intricate relationship between the intrinsic and extrinsic reward has an important impact on the behavior of the agent. A small change of f3, which controls the relative weight of the intrinsic reward b and the task reward r, would heavily change such a relationship, leading to the sensitivity of this coefficient.
We empirically analyze the robustness of Hyper to B, where Hyper shows substantially lower sensitivity compared to the original curiosity-driven exploration algorithm.
2. Preliminaries
In this paper, formulate the RL problem an episodic Markoy Decision Process (MDP) (Bellman, 1957) under episodic setting. denoted by (S, A, H, y. IP), where S is the state space, A is the action space, P = {Pr are the transition measures that govern the dynamics of the en- vironment, (s, a) is reward function at step h, H is the episode length. y E (0, 1] is the discount factor. The task of the agent is to learn policy π : S A to maximize the discounted total reward Q = E. 12 h= " (sss,,))) We also denote the intrinsic reward as a(s,a, a, s'), where (s, a, s') is transition. The curiosity-driven exploration method generally aims to learn a policy that maximizes Ex D , (M ap) + by (5h, ags 8h++1) )) instead. We slightly abuse the notation by omitting the sub-scripts, de- noting rh: bb: 8he ap; 8h+1 as r, b, 8, a, s' when the context is clear.
Specifically, when the cumulative intrinsic reward domi- nates the extrinsic one, causes over-exploration, i.e. the agent will keep visiting uncertain transitions instead of ex- ploiting the task. Conversely, if the intrinsic reward is too small to encourage the agent to change from its current policy, the algorithm will likely yield sub-optimal result. Furthermore, large intrinsic rewards will cause problems in the optimization process by introducing a large bias to the fitting of the neural networks thus making the learning pro- cess hard to converge (Schäfer al., 2021; Whitney al., 2021).
Predominantly, existing suriosity-based algorithms exhibit a conservative inclination towards small B. A higher value of 3 would heavily corrupt the task if not carefully tuned for different environments. The involvement of the neural network in practice makes the curiosity-driver methods suffer from optimization instability due to frequent policy changes. This limits the existing methods from using large 33 to sufficiently explore the enviromment and increases the chance of getting stuck in the sub-optimal policy.
3. Warm-up Example
Curiosity- exploration algorithms introduce a bonus term that reflects the novelty of the current transition, into the RL objective Q" Bb(s, a, s')) to reward the agent for visiting novel tran- sitions. We can decompose the joint objective into Q" E(T) + (TT),, where:
a) +
To this end, we propose our algorithm Hyper to solve the problem by controlling the visitation distribution of the agent exploration and mitigate the optimization instability by increasing the persistence of the visitation for adopting large/ B. Hyper is theoretically efficient, and it leverages additional policy to decouple the exploitation learning from the exploration to prevent over-exploration in practice. It regularizes the visitation distribution of the agent's explo- ration to increase the exploration persistence, mitigating the optimization instability caused by frequent policy changes.
{(T) E. r(s.a) h=1
I(T) = E. 7 1(,, 8')l
a, ((s0,
Intuitively, the intrinsic reward coefficient 33 affects how the agent balances the exploration and exploitation by scaling the value of the intrinsic value I. When E(x) > (I(T), the agent will tend to optimize the task return, hence ex- ploiting more. Conversely, if (I(()) > E(T), the agent will
Our contributions are summarized as follows:
2

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
tend to explore more. The curiosity-driven algorithm works ideally when the intrinsic objective (I((z) is initially large enough to help the agent escape the sub-optimal policy, and it gradually decreases and diminishes, then the agent can quickly learn to exploit the diverse dataset and enjoy an overall better sample efficiency (Yang Wang. 2020; Jin et al., 2020). However, practice, only a limited range of can achieve this ideal case. The sensitivity to 3 of the curiosity-driver exploration comes from various aspects, in this section, we analyze this phenomenon and decompose the mechanism behind it.
(a) Layout
(b) 8 - 0.01
We first examine the behavior of curiosity-driven explo- ration methods with different choices of / from a wide range. We consider navigation task in 30x30 room, which only consists finite number of states and four actions taking the agent in four different directions: up, right, down left, the layout is shown in Figure 2(a). The agent starts from fixed initial location at the center colored by blue, and the agent should find and consistently reach the opti- mal goal location at the lower-right corner colored by green and receive a large reward of R. Besides the optimal goal, there is also sub-optimal goal that lies near the center of the room colored by purple, which will provide small reward of Each episode will end when the horizon is met, or the agent reaches either goal. This tabular environ- ment allows us to train the agent without the involvement of function approximation error, which allows us to isolate the behavior analysis of the curiosity-drives exploration meth- ods. The visitation frequencies from UCB-Q agent with different value of 3 are shown in Figure 2, where the grid with brighter color means more frequent visitation.
(c) B = 0.1
(d) 8 = 1.0
Figure 2. Comparison of visitation UCB-Q agent different exploration coefficient, in the environment with suboptimal goal, optimal goal. Higher visitation shown in brighter colors (visita- tion frequency: black red < yellow white). (a) Layout of the environment (b) State visitation UCB-Q with 3 = 0.01, Agent gets stuck in sub-optimal policy duc to insufficient exploration bonus. (c): State visitation of UCB-Q with / = 0.1, the agent finds near-optimal policy. (d): State visitation of UCB with B = 1.0, the agent over-explores and cannot learn to exploit due to the value of curiosity bonus high.
Parameter
range (5e le
R 1.0, r = 0.1 = 0.1, r = 0.02
(5e 31
= 10.0, r 1.0
{le 5e
optimal goal.
100.0, r = 2.0
(5e 11
When ,3 too small, once the agent finds the suboptimal goal, the intrinsic reward is too low to encourage the agent to explore other states and escape from this sub-optimal policy, shown in Figure 2(b). But if we choose improperly large (I((T) dominates E(Tr) throughout the training, as demonstrated in Figure 2(d), the UCB-Q agent will almost uniformly visit each state. Despite the agent finding the optimal goal location, it fails to consistently revisit it even after million training steps.
Table Range of proper 3 for different enviromment parameter
We use UCB-Q (Jin al., 2018) train agents in this environment, which is built upon Q-Learning (Watkins & Dayan, 1992) and leverages upper confidence bound (UCB) (Auer, 2002: Azar et al., 2017; Jin et al., 2018) as the intrinsic reward to encourage exploration. Ide- ally, the UCB-Q agent should sufficiently explore the room without being trapped by the sub-optimal goal, and as the intrinsic reward shrinks, can consistently reach the optimal goal. We run UCB-Q agents with E (5e 1e-3 -e le-2 2e-2,5e 2, 1,-1_,,5e 1,,1,0, 100} in the environment with set-up of R = 1.0,r = 0.1 for million steps and record their final performance. As shown in Figure 1, only the choice of 3 E [0.005, 0.5) can both efficiently escape sub-optimality and consistently reach the
Unfortunately, such a proper range of 3 highly depends on the configuration the environment, in our case, the values of R and r determine the proper range of B. As shown in Table 1, the proper ranges are drastically different with different configurations. Hence, it is almost always neces- sary to perform a comprehensive hyperparameter sweep on 3 to balance exploration exploitation, which limits the applicability of this exploration paradigm.
3

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
4. Hyper: Algorithm and Theoretical Results
4.1. Theoretical Result
In this section, we present an overview of the Hyper algo- rithm, which includes both the provably efficient version (Algorithm 2) and the empirically efficient implementation (Algorithm 1). The difference between the two different versions of Hyper is that they adopt different function ap- proximation methods. The provably efficient algorithm adopts a linear function approximation for us to examine the theoretical sample efficiency and derive a formal worst-case upper bound. The empirically efficient version is designed to work with more expressive function approximations (e.g.. neural networks) and has practical enhancements that im- prove sample efficiency in real-world applications. The two versions share core mechanism of "repositioning and ex- ploration," " which is introduced in the following and will be further elaborated in the next section.
We now present the theoretical results that demonstrate the efficiency of the Hyper algorithm under the linear function approximation framework, whose assumption is described in Assumption 4.1. Under this framework, we form the prov- ably efficient Linear-UCB--yyne
algorithm in Algorithm 2. The main result is that Linear-UCe CCB--yper achieves prov- able efficiency in exploration and guarantees convergence to a near-optimal policy with high probability.
We adopt linear function approximation (Yang & Wang, 2019; 2020; Jin et al., 2020) to derive the bound in our anal- ysis. The main theorem (Theorem 4.2) states that under this approximation, Hyper can achieve sample-efficient explo- ration with polynomial complexity. This guarantees that the algorithm will converge to an optimal or near-optimal policy, even in challenging exploration environments. Specifically, the result provides convergence guarantees in the worst-case scenario, where task reward signals may be sparse diffi- cult to access. We defer the formal proof to the appendix.
The fundamental design principle behind Hyper is to decou- ple exploration and exploitation using two-phase process: repositioning the agent based on exploitation knowledge and exploration based on curiosity-driven driven methods. By reposi- tioning the agent to states where it can gather more useful exploratory data, Hyper ensures that exploration is directed and more persistent. This improves both the stability of the learning process and the agent's 's ability to avoid suboptimal policies.
Theorem 4.2. With any truncation probability p (0,1) for the repositioning phase, it takes at most Ö 5(d"r=)) steps for Hyper to obtain an e-optimal exploitation policy μ with high probability under assumption 1.
While traditional curiosity-driven exploration algorithms can also achieve this worst-case upper bound, the key im- provement introduced by Hyper lies in the repositioning- and-exploration mechanism. This mechanism significantly boosts the sample efficiency of Hyper compared to standard approaches by guiding exploration more effectively, thus reducing the likelihood of suboptimal exploration or unnec- essary revisiting of uninformative states. This distinction is crucial and is further demonstrated in the empirical results in later sections.
The core design choice is this mechanism, which helps stabilize the learning process while still benefiting from curiosity-driven exploration. Instead of purely relying on intrinsic rewards to guide exploration, Hyper uses the exploitation policy to reposition the agent to promising areas of the state space. After repositioning, the agent then explores its environment to discover novel transitions. This helps mitigate the instability that typically arises from purely curiosity-driven approaches, where in- trinsic rewards may dominate and lead to over-exploration or slow convergence.
5. Repositioning & Exploration
In this section, we dive deeper into the design choices be- hind the repositioning wwwpiiiinnnnnnddllllde exploooooot mechanism, which is central to Hyper's 's efficiency as well robustness against B. The goal of this mechanism is to decouple task learning from exploration while regularizing exploration to ensure it remains both persistent and efficient. This decoupling al- lows the exploitation policy to focus on refining task-specific performance while the exploration policy is responsible for discovering novel states in the environment. We want to point out that Hyper shown in Algorithm I is generic al- gorithm that work with any off- off-policy reinforcement learning algorithms and any curiosity methods. As we will see Hyper performs well with TD3 (Fujimoto et al., 2018) as the learning algorithm and Disagreement (Pathak et al., 2019) as the curiosity module in Section 6, and it also per- forms well with DQN (Mnih et al., 2013) along with RND
Assumption 4.1. (Linear MDP, e.g., (Yang& & Wang. 2019; 2020; Jin et al., 2020)). MDP(S, AA, H, r) is linear MDP whose transition P- = [Px) is not necessarily stationary. With a feature map Φ= : S x A + Rd, such that for for any h E [H], there exists d unknown measures (2) (3)
14 (4% (1) 1h : 1hh 3-... / ( over S and an unknown vector Og E IRd, such that for any (8, a) E S x A we have:
Pa(+1s, = = (.),,, rn(s,a) = ((s,a)Too) T
(1)
Without loss of generality, we also assume that [1 a)ll 1
1, and max]]] ||0,1]]] < vā for all (s, as,,,h) h) SX
A x [H]
4

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Algorithm Empirically Efficient Hyper
Actual
1400
1: Initialize: replay buffer D. exploration policy x, ex-
ploitation policy μ., truncation probability p
12000
Optional: Linear decay schedule of
3: for Training iteration k 1, 1.2,..., K do
4: repositioning length +- bounded foondd H)
5: for i = 2...... H do
6: if i < repositioning.
then 7: # Repositioning phase
800
Use x to step in the environment
else
Stops
10:
# Exploration phase
Figure Decoupling causes distribution-shin where the exploita- tion policy drastically overestimates its value (yellow), yielding poor performance (blue).
11:
Use μ to step in the environment
12:
end if
13:
Store the transition in buffer D Policy Improvement
14:
(Burda al., 2018) in the Appendix A.5
15:
Sample a batch of data B D
16:
Update и with intrinsic reward 6 using B
5.1. Isolation of Task Learning Regularization Over Exploration Visitation
17:
Update j without intrinsic reward b using B Update b using B
18:
19:
end for
The decision to decouple the learning of task rewards from exploration was driven by the instability observed when using large curiosity coefficients (B) in traditional algo- rithms. In such cases, intrinsic rewards often overpower task rewards, leading to over-exploration and poor task per- formance. To address this, Hyper employs a repositioning phase before each exploration phase. In the repositioning phase, the agent acts according to the exploitation policy, moving it promising states where task learning is most likely to be effective.
20: Decay based on the decay schedule
21:
end for
We adopt a truncation probability that controls the stop- ping point for the repositioning phase, striking a balance between exploration and exploitation. Early the train- ing process, repositioning should not move the agent far from regions where it has gained task knowledge. To achieve this, we initially set 1 7, where is the dis- count factor. This value aligns the repositioning phase with the effective planning horizon of the agent's exploitation policy, ensuring that repositioning is meaningful without over-reliance on untested areas of the environment.
This approach prevents the exploration policy from wan- dering too far from regions where the agent has already gained useful task knowledge, avoiding the risk of over- exploration. Additionally, by regularizing the exploration visitation-ensuringg that exploration is conducted from states where the agent has already gathered substantial task- related experience-Hyper reduces the instability caused by frequent policy changes in traditional curiosity-driven methods.
As training progresses, the exploitation policy becomes more stable and better at identifying high-reward regions of the environment. Hence, we gradually increase the length of the repositioning phase by decaying the truncation probabil- ity. This allows the agent to explore more distant areas of the state space as it becomes more confident in its task-specific knowledge, further improving the exploration process.
This combination of isolation and regularization mitigates the distribution shift problem often observed decoupled methods that separate task learning from exploration. With- out repositioning, the exploitation policy can become de- tached from the data collected during exploration, leading to overestimation of value functions and poor performance in real-world tasks. Hyper addresses this by aligning the data collection process between exploration and exploitation, ensuring more reliable value estimates.
5.3. Truncating the Geometric Distribution
To ensure a balanced exploration process throughout train- ing, we also truncate the geometric distribution used to sample the repositioning phase length. Specifically, in an episodic setting, sampling directly from a geometric dis- tribution can lead to disproportionately long repositioning phases, particularly in environments with shorter horizons. Consider a setting that horizon H = 200, discount factor ? = 0.99, where the truncation probability will decay from p = 0.01 to p = 1 = 0.005. we stop the reposi- H
5.2. Truncation Probability p
The length of the repositioning phase is crucial in determin-
ing how far the agent moved before exploration begins.
5

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
p=0.01
p=0.0083
2018) as the reinforcement learning algorithm and with Disagreement (Pathak et al., 2019) the intrinsic reward when curiosity-driven exploration is used. Specifically, we consider the following baselines:
Gecemic Braake Dowenk
Probability
p=0.0067
p=00005
TD3 (Fujimoto et al., 2018) Off reinforcement learning method that uses random action noise for explo- ration.
Curiosity Driven Exploration (Curiosity) Curiosity- driven TD3 agent, using Disagreement intrinsic reward for exploration.
Repositioning Phese Length
Decoupled Reinforcement Learning (Schäfer et al., 2021) (Decouple) Agent that has additional exploitation pol- icy for exploiting the task by learning from the exploratory data collected by the exploration policy offline, as outlined in the previous section.
Figure 4. Distribution of length of repositioning phase (green) Bounded geometric distribution (blue) Original geometric distribu- tion.
tioning phase with the probability p 1-1 initially equivalently sample the length from geometric distribu- tion with parameter a large amount of probability will accumulate at H. As shown in Figure 4 (blue), the reposi- tioning phase is stopped with probability p. there is a very large probability that will consume one whole episode from the beginning of the training. As the training proceeds, the truncation probability decays, and this probability keeps increasing. This phenomenon will cause Hyper to be not as sample efficient in some tasks with short horizon and requiring efficient exploration.
All basclines are evaluated on various environments that differ in exploration difficulty, exploitation difficulty, and function approximation difficulty. The detailed setting of the environments is deferred to the appendix. Decouple, Cu- riosity and Hyper all use the Disagreement method (Pathak et al., 2019) to compute the curiosity bonus for fair compar- ison.
6.1. Performance
To address this issue, we use a bounded geometric distribu- tion to sample the reposition length before every episode. The original geometric distribution probability function is defined on all positive integers, which is not desirable in this case. As in the episodic RL setting, the probability of values larger than H accumulates to the marginal density of H, causing the undesirable spike shown in Figure 4. We instead restrict the domain to the range [1, H to avoid the probability accumulation, formulated as below:
Figure 5 depicts the performance of agents in the continuous goal-searching tasks (Fu et al., 2020) and locomotion tasks (Todorov et al., 2012) averaged over five trials, the shaded area represents the empirical standard deviation. The full results of the performance comparison and environment setup deferred to the appendix.
In the goal-searching tasks (Figure 5), the agent is spawned following some initial distribution and will receive zero re- wards until finding the fixed goal location. Hence the goal of the agent this series of tasks is to first explore the enviromment and find the goal location, and then learn to exploit the task by consistently revisiting it. Two mazes with differences in size used in the experiment: Medi- umMaze and LargeMaze, where it takes optimal policy taking approximately 150 steps to reach the goal location in MediumMaze and 250 steps in LargeMaze. We differentiate the difficulty of tasks in the horizon of every episode. A shorter horizon results steps, which requires the agent to find a sufficiently good policy obtain positive feedback from the environment. The horizon for each task is shown in the Table 2. In this set of experiments, we do not tune 3. We apply / = 1.0 for Hyper, Decouple, and Curiosity agents, to ensure fair comparison.
p(1-))11 ΣH P(-P))
OSISH
PLL =
otherwise
Figure 4 (green) depicts the shape of the resulting distribu- tion for p at different stages of the training. Despite there being an increasingly large probability for Hyper to have a longer repositioning phase, still has sufficient opportunity to explore, which enhances Hyper's capability of balancing exploration & exploitation different cases.
lower tolerance for redundant
6. Experiments
We evaluate the performance and the robustness of Hyper in this section, with the comparison to baselines with dif- ferent strategies of balancing exploration & exploitation. We implement all algorithms with TD3 (Fujimoto et al.,
TD3 explores inefficiently with random actions, which
6

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Decouple
Curiosity
TD3
Hyper (Ours)
Popper Dence
HolfChectah Dense
Ann Dense
Hopper Sparse
14000
2000
19000
Average Performance
1290
4000
2000
1850
0.0
0.2
0.4
0.6
0.0
1.0
0.0
0.2
9.4
0.6
0.0
1.0
0.0
0.2
0.6
0.6
0.8
1.0
0.0
0.2
0.6
0.6
08
1.0
1e5
1e6
1e6
1e6
Walker
MediumiMas
1.0
560
600
360
9.5
0.5
07
1.0
0.0
106
166
Steps
Figure 5. Performance of Hyper and baselines. For locomotion tasks, the performance is measured by the episodic cumulative reward, for navigation tasks. is measured by the success rate instead. Each line is averaeed over runs with different random seeds.
Decouple
Curiosity
Hyper (Ours)
Waleerad
HarCChotihh Denso
HalCCheetth-Sppre
Wallordd Sparso
LargeMazze Medium
0.25
172
61
12
1303
61
18.0
605
01
Figure 6. B-Sensitivitt analysis. The x-axis represents the different choices of 8, y-axis represents the final performance after 1M steps for the first four tasks, 2M steps for LargeMaze-Medium. The point in the graph represents the mean value over 5 runs, and the bars depict one standard deviation. The experiment shows that Hypernot only enjoys better robustness to compared to other methods, but also enjoys a smaller variance.
makes it hard perform well in exploration-intert -intensvinn tasks. In the sparse reward locomotion environment (Hopper- Sparse, Walker2d-Sparse), it fails to receive any reward in any trial. In the navigation tasks, despite it can quickly learn to exploit after finding the goal location, it can only manage to find the goal location once in all trials, indicat- ing its lack of efficient exploration. Curiosity explores the environment efficiently and succeeds in the sparse-rewan reward locomotion tasks. It also performs comparably, even favor- ably, in bense-reward locomotion tasks. However, the hard navigation tasks, show the problem in exploitation. It man- ages to find the goal location, however, it never manages to learn to properly exploit the task. The Decouple agent can learn successful policy based on a limited number of success trajectories collected by the Curiosity agent in
MediumMaze- Mediium and LargeMaze- -Mdiiuu,, but fails to do in the hardest navigation task, Large Hard. The Decouple agent also struggles with high nigh-dimensional locomotion tasks due to distribution shift.
Hyper performs comparable, often time favorable all the tasks. Notably, Hyper is the only agent that consistently tackles the task. Compared to the failure of the Decouple agent this task, it suggests that the regularization of the ex- ploration visitation and the exploration persistence is erucial in this environment. The decouple agent fails in this task because it has no control over the exploration policy. and as the exploration policy cannot collect enough successful trajectories, it would be difficult for the Decouple agent to learn exploit, whereas Hyper can guide the exploration policy towards the promising region, increasing the explo-
7

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
ration persistence, and the exploitation in turn benefits from the high-quality data.
but uses random actions. However, this method requires the environment be either deterministic resettable for the agent to have access to some domain knowledge, which is generally unrealistic.
6.2. B Sensitivity Analysis
We now present the performance of Hyper and Curiosity with different intrinsic coefficients 3.
Bayesian RL is also proposed to exhibit efficient exploration (Ghavamzadeh et al., 2015; Fortunato et al., 2017; Osband et al., 2016), which leverages the ideas of Bayesian infer- ence to quantify the uncertainty and encourage exploration accordingly. Bootstrapped DQN, the most practical variant of this line of work, wisely combines the idea of Bayesian inference and the property of the neural network for the agent to exhibit diverse and exploratory behavior and sig- nificantly improve the performance of DQN on a handful of environments. However, it does not fundamentally im- prove the exploration capability from the naive e-greedy exploration, it fails in exploration exploration-intensivee tasks.
We evaluate the final performance of Curiosity, Decouple, and Hyper agent over multiple trials with each different value of / choice on five environments. As shown in Figure 6, the Curiosity agent shows peak performance with differ- ent values of 3. Typically, the performance of the Curiosity agent peaks with small value of and drastically drops as > 10, whereas Hyper shows considerably more consis- tent with different 3 values, indicating its robustness to this hyperparameter. It is worth noting that, Hyper generally shows better tolerance to the large value of 3. which allows one to apply large 3 with Hyper without prior knowledge of the environment, to exhibit more exploratory behavior and prevent from being stuck in sub-optimality.
Options-based methods (Sutton et al., 1999; Bacon et al., 2017; Dabney et al., 2020; Chen et al., 2022; Kim et al., 2023) are also proposed for tackling the exploration problem by temporally abstracting the actions, resulting in conceptu- ally easier policy learning and more consistent exploration. This paradigm is closely related to Hyper, whereas options- based methods mostly train additional high-level switch policy to decide action selection protocol. (Kim et al., 2023) proposes an algorithm (LESSON) that automatically selects from exploitation and exploration policy to take action at every step. which yields superior results compared to orig- inal exploration and other option- based methods. We also compare Hyper to LESSON, examining the efficiency of Hyper. The results are deferred to the appendix.
7. Related Work
Exploration & exploitation is a long-standing research topic in the RL community (Thompson, 1933; Auer, 2002). Bal- ancing exploration & exploitation the key to efficient RI.. Curiosity-drived exploration has emerged as a promising paradigm for achieving efficient RL. A line of theoretical research focuses on the optimal asploration-explotataii trade-off in RL with theoretically sound intrinsic rewards (Azar et al., 2017; Jin et al., 2018; Yang & Wang, 2020; Jin et al., 2020). The statistical properties of the environment (dynamics, rewards) and the intrinsic reward are assumed to be known, which allows one to find coefficient / for the optimal trade-off between exploration and exploitation.
Recently, some dedicated methods have been for mitigating the hyperparameter sensitivity of the exploration methods (Liu et al., 2021; Whimey et al., 2021; Schäfer et al., 2021). Among these methods, (Schäfer et al., 2021) is the most related to our method, as it uses the decoupling method as we outlined in Section to mitigate the problem. is efficient in low-dimensional cases, but hard to scale to tasks with high-dimensional state and action spaces, we thoroughly demonstrated in the experiment.
Recently, this idea has been applied to practical RL al- gorithms and achieved great success in solving hard- exploration problems (Bellemare et al., 2016; Ostrovski et al., 2017; Burda et al., 2018). The common approach is to employ neural networks to estimate a transition's 's uncer- tainty and use this approximate uncertainty as the intrinsic reward b for encouraging exploration. Various notions of un- certainty were used: error on dynamics prediction (Oudeyer et al., 2007; Pathak et al., 2017; 2019), state visitation den- sity (Bellemare et al., 2016; Ostrovski et al., 2017; Machado et al., 2020), entropy gain (Tang et al., 2017; Choshen et al., 2018; Burda et al., 2018), fix-target prediction (Burda et al., 2018), etc.
8. Conclusion
We propose Hyper, a novel algorithm that leverages two distinct policies, that improve the robustness of curiosity- driven exploration by regularizing the exploration visitation. We theoretically justify its sample efficiency, that Hyper explores the environment efficiently. We also empirically validate its performance and robustness compared to the ex- ploitation algorithm, curiosity driven exploration algorithm, and previous attempts at solving this problem.
Go-Explore is a powerful paradigm for efficient exploration that is not sensitive to the hyperparameter (Ecoffet et al., 2019). The algorithm keeps track of the state visitation, re- turns to the least visited states, and then explores from there. This paradigm does not use curiosity to exhibit exploration
8

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Impact Statement
Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., and Clune, J. Go-explore: approach for hard- exploration problems. arXiv preprint 1rX1v:190..1099, 2019.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., et al. Noisy networks for exploration. arXiv preprint arXiv: 17066 10295, 2017.
References
Abbasi- Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Fu, J., Kumar, A., Nachum, O., Tucker, G., and Levine, S. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint WrXiv:2004.072194 2020.
Arulkumaran, K., Cully, A., and Togelius, J. Alphastar: An evolutionary computation perspective. In Proceedings of the genetic and evolutionary computation conference companion, pp. 314-315, 2019.
Fujimoto, S., Hoof, H., and Meger, D. Addressing function approximation error actor-critic methods. In Interna- tional conference on machine learning, pp. 1587-1596. PMLR, 2018.
Auer, P. Using confidence bounds for exploitation- exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Ghavamzadeh, M., Mannor, S., Pineau, J., Tamar, A., et al. Bayesian reinforcement learning: survey. Founda- tions and Trends in Machine Learning, 8(5-6))359-443, 2015.
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International Con- ference on Machine Learning, pp. 263-272. PMLR, 2017.
Jin, C.. Ahu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? Advances neural infor- mation processing systems, 31, 2018.
Bacon, P.-L., Harb, J., and Precup, D. The option-critic architecture. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Jin, C.. Yang. Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. Unifying count-based ex- ploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
Kim. W. Kim, J., and Sung, Y. Lesson: learning to integrate exploration strategies for reinforcement learning via an option framework. arXiv preprint arXiv:2310.03342. 2023.
Bellman, R. A markovian decision process. Journal of mathematics and mechanics, pp. 679-684, 1957.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 0266600000.0..... 2019.
Liu, E. Z., Raghunathan, A., Liang, P., and Finn, C. Decou- pling exploration and exploitation for meta-reinforcement learning without sacrifices. In International conference on machine learning, pp. 6925 6935. PMLR, 2021.
Burda, Y., Edwards, H., Storkey. A., and Klimov, O. Ex- ploration by random network distillation, arXiv preprint arXiv: 1XI0:1810.12894 2018
Machado, M. C., Bellemare, M. G., and Bowling, M. Count- based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp- 3125-5133 2020.
Chen, E., Hong, Z.W.., Pajarinen, J., and Agrawal, P. Re- deeming intrinsic rewards via constrained optimization. Advances in Neural Information Processing Systems, 35: 4996-5008, 2022.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 1 12.56002 2013.
Choshen, I.,, Fox, L.,, and Loewenstein, Y. Dora the explorer: Directed outreaching reinforcement action- selection. arXiv preprint arXiv: 084400012,, 2018.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M.. Fidje- land, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. nature, 518(7540): 529-533, 2015.
Dabney, W., Ostrovski, G., and Barreto, A. Temporally- extended { (Vepsilon)- (acillonngrreee -greddy exploration. arXiv preprint 2xXiv:000600/78/ 2020.

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016.
Watkins, C. J. and Dayan, Q-learing. Machine learning. 8:279-292, 1992.
Whitney, W. F., Bloesch, M., Springenberg, J. T., Abdol- maleki, A., Cho, K., and Riedmiller, M. Decoupled exploration and exploitation policies for sample-efficient reinforcement learning. arXiv preprini 2rx11:2000:220000 2021.
Ostrovski, G., Bellemare, M. G., Oord, A., and Munos, R. Count-based exploration with neural density models. In International conference machine learning, pp. 2721- 2730. PMLR, 2017.
Oudeyer, P.-Y., Kaplan, F., and Hafner, V. V. Intrinsic motivation systems for autonomous mental development. IEEE transactions on evolutionary compulation, 11(2): 265-286, 2007.
Yang, I.. and Wang, M. Sample-optimal parametric q- learning using linearly additive features. In Interna- tional Conference Machine Learning, pp. 6995-7004. PMLR, 2019.
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driven exploration by self-supervised predic- tion. In International conference on machine learning, pp. 2778 2778-2787. PMLR, 2017.
Yang. and Wang, M. Reinforcement learning feature space: Matrix bandit, kernels, and regret bound. In In- ternational Conference Machine Learning, pp. 10746- 10756. PMLR, 2020.
Pathak, D., Gandhi, D., and Gupta, A. Self-supervised exploration via disagreement. In International conference on machine learning, pp. 5062-5071, PMLR, 2019.
Schäfer, I.., Christianos, F., Hanna, J., and Albrecht, V. Decoupling exploration and exploitation in reinforcement learning. ICML 2021 Workshop on Unsupervised Re- inforcement Learning. 2021.
Silver, D., Huang, A., Maddison, C. Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844 489, 2016.
Silver, D., Schrittwesee, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., al. Mastering the game of go without human knowledge. nature, 550(7676):354-3355 2017.
Sutton, R. S., Precup, D., and Singh, S. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2): 181-211, 1999.
Tang, H., Houthooft, R., Foote, D., Stooke, A., Xi Chen, O., Duan, Y., Schulman, J., DeTurck, F., and Abbeel, exploration: A study of based exploration for deep reinforcement learning. Advances neural information processing systems, 30, 2017.
Thompson, W. R. On the likelihood that one unknown probability exceeds another view the evidence of two samples. Biometrika, 25(3-4):285-25 2944, 1933.
Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics engine for mrodel-based control. In 2012 IEEE/RSJ inter- national conference on intelligent robots and systems, pp. 5026-5033. IEEF, 2012.
10

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
A. Implementation & Experiment Details
A.I. Implementation of Agents
We implement Hyper, Decouple, and Curiosity based on the official implementation of TD3 (Fujimoto et al., 2018) along with the original hyperparameters reported in the paper. For adapting the intrinsic reward method with TD3, we update the Disagreement (Pathak et al., 2019) intrinsic reward model for every environmental step using 25% of data of each batch prevent the intrinsic reward from shrinking too fast following (Burda et al., 2018). In the locomotion experiments, set the truncation probability p to be 0.01 initially, and decay to 0.001, as we discussed in Section 5.
A.2. PointMaze
Our experiments continuous navigation tasks conducted in the PointMaze domain (Todorov al., 2012; Fu et al., 2020). PointMaze mostly serves fully observable goal-reaching benchmark, where the agent observes 6 values at state: current x-axis position, current y-axis position, current x-axis speed, current y-axis speed, goal x-axis position and goal y-axis position. And the agent is allowed to take a 2-dimensional action, that controls the x-axis acceleration and y-axis acceleration respectively.
In our experiment, we turn into a sparse-reward goal searching domain. In our experiment, the agent only observes its own position and state, but not the goal location. The agent will only receive positive reward once reaching the goal. In this series of tasks, the agents only need first find the goal location, but also to consistently reach the goal. Despite the environments consisting of low-dimensional state and action space, this series of experiments examines and distinguishes the capability of balancing exploration & exploitation of agents.
Figure 7. Layout of environments used continuous navigation experiments: (Left) MediumMaze (Right) LargeMaze
Figure shows the layout of the MediumMaze and LargeMaze, where the initial location is marked with the green circle, and the goal location marked with the red circle. For every episode, the agent is spawned randomly near the initial location, and the goal is spawned near the goal location. It takes approximately 150 steps for an optimal policy to reach the goal in MediumMaze and 250 steps in LargeMaze (depending the randomly spawned agent and goal location).
We differentiate the difficulty of each task by restricting the horizon of each task. Specifically, tasks with shorter show less tolerance to redundant steps, and the agent will only receive positive feedback by exploring a more optimal trajectory. The detailed setup is shown in Table 2, where Optimal #Steps means the number of steps that an optimal policy needs to take from the initial location to the goal location, the variation is caused by the randomness when initializing the initial and goal location.
Task Name
Optimal #Steps
Horizon H
MediumMaze Easy
= x50
500
MediumMaze-MMdiim
1550
200
LargeMaze-Eas
=250
1000
LargeMaze-Mediue
=250
500
LargeMaze-Hard
~550
300
Table 2. Difficulty of navigation tasks

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
A.3. MuJoCo Locomotion
For the locomotion environments (Todorov et al., 2012), the agent starts idle and the task is to control the robot to move forward as fast as possible within 1000 steps, and the episode will end if the robot falls down. The agent will observe the position, velocity, and angular velocity of the joints of the robot, and take actions to control the torque on all the joints. In the dense reward version, including Hopper, Walker2d, HalfCheetah, Ant, and Humanoid. At each step, the agent will receive a performance reward proportional to its velocity and a constant "healthy reward" if it remains in healthy position (i.e. not falling). In the sparse reward version, including SparseHopper, Sparse Walker2d, SparseHalfChcctaa. and SparseHumanoid, the agent will not receive the healthy reward, and will only get a unit reward once its forward speed exceeds some threshold.
A.4. More Experiment Results
We present the full set of experiment results in this section. TD3 and Curiosity agent perform well in some of the tasks, depending on the property of the environment, whereas Hyper performs comparable to the best-perforning algorithm in every task.
Decouple
Curiosity
TD3
Hyper (Ours)
1000
470
Darin
Walee Odd Sparie
Halfhwettal Sparee
A000
3888
2000
100
1000
Humanall Spare
Medumiiaa Medium
Mediumilaze Easy
Langelazze Hedium
190
160
-200
166
166
LangMMazc
LangeMaze
1.2
166
Figure 8. Full experiments results for performance comparison.
12

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
LESSON
Hyper (Ours)
MiniGrid-EEptty6x1166
MiniGrid-Fetchkka
MiniGrid-UnioccPPccuup
MinisrddLLavaroossnnghht
1.00
1.00
0.4
0.75
0.75
0.3
0.2
0.50
0.2
0.50
0.1
0.25
0.1
0.00
0.0
0.00
0.0
1e6
1e6
1e6
1e6
Figure MiniGrid Performance of Hyper LESSON. The x-axis represents the number steps, y-axis represents success rate.
A.5. Comparision with Oased Method
We compare method with the recently proposed options- based exploration method LESSON (Kim et al., 2023). We implement Hyper based on official implementation provided by (Kim et al., 2023), which uses DQN (Mnih et al., 2013) as the RL algorithm, and RND (Burda et al., 2018 8) as the intrinsic reward. We also use the same set of hyperparameters provided by the original paper.
We apply Hyper the MiniGrid domain, on which LESSON is tested the original paper. The comparison shown the Figure Hyper performs comparable in Empty 16 16 and Fetch8x8 tasks, and outperforms LESSON in UnlockPickup and LavaCrossingSNN, which further validates the efficiency of Hyper.
A.6. Hyperparameters of Experiments
1. HYPERPARAMETERS FOR TD3-BASED ALGORITIMM
Hyperparameter
Value
Learning Rate
3e-4
Intrinsic Reward Learning Rate
le-4
Batch Size
256
Policy Update Delay
2
Optimizer
Adam (256, 256)
Q-Network Architecture
Actor-Network Architecture
(256, 256)
Activation function
ReLU
A.6.2. HYPERPARAMETERS FOR CURIOSITY-DRIVEN EXPLORATION
Hyperparameter
Value
8
1.0 (0.01, 0.001)
P
Learning Rate Disagreement Model
lc-4
Disagreement Ensemble Size
5
B. Proof of Efficiency of Hyper
Theorem B.1. With any truncation probability p (0, 1) for the repositioning phase it takes most Ö D(="H) steps for MCnear-UCB Bypee to obtain an c-optimal exploitation policy with high probability under assumption B.2.
In this section, we provide comprehensive proof for theoretically justifying the efficiency of Hyper under linear function approximation assumption Secar-UB--Haaae which is formally stated in Theorem B.I. To theoretically justify the efficiency of Hyper, the core assumption the following:
13

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Algorithm 2 Provably Efficient Linear-UCB-HHpprr
Requires: Parameters À > 0, > 0, > 0, > 0, Horizon H, Feature Mapping Φ, Truncation probability p > 0, Weights Wa, for optimistic Q-function, Q-function wi for exploitation, Wд for pessimistic Q-function for all E [H]
x S 0
Requires: Clipping function clip(æ)
a E (0, H) Geometrical distribution Geom
H
x 2 H
for k 1, K do Receive the initial state sf Sample length L ~ Geom(p) for the first phase
Repositioning phase
for step 1, 2, .... L* do
Take action / arg maxaEA Qh (sf i a; wh), and observe 6/+1 end for # Exploration phase
for step h = L + 1, LA + 2.,,,, H....,d.. do
Take action a +- arg max (s a; W.), and observe # end for # Policy Improvement for h H, H 1,... 1 do
if L 0 then
Au Σ
2 of (5 77 + I
Wa + A₁ D 0 (5% d)) + max, Qh+1(87) ++1 wall
Wa A (
(1 x max. Q (s) +1
a; wr]]
WA + A E O [r. a ) + max, Q a; W.
Q wh) clip wh ((:)))
Q (.)) clip wT)((.)) Blo(s)) ( (1.-1
(w))) - clip (wT Bl - )]}
end if
end for end for
Assumption B.2. (Linear MDP, e.g., (Yang & Wang, 2019; Jin al., 2020)). MDP(S, A, H,P, is linear MDP whose
transition P : [P is not necessarily stationary. With a feature map & S x A + Rd, such that for for any h E [H].
there exists unknown measures μ4 = (ph 1/ Ph ....,1%% (8, a) E S we have:
(1) (2) (3)
(()) over S and an unknown vector 6, E Rdd, such that for any
(A a) ((s, (m(+) and (n(s,a) a)
(2)
Without loss of generality, we also assume that [| a)ll s 1, and (I) 10 s va for all (8, a, h) A x [
Specifically, adopt the UCB-enhancee least-square value calue-iteration (Jin et al., 2020), theoretically well-studied off-policy RL algorithm our proposed Hyper framework, which we refer to as UCB-Hyper. The algorithm follows the generic Hyper framework shown in Algorithm ??. it first collects data in a two-phase manner, and updates the policies afterward. Note that Linear- -icear-UBB-ER UCy-- adopts an additional pessimistic Q-function with weights w/ this Q-function is not used in Linear-UCB--Hpeer but serves as a tool for our proof. put it in the Algorithm just for the sake of clarity in terms the definition and the update rule.
For simplicity, consider 7 1.0 without loss of generality, denote Wh. Wh. Wa at k-th episode as w/. w wh. and denote Qn (,, wx), : (:.: W.. at k-th episode as (+))),, )), (+..)) when the context clear. Proposition B.3. Bellman equation: (Bellman, 1957)
(7 (n) + + (it and (s)
((s.a)
(3)
(8) = (s. + + Vi (8) and Vi+
((s
(4)
14

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Proposition B.4. (1t" realizability (Jin el al., 2020)) For linear MDP, for any policy n, there exist weights heEM such that for any (8,0, h) 8 x (H), we have Qh a) Φ(88 a)² w
Proof. By the Bellman equation we have:
= = + (PA = ((s,a)"Tn +/8 Vitt(ss)) als,,)"duu(
= a)) (0n /s (s)
(5)
This directly shows that Q7 is linear with respect to features Ø
Lemma B.5. (Boundedness of wi. (Jin al., 2020)) Under Assumption B.2 for any fixed policy n, let heihn be the weights such that Q7, a) = (0(s, a), wi) for all (s, h)) E S x x [H] Then, we have
|! 2HHVd 4A [M]
Proof. By the Bellman equation, we have:
(),s) = (rh PAV.)))) (s, vh [4]
And by the Proposition B.4, we have:
W = 0n + { Vitta (s')
dup (s')
Under the normalization conditions of Assumption B.2 the reward each step is in [0,1], have:
Vitta (
< H, Vs' ~ PP(ls,))
Thus, ||0all S Vd, and [| VR+1 (5) dun (s') < Hvd. This concludes the proof.
Lemma B.6. (Bound W in Algorithm 2 (Jin et al., 2020)) The weight w Algorihtm 2 satisfies:
wh S 2H dk/A
Proof. For simplicity, we denote the index set U = fi e [K] L' 0}. i.c. the index of episodes in which the roll-in length is O. For any index of episode t E [K]. we denote [k] max(U*) when is not empty, and [k] = 0 otherwise, i.e. the last time we encounter an episode whose roll-in length is O. Suppose v e Id is an arbitrary vector, we have:
|k|-1
W =
T
Σ
(7) + max Qu+1 (sh+1:
(6)
[R]-1
<
Σ
T
(A -1
2H
(7)
==1
[K Σ V
[k]-1
(A
v
Σ
(Φ)) T
(A
2H
(8)
< M
(9)
where the first step follows the algorithm construction, the second step follows directly from Schwarz incquality, and the last step follows from Lemma B. and the third step follows from the fact that w = maxy: |v [T]l
15

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
This implies that | 2H / and by definition of [ki] have | s 2H 2H /alkk/ s 2H v dk//, which concludes the proof.
Remark B.7. Let 3 d d. /.og.ooog(2dd (lggToTg max, Qs a)), and (.))) clip ((w] (' A 0 ((: 0, H). By similar approach as in the proof of Lemma B.6, the weight w also satisfies:
for some proper constant e' > 0, w + An a añ)) +
w 2H 2 dk/A
This result is direct, as the proof of Lemma B.6 does not leverage any property specific wf.
We then define a high-probability event that bound the approximation error of our optimistic value function.
Lemma B.8. (High Probability Event on Approximating Optimistic Value Function (Jin et al., 2020)) Under the setting of Theorem B. I, let eg be the constant in the definition of (9, such that
B C3 dH (lg((22T0)))
There exists and an absolute constant C. that is independent of ca such that for any fixed E [0, 1}, if we let the event that:
v(k, [K)
Vi (sh+1) - Ih Vhta (5% aR)
<C-dHVX
(at)
where X log (2 (c3 1) /T/p), then P(E) 2/2.
Proof. By Lemma B.6, have:
w S 2H dakA, v(k,h) E [K] x [H]
Also, by the construction of AA, its smallest eigenvalue is lower bounded by A. Combining with Lemmas C.5 and C.7, for any fixed constant > O, we have:
Σ
h+1 (sh+1)
Pn Dhen (5h, an)]
(10)
(At)
S 2 log
d
h +
dlog
1+
8H vdk
evā )
d &olog log (++
8dl/233 E²
log
2
8k2E2
(11)
2
By plugging in À = and B .dH (8 this inequality, where C' is positive constant independent of cg. and picking dH/ k have:
Σ
Φ% h+t (sh+2) - PA V (5%, a
SC d 112 log (2 + dT)p)
(AR)-
This concludes the proof.
Lemma B.8 provides the bound on the approximation of the optimistic value function, we can then bound the pessimistic value function in similar way, as by Lemma C.8, these two functions classes share the same upper bound on the covering number.
16

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Lemma B.9. (High Probability Event on Approximating Pessimistic Value Function) Under the setting of Theorem B.I, let cz be the constant in the definition of B', such that
8 c - dH Vlog(20T/))
There exists and an absolute constant C' that is independent of cœ such that for any fixed p E [0, 1], if we let be the event that:
h(k [K] [
Σ Φh [ (sh-1) Ph Vhttt (5h [sh]
-C'
(A7)
where X log (2 (car d)TT /p), then P(E) 2 p/2.
Proof. By Lemma B.6, we have:
[ S 2H dk/A, V(k,h) E [K] (M]
Also, by the construction of A its smallest eigenvalue is lower bounded by A. Combining with Lemmas C.5 and C.8, for any fixed constant > 0, we have:
Σ 2 h+1 (sh+1) Pn PA (8%,
(12)
(1t)
+ A dlog
8/1 d
8d2 E²A
2
Sk-
S 2
log
d d log (1
log
(13)
2
eVA
p
By plugging in À = 1 and 8' = C ddd ddH (log(2dT/5))) (6) to this inequality, where O' is a positive constant independent of cæs, and picking c = dH/k / we have:
Σ
Sh Wh+1 (oh+1) Pr P 1 (8h, ahl]
C dd dHH log (c + 1)dT/p
(12)
This concludes the proof.
Lemma B.10. (Optimistic Policy Action- Value Estimation Error (Jin al., 2020)) There exists an absolute constant C3 such that for = cg dH /log(2dT))) (5), and for any fixed policy n, on the high-probability event & defined in Lemma B,8 we have for all (s, h, E S x x H x [K] that:
(p(s,a), w (T(s,a)= = =P (Vitiz Vitza) (s,a) A5(s,)),
for some (s,a)) that satisfies (s) & / a(s, (At) -1 ((s,a).
Proof. By Proposition B.4 and the Equation 3, we know for any (s, h) E S x A x H
(T( = ()(s, w = (rr + PAV (s,a) a)
And the residual between W w is given by and can be decomposed the following:
17

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
wh
w = -AA)) -1
Σ 1% Th +
Vh+t1 (oh+1) - w
(14)
k-1
V/tt1 (0h+2) - PuVi+t (5% (R) oid}}
= -(A))
Xw +
Σ
(15)
r=1
(A
w + (AA)
Σ
2 [Vitz (sh+1)
Pr Vht2 (0% (5%
(16)
42
R-1 Σ
+ (A
(Veti
Vitt) (sh) ah)
(17)
qa
Now, we bound the terms on the right-hand side individually. For the first term,
( a). qn>) = | (0 a). (At) wx)l VA Vo(s,a) (A+) ((s,a).
For the second term, given the event & defined in Lemma B.8, we have:
((((s,) 92) S co dH /x / a() (MR) Ø(s,a)
for an absolute constant eo independent of cB, and X = log (2 (cB + 1) dT dTppp. For the third term,
(b(*, qs)
((),a), (4%) Σ 4T (vh.. - vitss) (oh.04)
(18)
()s. (At) Σ 0% (oF)T f (9it, vRee)) (x") dun (4))
(19)
(ola.a). / (v/++1 vi+ta) (z)) den (1)) -2 (oc.e)) (at) ( (P/tt -ittt)) (a)) dun (+))
(20)
where, by Assumption B.2 Equation 1, we have
P1 = Pn (Vitz Vitta) (s, 1p2l <2HvdxV á(s,a)T (At) @(s,a)
Finally, since (Ø(s, a), w/) (R(s (Ø(8, a), w -wi) (Ø(s,a). q1 + 9 qs), by Lemma B.5 and our choice of parameter X, we have
(M(s, - (7 Pr (V/+1 Vit (s, (s, < dH o(s (AA) ((s,
for an absolute constant c' independent of cz. Finally, to prove this lemma, we only need to show that there exists a choice of absolute constant Cg so that
d' Vv 1 log (ce + 1) S cavi
(21)
where e = log(2dT/p). We know & E [log 2, oo) by its definition, and c' is an absolute constant independent of cg. Therefore, we can pick an absolute constant eg which satisfies c' d''log 2 + log (cs + 1) < ca 2 2. This choice of cg will make Equation 21 hold for all E [log 2, oo), which finishes the proof.
18

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
With similar approach, can bound the action-value approximation for the pessimistic policy.
Lemma B.11. (Pessimistic Policy Action- Value Estimation Error) There exists an absolute constant eœ such that for 3' car dH / Mlog(ddT/// and for any fixed policy n, on the high-probability event & defined in Lemma B.9 we have for all (s. k) E SSx A x [ x [K] that:
(Ø(s.a). wh) - ())),))= = (Vi+1 - Vitt) (s, + (s,,))
for some ( a) that satisfies | s 3' VV ()7 (At) ((8,a).
Proof. Similar to the proof of Lemma 10,0, we decompose the residule between w and w as the following:
W w = -AA)
[rA +
V/4t1 (sh+1)] W
(22)
k-1
- -AA))
Aw + Σ
1 Vi++2 (sh+1) - V (5h [D)
(23)
k-1
-AA(A))
w (AA)
Σ
Φ | (oh+1) - Pr Ph (5% 9[]
(24)
+ (AA) Σ
PT (V/++ (S)
(25)
By the proof of the first term,
->aa)l->>>(aaa (>(( (A)) wx) VA /ols (AR) @(s,a).
(((s, q1)l =
For the second term, given the event & defined in Lemma B.9, we have:
(()(s, 92)l S co dHl dH /x a( (M)) á(s,a)
for absolute constant co independent of ca. and x = log (2 (c3r + 1) dT /p). For the third term,
(0(8, q3)
(1s, (A
oT (Vi+1 - -Vitz) (1%)
(26)
8% (t)) T / (Vitz Viita) (x') due (2')
a(s,a), (AA)
(27)
((s,a))
(Vitzz vitta) (x') dup (o))
(28)
P1
6(s ((s,a), (A+) ((s,a),(A}))) / (VA Vi+ti) (a')ddu, djan (x')
->
(29)
19

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
where, by Equation (3), have
P1 = Ph (Vh+1 Vh+ta) (s. |p2 s 2HHdX ()s,a)
((s,a)T (A/) - ((s,a)
Finally, since (Ø(s, a). w ))) (T( (o(s, wX wT) (d(ssa)).g + q2 q3). by Lemma B.5 and our choice of parameter X, we have
(1)(,, (), - (8) - Pn (Vi+1 VT++1) S d" dH (() (AE)
Φ(s, a),
for an absolute constant e" independent of cæ.. Finally, to prove this lemma, we only need to show that there exists choice of absolute constant Car so that
c" V 6+ log (c3 + +1) S ci
(30)
where c log(2dT/p). We know [log o0) by its definition, and e' is an absolute constant independent of ca Therefore, we can pick an absolute constant Cg which satisfies /Vlog + log (car + 1) S ear Vlog2. This choice cg will make Equation 30 hold for all i. E [log 2, o0), which finishes the proof.
Lemma B.12. (Upper Confidence Bound (Jin al., 2020)) Under the setting of Theorem B.l on the event & defined in Lemma B.8 we have (s,ss,) 2 (%,s, a) for all (s, a, h k) 8 A [M] [K].
Proof. We prove this lemma by induction.
First, prove the base case, at the last step H. The statement holds because (s, 2 (s, a). Since the value function at H + 1 step is zero, by Lemma B.10 we have:
(K(s,a), a)) By a) (At) a(s,a).
Therefore, we know:
Qir(s, S min (((( wh)) +V (Ah) ((s,a), a) H Qir
Now, suppose the statement holds true at step + and consider step Again, by LemmaB.4 4, we have:
( wi) (+,ss a) -Pn (vhti -Viti) ) (s, (s s BVs(s,)) (At) -1 a(s,a).
By the induction assumption that PA, (b/+11 -Vit1) (s) 2 0. have:
a) S min { (0(s,))) wh) BB +BV a() (M) 0(8,)), = (%,
which concludes the proof.
We will also be needing the following lemma, for lower bounding the value our output policy arg max.e. Q(s,)). The following lemma shows that the pessimistic value function always lower bounds any policy value function.
Lemma B.13. (Lower Confidence Bound) Under the setting of Theorem B.I on the event defined Lemma B.9 we have, for any policy n. (s,a) a) S Q (s, a) for all (s, a, h, k) E S H x [K].
20

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Proof. We prove this lemma by induction similar to we just did in Lemma B.
Consider fixed, arbitrary policy т, first, we prove the base case, at the last step H. The statement holds because (s, 2 (s, Since the value function at H + step is zero, by Lemma B.1 we have:
((((,.).. - (7) & 8' ((s,)) (A+)* ((s,a).
Therefore, we know:
(H(s,a) clip ((b(). - 8' als (A+) o(s.a) = (s)
Now, suppose the statement holds true at step h and consider step h. Again, by Lemma B.11, have:
( w (8) Phh (V Vi+1) (s, 8' ((s,a) (AR) -1 ((8,a).
By the induction assumption that Pr, (Vi++ h+1 Vi+z2) (8, S O, we have:
(s, 2 clip (()) -B
3 ((s,a)) (AR) o(s,a),0, (s)
which concludes the proof.
Theorem B.14. (Pseudo Regret Bound) Under Assumption B.2. for any fixed constant 8 (0,1). with proper choice of <> 0, and if we set X = 1, B c. dH (log(2dT//)) then with probability at least 1 - 6, the regret of interest of algorithm 2, E Σ k= (s) ViTh (s/) (**((s)) is at most Ô HT)) where is the parameter of geometric distribution.
Proof. For simplicity, we use the notation:
**,,,) = arg max (s,)) (+(,,)) = arg max aEA (+,
arg
aaA
We also denote = {k [K], L 0}. an index set of episodes which the trajectory is fully exploratory, then we have,
K
K
E
Vi' - VITh (st)
$
(* - v7((5))
(31)
(l( (344
E
(32)
(1(( - (77(6)))
(33)
kgl
where the first step the direct result Lemmas B.12 and B.13, the second and the third steps are due to the construction of our algorithm, where we do not update weights until full exploratory episode happens, and the expected interval of such event happening is I. And further, p.
21

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
-
Σ @t at)
(34)
KEl
(+ at) Q7 af)
(35)
KEl
Σ
{ ( - - at) + E - (16))44a)))
(36)
KET
3 S// at) (AA)
+ 8 (At) - a(st,at)
+ E
(s5) Vs (f
(37)
Σ
BV By ( Tt (AA)
(ist.at) + 1 // vollst (AR) -1 af)
(38)
K
of
+ E
Vi (55))
V/5 (35) af - (1/ - (55)) (122 - (65))
(39)
C
- (2)) + 1/tt + c3}
(40)
KE
where, a arg A (+ ) and a' E arg ea E (5t, By recursively applying Equation. (34), we have,
H
H
k
(41)
Sh
KET
k hm
KE
kgT
Am
(42)
We now bound each terms, for the first term in Equation (41), by Lemma C.2 and C.3:
H
3 V (55% of) (AR) -1 ((s) att
(43)
KET
k
H
Kp
BV ((s T (At) ( aft)
(44)
hml
KET
H
(ct)
$ $B Kp
2 log
(45)
det(At))
h=1
A + k
BB Kp
2d
(46)
X
< Hddk22dKp
(47)
where, the second step follows from Cauchy-Schware Schwarz inequality, the third step follows from the Lemma C.2 and C.3, and the second last step follows from the fact that [[)(;))]| < 1, and thus ||A||| || S x + k. And following the same logic, we have, for the second term in Equation (41):
22

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
by S H3' 2dKp
REI h=1
For the third term in Eq(41), notice it is martingale difference sequence, and by applying Azuma- Hoeffding inequality, with probability at least
H
k
122HH110222 S 2H KH
KET h=1
By combining the upper of three terms in Equation (41), recall that = c. dH (log(2dT /8), = .d.dH LlH (log(2d)) 18) we obtain:
Σ
v/ S 133
Kp 11 13 K Kp + 2H KHi C' .THTT
kel
for some absolute constant C².
Hence, the total regret is given by:
K Σ
C' -
This concludes that the total pseudo regret of policy ı K episode is given by H(V And equivalently, conclude that our algorithm obtains c-optimal policy with Ō d" samples with probability at least
C. Auxiliary Lemmas Lemma C.1. (Jin et al., 2020) Let A, X Ei D.O. where 0; E Rdd and X > 0. Then:
Σ Φ (Ar) sd
(((( E'= 0.=)) Given the eigen- value decomposition Σ1=1 0.0. diag (AI,..., AT) UT, we have A, Udiag (h1 A....,, + X)UT, and ir ((A:)) E Φ.0.1 Σj= >3/ (A3 + 2) S d.content...
Proof. We have Σi=
Φ (At) Φ, Ei tr (o. (Ae) Φ.) =u -
Lemma C.2. (Abbasi-Yadkori Yadkori et al., 2011) Let { be bounded sequence in IRd satisfying supizo |1 S 1. Let Ao E gaxd be a positive definite matrix. For any 2 0, we define A, = Ao + +E $6 Then, if the smallest eigenvalue of Ag satisfies Amin (Ao) 2 1, we have
det (At)
det (A+) del (Ao)
log
2 A 15 S 2og
det (Ao)
j=1
Proof. Since Amin (Ao) 2 1 and
|| < 1 for all j 0, we have
$ A A Φb S DAmin (Ao)
1 1
$1,
Vj 2 0.
23

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Note that, for any [0, 1J, it holds that log(1 x) S x S 2 log(1 x). Therefore, have
Σ log 1+ Ao)100)))))) & Σ
A 2 Σ
log (=
(48)
j=1
/=1
Moreover, for any t 2 0, by the definition of As, we have
det (AA) = det (Ac-1 + = det (Ae-1) det
A
Since det A 0 A A,11 + Φ1 A p. the recursion gives:
Σ
log
[1 log det (AA) log det (Ao)
(49)
1=1
Therefore, combining Equation (48) and Equation (49), we conclude the proof.
In our algorithm, full-exploratory trajectory occasionally occurs, and other trajectories also contributes our parameter A in the following Lemma, we show that by adding more data, the bound remains effective.
Lemma C.3. Let { 122 be bounded sequence in Rdd satisfying supizo |1 S 1. And let {1ss) be another sequence of in Rd satisfying sup&20 l|vall S 1. Let Ao Raxd be positive definite matrix. For any 0, 2 define
Ar = Ag + Ej= , Me, = Ao - Σラ $ + +imn that. Then, if the smallest eigenvalue of No satisfies Amin (Ap) 2 1, we have
det (AA)
Σ Φ A 1- Φ3 s 2
det (Ao)
where {syhısse any non-decreasing sequence of number satisfying 8y E
Proof. Consider any t, s N, since Ag is positive definite, and Σ o and Eis daa are semiipositive-definite, we know that or (Ae,s) a (At) and ar "A 2 (AA,)) in pointwise manner. This gives us, for any sequence (sy)1sst, N.
det (Ac) det (Ap)
Σ
0 4,
06 Σ Φ 1 - 22 Ø=1
This concludes the proof.
Lemma C.4. (Concentration of Self-Normalized Processes (Abbasi-Yadiee al., 2011)). Let { be real- valued stochastic process with corresponding filtration (Fi) Let Fi- be zero-mean and o-subGaussian; iee. E Esr, F.-1] = 0, and
V.ER, E (igeiFFrii Fr S 22
Let ( be R- stochastic process where o, Fi-1 Assume Ao is d x d positive definite matrix, and let A, = Ag E'm -- Then for any 8 > 0, with probability at least we have for all '
24

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
det (As) det (Ao)
Cx
log AT
S 20
8
Lemma C.5. (Jin et al., 2020) Let {s, Ir=1 be stochastic process on state space with corresponding filtration { 1r=0 Let { J be an valued stochastic process where 4, E F- and || S 1. Let A₃ -1- Σ x, Then
for any ó > 0, with probability at least 1 for all k 2 0, and any V V so that sup, [V(s)] S H, we have:
k
d
+
N
8k
Σ Φ- (V
-V (8+) F F-
I 4H2
log
+ log
+
2
8
A
where Ne is the e-covering number of V with respect the distance dist (V, V*) sup, (V(8) V'()))
Proof. For any V V, we know there exists V in the e-covering such that
V = + Av and
sup pyplA((s) Se
This gives following decomposition:
k
Σ Φ E8))
Fr
(50)
k
k
2
Σ
V (((+)
(s+)) F
+
Σ o (
-E(Av (87) Fr
(51)
where apply Theorem D.3 and union bound to the first term. Also, it is not hard to bound the second term by 8k22?/X. //
To compute the covering number of function class V. we first require basic result on the covering number of a Euclidean ball as follows. We refer readers to classical material, such as Lemma 5.2 in [44], for its proof. Lemma D.5 (Covering Number of Euclidean Ball). For any E > 0, the E-covering number the Euclidean ball in gd with radius is upper bounded by (1 + 2R/e)
Lemma C.6. (Covering Number of Euclidean Ball). For any e > the E-covering number of the Euclidean ball in Rd with radius R > 0 upper bounded by (1 2R/e)*.
Based on the lemmas above, we can bound the covering number of the optimistic value function and pessimistic value function class.
Lemma C.7. (Covering number of optimistic function class (Jin al., 2020)) Let V denote a class of functions mapping from S to R with following parametric form
v(-) = min max T ((;;a) + BB (((aa) A-1o)))-,,,,,)).
where the parameters (w, 3, A) satisfy [|w]| < L, 3 E [0, B] and the minimum eigenvalue satisfies Amin (m) 2 Assume (1 a)ll $ 1 for all (s, a) pairs, and let N be the E-covering number of with respect to the distance dist (V,V"= sup, (s(s) V'(s) Then
log,N, S dlog(1 + 4L/s) + dl log + /22 (As2)
25

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
Proof. Equivalently, reparametrize the function class by let A 3 have
V(-) min max w T Ø(:.a) + v v (((()))(((.a))) H
(52)
for ||w]| I L and ||A|| & BaX-1 For any two functions V1, V/2 E V, let them take the form in Equation (52) with parameters (W1,A1) and (w2, A2). respectively. Then, since both min , H and max, are contraction maps, we have
dist (2) - sup 6.0
wi T Φ(s, a) + V (lls,))TA2(ss,. A2 - W + ( A2σ(5,a)
(53)
sup
T W Φ + VΦl A2Ø -
W2 T Φ V 2 A2Φ
(54)
sup ~
(w] ww) T
/b/ +
sup
V107 (A1 A
(55)
w| - w2ll VII
A2ll
S WI w2ll VIA
A2l1F
(56)
where the second last inequality follows from the fact that I - / S V |- yi holds for any 2, y 2 0. For matrices, || ||- and ||r denote the matrix operator norm and Frobenius norm respectively.
Let Ow be an e/2-cover of {w E R4 || N [} with respect to the -norm, and CA be an 6²/4-cover of [A E Raxd F| S d222 d2/2 with respect to the Frobenius norm. By Lemma C.6, we know:
|Cw| S S + 4T//8", CclS [1
/d//2 (A=?)
By Equation (53), for any Vi there exists W2 E Cw and A₂ E CA such that 1/2 parametrized by (w2, A2) satisfies dist (V1, V2) $ Hence, it holds that Ns. |Cwl [Cal. which gives:
Ng I log Cwl log |Cal s dllog1 4L/e) d d [ /2 (d=t)
This concludes the proof.
And we can obtain the same covering number bound on our pessimistic value function class due to the symmetry.
Lemma C.8. (Covering number of pessimistic function class) Let V denote class of functions mapping from S to IR with following purametric form
v(-) clip mmax w
TewwwT/b... ((;aa) (
where the parameters (w, B, satisfy ||w|| < L,B B) and the minimum eigenvalue satisfies (A) 2 A. Assume [| a))l < 1 for all (s. o) pairs, and let Ne be the e-covering number of V with respect to the distance dist (V,V") = sup, (V(s) [s))) Then
log < dlog(1 + 4T/e) + d log [ /22 (As2)
Proof. Similar to the proof strategy used in Lemma C.7, we reparametrize the function the function class V by letting A A-1 which gives us.
26

---

Hyperparameter Robust Efficient Exploration in Reinforcement Learning
V+) = clip max w ((,a) Ab(.)))A((..))..1
(57)
for ||w|| I L and ||A|| -² For any two functions V1, V, let them take the form in Equation (57) with parameters (W1, A1) and (W2, A2), respectively. Then, since both clip(:, 0, H) and max, are contraction maps, we have
dist (V1, V2) - sup 6.0
wi T Φ(s a) ( a) (aaaa)AAooo Al)(s,
W3 (( /
(58)
sup
W Φb VΦ A Φ
W Φ
$ A2Ø
(59)
+1
sup +:||||<11
(wi [W2)
W2) T
/ + sup
00 (A2 -A) 1
(60)
= W - w22l + VI Ail
|| w2ll + V1IA2- AAIlF
(61)
= w/ - w2ll + V ||| - -22ll
(62)
Equation (58) shows that the distance of elements in pessimistic value function class shares same upper bound with the optimistic value function class. By Lemma C.7. conclude the proof.
27


Reviews:
[{"review_id": "RbkYm1wV5r", "reviewer": "Reviewer_L37S", "summary": "This paper has proposed a new method, referred to as \"hyper-parameter robust exploration (Hyper)\", which aims to mitigate the \"extensive hyper-parameter tuning\" problem in existing curiosity-based exploration methods. The proposed method Hyper is summarized in Algorithm 1. This paper also analyzes Hyper under the linear MDP setting (Theorem 4.2), and preliminary experiment results are demonstrated in Section 6. In particular, Section 6.2 demonstrates Hyper's robustness to $\\beta$.\n\n## update after rebuttal\n\nI have read the rebuttal and discussed with the authors.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the strengths of our work, particularly our careful experiment design and comprehensive literature review.\n\nRegarding 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.\n\n***Regarding truncation probability $p$ dependency in sample complexity***\n\nThe 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:\n\n- When $p = 0$: The algorithm operates exclusively in exploitation mode. This will bring the theoretical sample complexity to infinity.\n- 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).\n\n***Regarding the tightness of the bound***\n\nOur 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.\n\n***Regarding the regret bound***\n\nOur 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.\n\n***Regarding the paper flow***\n\nThank 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.\n\nFollowing 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.\n\n***Regarding the finite horizon & discounted setting***\n\nWe 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.\n\nIn 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.\n\n### References\n\n- Jin et al. (2020). *Provably efficient reinforcement learning with linear function approximation*. In COLT\n- He et al. (2023). *Nearly minimax optimal reinforcement learning for linear Markov decision processes*. In ICML\n- Zhou et al. (2021). *Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes*. In COLT", "claims_and_evidence": "Overall, the main claims of this paper are supported by both the theoretical analysis (Theorem 4.2) and experiment results in Section 6. Some comments:\n\n- The theoretical analysis and result are limited to linear MDPs. This is an obvious limitation, however, it is mainly due to existing analysis techniques in the theoretical RL community. I do not see an easy way to extend the analysis beyond the linear MDP framework.\n\n- The existing experiment results in Section 6 are solid, but I am wondering if they can be further strengthened. Specifically, my understanding is that the proposed Hyper method is a general method for all curiosity-based exploration approaches. However, in Section 6, only experiment results under a few algorithms have been demonstrated. I recommend the authors to add more experiment results under more algorithms to further strengthen the paper.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the considered problem.", "theoretical_claims": "I think the theoretical claims in Theorem 4.2 can be further strengthened, specifically\n\n- Please discuss the tightness of the upper bound developed in Theorem 4.2. Ideally, this paper should also develop a lower bound under the linear MDP setting and discuss the tightness.\n\n- Rather than the number of steps, why not present the results of Theorem 4.2 using a regret bound?\n\n- Please discuss how the results depend on the truncation probability $p$. Currently they are hidden in the $\\tilde{O}$ notation.", "experimental_designs_or_analyses": "I have checked the experiment design. To the best of my knowledge, it is sound and valid.", "relation_to_broader_scientific_literature": "My understanding is that this paper has done a good job of literature review and well positions itself among the relevant literature.", "essential_references_not_discussed": "I have not found any essential references that have not been discussed.", "other_strengths_and_weaknesses": "- The flow of this paper can be further improved. In particular, Algorithm 1 is after the analysis section (Section 4), which makes it a little bit difficult to read Section 4.\n\n- I think the key points of Section 3 are well known to experts in this field. Maybe the authors can shorten it a little bit, and use the space to add more experiment results.", "other_comments_or_suggestions": "- Typo: in Section 2, when defining the total reward, $\\gamma^{h-1}$ is missing before $b_h$\n\n- This paper considers a setting with both the finite time horizon $H$ and the discount factor $\\gamma$, this seems to be a non-standard RL setting. Usually we either consider a finite-horizon setting with $\\gamma=1$, or an infinite horizon setting with $\\gamma<1$.", "questions_for_authors": "Please try to address the weaknesses and questions listed above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h3TB25iFW1", "reviewer": "Reviewer_3vGR", "summary": "The paper addresses hyperparameter sensitivity in curiosity-driven RL exploration, proposing **Hyper**, a two-phase algorithm that decouples exploration (curiosity-driven) and exploitation (repositioning-guided). Theoretical guarantees under linear MDP assumptions and empirical validation across navigation/locomotion tasks demonstrate Hyper’s robustness to the intrinsic reward coefficient β.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback, and we appreciate your positive comments. We will address your concerns below.\n\n***Regarding relevant literatures***\n\nThank you for the valuable suggestion. We will incorporate discussions on the references you suggested in the camera-ready version.\n\n***Regarding partially observable environments***\n\nWe 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.\n\n***Regarding baseline fairness***\n\nWe used $\\beta=1.0$ following the official Disagreement implementation by Pathak et al. (2019) to ensure fair comparison with the baselines.  \n\n***Regarding experiment analysis and metric consistency***\n\nWe 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.\n\n***Regarding $p$-robustness***\n\nHyper 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$).\n\n***Regarding interaction between the repositioning and exploration phases***\n\nSection 5 comprehensively explains Hyper's key mechanisms: \n1. The repositioning phase strategically places the agent in promising regions, preventing over-exploration demonstrated in our warm-up example\n2. The truncated geometric distribution ensures sufficient exploration while focusing resources on promising areas\n3. 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. \n\n***Regarding the choices of environments***\n\nOur 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.\n\n***Regarding the limitations & future works***\n\nWe appreciate this suggestion and will expand the limitations discussion in our revised paper. The primary limitations include:\n\n1. **Computational cost**: Like Decouple, Hyper requires maintaining and training an additional exploitation policy, increasing computational overhead compared to traditional curiosity-driven methods.\n2. **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.\n\nWe will incorporate this into discussion in the camera-ready version.\n\n***Regarding the visualization of agent behavior***\n\nThank 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. \n\nThe visualizations clearly illustrate Hyper's advantage over baseline methods and provide further evidence of Hyper's exploration-exploitation balance.\n\n***Regarding the connection between theory and practice***\n\nHyper 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.\n\n## Reference\n\n**Kim et al. (2023) LESSON: Learning to Integrate Exploration Strategies for Reinforcement Learning via an Option Framework. In ICML**\n\n**Pathak et al. (2019) Self-Supervised Exploration via Disagreement. In ICML**", "claims_and_evidence": "- **Claim 1 (β Sensitivity):** Supported by the navigation warm-up example (Fig. 2) and Table 1. **Limitation:** Baseline comparisons use β=1.0 for all methods, potentially disadvantaging baselines requiring tuned β.  \n- **Claim 2 (Hyper’s Robustness):** Empirical results (Fig. 6) validate reduced β sensitivity. **Gap:** Robustness to **p** (truncation probability) is not rigorously tested.  \n- **Claim 3 (Theoretical Efficiency):** Theorem 4.2 under linear MDPs is sound but lacks direct connection to practical Algorithm 1.", "methods_and_evaluation_criteria": "- **Strengths:** Warm-up example effectively isolates β sensitivity; environment diversity (PointMaze, MuJoCo) tests multiple dimensions.  \n- **Weaknesses:**  \n  - **Baseline Fairness:** Using β=1.0 for all methods may skew comparisons (e.g., Curiosity-Driven methods often require smaller β).  \n  - **Ablation Studies:** Missing analysis of repositioning phase’s contribution vs. truncation mechanism.", "theoretical_claims": "- Theorem 4.2 (sample efficiency) is valid under linear MDPs but assumes Algorithm 2 (theoretical) aligns with Algorithm 1 (practical). **Gap:** No discussion of how neural networks in practice affect theoretical guarantees.", "experimental_designs_or_analyses": "- **Statistical Significance:** Standard deviations reported but no formal tests (e.g., t-tests).  \n- **Metric Consistency:** Success rate (navigation) vs. cumulative reward (locomotion) is appropriate but obscures sample efficiency comparisons.", "relation_to_broader_scientific_literature": "- **Strengths:** Builds on curiosity-driven (Pathak et al.) and decoupled RL (Schäfer et al.) literature.  \n- **Gaps:**  \n  - Fails to cite meta-RL exploration strategies (e.g., Stadie et al. 2018).  \n  - Omits hierarchical RL with intrinsic motivation (Kulkarni et al. 2016).  \n\n## Relation To Broader Scientific Literature\n\nThe paper is well-positioned within the broader literature on exploration in RL:\n\n1. It builds upon the established curiosity-driven exploration methods (Bellemare et al., 2016; Pathak et al., 2017, 2019; Burda et al., 2018).\n\n2. It addresses a practical limitation of these methods (hyperparameter sensitivity) that has been noted but not thoroughly addressed in previous work.\n\n3. The decoupling of exploration and exploitation relates to work by Schäfer et al. (2021) and Whitney et al. (2021), but with the novel addition of the repositioning mechanism.\n\n4. The theoretical analysis extends the line of work on provably efficient RL with function approximation (Jin et al., 2018, 2020; Yang & Wang, 2020).", "essential_references_not_discussed": "The paper covers most relevant literature, but could benefit from discussing:\n\n1. **Meta-RL approaches to exploration**: Recent work on meta-learning exploration strategies (e.g., Stadie et al., \"Some Considerations on Learning to Explore via Meta-Reinforcement Learning,\" 2018) could provide context for automatically adapting exploration strategies.\n\n2. **Intrinsic motivation in hierarchical RL**: The paper could discuss connections to hierarchical RL methods that use intrinsic motivation (e.g., Kulkarni et al., \"Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation,\" 2016).\n\n3. **Exploration in partially observable environments**: Since many real-world tasks involve partial observability, discussing how Hyper might perform in such settings would be valuable.", "other_strengths_and_weaknesses": "**Strengths:**\n1. The paper addresses a practical and significant problem in RL that limits the applicability of powerful exploration methods.\n2. The proposed solution is elegant, combining theoretical guarantees with practical implementation.\n3. The empirical results are comprehensive and convincing.\n4. The paper is well-written and the ideas are clearly presented.\n\n**Weaknesses:**\n1. The practical implementation of Hyper still requires setting the truncation probability p, which introduces another hyperparameter. While the authors provide a reasonable default and decay schedule, this somewhat undermines the claim of hyperparameter robustness.\n2. The analysis of why Hyper works is somewhat limited - more insight into the interaction between the repositioning phase and exploration would strengthen the paper.\n3. The environments, while varied, are still relatively standard RL benchmarks. Testing on more diverse or challenging environments would strengthen the claims.", "other_comments_or_suggestions": "1. The paper would benefit from a more detailed discussion of the limitations of Hyper, particularly cases where it might not perform well.\n2. A visualization of the agent's behavior during the repositioning and exploration phases would help readers understand the algorithm's dynamics.\n3. The connection between the theoretical algorithm (Algorithm 2) and the practical implementation (Algorithm 1) could be more clearly explained.\n4. Minor typos:\n   - In equation (1), \"Qπ = Eπ[PHh=1 γh−1rh(sh, ah)]\" should likely be \"Qπ = Eπ[∑Hh=1 γh−1rh(sh, ah)]\"\n   - Several instances of missing or incorrect mathematical notation in the PDF rendering.", "questions_for_authors": "1. **Truncation Probability Sensitivity:** How does Hyper’s performance vary with **p**? Does the decay schedule generalize across environments?  \n2. **Baseline Tuning:** Why was β=1.0 chosen for baselines? Were baselines tested with their optimal β ranges?  \n3. **Theory-Practice Gap:** How does Algorithm 1’s neural network implementation relate to Algorithm 2’s linear assumptions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BoaC0v6fgy", "reviewer": "Reviewer_Sbxf", "summary": "This paper proposes a “repositioning_length” based method to alternate between exploration and explosion. The key idea is to choose the bounded geometric distribution with probability p to determine the repositioning_length to make the process more sample efficient.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n### Difficulty of Understanding the Meaning of $\\beta$\n\n> 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.\n\n> In Fig. 1, you should illustrate what $\\beta$ represents.\n\n$\\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).\n\nThe 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.\n\n\n### Difficulty of Understanding Section 5\n\n> 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.\n\n> 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.\n\nWe 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.\n\n\n\n> The comparison with LESSON is questionable, as it is based on a single comparison in specific MiniGrid tasks.\n\nOur 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.\n\n> 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.\n\nThe 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.\n\n> The title is quite broad. To make it more explicit, consider including terms like \"Repositioning & Exploration\" for greater clarity.\n\nThe 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.\n\n> 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.\n\nWe 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.\n\n\n**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.**", "claims_and_evidence": "Yes the motivation is clear though the presentation of method is unclear.", "methods_and_evaluation_criteria": "Yes it uses toy tasks and some basic robot related tasks.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "It might inspire the understanding on the exploration.", "essential_references_not_discussed": "No to my knowledge.", "other_strengths_and_weaknesses": "# Strengths:\n- The presentation regarding motivation is generally clear, and the method is simple.\n- Results show improvement in most empirical evaluations.\n# Weaknesses:\n- 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.\n- 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.\n- In Algorithm 1, I cannot find β. I am wondering whether the proposed method explicitly incorporates β in its design loop. From Figures 1 and 6, it appears that β is part of the algorithm loop.\n- The comparison with LESSON (another method for switching between exploration and exploitation) is questionable, as it is based on a single comparison in specific MiniGrid tasks.", "other_comments_or_suggestions": "- In Fig. 1, you should illustrate what β represents.\n- The first equation in Section 3 is unclear, as there is no indication that a discount is applied to the intrinsic reward.\nUse vector graphics for the figure plots.\n- The title \"Hyperparameter Robust Exploration in Reinforcement Learning\" is quite broad. To make it more explicit, consider including terms like \"Repositioning & Exploration\" for greater clarity.\n- 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.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No"}}, {"review_id": "JkWEIyJvCZ", "reviewer": "Reviewer_QGsd", "summary": "This submission proposes a novel method, referred to as Hyper, to address the challenging issue of hyperparameter tuning in curiosity-based exploration methods. It introduces a repositioning and exploration mechanism that controls the horizon of exploitation before conducting exploration. The length of the exploitation horizon is sampled from a bounded Geometric distribution. The authors provide both theoretical and empirical evidence to demonstrate the effectiveness of the proposed Hyper method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment and insightful questions. We appreciate your recognition of our work's value and address your questions below.\n\n***Regarding Hyper’s efficiency***\n\nOur claim that \"Hyper is efficient\" operates on two complementary levels:\n\n1. **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.\n2. **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.\n\nWhile 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.\n\n***Regarding $\\epsilon$ in Theorem 4.2***\n\nIt 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.\n\n***Regarding comparison to recent methods***\n\nCuriosity-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.\n\nIn 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.\n\n***Regarding truncation probability parameter $\\gamma$ and $p$***\n\nThe 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.\n\nThis 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.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and the corresponding evaluation criteria are appropriate for addressing the problem.", "theoretical_claims": "The proofs for the theoretical claims in this submission are correct.", "experimental_designs_or_analyses": "The experimental design and analysis exhibit soundness and validity.", "relation_to_broader_scientific_literature": "This work primarily focuses on the field of reinforcement learning.", "essential_references_not_discussed": "This submission includes sufficient related references.", "other_strengths_and_weaknesses": "**Strengths**\n1. Addressing the exploration-exploitation dilemma in reinforcement learning is valuable.\n2. The proposed Hyper method is well-introduced and clearly described.\n3. The authors provide theoretical analysis and empirical studies supporting the effectiveness of the proposed methods.\n\n**Weaknesses**\nSee the following comments and questions.", "other_comments_or_suggestions": "1. On line 175 of the right column, it is mentioned \"We defer the formal proof to the appendix.\" The specific appendix should be cited for clarity.", "questions_for_authors": "1. I do not see the efficiency of Hyper according to the upper bound involving the $d^3H^4$. Could you clarify?\n2. What is the $\\epsilon$ in Theorem 4.2?\n3. I see that the proposed Hyper method is an improvement based on curiosity-based methods. How does it compare to more recent exploration algorithms?\n4. Is the parameter $\\gamma$, which controls the probability of the repositioning phase, fixed for all tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces Hyper, a reinforcement learning algorithm designed to mitigate the well-known sensitivity of curiosity-driven exploration methods to the intrinsic reward scaling hyperparameter, beta. The core idea involves alternating between an exploration phase guided by intrinsic rewards and an exploitation phase focused on repositioning the agent using only the task reward, with phase lengths determined probabilistically. The authors provide theoretical justification for Hyper's efficiency under linear MDP assumptions and extensive empirical results demonstrating its robustness to beta and strong performance across various environments, including navigation and locomotion tasks.

Reviewers generally recognized the practical importance of addressing hyperparameter sensitivity in exploration. Initial reviews were largely positive but included requests for clarification on theoretical details (like dependence on the new parameter 'p' and tightness of bounds), justification for experimental choices (like baseline comparisons and the fixed 'p' schedule), and additional analyses (such as visualizations of agent behavior).

The authors provided a detailed rebuttal that effectively addressed most concerns. They clarified the theoretical results, explained the rationale behind the experimental design (including comparisons to LESSON in the appendix), demonstrated the robustness to the new parameter 'p' by using a consistent schedule across tasks, and supplied helpful visualizations of agent trajectories. This led to reviewers 3vGR and Sbxf increasing their scores, with Reviewer 3vGR moving to Accept. While Reviewer L37S acknowledged the clarifications, they maintained their score, hoping for tighter theoretical bounds in the current paper, which the authors positioned as future work. Reviewer QGsd was satisfied with the responses and maintained their positive score.

Overall, the reviewers converged towards acceptance, acknowledging that Hyper presents a well-motivated and empirically validated approach to a significant practical challenge in RL exploration. The method demonstrates considerable robustness compared to standard curiosity techniques, and the theoretical analysis provides a foundation for its efficiency.
Decision: Accept (poster)