Reinforcement Learning with Structured Hierarchical Grammar Representations of Actions
Authors: Petros Christodoulou
Robert Lange
Ali Shafti
A. Aldo Faisal
Venue:  (2020)
Keywords: Hierarchical Reinforcement Learning
Action Representations
Macro-Actions
Action Grammars

Abstract: From a young age humans learn to use grammatical principles to hierarchically combine words into sentences. Action grammars is the parallel idea; that there is an underlying set of rules (a "grammar") that govern how we hierarchically combine actions to form new, more complex actions. We introduce the Action Grammar Reinforcement Learning (AG-RL) framework which leverages the concept of action grammars to consistently improve the sample efficiency of Reinforcement Learning agents. AG-RL works by using a grammar inference algorithm to infer the “action grammar" of an agent midway through training, leading to a higher-level action representation. The agent's action space is then augmented with macro-actions identified by the grammar. We apply this framework to Double Deep Q-Learning (AG-DDQN) and a discrete action version of Soft Actor-Critic (AG-SAC) and find that it improves performance in 8 out of 8 tested Atari games (median +31%, max +668%) and 19 out of 20 tested Atari games (median +96%, maximum +3,756%) respectively without substantive hyperparameter tuning. We also show that AG-SAC beats the model-free state-of-the-art for sample efficiency in 17 out of the 20 tested Atari games (median +62%, maximum +13,140%), again without substantive hyperparameter tuning.

Under review as a conference paper at ICLR 2019
REINFORCEMENT LEARNING WITH STRUCTURED HI- ERARCHICAL GRAMMAR REPRESENTATIONS OF AC- TIONS
Anonymous authors Paper under double-bling brinnd review
ABSTRACT
From a young age we learn to use grammatical principles to hierarchically com- bine words into sentences. Action grammars is the parallel idea, that there is an underlying set of rules (a grammar) that govern how we hierarchically combine actions to form new, more complex actions. We introduce the Action Grammar Reinforcement Learning (AG-RL) framework which leverages the concept of ac- tion grammars consistently improve the sample efficiency of Reinforcement Learning agents. AG-RL works by using grammar inference algorithm to in- fer the action grammar of an agent midway through training. The agent's action space is then augmented with macro-actions identified by the grammar. We apply this framework to Double Deep Q-Learning (AG-DDQN) and a discrete action version of Soft Actor-Critie (AG-SAC) and find that it improves performance in 8 out of tested Atari games (median +31%, max +668%) and 19 out of 20 tested Atari games (median +96%, maximum +3, +3,756%) respectively without substantive hyperparameter tuning. We also show that AG-SAC beats the model-free state-of- aht for sample efficiency in 17 out of the 20 tested Atari games (median +62%, maximum + +13,140% again without substantive hyperparameter tuning.
INTRODUCTION
Reinforcement I Learning (RI.) has made great progress in recent years, successfully being applied to settings such as board games (Silver et al. 2017), video games (Mnih et al., 2015) and robot tasks (OpenAl et al.) 2018). Some of this advance is due to the use of deep learning techniques to avoid induction biases in the mapping of sensory information to states. However, widespread adoption of RL in real-world domains has remained limited primarily because of its poor sample efficiency, dominant concern in RL (Wu et al. 2017). and complexity of the training process that need to be managed by various heuristies.
Hicrarchical Reinforcement Learning (HRL) attempts to improve the sample efficiency of RL agents by making their policies to be hierarchical rather than single level. Using hierarchical policies can lead not only to faster learning, but also ease human understanding of the agent's is hehaviour - this because higher-level action representations are easier to understand than low-level ones (Beyret eet al. 2019). Identifying the right hierarchical policy structure is, however a non-trivial task (Osa al. 2019) and so far progress in hierarchical RL has been slow and incomplete, as no truly scalable and successful hierarchical architectures exist /Vezhnevets et al. 2016). Not surprisingly most state- of-the-art RL agents the moment are not hierarchical.
In contrast, humans, use hierarchical grammatical principles to communicate using spoken/writtenn written language (Ding et al. 2012) but also for forming meaningful abstractions when interacting with var- ious entities. In the language case, for example, to construct valid sentence we generally combine a noun phrase with a verb phrase (Yule) 2015). Action grammars are an analogous idea proposing there is underlying set of rules for how we hierarchically combine actions over time to produce new actions. There is growing neuroscientific evidence that the brain uses similar processing strate- gies for both language and action, meaning that grammatical principles are used in both neural repre- sentations of language and action (Faisal et al., 2010;) Hecht et al.) 2015 Pastra & Aloimonos 2012). We hypothesise that using action grammars would allow to form hierarchical action represen-

---

Under review as a conference paper at ICLR 2019
tation that we could use to accelerate learning. Additionally, in light of the neuroscientific findings, hierarchical structures action may also explain the interpretability of hierarchical RL agents, as their representations are structurally more similar to how humans structure tasks. In the following we will explore the use of grammar inference techniques to form a hierarchical representation of actions that agents can operate on. Just like much of Deep RL has focused on forming unbiased sensory representations from data-driven agent experience, here we explore how data-driven agent experience of actions can contribute forming efficient representations for learning and controlling tasks.
Action Grammar Reinforcement Learning (AG-RL) operates by using the observed actions of the agent within a time window to infer an action grammar. We use grammar inference algorithm to substitute repeated patterns of primitive actions (i.e. words) into temporal abstractions (rules, anal- ogous to a sentence). Similarly, we then replace repeatedly occurring rules of temporal abstractions with higher-level rules of temporal abstractions (analogous to paragraphs), and so forth. These ex- tracted action grammars (the set of rules, rules of rules, rules of rules of rules, etc) is appended to the agent's 's action set in the form of macro-actions so that agents can choose (and evaluate) primitive actions well any of the action grammar rules. We show that AG-RL L is able consistently and significantly improve sample efficiency across a wide range of Atari settings.
2 RELATED WORK
Our concept of action grammars that act as efficient representations of actions is both related to and different from existing work in the domain of Hierarchical Control. Hierarchical control of temporally-extendee actions allows RL agents constrain the dimensionality of the temporal credit assignment problem. Instead of having to make an action choice at every tick of the environment, the top-level policy selects a lower-level policy that executes actions for potentially multiple time- steps. Once the lower-level policy finishes execution, it returns control back to top-level policy. Identification of suitable low level sub-policies poses a key challenge HRI.
Current approaches can be grouped into three main pillars: Graph theoretic (Hengst 2002 Man- nor et al. 2004; [Simsek al. (004) and visitation- (Stolle & Precup 2002; Simsek et al. 2004) approaches aim to identify "bottlenecks" within the state space. Bottlenecks are regions in the state space which characterize successful trajectories. Our work, on the other hand, identi- fies patterns solely in the action space and does not rely reward-less exploration of the state space. Furthermore, our action grammar framework defines a set of macro-actions as opposed to full option-specific sub-policies. Thereby, it is less expressive but more sample-efficient infer.
Gradient- approaches, on the other hand, discover parametrized temporally-exterr extendde actions by iteratively optimizing objective function such as the estimated expected value of the log like- lihood of the observed data under the current policy with respect to the latent variables in a proba- bilistic setting (Daniel al. (016)) the expected cumulative reward in a policy gradient context (Bacon et al., 2017; Smith et al. 2018). Our action grammar induction, on the other hand, infers pat- terns without supervision solely based on a compression objective. The resulting parse tree provides an interpretable structure for the distilled skill set.
Furthermore, recent approaches in macro-action discovery (Vezhnevets al. 2017: Florensa al., 2017) attempt to split the goal declaration and goal achievement across different stages and layers of the learned architecture. Thus, while hierarchical construction of goals follows set of coded rules, our action grammars are inferred entirely data-driven based on agent experience. Usually, the top level of the hierarchy specifies goals in the environment while the lower levels have achieve them. Again, such architectures lack sample efficiency and casy interpretation. Our context- free grammar-base approach, on the other hand, is a symbolic method that requires few rollout traces and generalizes more difficult task-set
Finally, unlike recent work on unifying symbolic and connectionist methods, we do not aim to discover relationships between entities (Garnelo et al. 2016 Zambaldi et al. (018). Instead our proposed action grammar framework achieves interpretability by extracting hierarchical subroutines associated with sub-goal achievements (Beyret et al. 2019).
2

---

Under review as a conference paper at ICLR 2019
3 METHODOLOGY
The Action Grammar Reinforcement Learning framework operates by having the agent repeatedly iterate through two steps (as laid out in Figure T
(A) Gather Experience: the base off policy RL agent interacts with the environment and stores its experiences
B Identify Action Grammar: the experiences are used to identify the agent's action gram- mar which is then appended to the agent's action set in the form of macro-actions
Identify Action
(A) Gather Experience
Gather Experience
Grammar
For episodes to N1
For episodes N1 to N2
Agent
Environment
Action A2
Agent (Action
Environment
(Action aet
Action
Sans eqAnAAGs
Sen ropanons
expeiiece
sspedence
Roplay Butfer
Experiences
Grammar Calculator
Raplay
Experiences
Figure The high-level steps involved in the AG-RL algorithm. In the first Gather Experience step the base agent interacts as normal with the environment for N1 episodes. Then we feed the experiences of the agent to a grammar calculator which outputs aacronactions that get appended to the action set. The agent starts interacting with the environment again with this updated action set. This process repeats many times as required, as set through hyperparameters.
During the first Gather Experience step of the game the base RL agent plays normally in the environment for some set number of episodes. The only difference that during this time we occasionally run an episode of the game with all random exploration turned off and store these experiences separately. We do this because we will later use these experiences to identify the action grammar and so we do not want them to be influenced by noise. See left part of Figure
After some set number of episodes we pause the agent's interaction with the environment and enter the first Identify Action Grammar stage, see middle part of Figure [ This firstly involves col- lecting the actions used in the best performing of the no-exploration episodes mentioned above. We then feed these actions into grammar calculator which identifies the action grammar. A simple choice for the grammar calculator is Sequitur Seevill-Manning & Witten 1997). Sequitur receives a sequence of actions as input and then iteratively creates new symbols to replace any repeating sub- sequences of actions. These newly created symbols then represent the macro-actions of the action grammar. To minimise the influence of noise on grammar generation, however, need to regularise the process. A naive regulariser is k-Sequitur (Stout et al. 2018) which is version of Sequitur that only creates new symbol if sub-sequence repeats at least k times (instead of at least two times), where higher & corresponds to stronger regularisation. Here we use more principled approach and regularise on the basis of an information theoretic criterion: we generate new symbol doing so reduces the total amount of information needed to encode the sequence.
After we have identified the action grammar we enter our second Gather Experience step. This firstly involves appending the macro-actions in the action grammar to the agent's 's action set. To do this without destroying what our nenetwork and/or policy has already learned we use transfer learning. For every new macro-action we add all other nodes and weights unchanged. We also initialise the weights of cach new node to the weights of their first primitive action (as it is this action that is most likely to have similar action value to the macro-action). e.g. if the primitive actions are {a, b} and we are adding macro-action abb then we initialise the weights of the new macro-action to those of a.
node to the final layer of the network, leaving
Then our agent begins interacting with the environment as normal but with an action set that now includes macro-actions and four additional changes:
3

---

Under review as a conference paper at ICLR 2019
1) In order to maximise information efficiency, when storing experiences from this stage onwards use a new technique we call Hindsight Action Replay (HAR). is related to Hindsight Experience Replay which creates new experiences by reimagining the goals the agent was trying achieve. Instead of reimagining the goals, HAR creates new experiences by reimagining the actions. In particular it reimagines them in two ways:
1. If we play a macro-action then we also store the experiences as we had played the se- quence of primitive actions individually
2. If we play a sequence of primitive actions that matches an existing macro-action then also store the experiences as if we had played the macro-action
See Appendix A for example of how HAR is able more than double the number of collected experiences in some cases.
ii) To make sure that the longer macro-actions receive enough attention while learning, sample experiences from an action balanced replay buffer. This acts as a normal replay buffer except returns samples of experiences containing equal amounts of each action.
iii) To reduce the variance involved in using long macro-actions we develop a new technique called Abandon Ship. During every timestep of conducting a macro-action calculate how much worse it is for the agent to continue executing its macro-action compared to abandoning the macro-action and picking the highest value primitive action instead. Formally we calculate this value as
1 exp(4m) where 7m is the action value of the primitive action we are conducting as part of the macro-action and Qhighest is the action value of the primitive action with the highest action value. We also store the moving average, m(d), and moving standard deviation, sld(d), of d. Then each timestep we compare dl to threshold / mmd) sld(d)= where is the abandon ship hyperparameter that determines how often we will abandon macro-actions. If d > then we abandon our macro- action and return control back to the policy, otherwise continue executing the macro-action.
oxp(Aiigheat)
Algorithm AG-RL
1: Initialise environment env, base RL algorithm R, replay buffer D and action set A
2: for each iteration do
3: F <- GATHER EXPERIENCE(A)
4: A f- IDENTIFY ACTION GRAMMAR(R
5:
6: procedure ENTHER.EXPERIEENEE
7: transfer learning(A)
>> If action set changed do transfer learning b Initialise F to store no-exploration episode experiences
8: F <-0 0
9:
for each episode do
10:
no exploration time then turn off exploration
> Periodically turn off exploration D Initialise E to store an episode's experiences
11:
E. +- 0
while not done do ma, a.ppck_action(s;) for a, in ma, do if abandon
13:
> Pick next primitive action / macro-action b Iterate through each primitive action the macro-action Abandon macro-action if required
14:
15:
a4) then break St+1. Tr+1, de+1 = env.step(a.) F EU {(1t, 0r, F141, 8441, (4+44)
> Play action in environment Store the episode's 's experiences & Learning iteration for base RI. algorithm b Use HAR when updating replay buffer Store no-exploration experiences
17:
R.learn(D)
19:
D t- D HAR(E)
20:
if no exploration time then F FUE
return
22:
23:
procedure
24:
Keep only the best performing no-exploration episodes action grammar +- grammar algorithm(F)
F extract_best.c extract.best.episodees/
25:
& Infer action grammar using experiences & Update the action set with identified macro-actions
26:
A A action grammar
27:
return

---

Under review as a conference paper at ICLR 2019
iv) When our agent is picking random exploration moves we bias its choices towards macro-actions. For example, when a DQN agent picks a random move (which it does epsilon proportion of the time) set the probability that it will pick macro-action, rather than primitive action, to the higher probability given by the hyperraarameter "Macro Action Exploration Bonus". In these cases, we do not Abandon Ship and instead let the macro-actions fully roll out.
The second Gather Experience step then continues until it is time to do another Identify Action Grammar step or until the agent has been trained for long enough and the game ends. Algorithm provides the full AG-RL algorithm.
SIMPLE EXAMPLE
We now highlight the core aspects of how AG-RL works using the simple game Towers of Hanoi. The game starts with a set of disks placed on a rod in decreasing size order. The objective of the game is move the entire stack to another rod while obeying the following rules: i) Only one disk can be moved at a time; ii) Each move consists of taking the upper disk from one of the stacks and placing on top of another stack or on an empty rod; and iii) No larger disk may be placed on top of a smaller disk. The agent only receives reward when the game is solved, meaning rewards are sparse and that it is difficult for an RL. agent to learn the solution. Figure Figure[]rum runs through an example of how the game can be solved with the letters 'a" to 'f" being used to represent the 6 possible moves in the game.
In this game, AG-RL proceeds by having the base agent (which can be any off-policy RL agent) play the game as normal. After some period of time we pause the agent and collect some of the actions taken by the agent, c.g. say the agent played the sequence of actions: "bafbedbbafecfeef bedbefecdbafheed... Then we use a grammar induction algorithm such as Sequitur to create new symbols represent repeating sub-sequences. In this example, Sequitur would create the 4 new symbols: {G be, H ec, I : baf. : bbccc. We then append these symbols to the agent's 's action set as macro-actions, that the action set goes from A {a, b, c, d, e, f to:
A= {a, b, c, d,e, e, U bbc, ec, bas, baffddd
The agent then continues playing in the environment with this new action which includes macro- actions. Because the macro-actions are of length greater than one it means that their usage effectively reduces the time dimensionality of the problem, making an easier problem solve in some cases
We now demonstrate the ability of AG-RL to consistently improve sample efficiency on the much more complicated Atari suite setting.
Initial State: (1 1)
State 1: (3 1913)) D
State (32 +
(2.2 +
1b' (1.3)
(1.2)
Scate (2.33
State & (1 23)
State (1 +
Final (3 +100
l (2.1)
(1.3)
(13)
Figure Example a solution to the Towers of Hanoi game. Letters a to represent the 6 different possible moves. After 7 moves the agent has solved the game and receives +100 reward.
5 RESULTS
We first evaluate the AG-RL framework using DDQN as the base RL algorithm. We refer to this as AG-DDQN. We compare the performance of AG-DDQN and DDQN after training for 350,000 steps on 8 Atari games chosen a priori to represent broad range. To accelerate training times for both we set their convolutional layer weights as equal those of some pre-trained agent and then only train the fully connected layers.
Experimental results for this simplified setting may he found in section of the appendix. We used the pre-trained agents in the GitHub repository rl-haselines-zoo http://githuh..om/aaafffiiii haselineszzao/tre/mastrrrrtiii agents/dqn
5

---

Under review as a conference paper at ICLR 2019
300
DCON
300
1000-
000
420
600
100
250
50-
200
400
100
200
300
100
202
100
200
300
102
208
100
Shaps (thossnnds)
Tranking Stepe
Trakiig Steyss (hhoroodd))
Trokning Steps
Pong
Space Inveders
MsPacmen
Seaquest
200
5are
0-
200-
1820
323
150
17%
150
500
102
25
-20
100
200
300
1000
202
300
200
320
102
200
300
Training Stape (thousnnds)
Training Stops (hrcusardh)
Thamiin Steps (thomaadd))
Training Steps (housendss
Figure 3: Comparing AG-DDQN to DDQN for 8 Atari games. Graphs show the average evaluation score over 5 random seeds where an evaluation score is calculated every 25,000 steps and averaged over the previous 3 scores. For the evaluation methodology we used the same no-ops condition as in van Hasselt et al. (2015). The shaded area shows =1 standard deviation.
For the DDQN-specific hyperparameters of both networks we do no hyperparameter tuning and instead use the hyperparmacters from van Hasselt et al. (2015) or set them manually. For the AG- specific hyperparameters we tried four options for the abandon ship hyperparameter (No Abandon Ship, 1, 2, 3) for the game Qbert and chose the option with the highest score. No other hyperpa- rameters were tuned and all games then used the same hyperparameters which can all be found in Appendix B along with a more detailed description of the experimental setup.
We find that AG-DDQN oulperforms DDQN in all 8 games with median final improvement of 31 % and a maximum final improvement of 668% Figure summarises the results.
Next we further evaluate AG-RL by using SAC as the base RL algorithm, leading to AG-SAC. We compare the performance of AG-SAC to SAC. We train both algorithms for 100,000 steps on 20 Atari games chosen a priori to represent broad range games. As SAC is much more efficient algorithm than DDQN this time we train both agents from scratch and do not use pre- pre-trained convo- lutional layers.
For the SAC-specific hyperparameters of both networks we did no hyperparameter tuning and in- stead used mixture of the hyperparameters found in Haarnoja al. (2018) and[Kr al. (2019). For the AG-specific hyperparmaeters again the only tuning we did was amongst 4 options for the abandon ship hyperparameter (No Abandon Ship, 1, 2, 3) on the game Qbert. No other hyperparam- eters were tuned and all games then used the same hyperparameters, details of which can be found in Appendix C
Our results show AG-SAC outperforms SAC in 19 out of 20 games with a median improvement of 96% and a maximum improvement of 3,756% Figure 4 summarises the results and Appendix D provides them in more detail.
We also find that AG-SAC outperforms Rainbow, which is the model-free state-of-the-art for Atari sample efficiency, in 17 out of 20 games with a median improvement of 62% and maximum improve- ment of 13.140% taken from Kaiser et al. (2019) who explain they were the result of extensive hyperparameter tuning compared to our AG-SAC scores which benefited from very little hyperparameter tuning.
see Appendix (eaddixDfor for more details. Also note that the Rainbow scores used were
6 DISCUSSION
To better understand the results, we first explore what types of macro-actions get identified during the Identify Action Grammar stage, whether the agents use them extensively not, and to what extent the Abandon Ship technique plays a role. We find that the length of macro-actions can vary greatly from length 2 to over 100. An example of an inferred macro-action 8888/ // 18888/111

---

Under review as a conference paper at ICLR 2019
AG-SAC SAC Relative Performance
Enduro
+3756%
Amidar
+617%
UpNDown
+594%
Road
+512%
Frostblte
+3255%
Freeway
+-199%
Kangaroo
+136%
Pong
+133%
Breakout
+107%
Crazy Climber
+105%
Space Invaders
+87%
Asterix
+699%
Allen
Assault
+400%
Obert
BattleZone
+25%
Seaquest
Beam Rider
+7%
MsPacman
JamesBond
-3%
100
100
200
300 400 500 600 700
800
900
1000
Relative Performance
Figure 4: Comparing AG-SAC to SAC for 20 Atari games. Graphs show the average evaluation score over random seeds where an evaluation score is calculated at the end of 100,000 steps of training. For the evaluation methodology used the same no-ops condition as in van Hasselt et al. (2015).
from the game Beam Rider where I represents Shoot and represents move Down-Right. This macro-action seems particularly useful in this game as the game is about shooting enemies whilst avoiding being hit by them.
Hindsight Action Replay Ablation Study
Action Balanced Replay Buffer Ablation Study
Score
400
Score
400
200
Without Hindsight Action Replay With Hindsight Action Replay
200
With Action Balanced Replay Buffer No Action Balanced Replay Buffer DDQN
DDQN
50
100
150
200
250
300
100
150
200
250
300
Training Steps (thousands)
Training Steps (thousands)
Abandon Ship Ablation Study
Transfer Learning Ablation Study
700
600
600
500
Score
400
Score
400
Abandon Ship: 3.0
300
Abandon Ship: 2.0
200
Abandon Ship: 1.0
200
Without Transfer Learning With Transfer Learning DDQN
No Abandon Ship
100
DDQN
50
100
150
200
250
300
100
150
200
250
300
Training Steps (thousands)
Training Steps (thousands)
Figure Ablation study comparing DDQN to different versions of AG-DDQN for the game Qbert. The dark line the average 5 random seeds, shaded area shows +1 standard deviation across seeds.
We also found that the agents made extensive use of the macro-actions. Taking each game's best performing AG-SAC agent, the average atlempted move length during evaluation was 20.0. Because

---

Under review as a conference paper at ICLR 2019
of Abandon Ship the average executed move length was significantly lower at 6.9 but still far above the average of 1.0 we would get the agents were not using their macro- -cctoon Appendix gives more details the differences in move lengths between games.
We now conduct an ablation study to investigate the main drivers of AG-DDQN's performance the game Qbert, with results in Figure 5 Firstly find that HAR erucial for the improved perfor- mance and without it AG-DDQN performed no better than DDQN. We suspect that this is because without HAR there are much fewer experiences learn from and so our action value estimates have very high variance.
Next find that using an action balanced replay buffer improved performance somewhat but by a much smaller and potentially insignificant amount. This potentially implies that it may not be necessary to use an action balanced replay and that the technique may work with an ordinary replay buffer. We also see that with our chosen abandon ship hyperparameter of 1.0, performance was higher than when abandon ship was not used. Performance was also similar for the choice of 2.0 which suggests performance was not too sensitive to this choice of hyperparameter. Finally see improved performance from using transfer learning when appending macro-actions to the agent's action set rather than creating a new network.
Lastly, we note that the game which AG-DDQN and AG-SAC both do relatively best in Enduro. Enduro is game with sparse rewards and therefore one where exploration is very important. We therefore speculate that AG-RL does best on this game because using long macro-actions increases the variance of where agent can end up and therefore helps exploration.
CONCLUSION
Motivated by the parallels between the hierarchical composition of language and that of actions, we combine techniques from computational linguistics and RL to help develop the Action Grammars Reinforcement Learning framework.
The framework expands on two key areas of RL research: Symbolic RL and Hierarchical RL. We ex- tend the ideas of symbolic manipulation in RL (Garnelo et al. 2016 Garnelo & Shanahan (019)) to the dynamics of sequential action execution. Moreover, while Relational RL approaches (Zambaldi let al. 2018) draw the complex logic-based framework of inductive programming, merely observe successful behavioral sequences to induce higher order structures.
We provided two implementations of the framework: AG-DDQN and AG-SAC. We showed that AG-DDQN improves on DDQN out 8 tested Atari games (median +31%, max +668%) and AG-SAC improves SAC in 19 out of 20 tested Atari games (median +96%, +3,756%) all without substantive byperparameter tuning. We also show that AG-SAC beats the model-free state- of-the-art for 17 of 20 Atari games (median +62%, max 13,110%% terms of sample efficiency, again even without substantive hyperparameter tuning.
As part of AG-RL we also provided two new and generally applicable techniques: Hindsight Action Replay and Abandon Ship. Hindsight Action Replay can be used to drastically improve information efficiency any off-policy setting involving macro-actions. Abandon Ship reduces the variance involved when training macro-actions, making it feasible to train algorithms with very long macro- actions (over 100 steps in some cases).
Overall, we have demonstrated the power of action grammars to consistently improve the perfor- mance of RL agents. We believe our work is just one of many possible ways of incorporating the concept of action grammars into RL and we look forward to exploring other methods.
REFERENCES
Pierre-Lue Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In AAAI, pp. 1726 1734, 2017.
Benjamin Beyret, Ali Shafti, and Aldo Faisal. Dot-to-dot: Explainable hierarchical reinforcement learning for robotic manipulation. 2019.
8

---

Under review as a conference paper at ICLR 2019
Steven J Bradtke and Michael O Duff. Reinforcement learning methods for continuous-time markov decision problems. Advances in neural information processing systems, pp. 393 993-400, 1995.
Christian Daniel, Herke Van Hoof, Jan Peters, and Gerhard Neumann. Probabilistic inference for determining options in reinforcement learning. Machine Learning, 104(2-3)3337-55) 2016.
N. Ding, I.. Melloni, X. Tian, and D. Poeppel. Rule-based and word-level statistics-based processing of language: Insights from neuroscience. Philosophical Transactions of the Royal Society of London B: Biological Sciences, 2012.
Aldo Faisal, Dietrich Stout, Jan Apel, and Bruce Bradley, The manipulative complexity of lower palcolithic stone toolmaking. PloS one, 5(11))e13718, 2010.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical rein- forcement learning. arXiv preprint arXiv:1704.0300 2017.
Marta Garnelo and Murray Shanahan. Reconciling deep learning with symbolic artificial intelli- gence: representing objects and relations. Current Opinion in Behavioral Sciences, 29:17-23, 2019.
Marta Garnelo, Kai Arulkumaran, and Murray Shanahan. Towards deep symbolic reinforcement learning. arXiv preprint 1rXiv:1609.05578. 2016.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Schoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft actor-critic algo- rithms and applications. ArXiv, abs/1812.05900 2018.
Erin E Hecht, DA Gutman, Nada Khreisheh, SV Taylor, J Kilner, AA Faisal, BA Bradley, Thierry Chaminade, and Dietrich Stout. Acquisition of paleolithic toolmaking abilities involves structural remodeling inferior frontoparictal regions. Brain Structure and Function, 22044)3315--231, 2015.
Bernhard Hengst. Discovering hierarchy in reinforcement learning with hexq. In ICML, volume 2, pp. 243-250, 2002.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model-based reinforcement learning for atari. ArXiv, abs/1903.00374, 2019.
Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the twenty-first international conference on Machine learning, pp. 71. ACM, 2004.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529- 533, 2015.
C. Nevill-Manning and I. Witten. Identifying hierarchical structure in sequences: A linear-time algorithm. CoRR, 1997.
OpenAI, Marcin Andrychowicz, Bowen Baker, Maciek Chociej. Rafal Józefowicz, Bob McGrew, Jakub W. Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, Jonas Schnei- der, Szymon Sidor, Josh Tobin, Peter Welinder, Lilian Weng, and Wojciech Zaremba. Learning dexterous in-hand manipulation. ArXiv, htt//1888.001770 2018.
Osa, V. Tangkaratt, and M. Sugiyama. Hicrarchical reinforcement learning via advantage- weighted information maximization. International Conference Learning Representations, 2019.
Ronald Edward Parr. Hierarchical control and learning for Markov decision processes. University of California, Berkeley Berkeley, CA, 1998.

---

Under review as a conference paper at ICLR 2019
K. Pastra and Y. Aloimonos. The minimalist grammar of action. Philosophical Transactions the Royal Society of London Biological Sciences, 2012.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lynette R. Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lilli- crap, Hui-zhen Fan, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hass- abis. Mastering the game of go without human knowledge. Nature, 550:354 2017.
Ozgür Simsek, Alicia Wolfe, and Andrew G Barto. Local graph partitioning as a basis for gen- erating temporally-extended actions in reinforcement learning. In AAAI Workshop Proceedings, 2004.
Matthew Smith, Herke van Hoof, and Joelle Pineau. An inference- based policy gradient method for learning options. In Proceedings of the 35th International Conference Machine Learning, pp- 4710-4719, 2018.
Martin Stolle and Doina Precup. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and approximation, pp. 212-223. Springer, 2002.
Dietrich Stout, Thierry Chaminade, Andreas A. C. Thomik, Jan Apel, and Aldo Faisal. Grammars of action in human behavior and evolution. 2018.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. AAAI, 2015.
Alexander Vezhnevets, Volodymyr Mnih, John Agapiou, Simon Osindero, Alex Graves, Oriol Vinyals, and Koray Kavukcuoglu. Strategic attentive writer for learning macro-actions. NIPS, 2016.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. arXiv preprint 1703.0016,1 2017.
Yuhuai Wu, Elman Mansimov, Shun Liao, Roger B. Grosse, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation. In NIPS, 2017.
G. Yule. The Study of Language. Cambridge University Press, 2015.
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et Relational deep reinforcement learning, arXiv preprint arXiv: 10x.v:180..01830, 2018.
10

---

Under review as a conference paper at ICLR 2019
APPENDIX
A HINDSIGHT ACTION REPLAY
Below provide example of how HAR the experiences of an agent after they played the moves acab where a and b are primitive actions and represents the macro-action ababa.
Hindsight Action Replay for Action Set: (a, c: (abab))
Step Convert macro-attions to their primiiive actions
primitive experiences imagine that every occurance of macro actio's primiiiva actions was the macro action being chosen even it was not
Combine
states, rewards
spisode collect the actions played in that episode
terminal information to form experinces and store them the raplay buffer. For the macro actions follow the below ruics:
State - state start macro action execution
Next stats state wher maco-attion sosccutin
Reward sum of rowerds during maoro-actiee actionniiion execution Done terminal statis after macro ection wees,
a's: aababab
acab
aababab
b's: aababab
(etate, reward, nest atate, done) reward, done)
c's: acab and aabc
Replay Buffer
Figure 6: The Hindsight Action Replay (HAR) process with Action Set: {a, b, c: (abab)) meaning that there primitive actions and and macro-action which represents the sequence of primitive actions abab. example shows how using HAR leads original sequence actions acab producing experiences for the replay buffer instead of only 4.
11

---

Under review as a conference paper at ICLR 2019
B AG-DDQN EXPERIMENT AND HYPERPARAMETERS
The hyperparameters used for the DDQN results are given by Table 1 The network architecture was the same as in the original Deepmind Atari paper (Mnih al. 2015).
Table Hyperparameterss used for DDQN and AG-DDQN results
Hyperparameter
Value
Batch size
32
Replay buffer size
1,000,000
Discount rate
0.99
Steps per learning update
4
Learning iterations per round
1
Learning rate
0.0005
Optimizer
Adam
Weight Initialiser
He
Min Epsilon
0.1
Epsilon decay steps
1,000,000
Fixed network update frequency
10000
Loss
Huber
Clip rewards
Clip to [-1, +1]
Initial random steps
25,000
The architecture and hyperparameters used for the AG-DDQN results that are relevant to DDQN are the same as for DDQN and then the rest of the hyperparameters are given by Table
Table 2: Hyperparameters used for AG-DDQN results
Hyperparameter
Value
Description
The number of no explo- ration episodes we use in- fer the action grammar
Evaluation episodes
5
Replay buffer type
Action balanced
The type of replay buffer we use
The number of steps we run before inferring the action grammar
Steps before inferring grammar
75,001
The threshold for the aban- don ship algorithm
Abandon ship
1.0
How much more likely are to pick a macro-action than primitive action when acting randomly
Macro-action exploration bonus
4.0
12

---

Under review as a conference paper at ICLR 2019
C AG-SAC HYPERPARAMETERS
The hyperparameters used for the discrete SAC results are given by Table The network architec- ture for both the actor and the critic was the same in the original Deepmind Atari paper (Mnih) et al. 2015).
Table Hyperparameters used for SAC and AG-SAC results
Hyperparameter
Value
Batch size
64
Replay buffer size
1,000,000
Discount rate
0.99
Steps per learning update
4
Learning iterations per round
1
Learning rate
0.0003
Optimizer
Adam
Weight Initialiser
He
Fixed network update frequency
8000
Loss
Mean squared error Clip to [-1.
Clip rewards
Initial random steps
20,000
The architecture and hyperparameters used for the AG-SAC results that are relevant to SAC are the same as for SAC and then the rest of the hyperparameters are given by Table
Table 4: Hyperparameters used AG-SAC results
Hyperparameter
Value
Description
The number of no explo- ration episodes we use to in- fer the action grammar
Evaluation episodes
Replay buffer type
Action balanced
The type of replay buffer we
The number of steps we run before inferring the action grammar
Steps before inferring grammar
30,001
The threshold for the aban- don ship algorithm
Abandon ship
2.0
How much more likely we to pick macro-action than primitive action when acting randomly
Macro-action exploration bonus
4.0
The number of random steps we run immediately after updating the action set with new macro-actions
Post inference random steps
5,000
13

---

Under review as a conference paper at ICLR 2019
D SAC, AG-SAC AND RAINBOW ATARI RESULTS
Below we provide all SAC, AG-SAC and Rainbow results after running 100,000 iterations for random seeds. We that AG-SAC improves over SAC in 19 of 20 games (median improvement of 96%, maximum improvement of 3756%) and that AG-SAC improves over Rainbow in 17 out of 20 games (median improvement 62%, maximum improvement 13140%).
Table 5: SAC, AG-SAC and Rainhow results 20 Atari games. The result of 5 random seeds is shown with the standard deviation brackets, As benchmark we also provide a column indicating score an agent would get if it acted purely randomly.
Game
Random
Rainbow
SAC
AG-SAC
Enduro
0.0
0.53
0.8
30.1
(0.8)
(10.1)
Amidar
11.8
20.8
7.9
56.7
(5.1)
(15.4)
UpNDown
488.4
1346.3
250.7
1739.1
(176.5)
(835.8)
Road Runner
0.0
524.1
305.3
1868.7
(607 44)
(1658.3)
Frostbite
74.0
140.1
59.4
252.3
(16.3)
(79.8)
Freeway
0.0
0.1
4.4
13.2
(9.9)
(12.1)
Kangaroo
42.0
38.7
29.3
69.3
(55.1)
(80.4)
Pong
-20.4
-19.5
20.98
20.95
(0.0)
(0.1)
Breakout
0.9
3.3
0.7
1.5
(0.5)
(1.4)
Crazy Climber
7339.5
12558.3
3668.7
7510.0
(600.8)
(3898.7)
Space Invaders
148.0
135.1
160.8
301.0
(17.3)
(75.1)
Asterix
248.8
285.7
272.0
459.0
(33.3)
(101.2)
Alien
184.8
290.6
216.9
349.7
(43.0)
(33.4)
Assault
233.7
300.3
350.0
490.6
(40.0)
(119.0)
Qbert
166.1
235.6
280.5
359.7
(124.9)
(172.8)
BattleZone
2895.0
3363.5
4386.7
5486.7
(1163.0)
(1461.7)
Seaquest
61.1
206.3
211.6
261.9
(59.1)
(56.3)
Beam Rider
372.1
365.6
432.1
463.0
(44.0)
(219.1)
MsPacman
235.2
364.3
690.9
712.9
(1:1.8)
(191.5)
JamesBond
29.2
61.7
68.3
66.3
(26.2)
(19.4)
Note that the scores for Pong are negative and so calculate the proportional improvement for this game we first convert the scores to their increment over the minimum possible score. In Pong the minimum score -21.0 and so we first add 21 to all scores before calculating relative performance.
Also note that for Pong both AG-SAC and SAC perform worse than random. The improvement of AG-SAC over SAC for Pong therefore could be considered somewhat spurious result and poten- tially should be ignored. Note that there are no other games where AG-SAC performs worse than random though and so this issue contained to the game Pong.
14

---

Under review as a conference paper at ICLR 2019
E MACRO-ACTIONS AND ABANDON SHIP
Table 6: The lengths of moves attempted and executed in the best performing AG-SAC seed for each game. Executed move lengths being shorter than attempted move lengths indicates that the Abandon Ship technique used. The games ordered in terms of the percentage improvement AG-SAC saw over SAC with the first. game being game that saw the most improvement.
Game
Attempted Move Lengths
Executed Move Lengths
Executed Attempted
Enduro
14.8
12.0
81. %
Amidar
3.4
2.8
82.4%
UpNDown
16.4
11.6
71.0%
Road Runner
8.2
6.8
82.9%
Frostbite
2.0
2.0
100.0%
Freeway
15.8
15.2
96.2%
Kangaroo
2.1
1.5
73.8%
Breakout
7.9
2.2
27.8%
Crazy Climber
7.1
4.4
62.0%
Space Invaders
8.7
6.3
72.4%
Asterix
58.3
9.8
16.8%
Alien
13.1
11.6
88.5%
Assault
126.9
8.1
6.4%
Qbert
8.2
8.0
97.6%
Battle Zone
63.4
6.0
9.5%
Seaquest
14.0
8.6
61.4%
Beam Rider
12.2
5.8
47.5%
MsPacman
8.2
7.5
91.5%
Pong
8.4
6.5
77.4%
James Bond
1.3
1.2
97.8%
15

---

Under review as a conference paper at ICLR 2019
F ADDITIONAL EXPERIMENTS
The Towers Hanoi experiments depicted in the figure below are run with SMDP-Q-Leamiig. Let Tr.. > r denote the accumulated and discounted reward for executing macro. Tabular value estimates can then be updated using SMDP-Q-Leaming (Bradtke Duff 1995 Parr 1998 in model-free bootstrapping- based manner:
m)s, (1 a))(s, (Trm +y max Q(s', Q(s'mm')
m' m'EM
We do not make of HAR or "Abandon Ship" in these experiments and use the following hyper- parameters:
Tabular Action Grammar SMDP- SMDP-Q-Learnin Q-e-nni-LL-n Hyperparameters:
Hyperparameter
Value
Hyperparameter 0.95
Value
Learning rate
0.8
Discount factor y
Eligibility Trace À
Exploration
0.1
The (A) baseline shares all the hyperparameters apart from the eligibility trace À which is set to 0.1. We train the agents 300000 (5 disks) and 7000000 (6 disks) steps.
20
15
Episode Reward
10
5
-5
k-Sequitur G-Lexis
-10
-15
TD(A)
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
1 Iterations
x
Figure 7: Action Grammar Reinforcement Learning for Towers of Hanoi (5 Disk Environment). Red vertical lines correspond grammar updates.
16


Reviews:
[{"review_id": "rJeFXXNJcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes the use of macro (i.e. aggregated) actions to address reinforcement learning tasks. The inspiration presented is from hierarchical grammar representations, and the method is tested on a subset of Atari games. The paper is overall well written, although many paragraph demonstrate a level of polish inadequate for a top level submission (repetitions, typos, etc.).\nThe main idea pursued in the work is extremely interesting and with likely important implications to recent DRL. The concept though is far from new: a quick search for \"macro action reinforcement learning\" points to a NIPS '99 paper from J. Randlov, though on top of my mind there should be even older work on the topic.\nThe perspective proposed of considering macro actions as atoms in a grammar is certainly intriguing, but the work proposed does not develop the concept. The macro actions are identified as patterns in action sequences, then built in straight hierarchies, without any distinction in type of atoms nor any rule to effectively make up a grammar.\nThe related work section is extremely lacking, with no work older than 2016. The introduction presents more background, marginally older than that (up to 2012), when grammars make for an entire field of study with decades of history.\nThe process is interesting and incorporates plenty of useful experience, which I would personally be glad to see published, although in the current context is insufficient as stand-alone contribution.\nOn a more personal note, I suggest the authors not to get discouraged, as I strongly believe such an avenue of research is worthy investigating. A few research questions which I think should be asked are:\n- Are the agents actually learning to play the game? Just render the game with one of your best players. For example, achieving a score of 360 on Qbert barely takes constant down input, and the fact that comparable scores have been published before is of no support.\n- Are long action sequences always useful? For Qbert for example an average move length of 8 learned from an initial, untrained policy, is sufficient to get off the screen consistently. While the Abandon Ship protocol can mitigate this, the RL exploration phase is done by random action selection (consider explicit exploration instead), and the action space grows fast from the small initial 6 actions with the addition of all the macro actions, possibly limiting the exploration capability and biasing towards the use of longer macro actions even when sub-optimal.\n- Mitigate the claims. I would love to \"eventually help make RL a universally practical and useful tool in modern society\", but unfortunately I think no single contribution can today make such a claim.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1x8yFBCtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduced a way to combine actions into meta-actions through action grammar. The authors trained agents that executes both primitive actions and meta-actions, resulting in better performance on Atari games. Specifically, meta-actions are generated after a period of training from collected greedy action sequences by finding repeated sub-sequences of actions. Several tricks are used to speed up learning and to make the framework more flexible. The most effective one is HAR (hindsight action replay), without which the agent's performance reduces to that of the baseline.\n\nOverall, this paper could be a great contribution for the following reasons: \n1. The paper is well written, with clear performance advantages over the baseline. \n2. The paper provides a different perspective for HRL research, namely that we might not need to have a hierarchical policy to benefit from hierarchical actions that spans over many timesteps. \n3. From this paper's ablation study for HAR, it seems to suggest that even with similar experiences, one can get better performance by substituting actions with temporally abstracted actions, propagating value function errors further back in time. If so, this work can serve as a novel counterexample to the claim made in Nachum et al., 2019.\n\nThe authors may want to address the following:\n1. They may want to compare and contrast to other works in HRL that also does temporally abstracted actions. e.g. h-DQN, Feudal networks. Or even to repeating the same action N times-- a simple trick commonly used in Atari  -- which can be seen as a very naive form of action grammar.\n2. The main claim that having Action Grammar improves sample efficiency is not proved clearly. Apart from the ablation study, it's not immediately clear whether sticking to sub-sequence of actions are inherently beneficial for exploration, or that the agent somehow learned faster with the same set of samples collected.\n3. It seems that the algorithm may be the most effective in areas where a baseline algorithm can learn to perform at least some meaningful action sequences already. Otherwise the Action Grammar may not extract meaningful subsequences. Has the algorithm been tried on sparse-reward games?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BygCV9NAYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a method for learning macro-actions in a multi-step manner, where Sequitur, a grammar calculator, is leveraged together with an entropy-minimisation based strategy to find relevant macro-actions. The authors propose a system to bootstrap the weights of these macro-actions when increasing the policy's action space, and a system to increase the amount of data (and bias it towards macro-actions) used to learn a policy for when conditioned on this increased action-space. The authors test against a subset of the Arcade Learning Environment suite.\n\nOverall, I'm conflicted by this paper. On one hand, the framework is interesting, and their method involves the usage and exploration of quite a few nice ideas; on the other hand, (a) the quality of the scientific contribution is hard to judge considering the significant differences between the proposed baselines and and their methods, and (b) the experimental section doesn't provide a lot of qualitative analysis and signal wrt. each component.\n\nFurthermore, I have the following issues / questions:\n\n1. I'm not convinced that the usage of Sequitur to build the macro-actions is sufficient to declare this work novel wrt. other macro-action papers. Sequitur usage in this case seems to be particularly overkill, since ultimately all that the method seems to be doing is finding frequent sequences of actions, which can be done quite fast (at least given the amount of training steps) simply using search and pattern matching. From my point of view, there doesn't seem to be a lot in that work that exploits the fact that the macro-actions are constructed as a \"grammar\" (beyond, maybe, HAR)\n\n2. The Abandon Ship heuristics is effectively a fixed termination policy, which makes the entire setup somewhat similar to options. In this case, what is traded is learning complexity for a hyperparameter and a significant restriction in how the macro-actions terminate. Did you attempt to learn this function at all? Do you have any insights / experiments that might show how the heuristics behaves with changing values of $z$? Would it be possible to plot the distribution of attempted vs executed move lengths rather than then averages (since I doubt they would be normally distributed)?\n\n3. Given points 1 and 2, the literature review is lacking - there's a lot of prior work done on macro-actions in both RL and robotics (planning, HRI, ...) that goes well beyond the few recent papers mentioned by the authors, and I think it might be necessary to mention work on options where the termination function is structured / biased in some way.\n\n4. I have some doubt the experimental setup for DDQN fairly gives a fair assessment of the method. When using a pretrained features, the problem becomes significantly easier, and thus AG-DDQN potentially doesn't need to deal with the problem of learning extremely bad / noisy macro-actions. I would love to see the method trained for a more reasonable amount of frames without pre-training. Also, did the 8 / 20 atari games get chosen randomly, or were they picked based on some environment features?\n\n5. How do the Q-values for the policy evolve with training time? The proposed methods seem to somewhat imply that the action space grows unboundedly, which might seriously destroy the policy for tasks that require much longer training. Would it be possible to add a paragraph about how the policies evolve in at least some of these environments? Are macro-actions used most of the times after some full iterations? How many <learning -> action distillation> iterations are actually done in the current experiments?\n\nAt this point, I cannot recommend the acceptance of this work, however I'd be willing to reconsider my rating if the authors address the above points.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The topic of macro-actions/hierarchical RL is an important one and the perspective this paper takes on this topic by drawing parallels with action grammars is intriguing. However, some more work is needed to properly evaluate the significance. In particular, a better evaluation of the strengths and weaknesses of the method would improve this paper a lot.
Decision: Reject