Regret Minimization with Adaptive Opponents in Repeated Games

In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents whose strategies may depend on the histories of play. The classical online learning metric of \emph{external regret} does not fully capture such adaptivity, since it compares against decisions while treating the loss sequence as fixed. To account for the counterfactual reasoning of the players, we introduce a new metric, \texttt{Repeated Policy Regret (RP-Regret)}, specific to this game-theoretic setting, which measures the difference between the \emph{realized} and the \emph{best-in-hindsight} accumulated utility when all players can \emph{respond} to the history of play. Compared with existing regret notions in adaptive environments, \texttt{RP-Regret} allows stronger dynamic comparators and less restricted opponents, while still enabling the learning of better equilibria when all players minimize it. We first identify necessary conditions for achieving sublinear \texttt{RP-Regret}. The comparator strategies must have sublinear accumulated variation, and both the comparator and the opponents must have imperfect recall. Without these conditions, sublinear \texttt{RP-Regret} is impossible to achieve in general. We then provide additional sufficient conditions and algorithms for minimizing \texttt{RP-Regret}. A key challenge is that \texttt{RP-Regret} is \emph{nonconvex} in the strategy space by definition. We address this challenge through three approaches. The first approach uses a nonconvex optimization oracle, as in prior work on online nonconvex learning. The second approach minimizes a convex \emph{linearized} surrogate at each iteration, which yields the minimization of a local variant of \texttt{RP-Regret}. The third approach directly minimizes \texttt{RP-Regret} when the opponents change their strategies slowly, by reformulating the repeated game as a Markov game and optimizing over occupancy measures. Finally, we show that when all players can run algorithms to mini