기술 요약: 불완전 정보 하의 제로섬 확률 게임에서의 이질적 학습 (Heterogeneous Learning)

문제 정의

본 논문은 플레이어(에이전트)들이 불완전한 정보를 가지고 운영되는 동적, 분산형 환경에서의 학습 문제를 다룬다. 구체적으로, 저자들은 다음과 같은 조건의 2인 제로섬 확률 게임(two-person zero-sum stochastic game)을 고려한다:

• 플레이어는 자신의 보수 함수(유틸리티 행렬의 항목)를 알지 못한다.
• 플레이어는 상대방의 과거 행동에 대한 지식이 없다.
• 상태 공간(state space)과 전이 법칙(transition laws)은 플레이어들에게 알려져 있지 않다.
• 에이전트 간의 통신은 비실용적이다.

이러한 설정에서는 상대방의 행동 이력을 관찰하는 것에 의존하는 가상 놀이(fictitious play)나 최적 대응(best response) 역학(dynamics)과 같은 표준 학습 알고리즘을 적용할 수 없다. 더욱이, 기존의 강화 학습(RL) 알고리즘은 전략 강화와 보수 강화 중 하나에만 집중하는 경우가 많으며, 이 둘을 결합하는 데에는 한계가 있다. 핵심적인 질문은 최소한의 정보와 자원을 요구하면서도, 에이전트가 최적 전략을 학습하고 최적 보수를 동시에 추정할 수 있게 하는 완전 분산형 학습 체계를 어떻게 설계하느냐 하는 것이다.

방법론

저자들은 에이전트들이 서로 다른 학습 패턴(알고리즘)을 채택하거나 서로 다른 학습 속도(시간 척도)로 작동할 수 있는 이질적 학습 체계(heterogeneous learning schemes) 클래스를 제안한다.

게임 모델

연구는 $\Xi = \langle S, A_1, A_2, \{U(s, .)\}_{s \in S} \rangle$ 형태의 2인 제로섬 확률 게임 모델을 활용한다.

• $S$: 상태 집합 (플레이어에게는 미지의 값이며, i.i.d. 확률 변수임).
• $A_1, A_2$: 유한한 행동 집합.
• $U$: 플레이어 1(P1)은 최대화하고 플레이어 2(P2)는 최소화하는 유틸리티 함수.
• 플레이어들은 시간 $t$에서 혼합 전략 $f_t$와 $g_t$를 사용한다.

학습 알고리즘 (CODIPAS-RL)

핵심 방법론은 결합된 완전 분산형 보수 및 전략 강화 학습(CODIPAS-RL) 프레임워크이다. 이 접근 방식은 기대 보수를 학습하는 것과 전략을 학습하는 것을 결결합한다. 저자들은 이 프레임워크 내에서 다섯 가지 특정 알고리즘을 정의한다:

1. CRL0: 관찰된 보수의 가중 평균을 통해 전략과 보수를 업데이트하는 기본적인 결합 알고리즘 (Q-learning과 전략 업데이트가 결합된 것과 유사함).
2. CRL1: 전략 업데이트가 추정된 평균 보수의 소프트맥스(soft-max) 함수를 따르는 볼츠만-깁스(Boltzmann-Gibbs) 기반 알고리즘.
3. CRL2: CRL1과 유사하지만, 현재 전략 벡터에 의해 소프트맥스가 가중치 부여되는 모방적(imitative) 볼츠만-깁스 전략을 사용함.
4. RL2: 명시적인 보수 추정 결합 없이 표준 전략 강화 알고리즘(레플리케이터 역학과 유사함)을 사용하는 방식.
5. RL3: RL2의 정규화된 버전.

분석 접근 방식

저자들은 이산 시간 학습 알고리즘의 수렴을 분석하기 위해 **확률 근사 기법(stochastic approximation techniques)**을 사용한다. 이들은 확률적 학습 과정을 결정론적인 상미분 방정식(ODE) 대응물로 매핑한다.

• 분석은 한 플레이어가 다른 플레이어보다 현저히 빠르게 학습하는 경우(예: $\lambda_{1,t} / \lambda_{2,t} \to 0$)와 같은 이질적 학습 속도를 고려한다.
• 결과적으로 도출된 ODE는 사용된 알고리즘과 학습 속도의 특정 조합에 따라 표준 레플리케이터 역학, 최적 대응 역학, 로짓(logit) 역학 및 가상 놀이와는 다르게 나타난다.

주요 기여

1. 이질적 학습 프레임워크: 본 논문은 에이전트들이 서로 다른 학습 체계(예: 한 명은 CRL1을 사용하고 다른 한 명은 RL2를 사용)를 채택하고 서로 다른 시간 척도에서 작동할 수 있는 프레임워크를 도입한다.
2. 결합된 보수-전략 학습: 상대방의 행동에 대한 지식을 요구하지 않고 전략 벡터와 추정된 평균 보수를 동시에 업데이트함으로써, 전략과 가치 학습을 분리하는 일반적인 RL과 차별화되는 CODIPAS-RL 알고리즘을 제시한다.
3. ODE 특성화: 이질적 체계의 점근적 거동을 지배하는 특정 ODE를 도출한다. 저자들은 플레이어들이 서로 다른 속도로 학습할 때, 시스템 역학이 '빠른' 플레이어의 매끄러운 최적 대응(smooth best response)에 반응하는 '느린' 플레이어의 궤적 또는 그 반대로 묘사될 수 있음을 보여준다.
4. $\epsilon$-안장점(Saddle Points)으로의 수렴: 이러한 이질적 역학이 기대 게임의 $\epsilon$-안장점으로 거의 확실하게(almost surely) 수렴함을 입증한다. 소프트맥스 파라미터 $\epsilon \to 0$일 때, 이 지점들은 진정한 안장점으로 수렴한다.
5. 지배된 전략의 제거: CRL1 알고리즘 하에서, 저자들은 엄격하게 지배되는 전략(strictly dominated strategies)이 장기적으로 제거됨을 증명한다.

결과

• 수렴: 본 논문은 CRL1, RL2, RL3의 조합(예: CRL1 대 RL2, CRL1 대 CRL2)이 제로섬 확률 게임의 안장점 해로 수렴함을 증명한다.
• 시간-척도 분리: 한 플레이어가 더 빨리 학습할 때, 느린 플레이어의 궤적은 빠른 플레이어의 전략에 대한 매끄러운 최적 대응(또는 조정된 레플리케이터 역학)으로 수렴한다.
• 시뮬레이션 (보안 게임 응용): 저자들은 알고리즘을 네트워크 침입 탐지 시나리오(공격자 vs 방어자)에 적용한다.
  • 시나리오: 확률적 보수를 갖는 $2 \times 2$ 게임.
  • 동질적 경우 (Homogeneous Case): 두 플레이어 모두 CRL1을 사용할 때, 보수와 전략은 게임의 가치(약 2.6)와 안장점 전략($f^*=[0.4, 0.6]$, $g^*=[0.2, 0.8]$)으로 수렴하지만, 수렴 속도는 느리다.
  • 이질적 경우 (Heterogeneous Case): 공격자가 CRL1을 사용하고 방어자가 RL2를 사용할 때도 시스템은 수렴하며, 이는 이질적 접근 방식의 견고함을 입증한다.

의의 및 주장

본 논문은 최소한의 정보 요구 사항을 갖춘 분산 환경에서의 학습이라는 주요 과제를 해결하는 데 기여했다고 주장한다. 플레이어가 상대방의 행동 이력을 관찰해야 한다는 가정을 완화함으로써, 제안된 알고리즘은 그러한 관찰이 "불가능하고 비실용적인" 실제 네트워킹 및 보안 시나리오에 더 적합하다.

저자들은 다음과 같은 점을 강조한다:

• 이질적 학습에 대한 이론적 토대를 제공하여, 실제 시스템(공격자와 방어자 등)의 에이전트들이 서로 다른 수준의 합리성과 정보를 가지고 있음을 인정한다.
• 오직 국소적인 보수 관찰만을 필요로 하는 완전 분산형 알고리즘 클래스를 제공한다.
• 표준 레플리케이터 또는 최적 대응 모델을 넘어 학습의 이해를 확장하며, 서로 다른 학습 속도와 체계가 어떻게 여전히 평형으로 수렴하는 새로운 동적 거동을 만들어내는지 보여준다.

본 논문은 향로 연구로서 제어된 상태를 가진 확률 게임 및 비제로섬 게임으로의 확장을 언급하며 겸허하게 마무리된다.