Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus

2022/06/01 by Qiwen Cui, Simon S. Du, Cui, Qiwen +1 · 2 citations
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Multiagent Systems (cs.MA) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2206.00159

openalex publication_date 2022/06/01 · openalex created_date 2023/02/13 · openalex updated_date 2026/07/28

Abstract

This paper considers offline multi-agent reinforcement learning. We propose the strategy-wise concentration principle which directly builds a confidence interval for the joint strategy, in contrast to the point-wise concentration principle that builds a confidence interval for each point in the joint action space. For two-player zero-sum Markov games, by exploiting the convexity of the strategy-wise bonus, we propose a computationally efficient algorithm whose sample complexity enjoys a better dependency on the number of actions than the prior methods based on the point-wise bonus. Furthermore, for offline multi-agent general-sum Markov games, based on the strategy-wise bonus and a novel surrogate function, we give the first algorithm whose sample complexity only scales ∑_i=1^mA_i where A_i is the action size of the i-th player and m is the number of players. In sharp contrast, the sample complexity of methods based on the point-wise bonus would scale with the size of the joint action space Π_i=1^m A_i due to the curse of multiagents. Lastly, all of our algorithms can naturally take a pre-specified strategy class Π as input and output a strategy that is close to the best strategy in Π. In this setting, the sample complexity only scales with log |Π| instead of ∑_i=1^mA_i.

Cited by

• Rate optimal learning of equilibria from data
• Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees

Related

• Offline Learning in Markov Games with General Function Approximation
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play