  Value function decomposition is becoming a popular rule of thumb for scaling
up multi-agent reinforcement learning (MARL) in cooperative games. For such a
decomposition rule to hold, the assumption of the individual-global max (IGM)
principle must be made; that is, the local maxima on the decomposed value
function per every agent must amount to the global maximum on the joint value
function. This principle, however, does not have to hold in general. As a
result, the applicability of value decomposition algorithms is concealed and
their corresponding convergence properties remain unknown. In this paper, we
make the first effort to answer these questions. Specifically, we introduce the
set of cooperative games in which the value decomposition methods find their
validity, which is referred as decomposable games. In decomposable games, we
theoretically prove that applying the multi-agent fitted Q-Iteration algorithm
(MA-FQI) will lead to an optimal Q-function. In non-decomposable games, the
estimated Q-function by MA-FQI can still converge to the optimum under the
circumstance that the Q-function needs projecting into the decomposable
function space at each iteration. In both settings, we consider value function
representations by practical deep neural networks and derive their
corresponding convergence rates. To summarize, our results, for the first time,
offer theoretical insights for MARL practitioners in terms of when value
decomposition algorithms converge and why they perform well.
