pith. sign in

arxiv: 2603.03664 · v2 · submitted 2026-03-04 · 📡 eess.SY · cs.LG· cs.MA· cs.SY· math.OC

Principled Learning-to-Communicate with Quasi-Classical Information Structures

Xiangyu Liu , Haoyi You , Kaiqing Zhang This is my paper

Pith reviewed 2026-05-15 17:12 UTC · model grok-4.3

classification 📡 eess.SY cs.LGcs.MAcs.SYmath.OC
keywords learning to communicateDec-POMDPinformation structuresquasi-classicalmulti-agent reinforcement learningdecentralized stochastic controlplanning algorithms
0
0 comments X

The pith

Quasi-classical information structures allow provable planning and learning algorithms for communication in Dec-POMDPs with quasi-polynomial complexity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper formalizes learning-to-communicate problems in decentralized partially observable Markov decision processes using the common-information-based framework from control theory. It classifies these problems by their information structures before additional sharing occurs and shows that non-classical cases are computationally intractable in general. The central contribution is a set of conditions for quasi-classical LTCs under which the information structure remains quasi-classical after sharing, enabling the design of planning and learning algorithms that achieve quasi-polynomial time and sample complexities on satisfying examples. New supporting results connect strictly quasi-classical structures to strategy-independent common-information-based beliefs and extend solution methods for Dec-POMDPs beyond those beliefs without requiring intractable oracles.

Core claim

Under a series of conditions that keep the information structure quasi-classical after communication, LTC problems admit planning and learning algorithms with quasi-polynomial time and sample complexities; these conditions are necessary in the sense that their violation restores general intractability, and the framework also yields new relationships between quasi-classical structures and strategy-independent common-information-based beliefs.

What carries the argument

Quasi-classical information structures (QC IS) together with the preservation conditions after information sharing, which reduce the problem to solvable forms while avoiding computationally intractable oracles.

If this is right

  • Planning and learning become feasible for any QC LTC that meets the preservation conditions, with explicit quasi-polynomial bounds.
  • Dec-POMDPs without SI-CIBs can still be solved tractably when they admit QC LTC structure.
  • The same algorithmic template applies uniformly to several concrete QC LTC families once the conditions hold.
  • Communication strategies learned under these conditions remain optimal within the preserved quasi-classical class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of multi-agent systems can check the preservation conditions at design time to guarantee that joint learning of control and communication will stay tractable.
  • The quasi-polynomial bound suggests that moderate increases in the number of agents or horizon length remain computationally feasible when the structure is preserved.
  • The bridge between control-theoretic information structures and deep RL training loops may allow transfer of complexity results in both directions.

Load-bearing premise

The LTC instance must satisfy the listed conditions that ensure the quasi-classical information structure is preserved after the agents share information.

What would settle it

An explicit QC LTC example that meets all but one preservation condition yet requires super-quasi-polynomial time for planning or learning, or a concrete Dec-POMDP instance where violating the conditions produces hardness matching the non-classical case.

Figures

Figures reproduced from arXiv: 2603.03664 by Haoyi You, Kaiqing Zhang, Xiangyu Liu.

Figure 1
Figure 1. Figure 1: Illustrating the subroutines for solving the LTC problems. [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Venn diagram of LTCs with different ISs: ① QC LTCs. ② QC LTCs satisfying Assump￾tions III.4, III.5, and III.7. ③ sQC LTCs. ④ sQC LTCs satisfying Assumptions III.4, III.5, and III.7, which can be converted to Dec-POMDPs with SI-CIBs; (b) Venn diagram of general Dec-POMDPs with different ISs. PR denotes perfect recall. We construct examples for each area of ①-⑤ in §H. eral QC Dec-POMDPs, which thus advan… view at source ↗
Figure 3
Figure 3. Figure 3: The time-average values achieved under di [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Learning curves, i.e., the values associated with the overall objective (reward minus cost) [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustrating the learning-to-communicate problem considered in this paper. [PITH_FULL_IMAGE:figures/full_fig_p071_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Timeline of the information sharing and information evolution protocols in the learning [PITH_FULL_IMAGE:figures/full_fig_p071_6.png] view at source ↗
read the original abstract

Learning-to-communicate (LTC) in partially observable environments has received increasing attention in deep multi-agent reinforcement learning, where the control and communication strategies are jointly learned. Meanwhile, the impact of communication on decision-making has been extensively studied in control theory. In this paper, we seek to formalize and better understand LTC by bridging these two lines of work, through the lens of information structures (ISs). To this end, we formalize LTC in decentralized partially observable Markov decision processes (Dec-POMDPs) under the common-information-based framework from decentralized stochastic control, and classify LTC problems based on the ISs before (additional) information sharing. We first show that non-classical LTCs are computationally intractable in general, and thus focus on quasi-classical (QC) LTCs. We then propose a series of conditions for QC LTCs, under which LTC preserves the QC IS after information sharing, whereas violating them can cause computational hardness in general. Further, we develop provable planning and learning algorithms for QC LTCs, and establish quasi-polynomial time and sample complexities for several QC LTC examples that satisfy the above conditions. Along the way, we also establish new results on a relationship between (strictly) QC IS and the condition of having strategy-independent common-information-based beliefs (SI-CIBs), as well as on solving Dec-POMDPs without computationally intractable oracles but beyond those with SI-CIBs, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper formalizes learning-to-communicate (LTC) in Dec-POMDPs under the common-information-based framework, classifies LTC problems by information structures (ISs) before additional sharing, proves general intractability for non-classical cases, and identifies conditions for quasi-classical (QC) LTCs under which the QC IS is preserved after sharing. It develops provable planning and learning algorithms for such QC cases and derives quasi-polynomial time and sample complexity bounds for several compliant examples, while also establishing new relationships between (strictly) QC IS and strategy-independent common-information-based beliefs (SI-CIBs) and results on solving Dec-POMDPs beyond SI-CIBs.

Significance. If the stated conditions and complexity derivations hold, the work supplies a principled bridge between decentralized stochastic control and deep multi-agent RL by identifying when communication preserves tractable structure, yielding the first quasi-polynomial guarantees for structured LTC instances. The explicit tie to SI-CIBs and the dynamic-programming reductions are strengths that could guide algorithm design in partially observable multi-agent settings.

major comments (2)
  1. [Conditions for QC LTCs (post-abstract development)] The central claim that the proposed series of conditions for QC LTCs preserve the QC IS (and thereby enable the quasi-polynomial bounds) is load-bearing; the manuscript should include an explicit necessity argument or counter-example showing that violation of at least one condition restores hardness, rather than only sufficiency.
  2. [Planning and learning algorithms section] The quasi-polynomial time and sample complexity statements for the QC LTC examples rely on dynamic-programming reductions under the preserved structure; the derivation of the precise exponent and the error propagation from the SI-CIB property to the final bound should be expanded with explicit constants or recurrence relations to allow verification.
minor comments (2)
  1. [Preliminaries] Notation for common-information-based beliefs and SI-CIBs should be introduced with a short table or diagram early in the paper to assist readers coming from the MARL literature.
  2. [Figures throughout] Figure captions illustrating information structures should explicitly reference the corresponding theorem or condition number for quick cross-checking.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and the constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: The central claim that the proposed series of conditions for QC LTCs preserve the QC IS (and thereby enable the quasi-polynomial bounds) is load-bearing; the manuscript should include an explicit necessity argument or counter-example showing that violation of at least one condition restores hardness, rather than only sufficiency.

    Authors: We agree that an explicit counter-example would strengthen the necessity claim. The manuscript already states that violating the conditions can cause computational hardness in general (via the non-classical intractability result), but we will add a concrete counter-example in the revision demonstrating that violating at least one specific condition restores a non-quasi-classical structure and associated hardness. revision: yes

  2. Referee: The quasi-polynomial time and sample complexity statements for the QC LTC examples rely on dynamic-programming reductions under the preserved structure; the derivation of the precise exponent and the error propagation from the SI-CIB property to the final bound should be expanded with explicit constants or recurrence relations to allow verification.

    Authors: We will expand the planning and learning algorithms section to include the detailed recurrence relations for the dynamic-programming reductions and explicit constants for error propagation from the SI-CIB property through to the final quasi-polynomial bounds, allowing direct verification. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's derivation chain starts from standard Dec-POMDP definitions and the common-information-based framework of decentralized stochastic control (external prior literature). It then states explicit conditions under which LTC preserves the QC IS, derives planning/learning algorithms via dynamic programming reductions on the preserved structure, and obtains quasi-polynomial bounds for concrete examples satisfying those conditions. No step reduces by construction to a fitted parameter, a self-citation chain, or a renamed input; the SI-CIB relationship and new complexity results are presented as independent contributions built on the external foundations rather than presupposing the target claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard definitions of Dec-POMDPs and the common-information-based framework; no free parameters or invented entities are introduced in the abstract. The conditions for preserving QC structure after sharing are presented as domain assumptions rather than derived quantities.

axioms (1)
  • domain assumption Dec-POMDP model with common-information-based information structures
    Invoked throughout the classification and algorithm development sections referenced in the abstract.

pith-pipeline@v0.9.0 · 5578 in / 1220 out tokens · 27819 ms · 2026-05-15T17:12:20.608036+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

  1. [1]

    Learning to communicate with deep multi-agent reinforcement learning,

    J. Foerster, I. A. Assael, N. De Freitas, and S. Whiteson, “Learning to communicate with deep multi-agent reinforcement learning,” inNeurIPS, 2016

    work page 2016

  2. [2]

    Learning multiagent communication with backpropagation,

    S. Sukhbaatar, R. Fergus,et al., “Learning multiagent communication with backpropagation,” inNeurIPS, 2016

    work page 2016

  3. [3]

    Learning attentional communication for multi-agent cooperation,

    J. Jiang and Z. Lu, “Learning attentional communication for multi-agent cooperation,” in NeurIPS, 2018

    work page 2018

  4. [4]

    Control under communication constraints,

    S. Tatikonda and S. Mitter, “Control under communication constraints,”IEEE Trans. Autom. Control, vol. 49, pp. 1056–1068, 2004

    work page 2004

  5. [5]

    Feedback control under data rate con- straints: An overview,

    G. N. Nair, F. Fagnani, S. Zampieri, and R. J. Evans, “Feedback control under data rate con- straints: An overview,”Proc. IEEE, vol. 95, pp. 108–137, 2007

    work page 2007

  6. [6]

    Joint optimization of wireless communication and networked control systems,

    L. Xiao, M. Johansson, H. Hindi, S. Boyd, and A. Goldsmith, “Joint optimization of wireless communication and networked control systems,” inSwitching and Learning in Feedback Systems. Springer, 2005, pp. 248–272

    work page 2005

  7. [7]

    Jointly optimal LQG quantization and control policies for multi-dimensional sys- tems,

    S. Yüksel, “Jointly optimal LQG quantization and control policies for multi-dimensional sys- tems,”IEEE Transactions on Automatic Control, vol. 59, no. 6, pp. 1612–1617, 2013

    work page 2013

  8. [8]

    Optimal communication and control strategies in a multi-agent MDP problem,

    S. Sudhakara, D. Kartik, R. Jain, and A. Nayyar, “Optimal communication and control strategies in a multi-agent MDP problem,”arXiv preprint arXiv:2104.10923, 2021

    work page arXiv 2021

  9. [9]

    Optimal communication and control strategies for a multi-agent system in the presence of an adversary,

    D. Kartik, S. Sudhakara, R. Jain, and A. Nayyar, “Optimal communication and control strategies for a multi-agent system in the presence of an adversary,” inProc. IEEE Conf. on Dec. and Control, 2022

    work page 2022

  10. [10]

    Separation of estimation and control for discrete time systems,

    H. S. Witsenhausen, “Separation of estimation and control for discrete time systems,”Proc. IEEE, vol. 59, pp. 1557–1566, 1971

    work page 1971

  11. [11]

    Information structures in optimal decentralized control,

    A. Mahajan, N. C. Martins, M. C. Rotkowitz, and S. Yüksel, “Information structures in optimal decentralized control,” inProc. IEEE Conf. on Dec. and Control, 2012

    work page 2012

  12. [12]

    Yüksel and T

    S. Yüksel and T. Başar,Stochastic teams, games, and control under information constraints. Springer, 2024

    work page 2024

  13. [13]

    The complexity of decentralized control of Markov decision processes,

    D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein, “The complexity of decentralized control of Markov decision processes,”Math. Oper. Res., vol. 27, pp. 819–840, 2002. 17

    work page 2002

  14. [14]

    Partially observable multi-agent reinforcement learning with information sharing,

    X. Liu and K. Zhang, “Partially observable multi-agent reinforcement learning with information sharing,”arXiv preprint arXiv:2308.08705 (SIAM Journal on Control and Optimization (SICON), vol. 64, pp. 673–697, 2026), 2023

    work page arXiv 2026

  15. [15]

    Decentralized stochastic control with partial history sharing: A common information approach,

    A. Nayyar, A. Mahajan, and D. Teneketzis, “Decentralized stochastic control with partial history sharing: A common information approach,”IEEE Trans. Autom. Control, vol. 58, no. 7, pp. 1644– 1658, 2013

    work page 2013

  16. [16]

    Common information based Markov perfect equilibria for stochastic games with asymmetric information: Finite games,

    A. Nayyar, A. Gupta, C. Langbort, and T. Başar, “Common information based Markov perfect equilibria for stochastic games with asymmetric information: Finite games,”IEEE Trans. Autom. Control, vol. 59, pp. 555–570, 2013

    work page 2013

  17. [17]

    Communication and control co-design for networked con- trol systems,

    L. Zhang and D. Hristu-Varsakelis, “Communication and control co-design for networked con- trol systems,”Automatica, vol. 42, no. 6, pp. 953–958, 2006

    work page 2006

  18. [18]

    Communication delay co-design inH 2-distributed control using atomic norm mini- mization,

    N. Matni, “Communication delay co-design inH 2-distributed control using atomic norm mini- mization,”IEEE Trans. Control Netw. Syst., vol. 4, no. 2, pp. 267–278, 2015

    work page 2015

  19. [19]

    Event-triggered communication andH ∞ control co-design for net- worked control systems,

    C. Peng and T. C. Yang, “Event-triggered communication andH ∞ control co-design for net- worked control systems,”Automatica, vol. 49, no. 5, pp. 1326–1332, 2013

    work page 2013

  20. [20]

    Simultaneous design of measurement and control strategies for stochas- tic systems with feedback,

    R. Bansal and T. Başar, “Simultaneous design of measurement and control strategies for stochas- tic systems with feedback,”Automatica, vol. 25, no. 5, pp. 679–694, 1989

    work page 1989

  21. [21]

    The complexity of Markov decision processes,

    C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of Markov decision processes,”Math. Oper. Res., vol. 12, pp. 441–450, 1987

    work page 1987

  22. [22]

    Nonapproximability results for partially observ- able Markov decision processes,

    C. Lusena, J. Goldsmith, and M. Mundhenk, “Nonapproximability results for partially observ- able Markov decision processes,”J. Artif. Intell. Res., pp. 83–103, 2001

    work page 2001

  23. [23]

    Sample-efficient reinforcement learning of undercomplete POMDPs,

    C. Jin, S. Kakade, A. Krishnamurthy, and Q. Liu, “Sample-efficient reinforcement learning of undercomplete POMDPs,” inNeurIPS, 2020

    work page 2020

  24. [24]

    Sample-efficient reinforcement learning of partially observ- able Markov games,

    Q. Liu, C. Szepesvári, and C. Jin, “Sample-efficient reinforcement learning of partially observ- able Markov games,” inNeurIPS, 2022

    work page 2022

  25. [25]

    On the role of information structure in reinforcement learning for partially-observable sequential teams and games,

    A. Altabaa and Z. Yang, “On the role of information structure in reinforcement learning for partially-observable sequential teams and games,” inNeurIPS, 2024

    work page 2024

  26. [26]

    Extensive games and the problem of information,

    H. W. Kuhn, “Extensive games and the problem of information,” inContrib. Theory Games, Vol. II. Princeton Univ. Press, 1953

    work page 1953

  27. [27]

    The intrinsic model for discrete stochastic control: Some open problems,

    H. S. Witsenhausen, “The intrinsic model for discrete stochastic control: Some open problems,” inControl Theory, Numer. Methods Comput. Syst. Model., Int. Symp., Rocquencourt, 1975, pp. 322– 335

    work page 1975

  28. [28]

    Measure and cost dependent properties of information structures,

    A. Mahajan and S. Yüksel, “Measure and cost dependent properties of information structures,” inProc. Amer. Control Conf., 2010, pp. 6397–6402

    work page 2010

  29. [29]

    Planning and learning in partially observable systems via filter stability,

    N. Golowich, A. Moitra, and D. Rohatgi, “Planning and learning in partially observable systems via filter stability,” inProc. 55th Annu. ACM Symp. Theory Comput. (STOC), 2023. 18

    work page 2023

  30. [30]

    The value of observation for monitoring dynamic systems,

    E. Even-Dar, S. M. Kakade, and Y. Mansour, “The value of observation for monitoring dynamic systems,” inProc. Int. Joint Conf. Artif. Intell. (IJCAI), 2007

    work page 2007

  31. [31]

    Team decision theory and information structures in optimal control problems – Part I,

    Y.-C. Hoet al., “Team decision theory and information structures in optimal control problems – Part I,”IEEE Trans. Autom. Control, vol. 17, pp. 15–22, 1972

    work page 1972

  32. [32]

    Optimal decentralized state-feedback control with sparsity and delays,

    A. Lamperski and L. Lessard, “Optimal decentralized state-feedback control with sparsity and delays,”Automatica, pp. 143–151, 2015

    work page 2015

  33. [33]

    On the complexity of decentralized decision making and detection problems,

    J. Tsitsiklis and M. Athans, “On the complexity of decentralized decision making and detection problems,”IEEE Trans. Autom. Control, vol. 30, pp. 440–446, 1985

    work page 1985

  34. [34]

    Learning in observable POMDPs, without computa- tionally intractable oracles,

    N. Golowich, A. Moitra, and D. Rohatgi, “Learning in observable POMDPs, without computa- tionally intractable oracles,” inNeurIPS, 2022, pp. 1458–1473

    work page 2022

  35. [35]

    Convergence of finite memory Q learning for POMDPs and near optimality of learned policies under filter stability,

    A. D. Kara and S. Yüksel, “Convergence of finite memory Q learning for POMDPs and near optimality of learned policies under filter stability,”Mathematics of Operations Research, vol. 48, no. 4, pp. 2066–2093, 2023

    work page 2066

  36. [36]

    Near optimality of finite memory feedback policies in partially observed Markov decision processes,

    A. Kara and S. Yüksel, “Near optimality of finite memory feedback policies in partially observed Markov decision processes,”Journal of Machine Learning Research, vol. 23, no. 11, pp. 1–46, 2022

    work page 2022

  37. [37]

    Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings,

    R. Nair, M. Tambe, M. Yokoo, D. Pynadath, and S. Marsella, “Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings,” inProc. Int. Joint Conf. Artif. In- tell. (IJCAI), 2003

    work page 2003

  38. [38]

    Incremental policy generation for finite-horizon Dec-POMDPs,

    C. Amato, J. Dibangoye, and S. Zilberstein, “Incremental policy generation for finite-horizon Dec-POMDPs,” inProc. Int. Conf. Autom. Plan. Sched. (ICAPS), vol. 19, 2009, pp. 2–9

    work page 2009

  39. [39]

    Filar and K

    J. Filar and K. Vrieze,Competitive Markov decision processes. Springer, 2012

    work page 2012

  40. [40]

    Provable self-play algorithms for competitive reinforcement learning,

    Y. Bai and C. Jin, “Provable self-play algorithms for competitive reinforcement learning,” in ICML, 2020

    work page 2020

  41. [41]

    Solving hierarchical information-sharing Dec-POMDPs: an extensive-form game approach,

    J. Peralez, A. Delage, O. Buffet, and J. S. Dibangoye, “Solving hierarchical information-sharing Dec-POMDPs: an extensive-form game approach,”arXiv preprint arXiv:2402.02954, 2024

    work page arXiv 2024

  42. [42]

    Multiagent systems: Challenges and opportunities for decision-theoretic plan- ning,

    C. Boutilier, “Multiagent systems: Challenges and opportunities for decision-theoretic plan- ning,”AI Magazine, vol. 20, pp. 35–35, 1999. 19 Appendices A. Examples of QC LTC Problems In this section, we introduce 8 examples of QC LTC problems, with 4 of them being extended from the information structures of the baseline sharing protocols considered in the...

    work page 1999

  43. [43]

    For anyh∈[H], the states h can be controlled by one agentct(h), i.e.,T h : S × A ct(h),h →∆(S). Furthermore, the reward function has an additive form, i.e., Rh(sh, ah) = Pn i=1 Ri,h(sh, ai,h), and the increment of the common information satisfies zb h+1 =χ h+1(ph+, act(h),h, oh+1)

    work page

  44. [44]

    Furthermore, the communication cost and reward functions can be decoupled as Kh(za h) =Pn i=1 Ki,h(za i,h),R h(sh, ah) =Pn i=1 Ri,h(si,h, ai,h)

    For anyh∈[H], the states h can be partitioned intonlocal states ass h = (s1,h, s2,h,· · ·, sn,h), and the transition kernel and observation emission have the factor- ized forms ofT h(sh+1 |s h, ah) = Qn i=1 Ti,h(si,h+1 |s i,h, ai,h),O h(oh |s h) = Qn i=1 Oi,h(oi,h |s i,h). Furthermore, the communication cost and reward functions can be decoupled as Kh(za ...

    work page

  45. [45]

    This condition is only applicable toExamples 1and5. For anyh∈[H], the emission Oh satisfies that:∀i < j≤n, o j,h ∈ Oj,h,∃o i,h ∈ Oi,h such that∀s h ∈ S,O {i,j},h (oi,h, oj,h |s h) = Oj,h(oj,h |s h), whereO {i,j},h is the marginalized distribution ofOh with respect to agents iandj. – Example 3:we do not need any additional condition. Remark A.1.The additio...

    work page

  46. [46]

    Ifa i1,t1 influences the underlying states t1+1, then from Assumption III.7, agent (i 1, t1) influences o−i1,t1+1, so there must existi 3 ,i 1, such that agent (i1, t1) influenceso i3,t1+1. From part (e) of Assump- tion II.1 andt1 < t2 (since otherwise agent (i1,2t 1) cannot influence agent (i2,2t 2) inD L), we know that oi3,t1+1 ∈τ i3,(t1+1)− ⊆τ i3,t− 2 ...

    work page

  47. [47]

    Thus eai1,2t1 =a i1,t1 does not influ- ence eτi,2t1+1,∀i∈[n], and then it does not influence eai,2t1+1,∀i∈[n]

    Ifa i1,t1 does not influences t1+1, then from Assumption III.5, for anyt > t 1, ai1,t1 <τ t− anda i1,t1 <τ t+, and then agent (i 1,2t 1) does not influence es2t1+1 and eo2t1+1 inD L. Thus eai1,2t1 =a i1,t1 does not influ- ence eτi,2t1+1,∀i∈[n], and then it does not influence eai,2t1+1,∀i∈[n]. And hence, it does not influence eτi,2t1+2 and eai,2t1+2,∀i∈[n]...

    work page

  48. [48]

    Hence, (g a,∗ 1:H , gm,∗ 1:H) is not anϵ-team-optimal for anyϵ∈[0,1/4)

    Note that the rewards inPare bounded by [0, 1 2], and the rewards inLare bounded by [0, 1 2H ]. Hence, (g a,∗ 1:H , gm,∗ 1:H) is not anϵ-team-optimal for anyϵ∈[0,1/4). Therefore, anyϵ-team-optimal strategy yields no additional sharing. Then, any (g a,∗ 1:H , gm,∗ 1:H) being an ϵ H -team-optimal strategy ofLwill directly give anϵ-optimal strategy ofPas{g a...

    work page

  49. [49]

    The communication cost functions are defined as: ∀h∈ {1,2}, z a h ∈ Z a h,K h(za h) = 1 ifz a h ,{m 1,h, m2,h}, else 0; K3(za

    and (a2,3 =s 1 3 ora 2,3 =s 3 3) 0 o.w. . The communication cost functions are defined as: ∀h∈ {1,2}, z a h ∈ Z a h,K h(za h) = 1 ifz a h ,{m 1,h, m2,h}, else 0; K3(za

    work page

  50. [50]

    , where we letα 0 = maxy1,y2,u1,u2ec(y1, y2, u1, u2), and setα 1 = 2α0, α2 ∈(0,1)

    =  ec(o1 1,3, o1 2,3,1,1)/α 1 if{o 1,1, o2,1} ⊆z a 3 and{o 1,2, o2,2} ∩z a 3 =∅ ec(o1 1,3, o1 2,3,2,1)/α 1 if{o 1,2, o2,1} ⊆z a 3 and{o 1,1, o2,2} ∩z a 3 =∅ ec(o1 1,3, o1 2,3,1,2)/α 1 if{o 1,1, o2,2} ⊆z a 3 and{o 1,2, o2,1} ∩z a 3 =∅ ec(o1 1,3, o1 2,3,2,2)/α 1 if{o 1,2, o2,2} ⊆z a 3 and{o 1,1, o2,1} ∩z a 3 =∅ 0 o.w. , where we letα ...

    work page

  51. [51]

    Letα 0 = maxy1,y2,u1,u2ec(y1, y2, u1, u2), which is supposed to be positive without loss of optimality (see a discussion in §B-C)

    =  ec(o1 1,2, o1 2,2,1,1)/α 1 ifa 1,2, a2,2 ∈z a 3, a1 1,2 = 0, a1 2,2 = 0 ec(o1 1,2, o1 2,2,2,1)/α 1 ifa 1,2, a2,2 ∈z a 3, a2 1,2 = 0, a1 2,2 = 0 ec(o1 1,2, o1 2,2,1,2)/α 1 ifa 1,2, a2,2 ∈z a 3, a1 1,2 = 0, a2 2,2 = 0 ec(o1 1,2, o1 2,2,2,2)/α 1 ifa 1,2, a2,2 ∈z a 3, a2 1,2 = 0, a2 2,2 = 0 0 o.w. . Letα 0 = maxy1,y2,u1,u2ec(y1, y2, ...

    work page

  52. [52]

    𝑐#! 𝑝$,#! 𝑝&,#! 𝑚$,# 𝑚&,# 𝑧$,#' 𝑧&,#' 𝑧#'𝑐#

    Therefore,E[ P3 h=1 κh |(g a,′ 1:3, gm,′ 1:3)]≤E[ P3 h=1 κh |g a,∗ 1:3, gm,∗ 1:3 ], and thusJ L(ga,∗ 1:3, gm,∗ 1:3 )≤J L(ga,′ 1:3, gm,′ 1:3). From the above, we know that (g a,′ 1:3, gm,′ 1:3) is also a team-optimal strategy. LetU 1 =f 1(a1,2) := 2−1[a 1 1,2 = 0], U2 =f 2(a2,2) := 2−1[a 1 2,2 = 0], thenJ L(ga,′ 1:3, gm,′ 1:3) =E[ P3 h=1 rh −κ h |g a,′ 1:3...

    work page