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

우리는 유한 일반합 게임(finite general-sum games)을 위한 비결합 학습 규칙인 Multiplicatively Optimistic Regret Matching (MORM)을 소개합니다. 동시 완전 정보 자가 플레이(simultaneous full-information self-play) 하에서, 모든 플레이어는 단일 단계 낙관성만을 사용하여 모든 지평(horizon)에 걸쳐 $O(\sqrt n\log d)$의 외부 후회(external regret)를 달성합니다. 이 분석은 잠재 기반 후회 매칭 논증(potential-based regret-matching argument)과 승산적 안정성(multiplicative stability), 그리고 전략 이동에 대한 Hellinger 제어(Hellinger control)를 결합합니다. 또한, 학습률 보호 장치(learning-rate safeguard)는 적대적 효용(adversarial utilities)에 직면했을 때 $O(\sqrt{T\log d})$의 후회를 제공합니다.