Is Learning in Games Good for the Learners?

Understand

We consider a number of questions related to tradeoffs between reward and regret in repeated gameplay between two agents.

• To facilitate this, we introduce a notion of $\textit{generalized equilibrium}$ which allows for asymmetric regret constraints, and yields polytopes of feasible values for each agent and pair of regret constraints, where we show that any such equilibrium is reachable by a pair of algorithms which maintain their regret guarantees against arbitrary opponents.
• As a central example, we highlight the case one agent is no-swap and the other's regret is unconstrained.
• We show that this captures an extension of $\textit{Stackelberg}$ equilibria with a matching optimal value, and that there exists a wide class of games where a player can significantly increase their utility by deviating from a no-swap-regret algorithm against a no-swap learner (in fact, almost any game without pure Nash equilibria is of this form).