🤖 AI

Regret Minimization with Adaptive Opponents in Repeated Games

이 논문은 반복 게임에서 적응형 상대방을 다루기 위해 설계된 새로운 게임 이론적 지표인 반복 정책 후회(Repeated Policy Regret, RP-Regret)를 소개하고, 이 비볼록 후회 척도를 최소화하는 알고리즘을 제안함으로써 부분 게임 완전 균형 및 더 협력적인 결과를 학습할 수 있게 한다.

원저자: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

게시일 2026-06-05

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 친구와 긴 체스 게임, 포커, 혹은 아주 단순한 가위바위보 게임을 하고 있다고 상상해 보세요. 일반적인 게임에서는 당신이 한 수를 두고, 상대가 한 수를 두면 점수를 집계합니다. 하지만 현실 세계에서(그리고 이 논문에서 연구하는 '반복 게임'에서) 당신의 친구는 로봇이 아닙니다. 그들은 당신을 지켜보고 있습니다. 당신이 공격적으로 플레이하면, 그들은 방어적으로 변할 수 있습니다. 당신이 착하게 플레이하면, 그들은 협력할 수도 있습니다. 그들은 **적응형(adaptive)**입니다. 즉, 당신의 이력에 따라 그들의 전략을 바꿉니다.

문제는 컴퓨터 과학자들이 "당신이 얼마나 잘했는지"를 측정하는 표준 방식인 **외부 후회(External Regret)**가, 당신이 무엇을 하든 상관하지 않는 정적인 벽을 상대로 하는 게임을 가정한다는 점입니다. 이 방식은 다음과 같이 묻습니다: "상대가 무엇을 했든 상관없이, 매 턴마다 단 하나의 최선의 수만을 골랐다면 내가 더 많이 이겼을까?"

이 논문은 스마트하고 적응력이 있는 상대를 대상으로 하는 게임에서 이 표준 측정 방식이 잘못되었다고 주장합니다. 이 방식은 당신의 행동이 상대방의 미래 행동을 변화시킨다는 사실을 반영하지 못하기 때문에, 플레이어가 (예를 들어 죄수의 딜레마에서 항상 '배반'을 선택하는 것처럼) 좋지 못한 플레이를 하도록 강요하곤 합니다.

다음은 이 논문의 해결책을 쉬운 비유를 사용하여 설명한 것입니다.

1. 새로운 지표: "반복 정책 후회" (RP-Regret)

저자들은 RP-Regret라고 불리는 새로운 성공 측정 방식을 도입합니다.

기존 방식 (외부 후회): 당신이 자동차를 운전하고 있다고 상상해 보세요. 기존의 지표는 다음과 같이 묻습니다: "교통 신호나 다른 차들을 무시하고 매일 똑같은 경로로만 운전했다면, 시간을 얼마나 아낄 수 있었을까?" 만약 교통 신호가 당신의 운전에 따라 변한다면, 이 질문은 쓸모가 없습니다.
새로운 방식 (RP-Regret): 이 지표는 다음과 같이 묻습니다: "만약 당신이 전체 여정 동안 다른 **전체 계획(정책)**을 선택했고, 그 특정 계획에 따라 교통 신호와 다른 운전자들이 반응할 것이라는 점을 미리 알고 있었다면, 당신은 얼마나 더 나은 상황이었을까?"

핵심 차이점: 새로운 지표에서 당신은 단순히 현재의 움직임을 하나의 "최선의 수"와 비교하는 것이 아닙니다. 당신은 당신의 전체 전략을, 당신의 상대 또한 그 더 나은 전략에 적응할 것임을 가정했을 때 사용할 수 있었던 가상의 "더 나한 전략"과 비교합니다.

2. "기억"의 문제

이 논문은 중대한 장애물을 발견했습니다. 만약 플레이어들이 완벽하고 무한한 기억력을 가지고 있어서 과거의 아주 작은 세부 사항에도 모두 반응할 수 있다면, 이 새로운 후회를 최소화하는 것은 수학적으로 불가능해집니다. 이는 마치 당신이 조각 하나를 움직일 때마다 다른 모든 조각의 모양이 즉각적으로 변하는 퍼즐을 푸는 것과 같습니다.

이를 해결하기 위해 저자들은 문제를 풀 수 있게 만드는 두 가지 "도로 규칙(조건)"을 제안합니다.

느린 변화: 당신의 상대(그리고 당신의 '만약에' 전략)는 한 순간에서 다음 순간으로 넘어갈 때 너무 급격하게 생각을 바꾸어서는 안 됩니다.
망각: 플레이어들은 모든 것을 완벽하게 기억해서는 안 됩니다. 그들은 "희미해지는 기억"을 가져야 합니다. 100번 전의 일이 지금은 거의 중요하지 않아야 합니다. 논문에서는 이를 **지수적 감쇠 기억(Exponential Decay Memory)**이라고 부릅니다. 이는 최근의 대화는 더 잘 기억하지만, 1년 전 대화의 세부 사항은 희미해지는 것과 같습니다.

3. 더 잘 플레이하는 세 가지 방법 (알고리즘)

(완벽한 "RP-Regret" 전략을 계산하는 것은 형태가 계속 변하는 미로를 푸는 것만큼 어렵기 때문에) 저자들은 최선의 결과에 가까워지기 위한 세 가지 도구를 제안합니다.

도구 1: 마법의 오라클(Oracle). 당신에게 어떤 복잡하고 비선형적인 퍼즐이라도 즉시 풀어낼 수 있는 슈퍼컴퓨터가 있다고 상상해 보세요. 만약 이 "오라클"이 있다면, 당신은 완벽한 전략을 찾을 수 있습니다. 논문은 이것이 작동함을 증명하지만, 현실 세계에는 그런 마법 같은 컴퓨터가 없다는 점도 인정합니다.
도구 2: "로컬(Local)" 지름길. 전체 게임 동안의 전체 계획을 바꾸려고 노력하는 대신, 이 도구는 다음과 같이 묻습니다: "만약 내가 지금 당장 단 하나의 수만 바꾼다면, 그리고 나머지는 그대로 유지한다면 어떨까?" 이는 문제를 작은, 국소적인 변화를 보는 것으로 단순화합니다. 이를 통해 수학적 계산이 훨씬 쉬워지며(울퉁불퉁하고 거친 언덕을 매끄러운 경사로 만드는 것과 같음), 빠르고 실용적인 알고리즘을 가능하게 합니다.
도구 3: 슬로우 모션 게임. 만약 상대방이 매우 느리게 전략을 바꾼다면, 저자들은 당신이 이 게임을 "마르코프 게임(현재의 상태가 전체 이력이 아닌 현재 상태에만 의존하는 게임)"처럼 다룰 수 있음을 보여줍니다. 그들은 이 게임을 표준 최적화 도구들이 잘 작동하는 형식으로 변환하며, 효과적으로 문제를 더 높은 차원으로 "들어 올려(lifting)" 해결 가능한 형태로 만듭니다.

4. 결과: 협력이 승리한다

이 논문에서 가장 흥激한 부분은 모두가 이 새로운 도구들을 사용할 때 일어나는 일입니다.

두 사람이 서로 배신하여 결국 둘 다 손해를 보게 되는 유명한 죄수의 딜레마에서, 기존 방식은 보통 둘 다 손해를 보는 "배반-배반" 결과로 이어집니다. 그러나 이 논문은 플레이어들이 RP-Regret를 최소화하면 자연스럽게 협력을 배우게 된다는 것을 보여줍니다.

비유: 두 이웃을 생각해 보세요. 만약 그들이 오늘의 상호작용만을 본다면 서로의 우편물을 훔칠 수도 있습니다. 하지만 "내가 오늘 훔치면 내 이웃도 내일 훔칠 것이고, 그러면 우리 둘 다 손해를 본다"는 것을 깨닫는다면, 그들은 친절하게 행동하는 법을 배웁니다. 새로운 지표는 이러한 장기적인 사고를 포착합니다.
실험: 저자들은 이를 사슴 사냥(Stag-Hunt) 게임(작은 보상을 위해 혼자 토끼를 잡거나, 큰 보상을 위해 함께 사슴을 잡는 게임)에 테스트했습니다. 플레이어들이 새로운 "로컬 RP-Regret" 알고리즘을 사용했을 때, 그들은 성공적으로 협력을 배워 사슴을 함께 사냥했으며, 이전보다 훨씬 높은 점수를 달성했습니다.

요약

이 논문은 다음과 같이 말합니다: "플레이어를 로봇을 상대로 할 때의 기준으로 측정하는 것을 멈추십시오. 대신 스마트하고 반응하는 인간을 상대로 할 때의 기준으로 측정하십시오." 적응성과 기억의 한계를 고려한 새로운 지표를 도입하고 이를 계산하는 알고리즘을 제공함으로써, 저자들은 플레이어들이 반복 게임에서 이전보다 더 잘 협력하고 더 나은 결과를 얻을 수 있음을 보여줍니다.

기술 요약: 반복 게임에서의 적응형 상대방을 고려한 후회 최소화 (Regret Minimization with Adaptive Opponents in Repeated Games)

문제 정의

본 논문은 상대방이 플레이 기록(history of play)에 따라 전략을 조정할 수 있는 적응형(adaptive) 상황에서의 반복 게임 내 후회 최소화 문제를 다룹다. 저자들은 온라인 학습에서의 표준 지표인 **외부 후회(external regret)**가 이러한 설정에서는 불충분하다고 주장한다. 외부 후회는 손실 시퀀스가 시간 단계만의 함수라고 가정하며, 이는 암묵적으로 상대방을 비적응형으로 취급한다. 그러나 게임 이론적 설정에서 상대방의 대응은 플레이어의 행동에 따라 미래의 손실을 변화시킬 수 있다. 결과적으로, 반복 게임에서 외부 후회를 최소화하는 것은 차악의 균형(예: 반복 죄수의 딜레마에서의 '배반-배반' 결과)으로 이어질 수 있으며, 높은 효용을 창출하는 '눈에는 눈(tit-for-tat)'과 같은 효과적인 협력 전략을 포착하는 데 실패한다.

정책 후회(Policy Regret)(손실 함수에 메모리를 반영함)나 반응 후회(Response Regret)(이력 의존적 혼합 전략을 고려함)와 같은 기존의 대안들은 상당한 한계에 직면해 있다. 정책 후회는 초기 이탈이 장기적인 효과를 미칠 수 있는 반복 게임의 특성을 반영하지 못하는 제한적인 $m$ -유계 메모리(m-bounded memory) 가정에 의존하는 경우가 많다. 반응 후회는 이론적으로는 타당하지만, 지수적으로 거대한 전략 공간을 요구하여 계산적으로 실행 불가능하다.

방법론

1. 반복 정책 후회 (Repeated Policy Regret, RP-Regret)

저자들은 반복 게임에 특화된 새로운 성능 지표인 **반복 정책 후회(RP-Regret)**를 도입한다.

정의: RP-Regreg는 모든 플레이어(상대방 포함)가 플레이 이력에 적응적으로 반응한다고 가정할 때, 실현된 누적 효용과 과거 최적의 누적 효용 사이의 차이를 측정한다.
핵심 차이점: 외부 후회와 달리, 시점 $t$ 에서의 비교 전략(comparator strategy)으로의 이탈은 $t$ 시점의 손실뿐만 아니라, 새로운 이력에 반응하여 전략을 바꾸는 적응형 상대방에 의한 이후의 모든 손실에도 영향을 미친다.
필요 조건: 본 논문은 특정 제약 조건 없이는 아선형(sublinear) RP-Regret를 달하는 것이 불가능함을 입증한다. 두 가지 필요 조건이 식별되었다:
1. 아선형 변동(Sublinear Variation): 비교 전략이 시간에 따라 너무 급격하게 변해서는 안 된다.
2. 불완전 기억(Imperfect Recall): 플레이어(및 비교 대상)는 전체 이력을 완벽하게 기억할 수 없다. 구체적으로, 본 논문은 **지수적 감쇄 메모리(Exponential Decay Memory, EDM)**를 제안하는데, 이는 과거 이력이 현재 전략에 미치는 영향이 지수적으로 감소하도록 한다. 이는 행동을 통한 '상태 전달(state passing)'을 방지하며, 유효한 메모리 길이가 정확도 요구 사항에 따라 로그 단위로만 성장하도록 보장한다.

2. 최소화 알고리즘

목적 함수가 시간에 따른 전략의 곱으로 인해 **비볼록(non-convex)**하기 때문에, 본 논문은 이를 최소화하기 위한 세 가지 접근 방식을 제안한다.

오라클 기반 접근 방식 (Oracle-Based Approach): 비볼록 최적화 오라클에 대한 접근 권한이 있다고 가정할 때(이전의 온라인 비볼록 학습 연구와 같이), 저자들은 앞서 언급한 필요 조건(아선형 변동 및 EDM) 하에서 아선형 RP-Regret 달성이 가능함을 보여준다. 이는 이론적 기준점 역할을 한다.
국소 반복 정책 후회 (Local Repeated Policy Regret, LRP-Regret): 계산적 실행 가능성을 확보하기 위해, 저자들은 대리 지표인 LRP-Regret를 제안한다. 이 지표는 이탈 범위를 전역적인 전략 변경이 아닌 단일 타임스텝(single timestep) 내의 이탈으로 제한한다.
- 볼록화(Convexification): 특정 타임스텝에서의 기대 손실을 해당 단계의 전략에 대한 함수로 볼 때, 이는 선형(따라서 볼록)이 된다.
- 알고리즘: 저자들은 LRP-Regret를 최소화하기 위해 투영 경사 하강법(Projected Gradient Descent, PGD) 알고리즘을 제안한다. 이론적 보증에 따르면, 상대방이 EDM 조건을 만족하면 이 알고리즘은 아선형 LRP-Regret를 달성한다.
마르코프 게임 재구성 (Markov Game Reformulation): 상대방 또한 전략을 느리게 변화시키는 경우(아선형 변동을 만족하는 경우), 저자들은 유계 메모리를 가진 반복 게임을 무한 시계(infinite-horizon) 마르코프 게임으로 재구성한다.
- 점유 측도 (Occupancy Measures): 전략을 직접 최적화하는 대신, 알고리즘은 점유 측도(상태-행동 방문 빈도)를 최적화한다. 이는 비볼록 문제를 점유 측도 공간에서의 볼록 문제로 변환한다.
- 제약 조건: 알고리즘은 점유 측도가 적응형 상대방에 대한 유효한 곱 전략 프로파일(product strategy profile)에 부합하도록 시변 제약 조건을 처리한다.
- 결과: 이 접근 방식은 (단순한 대리 지표가 아닌) 원래의 RP-Regret를 직접 최소화하며 아선형 후회를 달성한다.

주요 결과

난해성 결과 (Hardness Results): 본 논문은 아선형 변동과 불완전 기억(특히 EDM) 조건 없이는 RP-Regret를 최소화하는 것이 불가능함(선형 후회 발생)을 증명한다.
알고리즘 보증:
- LRP-Regret 최소화 알고리즘은 $\tilde{O}(|A|^{m+1}\sqrt{P_T/T})$ 의 후회 상한을 달성한다 (여기서 $P_T$ 는 비교 대상의 변동이며 $m$ 은 메모리 길이이다).
- 마르코프 게임 기반 알고리즘은 상대방이 천천히 변화할 때 아선형 RP-Regret를 달성한다.
균형 계산: 저자들은 이러한 후회 개념을 최소화하는 것과 균형을 계산하는 것 사이의 이론적 연결 고리를 확립한다.
- 모든 플레이어가 RP-Regret(또는 LRP-Regret)를 최소화하면, 시간 평균 전략은 근사적 부분게임 완전 내쉬 균형(Approximate Subgame Perfect Nash Equilibrium, SPNE) 또는 **부분게임 완전 코즈 상관 균형(Subgame Perfect Coarse Correlated Equilibrium, SPCCE)**으로 수렴한다.
- 구체적으로, 무한 반복 게임의 경우, 궤적은 특정 변동 예산 내에서의 이탈에 대해 강건한 균형으로 수렴한다.
실험적 검증: 스태그 헌트(Stag-Hunt) 게임에 대한 실험을 통해, LRP-Regret를 최소화하는 방식이 외부 후회를 최소화하는 방식보다 협력적 균형(Stag-Stag)에 도달하여 더 높은 효용을 얻는 빈도가 높음을 보여준다. 외부 후하 최소화 방식은 종종 위험 지배적이지만 효용이 낮은 균형(Hare-Hare)에 갇히게 된다.

의의 및 주장

본 논문은 제한적인 유계 메모리 가정을 부과하는 기존의 정책 후회 연구나 계산적으로 실행 불가능한 반응 후회와 달리, 상대방의 적응성을 고려하면서도 반복 게임에 적합한 본연적이고 자연스러운 후회 지표를 제공한다고 주장한다.

이론적 기여: 적응형 환경에서의 학습에 대한 근본적인 한계(필요 조건)를 식별하였으며, 동적 비교 대상과 적응형 상대방을 허용하는 게임 이론적 후회 지표를 최소화하는 최초의 증명 가능한 알고리즘을 제공하였다.
실제적 함의: RP-Regret(또는 그 볼록 대리 지표인 LRP-Regret)를 최소화함으로써, 플레이어는 일회성 게임의 내쉬 균형이 제시하는 것보다 더 높은 효용을 얻으며 반복 죄수의 딜레마나 스태그 헌트와 같은 게임에서 협력을 학습할 수 있다.
균형 선택: 본 연구는 반복 게임에서의 후회 최소화가 (일회성 게임의 유일한 내쉬 균형이 아닐 수도 있는) 더 나은 균형(예: 협력적 균형)을 선택하는 메커니즘으로 기능할 수 있음을 시사한다.

저자들은 비볼록 성질로 인해 일반적으로 오라클이나 특정 구조적 가정(예: 느리게 변하는 상대방)이 필요하다는 점을 인정하며, 계산 복잡도에 대해 신중한 태도를 유지한다. 이들은 자신의 연구가 더 약한 형태의 균형 개념과 후회 최소화를 통한 균형 선택에 대한 새로운 연구 방향을 여는 것이라고 규정한다.