Learning to Represent Action Values as a Hypergraph on the Action Vertices
Authors: Arash Tavakoli
Mehdi Fatemi
Petar Kormushev
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
structural credit assignment
structural inductive bias
multi-dimensional discrete action spaces
learning action representations

Abstract: Action-value estimation is a critical component of many reinforcement learning (RL) methods whereby sample complexity relies heavily on how fast a good estimator for action value can be learned. By viewing this problem through the lens of representation learning, good representations of both state and action can facilitate action-value estimation. While advances in deep learning have seamlessly driven progress in learning state representations, given the specificity of the notion of agency to RL, little attention has been paid to learning action representations. We conjecture that leveraging the combinatorial structure of multi-dimensional action spaces is a key ingredient for learning good representations of action. To test this, we set forth the action hypergraph networks framework---a class of functions for learning action representations in multi-dimensional discrete action spaces with a structural inductive bias. Using this framework we realise an agent class based on a combination with deep Q-networks, which we dub hypergraph Q-networks. We show the effectiveness of our approach on a myriad of domains: illustrative prediction problems under minimal confounding effects, Atari 2600 games, and discretised physical control benchmarks.

Published as a conference paper at ICLR 2021
LEARNING TO REPRESENT ACTION VALUES AS A HYPERGRAPH ON THE ACTION VERTICES
Arash Tavakoli
Mehdi Fatemi Microsoft Research Montréal
Petar Kormushev Imperial College London
Imperial College London
ABSTRACT
Action-value estimation is a critical component of many reinforcement learning (RL) methods whereby sample complexity relies heavily how fast good esti- mator for action value can be learned. By viewing this problem through the lens of representation learning. good representations of both state and action can facilitate action-valus estimation. While advances in deep learning have seamlessly driven progress in learning state representations, given the specificity of the notion of agency to RL, little attention has been paid to learning action representations. We conjecture that leveraging the combinatorial structure of multi-dimensional action spaces is a key ingredient for learning good representations of action. To test this, we set forth the action hypergraph nelworks framework-a class of functions for learning action representations in structural inductive bias. Using this framework we realise an agent class based a combination with deep Q-networks, which we dub hypergraph Q-networks. We show the effectiveness of our approach on a myriad of domains: illustrative prediction problems under minimal confounding effects, Atari 2600 games, and discretised physical control benchmarks.
discrete action spaces with a
INTRODUCTION
Representation learning methods have helped shape recent progress in RL by enabling a capacity for learning good representations of state. This is in spite of the fact that, traditionally, representation learning was less often explored in the RL context. techniques which are widely used in RL were developed under other machine learning paradigms (Bengio et al., 2013). Nevertheless, RL. brings some unique problems to the topic of representation learning, with exciting headway being made in identifying and exploring such topics.
such, the de facto representation learning
Action-valus estimation is a critical component of the RL paradigm (Sutton Barto, 2018). Hence, how to effectively learn estimators for action value from training samples is one of the major prob- lems studied in RL. We set out to study this problem through the lens of representation learning, fo- cusing particularly on learning representations of action in multi-dimension While action values are conditioned on both state and action and as such good representations of both would be beneficial, there has been comparatively little research learning action representations.
discrete action spaces.
We frame this problem as learning a decomposition of the vation-value function that is structured in such way leverage the combinatorial structure of multi-dimensional discrete action spaces. This structure is an inductive bias which we incorporate in the form of architectural assumptions. We present this approach multi-dimensional discrete actions by leveraging various orders of their underlying sub-action com- binations. Our architectures can be combined in succession with any other architecture for learning state representations and trained end-to-end using backpropagation, without imposing any change to the RI. algorithm. We remark that designing representation learning methods by incorporating some form of structural inductive biases is highly common in deep learning, resulting in highly- architectures such as convolutional, recurrent, and graph networks (Battaglia et al., 2018).
framework to flexibly build architectures for learning representations of
We first demonstrate the effectiveness of our approach in illustrative, structured prediction problems. Then, we argue for the ubiquity of similar structures and test our approach in standard RL problems.
"Correspondence Arash Tavakoli tavalvooo imperial.ac.uks

---

Published as a conference paper at ICLR 2021
Our results advocate for the general usefulness of leveraging the combinatorial structure of multi- dimensional discrete action spaces, especially in problems with larger action spaces.
2 BACKGROUND
2.1 REINFORCEMENT LEARNING
We consider the RL problem in which the interaction of an agent and the environment modelled as a Markov decision process (MDP) AS P, R, So), where S denotes the state space, A the action space, P the transition distribution, R the reward distribution, and So the initial-state distribution (Sutton & Barto, 2018). At each step the agent observes state S and produces an action at A drawn from its policy T.. 8t). The agent then transitions to and observes the next state 81+1 ES, drawn from P(. 8t, a1), and receives reward T141, drawn from R(. |1, ag 8(+1).
The standard MDP formulation generally abstracts away the combination of sub-actions that are activated when action a is chosen. That is, if problem has an NV'dimmesional action space, each action a maps onto an -tppl (a), "eE....,""" ). where each a; is a sub-action from the ith sub-action space. Therefore, the action space could have an underlying combinatorial structure where the set actions is formed as a Cartesian product of the sub-action spaces. To make this explicit, we express the action space as A = Ai X A2 x... Ay,, where each A; is finite set of sub-actions. Furthermore, we amend our notation for the actions az into a, (in bold) to reflect that actions are generally combinations of several sub-actions. Within our framework, we refer to each sub-action space A; as an action vertex. As such, the cardinality of the set of action vertices is equal the number of action dimensions N
Given a policy π that maps states onto distributions over the actions, the discounted sum of future rewards under ı is denoted by the random variable (s, a) = E 7'r,41, where 8g = 8, ag = a, $1411 ~ P(. 8z, a,), T++1 ~ R(. 8z, a,, $t+1), 1,, a, ~ T(. st), and y S 1 is discount factor. The action-value function is defined as Q=(8, = (s a)]. Evaluating the action-value function Qr of policy и is referred to prediction problem. In a control problem the objective is to find an optimal policy π² which maximises the action-value function. The thesis of this paper applies to any method for prediction or control provided that they involve estimating an action-value function. A canonical example of such a method for control is Q-learning (Watkins, 1989; Watkins & Dayan, 1992) which iteratively improves estimate of the optimal action-value function Q" via
( ar) Q(st, ar) + a (re+1 y max Q(5+11, a') Q( an)
(1)
where 0 S a < learning rate. The action-value function typically approximated using a parameterised function Qs. where 0 is a vector of parameters, and trained by minimising sequence of squared temporal-different errors
of = (re41 + Y max Q0(5++1, (o at))
a²
over samples (st. a,, 1,+1, 1)+ Deep Q-networks (DQN) (Mnih et al., 2015) combine Q-learning with deep neural networks achieve human-level performance in Atari 2600.
2.2 DEFINITION OF HYPERGRAPH
A hypergruph (Berge, 1989) is a generalisation of a graph in which an edge, also known as hyperedge, can join any number of vertices. Let V A2,,A...... Ay.) } be a finite set repre- senting the set of action vertices A,. A hypergraph on V is a family of subsets or hyperedges H = E1, Eg...., E such that
E, + 0 (j= 1j=1,2..... 1,",..,,N))
(3)
J=1 E, =V
(4)
According to Eq. (3), each hyperedge E, is member of غ P(V) (0, where P(V), called the powerset of V. is the set of possible subsets on V. The rank r of hypergraph is defined as the maximum cardinality of any of its hyperedges. We define c-hyperedge, where CE (1,2...., N.).
2

---

Published as a conference paper at ICLR 2021
(b)
(c)
Action Hypergraph Network block
N'
O
A
O
Mixer
B
v(()
E2
UB, (8)
f - Q((,
A
O
O
# outputs: [A Ar A
Figure 1: (a) sample hypergraph overlaid on physical system with six action vertices. (b) An instance building block of our framework for a sample hyperedge. (c) An architecture is realised by stacking several building blocks, one for each hyperedge the hypergraph.
as a hyperedge with cardinality or order c. The number of possible c-hyperedges on V is given by the binomial coefficient (N"). We define a c-uniform hypergraph as one with only e-hyperedges. As special case, c-complete hypergraph, denoted K is one with all possible e-hyperedges.
ACTION HYPERGRAPH NETWORKS FRAMEWORK
We now describe our framework using the example in Fig. 1. Consider the sample physical system of Fig. la with six action vertices (solid circles). A sample hypergraph is depicted for this system with four hyperedges (dashed shapes), featuring l-hyperedge, two 2-hyperedges, and 3-hyperedge. We remark that this set of hyperedges constitutes a hypergraph as there are no empty hyperedges (Eq. (3)) and the union of hyperedges spans the set of action vertices (Eq, (4)).
We wish to enable learning a representation of each hyperedge in arbitrary hypergraph. To achieve this, we create a parameterised function UE, (e.g. a neural network) for each hyperedge F, which receives state representation (s) input and returns as many values as the possible combinations of the sub-actions for the action vertices enclosed by its respective hyperedge. In other words, UE, has as many outputs the cardinality of a Cartesian product of the action vertices in E,. Each such hyperedge-specific function UF, is building block of our action hypergraph networks framework.! Figure lb depicts the block corresponding to the 3-hyperedge from the hypergraph of Fig. la. We remark that for any action one output that corresponds to a and, thus, contributes exactly one value as a representation of its respective hyperedge at the given action. This output UE (19(s), BF) is identified by a which denotes the combination of sub-actions in a that correspond to the action vertices enclosed by Ez.
(a a² a N²) from the action space A, each block has only
We can realise architecture within our framework by composing several such building blocks, one for each hyperedge in a hypergraph of our choosing. Figure Ic shows an instance architecture corresponding to the sample hypergraph of Fig. 1a. The forward view through this architecture is as follows. A shared representation of the input state s is fed into multiple blocks, each of which features unique hyperedge. Then, representation vector of size N is obtained for each action a, where N is the number of hyperedges or blocks. These action-specific representations are then mixed (on an action-by- eetion-by-action basis) using a function f (e.g. a fixed non- parammeerrri function neural network). The output of this mixing function is our estimator for action value at the state- action pair (s, a). Concretely,
(ss, (UEE
a
UEy: (1b(),, axx=)
(5)
While only single output from each block is relevant for action, the reverse is not the case. That is, an output from a block generally contributes to more than a single action's 's value estimate. In fact, the lower the cardinality of hyperedge, the larger the number of actions' value estimates to which a block output contributes. This can be thought of as form of combinatorial generalisation.
TTrouuhoutt this paper assume linear units for the block outputs. However, other activation functions could be more useful depending on the choice of mixing function the task.
3

---

Published as a conference paper at ICLR 2021
Particularly, action value be estimated for an insufficienty-explorce mixing the action's 's corresponding representations which have been trained as parts of other actions. Moreover, this structure enables capacity for learning faster on lower-order hyperedges by receiv- ing more updates and slower on higher-order ones by receiving less updates. This is a desirable intrinsic property as, ideally, we would wish to learn representations that exhaust their capacity for representing action values using lower-order hyperedges before they resort to higher-order ones.
unexplored action by
3.1 MIXING FUNCTION SPECIFICATION
The mixing function receives as input a state-conditioned representation vector for each action. We view these action-specific representation vectors action representations. Explicitly, these action representations are learned as a decomposition of the action-value function under the mixing func- tion. Without priori knowledge about its appropriate form, the mixing function should be learned by a universal function approximator. However, joint learning of the mixing function together with good decomposition under its dynamic form could be challenging- Moreover, increasing the num- ber of hyperedges expands the space of possible decompositions, thereby making it even harder to reach good one. The latter is due to lack of identifiability in value decomposition in that there is not a unique decomposition to reach. Nevertheless, this issue is not unique to our setting as repre- sentations learned using neural networks are general unidentifiable. We demonstrate the potential benefit of using a universal mixer (a neural network) in our illustrative bandit problems. However, to allow flexible experimentation without re-tuning standard agent implementations, non- non-parametric mixing function. This boils down the task of
our RL bench-
marks we choose to use summation learning action representations to reaching good linear decomposition of the action-value function under the summation mixer. We remark that the summation mixer is commonly used with value- decomposition methods in the context of cooperative multi-agent RL (Sunchag et al., 2017). In an informal evaluation in our RL benchmarks, did not find any advantage for universal mixer over the summation one. Nonetheless, this could be a matter of tuning the learning hyperparameters.
3.2 HYPERGRAPH SPECIFICATION
We now consider the question of how to spec- ify a good hypergraph. There is actually not an all-encompaasing answer to this question.
(a)
DON
((,,
For example, the choice of hypergraph could be treated as a way to incorporate a priori knowl- edge about specific problem. Nonetheless, we can outline some general rules of thumb. In principle, including many hyperedges possible enables a richer capacity for discover- ing useful structures. Correspondingly, representation is one that returns neutral val- ues (e.g. near-zero inputs to the summation mixer) for any hyperedge whose contribution is not necessary for accurate estimation of action values, provided that lower-order hyperedges are able to represent its contribution. However, as described in Sec. 3.1, having many mixing terms could complicate reaching a good decom- position due to lack of identifiability. Taking these into consideration, we frame hypergraph specification as choosing rank whereby specify the hypergraph that comprises all possible hyperedges of orders up to and including r:
(b)
K
N
Mixer
K²
ideal
HGON
V
f
((,
k
Figure 2: (a) A standard model. (b) A class of models in our framework, depicted by the ordered space of possible hyperedges E. Our class of mod- els subsumes the standard one an instance.
H = U KS
where hypergraph H is specified as the union c-complete hypergraphs K Figure 2b depicts a class of models in our framework where the space of possible hyperedges & is ordered by cardinality.
On the whole, not including the highest-order (N") hyperedge limits the representational capacity of an action-value estimator. This could introduce statistical bias due to estimating N actions' values
4

---

Published as a conference paper at ICLR 2021
Normaltzed (
5t Actions
10' Actions
20 Actions
(b)
400 Iteration
2.2
Raw TOKS
2.2
83
0.8
430
Actions
10a Actions
Actions
Universal
Sum
Raseline
Universal
1. Sum
Baseline
r= 2. Universal
r- 2, Sum
3,
Figure 3: Prediction error in our illustrative multi-armed bandits with three action dimensions and increasing action-space sizes. Each variant is run on 64 reward functions in any action-space size. (a) Normalised average RMS error curves. (b) Average RMS errors at the 400th training iteration.
using a model with M <NN unique outputs. In structured problem M < N could suffice, otherwise such bias is inevitable. Consequently, choosing any r <<N" could affect the estimation accuracy in prediction problem and cause sub-optimality in a control problem. Thus, preferably, we wish to use hypergraphs of rank r N We remark that this bias is additional to-and should be distinguished from the bias of function approximation which also affects methods such as DQN. We can view this in terms of the bias-variance tradeoff with acting as a knob: lower means more bias but less variance, and vice versa. Notably, when the N"-hyperedge is present even the simple summation mixer can be used without causing bias. However, when this is not the case, the choice of mixing function could significantly influence the extent of bias. In this work we generally fix the choice of mixing function to summation and instead try include high-order hyperedges.
ILLUSTRATIVE PREDICTION PROBLEMS
We out to illustrate the essence of problems in which we expect improvements by our approach. To do so, we minimise confounding effects in both our problem setting and learning method. Given that we are interested purely in studying the role of learning representations of action (and of state), we consider multi-armed bandit (one-state MDP) problem setting. We specify our bandits such that they have a combinatorial action space of three dimensions, where we vary the action-space sizes by choosing the number of sub-actions per action dimension from (5, 10, 20).
The reward functions are deterministic but differ for each random seed. Despite using different reward function in each independent trial, they are all generated to feature good degree of decom- posability with respect to the combinatorial structure of the action space. That is to say, by design, there is generally at least one possible decomposition that has non-zero values all possible hyper- edges. See Appendix A for details about how we generate such reward functions.
We train predictors for reward (equivalently, the optimal action values) using minimalist parame- terised models that resemble tabular ones as closely as possible (c.g. our baseline corresponds to a standard tabular model) and train them using supervised learning. For our approach, consider summation and universal mixers as well as increasingly more complete hypergraphs, specified using Eq. (6) by varying rank r from to 3. See Appendix A for additional experimental details.
Figure 3a shows normalised RMS prediction error curves (averaged over 64 reward functions) for two variants of our approach that leverage all possible hyperedges see that the ordering of the curves remains consistent with the increasing number of actions, where the baseline is outperformed by our approach regardless of the mixing function. Nevertheless, our model with universal mixer performs significantly better in terms of sample efficiency. Moreover, the performance gap becomes significantly wider as the action-space size increases, attesting to the utility of leveraging the combinatorial structure of actions for scaling to more complex action spaces. Figure 3b shows average RMS prediction errors at the 400th training iteration (as proxy for "final"
tabular baseline. We
"The notions of statistical bias and inductive bias are distinct from one another: an inductive bias does not necessarily imply statistical bias. In fact, good inductive hias enables a better generalisation capacity hut causes little statistical bias. In this paper use "bias" convenient shorthand for statistical bias.
5

---

Published as a conference paper at ICLR 2021
50%
HGQN vs. DQN
25%
0%
-2%
Chopper Command Fishing Dorty
Ice Hockey Centipodle
Bank Baok& Holst
Boxinu
Berzork
Montezuma's Ravenge
Gravita
Pirfall
Private Eye
Solars
James Bond D07
H.E.R. R.O.
River Raid
Seequest
Rohot Tank
Yars Revange
Tennis
Ventare
Alien
Kangaroo
Frostbite
Road Runnor
Batilezons
Krall
Douhlo Dunk Stargunnor
Zazzon
Figure 4: Difference in normalised score for 29 Atari 2600 games with 18 valid actions, HGQN versus DQN over 200 training iterations (positive % means HGQN outperforms DQN).
performance) for all variants in our study. As expected, including higher-order hyperedges and/or using a more generic mixing function improves final prediction accuracy in every case.
Going beyond these simple prediction tasks to control benchmarks RL we anticipate a general advantage for our approach, following the same pattern of yielding more significant improvements in larger action spaces. Indeed, this is if similar structures are ubiquitous in practical RL. tasks.
ATARI 2600 GAMES
We tested our approach in Atari 2600 games using the Arcade Learning Environment (ALE) (Bellemare et al., 2013). The action space of Atari 2600 is determined by a digital joystick with three degrees of freedom: three positions for each axis of the joystick, plus a button. This implies that these games can have a maximum of 18 discrete actions, with many not making full use of the joy-
Median
75%
50%
Human-Normelllee Soore
25%
stick capacity. To focus our compute resources on games with a more complex action space, we limited our tests 29 Atari 2600 games from the literature that feature 18 valid actions.
0%
Mean
For the purpose of our control experiments, we combine our ap-
proach with deep Q-networks (DQN) (Mnih et al., 2015). The resulting agent, which we dub hypergraph Q-networks (HGQN), deploys an architecture based on our action hypergraph networks, similar that shown in Fig. 2b, and using the summation mixer. Given that the action space has merely three dimensions, we in- stantiate our agent's model based on a hypergraph including the seven possible hyperedges. We realise this model by modifying the DQN's final hidden layer into a multi-head one, where each head implements block from our framework for respective hy- peredge. To achieve a fair comparison with DQN, we ensure that our agent's model has roughly the same number of parameters as DQN by making the sum of the hidden units across its seven heads match that of the final hidden layer in DQN. Specifically, we implemented HGQN by replacing the final hidden layer of 512 rectifier units DQN with seven network heads, each with a sin- gle hidden layer of 74 rectifier units. Our agent is trained in the same way DQN. Our tests are conducted on a stochastic version of Atari 2600 using sticky actions (Machado et al., 2018).
150%
190%
50%
HGQN
DQN
0%
0
50
100
150
200
Iteration
Figure 5: Human normanneerrmaisedd median and mean scores across 29 Atari 2600 games with 18 valid actions. Random seeds are shown as traces.
Figure 4 shows the relative human-normalised score of HGQN (three random seeds) versus DQN (five random seeds) for each game. Figure shows median and mean human-normalised scores across the 29 Atari games for HGQN and DQN. Our results indicate improvements over DQN on the majority of the games (Fig. 4) as well as in overall performance (Fig. 5). Notably, these im- provements are both in terms of sample complexity and final performance (Fig. 5). The consistency of improvements in these games has the promise of greater improvements in tasks with larger action spaces. See Appendix B for experimental details, including complete learning curves.

---

Published as a conference paper at ICLR 2021
Reacher
Hopper
HallCheetab
Walker2D
Ant
Avecage Scome
2000
1002
3300
-.2
1000
1:00
1002
2300-
11000
1300
2000
154
2M
200
IM
2M
3M
134
20
2M
IMC
3M
13t
20d
202
Environment Step
Envtronment Step
Environment Stop
Enstronment Step
Enviroement Step
HGQN (F= 1)
HGQN (+=
HGQN 33
DGN
Raizbow
DDPC
Figure 6: Learning curves for HGQN, DQN, and a simplified version of Rainbow in physical control benchmarks of PyBullet (nine random seeds). Shaded regions indicate standard deviation. Average performance of DDPG trained for million environment steps is provided for illustration purposes.
(a)
1-hypecedges
2-byperedges
3-hyperedges
(b)
Morphology
HairChettah
Greedy Action's Representation
S
obow
wiitt
30-
2right
C12. MM
Figure 7: (a) Average (bars) and minimum maximum (error bars) per-hyperedge representation of the greedy action over 90000 steps (nine trained rank-3 HGQN models, 10000 steps each). (b) The actuation morphology of each respective domain is provided for reference.
To further demonstrate the versatility of our approach, we combine with a simplified version of Rainbow (Hessel et al., 2018). We ran the resulting agent the three best and worst-performing games from Fig. 4. We report our results in Appendix C. Notably, our results show that where HGQN outperforms DQN most significantll, its combination with the simplified version of Rainbow also outperforms the corresponding Rainbow baseline.
PHYSICAL CONTROL BENCHMARKS
To test our approach in problems with larger action spaces, we consider suite of physical control benchmarks simulated using PyBullet (Coumans & Bai, 2019). These domains feature continuous action spaces of diverse dimensionality. allowing us to test on range of combinatorial action spaces. We discretise each action space to obtain five sub-actions per joint. See Appendix for experimental details, including network architecture changes for the non-pixel nature of states in these domains.
We ran HGQN with increasingly more complete hypergraphs, specified using Eq. (6) by varying rank r from 1 to 3. Figure 6 shows the learning curves for HGQN and DQN. In low-dimensional Reacher and Hopper we do not see any sigmificant difference. However, the higher-dimensions domains render DQN entirely ineffective. This demonstrates the utility of action representations learned by our approach. In Ant we only ran HGQN with 1-complete model as the other variants imposed greater computational demands (see Sec. for more information).
We provide the average final performance of DDPG (Lillicrap et al., 2016) to give a sense of the performances achievable by a continuous control method, particularly by one that is closely related to DQN. Interestingly. HGQN generally outperforms DDPG despite using the training routine of DQN, without involving policy gradients (Sutton et al., 1999). This may be due local optimisation issues DDPG which can lead to sub-optimal policies in multi modal value landscapes (Metz al., 2017: Tessler al., 2019). Furthermore, include the performance of DQN combined with
7

---

Published as a conference paper at ICLR 2021
prioritised replay, dueling networks, multi-step learning, and Double Q-learning (denoted Rainbow see Hessel et al. (2018) for an overview). The significant gap between the performances of this agent and vanilla HGQN supports the orthogonality of our approach with respect to these extensions.
In Walker2D we see a clear advantage for including the 2- 2-hyperedges, but additionally including the 3 3-hyperedges relatively degrades the performance. This suggests that a rank- hypergraph strikes the right balance between bias and variance, where including the 3-hyperedges causes higher variance and, potentially, overfitting. In HalfCheetah we see little difference across hypergraphs, despite having the same action space as Walker2D. This suggests that the 1-complete model is sufficient in this case for learning a good action-value estimator.
Figure 7 shows average per-hyperedge representation of the greedy action learned by our approach. Specifically, we evaluated nine trained rank-3 HGQN models using greedy policy for 10000 steps in each case. We collected the greedy action's corresponding representation at each step (i.e. one action-repress cetion-representttion value for each hyperedge) and averaged them per hyperedge across steps. The emror bars show the maxima and minima of these representations. In HalfCheetah the significant representations are on the I-hyperedges. In Walker2D, while I-hyperedges generally receive higher average representations, there is one 2-hyperedge that receives comparatively significant average representation. The same 2-hyperedge also receives the highest variation of values across steps. This 2-hyperedge, denoted {1, 4), corresponds to the left and right hips in the agent's morphology (Fig. 7b). A good bipedal walking behaviour, intuitively, relies on the hip joints acting in uni- son. Therefore, modelling their joint interaction explicitly enables way of obtaining coordinated representations. Moreover, the significant representations on the 3-hyperedges correspond to those including the two hip joints. This perhaps suggests that the 2-hyperedge representing the hip joints is critical in achieving good walking behaviour and any representations learned by the 3-hyperedges are only learned due to lack of identifiability in value decomposition (see Sec. 3).
7 RELATED WORK
Value decomposition has been studied in cooperative multi-agent RL under the paradigm of cen- tralised training but decentralised execution. In this context, the aim is to decompose joint action values into agent-wise values such that acting greedily with respect to the local values yields the same joint actions as those that maximise the joint action values. A sufficient but not necessary condition for decomposition that satisfies this property is the strict monotonicity of the mixing function (Rashid et al., 2018). An instance is VDN (Sunehag et al., 2017) which learns to decom- pose joint action values onto sum of agent-wise values. QMIX (Rashid et al., 2018) advances this by learning a strictly increasing nonlinear mixer, with further conditioning on the (global) state using hypernetworks (Ha et al., 2017). These are multi-agent counterparts of our I-complete models combined with the respective mixing functions. To increase the representational capacity of these methods, higher-order interactions need to be represented. In a multi-agent RL context this means that fully-localised maximisation of joint action values is no longer possible. By relaxing this requirement and allowing some communication between the agents during execution, coordina- tion graphs (Guestrin et al., 2002) provide framework for expressing higher-order interactions in a multi-agent setting. Recent works have combined coordination graphs with neural networks and studied them in multi-agent one-shot games (Castellini al., 2019) and multi-agent RL benchmarks (Böhmer et al., 2020). Our work repurposes coordination graphs from cooperative multi-agent RL as a method for action representation learning standard RL.
Sharma et al. (2017) proposed a model on par with a 1-complete one in our framework and evaluated it in multiple Atari 2600 games. In contrast to HGQN, their model shows little improvement beyond DQN. This performance difference is likely due to not including higher-order hyperedges, which in turn limits the representational capacity of their model.
Using Q-learning in continuous action problems by discretisation has proven as viable alternative to continuous control. Existing methods deal with the curse of dimensionality by factoring the action space and predicting action values sequentially (Metz et al., 2017) independently (Tavakoli et al., 2018) across the action vertices. Another approach is to learn a (factored) proposal distribution for performing sampling- based maximisation of action values (Van de Wiele et al., 2020). Our work introduces an alternative approach based on value decomposition and further enables a capacity for explicitly modelling higher-order interactions among the action vertices. We remark that our
8

---

Published as a conference paper at ICLR 2021
1-complete models can achieve linear time complexity when used with strictly monotonic mixer (e.g. summation) by enabling to find the action-vait value maximising actions in a decentralised manner.
Graph networks (Scarselli et al., 2009) have been combined with policy gradient methods for train- ing modular policies that generalise to new agent's 's morphologies (Wang et al., 2018; Pathak et al., 2019; Huang al., 2020). The global policy is expressed that correspond to each of the agent's s actuators, where every policy is only responsible for control- ling its corresponding actuator and receives information from only its local sensors. The information is propagated based on some assumed graph structure among the policies before acting. Our work differs from this literature in many ways. Notably, our approach does not impose any assumptions on the state structure and, thus, is applicable to any problem with a multi-dimensions action space. The closest to our approach in this literature is the concurrent work of Kurin al. (2021) in which they introduce transformer- basee approach to bypass having to assume specific graph structure.
collection of graph policy networks
Chandak et al. (2019) explored learning action representations in policy gradient methods by sep- arate supervised learning process. Other methods have been proposed for learning in large discrete action spaces that have an associated underlying continuous action representation by using a contin- uous control method (van Hasselt & Wiering, 2009; Dulac-Arold et al., 2015). Nevertheless, these methods do not leverage the combinatorial structure of multi-dimensionall action spaces.
DISCUSSION AND FUTURE WORK
We demonstrated the potential benefit of using a more generic mixing function in our bandit prob- lems (Sec. 4). However, in an informal study subset of our RL benchmarks, did not see any improvements beyond our non parametric summation mixer. Further exploration of more generic (even state-conditioned) mixing functions is an interesting direction for future work. In this case, comparisons with an action-in baseline architecture would be appropriate to investigate how much of the advantages of using a hypergraph model may come from sharing the parameters of mixing function across actions as opposed to modelling lower-order hyperedges.
The requirement to maximise over the set of possible actions limits the applicability of Q-learning in environments with high-dimensional action spaces. In the case of approximate Q-learning, this limitation is partly due to the cost of computing the possible actions' values before an exact maximi- sation can be performed. Our approach can bypass these issues in certain cases (e.g. when using I-complete hypergraph with a strictly monotonic mixer; see See. 7 for more information). To more generally address such issues, we can maximise set of possible actions (Van de Wiele et al., 2020). An approximate maximisation as such will enable including higher-order hyperedges in environments with high-dimensional action spaces.
sampled set of actions instead of the entire
We demonstrated the practical feasibility of combining our approach with a simplified version of Rainbow. An extensive empirical study of the impact of these combinations as well combining with further extensions, e.g. for distributional (Bellemare et al., 2017) and logarithmic RL (van Sci- jen et al., 2019), is left as future work. Moreover, a better understanding of how value decomposition affects the learning dynamics of approximate Q-learning could help establish which extensions are theoretically compatible with our approach.
Much could be done to improve learning in continuous action problems by discretisation. For in- stance. the performance of our approach could be improved by using exploratory policies that exploit the ordinality of the underlying continuous action structure instead of using é-greedy. Moreover, process (Uhlenbeck & Ornstein, 1930) to generate temporally-
DDPG uses an Trnstein-Uhlenbee correlated action noise to achieve exploration efficiency in physical control problems with inertia. Using a similar inductive bias could further improve the performance of our approach in such prob- lems. A more generally applicable approach which does not rely on the ordinality of the action space is to use sepporrlll--xtendde E-greedy exploration (Dabney et al., 2021). The latter could prove es- pecially useful in discretised physical control problems as such. Another interesting opportunity is using a curriculum of progressively growing action spaces where a coarse discretisation can help exploration and a fine discretisation allows for more optimal policy (Farquhar al., 2020).
Code availability bctiion-bypergraph--eet.
The source code can be accessed at: https: /ttp://gttttt com/ at avaakol
9

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
We thank Ileana Becerra for insightful discussions, Nemanja Rakicevic and Fabio Pardo for com- ments on the manuscript, Fabio Pardo for providing the DDPG results which he used for benchmarks Tonic (Pardo, 2020), and Roozbeh Tavakoli for help with visualisation. A.T. acknowledges finan- cial support from the UK Engineering and Physical Sciences Research Council (EPSRC DTP). We also thank the scientific Python community for developing the core set of tools that enabled this work, including TensorFlow (Abadi al., 2016) and NumPy (Harris et al., 2020).
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaogiang Zheng. TensorFlow: A system for large- scale machine learning. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, pp. 265-283, 2016.
Joshua Achiam. Spinning up in deep reinforcement learning. https://spinningut openai com, 2018.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre. Francis Song. Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv: 0/261, 2018.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In Proceedings of the International Conference Machine Learning, pp. 449-458, 2017.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1788)187,888888, 2013.
Claude Berge. Hypergraphs: Combinatorics of Finite Sets. North-Holland, 1989.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Proceedings of the International Conference on Machine Learning, pp. 261 1-2622, 2020.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv:1606.01544 2016.
Jacopo Castellini, Frans Oliehoek, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, pp. 1862-1864, 2019.
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Marc G. Bellemare. Dopamine: A research framework for deep reinforcement learning. arXiv: DrrXiv:1812.000 1812.061 10, 2018
Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip S. Thomas. Learning action representations for reinforcement learning. In Proceedings of the International Conference on Machine Learning, pp. 941-950, 2019.
Erwin Coumans and Yunfei Bai. PyBullet: A Python module for physics simulation for games, robotics and machine learning. https::///// httpaa://pypllll/ let. org, 2019.
10

---

Published as a conference paper at ICLR 2021
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In Proceedings of the International Conference on Machine Learning. pp. 1096-1105, 2018.
Will Dabney, Georg Ostrovski, and André Barreto. Temporally-extended e-greedy exploration. In Proceedings of the International Conference on Learning Representations, 2021.
Gabriel Dulac-Armold, Richard Evans, Hado van Hasselt, Peter Sunchag, Timothy P. Lillierap, Jonathan Hunt, Timothy Mann, Théophane Weber, Thomas Degris, and Ben Coppin. Deep rein- forcement learning in large discrete action spaces. arXiv:1512.07677 2015.
Gregory Farquhar, Laura Gustafson, Zeming Lin, Shimon Whiteson, Nicolas Usunier, and Gabriel Synnaeve. Growing action spaces. In Proceedings of the International Conference on Machine Learning. pp. 4335-4346, 2020.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Volodymyr Mnih, Rémi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. Proceedings of the International Conference on Learn- ing Representations, 2018.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 249-256, 2010.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In Proceedings of the International Conference on Machine Learning, pp. 227-234, 2002.
David Ha, Andrew Dai, and Quoc V. Le. Hypernetworks. In Proceedings of the International Conference on Learning Representations, 2017.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array program- ming with NumPy. Nature, (55(7825)3377-366 2020.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining im- provements in deep reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 3215-32112 3222,, 2018.
Wenlong Huang, Igor Mordatch, and Deepak Pathak. One policy to control them all: Shared modular policies for agent-agnostic control. In Proceedings of the International Conference on Machine Learning. pp. 8398 8407, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Representations, 2015.
Vitaly Kurin, Maximilian Igl, Tim Rocktäschel, Wendelin Bochmer, and Shimon Whiteson. My body is a cage: The role of morphology in graph-based incompatible control. In Proceedings of the International Conference on Learning Representations, 2021.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Pro- ceedings of the International Conference on Learning Representations, 2016.
Marlos C. Machado, Mare G. Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the Arcade Learning Environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
Luke Metz, Julian Ibarz, Navdeep Jaitly, and James Davidson. Discrete sequential prediction of continuous actions for deep reinforcement learning- arXiv: 1705005030 2017.
11

---

Published as a conference paper at ICLR 2021
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonogiou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. 2015.
Nature, 518(7540))522--553
Fabio Pardo. Tonic: deep reinforcement learning library for fast prototyping and benchmarking. wrXiv:2011.07537. 2020.
Fabio Pardo, Arash Tavakoli, Vitaly Levdik, and Petar Kormushev. Time limits in reinforcement learning. In Proceedings of the International Conference on Machine Learning, pp. 2018.
Deepak Pathak, Chris Lu, Trevor Darrell, Phillip Isola, and Alexei A. Efros. Learning to control self-assembling morphologies: A study of generalization via modularity. In Advances in Neural Information Processing Systems, pp. 2295-2305, 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob N. Foer- ster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In Proceedings of the International Conference on Machine Learning, pp. 4295--255522 44055-434422 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In Proceedings of the International Conference Learning Representations, 2016.
Sahil Sharma, Aravind Suresh, Rahul Ramesh, and Balaraman Ravindran. Learning to factor poli- cies and oetion-value functions: Factored action space representations for deep reinforcement learning. wwXiv:170..07269 2017.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning. 17X.:1706..02990 2017.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2nd edition, 2018
Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Infor- mation Processing Systems, pp. 1057-1063, 1999.
Arash Tavakoli, Fabio Pardo, and Petar Kormushev. Action branching architectures for deep rein- forcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4131- 4138, 2018
Chen Tessler, Guy Tennenholtz, and Shie Mannor. Distributional policy optimization: An alternative approach for continuous control. In Advances in Neural Information Processing Systems, pp- 1352-1362, 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. MuJoCo: A physics engine for model-based control. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
George E. Uhlenbeck and Leonard S. Ornstein. On the theory of the Brownian motion. Physical Review, 36(5):823-84) 1930.
Tom Van de Wiele, David Warde-Farley, Andriy Mnih, and Volodymyr Mnih. Q-learning in enor- mous action spaces via amortized approximate maximization. arXiv:2001.08/ 2020.
Hado van Hasselt and Marco A. Wiering. Using continuous action spaces to solve discrete problems. In Proceedings of the International Joint Joint Conference on Neural Networks, pp. 1149-1 156, 2009.
12

---

Published as a conference paper at ICLR 2021
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with Double Q- learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 2094-2100, 2016.
Harm van Seijen, Mchdi Fatemi, and Arash Tavakoli. Using logarithmic mapping to enable lower discount factors in reinforcement learning. In Advances in Neural Information Processing Sys- tems, pp. 14134-14144, 2019.
Jianhao Wang. Zhizhou Ren, Beining Han, and Chongjie Zhang. Towards understanding linear value decomposition in cooperative multi-agent Q-learning. arXiv:2006. 00.22006.00577, 2020.
Tingwu Wang. Renjie Liao, Jimmy Ba, and Sanja Fidler. NerveNet: Learning structured policy with graph neural networks. In Proceedings of the International Conference Learning Representa- tions, 2018.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanctot, and Nando de Freitas. Dueling network architectures for deep reinforcement learning. In Proceedings of the Interna- tional Conference on Machine Learning, pp. 1995-2003, 2016.
Christopher J. C. H. Watkins. Learning from delayed rewards. PhD thesis, University of Cambridge, 1989.
Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3):279 2922, 1992.
13

---

Published as a conference paper at ICLR 2021
A ILLUSTRATIVE PREDICTION PROBLEMS: EXPERIMENTAL DETAILS
Environment We created each reward function by randomly initialising a hypergraph model with all possible hyperedges. Explicitly, in each independent trial, we sampled as many values as the total number of outputs across all possible hyperedges: sampling uniformly from [-10, 10j for the I-hyperedges, [-5. 5] for the 2-hyperedges, and [-2.5, 2.5] for the 3-hyperedges. This results in structured reward functions that can be decomposed to good degree on the lower-order hyperedges but still need the highest-order hyperedge for a precise decomposition. Next, we generated a random mixing function by uniformly sampling the parameters of a single-hidden-Ian
neural network from [- The number of hidden units and the activation functions were sampled uniformly from (1,2..... ..2.....,, 55 and (ReLU, tanh, sigmoid, linear), respectively. Lastly, a deterministic reward for each action was generated by mixing the action's ' corresponding subset of values.
Architecture We used minimalist parameterised models that resemble tabular ones as closely as possible. As such, our baseline corresponds to a standard tabular model in which each action value estimated by single unique parameter. In contrast, our approach does not require unique parameter for each action as it relies on mixing multiple action-represennation values to produce an action-value estimate. Therefore, for our approach we instantiated as many unique parameters as the total number of outputs from each model's 's hyperedges. For any model using a universal mixer, we additionally used a single hidden layer of 10 rectifier units for mixing the action-representation values, initialised using the Xavier uniform method (Glorot & Bengio, 2010).
Training Each predictor was trained by backpropagation using supervised learning. repeatelyy sampled minibatches of 32 rewards (with replacement) to update a predictor's parameters, where each training iteration comprised 100 such updates. We used the Adam optimiser (Kingma & Ba, 2015) to minimise the mean-squared prediction error.
The number of hyperedges in our hypergraphs of interest (see Sec. 3.2) can be expressed in terms of binomial coefficients
TSM' Σ c=1
HI
where hypergraph H is specified by its rank r according to Eq. (6). As we discussed in Sec. 3, each action's value estimator is formed by mixing as many aetion-represennatiion values as there hyperedges in the model (Eq. (5)). In our simple models for the bandit problems, each such value corresponds to single parameter. As such, each learning update per action involves updating as many parameters as the number of hyperedges. Therefore, to ensure fair comparisons, we adapted the learning rates across different models in our study based on the number of parameters involved in updating each action's 's value estimate. Concretely, we set single effective learning rate across all models in our study. We then obtained each model's individual learning rate a via
effective learning rate
We used an effective learning rate of 0.0007 in our study. While this achieves the same actual effective learning rate for both the baseline and our models using the summation mixer, the same does not hold exactly for our models using universal mixer. Nonetheless, this still serves as useful heuristic to obtain similar effective learning rates across all models. Importantly, the baseline receives the largest individual learning rate across all other models esspccallyy one that improved its performance with respect to any other learning rates used by the variants of our approach.
The logic behind the adjustments of learning rate here simply does not hold in the case of high- capacity, nonlinear models such as those used in our RL benchmarks. Therefore, in our RL bench- marks we used the same learning rate across all variants.
The learning curves were generated by calculating the RMS prediction error across all possible actions after each training iteration per independent trial.
Evaluation
14

---

Published as a conference paper at ICLR 2021
B ATARI 2600 GAMES: EXPERIMENTAL DETAILS
We based our implementation of HGQN on the Dopamine framework (Castro et al., 2018). Dopamine provides a reliable open-source code for DQN as well as enables standardised bench- marking in the ALE under the best known evaluation practices (see, e.g., Bellemare et al. (2013); Machado al. (2018)). As such, we conducted our Atari 2600 experiments without any modifi- cations to the agent or the environment parameters with respect to those outlined in Castro et al. (2018), except for the network architecture change for HGQN (see Sec. 5). Our DQN results are based on the published Dopamine baselines. We limited our tests in Atari 2600 to all the games from Wang et al. (2016) that feature 18 valid actions excluding Defender for which DQN results were not provided as part of the Dopamine baselines.
The human-normalised scores reported in this paper were given by the formula (similar to van Hasselt et al. (2016); Dabney et al. (2018)) 8))
ScOrengent SCOTemndom
Scorehuman
Scorerandon
where Scoreagent: ScOrepuman- and ScOrerandmm are the per-game scores (undiscounted returns) for the given agent, a reference human player, and random agent baseline. We used Table from Wang et al. (2016) to retrieve the human player and random agent scores.
The relative humanenormalised score of HGQN versus DQN in each game (Fig. 4) was given by the formula (similar to Wang et al. (2016))
scoreHGoN scoreDON
(10)
max (scorennn,, scotehuman) scOre
where scoreNGoN and scoreDQN were computed by averaging over their respective learning curves.
Figure shows complete learning curves across the 29 Atari 2600 games with 18 valid actions.
C ATARI 2600 GAMES: ADDITIONAL RESULTS
We combined our approach with a simplified version of Rainbow (Hessel et al., 2018) that includes prioritised replay (Schaul et al., 2016). dueling networks (Wang et al., 2016), multi-step learning (Hessel et al., 2018), and Double Q-learning (van Hasselt et al., 2016). We did not include C51 (Bellemare et al., 2017) as is not trivial how it can effectively be combined with our approach. We also did not combine with noisy networks (Fortunato et al., 2018) which are not implemented in Dopamine. We denote the simplified Rainbow by Rainbow and the version combined with our approach by HG-Rainbow!.
We ran these agents on the three best and worst-performing games from Fig. 4. We conjecture that the games in which HGQN outperforms DQN most significantly should feature kind of structure that exploitable by our approach. Therefore, given that our approach is notionally orthogonal to the extensions in Rainbow we can also expect to see improvements by HG-Rainbow over Rainbow Figure shows the relative human-normalised score of HG-Rainbow versus Rainbow (three random seeds in each case) along with those of HGQN versus DQN from Fig. 4 for these six games, sorted according to Fig. (blue bars). We see that, generally, the signs of relative scores for Sainbowi-based runs aligned with those for DON-based runs. Remarkably, in Stargunner the relative improvements are on par in both cases.
This experiment mainly serves to demonstrate the practical feasibility of combining approach with several DQN extensions. However, as each extension in Rainbow impacts the learning process in certain ways, believe that extensive work is required to establish whether such extensions theoretically sound when combined with the learning dynamics of value decomposition. In fact, a recent study on the properties of linear value-decomposition methods in multi-agent RL could hint at a potential theoretical incompatibility with certain replay schemes (Wang et al., 2020). Therefore, we defer such a study to future work.
Figure 10 shows complete learning curves across the six select Atari 2600 games.
15

---

Published as a conference paper at ICLR 2021
Alien
Bank Heist
Balliezone
Berzerk
600
Scote
Scure
500
Score
20000
Score
4.0-
2000
200
200
200
150
200
50
100 Beration
150
200
Ieeration
Iteration
Derction
Boxing
Centipede
Chopper Command
Double Dunk
4000
3000
Score
Scure
Score
2000
2000
10
1000
150
200
200
200
50
100 Iteratio
150
200
Iteration
Iteration
Iteration
Fishing Derby
Frostbite
Grsvitar
E.E.E
2000
400
20000
Scare
Scuru
1000
Score
200
Score
10000
200
200
200
100 Iteration
150
200
Iteration
Iteration
Iteration
Ice Hockey
James Bond
Kangaroo
Krull
Scare
Scun
500
Score
10000
Score
-10
-15
2500
200
200
200
50
100
150
200
Iteration
Iteration
Iteration
Iterattion
Montezuma's Revenge
Pitfall!
Private Eye
River Raid
15000
Scure
Score
10000
-100
5000
200
200
200
50
150
200
Iteration
Iteratio
Eteration
Iteration
Road Runner
Robot Tank
Seaquest
Solarts
40000
Scare
Score
Score
10000
2000
20000
1000
200
200
50
150
200
Iteration
Iteration
Lteration
Iteration
Stargunner
Tennis
Venture
Yars' Revenge
50000
1000
50000
Scare
Score
20000
25000
10000
200
50
200
50
150
200
Iteration
Iteration
Eteration
Iteration
Zaxxon
Scote
10000
HGQN DQN
Iteration
Figure& 8: Learning curves in 29 Atari 2600 games with 18 valid actions for HGQN and DQN. Shaded regions indicate standard deviation.
16

---

Published as a conference paper at ICLR 2021
HGQN vs. DQN
HG-Rainbow' Rainbow
50%
25%
0%
-25%
Chopper Command
Fishing Derby
Ice Hockey
Double Dunk
Stargunner
Zaxxon
Figure 9: Difference in human comman-normalised score for six Atari 2600 games with 18 valid actions, fea- turing the three best and portt-performig games from Fig. (positive % means HGQN outperforms DQN or HG- IG-RRinbow outperforms Rainbow over 200 training iterations).
Double Dunk
Stargunner
Zaxxon
20
Scure
50000
10000
25000
3000
-20
50
1.00
150
200
100
150
200
50
100
150
200
Iteration
Iterttoon
Iterition
Chapper Command
Fishing Darby
Hockey
3000
Scare
1000
-50
100
200
Heratica
Beeration
Herotton
HGQN
HG-Raine Rainbow
DQN
Rainbow
Figure 10: Learning curves for HGQN, HG-Rainbowi, DQN, and Rainbowl in six Atari 2600 games with 18 valid actions, featuring the three best and perst-pe games from Fig. 4.
17

---

Published as a conference paper at ICLR 2021
D PHYSICAL CONTROL BENCHMARKS, EXPERIMENTAL DETAILS
Environment We tested our approach on a suite of physical control benchmarks simulated using PyBullet (Coumans & Bai, 2019). PyBullet benchmarks provide free and open-source alternative to the standard MuJoCo (Todorov et al., 2012) benchmarks of OpenAl Gym (Brockman et al., 2016). The five environments in our experiment feature ByBullet benchmarks excluding those with one- dimensional action spaces (i.e. InvertedPendulum and InvereedDoubeePendulum or without stable implementation (i.e. Humanoid). Table shows dimensionality and size the action spaces in these environments, where the latter is obtained by discretising each action space with the granularity of five sub-actions per joint. By default, these environments use predefined time limits: 1000 steps for all locomotion tasks and 150 steps for the single manipulation task (i.e. Reacher).
Architecture We simplified the network architectures by replacing the convolutional networks with hidden layers of 600 and 400 rectifier units reflect the non-pixel nature of states. More- over, we adapted the final hidden layer from 512 to 400 rectifier units, applying the same heuristic of dividing them equally across the number of network heads for HGQN as in our Atari 2600 exper- iments. We remark that this heuristic does not achieve similar numbers of parameters with respect to our baselines in environments with large action spaces. Nevertheless, this inevitable given that such standard models require set of unique parameters for representing each action's 's value.
Training We left the rewards unchanged, unlike in our Atari 2600 experiments where the rewards were clipped to deal with the great variations of the scale of rewards from game to game.
We generally used the same agent implementations as our Atari 2600 experiments, with the excep- tion of the following changes. Bootstrapping from non-terminal timeout transitions significantly improve performance in environments which have short auxiliary time limits (Pardo et al., 2018). As such, in physical control environments which have relatively short time limits, we applied this technique to all agents in our experiment (including DDPG). This is especially admissible in our case given that all agents in our study are off-policy. We outline any other changes to the learning hyperparameters with respect to those used in our Atari 2600 experiments in Table 2 (see Extended Data Table 1 of Mnih et al. (2015) for descriptions of hyperparameters)
Evaluation The learning curves (Fig. 6) were generated by evaluating the agents every 10000 steps during the training, each time for a minimum of 5000 steps (until the last evaluation episode ends by reaching terminal state or the time limit).
Continuous control baseline The reported DDPG results are based on Spinning Up in Deep RL (Achiam, 2018) which provides reliable open-source code for DDPG. The final performances (at million environment steps) were obtained by averaging test performances (with no action noise) over the last 100000 steps of training (20 random seeds). The network architecture and hyperparameters match those reported in Lillicrap et al. (2016).
E PHYSICAL CONTROL BENCHMARKS, SUPPLEMENTAL VIDEOS
In Table 3 we provide links to supplemental videos showing representative behaviours learned by HGQN in subset PyBullet benchmarks together with the representation of the chosen action at each step. The videos are created using an e-greedy policy with e 0.001 on models that were trained for million environment steps.
18

---

Published as a conference paper at ICLR 2021
Table Action spaces our physical control benchmarks.
DOMAIN
DIMENSIONALITY
SIZE
Reacher
25
Hopper
125
HalfCheetah
15625
Walker2D
15625
Ant
390625
Table 2: Hyperparameters used for HGQN and DQN in our physical control benchmarks.
HYPERPARAMETER
VALUE
minibatch size
64
replay memory size
100000
agent history length
target network update frequency
2000
action repeat
update frequency
optimiser
Adam (Kingma & Ba, 2015)
learning rate
0.00001
? (a constant used for numerical stability in Adam)
0.0003125
81 (1* moment decay rate used by Adam)
0.9
83 (2nd moment decay rate used by Adam)
0.999
loss function
mean-squared error
initial exploration
final exploration
0.05
final exploration step
50000
replay start size
10000
Table 3: Supplemental videos of HGQN subset of our physical control benchmarks.
DOMAIN
VIDEO URL
Hopper
http:://poatt.bb///lgiivvvgg
HalfCheetah https///goutt.bee/fffSooggg
Walker2D
http:///yoatuubbe/BSD0000007
19


Reviews:
[{"review_id": "bvrYc51tyHK", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper incorporates a concept called hypergraph network into reinforcement learning. The idea of hypergraph is to extend edge to hyperedge where a set of vertices can be considered at the same time. This seems natural for scenarios like continuous action control with multi-dimension action space. From experimental results this proposed action hypergraph networks outperform several existing baselines.\n\nPros:\nThis paper has relatively high novelty. The idea of hypergraph may be useful for broad range of applications.\n\nCons:\n1. HGQN vs. DQN is this a good comparison? DQN is a good baseline but no longer SOTA for Atari games. I wonder how HGQN vs. rainbow or DDPG for Figure 4 looks like.\n2. It will be better if authors provide error bands for Figure 5. It's unclear how significant the proposed method is better.\n3. When number of actions gets large, this hypergraph idea will have exponential complexity. How to find a best way to partition the graph (or generalize to 3+ hyperedges)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "TcQ1oqldPi2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of representation learning of actions, i.e., learning a decomposition of action-value function in multidimensional action spaces using hypergraphs. The key idea is to represent the actions as a hypergraph and learn a representation for each hyperedge in an arbitrary hypergraph. Consequently, the architecture conduits of a neural network for each hyperedge that are then combined using a mixing function. The choice of mixing function appears to be dependent on the problem -- for instance, it could be an universal mixer such as a neural  network or it could be a simple summation. The key impact of this architecture could be in the bandit problem setting with very large action spaces. Empirical results on a few atari games (29) and simulated physical control benchmarks clearly demonstrate the superiority of the approach.\n\nThe paper is written well. The problem is well motivated and sufficient details are provided. Experimental results appear convincing. The use of hypergraphs themselves are not necessarily novel but the implications in large multi-agent systems makes the paper compelling. Personally, i feel that the paper can have a good impact. \n\nI do have a few comments:\n\nFirst, I think the term “relational inductive bias” is quite a stretch for here. It really is much more than a simple inductive bias. You are constructing the full architecture. Granted that the structure serves as a bias but this is much more than an inductive bias. It really can be interpreted as a search bias as well. \nMoreover, relational is also misused a lot (not just in this paper). IF you claim relational, then you should demonstrate generalization. Without that one cannot claim relational. I dont think your method is generalizable to varying number of objects in the domain. I suggest calling these as structured problems more than relational domains. The atari games for instance are not even close to being relational. \nI am not sure I understand why a 3-hyperedge will have higher variance. Could you kindly explain this? Does this mean that you are overfitting in terms of creating newer edges that dont exist? Is it too fine-grained of a representation? Some speculation could certainly improve the paper. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SRAjBw5WSq1", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work focuses on learning action representations for problems involving high-dimensional action spaces. The aim is to build a flexible and general methodology for learning representations of multidimensional actions that can be combined with existing architectures (which mostly focus on learning state representations). The ideas initially suggested in Sharma et al (2017) have been generalized and refined in this work leading to impressive empirical results.\n\nStrengths:\n* The hypergraph formulation of the action space is well motivated and well grounded in literature.\n* The aims set out in the introduction of the paper were duly justified -- the proposed framework is indeed very flexible and general as can be seen from the application to multiple problem types.\n* The choice for Mixing function and Hypergraph specification are practical which makes them broadly applicable.\n* The empirical results clearly illustrate the benefits achieved due to action representation.\n* The paper is clearly written and well-organized.\n\nWeaknesses:\n* The experiments with three dimensional actions (Sec 4, 5) demonstrate clear benefits of the method, however, the action dimensionality is small enough to include all possible hyperedges. Sec 6 conducts experiments using five-dimensional actions where we notice tradeoffs between using hypergraphs of different ranks. From Fig 6 & 7, it is unclear what are the benefits of using hyperedges of higher order.\n* It would be informative to conduct experiments on problems with higher dimensional action spaces such as Hunters & Rabbits. \n* The experiments lack comparison against other methods that decompose actions such as Metz et al (2017).\n\nUpdate after author response:\nI thank the authors for their detailed rebuttals as well as for engaging with the reviewers. It'd be worth adding a small section on how to scale this method for higher dimensional action spaces (bullet 2 in author response). Comparison with Metz et al (2017) is valid and appreciated. Based on this, I am happy to increase my rating from 7 to 8.", "extra_scores": {}, "extra_text": {}}, {"review_id": "FnGM2heLzB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work considers the idea of adding a representation for action space. This is on top of the usual representation of state-space. Their approach is based on hypergraph representation and shows its merits in the experimental results. But in general, I find the technical contributions (borderline) incremental.", "extra_scores": {}, "extra_text": {}}, {"review_id": "40K5YkVTgc", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "EDIT: The authors clarified the presentation, gave a nuanced response to my concerns about the relative scalability, and promised to discuss the relationship to the actions-in architecture in the final version (it's not as central as I first thought given the limited role played by universal mixers). Solid work in its current state.\n\nThe authors propose a method that incorporates multi-way relationships between action dimensions in the estimate of action-value functions. This provides a strong inductive bias for reinforcement learning problems with a small number of action dimensions, each  taking several values. This is an interesting approach, but there are presentation and experimental issues preventing me from endorsing its publication.\n\nCurrently the presentation obscures some of the limitations of the method. Not until the experiments is it revealed that the method (in its current state) is only applicable to tasks with finite action spaces. Most tasks typically considered as having multiple action dimensions are continuous control tasks, so this is unexpected given the motivation. Not knowing this up front also hurts the clarity of the paper e.g. Figure 1b mentions outputting all possible actions, which is only coherent in the context of this finite cardinality restriction. Now, I'm not saying that not handling continuous action spaces is necessary (your results on discretized continuous action tasks are impressive), just that you should be more up front with this fact.\n\nA second hidden limitation has to do with your method's scaling. If I understand your method correctly, to compute the maximum action-value you have execute the hyper-graph and mixer repeatedly, once for each possible action. This is in stark contrast to the standard actions-out architecture popularized by DQN -- a single forward pass compute all action-values. You (correctly) point out that both your method and DQN grow exponentially in the number of action dimensions, but in practice the latter will scale much better as it just amounts to a larger dimension matmul. Again, this limitation need not be overcome, but it should be mentioned.\n\nOn the experimental front, there is a serious baseline missing. Prior to DQN, many RL (with function approximation) papers treated the action as an input. Indeed, the only reason this is less common these days is due to the run-time issue discussed above. Treating the action as an input corresponds to only using the highest order hyper-graph (since the action contains all action dimensions), making that special case not a contribution of this paper. Thus, comparing against this case would be necessary to show that this method improves upon prior work. Additionally comparing against more recent approaches (e.g. auto-regressive processing of action dimensions) would further strengthen the paper, but this is of less importance in my opinion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the reviews and rebuttal and looking over the paper, I feel that the results are indeed strong, and the paper could have an impact in terms of exploiting the relationship among action dimensions. Maybe the only detail that I would add is that going through the example given in Fig 1 completely could be useful as it might not be perfectly obvious how (e.g. considering a simple mixing function like summation) one retrieves the q values for someone not familiar with this particular topic. 
Decision: Accept (Poster)