Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
The authors discuss the impact of Monte Carlo Tree Search (MCTS) algorithms.  MCTS allows us to roll out trajectories using state value estimates to determine local actions, however computational cost can be high. This means that the approach is prohibitive for large problem spaces.  RL seeks to learn a control policy that generalizes well over the state space. This can be challenging and MCTS algorithms can help with this.

In goal reaching problems the agent takes as input the current state of the env as well as the goals state.  The only trajectories that confer positive reward are those where the goal is reached. RL can struggle here as the rewards are sparse due to the success criteria.  More informative reward functions can be used (e.g. distance to goal) but this isn't always possible.  Hindsight Experience Replay (HER) is applied to offline RL algorithms to improve sample efficiency where a replay buffer is maintained over retained trajectories and a set of sub-goals are defined over visited states with returns applied accordingly.

The authors propose to apply HER to AlphaZero to solve goal directed tasks and thereby avoid computationally intense tasks. They evaluate the approach against a set of simulated environments and compare to AlphaZero, including a novel Quantum compiling environment.

Much of the challenge in solving games like Go and Chess comes down to the size of the state space.  AlphaZeroHER works by sampling new sub-goals from already visited states and thus avoiding both the high computational cost involved in tree re-weighting and also the problem of sparse rewards.   This is done by retracing episodes and sample M subgoals from a trajectory of length T and training the policy and value networks on these hindsight inferred goals.  Since AlphaZero is on on-policy the policies used during play are retained when computing updates from the sub-goal rollouts which alleviates the computational burden.

The authors show that AlphaZeroHER outperforms AlphaZero over a number of simulated environments where the latter often fails to achieve learning much while the former achieves strong results.



main_review: 
**Strengths:**

The paper is over all well written and organized.  The background material is clearly presented and sets up the description of the method well.  The results and environment descriptions are also clear and demonstrate a significant improvement under the proposed method.

The idea presented is simple and yet novel.  The authors have done well to address and rectify  the potential issues around the on-policy feature of AlphaZero with HER.

The results provided are clear and show that this approach can confer significant benefit over AlphaZero in a reward sparse setting.


**Weaknesses:**

More formality and description in some areas of this paper could help.  For instance in section 3.1, I think the paper can benefit from more description.  In the paper: "The basic idea is to neglect its on-policy nature generating additional training samples at the end of each episode by sampling additional subgoals from the visited states."  The following paragraph does go into more detail however I'm wondering if an algorithm box may or some other more detailed description might make the details clearer.

It would be helpful to see more detail around the tree re-weighting procedures and how HER helps reduce the computational costs on AlphZero.  Can the other sources of high computational costs be explicitly stated if there are any?

While the results indicate that  AlphaZeroHER yields significant improvements over the chosen evaluation domains however the set of environments seem to be mainly toy environments that can be solved on the order of hundreds or thousands of training epochs.  That said, the authors have mentioned that they have left more complex environments, including those with stochastic transition models, to future work.

It would be useful to include analysis around the computational efficiency claims made with respect to including HER.  For instance, does AlphaZero eventually reach the performance of AlphaZeroHER after more training?

How close are the presented results close to optimal scores in their respective environments?

How exactly are subgoals selected?  Could more details be provided?  Are they simply sampled randomly?
summary_of_the_review: 
Overall this paper is well presented and delivers a simple yet clear idea with clear and convincing results over AlphaZero by applying HER to AlphaZero.  I'm somewhat on the fence as I do believe this a worthy contribution showing clear results, however I think that this paper would benefit from a bit more clarity around the algorithmic details and would strongly recommend that something be included to this effect at least in the appendix, but more preferably in the main paper.  Also useful would be some analysis to help the reader understand why this method works better, lending insight into the execution model and helping us to understand why we may expect this to extend to more complex environments.

Post rebuttal:

Given the rebuttal additional clarity on algorithmic details and computational costs, tree re-weighting and it's relational to HER have clarified things on my end. I'm happy to increase my score to an eight.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper addresses multi-goal reinforcement learning. It presents empirical results with a variation of an existing algorithm, Hindsight Experience Replay (HER). Specifically, the paper uses HER alongside AlphaZero. 
main_review: My main comment is that the technical and empirical novelty of the paper is relatively low. Andrychowicz et al. (NeurIPS, 2017) give extensive results with HER in multiple domains and with different reinforcement learning algorithms. HER can be combined with any off-policy algorithm, and the novelty here is that it is being combined with AlphaZero even though Alpha Zero is not off-policy. The experimental evaluation does not probe the technical approach deeply. The main result is that the combination of HER + AlphaZero improves performance over AlphaZero only, which is expected. Some avenues of further investigation include the following: What are the impacts of different ways of choosing goal states to use with HER? How well is the combination of HER + AlphaZero address various problems compared to other approaches to multi-goal reinforcement learning? 

The paper is clear. 

In the 2D navigation task, what if the start and goal states were sampled randomly from the entire state space? I am wondering whether the task is being made simpler by consistently sampling the start and the goal states on the left and the right sides of the wall, respectively.

After author response: Thanks to the authors for their additional comments and work on the paper. My main comments remain the same.  Compared to the original paper on HER, the novelty here is relatively low. While there are now additional experimental results with DQN, the end result is still a narrow range of algorithms being compared experimentally, and the experimental evaluation does not probe the technical approach deeply. In the response, the authors do not actually answer my question on the impact of different ways of choosing the goal states. Instead, their response is only about choosing a different number of goal states. 

About the 2D navigation task: The authors write "Sampling start and goal states randomly over the whole state space, would allow to easily reach the goal if they both are on the same side of the wall." But it would also require the agent to learn to move in both directions (left to right, and right to left). 
summary_of_the_review: The paper makes a relatively small technical and empirical contribution given existing results on HER (Andrychowicz et al., NeurIPS 2017).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: For the AlphaZero approach, the rewards of goal-directed planning environments are too sparse to learn efficiently. To solve this problem, the authors proposed the AlphaZeroHER method by combining AlphaZero with Hindsight Experience Replay(HER) to enable AlphaZero agents to learn in goal-directed environments. The experiments showed that AlphaZeroHER is better than AlphaZero on BitFlip, 2D Navigation Task, 2D Maze and Quantum Compiler environments.

main_review: This paper proposes to incorporate HER into AlphaZero to solve the problem of goal-directed planning under a deterministic transition model. Their method is particularly eﬀective for those sparse rewards problems as demonstrated in the experiments. While the method is interesting, the following comments need to be addressed. 

* The authors should experiment using HER, since it is also interesting to see whether HER can already solve the problem well, and how much AlphaZero can contribute to the method.
* In this paper, M subgoals are sampled for training. Why not all subgoals? An experiment on this is requested. 
* For goal-directed problems, the author should also reference the following work. 
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's Cube with Approximate Policy Iteration, ICLR 2019.

Some minor comments: 
* In the BitFlip experiment, how many steps does the environment for AlphaZero/AlphaZeroHER interrupt during self-play? 
* In Page 5, What is "tree-s"? 
* Keep the terminology consistent, say goal-directed and goal-oriented. And, also for neurons, nodes, and units. 
* A typo in the last paragraph of Page 2, discounted sum of future rewards $R_t = \sum_{i=t}^{\infty}\gamma^{t-1}r_t$ should be $R_t = \sum_{i=t}^{\infty}\gamma^{i-t}r_i$

summary_of_the_review: This paper proposes to incorporate HER into AlphaZero to solve the problem of goal-directed planning under a deterministic transition model. Their method is particularly eﬀective for those sparse rewards problems as demonstrated in the experiments. While the method is interesting, the above comments need to be addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents AlphaZeroHER, an extension of the AlphaZero learning-informed Monte Carlo Tree Search algorithm in which the ideas of Hindsight Experience Replay (HER) are applied to augment training and therefore better support goal-directed planning tasks. Consistent with the general HER procedure, the approach generates new data under the assumption that the goal was one of a set of sampled "subgoals", requiring that that the reward and target policy be recomputed. The target policy is chosen to be the empirical policy achieved during the episode, for though it is not optimal for the new goal, it did indeed reach the subgoal. The authors demonstrate performance on a handful of goal-directed planning tasks—including BitFlip, navigation, and a quantum compiling task—on which they show improved performance over AlphaZero without the addition of HER.
main_review: Overall, the paper outlines an interesting and novel idea that could have potential to improve learning-informed model-based planning in this space. The experiment involving the quantum compiler is an interesting application as well that seems it could benefit in particular from a model-based approach to planning. However there are a couple high-level issues that should be addressed before the paper is suitable for publication.

The clarity of the paper is poor in key areas and it is difficult to understand the particulars of the method being proposed. First, nearly all figure captions contain the term "searches" to describe how much computational effort was put into the search process, yet it is not entirely clear what this term is referring to. Is this the total number of rollouts? The number of states that the agent has visited? The authors should clarify this point. Second, the final paragraph of Section 3.1, in which the only contribution of the paper is described, is hard to follow. After a few readings it is somewhat clear how the approach works, but the addition of an algorithm block or of a comparison between the initial AlphaZero training procedure and the new modifications added by HER would be a welcome addition. It seems that, rather than generate a new policy for the new goal states (which would be expensive) the policy executed by the agent during this episode are used as the target policy instead: is this correct? This seems like the simplest thing one might do in this situation (and seems quite reasonable given the challenge of the alternatives), but it would help me to be certain of my understanding.

Perhaps more importantly, the comparison to *only* AlphaZero is somewhat unconvincing, especially since much of the paper is spent describing other approaches that employ HER to improve performance a goal-directed planning tasks. While one can understand the potential advantage of a model-based planning approach like MCTS and AlphaZero, the paper in its current form does not show this advantage. In particular, most (if not all) of the experimental domains studied here are studied in other domains. The BitFlip domain presented in the original HER paper shows that it is possible to "easily" obtain good performance using DQN, suggesting that it might also be possible for existing model free approaches to reach or even exceed the performance of AlphaZeroHER in these domains. More results comparing AlphaZeroHER to existing baselines would greatly strengthen the paper. The authors should either justify why these other approaches were not included as a point of comparison (and add compelling reasons one might prefer to use AlphaZeroHER in the absence of empirical verification) or directly compare performance.

Smaller comments and suggestions for clarity:
- A few points in the abstract are somewhat unclear or hard to follow: (1) the sentence beginning with "It has been extended..." sounds as if AlphaZero is the function approximator. (2) "sparse rewards are adopted" 'adopted' is not the correct choice of word; rewards are either sparse for a particular problem or they are not (without additional heuristics). Making the language more precise in the abstract in particular will help guide the reader.
- The network definition at the end of 5.2 is unclear. Please reword so that it clear of the dimensions from the input all the way to the output for each network: e.g., 6->20->4->1 (I believe) for the value network.
summary_of_the_review: Though the paper demonstrates an interesting idea—combining AlphaZero with recent insights from Hindsight Experience Replay, on how to train a learning-driven agent in the presence of sparse rewards—the paper is lacking in clarity and omits comparison against clearly-important baselines that are known to perform somewhat well on some of the tasks of interest. Until these limitations are addressed, the paper is not likely yet suitable for publication.
review_title: null

Meta-review: The main detractor of this paper feels that the paper makes a relatively small technical and empirical contribution given existing results on HER (Andrychowicz et al., NeurIPS 2017).  However, several other reviewers, who had more engagement in the discussion, were strong supporters. Having looked at the paper myself I thought the selection of experimental problems undermined the results.  Experiments are most compelling when many unaffiliated groups compete on the same benchmarks.  But the basic idea of integrating HER with AlphaZero, and a reasonable attempt at this, seems to be interesting enough to warrant a poster.
Decision: Accept (Poster)