Growing Action Spaces
Authors: Gregory Farquhar
Laura Gustafson
Zeming Lin
Shimon Whiteson
Nicolas Usunier
Gabriel Synnaeve
Venue:  (2020)
Keywords: reinforcement learning
curriculum learning
multi-agent reinforcement learning

Abstract: In complex tasks, such as those with large combinatorial action spaces, random exploration may be too inefficient to achieve meaningful learning progress. In this work, we use a curriculum of progressively growing action spaces to accelerate learning. We assume the environment is out of our control, but that the agent may set an internal curriculum by initially restricting its action space. Our approach uses off-policy reinforcement learning to estimate optimal value functions for multiple action spaces simultaneously and efficiently transfers data,  value estimates, and state representations from restricted action spaces to the full task. We show the efficacy of our approach in proof-of-concept control tasks and on challenging large-scale StarCraft micromanagement tasks with large, multi-agent action spaces.

Under review as a conference paper at ICLR 2020
GROWING ACTION SPACES
Anonymous authors Paper under double-blind review
ABSTRACT
In complex tasks, such as those with large combinatorial action spaces, random exploration may be too inefficient to achieve meaningful learning progress. In this work, we use a curriculum of progressively growing action spaces to acceler- ate learning. We assume the environment is out of control, but that the agent may set an internal curriculum by initially restricting its action space. Our ap- proach uses off-policy reinforcement learning to estimate optimal value functions for multiple action spaces simultaneously and efficiently transfers data, value es- timates, and state representations from restricted action spaces the full task. We show the efficacy of our approach in proof-of-coneept control tasks and on challenging large-scale StarCraft micromanagement tasks with large, multi-agent action spaces.
INTRODUCTION
The value of curricula has been well established in machine learning, reinforcement learning, and in biological systems. When a desired behaviour is sufficiently complex, or the environment too unforgiving, it can be intractable learn the behaviour from scratch through random exploration. Instead, by "starting small" (Elman 1993), an agent can build skills, representations, and a dataset of meaningful experiences that allow to accelerate its learning. Such curricula can drastically improve sample efficiency (Bengio et al. 2009).
Typically, curriculum learning uses progression of tasks or environments. Simple tasks that provide meaningful feedback to random agents are used first, and some schedule is used to introduce more challenging tasks later during training (Graaves al,, 2017). However, in many contexts neither the agent nor experimenter has such unimpeded control over the environment. In this work, we instead make use of curricula that are internal to the agent, simplifying the exploration problem without changing the environment. In particular, we grow the size of the action space of reinforcement learning agents over the course of training.
At the beginning of training, ration by guiding the agent towards rewards and meaningful experiences, and provides low variance updates during learning. The action space is then grown progressively. Eventually, using the most unrestricted action space, the agents are able to find superior policies. Each action space is a strict superset of the more restricted ones. This paradigm requires some domain knowledge to identify a suitable hierarchy of action spaces, However, such a hierarchy is often easy to find. Continuous action spaces can be discretised with increasing resolution. Similarly, curricula for coping with the large combinatorial action spaces induced by many agents can be obtained from the prior that nearby agents are more likely need to coordinate. For example, in routing or traffic flow problems nearby agents or nodes may wish to adopt similar local policies to alleviate global congestion. Our method will be valuable when it is possible to identify a restricted action space which random exploration leads to significantly more meaningful experiences than random exploration in the full action space.
agents use severely restricted action space. This helps explo-
We propose an approach that uses off-policy reinforcement learning to improve sample efficiency in this type of curriculum learning. Since data from exploration using restricted action space is still valid in the Markov Decision Processes (MDPs) corresponding to the less restricted action spaces, can learn value functions in the less restricted action space with 'off-action- -sction-space' data collected by exploring in the restricted action space. In our approach, we learn value functions corresponding to each level of restriction simultaneously. We can use the relationships of these value functions to

---

Under review as a conference paper at ICLR 2020
each other to accelerate learning further, by using value estimates themselves as initialisations as bootstrap targets for the less restricted action spaces, as well as sharing learned state representations.
Empirically, we first demonstrate the efficacy of our approach in two simple control tasks, in which the resolution of discretised actions is progressively increased. We then tackle a more challenging set of problems with combinatorial action spaces, in the context of StarCraft micromanagement with large numbers of agents (50-100), Given the heuristic prior that nearby agents in a multiagent setting are likely need coordinate, we use hierarchical clustering to impose restricted action space on the agents. Agents in a cluster are restricted to take the same action, but we progressively increase the number of groups that can act independently of one another over the course of training. Our method substantially improves sample efficiency on a number of tasks, outperforming learning any particular action space from scratch, number of ablations, and an actor-critic baseline that learns single value function for the behaviour policy, as in the work of Czarnecki et al. (2018). Code is available, but redacted here for anonymity.
2 RELATED WORK
Curriculum learning has a long history, appearing at least as early as the work of [Selfridge et al. (1985) in reinforcement learning, and for the training of neural networks since Elman (1993). In supervised learning, one typically has control of the order in which data is presented to the learning algorithm. For learning with deep neural networks, [enniio et al. (2009) explored the use of curricula in computer vision and natural language processing. Many approaches
handcrafted schedules
for task curricula, but others Zarrmba & Sutskever 2014: Pentina et al. 2015 Graves et al.) 2017) study diagnostics that can be used automate the choice of task mixtures throughout training. In self-supervised control setting, Murali et al. (0188) use sensitivity analysis to automatically define a curriculum over action dimensions and prioritise their search space.
In some reinforeement learning settings, it may also be possible to control the environment so as to induce a curriculum. With a resettable simulator, it is possible to use a sequence of progressively more challenging initial states (Asada et al., 1996 Florensa et al. 2017). With a procedurally gen- erated task, it often possible to automatically tune the difficulty the environments (Tamar al.) 2016). Similar curricula also appear often in hierarchical reinforcement learning, where skills can be learned in comparatively easy settings and then composed in more complex ways later (Singh) T
1992). Taylor et al. (2007) use more general inter-task mappings to transfer Q-values between tasks that do not share state and action spaces. In adversarial settings, one may also induce a curricu- lum through self-play (Tesauro) 1995| Sukhbaatar et al. 2017 Silver et al. (017). In this case, the learning agents themselves define the changing part of the environment.
A less invasive manipulation of the environment involves altering the reward function. Such reward shaping allows learning policies in an easier MDP, which can then be transferred to the more difficult sparse-reward task (Colombetti & Dorigo 1992; Ng et al. 1999). It is also possible to learn reward shaping on simple tasks and transfer it to harder tasks in a curriculum (Konidaris & Barto 2006).
In contrast, learning with increasingly complex function approximators does not require any control of the environment. In reinforcement learning, this has often taken the form of adaptively grow- ing the resolution of the state space considered by a piecewise constant discretised approximation (Moore, 1994, Munos & Moore, 2002; W Whiteson et al. (007). Stanley & Mikkkulainen (0004) study continual complexification in the context of coevolution, growing the complexity of neural network architectures through the course of training. These works progressively increase the capabilities of the agent, but not with respect to its available actions.
In the context of planning on-line with a model, there are a number of approaches that use progres- sive widening to consider increasing large action spaces over the course of search (Chaslot et al.) 2008), including in planning for continuous action spaces (Couêtoux et al. 2011). However, these methods cannot directly be applied to grow the action space in the model model-free setting.
A recent related work tackling our domain is that of Czarnecki et al. 2018)) who train mixtures of two policies with an actor-critie approach, learning a single value function for the current mixture of policies. The mixture contains a policy that may be harder to leam but has higher performance ceiling, such as a policy with a larger action space as we consider in this work. The mixing coef- ficient is initialised to only support the simpler policy, and adapted via population based training
2

---

Under review as a conference paper at ICLR 2020
Jaderberg al. 2017). In contrast, simultaneously learn different value function for each policy, and exploit the properties of the optimal value functions to induce additional structure on our models. We further use these properties to construct scheme for off-action space learning which means our approach may be used in an off-policy setting. Empirically, in our settings, we find our approach perform better and more consistently than actor-critic algorithm modeled after Czar- necki et al. (2018), although we do not take on the significant additional computational requirements of population based training in any of our experiments.
A number of other works address the problem of generalisation and representation for value func- tions with large discrete action spaces, without explicitly addressing the resulting exploration prob- lem (Dulac-Aroodd et al. [0115] Pan et al. 2018). These approaches typically rely on action rep- resentations from prior know ano.. Such representations could be used in combination with our method to construct hierarchy of action spaces with which to shape exploration.
3 BACKGROUND
We formalise our problem as MDP, specified by a tuple < P,r, >. states and actions are given by S and A, P is the transition function that specifies the environment dynamics, and y is a discount factor used to specify the discounted return R = Σr 7'T for an episode of length T. We wish our agent to maximise this return in expectation by learning a policy æ that maps states to actions. The state-action value function (Q-function) given by
The set of possible
Q* == Rr, [R]s,, a). The optimal Q-function Q" satisfies the Bellman optimality equation:
-
B(r(s,a) a) + 7 max ('ss',
(I)
Q-learning (Watkins & Dayan 1992) uses a sample-based based approximation of the Bellman optimality operator T to iteratively improve an estimate of Q" Q-learning is off-policy method, meaning that samples from any policy may be used to improve the value function estimate. We use this property engage Q-learning for off-action-space learning, as described in the next section.
We also introduce some notation for restricted action spaces. In particular, for an MDP with unre- stricted action space A define a set of N action spaces Aes {0, :
1}. Each action
space is subset of the next: Au C A1 C denoted (a)s)). The optimal policy in this restricted policy class is कद (a]s) s). and its corresponding action-value and value functions are (7 a) and V2 (s) max, Q7 a).
C AN-1 C A. A policy restricted to actions A, is
Additionally, we define hierarchy of actions by identifying for every action E Ae, > 0 parent action (arent.(a) in the space of Ar-1. Since action spaces are subsets of larger action spaces, for all E A pare,t, = a, i.e., one child of each action itself. Simple pieces of domain knowledge are often sufficient to define these hierarchies. For example, discretised continuous action can identify its nearest neighbour in Aç-1 as a parent. In Section 5 we describe a possible hierarchy for multi-agent action spaces. One could also imagine using -etbed-emmeddiing Tennenholtz Mannor 2019) to learn such a hierarchy from data.
4 CURRICULUM LEARNING WITH GROWING ACTION SPACES
We build our approach to growing action spaces (GAS) on off-policy value-based reinforcement learning. Q-learning and its deep-learning adaptations have shown strong performance (Hessel et al.) 2018 and admit a simple framework for off-
off- policy learning.
4.1 OFF-ACTION-SPACE LEARNING
A value function for an action space Ar may be updated with transitions using actions drawn from its own action space, or any more restricted action spaces, we use an off-policy learning algorithm. The restricted transitions simply form subset of the data required to learn the value functions of the less restricted action spaces. To exploit this, we simultaneously learn an estimated optimal value function Q7 (s, a) for each action space As, and use samples drawn from a behaviour policy based on value function for low é directly train the higher value functions.
3

---

This monotonicity intuitively recommends an iterative decomposition of the value estimates, in which _ (s, a) is estimated as a sum of (s, a) and some positive Ar(s, a). This not im- mediately possible due to the mismatch in the support of each function. However, we can leverage Under review as a conference paper at ICLR 2020
At the beginning of each episode, sample according to some distribution. The experiences generated in that episode are used to update all of the Q2e(s, a). This off-action-space learning is type of off-policy learning that enables efficient exploration by restricting it to the low-l regime. We sample at the beginning of the episode rather than at each timestep because, if the agent uses high-l action, it may enter state that is inaccessible for lower-f policy, and we do not wish to force a low-& value function to generalise to states that are only accessible at higher f.
Since data from restricted action space only supports subset of the state-action space relevant for the value functions of less restricted action spaces, we hope that a suitable function approximator still allows some generalisation to the unexplored parts of the less restricted state-action space.
4.2 VALUE ESTIMATES
Note that:
(*) S if
(2)
This is because each action space a strict subset of the larger ones, so the agent can always in the worst case fall back to policy using more restricted action space.
a hierarchical structure in the action spaces when present, as described in Section In this case we can use:
Qi+ (s, a) = (7, parent,(a)) + Ae(s,
This is a task-specific upsampling of the lower-& value function to intialise the next value function. Both (s. a) and As(s, a) are learned components. We could further regularise or restrict the functional form of de ensure its positivity when parent, to be valuable in our experiments, and simply initialised A, to be small.
However, we did not find this
The property also implies modified Bellman optimality equation:
(s, E(r(s,a) + max max
(4)
ESt o'
The maxiet are redundant their role as conditions on the optimal value function Q7- However, the Bellman optimality equation also gives us the form of a Q-learning update, where the term in the expectation on the RHS is used as an operator that iteratively improves an estimate of Q". When these estimates inaccurate, the modified form of the Bellman equation may lead to different updates, allowing the solutions to higher l to be bootstrapped from those at lower l.
We expect that policies with low are easier to learn, and that therefore the corresponding Q; is higher value and more accurate earlier in training than those at high f. These high values could be picked up by the extra maximisation in the modified bootstrap, and thereby rapidly learned by the higher-& value functions. Empirically however, we find that using this form for the target in our loss function performs no better than just maximising over Q7 a'). We discuss the choice of target and these results in more detail in Section 6.2
4.3 REPRESENTATION
By sharing parameters between the function approximators of each Qt. we can learn a joint state representation, which can then be iteratively decoded into estimates of Q" for each f. This shared embedding can be iteratively refined by, e.g. additional network layers for each Q; maintain flexibility along with transfer of useful representations. This simple approach has had great success in improving the efficiency of many multi-task solutions using deep learning (Ruder 2017).
4.4 CURRICULUM SCHEDULING
We need to choose a schedule with which to increase the & used by the behaviour policy over the course of training. Czarnecki et al. (2018) use population based training (Jaderberg et al.) (0177) to choose mixing parameter the fly. However, this comes at significant computational cost, and
4

---

Under review as a conference paper at ICLR 2020
optimises greedily for immediate performance gains. We use simple linear schedule mixing parameter a E N.. Initially a = and we always choose l = 0. Later, we pick |a] with probability [a] 90% chance and = 2 with 10% chance). This worked well empirically with little effort to tune. Many other strategies exist for tuning a curriculum automatically (such those explored by Graves) et al. (2017)) and could be beneficial, at the cost of additional overhead and algorithmic complexity.
and & [a] with probability a [a] (e.g. if = 1.1, we choose & = 1 with
GROWING ACTION SPACES FOR MULTI-AGENT CONTROL
In cooperative multi-agent control, the full action space allows each of N agents to take actions from set Aagent, resulting an exponentially large action space of size Aageni | Random exploration in this action space is highly unlikely to produce sensical behaviours, so growing the action space we propose is particularly valuable in this setting. One approach would be to limit the actions available to each agent, as done in our discretised continuous control experiments (Section 6.1) and those of Czarnecki et al. (2018). However, the joint action space would still be exponential in N. We propose instead to use hierarchical clustering, and to assign the same action to nearby agents.
At the first level of the hierarchy, constrained to take the same action. At the next level of the hierarchy, we split the agents into k groups using an unsupervised clustering algorithm, allowing each group act independently. At each further level, every group is split once again into & smaller groups. In practice, we simply use k-means clustering based on the agent's spatial position, but this can be easily extended more complex hierarchies using other clustering approaches.
treat the whole team as single group, and all agents
To estimate the value function, we compute state-value score (s). and group-action delta (s ag.g) g) for each group g at each level É. Then, we compute an estimated group-action value for each group, at each level, using a per-group form of (3) Qi+1 (8, (8, = (s, parentx((g)) + (s) to initialise the iterative computation, similarly to the du-
(e(s, ag. g). We use (s, eling architecture of Wang et al. 2015 The estimated value of the parent action is the estimated value of the entire parent group taking the same action as the child group. At each level & we now
have a set of group-action values.
In effect, a multi-agent value-learning problem still remains at each level f, but with a greatly re- duced number of agents at low f. We could simply use independent Q-learning [Tan] 1993). but instead choose to estimate the joint-action value at each level as the mean of the group-action values for the groups at that E, as in the work of (Sunhhag et al. (2017). A less restrictive representation, such as that proposed by Rashid et al. 2018), could help, but we leave this direction to future work.
A potential problem is that the clustering changes for every state, which may interfere with gener- alisation as group-actions will not have consistent semantics. We address this in two ways. First, include the clustering as part of the state, and the cluster centroids previous timestep for t > 0 to keep the cluster semantics approximately consistent. Second, we use functional representation that produces group-action values that are broadly agnostic to the identifier of the group. In particular, we compute a spatially resolved embedding, and pool over the locations occupied by each group. See Figure 2 and Section 6.2 for more details.
re-initialised from the
6 EXPERIMENTS
We investigate two classes of problems that have natural hicrarchy in the action space. First, simple control problems where a coarse action discretisation can help accelerate exploration, and fine action discretisation allows for more optimal policy. Second, the cooperative multi-agent using large-scale StarCraft micromanagement scenarios.
setting, discussed in Section 5
6.1 DISCRETISED CONTINUOUS CONTROL
As proof-of-concept. look at two simple examples: versions of the classic Acrobot and Moun- tain Car environments with discretised action spaces. Both tasks have a sparse reward of +1 when the goal is reached, and we make the exploration problem more challenging by terminating episodes
5

---

Under review as a conference paper at ICLR 2020
0.0
0.0
-2.5
-2.5
collattoon ret0nns
modl mollcation retUTt
-6.0
-5.0
-10
Ag
A1
A
0.0
Ae (skor
10.0
(sleor GAS(2)
GAS
-.5.5
-12.5
150000
200000
150000
01NT1O0 stegs
Covionmment steps
(a) Acrobot
(b) Mountain Car
Figure 1: Discretised continuous control with growing action spaces. We report the mean and standard error (over 10 random seeds) of the returns during training, with moving average over the past 20 episodes. A2 (slow c) is ablation of A2 that decays at quarter the rate.
with a penalty of 11 the goal not reached within 500 timesteps. The normalised remaining time is concatenated the state it remains Markovian despite the time limit. There is further actu- ation cost of 0.05||al al|2. At Ao. the actions apply a force of +1 and -1. At each subsequent Aryo, each action is split into two children, one that is the same as the parent action, and the other applying half the force. Thus, there are 2 actions in As.
The results of our experiments are shown in Figure I Training with the lower resolutions Ag and A from scratch converges to finding the goal, but incurs significant actuation costs. Training with Ag from scratch almost never finds the goal with e-greedy exploration. We also tried decaying the at quarter of the rate (A2 slow c) without success. In these cases, the policy converges to the one that minimises actuation costs, never finding the goal. Training with growing action space explores to find the goal early, and then uses this experience to transition smoothly into solution that finds the goal but takes slower route that minimises actuation costs while achieving the objective.
6.2 COMBINATORIAL. ACTION SPACES: STARCRAFT BATTLES
6.2.1
LARGE-SCALE STARCRAFT MICROMANAGEMENT
The real-time strategy game StarCraft and its sequel StarCraft II have emerged as popular platforms for benchmarking reinforcement learning algorithms (Synnaeve et al. [0016] Vinyals et al. 2017). Full game-play has been tackled by e.g. (Lee et al. 2018, Vinyals et al. 2019), while other works focus on sub-pra problemssem such as micromanagement, the low-level control of units engaged in a battle between two armies (e.g. (Usunier al., 2016)). Efforts to approach the former problem have required some subset of human demonstrations, hierarchical methods, and massive compute scale, and focus the latter more tractable benchmark evaluate our methods.
Most previous work on RL benchmarking with StarCraft micromanagement is restricted to maxi- mally 20-30 units (Samvelyan et al., 2019; Usunier et al.) 2016). In our experiments we focus on much larger-scale micromaaagemmnt scenarios with 50-100 units on each side of the battle. To fur- ther increase the difficulty of these micromanagement scenarios, in our setting the starting locations of the armies are randomised, and the opponent is controlled by scripted logic that holds its position until any agent-controlled unit is in range, and then focus-fires on the closest enemy. This increases the exploration challenge, our agents need to learn to find the enemy first, while they hold a strong defensive position. The action space for each unit permits an at ttttackmma movee or move action in eight cardinal directions, well as stop action that causes the unit to passively hold its position.
In our experiments, we use k 2 for k-means clustering and split down to at most four or eight groups. The maximum number of groups in experiment with Ar is 2 Although our approach is designed for off policy learning. we follow the common practice of using n-step Q-learning to accelerate the propagation of values (Hessel al. 2018). Our base algorithm uses the objective of n-step Q-learning from the work of Mnih et al. (2016), and collects data from multiple workers into short queue similarly to Espeholt et al. (2018). Full details can be found in the Appendix.

---

Under review as a conference paper at ICLR 2020
5a.
(,,,))
(,(aa) 8b.
V(s)
7a.
Tb
70
Pool Evaluate
36.
Copy
Embed
CNN
Scatter
Figure 2: Architecture for GAS with hierarchical clustering. For clarity, only two levels of hierarchy are shown. The dark shaded regions identify locations that are pooled over before state-valus or actup-action scores computed.
6.2.2 MODEL ARCHITECTURE
We propose an architecture to efficiently represent the value functions of the action-space hierarchy. The overall structure is shown in Figure 2 We start with the state of the scenario (1). Ally units are blue and split into two groups. From the state, features are extracted from the units and map (see Appendix for full details). These features concatenated with one-hot representation of the unit's group (for allied agents), and are embedded with a small MLP. 2-D grid of embeddings constructed by adding up the unit embeddings for all units in each cell of the grid (2). The embeddings are passed through a residual CNN to produce a final embedding (3), which is copied several times and decoded as follows. First, state-value branch computes scalar value by taking global mean pooling (4) and passing the result through 2-layer MLP (6). Then, for each e, masked mean-pooling is used to produce an embedding for each group that Ar by masking out the positions in the spatial embedding where there are no units of that group (5a, 5b, 5c). A single evaluation MLP for each is used to decode this embedding into a group action-score (7a, 7b, 7c). This architecture allows shared state representation to be efficiently decoded into value-function contributions for groups of any size, at any level of restriction in the action space.
We consider two approaches for combining these outputs. In default approach, described in Section 5 each group's action-value is given by the sum of the state-value and group-action-scores
for the group and its parents (8a, 8b). In 'SEP-Q', each group's action-value is simply given by the state-value added the group-action score, i.e., (7, a.) ((s) Ae(s, (e(s,0g.9) Mg.g). This is
ablation in which the action-value estimates for restricted action spaces do not initialise the action- value estimates of their child actions.
6.2.3 RESULTS AND DISCUSSION
Figure presents the results of our method, as well as number of baselines and ablations, on variety of micromanagement tasks. Our method labeled Growing Action Spaces GAS(E), such that GAS(2) will grow from Ao to Ag. Our primary baselines are policies trained with action spaces Ao or A2 from scratch. GAS(2) consistently outperforms both of these variants. Policies trained from scratch on Ag struggle with exploration, in particular in the harder scenarios where the opponent has a numbers advantage. Policies trained from scratch on Ag learn quickly, but plateau comparatively low, due to the limited ability of single group to position effectively. GAS(2) benefits from the efficient exploration enabled by an intialisation at Ap. and uses the data gathered under this policy to efficiently transfer to Ag; enabling higher asymptotic performance.
We also compare against a Match (MM) baseline using the actor-critic approach of Czarnecki al. (008)) but adapted for our multi-agent setting and supporting third level in the mixture

---

Under review as a conference paper at ICLR 2020
thiil
301
XD1
Miaaee en SulC
6432
CAB 20 Yau. Tappo
1.5
-10
Sr Mndtraliiac va Sytrable
Xtbreed 30 votediale to Iedreiido
CASS0 0S-CC
Figure 3: StarCraft micromanagement with growing action spaces. We report the mean and standard error (over 5 random seeds) of the evaluation winrate during training, with moving average over the past 500 episodes.
of policies (Ao. Ai A2). We tuned hyperparameters for all algorithms on the easiest, fastest- training scenario (80 marines vs. 80 marines). On this scenario, MM learns faster but plateaus at the same level as GAS(2). MM underperforms on all other scenarios to varying degrees. Learning separate value functions for each A,, as in our approach, appears to accelerate the transfer learning in the majority of settings. Another possible explanation is that MM may be more sensitive to hyperparameters. We do not use population based training to tune hyperparameters on the fly, which could otherwise help MM adapt to each scenario. However, GAS would presumably also benefit from population based training, at the cost of further computation and sample efficiency.
The policies learned by GAS exhibit good tactics. Control of separate groups is used position our army so as to maximise the number of attacking units by forming a wall or a concave that surrounds the enemy, and by coordinating simultaneous assault. Figure 5 in the Appendix shows some example learned policies. In scenarios where MM fails to learn well. it typically falls into local minimum of attacking head-on.
In each scenario, we test an ablation GAS (2): ON-AC that does not use our off-action-space up- date, instead training each level of the Q-function only with data sampled at that level. This ablation performs somewhat worse on average, although the size of the impact varies in different scenar- ios. In some tasks, is beneficial to accelerate learning for finer action spaces using data drawn from the off-action-space policy. In Appendix A.I.I the same ablation shows significantly worse performance on the Mountain Car task and comparable performance on Acrobot.
We present number of further ablations two scenarios. The most striking failure is of the 'SEP- Q' variant which does not compose the value function as a sum of scores in the hicrarchy. It is critical ensure that values well-initialised discretised continuous control tasks, 'SEP-Q" also underperforms, although less dramatically.
move less restricted action spaces. In the
The choice of target is less important: performing
coarser action spaces to construct the target as described in Section 4.2 does not improve learning speed as intended. One potential reason that maximising more potential targets increases the maximisation bias already present in
8

---

Under review as a conference paper at ICLR 2020
Q-learning (Hasselt 2010). Additionally, we use n-step objective which combines partial on- policy return with the bootstrap target, which could reduce the relative impact of the choice of target.
Finally, we experiment with a higher É. Unfortunately, asymptotic performance is degraded slightly once we use Ag or higher. One potential reason is that it decreases the average group size, pushing against the limits of the spatial resolution that may be captured by our CNN architecture. Higher l increases the amount of time that there are fewer units than groups, leaving certain groups empty and rendering our masked pooling operation degenerate. We do not see a fundamental limitation that should restrict the further growth of the action space, although we note that most hierarchical approaches in the literature avoid too many levels of depth. For example, Czarnecki al.) (2018) only mix between two sizes of action spaces rather than the three we progress through in the majority of our GAS experiments.
7 CONCLUSION
In this work, we presented an algorithm for growing action spaces with off- off-policy reinforcement learning efficiently shape exploration. We leam value functions for all levels of hierarchy of restricted action spaces simultaneously, and transfer data, value estimates, and representations from more restricted to less restricted action spaces. We also present strategy for using this approach in cooperative multi-agent control. In discretised continuous control tasks and challenging multi- agent StarCraft micromanagement scenarios, we demonstrate empirically the effectiveness of our approach and the value of off off-action-space learning. An interesting avenue for future work is to automatically identify how restrict action spaces for efficient exploration, potentially through meta-optimisation. We also look to explore more complex and deeper hierarchies of action spaces.
REFERENCES
Minoru Asada, Shoichi Noda, Sukoya Tawaratsumida, and Koh Hosoda. Purposive behavior ac- quisition for a real robot by vision-based reinforcement learning. Machine learning, 23(2-3); 279-303, 1996.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, ACM, 2009.
Guillaume M JB Chaslot, Mark HM Winands, H JAAP VAN DEN HERIK, Jos WHM Uiterwijk, and Bruno Bouzy. Progressive strategies for monte-carlo tree search. New Mathematics and Natural Computation, 4(03):343-3577 2008.
Marco Colombetti and Marco Dorigo. Robol shaping: developing situated agents through learning. International Computer Science Institute, 1992.
Adrien Couëtoux, Jean-Baptiste Hoock, Nataliya Sokolovska, Olivier Teytaud, and Nicolas Bon- nard. Continuous upper confidence trees. In International Conference on Learning and Intelligent Optimization, pp. 433-445. Springer, 2011.
Wojeiech Marian Czarnecki, Siddhant M Jayakumar, Max Jaderberg, Leonard Hasenclever, Yee Whye Teh, Simon Osindero, Nicolas Heess, and Razvan Pascanu. Mix&match-agent cur- ricula for reinforcement learning. arXiv preprint arXiv: 11800607788 2018.
Gabriel Dulac-Amold, Richard Evans, Hado van Hasselt, Peter Sunehag. Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep rein- forcement learning in large discrete action spaces. arXiv preprint arXiv: 152.07676 2015.
Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 4811:911-99, 1993.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint arXiv: 1802.01561 2018.

---

Under review as a conference paper at ICLR 2020
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse riculum generation for reinforcement learning. arXiv preprint arXiv:1707.05300 2017.
Alex Graves, Mare G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. Proceedings of the 34th International Conference on Learning-Volume
Machine Learning- Volume 70, pp. 1311 1311-1320. JMLR. org, 2017.
Hado Hasselt. Double q-learning. Advances Neural Information Processing Systems, pp- 2613-2621, 2010.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojeiech M Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based train- ing of neural networks. arXiv preprint arXiv: 1.000866, 2017.
George Konidaris and Andrew Barto. Autonomous shaping: Knowledge transfer in reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pp. 489-496. ACM, 2006.
Dennis Lee, Haoran Tang, Jeffrey Zhang, Huazhe Xu, Trevor Darrell, and Pieter Abbeel. Modular architecture for starcraft ii with deep reinforcement learning. In Fourteenth Artificial Intelligence and Interactive Digital Entertainment Conference, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Marc G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning, Nature, 518(7540):529, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937, 2016.
Andrew W Moore. The parti-gam algorithm for variable resolution reinforcement learning in mul- tidimensional spaces. In Advances in neural information processing systems, pp. 711-718, 1994.
Rémi Munos and Andrew Moore. Variable resolution discretization in optimal control. Machine learning, 49(2-3):291-323, 2002.
Adithyavairavan Murali, Lerrel Pinto, Dhiraj Gandhi, and Abhinav Gupta. Cassl: Curriculum ac- celerated self-supervised learning. In 2018 IEEE International Conference on Robotics and Au- tomation (ICRA), pp. 6453-6460, IEEE, 2018.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. ICML, volume 99, pp. 278-287, 1999.
Yangchen Pan, Amir-massoud Farahmand, Martha White, Saleh Nabi, Piyush Grover, and Daniel Nikovski. Reinforcement learning with function-valued action spaces for partial differential equa- tion control. 07 2018.
Anastasia Pentina, Viktoriia Sharmanska, and Christoph H Lampert. Curriculum learning multi- ple tasks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 5492-5500, 2015.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint IrXiv:1803: /485, 2018.
Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint arXiv: arXiv:1706.0550 050998 2017.
10

---

Under review as a conference paper at ICLR 2020
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. 2019.
Oliver G Selfriigee Richard Sutton, and Andrew Barto. Training and tracking in robotics. In IJCAI, pp. 670-672, 1985.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01880 2017.
Satinder Pal Singh. Transfer of learning by composing solutions elemental sequential tasks. Machine Learning. 8(3-4):323-333 1992.
Kenneth Stanley and Risto Mikkulainen. Competitive coevolution through evolutionary com- plexification. Journal of artificial intelligence research, 21:63-100, 2004.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. arXiv preprint 1rXiv:1703.05547, 2017.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Valuo-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv: wrXiv:1706.052990 052996 2017.
Gabriel Synnaeve, Nantas Nardelli, Alex Auvolat, Soumith Chintala, Timotéée Lacroix, Zeming Lin, Florian Richoux, and Nicolas Usunier. Torchcraft: library for machine learning research on real-time strategy games. arXiv preprint arXiv:1611.0060 2016.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Picter Abbeel. Value iteration networks. In Advances Neural Information Processing Systems, pp. 2154-2162, 2016.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
Matthew E Taylor, Peter Stone, and Yaxin Liu. Transfer learning via inter-task mappings for tem- poral difference learning. Journal of Machine Learning Research, 8($e)):2125-2167, 2007.
Guy Tennenholtz. and Shie Mannor. The natural language of actions. In International Conference on Machine Learning, pp. 6196-6205, 2019.
Gerald Tesauro. Temporal difference learning and td d--gammon. Communications of the ACM. 38(3): 58 68, 1995.
Nicolas Usunier, Gabriel Synnaeve, Zeming Lin, and Soumith Chintala. Episodic exploration for deep deterministic policies: An application to starcraft micromanagement tasks. arXiv preprint 161iv:1609.02992 2016.
Oriol Vinyals, Timo Ewalds. Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets,
Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: new challenge for reinforcement learning. arXiv preprint /70.v://70..477700 2017.
Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathicu, Max Jaderberg, Woj- ciech M. Czamecki, Andrew Dudzik, Aja Huang. Petko Georgiev, Richard Powell, Timo Ewalds, Dan Horgan, Manuel Kroiss, Ivo Danihelka, John Agapiou, Junhyuk Oh, Valentin Dal- ibard, David Choi, Laurent Sifre, Yury Sulsky, Sasha Vezhnevets, James Molloy, Trevor Cai, David Budden, Tom Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Toby Pohlen, Yuhuai Wu, Dani Yogatama, Julia Cohen, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap. Chris Apps. Koray Kavukcuoglu, Demis Hassabis, and David Silver. AlphaStar: Mastering the Real-Time Strategy Game StarCraft II. https: betttps:/ddeepmnndee hwtp/eeeeennnnne//////./ complooog//coo///////oooooooooo. real -imee---m----e 1lphstar-maste - (iccimmmstttttgy-ggaae htwpattteyyyaaaettttrrrraaeeeeee starcraft-ii/111 2019.

---

Under review as a conference paper at ICLR 2020
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning, arXiv preprint arX00:1511.06881, 2015.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Shimon Whiteson, Matthew Taylor, Peter Stone, et Adaptive tile coding for value function approximation. Computer Science Department, University of Texas at Austin, 2007.
Wojeiech Zaremba and Ily Sutskever. Learning to execute. arXiv preprint
2014.
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 DISCRETISED CONTINUOUS CONTROL.
A.1.1 ADDITIONAL ABLATIONS
Here, we present results on some additional ablations GAS on the discretised continous control tasks. SEP-Q performs slightly worse both tasks, less dramatic failure than in the StarCraft experiments. These value functions are simpler, and it is easier to learn the new action space's 's value without relying so much on the previous suggesting once again that the significance of this component of the algorithm is somew hat problem- dependent. We also test version that follows the intuition of the 'Match' objective of M&M more closely, adapted for the value-based setting: instead of using an adaptive initialisation of each level's Q-function as described in the main text, we use an L2 penalty to 'Match' the new level's value function to its parent action. which should have similar effect. This variant performs similarly here (perhaps slightly worse the more challenging Mountain Car).
ON-AC performs worse only Mountain Car,
0.0
0.0
-2.
-2.
mall mollcation reTUr
-5.0
-5.0
GAS:2)
GAS12)
GAS Match
GASF2) Masch
0.0
GAS ON-AC
10.0
CAS(21 ON-AC
GAS(3): SMP-Q
GASI2): SEP*QQ
-22
-12.5
150000
20000
15000
CINTFon12AS stegs
cuvironment steps
(a) Acrobot
(b) Mountain Car
Figure 4: Additional GAS ablations the discretised continuous control tasks.
A.1.2 HYPERPARAMETERS
For our experiments in discretised continous control, standard DQN trainer (Mnih al., 2015) with the following parameters.
Parameter
Value
batch size replay buffer size
128
10000
target update interval
200
initial
1.0
final
0.1
decay
25000 env steps
lead-in
25000 steps
growth
25000 env steps
env steps per model udpate
4
Adam learning rate
5e-4
Adam e
le-4
For GAS experiments, we keep the mixing cocfficient for 25000 environment steps, and then increase it linearly by every 25000 steps until reaching the maximum value. use 7 0.998 for Acrobot experiments, but reduce it to y 0.99 for Mountain Car to prevent diverging Q Q-values.
Our model consists of fully-connected ReLU layers, with 128 hidden units for the first and 64 hidden units for all subsequent layers. Two layers are applied applied on the current embedding to produce a new embedding, and an evaluation layer on that embedding produces the Q-values for that level.
encoder. Then, for each one layer
13

---

Under review as a conference paper at ICLR 2020
Figure 5: Final learned policies of StarCraft micromanagement unit control with growing action spaces. Scenarios shown from left to right at time 0, 3, 5, 10, 15 seconds. Top to bottom the scenarios are: marines vs 65 marines, 50 hydralisks 50 hydralisks, 95 zerglings vs 50 marines. In these examples, the opponent is always on the right, and the agent controlled by model trained with GAS is on the left.
A.2 STARCRAFT MICROMANAGEMENT SCENARIOS
A.2.1 SCENARIOS AND LEARNED STRATEGIES
We explore five Starcraft micromanagement scenarios: 50 hydralisks vs 50 hydralisks, 80 marines vs 80 marines, 80 marines 85 marines, 60 marines vs 65 marines, 95 zerglings 50 marines. In these scenarios, our model controls the first set of units, and the opponent controls the second set.
The opponent scripted opponent that holds its location until an opposing unit is within range to attack. Then, the opponent will engage in an "attack- behavior, as described in Usunier al. (2016), where each unit individually targets the closest unit to it. Having the opponent remain stationary until engaged makes this more difficult problem the agent must find its opponent, and attack into defensive position, which requires good positions prior to engagement.
As mentioned in section 6.2. all of our scenarios require control of much larger number of units than previous work. The 50 hydralisks and 80v80 marines scenarios are both imbalanced as a result of attacking into defensive position. The optimal strategy for 80 marines 85 marines and 60 vs 65 marines requires slightly more sophisticated unit positioning, and the 95 zerglings vs 50 marines scenario requires the most precise positioning. The agent can the enemy's initial stationary positioning to its advantage by slightly surrounding the opponent in a concave, ensuring that the outermost units are in its attack range, but far enough away to be of range of the center-most enemy units. Ideally, the timing of the groups in all scenarios should be coordinated such that all units get range of the opponent roughly the same point in time. Figure shows how our model is able to exhibit this level of unit control.
A.2.2 FEATURES
We use a standard features for the units and map, given by TorchcraftAl
For each of the units, the following features extracted:
14

---

Under review as a conference paper at ICLR 2020
Current x, positions.
Current x, velocities.
Current hitpoints
Armor and damage values
Armor and damage types
Range versus both ground and air units
Current weapon cooldown
A few boolean flags on some miscellaneous unit attributes
Approximate normalization for each feature keep its value approximately between 0-1. For the map, the following features are extracted for each tile in the map:
a one-hot encoding of tile's the ground height (4 channels)
boolean representing or not the given tile walkable
boolean representing or not the given tile buildable
and boolean representing or not the given tile is covered by fog of war.
The features form a HrWaT tensor, where our map has height H and width W.
A.2.3 ENVIRONMENT DETAILS
We use a frame-skip of 25, approximately 1 second of real time, allowing for reasonably fine-graing grained control but without making the exploration and credit assignment problems too challenging.
We calculate at every timestep the difference in total health points (HP) and number of units for the enemy from the last step, normalised by the total starting HP and unit count. As reward function, we use the normalised damage dealt, plus 4 times the normalised units killed, plus an additional reward of 8 for winning the scenario by killing all enemy units. This reward function is designed such that the agent gets some reward for doing damage and killing units, but the reward from doing damage will never be greater than from winning the scenario. Ties and timeouts are considered losses.
A.3 EXPERIMENTAL DETAILS
A.3.1 MODEL
As described in Section 6.2.2 custom model architecture is used for Stareraft micromanagement. Each unit's is feature vector is embedded to size 128 step 2 of Figure The grid where the unit fea- tures and map features downsampled by factor of 8. After being embedded, the unit features for ally and enemy units are concatenated with the downsampled map features and sent into a ResNet encoder with four residual blocks (stride padding 3). The output is an embedding of size 64.
scattered onto is the size of the Starcraft map of the scenario in walktiles
The decoder uses mean pooling over the embedding cells as described in Section 2 Each evaluator is a 2-layer MLP with 64 hidden units and 17 outputs, one for each action. All layers are separated with ReLU nonlinearities.
A.3.2 TRAINING IYPERRARRMETERS
We use 64 parallel actors to collect data in a short queue from which batches are removed when they consumed by the learner. We use batches of 32 6-step segments for each update.
For the Q-learning experiments, we used the Adam optimizer with a learning rate of 2.5 x 10 10-4 and 10 4 For the MM baseline experiments, loss coefficient of 8 x 10 and value loss coefficient 0.5. The learning rates and entropy loss coefficient were tuned by random search, training with An from scratch on the 80 marines 80
learning rate of 1 x 10 entropy
15

---

Under review as a conference paper at ICLR 2020
marines scenario with 10 configurations sampled from loq.uniform(-33 -3) for the learning rate and Log.uniform(33, -1) for the entropy loss coefficient.
For Q-learning, the first 10000 model updates. We also use a target network that copies the behaviour model's parameters every 200 model updates.
e-greedy exploration strategy decaying linearly from 1.0 0.1 over
We also use a linear schedule to grow the action-space. There a lead of 5000 model updates, during which the action-space is held constant at Ao, to prevent the action space from growing when e or the policy entropy is too high. The action-space is then grown linearly at a rate of 10000 model entirely at Ai and after 20000,
updates per level of restriction, that after 10000 updates, entirely at A2.
16


Reviews:
[{"review_id": "Syg2YyWTYH", "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 paper presents a method of scaling up towards action spaces, that exhibit natural hierarchies (such as a controllable resolution of actions), throughout joint training of Q-functions over these. Authors notice, and exploit a few interesting properties, such as inequalities that emerge when action spaces form strict subsets that lead to nice parametrisation of policies in a differential way. The evaluation is performed in simple toy-ish tasks, and in micro-management problem in 5 scenarios in the game of SC2.\n\nOn a fundamental level, proposed method resembles that of Mix & Match, that authors discuss in the paper. In the M&M paper authors use the matching (distillation) of the policies, to ensure knowledge transfer, while in GAS, authors share information through said differential reparametrisation. Ablations provided imply that this part is indeed crucial (as with independent Qs, called \"Sep-Q\" learning flat-lines). The ablation testing the off-policy modification, seems a bit less conclusive, despite authors claiming that \"This ablation performs slightly, or considerably, worse in each scenario. \" We can see in Figure 3 that there were 5 experiments:\n- in one [95z vs 50m] GAS works much better\n- in two [80m v 80m, 80m v 85m] there seems to be no difference (in terms of longer term performance)\n- in one [60m v 65m] GAS works slightly better\n- in one [50h v 50h] GAS works slightly worse\nThis mixed bag of results would rather suggest that the offpolicy part is not the main contributing factor, and might require closer investigation to really understand which part of the system proposed brings the benefits. Could this ablation be also done on the toy-ish tasks from experiment 1? Given its simplicity it should be cheap enough to run these extra experiments (I am assuming the SC2 ones are quite expensive?)\n\nReviewer finds it hard to understand, given current description, how was M&M baseline adapted to the Q-learning setup? Was the distillation loss replaced with L2 one? Was the exact same architecture used for these experiments? How were the missing parent actions handled? Or did M&M experiments use an actor critic learning instead (which would make the comparison more about Q-learning vs Actor-Critic learning, than about methods of action space scaling). Methods section (mentioning entropy loss) looks like M&M was indeed trained with actor-critic, which would make the baseline hardly comparable. Adapting M&M strategy to Q-learning (or picking other baselines, that work on the same RL setup), in reviewer's opinion, is crucial for actual evaluation of author's contributions (given that this is the only baseline).\n\nOn a minor point - given how unique SC2 environment (and problem of unit micromanagement) is, would it be possible to provide baselines results also for the toy-ish experiment 1? \n\nOverall, I recommend a weak rejection of the paper, and I am happy to revisit this evaluation given that authors address the above comments.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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": {}}, {"review_id": "HyxjNYwTKr", "reviewer": "AnonReviewer2", "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": "Based on the intuition that smaller action space should be easier to learn, the author proposes a curriculum learning approach which learns by gradually growing the action space. An agent using simpler action space can generate experiences to be used by all the agents with larger action spaces. The author presents experiments on simple domains and also on a challenging video game. In general, it is an interesting research work. I think the author can improve the paper in the following aspect. \n\n1. Motivation. Curriculum learning is based on the idea that tasks can be arranged in a sequential manner and those tasks learned earlier can be somehow helpful for subsequent tasks. Although it is clear that small action space should be easy to learn, it is unclear why those off-policy samples can be helpful for more complex action space. Smaller action space can correspond to a completely different optimal policy. Imagine that in a tabular environment, two actions A, B are available, and the optimal action is to always take B. Then if the agent with full action space uses the experiences generated by the agent with action space {A} may get completely wrong action values. There must be some constraint of the underlying MDP. The author may provide some experiments in tabular case to illuminate the issue.\n\n2. Relevant works. I think the author should include some discussions regarding large action spaces, since one goal of the proposed method is to handle such situation. There are several works should be discussed. For example, Deep Reinforcement Learning in Large Discrete Action Spaces, Function-valued action space for PDE control. The former handle the large discrete action space by learning an action embedding; while the latter attempts to leverage the regularity in the action space by introducing a convolutional structure for the output of the actor network and hence the proposed method can scale to arbitrary action dimensions. ", "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": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bke5PXoRFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary: This paper proposes a method to progressively explore the action space for RL. The proposed method is called “growing action spaces”. The basic idea is that actions can usually be grouped by a hierarchical structure: the lowest level is the coarsest and higher levels gradually refine the action partition. This method effectively captures many RL settings, including multi-agent learning. One effective approach is to apply the action hierarchy. \n\nThen the paper performs experiments on both simple toy examples and a more complicated one, the Starcraft game. The simple toy problems is “Acrobot” and “Mountain Car” with discretized spaces. A hierarchy of level 3 is considered. The experiments clearly demonstrate the effectiveness of the proposed methods. Also, the behavior of each level of the hierarchy is shown: coarse level of actions help exploration but cannot reach the highest value. \n\nThe paper then demonstrates extensive experiments on the game StarCraft. 50-100 units on each side of the game are used — which is much larger than previous papers. Further difficulties are introduced by randomizing the initializing location, and scripted logic controlled opponents. A 2-level hierarchy are tested and obtain consistently good results in all experiments. Further ablations are tested and explanations are provided. \n\nEvaluation: Overall, I like this paper. This paper is well-written, everything is clearly explained. The proposed method is novel and effective. \n\nSome minor comments:\n\t• What is the epsilon in Figure 1? \n\t• Using 3-level of hierarchy in the StarCraft game does not work well. You said the possible reason might be that the high level is pushing the limit of CNN. Did you try a different architecture that has a higher resolution?\n\t• The training curriculum is still mysterious. Why you pick a random l to start training? Maybe training level by level is better? By starting from the lowest level, you may be able to stop at any level. So you will have l different policies. In practice, you may find the best l this way.\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 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": {}}]

Author rebuttal:

Meta-review: This paper presents a novel approach to learning in problems which have large action spaces with natural hierarchies. The proposed approach involves learning from a curriculum of increasingly larger action spaces to accelerate learning. The method is demonstrated on both small continuous action domains, as well as a Starcraft domain.

While this is indeed an interesting paper, there were two major concerns expressed by the reviewers. The first concerns the choice of baselines for comparison, and the second involves improving the discussion and intuition for why the hierarchical approach to growing action spaces will not lead to the agent missing viable solutions. The reviewers felt that neither of these were adequately addressed in the rebuttal, and as such it is to be rejected in its current form.
Decision: Reject