Learning in Matching Games with Bandit Feedback

기술 요약: 매칭 게임에서의 밴딧 피드백을 통한 학습

문제 정식화
본 논문은 양측 매칭 시장(two-sided matching markets)과 게임 이론의 교차점에 위치한 새로운 학습 문제를 소개한다. 이 설정은 두 개의 서로 다른 에이전트 집합 $P$와 $A$가 존재하는 일반화된 시장을 포함하며, 이들은 시간 지평 $T$ 동안 중앙 플랫폼에 의해 매칭된다. 에이전트가 정적인 알려진 선호도를 갖는 전통적인 매칭 문제나, 에이전트가 직접적인 확률적 보상을 받는 표준 멀티 암드 밴딧(MAB) 설정과 달리, 이 프레임워크는 일단 매칭되면 에이전트들이 초기에 알 수 없는 보상 행렬(payoff matrix)을 가진 2인 제로섬 게임(ZSG)을 수행한다고 가정한다.

이 시나리오에서 에이전트들은 매칭된 후의 상호작용 결과로부터 기저의 게임 역학을 학습하는 동시에 자신의 선호도를 도출해야 한다. 각 시간 단계 $t$에서:

1. 중앙 플랫폼은 추정된 에이전트 선호도를 바탕으로 매칭 $m_t$를 생성한다.
2. 매칭된 에이전트들은 전략(혼합 행동)을 선택하고 특정 행동을 샘플링한다.
3. 에이전트들은 확률적 밴딧 피드백(보상)을 받고 상대방의 행동을 관찰한다.
4. 에이전트들은 다음 라운드를 위해 보상 행렬과 자신의 선호도를 업데이트한다.

핵심 과제는 **매칭 균형(Matching Equilibrium)**을 학습하는 것이다. 이는 [10]에서 정의된 개념으로, 매칭이 안정적(blocking pair가 없음)이고 에이전트들이 할당된 파트너와 내쉬 균형(NE)을 이루는 상태를 의미한다. 난이도는 에이전트들이 사전에 게임 행렬을 알지 못하여 선호도를 형성하기 위해 탐색(exploration)을 수행해야 하는 반면, 매칭 메커니즘(일반적으로 Gale-Shapley)은 안정성을 보장하기 위해 이러한 선호도에 의존한다는 점에서 발생한다.

방법론 및 알고리즘
이를 해결하기 위해 저자들은 "불확실성에 대한 낙관주의(optimism in the face of uncertainty)" 원리에 기반한 UCB-MG 알고리즘을 제안한다. 방법론은 다음과 같이 작동한다:

• 낙관적 추정(Optimistic Estimates): 에이전트들은 잠재적 매치에 대한 보상 행렬의 상한 신뢰 구간(UCB)을 유지한다. 구체적으로, 쌍 $(p, a)$에 대해 추정된 보상 행렬 $\bar{A}_{p,a}$는 관찰된 보상의 경험적 평균에 신뢰 보너스를 더하여 구성된다.
• 선호도 형성(Preference Formation): 이러한 낙관적 보상 행렬을 바탕으로, 에이전트들은 각 잠재적 파트너에 대한 최적 플레이(minimax 전략)를 가정하여 낙관적 게임 가치($\bar{V}^*$)를 계산한다. 에이전트들은 이 낙관적 게임 가치에 따라 자신의 선호도를 순위 매긴다.
• 매칭(Matching): 중앙 플랫폼은 이러한 보고된 선호도를 수집하고 현재 라운드의 안정적 매칭을 생성하기 위해 Gale-Shapley(GS) 알고리즘을 실행한다.
• 전략 실행(Strategy Execution): 일단 매칭되면, 에이전트들은 낙관적 보상 행렬에서 유도된 minimax 전략에 따라 행동을 선택하고, 행동을 샘플링하며, 피드백을 받아 추정치를 업데이트한다.

후회(Regret) 정식화: 매칭 불안정성(Matching Instability)
본 논문의 중요한 기여 중 하나는 **매칭 불안정성(Matching Instability, MI)**이라 불리는 적절한 후회 지표를 정의한 것이다. 표준 MAB 또는 게임 이론의 후회 정의는 매칭과 전략의 결합 균형으로 수렴하는 것을 목표로 하는 본 연구의 목적에 부적합하다.

저자들은 MI를 현재의 매칭 $m$과 전략 프로필 $X$가 주어졌을 때 시장을 안정화하기 위해 필요한 최소 총 보조금(subsidy)으로 정의한다. 수학적으로 이는 보조금 $s_a$를 최소화하는 선형 계획법의 해이다:

1. 차단 쌍 없음(No Blocking Pairs): 현재 전략이 주어졌을 때, 어떤 쌍 $(p, a)$도 이탈을 통해 효용을 개선할 수 없도록 보장한다.
2. 개별 합리성(Individual Rationality): 에이전트들이 매칭되지 않은 상태보다 매칭된 상태를 선호하도록 보장한다.
3. 가치 보장(Value Guarantee): 에이전트들이 자신의 게임의 minimax 값과 같거나 높은 효용을 받도록 보장한다(분석의 용이성을 위해 엄격한 내쉬 조건을 완화함).

누적 후회 $R_T$는 시간 지평 $T$ 동안의 매칭 불안정성의 합으로 정의된다.

주요 기여

1. 학습 문제 정의: 본 논문은 양측 시장의 에이전트들이 매칭을 위한 선호도를 형성하기 위해 미지의 제로섬 게임을 학습해야 하는 최초의 학습 환경을 정식화하였다.
2. 후회 지표: 매칭된 에이전트들이 게임을 수행하는 설정으로 Subset Instability [8, 17]의 개념을 확장하여 매칭 불안정성을 도입하였다. 이 지표는 매칭 균형으로부터의 거리를 정량화한다.
3. 알고리즘 설계: 낙관적 게임 가치 추정과 Gale-Shapley 메커니즘을 통합하는 UCB 기반 알고리즘(UCB-MG)을 제안한다.
4. 이론적 보장: 제안된 알고리즘이 $T$가 시간 지평이고, $m$과 $k$가 에이전트당 행동 수, $p$와 $a$가 각 측의 에이전트 수일 때, 인스턴스 독립적인 $\tilde{O}(\sqrt{Tmkpa})$의 부치선형(sublinear) 후회 상한을 달라는 것을 증명한다.
5. 일반화: 이 이론적 상한은 기존 결과들을 통합한다. $m=k=1$일 때, 고전적인 양측 매칭의 상한 $\tilde{O}(\sqrt{Tpa})$를 회복한다. $p=a=1$일 때, 제로섬 게임의 셀프 플레이(self-play) 상한 $\tilde{O}(\sqrt{Tmk})$를 회복한다.

결과 및 실증적 증거
저자들은 보상 행렬이 정규 분포에서 샘플링된 합성 인스턴스를 사용하여 실증적 검증을 제공한다. 이들은 세 가지 시나리오를 비교한다:

• 셀프 플레이(Self-Play): 양측 모두 UCB-MG 알고리즘을 따른다.
• 내쉬 응답(Nash-Response): 한쪽은 실제 게임 행렬을 알고 내쉬 균형 전략을 수행하며, 다른 한쪽은 학습한다.
• 최적 대응(Best-Response): 한쪽은 실제 행렬과 상대방의 전략을 알고 최적 대응을 수행한다.

결과는 시스템이 모든 시나리오에서 안정적인 결과를 학습하며, 부치선형 후회 성장을 보임을 나타낸다. 예상대로 내쉬 응답 시나리오가 가장 낮은 후회를 기록한다. 흥미롭게도, 최적 대응 시나리오는 초기에는 셀프 플레이보다 성능이 뛰어나지만, 시장 규모(에이전트 및 행동 수)가 커짐에 따라 성능이 저하되는데, 이는 한쪽이 다른 쪽을 착취하는 데서 오는 복잡성 때문인 것으로 보인다.

의의 및 향후 방향
본 논문은 에이전트들이 직접적인 선호 신호를 받는 대신, 게임 내 행동을 통한 상호작용 후에만 보상을 받는 환경에서의 학습을 이해하기 위한 첫 걸음으로서의 의의를 갖는다. 이는 복잡하고 결합된 설정에서도 안정적인 결과가 효율적으로 학습될 수 있음을 보여준다.

저자들은 이 연구를 향후 연구를 위한 토대로 겸허히 규정하며, 몇 가지 개방된 방향을 제시한다:

• 모델을 제로섬 게임에서 일반 합 게임(general-sum games)으로 확장.
• 비제로섬 역학을 다루기 위해 no-regret 학습 알고리즘(예: Exp3)을 매칭 프레임워크에 통합.
• 에이전트가 파트너의 행동을 관찰한다는 가정을 완화.
• 대안적인 게임 모델(마르코프 게임, 스태켈버그 게임) 및 매칭 구조(one-to-many 시장) 탐색.
• 중앙 조정자 없이 에이전트가 매칭과 전략을 모두 선택하는 분산 환경 조사.