Efficient Last-iterate Convergence Algorithms in Solving Games
Created by
Haebom
Category
Empty
저자
Linjian Meng, Youzhi Zhang, Zhenxing Ge, Shangdong Yang, Tianyu Ding, Wenbin Li, Tianpei Yang, Bo An, Yang Gao
개요
본 논문은 확장형 게임(EFG)의 내쉬 균형(NE) 학습에서 Counterfactual Regret Minimization (CFR) 알고리즘의 마지막 반복값 수렴을 확립하기 위해, 기존 EFG의 NE 학습을 일련의 (섭동된) 규제화된 EFG의 NE 학습으로 재구성하는 최근 연구들을 바탕으로 합니다. 기존 EFG를 푸는 것에서 마지막 반복값 수렴을 증명하는 것은 (섭동된) 규제화된 EFG를 푸는 것에서 마지막 반복값 수렴을 증명하는 것으로 축소됩니다. 하지만 기존 연구들의 알고리즘의 경험적 수렴 속도는 섭동된 EFG를 푸는 데 뛰어난 경험적 수렴 속도를 갖는 것으로 알려진 Regret Matching (RM) 기반 CFR 알고리즘을 사용하지 않기 때문에 최적이 아닙니다. 또한 여러 개의 섭동된 규제화된 EFG를 풀어야 하므로, 모든 게임에 걸쳐 미세 조정하는 것은 불가능하여 매개변수가 없는 알고리즘이 매우 바람직합니다. 본 논문에서는 매개변수가 없는 RM 기반 CFR 알고리즘인 CFR$^+$가 섭동된 규제화된 EFG의 NE 학습에서 마지막 반복값 수렴을 달성함을 증명합니다. 섭동된 규제화된 EFG를 푸는 데 CFR$^+$를 활용하여 Reward Transformation CFR$^+$ (RTCFR$^+$)를 얻습니다. 중요하게도, RTCFR$^+$의 경험적 수렴에 중요한 CFR$^+$의 매개변수가 없는 특성에 대한 이전 연구를 확장하여 안정성을 향상시킵니다. 실험 결과 RTCFR$^+$는 이론적으로 마지막 반복값 수렴 보장을 갖는 기존 알고리즘보다 성능이 훨씬 뛰어납니다.
시사점, 한계점
•
시사점:
◦
매개변수가 없는 RM 기반 CFR 알고리즘인 CFR$^+$가 섭동된 규제화된 EFG에서 마지막 반복값 수렴을 달성함을 증명.
