반복 게임에서 적응형 상대방을 고려한 후회 최소화 (Regret Minimization with Adaptive Opponents in

본 논문에서는 플레이 기록(histories of play)에 기반하여 대응할 수 있는 extit{적응형 (adaptive)} 상대방이 존재하는 반복 게임 (repeated games)에서의 후회 최소화 (regret minimization)를 연구합니다. 온라인 학습 (online learning)에서의 표준 지표인 extit{외부 후회 (external regret)}는 이러한 적응성을 포착하지 못하는 것으로 알려져 있습니다. 플레이어들의 반사실적 추론 (counterfactual reasoning)을 고려하기 위해, 우리는 모든 플레이어가 플레이 기록에 extit{대응 (respond)}할 수 있을 때 extit{실현된 (realized)} 효용과 extit{사후 최적 (best-in-hindsight)} 누적 효용 사이의 차이를 측정하는 게임 이론적 지표인 { t Repeated Policy Regret (RP-Regret)}를 도입합니다. 이 설정에서의 기존 후회 개념과 비교했을 때, 우리의 지표는 반복 게임 플레이에 본질적으로 최적화되어 있어, 더 적은 제약 조건 하에서도 더 강력한 비교 대상 (comparators)과 상대방을 허용하는 동시에, 모든 플레이어가 이를 최소화할 때 더 나은 균형 (equilibria)을 찾을 가능성을 유지합니다. 우리는 먼저 후회 정의 내 플레이어 비교 전략의 변화와 비교 대상 및 상대방 전략의 메모리(memories)에 대해, { t RP-Regret}가 시간에 대해 하선형 (sublinear)이 되기 위한 필요 조건을 식별합니다. 그런 다음, 정의상 전략 공간에서 extit{비볼록 (non-convex)}한 { t RP-Regret}를 최소화하기 위한 추가 조건과 증명 가능한 알고리즘을 연구합니다. 이 과제를 해결하기 위해 우리는 세 가지 알고리즘을 제안합니다: (i) 온라인 비볼록 학습 (online non-convex learning)의 일부 선행 연구에서 가정된 최적화 오라클 (optimization oracle)에 기반한 알고리즘, (ii) 매 반복마다 { t RP-Regret}의 볼록하고 extit{선형화된 (linearized)} 대리 함수 (surrogate)를 최소화하는 알고리즘, (iii) 상대방의 전략이 느리게 변할 때 { t RP-Regret}를 직접 최소화하는 알고리즘입니다. 나아가, 모든 플레이어가 { t RP-Regret} (또는 그 선형화된 변형)를 최소화하는 알고리즘을 실행할 수 있을 때, 반복 게임의 특정 부분게임 완전 균형 (subgame perfect equilibria)을 학습할 수 있습니다. 또한 우리는 우리의 후회 개념을 최소화하는 것이 Stag-Hunt와 같은 게임에서 더 높은 효용을 가진 더 협력적인 솔루션으로 이어질 수 있음을 보여주는 실험을 제공합니다.