Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Relational ReasoningSimilar Papers 제목 키워드 기반
Abstractors and relational cross-attention: An inductive bias for explicit relational reasoning in Transformers
An extension of Transformers is proposed that enables explicit relational reasoning through a novel module called the Abstractor. At the core of the Abstractor is a variant of attention called relational cross-attention.…
Inductive BiasMathematical Problem-SolvingRelational ReasoningWhen can transformers reason with abstract symbols?
We investigate the capabilities of transformer models on relational reasoning tasks. In these tasks, models are trained on a set of strings encoding abstract relations, and are then tested out-of-distribution on data tha…
Relational ReasoningDisentangling and Integrating Relational and Sensory Information in Transformer Architectures
Relational reasoning is a central component of generally intelligent systems, enabling robust and data-efficient inductive generalization. Recent empirical evidence shows that many existing neural architectures, includin…
Information RetrievalLanguage ModelingLanguage ModellingRelational Reasoning+1Polynomial-Time Relational Probabilistic Inference in Open Universes
Reasoning under uncertainty is a fundamental challenge in Artificial Intelligence. As with most of these challenges, there is a harsh dilemma between the expressive power of the language used, and the tractability of the…
Relational Attention: Generalizing Transformers for Graph-Structured Tasks
Transformers flexibly operate over sets of real-valued vectors representing task-specific entities and their attributes, where each vector might encode one word-piece token and its position in a sequence, or some piece o…
Position