Breadth First Exploration in Grid-based Reinforcement Learning

Dear Reviewer SMnh

We would like to express our sincere gratitude for your valuable comments and insightful feedback. Your comment has greatly enriched our work and provided us with valuable perspectives. We address your comments one by one in what follows.

Q1 [Weakness1 & Question1] The description of the algorithm itself needs to be stated more clearly. How exactly do you collect the training data? Do you always choose the shortest path (according to the current state of the graph)? When do you switch subgoals? Do you have to replan at some point? It could be handled by either adding a small section that brings all the pieces in one place and describes the algorithm step-by-step or by adding a pseudocode. Without that, it is hard to understand your approach.

A1 We appreciate your meticulous reviews on the description of the proposed method, BEAG. Based on your questions and comments, we have substantial revised the draft (particularly, Appendix A) and added a comprehensive pseudocode of our algorithm, as you suggested. We individually respond to each question for clarification in the following:

  Q1-1. How exactly do you collect the training data?

  A1-1. Initially, we collect the training data from the random rollout phase where the agent proceeds with actions entirely at random. After the random rollout phase, we collect the training data using the policy network with BEAG.

  Q1-2. Do you always choose the shortest path (according to the current state of the graph)?

  A1-2. Yes, we always use the shortest path.

  Q1-3. When do you switch subgoals?

  A1-3. We switch subgoals when we reach the subgoal. More precisely, when a subgoal falls within $\delta$. (i.e., $\lVert \phi(s’)-g \rVert < \delta$ )

  Q1-4. Do you have to replan at some point?

  A1-4. We re-plan the path when we fail to achieve the subgoal in the failure condition threshold (100) step.

Q2. [Weakness2] Since your edges have different lengths, I suppose that you use Dijkstra to find the shortest path, instead of BFS as you claim.

A2. It appears there might be a misunderstanding. What we mean by breadth-first “exploration” is not aligned with the breadth-first search algorithm to compute the shortest path. It means that BEAG prefers broadly exploring bypasses for the currently unattainable subgoals than meticulously ransacking the local of them. We will further clarify the meaning of the breadth-first exploration in the revision. We thank the reviewer for pointing out the potential confusion of our expression.

Q3. [Weakness3] I agree that you show a clear advantage over DHRL, although the final difference is not very large. I suggest evaluating the algorithm on even harder instances to further highlight your superiority. Perhaps instances with a lot of blockers would do since you claim dealing with it to be one of your key strengths. How far can you push it, even in a toy environment?

A3. As requested, we have added an additional experiment and discussion, showcasing a clear advantage of BEAG over DHRL (See Figure 5 in Section 5.3). Specifically, we compare BEAG and DHRL in a U-maze environment, where the initial state and goal are fixed at the bottom-left and top-left corners, respectively. This environment is dedicated to evaluating the efficiency of exploration in various algorithms. BEAG reached the goal much faster than DHRL, thanks to the breadth-first exploration. The relatively small gap between BEAG and DHRL in the random goal setting may suggest that DHRL (and others) heavily relies on random goal generation for subgoal exploration. We hope the additional experiment and discussion address your question.

Q4. [Weakness4] The Ablation study section seems a little ad-hoc. I suggest extending it or merging it with other experiments.

A4. We appreciate your valuable suggestions on additional experiments. As suggested, in Figure 7, we conducted ablation studies on BEAG with different values of ($\tau_t$: [50, 100, 150, 200]) and ($\tau_n$: [1, 3, 5]). As expected, both $\tau_t$ and $\tau_n$ (determining the thresholds to avoid subgoals) need to be set at minimal values to reduce attempts at impossible subgoals. However, exceedingly small values for $\tau_t$ and $\tau_n$ may accidentally identify attainable subgoals as impossible ones and possibly degenerate performances in early phases, as depicted in Figure 7 (d) and (e). This observation provides a useful guideline for the hyperparameter choice of our method. We hope that these additional experiments address the reviewer's concern.

Q5. [Question 2] Do you ever remove edges from the graph, or is it simply enough to assign them $\infty$ weight?

A5. For ease of implementation and presentation, we simply indicate the removed edge with infinite weight.

Thank you for the answer. I acknowledge the clarifications by increasing my rating.

Dear Reviewer z2kz

We would like to express our sincere gratitude for your valuable comments and insightful feedback. Your comment has greatly enriched our work and provided us with valuable perspectives. We address your comments one by one in what follows.

Q1 [Weakness 1] Experiments are not enough. The authors only compared their work with DHRL, while there exists many other graph-based HRL methods that are worth to compare with, such as HIRO, HAC, … . [Question 1] Could the authors try some other baseline HRL benchmarks to further show the advantage of the proposed method?

A1. As requested, we have expanded our evaluation by incorporating additional baselines, namely PIG [1], HIGL [2], and HIRO [3], alongside DHRL [4]. BEAG outperforms all the baselines, not only graph-based RL approaches (DHRL, PIG, HIGL) but also the other hierarchical RL one (HIRO) while DHRL is the most competitive. We note that our evaluation fairly supports the superiority of BEAG since our choice of benchmarks is standard and comprehensive, aligning with those used by other works to justify their proposals. The observed superiority of BEAG stems from its unique ability to systematically identify and avoid impossible subgoals on the adaptive grid, a factor overlooked by other baselines. For a detailed comparison, please refer to Figure 4 and Section 5.2 in the revised draft, where we present a more comprehensive analysis of the results. We are confident that this expanded comparison offers a clearer understanding of BEAG's strengths, as well as addresses your concerns.

[1] Junsu Kim, Younggyo Seo, Sungsoo Ahn, Kyunghwan Son, and Jinwoo Shin. Imitating graph-based planning with goal-conditioned policies. ICLR 2023.

[2] Junsu Kim, Younggyo Seo, and Jinwoo Shin. Landmark-guided subgoal generation in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 34:28336–28349, 2021.

[3] ​​Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.

[4] Seungjae Lee, Jigang Kim, Inkyu Jang, and H Jin Kim. Dhrl: A graph-based approach for long- horizon and sparse hierarchical reinforcement learning.Advances in Neural Information Process- ing Systems, 35:13668–13678, 2022.

Q2. [Weakness2] The method is a minor upgrade of existing Graph-based methods. Although pure empirical evidence can show the effectiveness of the method, I am expecting to see some more theoretical analysis on why it may work.

A2. Thank you for the constructive comments. One of our contributions is to address the importance of avoiding consecutive attempts at impossible subgoals, which the literature of graph-based RL (including the most competitive baseline, DHRL) have been overlooked. In addition, we report an additional experiment and discussion, demonstrating a clear advantage of BEAG over DHRL in Figure 5 and Section 5.3 of the revised draft. This result underscores the efficacy of our main idea, the breadth-first exploration.

As you may understand, it is prohibitively challenging to theoretically analyze deep RL. Instead, in response to your request for a theoretical analysis of BEAG, we can provide a guarantee on the grid-based “planner”. Specifically, we can show that given 2D Euclidean goal space, the grid pattern of $\square$ has the worst-case sub-optimality ratio $\frac{\sqrt{2}}{2} \approx 0.707$, and a denser pattern of $\boxtimes$ improves it to $\frac{\sqrt{5}}{1+\sqrt{2}} \approx 0.926$ where ratio 1 implies the optimality. Regarding this, we will include a formal statement and proof as soon as possible.

We appreciate your comment as it provides the opportunity to clarify our contributions and drive an interesting theoretical analysis.

Q3. [Weakness1] The effect of threshold hyperparameters are not shown. Also, the ablation study can focus on more aspects of BEAG. [Question 2] I would like to see more experiments on failure conditions and count thresholds.

A3. We appreciate your valuable suggestions on additional experiments. As suggested, in Figure 7, we conducted ablation studies on BEAG with different values of ($\tau_t$: [50, 100, 150, 200]) and ($\tau_n$: [1, 3, 5]). As expected, both $\tau_t$ and $\tau_n$ (determining the thresholds to avoid subgoals) need to be set at minimal values to reduce attempts at impossible subgoals. However, exceedingly small values for $\tau_t$ and $\tau_n$ may accidentally identify attainable subgoals as impossible ones and possibly degenerate performances in early phases, as depicted in Figure 7 (d) and (e). This observation provides a useful guideline for the hyperparameter choice of our method. We hope that these additional experiments address the reviewer's concern.

Thank you for the clarification and additional experiments. They help in a better understanding of the paper. I adjusted my score based on the revised version.

Q3. [Weakness 3] The authors did not provide clear explanations or intuitions for some of the design choices, such as why we use Euler-distance instead of others as the $w_{i,j}$

A3. Thank you for highlighting the need for clarification in our method. In response to your request, we have added an explanation in Section 4.1 to clarify why we opted for Euclidean distance as the weights. We bring it for your convenience:

We assume that the cost of moving between two subgoals at an equal distance is similar, and thus, we use the Euclidean distance as the weights of the edges. To generalize to diverse environments, if the aforementioned assumption does not hold, the distance measure introduced in Equation 1 can be employed as the weights of the edges. However, it is noteworthy that the Q-function may exhibit instability in predictions for untried transitions, potentially hindering exploration.

Furthermore, our method can adopt alternative edge weights. We are currently conducting an additional experiment using the value difference (Equation 1) for edge weight. We commit to promptly incorporating these results, while we anticipate observing nearly identical advantages of the proposed method. We thank the reviewer for the comment, providing this opportunity to explore other design options and to enhance the transparency of our design choices.

Q4. [Weakness 4] The illustration in Algorithm tables is unclear (e.g., some notations lack explanation), so it is hard to and even cannot follow that. [Weakness 5] It is unclear how the edge weights work for the proposed method

A4. Following your comments, we revised the algorithm in Appendix A and Section 4 for a detailed explanation of our method.

• change the notation of graph $\mathcal{G}$ into $\mathcal{H}$ for clarification
• change the notation $a_j, s_j$ into $n_j^a, n_j^s$ in equation (2) for clarification and align them in the algorithm.
• add the simple explanation of notation in the algorithm.
• add the algorithm for training and graph construction.
• add the training details (e.g. initial random stage).

According to your comment on the description of the edge weights in BEAG, we have revised Section 4.1. For the sake of clarity, in what follows, we elaborate on how the edge weights work for BEAG. Each edge weight is uniformly initialized with an interval $n$. During an episode, if an assigned subgoal remains unachieved for $\tau_t$ steps, the edges connected to the unattained subgoal in that episode are disconnected by assigning infinite weights to encourage the exploration of new paths. If such failures have been continued in the previous $\tau_n$ episodes, the edges will remain disconnected (while the refinement procedure can revive a part of them). Otherwise, they are reconnected in the next episode.

Q5. [Question 2] Why does the coverage in Figure 7 decrease?

A5. We note that Figure 7 in the submitted paper has been removed in the revised one. The decrement is just temporal and the coverage is recovered in a few epochs. We present the raw data for Figure 7 in the below table. We hope these have addressed your concern.

Q6. [Question 3] Why is the success rate in Figure 4(d) higher than 1?

A6. We note that Figure 4(d) in the submitted paper has been replaced with Figure 4(e) in the revised one. The shaded region in our plots visualizes the standard deviation centered around the average. Hence, it is possible to observe the shaded region of the success rate curve higher than 1, while there are no sample instances exceeding 1.

Q7. [Question 4] Why does the learning curve in Figure 8(a) not start from 0 environment step?

A7. In response to your question, we report the curve starting from the 0 environment step. The revised figure can be found in Figure 4(a) in the revised draft (while it was Figure 8(a) in the submitted paper). BEAG begins with a roll-out phase where the agent proceeds with actions entirely at random without training. This is to obtain a certain size of replay buffer and is also employed in DHRL. In our plots, the success rates of BEAG and DHRL are set to zero over the roll-out phase.

Dear Reviewer fvhd

We would like to express our sincere gratitude for your valuable comments and insightful feedback. Your comment has greatly enriched our work and provided us with valuable perspectives. We address your comments one by one in what follows.

Q1. [Weakness 1]The proposed method heavily relies on the task structure (distance-based, discrete) to apply the graph construction to record the achieved and unattained goals.

A1. We appreciate the opportunity to clarify the applicability of our approach. The proposed BEAG is designed to be versatile and can be applied to a broad range of environments where other graph-based RL frameworks are applicable. In essence, the main goal of studying graph-based RL is to develop a framework that fully leverages the distance-based goal structure, a characteristic shared by various practical systems such as navigation and robot-arm manipulation.

Given such a goal structure, BEAG not only applies but also offers distinct advantages, which are twofold: (i) recording achieved and unattained subgoals to avoid consecutive attempts at impossible subgoals; and (ii) selectively densifying the grid to adapt to diverse environments.

Notably, an additional experiment (Figure 8) demonstrates the effectiveness of recording achieved and unattained subgoals, even in a variant of BEAG using a random graph over the entire goal space instead of a grid, while previous works are prone to obsessively attempting impossible subgoals as they rely on SoRB, subsampling subgoals only from a set of visited subgoals. In addition to this, BEAG using grids shows a clear benefit, compared to the variant with random graphs of irregularly distributed subgoals. We refer the reviewer to Section 5.5 for a comprehensive discussion.

We hope this clarification addresses concerns about the reliance on task structure and underscores the versatility and advantages of our approach across various goal-oriented environments.

Q2. [Weakness 2] The comparative baselines are limited on some environments. Only DHRL is involved. Since RL algorithms often perform high-performance variance in different environments/tasks, I think it is necessary to make comparisons with more baselines. And also, I think it would be better if the authors make comparisons on different environments. [Question 2.] Why does the comparison in Figures 4-6 not include the other baselines introduced in the Appendix?

A2. As requested, we have expanded our evaluation by incorporating additional baselines, namely PIG [1], HIGL [2], and HIRO [3], alongside DHRL [4]. BEAG outperforms all the baselines, not only graph-based RL approaches (DHRL, PIG, HIGL) but also the other hierarchical RL one (HIRO) while DHRL is the most competitive. We note that our evaluation fairly supports the superiority of BEAG since our choice of benchmarks is standard and comprehensive, aligning with those used by other works to justify their proposals. The observed superiority of BEAG stems from its unique ability to systematically identify and avoid impossible subgoals on the adaptive grid, a factor overlooked by other baselines. For a detailed comparison, please refer to Figure 4 and Section 5.2 in the revised draft, where we present a more comprehensive analysis of the results. We are confident that this expanded comparison offers a clearer understanding of BEAG's strengths, as well as addresses your concerns.

[1] Junsu Kim, Younggyo Seo, Sungsoo Ahn, Kyunghwan Son, and Jinwoo Shin. Imitating graph-based planning with goal-conditioned policies. ICLR 2023.

[2] Junsu Kim, Younggyo Seo, and Jinwoo Shin. Landmark-guided subgoal generation in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 34:28336–28349, 2021.

[3] ​​Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.

[4] Seungjae Lee, Jigang Kim, Inkyu Jang, and H Jin Kim. Dhrl: A graph-based approach for long- horizon and sparse hierarchical reinforcement learning.Advances in Neural Information Process- ing Systems, 35:13668–13678, 2022.

Thank you for the positive response. To adderss your remaining concern on our presentation of success rate curves (which should be bounded in [0,1], instance-wisely), we have made the following revisions:

• We have included plots of all the raw data, instance-wisely, in Appendix B.
• To reduce the potential misunderstanding, we have modified all the figures plotting success rate curves (Figure 4, 5, 6, 7, 8), where we clip the values of (average+-1 standard deviation) of success rates inbetween [0,1]. Apprantely, this cliped presentation is standard in previous works, e.g., HIGL and PIG. Additionally, we would like to emphasize that the computation of the success rate employs the same formula as used in these previous works

We believe these additional plots and modifications will address any concerns or uncertainties you may have had. Please let us know if further clarification or adjustments are needed.

Dear Reviewer qmXA

We would like to express our sincere gratitude for your valuable comments and insightful feedback. Your comment has greatly enriched our work and provided us with valuable perspectives. We address your comments one by one in what follows.

Q1. [Weakness 1] While grid is a way to have a systematic representation of the space, there are other approaches in planning that are present in the literature, including sampling-based approaches that can address similar problems. It is worth discussing the rationale behind choosing grid, as that is not necessarily the primary choice for high-dimensional spaces (which the paper mentions to leave it for the future)

A1.
Thanks for the suggestion. As you mentioned, it is crucial to manage subgoals including not only visited but also unattained ones, in order for avoiding successive attempts to impossible subgoals. To support such subgoal managements, one can also consider a random sampling over the entire goal space (noticing that this random graph now contains unattained ones and thus differs from SoRB used in the previous works). However, thanks to the regularity of grid, the grid-based one is more efficient than the random one in terms of the number of subgoals covering the goal space. Indeed, in our additional experiment (Figure 8), the grid-based management (without adaptive refinement) outperforms the random-sampling. (See Section 5.5 for a comprehensive discussion.) Besides this, the regularity of grid inherently provides the ease of implementing the breadth-first exploration upon adaptive refinement, whereas it is somewhat non-trivial to devise a mechanism of adaptive refinement on the random graph due to the irregular dense, although it seems not impossible.

We note that graph-based RL algorithms share the reviewer’s concern about the scalability in high-dimensional goal spaces. However, this concern can be addressed by the proposed adaptive refinement, starting from a sufficiently sparse grid and selectively densifying the grid. The grid also provides the aforementioned efficiency from the regularity. In summary, this strategic combination of adaptive refinement and grid structure is designed to offer a scalable solution to high-dimensional goal spaces, as well as the efficiency gained from the regularity of the grid.

We appreciate the opportunity to further clarify these points and invite any additional feedback or questions from the reviewer.

Q2. [Weakness2] As Reacher3D is the scenario where results are fairly close, goals could be set at different locations to report the coverage too, unless there is a specific reason not to have different goals also for Reacher3D.

A2. We will provide the requested plot comparing the average coverage in Reacher3D, where we believe the main message drawn from the success rate is not different to that from the average coverage.

Q3. Minor comments on the presentation

A3. We appreciate your valuable feedback on the presentation of our work. Specifically, we acknowledge the need for improvement regarding the provocative expression used to describe the performances of the baselines that were initially excluded. Accordingly, we have revised the manuscript to include a clear and comprehensive presentation of results, encompassing the complete set of baselines. We extend our sincere apologies for any unintended tone in the initial description. We have diligently incorporated all of your suggestions into the revised draft.