부분 관측 가능한 마르코프 게임에서의 미니맥스 최적 정책 후회 (Minimax-Optimal Policy Regret in Partially

우리는 부분 관측 가능한 마르코프 게임 (Partially Observable Markov Games, POMGs)으로 모델링된, 전략적이고 적응적인 상대방에 맞선 부분 관측 가능한 환경에서의 순차적 의사결정 (Sequential Decision-making)을 연구합니다. 핵심 과제는 학습자의 전략에 따라 행동이 달라지는 적대자 (Adversary)에 맞서면서, 부분적인 관측 (Partial Observations)으로부터 잠재적 역학 (Latent Dynamics)을 학습하는 것이며, 이로 인해 표준적인 후회 (Regret) 개념으로는 불충분합니다. 우리는 에포크 기반의 낙관적 최대 우도 알고리즘 (Epoch-based Optimistic Maximum-Likelihood Algorithm)이 고정된 문제 파라미터에 대해 $\tilde{O}(\sqrt{T})$의 정책 후회 (Policy Regret)를 달성함을 증명하며, 이는 호라이즌 (Horizon), 적대자의 메모리 (Adversary Memory), 신뢰 반경 (Confidence Radius), 그리고 관측 가능 연산자 클래스의 집합적 Eluder 차원 (Aggregate Eluder Dimension)에 명시적으로 의존합니다. 이 알고리즘은 과거 데이터로부터 누적적으로 구축된 신뢰 집합 (Confidence Sets)을 사용하여 기하급수적으로 증가하는 에포크당 하나의 정책을 선택하며, 이를 통해 정책 간의 적대자 반응을 비교하는 비용을 $T$에 대한 로그 수준으로 유지합니다. 또한 우리는 문제 의존적 및 로그 요인들을 제외하고, $\sqrt{T}$ 및 집합적 Eluder 차원 의존성과 일치하는 하한 (Lower Bound)을 증명합니다. 마지막으로, 우리는 이 프레임워크를 호라이즌 적응형 보장 (Horizon-adaptive Guarantees) 및 기하급수적으로 소멸하는 메모리 (Geometric Fading Memory)를 가진 적대자로 확장합니다.