게임에서 상수 후회(Constant Regret)를 위한 승산적 낙관성 (Multiplicative Optimism)

요약

본 논문은 유한 일반합 게임을 위한 비결합 학습 규칙인 Multiplicatively Optimistic Regret Matching (MORM)을 제안합니다. 이 방법은 동시 완전 정보 자가 플레이 환경에서 모든 플레이어가 단일 단계 낙관성만으로 $O(\sqrt n\log d)$의 외부 후회를 달성함을 분석했습니다.

핵심 포인트

• Multiplicatively Optimistic Regret Matching (MORM)을 제안함.
• 동시 완전 정보 자가 플레이에 적용 가능.
• 외부 후회(external regret)를 $O(\sqrt n\log d)$로 달성.
• 잠재 기반 후회 매칭 및 Hellinger 제어를 결합하여 분석.