eess.SYMar 4, 2026

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

Authors: Xiangyu Liu, Haoyi You, Kaiqing Zhang

Organizations: University of Maryland, College Park, MD, USA, 20742

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1: Illustrating the subroutines for solving the LTC problems.
Figure 2: (a) Venn diagram of LTCs with different ISs: ① QC LTCs. ② QC LTCs satisfying Assumptions 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 .
Horizon/CostNo SharingCost=0.1Cost=0.05Cost=0.01Fully Sharing
H=4 w/ cost1.32 ±\pm 0.0251.33 ±\pm 0.0441.44 ±\pm 0.0341.54 ±\pm 0.0131.57 ±\pm 0.004
H=4 w/o cost-1.36 ±\pm 0.0321.48 ±\pm 0.0341.59 ±\pm 0.002-
H=6 w/ cost1.95 ±\pm 0.0091.97 ±\pm 0.072.08 ±\pm 0.0682.26 ±\pm 0.0122.29 ±\pm 0.002
H=6 w/o cost-2.01 ±\pm 0.0472.14 ±\pm 0.0722.27 ±\pm 0.011-
H=8 w/ cost2.56 ±\pm 0.0412.64 ±\pm 0.0782.74 ±\pm 0.1182.96 ±\pm 0.0213.0 ±\pm 0.002
H=8 w/o cost-2.7 ±\pm 0.0442.83 ±\pm 0.1172.98 ±\pm 0.02-
Table 1: Experimental results for Dectiger with different horizon lengths and cost functions.
Horizon/CostNo SharingCost=0.1Cost=0.05Cost=0.01Fully Sharing
H=4 w/ cost0.14 ±\pm 0.0030.14 ±\pm 0.0190.15 ±\pm 0.0020.26 ±\pm 0.0280.48 ±\pm 0.023
H=4 w/o cost-0.14 ±\pm 0.0190.21 ±\pm 0.0070.33 ±\pm 0.023-
H=6 w/ cost0.33 ±\pm 0.020.32 ±\pm 0.0250.4 ±\pm 0.0090.48 ±\pm 0.0590.38 ±\pm 0.075
H=6 w/o cost-0.32 ±\pm 0.0250.54 ±\pm 0.020.62 ±\pm 0.075-
H=8 w/ cost0.52 ±\pm 0.0840.52 ±\pm 0.0510.58 ±\pm 0.0720.67 ±\pm 0.0310.4 ±\pm 0.022
H=8 w/o cost-0.52 ±\pm 0.0510.72 ±\pm 0.0350.82 ±\pm 0.074-
Table 2: Experimental results for Grid3x3 with different horizon lengths and cost functions.
Figure 3: The time-average values achieved under different communication costs and horizons. For each bar, the dark portion and the light portion correspond to the values associated with the communication cost and the overall objective (reward minus cost) of the agents, respectively; the full bar corresponds to the values associated with the reward.
Figure 4: Learning curves, i.e., the values associated with the overall objective (reward minus cost) achieved during learning, under different communication costs.
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

 (g^1,h∗(⋅ ∣ c^h,⋅),⋯ ,g^n,h∗(⋅ ∣ c^h,⋅))←argmaxγ1:n,h∈ΓhQh∗,M(c^h,γ1,h,⋯ ,γn,h)\displaystyle\left(\widehat{g}_{1,h}^{\ast}(\cdot{\,|\,}\widehat{c}_{h},\cdot),\cdots,\widehat{g}_{n,h}^{\ast}(\cdot{\,|\,}\widehat{c}_{h},\cdot)\right)\leftarrow\mathop{\mathrm{argmax}}_{\gamma_{1:n,h}\in\Gamma_{h}}Q^{\ast,\mathcal{M}}_{h}(\widehat{c}_{h},\gamma_{1,h},\cdots,\gamma_{n,h}) (E.1)
Appendix
Algorithm 6 Planning in Dec-POMDPs with Expected Approximate Common-information Model
Figure 5: Illustrating the learning-to-communicate problem considered in this paper.
More in this topic

Multi-Agent Communication

Multi-agent communication studies how autonomous agents exchange information to coordinate decisions, share knowledge, and act together under constraints.

See all 375 papers

Explore similar work

CardsList
Mar 27, 2026

On the Reliability Limits of LLM-Based Multi-Agent Planning

This technical note studies the reliability limits of LLM-based multi-agent planning as a delegated decision problem. We model the LLM-based multi-agent architecture as a finite acyclic decision network in which multiple stages process shared model-context information, communicate through language interfaces with limited capacity, and may invoke human review. We show that, without new exogenous signals, any delegated network is decision-theoretically dominated by a centralized Bayes decision maker with access to the same information. In the common-evidence regime, this implies that optimizing over multi-agent directed acyclic graphs under a finite communication budget can be recast as choosing a budget-constrained stochastic experiment on the shared signal. We also characterize the loss induced by communication and information compression. Under proper scoring rules, the gap between the centralized Bayes value and the value after communication admits an expected posterior divergence representation, which reduces to conditional mutual information under logarithmic loss and to expected squared posterior error under the Brier score. These results characterize the fundamental reliability limits of delegated LLM planning. Experiments with LLMs on a controlled problem set further demonstrate these characterizations.

Ruicheng Ao, Siyang Gao, David Simchi-Levi

Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139. · Department of Systems Engineering, City University of Hong Kong, Kowloon, Hong Kong. · Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, MA 02139. +1

LLM Agent ReliabilityMulti-Agent LLM SystemsMulti-Agent PlanningMulti-Agent Communication
AskPDF
Aug 13, 2026

Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry

We study decentralized multi-player reinforcement learning in episodic tabular Markov decision processes (MDPs) under three forms of information asymmetry: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards. Players cannot communicate during learning but may agree on a protocol a priori. For Problems A and B we propose mQ-learning and mQ-learning-intervals, achieving O~(H4SAjoint T)\tilde{O}(\sqrt{H^4 S A_{\text{joint}}\, T}) regret, where HH is the horizon, SS the state count, T=KHT = KH the total steps, and Ajoint=∏i=1M∣Ai∣A_{\text{joint}} = \prod_{i=1}^M |\mathcal{A}_i| the joint action space across MM players. For Problem C we give mEXC and mEXC-Bellman, two-phase explore-then-commit algorithms with regret O~(H(SAjoint)1/3T2/3)\tilde{O}(H (S A_{\text{joint}})^{1/3} T^{2/3}). Against the centralized joint-action benchmark, decentralized learning under information asymmetry matches the single-agent Q-learning rate of \cite{jin2018q} up to logarithmic factors. Because AjointA_{\text{joint}} grows exponentially in MM, the bounds are most meaningful for small MM or small per-player action sets.

Larissa Xu, King Bi, William Chang

Department of Mathematics University of California, Los Angeles Los Angeles, USA · Department of Computer Science University of California, Los Angeles Los Angeles, USA

Regret Minimization in RLReinforcement LearningQ-LearningDecentralized MARLMulti-Agent Reinforcement Learning
AskPDF
Aug 13, 2026

Joint Communication-Control Strategy Optimization with Partially Nested Information Structures: The Linear-Quadratic Case

In this paper, we formalize a joint communication-control strategy optimization (JCCO) problem in multi-agent linear systems with quadratic costs, under the common-information-based (CIB) framework from decentralized stochastic control. For computational tractability, we focus on such JCCO problems with partially nested (PN) information structures (ISs). In particular, with a baseline communication protocol that leads to a PN IS, we establish a series of conditions under which the partial nestedness is preserved under the (additional) communication strategies to be optimized, while violating them may cause nonlinearity of the optimal strategies in general, with open-loop communication strategies. We then develop a dynamic-programming-based approach to compute the optimal control strategies of JCCO with open-loop communication strategies, which yields a set of closed-form Riccati Equations. As a byproduct of independent interest, such an approach also offers a way to solve decentralized linear-quadratic control with PN ISs and output feedback, under the CIB framework. Finally, we extend such an approach to JCCOs with closed-loop communication strategies, yielding a more tractable dynamic program than an infinite-dimensional CIB-belief-based one.

Haoyi You, Kaiqing Zhang

University of Maryland, College Park, MD, USA, 20742.

Stochastic Optimal Control
AskPDF