Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

기술 요약: 순위 기반 확률적 보상 수집 게임에서의 서수 응답 정책 학습

1. 문제 정의

본 논문은 다중 에이전트 시스템에서 **팀 오리엔티어링 문제(Team Orienteering Problem, TOP)**가 가진 한계를 다룹니다. TOP는 협력적 라우팅(예: 라스트 마일 배송, 감시)을 위한 통합된 프레임워크를 제공하며, 에이전트들이 이동 예산 하에서 집단적 효용을 극대화하도록 하지만, 자원이 희소한 환경에서 경쟁하는 자기 이익 중심의 에이전트들을 모델링하는 데에는 실패합니다. 이러한 설정에서 에이전트들(예: 경쟁하는 배송 차량 또는 크라우드 소싱 드라이버)은 집단적 이득보다 개인의 보상을 우선시하며, 이들의 상호작용은 확률적 전이와 에너지 제약에 의해 결정됩니다.

이러한 간극을 메우기 위해 저자들은 **확률적 보상 수집 오리엔티어링 게임(Stochastic Prize-Collecting Orienteering Game, SPCOG)**을 제안합니다. SPCOG에서:

• 에이전트는 노드에 확률적으로 분포된 가중치 보상이 있는 가중 그래프 위에서 작동합니다.
• 에이전트는 개별 이동 예산을 가지며, 자신의 누적 보상을 극대화하는 것을 목표로 합니다.
• 갈등 해결: 여러 에이전트가 동시에 동일한 노드를 방문할 경우, 순위 기반 규칙이 적용됩니다. 즉, 가장 높은 글로벌 순위(가장 낮은 인덱스)를 가진 에이전트가 보상을 독점하며, 다른 에이전트들은 보상을 받지 못합니다.
• 목표: 경쟁으로 인해 전체 팀 보상이 협력적 TOP의 최적해보다 낮아질 수 있음을 인정하면서, 독립적인 에이전트들이 개인의 보상을 극대화하기 위한 수렴 정책을 찾는 것입니다.

2. 방법론

평형에 대한 이론적 분석
저자들은 먼저 SPCOG에서 **순수 내쉬 평형(Pure Nash Equilibrium, PNE)**의 존재를 분석합니다:

• 완전 그래프(Complete Graphs): 순위 기반 갈등 해결 조건하에서 완전 그래프의 경우 유일한 PNE가 존재함을 증명합니다. 이 평형에서 $i$번째 순위의 에이전트는 사용 가능한 보상 중 $i$번째로 큰 보상을 선택합니다. 이 PNE에서의 총 보상은 동등한 협력적 TOP의 최적해와 일치합니다.
• 스타 그래프(Star Graphs): 에이전트들이 교대 단계마다 $i$번째로 큰 보상으로 이동하는 유사한 유일 PNE가 존재합니다.
• 임의의 그래프(Arbitrary Graphs): 에이전트들이 동시에 이동할 때 임의의 그래프 구조에서는 PNE가 반드시 존재하지는 않는다는 것을 특정 2인 시나리오를 통한 반례를 통해 입증하며, 이는 스택켈버그(Stackelberg, 리더-팔로워) 정식화와 비교하여 이 게임의 복잡성을 강조합니다.

서수 순위(Ordinal Rank, OR) 개념
부분 관측성과 일반 그래프에서의 지수적 상태 공간 문제를 해결하기 위해, 저자들은 **서수 순위(OR)**를 도입합니다:

• 직접적인 상대(Immediate Opponents): 에이전트들은 에이전트 간의 도달 가능한 집합이 겹치는 엣지로 연결된 "분리 그래프(separating graph)"를 기반으로 "국소적 단계 게임(localized stage games)"으로 그룹화됩니다.
• 정의: 에이전트의 OR은 자신의 직접적인 이웃(연결 성분) 내에서 자신보다 높은 글로벌 순위(낮은 인덱스)를 가진 에이전트 수에 1을 더한 값으로 정의됩니다.
• 의의: OR은 가장 영향력 있는 국소적 경쟁을 요약합니다. 저자들은 글로벌 상태나 글로벌 순위 대신 OR에 정책을 조건화하는 것이 강력한 귀납적 편향(inductive bias)으로 작용하여, 에이전트가 글로벌 정보 없이도 직접적인 상대에 대한 최적 대응을 학습할 수 있게 한다고 가설을 세웁니다.

가상 서수 응답 학습(Fictitious Ordinal Response Learning, FORL)
저자들은 독립적 다중 에이전트 강화 학습(MARL)을 위해 설계된 엔트로피 조절 학습 알고리즘인 FORL을 제안합니다:

• 순차적 업데이트: 에이전트들은 순위에 따라 순차적으로 정책을 업데이트합니다. 높은 순위의 에이전트가 먼저 업데이트하며, 낮은 순위의 에이전트들은 무작위 또는 정적 정책을 따른다고 가정합니다.
• 부트스트래핑(Bootstrapping): 가장 높은 순위의 에이전트가 기초적인 확률적 단일 에이전트 문제를 해결하며 먼저 학습합니다. 이 에이전트의 정책이 신뢰도 임계값(엔트로피로 측정)에 도달하면, 그 파라미터가 다른 에이전트들과 공유됩니다.
• 가상 놀이(Fictitious Play): 후속 에이전트들은 높은 순위 에이전트들의 "정적" 정책을 상대로 정책을 업데이트합니다.
• 엔트로피 조절: 알고리즘은 수렴을 보장하기 위해 감쇠하는 엔트로피 임계값($H_{stop}$)을 사용합니다. 만약 PNE가 존재한다면 알고리즘은 순수 전략(엔트로피 $\to$ 0)으로 수렴하며, 그렇지 않다면 혼합 전략 정책의 품질에 대한 신뢰 구간을 제공합니다.
• 정책 아키텍처: 정책은 Transformer 기반 아키텍처(TRXL-I)를 사용하여 모델링되며, OR이 추가된 국소 관측치에 조건화됩니다. 그래프 제약을 강제하기 위해 액션 마스킹(Action masking)이 사용됩니다.

3. 주요 기여

1. SPCOG 정식화: 확률적이고 에너지 제약이 있는 환경에서 자기 이익 중심의 에이전트를 위한 게임 이론적 변형인 TOP을 도입했습니다.
2. 이론적 보장: 최적의 TOP 솔루션과 일치하는 완전 그래프 및 스타 그래프에서의 유일한 PNE를 증명하였으며, 임의의 그래프에서 PNE가 존재하지 않을 수 있음을 보여주는 반례를 제시했습니다.
3. 서수 순위(OR): 에이전트의 경쟁적 위치를 나타내는 간결한 국소 표현으로서 OR을 제안하였으며, 이는 강력한 귀납적 편향 역할을 합니다.
4. FORL 알고리즘: 독립적 학습 환경에서 수렴하는 정책을 생성하는 엔트로피 조절 및 가상 놀이 기반 알고리즘을 개발했습니다.
5. 실험적 검증: OR 조건화 정책이 글로벌 상태 및 글로벌 순위에 조건화된 정책보다 일반화 성능, 확장성 및 학습 효율성 측면에서 우수함을 입증했습니다.

4. 실험 결과

실험은 정적 및 동적 보상 분포를 가진 실제 도로 네트워크(스톡홀름 및 맨해튼)에서 수행되었습니다.

• TOP 대비 성능: 완전 그래프에서 OR 조건화 정책은 최적 TOP 보상의 **95%**를 달성했습니다. 불완전 그래프에서 최악의 평형은 최적해의 **87%**를 달성했습니다.
• 일반화 능력: FORL과 OR 조건화를 통해 훈련된 정책은 글로벌 상태에 조건화된 독립 정책 학습(IPL) 및 파라미터 공유 방식에 비해 불균형하고 수요 중심적인 보상 분포에 대해 우수한 "제로샷(zero-shot)" 전이 능력을 보여주었습니다.
• 확장성: 최대 25명의 에이전트로 규모를 확장했을 때, OR에 조건화된 정책(PS-OR)은 낮은 분산과 함께 총 보상에서 선형적 확장을 보였습니다. 반면, 글로벌 순위에 조건화된 정책(PS-GR)은 아선형적 이득과 훨씬 높은 분산을 보였습니다.
• 효율성: FORL 방식은 표준 파라미터 공유 및 독립 학습 베이스라인과 비교하여 유사한 보상 프로필에 도달하는 데 1.56배에서 2.2배 적은 훈련 시간이 소요되었습니다.

5. 의의 및 주장

본 논문은 서수 순위(Ordinal Rank) 개념이 다중 에이전트 라우팅 게임에서 글로벌 상태 정보의 필요성을 효과적으로 제거한다는 점을 주장합니다. 직접적인 상대와 그들의 상대적 순위에 집중함으로써, 에이전트는 더 큰 팀 규모와 미지의 환경에 잘 일반화되는 견고한 전략을 학습할 수 있습니다.

저자들은 FORL이 전통적인 협력적 가정이 실패하는 경쟁적이고 확률적인 라우팅 게임에서 수렴하는 정책을 얻기 위한 실질적인 메커니즘을 제공한다고 단언합니다. 이 연구는 순위 기반 갈등 시나리오에서, 국소 정보가 서수 위치에 조건화될 때가 글로벌 상태나 글로벌 순위에 조건화될 때보다 더 효과적인 학습 신호가 된다는 것을 시사하며, 이는 이질적이고 자기 이익을 추구하는 로봇 플릿(fleet)을 위한 확장 가능한 솔루션을 제공합니다.