Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning

这项工作设计并分析了一组新颖的多智能体强化学习（MARL）算法，基于信息导向采样（IDS）原则。这些算法受到信息论基本概念的启发，并被证明在MARL设置中具有样本效率，例如两人零和马尔可夫博弈（MGs）和多人一般和MGs。对于情节性的两人零和MGs，我们提出了三种样本效率高的算法来学习纳什均衡。基本算法被称为MAIDS，采用不对称学习结构，其中最大玩家首先基于联合策略的联合信息比解决了极小化最大化优化问题，然后最小玩家在最大玩家的策略固定的情况下最小化边际信息比。理论分析表明，它在K个情节下实现了tilde{O}(sqrt{K})的贝叶斯遗憾。为了减少MAIDS的计算负担，我们开发了一种改进算法Reg-MAIDS，它具有相同的贝叶斯遗憾界，同时享有更少的计算复杂性。此外，通过利用IDS原则在选择学习目标方面的灵活性，我们提出了两种基于速率失真理论构建压缩环境的方法，其中我们开发了一种算法Compressed-MAIDS，其中学习目标是一个压缩环境。最后，我们将Reg-MAIDS扩展到多人一般和MGs，并证明它可以以样本有效的方式学习纳什均衡或粗略相关均衡。

本文旨在设计和分析基于信息导向采样原则的多智能体强化学习（MARL）算法，解决多智能体强化学习中的样本效率问题。

该算法利用信息论中的基本概念，设计了针对两人零和马尔科夫博弈和多人广义和马尔科夫博弈的样本效率算法，并通过理论分析证明了算法的有效性。

论文提出了三种用于学习纳什均衡的样本效率算法，并提出了基于率失真理论的压缩环境构建方法，开发了压缩-MAIDS算法。此外，论文还将Reg-MAIDS算法扩展到多人广义和马尔科夫博弈，并证明它可以在样本效率方面学习纳什均衡或粗略相关均衡。

近期的相关研究包括：Deep Reinforcement Learning for Multi-Agent Systems: A Review和Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms等。