다인수 불완전 정보 게임에서의 내쉬 균형 (Nash Equilibrium) 계산을 위한 투영 착취 가능성 하강법 (Projected

많은 중요한 게임들은 2명 이상의 플레이어를 포함하며 불완전 정보 (imperfect information)를 가집니다. 이러한 게임에서 게임 이론의 핵심 솔루션 개념인 내쉬 균형 (Nash equilibrium)을 계산하기 위한 기존 방식들은 확장성 (scalability)이 부족하거나 성능이 저조합니다. 본 논문에서는 불완전 정보 다인수 게임에서 내쉬 균형을 근사하기 위한 투영 착취 가능성 하강법 (Projected Exploitability Descent, PED)이라는 새로운 알고리즘을 소개합니다. 이 알고리즘은 다인수 일반화된 착취 가능성 함수 (multiplayer generalized exploitability function)의 대리 지표 (proxy)를 최소화하는 투영 하위 경사 하강법 (projected subgradient descent)을 실행함으로써 작동합니다. 목적 함수는 비볼록 (nonconvex) 및 비매끄러움 (nonsmooth) 특성을 가지지만, 선형 함수들의 최댓값들의 합으로 표현될 수 있어 하위 경사 (subgradient)를 쉽게 계산할 수 있으며, 실행 가능한 시퀀스 형태 전략 (sequence-form strategies)의 다포체 (polytope)로 투영할 수 있습니다. 우리는 잘 알려진 벤치마크 게임인 3인 쿠한 포커 (three-player Kuhn poker)의 일반화된 버전에서 PED의 성능을 탐색합니다. 기존의 어떤 정확한 알고리즘도 덱 크기가 4보다 큰 버전의 게임으로 확장되지 못하며, 우리는 이를 인기 있는 알고리즘인 허구적 놀이 (fictitious play, FP) 및 반사실적 후회 최소화 (counterfactual regret minimization, CFR)와 성능을 비교합니다. 우리는 PED가 모든 실행 과정에서 일관되게 거의 단조적인 (near-monotonic) 개선을 보인다는 것을 발견했습니다. 비록 FP와 CFR 모두 초기 반복 (iterations) 단계에서는 현저히 더 나은 성능을 보이지만 말입니다. 이는 초기 번인 (burn-in) 기간 동안 FP를 실행한 후, 안정적인 장기 정교화 (long-run refinement)를 위해 PED로 전환하는 하이브리드 알고리즘 FP-PED에 영감을 줍니다. 우리는 이를 대안적으로, PED를 위한 강력한 초기화 값을 얻기 위해 FP를 전처리 단계로 실행하는 다단계 알고리즘으로 볼 수도 있습니다.