We study provable multi-agent reinforcement learning (MARL) in the general
framework of partially observable stochastic games (POSGs). To circumvent the
known hardness results and the use of computationally intractable oracles, we
advocate leveraging the potential \emph{information-sharing} among agents, a
common practice in empirical MARL, and a standard model for multi-agent control
systems with communications. We first establish several computation complexity
results to justify the necessity of information-sharing, as well as the
observability assumption that has enabled quasi-efficient single-agent RL with
partial observations, for computational efficiency in solving POSGs. We then
propose to further \emph{approximate} the shared common information to
construct an {approximate model} of the POSG, in which planning an approximate
equilibrium (in terms of solving the original POSG) can be quasi-efficient,
i.e., of quasi-polynomial-time, under the aforementioned assumptions.
Furthermore, we develop a partially observable MARL algorithm that is both
statistically and computationally quasi-efficient. We hope our study may open
up the possibilities of leveraging and even designing different
\emph{information structures}, for developing both sample- and
computation-efficient partially observable MARL.

我们研究了部分可观察随机博弈的可证明多智能体强化学习 (MARL)。我们主张利用智能体之间的信息共享，在可观察性假设的情况下构建一个近似模型来规划近似均衡，并开发了一种具有统计和计算上拟效率的部分可观察 MARL 算法。