[Paper] 반복 게임에서 적응형 상대와의 후회 최소화
Source: arXiv - 2606.06486v1
Overview
이 논문에서는 적응형 상대방이 플레이 이력을 기반으로 반응할 수 있는 반복 게임에서의 regret 최소화를 연구합니다. 온라인 학습에서의 표준 지표인 외부 regret은 이러한 적응성을 포착하지 못하는 것으로 알려져 있습니다. 플레이어들의 반사실적(reasoning) 추론을 고려하기 위해 Repeated Policy Regret (RP‑Regret) 를 도입합니다. 이는 모든 플레이어가 플레이 이력에 반응할 수 있을 때, 실현된 누적 효용과 사후 최적 누적 효용 사이의 차이를 측정하는 게임 이론적 지표입니다.
기존의 regret 개념과 비교했을 때, 우리의 RP‑Regret는 반복 게임 플레이에 자연스럽게 맞춰져 있어 더 강력한 비교자와 제약이 적은 상대방을 허용하면서, 모든 플레이어가 이를 최소화할 경우 더 나은 균형을 찾을 가능성을 유지합니다.
우선, RP‑Regret를 시간에 대해 서브선형으로 만들기 위한 필요 조건을 규명합니다. 여기에는 regret 정의에서 비교자 전략의 변동성 및 비교자와 상대방 전략의 메모리 요구 사항이 포함됩니다. 이후 추가적인 조건과 RP‑Regret를 최소화하기 위한 증명 가능한 알고리즘을 연구합니다. RP‑Regret는 정의상 전략 공간에서 비볼록이기 때문입니다.
이러한 도전을 해결하기 위해 세 가지 알고리즘을 제안합니다:
- Optimization‑oracle 기반 방법 – 온라인 비볼록 학습에 관한 일부 선행 연구에서 가정된 방식.
- Convex linearized surrogate 최소화 – 각 반복에서 RP‑Regret의 볼록하고 선형화된 대리 함수를 최소화.
- Direct minimization – 상대방이 전략을 천천히 변경할 때 적용.
또한, 모든 플레이어가 RP‑Regret(또는 그 선형화 변형)를 최소화하는 알고리즘을 실행할 경우, 반복 게임의 특정 서브게임 완전 균형(subgame‑perfect equilibria)을 학습할 수 있습니다. 실험 결과, 우리의 regret 개념을 최소화하면 Stag‑Hunt와 같은 게임에서 더 높은 효용을 갖는 협력적 해결책을 얻을 수 있음을 보여줍니다.
Key Contributions
- 적응형 상대방을 위한 새로운 지표 Repeated Policy Regret (RP‑Regret) 를 도입.
- 비교자 변동성 및 메모리 측면에서 서브선형 RP‑Regret를 위한 필요 조건을 규명.
- 본질적으로 비볼록인 RP‑Regret를 최소화하기 위한 세 가지 알고리즘적 접근법을 제시.
- RP‑Regret의 공동 최소화가 학습 가능한 서브게임 완전 균형을 초래함을 증명.
- 고전 게임에서 협력 및 효용 향상을 입증하는 실증적 증거 제공.
Methodology
자세한 방법론은 전체 논문을 참고하십시오.
Practical Implications
이 연구는 머신러닝, 인공지능, 게임 이론(cs.LG, cs.AI, cs.GT)의 발전에 기여합니다.
Authors
- Mingyang Liu
- Asuman Ozdaglar
- Tiancheng Yu
- Kaiqing Zhang
Paper Information
- arXiv ID: 2606.06486v1
- Categories: cs.LG, cs.AI, cs.GT
- Published: June 4, 2026
- PDF: Download PDF