Deep Multi-Agent Reinforcement Learning with Discrete-Continuous Hybrid Action Spaces

1 Introduction

Reinforcement learning (RL) has recently shown a great success on a variety of cooperative multi-agent problems, such as multiplayer games [Peng et al., 2017], autonomous cars [Cao et al., 2013] and network packet delivery [Ye et al., 2015].

In many such settings, it is necessary for agents to learn decentralized policies due to the partial observability and limited communication. Fortunately, we can learn such policies using the paradigm of centralized training and decentralized execution. Forester et al. [2016] developed a decentralized multi-agent policy gradient algorithm; Lowe et al. [2017] extended DDPG [Lillicrap et al., 2016] to multi-agent setting with a centralized Q-function; Rashid et al. [2018] employs a Qmix network that estimates joint action-values as a complex non-linear combination of per-agent action values that condition on local observations only.

∗Corresponding author

These popular multi-agent reinforcement learning methods all require the action space to be either discrete or continuous. However, very often the action space in real world is discretecontinuous hybrid, such as Robot soccer [Hausknecht, 2016; Masson et al., 2016] and Real Time Strategic games [Xiong et al., 2018]. In such settings, each agent usually needs to choose a discrete action and continuous parameters associated with it at each time step. An obvious approach to handling this is to simply approximate hybrid action spaces by a discrete set or relax it into a continuous set [Hausknecht and Stone, 2016]. However, such approaches suffer from a number of limitations. Discrete approximation needs to balance the trade-off between learned policy quality and discrete action space explosion. If the continuous action space is discretized coarsely, the learned policy quality would decrease significantly; otherwise, the discrete action space would increase exponentially. If using continuous relaxation, it would be difficult to map the learned optimal actions in the relaxed continuous space to the feasible and optimal discrete actions.

An alternative and better solution is to learn directly over hybrid action spaces. Following this direction, Xiong et al. [2018] proposed Parameterized Deep Q-Network (PDQN) for single-agent learning in hybrid action spaces without approximation or relaxation by seamlessly integrating DQN [Mnih et al., 2013] and DDPG [Lillicrap et al., 2016]. However P-DQN cannot be directly applied to multi-agent settings due to the non-stationary property in multi-agent environments. In multi-agent settings, explicit coordination mechanism among agents' hybrid action spaces needs to be introduced.

In this work, we propose two approaches to address cooperative multi-agent problems in discrete-continuous hybrid action spaces based on centralized training and decentralized execution framework. The first approach, Deep Multi-Agent Parameterized Q-networks (Deep MAPQN), extends the architecture of P-DQN to multi-agent settings by leveraging the idea of Qmix [2018]. Our algorithm utilizes a joint actionvalue function to update policies of hybrid actions for all agents. However, Deep MAPQN requires to compute continuous parameters for all the discrete actions of all agents and thus may suffer from high computational complexity when the discrete part of hybrid action space has large dimensions. To alleviate this problem, we propose the second approach, Deep Multi-Agent Hierarchical Hybrid Q-networks (Deep MAHHQN). In contrast to Deep MAPQN, Deep MAHHQN only needs to calculate continuous parameters of the optimal discrete action for each agent. In addition, it further alleviates the non-stationary issue of multi-agent environments by realizing centralized training fashion at both action levels and augmenting each centralized training framework with information about policies of other action levels. Empirical results on standard benchmark game Half Field Offense (HFO) and a large-scale video game Ghost Story show the superior performance of our approaches compared to independent P-DQN.

2 Background

2.1 Cooperative Stochastic Game

In this work, we consider a Cooperative Stochastic Game [Wei et al., 2018a] in partially observable settings modeled as a tuple {S,U, r, P, γ,H,N} . This game for N agents is defined by a set S of states describing the possible configurations of all agents, a set of observations O1, ...,ON for each agent and a joint action space of N agents defined as U = A1 ×· · ·×AN. At each time step, each agent i chooses an action ai ∈ Ai using policy πi and constitutes a joint action ⃗a ∈ U, which produces the next state s′ following the state transition function P (s′ |s, ⃗a): S × U × S → [0, 1]. All agents share the same reward function r(s,⃗a): S × U → R. γ is the discount factor and H is the time horizon.

2.2 DeepMulti-agent Reinforcement Learning

Multi-agent learning has been investigated comprehensively in both discrete action domains and continuous action domains under framework of centralized training and decentralized execution.

MADDPG [Lowe et al., 2017] mainly focuses on multiagent problems with continuous action spaces. The core idea is to learn a centralized critic QµI (x, a1, · · · , aN) for each agent which conditions on global information. QµI (x, a1, · · · , aN) takes as input the actions of all agents, a1, · · · , aN, in addition to global state information x (i.e., x = (o1, · · · , oN)) and outputs the centralized action-value for agent i.

Qmix [Rashid et al., 2018] employs a mixing network that estimates joint action-values Qtot as a complex nonlinear combination of per-agent action value that conditions only on local observations. The weights of the mixing network are produced by separate hypernetworks which take the global state information as input. Importantly, Qmix ensures a global argmax performed on Qtot yields the same result as a set of individual argmax operations performed on each agent's action-value Qi by a monotonicity constraint:

Unfortunately, such multi-agent algorithms cannot be applied to hybrid action spaces. Qmix belongs to the class of value-based reinforcement learning approaches that are commonly considered suitable for discrete action space problems. But they cannot be applied to continuous settings [Sutton and Barto, 1988; Silver et al., 2014]. MADDPG belongs to the class of policy-based approaches which directly learn deterministic policies over either discrete action spaces or continuous action spaces. But such approaches cannot learn a policy over hybrid action spaces [Mnih et al., 2016; Schulman et al., 2017].

2.3 Parameterized Deep Q-Networks

To handle reinforcement learning problems with hybrid action space, Xiong et al. [2018] propose a new framework called Parameterized Deep Q-Networks (P-DQN). The core idea is to update the discrete-action and continuous-action policies separately combining the structure of DQN [Mnih et al., 2013] and DDPG [Lillicrap et al., 2016]. P-DQN first chooses low-level parameters associated with each high level discrete action, then figures out which hybrid action pair maximizes the action-value function.

More concretely, we can define the discrete-continuous hybrid action space A as:

where [K] = {1, · · · ,K} is the discrete action set, Xk is a continuous set for all k ∈ [K]. Then we can define a deterministic function which maps the state and each discrete action k to its corresponding continuous parameter xk:

where θ are weights of the deterministic policy network. We further define an action-value function Q (s, k, xk; ω) which maps the state and hybrid actions to real values. Here ω are weights of the value network.

P-DQN updates the action-value function Q by minimizing the following loss:

where y = r + maxk∈[K] γQ(s′ , k, µk(s′ ; θ); ω), and s′ denotes the next state after taking hybrid action (k, xk). The policy µk for the continuous part is updated by minimizing the following loss with parameters ω fixed:

3 Methods

To handle hybrid action spaces in multi-agent settings, one natural approach is to adopt the independent learning paradigm and equip each agent with an independent P-DQN algorithm. However, one major issue is that each agent's policy changes during training, resulting in the non-stationarity of environments. As we will show in our experiments in Section 4, independent P-DQN does not perform well in practice.

In this paper, we propose two novel deep multi-agent learning methods for hybrid action spaces, Deep MAPQN and Deep MAHHQN. By leveraging the current state-of-the-art single-agent deep RL for hybrid action spaces and coordination techniques for multi-agent learning, both algorithms can support multiple agents to learn effective coordination policies directly over the hybrid action spaces.

3.1 DeepMulti-Agent Parameterized Q-Networks (Deep MAPQN)

The first algorithm is a natural extention of single-agent PDQN. We leverage Qmix [Rashid et al., 2018] architecture to coordinate the policy update over hybrid action spaces among agents. The overall structure of Deep MAPQN is shown in Figure 1.

For each agent, we adopt the same settings in P-DQN. Concretely, considering a game with N agents, each agent i uses a deterministic policy network µki (θi) and an action value network Qi(ωi) to output hybrid action (k∗ i , x∗ki ). The deterministic policy network µki (θi) takes each agent's observation oi as input and outputs the optimal continuous parameters xki for all the discrete actions ki ∈ {1, · · · ,Ki}. Then the action value network Qi outputs the optimal hybrid action by:

where ωi are parameters for action value network of agent i.

To achieve coordinated update among agents' action value networks, we utilize a mixing network and produce a fully centralized state-action value function Qtot which can facilitate the coordinated update of the decentralized policies in hybrid action spaces. The mixing network consists of a feedforward neural network and separate hypernetworks. The hypernetworks take the global state s as the input and output the weights of the feedforward network. The feedforward network takes each agent's output Qi as input and mixing them monotonically, producing the joint action value denoted by Qtot. 1 Here we define the mixing network as a non-linear complex function f and denote this process by:

We update the mixing network weights ωmix along with each agent's action value network weights ωi by minimizing:

1 The detailed structure for the mixing network can be found at: https://bit.ly/2Eaci2X.

(⃗k, ⃗xk) is the joint action, θ′ are parameters of target policy networks. Our framework for computing Qtot ensures offpolicy learning updates while each agent can still choose the greedy action with respect to its own Qi in a decentralized fashion. This is because a global argmax on Qtot is equivalent with argmax on each Qi as explained in Section 2.2.

Finally we need to compute gradients for deterministic policy network. We first take the sum of Q-values of all the discrete actions for each agent i:

and then feed them into the mixing network, producing the value of Qstot . This process can be denoted by:

We update all agents' continuous policies µi (i ∈ N) by maximizing Qstot with parameters ωi and ωmix fixed, the gradient can be written as:

In this way we can update the policies of continuous parameters for all the different agents and different discrete actions in one single training step.

However, this algorithm may result in high computational complexity during both training and execution phases: every time we compute the joint action value Qtot, we need to compute continuous parameters for all the K discrete actions of all the agents. This is particularly severe when the discrete part of hybrid action space has a large dimension. The same problem exists in original P-DQN as well.

3.2 DeepMulti-Agent Hierarchical Hybrid Q-Networks (DeepMAHHQN)

To address the problem we mentioned in previous section, we propose another novel algorithm Deep MAHHQN, as inspired by Hierarchical Learning [Kulkarni et al., 2016; Tang et al., 2018].

The overall structure of Deep MAHHQN is illustrated in Figure 2. Different from Deep MAPQN, when choosing hybrid actions, a Deep MAHHQN agent first chooses a discrete action through high-level network and then decides the corresponding continuous parameters conditioning on the given discrete action and individual observation through low-level network. This is consistent with human's decision-making process since in real world humans usually tend to decide what to do before deciding to what extent to do it. We train the high-level network and low-level network separately and both of them follow the centralized training but decentralized execution paradigm.

As for the high-level network, each agent utilizes the basic DQN [Mnih et al., 2015] framework to select a discrete action ki given its own observation oi. The high-level policies among agents over discrete actions are coordinated by using the mixing network structure [Rashid et al., 2018]. Importantly, unlike Qmix which only takes global state s as inputs for the hypernetworks to produce weights of mixing networks, we further consider low-level network's current policies for each agent. This information is critical for coordinating agents' discrete actions since the hybrid action spaces are highly correlated in determining the global optimal policies. Concretely, at each training step, we first calculate the continuous parameters xi related to each agent's high level action ki using the current low-level network's policy (i.e., xi = µi(ϕ(oi, ki)) ). Then we combine them (i.e., χ = {x1, · · · , xN} ) with the global state s and feed them into the hypernetworks to generate weights for the mixing network. The high-level networks' parameters are updated by minimizing the following loss:

where ⃗k denotes the joint discrete action sampled from the replay buffer, ytot = r + γmax⃗k′ Qhtot (s′ ,⃗k′ , χ′ ), χ′ is a set of continuous parameters from low-level target policies.

For the low-level part, each agent i chooses continuous parameters xi according to its new observation:

where ki is the discrete action obtained from the high-level part. In our experiments, we simply concatenate oi and ki as the new observation ̂ oi. In order to learn a coordinated policy over the corresponding continuous parameters, we apply Multi-agent Actor-critic framework [Lowe et al., 2017] and further modify it with a centralized Q function for each agent. Considering N agents with low-level policies parameterized by θ = {θ1, · · · , θN}, and let µ = {µ1, · · · , µN} be the set of all agents' low-level policies. The gradient with expected return for agent i with low-level policy µi can be written as:

Here Qli (s, k1, x1, · · · , kN, xN) is a centralized action-value function that takes as input the hybrid actions of all agents (k1, x1), · · · , (kN, xN), in addition to the global state s, and outputs the low-level Q-value for agent i. The experience replay buffer D contains the tuples (s, k1, x1, · · · , kN, xN, r1, · · · , rN, s′ ). The centralized Q function is updated as:

where Ql′ i denotes the low-level target Q network for agent i. Note that k′i are derived from high-level target policies. Combining (14) and (15) yields our proposed low-level network.

Compared with Deep MAPQN, Deep MAHHQN only needs to calculate one discrete action with the optimal continuous parameters for each agent. This would significantly reduce the algorithm's computational complexities, which will be validated in our experimental results. Moreover, both lowlevel and high-level training frameworks of Deep MAHHQN are augmented with extra information about policies of other agents and policies of other action levels. In hybrid action environments, we expect that such kind of communication would better alleviate the non-stationary issue of the environments.

When training Deep MAHHQN, we let the low-level network train alone for m steps and then start training high-level and low-level network together. The main reason is that the associated low-level continuous parameters play an important role when our high-level network computes the value of Qhtot . Otherwise, the gradients for high-level network can be very noisy and misleading since the low-level policies are still exploring at a high rate at the very beginning.

4 Experimental Results

In this section, we evaluate our algorithms in 1) the standard benchmark game HFO, 2) 3v3 mode in a large-scale online video game Ghost Story. We compare our algorithms, Deep MAPQN and Deep MAHHQN, with independent P-DQN in all our experiments.

4.1 Experiments with Half Field Offense (HFO)

Half field Offense (HFO) is an abstraction of full RoboCup 2D game. The environment features in a hybrid action space. Previous work [Hausknecht and Stone, 2016; Wang et al., 2018; Wei et al., 2018b] applied RL to the single-agent version of HFO, letting one agent try to goal without a goalkeeper (1v0). In this paper, we apply our proposed algorithms on the challenging multi-agent problems of HFO , which includes 1v2 (two agents with the shared objective of defending the goal against one opponent) and 2v1 (two agents with the shared objective of scoring the goal against one goalie). The opponent (or goalie) we play against are all built-in handcoded agents.

We use the high level feature set and each agent's observation is a 21-d vector consisting of its position and orientation; distance and angle to the ball and goal; an indicator if the agent can kick etc. A full list of state information can be found at the official website https://github.com/mhauskn/ HFO/blob/master/doc/manual.pdf.

In our experiments, we use a discrete-continuous hybrid action space. The full set of hybrid actions is: Kick To (targetx, targety, speed); Move To (targetx, targety); Dribble To (targetx, targety); Intercept(). Valid values for targetx,y ∈ [-1, 1] and speed ∈ [0, 3]. In this settings, acting randomly is almost unlikely to score or successfully defend the goal and the exploration task proves too difficult to gain traction on a reward that only consists of scoring goals. Thus, we do reward engineering to our two tasks respectively to alleviate the sparse reward problem, which will be described in details in following sections.

1v2 Defense

In the defending scenario, our models control two agents with the shared objective of defending the goal. Note that for defensive agents, only two actions Move To and Intercept are applicable since the defensive players do not control the ball. The reward for each time step is calculated as a weighted sum of the following three types of statistics:

• Move to ball reward: A reward proportional to the change in distance between the agent and the ball.
• Punishment for no agent in goal area. We add a punishment if there's no defensive agent in the goal area.
• Bonus points for game result. Agents will get extra positive points if they successfully defend the goal and vice versa.

We can see from Figure 3 that both Deep MAPQN and Deep MAHHQN achieve much higher performance than PDQN. This demonstrates the benefits of explicitly coordinating the joint hybrid policies among agents. In addition, Deep MAHHQN is found to outperform Deep MAPQN after convergence. We attribute this to the improved communication between different agents when we do centralized training for Deep MAHHQN. We further examine the learned behaviours of policies in order to better understand the methods. The agents of Deep MAPQN and Deep MAHHQN tend to play different roles automatically when defending the ball: one agent moves directly to the goal area and act like a goalkeeper while the other one approaches the offensive player trying to capture the ball. In contrast, the agents of P-DQN tend to approach the offensive player or move to the goal area together without cooperating with an appropriate division of their roles. A video of our learned policies may be viewed at https://youtu.be/ndJYZFL5BxE.

2v1 Offense

We further evaluate our algorithms on 2v1 offense mode which have larger action space and the coordination task is expected to be more challenging. In this scenario, our models control two agents aiming to score a goal against one goalie. We add a discrete action Shoot() to our action list and there are totally five types of actions for this experiment. The reward for each time step is calculated as a weighted sum of the following types of statistics:

• Move to ball reward: Similar to last section.
• Kick to goal reward: A reward proportional to change in distance between the ball and the center of the goal.
• Additional punishment: To avoid long shot, we add an additional punishment if the ball is too far away from both agents when it is still outside the goal area.
• Bonus points for game result: Agents will get extra points if they successfully score a goal.

As shown in Figure 4, in this challenging offense problem, independent P-DQN fails to learn the coordination policy. In practice, we observe that independent P-DQN agents first try to approach the ball, then dribble it to somewhere and stop without shooting. A primary reason for this may be the lack of information of other teammates. In comparison, our proposed methods Deep MAPQN and Deep MAHHQN perform much better. Similar to the previous defense setting, the Deep MAPQN agents learn policies a little faster than Deep MAHHQN in terms of the number of time steps required. The underlying reason is that in Deep MAPQN we update policies of continuous parameters associated with all the discrete actions at one single training step. However, such a framework also introduces huge computational complexity since each training step of Deep MAPQN occupies much more computing resources than Deep MAHHQN. This problem can be seen more clearly in our second game (Ghost Story) with a more complicated practical environment.

4.2 Experiments with Ghost Story

We evaluate the proposed algorithms with Ghost Story (or QianNvYouHun) - a fantasy massive multiplayer online roleplaying game (MMORPG) from NetEase, in which each of the learning agents controls an individual hero. We performed our evaluation in the "3v3" game mode, where 3 hero agents cooperate with each other to fight against the other 3 built-in AI on the opposite side. At each time step, every hero can choose to move or use one of its own skills. The game ends when all 3 heroes on the same side are killed.

The observation for each agent is a 97-d feature vector which is manually constructed using output from the game engine. Concretely, these features consist of some basic properties of the agents: agent's Health Point (HP), value range of attack, value range of defense 2 , carried skills and Cool Down (CD), carried buffs 3 , relative positions etc.

We simplify the actions of each hero into five hybrid action types: Move(x, y), move to a relative position(x,y); and four skills, Tanlang(x, y), Siguai(x, y), Tianshou() and Hegu(x, y). When a hero player chooses to use a skill, the enemies near the relative position (x, y) will be attacked or added some buffs depending on the specific types of selected skills. Skill Tianshou has no parameters since it functions as adding a buff on the hero agent itself. More details of our experimental settings can be found at https://bit.ly/2Eaci2X.

At each time step, each agent receives a joint reward consists of four parts: (1) the change in HP for all heroes; (2) a punishment for the agents which did not do anything (e.g. No enemy is near the skill's target point; the selected skill's CD is not zero ); (3) small bonus points for killing an enemy hero and huge bonus points for winning the game.

2 The agent's true attack or defense value is uniformly distributed on the given value range.

3 Buffs can be beneficial, such as increase agent's own defense value, or harmful, such as decrease its own attack value, but buffs can only exist for a short time period.

Figure 6: Win rates for Deep MAPQN, Deep MAHHQN and PDQN in 3v3 mode of Ghost Story

Figure 6 shows our experimental results. Clearly we can see independent P-DQN fails to learn a coordinated policy that can consistently defeat the enemies. Both Deep MAPQN and Deep MAHHQN outperform independent P-DQN learning method and get a win rate over 75%. Moreover, we find Deep MAHHQN method performs slightly better than Deep MAPQN, which further validates that the improved communication between agents using information about policies of other action levels can better stabilize the centralized training process. It indicates that Deep MAHHQN framework provides a better way to handle problems with large hybrid action space and number of agents. A final note is that the actual training time of Deep MAPQN is about three days while Deep MAHHQN takes less than one day to train on the same NVidia Geforce GTX 1080Ti GPU. This is quite reasonable since each MAPQN agent need to compute continuous parameters for all the discrete actions at each single training step while in Deep MAHHQN we only need to calculate low level continuous parameters associated with the selected optimal high-level discrete action.

5 Conclusion

This paper should be seen as the first attempt at applying deep reinforcement learning in cooperative multi-agent settings with discrete-continuous hybrid action spaces. Two novel approaches are proposed under the paradigm of centralized training and decentralized execution. The experimental results show their superiority to independent parameterized Q-learning method under both the standard testbed HFO and a large-scale MMORPG game. As future work, we wish to extend our algorithms to competitive multi-agent settings, and conduct additional experiments with more agents and larger hybrid action space to further investigate the difference of performance between our two proposed algorithms.

Acknowledgments

The work is supported by the National Natural Science Foundation of China (Grant Nos.: 61702362, U1836214), Special Program of Artificial Intelligence and Special Program of Artificial Intelligence of Tianjin Municipal Science and Technology Commission (No.: 569 17ZXRGGX00150).