从专家数据学习博弈均衡，首次给出样本复杂度理论分析。
Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning
- 引入新系数刻画单策略偏差的集中性，影响模仿学习性能。
- 提出两种新算法，分别需 $\mathcal{O}(\varepsilon^{-4})$ 和 $\mathcal{O}(\varepsilon^{-8})$ 次专家查询。
- 理论与实验结合，适用于多智能体强化学习研究者。
本文首次对马尔可夫博弈中从专家数据学习纳什均衡的样本复杂度进行了理论刻画。我们证明，在非交互式模仿学习设定下，一个名为单策略偏差集中系数的新量是不可避免的，并给出了包含该系数的行为克隆（BC）上界。在高集中系数的博弈中，BC表现出显著遗憾。为此，我们利用专家查询，提出了两种新颖的算法：MAIL-BRO 和 MURMAIL。前者使用最优回应预言机，以 $\mathcal{O}(\varepsilon^{-4})$ 次专家和预言机查询学习到 $\varepsilon$-纳什均衡；后者完全避免最优回应预言机，但专家查询复杂度上升至 $\mathcal{O}(\varepsilon^{-8})$。最后，我们提供了数值证据，验证了理论结论。
原文摘要 · Abstract (English)
This paper provides the first expert sample complexity characterization for learning a Nash equilibrium from expert data in Markov Games. We show that a new quantity named the single policy deviation concentrability coefficient is unavoidable in the non-interactive imitation learning setting, and we provide an upper bound for behavioral cloning (BC) featuring such coefficient. BC exhibits substantial regret in games with high concentrability coefficient, leading us to utilize expert queries to develop and introduce two novel solution algorithms: MAIL-BRO and MURMAIL. The former employs a best response oracle and learns an $\varepsilon$-Nash equilibrium with $\mathcal{O}(\varepsilon^{-4})$ expert and oracle queries. The latter bypasses completely the best response oracle at the cost of a worse expert query complexity of order $\mathcal{O}(\varepsilon^{-8})$. Finally, we provide numerical evidence, confirming our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。