While single-agent policy optimization in a fixed environment has attracted a lot of research attention recently in the reinforcement learning community, much less is known theoretically when there are multiple agents playing in a potentially competitive environment. We take steps forward by proposing and analyzing new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We consider two classes of transition structures: factored independent transition and single-controller transition. For both scenarios, we prove tight $\widetilde{\mathcal{O}}(\sqrt{K})$ regret bounds after $K$ episodes in a two-agent competitive game scenario. The regret of each agent is measured against a potentially adversarial opponent who can choose a single best policy in hindsight after observing the full policy sequence. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization in a non-stationary environment. When both players adopt the proposed algorithms, their overall optimality gap is $\widetilde{\mathcal{O}}(\sqrt{K})$.

本研究在多智能体竞争的环境下对零和结构化Markov博弈问题的策略优化算法进行了提出和分析，考虑通过上置界乐观算法与虚拟博弈相结合的同时策略优化，从而使双方智能体的总体最优性差距以$\widetilde{O}(\sqrt{K})$的速度收敛，其中$K$为回合数量。

具有结构转移的零和马尔可夫博弈中可证明有效的虚拟博弈策略优化