  Fully decentralized learning, where the global information, i.e., the actions
of other agents, is inaccessible, is a fundamental challenge in cooperative
multi-agent reinforcement learning. However, the convergence and optimality of
most decentralized algorithms are not theoretically guaranteed, since the
transition probabilities are non-stationary as all agents are updating policies
simultaneously. To tackle this challenge, we propose best possible operator, a
novel decentralized operator, and prove that the policies of agents will
converge to the optimal joint policy if each agent independently updates its
individual state-action value by the operator. Further, to make the update more
efficient and practical, we simplify the operator and prove that the
convergence and optimality still hold with the simplified one. By instantiating
the simplified operator, the derived fully decentralized algorithm, best
possible Q-learning (BQL), does not suffer from non-stationarity. Empirically,
we show that BQL achieves remarkable improvement over baselines in a variety of
cooperative multi-agent tasks.
