Regret Minimization with Adaptive Opponents in Repeated Games

적응적 상대가 있는 반복 게임에서 후회 최소화를 위한 새로운 게임이론적 메트릭 RP-Regret을 제안한다.

이 논문은 상대가 플레이 이력에 따라 전략을 바꾸는 반복 게임에서 기존 외부 후회(external regret)가 적응성을 포착하지 못하는 한계를 지적하고, Repeated Policy Regret(RP-Regret)을 새롭게 제안한다. RP-Regret은 모든 플레이어가 플레이 이력에 반응할 수 있는 설정에서 실현된 효용과 사후 최적 효용의 차이를 측정한다. 최적화 오라클, 선형화 대리 함수, 느리게 변하는 상대에 대한 직접 최소화 등 세 가지 알고리즘을 제안하며, 실험에서 Stag-Hunt 게임에서 더 협력적인 해로 수렴함을 보여준다.

핵심 요약

• 적응적 상대가 있는 반복 게임을 위한 새 메트릭 RP-Regret을 도입한다.
• RP-Regret은 기본적으로 비볼록 문제이며, 이를 다루기 위한 세 가지 알고리즘을 제안한다.
• 모든 플레이어가 RP-Regret을 최소화하면 부분게임 완전 균형을 학습할 수 있다.
• Stag-Hunt 게임에서 기존 방식보다 더 협력적이고 효용이 높은 해로 수렴한다.
• 비교 전략과 상대 전략의 기억에 대한 필요조건을 규명한다.

논문 링크

외부 연구를 정리한 자료입니다. HDATF가 발표한 논문이나 제품 성능을 측정한 결과는 아닙니다.