Information Design in Multi-Agent Reinforcement Learning
Authors: Yue Lin
Wenhao Li
Hongyuan Zha
Baoxiang Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-agent reinforcement learning
multi-agent communication
information design
signaling gradient
obedience constraints
TL;DR: We investigates how an RL agent could influence other learning agents by providing information in mixed-motive settings.

Abstract: Reinforcement learning (RL) is inspired by the way human infants and animals learn from the environment. The setting is somewhat idealized because, in actual tasks, other agents in the environment have their own goals and behave adaptively to the ego agent. To thrive in those environments, the agent needs to influence other agents so their actions become more helpful and less harmful. Research in computational economics distills two ways to influence others directly: by providing tangible goods (mechanism design) and by providing information (information design). This work investigates information design problems for a group of RL agents. The main challenges are two-fold. One is the information provided will immediately affect the transition of the agent trajectories, which introduces additional non-stationarity. The other is the information can be ignored, so the sender must provide information that the receiver is willing to respect. We formulate the Markov signaling game, and develop the notions of signaling gradient and the extended obedience constraints that address these challenges. Our algorithm is efficient on various mixed-motive tasks and provides further insights into computational economics. Our code is publicly available at https://github.com/YueLin301/InformationDesignMARL.

Information Design in Multi-Agent Reinforcement Learning
Yue Lin, Wenhao Li, Hongyuan Zha, Baoxiang Wang"
The Chinese University of Hong Kong, Shenzhen 1inyue3h10gmaill com, (liwenhao, zhaby, exiangvang)@cule edu. cn
Abstract
Reinforcement learning (RL) is inspired by the way human infants and animals learn from environment. The setting somewhat idealized because, in actual tasks, other agents in the environment have their goals and behave adaptively to the ego agent. To thrive in those environments, the agent needs to influence other agents their actions become more helpful and less harmful. Research in computational economics distills two ways to influence others directly: by providing tangible goods (mechanism design) and by providing information (in- formation design). This work investigates information design problems for a group of RL agents. The main challenges are two-fold. One is the information provided will immediately affect the transition of the agent trajectories, which introduces additional non-stationarity. The other is the information can be ig- nored, so the sender must provide information that the receiver is willing to re- spect. We formulate the Markov signaling game, and develop the notions signaling gradient and the extended obedience constraints that address these chal- lenges. Our algorithm is efficient various further insights into computational economics. Our code is publicly available at https: http:///wwcoaaaaaooooooooooottta
tasks and provides
Introduction
Reinforcement learning (RL) studies how a world-agnostic agent makes sequential decisions to maximize utility. It gains increasing popularity and achieves milestone progress in Atari [46 22).
Go [48) Poker [8] 19.9 39), video games 2 []. and bioinformatics (26), economics (59), etc. The
canonical RL formulation requires the environment to stationary, meaning that other agents could not respond to the ego agent's policy by adapting their policies [50]. The assumption does not hold in real applications. Instead, the ego agent, in general, cannot dictate other agents and needs to influence others their adaptation becomes more helpful and less harmful.
substantial subarea RL, multi-agent reinforcement learning (MARL), investigates the interaction and influence among multiple RL agents when they are placed in shared environment. It has obtained promising results thanks to the generality and diversity of its settings. Examples are pure cooperative games and pure competitive games. The pure cooperative setting studies agents that work on a consentaneous goal. this case, influencing other agents relatively straightforward. The pure competitive setting studies zero-sum games. In this case, influencing other agents is less likely to be practical or even impossible for two-player games. between these two extreme cases arises the large, more realistic but less charted area of mixed-motive MARL, where influencing other learning agents becomes a main challenge 31 37 30
"Corresponding Baoxiang Wang
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Studies in computational economics have distilled different ways of directly influencing rational, self-interested agent into two types: by providing tangible goods (mechanism design) and by providing information (information design) [52 L5| For the former type, tangible goods align perfectly with RI. rewards because rewards are natural and utilitarian. Several works RI. design algorithms for the ego agent to use the reward to incentivize other agents [57 58
59 29]. For the latter type, the
ego agent must possess information that is helpful to the other agent while not observed by the other agent. The ego agent then sends a message that partially reveals this information in the hope that the other agents respect the message and act in a way that benefits the ego agent. The key observation in information design is that the message needs to be respected, which indicates that the message, apart from benefiting the ego agent, must also benefit the receiving agent.
Two difficulties persist in modeling and solving information design with reinforcement learning. The first challenge is the issue of non-stationarity. The receiver's environment changes as the sender's signaling scheme is updated. If the sender uses policy gradient, it does not consider how modifications to its scheme affect the receiver's learning [7]. On top of this, the signal impacts not only the updating phase but also the sampling phase. In fact, the receiver uses the signals from the sender as part of its input. The signaling scheme will, therefore, directly affect the trajectory generation. This means that specific techniques in mechanism design, such as hyper-gradient, are unsuitable, and new methods need to be formulated [57].
The second challenge lies in how the message can potentially be respected by the receiver. The most general signal space is the set of all state subsets and is exponentially large. An analysis analogous to the revelation principle proves that there is an optimal signaling scheme that uses signal space of the same size as the action space of the receiver, which leads to the classic obedience constraints and the linear program formulation of information design 18 40). However, under the revelation principle, a signal suggests an exact action, which means the receiver will be dictated by the sender if it respects the message. When both parties are reinforcement learning agents, such want of dictatorship does not build trust and respect between them and instead inevitably drives them to the equilibrium where all signals are ignored. Counter-intuitively we find that the revelation principle can be removed under the learning context, and one will need to resort to more persuasive signaling schemes and the corresponding update methods.
This paper investigates how an informative ego sender could learn to influence a self-interested receiver with its informational advantage. We propose Markov signaling game for mixed-motive communication, where in each timestep, the sender encodes and sends a message to the receiver. After the signaling step, the receiver will act based on the message and its observation. We derive the signaling gradient to learn the signaling scheme that addresses the non-stationarity problem. This gradient considers the additional gradient chain from the receiver's policy and is proved to be an unbiased gradient estimation. It agrees with our intuition that the influence of the sender on the behavior of the receiver should be reflected in the gradient term. Based on the signaling gradient, we design the extended obedience constraints for incentive compatibility of the signaling scheme We further provide challenge because it is suitable for learning algorithms while preserving the optimum of the ego agent. Information design in MARL is then end-to-end differentiable and learnable with our algorithm.
approximation of the gradient of such constraints, which solves the second
Numerical experiments on Recommendatior Letter and Reaching Goals demonstrate the effi cacy of our approach. Extended discussions are provided for the method and the empirical results.
2 Preliminaries and Related Works
For information design, the core insight is to send messages to change the posterior beliefs of the receiver, which persuades take actions that benefit the sender 552 [5]. The canonical formulation considers a task that sender wants to persuade a myopic receiver for one step (28). The sender and the receiver share a prior distribution P(s) over the state s, which affects both the payoffs of the sender r'(s a) and the receiver r (s, a) (some recent work lifts this assumption 60). The sender needs to honestly commit its signaling scheme, which a policy that determines the distribution of signals, to the receiver before the interaction. This is referred to as the commitment assumption.
Information Design
A mechanism is said to be incentive compatible if every participant's 's optimal strategy, given the strategies of others and the mechanism's 's rules, leads to outcome that is desired by the mechanism designer.

---

The flow of the persuasion process is as follows: (1) The sender commits signaling scheme to the receiver; (2) The environment generates state s. The sender observes the state and then samples message according to the distribution of the committed signaling scheme; and (3) The receiver receives the message, and then calculates a posterior and chooses an optimal action for itself. Given the current state and the receiver's chosen action, the sender and the receiver get rewards from the environment.
Based on an analysis similar to the revelation principle 28 19 there is an optimal signaling scheme that does not require more signals than the number of actions available the receiver. Thus is without loss of generality for the sender to recommend an action directly to the receiver rather than sending message. From the self-interested receiver's perspective, as long as it believes that the recommended actions are optimal in its posterior belief, it will follow the sender's advice. This kind of constraints of the sender's signaling scheme is called obedience constraints. When such constraints are satisfied, the signaling scheme will be incentive compatible, meaning that the receiver will follow the sender's 's advice. In this way, the process of information design can modeled as a constrained optimization problem
max Eppl w (s s.t. P(ss) ()) (s,a) (s, 0, Va, d',
(I)
where w' (s, a) and w (s, a) are the utility functions of the sender and the receiver respectively, (p(a| s) the sender's signaling scheme, and the problem is formulated as a linear program.
Information design is applicable to a vast array of real-world scenarios, including voter coalition formation (1]. law enforcement deployment (21], price discrimination (4), etc. See [27 for summary.
Learning to Communicate Communication learning is significant subarea of MARL. Existing research primarily focus on fully cooperative settings [6 49 Among the proposed methods in MARL with communication, DIAL [6) is the closest work to ours. It highlights the importance of the receiver's s feedback to the sender, where the receiver updates its critic network and passes the gradient back to the sender's network. This also implies that the sender is assisting the receiver in evaluating the environment. The altruistic design of the sender is appropriate in fully cooperative scenarios, but might not extend to mixed-motive scenarios.
MARL communication under -oxxive settings was attempted in [25]. The work uses social influence, which is defined via the Kullback-Leibe divergence of the receiver's 's policy update, to measure how persuasive is the sender's message. is a pioneer attempt and demonstrates efficacy in several contexts, but the authors observed that "The listener agent is not compelled to listen to any given speaker. Listeners selectively listen to a speaker only when it is beneficial, and influence cannot occur all the time." This describes lack of the obedience constraints, and motivates to propose algorithms that are more effective and more general.
Related works mechanism design, sequential information design, and emergent communication are deferred to Appendix A
3 Markoy Signaling Games
Consider signaling game involving a sender and receiver. The sender i is assumed to have access to the global state E S, while the receiver j makes decisions based only on its local observation E O and received message E Σ from i. At each timestep I, the observation the emission function q S + O, where the information in og is a proper subset of the information in s, We overload the notation and write o, C st. The receiver's observation at cach timestep is common knowledge between the sender and receiver. The sender's informational advantage over the receiver at each timestep is reflected by s; o,, By the sender's informational advantage of the problem setting, assume that {st of he affects j payoff. This ensures that the sender has information that the receiver wants know but does not know.
E O is sampled by
The sender maintains a stochastic signaling scheme y by 7 and ((X) denotes the set of all random variables on X. The receiver's stochastic action policy denoted as up O x Σ - A(A), where is the receiver's action space and E the policy parameter. Without loss of generality, assume that the sender takes environmental action. The state
O + A(E), where y parameterized
3

---

transition function p: S x A - A(S) and the reward functions R S - A A are dependent on j's chosen action and are not dependent on i's message. In this way, i needs to influence j through its signaling scheme, which indirectly affects its long-term payoff expectation.
Then, Markov signaling game (MSG, Figure T is defined as tuple
g = (i.j. S, A, R.P.))
At each timestep in G. i observes a state 8, E S and j's observation of E is sampled by q. and then sends message de based on (py- Then j takes action a, E A based its policy Ty and the environment transits to the next state s' E S according to the transition function Meanwhile, player i (respectively, j) receives the reward r (r²) via the reward function Rt (R)). The agents and the environment repeat this process until the environment terminates the episode.
{(0[a)
To l σ)
p(s' (s,a)
8:
ae
81+1
())
Figure 1: Illustration of the Markov signaling game. The arrows symbolize probability distributions, whereas the nodes denote the sampled variables.
The value functions in MSGs are similar the value functions in Markov decision processes (MDPs). The sender's 's state value function Vi (s) = Ex,' [G] 8t s] defines the expected return of the sender at state, where Gj denotes the same expectation but under an additional condition of sending signal a at the state s, as Q (s) Ex,x Gt s o, = o.. The action value function U is the same expectation that conditions on all variables 8t, de, ae, as U (s,
E==t " " R++ The signal value function Q for player i
(s. o, a) E,,x [G; 8t s, dt O, a, = a] Notice
(s,or,
the transition function and the reward functions are not dependent a. We then define the marginal action value function W p,x (s, a) = E.p,* [G; 8: = 8, a, = al U (s. a, a). The receiver's value functions are similarly defined, by replacing G; with Gy
Assume that the agents involved are self-interested. i.c.. they are focusing solely on optimizing their own payoffs. However, their payoff's are general and are not necessarily the environmental rewards. For instance, the sender may replace its reward function R with (R' R²) its optimization goal, which would result in it "selfishly" optimizing for the social welfare.
MSG is new to the community and the features of MSG quite distinctive: (1) The sender and receiver are heterogeneous, with the sender having an informational advantage; (2) Their interests may differ and thus they are in a mixed-motive scenario; (3) The sender "signal does not influence anyone's ' reward. Thus the sender can only influence the receiver's belief to improve its own expected payoffs; (4) The receiver can take actions to directly determine the payoffs for both parties, but lacks sufficient information to estimate the current state and needs to obtain information from the sender.
There are several extensions of the MSGs. For example, (1) One may allow the sender take environmental actions; (2) The sender may only have partial observation of the state; (3) There could be multiple senders and receivers. Discussions these extensions deferred to Appendix B
4 Method
The fundamental concept of information design is the sender optimizing its payoff's while adhering to the obedience constraints, referenced in Equation (T.. However, persuasion becomes more challenging in sequential and learning scenarios, due to the non-stationarity and the existence of the trivial equilibrium where all messages arbitrary and are ignored.
The first obstacle non-stationarity, a recognized issue in MARL, that is especially problematic in communication since it requires bi-level optimization. During the early stages of training, the sender's signaling scheme is mostly random and provides little information, which can quickly break the trust between mixed-monl motive agents and lead to the trivial equilibrium. The second difficulty is the want

---

of dictatorship. In the original obedience constraints, the receiver's policy is set to be deterministic by the revelation principle. means that recommending& wrong action is non-forgiving, and thus suitable for trial-and-error algorithm. This will also lead to the trivial equilibrium. In this section, we present how these challenges are addressed and how information design is learned.
4.1 Signaling Gradient
The proposed signaling gradient is utilized to compute the gradient of the sender's long- long-term expected payoff w.r.t its signaling scheme parameters. When caleulating this gradient, it explicitly takes into account the chain of the receiver's 's policy. This helps alleviate the non-stationarity between agents.
In MSGs, the signaling scheme affects the distribution of signals, indirectly impacting the receiver's action, which then determines the payoffs for all agents. Specifically, the sender's expected payoff is expanded as p. [V V. [s)] Σ (s) g(0 (i,(ar 88, 8, To(a (, U a (8, a, a),
where d is the state visitation frequency given yr, and Similar to the case of the policy gradient (PG), the relationship between state visitation frequency and и cannot be explicitly written. The introduction of communication yp further complicates this process it involves deriving V,,dp,. (s).
We utilized a method similar to the policy gradient to derive the gradient V,,Bg,. [V oo (s)] and obtain an unbiased gradient estimation. We call this estimation the signaling gradient. The proof of the lemma is deferred to Appendix [D]
Lemma 4.1. Given a signaling scheme fn of the sender and action policy no of the receiver in an MSG G, the gradient of the sender's 's value function Va (3) w.r.t. the signaling parameter nj is
v. x Exp,T (w, [V,,og Tola 10,0) + V,, log 90,(0r s, s,o)]]
(2)
worth noting that E [W (8, VV log (a o, a)] * 0 and W 2,, (s, a) takes an action as an input. As a consequence of this derivation, the sender's 's updated term inc the receiver's s policy and action. This result aligns with intuition, as this additional term reflects the sender's consideration of its impact on the receiver.
One may naturally regard the signal an action and directly apply the policy gradient. If so, one will obtain Ep. 12..r (s. d)- V,, log (ay(ar s)]. This gradient will then be independent of the receiver's action and therefore biased.
Connections to Other MARL Methods There are three perspectives to gain insights from the derivation of the signaling gradient. The first perspective is that the signaling gradient can be regarded as palicy-based feedback from the receiver instead of value-based feedback in DIAL [6]. The second
perspective is that the signaling gradient and LOLA 17 similar in alleviating the non-stationarity in MARL communication. (More discussions are deferred to Appendix H.4) Since MSGs consider the coupling decision-making processes of both parties, the signaling gradient involves the sender taking the initiative to consider how to influence the receiver. In contrast, LOLA involves an agent proactively adapting to other people's updates. The third perspective is that the signaling gradient can be seen as a first-order gradient that is absent in LIO [57]. This new gradient chain can be explicitly derived because the signaling scheme directly affects the receiver's sampling phase.
4.2 Policy Gradient for the Receiver
From the receiver's perspective, the decision process can be modeled as partially observ- able MDP (POMDP), in which its observation is O x Σ in the corresponding MSG. There- fore, the receiver can optimize its payoff expectation Vi p.x (0, by calculating the gradient Ep.. [Af_r (o,oo,,0 a) V log (a(a o,a)]. where A(o, a) = Q(o, a. a) V(,, σ) is the advan- tage function [5T). Compared to the receiver in Bayesian persuasion ( (28), see Section 4.3.J for more details), the policy of the receiver in MSGs is now stochastic rather than deterministic, which allows a larger capacity in taking different actions and a larger capacity in decoding the received information.
4.3 Extended Obedience Constraints
In the learning algorithm context, we consider the sender's informational advantage on the current state s and investigate the incentive compatibility of the receiver. As an analogous of (T). the prior
5

---

of such information is then the occupancy measure (s) of the state condition on the current signaling scheme and action policy. The payoff function w (s, a) corresponds to the action value function W (s, a) in Markov signaling games.
amounts to deciding the signal space E. The revelation principle states that there is an optimal signaling scheme that does not require signals than the number of actions available to the receiver. If one follows the revelation principle, one would reasonably use Σ = A, resulting in the following obedience constraints.
de,r(s)) Pay(a 8). (s, a) - (x, d') 2 O, Va, E A.
(3)
These constraints are technically correct. However, in the learning context, having only |-|] possible signals means that the receiver either completely follows the suggested action or completely ignores the message. The former happens only if the obedience constraints are satisfied. sequential interactions, the constraints will, of course, be violated occasionally. However, the dictatorship nature of the signaling scheme fails to sway the receiver without consistent satisfaction with the constraints.
Moreover, consider the trivial equilibrium between the sender and the receiver: The sender does reveal useful information, and the receiver ignores the message. could escape from the equilibrium alone. This means it is likely to fail once the learning algorithm converges to the trivial equilibrium. One natural choice is to send the information to the receiver instead of dictating actions. In this way, the receiver, as a learning agent, is more likely to be able to utilize the information and more likely to respect the message.
this point, neither side
Therefore, we extend the obedience constraints to general, continuous signal space Σ that describes the state. A common choice is Σ = S. The following lemma asserts that the extended obedience constraints impose the same optimum as with the obedience constraints.
Lemma 4.2. Given a receiver's observation o, the extended obedience constraints the same optimum as the obedience constraints 3
MSGs yield
Ede,(()) Gn 18,0)
8) Σ
To(a 0, - =o(alo, . (s, 20,
(4)
for all a, o' E.
The lemma assumes the sender can access the receiver's policy and observation. Otherwise, the sender may use inferring methods to maintain an estimation that (an example is (35)). This lemma is proved using the same argument in (3. For convenience, in later sections, the left-hand side of denoted as Ca,aa
4.4 Learning Markov Signaling Games
Given a joint policy म, the self-interested sender attempts to optimize its payoff' expectation in an MSG while satisfying the extended obedience constraints. This optimization problem
max B.p.7 [Vr, (8)] Cola,o') 2 O, Va,a'.
(5)
7
Since we are employing a learning-based approach, it is necessary to calculate the gradient (', In this way, our method is model-free and does not require the prior knowledge of Ps)) (the occupancy measure (s)). Unfortunately, when calculating the gradient of the extended obedience constraints, the technique used in the signaling gradient cannot be applied to reveal the dependency of dip.r on sp Instead, the gradient estimated using the biased sampling method as below.
1 V V,CC,o,,0') =
Σ 7LET
Σ (To(a) o0, -To(a oe,) W (s,. Vn s oi)
(6) where t is a sampled trajectory with timesteps, and o' randomly sampled, instead of being sampled from the signaling scheme. Despite that or is from the data that is generated from y2, the purpose of having these a, a' to find the violation of the Va, o' constraints. Therefore in extended obedience constraints V aa o, 0. which is different from the signaling gradient.

---

There are various methods available to solve the constrained optimization problem iteratively, e.g.. the Lagrangian method. the dual gradient descent method (DGD) 77. We tested both methods the experiments and we found that the Lagrangian method has better performance. See Appendix HH.5 for the details. Taking the Lagrangian method as an example, The update of the signaling scheme parameters (b)) for the k-th iteration
1(++1) + (b) + Byp (s)] + Σ>O V,
0,0"
where o denotes the non-negative Lagrangian multipliers (predefined as hyperparameters), and ()) = min
4.5 Discussions on Method
4.5.1 Lift to the Commitment Assumption
The most controversial but reasonable assumption information design the commitment assump- tion. In Bayesian persuasion (one-to-one persuasion) [28). the sender will commit to signaling scheme first. The sender determines its signaling scheme before the games start and honestly tells to the receiver. A justification of the commitment assumption is that, in repeated game where long-term sender interacts with a sequence of short-term receivers, the commitment will naturally emerge in equilibria. This is due to the sender's need to establish its reputation for credibility, which is essential for optimizing its long-term payoff expectations [45]
However, the reputation system between the receivers still needs to be well-defined, so the receivers that have previously interacted cannot convey information about the sender the receivers that will interact later. Without reputation system, the sender can optimize its payoff by claiming respectful signaling scheme while taking an exploitable one. Instead, RL allows for organic and repeated interactions between senders and receivers in given environment, more closely resembling real-world scenarios. This unique feature enables the learning framework to capture policy evolution and better replicate phenomena in human society.
4.5.2 Lift to the Revelation Principle
The extended obedience constraints remove the revelation principle analysis from the obedience constraints, thereby reverting the sender's behavior from "action recommending" to "signal sending". In this way, the sender's set of signals becomes redundant. The redundancy renders the signaling scheme more general and amenable to learning-based approaches. Previously, the signaling scheme required one-to-one mapping recommend a particular action, where recommending an undesired action can be non-forgiving. With the introduction of redundancy, the sender can now learn many- to-one mappings refer the wanted action distribution, which is a more lenient way for cial-and-erros method. This redundancy is similar to other areas of learning algorithms. For example, one could increase the size the neural network beyond the information theory necessity to better encode and represent the mapping.
4.5.3 Far-sighted Receiver
The nature of RI. determines that the receiver in MSGs is considering the cumulative reward. This lifts the commitment assumption and evolves the trustworthiness of the sender's ' signaling scheme. But meanwhile, the cumulative reward formulates that the receiver must be far-sighted, which is different from the common assumption of a myopic receiver in information design. fact, fightee receiver is inevitable once we lift the commitment assumption.
far sightdd receiver is, in general, regarded hard in the literature. Gan al. [8] prove that information design with fir-sighted receiver is NP-hard, One could intuitively see this from the Recommendation Letter example (See Appendix F.. The HR can deliberately choose not to hire any students, even when the signaling scheme satisfies the obedience constraints, hoping to force the professor be more honest (i.e., reveal more information) in the future. The optimality of the receiver's 's policy is undefined in this setting.
7

---

One way to empirically prevent this is to set an additional constraint Jo CG((T, o') 2 apart from the obedience constraints Cy o') in Equation (5), where c > O. A more substantial improvement in reward will incentivize the receiver to establish trust in the long run.
4.5.4 Hyper Gradient
Our approach shares similarities with LIO (discussed in Appendix A as both methods allow agents to alter their parameters to indirectly enhance their payoff expectations by influencing others. their cases, agents achieve influence by offering rewards to others. The main difference between rewarding and signaling is that the former solely impacts others' policy updates (as the gained rewards are used exclusively for updating). In contrast, the latter additionally affects the sample generation.
In methods incentivize others, the gradients the receiver's one-step policy update w.r.t. the sender's rewarding network parameters are required to capture the sender's influence on the receiver. This kind of gradient is second-order and can be viewed as hyper-gradient
Unlike incentive- based interventions, in communication methods, the sender's outputs are the inputs of the receiver's actor. The sender can achieve influence while generating trajectories. Hence, our primary focus is on studying the first-order gradient of the receiver's policy w.r.. the sender's 's signaling parameters, i.e., VT o, o). The second-order gradients can also be computed, as shown in Equation (I in the appendix. The effect of the hyper gradient is left for future work.
4.5.5 Sender's Access to Receiver
In signaling gradient, the updating of the sender's signaling scheme needs to backpropagate through the receiver's policy during training. Accessing the opponent in mixed-motive settings might sound counterintuitive glance, but this setting actually reasonable and technically feasible.
In MARL algorithms, the Centralized Training with Decentralized Execution (CTDE) framework is commonly used (35). This means that in the simulated environment, data is centralized and accessible during training, which allows us to use all the required quantities. Once the training is completed, the agent no longer has access to other agents.
From the information design perspective, we may consider the receiver as "dummy" learning agent that is auxiliary in centralized training. Once a sender agent is trained, it finds the (coarse correlated) equilibrium that is no longer connected specific receivers. The sender is supposed to persuade any rational, self-interested agents in subsequent interactions with them.
Technically, in communication methods, it is common for gradients pass through other agents during training. We adopted the commonly used Gumbel-Softmax technique in the field of emergent communication research allow for end-to-end differentiation, which is used to retain the gradients of sampled signals [24] 20
Experiments
The method proposed in this paper is validated in Recommendation Letter and Reaching Goals. The receiver's action policy is implemented by the advantage actor-critic (A2C) (38). Each curve in the experimental result graphs is drawn with least 15 random seeds. All the seeds are included in the results (including those failed ones). Running 4 seeds with 2 NVIDIA GeForce RTX 3090, the longest time is Reaching Goals with 5 map, which takes up day.
Our designed algorithm takes the perspective of a self-interested sender. Therefore, the measure of success for our algorithm primarily depends on the sender's reward r². However, we also present the curve of y yd (social welfare) in an attempt to demonstrate that even when the sender is self-interested and the signaling scheme is somewhat deceptive, it does not harm social welfare, and it might even enhance social welfare in some scenarios.
5.1 Recommendation Letter
In this task, professor will write recommendation letters for number of graduating students, and a company's human resources department (HR) will receive the letters and decide whether to hire the students.
Recommendation Letter is classic example in information design 15 28

---

The professor and the HR share a prior distribution of the candidates' quality, with a probability of 1/3 that the candidate is strong and a probability of 2/3 that the candidate weak. The HR does not know exactly what each student's quality is but wants to hire strong students, while the letters are the only source of information. The HR will get reward of 1 for hiring a strong candidate, a penalty of -1 for hiring weak candidate, and a reward of O for not hiring. The professor gets a 1 reward for each hire. In this section, we focus on analyzing the experimental results, while a classic analysis of the three situations is presented in Appendix FF
In the experiments, we primarily compared the performance of policy gradient class algorithms (PG), PG class algorithms with obedience constraints (PGOC), DIAL [16]. signaling gradient (SG, our ablation), and signaling gradient with obedience constraints (SGOC, our proposed method) in learning a signaling scheme. More specifically, the PG class algorithm utilized in experiments refers to A2C. Furthermore, SG also employed A2C techniques, including the use of the actor-critic framework, target critic, and advantage function (adapted to W*(s, a.) (*()) in MSGs). The algorithms with obedience constraints are also required to maintain an extra critic for estimating W (s, a). We let
SPy (a 8, Pn(o 8) and Σ {0, 1}. The performance comparisons are shown in Figure (a-c).
SGOC
SG
PG Reward
PGOC
DIAL
Reward
Reward
Reward
400
0.3
0.5
0.2
0.5
200
04
04
-200
0
-000
0
0
2
0
2
0
2
Stop
Lew
Step
1e8
Stop
leh
Egisode
les
(a) yr
(b) yd
(c) rr + تو
(d) r in 5 x map
Reward
Reward
Reward 400
Reward
400
200
200
0
200
-200
.200
-200
400
-400
-400
-400
0
2
4
6
8
10
0
2
4
6
8
10
0
2
4 6
10 le4
2
Episode
1e4
Egisode
16f
Episode
Episode
165
(e) of in 3 x 3 map
(f) r2 in 3 3 map
(g) r' + rd in x 3 map
(h) r + p in 5 x map
Figure 2: Comparisons of the performance. (a-c) The results of Recommendation Letter. (d-h) The results of Reaching Goals. The rewards and penalties are amplified by 20 and 5 (12 and 3.5) respectively in 3 x 3 (5 x 5) map.
The experiment results show that the three examples (two equilibria plus the honest signaling scheme) introduced in Section]] | have emerged. The algorithms with obedience constraints (PGOC and SGOC) reach the third equilibrium (the best for the sender), DIAL reaches the second example (the best for the receiver), and PG and SG reach the first equilibrium (the worst for both parties). Given that the Recommendation Letter task is not a problem with interdependent states, it is justifiable to expect that the performance of PGOC and SGOC (PG and SG) would be similar.
5.2 Reaching Goals
To reffect the inconsistency of the interests and the information asymmetry, we evaluate the methods in the Reaching Goals task. In this challenging task, the sender and receiver have different goals: the sender wants the red apple, while the receiver wants the green apple. At any given time, there is one of each type of apple on the map. Only the receiver is able to move around reach apples in the grid-world map. The conflict of interest arises because these two types of apples are independently generated random, and their locations are typically not the same. The receiver will not get reward for reaching the red apple, but it does not know where the green apple is. The sender, on the other hand, knows the location of both types of apples, but can only get a reward when the receiver reaches the red apple. The sender can only indirectly optimize its payoff by sending messages to influence the receiver's actions. Moreover, this conflict can be exacerbated by designing distance penalties. After each timestep, both agents will get penalty based on the distance between the receiver and its desired goal. And we set fixed horizon of 50 for each episode in this scenario. Example maps of Reaching Goals are shown in Figure 6
9

---

To evaluate the efficacy of SGOC, we conducted experiments on mäps of 3 x 3 and 5 x 5, and the results are presented in Figure 2 Let the signal space Σ S', where S' one channel out of three channels (the locations of two apples and the receiver's position) of the image. The receiver can only see its position. The experiments of having larger of are included in Appendix H..7 The smaller the o², the greater the sender's persuasion ability. From the empirical results, the signaling gradient is shown to be an essential factor in sequential communication scenarios.
5.3 Discussions on Experiments
5.3.1 Symmetricity of the Signaling Schemes
An interesting phenomenon is observed in the Recommendation Letter experiments: training with different random seeds may result in different pairs of encoders and decoders. In other words, the professor may signal to indicate a strong student (or recommend this student) in some seeds, while in others, this is signaled by O. However, regardless understand the semantics of the signals (reflected in the evolution of the receiver's ' policy). Based on the outcomes, the seeds are divided into two parts (A seeds and B seeds).
which case it is, the paired HR can always
This phenomenon is reasonable since we do not make any prior assumption about signaling semantics. The symmetric results of Recommendation Letter experiments are shown in Figure
A Seeds
B Seeds
Prob.
Prob.
Prob.
Prob.
0
2
3
3
Step
Les
Step
1c8
Step
Le8
Stop
(a) (11 "W"))
(b) (p(1 "S"")
(c) π ("HH"
(d) n: ("H")
[1)
Figure 3: The signaling schemes and the action policy by SGOC, (a) The prob. of signaling 1 for Weak students. (b) The prob. of signaling 1 for Strong students. (c) The prob. of choosing to Hire
when signaled O. (d) The prob. choosing to Hire when signaled
5.3.2 Honesty the Sender
As discussed Section 4.3.3] the obedience constraints can be associated with additional constraint Smaw C2(O, o' d')dodo'
is set to improve the credibility of signaling schemes in practical situations and cope with the RL capacity of the receiver. Define the honesty metric as [5p(1 "S") - =p(1 "W""]. The experiments show that the larger the e and the Lagrangian X, the more honest the signaling scheme will be, as shown in Figure in the appendix.
The hyperparameter
6 Conclusion
We investigate information design, substantial and open area, for MARL that discusses mixed- motive communication. Technically, we propose the Markov signaling games to describe the problem and provide its characterizations. We then prove the signaling gradient lemma, which gives an unbiased way to estimate the gradient and update the sender's signaling network. To learn the incentive compatibility of the signaling scheme, we propose extended obedience constraints. The new constraints are more suitable for learning algorithms and practically promote mutually beneficial signaling schemes. The commitment assumption and the revelation principle are lifted by investigating information design with MARL. Experiments and extended discussions are presented to demonstrate the efficacy of our framework and algorithm.
10

---

Acknowledgments
We extend our heartfelt gratitude to Cynthia Huang, Zongqing Lu, Shuai Li, Pascal Poupart, Dan Qiao, Han Wang, Zichuan Wan, Jiachen Yang, Zewu Zheng, Shuhui Zhu for their enlightening discussions, Part of the implementation regarding the signaling gradient was developed by Zewu Zheng.
The authors are partially supported by National Natural Science Foundation of China (62106213, 72150002), Postdoctoral Science Foundation of China (2022M723039), Shenzhen Science and Technology Program IRCBS20210609 1609966556666,, Provincial Key Laboratory of Big Data Computing of The Chinese University of Hong Kong, Shenzhen.
and Guangdong
References
[1] Ricardo Alonso and Odilon Câmara. Persuading voters. American Economic Review, 106(11); 3590-3605, 2016.
[2] Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the genetic and evolutionary computation conference companion, pages 314-315, 2019.
[3] Dirk Bergemann and Stephen Morris. Information design: A unified perspective. Journal of Economic Literature, 57(1):44-95, 2019.
[4] Dirk Bergemann, Benjamin Brooks, and Stephen Morris. The limits of price discrimination. American Economic Review, 105(3):921-957, 2015.
[5] Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: Learning to persuade in the dark. In Advances in Neural Information Processing Systems, 2022.
[6] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 19Xiv:19/2.06680/ 2019.
[7] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[8] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
[9] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365 (6456):885-890, 2019.
[10] Kris Cao, Angeliki Lazaridou, Marc Lanctot, Joel Z Leibo, Karl Tuyls, and Stephen Clark. Emergent communication through negotiation. arXiv preprint arXiv:1804. 03980, 2018.
[11] Andrea Celli, Stefano Coniglio, and Nicola Gatti. Private bayesian persuasion with sequential games. In Proceedings of the AAAI Conference Artificial Intelligence, pages 1886-1895, 2020.
[12] E Choi, A Lazaridou, and N de Freitas. Compositional obverter communication learning from raw visual input. arXiv preprint arXiv:/804.023344 2018.
[13] Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. In UAI, 2002.
[14] Alvin W Drake. Observation of a Markov process through a noisy channel. PhD thesis, Massachusetts Institute of Technology, 1962.
[15] Shaddin Dughmi. Algorithmic information structure design: survey. ACM SIGecom Ex- changes, 15(2):2-24, 2017.

---

[16] Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning communicate with deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 2016.
[17] Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-eeaming awareness. Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, pages 122-130, 2018.
[18] Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential decision-making. In AAAI Conference on Artificial Intelligence, 2022.
[19] Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Sequential decision making with information asymmetry. In International Conference on Concurrency Theory, 2022.
[20] Serhii Havrylov and Ivan Titov. Emergence of language with multi-agent games: I Learning to communicate with sequences of symbols. Advances in Neural Information Processing Systems, 30, 2017.
[21] Penélope Hernández and Zvika Neeman. How bayesian persuasion can help reduce illegal parking and other socially undesirable behavior. American Economic Journal: Microeconomics 14(1):186-25 215, 2022.
[22] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improve- ments in deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, 2018
[23] Dmitry Ivanov, Iskander Safiulin, Igor Filippov, and Ksenia Balabaeva. Optimal-er auctions through attention. Advances in Neural Information Processing Systems, 35:34734-34747, 2022.
[24] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint
2016.
[25] Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcchre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning. pages 3049. PMLR, 2019.
[26] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 2021.
[27] Emir Kamenica. Bayesian persuasion and information design. Annual Review of Economics,
11 11:249-272, 2019.
[28] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 10166):550-26115 2011.
[29] Raphael Koster, Jan Balaguer, Andrea Tacchetti, Ari Weinstein, Tina Zhu, Oliver Hauser, Duncan Williams, Lucy Campbell-Gillinghann Phoebe Thacker, Matthew Botvinick, al. Human-centred mechanism design with democratic ai. Nature Human Behaviour, 6(10): 1398-1407, 2022.
[30] Joel Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Græepel. Multi-agent reinforeement learning in sequential social dilemmas. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Agent Systems, pages 464 473, 2017.
[31] Joel 7. Leibo, Edgar A mueñez-Guzman, Alexander Vezhnevets, John P Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch, and Thore Graepel. Scalable evaluation of multi-agent reinforcement learning with melting pot. In International Conference on Machine Learning, 2021.
[32] David Lewis. Convention: A philosophical study. John Wiley & Sons, 2008
12

---

[33] Changxi Li, Fenghua He, Hongsheng Qi, Daizhan Cheng, Longbiao Ma, Yonghong Wu, and Shuo Chen. Potential games design using local information. In 2018 IEEE Conference on Decision and Control, pages 1911-1916. IEEE, 2018.
[34] Na Li and Jason R Marden. Designing games for distributed optimization. IEEE Journal of Selected Topics in Signal Processing, 7(2):230-242, 2013.
[35] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competitve environments. Advances in Neural Information Processing Systems, 2017.
[36] Donald McCloskey and Arjo Klamer. One quarter of gdp is persuasion. The American Economic Review, 85(2):191-195, 1995.
[37] Kevin R McKee, Ian Gemp, Brian McWilliams, Edgar Dučñez- Edward Hughes, and Joel 7. Leibo. Social diversity and social preferences in mixed-motive reinforcement learning. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages
2020.
[38] Volodymyr Mnih, Adria Puigdomenech Badia, Mchdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, 2016.
[39] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337)5508-51133 2017.
[40] Roger B Myerson. Incentive compatibility and the bargaining problem. Econometrica: Journal of the Econometric Society, pages 61-73, 1979.
[41] Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73. 1981.
[42] Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent iifrecttionallycoordnnattt nets: Emergence of human- level coordination in learning to play starcraft combat games. arXiv preprint arXiv: 10069, 2017.
[43] Xue Bin Peng, Angjoo Kanazawa, Sam Toyer, Pieter Abbeel, and Sergey Levine. Variational discriminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining information flow. In International Conference on Learning Representations, 2019.
[44] Lillian J Ratliff and Tanner Fiez. Adaptive incentive design. IEEE Transactions on Automatic Control, (6(8)3371-3877 2020.
[45] Luis Rayo and lya Segal. Optimal information disclosure. Journal of Political Economy, 118 (5)9949-987, 2010.
[46] Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 2020.
[47] Tianmin Shu and Yuandong Tian. MÅRL: Mind-aware multi-agent management reinforcement learning. In International Conference Learning Representations, 2019.
[48] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. Nature, 529(7587):484-489, 2016.
[49] Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropa- gation. Advances in Neural Information Processing Systems, 2016.
[50] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
13

---

[51] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 1999.
[52] Ina Taneva. Information design. American Economic Journal: Microeconomics, 11(4):151-85, 2019.
[53] Leigh Tesfatsion and Kenneth L Judd. Handbook of computational economics: Agent-based computational economies. Elsevier, 2006.
[54] Richard H Thaler. Anomalies: The ultimatum game, Journal of economic perspectives, 2(4): 195-206, 1988.
[55] Mycal Tucker, Roger Levy, Julie A Shah, and Noga Zaslavsky. Trading off utility, informative- ness, and complexity in emergent communication. Advances Neural Information Processing Systems, 35:2221 1012221-220 22228, 2022.
[56] Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang. Zhuoran Yang, Michael I Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 471 17124 2022.
[57] Jiachen Yang, Ang Li, Mehrdad Farajtabar, Peter Sunehag, Edward Hughes, and Hongyuan Zha. Learning incentivize other learning agents. Advances in Neural Information Processing Systems, 2020.
[58] Jiachen Yang, Ethan Wang, Rakshit Trivedi, Tuo Zhao, and Hongyuan Zha. Adaptive incentive design with multi-agent meta-gradien reinforcement learning. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 1436-1445, 2022.
[59] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C Parkes, and Richard Socher. The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8(18)ccab22607, 2022.
[60] You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to persuade on the fly: Robustness against ignorance. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 927-928, 2021.
14


Reviews:
[{"review_id": "CM8zV8htnH", "reviewer": "Reviewer_sBPo", "summary": "This paper studies how multi-agent reinforcement learning agents influence each other by hsaring different kinds of information. Additionally, the authors study how different information affects the transition of the agents trajectories and what information can be ignored. To ensure efficient learning, a suitable gradient for the problem is also proposed.", "questions": "1. in line 306 it is stated that the receivers action policy is implemented using A2C. Is this the case for the sender too? Or do they share the same network as in multiple MARL approaches? This should be clarified in the paper.", "limitations": "1. It would be interesting to analyse the explainability of the messages exchanged by the receiver and speaker in these experiments, using the proposed method, as I can't find this is the paper and it is something very relevant when it comes to communication-driven games.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is well written and reads well. It is also well structured and contains only few spelling mistakes.\nSome other strengths in particular:\n- Proposes markov signalling games\n- Provides an extensive theoretical analysis of the approach\n- Develop the notions of a signalling gradient ", "weaknesses": "1. some of the related works in the appendix could be moved (or summarised) to the main text; the provided related works in the main text are too scarce and do not provide enough relevant information that relates to the paper\n2. the introduced markov signalling games seem to have some links with the famous Lewis games and other similar referencial games. Would be interesting to see a discussion around these concepts, as I cannot find it in the paper. Some related works also use reinforcement learning to learn communication involving similar games and concepts, such as [1], [2], [3], [4].\n\nminor:\n- line 323: \"ours\" -> \"our\"\n\nOverall, this paper is interesting and well structured. Please find here and below some points that I would like the authors to comment on.\n\n[1] https://openreview.net/pdf?id=O5arhQvBdH\n\n[2] https://arxiv.org/pdf/1804.02341.pdf\n\n[3] https://arxiv.org/pdf/1804.03980.pdf\n\n[4] https://arxiv.org/pdf/1705.11192.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. We now provide our responses.\n\n### Emergent communication\n\nThis reviewer shows particular interest in understanding how information is conveyed semantically, especially in the context of **emergent communication** and the emergence of language in multi-agent learning methods.\n\nWe find this aspect quite intriguing, and our experimental results have indeed observed a relevant phenomenon. Actually, we have discussions in **Section 5.3.1** of the paper, although we were not aware of it as a research direction beforehand. It's essential to note that this is not our primary focus, but we acknowledge that we lack an introduction to this direction in the related work. We will **add a separate subsection to the related work** to address this.\n\n### Comparisons of Markov signaling games with referential games.\n\nWe were not aware of the concept of referential games beforehand. After understanding them, we believe that these games **have significant differences** compared to the Markov signaling games we proposed.\n\nLewis signaling games and other similar referential games are usually **cooperative** tasks. The core of these tasks is how the sender efficiently conveys its information to the receiver, enabling the receiver to take **a specific action desired by both the sender and receiver.** The crucial aspect lies in how the sender conveys information to enable the receiver to understand the intended semantics. Therefore, **the sender aims to transmit as much of its available information as possible.** They train communication as a referential tool, and messages are used to disambiguate between different possible referents.\n\nInformation design focuses on **mixed-motive** communication tasks. The receiver's action will determine the payoffs for both parties, but there may not be a specific action that is desired by both. In fact, the **self-interested sender**'s goal is not to maximize the transmission of its known information, but to **leverage its information advantage to confuse the self-interested receiver, so as to maximize its own payoffs.** The sender aims to make the receiver believe in its statements in terms of posterior probabilities, convincing the receiver that following the sender's instructions is beneficial for the receiver itself. **the sender persuades the receiver to take actions that are advantageous to the sender** (In fact, senders typically learn deceptive strategies).\n\nOur experimental results also indicate that the sender and receiver can indeed establish a communication protocol through our method, allowing mutual understanding, even in situations where they have mixed motives (for a detailed discussion, refer to the answer to L1 below).\n\n### On the references provided by the reviewer\n\nThese papers focus on algorithms related to how to more efficiently convey information, the emergence of language in communication, and the relationship between learning algorithms and human language. Though they are not directly related to our work, these papers have inspired us in some ways, and we now have insights into the relationship between information design and emergent communication research. We have added [1-4] as references.\n\nThe most relevant one is probably the third paper [3], as they mention a negotiation environment that is indeed a mixed-motive task. The points of **difference** between their setting and Markov signaling games (ours) are as follows:\n\n1. They communicate multiple times and then choose an action. In contrast, we make a decision on the action after each communication round, and this selected action affects future states, making it a problem on a Markov model.\n2. Their communication is bidirectional, while ours is unidirectional.\n3. Their agent's information advantage over the other is its own utility function that remains hidden. In contrast, our sender's information advantage lies in its ability to observe the $s-o$ part that the receiver cannot see, and this portion is of interest to the receiver (as it determines the receiver's utility).\n\nThe **connection** between their work and ours is: The communication protocol we study uses the **linguistic channel** they mentioned, as it also satisfies two key properties: \n\n1. Non-bindingness: Messages sent via this channel do not commit the sender to any course of action (nor state), because the sender has an empty action space. The communication is purely a cheap talk.\n2. Unverifiability: There is no inherent link between the linguistic utterance and the true situation of the current state, meaning that the sender could potentially lie.\n\nWith their approach, self-interested agents cannot achieve good results using a linguistic channel, while ours can achieve good performance in Markov siganling games.\n\nThe fourth paper [4] reminded us that we also used **Gumbel-Softmax** to allow for end-to-end differentiation. Specifically, this is manifested in the signaling gradient derivation, where an unbiased gradient term includes $\\nabla_\\eta \\log \\pi_\\theta(a\\mid o,\\sigma)$, and this gradient is passed from the receiver's action policy to the sender's signaling network. The missing reference is \"Categorical Reparameterization with Gumbel-Softmax.\"\n\n### Implemented using A2C and explainability of the messages\n\nWe are using A2C **without parameter sharing**. In the experiments, PG represents the A2C algorithm; PGOC represents the A2C algorithm with extended obedience constraints. **SG represents the A2C algorithm with the policy gradient update part replaced by signaling gradient.** SGOC represents the SG algorithm considering extended obedience constraints when updating the signaling network.\n\nWe did not focus on the explainability of the messages. As we have discussed in **Section 5.3.1**, in some training seeds, the sender uses the signal **'1'** to represent a good student, while in other seeds, the sender uses the signal **'0'**. Therefore the messages are not explainable."}, {"review_id": "R1hwjTz9ny", "reviewer": "Reviewer_bi5b", "summary": "The article tackles the scenario where two agents, a sender $i$ and a receiver $j$, act in an environment.\nThe sender $i$ can send a message to the receiver $j$ at each time step.\nThe sender's goal is to learn what information to send to the receiver such that it influences the latter's policy to maximize its own return.\nThe authors derive a learning signal analogous to the policy gradient in the single-agent setup, and they also propose a version with a supplementary obedience constraint.\n\n", "questions": "What is incentive compatibility?", "limitations": "The authors mention some limitations, but I would add to that the need to backpropagate through the receiver's policy estimator.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strength of the paper lies in the extensive discussion of the setup and its challenges, and the different equilibria that could be reached by the two agents. These are also supported by empirical results.", "weaknesses": "The scenario is limited to the case where the sender can backpropagate through the receiver's estimator, which looks far from a realistic setup.\n\nFormula (3) needs some introduction. It is not clear why that formula expresses an obedience constraint. Similarly, it would be helpful to restate the revelation principle, not just mention it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. We now provide our responses.\n\nThe suggestions by the reviewer have reminded us that we should provide more detailed explanations for some fundamental concepts, which could also be confusing for other reviewers. We have improved the explanations of these concepts in the main text. \n\n### Is it reasonable for the sender to access the receiver's actor during training?\n\nYes, it is reasonable. Please kindly refer to the global response.\n\n### Introducing obedience constraints and the revelation principle.\n\nIn the context of information design, the revelation principle can be understood as follows: **The revelation principle states that there exists an optimal signaling scheme that does not require more signals than the number of actions available to the receiver.** (As mentioned in line 200 of our paper.) This principle is commonly used in the field of information design. \n\nThe **obedience constraints** are the core of information design and it significantly improves the performance in experiments. Assuming that the sender's signal set is equal to the receiver's action set, the sender's signals can be interpreted as recommending the receiver to take a specific action (This common assumption is without loss of generality according to the revelation principle). Under this premise, **obedience constraints ensure that the receiver will definitely follow the sender's recommendations.** \n\nTo explain why is it that as long as the sender's signaling scheme satisfies obedience constraints, the receiver will definitely follow the sender's recommendations, we provide a simple derivation as follows: \n$$\n\\begin{aligned}\n  & \\sum\\limits_{s} \\mu_0(s) \n  \\cdot \\varphi( a\\mid s )\n  \\cdot \\Big( r^j(s, a) - r^j(s, a') \\Big) \\ge 0 \\\\\n  \\Leftrightarrow &\n  \\sum\\limits_{s} \\frac{\\mu_0(s) \\cdot \\varphi( a\\mid s )}\n  { \\sum\\limits_{s'}\\mu_0(s') \\cdot \\varphi( a\\mid s')}\n  \\cdot \\Big( r^j(s, a) - r^j(s, a') \\Big) \\ge 0 , \\forall a'\\in A.\\\\\n  \\Leftrightarrow &\n  \\sum\\limits_{s} \\mu(s\\mid a)\n  \\cdot \\Big( r^j(s, a) - r^j(s, a') \\Big) \\ge 0 , \\forall a'\\in A.\\\\\n  \\Leftrightarrow &\n  \\sum\\limits_{s} \\mu(s\\mid a)\n  \\cdot r^j(s, a)  \\ge \n  \\sum\\limits_{s} \\mu(s\\mid a)\n  \\cdot r^j(s, a'), \\forall a'\\in A.\n\\end{aligned}\n$$\nIn the derivation, $\\mu_0$ represents the prior probability, and $\\mu$ represents the posterior probability. Therefore, a self-interested and rational receiver will definitely follow the sender's recommendations, because the posterior expected payoff of the action recommended by the sender is greater than or equal to the posterior expected payoffs of all other actions.\n\nThis greatly simplifies the problem, allowing **the sender to choose the action that maximizes its expected payoff, while ensuring that the receiver obeys, and then recommends the receiver to take that action.** Thus, the specific representation of the sender's optimization goal is:\n$$\n\\begin{aligned}\n\\max\\limits_{\\varphi} \\mathbb{E}_{\\varphi}[\\ r^i(s, a) \\ ],\\quad\\textrm{s.t. Obedience Constraints.}\n\\end{aligned}\n$$\n\n\n### Introducing incentive compatibility\n\nOur setting considers convincing a **self-interested rational** receiver to take actions that benefit the sender in mixed-motive tasks. \n\n**Incentive compatibility** refers to the idea that based on this receiver's assumption (self-interested and rational), the sender needs to make the receiver **\"believe\"** that the recommended action provides the maximum payoff (in terms of **posterior** belief), so that the receiver will choose the action recommended by the sender."}, {"review_id": "AYU8gBbnka", "reviewer": "Reviewer_5nfz", "summary": " This paper addresses the problem of multi-agent reinforcement learning in environments with mixed motives, which lie on the spectrum from fully cooperative to fully competitive scenarios. Specifically, it studies the problem of information design in this setting: how a sender might craft messages so that the behaviour of a receiver is successfully influenced. There are non-trivial implications in this setup, including the non-stationarity introduced by the messages and the fact that the receiver may choose not to obey them. The authors propose an algorithm to derive a signaling policy that takes into account the effect of the messages on the receiver's policy, as well as a way to learn the receiver's policy in a way that provides compatibility between the incentives. The algorithm is validated on two types of environments with mixed incentives.", "questions": "QS1. Please see W1 above, I would appreciate an answer.\n\nQS2. In the evaluation, it is unclear to me what is the appropriate metric to judge the performance of the algorithm. Is it $r^i$, $r^j$, or $r^i + r^j$ (social welfare)? Can we even speak of a right metric given the incompatibility between the incentives? Given that e.g. DIAL reaches the best equilibrium for the receiver, are the methods even comparable, or is the evaluation merely meant to illustrate which equilibria are reached? The \"goal\" of the evaluation should be clarified.\n\nQS3. Note that the supplementary material also includes the main paper text, and that the main PDF is not rendered properly (text is inaccessible, references are not linked). Consider compiling the main paper and supplementary material separately instead of cutting the PDF.\n\nQS4. Some nitpicks: first phrase of the abstract, while RL definitely is inspired by reward-driven learning in humans and animals, it is not necessarily setting out to mimic it; line 90 nature -> environment?.\n", "limitations": "Code and detailed information is available, which means the work is reproducible. No limitations beyond those already discussed in previous points. The authors have discussed broader impacts. The supplementary material includes a high-quality discussion of possible extensions in great depth.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: the paper is original in its consideration of mixed-motive environments, which have not received much attention in MARL, and yet are highly relevant for practical scenarios.\n\nQuality: the paper is of good quality. It motivates the work well by drawing connections to computational economics. It proposes methods that are grounded and sound, and performs a reasonable evaluation.\n\nClarity: the paper is well-structured and clear overall, although I was not able to understand some of the technical details as I am not familiar with the area in depth.\n\nSignificance: the area is one of active interest in the NeurIPS community.", "weaknesses": "W1. In my opinion, the primary weakness of this work is the strength of a particular assumption made by the authors: that the sender has full access to the receiver's policy and observation at every step. I am struggling to think of a scenario in which the assumption is suitable (since it amounts to global visibility) and yet the setting is not fully cooperative. What are some examples of scenarios in which this is the case? This aspect needs to be discussed more thoroughly. Otherwise, the proposed method may be of limited practical use.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. We now provide our responses.\n\n### QS1: Is it reasonable for the sender to access the receiver's actor and observation during training? What is the practical use of this model?\n\nYes, it is reasonable for the sender to access the receiver's actor and observation during training. Please kindly refer to the global response.\n\nTo illustrate its applications, we cited examples from this survey: Kamenica, Emir. \"Bayesian persuasion and information design.\" *Annual Review of Economics* (2019).\n\n\"Research in this second strand includes applications to (in no particular order): financial sector stress tests, **grading in schools**, employee feedback, law enforcement deployment, censorship, entertainment, financial over-the-counter markets, **voter coalition formation**, research procurement, contests, medical testing, medical research, matching platforms, price discrimination, financing, insurance, transparency in organizations, and **routing software**.\"\n\nIn fact, the classic Recommendation Letter (which serves as the experimental environment to test our algorithm. Detailed explanation can be found in **Section 5.1**.) serves as a real-world example corresponding to the \"grading in schools\" mentioned earlier.\n\nFurthermore, **routing software** is another easily imaginable example. In fact, this is the work we are currently undertaking (and this paper serves as its theoretical foundation). The central routing software and user vehicles are in a **mixed-motive** scenario, where the routing software aims to optimize the overall traffic speed, while each user wants to increase their individual speed. Moreover, the routing software has more **informational advantage** than user vehicles; it can know the congestion status of all relevant road segments, while user vehicles are not allowed to do so. Each user is self-interested, which may lead to a decrease in collective benefits, known as a social dilemma. A common example of this is **Braess's paradox**. Using information design can resolve this issue. For specific details, please refer to the article mentioned in this paper: Das, Sanmay, Emir Kamenica, and Renee Mirka. \"Reducing congestion through information design.\" *2017 55th annual allerton conference on communication, control, and computing (allerton)*. IEEE, 2017.\n\nIn recent years, there has been significant attention on autonomous driving, but fully cooperative communication algorithms cannot meet the requirements of this scenario. We believe that information design is a crucial approach to address the communication challenges in this context, making our paper highly valuable.\n\n### QS2: What is the appropriate metric to judge the performance of the algorithm?\n\nWe thank the reviewer for this insightful question. We have the below response and will add the discussions to the main body of the paper.\n\nFirst, our designed algorithm takes the perspective of a self-interested sender, aiming to optimize the following problem:\n$$\n\\begin{aligned}\n\\max\\limits_{\\varphi} \\mathbb{E}_{\\varphi}[\\ r^i(s, a) \\ ],\\quad\\textrm{s.t. Obedience Constraints.}\n\\end{aligned}\n$$\nTherefore, the measure of success for our algorithm primarily depends on $r^i$. However, we also present the curve of $r^i+r^j$ (social welfare) in an attempt to demonstrate that **even when the sender is self-interested and the signaling scheme is deceptive, it does not harm social welfare.**\n\nMoreover, for the same experiment, if we add a constant to all sender rewards, the sender can still persuade the receiver using the same signaling scheme (as the receiver's reward remains unchanged), and thus the receiver's utility remains unaffected. In this case, the difference between fully cooperative communication methods (e.g., DIAL) and our method becomes evident. Because DIAL only considers the receiver's reward and does not utilize the sender's reward (according to their concept, their method does not even use $r^i$ and does not reflect the self-interested sender). **If we add a constant to all sender rewards, their method's social welfare remains unchanged, while our method's social welfare improves.** \n\nAlso, the specific experimental results show that, even in the simplest scenario like Recommendation Letter, where the sender is self-interested, our method's social welfare far surpasses that of DIAL.\n\nFor completeness, we discuss the case where the sender's optimization objective is social welfare in lines 134-137 and in Appendix I: Broader Impacts. In this case, although the sender receives rewards from the environment ($r^i$), the sender can consider the following problem:\n$$\n\\begin{aligned}\n\\max\\limits_{\\varphi} \\mathbb{E}_{\\varphi}[\\ r^i(s, a)+r^j(s, a) \\ ],\\quad\\textrm{s.t. Obedience Constraints.}\n\\end{aligned}\n$$\nAnd in this setting, comparing social welfare is fair.\n\nMost of the existing MARL communication methods are not for mixed-motive tasks. The insight of DIAL is to update the sender's signaling network based on the receiver's gradient, but this means that the training only utilizes information from $r^j$ and does not take advantage of $r^i$. In fully cooperative tasks, this is not an issue because all agents' rewards are always the same.\n\nWe thank the reviewer for QS3 and QS4 and we have fixed them immediately.\n"}, {"review_id": "NhdumA0xvk", "reviewer": "Reviewer_6N28", "summary": "This paper proposes a new agent-interaction framework called Markov signaling games, and the corresponding algorithm for mixed-motive tasks. Various experiments and discussions are provided to show the efficacy of the proposed method.", "questions": "See Weakness", "limitations": "The limitations are provided in Appendix.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The authors provide a new formulation of agent-interaction framework for multi-agent reinforcement learning and the corresponding detailed explanation.\n\n- The proposed algorithm to solve Markov signaling game with theoretical results is provided.\n\n\n\n", "weaknesses": "It is unclear what makes Markov signaling games important. While related works on multi-agent RL with communication are provided, It seems that Markov signaling games appear to be just one concept of communication in multi-agent RL. In the proposed game, it is assumed that the sender observes a fully environmental state and sends a message to the receiver. Is this assumption reasonable and important? The authors should explain why Markov signaling games are important compared to conventional communication frameworks in multi-agent RL, where multiple agents aim to solve tasks while communicating with other agents. The conventional framework does not even differentiate between which agents are senders or receivers.\n\nFurthermore, the paper should include a comparison with state-of-the-art multi-agent communication algorithms such as TarMAC[1], ATOC[2], and others. Currently, the authors only provide a comparison with DIAL.\n\n\n[1] A. Das et al., \"TarMAC: Targeted multi-agent communication\"\n\n[2] J. Jiang et al., \"Learning attentional communication for multi-agent cooperation\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. We now provide our responses. We wanted to point out that our work is a learning-based extension of information design in sequential decision-making. It focuses on mixed-motive settings which are less addressed in existing MARL communication works. We also wish that with our responses and explanation, the reviewer might re-evaluate the work should they have their concerns addressed.\n\n### What makes Markov signaling games important?\n\nMSG is the necessary and fundamental formulation to achieve information design. Please kindly refer to the global response for a detailed explanation.\n\n### Comparison with SOTA MARL communication algorithms\n\nWe believe that additional experiments are not necessary because it is not relevant to the scope of our work. We are not aiming to improve algorithm performance based on existing research on cooperative settings. Instead, we focus on mixed-motive settings.\n\nFirst, let's take the Recommendation Letter experiment (detailed description can be found in Section 5.1) as an example. This task is already quite simple, and DIAL has reached the limit of traditional MARL communication methods. In fact, theoretically designed algorithms for fully cooperative tasks cannot be applied to mixed motive tasks and cannot reach equilibrium in theoretical analysis. These algorithms are not fitting into mixed-motive tasks, and the training for these tasks is not even well-defined. \n\nFor instance, the insight behind DIAL is to update the sender's signaling net based on the receiver's gradient, but this means that the training only utilizes information from $r^j$ and does not leverage $r^i$. As a result, the performance of $r^i$ in the experiments is significantly poor. This issue does not arise in fully cooperative tasks because all agents have the same reward.\n\nIn other AC-framework-based algorithms, they use independent policy gradient, which is biased compared to our signaling gradient, and we have provided experiments comparing PG with SG. If we were to compare other AC-framework-based algorithms, we could simply replace their PG part with SG and add the Lagrange term for obedience constraints. **Conducting experiments to compare with DIAL's performance was already done for completeness**, and there is no need to dwell on supplementing experiments for fully cooperative tasks.\n\nAdditionally, the notion of \"mixed-motive\" that we are referring to is different from that in TarMAC and ATOC. In their mixed motive task, predator and prey teams are fully cooperative within each team but fully competitive between teams. However, their algorithms focus on within-team interactions, so they essentially concentrate on fully cooperative scenarios. On the other hand, the problem we are discussing involves individual agents with mixed motives, where **mixed motives exist between the two agents themselves**.\n\n### Added explanation and comparison with social influence-based MARL communication algorithms\n\nWe thank the reviewer for suggesting exploring more into the subarea of MARL communication. Indeed, there is an existing social influence-based work that conducts insightful and pioneer attempts on communication in mixed-motive tasks. Please kindly refer to the global response for a detailed description and comparisons."}, {"review_id": "4I5IzY2XhM", "reviewer": "Reviewer_YNGH", "summary": "This paper studied a Markov signaling game and proposed to use the signalling gradient and extended obedience constraint to build a learning system that can effectively train the sender in the game to reach desirable equilibriums. Experiments performed on two toy problems suggest that the newly developed SGOC algorithm can perform well and reach desirable equilibriums, compared to several competing learning methods.", "questions": "Why is the Markov signaling game studied in this paper new and practically important?\n\nWhat is the practical difficulty of supporting/realizing the commitment assumption? When the sender and receiver have potentially conflicting interests, why would the receiver be motivated to honestly support the sender by providing its internal information to the sender?\n\nWhy will the non-stationarity issue be alleviated by using signalling gradient?\n\nWhat is the exact meaning of biased policy gradient?\n\nWhy should $\\nabla_{\\eta}\\pi_{\\theta}(a|o,\\sigma)$ be 0? Why should the sender's signaling scheme and the receiver's action policy be updated alternately rather than simultaneously?\n\nWhat are the feasibility, complexity, and difficulty of building a reputation system to support the basic assumptions of the new algorithm and the Markov signaling game?", "limitations": "I do not have any concerns regarding this question.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "It is interesting and important to study the information sharing problem in a multi-agent context. The Markov signaling game presented in this paper appears to be of some practical values and deserves further investigation. The design of the new SGOC algorithm also introduces some novel ideas.", "weaknesses": "It is not clear whether the Markov signaling game introduced in this paper is new and has never been studied previously. The novelty of this game may need to be clarified. Its usefulness for practical applications also seems uncertain. I cannot immediately relate the two toy problems studied experimentally in this paper with any practically important scenarios where an effective machine learning-based solution of the Markov signaling game is essential. Hence, the motivation and research value of this paper may need to be significantly strengthened.\n\nThe above concern is partially triggered by the lack of discussion of related works in the main text of this paper. Because of this, the importance and novelty of studying the Markov signaling game remain doubtful to a certain extent. The true technical novelty of using the signaling gradient and the extended obedience constraint hence should be further investigated.\n\nIt is assumed that the sender can access the receiver's policy and observation (the receiver's observation is not necessarily accessible to the sender). I have no idea when such an assumption could be true in a practical scenario. In fact, the calculation of the signaling gradient may rely on this assumption. However, when the sender and receiver have potentially conflicting interests, it is entirely unclear why the receiver would be motivated to honestly support the sender by providing its internal information to the sender (in a conflicting scenario, the sender and receiver may not have the motivation to participate in a centralized training process). This further makes me question the practical value of the new SGOC algorithm.\n\nSome statements in the paper sound a bit questionable and needs further clarification and justification. For example, the authors mentioned several times that the signaling gradient can alleviate the non-stationarity between the sender and receiver. However, it remains unknown to me why the non-stationarity can be alleviated in this way. Moreover, since the receiver is handling a partially-observable problem, it may consider to adopt a recurrent neural network as its policy network. In view of this, the calculation of the signaling gradient may become significantly more complicated. Meanwhile, the idea of biased policy gradient has been mentioned multiple times in this paper. However, I can hardly understand its true meaning. Hence, related discussions in the paper do not sound highly convincing to me.\n\nBesides the above, I have no idea why $\\nabla_{\\eta}\\pi_{\\theta}(a|o,\\sigma)$ should be 0 and why the sender's signaling scheme and the receiver's action policy should be updated alternately rather than simultaneously. This as well as several other algorithmic design details appear to have some technical issues.\n\nThe authors discussed the necessity of establishing a reputation system. However, the feasibility, complexity, and difficulty of building such a reputation system have not been investigated with sufficient depth. While building such a reputation system may not be necessary for this study, its feasibility could significantly affect the importance and practicality of the newly developed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. We now provide our responses. \n\nWe are glad that the reviewer is interested in our work and asked many questions. Despite this, there are factual misunderstandings in the review which might have affected the evaluation of our work. We wish that with our responses and explanation, the reviewer might re-evaluate the work should they have their concerns addressed.\n\n### Q1: Why is the Markov signaling game studied in this paper new and practically important?\n\nThe reviewer mentioned a lack of related work. Due to space constraints, our related work is only mentioned in the main text for information design, while the remaining parts are placed in Appendix A. This includes discussions on mechanism design, sequential information design, and conventional MARL communication methods.\n\n### Q2: What is the practical difficulty of supporting/realizing the commitment assumption?\n\nWe believe that this is a factual misunderstanding in the review. Our proposed algorithm does not rely on the commitment assumption. On the contrary, the commitment assumption is a limitation of many information design algorithms, and one of our contributions is actually the removal of this assumption. We specifically address this issue in **section 4.5.1**.\n\n### Q3: When the sender and receiver have potentially conflicting interests, why would the receiver be motivated to honestly support the sender by providing its internal information to the sender?\n\nYes, it is reasonable to have the access. Please kindly refer to the global response for a detailed explanation.\n\n### Q4: Why will the non-stationarity issue be alleviated by using signaling gradient?\n\nThis issue is a very important one and involves the insight behind signaling gradient. Non-stationarity is a common problem in the field of MARL. Each RL agent only focuses on its own learning, which means that every agent treats all quantities except itself as part of the environment, treating other agents as part of the environment. As a result, for an agent with policy $\\pi$, when other agents update, its environment changes, and even with the same policy, its value function will change as a result of the updates to other agents' states. We believe this phenomenon arises due to the independence of agents. However, our signaling gradient does not update its network independently; instead, it considers the impact of the receiver's policy. This is precisely the core insight behind signaling gradient.\n\n### Q5: What is the exact meaning of biased policy gradient?\n\nSimilar to Sutton's policy gradient theorem, we explicitly consider the complete Markov model that includes both the sender and receiver, and prove that the signaling gradient is unbiased. Here, the term \"unbiased\" has the same meaning as in the policy gradient theorem, indicating that the gradients we compute are accurate. If we were to treat the sender's signaling scheme as a regular action policy and update it using policy gradient, we would overlook a significant amount of gradient information, resulting in bias.\n\nOur signaling gradient is:\n$$ \\nabla_\\eta V_{\\varphi, \\pi}^i(s) \\propto\\ \\mathbb{E}\\_{\\varphi,\\pi} \\left[ W\\_{\\varphi,\\pi}^i(s, a) \\cdot \\left[ \\nabla_\\eta \\log \\pi_{\\theta}(a \\mid o, \\sigma) + \\nabla_\\eta \\log \\varphi_\\eta(\\sigma \\mid s, o) \\right] \\right].$$\n\nAnd if using the vanilla policy gradient, it would be:\n$$\n\\mathbb{E}\\_{\\varphi,\\pi} \\left[ Q\\_{\\varphi,\\pi}^i(s,\\sigma) \\cdot \\nabla_\\eta \\log \\varphi_\\eta(\\sigma \\mid s) \\right].\n$$\nOne could see that vanilla policy gradient is biased by missing the $\\nabla_\\eta \\log \\pi_{\\theta}(a \\mid o, \\sigma)$ term.\n\n### Q6: Why $\\nabla_\\eta \\pi_{\\theta}(a\\mid o,\\sigma) =0$ should be 0?\n\nWe assume that the reviewer is referring to line 235 of the manuscript. In obedience constraints, $\\sigma$ and $\\sigma'$ are given by the forall quantifier, see Equation (5). Therefore $\\sigma$ and $\\sigma'$ are not given by $\\varphi_\\eta$. As such the gradient does not backpropagate to $\\eta$.\n\n### Q7: Why should the sender's signaling scheme and the receiver's action policy be updated alternately rather than simultaneously?\n\nThe point of being updated alternately is indeed not explicitly mentioned in the paper. Thank you for pointing this out, and we will include this clarification in the manuscript.\n\nThis is achieved through the use of **online cross-validation** technique, which is used to optimize hyperparameters in meta-gradient RL, and by the optimal reward framework. In fact, this technique is inspired by LIO (Yang, Jiachen, et al. \"Learning to incentivize other learning agents.\" *NeruIPS (2020).). We are somewhat aligned with LIO, and the discussion of these perspectives is presented in Section 4.5.4: Hyper Gradient.\n\nAdditionally, the earliest instance of online cross-validation can be traced back to: Sutton, Richard S. \"Adapting bias by gradient descent: An incremental version of delta-bar-delta.\" *AAAI*. 1992.\n\n### Q8: What are the feasibility, complexity, and difficulty of building a reputation system to support the basic assumptions of the new algorithm and the Markov signaling game?\n\nThis refers to some future directions and is out of the scope of this manuscript.\n\n\n"}]

Author rebuttal:
We notice some common concerns expressed by the reviewers. One is on the sender's access to the receiver, and the other is on MSG for mixed-motive MARL communication. These "concerns" are not issues and we are happy to explain why.

### Sender and receiver are in interest conflict. Can the sender have access to the receiver's policy and observation in signaling gradient (2)?

Definitely yes for accessing the policy. Such access is only used in centralized training (CT) and once it is trained the access is no longer needed in decentralized execution (DE). Therefore, when interest conflict applies (execution time), the access is not used.

In MARL algorithms, whether they are communication algorithms or not, the CTDE (Centralized Training with Decentralized Execution) framework is commonly used (see, e.g., **MADDPG**). This means that in the simulated environment, data is centralized and accessible during training, allowing us to use all the required quantities. As long as the algorithm does not require cross-agent access during agent execution, it is reasonable.

Additionally, in communication methods, it is common for gradients to pass through other agents during training. We adopted the commonly used **Gumbel-Softmax** technique in the field of emergent communication research to allow for end-to-end differentiation, which is used to retain the gradients of sampled signals. Examples are

For observation, the receiver's observation is **common knowledge** between the sender and receiver. This is quite reasonable, as the sender possesses an informational advantage. For example, in the case of vehicle routing, the routing algorithm will have access to the user vehicles' observations. We have discussed the case if access to the observation is not available in **Appendix B**: Extensions of Markov Signaling Games.

[1] Havrylov, Serhii, and Ivan Titov. "Emergence of language with multi-agent games: Learning to communicate with sequences of symbols." *Advances in Neural Information Processing Systems (2017).

[2] Foerster, Jakob, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. "Learning to communicate with deep multi-agent reinforcement learning." Advances in Neural Information Processing Systems (2016).


### Justification for our proposed process: Markov signaling games

The core of MSG is extending information design to sequential decision-making scenarios. Specifically, what makes MSG different from other communication processes can be summarized in the following points: 

1. The sender and receiver are heterogeneous, with the sender having an **informational advantage**, which lies in its ability to observe the $s-o$ part that the receiver cannot observe, and this part is of interest to the receiver (as it influences the receiver's utility);
2. Their interests may differ. Their rewards are not specified to be identical, so they may be in a mixed-motive scenario. In reality, this is quite common, but the current MARL communication framework typically focuses on fully cooperative scenarios; 
3. The sender cannot take actions, and its signal is not an influencing factor in anyone's reward function. Therefore, the sender can only influence the receiver's belief and subsequently modify its own expected payoffs by changing the signaling strategy; 
4. The receiver can take actions to directly determine the payoffs for both parties, but lacks sufficient information to estimate the current state and thus needs to obtain information from the sender.

These differences are necessary to re-inspect the MARL communication process in a mixed-motive environment, and provide the necessary formulation to apply game-theoretic methods for the communication algorithm. 

### Added discussions and experiments on existing mixed-motive communication works

While most of the works in communication do not directly extend to mixed-motive cases, Section 5 in [3] conducts insightful pioneer works on this setting. We apologize for missing the references in our original text.

In [3], the authors propose social influence, which is defined using KL divergence to identify actions that cause the greatest change in the action distribution of others (in other words, actions that have the most influence on others). The social influence is then treated as an intrinsic reward. In this way, the agent will try to influence others as much as possible. This method serves as a promising initial attempt for this type of problem, achieving favorable results in several experiments. However, whether/why maximizing influence on others leads to good performance in mixed-motive communication tasks remains unclear.

Information design is a dedicated subarea in economics that studies mixed-motive communication problems. Our Markov signaling games and the SGOC algorithm are armed with formulations in information design, and can be regarded as a more methodological and game-theoretic follow-up of [3]. Our method is sound as the extended obedience constraints will induce incentive compatibility, which will be the foundation that the receiver will respect the message. 

We have re-implemented [3] and found out that it does not work in the Recommendation Letter task. The learning curves are provided in the attached PDF. We find that the receiver is unlikely to respect the message over time, which agrees with the following description in [3]: "Because the listener agent is not compelled to listen to any given speaker, listeners selectively listen to a speaker only when it is beneficial, and influence cannot occur all the time."

[3] Jaques, Natasha, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, D. J. Strouse, Joel Z. Leibo, and Nando De Freitas. "Social influence as intrinsic motivation for multi-agent deep reinforcement learning." In International Conference on Machine Learning (2019).

Meta-review: After a lively discussion and detailed and thorough rebuttal by the authors, several reviewers of this paper (sBPo, 6N28, and YNGH) have raised their initial scores, leading to a consensus among the reviewers that the paper should be accepted. The scores are now 6,6,6,5,5, with an average of 5.6, which is just above the acceptance threshold. 

Positive aspects of the paper identified by the reviewers include its **quality** ("It motivates the work well by drawing connections to computational economics. It proposes methods that are grounded and sound, and performs a reasonable evaluation."), **clarity** (“This paper is well written and reads well.”), and the **importance** of the problem (“It is interesting and important to study the information sharing problem in a multi-agent context. The Markov signaling game presented in this paper appears to be of some practical values and deserves further investigation.”). 

Below, I will summarize the main themes of the concerns raised by the reviewers as well as the authors' rebuttal to these concerns. Overall, given the authors' response thoroughly addresses the reviewers' concerns, and the reviewers themselves have raised their scores to a unanimous accept, I recommend the paper be accepted. 

### Lack of citations of relevant prior work
Several reviewers complained that the authors did not include a thorough related work section, and particularly that they failed to cite important works on multi-agent (emergent) communication, referential games, etc. In fact, the authors originally claimed that they were the first to study multi-agent communication in mixed motive settings, failing to cite prior work that does address this problem (e.g. https://arxiv.org/abs/1810.08647). In the rebuttal and global response, the authors have corrected these issues, added explanations of how the proposed work differs from this prior work, and even included additional experiments comparing to this baseline. So in my opinion, these concerns have been adequately addressed. 

### Practical applicability of backpropagating through the receiver's policy
Several reviewers initially complained that because the method relies on backpropagating through the receiver's policy in a mixed motive setting, it did not seem applicable to any realistic scenario. Quoting reviewers:
- bi5b: “The scenario is limited to the case where the sender can backpropagate through the receiver's estimator, which looks far from a realistic setup.” 
- 5nfz: “In my opinion, the primary weakness of this work is the strength of a particular assumption made by the authors: that the sender has full access to the receiver's policy and observation at every step. I am struggling to think of a scenario in which the assumption is suitable (since it amounts to global visibility) and yet the setting is not fully cooperative”
- YNGH: “I cannot immediately relate the two toy problems studied experimentally in this paper with any practically important scenarios where an effective machine learning-based solution of the Markov signaling game is essential.”

The authors rebutted these points in the global response by saying that they are using the common MARL training paradigm of CTDE (centralized training, decentralized execution), and therefore it is reasonable for the receiver to share its policy weights during training, if not execution. They added in the response to reviewer YNGH that their method is applicable to a vast array of real-world scenarios, including grading in schools, employee feedback, law enforcement deployment, etc.

Initially, I did not find these arguments convincing, because I also did not see how the CTDE paradigm was relevant in these scenarios. I was skeptical that students submitting homework have the opportunity to backprop through their instructor's brain when completing homework assignments. I agreed with reviewer YNGH's comment: "when the sender and receiver have potentially conflicting interests, it is entirely unclear why the receiver would be motivated to honestly support the sender by providing its internal information to the sender (in a conflicting scenario, the sender and receiver may not have the motivation to participate in a centralized training process).”

However, the authors provided further clarification in a final comment, where they explained that: the “sender's signaling scheme is the main objective to train, while the receiver is a "dummy" learning agent that is auxiliary in centralized training. [...] Therefore, our algorithm does not require access to those real agents' (e.g. real vehicles') policies. Instead, our algorithm only requires assumptions that they are rational and self-interested (which are commonly used in computational economics) and simulate them as such." In this case, it does make sense to use a simulated, dummy receiver to train the sender, and I find that this concern is also addressed adequately.
Decision: Accept (poster)