Highly Efficient Self-Adaptive Reward Shaping for Reinforcement Learning

## Abstract

Abstract 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.

## 1 Introduction

Environments with extremely sparse rewards present notable challenges for reinforcement learning (RL). In such contexts, as the reward model lacks immediate signals, agents receive feedback only after long horizons, making the ability to quickly discover beneficial samples crucial for successful learning (Ladosz et al.,, ). To address this, a straightforward solution is to reconstruct the reward models by introducing auxiliary signals to assess the agent’s behavior, which has led to the popular technique of Reward Shaping (RS) (Strehl and Littman,, ; Gupta et al.,, ). Inverse reinforcement learning (IRL), which extracts reward functions from human knowledge or expert demonstrations, represents an intuitive approach within this framework Arora and Doshi, (). However, IRL heavily relies on extensive human input, which can be difficult to obtain especially in complex environments. Alternatively, fully autonomous approaches have emerged as an attractive direction.

Automatically maintained reward shaping can be broadly categorized into two branches: intrinsic motivation-based rewards, which are task-agnostic, and inherent value-based rewards, which are typically task-specific. The former mainly introduces exploration bonuses to encourage agents to explore a wider range of states, commonly by rewarding novel or infrequently visited states (Burda et al.,, ; Ostrovski et al.,, ; Tang et al.,, ; Bellemare et al.,, ). While these methods effectively enhance exploration, they tend to overlook the internal values of the states. This can lead to the "noisy TV" problem, where agents fixate on highly novel but meaningless regions, thus trapping them in suboptimal behaviors (Mavor-Parker et al.,, ). In contrast, the latter leverages high-level heuristics to guide agents in extracting meaningful values from learning experiences, which helps stabilize convergence. (; Memarian et al.,, ; Trott et al.,, ).

To overcome the limitations of existing RS methods and combine the advantages of exploration-encouraged and inherent value-based rewards, this paper introduces a novel Self-Adaptive Success Rate based reward shaping mechanism (SASR). The success rate, defined as the ratio of a state’s presence in successful trajectories to its total occurrences, works as an auxiliary reward distilled from historical experience. This success rate assesses a state’s contribution toward successful task completion, which closely aligns with the agent’s original objectives, offering informative guidance for learning. Furthermore, to mitigate overconfidence caused by deterministic success rates, we adopt Beta distributions to model success rates from a probabilistic perspective. Beta distributions enable a self-adaptive evolution of confidence in approximating a state’s success rate, ensuring the system gradually converges to reliable rewards as more data is collected, while preventing premature certainty. To derive Beta distributions, we use kernel density estimation (KDE) enhanced by random Fourier features (RFF) to estimate success and failure counts, formulating a highly efficient approach. The main contributions of this paper are summarized as follows:

- •
We propose SASR, an autonomous reward-shaping mechanism without the requirement of domain knowledge. By extracting a metric from historical experiences that aligns with the agent’s optimization objectives, SASR effectively augments the environmental rewards.
- •
A novel self-adaptive mechanism is introduced to achieve an efficient exploration-exploitation balance. Initially, low-confidence Beta distributions provide stochastic rewards that encourage exploration by diversifying policy optimization. As more experience accumulates, high-confidence Beta distributions offer more reliable and precise rewards to enhance exploitation.
- •
To derive the Beta distributions in continuous state spaces, we implement KDE with RFF. This formulates a non-parametric and learning-free approach, thereby achieving remarkably low computational complexity.
- •
SASR is evaluated on various extremely sparse-reward and continuous control tasks, significantly outperforming several baselines in sample efficiency, learning speed, and convergence stability.

## 2 Related Work

Reward shaping (RS) methods can generally be categorized based on the source of learning: either from human knowledge or agent’s own experiences. Techniques that derive reward models from human knowledge, such as Inverse Reinforcement Learning (IRL) (Arora and Doshi,, ; Ramachandran and Amir,, ; Ziebart et al.,, ; Hadfield-Menell et al.,, ) and Inverse Optimal Control (IOC) (Schultheis et al.,, ), aim to extract reward or objective functions from expert demonstrations. Following this, transferring the learned reward models to new tasks has received considerable efforts (Bıyık et al.,, ; Wu et al.,, ; Ellis et al.,, ; Cheng et al.,, ; Adamczyk et al.,, ). However, these methods rely heavily on human-generated data and often struggle to adapt to out-of-distribution scenarios. Thus, our focus shifts toward autonomous self-learning approaches, which can be further divided into intrinsic motivation-based and inherent value-based rewards based on the nature of the rewards.

Intrinsic motivation based RS explores general heuristics or task-agnostic metrics to encourage exploration. Potential-based algorithms define the shaped reward as $\gamma\Phi(s^{\prime})-\Phi(s)$, where $\Phi(\cdot)$ is a potential function. This ensures the reward cancels out in the Bellman equation, preserving the optimal policy (Devlin and Kudenko,, ; Asmuth et al.,, ; Wiewiora,, ). However, designing the potential function is highly dependent on the environmental dynamics, making it more applicable to model-based RL. More commonly, methods incorporate exploration bonuses to reward novel states (Devidze et al.,, ; Badia et al.,, ; Hong et al.,, ; Eysenbach et al.,, ). Representatively, count-based strategies track visitation counts and assign higher rewards to less frequently visited states (Lobel et al.,, ; Machado et al.,, ; Fox et al.,, ; Fu et al.,, ; Martin et al.,, ). In continuous spaces, state counting is challenging, so Tang et al., () introduced a hash function to discretize the state space, Bellemare et al., () proposed pseudo-counts based on recording probabilities, and Ostrovski et al., () used PixelCNN Van den Oord et al., (). Additionally, random network distillation based methods measure state novelty by neural networks (Yang et al.,, ; Burda et al.,, ), curiosity-driven approaches reward agents for encountering surprising or unpredictable states (Sun et al.,, ; Burda et al.,, ; Pathak et al.,, ). Although intrinsic motivation has proven effective in enhancing exploration, only considering novelty while ignoring the inherent values of states may lead to suboptimal policies. A notable example illustrating this limitation is the "noisy TV" problem (Mavor-Parker et al.,, ), where agents may become attracted to irrelevant, dynamic stimuli that generate high novelty but provide no useful information.

Inherent value based RS, on the other hand, focuses on task-related signals that highlight how states contribute to achieving higher rewards and their underlying significance. For instance, Trott et al., () introduced additional rewards based on the distance between a state and the target; Stadie et al., () derived informative reward structures using a Self-Tuning Network to optimize guidance; Memarian et al., () captured the preferences among different trajectories by ranking them via a trained classifier; Zheng et al., () minimized the KL-divergence between learned and original rewards to align their distributions. Mguni et al., () used an auxiliary agent competing against the original agent in a Markov game; Instead, introduced ReLara, a collaborative framework where an assistant reward agent automatically generates rewards to guide the policy agent. Moreover, incorporating multiple agents or hierarchical structures to share and transfer knowledge through synchronized reward functions is another promising research direction (Gupta et al.,, ; ; ; Park et al.,, ; Ma et al.,, ; Yi et al.,, ; Hu et al.,, ; Raileanu and Rocktäschel,, ).

While intrinsic motivation rewards guide exploration, inherent value rewards support convergence, combined these two advances by introducing a scheme that evolves the shaped rewards from random perturbations into meaningful metrics. Injecting random rewards during early training relaxes the assumption that only novel states should be rewarded, suggesting instead that any state can be randomly rewarded. Building on this idea, our study considers the success rate as an informative value. We sample this metric from evolving Beta distributions that progressively increase in confidence, enabling a self-adaptive exploration-exploitation balance. Compared with ReLara, which relies on a black-box agent, our method draws information from historical data, effectively reducing the delay of reward convergence and enhancing explainability.

## 3 Preliminaries

Reinforcement Learning (RL) aims to train an agent to interact with an environment, which is commonly modeled as a Markov Decision Process (MDP). An MDP represented as $\langle S,A,T,R,\gamma\rangle$, involves four main components: $S$ is the state space, $A$ is the action space, $T:S\times A\times S\rightarrow[0,1]$ is the probability of transitioning from one state to another given a specific action, and $R:S\rightarrow\mathbb{R}$ is the reward model. The objective in RL is to learn a policy $\pi(a|s)$ that maximizes the expected cumulative rewards $G=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t})]$, where $\pi(a|s)$ indicates the likelihood of selecting action $a$ in state $s$, and $\gamma$ is the discount factor (Sutton and Barto,, ).

Beta Distribution is defined on the interval $[0,1]$, making it ideal for modeling proportions or probabilities. It is parameterized by $\alpha$ and $\beta$, which are interpreted as prior counts of successes and failures of a binary outcome. The probability density function of a Beta-distributed variable $X$ is:

$$ $f(x;\alpha,\beta)=\frac{1}{B(\alpha,\beta)}x^{\alpha-1}(1-x)^{\beta-1},$ (1) $$

where $B(\alpha,\beta)$ is a normalization factor. The key characteristic of Beta distribution is its adaptability: as more data accumulates, the values of $\alpha$ and $\beta$ increase, the distribution’s shape becomes narrower, thereby increasing confidence in the estimated probabilities. This feature is particularly beneficial in adaptive online learning, aligning closely with our objective of balancing exploration and exploitation.

Kernel Density Estimation (KDE) is a non-parametric approach to approximate the probability density function of a random variable from data samples. Given $n$ data points $\{x_{i}\}_{i=1}^{n}$, KDE smooths these points to approximate the density function as follows:

$$ $\hat{d}(x)=\frac{1}{nh}\sum_{i=1}^{n}K\left(\frac{x-x_{i}}{h}\right),$ (2) $$

where $h$ is the bandwidth, $K(\cdot)$ is a kernel function such as Gaussian kernel, Laplacian kernel, or Cauchy kernel. KDE is particularly useful in scenarios where the actual distribution is not well-defined or complex, such as continuous state spaces in our RL environments.

## 4 Methodology

We propose a Self-Adaptive Success Rate based reward shaping mechanism (SASR) to accelerate RL algorithms learning in extremely-sparse-reward environments. Figure 1 illustrates the principles of the SASR mechanism: The diagram consists of two parts representing the early and late learning stages. As experiences accumulate with learning progresses, the Beta distributions modeling the success rates evolve from being more stochastic to more deterministic. This autonomous adaption closely aligns with the agent’s exploration-exploitation balance. Section 4.1 introduces how Beta distributions evolve and how shaped rewards are generated from them. Additionally, to achieve highly efficient computation, we leverage KDE and RFF to estimate success and failure counts, which are used to derive the corresponding Beta distributions, as detailed in Section 4.2. Lastly, Section 4.3 presents the integration of SASR into the RL agent and the overall algorithmic flow.

Figure: Figure 1: A schematic diagram of the self-adaptive success rate based reward shaping mechanism. KDE: Kernel Density Estimation; RFF: Random Fourier Features.
Refer to caption: x1.png

### 4.1 Self-Adaptive Success Rate Sampling

We formulate the augmented reward function in SASR as adding an auxiliary shaped reward $R^{S}(s)$ to the environmental reward $R^{E}(s)$, weighting by a factor $\lambda$:

$$ $R^{SASR}(s)=R^{E}(s)+\lambda R^{S}(s).$ (3) $$

We assign the shaped reward $R^{S}(s_{i})$ of a given state based on its success rate – defined as the ratio of the state’s presence in successful trajectories to its total occurrences. This metric provides a meaningful reward from a statistical perspective: a higher success rate, reflected in a higher shaped reward, indicates a greater likelihood that the state will guide the agent toward successful task completion. Formally, the success rate based shaped reward $R^{S}(s_{i})$ is given by:

$$ $R^{S}(s_{i})=f\left(\frac{N_{S}(s_{i})}{N_{S}(s_{i})+N_{F}(s_{i})}\right),$ (4) $$

where $N_{S}(s_{i})$ and $N_{F}(s_{i})$ denote the counts of state $s_{i}$ appearing in successful and failed historical trajectories, respectively, and $f(\cdot)$ is a mapping function that adjusts the magnitude of rewards: $f:[0,1]\rightarrow[R_{\min},R_{\max}]$.

Given $N_{S}(s_{i})$ and $N_{F}(s_{i})$, directly using a deterministic success rate $N_{S}(s_{i})/(N_{S}(s_{i})+N_{F}(s_{i}))$ may lead to overconfidence in the estimation of the true value. To address this, we model the success rate estimation from a probabilistic perspective, inspired by the principles of Thompson sampling, an effective algorithm widely used to balance exploration and exploitation in multi-armed bandit problems (Thompson,, ; Agrawal and Goyal,, ). We model the success rate of each state as an approximated variable in a Beta distribution, setting the shape parameters $\alpha=N_{S}(s_{i})+1$ and $\beta=N_{F}(s_{i})+1$:

$$ $\displaystyle r^{S}_{i}\sim\text{Beta}(r;\alpha,\beta)=\frac{1}{B(N_{S}(s_{i}) +1,N_{F}(s_{i})+1)}r^{N_{S}(s_{i})}(1-r)^{N_{F}(s_{i})},$ (5) $$

where the beta function $B(\cdot,\cdot)$ is the normalization factor. By sampling from this distribution, we obtain a probabilistic estimate of the true success rate. This sampled value, $r^{S}_{i}$, is then processed through the scaling function $f(\cdot)$ to produce the shaped reward: $R^{S}(s_{i})=f(r^{S}_{i})$.

As $N_{S}(s_{i})$ and $N_{F}(s_{i})$ progressively increase throughout the learning process, they influence the shape and sampling variability of the Beta distribution. Generating the shaped reward from these evolving Beta distributions offers several advantages:

- •
Encourage Exploration. In the early learning phases, the counts $N_{S}(s_{i})$ and $N_{F}(s_{i})$ are relatively low, resulting in broader Beta distributions and greater variability in sampled values, which injects significant randomness into the shaped rewards. These random rewards optimize the agent in various directions with tiny steps, thus shifting the anchors from which the stochastic policy samples actions. The strategy effectively broadens the range of policies and actions, thus encouraging the exploration. (Supporting experimental results in Section 5.2.)
- •
Enhance Exploitation. In the late learning phases, as the counts $N_{S}(s_{i})$ and $N_{F}(s_{i})$ increase, the Beta distribution gradually sharpens, concentrating generated rewards closer to the true success rate. The evolution to a certain reward signal with higher confidence highly supports the agent’s exploitation, facilitating more efficient convergence towards optimal policies.
- •
Consistent Optimization. The peak of the Beta distribution, computed as $N_{S}(s_{i})/(N_{S}(s_{i})+N_{F}(s_{i}))$, directly equals to the success rate. Meanwhile, the expectation, $(N_{S}(s_{i})+1)/(N_{S}(s_{i})+N_{F}(s_{i})+2)$, closely approximates the success rate. This ensures that, despite stochastic, the overall reward remains consistent with policy optimization.

### 4.2 Highly Efficient Beta Distribution Derivation

In this section, we present the methods to obtain the success and failure counts, $N_{S}(s_{i})$ and $N_{F}(s_{i})$, for deriving the Beta distributions. In tabular environments with low-dimensional, discrete, and finite state spaces, tracking these counts can be straightforwardly accomplished using two tables. However, most real-world environments involve high-dimensional, continuous, and infinite state spaces, making it impractical to maintain exact counts for every state.

To address this challenge, we use Kernel Density Estimation (KDE) to approximate the densities of successes and failures from accumulated experience. Specifically, we maintain two buffers, $\mathcal{D}_{S}$ and $\mathcal{D}_{F}$, to store the states in successful and failed trajectories, respectively. By treating these states as scattered data instances distributed across the state space, KDE estimates the density as:

$$ $\tilde{d}_{X}(s_{i})=\frac{1}{|\mathcal{D}_{X}|}\sum_{j=1}^{|\mathcal{D}_{X}|} {K(s_{i}-s_{j})},\quad X\in\{S,F\},$ (6) $$

where $K(\cdot)$ is the kernel function and $|\mathcal{D}_{X}|$ is the buffer size. We select Gaussian kernel in our implementation. The estimated density $\tilde{d}_{X}(s_{i})$ approximates the likelihood of encountering state $s_{i}$ in success or failure scenarios, providing a statistically sound basis for estimating $N_{X}(s_{i})$. By multiplying $\tilde{d}_{X}(s_{i})$ by the total number of observed states $N$, the count $\tilde{N}_{X}(s_{i})$ is estimated as:

$$ $\tilde{N}_{X}(\bm{s}_{i})=N\times\tilde{d}_{X}(\bm{s}_{i})=\frac{N}{|\mathcal{ D}_{X}|}\sum_{j=1}^{|\mathcal{D}_{X}|}{\exp\left(-\frac{||\bm{s}_{i}-\bm{s}_{j }||^{2}}{2h^{2}}\right)},\quad X\in\{S,F\},$ (7) $$

where $h$ is a hyperparameter, the bandwidth of the Gaussian kernel.

We further integrate Random Fourier Features (RFF) (Rahimi and Recht,, ) to reduce computational complexity, as calculating the Gaussian kernel can be expensive, especially in scenarios involving high-dimensional state spaces and large buffers. RFF approximates the kernel function of the original $k$-dimensional states through an inner product of $M$-dimensional randomized features:

$$ $K(\bm{s}_{i},\bm{s}_{j})\approx z(\bm{s}_{i})^{T}z(\bm{s}_{j}),\quad z(\bm{s}) =\sqrt{\frac{2}{M}}\cos(\bm{W}^{T}\bm{s}+\bm{b}),$ (8) $$

where $z(\cdot)$ is the RFF mapping function with $\bm{W}=\big{[}\bm{w}^{(1)},\ldots,\bm{w}^{(M)}\big{]}\in\mathbb{R}^{k\times M}$ and $\bm{b}=\big{[}b^{(1)},\ldots,b^{(M)}\big{]}^{T}\in\mathbb{R}^{M}$ randomly sampled from the following *spectral* distributions:

$$ $\bm{w}^{(m)}\sim\mathcal{N}(\bm{0},\sigma^{-2}\bm{I}_{k}),\quad b^{(m)}\sim \text{Uniform}(0,2\pi),\quad m=1,\ldots,M,$ (9) $$

where $\bm{I}_{k}$ is the $k\times k$ identity matrix. Equation 9 is applied for the Gaussian kernel, while different kernels and the detailed derivations of the RFF method are provided in Appendix A.

#### 4.2.1 Time and Space Complexity of SASR

Suppose the buffer size of $\mathcal{D}_{X}$ is $D$ and the batch size is $B$ per iteration, the computational complexity to compute the count $N_{X}$ is $O(MDB)$, indicating linear complexity (detailed derivation in Appendix B). RFF transforms nonlinear kernel computations into linear vector operations, significantly speeding up computation by leveraging the vectorization capabilities of GPUs (Dongarra et al.,, ). This demonstrates its higher efficiency compared to methods that rely on network updates and inferences involving extensive nonlinear computations. For an empirical comparison of inference time with and without RFF, as well as related discussions, please refer to Appendix C.

Given the retention rate $\phi$, the space complexity of maintaining two buffers is $O(\phi T|s|)$, where $T$ is the total iterations and $|s|$ is the size of a single state. However, storage space can be largely saved by leveraging the existing replay buffer in off-policy backbone RL algorithms, such as SAC () and TD3 (Fujimoto et al.,, ). By augmenting the replay buffer with a flag that marks each state as either success or failure, we can efficiently manage space requirements despite some additional indexing computations introduced during processing.

#### 4.2.2 Implementation Details

Retention Rate. We introduce a hyperparameter, the retention rate $\phi\in(0,1]$, to regulate the volume and diversity of states stored in the buffers. Rather than storing all encountered states, we uniformly retain a specific portion of $\phi$. The motivation behind this are: (1) adjacent states in one trajectory tend to be highly similar, especially those near the initial state are repetitive and uninformative, retaining a portion of states can skip redundant states and increase sample diversity; (2) using a lower retention rate in the early stage keeps $N_{S}$ and $N_{F}$ lower, resulting in broader Beta distributions and preventing premature overconfidence.

Defining Success and Failure. In tasks where sparse rewards are only given at the end of an episode to indicate task completion, the entire trajectory can be classified as either a success or failure based on the episodic reward. For tasks with sparse rewards that do not explicitly indicate task completion, we segment the trajectories by positive reward occurrences. Specifically, if a reward is obtained within a pre-defined maximum steps, the corresponding sub-sequence is classified as a success; otherwise, it is considered a failure.

### 4.3 The SASR Mechanism for RL agents

Building upon the SASR reward, we employ the soft actor-critic (SAC) algorithm by  as the foundation for our RL agent. Let $Q^{\mathcal{A}_{P}}_{\psi}$ be parameterized Q-network and $\pi^{\mathcal{A}_{P}}_{\theta}$ be parameterized policy network. The Q-network can be optimized by the following loss function:

$$ $\mathcal{L}(\psi)=\Big{(}Q_{\psi}(s_{t},a_{t})-\big{(}r^{E}_{t}+\lambda R^{S}( s_{t})+\gamma Q_{{\psi}^{\prime}}(s_{t+1},a_{t+1})\big{)}\Big{)}^{2},$ (10) $$

where $Q_{{\psi}^{\prime}}$ is obtained from a secondary frozen target network to maintain a fixed objective (Mnih et al.,, ). It is worth noting that the environmental reward $r^{E}_{t}$ is retrieved from the replay buffer. Conversely, the shaped reward $R^{S}(s_{t})$ is computed in real-time using the most recently updated $N_{S}(s_{t})$ and $N_{F}(s_{t})$, thereby capturing the latest advancements in learning progress.

We optimize the policy network by maximizing the expected Q-value and the entropy of the policy $\mathcal{H}\big{(}\pi^{\mathcal{A}_{P}}(\cdot|s_{t})\big{)}$, following :

$$ $\mathcal{L}(\theta)=\mathbb{E}_{a_{t}\sim\pi_{\theta}(\cdot|s_{t})}\big{[}-Q_{ \psi}(s_{t},a_{t})+\log{\pi_{\theta}(a_{t}|s_{t})}\big{]}.$ (11) $$

Figure: Algorithm 1 Self-Adaptive Success Rate based Reward Shaping

The flow of the SAC-embedded SASR algorithm is summarized in Algorithm 1. We maintain two buffers to store successful and failed states and estimate the success and failure counts from them. Subsequently, shaped rewards are computed by sampling from Beta distributions followed by a scale transformation. The shaped rewards, combined with environmental rewards, are used to update the agent’s Q-function and policy.

## 5 Experiments

We evaluate SASR in continuous control environments, following the guidelines established by , including seven MuJoCo tasks (Todorov et al.,, ), two robotic tasks (de Lazcano et al.,, ), and one physical simulation task (Towers et al.,, ), as shown in Figure 2. All tasks provide extremely sparse rewards, with a reward of $1$ granted only upon reaching the final objective within the maximum permitted steps. To ensure robust validation, we run $10$ instances for each setting using different random seeds and report the average results. We also maintain consistent hyperparameters and network architectures across all experiments, as detailed in Appendix E.

Figure: AntStand
Refer to caption: x2.png

### 5.1 Comparison and Discussion

Baselines. We compare SASR with eight baselines to benchmark its performance: (a) RL with an Assistant Reward Agent (ReLara) (), (b) RL Optimizing Shaping Algorithm (ROSA) (Mguni et al.,, ), (c) Exploration-Guided RS (ExploRS) (Devidze et al.,, ), (d) Count-based static hashing exploration (#Explo) (Tang et al.,, ), (e) Random Network Distillation (RND) (Burda et al.,, ), (f) Soft Actor-Critic (SAC) (), (g) Twin Delayed DDPG (TD3) (Fujimoto et al.,, ), and (h) Proximal Policy Optimization (PPO) (Schulman et al.,, ). Algorithms (a) to (e) are all reward shaping methods, involving either exploration bonuses or auxiliary agents to shape rewards, while algorithms (f) to (h) are advanced RL algorithms.

Figure 3 and Table 1 report the average episodic returns and standard errors throughout training. Our findings indicate that SASR surpasses the baselines in terms of sample efficiency, learning stability, and convergence speed. The primary challenge in these environments is the extremely sparse reward given after a long horizon, making exploration essential for timely obtaining successful trajectories. Although the exploration strategies of algorithms such as ExploRS, #Explo, and RND are designed to reward novel states, effectively expanding the early exploration space with the direct additional target, they continue focusing on discovering novel states, overlooking the implicit values of these states, which makes them fail to return to the final objectives.

Figure: Figure 3: The learning performance of SASR compared with the baselines.
Refer to caption: x12.png

**Table 1: The average episodic returns and standard errors of SASR and the baselines.**
| Algorithms | AntStand | AntSpeed | AntFar | AntVeryFar | WalkerKeep | HumanStand | HumanKeep | RobotReach | RobotPush | MountainCar |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| SASR | 39.12$\pm$2.86 | 0.94$\pm$0.07 | 73.92$\pm$4.97 | 78.64$\pm$3.92 | 158.24$\pm$5.59 | 42.63$\pm$2.17 | 180.98$\pm$4.40 | 81.29$\pm$6.52 | 137.06$\pm$12.66 | 0.91$\pm$0.04 |
| ReLara | 28.66$\pm$1.82 | 0.33$\pm$0.02 | 67.77$\pm$4.30 | 64.07$\pm$4.17 | 77.14$\pm$8.77 | 29.72$\pm$1.85 | 160.31$\pm$7.30 | 103.56$\pm$7.18 | 58.71$\pm$6.98 | 0.89$\pm$0.01 |
| ROSA | 3.80$\pm$0.03 | 0.02$\pm$0.00 | 4.71$\pm$0.28 | 0.64$\pm$0.07 | 32.14$\pm$1.19 | 8.55$\pm$0.03 | 152.38$\pm$4.98 | 0.27$\pm$0.03 | 0.00$\pm$0.00 | -0.90$\pm$0.02 |
| ExploRS | 4.52$\pm$0.04 | 0.01$\pm$0.00 | 5.42$\pm$0.22 | 1.67$\pm$0.10 | 2.47$\pm$0.13 | 8.63$\pm$0.03 | 158.09$\pm$4.42 | 0.79$\pm$0.04 | 0.20$\pm$0.08 | -0.99$\pm$0.02 |
| #Explo | 6.79$\pm$0.50 | 0.00$\pm$0.00 | 12.40$\pm$1.66 | 0.55$\pm$0.09 | 131.56$\pm$5.40 | 28.73$\pm$1.79 | 160.60$\pm$7.04 | 4.19$\pm$0.42 | 6.31$\pm$0.85 | 0.79$\pm$0.02 |
| RND | 4.23$\pm$0.03 | 0.02$\pm$0.00 | 6.66$\pm$0.25 | 1.00$\pm$0.09 | 44.78$\pm$1.39 | 8.67$\pm$0.03 | 159.79$\pm$4.27 | 28.18$\pm$2.53 | 0.04$\pm$0.04 | 0.94$\pm$0.00 |
| SAC | 15.93$\pm$0.69 | 0.00$\pm$0.00 | 9.64$\pm$0.57 | 20.73$\pm$2.87 | 70.96$\pm$8.10 | 9.31$\pm$0.05 | 4.59$\pm$0.84 | 45.03$\pm$4.92 | 0.55$\pm$0.21 | -0.05$\pm$0.02 |
| TD3 | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.81$\pm$0.02 | 0.81$\pm$0.02 | 18.62$\pm$0.75 | 5.72$\pm$0.04 | 0.55$\pm$0.03 | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00 |
| PPO | 4.54$\pm$0.04 | 0.00$\pm$0.00 | 6.33$\pm$0.24 | 1.80$\pm$0.11 | 33.77$\pm$1.11 | 8.36$\pm$0.03 | 138.13$\pm$12.64 | 79.52$\pm$10.80 | 0.00$\pm$0.00 | 0.93$\pm$0.00 |

SASR outperforms the baselines primarily due to its self-adaptive reward evolution mechanism. In the early phases, SASR encourages exploration by injecting substantial random rewards to optimize the agent in multiple directions, thereby increasing the likelihood of collecting positive samples. Unlike novelty-driven exploration strategies that reward only novel states, SASR relaxes this assumption by rewarding random states, under the belief that all states are worth exploring, and this approach has proven empirically effective. Additionally, SASR leverages the success rate as auxiliary information to assess each state’s contribution to task completion, aligning with the agent’s primary objectives. As more data is collected, the success rate becomes more accurate, and the shaped reward provides more valuable guidance, significantly enhancing the exploitation and stabilizing the convergence toward optimal policies. Cooperatively, these strategies improve SASR’s sample efficiency and convergence stability in challenging tasks.

While ReLara used a similar exploration mechanism to SASR by perturbing reward functions, it relies on an independent black-box agent, requiring more iterations to converge. In contrast, SASR’s success rate sampling is more direct, reducing the delay in converging to valuable information. ReLara’s advantage lies in incorporating the policy agent’s actions into reward construction, as seen in the RobotReach task, where the target point is randomly selected in each episode. In this case, ReLara outperforms SASR due to access to action information. This can also be achieved in SASR by treating actions as additional features in the state vector.

### 5.2 Effect of Self-Adaptive Success Rate Sampling

SASR introduces a novel self-adaptive mechanism that balances exploration and exploitation by maintaining the randomness of the shaped rewards. To further explore the effect of this mechanism, we use the AntStand task as a case study, analyzing the shaped rewards learned at different stages of training. Figure 4 (bottom) shows the learning curve, while Figure 4 (top) illustrates the distributions of generated rewards over the “height of the ant" feature, one dimension in the state vector.

Figure: Figure 4: Distributions of the shaped rewards over the height of the ant robot in the AntStand task at different training stages. Red diamonds represent the estimated success rate, while the blue polylines show the actual shaped rewards sampled from the Beta distribution.
Refer to caption: x13.png

Figure: Figure 5: The density of visited states in the MountainCar task for four training periods.
Refer to caption: x14.png

As learning progresses, the shaped rewards demonstrate two key attributes: the values transition from random to meaningful, and the variance decreases from uncertain to deterministic. Besides, although the sampled rewards fluctuate, their center gradually shows a positive linear correlation with the robot’s height. In early phases, the shaped rewards contain significant randomness due to higher uncertainty. Although these random signals offer limited information, they drive the agent to take tiny optimization steps in diverse directions, effectively shifting the anchors of the policies, thus broadens the actions sampled from SAC’s stochastic policy, encouraging exploration and increasing the diversity of collected samples. In later phases, the rewards converge to closely match the height of the robot, a meaningful and intuition-aligned metric, which enhances the agent’s exploitation.

To further investigate the exploration behavior of SASR, we compare the density of the visited states throughout the training in the MountainCar task with four representative exploration strategies: (1) ReLara, perturbating on both rewards and actions; (2) #Explo, rewarding novel states; (3) SAC, entropy-regularized exploration; and (4) NoisyNet (Fortunato et al.,, ), perturbing network weights. The density for every 25k steps is shown in Figure 5. We observe that SASR progressively covers a wider range of the state space. From 50k to 100k steps, SASR reaches positions near the goal, driven by the success rate mechanism. In contrast, ReLara covers a similar range to SASR, but is less smooth and takes longer to reach the right side. #Explo shows no clear rightward shift, as it focuses on rewarding novelty without considering the inherent value of states. SAC’s exploration is relatively narrow, making it easier to trap in local optima. NoisyNet shows a narrowing range as network weight perturbations diminish through optimization. Overall, SASR demonstrates more effective exploration and collects valuable samples sooner, leading to faster convergence.

### 5.3 Ablation Study

We conduct ablation studies to investigate key components of SASR. We select six representative tasks to report the experimental results, and the quantitative data is provided in Appendix D.

Figure: (a) The impact of omitting Beta distribution sampling on the performance of SASR.
Refer to caption: x15.png

Sampling from Beta distributions. (Figure 6(a)) We examine a variant of SASR that omits Beta distribution sampling, instead directly using the success rate $N_{S}(s_{i})/(N_{S}(s_{i})+N_{F}(s_{i}))$. In the early stages, limited experience makes this success rate an unreliable estimate, and using this fixed, overly confident value can mislead the agent. Furthermore, skipping Beta distribution sampling removes the exploration driven by random rewards, leading to narrower exploration. The results highlight the critical role of Beta distribution sampling for effective learning.

Retention rate $\phi$. (Figure 6(b)) The retention rate controls the estimation of counts, which affects the confidence of Beta distributions. A high retention rate ($\phi=1$) preserves all samples, resulting in a densely populated and redundant state pool, causing the Beta distribution to be prematurely overconfident, which degrades performance. Conversely, a low retention rate ($\phi=0.01$) slows convergence by requiring more iterations to gather sufficient samples. The results suggest that an appropriate retention rate is important.

Bandwidth $h$ of Gaussian kernel. (Figure 6(c)) The bandwidth $h$ controls the smoothness of the kernel functions. Beyond fixed bandwidths, we also test a linearly decreasing configuration ($h:0.5\rightarrow 0.1$), which reflects increasing confidence in KDE. Results indicate that a small bandwidth ($h=0.01$) increases the distance between samples, causing many to have zero estimated density, while a large bandwidth ($h=1$) makes samples indistinguishable due to an overly flat kernel function. Both cases result in suboptimal performance. The decreasing bandwidth setting offers no significant improvement and tends to reduce stability due to inconsistent density estimations.

RFF feature dimensions $M$. (Figure 6(d)) SASR shows relatively low sensitivity to $M$, provided it is large enough to capture the states’ complexity. Results show that values like $M=500,1000,2000$ all yield similar performance levels, while significantly low dimensions, such as $M=50$, degrade performance. This is also suggested in the original RFF study (Rahimi and Recht,, ).

Shaped reward weight factor $\lambda$. (Figure 6(e)) Regarding the shaped reward weight factor $\lambda$, we observe that SASR performs better with intermediate values like $\lambda=0.4,0.6,0.8$. At $\lambda=0.2$, the minimal shaped reward scale reduces state differentiation, leading to suboptimal performance. At $\lambda=1$, aligning the shaped reward scale with the environmental reward introduces excessive uncertainty and randomness, which may overwhelm the feedback and hinder learning. The findings highlight that maintaining a balanced reward scale is important for optimal learning outcomes.

## 6 Conclusion and Discussion

In this paper, we propose SASR, a self-adaptive reward shaping algorithm based on success rates, to address the sparse-reward challenge. SASR achieves an exploration and exploitation balance mechanism by generating shaped rewards from evolving Beta distributions. Experiments demonstrate that this adaptability significantly enhances the agent’s convergence speed. Additionally, the implementation of KDE and RFF formulates a highly efficient, non-parametric, and learning-free approach to deriving Beta distributions. This mechanism also provides a sound alternative to traditional count-based RS strategies, adapting effectively to continuous environments. Our evaluations confirm the superior performance of SASR in terms of sample efficiency and learning stability.

While SASR is designed for sparse-reward environments, in settings with dense rewards, the introduction and maintenance of additional shaped rewards could be unnecessary. Exploring the extension of SASR to dense reward scenarios presents a promising direction for further research. Moreover, the derivation of Beta distributions depends heavily on the samples stored in the success and failure buffers. Currently, our method does not account for the relationships or varying importance of different states within the same trajectory, making the algorithm sensitive to the retention rate $\phi$. Therefore, developing an adaptive retention rate or better mechanisms for managing the buffers are crucial avenues for future improvement.

## 7 Acknowledgement

## Appendix A Derivation of Random Fourier Features

We incorporate Random Fourier Features (RFF) (Rahimi and Recht,, ) to approximate the kernel functions in the KDE process for the SASR algorithm. Let the original state be $k$-dimensional, denoted as $\bm{s}\in\mathbb{R}^{k}$, and the kernel function be $k(\bm{s}_{i},\bm{s}_{j})$. RFF approximates the kernel function by projecting the input $k$-dimensional space into a $M$-dimensional feature space using a mapping function $z:\mathbb{R}^{k}\rightarrow\mathbb{R}^{M}$. The RFF-based kernel function is then defined as follows:

$$ $k(\bm{s}_{i},\bm{s}_{j})\approx z(\bm{s}_{i})^{T}z(\bm{s}_{j}),$ (12) $$

We provide the derivation of the RFF approximation in this section.

First, we clarify that RFF primarily targets shift-invariant kernels, that satisfy $k(\bm{s}_{i},\bm{s}_{j})=k(\bm{s}_{i}-\bm{s}_{j})$. Common shift-invariant kernels include Gaussian kernels, Laplacian kernels, and Cauchy kernels. Given a shift-invariant kernel function $k(\Delta)$, we perform the inverse Fourier transform:

$$ $\displaystyle k(\bm{s}_{i},\bm{s}_{j})$ $\displaystyle=\int_{\mathbb{R}^{k}}p(\bm{w})e^{\mathsf{i}\bm{w}^{T}(\bm{s}_{i} -\bm{s}_{j})}d\bm{w}$ (13) $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}e^{\mathsf{i}\bm{w}^{T}(\bm{s}_{i}-\bm {s}_{j})}\big{]},$ (14) $$

where we can consider $\bm{w}\sim p(\bm{w})$ based on the Bochner’s theorem, and $p(\bm{w})$ is called the spectral distribution of kernel function. For the three types of shift-invariant kernels, the corresponding spectral distributions are listed in Table 2:

**Table 2: Some shift-invariant kernels and their associated spectral distributions.**
| Kernel | Kernel function, $\displaystyle k(\bm{s}_{i}-\bm{s}_{j})$ | Spectral density, $\displaystyle p(\bm{w})$ |
| --- | --- | --- |
| Gaussian | $\displaystyle\exp\left(-\frac{\|\bm{s}_{i}-\bm{s}_{j}\|_{2}^{2}}{h^{2}}\right)$ | $\displaystyle\frac{\sqrt{h}}{2\sqrt{\pi}}\exp\left(-\frac{h\|\bm{w}\|_{2}^{2}}<br>{4}\right)$ |
| Laplacian | $\displaystyle\exp\big{(}-\|\bm{s}_{i}-\bm{s}_{j}\|_{1}\big{)}$ | $\displaystyle\prod_{m=1}^{M}\frac{1}{\pi(1+w_{d}^{2})}$ |
| Cauchy | $\displaystyle\prod_{i=1}^{k}\frac{2}{\pi\big{(}1+(\bm{s}_{i}-\bm{s}_{j})^{2}<br>\big{)}}$ | $\displaystyle\exp\big{(}-\|\bm{w}\|_{1}\big{)}$ |

Next, we perform the Euler’s formula transformation, which retains only the cosine term since we are dealing with real-valued functions, the kernel function can be further derived as:

$$ $\displaystyle k(\bm{s}_{i},\bm{s}_{j})$ $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}e^{\mathsf{i}\bm{w}^{T}(\bm{s}_{i}-\bm {s}_{j})}\big{]}$ (15) $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}\cos(\bm{w}^{T}(\bm{s}_{i}-\bm{s}_{j}) )\big{]}$ (16) $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}\cos(\bm{w}^{T}(\bm{s}_{i}-\bm{s}_{j}) )\big{]}+\mathbb{E}_{\bm{w}}\big{[}\mathbb{E}_{b}[\cos(\bm{w}^{T}(\bm{s}_{i}+ \bm{s}_{j})+2b)]\big{]}$ (17) $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}\mathbb{E}_{b}[\cos(\bm{w}^{T}(\bm{s}_ {i}-\bm{s}_{j}))+\cos(\bm{w}^{T}(\bm{s}_{i}+\bm{s}_{j})+2b)]\big{]}$ (18) $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}\mathbb{E}_{b}[\sqrt{2}\cos(\bm{w}^{T} \bm{s}_{i}+b)\sqrt{2}\cos(\bm{w}^{T}\bm{s}_{j}+b)]\big{]},$ (19) $$

where $b\sim\text{Uniform}(0,2\pi)$. Equation 17 holds since $\mathbb{E}_{b\sim\text{Uniform}(0,2\pi)}\big{[}\cos(t+2b)\big{]}=0$ for any $t$. Equation 19 is obtained from $\cos(A-B)+\cos(A+B)=2\cos(A)\cos(B)$, where $A=\bm{w}^{T}\bm{s}_{i}+b$, $B=\bm{w}^{T}\bm{s}_{j}+b$.

We define the mapping $z_{\bm{w},b}(\bm{s})=\sqrt{2}\cos(\bm{w}^{T}\bm{s}+b)$, then the kernel function can be approximated by the inner product of two vectors and the expectation can be approximated by Monte Carlo sampling:

$$ $\displaystyle k(\bm{s}_{i},\bm{s}_{j})$ $\displaystyle=\mathbb{E}_{\bm{w}}\big{[}\mathbb{E}_{b}[z_{\bm{w},b}(\bm{s}_{i} )z_{\bm{w},b}(\bm{s}_{j})]\big{]}$ (20) $\displaystyle\approx\frac{1}{M}\sum_{m=1}^{M}z_{\bm{w}_{d},b_{d}}(\bm{s}_{i})z _{\bm{w}_{d},b_{d}}(\bm{s}_{j})$ (21) $\displaystyle=z(\bm{s}_{i})^{T}z(\bm{s}_{j}).$ (22) $$

Therefore, we have derived the mapping function $z(\bm{s})=\sqrt{2/M}\cos(\bm{W}^{T}\bm{s}+\bm{b})$, where $\bm{W}\in\mathbb{R}^{M\times k}$ and $\bm{b}\in\mathbb{R}^{M}$. The RFF-based kernel function can be approximated by the inner product of the mapped features in the $M$-dimensional space.

## Appendix B Derivation of Computation Complexity

In this section, we derive the computational complexity to retrieve the success or failure counts $N_{S}$ and $N_{F}$ for each iteration. Suppose the buffer size of $\mathcal{D}_{X}$ is $D$, the batch size of $\mathcal{B}$ is $B$, the corresponding counts are retrieved by calculating:

$$ $\tilde{N}_{X}=N\times z(\bm{\mathcal{B}})^{T}z(\bm{\mathcal{D}}_{X}),$ (23) $$

where the mapping function is defined as:

$$ $z(\bm{s})=\sqrt{\frac{2}{M}}\cos(\bm{W}^{T}\bm{s}+\bm{b}),\quad\bm{W}\in \mathbb{R}^{k\times M},\quad\bm{b}\in\mathbb{R}^{M}.$ (24) $$

For each state, the mapping function calculation involves:

- •
Matrix multiplication $\bm{W}^{T}\bm{s}$: $kM$.
- •
Addition $\bm{W}^{T}\bm{s}+\bm{b}$: $M$.
- •
Cosine calculation $\cos(\bm{W}^{T}\bm{s}+\bm{b})$: $M$.

Therefore, the computational complexity for calculating $z(\bm{s})$ for one state is $O(kM)$.

For each pair of states $(\bm{s}_{i},\bm{s}_{j})$, calculating the kernel involves $M$ multiplications and $M-1$ additions, thus, the complexity is $O(M)$.

For each iteration, we calculate the RFF mapping for all states in the buffer and the batch and then compute the kernel between them. The complexities involve three parts: RFF mapping for the buffer, RFF mapping for the batch and kernel calculation:

$$ $O(DkM)+O(BkM)+O(MDB).$ (25) $$

Since the first two terms $O(DkM)$ and $O(BkM)$ are dominated by the last term $O(MDB)$ when the buffer size and the batch size are large, the overall computational complexity to retrieve the corresponding counts can be approximated as $O(MDB)$.

## Appendix C Comparison of SASR with and without RFF

To evaluate the effect of introducing RFF, we compare the training time of SASR with and without RFF, also with the backbone SAC algorithm, the results are shown in Table 3. The tests are conducted on the NVIDIA RTX A6000 GPUT. The results show that excluding SAC’s inherent optimization time, RFF significantly saves time in the SASR algorithm, while with varying effects across tasks.

**Table 3: Comparison of training time (in hours) for SASR with and without RFF.**
| Algorithms | AntStand | AntFar | HumanStand | HumanKeep | RobotReach | RobotPush |
| --- | --- | --- | --- | --- | --- | --- |
| SAC (backbone) | 5.87 | 5.08 | 4.87 | 5.67 | 5.42 | 6.3 |
| SASR KDE+RFF | 7.15 | 7.52 | 6.92 | 6.20 | 7.07 | 8.13 |
| SASR w/o RFF | 8.12 | 8.72 | 8.37 | 6.53 | 11.12 | 9.21 |

## Appendix D Supplementary Experimental Results for Ablation Study

We provide the detailed quantitative results of the ablation study in this section.

**Table 4: Ablation study #1: The average episodic returns and standard errors of SASR and the variant without sampling from Beta distributions.**
| Tasks | SASR (with sampling) | SASR (without sampling) |
| --- | --- | --- |
| AntStand | $\bm{39.12\pm 2.86}$ | $23.25\pm 2.12$ |
| AntFar | $\bm{73.92\pm 4.97}$ | $37.86\pm 5.16$ |
| HumanStand | $\bm{42.63\pm 2.17}$ | $9.30\pm 0.083$ |
| HumanKeep | $\bm{180.98\pm 4.40}$ | $170.51\pm 10.68$ |
| RobotReach | $\bm{81.29\pm 6.52}$ | $33.76\pm 4.41$ |
| RobotPush | $\bm{137.06\pm 12.66}$ | $70.37\pm 11.97$ |

**Table 5: Ablation study #2: The average episodic returns and standard errors of SASR with different retention rates.**
| Tasks | $\phi=1$ | $\phi=0.1$ (default) | $\phi=0.01$ |
| --- | --- | --- | --- |
| AntStand | $17.98\pm 1.86$ | $\bm{39.12\pm 2.86}$ | $20.27\pm 2.08$ |
| AntFar | $19.95\pm 3.00$ | $\bm{73.92\pm 4.97}$ | $48.47\pm 5.28$ |
| HumanStand | $9.25\pm 0.08$ | $\bm{42.63\pm 2.17}$ | $19.17\pm 1.52$ |
| HumanKeep | $179.10\pm 7.06$ | $\bm{180.98\pm 4.40}$ | $180.13\pm 6.27$ |
| RobotReach | $54.07\pm 8.39$ | $\bm{81.29\pm 6.52}$ | $35.18\pm 5.95$ |
| RobotPush | $3.91\pm 1.22$ | $\bm{137.06\pm 12.66}$ | $1.88\pm 0.47$ |

**Table 6: Ablation study #3: The average episodic returns and standard errors of SASR with different bandwidths $h$ of Gaussian kernel.**
| Tasks | $h=0.01$ | $h=0.1$ | $h=0.2$ (default) | $h=1$ | $h=0.5\rightarrow 0.1$ |
| --- | --- | --- | --- | --- | --- |
| AntStand | $7.94\pm 0.28$ | $16.77\pm 1.18$ | $\bm{39.12\pm 2.86}$ | $12.76\pm 0.40$ | $19.00\pm 1.63$ |
| AntFar | $11.68\pm 0.96$ | $44.31\pm 3.34$ | $\bm{73.92\pm 4.97}$ | $27.96\pm 2.46$ | $72.71\pm 4.57$ |
| HumanStand | $9.31\pm 0.06$ | $\bm{43.64\pm 1.94}$ | $42.63\pm 2.17$ | $9.32\pm 0.06$ | $13.81\pm 0.93$ |
| HumanKeep | $178.51\pm 4.99$ | $\bm{181.44\pm 4.73}$ | $180.98\pm 4.40$ | $178.22\pm 4.97$ | $178.04\pm 5.12$ |
| RobotReach | $37.03\pm 4.19$ | $72.30\pm 5.67$ | $\bm{81.29\pm 6.52}$ | $35.87\pm 4.57$ | $49.47\pm 5.1$ |
| RobotPush | $0.40\pm 0.13$ | $8.80\pm 4.44$ | $\bm{137.06\pm 12.66}$ | $0.12\pm 0.06$ | $0.34\pm 0.13$ |

**Table 7: Ablation study #4: The average episodic returns and standard errors of SASR with different RFF feature dimensions $M$.**
| Tasks | $M=50$ | $M=500$ | $M=1000$ (default) | $M=2000$ |
| --- | --- | --- | --- | --- |
| AntStand | $3.56\pm 0.12$ | $12.08\pm 1.36$ | $39.12\pm 2.86$ | $\bm{42.52\pm 3.14}$ |
| AntFar | $27.76\pm 3.24$ | $36.31\pm 2.69$ | $\bm{73.92\pm 4.97}$ | $61.79\pm 4.63$ |
| HumanStand | $9.46\pm 0.05$ | $25.42\pm 1.83$ | $42.63\pm 2.17$ | $\bm{52.70\pm 2.13}$ |
| HumanKeep | $178.51\pm 4.84$ | $181.81\pm 4.60$ | $\bm{180.98\pm 4.40}$ | $180.58\pm 4.63$ |
| RobotReach | $65.39\pm 6.22$ | $38.25\pm 4.37$ | $\bm{81.29\pm 6.52}$ | $45.98\pm 4.90$ |
| RobotPush | $33.58\pm 4.86$ | $54.56\pm 6.66$ | $\bm{137.06\pm 12.66}$ | $45.15\pm 6.15$ |

**Table 8: Ablation study #5: The average episodic returns and standard errors of SASR with different shaped reward weight factors.**
| Tasks | $\lambda=0.2$ | $\lambda=0.4$ | $\lambda=0.6$ (default) | $\lambda=0.8$ | $\lambda=1.0$ |
| --- | --- | --- | --- | --- | --- |
| AntStand | $7.60\pm 0.73$ | $17.25\pm 1.58$ | $\bm{39.12\pm 2.86}$ | $28.43\pm 2.07$ | $2.82\pm 0.09$ |
| AntFar | $22.51\pm 2.60$ | $34.04\pm 3.87$ | $\bm{73.92\pm 4.97}$ | $67.62\pm 4.89$ | $18.05\pm 1.79$ |
| HumanStand | $9.53\pm 0.04$ | $33.95\pm 1.90$ | $\bm{42.63\pm 2.17}$ | $30.65\pm 1.65$ | $12.23\pm 0.42$ |
| HumanKeep | $\bm{182.57\pm 4.32}$ | $180.22\pm 4.60$ | $180.98\pm 4.40$ | $179.74\pm 4.53$ | $179.62\pm 4.70$ |
| RobotReach | $41.05\pm 4.17$ | $\bm{82.33\pm 6.37}$ | $81.29\pm 6.52$ | $71.30\pm 6.54$ | $15.89\pm 2.06$ |
| RobotPush | $9.18\pm 1.99$ | $118.92\pm 10.79$ | $\bm{137.06\pm 12.66}$ | $65.51\pm 12.71$ | $47.98\pm 9.64$ |

## Appendix E Network Structures and Hyperparameters

### E.1 Network Structures

Figure 7 illustrates the structures of the policy network and Q-network employed in our experiments. The agent utilizes simple multilayer perceptron (MLP) models for these networks. Given the use of stochastic policies, the policy network features separate heads to generate the means and standard deviations of the inferred normal distributions, which are then used to sample actions accordingly.

Figure: Figure 7: The structures of policy network and Q-network in our implementation.
Refer to caption: x20.png

### E.2 Hyperparameters

We have observed that SASR demonstrated high robustness and was not sensitive to hyperparameter choices. Table 9 shows the set of hyperparameters that we used in all of our experiments.

**Table 9: The hyperparameters used in the SASR algorithm.**
| Hyperparameters | Values |
| --- | --- |
| reward weight $\lambda$ (default) | 0.6 |
| kernel function bandwidth | 0.2 |
| random Fourier features dimension $M$ | 1000 |
| retention rate $\phi$ (default) | 0.1 |
| discounted factor $\gamma$ | 0.99 |
| replay buffer size $|\mathcal{D}|$ | $1\times 10^{6}$ |
| batch size | 256 |
| actor module learning rate | $3\times 10^{-4}$ |
| critic module learning rate | $1\times 10^{-3}$ |
| SAC entropy term factor $\alpha$ learning rate | $1\times 10^{-4}$ |
| policy networks update frequency (steps) | $2$ |
| target networks update frequency (steps) | $1$ |
| target networks soft update weight $\tau$ | $5\times 10^{-3}$ |
| burn-in steps | $5000$ |

## Appendix F Compute Resources

The experiments in this paper were conducted on a computing cluster, with the detailed hardware configurations listed in Table 10. The computing time for the SASR algorithm in each task (running 1,000,000 steps) was approximately $6\pm 2$ hours.

**Table 10: The compute resources used in the experiments**
| Component | Specification |
| --- | --- |
| Operating System (OS) | Ubuntu 20.04 |
| Central Processing Unit (CPU) | 2x Intel Xeon Gold 6326 |
| Random Access Memory (RAM) | 256GB |
| Graphics Processing Unit (GPU) | 1x NVIDIA A100 20GB |
| Brand | Supermicro 2022 |

## Appendix G Configurations of Tasks

We provide the detailed configurations of the tasks in the experiments in this section.

- •
AntStand: The ant robot is trained to stand over a target position. The reward is given if the ant robot reaches the target height. Maximum episode length is 1000 steps.
- •
AntSpeed: The ant robot is trained to move as fast as possible. The reward is given if the ant robot reaches a target speed. Maximum episode length is 1000 steps.
- •
AntFar: The ant robot is trained to reach a target position far from the starting point. The reward is given if the ant robot reaches the target position. Maximum episode length is 1000 steps.
- •
AntVeryFar: The ant robot is trained to reach a target position very far from the starting point. The reward is given if the ant robot reaches the target position. Maximum episode length is 1000 steps.
- •
WalkerKeep: The walker robot is trained to keep a target height. The robot is initialized by standing, and the reward is given if the robot maintains the target height. Maximum episode length is 1000 steps.
- •
HumanStand: The human robot is trained to stand over a target position. The robot is initialized by lying on the ground, and the reward is given if the robot reaches the target height. Maximum episode length is 1000 steps.
- •
HumanKeep: The human robot is trained to keep a target height. The robot is initialized by standing, and the reward is given if the robot maintains the target height. Maximum episode length is 1000 steps.
- •
RobotReach: The robot arm is trained to reach a target position. The target position is randomly generated in the workspace, and the reward is given if the robot reaches the target position. Maximum episode length is 500 steps.
- •
RobotPush: The robot arm is trained to push an object to a target position. The target position is randomly generated on the table, and the reward is given if the object reaches the target position. Maximum episode length is 500 steps.
- •
MountainCar: The car is trained to reach the top of the right hill. The reward is given if the car reaches the top. Maximum episode length is 1000 steps.

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
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?
soundness: 4
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.
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.
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"

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
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 |
```
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
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?
soundness: 2
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.
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.
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"

---

confidence: 4
contribution: 3
initial_rating: 3
presentation: 2
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.
soundness: 2
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.
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.
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).

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.

Decision: Accept (Poster)