💻 computer science

Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

이 논문은 비대칭 정보 하의 적대적 팀 게임을 위한 새로운 솔루션 개념으로서, 전략적 기만을 완화하기 위해 분포 불변 강건성과 확률적 통찰을 결합한 확률론적 강건 미니맥스 후회 평형(PR-MRE)을 소개하고, 심층 강화 학습을 사용하여 이러한 전략들을 효율적으로 계산하기 위한 PRMRE-PSRO 알고리즘을 제안한다.

원저자: Naman Aggarwal, Jonathan P. How

게시일 2026-07-14

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Naman Aggarwal, Jonathan P. How

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

당신이 거대하고 복잡한 지도 위에서 벌어지는 고도의 심리전이 가미된 '깃발 뺏기(Capture the Flag)' 게임을 하고 있다고 상상해 보십시오. 당신은 블루 팀이며, 당신의 임무는 레드 팀이 숨겨둔 깃발을 찾아 가져오는 것입니다. 여기서 반전이 있습니다. 당신은 깃발이 정확히 어디에 있는지 모릅니다. 대신 과거의 게임을 바탕으로 한 "최선의 추측"을 가지고 있습니다. 예를 들어, 왼쪽 터널에 있을 확률이 70%, 오른쪽 터널에 있을 확률이 30%라고 생각할 수 있습니다. 하지만 레드 팀은 어떤가요? 그들은 깃발의 정확한 위치를 알고 있습니다. 심지어 그들은 당신을 함정으로 유인하기 위해 깃발이 엉뚱한 곳에 있는 것처럼 행동하며 당신을 속일 수도 있습니다.

이것이 바로 **비대칭 정보가 존재하는 적대적 팀 게임(Adversarial Team Games with Asymmetric Information)**의 세계입니다. Naman Aggarwal과 Jonathan P. How의 논문은 한 가지 큰 문제를 다룹니다. 당신의 "최선의 추측"이 거짓일 수도 있거나, 게임의 규칙이 예상치 못한 방식으로 변할 때 어떻게 플레이해야 하는가에 대한 문제입니다.

"확률에 베팅하기"의 문제점

보통 똑똑한 플레이어들은 **베이지안 내쉬 균형(Bayesian Nash Equilibrium, BNE)**이라는 전략을 사용합니다. 이것은 평균만을 신경 쓰는 일기 예보관을 생각하면 쉽습니다. 만약 예보에서 "비가 올 확률 70%"라고 한다면, 예보관은 70%의 확률로 우산을 챙기고 30%의 확률로 그냥 집을 나섭니다. 이 게임에서 블루 팀은 깃발이 있을 가능성이 가장 높은 왼쪽 터널에 모든 에너지를 집중할 것입니다.

하지만 문제는 레드 팀이 아주 영악하다는 점입니다. 만약 당신이 왼쪽 터널에 집착하고 있다는 것을 안다면, 그들은 깃발을 오른쪽 터널으로 옮길 수도 있습니다. 갑자기 당신의 "70% 확률" 전략은 처참하게 실패합니다. 논문은 하나의 "최선의 추측"(명목 분포)에만 의존하는 것이 위험하다고 주장합니다. 왜냐하면 상대방이 상황을 조작할 수 있기 때문입니다. 이는 마치 경마에서 승리할 확률이 높다는 이유만으로 전 재산을 걸었는데, 알고 보니 기수가 당신의 라이벌로 변장한 적이었다는 사실을 깨닫는 것과 같습니다.

"최악의 경우"라는 함정

어떤 플레이어들은 극도로 안전한 길을 택하려고 합니다. 그들은 최악의 시나리오에 대비하여 깃발이 어디에든 있을 수 있다고 가정합니다. 심지어 한 번도 발생한 적 없는 장소에 깃발이 있을 수도 있다고 생각하죠. 그래서 그들은 혹시 모를 상황에 대비해 지도의 모든 구석구곳을 정찰하기 위해 정찰병을 보낼지도 모릅니다.

논문은 이러한 접근 방식이 너무 편집증적이라고 지적합니다. 이는 아주 작은 먼지 입자가 생길 확률이 0.01%라고 해서 풀 세트 방호복을 입는 것과 같습니다. 비록 최악의 상황으로부터 당신을 보호해주긴 하겠지만, 당신을 느리고 서투르게 만들어 결국 무서워서 움직이지 못하다가 게임에서 패배하게 만들 것입니다. 논문은 실제 게임에서 아주 희박한 가능성은 무시해도 되는 경우가 많기 때문에, 이러한 "완전한 최악의 경우(fully worst-case)"를 고려하는 방식은 너무 보수적이라며 명시적으로 배제합니다.

새로운 영웅: PR-MRE

여기 논문의 새로운 해결책인 **확률적 강건성을 갖춘 미니맥스 후회 균형(Probabilistically Robust Minimax-Regret Equilibrium, PR-MRE)**이 등장합니다.

PR-MRE를 "스마트 정찰병" 전략이라고 생각해 보십시오. 단순히 가장 가능성 높은 곳에 베팅하거나(BNE처럼), 혹은 땅속의 모든 구멍을 다 확인하는 것(편집증적인 접근처럼) 대신, PR-MRE는 영리한 질문을 던집니다. "내가 실수를 한다면, 얼마나 후회하게 될 것이며, 그 실수가 실제로 일어날 가능성은 얼마나 되는가?"

이것은 **"전형성을 보존하는 위협 모델(Typicality-Preserving Threat Model)"**이라는 특별한 규칙을 사용합니다. 당신에게 "의심스러운" 위치 목록이 있다고 상상해 보십시오. 당신은 어떤 장소들(예: 하늘에 떠 있는 깃발)은 너무 이상하고 일어날 법하지 않아서 안전하게 무시할 수 있다는 것을 알고 있습니다. 하지만 (비록 인기 있는 곳은 아닐지라도) 그럴 법한(plausible) 장소들에 대해서는 대비책을 세웁니다.

PR-MRE는 이렇게 말합니다. "나는 매우 드물고 불가능한 시나리오는 무시하겠다. 하지만 가능성은 있지만 흔치 않은 시나리오들에 대해서는, 내가 속지 않도록 대비하겠다." 즉, "보통 일어나는 일"의 수학적 계산과 "일어날 수 있는 일" 사이의 균형을 맞추는 것입니다.

어떻게 테스트했는가

저자들은 단순히 이론만 제시한 것이 아니라, 이를 테스트하기 위해 컴퓨터 시뮬레이션을 구축했습니다. 그들은 그래프(경로와 노드로 이루어진 네트워크) 형태의 디지털 깃발 뺏기 게임을 만들었습니다.

실험에서 그들은 새로운 PR-MRE 전략을 기존의 BNE 전략과 맞붙였습니다.

설정: 블루 팀에게 깃발이 왼쪽에 있을 확률 80%, 오른쪽에 있을 확률 20%라는 "명목상" 믿음을 주었습니다.
테스트: 그 후 실제 깃발의 위치를 오른쪽(20% 확률의 지점)으로 바꾸거나 확률 분포를 뒤섞음으로써 시스템을 속였습니다.
결과: 모든 것을 왼쪽에 걸었던 BNE 팀은 깃발이 오른쪽에 나타나자 처참하게 무너졌습니다. 그들은 다수 의견에 너무 집중되어 있었습니다.
PR-MRE 팀: 이 플레이어들은 다르게 행동했습니다. 왼쪽으로 돌진하는 대신, 먼저 양쪽을 모두 확인하기 위해 정찰병을 보냈습니다. 그들은 확실해지기 전까지는 한 경로에 완전히 몰두하지 않았습니다.

논문은 이러한 시뮬레이션에서 PR-MRE 팀이 깃발 위치가 예상치 못하게 변했을 때 훨씬 더 높은 승률을 유지했음을 보여줍니다. 그들은 단순히 더 자주 이긴 것이 아니라, 속이기가 훨씬 더 어려웠습니다. 논문은 게임이 예측된 대로 정확히 진행될 때는 BNE가 훌륭하게 작동하지만, 상대방이 당신을 속이려 할 때 살아남는 것은 PR-MRE라는 점을 명시적으로 밝히고 있습니다.

마법 뒤에 숨겨진 수학

이것을 구현하기 위해 저자들은 매우 까다로운 수학 문제를 풀어야 했습니다. 그들은 이 게임을 "강건한 쌍선형 프로그램(robust bilinear program)"으로 변환했습니다. 이 어려운 이름에 겁먹지 마십시오. 이것은 당신의 특정 계획을 망치려는 상대방을 가정하면서도 최선의 수를 찾아야 하는 복잡한 퍼즐이라고 생각하면 됩니다.

그들은 PR-MRE-PSRO라는 새로운 알고리즘을 만들었습니다. 이것은 AI 에이전트들이 서로 수천 번씩 대결하는 훈련 캠프와 같습니다. "블루" 에이전트들은 "후회를 최소화하는 법(regret-minimizing)"을 배웁니다. 즉, 깃발이 다른 곳에 있었을 때 나중에 스스로를 자책하게 될 만한 움직임을 피하는 법을 배웁니다. "레드" 에이전트들은 어떠한 약점을 이용할지를 배웁니다. 이러한 상호 작용을 통해 블루 팀은 기만(deception)에 강한 전략을 학습하게 됩니다.

결론

이 논문은 한쪽이 다른 쪽보다 더 많은 정보를 알고 있는 게임에서는, 단순히 대중을 따르거나(가장 가능성 높은 결과) 모든 가능성에 대해 공포에 질려서는 안 된다고 제안합니다. 대신 PR-MRE를 사용해야 합니다. 이는 "통상적인" 확률을 존중하면서도 "그럴 법하지만 드문" 시나리오를 위한 안전망을 유지하는 전략입니다.

시뮬레이션 결과, 이 접근 방식은 "과잉 몰입(한 가지 추측에 모든 것을 거는 것)"보다는 "정찰(여러 옵션을 확인하는 것)"에 능한 블루 팀을 만들어냈습니다. 덕분에 레드 팀이 게임의 현실을 바꾸려 할 때 훨씬 더 속이기 어려워졌습니다. 저자들은 이 방법이 상대방이 실시간으로 규칙을 바꾸려 할 때 더 강력한 성능 보장을 제공한다고 결론짓습니다.

기술 요약: 베이지안 내쉬를 넘어: 비대칭 정보 하의 적대적 팀 게임을 위한 미니맥스 후회 평형 학습

1. 문제 정의

본 논문은 비대칭 정보를 특징으로 하는 **적대적 팀 게임(Adversarial Team Games, ATGs)**에서 강건한 전략을 계산하는 문제를 다룹로다. 이러한 설정에서 한 팀(정보를 가진 팀, 예: Red)은 숨겨진 상태(Nature의 타입, 예: 깃발 위치)에 대한 완벽한 지식을 보유하는 반면, 대립하는 팀(정보가 없는 팀, 예: Blue)은 가능한 타입들에 대한 사전 믿음 분포(prior belief distribution)를 바탕으로 행동해야 합니다.

핵심 과제는 **전략적 분포 변화(strategic distribution shifts)**입니다. **베이지안 내쉬 평형(Bayesian Nash Equilibrium, BNE)**과 같은 기존 솔루션 개념은 공통 사전 분포 가정에 의존합니다. 그러나 기만적인 환경에서는 정보를 가진 상대방이 명목상 사전 분포(nominal prior)로부터 타입을 이동시키기 위해 "Nature"와 결탁하여, 해당 사전 분포에 최적화된 전략을 악용할 수 있습니다.

기존 접근 방식의 한계:
- 위험 중립(BNE): 분포 변화에 매우 민감합니다. 명목상 사전 분포에 최적화된 전략은 분포가 변할 경우 악용되기 쉽습니다.
- 분포 강건 최적화(Distributionally Robust Optimization, DRO): 규정된 모호성 집합(예: KL-divergence 볼) 내에서만 보장을 제공합니다. 이는 대규모의 레짐 변화(regime change)나 국소적 발산 모델에 부합하지 않는 변화가 발생할 경우 실패합니다.
- 최악-경우 강건성(Minimax-Regret Equilibrium, MRE): 전체 타입 공간에 대해 후회(regret)를 최소화합니다. 분포에 의존하지는 않지만, 유용한 확률적 정보(사전 분포)를 무시하고 희귀한 타입에도 일반적인 타입과 동일한 가중치를 부여하기 때문에 지나치게 보수적입니다.

본 논문은 전략적 변화에 대한 강건성과 전형적인 분포에서의 효율성 사이의 균형을 맞추고자 하며, MRE의 과도한 보수성을 피하면서도 적대적인 확률 질량 재배치로부터 보호하고자 하는 새로운 평형 개념을 추구합니다.

2. 방법론

A. 이론적 프레임워크: 확률적 강건 미니맥스 후회 평형 (PR-MRE)
저자들은 PR-MRE라는 새로운 평형 개념을 도입하며, 이는 위험 중립 BNE와 분포 불변 MRE 사이를 보간(interpolate)합니다.

위협 모델 (전형성 보존 변화): 임의의 변화나 국소적 섭동을 가정하는 대신, 저자들은 허용 가능한 분포가 타입의 **전형성(typicality)**을 보존한다는 위협 모델을 정의합니다. 즉, 명목 분포 하에서 희귀한 타입은 여전히 희귀하게 유지되며(신뢰 매개변수 $\delta$ 에 의해 제한됨), 확률 질량은 고확률(전형적) 타입들 사이에서 임의로 재배치될 수 있습니다.
목적: 정보가 없는 팀은 이 허용된 분포 집합에 대해 **최악-경우 후회(worst-case regret)**를 최소화합니다. 후회는 타입별 최적 전략 대비 성능 손실로 정의됩니다.
수학적 정식화:
- 노멀 폼 게임(normal-form games)의 경우, PR-MRE 최적 대응(best-response)은 **강건한 쌍선형 계획법(robust bilinear program)**으로 정식화됩니다.
- BNE(선형 계획법)나 표준 MRE(전체 심플렉스 상의 쌍선형 계획법)와 달리, PR-MRE는 전형성 보존 위협 모델의 제약 조건에 의해 가중치가 부여된 타입 간의 후회를 결합합니다.
- 저자들은 이 강건한 쌍선형 프로그램을 해결하기 위해 **다룰 수 있는 준정부호 계획법(semidefinite programming, SDP) 완화(relaxation)**를 도출합니다.

B. 알고적 프레임워크: PRMRE-PSRO
대규모 그래프 구조의 ATG(예: Graph Capture-the-Flag)로 PR-MRE를 확장하기 위해, 저자들은 정책 공간 응답 오라클(Policy-Space Response Oracles, PSRO) 프레임워크의 강건한 확장판인 PRMRE-PSRO를 제안합니다.

강건한 더블 오라클 (Robust Double Oracle, RDO): 알고리즘은 양 팀을 위한 전략 인구(population)를 유지합니다.
- 메타 솔버(Meta-Solver): SDP 완화를 사용하여 현재 정책 인구에 대한 PR-MRE 메타 평형을 계산합니다.
- 최적 대응 오라클(Best-Response Oracles):
  - Red (정보가 있는 팀): Blue 메타 평형에 대한 최적 대응을 찾기 위해 협력적 다중 에이전트 강화학습(MARL)을 사용합니다.
  - Blue (정보가 없는 팀): Red 메타 평형에 대한 최악-경우 후회를 최소화하는 최적 대응을 찾기 위해 MARL을 사용하며, 이때 미니맥스 후회 정지 기준을 적용합니다.
3D 페이오프 텐서(3D Payoff Tensor): 표준 PSRO가 2D 페이오프 행렬을 사용하는 것과 달리, PRMRE-PSRO는 학습 과정 동안 다양한 타입 가설에 대한 성능과 후회를 명시적으로 추적하기 위해 3D 페이오프 텐서(Red 정책 $\times$ Blue 정책 $\times$ 타입)를 유지합니다.

3. 주요 기여

새로운 평형 개념 (PR-MRE): 본 논문은 명목 사전 분포로부터 얻은 거친 확률 정보(전형성)를 활용하여 악용 가능성을 최소화하는 PR-MRE를 도입합니다. 이는 MRE, BNE 및 표준 DRO 방식보다 더 타이트한 성능 하한을 제공합니다.
전형성 보존 위협 모델: 저자들은 허용 가능한 변화가 타입의 "희귀성"을 보존하는 위협 모델을 공식화했습니다. 이를 통해 국소적 발산 볼(divergence balls)보다 더 현실적인 전략적 기만 모델을 제공하며, 전형적인 타입들 사이의 임의적인 질량 재배치를 허용하면서도 희귀한 타입에 대한 질량은 제한합니다.
확장 가능한 알고리즘 (PRMRE-PSRO): 더블 오라클 루프 내에서 SDP 완화를 메타 솔버로 통합한 인구 기반 학습 프레임워크를 제안합니다. 이를 통해 정확한 계산이 불가능한 대규모 그래프 구조 게임에서도 근사적인 PR-MRE 전략을 계산할 수 있습니다.
실험적 검증: Graph Capture-the-Flag 실험을 통해 PRMRE-PSRO가 BNE-PSRO에 비해 실질적으로 개선된 최악-경우 성능을 가진 전략을 발견함을 입증했습니다.

4. 결과

분포 변화에 대한 강건성: 테스트 분포가 명목 사전 분포에서 벗어나는 실험(예: 소수 깃발 가설이 다수 가설이 되는 경우)에서, PRMRE로 학습된 정책은 BNE로 학습된 정책에 비해 현저히 높은 승률을 유지합니다. 다수 가설에 과적합된 BNE 정책은 분포가 변할 때 치명적인 성능 저하를 겪습니다.
행동 분석:
- BNE 정책: 가장 가능성이 높은 깃발 가설과 관련된 통로로 즉시 진입하는 경향이 있습니다(과적합).
- PR-MRE 정책: **정찰 행동(scouting behavior)**을 보입니다. 학습된 정책은 특정 통로로 확정하기 전에 두 가지 잠재적 깃발 위치를 대칭적으로 탐색합니다. 이러한 행동은 경쟁하는 가설들 사이의 후회를 줄이고, 함정일 수 있는 단일 가설에 과도하게 몰입하는 것을 방지합니다.
성능 보장: 이론적 분석(Lemma 1-4)은 PR-MRE가 전형성 보존 집합 내의 모든 분포에 대해 균등한 성능 하한을 제공함을 확인하며, 이는 전형적인 분포에 대해 MRE가 제공하는 하한보다 엄격하게 더 타이트합니다.

5. 의의 및 주장

본 논문은 PR-MRE가 비대칭 정보 게임에서 **강건성(robustness)**과 효율성(efficiency) 사이의 트레이드오프에 대한 원칙적인 솔루션을 제공한다고 주장합니다.

BNE를 넘어서: 기만 상황에서 취약한 위험 중립 평형의 한계를 극봅니다.
MRE를 넘어서: 전형적인 시나리오에서 낮은 성능을 초래할 수 있는 완전 미니맥스 후회 접근 방식의 과도한 보수성을 피합니다.
실질적 영향: 전략적 분포 변화(예: 상대방이 숨겨진 상태의 가능성을 조작하는 경우)에 대해 헤징(hedging)하는 전략을 학습함으로써, PR-MRE는 탐색 및 포획 또는 방어 시나리오와 같은 적대적 환경에서 더 강건한 자율 에이전트를 가능하게 합니다.

저자들은 정규 폼 근사(normal-form approximations)를 위한 실행 가능한 완화(tractable relaxation)를 제공하지만, 확장형 게임(extensive-form games, EFG)에 대한 미니맥스 후회 평형의 순차적 정교화(sequential refinement)를 계산하는 것은 여전히 열린 연구 과제라고 언급합니다. 특히, 카운터팩추얼 후회 최소화(CFR)에서처럼 EFG 표현에서 후회 분해(regret decomposition)가 MRE에서도 성립하는지에 대한 문제가 남아 있습니다.