Over-generalization is a thorny issue in cognitive science, where people may
become overly cautious due to past experiences. Agents in multi-agent
reinforcement learning (MARL) also have been found to suffer relative
over-generalization (RO) as people do and stuck to sub-optimal cooperation.
Recent methods have shown that assigning reasoning ability to agents can
mitigate RO algorithmically and empirically, but there has been a lack of
theoretical understanding of RO, let alone designing provably RO-free methods.
This paper first proves that RO can be avoided when the MARL method satisfies a
consistent reasoning requirement under certain conditions. Then we introduce a
novel reasoning framework, called negotiated reasoning, that first builds the
connection between reasoning and RO with theoretical justifications. After
that, we propose an instantiated algorithm, Stein variational negotiated
reasoning (SVNR), which uses Stein variational gradient descent to derive a
negotiation policy that provably avoids RO in MARL under maximum entropy policy
iteration. The method is further parameterized with neural networks for
amortized learning, making computation efficient. Numerical experiments on many
RO-challenged environments demonstrate the superiority and efficiency of SVNR
compared to state-of-the-art methods in addressing RO.

本文提出了一种新的协商推理框架和实例化算法 Stein 变分协商推理 (SVNR)，其使用 Stein 变分梯度下降来导出一种协商政策，以便在最大熵策略迭代下在多智能体强化学习中避免 RO 。对许多 RO 挑战环境的数值实验证明了 SVNR 在解决 RO 中的卓越性和效率。