Reward shaping is a technique in reinforcement learning that addresses the sparse-reward problem by providing more frequent and informative rewards. We introduce a self-adaptive and highly efficient reward shaping mechanism that incorporates success rates derived from historical experiences as shaped rewards. The success rates are sampled from Beta distributions, which dynamically evolve from uncertain to reliable values as data accumulates. Initially, the shaped rewards exhibit more randomness to encourage exploration, while over time, the increasing certainty enhances exploitation, naturally balancing exploration and exploitation. Our approach employs Kernel Density Estimation (KDE) combined with Random Fourier Features (RFF) to derive the Beta distributions, providing a computationally efficient, non-parametric, and learning-free solution for high-dimensional continuous state spaces. Our method is validated on various tasks with extremely sparse rewards, demonstrating notable improvements in sample efficiency and convergence stability over relevant baselines.
Paper
Similar papers
Peer review
Summary
The paper proposes a reward shaping method, SASR, for deep reinforcement learning by incorporating success rates derived from historical experiences. These success rates are sampled from Beta distributions with decreasing uncertainty. Kernel Density Estimation (KDE) and Random Fourier Features (RFF) are used to derive the Beta distributions. The method is evaluated on sparse reward tasks and compared with eight baseline methods. The results demonstrate that the proposed method outperforms the baseline methods on the chosen tasks.
Strengths
- The paper is well-organized and easy to follow. - The idea makes sense. The method is original and the authors provide a clear explanation of the method. - The authors compare their method with 8 baseline methods, which is a good practice.
Weaknesses
- The scope of the proposed method is unclear. Although the authors mention "sparse reward tasks" several times, it remains uncertain whether the method is exclusively suitable for sparse reward tasks. If so, this should be clearly stated [1]. - The authors motivate the method by mentioning that "most real-world environments involve high-dimensional state spaces". However, the tasks chosen for the experiments appear to involve vectors with only tens of dimensions. - The chosen tasks are not standard in the RL community. The authors compare their method with 8 baseline methods, but 7 of these were not tested on the chosen tasks in the original papers. Additionally, there are no implementation details or results of hyperparameter searches for these baseline methods, making it unconvincing that the proposed method outperforms them. I recommend testing the proposed method on standard tasks used in the chosen baselines, such as sparse reward Atari games like Montezuma's revenge and Gravitar chosen by ROSA, #Explo, RND and PPO, or mujoco tasks (though they may not be sparse reward tasks) chosen by #Explo, SAC, TD3, and PPO. In addition, if the proposed method is intended for sparse-reward, high-dimensional, continuous control tasks, dmcontrol conld be a good choice [2,3]. - The method introduces many parameters to tune, such as the weighting factor $\lambda$, the bandwidth of the Gaussian kernel $h$, the retention rate $\phi$, and the Fourier features dimension $M$. These parameters are sensitive to performance, as shown in the ablation study (Figure 6). Additionally, some functions need to be predefined, such as the scaling function $f$ and the kernel function $K$. The interaction between these parameters and functions is complex, making it difficult to understand how they influence each other and how can the method be tuned for other tasks. - The method introduces additional computational costs (reward computation) and memory costs (three buffers). It is unfair to compare it with other methods without considering these costs. A comprehensive comparison with other methods in terms of computational and memory costs, in addition to performance, would be more appropriate. [1] Devidze, Rati, Parameswaran Kamalaruban, and Adish Singla. "Exploration-guided reward shaping for reinforcement learning under sparse rewards." Advances in Neural Information Processing Systems 35 (2022): 5829-5842. [2] Tassa, Yuval, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden et al. "Deepmind control suite." arXiv preprint arXiv:1801.00690 (2018). [3] Yarats, Denis, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. "Mastering visual continuous control: Improved data-augmented reinforcement learning." arXiv preprint arXiv:2107.09645 (2021).
Questions
- What is the formula for the scaling function $f$ in Equation 4? - In sparse reward tasks, the most challenging part is at the beginning of the learning process when all the trajectories fail or have zero rewards. How does the proposed method handle this situation? What advantage does it offer over other methods in this situation? - It seems Table 1 computes the average reward over the entire learning process. Why not use the final reward as the metric? - RND achieves the best performance on MountainCar. Why is it not included in Figure 5? - What are the dimensions of the chosen tasks? It appears that the state space is a vector of tens of dimensions. How does the method perform on tasks with high-dimensional state space or images-based tasks like Atari games or dmcontrol tasks? - Since all tasks provide extremely sparse rewards, is the proposed method only suitable for sparse reward tasks? If not, how does it perform on tasks with dense rewards? - Given that 7 out of 8 baseline methods were not tested on these chosen tasks in the original papers, how did you finetune the hyperparameters of these baseline methods? Did you compare their performance on the tasks reported in the original papers? - See Weaknesses. I am willing to increase my score if all my concerns are addressed.
Rating
6
Confidence
4
Soundness
2
Presentation
2
Contribution
3
***Response to Reviewer 52SB Part 1/5*** Dear reviewer, Thank you for your valuable comments. We have addressed your concerns in detail, along with the identified weaknesses and questions. ## Scope of Sparse-Reward Tasks > * (Weakness 1) The scope of the proposed method is unclear. Although the authors mention "sparse reward tasks" several times, it remains uncertain whether the method is exclusively suitable for sparse reward tasks. If so, this should be clearly stated [1]. > * (Question 6) Since all tasks provide extremely sparse rewards, is the proposed method only suitable for sparse reward tasks? If not, how does it perform on tasks with dense rewards? > [1] Devidze, Rati, Parameswaran Kamalaruban, and Adish Singla. "Exploration-guided reward shaping for reinforcement learning under sparse rewards." Advances in Neural Information Processing Systems 35 (2022): 5829-5842. Regarding the scope of SASR (*Weakness 1* and *Question 1*), SASR is designed within the domain of reward shaping, which is exclusively targeted for the sparse-reward tasks, sharing the same scope as your mentioned *ExploRS* algorithm [1]. We have highlighted this in the revised paper. (Our revised paper will be updated here as soon as possible.) Furthermore, the main reason for most reward shaping methods are not suitable for dense reward tasks is that the dense environmental rewards already provide fine-grained and informative feedback at each timestep, i.e., the most direct objective with clear guidance. In this case, introducing additional shaped rewards is unnecessary and may even introduce bias. For instance, in the *AntStand* task, if the environmental reward is defined by the robot’s center of gravity height – a direct and pertinent objective, introducing additional shaped rewards could potentially hinder early training. We have discussed this in the last paragraph of *Section 6 Conclusion and Discussion*, and will further highlight this in the revised paper. ## High-Dimensional State Spaces > * (Weakness 2) The authors motivate the method by mentioning that "most real-world environments involve high-dimensional state spaces". However, the tasks chosen for the experiments appear to involve vectors with only tens of dimensions. > * (Question 5) What are the dimensions of the chosen tasks? It appears that the state space is a vector of tens of dimensions. How does the method perform on tasks with high-dimensional state space or images-based tasks like Atari games or dmcontrol tasks? Regarding the dimensionality of the tasks used in our experiments (*Weakness 2* and *Question 5*), we have addressed your concerns by conducting new experiments on high-dimensional environments in image-based tasks (Atari games). We also provide the state space dimensions of the tasks used in our study. **Additional experiments on high-dimensional environments:** We have conducted additional experiments on 5 Atari games, including the well-known *Montezuma's Revenge*. These tasks offer a significantly higher-dimensional state representation. The results of SASR compared to several baselines are shown in [Figure R.3](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.3.pdf). These new results and discussions will be included in the revised paper. **Dimensions of the tasks used in our study:** | Tasks | Dimension | | :---: | :---: | |Ant tasks (AntStand, AntSpeed, AntFar, AntVeryFar)| 105 | |Humanoid tasks (HumanStand, HumanKeep) | 348 | |RobotReach | 20 | |RobotPush, RobotSlide and RobotPickPlace | 35 | |Atari games (MontezumaRevenge, PitFall, Frooger, Solaris, Freeway) | 84x84 = 7056 | |MountainCar | 2 | The tasks with hundreds of dimensions (*Ant Robot*, *Humanoid Robot*, and Atari games) are generally considered high-dimensional in the RL community, given the complexity of the dynamics modeled by their state vectors. By the way, the extended comparison is shown in [Figure R.1](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.1.pdf).
***Response to Reviewer 52SB Part 2/5*** ## Baselines and Comparison > * (Weakness 3) The chosen tasks are not standard in the RL community. The authors compare their method with 8 baseline methods, but 7 of these were not tested on the chosen tasks in the original papers. Additionally, there are no implementation details or results of hyperparameter searches for these baseline methods, making it unconvincing that the proposed method outperforms them. I recommend testing the proposed method on standard tasks used in the chosen baselines, such as sparse reward Atari games like Montezuma's revenge and Gravitar chosen by ROSA, #Explo, RND, and PPO, or mujoco tasks (though they may not be sparse reward tasks) chosen by #Explo, SAC, TD3, and PPO. In addition, if the proposed method is intended for sparse-reward, high-dimensional, continuous control tasks, dmcontrol conld be a good choice [2,3]. > * (Question 7) Given that 7 out of 8 baseline methods were not tested on these chosen tasks in the original papers, how did you finetune the hyperparameters of these baseline methods? Did you compare their performance on the tasks reported in the original papers? > [2] Tassa, Yuval, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden et al. "Deepmind control suite." arXiv preprint arXiv:1801.00690 (2018). > [3] Yarats, Denis, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. "Mastering visual continuous control: Improved data-augmented reinforcement learning." arXiv preprint arXiv:2107.09645 (2021). We have conducted additional experiments on 5 Atari games, all are sparse-reward tasks, including the famous *Montezuma's Revenge*. The results of SASR compared to several baselines are shown in [Figure R.3](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.3.pdf), and an extended comparison with more baselines in more tasks in shown in [Figure R.1](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.1.pdf), as we have discussed in the previous part. 1. Regarding the **implementation details and hyperparameter tuning of the baseline methods** (*Weakness 3* and *Question 7*), we followed the hyperparameters and implementation details from reliable and widely-used sources: * The [CleanRL library](https://docs.cleanrl.dev/), a well-known repository for DRL algorithms, which provides detailed and standardized hyperparameters for various algorithms. * The [RLeXplore repository](https://github.com/RLE-Foundation/RLeXplore), which focuses on intrinsic reward algorithms and offers detailed implementations and settings. * Codebases provided by the baseline papers themselves, including [DRND](https://github.com/yk7333/DRND), [GFA-RFE](https://github.com/uclaml/GFA-RFE), [ReLara](https://github.com/mahaozhe/ReLara) and [ExploRS](https://github.com/machine-teaching-group/neurips2022_exploration-guided-reward-shaping). These sources allowed us to reproduce the baselines accurately while adhering to their recommended hyperparameters and implementation details. 2. Regarding the **choice of standard tasks**, (a) DeepMind Control Suite [1], (b) DrQ-v2 [2], and (c) Atari games, after careful consideration, we chose to prioritize Atari games for the following reasons: * The (a) DMControl tasks are also Mujoco-based, which share a similar state space dimension with our current environments, offering limited additional insights. * The (b) DrQ-v2 has not been used in any of the baselines, making it less relevant for comparison. * The (c) Atari games, on the other hand, are widely used in the RL community and have been used in several baselines. The observation space of Atari games is high-dimensional and image-based, and many tasks are sparse-reward. As such, Atari games represent a more general and meaningful benchmark for providing a comprehensive and convincing comparison.
***Response to Reviewer 52SB Part 3/5*** ## Hyper-Parameter Tuning and Complexity > * (Weakness 4) The method introduces many parameters to tune, such as the weighting factor, the bandwidth of the Gaussian kernel, the retention rate, and the Fourier features dimension. These parameters are sensitive to performance, as shown in the ablation study (Figure 6). Additionally, some functions need to be predefined, such as the scaling function f and the kernel function K. The interaction between these parameters and functions is complex, making it difficult to understand how they influence each other and how can the method be tuned for other tasks. Regarding the hyper-parameter tuning and complexity of SASR (*Weakness 4*), although SASR introduces several hyper-parameters, their selection is intuitive and straightforward. More importantly, in our experiments, we observed that a single set of hyper-parameters performed consistently well across all tested tasks, demonstrating SASR's robustness and generalizability in hyper-parameter selection. The ablation study mainly aims to explore the impact of extreme and counterintuitive hyper-parameter values (e.g., a too large bandwidth $h=1$ or a very low RFF dimension $M=50$) to highlight their potential influence on performance. We acknowledge the importance of automated methods to determine optimal hyper-parameters, here are some potential approaches we can employ: * For bandwidth $h$, we can use the empirical formula "Silverman's Rule of Thumb" $h=1.06 \cdot \sigma \cdot N^{-1/5}$ or cross-validation to determine the optimal bandwidth. * For the RFF dimension $M$, it is directly related to the bandwidth $h$. After determining $h$, we can use the formula mentioned in the RFF theory to determine $M$: $$ M = O(\frac{1}{\epsilon^2} \log{\frac{N}{\delta}}), $$ where $\epsilon$ and $\delta$ are the error and confidence parameters. Or, we can compare the Frobenius norm error between the RFF approximated kernel matrix $K^{RFF}$ and the true kernel matrix $K^{Gaussian}$ to select $M$: $\|K^{RFF} - K^{Gaussian}\|_F$. * For the reward weight $\lambda$, it is usually determined based on the environment reward scale. Based on the reward shaping studies, e.g., RND, ReLara, and ExploRS, setting the shaped reward to half of the environment reward is a good choice. We used this finding in our experiments and obtained consistent results in the ablation study. Another feasible approach is to use a dynamic reward weight according to the learning effect and exploration requirement.
***Response to Reviewer 52SB Part 4/5*** ## Computational and Memory Efficiency > * (Weakness 5) The method introduces additional computational costs (reward computation) and memory costs (three buffers). It is unfair to compare it with other methods without considering these costs. A comprehensive comparison with other methods in terms of computational and memory costs, in addition to performance, would be more appropriate. Regarding the computational and memory costs (Weakness 5), the additional overhead introduced by SASR is minimal compared to most baseline methods (that's why we call it a highly-efficient approach). We provide both an analysis and experimental results to support this claim. All reward shaping methods inherently introduce some computational overhead to compute the shaped rewards. Below, we summarize the computational and memory costs of the RS baselines: * **ReLara** requires an additional RL agent (of the same scale as the original RL agent) and an additional replay buffer. This leads to more than double the training time of the backbone SAC algorithm, because of the simultaneous maintenance of two RL agents and running two RL algorithms. * **ROSA** involves a competition agent (the same sacle as the original RL agent) and a switching model (a neural network). The competition agent is trained to compete with the original agent, and the switching model is trained to predict whether to switch between the agents, which introduces additional computational and memory costs. * **ExploRS** requires learning two parameterized networks: one for a self-supervised reward model and another for the exploration bonus (i.e., a random network distillation module). This introduces additional computational and memory costs. * **#Explo** doesn't introduce additional networks or models, but it requires a hash function to discretize the state space and a hash table to store the state-visitation counts. This introduces additional memory costs and it sacrifices accuracy in complex continuous spaces. * **RND** uses a random network distillation module to compute the intrinsic rewards, which requires learning an additional neural network. In contrast, SASR calculates shaped rewards using RFF, which essentially is matrix operations, without additional networks/models learning processes. Regarding the memory costs, the buffers $D_S$ and $D_F$ are much smaller than the replay buffer used in the backbone SAC algorithm, due to the retention rate $\phi$. In our experiments, we set $\phi=0.1$, assume the state dimension is $S=100$, with the data type of `float32`, the total time steps is $T=10^6$, then the memory costs of $D_S + D_F$ (because one state is either in $D_S$ or $D_F$) is $\phi S T$. We tested that a PyTorch tensor of shape $(10^5, 100)$ occupies around **38.15 MB**, in this case, memory is not a big concern in practice for our current configurations. However, considering the scalability for larger problems, we have implemented an alternative approach, which is briefly discussed in our paper *Sectin 4.2.1 Time and Space Complexity of SASR* (Line 265). This method utilizes the existing replay buffer of the SAC algorithm, augmenting it with a flag to indicate whether each state in the replay buffer is a success (flag=1) or failure (flag=0). This design allows us to avoid the need for additional buffers. This is exactly the approach we used in the Atari experiments. **Experimental Results** To further support our claim, we report the computational and memory costs of SASR and the RS baselines in two tasks: *AntStand* and *Frogger*, the results are shown in the following tables. To provide a more intuitive comparison, we report the relative value normalized to our SASR, e.g., the relative value of 1.2 means the baseline is 1.2 times of SASR. In this case, if the value $>1$, it indicates that the baseline is more computationally or memory expensive than SASR. 1. Table 1: Average maximum memory consumption during the training process, normalized to SASR. | Tasks | *SASR* | ReLara | ROSA | ExploRS | #Explo | RND | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | AntStand | *1* | 3.67 | 4.12 | 2.05 | 0.89 | 0.12 | | Frogger | *1* | 5.21 | 4.33 | 2.64 | 0.92 | 0.09 | *Note*: The RND is PPO-RND, which is an on-policy method, as it doesn't require a replay buffer, the memory cost is much lower than the other off-policy methods. 1. Table 2: Average training time, normalized to SASR. | Tasks | *SASR* | ReLara | ROSA | ExploRS | #Explo | RND | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | AntStand | *1* | 1.87 | 2.12 | 1.67 | 1.08 | 1.11 | | Frogger | *1* | 1.98 | 3.17 | 1.72 | 1.24 | 1.06 | The results demonstrate that SASR introduces low additional computational and memory costs compared to the RS baselines. All of these results and discussions will be included in the revised paper.
***Response to Reviewer 52SB Part 5/5*** ## Scaling Function > * (Question 1) What is the formula for the scaling function f in Equation 4? Regarding the scaling function $f(\cdot)$ in Equation 4 (*Question 1*), it is defined as a linear mapping from $[0, 1]$ to $[R_{min}, R_{max}]$, where $R_{min}$ and $R_{max}$ refer to the lower and upper bounds of the desired shaped rewards, specifically, $f(x) = R_{min} + x \cdot (R_{max} - R_{min})$. We will clarify this in the revised paper. As the rewards drawn from the Beta distribution are ranged in $[0, 1]$, we introduce this scaling function mainly for the cases where different reward scales are required (e.g., some tasks may assign $1$ as a positive reward, while others may assign $100$). This is mainly for enhancing generality and adaptability. In our experiments, all tasks are using the default $R_{min}=0$ and $R_{max}=1$. Usually, many studies (RND, SORA, ReLara, ExploRS, etc.) on reward shaping have found that aligning the shaped reward scale with the scale of the environmental rewards is a good choice. ## Positive Trajectories Discovery in Early Stages > * (Question 2) In sparse reward tasks, the most challenging part is at the beginning of the learning process when all the trajectories fail or have zero rewards. How does the proposed method handle this situation? What advantage does it offer over other methods in this situation? Regarding the challenge of exploration and getting out of fail trajectories in the early stages of learning (Question 2), we would like to highlight that SASR indeed accelerates the initial successful trajectories discovery through multiple exploration mechanisms. Please kindly refer to our **Global Response - Section 1** for detailed explanations. ## Evaluation Metrics > * (Question 3) It seems Table 1 computes the average reward over the entire learning process. Why not use the final reward as the metric? Regarding the evaluation metrics used in Table 1 (Question 3), we agree that the final reward is a more intuitive and critical metric for assessing the performance, we have updated Table 1 and the extended results are shown in [Figure R.1](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.1.pdf), where we compared SASR with 10 baselines in 14 tasks. In the updated table, it reports the mean and standard deviation of the final performance of each algorithm over 100 episodes. All of these updates will be included in the revised paper. ## RND in Figure 5 > * (Question 4) RND achieves the best performance on MountainCar. Why is it not included in Figure 5? Regarding Figure 5, we acknowledge the oversight in excluding RND from the comparison, thanks for pointing this out. We have included RND in Figure 5 for a direct comparison with SASR, the results are shown in [Figure R.5](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.5.pdf). In this task, both SASR and RND are able to jump out of the local optimum. All of these updates will be included in the revised paper. Overall, we appreciate your constructive criticism and are confident that our responses have addressed your concerns.
I thank the authors for their detailed response. I am satisfied with the authors' response and I am willing to accept the paper. I increased my score to 6.
Dear reviewer, Thanks so much for your feedback and raising the score. We are glad that our response addressed your concerns and sincerely appreciate your support.
Summary
This paper introduced Self-Adaptive Success Rate based reward shaping (SASR) for reward-sparse RL problems. SASR incorporates success rates, defined as the ratio of a state's presence in successful trajectories to its total occurrences, as auxiliary rewards. Further, SASR adopt Kernel Density Estimation (KDE) and Random Fourier Features (RFF) to derive Beta distributions and sample success rates from that distribution.
Strengths
- The idea of using success rate as auxiliary reward is interesting. - The writing is clear and the paper is easy to follow. - SASR shows promising results in the experiments.
Weaknesses
- Some of the selected environments are simple toy tasks. For example, the authors select the simpler Reach and Push tasks instead of the more challenging PickAndPlace and Slide tasks. It's still unclear if SASR is effective for hard-exploration tasks from the current experiment results. - Many baselines are old. The paper should compare to more recent baselines in exploration. For example, - DRND (https://github.com/yk7333/DRND) - RLE (https://github.com/Improbable-AI/random-latent-exploration) - GFA-RFE (https://github.com/uclaml/GFA-RFE) - There are no pixel-based experiments, i.e., Atari games. It's unclear how would SASR perform with pixel-based inputs? - Typos: (Line 296) "The motivations behind this are"
Questions
- How would SASR perform on some famous hard exploration tasks, i.e., Montezuma's Revenge and DM-Hard-8? - Can SASR solve difficult maze tasks with sparse reward, i.e., `AntMaze_HardestMaze-v5` from https://robotics.farama.org/envs/maze/ant_maze/? - For a hard exploration task where we only receive nonzero reward when the task is solved. If it's very difficult to collect the first successful trajectories. How will SASR perform when the success rates for all states are zero? Will the beta distribution be accurate enough to solve such problems?
Rating
6
Confidence
4
Soundness
2
Presentation
2
Contribution
2
Dear reviewer, In the original paper, we compared SASR with **8 commonly used and classic baselines across 10 tasks**, demonstrating its effectiveness in terms of sample efficiency, learning stability, and exploration-exploitation balance. We understand the reviewer’s concerns about SASR’s performance in other environments and with other baselines. To address this, we have conducted experiments on several new benchmarks, as detailed in the following replies. The latest experiments further demonstrate the robustness and applicability of SASR. Looking forward to your reply. ## Experiments in Robot Tasks > * (*Weakness 1*) Some of the selected environments are simple toy tasks. For example, the authors select the simpler Reach and Push tasks instead of the more challenging PickAndPlace and Slide tasks. It's still unclear if SASR is effective for hard-exploration tasks from the current experiment results. Regarding the *PickAndPlace* and *Slide* tasks (*Question 1*), we have included additional experiments on these tasks to evaluate SASR in comparison to the baselines, including your suggested two new baselines in *weakness 2*, the DRND and GFA-RFE. All four *FetchRobot* tasks are developed as sparse-reward tasks, where a positive value will be given only when the overall task is completed. The results are shown in [Figure R.4](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.4.pdf). We can observe that in the hard *Slide* and *PickAndPlace* tasks, SASR demonstrates competitive performance compared to all baselines. ## Experiments for New Baselines > * (*Weakness 2*) Many baselines are old. The paper should compare to more recent baselines in exploration. For example, > * DRND (https://github.com/yk7333/DRND) > * RLE (https://github.com/Improbable-AI/random-latent-exploration) > * GFA-RFE (https://github.com/uclaml/GFA-RFE) Regarding the comparison with more recent baselines (*Question 2*), we have included the DRND (online) and GFA-RFE in our experiments, and we extend the comparison tasks to include 5 Atari games and 2 more Robot tasks. The results are shown in [Figure R.1](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.1.pdf). The extended comparison includes 10 baselines in 14 tasks, and SASR demonstrates competitive performance. ## Experiments for Atari Games > * (*Weakness 3*) There are no pixel-based experiments, i.e., Atari games. It's unclear how would SASR perform with pixel-based inputs? > * (*Question 1*) How would SASR perform on some famous hard exploration tasks, i.e., Montezuma's Revenge and DM-Hard-8? Regarding the pixel-based experiments and hard exploration tasks, we have conducted additional experiments on 5 Atari games, including the well-known *Montezuma's Revenge*. The results are shown in [Figure R.3](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.3.pdf). ## Experiments in AntMaze Task > * (*Question 2*) Can SASR solve difficult maze tasks with sparse reward, i.e., AntMaze_HardestMaze-v5 from https://robotics.farama.org/envs/maze/ant_maze/? Regarding the *AntMaze* task, we have tested SASR on this benchmark and observed strong performance, showcasing its ability to handle difficult maze tasks effectively. The results, shown in [Figure R.6](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.6.pdf), will be included in the revised paper. ## Initial Successful Trajectories Discovery > * (*Question 3*) For a hard exploration task where we only receive nonzero reward when the task is solved. If it's very difficult to collect the first successful trajectories. How will SASR perform when the success rates for all states are zero? Will the beta distribution be accurate enough to solve such problems? Regarding your concern about the discovery of successful trajectories in the early learning stages, even one state is only included in the failed trajectories in the beginning, the Beta distribution for this state is $Beta(1, N)$, and sampling from this distribution will still generate a non-zero success rate. Moreover, SASR indeed accelerates the initial successful trajectory discovery due to multiple exploration mechanisms. Please kindly refer to our **Global Response - Section 1** for detailed explanations. > * (*Weakness 4*) Typos: (Line 296) "The motivations behind this are" The typo is fixed in the revised paper. Lastly, we thank you for your feedback.
Many thanks to the authors for thoroughly addressing my concerns and adding the extra experiments. I would like to raise my score to 6. - For the first point in the Global Response, it seems the motivation "any state can be randomly rewarded" is close to use a random noise as the reward during the early stage. Can the author further comment on the differences of using a random noise as the reward? - Will the code be open-sourced?
Dear reviewer, Thank you so much for your reply and raising the score. Regarding your follow-up questions: 1. **Further comments on the random noise rewards:** In the very early stages of training, the mechanism of "any state can be randomly rewarded" is indeed similar to using random noise as the reward. However, there are two key differences and advantages: * The randomness is directly generated by SASR’s mechanism, without the need for additional noise functions or mechanisms. Importantly, for unexplored states, the $Beta(1, 1)$ distribution is equivalent to $Uniform(0, 1)$: $$ \text{Beta}(x; 1, 1) = \frac{\Gamma(1+1)}{\Gamma(1)\Gamma(1)}x^{1-1}(1-x)^{1-1} = 1, $$ thus, SASR naturally incorporates the randomness without requiring additional noise functions/distributions. * If external random noise is used, additional considerations are needed, such as when to stop the noise, how to decay it, how to allocate randomness across different states, etc. However, with SASR, these complexities are resolved automatically. As explained in the Global Response, as more samples are collected, SASR inherently assigns relatively higher random values to unexplored states, encouraging the agent to explore novel states. This dynamic adaptation is not achievable with other purely random noise. 2. **Open-Source Codes:** Yes, we plan to open-source the code after the review process. The current code is already provided in the supplementary materials. Thank you for your interest! Once again, we appreciate your recognition and support.
Summary
The paper presents a method called Self-Adaptive Success Rate based Reward Shaping (SASR) aimed at addressing the sparse-reward problem in reinforcement learning. SASR uses success rates from past interactions to construct a shaped reward functions. Success rates are sampled from an evolving Beta distribution, estimated via Kernel Density Estimation with Random Fourier Features to improve efficiency. The authors experimentally validate SASR and ablate their design choices.
Strengths
- The use of Beta distributions to manage exploration-exploitation trade-offs in sparse-reward environments seems to be simple yet effective. - The use of KDE with RFF makes the estimation of Beta distributions more efficient. Moreover, the success rates based method is more computationally efficient than similar previous work (ReLara), which uses a neural network to learn shaping rewards. - SASR shows improved convergence stability in sparse-reward settings compared to several baselines.
Weaknesses
1. **Inconsistent Notation.** The notation is inconsistent in some parts of the paper. 1. Equation 6 uses boldface notation for state variables, while the rest of the paper does not. 2. Similarly, in Algorithm 1, in lines 12 and 13 the states and states buffers are bolded, when they are not everywhere else. 3. In Section 4.3, the environmental reward uses a different notation from Equation 3. The authors should choose to either use $R^E(s_{t})$ or $r_t^E$. 2. The retention rate $\phi$ in line 265 has not been introduced yet. It can be helpful to introduce it before using it in presenting the space complexity of SASR. 3. Section 4.3 seems to be partially copied from the ReLara paper. 1. The $\mathcal A_P$ in the Q-function is redundant. 2. The notation for the policy should be made consistent. At the moment, the policy appears with three different notations. 4. This method was only tested for state-only reward functions. In contrast, ReLara can also work for state-action reward functions. Why is the reward function considered in SASR state-only? Can the authors also show the efficacy of SASR for state-action reward functions or provide arguments as to why this is not necessary? 5. Montezuma Revenge is know to be a hard exploration problem. It would be insightful to have a comparison of SASR with other exploration algorithms, such as RND. 6. SASR appears to be quite similar to ReLara, except it is restricted to using a Beta distribution for success rates, rather than a more expressive neural network to propose shaping rewards. The paper would benefit from a more thorough discussion on why ReLara seems to perform worse, despite using an overparametrized neural network, which should in theory be able to learn a Beta distribution.
Questions
See **Weaknesses**. Additionally: 1. Does the method require to know $R_\min$ and $R_\max$? If not, are they estimated? How? 2. In line 305, it is stated that "if a reward is obtained within a pre-defined maximum number of steps, the corresponding sub-sequence is classified as a success". How is the threshold for the reward and number of steps decided? Is the algorithm sensitive to how these are chosen? 3. In the following grid-world environment, where B is a bad state with very low reward, O is an empty state, G is the goal state, W is a wall and A is the agent, would SASR encourage the agent A to encourage the agent to take the longer path that goes down, right and then up because the state between B and G would be counted in many successful and failure trajectories, so it would be deemed a bad state? How could you make sure that in this case, the agent still takes the shortest path? ``` | B | O | G | O | | W | A | W | O | | W | O | W | O | | W | O | O | O | ```
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
2
***Response to Reviewer JGvx Part 1/3*** Dear reviewer, Thank you for your valuable comments. We address your concerns and questions in the following sections. ## Weaknesses > 1. Inconsistent Notation. The notation is inconsistent in some parts of the paper. > 1. Equation 6 uses boldface notation for state variables, while the rest of the paper does not. > 2. Similarly, in Algorithm 1, in lines 12 and 13 the states and states buffers are bolded, when they are not everywhere else. > 3. In Section 4.3, the environmental reward uses a different notation from Equation 3. The authors should choose to either use $R^E(s_t)$ or $r^E_t$. * Regarding the boldface states in Equations and Algorithm 1, our intention was to distinguish state variables as vectors. We acknowledge that this differentiation was applied inconsistently, we have revised the entire paper and made the notation uniform to avoid confusion. (Our revised paper will be updated here as soon as possible.) * Regarding the environmental reward, we intended $R^E(s_t)$ to denote the reward function and $r^E_t$ to denote the reward value at timestep $t$, wi.e., $r^E_t = R^E(s_t)$. We have clarified this to avoid any confusion in the revised paper. > 2. The retention rate in line 265 has not been introduced yet. It can be helpful to introduce it before using it in presenting the space complexity of SASR. Thanks for pointing out the misplacement of the retention rate introduction, we have exchanged *Section 4.2.2 Implementation Details* and *Section 4.2.1 Time and Space Complexity of SASR* to introduce the retention rate before using it in the space complexity analysis. > 3. Section 4.3 seems to be partially copied from the ReLara paper. > 1. The $A_p$ in the Q-function is redundant. > 2. The notation for the policy should be made consistent. At the moment, the policy appears with three different notations. We appreciate your comment on this and apologize for the oversight, we have corrected the whole section to avoid any redundancy or inconsistency. > 4. This method was only tested for state-only reward functions. In contrast, ReLara can also work for state-action reward functions. Why is the reward function considered in SASR state-only? Can the authors also show the efficacy of SASR for state-action reward functions or provide arguments as to why this is not necessary? Regarding the state-action reward function, we agree that it is an important aspect to consider. It is a natural extension of SASR by incorporating the action as an additional feature in the state vector, i.e., we evaluate the success rates of state-action pairs. We conducted additional experiments on five tasks to compare state-only SASR with state-action SASR, and ReLara was aslo included for comparison. We show the results in [Figure R.2](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.2.pdf), we want to share some insights here: * State-action SASR outperforms state-only SASR in several tasks, because of incorporating the action dimension, more information is available for the success rate evaluation, while we found that the improvement is not significant. * In two tasks, RobotReach and RobotPush, state-only SASR still outperformed state-action SASR, where the potential reasons would be: (a) **distribution mismatch**, the state and action vectors may exhibit different distributions, potentially reducing the accuracy of KDE estimations; and (b) **dimensionality**: adding actions increases the dimensionality, complicating density estimation and correlation assessment. All of the results and discussions will be reported in the revised paper. > 5. Montezuma Revenge is know to be a hard exploration problem. It would be insightful to have a comparison of SASR with other exploration algorithms, such as RND. To provide a more comprehensive evaluation, we have conducted additional experiments on 5 Atari games, including the well-known *Montezuma's Revenge*. The results are shown in [Figure R.3](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.3.pdf). In the *Montezuma's Revenge* task, SASR demonstrates competitive performance compared to all baselines, including RND.
***Response to Reviewer JGvx Part 2/3*** > 6. SASR appears to be quite similar to ReLara, except it is restricted to using a Beta distribution for success rates, rather than a more expressive neural network to propose shaping rewards. The paper would benefit from a more thorough discussion on why ReLara seems to perform worse, despite using an overparametrized neural network, which should in theory be able to learn a Beta distribution. Regarding the comparison with ReLara, while our work is inspired by ReLara, there are several key differences that make SASR a fundamentally distinct approach. The main difference is that SASR uses the success rate, a more intuitive and direct metric, while ReLara uses a black-box RL agent. We want to highlight some targeted improvements of SASR addressing some of ReLara's limitations: 1. **Reduced Computational Requirements**: ReLara’s use of an assistant RL agent (with the same scale of the original RL agent) adds significant computational overhead. In comparison, ReLara requires approximately 1.8 times the training time of SASR to complete 1 million steps, which is primarily due to the simultaneous maintenance of two RL agents and running two RL algorithms. In contrast, SASR provides computationally efficient reward calculations. 2. **Faster Reward Model Convergence**: ReLara’s reward agent requires step-by-step learning through backpropagation to converge to a good reward model, SASR, on the other hand, derives rewards from statistical metrics, providing meaningful rewards earlier. This is also evident in Figure 3, where SASR demonstrates faster convergence in most tasks. 3. **ReLara's Advantage**: We agree with your mentioned, that ReLara's advantage lies in its ability to capture richer and more complex reward features beyond the success rate, which aligns with our observations that ReLara gets better performance in the **RobotReach** task, where the changing target position requires a more complex reward model. However, this advantage comes at the cost of significantly higher training time. ## Questions > 1. Does the method require to know $R_{min}$ and $R_{max}$? If not, are they estimated? How? Regarding the $R_{min}$ and $R_{max}$, they refer to the lower and upper bounds of the desired shaped rewards. As the rewards drawn from the Beta distribution are ranged in $[0, 1]$, we introduce a linear mapping function to project them to $[R_{min}, R_{max}]$ for cases where different reward scales are required (e.g., some tasks give $1$ positive reward, while others may give $100$). This is mainly for enhancing generality and adaptability. In our experiments, all tasks are using the default $R_{min}=0$ and $R_{max}=1$. Usually, aligning the reward scale with the scale of the environmental rewards is a good choice. > 2. In line 305, it is stated that "if a reward is obtained within a pre-defined maximum number of steps, the corresponding sub-sequence is classified as a success". How is the threshold for the reward and number of steps decided? Is the algorithm sensitive to how these are chosen? Regarding the threshold for the number of steps, it is introduced mainly for some special tasks where sparse rewards are not only given at the end of the episode but also at some intermediate steps. In our experiments, the *RobotReach* task is an instance of this situation. In this task, each episode has a fixed maximum number of steps. The robot receives a reward of $1$ upon reaching the target point, but it might subsequently move away and receive a reward of $0$. This reward structure does not reflect the entire trajectory of task completion. Instead, it mainly measures the frequency of the robot reaching and keeping at the target point. In this case, we define the threshold as $50$ steps, which is $1/4$ of the maximum episode length ($200$). The algorithm is not sensitive to the choice of this threshold, and our intention is to show that SASR can be applied to tasks with more general intermediate rewards.
***Response to Reviewer JGvx Part 3/3*** > 3. In the following grid-world environment, where B is a bad state with very low reward, O is an empty state, G is the goal state, W is a wall and A is the agent, would SASR encourage the agent A to encourage the agent to take the longer path that goes down, right and then up because the state between B and G would be counted in many successful and failure trajectories, so it would be deemed a bad state? How could you make sure that in this case, the agent still takes the shortest path? ``` | B | O | G | O | | W | A | W | O | | W | O | W | O | | W | O | O | O | ``` Thanks for this interesting question, overall, we believe that SASR can still ensure the agent takes the shortest path by going through the intermediate states between the bad state $B$ and the goal state $G$. We conducted an analysis and an empirical experiment to demonstrate this as follows: **Analysis:** 1. First, we define the bad state $B$ as $s_B$, the good state $G$ as $s_G$, the middle state between $B$ and $G$ as $s_{mid}$, and the agent's starting state as $s_A$. We assign the environmental rewards as: $R^E(s_B) = -1$, $R^E(s_G) = 1$, $R^E(s_{mid}) = 0$, and $R^E(s_A) = 0$. We assume the discount factor $\gamma = 0.9$, the shaped reward weight $\lambda = 1$. 2. Second, since both the trajectories from $s_A$ to $s_G$ and from $s_A$ to $s_B$ pass through $s_{mid}$, **in the inital phase**, we can assume that the visits to $s_{mid}$ are evenly distributed between these two types of trajectories. Specifically, the number of trajectories $s_A \rightarrow s_{mid} \rightarrow s_G$ and $s_A \rightarrow s_{mid} \rightarrow s_B$ are equal. Therefore, the success rate of $s_{mid}$ is $0.5$ (ignoring the Beta sampling part for simplicity), then the shaped reward $r^S(s_{mid}) = 0.5$. Using this shaped reward, we can calculate: $$ Q(s_{mid}, Right) = R^E(s_{mid}) + \lambda R^S(s_{mid}) + \gamma Q(s_G) = 0 + 0.5 + \gamma \times 1 = 1.4 $$ while $$ Q(s_{mid}, Left) = R^E(s_{mid}) + \lambda R^S(s_{mid}) + \gamma Q(s_B) = 0 + 0.5 + \gamma \times (-1) = -0.4 $$ 3. Next, **in the later stage**, we can assume that the policy is greedy, so the agent will choose the action $Right$ at $s_{mid}$ because $Q(s_{mid}, Right) > Q(s_{mid}, Left)$. Consequently, the number of trajectories $s_A \rightarrow s_{mid} \rightarrow s_G$ will increase, which implies that $s_{mid}$ will appear more in successful trajectories, leading to an increase in its success rate. Over time, $s_{mid}$ will gradually converge to a shaped reward that is more associated with success rather than failure. 4. Since the $s_{mid}$ state is gradually associated with success, the agent will eventually learn to take the shortest path $s_A \rightarrow s_{mid} \rightarrow s_G$ instead of the longer path, because of the RL agent is driven to maximize the long-term discounted return. In summary, $s_{mid}$, being located between the successful and failed states, start with a success rate close to the middle value in the early phase. However, as the agent's policy is driven by the Q-values, $s_{mid}$ will increasingly appear in successful trajectories during the later phase. This mechanism ensures that $s_{mid}$ can be deemed as a good state. **Experiment Validation:** To further prove this, we also conducted an experiment in this grid-world environment, to simplify, we incorporated SASR into a tabular Q-learning. The configurations are: $R^E(s_B) = -1$, $R^E(s_G) = 1$, $R^E(s_{mid}) = 0$, $R^E(s_A) = 0$, $\gamma = 0.9$, $\lambda = 0.1$, learning rate $\alpha=0.1$, maximum episode length is $15$, total learning episodes is $10000$. After learning, the Q-table shows that: $$ Q(s_A, Up) = 1.084, Q(s_A, Down) = 1.062, Q(s_A, Up) > Q(s_A, Down) $$ and $$ Q(s_{mid}, Right) = 1.097, Q(s_{mid}, Left) = -0.903, Q(s_{mid}, Right) > Q(s_{mid}, Left) $$ Thus, the final optimal policy for the agent is to take the shortest path $s_A \rightarrow s_{mid} \rightarrow s_G$. Once again, we appreciate your valuable feedback and also hope our responses have addressed your concerns.
Thank you for the detailed comments! The authors have effectively addressed my concerns and included experiments on additional tasks to support their claims. I recommend acceptance and will maintain my score (6, marginally above the acceptance threshold). I am also open to further discussions with the authors, other reviewers, and the chairs.
Summary
The paper proposes SASR, a novel method for adaptive reward shaping in RL with sparse binary rewards, based on the idea that states that belong to trajectories ending in success are more valuable than states that belong in a trajectories that end in failure, so visiting such states should be encouraged by increasing the immediate stage reward leading to them. This mechanism is a form of temporal credit assignment, a central question in RL with sparse rewards, and appears to be very effective in speeding up learning in multiple test problems.
Strengths
The main strength of the paper is perhaps the principled approach in augmenting the reward function of RL with sparse rewards with a component that encourages visiting states that have proven to be useful in completing a sequential decision making task in past trials. The proposed method of using beta distributions to model the probability that a state is useful avoids overconfidence in this probability from very few samples, and is helpful in encouraging exploration in the early stages of learning. The proposed use of kernel density estimation combined with random Fourier features solves the problem of keeping tally of which states are successful in continuous state spaces. The experimental verification is rigorous and of high quality and leaves no doubt in the effectiveness of the method on representative benchmark problems of significant complexity. The paper is well written and easy to follow, and the related work section is thorough and informative.
Weaknesses
The method still needs at least some trajectories with successful outcomes, so it cannot speed up the initial discovery of such trajectories, which is perhaps the most difficult problem in RL with sparse rewards. A claim has been made that the method for estimating the beta distributions of expected success of individual states is parameter-free and learning-free, and I am not sure I agree with that. At the very minimum, the KDE estimator depends on the bandwidth parameter h, and the ablation study in Section 5.3 clearly shows that its value does matter a lot as regards the accuracy of estimation and the overall success of the algorithm. Usually, the bandwidth of KDE schemes is determined by a search routing of some kind, either grid search or cross-validation, which is a form of learning. Other parameters that matter are M, the number of RFF, and lambda, the weight of the additional reward term, and they must be determined somehow, preferably automated by some form of learning. A minor typo: P. 8. L. 427: "broadens" -> "broadening"
Questions
The use of a state's success rate reminds me of the use of eligibility traces, whose purpose is also to assign credit to states and actions taken in them. Eligibility traces typically depend on how far in the future success happened, whereas in this paper, the success of a state does not depend on the time horizon of a positive reward. Have the authors considered time-dependent or other variable weights depending on distance to the goal state, similar to eligibility traces? Could the authors clarify what they mean by "parameter-free" and "learning-free" in the context of KDE estimation? Could the authors discuss potential automated methods for selecting parameters like bandwidth h, number of RFF M, and reward weight λ? Regarding getting to successful outcomes earlier rather than later, does SASR provide any benefits in the very early stages of learning before successful trajectories are found?
Rating
8
Confidence
4
Soundness
4
Presentation
4
Contribution
4
***Response to Reviewer XbGP Part 1/2*** Dear reviewer, Thank you for your constructive comments. We respond to your questions in the following sections. ## Discovery of Successful Trajectories in Early Stages > The method still needs at least some trajectories with successful outcomes, so it cannot speed up the initial discovery of such trajectories, which is perhaps the most difficult problem in RL with sparse rewards. > Regarding getting to successful outcomes earlier rather than later, does SASR provide any benefits in the very early stages of learning before successful trajectories are found? Regarding your comments on the discovery of successful trajectories in the early learning stages (*Weakness 1* and *Question 1*), we would like to highlight that SASR indeed accelerates the initial successful trajectories discovery due to multiple exploration mechanisms. Please kindly refer to our **Global Response - Section 1** for detailed explanations. ## Eligibility Trace Inspired Reward Shaping > The use of a state's success rate reminds me of the use of eligibility traces, whose purpose is also to assign credit to states and actions taken in them. Eligibility traces typically depend on how far in the future success happened, whereas in this paper, the success of a state does not depend on the time horizon of a positive reward. Have the authors considered time-dependent or other variable weights depending on distance to the goal state, similar to eligibility traces? Regarding the potential connection between SASR and eligibility traces (*Question 2*), the current work focuses on reward shaping to densify sparse rewards, so the horizon-dependent utility is still assumed to be learned by the critic module in the RL algorithm. However, we agree that encoding time-related contributions into the shaped rewards is a valuable direction for improvement. A potential extension could be using **weighted Kernel Density Estimation** [1], where the density estimation is reformulated as: $$ \hat{d}(x) = \frac{1}{\sum_{i=1}^n w_i} \sum_{i=1}^n w_i K\left(\frac{x - x_i}{h}\right), $$ with weights $w_i$ determined by the state’s position in the trajectory, reflecting its contribution to the success in the temporal dimension, similar to eligibility traces: $$ w_{\tau} = \lambda^{T-\tau}, \quad \lambda \in (0, 1), $$ where $T$ is the trajectory length and $\tau$ is the timestep. This adjustment would encode the state's temporal contribution, aligning with the principles of eligibility traces. [1] Jones, M. C., Marron, J. S., & Sheather, S. J. (1996). A brief survey of bandwidth selection for density estimation. Journal of the American Statistical Association, 91(433), 401-407.
***Response to Reviewer XbGP Part 2/2*** ## Parameter-Free and Learning-Free KDE > A claim has been made that the method for estimating the beta distributions of expected success of individual states is parameter-free and learning-free, and I am not sure I agree with that. At the very minimum, the KDE estimator depends on the bandwidth parameter h, and the ablation study in Section 5.3 clearly shows that its value does matter a lot as regards the accuracy of estimation and the overall success of the algorithm. Usually, the bandwidth of KDE schemes is determined by a search routing of some kind, either grid search or cross-validation, which is a form of learning. Other parameters that matter are M, the number of RFF, and lambda, the weight of the additional reward term, and they must be determined somehow, preferably automated by some form of learning. > Could the authors clarify what they mean by "parameter-free" and "learning-free" in the context of KDE estimation? Could the authors discuss potential automated methods for selecting parameters like bandwidth h, number of RFF M, and reward weight $\lambda$? Regarding your concern on the parameter-free and learning-free claim and the automated hyper-parameter selection (*Weakness 2* and *Question 2*), our intention was to differentiate SASR from methods requiring parameter learning of neural networks or complex models. For instance, in our baselines: RND requires learning of random networks, ReLara requires an additional RL agent, ROSA requires a competition agent and switching model, and ExploRS requires learning a parameterized network. In contrast, *non-parametric and learning-free* in SASR refers to the direct computation of the shaped reward without additional learning processes. We admit that this definition might not be precise, and we will provide a more accurate clarification in the revised paper. (Our revised paper will be updated here as soon as possible.) Regarding your suggestion on automated hyper-parameter selection, we agree that it is an important aspect. Our current approach treats the bandwidth $h$, RFF dimension $M$, and reward weight $\lambda$ as hyper-parameters, and we use heuristic methods to select them. The ablation study mainly examines the impact of extreme values of these hyper-parameters. However, we identified an intuitively reasonable value that works consistently across all experiments, which is also used in our experiments. However, we acknowledge the importance of using learning methods to determine the optimal parameters. Here are some potential methods for further research: * For bandwidth $h$, we can use the empirical formula "Silverman's Rule of Thumb" $h=1.06 \cdot \sigma \cdot N^{-1/5}$ or cross-validation to determine the optimal bandwidth. * For the RFF dimension $M$, it is directly related to the bandwidth $h$. After determining $h$, we can use the formula mentioned in the RFF theory to determine $M$: $M = O(\frac{1}{\epsilon^2} \log{\frac{N}{\delta}})$, where $\epsilon$ and $\delta$ are the error and confidence parameters. Or we can compare the Frobenius norm error between the RFF approximated kernel matrix $K^{RFF}$ and the true kernel matrix $K^{Gaussian}$ to select $M$: $\|K^{RFF} - K^{Gaussian}\|_F$. * For the reward weight $\lambda$, it is usually determined based on the environment reward scale. Based on the reward shaping studies, e.g., RND, ReLara, and ExploRS, setting the shaped reward to half of the environment reward is a good choice. We used this finding in our experiments and obtained consistent results in the ablation study. Another feasible approach is to use a dynamic reward weight according to the learning effect and exploration requirement. Once again, thank you for your valuable comments.
Questions addressed well
I am satisfied with the comments provided by the authors on how the bandwidth of KDE and the number of RFF can be determined in practice. I maintain my rating and recommend acceptance.
Official Comment - Global Response
***Global Response Part 1/2*** # Global Response We appreciate all reviewers' insightful feedback on our work. In response to some common questions and to share new experimental results, we provide a comprehensive response covering the following aspects: ## Section 1: Exploration and Successful Trajectories Discovery in Early Stages A common question is how SASR effectively explores and discovers the initial successful trajectories in the early stages. We would like to highlight that SASR indeed accelerates the initial successful trajectory discovery through multiple exploration mechanisms. We provide detailed explanations below: **Early Exploration Mechanisms** Beyond the backbone exploration strategies by the entropy term and stochastic policy in SAC, SASR has two additional exploration mechanisms: **random rewards perturbation** and **encouragement for novel states**: 1. **Random Rewards Perturbation**: It is known that in intrinsic motivation based approaches (e.g., RND, #Explo, and ExploRS), exploration is driven by rewarding novel states. However, during the **very early stages** of training, we observed that almost all states exhibit similar levels of novelty due to insufficient experience, making the intrinsic rewards nondiscriminatory. Therefore, we relax the assumption that only novel states should be rewarded, instead, any state can be randomly rewarded. The advantage is that it generates more diverse rewards, randomly encouraging the agent to explore different regions, additionally, it avoids the stagnation of training with sparse rewards. Specifically, the original TD-target is $y^{ori} = r^E + \gamma Q'$, while the perturbed TD-target is $y^{shaped} = r^E + \lambda r^S + \gamma Q'$, importantly, $r^E$ is almost $0$. So without the perturbation ($\lambda r^S, r^S \sim Beta(1,1)$), the Q-function is only optimized to the discounted next-state Q-value, while with the perturbation, the Q-function is optimized to chase a "moving" target, which then influences the policy network optimization to "shift" its policy anchor, thus expanding the visited state space. 2. **Encouragement for Novel States**: after the very beginning phase, the mechanism of *random rewards perturbation* gradually weakens. Because a large number of states have been visited, and, as reviewers mentioned, almost all states are classified into the failure category. This leads to a decrease in the success rate of these states. We know that the initial Beta distribution for an unvisited state is $Beta(1,1)$, which is equivalent to a uniform distribution, and the expected success rate of the unvisited states is $0.5$. For example, we assume that the visited and failed states decrease their success rate from the initial $0.5$ to $0.3$, then the unvisited states will have relatively higher shaped rewards. As a result, SASR will encourage the agent to explore these unvisited states, i.e., novel states. The advantage is avoiding explicit novelty evaluation while still increasing the rewards for novel states (by relatively reducing the rewards of visited states). This mechanism achieves a similar effect to explicitly rewarding novelty and leads to broader exploration. **Evidence in Experiments** The early exploration effect is also evident in Figure 5. In the *MountainCar* task, SASR covers a much larger range of visited states within the first 50k steps compared to the backbone SAC algorithm. The comparison with different exploration strategies in Figure 5 also demonstrated comparable performance.
***Global Response Part 2/2*** ## Section 2: Additional Experimental Results To provide more comprehensive evaluations, we provide additional experimental results by anonymous links: 1. [Figure R.1](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.1.pdf): An extended comparison of SASR with 10 baselines in 14 tasks. In addition to the original 8 baselines, we include 2 more baselines (DRND and GFA-RFE) suggested by *Reviewer NDw1*; Besides, we added 5 Atari games to evaluate SASR in pixel-based environments, including the well-known *Montezuma's Revenge*, and 2 new Robot tasks. The table reports the mean and standard deviation of the final performance of each algorithm over 100 episodes. 2. [Figure R.2](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.2.pdf): A new ablation study to compare SASR with state-action reward functions and state-only reward functions in 6 tasks. 3. [Figure R.3](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.3.pdf): New results on 5 Atari games, including the well-known *Montezuma's Revenge*, to evaluate the performance of SASR in pixel-based environments. (Included in Figure R.1) 4. [Figure R.4](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.4.pdf): New results on 4 Robot tasks. (Included in Figure R.1) 5. [Figure R.5](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.5.pdf): Updated Figure 5 in the paper to include the RND algorithm for comparison. 6. [Figure R.6](https://anonymous.4open.science/api/repo/SASR-Materials/file/R.6.pdf): Case study on the *AntMaze* task to evaluate the performance of SASR on hard-exploration tasks. ## Section 3: Revised Paper We are revising the paper according to the reviewers' suggestions. All of the new experimental results and discussions will be included in the revised version. Our revised paper will be updated here as soon as possible.
Revised Paper Uploaded
Dear Reviewers, We are pleased to inform you that **our revised paper has been uploaded**. All major updates have been highlighted in blue for your convenience. The key revisions are as follows: 1. We have incorporated all suggestions from the reviewers into the revised paper, addressing both the main text and the appendix. 2. We have extended our experiments, comparing our algorithm with 2 more baselines (10 in total) across 4 domains (14 environments): four *MuJoCo* tasks, four robotic tasks, five *Atari* games, and one physical simulation task. Besides, there is an additional ablation study experiment, as well as time and space complexity evaluations. All new results are included in the revised paper. 3. More related papers are cited and discussed. 4. All typos, incorrect symbols, and other minor errors have been corrected. Thank you again for your feedback, and we look forward to hearing your thoughts. --- **Update**: Dear reviewers, we have removed the blue highlights from the revised paper to comply with the submission format requirements. Thanks a lot!
Meta-review
Reward shaping is important for RL in general. This paper address the sparse-reward problem in reinforcement learning. The proposed method uses success rates from interactions to shape reward functions. Success rates are sampled from a Beta distribution posterior, estimated via Kernel Density Estimation with Random Fourier Features to improve efficiency. The paper is easy to follow. The AC agrees with all of the reviewers that it reached the bar of ICLR 2025.
Additional comments on reviewer discussion
The authors extended the experiments during the discussion phase. It is an incremental work on an important problem.