Factored Action Spaces in Deep Reinforcement Learning
Authors: Thomas PIERROT
Valentin Macé
Jean-Baptiste Sevestre
Louis Monier
Alexandre Laterre
Nicolas Perrin
Karim Beguir
Olivier Sigaud
Venue:  (2021)
Keywords: Deep Reinforcement Learning
Large action spaces
Parameterized action spaces
Multi-Agent
Continuous Control

Abstract: Very large action spaces constitute a critical challenge for deep Reinforcement Learning (RL) algorithms. An existing approach consists in splitting the action space into smaller components and choosing either independently or sequentially actions in each dimension. This approach led to astonishing results for the StarCraft and Dota 2 games, however it remains underexploited and understudied. In this paper, we name this approach Factored Actions Reinforcement Learning (FARL) and study both its theoretical impact and practical use. Notably, we provide a theoretical analysis of FARL on the Proximal Policy Optimization (PPO) and Soft Actor Critic (SAC) algorithms and evaluate these agents in different classes of problems. We show that FARL is a very versatile and efficient approach to combinatorial and continuous control problems.

Under review as a conference paper at ICLR 2021
FACTORED ACTION SPACES IN DEEP REINFORCE- MENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Very large action spaces constitute a critical challenge for deep Reinforcement Learning (RL) algorithms. An existing approach consists in splitting the action space into smaller components and choosing either independently or sequentially actions in each dimension. This approach led to astonishing results for the Star- Craft and Dota 2 games, however it remains underexploited and understudied. In this paper, we name this approach Factored Actions Reinforcement Learning (FARL) and study both its theoretical impact and practical use. Notably, we pro- vide theoretical analysis of FARL on the Proximal Policy Optimization (PPO) and Soft Actor Critic (SAC) algorithms and evaluate these agents in different classes of problems. We show that FARL a very versatile and efficient approach to combinatorial and continuous control problems.
INTRODUCTION
In many decision making problems, especially for combinatorial problems, the search space can be extremely large. Learning from scratch in this setting can be hard if not sometimes impossible. Using deep neural networks helps dealing with very large state spaces, but the issue remains when the action space the horizon required to solve problem are too large, which is often the case in many real-world settings. Several approaches tackle the problem of long horizon tasks like learning compositional neural programs (Pierrot et al. 2019). hierarchical policies (Levy al.] 2018) or options (Bacon et al. 2017). However, the large action space problem is not as well covered. The main approach consists in factorizing the action space into Cartesian product of smaller sub- spaces. We call it Factored Actions Reinforcement Learning (FARL). In FARL, the agent must return a sequence of actions each time step instead of single one. This approach has been applied successfully to obtain astonishing results in games like StarCraft (Jaderberg et al.) 2019). Dota (Berner et al., 2019) or for neural program generation (Li et al.) (0020). There was also several attempts to use factored action spaces with DQN, PPO and AlphaZero to solve continuous action problems by discretizing actions and specifying each dimension at time (Metz et al. 2017
Grill et al. 2020 Tang & Agrawal 2020). The resulting algorithms outperformed several native continuous action algorithms on McJoCo benchmarks.
While this approach has been successfully applied in practice, a deeper analysis of the consequences of such formulation on the RL problem missing. In this paper, we highlight two different ways to factorize the policy and study their theoretical impact. We discuss the pros and cons of both approaches and illustrate them with practical applications. We extend two state-of-the-art agents PPO and SAC work with both factorization methods. To highlight the generality of the approach, we apply these algorithms to diverse domains, from large sequential decision problems with discrete actions to challenging continuous control problems and hybrid domains mixing discrete decisions and continuous parameterization of these decisions. We illustrate the method on three benchmarks chosen for the different difficulties they raise and highlight the benefits of using factored actions.
RELATED WORK
A large part of the reinforcement learning literature covers the long time horizon problem with ap- proaches based on options (Bacon et al.) 2017]] Vezhnevets et al. 2017), compositionality (Pierrot
et al. 2019 2020) more generally Hierarchical Reinforcement Learning (Levy al.

---

Under review as a conference paper at ICLR 2021
Yang et al. 2018: Nachum et al. 2018al b). However, there has been fewer attempts to deal with large action spaces. In many real life problems, especially in combinatorial or optimisation research standard problems, the number of entities and the size of instances can be very large thus leading to action spaces which may contain thousands of actions. Some prior works have focused on factor- izing the action space into binary sub-spaces and using generalized value functions (Pazis & Parr) 2011). A similar approach leveraged Error-Correcting Output Code classifiers (ECOCs) (Dietterich) & Bakiri 1994) to factorize the action space and allow for parallel training of a sub-policy for each action sub-space (Dulac-Amon) et al., 2012). More recently. Dulac et al. (2015) proposed to leverage prior information about the actions to embed them into a continuous action space in which the agent can generalize. A concurrent approach is to learn what not to learn (Zahavy et al.) 2018). The authors train an action elimination network to eliminate sub-optimal actions, thus reducing the number of possible actions for the RL agent.
In another approach, the action space factored into a Cartesian product of n discrete sub-action spaces. In Parameterized actions RL, also called Hybrid RL, actions are factored into sequences that correspond to the choice of an action in a discrete action space of size m and then the choice
of the intensity of this action in continuous action space (Hausknecht & Stone 2015) Masson jet al. 2016 Fan et al. 2019; Delalleau et al. 2019). In other problems, the action space exhibits a natural factorization as in Dota 2 or StarCraft. Indeed, one must first choose a macro-action such as selecting a building or a unit and then a sequence of micro-actions such as creating a specific unit, specific position. In such a factorization, the autoregressive property essential, as the selection of an action must be conditioned on the previously selected actions in the sequence. For both games, factorizing the action space and selecting sequences of autoregressive actions instead of single discrete actions has been shown to be crucial (Berner et al. 2019 Vinyals et al. 2019).
However neither of these works sufficient highlight this aspect nor propose proper formalisation.
As far as we know, the only work that establishes a proper FARL framework is Metz et al. (2017)
with the model called Sequential DQN (SDQN). They build on existing methods to construct se- quential models that have been proposed outside the RI. literature. Notably, these models are natural fit for language modelling Bengio et al. (2003); Sutskever et al. (2014). Metz et al. (2017) extend the DQN algorithm (Mnih et al. 2013) to the sequential setting and present this approach as an alternative way to handle continuous action spaces such as robotic control. Here, we go beyond Q-learning approaches and propose general formulations to extend any actor-critic RL agent to the FARL setting. We illustrate this framework on two examples: we extend both the Proximal Policy Optimization (PPO) (Schulman et al.) 2017) and Soft Actor Critic (SAC) algorithms (Haarnoja al., 2018) to the sequential setting. We also highlight the flexibility and generality of the FARL approach by using it on broad class of problems. We show results on robotic control MuJoCo benchmarks as in Metz et al. (2017) to demonstrate the relevance of our derivations, and we also successfully apply factored PPO and SAC to parameterized and multi-agent problems.
FACTORED ACTION SPACES
In this section, we introduce notations for Markov Decision Problems with factored action spaces. We consider Markov Decision Process (MDP) (S, A, T, R.
7, Po) where S is the state space, A the action space, T S x A + S the transition function, It S x A x S + R the reward function, Y S is discount factor and Pu the initial state distribution. We assume that the state space is continuous and that the MDP is bully-observable, thus observations equal states. In this paper, we assume that the action space is factored, thus might be expressed as Cartesian product of discrete action sub-spaces: A Ai x .... x An where A; is a discrete action space of size n,,
We aim to learn a parameterized stochastic policy no A S - [0,1], 1). where π (als) is the proba- bility of choosing action a in state s. The objective function to maximise is [(6) = IE, 1E rrr where T is a trajectory obtained from Te starting from state so ~ Po and T. is the reward ob- tained along this trajectory at time t. We define the Q-value for policy n. Q" S x A + R as =E, EE, y're), where т is a trajectory obtained from To starting from state s and per- forming initial action We define the V-value Va S R as (ss) Eae (aals) (s. a). The policy is factored into a product of n joint distributions to handle the factored action space. We consider two settings.
(s =
2

---

Under review as a conference paper at ICLR 2021
Independent Factorization. A first setting corresponds to problems in which the actions com- ponents can be chosen independently from each other, only taking into account the environ- ment state In this case, we decompose policy xo into policies Ti S + A, such that (s) E S x A, To(als) IT==1 mi (a) where a' is the 8th component of action Each sub-policy i returns probabilities over the possible actions a' E A,, In this setting, to sample an action from Ty, we sample in parallel the sub-actions from the sub- uub-distributions Ti..
Autoregressive Factorization. In this second setting, actions assumed ordered and dependent. For instance, the choice of action a² depends on the value of the action a' that has been chosen by policy n². To account for this, are selected conditionally to previous action choices a ..a...a_____._. 1-1 More formally, the probability of choosing action a' is (a [s, a², ,...,, "), As Metz et al. (0117). we introduce sub-state spaces U, S x A1 ... X A, where Up S and associated sub-states un U₁ which contain the information of the environment state 8; and all the sub-actions that have been selected so far. We S - A into sub-policies x² Ui- Ai,
impose the autoregressive property, i.e. intermediate actions a'
decompose the policy
[1, such that
V(s, a) S x A, (a [s,] = II m [ajaall
In this setting the sub-actions cannot be sampled in parallel. To sample an action from тa, we sample each sub-action sequentially, starting from the first and conditioning each sub-policy on the previously sampled actions.
4 PROPERTIES OF FACTORED POLICIES
In this section, we discuss the differences between both factorization methods from a theoretical point view and the impact on their use practice. We study particular how the factorization choice affects the expression of the policy entropy and the Kullback-Leibler divergence between two factored policies. Entropies and KI. divergences between policies are used many RI. algorithms regularization terms in order to favor exploration during policy improvement or to prevent policy updates from modifying the current policy too much. When the policy is factored into independent sub- cobb-policiss, show that these quantities can easily be computed the sum of the same quantities computed over the sub-policies. It is not as simple when the policy is autoregressive, but in this case, when computed over actions sampled from the current policy, the sum of the sub-entropies or sub-KL divergences has actually for expected value the global entropy or global KL divergence. The proofs of all propositions are Appendix B
4.1 SHANNON ENTROPY
The Shannon entropy of a policy is used in several RL algorithms to regularize the policy improve- ment step or favor exploration. is defined as H(*((Is))
- <Taas) (a]ss))
aEA
Proposition 1.1 computed as the sum of the Shannon entropies of the sub-policies:
When the policy is factored into independent policies, its Shannon entropy can be
a
((((11))= Σ (1))))))) with H( H(1s(-1s)
Σ
x' (aals) log ( (a)1s))
(1)
o² EA.
In this setting, the n Shannon entropies can be computed independently parallel and then summed to obtain the global policy entropy.
Proposition 1.2 When the policy is autoregressive, we have:
H(((-1s)) = Easw((Is))
Σ H(T (((7'((1/))))
This result gives us a simple way to estimate the Shannon entropy of n. In practice, updates are performed batches of transitions originating from different states, the quantity used for regu- larization is an estimation of IF, (H((()))))) Using the above proposition, we know that it equals IE, [E.+)(1)) ΣE= H([ (. DD]]] = Egaas)((s)) |Ei= H(TT(.(u))))]
Therefore, using Σn (-[w") instead of H(()(.(s) for each transition of the batch, we are actually estimating the same quantity. However, must be noted that the estimation is correct only
3

---

Under review as a conference paper at ICLR 2021
if all sequences of actions sampled according the current policy T(|s)) This does not cause any issue in am on-policy context, but when using a replay buffer (and thus transitions obtained with past versions of the policy), the sequences of actions must be resampled with the current policy for the estimation to remain correct.
4.2 KULLBACK-LEIBAL DIVERGENCE
The KL-divergence between two policies is also often used in RL, either regularization term Schulman et al. (017)) or as a loss function Grill et al. (222)). The Kl-divergence between two
(*(als)
policies (-|s) and (u((ss is defined as KL. [=((ss]llu((ss)
Σ (a|s) ( aEA
log <<aas))
Proposition 2.1 When the two policies are factored into independent sub-policies, their KL- divergence can be computed as the sum of the KL-divereences between the sub-policies:
KL [[s))]][[(]))]] KL क ([s))la())))))
(2)
In this setting, the n KL-divergences can be computed independently in parallel and then summed to obtain the final di-deieeeeece.
Proposition 2.2 When the two policies are autoregressive, we have:
KL (-]))))) = (ea)x((1))
Σ KL [- ") (1
this setting, similarly to the Shannon entropy, we use this result to form an estimate where the enriched states are computed from sequence of actions sampled according to r(-ss). Importantly, the sequence of actions used to sequentially compute the sub-distributions must be the same for and μ.
FACTORED AGENTS
In this section, highlight the impact of factorizing the action space and of the chosen factorization approach for the policy. In particular, we study two state-of-the-art algorithms, PPO (on-policy) and SAC (off-policy), and show how adapt them to both factorization settings. We provide guidelines and practical tips to make the factorization work in practice. The relative performance of these algorithms is evaluated in Section 6
5.1 POLICY ARCHITECTURE AND ACTION SAMPLING
We consider a stochastic policy network taking an environment state E S and returning proba- bilities over the actions a A.
When the sub-policies are independent distributions, the policy network is composed of n heads, each taking either directly the state an embedding of the state computed by shared neural net- work between all heads. The tth head returns probabilities over the ith action component a' E A; The action components are sampled independently and the probability of the resulting action is com- puted as the product of the components probabilities. As the action components are independent, their sampling can performed in parallel.
When the policy is autoregressive, the policy network is also composed of n heads. However the 7th head takes as input not only the state or an embedding but also an encoding of the first i selected action components. This encoding can be engineered model. Thus, the th head returns probabilities over the tth action component a' A, conditioned on the choice of the first i 1 action components (a ...., a d)- Therefore, the action components must be sampled sequentially. As above, the resulting action probability is computed as the product of its components probabilities.
computed through a recurrent

---

Under review as a conference paper at ICLR 2021
5.2 PROXIMAL POLICY OPTIMIZATION
The Proximal Policy Optimization (PPO) algorithm (Schulman et al. (017) is an on-policy algorithm using a stochastic policy wy and value function Vo. It replaces the policy gradient by surrogate loss to constrain the size of policy updates. The policy parameters are updated so as to maximise this loss. An entropy term H(T (.]s) and Kullback-Leibler distance between the current policy distribution and its version before the update can be added as regularization terms to further stabilize the training"
More formally, policy parameters are updated by gradient descent so as to maximise the following expression:
(0) min
H(To(Ils))
where Å is an estimate of the advantage and is computed from the target network Vo using the Generalized Advantage Estimation method (GAE) (Schulman et al. 2015). The r(0) term denotes the policy ratio r(0) =owsala(s)
mo(ale) where Poid are the parameters before the update.
The value network is trained to minimize the mean squared error between its prediction and an estimation of the return. This estimation can be computed from the advantage estimate. More formally, the value function parameters are updated to minimize:
(v Vo(s)) (À Veace (s))
As the value network only depends on states and not on actions, its architecture and update rule not impacted by the factorization of the action space. It impacts only the policy architecture and its update expression. More precisely: (a) The policy architecture and the way the actions are sampled are modified as explained in Section 5.1 (b) Both me (als) and (a(a))) are computed by multiplying the probabilities given by the sub-distributions over the action components; (c) The
Shannon entropy and the KL--divergence terms are computed as explained in Sections 4.1 and
5.3 SOFT ACTOR CRITIC
As illustrated with PPO, factorizing the action space of RL algorithm using the V-value function is easy. However, things get more complicated when using a Q-value function, as actions involved in the critic. We give a concrete example with the Soft Actor Critic (SAC) (Haarnoja et al. 2018) algorithm. SAC learns a stochastic policy π¹ maximizing both the returns and the policy entropy. It maximises sums of augmented rewards sac a (r(sss)) where is temperature parameter controlling the importance of entropy versus reward, and thereby the level of stochasticity of the policy. SAC trains policy network TT. for control and soft Q-function network Qo and relies on replay buffer D. While the original SAC paper proposes derivations to handle the continuous action setting, the algorithm has been then extended handle discrete action spaces (Christodoulou, 2019). We use the discrete action derivations as a basis to derive its factored versions. SAC relies on soft policy iteration which alternates between policy evaluation and policy improvement. To extend this algorithm factored action spaces, parameterize the policy explained in Section[5..
CRITIC ARCHITECTURE
A naive parameterization of the critic would use a Q-value function taking a state-action pair as input and returning a scalar value. As there are n1 ... x nn possible actions, training Q-value under this form quickly becomes intractable as the action space grows. To avoid this, we consider a sub Q-value for each action dimension.
In the independent factorization setting, the action components are selected independently, thus we consider n independent sub Q-value functions Q' S > A, which take state s and return one Q-value per possible action in A, The Q-value function Q' estimates the average return from
'The entropy term is not specified in the original paper, but can often be found in available implementations such in RI.bblon Spiinnnng Up
5

---

Under review as a conference paper at ICLR 2021
state given the sub-action chosen by policy n², regardless of the other sub-actions chosen, i.. as it had to assume that the other sub-actions were chosen by the environment. By maintaining these independent Q-value functions, one can perform independent policy evaluation steps in parallel as well as n independent policy improvement steps in parallel. We also consider n. independent temperature parameter (z; control the entropy versus reward trade-off for each action dimension.
In the autoregressive setting, the action chosen by a sub-policy n is conditioned on the i previously chosen action components (a* (a',...,dd 1 To give proper meaning separate Q- values in this framework, we reuse the formulation proposed by Metz et al. (2017) and consider two MDPs: the top MDP corresponds the MDP at hand in which the action space factored; the bottom MDP is an extended version of the top one. Therefore, between two top MDPs states and 8141, we consider the intermediate states ut. For the value functions to be equal both MDPs, we set = 0 and = 1 each intermediate state. In this formulation, the Q-value function Q' : 14-1 - A, can be interpreted as an estimate of the average return from a intermediate state w' given the action choice of policy n². We also introduce
extra Q-value function, dubbed "up Q-value", Q x A + IR that estimates the return of the policy the top MDP. We consider temperature parameters ag one per action dimension in the bottom MDP, well as global temperature parameter a to control the entropy versus reward trade-off in the top MDP.
Below detail the impact of both factorization approaches the soft policy evaluation, this is where most changes are necessary. See Appendix A for the detailed derivations of the policy improvement step and the automatic entropy adjustment step.
SOFT POLICY EVALUATION
To evaluate policy म. Haarnoja et al. (2018) introduced the soft state value function defined as
(s+)) IE (.1x)) [Qo(s,, ax) log (T<(s))))))
To compute (s;), one must compute an expectation over the distribution IT (T(. In the continu- ous action setting, computing this expectation is replaced by an expectation over a Gaussian using the re- pe-arammetrrizaionn trick, thus reducing the variance of the estimate. In the discrete action set- ting, this expectation can be computed directly through an inner product, thus leading to smaller variance estimate of the soft value, see Appendix AA. for more details. Note that, while in the con- tinuous action setting the Q-value network takes state and an action and returns a scalar value, its discrete version takes state and returns scalar value for each possible action. Finally, the soft Q- Q-value network is trained to minimize the soft Bellman residual:
JQ(0) (s DDD [Qo(s), a.) (r. + (
(5)
Independent Factorization setting. When the sub-policies are independent distributions, the n sub Q-value functions parameters are updated so to minimize the soft Bellman residual in Equa- tion (5) where Qo is replaced by Q3 and the soft value term V(8++1) replaced by (*(++1) computed as
((ss)= [Qb(st.)) az log (TT{(1
where (s:.)) stands for the vector of Q-values over A given state st. As these equations are independent from each other, all the updates can be performed in parallel.
Autoregressive Factorization setting. When the policy autoregressive, the first n 11 sub Q- value functions are updated so as to minimize the soft Bellman residual in Equation (5) where r == 0, = 1, (0 ax) is replaced by (u( [-1 ,aat) and the soft value term V(8+1) is replaced by (ut) This term computed using (6) where states 8, E S are replaced by sub-states
ui 11 E U4-1, see Appendix A.2 for more details.
The up Q-vauue function is updated using and (5) where the expectation over the distribution (.(;)) is replaced by an estimate using one action sampled from n3 (-1ss). The last sub Q-value is updated to enforce equality between values in the top and bottom MDPs:

---

Under review as a conference paper at ICLR 2021
JQ (0) = (s, an) DDD (Q "aa)) -00)--000 (st, (a))
On one side, training the up Q-value overcomes the credit assignment problem induced by the zero reward in the bottom MDP. However, mentioned before, relying this Q-value alone does work in practice. On the other side, training the sub Q-values enables computing a better estimate of the expectation over the distribution T (-18)).
6 EXPERIMENTAL STUDY
We illustrate the efficiency of FARL on three different use cases. First, we show that factored action spaces are well suited to solve problems which actions are composed of a discrete part and a continuous part, i.c. parameterized hybrid action spaces. Second, we show that the autoregres- sive property can be used in multiagent problems. We use PPO in the challenging Google football environment Kurach et al. (2019). Finally, we evaluate our agents in discretized MuJoCo envi- ronments and show that independent factored policies match continuous action ones even in large dimension and can learn even with millions of possible actions. See Appendix C.T for summary of the experimental setting and additional experimental details.
6.1 PARAMETERIZED ACTION SPACES
In this section, we highlight the benefits of autoregressive factorization in parameterized action spaces. We use the gym PLATFORM benchmark, introduced in Masson et al. (2016); Bester et al. (2019), in which an agent must solve platform game by selecting each step discrete action among hop, run or leup as well as the continuous intensity of this action. In the original problem formulation, the agent must return one discrete action as well as three continuous actions lying in different ranges. Only the continuous action corresponding to the discrete choice is applied. The environment contains three platforms as well as stochastic enemies to be avoided. The observation is vector of features. The return is the achievement percentage of the game: 100 corresponds to completion, i.e. the agent reached the extreme left of the platform. By reducing the action space through autoregressive factorization, the three continuous action spaces are transformed into one single discrete space containing m actions corresponding to discrete bins. The agent first chooses discrete action and then autoregressively selects among the m bins. The selected bin is converted into a continuous value depending on the discrete choice. Thus, there are 3m actions. With this transformation, both factored agents reach completion in a few time steps, see Figure Ic] We also observe that Factored PPO (FPPO) is more stable and has lower inter-seeds variance but reaches plateau score of 90% while Factored SAC (FSAC) shows more variability but is sometimes able to reach 100%.
6.2 MULTI-AGENT BENCHMARK: GOOGLE FOOTBALI.
In this section, we show that autoregressive factorization also performs well in agget problems. We tested FPPO in the Google football environment where Kurach et al. (2019) have shown good performance using IMPALA. As the authors, we conducted our experiments with the versus Keeper scenario from Football Academy, where we control team of 3 players who must score against an opponent keeper. Three types of observations exist in this environment. While the authors observed that their algorithms perform better with minimap pictures inputs, we performed well from raw vectors of features as can be seen in Figure Tb In the original study, single neural architecture shared between all players. Each agent receives a vector of general features as well as a one hot code corresponding to its number and chooses discrete action among 19. Thus, the total number of possible actions is 193 6859. Through autoregressivity. we consider only one agent that receives the global features and return sequence of discrete actions, one per player to be controlled. Therefore, instead of making choice among 6859 actions, our agent chooses three actions choices among 19 at each time step. We show that through this approach, PPO outperforms IMPALA with fewer computer resources. After 50M steps, reaches an averaged number of goals of 0.91 + 0.04 while IMPALA reaches 0.86 = 0.08 as reported in Kurach et al. (2019). FPPO was trained only for days on 4 CPU cores while IMPALA was trained with 150 CPU cores. The 4 trained agents played 10.000 episodes. Results are averaged over seeds.
7

---

Under review as a conference paper at ICLR 2021
To demonstrate the impact of autoregressivity in this setting, also performed an ablation study in which we kept the same architecture and hyperparameters but removed the autoregressive property. In this case, the PPO policy returns 3 actions, each depending of the environment observation but independent from each other. Figure Ta shows that, without autoregressivityy the ablation can still learn some behavior but quickly plateaus a poor local optimum while FPPO finds optimal strategy.
Milmoe MSC
(a) FPPO with and without the (b) Average goal difference (c) FPPO VS FSAC on PLAT- autoregressive property
evolution
FORM
Figure I: autoregressive factorization assessment. Figures a) and b) correspond to Factored PPO performance the Google Football 3 vs keeper environment. Figure e) compares FPPO and FSAC in the gym PLATFORM environment.
6.3 MUJoCo BENCHMARKS
Finally, we evaluate our factored agents on four well-documented MuJoCo benchmarks, HalfCheetah-v2. Hopper-v2, Walker2d-v2 and Humanoid-v2. We discretize each of the contin- uous action dimensions into m bins, resulting in m" actions. We use an independent factorization approach no inter-correlation between action components is needed for those benchmarks for both continuous versions of SAC and PPO. Indeed, these algorithms sample actions from Gaussian dis- tributions with diagonal correlation matrices. We chose observed low impact of this value on performance. Results are reported in Figure 2 We confirm the results from Tang Agrawal (2020) for FPPO and demonstrate that FSAC obtains comparable performance to its continuous version despite the discretization. Notably, FSAC performs well on factored Humanoid-v2 which has 10 possible actions, thus demonstrating the scalability of action independent factorization.
11 bins for the three benchmarks but
41000
41740 C0A40
1040
(a) HalfChectah-v2
(b) Hopper-v2
(c) Walked2d-v2
(d) Humanoid-v2
Figure 2: Independent factorization assessment. FSAC (in blue) vs FPPO (in purple) in factored Mujoco environments. We use independent factorization for both agents.
7 CONCLUSION
Factorizing action spaces leads to impressive results in several RL domains but remains under- exploited and understudied. In this work, we studied two factorization methods and highlighted both there theoretical impact update equations well as their practical use. We derived practical expression used either to compute or estimate Shannon entropy and Kullback-Lebler divergences. Notably, we showed that action space factorization is well suited for many problems and that these approaches can scale to large number of actions. We used the theoretical study to adapt PPO and SAC, two state-of-the-ar ahe agents, to both factorization settings and demonstrated their performance on several benchmarks. We believe that from these derivations and the implementation tips we provided, most of the existing RI agents can be easily adapted to factored action spaces.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In AAAI, pp. 1726- 1734, 2017.
Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. neural probabilistic language model. Journal of machine learning research, 3(Feb): 2003.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1912:699,, 2019.
Craig Bester, Steven D. James, and George Konidaris. Multi-pass q-networks for deep rein- forcement learning with parameterised action spaces, 2019.
Petros Christodoulou. Soft actor-critic for discrete action settings. arXiv preprint arXiv: 2019.
Olivier Delalleau, Maxim Peter, Eloi Alonso, and Adrien Logut. Discrete and continuous action representation for practical rl in video games. arXiv preprint
2019.
Thomas G Dietterich and Ghulum Bakiri. Solving multiclass learning problems via crror-correcting output codes. Journal of artificial intelligence research, 2:263-286, 1994.
Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, and Patrick Gallinari. Fast reinforcement learning with large action sets using coroe-coreetiin output codes for mdp factorization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 180- 194. Springer, 2012.
Gabriel Dulac-Amold, Richard Evans, Peter Sunehag, and Ben Coppin. Reinforcement learning in abs/
large discrete action spaces. CoRR, abs/1512.00679, 2015. URL 151 1.112.00 07679
Zhou Fan, Rui Su, Weinan Zhang, and Yong Yu. Hybrid actor-critic reinforcement learning in parameterized action space. arXiv preprint arXiv:1903.01344 2019.
Robert M Gray. Entropy and information theory. Springer Science & Business Media, 2011.
Cean-Bastien Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, Ioannis Antonoglou, and Remi Munos. Monte-carlo tree search as regularized policy optimization. In Proceedings of Machine Learning and Systems 2020, pp. 6610-6619, 2020.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft actor-critic al- gorithms and applications. CoRR, abs/1812.05905, 2018. URL http:t/aaxxxi.ooo/
1812.055 05905
Matthew Hausknecht and Peter Stone. Deep reinforcement learning in parameterized action space. arXiv preprint arXiv:1511.0414 2015.
Max Jaderberg, Wojeiech M Czamecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population-based reinforcement learning. Sci- ence, 364(6443)88598863 2019.
Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Car- los Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, al. Google research football: A novel reinforcement learning environment. arXiv preprint arXiv: 1907:1197..11880 2019.
Andrew Levy, Robert Platt, and Kate Saenko. Hierarchical actor-critic. 172iv:1712.00044, 2017.
arXiv preprint
Andrew Levy, Robert Platt, and Kate Saenko. Hierarchical reinforcement learning with hindsight. arXiv preprint arXiv: a 1805.08011881111 08/80, 2018

---

Under review as a conference paper at ICLR 2021
Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs, 2020.
Warwick Masson, Pravesh Ranchod, and George Konidaris. Reinforcement learning with parame- terized actions. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Luke Metz, Julian Ibarz, Navdeep Jaitly, and James Davidson. Discrete sequential prediction of 2017.
continuous actions for deep rl. CoRR,
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013.
5602
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation learning for hierarchical reinforcement learning. arXiv preprint arXiv:1810.01257, 2018a.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, pp. 3303-3313, 201 8b.
Jason Pazis and Ron Parr. Generalized value functions for large action sets. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 1185-1192, 2011.
Thomas Pierrot, Guillaume Ligner, Scott Reed, Olivier Sigaud, Nicolas Perrin, Alexandre Laterre, David Kas, Karim Beguir, and Nando de Freitas. Learning compositional neural programs with recursive tree search and planning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'Ach Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 14646-1656. Curran Associates, Inc., 2019.
Thomas Pierrot, Nicolas Perrin, Feryal Behbahani, Alexandre Laterre, Olivier Sigaud, Karim Be- guir, and Nando de Freitas. Learning compositional neural programs for continuous control, 2020.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint (XXiv:5506.024333 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks In Advances in neural information processing systems, pp. 3104-3112 12, 2014.
Yunhao Tang and Shipra Agrawal. Discretizing continuous action space for on-policy optimization. Proceedings of the AAAI Conference Artificial Intelligence, 3404))5981155888 Apr 2020.
ISSN 2159-5399. doi: 10. 10.16099aaai.v344444.oom
aaai v34104.6059
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. arXiv preprint arXiv:1703.0111 2017.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameeki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):35--554 2019.
Zhaoyang Yang, Kathryn Merrick, Lianwen Jin, and Hussein A Abbass. Hierarchical deep rein- forcement learning for continuous action control. IEEE transactions on neural networks and learning systems, 29111)517444114 2018.
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J. Mankowitz, and Shie Mannor. Learn what not to leam: Action elimination with deep reinforcement learning. CoRR, abs/ 1809,02291, 2018. URL http: //tp:v//aivvvvv.a org abs 02121
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
A FACTORED SOFT ACTOR CRITIC: ADDITIONAL DETAILS
A.1 EXPECTATION COMPUTATIONS
Several expressions minimised in SAC rely on an expectation over actions sampled according to the policy no- In the original version, SAC considers continuous action spaces and assumes a squashed Gaussian policy distribution. Actions are sampled from a Gaussian distribution parameterized by mean vector nog (s) and diagonal covariance matrix (s)., both returned by neural network of weights 0. Then the actions are scaled by a tanh function. More formally, a = tanh (e) where
N (Ho(s)) (s))). This expression can be rewritten as a tanh (oo(s)2 + (o(()) where ~ 1). This is called the reparametriization trick; instead of sampling from a distribution which depends on the neural network weights, we sample from standard normal distribution and apply linear scaling. This trick enables to rewrite the expectation (oolle)))) that depends on O as an expectation over the 1E=N((011) This trick allows to reduce the variance of this expectation estimate, thus allowing to compute it in practice.
When the action space is discrete, common choice for the policy distribution is a categorical distribution over actions. In this case, the policy neural network outputs a softmax over the possible actions. This parametrization enables to compute the exact expectation over actions without having to rely on an estimate. Indeed, this expectation can be computed simple inner product:
= Ea- [f(a, [|] (o(ls)) ((.)))
where 8 A contains all the values of f for each possible action a. Using this expression reduces the variance of both the actor and critic losses. We use this expression to construct the losses expressions in the factored action settings.
IR is a scalar function and ((,,s) = s)..,, s)] is a vector that
A.2 SOFT POLICY ITERATION
We demonstrated that in the independent factorization setting, we can use sub-policies and n sub- Q- Q-values, one per action dimension, and update them independently in parallel as if we were solving parallel MDPs, one per dimension. While this introduces some instability as the reward obtained by one sub-agent depends on the other agents decisions, we observed that this strategy works well in practice. We hypothesize that this performance comes form the fact that modifying the behavior of other agents is slow enough for one agent to improve its own behavior as if the MDP was stationary.
In the autoregressive factorization setting, such a strategy cannot work agents choices are con- ditioned on choices of other agents. In this situation, as explained in Section 5.3] we consider two MDPs: the top MDP that corresponds to the MDP at hand in which the action space is factored, and the bottom MDP which is an extended version of the top one. Between two top MDPs states 8t and 1, we consider the intermediate states ut. We apply to these intermediate states a discount factor that equals 1 and a zero reward so as to ensure value equality on the shared states between both MDPs. In this case, the sub-Q-valus functions estimate the Q-values on bottom states: Q3 es- timates Q-values for states - We also consider a Q-value function Q estimating returns on top states. Both Q-values types are complementary: the top Q-value suffers from the large number of possible actions. The sub-Q-values do not have this issue as they rely on smaller number actions, i.e. the number of actions per dimension, but suffer from the credit assignment problem induced by the extra zero rewards. We observed that training the top Q-value alone does not work, however adding these sub-Q -abuuss enables learning. On one side, we train the up Q-value as to minimize soft Bellman residuals in the top MDP, see (5) and on the other we train all Lub-Q-valuee except the last one, to minimize soft Bellman residuals in the bottom MDP:
(0) E (
(vt ..a)) (ra + y (ut))
n,
(9)
where (2(((_n) = Bar (ut a.) - a log (T²² (u. - 1s)) Finally, the last sub Q- value is updated enforce equality between values in the top and bottom MDPs:
11

---

Under review as a conference paper at ICLR 2021
JQn (0) E ar) (Q ,aft) - (st, ai))
(10)
Note that in all previous expressions, the expectation over actions has been sampled through an inner product as explained in (8)
A.3 SOFT POLICY IMPROVEMENT
The policy improvement step updates policy Th by minimizing the cost function:
J= (Ø) Fer (a log To(a (8)) (s,,,,
As before, the expectation approximated by a Monte Carlo estimate in the continuous action setting replaced by the true expectation the discrete action setting.
When the sub- sub-policies are independent distributions, the sub-policies parameters are updated in- dependently so as to minimize:
(+) = n (-(s))))) [ox, log m/((11))) Qb )] Isisn.
(11)
When the policy autoregressive, the n sub policies are updated so to minimize the same loss in which states &; S are replaced by sub-states ui-1 E Ui-1- Each sub-policy is updated from its corresponding sub Q-value function.
A.4 AUTOMATING ENTROPY ADJUSTMENT
The entropy adjustment coefficient a can either be fixed as an hyper-parameter or updated online so as to ensure that the policy entropy does below an entropy target value H. Haarnoja et al. (2018) show that a can be updated at each iteration so as to minimize
Jaa) (aws)o()))) [-ax (log No (a(s)) + H}]
(12)
In this work, we express the entropy target as a fraction E [0. 1] the maximum entropy, i.c. the entropy of the uniform distribution over A that note Hy. We give some expressions of H.
corresponding to different action spaces in Table
Table I: Uniform distributions entropies.
Action space
Entropy of uniform distribution
A = [1, 11....m. nn 1, 1)m
H. = log
H. n log 2 n H. > i-1 log n2
A A x An
When the factorization is independent, we simply minimize independent losses, one for each sub-entropy coefficient o;:
J(as) =T((1s) [-a; (log r/(ss) +1,)]
(13)
where H. 3 log (n:).
When the factorization is autoregressive, we minimize the same losses where states are simply replaced by sub-states ui-1, We also optimize the entropy coefficient for the top MDP a by mini- mizing expression (12) where the entropy target is computed H B D' log (n:). We found in practice that the choice of parameter & has the greatest impact on performance. We show an example on the Humanoid-v v22 benchmark in Section C.2
12

---

Under review as a conference paper at ICLR 2021
B PROPERTIES OF FACTORED POLICIES PROOFS
B.1 SHANNON ENTROPY
PROOF PROPOSITION 1.1
When the policy x is factored into independent sub-policies, partial actions a² depend only on the state In this case, the entropy of the policy is by definition the joint entropy of the random variables associated to each partial action. Furthermore, this joint entropy is equal to the sum of the entropies of each sub-policy, due to the additivity of entropy for independent random variables:
H(((s1))) =
Σ
x (als) log (TT(a)s)
a= u JEA JEAIX XA,
Σ
II i=
ah' (a'ls) log II n' (ad)ss)
EA1 XAn
H(T (1ss).
see Gray 2011) for proof of the additivity of the Shannon entropy for independent random variables. In the case of two discrete independent random variables X and Y, can be demonstrated as follows:
Remark:
H(X,Y)= = - Σ P(x, y) log (P(x,
Σ P(x) log (P(x))
Σ P(z) log (P(y))
Σ P(x) log (P(x))
Σ P(y) log (P())
H(X) + H(Y).
PROOF PROPOSITION 1.2
When the discrete random variables and Y are not necessarily independent, the more general equation is that the joint entropy is equal to the sum of the entropy of X and the conditional entropy P(x.9)
X((())== = ---6 P(æ, v) log
P(x)
m.
H(X,Y) = ((X)))++()+++++ ((())+((11X))
can be expressed as an expected value:
Σ P(a) P( v)
((x,
H(X,Y) = H(X)
log
P(x)
P(x)
=((X) Σ P(x) Σ P(yl=) (P())=)
H((X) EE [x)]]
Or for three random variables: H(X,Y,2)
[H(Y + Er [H(2 xz, v)). and this
can be generalized further. Applying autoregressive policy (a]ss) I (a' (ud
yields the following equation:
(()())))) H(T (cls)) [H[ 1 (1lxt))] [=( ++ FF [H( (1' (-|um>1))]
13

---

Under review as a conference paper at ICLR 2021
which can be written:
Σ H(T (((r((1u-)))
H((((1s)) = (.1o)
B.2 KULLBACK-LEIBLER DIVERGENCE
PROOF PROPOSITION 2.1
Let us consider 4 independent discrete random variables X, Y, X' and Y', X and X' having same support and respectively probability mass functions p and p', and Y and Y" having same support and respectively probability mass functions q and q'. We denote by H(X, Y| Y") the cross-entropy between the joint distributions of X, Y and X X',Y':
H(X, (
Σ loge)a
We have:
H(X,YII Y") = Σ (og ((z))(1)) log
2,8
3.
Σ logr'
Σ logd
Therefore:
H(X, YIIX', -(XII*+++++ H(YIIY")
The Kullback-Leibler divergence, cross-entropy and entropy are linked by the following formula:
KL|Z||IZ2| = H((z)lZ))) H((2).
Using the additivity of entropy for independent random variables:
KL(X,Y||X' y X(X,YIXXX X)X,Y)
-H(XIIX') + H(Y[|Y') - - ((X)--(() H(Y)
-H(XIIX') + H(Y[[Y') - -(())) - H(Y)
-KL[X|XX] KL[Y][""]
This can be generalized to joint distributions of more than independent discrete random variables. Applied the context of policies in factored action spaces, and assuming that and μ are two policies such that (ss.a) E S x A, r'(als) = I n mr(aal>) and μ² (a(s) I [ (a*)s,, it results in
KL [=(()))|
Σ KL IT (1s))l
PROOF PROPOSITION 2.2
As in the proof of the previous proposition, we consider discrete random variables X, X', Y and Y". X and X' have the same support and are independent, Y and Y have the same support and are independent, but this time X and Y are not independent, and X' and Y' are not independent. We respectively denote their joint probability mass functions by p and Without ambiguity, we also denote by p and the marginalizations over y: p(x) E, p(a,, y) and q(v) = E, 9(5
14

---

Under review as a conference paper at ICLR 2021
Let us consider the cross-entropy between the joint probability distributions of X, Y and X', Y
H(X,Y ,IIX', Y") - Σ p(z, u) log g(x, v)
2,91
Σ 2,8
pzz, v) log ((2, v) +
Σ p(a, y) log Σ
p(z, v) log ((x)
2,9
((5,1))
Σ 2
p(,, v) log
Σx(e p(x) logg()))
((x)
p(a, 8)
g(r,y) 4)
Σp(w) p(x)
log ((x)
Ep(x) p(x) logg(z)
p(r)
2,81
Σ p(x) Σ p(y( log (ug(()))) - Σ [o(z)log((s))
x
-(X||X') + IF (YM
Using the equality [L lZZ)l1Z2) H(ZZ), and the equality derived in the proof of Proposition 1.2, we get:
KL|X, XIX,, H(XIIX' + Eapp [x (2 - H(X,Y) Y) -X(II*) H(X) IF 1P2zup (H x [=]]]
IFap [H({|z))]
KK |X + 1xpop KL | Y [r]]
Similarly, for random variables X, Y, Z and X', Y', Z', we obtain KL[X, Y. X| Y", z KI. X X'I+ Frop [X]
|Z||0: [KI, y 1/
v)
Again, the equation can be generalized to joint distributions of discrete random variables. In the context of autoregressive policies, assuming that π and are two policies such that V(s, a) e S A, (a(ss) = II= n (a'lu'²-) and n² (a(ss) I (a" (w--)), results in
n KL x (-(u"= ( (lut
KL ([]ss) Eaax((1))
15

---

Under review as a conference paper at ICLR 2021
C ADDITIONAL EXPERIMENTAL RESULTS
C.I EXPERIMENTAL SETTING SUMMARY
Table 2: Experimental setting summary
Environment
Nb of actions dimensions
Nb of actions
Total nb ac- tions
Factorization
per dimension
Google Football
6859
Autoregressive
Platform
(3, 21)
63
Autoregressive
Humanoid-v2
17
11
5e17
Independent
HalfCheetah-v2
1.7c6
Independent
Walker2d-v2
6
11
1.7c6
Independent
Hopper-v2
1.8e5
Independent
C.2 IMPACT OF ENTROPY TARGET STUDY
We study in Figure the impact of coefficient 3 that defines the entropy target the agent perfor- mance. This parameter defines the balance between exploration and exploitation. When its value tends to 1, a is tuned so as to maintain policy entropy near the maximum entropy while when its value tends O, the policy becomes almost deterministic. We observe that Humanoid-v2 this value must remain small so as to ensure convergence.
entropy target
4000
target 0.25
3500
entrapy target 0.1
entropy target 0.05
3000
entrapy target 0.025
mean rewards
2500
2000
1500
1000
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Figure 3: Study on the impact of the entropy target in FSAC on the Humanoid-v2 environment. Each run has been averaged over 4 seeds. In this example, all dimensions share the same entropy target H, = log 17. Each run represented corresponds to a different value parameter 3.
16

---

Under review as a conference paper at ICLR 2021
C.3 HYPERPARAMETERS
Table 3: Hyper-parameters for the MuJoCo environments
(a) FPPO
(b) FSAC
Parameter
Value
Parameter
Value
Optimizer
Adam
Optimizer
Adam
Learning rate
3. 3.10
Learning rate
3.10 44
Discount factor
0.99
Discount factor
0.99
Number of bins per dimension
11
Number of bins dimension
11
Clipping epsilon
Replay buffer size
108
KL coefficient
0.2
Hidden layers size
256/256
Lambda GAE
0.95
Activations
ReLU
Hidden layers size
256/256
Minibatch size
256
Activations
ReLUU
Target smoothing coefficient
0.005
Minibatch size
128
Entropy target
0.05, 0.1, 0.5
Number of epochs
20
"respectively 0.05 Humanoid-v2, B 0.1
Memory size
2048
in HallCheetah-v2 and Walker2d-v2 and , 0.5 in Hopper-v2
Table Hyper-parameters the PLATFORM environment
(a) FPPO
(b) FSAC
Parameter
Value
Parameter
Value
Optimizer
Adam
Optimizer
Adam
Learning rate
5.10-5
Learning rate
3.10
Discount factor
0.99
Discount factor
0.99
Number of bins per dimension
21
Number of bins per dimension
21
Clipping epsilon
0.2
Replay buffer size
10
KI. coefficient
0.2
Hidden layers size
128/128
Lambda GAE
1
Activations
ReLU
Hidden layers size
128/120 128/128
Minibatch size
256
Activations
ReLU
Target smoothing coefficient
0.01
Minibatch size
64
Entropy target
0.5
Number of epochs
20
Memory size
512
Table 5: FPPO hyper- parameters for the Google Football environment
Parameter
Value
Optimizer
Adam
Learning rate
3.10-1
Discount factor
0.99
Clipping epsilon
0.08
KL coefficient
0.2
Lambda GAE
0.95
Hidden layers size
256/256
Activations
ReLU
Minibatch size
375
Number of epochs
2
Memory size
3000
17


Reviews:
[{"review_id": "si4h0Z-Xw9G", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n\nThe paper studies policy optimization in multidimensional action spaces. They consider atomic factorization of the action space (i.e. action space is factored into sub-action spaces, one per action dimension). In this setting, the authors consider two well-known policy representation techniques: 1) independent sub-policies (diagonal-covariance policies over the sub-action spaces) and 2) sequential/autoregressive policies (an ordering of the sub-action spaces is assumed a priori and the sub-policies receive as input the state and the selected sub-actions for the preceding sub-action spaces). The authors develop methods based on these two factorization techniques for discrete versions of PPO and SAC (called FPPO and FSAC) and evaluate them on Gym Platform, Google Football, and discretized MuJoCo tasks.  \n\n##########################################################################\nReasons for score:\n\nI believe this paper fails to position itself appropriately with respect to the literature. This makes it difficult to assess what the main contributions are and whether sufficient new methodology is proposed. Additionally, the paper misses on several fundamental experiments for the results to be convincing. Also, the paper does not set a clear agenda for what would be interesting to see in the results; Is scalability to large action spaces being investigated (in which case, comparison with the non-factored baselines of PPO and SAC should be included)? Is it the improvements of the discrete versions over the continuous versions of the methods that are interesting (in which case, the results for the continuous versions on the MuJoCo tasks should be reported)?  \n\n##########################################################################\nPros:\n\n- Factorizing action spaces is an interesting approach for scaling to high-dimensional action spaces. Also, they have been shown in several recent studies to enable discrete-action methods to outperform numerous continuous-control methods. So studying them more extensively is useful. \n\n- The paper nicely outlines how PPO and SAC should be configured to work with independent and autoregressive policies under the atomic factorization of the action space. \n\n##########################################################################\nCons:\n\n1) The paper generally does not position itself appropriately with respect to the literature. Below is my overview of the paper with additional related works (some are suggestions that would enhance the paper):  \n\n- Branching Q-learning (BQL) in Ref. [I] is similar (if not the same) to the independent critic of FSAC. Using this approach they scale to domains with 33^17 discrete actions. \n \n- Autoregressive critic of FSAC is the same as that in Metz et al. (2017) (also stated in the paper I believe).\n\n- Independent versions of numerous PG methods have been previously developed and studied extensively by Tang and Agrawal (2020). Also, the original TRPO paper was used with independent discrete sub-action policies in Atari tasks (if I remember correctly). Therefore, there is nothing new about FPPO-independent (also stated in the paper I believe).  \n\n- Other methods for learning the independent critic in FSAC are also possible but are not discussed in the paper (see e.g. Ref. [II]). Moreover, Ref. [II] uses independent policies with A2C.\n\n- When independent policies are used in PG, a better baseline can be used which provably reduces variance [III]. Discussion of such a baseline would be very useful in this paper which somewhat serves to summarize deep RL in factored action spaces.\n\n- Ref. [IV] combines autoregressive and independent proposal policies for approximate Q-maximization in Q-learning. In this way, they scale to very high-dimensional action spaces. This work is able to handle hybrid action spaces without discretization. A discussion and positioning with respect to this paper could be valuable.  \n\n\n2) Experiments fall very short in my opinion. Below are some of the experiments that I think are necessary to include: \n\n- Figure 1a,b: Why not run FSAC?\n\n- Figure 1c: I believe the autoregressive FPPO and FSAC are reported in Platform. But why not independent? Why not report the standard (non-factored) baselines of PPO and SAC?\n\n- Figure 2: Compare against the continuous versions of SAC and PPO on MuJoCo.\n\n- Figure 2: Why not evaluate autoregressive policies in MuJoCo? Metz et al. did that with DQN.  \n\n\n3) No new factorization schemes are explored in this paper. For instance, Ref. [V] explores a mixture of independent and sequential action-value function representations. A discussion of the spectrum of other possible factorizations would be interesting. \n\n\n[I] Action Branching Architectures for Deep Reinforcement Learning, AAAI 2018.\n[II] Learning to Factor Policies and Action-Value Functions: Factored Action Space Representations for Deep Reinforcement Learning, arXiv 2017. \n[III] Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines, ICLR 2018.\n[IV] Q-Learning in enormous action spaces via amortized approximate maximization, arXiv 2020. \n[V] Inferring DQN structure for high-dimensional continuous control, ICML 2020. \n\n##########################################################################\nQuestions during the rebuttal period:\n\n1) In light of new related works together with those included in the paper, I believe the novelty of the paper currently is in developing the policy optimization updates for autoregressive policies. The rest (independent policy optimization updates, independent critic, and autoregressive critic) are not novel as far as my assessment goes at this point. Is this correct?  \n \n2) Does \"without autoregressive\" (in Figure 1) imply \"independent\"? Or does it refer to the standard (non-factored) versions of PPO and SAC? If not, I need clarification on what it exactly means.\n\n3) This paper considered stochastic policies. I'm curious about any potential use for extending it to deterministic policies; e.g. could it be useful to use an autoregressive policy network with DDPG?\n\n4) I think that the manual ordering of the sub-action spaces in an auto-regressive policy could introduce bias (i.e. I think there could be a setting that some orderings would make it impossible to learn the optimal policy). Can you comment on this?\n\n##########################################################################\nMinor comments:\n\n- The title is too broad in my opinion. Unless the paper also incorporates analysis and results for purely action-value methods (e.g. DQN-based agents such as Sequential and Branching Q-learning), the paper should specify that policy optimization methods are of focus. Also, stating atomic factorization in multidimensional action spaces instead of only \"factored\" could clarify the kind of factorization that is the subject of this paper.   \n\n- \"FPPO was trained only for 2 days on 4 CPU cores while IMPALA was trained with 150 CPU cores.\":\nThis is not very useful without providing training-time of IMPALA.\n\n- The word action is frequently used instead of action dimension and sub-action.\n\n- \"With this transformation, both factored agents reach completion in a few time steps, see Figure 1c\": \nSaying \"a few time steps\" for a plot that goes to 90k time steps is somewhat strange.  \n\n- This work claims to develop techniques for dealing with hybrid action spaces. But in the experiments, this is not demonstrated. In fact, the action space in Gym Platform features discrete and continuous sub-action spaces, but they are discretized. As such, I think this paper should state dealing with discrete action spaces or continuous ones via discretization. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5DCNyzPK6y", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\nThe paper presents a study of factored action spaces for RL problems, and two basic forms of this,\ni.e., independent factorization (IF) and autoregressive factorization (AF).\nNote: these acronyms are my own. Building on these two types of factorization, the paper presents: \n(a) derivations of the entropy and KL-divergence for these policy factorizations;\n(b) PPO and SCA adaptations for IF + AF; and\n(c) three categories of experimental results.  \nThe experiments compare, in separate scenarios:  (i) AF-PPO vs AF-SAC; (ii) AF-PPO vs IMAPLA and non-autoregressive F-PPO; \n(iii) IF-SAC vs IF-PPO. \nOverall, the experiments show some of the possible potential of factored action spaces with PPO and SAC.\n\n### Strengths\n- I believe that factored action space are an under-explored area of research, and \n  understanding the benefits and limitations of these factorizatios is an important area,\n  as well as understanding how popular algorithms such as PPO and SCA can be adapted to use these factorizations.\n- The adaptations of PPO and SCA and the related derivations, while not entirely surprising, are useful.\n- The experiments show some of the potential of factored action spaces, both IF and AF.\n  The experimental parameters appear to be well documented, c.f., Appendix C.3.\n\n### Weaknesses\n- There are no guidelines or experiments to help determine when the factored approaches should be used,\n  i.e., when do they do better and when they do worse.  When is it harmful to use a factored approach?\n  Similarly, when should IF vs AF be used?  \n- Related to the point above, the experiments generally reflect the idea that the implementations can be made to work on some examples, rather than understanding where these factored actions spaces sit in the broader universe of algorithmic choices. What motivated the given choices of three benchmark problems, and the specific  (limited) comparisons shown for each benchmark?  It is difficult to fully understand the \"take home message\"  of each of the experiments.\n- It would be good to understanding more about the relationship with possible continuous action derivations\n\n### Recommendation\nI am on the fence regarding this paper.\nExploring and understanding factored action spaces is important, and the paper presents a reasonable step\nin this direction, and will therefore provide a foundation for further work.\nHowever there is little provided in the way of insights as to understanding the types of situations\nwhere factored representations should be used, and how this plays our for PPO and SCA.\nIf pressed, I currently lean slightly in favor.\n\n### Questions\n- What is the impact of the action ordering for the autoregressive factorization?\n- It is stated that there is no inter-correlation between action components for the MuJoCo benefits.\n  What evidence do you have for this?  The statement is unintuitive to those working on continuous control problems.\n  Why can't there be multimodal areas of the state space where the action decisions need to be coordinated?\n\n### Additional Feedback\n- section 5.3 Critic Architecture\n  \"As there are n1 ... nn possible actions\".  The notation is flawed, given that n is used to represent \n  both the number of dimensions and the discretization. Similarly, later it is stated:\n  \"these independent n Q-value functions\" is confusing, given that each of N dimensions presumably each need n Q-value\n  functions in the discrete action setting.\n- section 5.3 \"we reuse the formulation proposed by Metz et al. (2017)\n  and \"The top MDP corresponds to the MDP at hand in which the action space is factored\"\n  Should make it clear that this refers to Figure 1 of that paper.\n  And I would refer to the top MDP as being the original unfactored MDP.\n- section 5.3 Soft Policy Evaluation \"computed directly through an inner product\"\n  Could in include a forward reference to eqn (6)?\n- equation (5): missing right bracket\n- section 6.1 \"both factored agents reach completion in a few time steps, see Figure 1c\"\n  Figure 1c shows 20k - 40k timesteps, so while that is small, it is strange to call that \"a few time steps\"\n- section 6.2: \"our agent chooses three actions [sic] choices among 19 at each time step.\"\n  Why not explicitly state 3x19 = 57 choices at each time step (3 successive choices of 19 each).\n- The relationship to (Tang and Agrawal 2020) could be better explained.\n- A diagrammatic abstraction of the different forms of factorization could be very useful to the reader.\n\nUpdate:\n  After reading the other reviews and the responses, I have changed my score to 5: marginally below acceptance, due to the framing and related work issues, as discussed by R2 and R4.  There is potential here, but it will benefit from strong revisions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-hi2Tb0yWfC", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "##########################################################################\n\nSummary:\n\nThe paper highlights the difficulty of training with large action space in reinforcement learning. This is usually difficult due to the vast number of possibilities during exploration. They address this issue by studying existing approaches of splitting the action into a finite number of sub-actions and then sampling each sub-action independently or auto-regressively. This leads to a reduction in the candidate actions during exploration which would improve the sample efficiency.  Also, This splitting is referred to as “Factorization of Action Space”. \n\nThey majorly study this factorization with PPO and SAC and show how to estimate kl-divergence and entropy in each of these methods. Also, they introduce the notion of using independent q-values for each of the sub-actions which semantically represents expected “sub-action - value” for any action in the current policy with that sub-action.\n\nThey show their results on multi-agent and mujoco tasks.\n\n##########################################################################\n\nReasons for score: \n\nOverall, I do like the paper . However, at this moment, I will keep the paper below acceptance. This is due to the issues raised in Cons section which I believed should be addressed/discussed before I revise my score.\n\nIn particular, I would expect authors to have at least  PPO and SAC baseline in their work.\n \n##########################################################################\n\nPros: \n\n-Large action space has been one of the bottlenecks for scalability in reinforcement learning and the paper studies factorization for on-policy methods which to my understanding has not been done before. \n\n-They provide theoretical analysis for estimation of entropy and kl-divergence in PPO and SAC.\n\n-They show their results on both multi-agent settings as well as control.\n##########################################################################\n\nCons:\n\n- They merely make a comparison between FPPO and FSAC which are the factored versions of respective algorithms and show that FSAC seems to be more robust and has better sample efficiency. HOWEVER, they don’t make comparison with the unfactored ( original) versions of these algorithms. I believe without the comparison with the baseline PPO and SAC, one cannot establish the gain in sample efficiency.\n\n- The number of discrete sub-actions(“m”) for the policy is treated as a hyper-parameter. This is one of the core challenges for continuous control tasks as the environments could be highly sensitive to this choice. They don’t show any concrete evidence for the choice of number of sub-actions made by them, in particular for control tasks.\n\n- How does one decide on the order of the autoregressive actions? This is not clear from their work. Do they manually analyze each sub-action and decide on the order? I believe this order could play a significant role for performance.\n\n##########################################################################\n\nQuestions during the rebuttal period: \n \nPlease address and clarify the cons above \n \nOptional: \nYou may want to cite the following:\n\nQ-LEARNING IN ENORMOUS ACTION SPACES VIA AMORTIZED APPROXIMATE MAXIMIZATION (https://arxiv.org/abs/2001.08116).\nThis paper also talks about auto-regressive actions.\n\n\nThe following series of work involves the decomposition of Q-values for Actor/Critic and Q-learning approaches in multi-agent settings. The major difference is that instead of treating the reward as a vector where each reward component belongs to a specific q-values;  you are giving the same reward to each Q-value.\n \n- Value-Decomposition Networks For Cooperative Multi-Agent Learning\n- QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning\n- Hybrid Reward Architecture for Reinforcement Learning\n- Explainable Reinforcement Learning via Reward Decomposition\n\n##########################################################################\n\nI would be happy to revise my score post clarifications from the authors.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies two techniques for handling high dimensional action spaces in deep RL, namely selecting action components independently or selecting components sequentially in an autoregressive approach.  The methods are developed for two deep RL algorithms (PPO and SAC) and tested on multiple domains.

The reviewers recognized the significance of this research topic but found significant problems in the presentation.  The reviewers raised concerns on the relationship to prior work in the literature (R2), baseline comparisons that are missing in the experiments (R2, R4), and a lack of clarity in the intended message of the experiments (R3).  The authors responded favorably to the reviews, answered clarification questions, and acknowledged the limitations of the submitted work.  The authors expressed their intent to release a stronger paper sometime in the future.  The reviewers acknowledged the author response and were in consensus that the submission needs more work.

Three reviewers have indicated reject for the reasons described above.  The paper is therefore rejected.
Decision: Reject