Goal Achievement Guided Exploration: Mitigating Premature Convergence in Reinforcement Learning

Authors: Shengchao Yan, Baohe Zhang, Joschka Boedecker, Wolfram Burgard
Primary area: reinforcement learning
Keywords: reinforcement learning, exploration, deep reinforcement learning

Abstract:
Premature convergence to suboptimal policies remains a significant challenge in reinforcement learning (RL), particularly in tasks with sparse rewards or non-convex reward landscapes. Existing work usually utilizes reward shaping, such as curiosity-based internal rewards, to encourage exploring promising spaces. However, this may inadvertently introduce new local optima and impair the optimization for the actual target reward. To address this issue, we propose Goal Achievement Guided Exploration (GAGE), a novel approach that incorporates an agent's goal achievement as a dynamic criterion for balancing exploration and exploitation. GAGE adaptively adjusts the exploitation level based on the agent's current performance relative to an estimated optimal performance, thereby mitigating premature convergence. Extensive evaluations demonstrate that GAGE substantially improves learning outcomes across various challenging tasks by adapting convergence based on task success. Applicable to both continuous and discrete tasks, GAGE seamlessly integrates into existing RL frameworks, highlighting its potential as a versatile tool for enhancing exploration strategies in RL.

Decision: reject
Reviewer scores: 3, 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1730298141230

thread_type:
official_review

<thread_object>
creator: reviewer_fww4

<content>
summary:
This paper proposes an exploration approach in reinforcement learning aimed at mitigating the premature convergence issue. The proposed Goal Achievement Guided Exploration (GAGE) measures the ratio of currently achieved cumulative rewards over the expected maximum cumulative rewards as a criterion. If the agent has not reached an expected level of performance, it is encouraged to continue exploring.

strengths:
The GAGE algorithm is straightforward and easy to understand. The core idea is to set an expected "goal" and have the agent keep exploring (rather than converging) until the set goal is reached. The presentation is smooth, and the paper provides a comprehensive review of related works. The targeted issue of premature convergence is clearly stated and effectively addressed. The paper discusses both continuous and discrete action spaces and proposes appropriate solutions for each.

weaknesses:
1. The "goal achievement" is defined as the ratio of achieved cumulative rewards for the current policy over the maximum or optimal cumulative rewards. Since the optimal policy is unknown, the paper proposes setting a hyperparameter as a threshold. However, this introduces two limitations:

(1) The goal-setting determines the upper bound of learning performance, or at least, heavily influence the learning process. If the goal is set too high, the algorithm may struggle to converge as the agent will always perceive its performance as insufficient. Conversely, if the goal is set too low, the agent will reach it too easily, which may still lead to premature convergence.

(2) In this case, the expected "goal" is highly task-specific, requiring prior knowledge to define an appropriate threshold for different tasks.

2. The paper identifies four main factors contributing to premature convergence (discussed in Section 2.1). However, the five continuous control tasks used in the experiments do not seem to reflect these factors well. The motivation for selecting these tasks, and how they are capable of demonstrating the effectiveness of the GAGE algorithm in addressing premature convergence, should be more clearly explained.

3. In the experiments, the five continuous control tasks only compare GAGE with the backbone PPO algorithm. I believe comparisons with some benchmarks are necessary to fully demonstrate the advantages of GAGE.

questions:
1. In Section 4.1 (around Line 400), the experiments show that "When the target speed is set to 5m/s, which is below the learned optimal speed (~7m/s), the GAGE agent is still able to learn the optimal speed." Referring to Equations (2) and (4), if the learned policy achieves higher rewards than the expected target, the "goal achievement" $g(\pi) >1$, which means the lower bound $\sigma_L(\pi) = -\sigma_0 g(\pi) + \sigma_0 < 0$. Additionally, if the learned policy has already achieved the target goal of 5m/s, it would focus mainly on convergence and less on exploration, how is it able to continue optimizing to reach 7m/s?

2. What happens if the target goal is set too high? Will this result in the agent lacking confidence and failing to converge?

3. While GAGE is designed to avoid local optima, in Figure 3, we can observe that some GAGE variants still become trapped in local optima. For instance, in *Ant Acrobatics*, both GAGE-75 and GAGE-100; in *Humanoid Pole*, GAGE-100; and in *Humanoid Tightrope*, both GAGE-50 and GAGE-100 converge to relatively low episodic returns. Does this indicate that the local optima issue is not fully addressed?

I would like to increase the score if these concerns are addressed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691943640

thread_type:
official_review

<thread_object>
creator: reviewer_qvip

<content>
summary:
This paper proposes to use goal achievement as a learning progress measure to schedule the noise for exploration, where goal achievement is defined as the ratio of the current policy's expected return to the optimal policy's expected return. The results showed that goal achievement improves PPO's performance in robotic tasks with intensive reward shaping and hard-exploration tasks in MiniGrid.

strengths:
This method is very easy to implement and seems to improve the performance greatly. The authors claim that current methods suffer from premature convergence. Thus, they propose to tune the noise of exploration adaptively using a goal achievement rate, with the assumption that the maximum reward is known.

weaknesses:
- Lack of theoretical discussion. This is fine since I understand this paper's contribution is a practical algorithm. Still, it would be great to see why adjusting the noise level with goal achievement leads to improvement.
- Writing is a bit verbose. Section 2 is mostly about previous works. The proposed method doesn't come until page 4, which is too long in my opinion.

questions:
- Figure 3's legends are too small to read.
- Where are the differences between GAGE-50 and GAGE-100?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704908129

thread_type:
official_review

<thread_object>
creator: reviewer_dij6

<content>
summary:
This paper presents Goal Achievement Guided Exploration (GAGE), an algorithm to prevent premature convergence and encourage exploration in deep RL. The paper describes the major causes of premature convergence in RL and describes an algorithm to address specific types of issues, which is then evaluated in several different task domains.

strengths:
This paper is well written, and does an excellent job of contextualizing and motivating work on premature convergence, and intuitively develops and explains the GAGE algorithm, which is simple yet not trivial. This issue is an important one that is common in practice, but has received little attention from prior work, and thus a worthwhile topic of study. The GAGE algorithm requires several well-stated priors to work, most notably a human estimate of what the maximum achievable reward is for each reward term, but in my option this is a reasonable prior for many RL domains and not overly restrictive. The experimental validation of the algorithm is reasonably thorough.

weaknesses:
I didn't have any major issues with this paper, though there's a few issues I've noted in the questions section which could be improved. 

The biggest concern I have is that the benefits of doing any form of action smoothing to prevent premature convergence versus the specific algorithm of GAGE are not clear- it could be the case that a simpler baseline would be just as good (though I suspect this is not the case). However, this paper does not claim to be definitive regarding premature convergence prevention or action smoothing algorithms (and it doesn't need to be to provide a meaningful contribution), so I don't find this to be a critical flaw.

While not the final word on the problem (if such a thing is even possible), this work seems like a worthwhile step forward, with real implications for deep RL in practical and scientific use. I could see GAGE or a similar algorithm plugging in nicely as a standard tool to improve performance and stability alongside other methods. As such, I am inclined to recommend acceptance- this is good work.

questions:
Some minor issues and questions:

-What do the upper and lower brackets in equation 7 denote? I don't see this explained in the text and it is unusual notation in my experience of the field.

-The temperature computation for smoothing action probabilities is somewhat complex compared to simpler alternatives mentioned (e.g. mixing with uniform). I don't see any ablations testing whether this more sophisticated smoothing is better than the naive baseline, however, which be useful to see.

-The lines in figure 3 are a bit too small to comfortably read, please make them bigger (plot size is fine, the lines are too narrow).

-The captioning and plot spacing in figure 4 is a little confusing, the right two plots should be closer together to show that they are a pair, unlike the left plot.

-Section 4.2's writing takes a sudden nosedive- there's a number of instances of odd phrasing and wrong grammar here in what is otherwise an excellently written paper. This could use a pass to revise.

-For figure 5, what is the baseline performance for each method on the non-game-containing version of this task? I assume all algorithms can learn the task successfully? It would be good to make this clear if it is so as it strengthens the point being made.

-I would have liked to see more aggressive stress tests on the reward upper bound estimate where performance is lost as a result of a bad estimate. What happens if V_star in figure 4a is set to 1? What if it is set to 99? I imagine these won't perform well, but it would be useful to know what happens when things break down since sometimes human estimates of the maximum possible reward will be quite wrong.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730726403628

thread_type:
official_review

<thread_object>
creator: reviewer_dggt

<content>
summary:
The paper proposes an approach called Goal Achievement Guided Exploration (GAGE) to address premature convergence in reinforcement learning algorithms. Instead of using intrinsic rewards for exploration, the proposed approach maintains an estimate for the optimal performance level, comparing this level to the current performance for controlling between exploration and exploitation.

The main claim of the paper is that the proposed approach enhances exploration in reinforcement learning.

strengths:
The proposed approach aims to balance between exploration and exploitation in reinforcement learning. The approach is interesting in that it assumes that each reward term is equally important and exploration magnitude is kept as high as how far each reward term is from an assumed optimal solution.

In more detail, the approach uses a goal achievement term that is the minimum of goal achievement terms of each reward part. Each of these individual goal achievement terms is computed using Monte Carlo estimates of recent samples divided by a heuristic estimate of the optimal value, or, total maximum reward. An implicit assumption is that an agent should be able to succeed in all parts of the reward function sum.

Discussion of the "Game Console" problem in exploration is valuable.

weaknesses:
The approach is based on assuming explicit knowledge of the reward function and  the individual parts (terms) that as a sum define the reward function. This needs to be discussed and motivated in detail. Most of the exploration approaches in reinforcement learning do not need explicit knowledge of the reward function.

The approach makes strong assumptions about the task. I assume the approach only works if these assumptions are satisfied and can easily lead to slow convergence. The approach controls exploration according to the reward term that is furthest away from being satisfied. This means, for example, that if there is a single reward term that is very hard to get close to optimal, large amounts of exploration is used although the total reward would be already high. Moreover, the approach can lead to excessive exploration noise that may hinder improving reward terms which require small amount of noise.

Evidence for the main claim of the paper that the proposed approach enhances exploration is needed. That the algorithmic design and computations used in the approach improve on state-of-the-art need significantly stronger theoretical or/and empirical evidence.

Fig. 2 and the main text aim to motivate the proposed approach by saying that exploration methods typically somehow change the order of probabilities. This is not true. For example, target entropy [Haarnoja et al., 2018] is commonly used and does not change the order of the action probabilities.

The action smoothing procedure in Section 3.2 for discrete actions includes several computations for which there is some discussion of the motivation but no theoretical or empirical evidence. There should be a much more convincing discussion on why each of the steps 1. to 4. in Section 3.2 is used to compute the adaptive temperature of the softmax distribution.


Experiments:

Methods:
One of the main motivations for the proposed approach in the paper is that intrinsic motivation based approaches may converge to local optima. However, there are methods designed specifically to address this problem. For example, [Chen et al., 2022], explicitly optimizes the original optimization objective while taking advantage of intrinsic motivation. These kind of methods need to be added as baselines.

Typical exploration methods need to be added as baselines. This includes pre-defined entropy schedules: linearly descreasing entropy, constant entropy, constant + linearly decreasing etc.

Benchmarks:
In the continuous action setting, the proposed new benchmarks are valuable. However, to provide readers sufficient information also well known benchmarks should be used where existing baseline results are available. Examples of continuous action benchmarks which require exploration such as AntMaze etc. can be found for example in the hierarchical reinforcement learning literature (see [Nachum et al., 2018] and follow the citations to the newest work with the largest environments).

The "Game Console" problem in exploration is valuable and interesting but what is the relationship of the proposed approach compared to other methods that do not use intrinsic rewards? In "Game Console" type of problems, mostly intrinsic rewards cause problems?


Details:

Please explain "More severely, for discrete actions, the entropy loss can not maintain the distribution shape, i.e., the order of actions’ probabilities of the learned policy." in more detail.

Regarding control of policy variance in Equation 4, it seems that identical variances for all action dimensions is assumed?

In Fig. 2, please define what entropy maximization means. For a discrete distribution, maximum entropy results in a uniform distribution which differs from Fig. 2b.

The presentation is overall OK but there are typos such as  "probablities" that should be fixed.


Chen, E., Hong, Z. W., Pajarinen, J., & Agrawal, P. (2022). Redeeming intrinsic rewards via constrained optimization. Advances in Neural Information Processing Systems, 35, 4996-5008.

Nachum, O., Gu, S. S., Lee, H., & Levine, S. (2018). Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31.

Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P. and Levine, S., 2018. Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05905.

questions:
I recommend rejecting the paper. The authors can improve the paper by improving the motivation for the approach, discussing in more detail in which situations the approach works and does not work, providing proper experimental baselines and benchmarks.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732145290075

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response to Reviewer Feedback and Paper Changelog

comment:
We thank the reviewers for their thoughtful feedback. We hope that our response below addresses all concerns raised, and we are excited about the improvements to our paper based on the great and helpful comments.

Here, we list major changes (marked in red in the pdf, the colors will be removed in the camera-ready version) we made according to the feedback:
1. We added an explanation of GAGE in terms of exploration. We want to clarify two concerns raised:
    - GAGE can also work without prior knowledge of the reward function. To demonstrate that, we added experiments on Humanoid locomotion task using standard PPO's episode return as the goal, and our results show that by simply using the reward sum instead of individual goal rewards, GAGE can already improve performance.
    - GAGE does not replace the intrinsic reward for tasks with sparse reward. Instead, it serves as a supplement to help the intrinsic reward techniques better explore the tasks, avoiding Noisy TV or even Game Console problems.
2. We added Label smoothing together with DEIR as a new baseline method in Minigrid experiments.
3. We added a stress test of different target speeds for the Humanoid task to show the robustness of our method.
4. We added extra experiments on the task Dog Balance Beam with different entropy schedules as baselines, as proposed by one reviewer.
5. We added a baseline with RND in all continuous tasks and conducted a hyperparameter tuning for RND on the Dog Balance Beam task.
6. We improved writing quality by revising Section 4.2 and fixing typos.
7. We increased the line width and legend font size in Figure 3 and reduced the spacing between plots in Figure 4(c).
8. To improve clarity, we renamed the variations of our methods from GAGE-50, GAGE-75, and GAGE-100 to GAGE-0.5, GAGE-0.75, and GAGE-1.0. We added an explanation of their differences to Section 4.1.
9. We corrected the results from GAGE-100 in the Humanoid Dribbling task. We are sorry about this, but it does not affect our experiment results.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces an adaptive temperature mechanism based on the agent’s performance relative to maximum performance. The stated goal of the mechanism is to avoid local optimum during optimization. Experiments are conducted to highlight that the agent does find some better optimum. Unfortunately, the paper is a bit too unrefined, particularly in sections 3 and 4, which leads to a lack of clarity on the method, its limitations, and questionable experiment results. The paper is also missing a citation for an extremely similar method proposed by Gullapalli (1992). See the comments below for more details.


The background section for this paper is long, and it does not seem to build up to properly frame the contribution. The primary content of the paper starts halfway down page 4. It could be beneficial to get to this point faster. 

Figure 2: it is difficult to understand what this figure is contributing without providing the equations that would produce these plots. 

What impact does the forced lower bound have of optimization? This feature is introduced, but it is never demonstrated how this impacts the algorithm or that it is necessary. 

For the experiments in Figure 3, plotting the median return with 25%-75% quantiles is not a clear choice. This work aims to prevent the agent from getting trapped in a local optimum. These plots could only indicate if the agent didn’t get stuck in local optima 75% of the time. There will also be significant uncertainty with where these quantiles are with only 10 seeds. 

There is no accounting for hyperparameter tuning in comparing the success of each method. It has been shown that large step sizes (Jordan et al. 2024) lead policy gradient methods to getting trapped in plateaus. Without considering the impact of the step size from these experiments, it is impossible to understand if the method worked as intended or if there is some other confounding factor. Plus, with further hyperparameter tuning, PPO could get to the same performance level without this trick. If the only gauge of success of this method is getting good performance with a specific hyperparameter setting, how do we know it is doing anything of value? 


Where is the evidence that the tasks in Figure 3 are hard exploration problems? These may be challenging optimization problems, but whether they are hard exploration problems is unclear. In fact, I see no reason why this method of exploration could solve hard exploration problems efficiently. The primary exploration mechanism is random sampling, which is widely known to not solve hard exploration problems efficiently. Furthermore, it could be the case that having high entropy action distributions could make the agent get stuck in a local optimum that prefers having lots of noise. The experiments all try to show that the method is universally applicable, but this is not going to be the case. Every method has a limitation, and it should be made clear. The method and claims of this paper need to be adjusted to scope and clarify the applicability of this method correctly. 

The experiment of robustness to reward shaping is very interesting! However, it is unclear why this method would have any impact on this robust. Since it is included in the main paper, I would expect further investigation. Revealing this connection could produce further insights on the method and how it impacts policy optimization. 

I think the method is interesting and could be very useful for the community to understand its value. However, I do not think this is accomplished in the paper’s current form. 


Gullapalli, Vijaykumar. "A stochastic reinforcement learning algorithm for learning real-valued functions." Neural networks 3.6 (1990): 671-692.

Scott M Jordan, Samuel Neumann, James E Kostas, Adam White, and Philip S Thomas. "The Cliff of Overcommitment with Policy Gradient Step Sizes." Reinforcement Learning Journal, vol. 2, 2024, pp. 864–883.