Goal-Directed Planning via Hindsight Experience Replay
Authors: Lorenzo Moro
Amarildo Likmeta
Enrico Prati
Marcello Restelli
Venue: ICLR 2022 Poster (2022)
Keywords: Reinforcement Learning
Goal-Directed Planning
Monte Carlo Tree Search

Abstract: We consider the problem of goal-directed planning under a deterministic transition model. Monte Carlo Tree Search has shown remarkable performance in solving deterministic control problems. It has been extended from complex continuous domains through function approximators to bias the search of the planning tree in AlphaZero. Nonetheless, these algorithms still struggle with control problems with sparse rewards, such as goal-directed domains, where a positive reward is awarded only when reaching a goal state. In this work, we recast AlphaZero with Hindsight Experience Replay to tackle complex goal-directed planning tasks. We perform a thorough empirical evaluation in several simulated domains, including a novel application to a quantum compiling domain.

Published as a conference paper at ICLR 2022
GOAL-DIRECTED PLANNING VIA HINDSIGHT EXPE- RIENCE REPLAY
Lorenzo Moro 2 Amarildo Likmeta 1 Marcello Restelli', and Enrico Prati
IDEIB Politecnico di Milano, Milan, Italy 2CNR-IFN, Milan, Italy
3 FABIT, Universita di Bologna, Bologna, Italy
ABSTRACT
We consider the problem of goal-directed planning under deterministic transition model. Monte Carlo Tree Search has shown remarkable per- formance in solving deterministic control problems. By using function approximators to bias the search of the tree, MCTS has been extended to complex continuous domains, resulting in the AlphaZero family of algo- rithms. Nonetheless, these a algorithms still struggle with control problems with sparse rewards such as goal-directed domains, where positive reward is awarded only when reaching goal state. In this work, we extend AlphaZero with Hindsight Experience Replay to tackle complex goal-directed planning tasks. We demonstrate the effectiveness of the proposed approach through an extensive empirical evaluation several simulated domains, including a novel application to quantum compiling domain.
INTRODUCTION
Monte Carlo Tree Search (MCTS) (Browne et al. 2012) algorithms have shown outstanding results in solving sequential decision-making problems, especially in deterministic transition tasks, such games. MCTS planners use forward environment model to build search tree, estimate the value of each action in the current statc, and execute the best-cstimated one, respectively. Such a procedure allows finding "local" solution to the decision problem in every decision step by sampling trajectories of possible future policies using the forward model. Although providing local solutions is advantageous high computational cost since acting in the environment requires interleaved planning phases and possibly large search trees. These high computational costs have been a. barrier in applying MCTS to larger problems, especially those with long planning horizons and huge tree branching factors (number of actions). However, MCTS does not require a training phase and can be deployed immediately.
some contexts, comes at
Reinforcement Learning (RL) (Sutionn el al. 1998), on the other hand, aims to find a global solution to the control problem by learning a policy that performs adequately in the whole state space. While this may seem a more desirable outcome, it can often be hard to produce policy that generalizes satisfactorily across different state regions. For this reason, MCTS algorithms have achieved tremendous success a wide range of tasks (Borsboom et al. Enzenberger et al. 2010 Ikchata and Ito. 2011). The AlphaZero (Silver al. 2016) family of algorithms made it possible to use sequential planners like MCTS in more challengig environments, such the game of Go, where the AlphaGo agent defeated the world champion, achieving super-human performance. AlphaGo was in turn defeated by the AlphaZero, a version of the algorithm without any heuristic related the game of Go. AlphaZero combines MCTS with the ability of RL algorithms to generalize across the state-action space by keeping a parametrized policy and value network. Specifically, the policy network biases the exploration during the tree search, and the value network estimates the value of the
"Equal contribution of the first authors. Correspondence lorenzo. mwwo@polimi......m it

---

Published as a conference paper at ICLR 2022
states corresponding to the search tree leaves, replacing the trajectory-based evaluation usually performed with an ad-hoc evaluation policy called rollout policy. On the other hand, the MCTS algorithm acts as policy improvement step. It takes imput the current state, as well as the policy and value networks, therefore improving the parametrized policy and generating the samples used to train the networks in a supervised manner. Although tree search is still required, the deployment is cheaper since it usually requires a humbler planning budget, thanks to the policy and value networks which bias the search by making it more efficient. The algorithm has been successfully applicd to different games such as Go, Chess, and Shogi (Silver et al. (017a) without gamo-specific heuristics. However, despite its success, the algorithm sullers from a high sample complexity, especially prominent in tasks with sparse reward functions, such as goal-directed planning.
In goal-directed tasks, the agent aims to reach goal state, and in general, the policies take both the current state of the environment and the goal state as input. Usually, the actual reward function in these problems is zero for any transition except the one to the goal state, which gives a positive reward. RL algorithms struggle to optimize sparse reward functions since it might be hard to reach goal states, or even practically impossible during exploration if the task is quite challenging. Therefore, there is not a reward signal to guide the exploration. While in practice, in specifie tasks, it is possible to use more informative reward functions, such as a distance from the goal state, such a choice is not possible for every task. Furthermore, it might also lead sub-optimal solutions since a reward function based on a state distance might generate local-optima in the policy space (Grzes and Kudenko 2009). Hindsight Experience Replay (HER) (Andrychowiez et al. 2017) straightforward method to tackle the problem of sparse-reward functions in goal-directed tasks. HER can be used with any off-policy RL algorithm to extend the training datasct for the value networks. Practically, whenever the goal state is not reached during a training episode, the states visited during the episode are used as alternative goal states and are fed to the network during training. It allows reward signals to be given to the value networks and generalize them to reach the input goal state.
In this work, we consider the problem of applying HER to Alphazero to tackle goal-directed tasks. We provide a scheme that does not involve computationally heavy tree re- ro-weighting procedures or high additional computational costs. Finally, we benehmark the method with simulated environments, and we show a novel application to quantum compiling, where it is extremely hard to find unitary gate sequences from a set to approximate arbitrary single-qubit unitary operators.
PRELIMINARIES
2.1 GOAL-DIRECTED REINFORCEMENT LEARNING
In this work, we focus on goal-directed Reinforcement Learning problems. In such setting, an autonomous agent interacts with an environment maximize the sum of observed reward signals. Formally, in deterministic transition models, the environment consists of a state space S, a set of goal states G (that can also be equal to S), an action space A, a goal-state dependent reward function r S x A x g + I., a transition model P : S x A + S, a probability distribution over for the initial state so ~ μt, and a probability distribution over & for the goal state Sg ~ V.
The behavior of the agent is described by a Markovian stationary goal-dependent policy, Sxx Ç -+ A(A), which takes as input the current state and the goal state 8y, and outpuls a probability distribution over the actions in A. At the beginning of each episode, an initial state so y and goal state S, are sampled. Then, at time step t, the agent observes the current state st, selects an action a ~ T(S,, sy), observes the next state $t+1 = P(st, a;) and it gets the reward signal r. r(s,, Sg).
The goal of the agent is to maximize the expected return E[R] defined as the expectation of the discounted sum of future rewards R2 Σe ""r,, taken over the initial state and goal state. Given a policy n, the value of each state is encoded by the value function 1 (s, 8g) Ex [Rolso s]. Similarly, the action-value function is defined for each state-
2

---

Published as a conference paper at ICLR 2022
action pair, conditioning on the first action of the trajectories, (= a, 8y) = Eaia (s 8, Gu = al. The goal of maximizing the return can be expressed as finding an optimal policy, r arg max, V (s(ss)g)) V(s,8g) E S x g.
2.2 MONTE CARLO TREE SEARCH
We briefly introduce the Monte Carlo Tree Search (MCTS) family of algorithms, which combine tree-search algorithms with Monte Carlo sampling to build a search tree iteratively. We focus the most popular algorithm in the MCTS family, i.e. the upper confidence bound for trees (UCT) (Kocsis and Szepesvári, 2006). More precisely the general MCTS
algorithu consists of four stages (Browne et al. 2012
Selection. In the selection stage, the selection policy is applied from the root of the search tree recursively until an unexpanded leaf node is reached.
Expansion. In the expansion stage, one or more successors to the previously-found unex- panded node are generated according to the actions available in the node.
Evaluation. The newly generated nodes are evaluated, generally through a simulation (rollout) using a default policy.
Backpropagation. In the last. stage, the rewards collected during the selection and evalua- tion phase are backed up following the previously visited tree branch.
UCT performs the selection phase using the Upper Confidence Bound (UCB1) (Auer et al. 2002 bandit algorithm. Specifically, cach node of the scarch tree maintains statistics related to the future value of each action, including the number of visits, the number of times an action is performed, and the total sum of the returns observed, used to estimate the mean return. Using such statistics UCB1 chooses the next action to perform, axs according to
2 llogn
O₂ aar max B(a.)= = (e C I.l..K
(1)
T3 Tn 1)
where K is the number of actions, C is constant that regulates the exploration-exploitaaioo trade-off, Te(n- - 1) is the number of times action has been played up to time n - 1 and (n-)( is the average payoff observed from arm i. UCT recursively updates the values of the nodes from the leaf to the root of the tree, during the backup phase. The algorithm is proved to be consistent, i.e., it converges to the optimal policy in the limit.
2.3 ALPHIAZERO
AlphaZero Silver et al. 2017a) bridges the gap between RL and MCTS by maintaining parametric policy, To and value function vp- The policy and value networks are provided as input to the MCTS algorithm to bias the tree search. In contrast, the visit counts in the tree's root are used to build the targets for the supervised training of the policy network.
Compared to general MCTS, the selection and evaluation phases are modified. The former phase uses the policy no, to bias the exploration according to the policy recommendations. Furthermore, AlphaZero replaces the classic UCT algorithm with PUCT (Rosin 2011 and performs the selection according to:
On = arg max B(a;) = RA,I,(n-11 + (s)(s,a:) iml..K
71
(2)
1 1 Ti(n-
By multiplying the PUCT confidence interval with the probability given to by Alp- haZero initially prefers actions with high probability and a low visit count but asymptotically prefers actions with high values. In the latter phase, AlphaZero evaluates the leaf nodes using the estimate provided by the value network Up, instead of performing expensive simulations with default rollout policy. The training targets of the value network are the actual returns collected during acting. More formally, at each time step t, AlphaZero performs M search iterations of MCTS, starting from the current environment state 8, and using no during the
3

---

Published as a conference paper at ICLR 2022
selection phase, and Up during the evaluation of the leaves. After the search phase, the policy targets Pt are constructed using the visit counts at the root of the tree:
No. p:(a,) = Ne
Vi vi=l..... K.
(3)
where No. is the visit count, of the i-th action in the search tree at step i, and K is the number of actions. Then a is sampled according to pt and executed observing the next state st+1 and the reward signal r;. In practice, Pt is often constructed over the action counts, only executing the most explored one. At the end of each episode, the collected rewards added to a replay buffer used during training of the networks. In the original AlphaZero paper, the policy and value networks share the parameter vector 0 and AlphaZero minimizes:
greedy policy
used to build the value network targets RG- The triples (st, Pt, R.) are
(t,,
[R vo( - p" log = (sDD.R)DD
(4)
where controls the amount of L2 regularization.
2.4 HINDSIGHT EXPERIENCE REPLAY
Hindsight Experience Replay (Andrychowicz et al., 2017 is method of extending off-policy RL algorithms to improve sample efficiency even in the presence of sparse reward functions. HER requires parameterizing the reward, policy, and value as function of the current and the goal state. The basic idea behind HER to extend the replay buffer TB after each episode {50, 31,...,77 with the returns calculated based on set of subgoals. While the main goal influences the agent's actions during training, it does not influence the state transitions. Consequently,
generate additional training samples by considcring subset of the states visited during the episode as subgoals. This is extremely beneficial in cases with sparse rewards, such signals would be null until the goal state is visited by chance. However, HER enables the reward signals to be generalized across the state space.
reward function of the type r(s,, a,, 8g) 1 [s =g)) where reward
ALPHAZERO WITH HINDSIGHT EXPERIENCE REPLAY
This section describes the AlphaZeroHER algorithm. AlphaZero has been successfully applied to challenging games such as Go and Chess with outstanding results. The complexity of these games stands in the vast state-action spaces and the highly sparse reward function, since the agents will only know at the end of the game whether they have won (a reward of +1), lost (a reward of -1) or drawn (a reward of 0). Although in the context of Temporal Difference (TD) (Sutton et al. 1998) algorithms, Chess and Go fall under the definition of sparse reward, when considering returns observed at the end of the episode (Monte Carlo returns), such games have a clear reward function: the game''s 's result is either a win, a loss or draw. This reason may give the impression that AlphaZero doesn't. 't. suffer in sparse reward setting. However, in goal-directed planning, the Monte Carlo returns are often sparse, in the sense that the whole episode might finish without reward signal. This problem was also mitigated in the original AlphaGo Zero paper (Silver et al. (017b), where the authors employed ad-hoc board evaluators to compute the Monte Carlo returns when episodes of Go were interrupted because they were too long. Duc to the criticality of sparse rewards, we extend AlphaZero with HER to tackle goal-directed tasks.
3.1 ALPHAZEROHER.
The basic idea of AlphaZeroHER, is to extend AlphaZero by using goal-directed policy and value network and injecting HER into such a setting. Exploiting a goal-directed policy and value network in AlphaZero is effortless since the experience samples also include the goal state sg. However, AlphaZero is not an off-policy algorithm since the value network trained with the returns collected while playing the MCTS augmented policy. Moreover, it is not straightforward how to evaluate the new policy when considering a new goal s; * sy without introducing additional prohibitive computational costs and tree re-weighting procedures.
4

---

Published as a conference paper at ICLR 2022
Ideally, we aim at estimating new policy conditioned on subgoal 8t # 8g. However, estimating such a policy requires building an additional tree since the policy targets in AlphaZero are function of the action counts in the tree's root node, and this with an obvious additional computational cost. An alternative approach could keep the original goal's search tree and re-weight the statistics in the nodes conditioned on the reward function for the new goal 8t. However, such a procedure would require at least traversing the whole tree once, which would be computationally prohibitive for a large search-tree. Such problems represent the main obstacle toward introducing HER.
We propose a procedure that extends AlphaZero with HER without adding high computa- tional costs. 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. In fact, even though the MCTS augmented policy of AlphaZero did not reach the goal state, successfully reached all the states visited during the episode. More preciscly, we employ HER after finishing an episode of length T' and having generated the sequence of states, reward and policies, Ps, Pe. 1= The episode is retraced so that at each state &t. M subgoals are sampled from future visited states, {s.) After selecting the subgoals states for state St, we need to compute these states' policy and value targets. This task is not Arright.forward since AlphaZero an on-policy algorithm. If we computed, in some way, a different policy target. from the actual policy played Pt, these would generate a different sequence of state and rewards after timestep t, which are not available. We could use the built tree to evaluate these returns related to the subgoals, but these would come with heavy tree-reweighting schemes for an already computationally heavy algorithm AlphaZeroo For this reason, we select as additional policy targets the policies played during the episode pa since, although these are not the optimal policies that the MCTS agent would have playod the subgoal states were the goal during the search, they successfully reached the alternative goal states. Therefore, these samples still represent an improvement over the current policy Pa. which can be used policy improvement steps. Finally, compute the new returns based on the states visited only by computing the new reward signals for each new subgoal. Such procedure is done once for each episode and involves negligible additional computation. We call this method AlphaZeroHER. Algorithm 1 in the appendix shows the pscudocode of the proposed procedure.
3.2 MOTIVATING EXAMPLE
To highlight the AlphaZero oriticality in sparse reward enviromments, consider simple BitFlip domain from (Andrychowicz el al. 2017), described in detail in Section 5 In this domain, the goal is to modify long series of bits to reach the desired bit configuratio.. While it might be easy to achieve the goal configuration by applying a random policy when considering few bits only, it is practically impossible reaching the goal state if the bit length is increased.
Figure shows the performance of plain AlphaZero in the bit-flip environment, where have plotted the expected return and the percentage of solved episodes as a function of the training epochs for three different scenarios. While AlphaZero can consistently solve an "easy" scenario of 10 bits achieving almost perfect performance, it struggles with modest increase in the number of bits, dramatically failing solve the task with 18 bits.
4 RELATED WORKS
Goal-Directed Reinforcement Learning has been extensively studied over the years. The optimization of multiple goals has been largely investigated in multi-goal policy optimization, curriculum learning, goal-directed planning, and multiple-task off- off-policy learning.
In the context of universal value function approximators, in (Schaul et al. 2015 the authors consider the problem of approximating multiple value functions in a single architecture. In this line of work, various works study the problem of compact representations of multiple tasks (Dhiman et al. 2018 Ghosh et al., 2018). In such context, the use of sub-goals (intermediate states between the current state and the goal state) have been studied to
5

---

Published as a conference paper at ICLR 2022
100
Solved Episades (9)
Average Return
-10
40
-20
-25
0.0
0.5
1.0
1.5
2.0 Epoch
2.5
3.0
3.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
le1
Epoch
lc1
Figure 1: Performance of the AlphaZero agent in the BitFlip environment varying the number of bits using search iterations. Average over 10 runs, 95% c.i.
accelerate learning and generalize over the state-space (Nasiriany et al 2019 Jurgenson al. 2020). In (Parascandolo et al. 2020), the authors move the problem of goal-directed planning from the space of possible policies to the problem of finding suitable sub-goals. While this has some advantages in certain situations, it cannot be applied in large state spaces since the complexity of the algorithm scales linearly with the number of stales. Approximate value iteration has also been used with great results to solve the Rubic's cube with a goal-directed framework in (McAleer al. 2019
In the context of policy search, (Pinto and Gupta, 2016 and Caruana 1997 aim to learn policies to solve multiple tasks simultaneously. studied in recent years and can be scen as closcly related to multi-task lcarning. In meta- learning, a meta-learner is trained learn swiftly in ever-changing tasks adapt to learning in untested tasks quickly. While meta-learning has been investigated early in the
has also been extensively
literalure (Schmidhhuer 1987 2007), recent work has shown impressive results in the context of Deep RL (Finn et al. 2017 2018). Hierarchical Reinforcement Learning is also closely
related to meta-learning aand our work). Here the goal is to (automatically) learn to perform multiple tasks by splitting the main problem into sub-tasks (Schmidhuber 2002
Fruit et al.
2017). This is also closely related to the options framework.
5 EXPERIMENTS
In this section, provide experimental evaluation of AlphaZeroHEER on simulated do- mains, including a novel application on quantum compiling task, modeled as a deterministic goal-dirocted MDP. In the following, "search iteration" refers to single application of the 4 MCTS phases. More details are given in Appendix B.1 including a comparison with DQN+HER.
5.1 BITFL.PP
We consider BitFlip environment where the individual bits of a long series of bits are changed to reach a desired final configuration. More precisely, the state space is S = {0, 1J", as well the goal space G. The action space the current state changes from 0 to 1 or vice-versa. At the beginning of each episode, the starting bits and goal state are set randomly with uniform measures over the state space. We use "sparse" reward of -1 for each transition, unless the goal state is reached.
(0, I,...,
specifies which bit of
We tested such an environment as a motivating example for the application of HER in AlphaZero and a benchmark test since increasing the number of bits can vary the task's difficulty sensibly. In all the runs BitFlip, we use 20 neurons for the shared layer, neurons for the policy layer and for the value layer. The network hyper-parameters were not optimized. Figure 2 reports the performance
the scenario of 70 bits for different number of subgoals sampled (0 subgoals refers plain AlphaZero). While AlphaZero struggles with 12 bits and fails with 18 bits, AlphaZeroHER manages to achieve great results in the of 70 bits. Moreover, the agent. achieves better performance by
AlphaZeroHER

---

Published as a conference paper at ICLR 2022
-30
100
Solved Episades (%)
Average Return
-40
-50
40
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Epoch
1e1
Epoch
1c1
Figure 2: Comparison between AlphaZero (red line) and AlphaZeroHER (green, blue, and orange lines) in the BitFlip environment varying the number of sampled subgoals, using 20 search iterations and 70 bits. Average over 10 runs, 95% c.i.
-75
-100
Aptaades
Solvad Episades (96)
Average Return
-150
-175
-20
0.0
0.5
1.5
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Epoch
182
Epoch
1e2
Figure 3: Comparison between AlphaZero and AlphaZeroHER in the 2D Navigation task using search iterations. Average over runs, 95% c.i.
increasing the number of additional goals, getting perfect performance by using 4 subgoals only.
5.2 2D NAVIGATION TASK
In this section, consider 2D navigation task built on top of the Mujoco (Toorovv et al. 2012) robotics simulator, called Point. The purpose of this experiment performance of AlphaZero and AlphaZeroHER in more challenging task, that requires fair amount exploration. More precisely, the agent's goal (orange ball) has to reach the goal state highlighted by the green rectangle shown in Figure 4 The task is made more challenging by the presence of wall the center of the cnvironment. At the beginning of each episode, the starting state and the goal state sampled the left and right sides of the wall, respectively. The agent observes its current position and its current velocities in both directions and the coordinates of the goal state, while the action space is represented as control over two actuators of the agent. Although the original action space is continuous over the domain [-1, 1]2, we restricted the space to discrete actions, representing the center (no action) and 8 points on the circle centered at action (0, 0) with radius 1. The reward function is at each step, making the optimal policy the shortest path that reaches the green rectangle while circumventing the wall.
observe the
We use a simple MLP with 20 neurons for the shared layer, 10 neurons for the policy layer and for the value layer. Figure 3 shows the results of the experiments in this domain. We use a large horizon of 200 steps, alter which we interrupt the goal state was not reached. While AlphaZero fails to solve the environment, only reaching the goal state in 10% of the episodes, by applying HER we manage to solve most the episodes, with only sampling additional goals each episode of experience.
5.3
2D MAZE
This section considers an environment of 2D procedurally generated mazes whose structure changes each episode, shown in Figure This experiment aims to test the algorithm's

---

Published as a conference paper at ICLR 2022
Figure 4: Visual representation of the Point (left) and Maze (right) environments.
AlphaZeroHER AlphaZero
AlphaZeroHER
Salved Epicades (1%
AlphaZero
Averagn Return
-25
-35
400
0.0
0.2
0.4
0.6
0.8
1.0
1.2
0.0
0.6
1.0
1.2
Epoch
1e2
Epoch
Figure 5: Comparison between AlphaZero and AlphaZeroHER, in the 2D Maze task using 120 search iterations. Average over runs, 95% c.i.
performance in a challenging image task, where Convolutional Neural Networks represent the policy and value space. At each episode, the agent is spawned on free cell (shown in red) and moves to reach the goal cell (shown in green). The action space consists of four directional movements, which move the agent to one of the adjacent cells. However, if the action points towards wall, the agent does not move. The reward function employed in this environment is a constant reward of -1, prompting the agent to find the shortest path to the goal. The state-space corresponds to 2D image of the complete maze.
We employ the same network architecture all the experiments, consisting CNN, with kernel size of 3, Layer Normalization after each convolutional layer, and strides of [1,1,2]. The policy and value network heads have two additional fully connected layers of 128 and 64 neurons cach. We run experiments in 10x10 mazes, using an horizon of 60 steps, after which we interrupt the goal state was not reached. Figure 5 shows the results of the experiments in this domain. We can that AlphaZeroHER clearly outperforms plain AlphaZero in this environment, although it does not itself achieve a perfect score. We attribute this low general performance the fact that the hyperparameters of the training process were not optimized, and in an image based task, with CNNs as policy and value space, the architecture and training procedure is crucial. Nonetheless, AlphaZZroHHER manages to substantially clearly improve over plain AlphaZero with only 2 additional goals.
3-Layer
5.4 QUANTUM COMPILER ENVIRONMENT
Gate-model quantum computers achieve quantum computation by applying quantum trans- formations on quantum physical systems called qubits (Nielsen and Chuang 2002). Due to
hardware constraints and quantum disturbances (Linke et al. 2017 Maslov 2017 Leibfried ct al. 2007 Debnath et al. 2016), quantum computers require compilers to approximate any quantum transtormations as ordered sequences of quantum gates that can be applied on the hardware. In this work, we employ AlphaZeroHER to address the problem quantum compilation. We consider Quantum Compiler (QC) environment consisting of sequence

---

Published as a conference paper at ICLR 2022
-150
100
-175
AphaZaro
hwwww
Mwl
Solved Episades (9)
Average Raturn
-200
-225
-250
-275
-300
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Epoch
1e2
Epoch
1c2
Figure 6: Comparison between AlphaZero and AlphaZeroHER in the quantum compiling environment with 20 search iterations. Average over 10 runs, 95% c.i.
Un = II;= Ay of quantum gates A, that starts empty at the beginning of each episode, as fully described in Moro et al. (2027). Such sequence is built incrementally at each time-step by the agent, choosing from a finite set of quantum gates B corresponding to the action space. More specifically, we chose the base composed of six finite rotations, iee B = (Ra(+ 2. Rg(+ (28) R3 (=
The goal of the agent consists to approximate a single-qubit unitary transformation U that is chosen at each episode from Haar matrices. Pictorially, sampling Haar unitary matrices can be seen as choosing a number from a uniform distribution (Russell et al. 2017). The observation used as input at time-step t corresponds to the vector of the real and imaginary parts of the elements of the matrix On, where U = Un On- Such representation encodes all the useful information required to achieve the task, i.e the unitary transformation to approximate U and the current sequence (AGF) (Niclson 2002) a metric to evaluate the distance between the target gate U and the current sequence of gates Un. The task is solved whenever the agent reaches a distance equal to or greater than 0.99 AGF. The base of gates B allows defining a distance-based reward, which allows solving the problem with relative ease, although it leads to sub-optimal solutions as shown in Moro et al. (2021). However, in this work, we employ sparse reward equal to -1 regardless of the action performed by the agent. For such reason, the task is very challenging since a high number of steps are required to approximate Haar unitary targets on average.
gates. We exploited average gate fidelity
In all the experiments, we use the same network architecture, consisting of a simple MLP with one initial layers of 16 hidden neurons. The policy and value network heads have an additional layer of and hidden neurons respectively. Figure 6 shows the results of the experiments in the QC task. In this task, the planning horizon is substantially longer than in previous environments. We interrupted the episodes at 300 steps since a perfect policy achieves an average episode length of 180 steps, and 95% of the solution can be achieved using less than 200 stops Mooro et al. 2021 AlphaZero shows slow performance improvement, but after 100 training epochs it fails to learn the optimal policy. On the other hand, AlphaZeroHER consistently improves the performance and achieves almost perfect resolution of the problem.
CONCLUSIONS
We introduced a novel algorithm for goal-directed planning, consisting of the extension of AlphaZero with the Hindsight Experience Replay (HER) method to overcome the issues caused by sparse reward functions typical of goal-directed planning. We provide a straightforward procedure that does not involve high computational costs by sampling other goals from the visited states and addressing the intrinsic on-policy nature of Alpha The proposed approach outperforms AlphaZero in several test domains, including a novel application to quantum compiling, with negligible additional computation compared to plain AlphaZero. In the future, we aim to apply the proposed method to more challenging goal-directed tasks, including tasks with stochastic transition models, which were not considered in this work.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In I. Guyon, U. V. Luxburg, S. Bengio, Н. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Newral Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL htRps: httphccce///roeeeddggg .nw..eiriinnnn.....ii......
Paper pdf
Peter Auer, Nicolò Cesa- Bisncii and Paul Fischer. Finite-tine analysis of the multiarmed
bandit problem. Mach. Learn., 47(2-3):235-225 May 2002. ISSN 0885-6125. doi: 10.1023/ 10.1023/A:1013680 A:10136899774352. URL
1023/ A: 1013689704352
Joris Borsboom, Jahn takeshi Saito, Guillaume Chaslot, and Jos W. H. M. Uiterwijk. A comparison of monto-carlo methods for phantom go.
C. B. Browne, E. Powley, D. Whitehouse, M. Lucas, P. Cowling, Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods, IEEE Transactions on Computational Intelligence and Al in Games, 4(1):1 -::), 2012. doi: 10.1109/ N0.1109/TCIAIG.220 TCIIIG..011..21681)
Rich Caruana. Multitask learning. Mach. Learn., 28( July 1997. ISSN 0885-6125. doi: 10. 1023/ A:1007379606734, URL attps://doo org/10. 1
Shantamu Debmath, Norbert M Linke, Caroline Figgalt, Kevin A Landsman, Kevin Wrighl, and Christopher Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536(7614):63,, 2016.
Vikas Dhiman, Shurjo Banerjee, Jesfrey Mark Siskind, and Jason J. Corso. Floyd-warshall reinforcement learning learming from past experiences to reach new goals. CoRR, abs/ 1809.09318, 2018. URL http://arxiv wwgg/bs///t/eeeoeeeooooeee/ee ha///bb//1100 09318
M. Enzenberger, M. Müller, B. Arneson, and R. Segal. Fuego an open-source framework for board games and go engine based on monte carlo tree search. IEEE Transaclions on Computational Intelligence and Al in Games, 2:259-270 2010.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast
adaptation of deep networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1126 1135. PMLR, 06 //proceddings.oo mmr Stress/vo0ffinni/ html
Aug 2017. URL http
Chelsea. Finn, Kelvin Xu, and Sergey Levine. Probabilistic model-agnostic meta-learning. CoRR, abs/ 1806.02817, 2018. URL http://arxiv http:/aaxxvvv.../abbaa hatgg/bs//880 abs11806.18117
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret min- imization mdps with options without prior knowledge. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: htttp:://proceee http:s::///ooceedngss.oo newrips...e.ii..e.... cttrriis.ccpppaaae wttpcc/pppp/////////... 9DC9285aaf6e770aa17722555775-
pdf]
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal-conditioned policies. CoRR, abs/1811.07819 2018. URL http:://arxw..org///aa/ 0881.
Marek Grzes and Daniel Kudenko. Theoretical and empirical analysis of reward shaping in reinforcement. learning. Tn 2009 International Conference on Machine Learning and Applications, pages 337-344 2009. doi: 10.1109/TCMLA
ICMLA 2000.......3......
Nozomu Ikehata and Takeshi Ito. Monte-carlo tree search in ms. pac-man. In 2011 IEEE Conference on Computational Intelligence and Games (CIG'11), pages 39-46, 2011. doi: /0t////I...11.00000
10

---

Published as a conference paper at ICLR 2022
Tom Jurgenson, Or Avner, Edward Groshev, and Aviv Tamar. Sub-goal trees framework for goal-based reinforcement learning. CoRR, abs/ 22022.1361, 2020. URL https://arxit: org/abs/2000 12361
Levente Kocsis and Csaba Szeposvári. Bandit based monto-carlo planning. In In: ECML-06. Number 4212 in LNCS, pages 282-293. Springer, 2006.
Leibfried, E Knill, Christian Ospelkaus, and David J Wineland. Transport quantum logic gates for trapped ions. Physical Review A, 7633)24 2007.
Norbert M Linke, Dmitri Maslov, Martin Roetteler, Shantanu Debnath, Caroline Figgatt, Kevin A Landsman, Kenneth Wright, and Christopher Monroe. Experimental comparison of two quantum computing architectures. Proceedings of the National Academy of Sciences, 114(13):3305-33)) -3100, 2017.
Dmitri Maslov. Basic circuit compilation techniques for an ion-trap quantum machine. New Journal of Physics, 19(2):023035, 2017.
Stephen McAleer, Forcst Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with approximate policy iteration. In International Conference on Learning Represenlations, 2019. URL htttps:/oppereviiet http:///pppppreeeeee.eeerrrrrraa
Lorenzo Moro, Matteo G. A. Paris, Marcello Restelli, and Enrico Prati. Quantum piling by deep reinforcement learning. Communications Physics, 4(1):178, Aug 2021. ISSN 2399-3650. doi: 10.1038 00008//422005-02-006664 URL https://doi. wtt.//oo...g//....11//1 1038/ 342005-021-00688--
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal- conditioned policies. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpps://proceedngss http:///ppooddddngnn.o..ors.../p 1tll:/666900044400022111111100
pdf
Michael A Nielsen. A simple formula. for the average gate fidelity of quantum dynamical operation. Physies Letters A, (03(4))249-2)))) 252, 2002.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Giambattista Parascandolo, Lars Bucsing, Josh Merel, Lconard Hasenclever, John Aslanides, Jessica B. Hamrick, Nicolas Heess, Alexander Neitz, and Theophane Weber. Divide-and- conquer monle carlo tree search for goal-directed planning. CoRR,, abs/ 20044.11011,,, 2020.
URL https://arxiv.. org/ abs/ 11410.
Lerrel Pinto and Abhinav Gupta. Learning push by grasping: Using multiple tasks for effective learning, Coll,, abs/16008 1609..90090, 2016. URL http://arxiv.org// org/9//66///9999 09025
Christopher D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3))203 230, Mar 2011. ISSN 1573-7470. doi: 10.1007 s10472-011-9258-6 URL https: org/10 10010000000001010010000-------00 0220-11--99266
Nicholas J Russell, Levon Chakhmakhchyan, Jeremy O'Brien, and Anthony Laing. Direct dialling of haar random unitary matrices. New Journal of Physics, 19(3)0033007, 2017.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In Francis Bach and David Blei, editors, Proceedings of the 32nd In- ternational Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1312 1320, Lille, France, 07-09 Jul 2015. PMLR. URL html
http://proceeding. mlr. wttp://nnw.mmr..pees/eaaaa.
Jurgen Schmidhuber. Evolutionary principles in self-referential learning. learning now Diploma thesis, Technische Universitat Munchen, Germany, 14 May 1987. URL http:://ww: idsia. whtp:h/hegee/eipllleeeeeee html
to learn: The meta-meta-meta....
11

---

Published as a conference paper at ICLR 2022
Jürgen Schmidhuber. Optimal ordered problem solver. CoRR, Cs.AI/0207097, 2002. URL
https::/arxiv..om http://xxxv...rgaabbo CS20777
Jürgen Schmidhuber. Gödel Machines: Pully Self-referentidl Optimal Universal Self-improvers,
pages 199 226. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. ISBN 978-3-
5-10-68677-4.
doi: 0007779788-3-40--6677--7-7 7. URL https: org/10.1007/
116-3-540-68667-44
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, llya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587): 484-489, Jamuary 2016. doi: (0.1038/nature110 6961.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Anlonogion, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. CoRR, (bs/1712.018155 2017a. URL
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550(7676):354 359. Oct 2017b. ISSN 1476-4687. doi: 10.1038 n24.r224702. URL https://doo. or./ nature24270
Richard Sutton, Andrew G Barto, al. Reinforcement learning: An introduction. MIT press, 1998.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RS /SSJ International Conference on Intelligent Robots and Systems, pages 5026 5033, 2012. doi: 10.1109 LL.09/IROS.2012.63880000
12

---

Published as a conference paper at ICLR 2022
Table 1: List of the hyperparameters and their values used in all environments.
Hyperparameter
Value
Optimizer
Adam
Cact
2.0
Discount factor
0.999
Episodes per epoch
50
A ADDITIONAL DESCRIPTION OF ALPHAZEROHER
In this appendix, we present the psendocode of AlphaZerofERR in Algorithm [ We notice that the main loop of AlphaZero, where target values are generated from the policy targets given from MCTS and the Monte Carlo returns observed during the episodes, are extended with set of additional experiences, based on the secondary goal states. In our implemen- tation, the goal states are sampled uniformly from the states visited during each episode.
Algorithm 1: AlphaZeroHER
Initialize memory buffer
Initialize policy Te and value network vy for epoch = 1,.... N do
for episode 1,.... .M do
experiences < 0
9t ~ 4 while not done do
// Sample initial state
Pt, 0e + MCTS(s no, vo) St+1, done t appllActiin((0))
experiences t experiences U Pt.re)
f 81+1
end
Store every experience (st. Pt. 2t) in B, where 2 -E-r for l in episode experiences do
// Cenerate new experiences
G t Sample goals from future visited states 8, where j for in G do
r + r(r, g)
end
Store every (st, Pt, = in B, where 2/ = -EE
end
update TT, according to Equation 4
end end
B EXPERIMENTAL APPENDIX
B.1 REPRODUCIBILITY DETAILS
In this section, we provide the hyper-parameters employed in the experiments presented in this work. Table [ and Table provide list of hyperparameters employed for both AlphaZero and AlphaZeroHER, without being optimized. We ran each experiment in single multi-core machine, with no GPUs.
B.2 VARYING THE NUMBER OF SUBGOALS SAMPLED
In this section, study the effect of increasing the number of sampled subgoals in Alp- haZeroHER. Figure 7 and Figure 3 show the results of varying the number subgoal in the Flip and umantum compiling environments respectively. We that in both
13

---

Published as a conference paper at ICLR 2022
Table 2: List of the hyperparameters and their values used in each environment.
Hyperparameter
Environment
Value
BitPlip
0.0005
Learning rate
2D Navigation
0.001
2D Maze
0.0005
Quantum Compiling
0.00005
BitFlip
256
Batch size
2D Navigation
512
2D Maze
512
Quantum Compiling
512
BitFlip
20
Search Iterations
2D Navigation
2D Maze
120
Quantum Compiling
20
100
Salved Epicodes (%)
Average Return
-60
-70
-80
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Epoch
1e1
Epoch
1e1
Figure 7: Varying the number of subgoals in the BitFlip environment. Average of 10 runs, 95% c.i..
enviroments the performance increases as we increase the number subgoals k, until we reach (problem dependend) threshold after which the performance starts falling until it reaches the lower levels when we use as subgoals, all the available ones (label All
This is in line with the results presented in the original HER paper (Andrychowicz al. 2017).
B.3 COMPARISON WITH DQN HER
In this section, compared the proposed AlphaZeroHER with DQN-HE HER used in the original HER paper. The goal this experiment is to answer whether using HER in a MCTS method like AlphaZero needed, using "more traditional" HER implementations
-175
100
Selved Episades (96)
Average Raturn
-225
-275
0
Epoch
1e1
Epoch
lel
Figure 8: Varying the number of subgoals the quantum compiling environment. Average of 10 runs, 95% c.i..
14

---

Published as a conference paper at ICLR 2022
Table 3: List of the hyperparameters and their values used in DQN+ HER for each environ- ment.
Hyperparameter
Environment
Value
BitFlip
100
Target not update frequency
2D Navigation
500
Quantum Compiling
500
BitFlip
0.21
Final exploration epsilon
2D Navigation
0.21
Quantum Compiling
0.15
BitFlip
Train Frequency
2D Navigation
4
Quantum Compiling
BitFlip
0.00064
Learning Rate
2D Navigation
0.0007
Quantum Compiling
0.00022
BitFlip
32
Batch Size
2D Navigation
128
Quantum Compiling
64
BitFlip
500000
Buffer Size
2D Navigation
1000000
Quant Compiling
1000000
-20
100
-30
60 bits
60
bits
Averoge Return
70 bits
80
-40
Solved Episodes
-50
-60
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Epoch
1e2
Epoch
1e2
Figure 9: Performance of DQN+ in Bitflip by varying the number of bits. Average of
runs, 95% c.i..
like DQN was enough solve the considered environments. We use the implementation of DQN and HER given from stable-baselines ! To make the comparison fair, we first employed the same network architecture used by our agents. However, except for the bitflip domains of less than 20 bits, the DQN agents could not solve any of the domains. For this reason, in the following results, we have employed a more complex network architecture for all domains (except Maze where use the same CNN), namely MLP with single hidden layer of 128 neurons. We optimized the DQN hyperparameters using hyperop The best. hyperparameters used in all domains listed in Table 3 It. worth noting that the hyperparameters for AlphaZero and A AlphaZeroHer presented in Section were not tuned.
Figure shows the results of DQN DQN-HER in the Bitflip domain for different numbers of bits. We used four additional subgoals like in the AlphaZero case but a more complex network architecture. We can reproduce the results presented in the HER paper, as the top-performing policies solve the problems 100% of the time. When comparing the average performance, though, HER still performs worse than AlphaZeroHER, only solving on average 80% of the episodes to 60 bits, and even less when increasing to 70 bits.
http:///yperropt.itthu wtw.rropptttttttt..ee.o htt.tthhub...o/pypooo..///
15

---

Published as a conference paper at ICLR 2022
DON+HER
DON+HER
Solved Episodes, (%)
Average Reburn
-200
-225
-250
40
20
-300
0.75
1.50
1.00
Epoch
1e2
Figure 10: Performance of DQN HER in QC using additional subgoals. Average of 5 runs, 95% c.i..
+ON+
-105
Salved Episades (16)
Average Return
-190
-195
-200
-205
0.0
0.5
1.0
1.5
2.0 Epoch
2.5
3.0
3.5
4.0
2.5
3.5
1e2
Epoch
Figure 11: Performance of DQN+HER in the 2D navigation task. Average of runs, 95% c.i..
We also achieved satisfactory results in the quantum compiling domain, solving around 80% of the episodes within the given horizon, yet still less than the 95% achieved from the AlphaZeroHERR agent presented in Section Figure shows the performance in this domain. There, a more complex network structure was needed to achieve this performance too. DQN+HER starts to fail in the 2D navigation task. Figure [1 presents the results in this domain. Even after tuning the DQN parameters, we only can achieve around 5% of solved episodes on average, in contrast. to 80% achieved by AlphaZeroHEER Finally, in the Mase domain, even after luning, DQN- HER could not resolve single episode of the task against the 60% solve rate of AlphaZeroHER.
16


Reviews:
[{"review_id": "nkyJZv7CG_O", "reviewer": "Reviewer_mGXi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nPerhaps 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.\n\nSmaller comments and suggestions for clarity:\n- 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.\n- 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Y7XZrw8AsZQ", "reviewer": "Reviewer_1k2M", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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? \n\nThe paper is clear. \n\nIn 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.\n\nAfter 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. \n\nAbout 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_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. ", "summary_of_the_review": "The paper makes a relatively small technical and empirical contribution given existing results on HER (Andrychowicz et al., NeurIPS 2017). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SEru52jBRNQ", "reviewer": "Reviewer_Eiby", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n* 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.\n* In this paper, M subgoals are sampled for training. Why not all subgoals? An experiment on this is requested. \n* For goal-directed problems, the author should also reference the following work. \nStephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's Cube with Approximate Policy Iteration, ICLR 2019.\n\nSome minor comments: \n* In the BitFlip experiment, how many steps does the environment for AlphaZero/AlphaZeroHER interrupt during self-play? \n* In Page 5, What is \"tree-s\"? \n* Keep the terminology consistent, say goal-directed and goal-oriented. And, also for neurons, nodes, and units. \n* 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$\n", "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.\n", "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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JihENUCs5l1", "reviewer": "Reviewer_37RQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n**Strengths:**\n\nThe 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.\n\nThe 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.\n\nThe results provided are clear and show that this approach can confer significant benefit over AlphaZero in a reward sparse setting.\n\n\n**Weaknesses:**\n\nMore 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.\n\nIt 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?\n\nWhile 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.\n\nIt 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?\n\nHow close are the presented results close to optimal scores in their respective environments?\n\nHow exactly are subgoals selected?  Could more details be provided?  Are they simply sampled randomly?", "summary_of_the_paper": "\nThe 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.\n\nIn 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.\n\nThe 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.\n\nMuch 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.\n\nThe 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.\n\n\n", "summary_of_the_review": "\nOverall 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.\n\nPost rebuttal:\n\nGiven 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.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)