mlsanityData to 7 Oct 2026

Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL

arXiv 2209.09845 ↗First posted 20 Sep 2022cs.LG cs.MA stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

The cooperative Multi-A gent R einforcement Learning (MARL) with permutation invariant agents framework has achieved tremendous empirical successes in real-world applications. Unfortunately, the theoretical understanding of this MARL problem is lacking due to the curse of many agents and the limited exploration of the relational reasoning in existing works. In this paper, we verify that the transformer implements complex relational reasoning, and we propose and analyze model-free and model-based offline MARL algorithms with the transformer approximators. We prove that the suboptimality gaps of the model-free and model-based algorithms are independent of and logarithmic in the number of agents respectively, which mitigates the curse of many agents. These results are consequences of a novel generalization error bound of the transformer and a novel analysis of the Maximum Likelihood Estimate (MLE) of the system dynamics with the transformer. Our model-based algorithm is the first provably efficient MARL algorithm that explicitly exploits the permutation invariance of the agents. Our improved generalization bound may be of independent interest and is applicable to other regression problems related to the transformer beyond MARL.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 37 of its 64 references that are in the map. First posted on arXiv 20 Sep 2022.

Builds on

37 of 64 references.

References · 37

  1. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  2. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  3. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  4. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  5. 2017Deep Setscited by 1,394
  6. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  7. 2021Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNetcited by 1,096
  8. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  9. 2018MINE: Mutual Information Neural Estimationcited by 680
  10. 2021Intriguing Properties of Vision Transformerscited by 446
  11. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  12. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
25 more
  1. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  3. 2017Emergence of Grounded Compositional Language in Multi-Agent Populationscited by 257
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  7. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  8. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  9. 2020Toward the Fundamental Limits of Imitation Learningcited by 96
  10. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  11. 2022SO(2)-Equivariant Reinforcement Learningcited by 79
  12. 2015Neural Network with Unbounded Activation Functions is Universal Approximatorcited by 63
  13. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  14. 2021Equivariant Q Learning in Spatial Action Spacescited by 61
  15. 2021The Sensory Neuron as a Transformer: Permutation-Invariant Neural Networks for Reinforcement Learningcited by 50
  16. 2018Generalization Error in Deep Learningcited by 46
  17. 2019PIC: Permutation Invariant Critic for Multi-Agent Deep Reinforcement Learningcited by 46
  18. 2016Generalization Error of Invariant Classifierscited by 42
  19. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  20. 2019Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spacescited by 34
  21. 2014On the folded normal distributioncited by 31
  22. 2021Understanding the Generalization Benefit of Model Invariance from a Data Perspectivecited by 22
  23. 2017Deep Reinforcement Learning for Event-Driven Multi-Agent Decision Processescited by 21
  24. 2020Breaking the Curse of Many Agents: Provable Mean Embedding Q-Iteration for Mean-Field Reinforcement Learningcited by 19
  25. 2021Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approachcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 3; 2025: 4; 2026: 1.

12 papers.

  1. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 112
  2. 2024Chain of Preference Optimization: Improving Chain-of-Thought Reasoning in LLMscited by 94
  3. 2025LongSpec: Long-Context Lossless Speculative Decoding with Efficient Drafting and Verificationcited by 19
  4. 2022An Analysis of Attention via the Lens of Exchangeability and Latent Variable Modelscited by 15
  5. 2023Transformers in Reinforcement Learning: A Surveycited by 11
  6. 2024LightTransfer: Your Long-Context LLM is Secretly a Hybrid Model with Effortless Adaptationcited by 11
  7. 2023Learning multi-modal generative models with permutation-invariant encoders and tighter variational objectivescited by 4
  8. 2025Advances in Set Function Learning: A Survey of Techniques and Applicationscited by 3
  9. 2024Towards Better Understanding of In-Context Learning Ability from In-Context Uncertainty Quantificationcited by 2
  10. 2025Multi-level Advantage Credit Assignment for Cooperative Multi-Agent Reinforcement Learningcited by 2
  11. 2026Puzzle it Out: Local-to-Global World Model for Offline Multi-Agent Reinforcement Learningcited by 2
  12. 2025Topology Enhanced MARL for Multi-Agent Cooperative Decision-Making of CAVscited by 1