COLA: Consistent Learning with Opponent-Learning Awareness
  Learning in general-sum games can be unstable and often leads to socially
undesirable, Pareto-dominated outcomes. To mitigate this, Learning with
Opponent-Learning Awareness (LOLA) introduced opponent shaping to this setting,
by accounting for the agent's influence on the anticipated learning steps of
other agents. However, the original LOLA formulation (and follow-up work) is
inconsistent because LOLA models other agents as naive learners rather than
LOLA agents. In previous work, this inconsistency was suggested as a cause of
LOLA's failure to preserve stable fixed points (SFPs). First, we formalize
consistency and show that higher-order LOLA (HOLA) solves LOLA's inconsistency
problem if it converges. Second, we correct a claim made in the literature, by
proving that, contrary to Sch\"afer and Anandkumar (2019), Competitive Gradient
Descent (CGD) does not recover HOLA as a series expansion. Hence, CGD also does
not solve the consistency problem. Third, we propose a new method called
Consistent LOLA (COLA), which learns update functions that are consistent under
mutual opponent shaping. It requires no more than second-order derivatives and
learns consistent update functions even when HOLA fails to converge. However,
we also prove that even consistent update functions do not preserve SFPs,
contradicting the hypothesis that this shortcoming is caused by LOLA's
inconsistency. Finally, in an empirical evaluation on a set of general-sum
games, we find that COLA finds prosocial solutions and that it converges under
a wider range of learning rates than HOLA and LOLA. We support the latter
finding with a theoretical result for a simple game.
