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.


    Access

    Download


    Export, share and cite



    Title :

    Tesseract: tensorised actors for multi−agent reinforcement learning


    Contributors:
    Mahajan, A (author) / Samvelyan, M (author) / Mao, L (author) / Makoviychuk, V (author) / Garg, A (author) / Kossaif, J (author) / Whiteson, S (author) / Zhu, Y (author) / Anandkumar, A (author)

    Publication date :

    2021-07-26


    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629



    Tesseract: Supersonic business transport

    Reshotko, Eli / Garbinski, Gary | NTRS | 1992


    Tesseract supersonic business transport

    Reshotko, Eli / Garbinski, Gary / Fellenstein, James et al. | NTRS | 1992


    Tesseract: Supersonic Business Transport

    E. Reshotko / G. Garbinski | NTIS | 1992


    Tesseract Supersonic Business Transport

    E. Reshotko / G. Garbinski / J. Fellenstein et al. | NTIS | 1992


    Character Recognition using Tesseract enabling Multilingualism

    Niharika, Gorsa Lakshmi / Bano, Shahana / Kumar, Pavuluri Shyam et al. | IEEE | 2020