Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2021 | Published + Supplemental Material + Accepted Version
Journal Article Open

Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning

Abstract

Reinforcement Learning in large action spaces is a challenging problem. This is especially true for cooperative multi-agent reinforcement learning (MARL), which often requires tractable learning while respecting various constraints like communication budget and information about other agents. In this work, we focus on the fundamental hurdle affecting both value-based and policy-gradient approaches: an exponential blowup of the action space with the number of agents. For value-based methods, it poses challenges in accurately representing the optimal value function for value-based methods, thus inducing suboptimality. For policy gradient methods, it renders the critic ineffective and exacerbates the problem of the lagging critic. We show that from a learning theory perspective, both problems can be addressed by accurately representing the associated action-value function with a low-complexity hypothesis class. This requires accurately modelling the agent interactions in a sample efficient way. To this end, we propose a novel tensorised formulation of the Bellman equation. This gives rise to our method Tesseract, which utilises the view of Q-function seen as a tensor where the modes correspond to action spaces of different agents. Algorithms derived from Tesseract decompose the Q-tensor across the agents and utilise low-rank tensor approximations to model the agent interactions relevant to the task. We provide PAC analysis for Tesseract based algorithms and highlight their relevance to the class of rich observation MDPs. Empirical results in different domains confirm the gains in sample efficiency using Tesseract as supported by the theory.

Additional Information

© 2021 The authors. AM is funded by the J.P. Morgan A.I. fellowship. Part of this work was done during AM's internship at NVIDIA. This project has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation programme (grant agreement number 637713). The experiments were made possible by generous equipment grant from NVIDIA.

Attached Files

Published - mahajan21a.pdf

Accepted Version - 2106.00136.pdf

Supplemental Material - mahajan21a-supp.pdf

Files

mahajan21a.pdf
Files (6.7 MB)
Name Size Download all
md5:45f7785a77641b402d57041f578e3339
851.9 kB Preview Download
md5:19fd6daf552d18c737e1889d5a6d2227
3.0 MB Preview Download
md5:5d8233213dd491d6f44d09be81e0c2da
2.9 MB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023