SHAQ: Incorporating Shapley Value Theory into Multi-Agent Q-Learning
Authors: Jianhong Wang
Yuan Zhang
Yunjie Gu
Tae-Kyun Kim
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-Agent Reinforcement Learning
Shapley value
Q-Learning

Abstract: Value factorisation is a useful technique for multi-agent reinforcement learning (MARL) in global reward game, however, its underlying mechanism is not yet fully understood. This paper studies a theoretical framework for value factorisation with interpretability via Shapley value theory. We generalise Shapley value to Markov convex game called Markov Shapley value (MSV) and apply it as a value factorisation method in global reward game, which is obtained by the equivalence between the two games. Based on the properties of MSV, we derive Shapley-Bellman optimality equation (SBOE) to evaluate the optimal MSV, which corresponds to an optimal joint deterministic policy. Furthermore, we propose Shapley-Bellman operator (SBO) that is proved to solve SBOE. With a stochastic approximation and some transformations, a new MARL algorithm called Shapley Q-learning (SHAQ) is established, the implementation of which is guided by the theoretical results of SBO and MSV. We also discuss the relationship between SHAQ and relevant value factorisation methods. In the experiments, SHAQ exhibits not only superior performances on all tasks but also the interpretability that agrees with the theoretical analysis. The implementation of this paper is placed on https://github.com/hsvgbkhgbv/shapley-q-learning.

SHAQ: Incorporating Shapley Value Theory into Multi-Agent Q-Learning
Jianhong Wang Imperial College London, UK jianhong. wang16@imperian ac
Yuan Zhang
University of Freiburg, Germany yzhang@cs uni mii-freiburg
Yunjie Gu University of Bath, UK yg9348bath. ac.
Tyu-Kyun Kim
KAIST, South Korea kimtaekyunkkaist.aa ac
Abstract
Value factorisation is useful technique for multi-agent reinforcement learning (MARL) in global reward game, however, its underlying mechanism is not yet fully understood. This paper studies a theoretical framework for value factorisa- tion with interpretability via Shapley value theory. We generalisc Shapley value to Markov convex game called Markov Shapley value (MSV) and apply it as value factorisation method in global reward game, which is obtained by the equivalence between the two games. Based on the properties of MSV, we derive Shapley-Bellman Bellman optimality equation (SBOE) evaluate the optimal MSV, which corresponds to an optimal joint deterministic policy. Furthermore, we propose Shapley-Ber -Blllmnn operator (SBO) that is proved solve SBOE. With stochastic approximation and some transformations, a new MARI algorithm called Shapley Q-learning (SHAQ) is established. the implementation of which is guided by the theoretical results of SBO and MSV. We also discuss the relationship between SHAQ and relevant value factorisation methods. In the experiments, SHAQ ex- hibits not only superior performances on all tasks but also the interpretability that agrees with the theoretical analysis. The implementation of this paper is placed on https: httpssu///ithub.... http:///.w/ssggghg////happpppe --aaalllyy-----i-nngggg-
Introduction
Cooperative games critical research area in multi-agent reinforcement learning (MARL). Many real-life tasks can be modeled as cooperative games, e.g. the coordination of autonomous vehicles [1]. autonomous distributed logisties [2] and distributed voltage control in power networks [3] In this paper, we consider global reward game (a.k.a. team reward game), an important subclass of cooperative games, wherein agents aim jointly maximize cumulative global rewards time. There are two categories methods to solve this problem: (i) each agent identically maximizes cumulative global rewards, i.c. learning with shared value function 4-66: and (ii) each agent individually maximizes distributed values, i.c. learning with (implicit) credit assignments (c.g. marginal contribution and value factorisation) (7HТ
By the view of con-ooopeertive game theory, global reward game are equivalent to Markov game [2 with global reward (a.k.a. team reward). Its aim is to learn stationary joint policy to reach a Markov equilibrium so that no agent tends to unilaterally change its policy to maximize cumulative global rewards. Standing by this view, learning with value factorisation cannot be directly explained [ In
"Corresoondence Yunjie Gu who also honorary lecturer Imperial College London.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

this paper, to clearly interpret the value factorisation, we take the perspective of cooperative game theory [4.. wherein agents are partitioned into coalitions and payoff distribution scheme is found to distribute optimal values to coalitions. The corresponding solution is called Markov core, whereby no agent has an incentive to deviate. When all agents are partitioned into one coalition (called grand coalition), the payoff distribution scheme naturally plays the role of value factorisation.
Wang et al. 13 extended convex game (i.e. a game model in cooperative game theory) dynamic scenarios, which we name as Markov convex game in this paper. We construct the analytic form of Shapley value for Markov convex game, and prove that it reaches the Markov core under the grand coalition, named as Markov Shapley value. The optimal Markov Shapley value implies not only the optimal global value but also that no agent has incentives to deviate from the grand coalition. Additionally, Markov Shapley value enjoys the following properties: (i) identifiability of dummy agents; (ii) efficiency; (iii) reflecting the contribution; and (iv) symmetry. These properties aid the interpretation and validity of value factorisation in the global reward game, and such transparency and reliability are critical to industrial applications
14 to
Based on the efficiency property, we derive Shapley-Bellmen optimality equation that is an extension of Bellman optimality equation [1S [6) Moreover, we propose Shapley-Bellman operator and prove its convergence to the Shapley-Bellman optimality equation and its optimal joint deterministic policy, With a stochastic approximation of Shapley-Bell Bellman operator and some transformations, we derive an algorithm called Shapley Q-learning (SHAQ). SHAQ learns to approximate the optimal Markov Shapley Q-value (an equivalent form of the optimal Markov Shapley value). Moreover, we enable SHAQ decentralised in order to fit the decentralised execution framework and this decentralisation still remains the convergence condition of Shaaley--elllmas operator.
The proposed method, SHAQ, is evaluated on two global reward games such as Predator-Prey 17 and multi-agent StarCraft benchmark tasks [А. In the experiments, SHAQ shows not only generally good performances on solving all tasks but also the interpretability that is deficient in the state-of-the-art baselines.
2 Markov Convex Game
We now formally define Markov convex game (MCG) that can be described as tuple S,,,A, T, A, n, R). N the set of all agents. is the set of states and A Xi is the joint action set of all agents wherein A; is each agent's action set. ass) (CI....CC.) is a coali- tion structure, where C, S N called coalition is subset of all agents. A is collection of coalition structures. Ø and N are two special cases of coalitions i.c. the empty coalition and the grand coalition respectively. Conventionally, it is assumed that NC 2, VC,,, S N. π x "t ; is the joint policy of all agents. For any coalition C, it is equipped with a coalition policy Te ( (aels) [s) Ti (a,ls) defined over the coalition action set A X A,. Therefore, π can
Pr(s'|s,a)
is defined as the transition probability between the successive states. CS =
be seen as the grand coalition policy. R₁ : S x Ac + [0, oo) (i.e., a characteristic function) is the coalition reward at time step I. Accordingly, Rs,,, a) is the grand coalition reward (i.e., equivalent to the global reward) at time step / that is written as R(s, a) or R for conciseness in the rest of paper. 7 (0, 1) is the discounted factor. The infinite long-term discounted cumulative coalition rewards is defined as (s) lE - - 11 [e ac) S. = s] [O, oo). called coalition value. Moreover, the empty coalition value VT 0 and V (s) denotes the grand coalition value (i.e. also called the global value since the equivalence proof from (3).. The solution of MCG is to find a tuple (CS, (max,, (z(s)) credit assignments) under the optimal joint policy given coalition structure. Under the assumption C. NC+ = Ø, VCm,,C, S., the condition for MCG is as follows:
where (max,, (s)))) indicates the payoff distributions (i.e.
max TCC (s) 2 max 5m (s) max TC (s), VCm, C2 SNNCC Cm U Ct. Tou
(1)
mC2
In MCG with the grand coalition i.e., (N), Markov core, a solution concept describing stability, is defined as a set of payoff distribution schemes by which no agent has incentives to deviate from the grand coalition to gain more profits. Mathematically, Markov core can be expressed as:
MarkovCore = {(max (ev] max ma(C(ss(C 2 max V (s), VC SN,sE s....
(Imax:
(2)
Se
RC

---

where maxa: x(s(C) Exec max=; Iz (s). It aims to find a payoff distribution scheme (z)( that can finally converge to Markov core under the optimal joint policy.
To assist the application on Q-learning, we similarly define coalition Q-value as Q (s. a²) [O, + +00) for all coalitions C C W. Following the ahove convention, the grand coalition Q-value (or the global Q-value) can be written as Q" (s. a). Moreover, the optimal coalition Q-value of C w.r.t. the optimal joint policy of D S C (i.e., ) and the suboptimal joint policy of CDD (i.e., Teyp) is defined as QTD (s. ac). Therefore, the optimal coalition Q-value of w.r.t. the optimal joint policy of C is defined as Q (s, Accordingly, the optimal global coalition Q-value w.r.t. the optimal joint policy of the grand coalition is denoted as Q" (s.
3 Markov Shapley Value
By the view of cooperative game theory, the grand coalition progressively formed by a permutation of agents. Accordingly, marginal contribution is implementation of the credit reflecting agent's contribution. The formal definition is shown Definition II
Definition 1. In Markov convex game, with permulation of agents (j1, j2,--in-- Vjn e N forming the grand coalition N, where a E [1...,Wi] W ja + jo if a # b, the marginal contribution of an agent i is defined as the following equation such that
2 (s|C.)
max TTcut) (s) max V TC, (s), ne,
(3)
where C; --i,--.: for j. i is an arbitrary intermediate coalition where agent i would join during the process of grand coalition formation.
Proposition Agent i's action marginal contribution can be derived as follows:
ss a.(C,) = -max Q (s,,),)))) max Q (s, ac:).
ac;
ac;
As Proposition D shows, an agent's action marginal contribution (analogous to Q-value) can be It is usually more useful for solving MARL problems.
derived according Eq E
is apparent that marginal contribution only considers one permutation to form the grand coalition. By the viewpoint from Shapley [1) the fairness is achieved through considering how much the agent i increases the optimal values (i.e. marginal contributions) of the coalitions in all possible permutations when it joins in, i.e., max V=ecu(() (s) max V (s), VC, S [N((1. Therefore, we construct Shapley value under Markov dynamics based on the marginal contributions shown in Definition 2 named as Markov Shapley value (MSV).
Definition 2. Markov Shapley value is represented as
ICILCCI- C. CCI (s(C.).. WI
(s)= Σ
(5)
C. EMN
With the deterministic policy, Markov Shapley value can be equivalently represented as
- 1)! @,sssa.(..).
(s,,,)))= E
(6)
WI!
C. CEEN
where (s(C.) is defined in Eq and Φ:(s, as/C:) is defined in Eq
3
6 as Markov Shapley Q-value (MSQ). Briefly, MSV calculates the weighted average of marginal contributions. Since a coalition may repeatedly appear among all permutations (i.e. Wi! permutations), the ratio between the occurrence frequency (CC)(((V) and the total frequency W!! is used as a weight to describe the importance of the corresponding marginal contribution. Besides, the sum of all weights equal to so each weight can interpreted as a probability distribution. Consequently, MSV can be seen as the expectation of marginal contributions, denoted Ec.-Pr(C.IVV())) (s(C.)) Note that Pr(C((N(()) probability distribution. By the above relationship. Remark i directly obtained.
For convenience, name B
bell-shaped
Remark Uniformly sampling different permutations is equivalent to directly sampling from Pr(C,)A( since the coalition generation is from the permutation form the grand coalition.
3

---

Proposition 2. Markov Shapley value possesses properties as follows: (i) identifiability of dummy agents: Vi((s) =0, 0: (ii) efficiency: max, V (s) EiEN max=; V (s); (ii) reflecting the contribu- tion; and (iv) symmetry.
Proposition shows four properties of MSV. The most important property is Property (ii) that aids the formulation of Shapley-Bellman optimality equation. Property (ii) shows that MSV a fundamental index quantitatively describe each agent's contribution. Property (i) and (iii) play important roles in interpretation for value factorisation (or credit assignment). Property (iv) indicates that two agents are symmetric, then their optimal MSVs should be equal, but the reverse does not necessarily hold. All these properties that define the fairness are inherited from the original Shapley value 19]
Shapley Q-Learning
4.1 Definition and Formulation
Chapley-Bellmane Optimality Equation. Based on the Bellman optimality equation 15 and the following conditions (the interpretability of which are left to Section
C.I. Efficiency of MSV (i.e. the result from Proposition D
C.2. 0 (s. wi (s, a.) Q (s,a) - (s)),, where w/ az) 0 and (;(s) 2 are bounded and Eie (s. b, (s) = 0,
we derive Shapley-Bellman optimality equation (SBOE) for evaluating the optimal MSQ (an equiva- lent form to optimal MSV) such that
Q (s, a) Σ ar) g'eS
R+ y E iNN a:
max
Of (s' (s( b(s),
where w(s, a) = as)] RIM b(s) [s)] R. Q (s. = 10 (s, e R and Q (s, a;) denotes the optimal MSQ. If Eq holds, the optimal MSQ is achieved. Moreover, reveals implication that for any S and at = arg max., O (s,a;), we have a solution (s, 1/LV (see Appendix E.4.1. Literally, the assigned credits would be equal and each agent would receive Q" (s, a\/ if performing the optimal actions. It is apparent that the efficiency still holds under this situation, which can be interpreted as an extremely fair credit assignment such that the credit to each agent should not be discriminated if all of them perform optimally, regardless of their roles. The equal credit assignment was also revealed by Wang et al. [20] recently from another perspective of analysis. Nevertheless, w; (s, a,) for a, arg maxa, Q (s.a:) needs to be learned.
Shapley-Bellmn Beelman Operator. To find an optimal solution described by Eq we now propose an operator called Shapley-Bellman Bellman operator (SBO), i.c., T Xx (s) + Of a.). which is defined as follows:
max (s', [a)] b(s), r (X = ass Σ Pr(s'(s,a) R+ 7 Σ STe
(8)
eeN a;
where wi ws a.)) 1/P1 when a; arg maxa, Q (s, az). We prove that the optimal joint determinis- tic policy can be achieved by recursively running SBO in Theorem [
Theorem 1. Shapley-Bellee Bellman operator is able to converge to the optimal Markov Shapley Q-value and the corresponding optimal joint deterministic policy when max, { Eien max., w a:)} 2/2
Shapley Q-Learning. For easy implementation, we conduct transformation for the stochastic approximation of SBO and derive Shapley Q-learning (SHAQ) whose TD error is shown as follows:
A(s,a.s') R
Σ &NN
max Q (s', Σ á, a.) (s,
de
ieN
where
11 (s,
(s a # arg max,, (s,
(s, =
01 arg maxa;
(10)

---

Actually, the closed-form expression of (s a;) is written as condition that w,(s, a.) 1//M1 when a, arg max., (s, a,) as well defining (, a,) as as(s,a;) when a # arg maxa; 0, a.), Eq 10 is obtained. The term b(s) is cancelled in Eq 9
If inserting the
thanks to the condition such that Ene w/(s, a.) (s) O. Note that the condition to (; 0z) in
Theorem T should hold for the convergence of SHAQ in implementation (see Appendix
4.2 Validity and Interpretability
In this section, we show the validity of SBOE and the interpretability of SHAQ, i.e., providing the reasons why SBOE is valid to be formulated and SHAQ is an interpretable value factorisation method for the global reward game.
Theorem 2.
The optimal Markov Shapley value is solution in the Markov core under Markov convex game with the grand coalition.
Remark 2. For an arbitrary state s S, by C.2 it is not difficult to check that even if an arbitrary agent? i is dummy (i.e., Q (s, = 0 for some i E N, Q" (s, a) and O (s, az), V.j + i would not be zero if (s) + 0. If the extreme case happens that for an arbitrary state s S all agents are dummies, since EieN W/ (s,ss,;) by()) O we are allowed to set by(s) 0, e N so that Q" as. 0 and efficiency such that max, Q" (s, = EiEN maxo; Q (s, (s) is still valid.
First, we give a proof for showing that the optimal MSV a solution in Markov core under the grand coalition, as Theorem 2 shows. Since a solution in Markov core implies the optimal global value (see Remark 5 in Appendix (.2.2), we can conclude that the optimal MSV can lead to the optimal global value (a.k.a. social welfare), which links Condition C.I to Markov core. As result, solving SBOE is equivalent to solving Markov core under the grand coalition and SHAQ is actually a learning algorithm that reliably converges to Markov core. As per the definition in Section 2 can say that SHAQ leads to the result that no agents have incentives to deviate from the grand coalition, which provides interpretation of value factorisation for global reward game. Condition C.2 is condition that maintains the validity of the relationship between the optimal MSQ and the optimal global Q-value even if there exist dummy agents (see Remark 2 so that the definition of SBOE is valid for MCG and MSQ in almost every case, which preserves the completeness of the theory.
4.3 Implementations
We now describe practical implementation of SHAQ for Dec-POMDP [2I (i.e. the global reward game but with partial observations). First, the global state is replaced by the history of each agent to guarantee the optimal deterministic joint policy [I]. Accordingly, Markov Shapley Q-value is denoted as @ (Ta, (T)) wherein r; is history of partial observations of agent i. Since the paradigm of centralised training decentralised execution (CTDE) 22 is applied, the global state (i.e. s) for (s, o;) can be obtained during training.
Proposition 3. Suppose any action marginal contribution can be factorised to the form such that d, (s, a(s, Bcsuts) (ssss.)). With the condition such that
[1 K 10,
ag = arg max., (8 a:); # arg max (s)
Ec,- Bc.-Pr(CANN ac(())))
{
we have
(0((s,)))(((s,a))) = (s,
a, = arg max.; Q,
(11)
(1)(s, (s, âr(s, a:) (s)),
a, + arg maxa, as(s,a;),
where (s) Ee.-PrC. (s, ari a,, and (s, ar a,; a as) a d.
Compatible with the decentralised execution, we use only one parametric function Q1 0z) to directly approximate Q a.) By inserting Eq 11 into Eq (s, a;) is transformed into the form as follows:
8,(s, [1
arg max.; Qi a;), (s, a, arg max., as,s)))
(12)
5

---

where as,s),,) (c,-Pr(C,)M()) [Ws(s, als,aa;;e,)) ac; To solve partial observability, Qi(T,, a²) is
empirically represented as recurrent neural network (RNN) with GRUs 23 (i dj; ae, ) is directly approximated by parametric function F& + 1 and thus ás a;) can be expressed as follows:
(s)
Σ
Fa (Qot act), Qi(Ts, +1,
(13)
M
1=11
where Qct (r,
1c5 ject 25(T), and C is sampled M times from Pr(CI (i.e.,
implemented as Remark suggests) approximate Ec,-- Prc, (V)) [& 0g az using Monte Carlo approximation; and Fg is a monotonic function, followed by an absolute activation function, whose weights are generated from hyper-networks w.r.f. the global state. We show that Eq B satisfies the condition to ws, a;) in Theorem |
(see Appendix I.
). so it is reliable implementation.
By using the framework of fitted Q-learning infinite) and plugging in the above designed modules, the practical ceast-square-erve loss function derived from Eq D is therefore stated as follows:
24 to solve large number of states (i.e., could be usually
min E E...R..Rrr 0,A
( (R+
Σ max Qi(T, VeN a;
& (((r,;;)))))) ieN
(14)
where all agents share the parameters of (s, a;; 0) and (s, a;; A) respectively; and (s's,, a,;; 0-) works the target where O" is periodically updated. The general training procedure follows the paradigm of DQN [25] with a replay buffer to store the online collection of agents' episodes. To depict overview of the algorithm, the pseudo code is shown in Appendix A
5 Related Work
Value Factorisation in MARL. To deal with the instability during training in global reward game
by independent learners (266. the centralised training and decentralised execution (CTDE) 22
was
proposed and it became a general paradigm for MARL. Based on CTDE, MADDPG 27 learns a
global Q-value that can be regarded as assigning the same credits to all agents during training [3]
which may cause the unfair credit assignment 28 To avoid this problem, VDN ( was proposed to
learn the factorised Q-value, assuming that any global Q-value equals to the sum of decentralised Q-values. Nevertheless, this factorisation may limit the representation of the global Q-value. To
mitigate this issue, QMIX 2 and QTRAN [T were proposed to represent the global Q-value with richer class w.r.t. decentralised Q-values, based on the assumption (called Individual-Global-N of convergence to the optimal joint deterministic policy. Markov Shapley value proposed in this paper belongs to the family of value factorisation, based on the game-theoretical framework called MCG that enjoys the interpretability. From the conventional cooperative games (e.g., network flow game 29), induced subgraph game [E0 that can be used for modelling social networks, and facility location game (31), it is insightful that the coalition introduced in this paper exists. In many scenarios, however, the information of coalition might be unknown. Therefore, the latent coalition is assumed, and we only need to concentrate the observable information, e.g., the global reward.
Relationship to VDN. By setting (s, a.) = 1 for all state-action pairs, SHAQ degrades to VDN о. Although VDN tried to tackle the problem of dummy agents, Sunehag et al. [8] did not give a theoretical guarantee on identifying it. The Markov Shapley value theory proposed in this paper well addresses this issue from both theoretical and empirical aspects. These aspects show that VDN is a subclass of SHAQ. The theoretical framework proposed in this paper answers to why VDN works well in most scenarios but performs poorly in some scenarios (i.e., (s..,,) = in Eq was incorrectly defined over the suboptimal actions).
Relationship to COMA. Compared with COMA each agent i's credit assignment Q1 a;) is mathematically expressed as follows:
Qi(s. Q" (s, a)) (s. =s (a.ss)) (s. (s,;;a)))))
where subscript -i indicates the agents excluding Qs a;) can be seen as the action marginal contribution between the grand coalition Q-value and the coalition Q-value excluding the agent i,

---

under some permutation to form the grand coalition wherein agent is located at the last position. The efficiency is obviously violated (i.e., the sum of optimal action marginal contributions defined here is unlikely to be equal to the optimal grand coalition Q-value). In contrast to COMA, SHAQ considers all permutations to form the grand coalition to preserve the efficiency.
Relationship to Independent Learning, Independent learning (e.g. IQL 26 ) can be also seen as a special credit assignment, however, the credit assigned to each agent is still with no intuitive interpretation. Mathematically, suppose that Qs, a.) is the independent Q-value of agent i, we can rewrite it in the form consisting of action marginal contributions such that
(: a:) PCC.PP(CC,MM())) (ss,a
is intuitive to see that the independent Q-value is a direct approximation of MSQ. ignoring coalition formation, while SHAQ considers coalition formation in approximation. This gives an explanation for why independent learning works well in some cooperative tasks [32. Nevertheless, it encounters the same issue as in COMA, the loss of properties led by the coalition formation.
Relationship to SQDDPG. We now discuss the relationship between SQDDPG 1K and SHAQ. In terms of algorithms, SQDDPG belongs to policy gradient methods (i.e. an approximation of policy iteration) while SHAQ belongs to value based methods (i.c. an approximation of value iteration). Since policy iteration (with one-step policy evaluation) is equivalent to value iteration [A3] (at least under a finite state space and a finite action space), the theory behind SHAQ directly fills the gap in SQDDPG theoretical guarantees of convergence to optimal joint policy. Specifically, the learning procedure of SQDDPG iteratively performs the following two stages:
Stage 1:
min Bs, a.s R.
R +
Σ (.(('''))))))
- ((,(,))))) iN
0
HN
Stage 2:
(s) arg max (s, az
It can be observed that both SQDDPG and SHAQ ideally converge to the same optimal MSQs w.r.t. the optimal actions such that
Of (s, (3 )²]=0 =0.
Eg.s/ max R(s, + y Σ max Q (s',a)) - Σ max NnN of
sN a:
However, about suboptimal actions, SQDDPG does not provide any theoretical guarantee, whereas SHAQ does with specific implementations as shown in Eq 13 to match the theoretical results shown in this paper. Note that this is critical to reliable interpretations of the optimal MSQ w.r.t. suboptimal actions (c.g., for detecting adversarial attacks on controllers if deployed in industry (4|).
6 Experiments
In this section, we show the experimental results of SHAQ on Predator-Prey 1 and various tasks in StarCraft Multi- Agent Challenge (SMAC) The baselines that we select for comparison are COMA
ZZ. VDN
R QMIX 19, MASAC (36. OTRAN I0, QPLEX 377 and W-QMIX (including CW-
OMIX and OW-QMIX) 355 The implementation details of our algorithm are shown in Appendix
B.1
whereas the implementation of baselines are from 3 We also compare SHAQ with SQDDPG
which is shown in Appendix C.3 For all experiments, we use the e-greedy exploration strategy, where e is annealed from to 0.05. The annealing time steps vary among different experiments. For Predator-Prey, we apply 1 million time steps for annealing, following the setup from [37] For the easy and hard maps in SMAC, we apply 50k time steps for annealing, the same as that in [[]] while for the super- surer-hard hard maps in SMAC, we apply million time steps for annealing to obtain more explorations so that more state-action pairs can be visited. About the replay buffer size, we set as 5000 for all algorithms that is the same as that in B5 To fairly evaluate all algorithms, we run each experiment with 5 random seeds. All graphs showing experimental results are plotted with the
1k
"The version that we use in this paper is SC2.4.6.2.6922. rather than the newer SC2.4.10. As reported from the performance is not comparable across versions.
351
'The source code haseline implementation is from
'The code of SQDDPG is implemented based on httpp//s//.tthbbb.o.m//ss//////p
7

---

median and 25%-75% quartile shading. About the interpretability of algorithms, we evaluate the algorithms with both both e-greedy policy (i.e., 0.8) for obtaining mixed optimal and suboptimal actions and greedy policy for obtaining pure optimal actions. The ablation study of SHAQ is shown in Appendix
6.1 Predator-Prey
We firstly rum the experiments on a bartially-observabbl task called Predator-Prey [17] wherein predators that are feasible to be controlled aim capture 8 preys with random policies in 10x 10 grid world. Each agent's s observation is a 5x5 sub-grid centering around it. a prey is captured by coordination of 2 agents, predators will be rewarded by 10. On the other hand, each unsuccessful attempt by only agent will be punished by a negative reward p. In this experiment, we study the behaviors of each algorithm under different values p (that describes different levels of coordination). As 35 reported, only QTRAN and W-QMIX can solve this task, while [37] found that the failure was primarily due to the lack of explorations. As result, we apply the identical epsilon annealing schedule (i.e. million time steps) adopted in (37].
260
5140
ORX ORCOME OTAN MGAAC
CA-ONE
MAGIC
(a) 0=5..
(b) p=-1.
(c) p=-2.
Figure 1: Median return for Predator-Prey with different values of p.
Performance Analysis. As Figure I shows, SHAQ can always solve the tasks with different values
of p. With the epsilon annealing strategy from 577 W-QMIX does not perform as well reported in
35
The reason could be its poor robustness to the increased explorations 335 for this environment
(see the evidential experimental results Appendix C.6). The good performance of VDN validates
our analysis in Section 5 whereas the performance of QTRAN is surprisingly almost invariant to the value of p. The performances of QPLEX and QMIX become obviously worse when p=-2, The failure of MASAC and COMA could be due to that relative overgeneralisatior prevents policy gradient
methods from better coordination
30
2922
235D
0644
122111
3.3150
(a) SHAQ: e-greedy.
(b) SHAQ: greedy.
Figure 2: Visualisation of the evaluation for SHAQ on Predator-Prey: each red square is a controllable agent, whereas each green square indicates a prey. Each agent's factorised Q-value is reported the bubble in blue and the symbols within the squares indicate the action of each agent (i.e., arrows imply the movement direction, "S" implies staying and "C" implies capturing a prey that is valid only when the agent is around prey).
Interpretability SHAQ. To verify that SHAQ possesses the interpretability, we show its credit assignment on Predator- Predator-Prey. As we see from Figure 26 all agents are around and capture a prey, so
Relative overgeneralisation is common game theoretic pathology that the suboptimal actions are preferred when matched with arbitrary actions from the collaborating agents [8).

---

both of them perform the optimal actions and deserve almost the equal optimal credit assignment as 4. 4.2927 and 4.0644, which verifies our theoretical claim. From Figure Zaj can be seen that two agents are far away from preys, so they receive low credits as 2.4709 and 2.8435. On the other hand, the other two agents are around a prey, but they do not perform the optimal action "capture", so they receive less credits than the two agents in Figure 2b Nevertheless, they are around a prey, so they perform better than those agents that are far away from preys and receive comparatively greater credits as 3.2933 and 3. 1159. The coherent credit assignments in both Figure 2a and 26 implies that the assigned credits reflect agents' contributions (verifying (iii) in Proposition I.C., each agent receives the credit that is consistent with its decision.
6.2 StarCraft Multi-Agent Challenge
We next evaluate SHAQ on the more challenging SMAC tasks, the environmental settings of which the same as that in 08. To broadly compare the performance of SHAQ with baselines, we select 4 easy maps: 8m, 3s5z, lc3s5z and 10m_vs_1 3 hard maps: jm__v_6m, 38_vs_5z and 2c_ vss____g:: and super-hard maps: 3s57_ 1157_vs_3$62, Corridor, MMM2 and 6h_ 1__ All training is through online data collection. Due to the limited space, we only show partial results in the main part of paper and leave the rest in Appendix C.T
Performance Analysis. It shows in Figure B that SHAQ outperforms all baselines on all maps, except for 6h_ sz_ On 6h vs_ si_vv__z 8z, SHAQ can beat all baselines except for CW-QMIX VDN performs well on 4 maps but bad on the other maps, which still verifies our analysis in Section 5 QMIX and QPLEX perform well on the most of maps, except for 3s_ vs vs_5z, 2c vs 64zg and 6h vs 8z. As for COMA, MADDPG and MASAC, their poor performances could be due to the weak adaptability to challenging tasks. Although QTRAN can theoretically represent the complete class of the global Q-value [T]. its complicated learning paradigm could impede the convergence to the value function for challenging tasks and therefore result in the poor performance. Although W-QMIX performs well on some maps, owing to lacking law on hyperaarameter tuning B3 all scenarios (see Appendix
it is difficult to be adapted for
SINO
2040
ONLX
100
TimB
(a) 5m_vs__00 vmm_.__m...
(b) 3s_vs_52 5z.
(c) 2c_ vs__4zz
SARO
5140
OPLEX
CMX
V0N
Moee rep ACM0
CRLOME OTTAN
CAIONE
CITAA
MUSAC
MADAC
(d) 3s5s_vs_3aa0 v___r_6...
(c) Corridor.
(f) 6h 87.
Figure 3: Median test win % for hard (a-c), and hard (d-f) maps of SMAC.
Interpretability of SHAQ. To further show the interpretability of SHAQ, we also conduct a test on 3m (i.e. simple task in SMAC). As seen from Figure 4a Agent 3 faces the direction opposite to enemies, meanwhile, the enemies are out of its attacking range. It can be understood as that Agent 3 does not contribute to the team and thus it is almost dummy agent. Its MSQ is 0.84 (around 0) that correctly catch the manner of dummy agent (verifying (i) in Proposition 2). In contrast, Agent I and Agent 2 are attacking enemies, while Agent 1 suffers from more attacks (with lower health) than Agent 2. As result, Agent I contributes more than Agent 2 and therefore its MSQ is greater. which implies that the credits reflect agents' contributions (verifying (iii) in Proposition 2 On the other hand, we can see from Figure 4e that with the optimal policies all agents receive almost identical MSQs (verifying the theoretical results Section The above results well verify the theoretical analysis that we deliver before.
9

---

LAGE
2.479
-0.2001
H20000
SHAQQ e-greedy.
(b) VDN: e-greedy.
(c) QMIX: e-greedy.
(d) QPLEX: e-greedy.
SERGS
ZA2I9
34845
(e) SHAQ: greedy.
(I) VDN: greedy.
(g) QMIX: greedy.
(h) QPLEX: greedy.
Figure 4: Visualisation of the test for SHAQ and baselines on 3m in SMAC: each colored circle is the centered attacking range of a controllable agent (in red), and each agent's 's factorised Q-value is reported on the right. We mark the direction that each agent face by an arrow for clearness.
To justify that the MSQs learned by SHAQ are non-trivial, we also show the results of VDN, QMIX and QPLEX. It is surprising that the Q-values of these baselines also almost identical among agents for the optimal actions (however, the property disappears in more complicated scenarios as shown in Appendix C.3 while the property of SHAQ is still valid). Since VDN is subelass of SHAQ and possesses the same form of loss function for optimal actions, it is reasonable that it obtains the similar results to SHAQ. As for the suboptimal actions, VDN does possess explicit interpretation as SHAQ due to the incorrect definition of 6; (s a.) over suboptimal actions (verifying the statement in Section 5 The values of QMIX and QPLEX are difficult to be explained.
Conclusion
Summary. This paper generalises Shapley value Markov convex game, called Markov Shapley value. Markov Shapley value inherits a number of properties: (i) identifiability of dummy agents; (ii) efficiency; (iii) reflecting the contribution and (iv) symmetry. Based on Property (ii), we derive Shapley-Bellman optimality equation, Shapley-Bellman operator and SHAQ. We prove that solving Shapley-Bellman optimality equation is equivalent solving the Markov core (i.e., no agent has incentives to deviate from the grand coalition). Markov convex game with the grand coalition equivalent global reward game [3] wherein Markov Shapley value plays the role of value factorisation. Since SHAQ is a stochastic approximation of Shapley-Bellmen solve Shapley-Bellin
operator that is proved optimality equation, global reward game with value factorisation becomes valid standing by the cooperative game theoretical framework (i.e. solving Markov core). Property (i) and (iii) in Proposition 2 are demonstrated in the experiments showing the interpretability of SHAQ.
Limitation and Future Work. The value of Markov convex game is not limited to solving problems with the grand coalition, though in this paper we design SHAQ that only focuses on the scenario with the grand coalition. By removing the condition of supermodularity (see Eq this framework can be used study more general coalition games where different coalitions of agents as units may compete/cooperate with each other. Since the grand coalition and Markov Shapley value is not solution in Markov core yet, the learning process becomes more complicated to converge Markov core. A possible research direction in future is to investigate dynamically forming the coalition structure and conducting credit assignments simultaneously.
Acknowledgements
This work is sponsored by the Engineering and Physical Sciences Research Council of UK (EPSRC) under awards EP/S000909//. Tae- Kyun Kim is partly sponsored by KAIA grant (22CTAP-C163799; 02, MOLIT), NST grant (CRC 21011, MSIT), KOCCA grant (R2022020028. MCST) and the Samsung Display corporation. Yuan Zhang is sponsored by the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curia grant agreement No. 953348 (ELO-X).
10

---

References
[1] Tamás Keviezky, Francesco Borrelli, Kingsley Fregene, Datta Godbole, and Gary J Balas. Decentralized receding horizon control and coordination of autonomous vehicle formations. IEEE Transactions on control systems technology, 16(1): 2007.
[2] Arne Schuldt. Multiagent coordination enabling autonomous logistics. Kl-Künstliche Intelligenz, 26(1):91-94, 2012.
[3] Jianhong Wang, Wangkun Xu, Yunjie Gu, Wenbin Song, and Tim Green. Multi-agent reinforce- ment learning for active voltage control on power distribution networks. Advances in Neural Information Processing Systems, 34, 2021.
[4] Sainbayar Sukhbaatar, arthur szlam, and Rob Fergus. Learning multiagent communication with backpropagation. In Advances in Neural Information Processing Systems 29, pages 2244-2252. Curran Associates, Inc., 2016.
[5] Shayegan Omidshafiei, Dong-Ki Kim, Miao Liu, Gerald Tesauro, Matthew Riemer, Christopher Amato, Murray Campbell, and Jonathan P How. Learning to teach in cooperative multiagent reinforcement learning. arXiv preprint
2018
[6] Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning schedule communication in multi-agent reinforcement learning. In International Conference on Learning Representations, 2019.
[7] Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018
[8] Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinícius Flores Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decomposition networks for cooperative multi-agent learning based on team reward. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA/ ACM, 2018.
[9] Tabish Rashid, Mikayel Samvelyan. Christian Schröder de Witt, Gregory Farquhar, Jakob N. Foerster, and Shimon Whiteson. QMIX: monotonic value function factorisation for deep multi- agent reinforcement learning. Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholnsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Muchine Learning Reseurch, pages 2292-430. PMLR, 2018
[10] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Hostallero, and Yung Yi. QTRAN: learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Muchine Learning Research, pages 5887-5896. PMLR, 2019.
[11] Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning implicit credit assignment for multi-agent actor-critic. arXiv preprint arXiv:2007.022: 022529,,..2 2020.
[12] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[13] Jianhong Wang, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. Shapley q-value: local reward approach to solve global reward games. Proceedings of the AAAI Conference on Artificial Intelligence, 34(005):225-7799) Apr 2020.
[14] Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, (6):1-168, 101
11

---

[15] Richard Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Sciences of the United States of America, 38(8):116, 1952.
[16] Richard Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, 2018.
[17] Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Interna- tional Conference on Machine Learning, pages 980-991. PMLR, 2020.
[18) Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nan- tas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: arXiv: 1902.04443 2019.
[19] Lloyd S Shapley. A value for n-person games. Contributions the Theory of Games, 2(28): 307-317, 1953.
[20] Jianhao Wang, Zhizhou Ren, Beining Han, Jianing Ye. and Chongjie Zhang. Towards un- derstanding linear value decomposition cooperative multi-agent q-learning arXiv preprint arXiv:2006.0055 00587, 2020.
[21] Frans A Olichoek. Decentralized pomdps. In Reinforcement Learning, pages 471-503, Springer, 2012.
[22] Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353, 2008.
[23] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.388 1412.3555, 2014.
[24] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
[25] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 132.5562, 2013.
[26] Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI/IAAI, 1998(746-752);2, 1998.
[27] Ryan Lowe, Yi Wu, Aviy Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch, Multi- agent actor-critic for mixed cooperative-competttvee environments. In Advances in Neural Information Processing Systems, pages 6379-6390, 2017.
[28] David H Wolpert and Kagan Tumer. Optimal payoff functions for members of collectives. In Modeling complexity in economic and social systems, pages 355-369. World Scientific, 2002.
[29] Ehud Kalai and Eitan Zemel. Generalized network problems yielding totally balanced games. Operations Research, 30(5):998-1008, 1982.
[30] Xiaotie Deng and Christos Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of operations research, 19(2):257-22) 1994.
[31] Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi. Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3):751-766, 1999.
[32] Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Bench- marking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Joaquin Vanschoren and Sii-Kit Yeung, editors, Proceedings of the Neural Information Processing Sys- tems Track on Datasets and Benchmarks NeurIPS Datasets and Benchmarks 2021, December 2021, virtual, 2021.
[33] Dimitri Bertsekas. Reinforcement learning and optimal control. Athena Scientific, 2019.
12

---

[34] Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi. Secure estimation and control for cyber- physical systems under adversarial attacks. IEEE Transactions on Automatic control, 59(6): 1454-1467, 2014.
[35] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
[36] Shariq lqbal and Fei Sha. Actor-atiention-critic for multi-agent reinforcement learning. In International Conference on Machine Learning, pages 2961-2970. PMLR, 2019.
[37] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint arXiv:2008. 01062, 2020.
[38] Ermo Wei and Sean Luke. Lenient learning in independent-leareer stochastic cooperative games. The Journal of Machine Learning Research, (7(1):2914-2955 2016.
[39] Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. In 2018
AAAI Spring Symposium Series, 2018.
[40] David Ha, Andrew M. Dai, and Quoc V. Le. Hypernetworks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[41] Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint arXiv: 2661, 2014.
[42] Richard H. Byrd, Gillian M. Chin, Jorge Nocedal. and Yuchen Wu. Sample size selection in optimization methods for machine learning. Mathematical Programming, 134(1):127-155,
2012. doi: 10. 10.1007/110107-01--0577
[43] Thomas Hofmamn,, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams. Variance reduced stochastic gradient descent with neighbors. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 28, pages 2305-2315 Curran Associates, Inc., 2015.
[44] Lloyd S Shapley. Cores of convex games. International journal of game theory, 1(1):11-26, 1971.
[45] Harold Garth Dales, H Garth Dales, Pietro Aiena, Jörg Eschmeier, Kjeld Laursen, and George A Willis. Introduction to Banach algebras, operators, and harmonic analysis, volume 57. Cam- bridge University Press, 2003.
[46] Stefan Banach. Sur les opérations dans les ensembles abstraits leur application aux équations intégrales. Fund. math. 3(1):133-181 1922.
[47] Tommi Jaakkola, Michael I Jordan, and Satinder P Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural computation, 6(6):1185-120) 1994.
[48] Francisco S Melo. Convergence of q-learning: A simple proof. Institute Of Systems and Robotics, Tech. Rep, pages 1-4, 2001.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix E.
13

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Appendix
E.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix E.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URLY? [Yes] See supplemen-
tary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 6.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix B.1.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "ZIn7O8u8gi", "reviewer": "Reviewer_Mapg", "summary": "The paper presents a new framework and corresponding algorithm to solve value factorization in global reward games. Specifically, it derives the Shapley-Bellman optimality equation from evaluating the optimal Markov Shapley value and proposes the Shapley-Bellman operator to solve it, which is also proved in the paper. Furthermore, Shapley Q-learning is presented to implement the theoretical framework for predator-prey and SMAC environments. \n\nContributions: The paper proposes a new theoretical cooperative game framework and Shapley Q-learning algorithm for solving global reward games. Moreover, the authors give proof for the theoretical framework and evaluate SHAQ on Predator-Prey and StarCraft tasks, which shows good performance and interpretability. ", "questions": "Authors assume games (Predator-Prey and StarCraft) are satisfied those conditions of MCG in Eq. 1 (line 78), does it always satisfy?", "limitations": "The assumption in line 78 for Markov convex games looks too strong, is it possible to extend the same results to general cooperative games?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1.\twell written, easy to follow\n2.\tnovel cooperative game framework for global reward game justified both theoretically and empirically\n3.\twell literature review on relevant fields\n4.\tproof details and codes provided\n\nWeakness:\n1.\tFigures 1,2,3 are too small to read easily\n2.\tImprovements seem not significant compared to SOTAs\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "66pmL6oOwM5", "reviewer": "Reviewer_XnpC", "summary": "The paper considers multiagent reinforcement learning in a global (cooeprative) reward game. It contrasts the results value factorization frameworks, and proposes an alternative via the Shapley value from cooperative game theory. Basically, the authors consider a form of game with coalition structures, and apply the Shapley value to decompose the reward, and derive and Shapley-Bellman optimiality equation (SBOE) corresponding to the optimal joint determinisitic policy. They propose a Shapley-Bellman opeator (SBO) that solves for the SBOE. These finally give rise to a new multiagent reinforcement learning algorithm, called Shapley Q learning, SHAQ for short,  somewhat akin to existing value factorization methods. \n\nEmpirically, on a few settings (predator-prey and starcraft)  SHAQ exhibits better performance than existing approaches, and also provides some interpertability foundation. ", "questions": "What happens in domains which are not completely cooperative (team reward), such as social dillemas or mixed motive games. Does the algorithm still runs? Does it fail? What happens when agents are trained using a mixture of algorithms (SHAQ agent with other approaches - are they compatible). Can you replace the Shapley value with other cooperative solution concepts (the Banzhaf index seems to be the closest, basically your equation just with different weights for the subteams) - does the whole method fail? ", "limitations": "As I wrote, the empirical analysis is somewhat limited (but certainly a decent foundation). Also the writing could be improved - at the very least I'd give the formal definitions of a transferable utility cooperative game, coalition structures, the core (as applied to a general CS or characteristic function game). The paper does a better job on the RL side (where things are fully defined). Also, you should have the discussion on what happens in non team reward (non fully cooperative) settings. \n\nAll in all, a very interesting paper, if only for the nice connection between RL and cooperative game theory. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The key strength of the paper is in applying cooperative game theory tools to multiagent Q learning. Recently the Shapley value has become a very popular tool in machine learning due to its ability to decompose the performance of a model to the relative influence of specific features. This has proven a very strong tool for analyzing supervised learning models. The authors propose now propose to use this theoretic foundation to multiagent reinforcement learning. \n\nThe key weakness in my opion is not having a clear, crisp takeaway from this work. If the main claim is the superior performanc on multiagent reinforcement learning, then the empirical analysis seems to be somewhat lacking, as it covers relatively few domains (there are now enough multiagent gyms that allow a wider variability of tasks). If the main claim is a theoretical foundation, then one might expect a tighter analysis and bounds as compared to existing approaches. \n\nEither way, I think the writing is very formal, and could be imporved. What is the main driving intuition here? MARL is typically considered through a non-cooperative game theory prism (Markov Game). Here you are trying to use cooperative game theory, which means you consider subsets of agents, and have some function mapping each such subteam to its success in the task. Then, one might view the Shapley value as a decomposition allocating each single agent its individual reward / impact in the team's success. But why use the Shapley value rather than other solution concepts (such as the Core, which you mention, or the least-core), or the Nucleolous, or the Kernel, or other similar power indices such as the Banzhaf index? Are you using some of the axiomatic foundations to the Shapley value? If so, then where? \n\nAll in all, I really love the topic of the paper, but the execution could be improved (more domains for empirical evaluation, tighter theoretic bounds versus baselines). And the writing should focus on the intuitions before jumping to the technical definitions ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2r43uM1dI-w", "reviewer": "Reviewer_Bq8r", "summary": "This paper presents a theoretical framework that studies Shapley value in the context of Markov Games as a useful technique for value factorization and credit assignment in agents coalitions. Leveraging this framework, the authors proposed Shapley Q-Learning (SHAQ) derived from a novel definition of a Shapley-Bellman Operator. The proposed algorithm is compared with a suite of existing algorithms (COMA, VDN, QMIX) in predator-prey and the StarCraft MA Challenge, contrasting competitive results while showing interesting properties of interpretability.", "questions": "1. Would the authors be able to reproduce the interpretability results offer for SMAC on the simple predator-pray setting?", "limitations": "The authors addressed the limitation of the work, including the assumptions and restrictions imposed in the scenarios considered. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The paper is well-written and properly motivated. The work is well-placed among the existing and vast literature in Multiagent Reinforcement Learning (MARL).\n\n2. The combination of Shapley's theory with Q-Learning seems a novel contribution in the interesting and always challenging setting of MARL.\n\n**Weaknesses**\n1. The experimental section would benefit from a discussion on the interpretability of SHAQ in the predator-prey setting, which seems to be missing in the current manuscript.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept