기술 요약: 동시 확률적 게임의 강건한 검증

1. 문제 정의

드론 협업, 로봇 탐사 등 다중 에이전트 환경에서 작동하는 자율 시스템은 종종 불확실성 하에서 동시적인 전략적 의사결정을 필요로 한다. **동시 확률적 게임(Concurrent Stochastic Games, CSGs)**은 이러한 시스템을 모델링하기 위한 강력한 프레임워크를 제공하지만, 표준적인 검증 기법들은 전이 확률이 정확히 알려져 있다고 가정한다. 실제로 이러한 확률은 모델링의 부정확성, 노이즈, 추상화 또는 제한된 데이터(강화 학습에서 흔히 발생하는 현상)로 인한 **인식론적 불확실성(epistemic uncertainty)**에 노출될 수 있다.

표준 CSG 검증은 기초가 되는 모델이 약간만 틀리더라도 신뢰할 수 없는 보장을 제공할 수 있다. **강건한 마르코프 결정 과정(Robust Markov Decision Processes, RMDPs)**이 단일 에이전트 시스템을 위해 가능한 전이 확률의 집합을 고려함으로써 이를 해결하는 반면, 다중 에이전트 동시 설정을 위한 유사한 프레임워크는 그동안 충분히 발전하지 못했다. 핵심 과제는 플레이어들이 동시에 행동하고, "자연(nature)" 플레이어(불확실성을 해결하는 역할)가 여러 전략적 에이전트와 상호작용하는 동시 게임에 강건성을 확장하는 것이다.

2. 방법론

본 논문은 **강건한 동시 확률적 게임(Robust Concurrent Stochastic Games, RCSGs)**을 도입하며, 전이 확률이 구간 내로 제한되는 **구간 CSG(Interval CSGs, ICSGs)**라는 다루기 쉬운 하위 클래스에 초점을 맞춘다. 방법론은 이론적 토대, 게임 이론적 환원, 그리고 알고리즘 구현을 포함한다.

2.1 이론적 프레임워크

저자들은 최악의 상황 가설 하에서 제로섬(zero-sum) 및 비제로섬(nonzero-sum) 설정 모두에 대한 강건한 솔루션 개념을 정의한다:

• 제로섬: 이 프레임워크는 미니맥스(minimax) 개념을 적응시킨다. 게임이 **강건하게 결정(robustly determined)**된다는 것은 플레이어와 "자연"(불확실성을 해결하는 대립자)이 행동하는 순서에 관계없이 가치가 일관되게 유지됨을 의미한다. 본 논문은 유한 분기 ICSG에서 **플레이어 우선(player-first)**과 자연 우선(nature-first) 의미론이 동일한 강건한 가치를 산출함을 증명한다.
• 비제로섬: 본 논문은 **강건한 내쉬 균형(Robust Nash Equilibria, RNE)**과 **강건한 사회적 후생 최적 내쉬 균형(Robust Social-Welfare Optimal NE, RSWNE)**을 도입한다. RNE는 어떠한 불확실성 해결 상황에서도 내쉬 균형으로 유지되는 전략 프로파일이다. 저자들은 존재성을 보장하기 위해 서브게임 완전 $\epsilon$-RNE에 집중한다.

2.2 표준 게임으로의 환원

핵심 기여 중 하나는 **대립적 확장(Adversarial Expansion)**을 통해 강건한 검증 문제를 표준(비강건) CSG로 환원하는 것이다:

• 제로섬 환원: ICSG는 플레이어 1에게 불리하게 작용하는 세 번째 "자연" 플레이어를 추가함으로써 2-플레이어 CSG($G_A$)로 환원된다. 플레이어 2와 자연은 플레이어 1의 보상을 최소화한다는 목표를 공유하므로 하나의 연합을 형성한다. 원래 ICSG의 강건한 가치는 이 확장된 2-플레이어 CSG의 가치와 같다.
• 비제로섬 환원: 이 환원은 플레이어 1과 플레이어 2의 사회적 후생(효용의 합)을 최소화함으로써 두 플레이어 모두에게 대립적으로 작용하는 3-플레이어 CSG($G_A$)를 생성한다.
  • 과제: 확장된 3-플레이어 게임에서의 내쉬 균형이 반드시 원래 게임의 RNE를 의미하는 것은 아니다. 왜냐하면 자연의 사회적 후생(효용의 합) 최소화가 반드시 개별 효용의 최소화를 보장하지 않기 때문이다.
  • 해결책: 저자들은 필터링 단계를 제안한다. $G_A$에서 균형을 계산한 후, **편차 IMDP(Interval MDPs)**를 사용하여 각 개별 플레이어에 대한 자연의 최악의 선택에 대해 프로파일이 RNE 조건을 만족하는지 확인하여 프로파일을 필터링한다.

2.3 알고리즘

본 논문은 이러한 환원된 게임들을 해결하기 위한 효율적인 알고리즘을 개발한다:

• 무한 시계(Infinite-Horizon): **강건한 가치 반복(Robust Value Iteration, RVI)**을 사용한다. 각 상태와 결합 행동에 대해, 내부 최적화 문제(구간 내 최악의 전이 분포 찾기)를 해결한 다음 선형 계획법(LP) 또는 바이매트릭스 게임 솔루션을 수행한다.
• 유한 시계(Finite-Horizon): **강건한 역방향 귀납법(Robust Backward Induction, RBI)**을 사용한다.
• 구현: 이 알고리즘들은 PRISM-games 모델 체커에 구현되었다. 이 접근 방식은 내부 문제와 정규형 게임(NFG)을 온더플라이(on-the-fly)로 해결함으로써 전체 확장 상태 공간을 명시적으로 구축하는 것을 피한다.

3. 주요 기여

1. 모델 정의: 구간 경계 전이 불확실성을 가진 다중 에이전트 동시 시스템을 모델링하기 위한 RCSG 및 ICSG의 도입.
2. 이론적 토대:
   • 제로섬 ICSG에서 플레이어 우선과 자연 우선 의미론 사이의 가치 등가성 증명.
   • 강건한 내쉬 균형 및 RSWNE 개념 확립.
   • 강건한 검증이 표준 CSG(제로섬의 경우 2-플레이어, 비제로섬의 경우 필터링을 포함한 3-플레이어)를 푸는 것으로 환원될 수 있음을 입증.
3. 알고리즘 구현: 강건한 동적 계획법과 표준 CSG 솔루션 기법(가치 반복, Lemke-Howson)을 통합하여 유한 및 무한 시계에 대한 다루기 쉬운 알고리즘 개발.
4. 경험적 평가: PRISM-games에서의 구현 및 변동된 전이 확률($\pm \epsilon$)을 가진 벤치마크(로봇 협업, Aloha, 재밍 라디오 시스템)에 대한 평가.

4. 실험 결과

저자들은 변동된 전이 확률($\pm \epsilon$)을 가진 벤치마크를 사용하여 제안된 방식을 표준(비강건) CSG와 비교 평가하였다.

• 제로섬 성능: ICSG의 검증 시간은 표준 CSG와 유사했으며, 통상적으로 2배 이내의 차이를 보였다. 이 방법은 200만 개 이상의 상태와 1,000만 개의 전이를 가진 모델을 성공적으로 처리했다. Aloha와 같은 일부 사례에서는 ICSG 검증이 수렴에 필요한 반복 횟수가 적어 더 빠르게 수행되기도 했다.
• 비제로섬 성능: 3-플레이어 환원 및 필터링 단계의 복잡성으로 인해 검증 시간이 더 높았다. 이 접근 방식은 최대 40만 개의 상태와 130만 개의 전이를 가진 모델까지 효과적으로 확장되었다.
• 불확실성($\epsilon$)의 영향:
  • 검증 시간은 $\epsilon$에 대해 비단조적(non-monotonic)이었다. 반복당 비용과 수렴 속도 사이의 트레이드오프 때문에 중간 값일 때가 매우 작거나 매우 큰 값일 때보다 더 느린 경우가 많았다.
  • $\epsilon$이 증가함에 따라 더 보수적인(낮은) 가치가 산출되었으며, 이는 검증 결과에 대한 신뢰 구간을 효과적으로 제공한다.

5. 의의 및 주장

본 논문은 다중 에이전트 동시 시스템의 인식론적 불확실성을 추론하기 위한 원칙적인 프레임워크를 제공함으로써 형식 검증의 중요한 공백을 메운다고 주장한다.

• 실용성: 저자들은 강건한 검증이 이론적 구성물이 아닌 대규모 시스템에서도 실행 가능하다는 것을 입증했다. 제로섬 케이스는 표준 검증과 유사하게 확장 가능하므로, 안전이 중요한 적대적 시나리오에 즉시 적용 가능하다.
• 통찰: 비제로섬 결과는 특히 사회적 후생 최소화와 개별적 강건성 사이의 구분을 강조하며, 제안된 필터링 메커니즘이 필요할 만큼 다중 에이전트 강건 추론의 본질적인 복잡성을 부각시킨다.
• 토대: RCSG를 표준 CSG로 환원함으로써, 본 연구는 기존의 도구 지원(PRISM-games)과 이론적 결과들을 활용하여 자율 시스템의 강건한 분석을 위한 확장 가능한 경로를 제시한다.

저자들은 비제로섬 케이스가 더 높은 계산 요구량을 초래하지만, 본 프레임워크가 모델 부정확성에 강건한 전략을 합성할 수 있게 함으로써 불확실한 실제 환경에 자율 시스템을 배치하는 데 필수적인 요구 사항을 성공적으로 충족한다고 결론짓는다.