To fix this issue, the work of [1]} argues that a desirable multi-agent learning algorithm should have the following two properties simultaneously: rational and convergent. By their definition, a rational algorithm converges to its
opponent's best response if the opponent converges to a stationary policy,It is tempting to consider an even stronger rationality notion, that is, having no regret against an arbitrary opponent. This is, however, known to be computationally hard [2]}, [3]}.
while a convergent algorithm converges to a Nash equilibrium if both agents use it. They propose the WoLF (Win-or-Learn-Fast) algorithm to achieve this goal, albeit only with empirical evidence. Subsequently, [4]}, [5]}, [6]} design decentralized algorithms that provably enjoy these two properties, but only with asymptotic guarantees.
