It can be seen that a rational algorithm has different benefits compared to a convergent algorithm – the former satisfies individual player's interests, while the latter might be better for achieving social good. Therefore, a single algorithm that possesses both properties is highly desirable. For example, in a market where “enforcing” all traders to follow the same rule is difficult, but “recommending” them to use a specific algorithm is possible, a rational and convergent algorithm would be a good candidate — if all traders follow the recommendation, then a social equilibrium is quickly attained; otherwise, those who follow the recommendation are still satisfied because they best respond to a stationary environment.
Based on this motivation, our main contribution is to develop the first decentralized algorithm that is simultaneously rational, last-iterate convergent (with a concrete finite-time guarantee),Note that while average-iterate convergence is possible (and standard) for stateless convex-concave games (e.g. [1]}), it does not work for Markov games since the problem is nonconvex-nonconcave in the space of policies [2]}. agnostic, and symmetric (more details to follow in subsec: related work) for two-player zero-sum Markov games.
Our algorithm is based on Optimistic Gradient Descent/Ascent (OGDA) [3]}, [4]} and importantly relies on a critic that slowly learns a certain value function for each state.
Following previous works on learning MDPs [5]}, [6]} or Markov games [7]},
we present the convergence guarantee in terms of the number of iterations of the algorithm and the estimation error of some gradient information (along with other problem-dependent constants),
where the estimation error can be zero in a full-information setting, or goes down to zero fast enough with additional structural assumptions (e.g. every stationary policy pair induces an irreducible Markov chain, similar to [8]}).
