Title: Construction of Macro Actions for Deep Reinforcement Learning

Abstract: Conventional deep reinforcement learning typically determines an appropriate primitive action at each timestep, which requires enormous amount of time and effort for learning an effective policy, especially in large and complex environments. To deal with the issue fundamentally, we incorporate macro actions, defined as sequences of primitive actions, into the primitive action space to form an augmented action space. The problem lies in how to find an appropriate macro action to augment the primitive action space. The agent using a proper augmented action space is able to jump to a farther state and thus speed up the exploration process as well as facilitate the learning procedure. In previous researches, macro actions are developed by mining the most frequently used action sequences or repeating previous actions. However, the most frequently used action sequences are extracted from a past policy, which may only reinforce the original behavior of that policy. On the other hand, repeating actions may limit the diversity of behaviors of the agent. Instead, we propose to construct macro actions by a genetic algorithm, which eliminates the dependency of the macro action derivation procedure from the past policies of the agent. Our approach appends a macro action to the primitive action space once at a time and evaluates whether the augmented action space leads to promising performance or not. We perform extensive experiments and show that the constructed macro actions are able to speed up the learning process for a variety of deep reinforcement learning methods. Our experimental results also demonstrate that the macro actions suggested by our approach are transferable among deep reinforcement learning methods and similar environments. We further provide a comprehensive set of ablation analysis to validate our methodology.

1. Introduction:

Conventional deep reinforcement learning (DRL) has been shown to demonstrate superhuman performance on a variety of environments and tasks (Mnih et al., 2013 (Mnih et al., , 2015 (Mnih et al., , 2016;; Salimans et al., 2017; Schulman et al., 2017; Moriarty et al., 1999; Such et al., 2018) . However, in conventional methods, agents are restricted to make decisions at each timestep, which differs much from the temporally-extended framework of decision-making in human beings. As a consequence, traditional methods (Mnih et al., 2013 (Mnih et al., , 2016;; Houthooft et al., 2016) require enormous amounts of sampling data in environments where goals are hard to reach or rewards are sparse. In complex environments where goals can only be achieved by executing a long sequence of primitive actions, it is difficult to perform exploration efficiently. As most real-world environments are large, complex, and usually offer sparse rewards, finding an optimal policy is still hard and challenging. It becomes crucial to explore new mechanisms to deal with these environments more efficiently and effectively.

Researchers in the past few years have attempted various techniques to expand the realm of DRL to temporally-extended frameworks (Sutton et al., 1999; Vezhnevets et al., 2016; Kulkarni et al., 2016; Bacon et al., 2017; Frans et al., 2017; Daniel et al., 2016; Florensa et al., 2017; Machado et al., 2017) . In such frameworks, a high-level controller interacts with the environment by selecting temporal-extended policies usually named as "options". Once an option is selected, it interacts with the environment for a certain timesteps and perform primitive actions until a termination condition for that option is met. However, developing effective options either requires a significant amount of domain knowledge (Girgin et al., 2010) , or often restricted to low-dimensional and/or relatively simple environments only (Bacon et al., 2017; Heess et al., 2016; Kulkarni et al., 2016) .

Instead of developing options, another branch of research directions focus on constructing macro actions (Fikes and Nilsson, 1971; Siklossy and Dowson, 1977; Minton, 1985; Pickett and Barto, 2002; Botea et al., 2005; Newton et al., 2005 Newton et al., , 2007)) . A macro action (or simply "a macro") is an open-loop (DiStefano III et al., 1967) policy composed of a finite sequence of primitive actions. Once a macro is chosen, the actions will be taken by the agent without any further decision making process. Some researches in DRL attempt to construct macros from the experience of an agent (Durugkar et al., 2016; Randlov, 1999; Yoshikawa and Kurihara, 2006; Onda and Ozawa, 2009; Garcia et al., 2019) . A key benefit of these approaches is the ease to construct a desired macro without supervision (Durugkar et al., 2016) . However, these approaches may lead to biased macros. For example, the most frequently used sequence of actions may not correspond to a macro that can lead the agent to outperform its past policies. Furthermore, as agents generally perform exploration extensively in the early stages of training, the inconsistency in the early experience may perturb the construction of macros. A few researchers proposed to employ a reduced form of macro called action repeat (Lakshminarayanan et al., 2017; Sharma et al., 2017) . In this formulation, primitive actions are repeated several times in a macro before the agent makes another decision. However, this formulation may limit the diversity of macros. By relaxing the agent to perform macros consisting of diversified actions, the agent is granted more chances to achieve higher performance. In addition, there are a handful of researches that requires human supervision to derive macros for improving training efficiency. The authors in McGovern et al. (1997) show that handcrafted macros can speed up training in certain tasks but hinder performance in others. The authors in Heecheol et al. (2019) generate macros from expert demonstrations via a variational auto-encoder. However, the process of obtaining such demonstrations is expensive. It would thus be favorable if there exists a method to find a macro without human intervention. Nevertheless, little attention has been paid to the construction of such macros.

Our goal is to develop a methodology for constructing a macro action from possible candidates. As possible macros are allowed to have different lengths and arbitrary compositions of primitive actions, such diversified macro actions essentially form an enormous space. We define this space as the macro action space (or simply "macro space"). Repeated action sequences are simply a small subset of the macro space. For a specific task in an environment, we hypothesize that there are good macros and bad macros in the macro space. Different macro actions have different performance impacts to an agent. Good macro actions enable the agent to jump over multiple states and reach a target state quicker and easier. On the other hand, bad macro actions may lead the agent to undesirable states. We argue that whether a macro is good or bad can only be determined by direct evaluation. In this study, we propose an evaluation method to test whether a macro is satisfactory for an agent to perform a specific task in an environment. Our method first relaxes the conventional action space (Sutton and Barto, 2018) with a macro to form an augmented action space. We then equip the agent with the augmented action space, and utilize the performance results as the basis for our evaluation. In order to find a good macro in the vast macro space, a systematic method is critically important and necessary. The method entails two prerequisites: a macro construction mechanism and a macro evaluation method. Although the second one is addressed above, there is still a lack of an appropriate approach to construct macros.

To satisfy the above requirement, we embrace an genetic algorithm (or simply "GA") for macro construction. GA offers two promising properties. First, it eliminates the dependency of the macro action derivation procedure from the past policies of an agent and/or human supervision. Second, it produces diversified macros by mutation. In order to combine GA with our evaluation method, our approach comprises of three phases: (1) macro construction by GA; (2) action space augmentation; and (3) evaluation of the augmented action space. Our augmented action space contains not only the original action space defined by DRL, but also the macro(s) constructed by GA. To validate the proposed approach, we perform our experiments on Atari 2600 (Brockman et al., 2016) and ViZDoom (Kempka et al., 2016) , and compare them to two representative DRL baseline methods. We demonstrate that our proposed method is complementary to existing DRL methods, and perform favorably against the baselines. Moreover, we show that the choice of the macro have a crucial impact on the performance of an agent. Furthermore, our results reveal the existence of transferability of a few macros over similar environments or DRL methods. We additionally provide a comprehensive set of ablation analysis to justify various aspects of our approach. The contributions of this paper are summarized as follows:

• We define the proposed approach as a framework.

• We provide a definition of macro action space.

• We introduce an augmentation method for action spaces.

• We propose an evaluation method to determine whether a macro is good or not.

• We establish a macro action construction method using GA for DRL.

• We investigate and reveal the transferability of macro actions.

The rest of this paper is organized as follows. Section 2 explains our framework. Section 3 describes our implementation details. Section 4 presents our results. Section 5 concludes.

2. Framework Formulation:

In this section, we first provide the definition of macro actions. Then, we provide a model of the environment with macros, which is a special case of Semi-Markov Decision Processes (SMDP) (Sutton et al., 1999) . Next, we provide definitions of functions in DRL. Finally, we formulate a framework for constructing good macros. The essential notations used in this paper can be referenced in Table A1 in our appendices.

Macro action. A macro action is defined as a finite sequence of primitive actions m = (a 1 , a 2 , . . . , a k ), for all a i in action space A, and some natural number k. Macros can be selected atomically as one of the actions by an agent. The set of macros form a macro action space M, which can be represented as M = A + , where '+' stands for Kleene plus (Hopcroft and Ullman, 1979) .

Environment modeled. The environment we concerned can be modeled as a special case of SMDP, which can be represented as a 4-tuple (S, M, p m ss , r m s ), where S is a finite set of states, M the finite set containing macro and all primitive actions provided by the environment, p m ss the transition probability from s to s when executing m, and r m s the reward received by the agent after executing m. The expressions of M, p m ss , and r m s can be represented as Eqs. 1, 2, and 3, respectively.

Deep reinforcement learning. An agent interacts with an environment under a policy ν, where ν is a mapping, ν : S × M → [0, 1]. The expected cumulative rewards it receives from each state s under ν can be denoted as V ν (s). The objective of DRL is to train an agent to learn an optimal policy such that it is able to maximize its expected return. The maximal expected return from each state s under the optimal policy can be denoted as V * M (s). The expressions of V ν and V * M can be represented as Eqs. 4 and 5, respectively, where γ ∈ [0, 1]. We only use γ between macros but not between the primitive actions within a macro. This encourages the agent to prefer the provided macros over a series of primitive actions.

M = A ∪ {m}, where m ∈ M (1) p m ss = P s t+|m| = s st = s, mt = m (2) r m s = E    |m|-1 τ =0 rt+τ st = s, mt = m    (3) V ν (s) = m∈M ν(s, m) r m s + γ s ∈S p m ss V ν (s ) (4) V * M = max m∈M r m s + γ s ∈S p m ss V * M (s ) (5)

Framework. We define our framework as a 4-tuple (R, C , A , E ), where R is the collection of all DRL methods, C the collection of all macro action construction methods, A the collection of all action space augmentation methods, and E the collection of all evaluation methods. Following this framework, in this study, we select Proximal Policy Optimization (PPO) (Schulman et al., 2017) and Advantage Actor Critic (A2C) (Mnih et al., 2016) as our DRL methods. Our implementations of the latter three components of the 4-tuple are formulated as pseudocodes and are presented in Algorithms 1, A1, and A2, respectively.

Algorithm 1 Macro construction algorithm based on GA 1: input: Environment E; DRL algorithm R; Total number of evaluated macros k 2: input: The sizes of sets Q, Q+, Q * = q, q+, q * respectively 3: output: List of the top q highest-performing macros evaluated Q 4: function Construction(E, R, k, q, q+, q * ) 5: initialize: A = the primitive action space of E 6:

initialize: M = [m1, . . . , mq], a list of q randomly generated macros s.t. ∀ m ∈ M, |m| = 2 7:

initialize: F = [f1, . . . , fq], ∀ f ∈ F, f = 0, the fitness scores for all the macros in M 8:

initialize:

Q = ∅, Q+ = ∅, Q * = ∅, i = 0

Q contains the top q macros at any generation 9:

while i < k do Each iteration is one generation 10:

for j in 1 to q do 11:

M = Augment(A, mj) Please refer to Algorithm A1 12: fj = Evaluate(E, R, M)

Please refer to Algorithm A2 13:

i = i + 1 14: if i >= k then break 15:

end for 16:

Q = the top q scoring macros in Q ∪ [m1, . . . , mq] according to F 17:

for m in List of q+ randomly selected macros in Q do 18:

Q+ = Q+ ∪ {Append(A, m)} Please refer to Algorithm A3 19:

end for Q+ will hold q+ mutated macros using append operator 20:

for m in List of q * randomly selected macros in Q do 21:

Q * = Q * ∪ {Alter(A, m)} Please refer to Algorithm A4 22:

end for Q * will hold q * mutated macros using alternation operator 23:

M = Q+ ∪ Q * 24:

end while 25:

return Q 26: end function 

3. Generic Algorithm for Constructing Macro Actions:

In this section, we present our implementation details of GA for constructing macro actions. We formulate our macro construction algorithm based on GA as Algorithm 1, which is established atop (1) the action space augmentation method (presented as Algorithm A1 and accessed at line 11 of Algorithm 1), (2) the macro evaluation method (presented as Algorithm A2 and accessed at line 12 of Algorithm 1), as well as (3) the append operator (accessed at line 19) and (4) the alteration operator (accessed at line 22) presented in Fig. 1 (a) and the appendices for mutating the macros.

We walk through Algorithm 1 and highlight the four phases of GA as follows. Lines 1-3 declare the input and output of the algorithm. Lines 5-8 correspond to the "initialization phase", which initializes the essential parameters. The population of the macros M are initialized at line 6. Lines 10-15 correspond to the "fitness phase", which augments the action space and performs fitness evaluation. The fitness phase can be executed in parallel by multiple threads. Lines 16-17 corresponds to the "selection phase", which selects the top performers from the population. Lastly, lines 18-23 correspond to the "mutation phase", which alters the selected macros and updates the population.

4. Experimental Results:

In this section, we present our experimental results of Algorithm 1 and discuss their implications. We arrange the organization of our presentation as follows in order to validate the methodology we proposed in the previous sections. First, we walk through the experimental setups. Second, we compare the constructed macro actions of different generations to examine the effectiveness of Algorithm 1. Third, we investigate the compatibility of the constructed macros with two off-the-shelf DRL methods. Then, we explore the transferability of the constructed macros between the two DRL methods. We next demonstrate that the constructed macros can be transferred to harder environments. Finally, we present a set of ablation analysis to inspect the proposed methodology from different perspectives. Please note that we only present the most representative results in this section. We strongly suggest the interested readers to refer to our appendices for more details.

4.1. Experimental Setup:

We first present the environments used in our experiments, followed by a brief description of the baselines adopted for comparison purposes. All of the macros presented throughout this section are constructed by Algorithm 1, if not specifically specified. We tabularize the environmental configurations, the hyper-parameters of Algorithm 1, and the hyperparameters used during the training phase in our appendices. Except for Section 4.2, all of the curves presented in this section are generated based on five random seeds and drawn with 95% confidence interval (displayed as the shaded areas).

Environments. We employ two environments with discrete primitive action spaces in our experiments: Atari 2600 (Bellemare et al., 2013) and ViZDoom (Wydmuch et al., 2018) . For Atari 2600 , we select seven representative games to evaluate our methodology: BeamRider , Breakout, Pong, Q*bert, Seaquest, SpaceInvaders, and Enduro. Due to the limited space, we use only the former six games for presenting our comparisons and analyses in Section 4, while leaving the remainder of our results in the appendices. For ViZDoom, we evaluate our methodology on the default task my way home (denoted as "Dense") for comparing the macros constructed among generations. We further use the "Sparse", "Very Sparse" and, "Super Sparse" (developed by us) tasks for analyzing the properties of compatibility and transferability of the constructed macros mentioned above. The Super Sparse task comes with extended rooms and corridors in which the distance between the spawn point of the agent and the goal is farther than the other three tasks. The map layouts for these four tasks are depicted in Figs. 1 (b ) and 1 (c).

Baselines. In our experiments, we select PPO (Schulman et al., 2017) and A2C (Mnih et al., 2016) as our DRL baselines for training the agents. For the ViZDoom environment, we further incorporate the intrinsic curiosity module (ICM) (Pathak et al., 2017) in the Sparse, Very Sparse, and Super Sparse tasks to generate intrinsic rewards for motivating exploration.

ViZDoom setups for transferability evaluation. We use ViZDoom to validate our hypothesis that macro actions constructed from an easy environment can be transferred to complex environments. In order to perform this validation study, we use Algorithm 1 to construct macro actions from the Dense task and evaluate their performance after 5M training timesteps. The highest performing macro action is then selected and evaluated in the Sparse, Very Sparse, and Super Sparse tasks respectively after 10M training timesteps. with the corresponding confidence interval stands for the average performance of the best macros in the generation (i.e., Q in Algorithm 1). It is observed from the trends that the mean episode rewards obtained by the agents improve with generations, revealing that later generations of the constructed macros may outperform earlier ones. The improving trends suggest that the evaluation method of Algorithm A2 is effective and reliable for Algorithm 1.

4.2. Comparison of Macros among Generations:



4.3. Compatibility of the Constructed Macros with DRL Methods:

In order to examine whether the best macros constructed by our methodology is complementary to the baseline DRL methods, we first execute Algorithm 1 with A2C and PPO, and determine the best macros mA2C and mPPO for the two DRL baselines respectively. We then form the augmented action spaces M A2C = A ∪ { mA2C } and M PPO = A ∪ { mPPO }.

We next train A2C using M A2C and PPO using M PPO for 10M timesteps respectively. The results evaluated on BeamRider are shown in Fig. 3 (a). The learning curves reveal that the baseline DRL methods are both significantly benefited from the augmented action spaces. More supporting evidences are presented in Figs. 3 and 4 . Table 1 presents our evaluation results for the seven Atari games. It is observed that all of the constructed macros are able to considerably enhance the performance of the baseline DRL methods, especially for Enduro.

4.4. Transferability of the Constructed Macros among DRL Methods:

In order to inspect whether the macro constructed for one DRL baseline can be transferred to and utilized by another DRL baseline, we train PPO with M A2C for 10M timesteps and plot the results on Q*bert, Pong, and Breakout in Figs. 3 (b), 3 (c), and 3 (d), respectively. The results show that PPO is able to use mA2C to enhance both the performance and the learning speed of the agents. Additional experimental results are provided in our appendices.

4.5. Transferability of the Constructed Macros to Harder Environments:

In order to investigate the transferability of the constructed macros among similar environments, we first execute Algorithm 1 with A2C and ICM (together denoted as "Curiosity") on Dense to construct a macro mD . We choose to train on Dense because the agent can learn from both the dense and sparse reward scenarios at different spawn points, enabling it to adapt to different reward sparsity settings easier. We then form the augmented action space thus validate the transferability of the constructed macros to harder environments. Fig. 4 also reveals that the gap between 'Curiosity+ mD ' and 'Curiosity' grows as the sparsity of the reward signal increases. For the Super Sparse task, 'Curiosity+ mD ' converges at around 13M timesteps, while 'Curiosity' just begins to learn at about 25M timestep. We compare mean time required to reach the goal w/ and w/o mD over 100 episodes in our appendices.

M = A ∪ { mD }

The macro action mD constructed by Algorithm 1 is (2, 2, 1), which corresponds to two forward moves followed by one right turn. We speculate that this macro action is transferable because the map layouts favor forward moves and right turns. Moving forward is more essential than turning right for the four ViZDoom tasks, as the optimal trajectories comprise of a number of straight moves. On the contrary, left turn is rarely performed by the agent, as this choice of action is only adopted when the agent is deviated from its optimal routes.

4.6. Ablation Analysis:

To justify our decision of selecting GA as our macro construction method, we additionally compare GA with three different macro construction methods to validate that GA is superior to them in most cases and possess several promising properties required by our methodology.

Comparison with random macros. We first compare the performance of the macros constructed by Algorithm 1 against randomly constructed macros. We present the learning curves of 'A2C with mA2C ' and 'A2C with mD ' against 'A2C with the best random macro mRandom ' in Figs. 5 (a) and 5 (b), respectively. For a fair comparison, we randomly select 50 out of all possible macros with lengths from 2 to 5, and evaluate each random macro for 5M timesteps for 2 times similar to how GA evaluates. We limit the lengths of the macros from 2 to 5 because it is the range GA has attempted. Following this procedure, the macro with highest evaluation score is selected to be mRandom . The agents are then trained for 10M timesteps, and the results are plotted in Figs. 5 (a) and 5 (b) (denoted as "Random"). It is observed that the two curves for 'A2C with mRandom ' are not obviously superior to those of 'A2C with mA2C ' and 'A2C with mD '. We further compare the 50 randomly constructed macros with the 50 macros constructed in the course of Algorithm 1, and summarize their impacts on performance as distributions over mean scores in Fig. 5 (c ). It is observed that a larger portion of the macros constructed by our approach tend to result in higher mean scores than those constructed randomly. A breakdown and analysis are offered in our appendices.

Comparison with action repeat. We next compare the performance of 'A2C with mA2C ' and 'A2C with mD ' against 'A2C with the best action repeat macro mRepeat ', and plot the learning curves in Figs. 5 (a) and 5 (b). In order to construct mRepeat for the two figures, we evaluate all possible action repeat macros with the same length to mA2C and mD for five random seeds and for 10M timesteps. The macro with highest evaluation score is then selected as mRepeat . It is observed that the curves of 'A2C with mRepeat ' are significantly worse than those of 'A2C with mA2C ', 'A2C with mD ', and 'A2C with mRandom ' in the figures. The low performance of them is probably due to the lack of diversity in mRepeat .

Comparison with handcrafted macros. We further investigate whether human intervention affects the outcome of Algorithm 1. As the initial population of the macros used by Algorithm 1 are randomly constructed, in this ablation study we replace the initial population by handcrafted macros (1, 1, 1), (1, 1, 1, 1), (1, 1, 1, 1, 1), which correspond to consecutive 'fire' action in BeamRider . These handcrafted macros are advantageous to the agent from the perspective of human players, as waves of enemies continue to emerge throughout the game. The macro constructed in this manner is denoted as mHuman . Fig. 5 (d) shows a comparison of the learning curves of 'A2C with mA2C ' and 'A2C with mHuman '. It is observed that the two curves are almost aligned. From the analysis, we therefore conclude that our approach does not need human intervention, and is unaffected by the initial population of the macros.

5. Conclusions:

We have formally presented a methodology to construct macro actions that may potentially improve both the performance and learning efficiency of the existing DRL methods. The methodology falls within the scope of a broader framework that permits other possible combinations of the DRL method, the action space augmentation method, the evaluation method, as well as the macro action construction method. We formulated the proposed methodology as a set of algorithms, and used them as the basis for investigating the interesting properties of macro actions. Our results revealed that the macro actions constructed by our methodology are complementary to two representative DRL methods, and may demonstrate transferability among different DRL methods and similar environments. We additionally compared our methodology against three other macro construction methods to justify our design decisions. Our work paves a way for future research on macros and their applications.

Appendices:

The appendices are organized as follows. Section A1 lists our essential notations. Section A2 describes the implementations of the genetic operators. Section A3 summarizes the hyperparameters used. Section A4 shows the additional experimental results. Finally, Section A5 describes our computing infrastructure. 

A1 Notations:



A3 Implementation Details:

We used A2C (Mnih et al., 2016) and PPO (Schulman et al., 2017) implementations from Hill et al. (2018) and established our models on top of them. We implemented ICM (Pathak et al., 2017) along with A2C (together denoted as "Curiosity") instead of Asynchronous Advantage Actor-Critic (A3C) (Mnih et al., 2016) , and found that our implementations tend to be stabler in terms of the variance of learning curves from several runs. The detailed hyperparameters for each method are summarized in Table A2 . The GA-related parameters used in Algorithm 1 are presented in Table A3 . The primitive actions we used are summarized in Table A4 . Parameter q q + q * Value 8 5 3 

:



Figures and Tables:

The map for the Dense, Sparse, and Very Sparse tasks.GoalSpawn pointsSuper Sparse (c) The map for the Super Sparse task.

Figure 1: (a) The generic operators for the append and alteration operations in Section 3. (b)(c) Map layouts of the ViZDoom environment. The blue points denote the random spawn points for the Dense task, while the orange, red, and purple arrows denote the fixed spawn points of the agents and their initial orientations for the Sparse, Very Sparse, and Super Sparse tasks, respectively.

Fig. 2 compares the learning curves of the A2C agents trained with different generations of the constructed macros in BeamRider , SpaceInvaders, Q*bert, and Dense. Each curve along

Figure2: Learning curves of the A2C agents trained with the early, middle, and late generations of the constructed macros. Please note that "Gen" stands for "generation" for all of the four figures.

and train the agent to use M with Curiosity on similar but harder environments with sparser rewards. The results are plotted in Fig. 4. Figs. 4 (a)∼4 (d) demonstrate that the agents with M learn significantly faster than the agents without it. These results

Figure 3: (a) Learning curves of the baseline DRL methods with/without the uses of the constructed macros. (b)(c)(d) Learning curves of the baseline DRL methods with/without the uses of mA2C.

Figure 4: Learning curves of Curiosity with/without mD for four different ViZDoom tasks.

Figure 5: (a) We compare our methodology to random macros by averaging the episode rewards of the top 10% performing macros. For action repeat, we pick the best macro from all possible candidates. (b) The best macros constructed by our methodology versus the random macros and action repeat. (c) Distribution of the constructed macros over different ranges of the evaluated mean scores. (d) Comparison of the macros constructed from random and handcrafted initial populations.

Genetic Operators Algorithm A3 Append operator 1: input: Primitive action space A 2: input: Macro action m = (a1, . . . , a |m| ) 3: output: Mutated macro m 4: function Append(A, m) 5: Let α = random element in A 6: return m = (a1, . . . , a |m| , α) 7: end function Algorithm A4 Alteration operator 1: input: Primitive action space A 2: input: Macro action m = (a1, . . . , a |m| ) 3: output: Mutated macro m 4: function Alter(A, m) 5: Let α = random element in A 6: return m = (α, a2, . . . , a |m| ) 7: end function

Figure A1: Learning curves of the A2C agents using different generations of the constructed macros. Please note that "Gen" denotes "generation". Each curve along with the corresponding confidence interval stands for the average performance of the best macros in the generation (i.e., Q in Algorithm 1).

Figure A2: Learning curves of the baseline methods with/without the constructed macros for evaluating compatibility.

Figure A4: Performance comparison of the macros constructed via Algorithm 1 (the red bars) and the random construction method described in Section 4.6 (the gray bars) in terms of the mean scores of the last 100 episodes achieved by the A2C agents using the macros. Please note that we present only the results of the top 50 performers out of the constructed macros for the Seaquest and Dense tasks.

Evaluation results of Atari. We calculate the mean episode rewards over 100 episodes.

Table content: <table><tr><td>Environment</td><td colspan="2">A2C A2C+ mA2C</td><td>mA2C</td><td>Enhancement</td></tr><tr><td>BeamRider</td><td>1049.52</td><td colspan="2">2796.20 (1, 0, 1, 1)</td><td>166.43%</td></tr><tr><td>Breakout</td><td>81.76</td><td colspan="2">119.36 (3, 3, 0, 2)</td><td>45.99%</td></tr><tr><td>Enduro</td><td>0</td><td>1270.37</td><td>(1, 1)</td><td>NaN</td></tr><tr><td>Pong</td><td>4.54</td><td>20.47</td><td>(2, 0, 2)</td><td>350.88%</td></tr><tr><td>Q*bert</td><td>2411.50</td><td colspan="2">4540.25 (0, 2, 4, 4)</td><td>88.28%</td></tr><tr><td>Seaquest</td><td>420.00</td><td colspan="2">657.80 (2, 3, 4, 0)</td><td>56.62%</td></tr><tr><td>SpaceInvaders</td><td>214.55</td><td>454.25</td><td>(1, 0, 0)</td><td>111.72%</td></tr></table>

Essential notations.

Table content: <table><tr><td colspan="3">Symbol Name</td><td colspan="2">Symbol Name</td></tr><tr><td>| • |</td><td/><td>sequence length or set size</td><td>E</td><td>environment</td></tr><tr><td colspan="2">P{•}</td><td>probability</td><td>R</td><td>DRL method</td></tr><tr><td colspan="2">E{•}</td><td>expected value</td><td>M</td><td>macro action space</td></tr><tr><td>t</td><td/><td>timestep</td><td>M</td><td>augmented action space</td></tr><tr><td>S</td><td/><td>state space</td><td>m</td><td>primitive action or macro action</td></tr><tr><td>s</td><td/><td>regular state</td><td>mt</td><td>m taken at t</td></tr><tr><td>st</td><td/><td>s perceived by agent at t</td><td>r m s</td><td>(discounted) expected reward</td></tr><tr><td>A</td><td/><td>primitive action space</td><td colspan="2">ν(s, m) policy over M</td></tr><tr><td>a rt</td><td/><td>primitive action one-step reward</td><td>p m ss V ν (s)</td><td>environment dynamic value function</td></tr><tr><td>γ</td><td/><td>discount factor</td><td>V  *  M (s)</td><td>optimal value function</td></tr><tr><td>R</td><td/><td>DRL method collection</td><td>E</td><td>evaluation method collection</td></tr><tr><td>A</td><td/><td>augmentation method collection</td><td>C</td><td>macro construction method collection</td></tr><tr><td colspan="3">A2 Pseudo Code</td><td/></tr><tr><td colspan="3">A2.1 Constructing Macro Actions</td><td/></tr><tr><td colspan="4">Algorithm A1 Action space augmentation method</td></tr><tr><td colspan="3">1: input: Primitive action space A</td><td/></tr><tr><td colspan="3">2: input: Macro action m</td><td/></tr><tr><td colspan="3">3: output: Augmented action space M</td><td/></tr><tr><td colspan="3">4: function Augment(A, m)</td><td/></tr><tr><td>5:</td><td colspan="2">return M = A ∪ {m}</td><td/></tr><tr><td colspan="3">6: end function</td><td/></tr><tr><td colspan="3">Algorithm A2 Macro evaluation method</td><td/></tr><tr><td colspan="5">1: input: Environment E; DRL method R; Augmented action space M; Evaluation epochs N</td></tr><tr><td colspan="3">2: output: Fitness score of M</td><td/></tr><tr><td colspan="3">3: function Evaluate(E, R, M, N )</td><td/></tr><tr><td>4:</td><td colspan="3">initialize: E = [e1, . . . , eN ] ∀ e ∈ E, e = 0</td></tr><tr><td>5:</td><td colspan="2">for i in 1 to N do</td><td/><td>N epoch</td></tr><tr><td>6:</td><td/><td>Learn a policy over M in E using R</td><td/></tr><tr><td>7:</td><td/><td colspan="3">ei = the average of all "last 100 episode rewards"</td></tr><tr><td>8:</td><td colspan="2">end for</td><td/></tr><tr><td>9:</td><td colspan="2">return Average of E</td><td/></tr><tr><td colspan="3">10: end function</td><td/></tr></table>

List of the hyperparameters for the baseline methods.

Table content: <table><tr><td>Hyperparameter</td><td>A2C</td><td>PPO</td><td>Curiosity</td></tr><tr><td>Discount factor</td><td>0.99</td><td>0.99</td><td>0.99</td></tr><tr><td>Number of frame skip</td><td>4</td><td>4</td><td>4</td></tr><tr><td>Number of parallel environments</td><td>16</td><td>16</td><td>20</td></tr><tr><td>Rollout length</td><td>5</td><td>128</td><td>20</td></tr><tr><td>Batch size</td><td>80</td><td>2048</td><td>400</td></tr><tr><td>Value function coefficient</td><td>0.25</td><td>0.5</td><td>0.5</td></tr><tr><td>Entropy coefficient</td><td>0.01</td><td>0.01</td><td>0.01</td></tr><tr><td>Gradient clipping maximum</td><td>4.0</td><td>0.5</td><td>40.0</td></tr><tr><td>Learning rate</td><td colspan="2">0.001 0.0003</td><td>0.0003</td></tr><tr><td>Learning rate annealing</td><td>Linear</td><td/><td>Constant</td></tr><tr><td>Clipping parameter</td><td/><td>0.2</td><td/></tr><tr><td>Policy gradient loss weight λ</td><td/><td/><td>0.1</td></tr><tr><td>Forward model loss β</td><td/><td/><td>0.2</td></tr><tr><td>Intrinsic reward scaling factor</td><td/><td/><td>0.01</td></tr></table>

List of the GA-related parameters used in Algorithm 1.

Table content: <table/>

List of the primitive actions. Additional Comparison of the Learning Curves Figs. A1, A2 and A3 present results unable to be completely included in Sections 4.2, 4.3 and 4.4, respectively.

Table content: <table><tr><td colspan="2">Environment</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td/><td>BeamRider</td><td>NOOP</td><td>FIRE</td><td>RIGHT</td><td>LEFT</td><td/></tr><tr><td/><td>Breakout</td><td>NOOP</td><td>FIRE</td><td>RIGHT</td><td>LEFT</td><td/></tr><tr><td/><td>Enduro</td><td>NOOP</td><td>FIRE</td><td>RIGHT</td><td>LEFT</td><td>DOWN</td></tr><tr><td>Atari</td><td>Pong</td><td>NOOP</td><td>RIGHT</td><td>LEFT</td><td/><td/></tr><tr><td/><td>Q*bert</td><td>NOOP</td><td>UP</td><td>RIGHT</td><td>LEFT</td><td>DOWN</td></tr><tr><td/><td>Seaquest</td><td>NOOP</td><td>FIRE</td><td>UP</td><td colspan="3">RIGHT LEFT DOWN</td></tr><tr><td/><td>SpaceInvaders</td><td>NOOP</td><td>FIRE</td><td>RIGHT</td><td>LEFT</td><td/></tr><tr><td/><td>ViZDoom</td><td colspan="3">TURN LEFT TURN RIGHT MOVE FORWARD</td><td/><td/></tr><tr><td colspan="3">A4 Experimental Results</td><td/><td/><td/><td/></tr><tr><td>A4.1</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposed to augment the existing action set with the ‘macro’ actions that consist of sequence of primitive actions. The framework is based on genetic algorithm (GA) to propose and modify the ‘macro’ actions, where the fitness function in GA is simply the performance of underlying RL algorithm on the newly constructed action set. Experiments on some benchmarks from Atari and VisDoom show some promising results. Overall the technique proposed is simple and straightforward, which should be easy to understand and implement for the community. In my opinion, the augmented action set forces some form of exploration, and thus would achieve better performance especially in the situations where reward is sparse. There are still some concerns I have: 1. Some claims are too strong. For example, the paper criticizes the previous works with human supervision. However, the GA used here also requires a lot of human heuristics: the design of mutation/augmentation/selection/evaluation, etc. 2. The current specific method only works with discrete actions. How would the method be adapted to continuous case? Actually I’m also concerned about using such mutation based method for exploration, so I’m not fully convinced that this could be generalized to continuous case. 3. It seems that Q+ and Q* are always growing inside the while loop of Algorithm 1. Why there’s no deletion of the actions? Also what would be the trade-off between the size of action space and the performance? I think there must be a limit where afterwards RL becomes harder with large action space. 4. Regarding the experiment, I think the main competitors would be the other exploration based methods, like count based, intrinsic reward based, etc. I’m not asking for comparing against everything, but something like 1) separate the effort of curiosity with proposed method in Figure 4 (i.e., add a proposed method only baseline); 2) In fig 2 and 3, add baselines that using A2C/PPO + exploration, e.g., curiosity, count, etc. I would expect a stronger statement with these ablation studies. Minor: The paper could be more compact. For example, the Algorithm A1 contains only one operation. For better readability, there’s no need to put it into appendix.