반복 게임에서 적응형 상대방을 고려한 후회 최소화

Regret Minimization with Adaptive Opponents in Repeated Games

본 논문에서는 플레이 기록에 기반하여 반응할 수 있는 extit{적응형} 상대방이 존재하는 반복 게임에서의 후회 최소화를 연구합니다. 온라인 학습의 표준적인 지표인 extit{외부 후회(external regret)}는 이러한 적응성을 제대로 반영하지 못하는 것으로 알려져 있습니다. 플레이어들의 반사실적 추론을 고려하기 위해, 본 논문에서는 모든 플레이어가 플레이 기록에 extit{반응}할 수 있을 때, 실제로 얻은 누적 효용과 extit{사후 최적} 효용 간의 차이를 측정하는 게임 이론적 지표인 { t Repeated Policy Regret (RP-Regret)}를 제안합니다. 기존의 후회 개념과는 달리, 본 연구에서 제시하는 방법은 반복 게임 플레이에 특화되어 있으며, 더 강력한 비교 기준과 제약을 완화된 상대방을 가능하게 하면서 모든 플레이어가 이를 최소화할 때 더 나은 균형을 찾는 가능성을 유지합니다. 먼저, 시간 경과에 따라 { t RP-Regret}이 선형적으로 증가하도록 하기 위한 조건, 즉 플레이어의 비교 전략 변화와 비교자 및 상대방 전략의 기억 측면에서의 조건을 분석합니다. 그런 다음, { t RP-Regret}를 최소화하기 위한 추가적인 조건과 검증 가능한 알고리즘을 연구합니다. 여기서 제시하는 { t RP-Regret}는 본질적으로 전략 공간에서 extit{비선형(non-convex)}입니다. 이러한 문제를 해결하기 위해, 다음과 같은 세 가지 알고리즘을 제안합니다: (i) 일부 기존의 온라인 비선형 학습 연구에서 가정하는 최적화 오라클 기반 알고리즘; (ii) 각 반복 단계에서 { t RP-Regret}의 볼록하고 extit{선형화된(linearized)} 근사값을 최소화하는 알고리즘; (iii) 상대방이 전략을 느리게 변경할 때, 직접적으로 { t RP-Regret}를 최소화하는 알고리즘. 또한, 모든 플레이어가 { t RP-Regret}(또는 그 선형화된 변형)를 최소화하는 알고리즘을 실행할 수 있을 경우, 반복 게임의 특정 부분 게임 완전 균형(subgame perfect equilibrium)을 학습할 수 있습니다. 마지막으로, 본 연구에서 제시하는 후회 최소화 방법이 Stag-Hunt와 같은 게임에서 더 협력적인 해법과 높은 효용을 가져올 수 있음을 보여주는 실험 결과를 제공합니다.

In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents who can respond based on histories of play. The standard metric of \emph{external regret} in online learning is known to fail to capture such adaptivity. To account for players' counterfactual reasoning, we introduce {\tt Repeated Policy Regret (RP-Regret)}, a game-theoretic metric that 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 to existing regret notions in this setting, ours is native to repeated game playing, enabling stronger comparators and opponents with fewer constraints, while maintaining the possibility of finding better equilibria when all players minimize it. We first identify necessary conditions for obtaining {\tt RP-Regret} sublinear in time, on the variation of the player's comparator strategies in the regret definition and on the memories of both the comparator and opponents' strategies. We then study additional conditions and provable algorithms to minimize {\tt RP-Regret}, which is by definition \emph{non-convex} in the strategy space. To address this challenge, we propose three algorithms: (i) one based on an optimization oracle, as assumed in some prior work in online non-convex learning; (ii) one that minimizes a convex and \emph{linearized} surrogate of {\tt RP-Regret} at each iteration; (iii) one that directly minimizes {\tt RP-Regret} when opponents change strategies slowly. Furthermore, when all players can run algorithms to minimize the {\tt RP-Regret} (or its linearized variant), certain subgame perfect equilibria of the repeated game can be learned. We also provide experiments showing that minimizing our regret notions can lead to more cooperative solutions with higher utility in games such as Stag-Hunt.