  Efficient exploration strategy is one of essential issues in cooperative
multi-agent reinforcement learning (MARL) algorithms requiring complex
coordination. In this study, we introduce a new exploration method with the
strangeness that can be easily incorporated into any centralized training and
decentralized execution (CTDE)-based MARL algorithms. The strangeness refers to
the degree of unfamiliarity of the observations that an agent visits. In order
to give the observation strangeness a global perspective, it is also augmented
with the the degree of unfamiliarity of the visited entire state. The
exploration bonus is obtained from the strangeness and the proposed exploration
method is not much affected by stochastic transitions commonly observed in MARL
tasks. To prevent a high exploration bonus from making the MARL training
insensitive to extrinsic rewards, we also propose a separate action-value
function trained by both extrinsic reward and exploration bonus, on which a
behavioral policy to generate transitions is designed based. It makes the
CTDE-based MARL algorithms more stable when they are used with an exploration
method. Through a comparative evaluation in didactic examples and the StarCraft
Multi-Agent Challenge, we show that the proposed exploration method achieves
significant performance improvement in the CTDE-based MARL algorithms.
