Learning to Contest: Decentralized Robust Fairness in Cooperative MARL via… — 쉬운 설명

한 무리의 친구들이 피자를 나누어 먹으려는 상황을 상상해 보세요. 그들은 모두 공정하기로 합의했습니다. 만약 누군가 정말 배가 고프다면, 아무도 굶어서 집에 가지 않도록 더 큰 조각을 주는 식입니다. 이것이 바로 "공정 다중 에이전트 강화 학습(Fair Multi-Agent Reinforcement Learning, MARL)"의 목표입니다. 즉, 컴퓨터 프로그램이 협력하고 자원을 평등하게 나누는 법을 가르치는 것입니다.

하지만 문제가 하나 있습니다. 만약 한 친구가 이기적으로 행동하여 자신을 위해 가장 큰 조각을 가로챈다면, 공정한 친구들은 난처한 상황에 처합니다. 그들은 공정하도록 프로그래밍되었기 때문에, "싸우고 싶지 않아"라고 생각하며 이기적인 친구가 조각을 가져가는 것을 그냥 내버려 둘 수도 있습니다. 혹은 싸우려고 시도하다가 서로 충돌하여 모두의 피자를 망쳐버릴 수도 있습니다.

**"경합하는 법 배우기(Learning to Contest)"**라는 제목의 이 논문은 까다로운 질문을 던집니다: 공정한 친구들이 상사(보스)의 지시 없이도 스스로를 방어할 수 있을까?

다음은 간단한 비유를 사용하여 이들이 문제를 해결한 과정을 설명한 이야기입니다.

1. 오래된 문제: "전부 아니면 전무(All-or-Nothing)" 피자

과거의 사고방식에서 자원은 '승자 독식' 게임과 같았습니다.

시나리오: 두 사람이 마지막 조각을 원합니다.
규칙: 만약 두 사람이 동시에 움켜쥐면, 조각은 뭉개져서 버려집니다 (남은 양 0%). 만약 한 명은 움켜쥐고 다른 한 명은 손을 놓으면, 움켜쥔 사람이 100%를 가져갑니다.
결과: 공정한 사람은 싸울 동기가 없습니다. 싸우면 아무것도 얻지 못하고, 포기하면 역시 아무것도 얻지 못하기 때문입니다. 그래서 그들은 그냥 포기합니다. 결국 이기적인 친구가 모든 것을 차지하게 됩니다.

2. 새로운 규칙: "등급이 매겨진(Graded)" 피자

저자들은 게임의 규칙을 약간 바꾸었습니다. 그들은 **"등급이 매겨진 경합(Graded Contention)"**을 도입했습니다.

새로운 규칙: 두 사람이 조각을 움켜쥐더라도 조각이 완전히 파괴되지 않습니다. 대신 약간 찌그러질 뿐입니다 (예를 들어 20%가 낭비됨). 하지만 남은 80%는 두 사람 사이에 나누어집니다.
마법: 이제 공정한 사람이 이기적인 사람과 싸우더라도 아무것도 얻지 못하는 것이 아니라, '무언가'(찌그러진 피자의 작은 조각)를 얻게 됩니다. 이기적인 사람은 혼자 가져갔을 때보다 적게 가져가게 됩니다.
교훈: 이제 싸우는 것이 포기하는 것보다 낫습니다! 이것이 공정한 팀에게 반격할 수 있는 "지렛대"를 제공합니다.

3. 새로운 도전: "추측 게임"

지렛대를 갖는 것만으로는 충분하지 않습니다. 공정한 팀은 까다로운 협력 문제를 마주합니다.

시나리오 A: 아무도 이기적으로 행동하지 않습니다. 이때 공정한 팀이 굳이 싸운다면, 그들은 찌그러진 피자를 낭비하게 됩니다.
시나리오 B: 한 사람이 이기적으로 행동합니다. 이때 공정한 팀이 싸우지 않는다면, 이기적인 사람은 모든 것을 먹어 치울 것입니다.
딜레마: 공정한 팀은 방 안에 이기적인 사람이 '몇 명'이나 있는지 알지 못합니다. 그들은 주변을 살피고, 문제아의 수를 세고, 결정해야 합니다: "싸울 것인가, 아니면 그냥 평화롭게 나눌 것인가?"

4. 해결책: CAN (스마트한 관찰자)

저자들은 CAN(Cross-Attention Networks)이라는 새로운 시스템을 만들었습니다. CAN을 특별한 안경을 쓴 아주 똑똑한 팀 캡틴이라고 생각해보세요.

작동 방식: 모든 에이전트(친구)에게 무엇을 할지 알려주는 보스가 있는 대신, 각 에이전트는 다른 모든 이가 무엇을 하고 있는지 관찰합니다.
"교차 주의(Cross-Attention)" 기술: 각 에이전트가 스포트라이트를 가지고 있다고 상상해 보세요. 그들은 스포트라이트를 비추어 타인의 행동을 살핍니다.
- 만약 모두가 차분하다는 것을 발견하면, 스포트라이트는 "안심하세요, 평화롭게 나눕시다"라고 말합니다.
- 만약 누군가 탐욕스럽게 행동하는 것을 발견하면, 스포트라이트는 "이봐요, 저 사람이 움켜쥐고 있어요! 피자를 낭비할 정도로 세게 하지는 않되, 저 사람을 막을 수 있을 만큼만 밀어붙입시다"라고 말합니다.
훈련: 그들은 다양한 유형의 이기적인 플레이어들과 대결하게 함으로써 이 시스템을 훈련시켰습니다. 이를 통해 패턴을 인식하고 실시간으로 전략을 조정하는 법을 배웠습니다.

5. 결과: 두 마리 토끼를 잡다

이 논문은 CAN을 다른 방법들과 비교 테스트했으며, CAN만이 정답을 맞힌다는 것을 발견했습니다.

기존의 공정한 방법들:
- "착한" 팀: 항상 포기합니다. 모두가 착할 때는 효율적이지만, 이기적인 친구가 나타나면 모든 것을 빼앗깁니다.
- "공격적인" 팀: 항상 싸웁니다. 이기적인 친구를 막아내지만, 싸우느라 너무 많은 피자를 낭비해서 아무도 떼가 없습니다. 심지어 아무도 나쁘게 행동하지 않을 때조차도 말이죠.
CAN 팀:
- 모두가 착할 때: 완벽하게 나눕니다. 낭비가 거의 없습니다.
- 이기적인 친구가 나타날 때: 도둑을 막을 수 있을 만큼만 딱 적당히 싸우되, 피자를 망칠 정도로 과하게 싸우지는 않습니다.
- 결과: 마치 인간 상사가 직접 조각을 나눠주는 것처럼 높은 수준의 공정성을 얻었지만, 상사의 도움 없이 스스로 해냈습니다.

6. 한계: 시스템이 무너지는 지점

저자들은 이 시스템이 실패하는 지점에 대해서도 매우 솔직하게 밝히고 있습니다. 이것은 마법이 아니며, 게임의 규칙에 따라 달라집니다.

규칙이 너무 가혹할 경우: 만약 게임이 다시 "승자 독식"(싸우면 자원이 완전히 파괴되는 방식)으로 돌아간다면, 시스템은 실패합니다. 지렛대가 사라지기 때문입니다.
그룹이 너무 커질 경우: 만약 6명에 맞춰 훈련된 팀을 갑자기 24명이 있는 방에 넣는다면, 갈등이 고조될 때 그들은 혼란에 빠집니다. 군중 속에서 문제아의 수를 제대로 세지 못합니다.
보상이 너무 클 경우: 만약 "피자"가 100%를 차지해야만 싸울 가치가 있는 거대한 잭팟이라면, 시스템은 낭비의 위험이 너무 크다고 판단하여 싸우기를 두려워하게 됩니다.

요약

이 논문은 분산된 형태의 공정성(decentralized fairness)이 가능하다는 것을 보여줍니다. 단, 게임의 규칙이 사람들이 싸울 때 어느 정도의 "중간 지점"을 허용할 수 있어야 한다는 조건이 붙습니다. 교차 주의(Cross-Attention) 기술을 사용하여 에이전트들이 서로를 관찰하고 행동을 조정하도록 가르침으로써, 중앙 권력의 미세한 관리 없이도 이기적인 구성원으로부터 스스로를 보호할 수 있습니다. 그들은 필요할 때는 강해지고, 안전할 때는 예의 바르게 행동하는 법을 배웠습니다.

기술 요약: 경쟁 학습하기: 교차 주의 집중(Cross-Attention)을 통한 협력적 MARL에서의 분산형 강건한 공정성

1. 문제 정의

협력적 다중 에이전트 강화학습(MARL)은 종종 에이전트의 기아 상태(starvation)를 방지하기 위해 공정성(예: 일반화된 지니 복지)을 최적화한다. 그러나 이러한 "공정한" 팀은 이기적인 에이전트(무임승차자)가 존재할 때 본질적으로 착취당하기 쉽다. 팀이 최저 효용을 가진 에이전트를 높이기 위해 개별 효용을 희생할 때, 이기적인 에이전트는 이 잉여분을 무임승차할 수 있다.

엄격하게 경합적인(all-or-nothing) 자원 경합 상황에서, 이러한 착취는 정책 수준에서 대응하기 어렵다. 만약 협력자가 자원을 두고 무임승차자와 경쟁(contest)한다면, 자원은 한 명에게 돌아가거나 아니면 완전히 낭비(충돌)된다. 결과적으로, 복지 중심의 팀은 양보하는 것과 경쟁하는 것 사이에 차이를 느끼지 못하므로, 분산된 방어는 무용지물이 된다. 기존 연구들은 중앙 집중식의 필요 기반 할당만이 이를 해결할 수 있다고 시사하며, 분산형 정책이 강건한 공정성을 달사할 수 있는지에 대한 질문을 남겨두었다.

본 논문은 이 간극을 메우기 위해 단계적 경합(graded-contention) 모델을 도입한다. 이 모델에서 경합 중인 자원은 완전히 낭비되지 않는다. 만약 $m \ge 2$ 명의 에이전트가 자원을 주장하면, 그들은 자원을 완전히 파괴하는 대신 자원의 일부인 $1-c$ (여기서 $c$ 는 낭비 계수)를 나누어 갖는다. 핵심 과제는 불확실성 하에서의 조정 문제이다: 무임승차자( $D$ )의 수는 알 수 없으며 가변적이다. 고정된 정책은 무임승차자가 없을 때 항상 경쟁하면 자원을 낭비하게 되고, 무임승차자가 나타났을 때 항상 양보하면 시스템이 붕괴하므로 실패한다.

2. 방법론: CAN (교차 주의 집중 네트워크)

저자들은 무임승차자의 존재를 추론하고 그에 비례하여 대응하도록 설계된 분산형 정책인 CAN을 제안한다.

이론적 토대 (Proposition 1): 본 논문은 단계적 경합( $c < 1$ ) 하에서, 최저 효용을 가진 협력자가 무임승차자에게 양보하는 것보다 경쟁하는 것이 자신의 결과를 엄격하게 개선한다는 것을 증න්න한다. 경쟁은 $0 $대신$ (1-c)/2 > 0$의 결과를 가져오는 반면, 무임승차자의 이득을 줄인다. 이는 **분산된 레버리지(decentralized leverage)**의 존재를 입증한다.
아키텍처:
- 입력: 각 에이전트는 공적 상태 특징의 토큰을 관찰한다: 현재 효용( $u_i$ ), 평균으로부터의 편차( $u_i - \bar{u}$ ), 최소 효용으로부터의 편차( $u_i - u_{min}$ ), 최저 효용 상태 여부 지표, 실행 중인 클레임 비율( $cc_i$ ), 그리고 타임 스텝.
- 메커니즘: CAN은 순열 불변(permutation-equivariant) 단일 헤드 셀프 어텐션 블록을 사용한다. 에이전트들은 다른 모든 에이전트의 관찰된 행동 토큰에 주목(attend)한다. 이를 통해 에이전트는 고정된 에이전트 정체성에 의존하지 않고도 경합자(claimers)의 수를 추론할 수 있다.
- 출력: 정책은 CLAIM(클레임) 또는 **YIELD(양보)**에 대한 로짓(logits)을 출력한다.
훈련 체계:
- 목적 함수: 협력자는 복지 함수 $W_{coop} = \text{mean}(u) - \text{std}(u)$ 를 최대화하며, 이는 효용 회복과 형평성 있는 배분을 모두 보상한다.
- 적대적 훈련: 강건성을 확보하기 위해, CAN은 **적대적 리그(PSRO)**를 상대로 훈련된다. 단일하게 공진화하는 무임승차자를 상대로 훈련하는 대신, 시스템은 과거의 최적 대응 무임승차자 풀(pool)에 대해 훈련하는 것과 새로운 최적 대응 착취자를 풀에 추가하는 과정을 번갈아 수행한다. 이는 정책이 특정 적대적 전략에 과적합되는 것을 방지한다.

3. 주요 결과

본 논문은 다양한 경합 수준( $c \in \{0.3, \dots, 0.9\}$ )과 팀 규모( $N=6$ )에 대해 CAN을 복지 중심 베이스라인(GFF, FEN, SOTO) 및 중앙 집중식 오라클과 비교 평가한다.

강건성 vs 효율성 트레이드오프:
- 베이스라인: 복지 중심 학습자들은 한 축에서 실패한다. GFF는 양보하는 법을 배운다(효율적이지만 최대치로 착취당함, $\rho \approx N$ ). SOTO는 항상 경쟁하는 법을 배운다(강건하지만 낭비가 심함, 효율성 $\approx 1-c$ ). FEN은 불안정하다.
- CAN: 강건성과 효율성을 모두 달성한다. 모든 경합 수준에서 낮은 최적 대응 착취성( $\rho \approx 1.2\text{--}1.5$ )을 유지하면서도, 무임승차자가 없을 때는 거의 완벽한 효율성( $\approx 1.0$ )을 유지한다.
메커니즘 검증:
- 적응적 행동: CAN은 무임승차자가 없을 때( $D=0$ ) 낭비를 피하기 위해 "차례 지키기(양보)"를 학습하고, 무임승차자가 있을 때( $D \ge 1$ ) "필요한 만큼만 경쟁하기"를 학습한다.
- 훈련 방식: 리그 훈련이 결정적이다. 정적인 적대자를 상대로 하는 바닐라 공동 훈련은 더 높은 착취성( $\rho \approx 2.0$ )을 보이며 상승하는 경향이 있는 반면, 리그 훈련은 $\rho$ 를 낮고 안정적으로 유지한다.
- 아키텍처: 교차 주의 집중(Cross-attention)은 단순 풀링(mean-pool, deep-sets)보다 우수하며, 특히 높은 경합 수준( $c=0.9$ )에서 양방향 GRU보다 더 안정적이다.
일반화 및 한계:
- 팀 규모: CAN은 낮은 경합 수준에서는 더 큰 팀( $N=12, 24$ )으로 제로샷 전이가 가능하지만, 높은 경합 수준에서는 성능이 저하되며, 이는 경합 추론의 취약성을 나타낸다.
- 환경 범위: CAN은 혼잡(congestion) 및 스테이크(stakes, 가변 가치) 게임에서도 효율적이며 베이스라인을 파레토 지배한다. 그러나 CAN의 강건성은 레버리지에 의해 제한된다. 가장 부유한 에이전트가 경합과 상관없이 승리하는 "승자 독식(Matthew)" 규칙의 경우, 레버리지가 사라져 CAN이 착취당한다.

4. 의의 및 주장

본 논문은 분산형 강건한 공정성의 한계를 완전히 해소했다는 주장보다는, **통제되고 정직한 지도(map)**를 제공한다는 점을 강조한다.

무용론 반박: 저자들은 분산된 방어가 무용하다는 생각이 "전부 아니면 전무(all-or-nothing)" 식의 경합에서 비롯된 인위적인 결과임을 입증한다. 단계적 경합을 도입함으로써, 분산된 레버리지가 존재함을 증명한다.
오라클 근접성 달 achievement: CAN은 중앙 할당자 없이도 이론적 상한선인 중앙 집중식 필요 기반 오라클의 성능에 근접한다. 이는 다른 이들의 행동을 관찰하여 무임승차자의 수를 추론하도록 조건화함으로써 달성된다.
적용 범위: 본 논문은 강건성이 보편적이지 않음을 명시한다. 이는 게임 규칙이 제공하는 "경합 레버리지"에 비례하여 유지된다. 만약 게임 규칙이 경합자가 양(+)의 몫을 획득할 수 없게 만든다면(예: 승자 독식), 이 접근법은 실패한다.
기여: 본 연구는 공정한 MARL을 본질적으로 착취 가능한 것으로 보는 패러다임을, 게임이 단계적 경합을 허용하고 정책이 다양한 적대자 군단에 맞서 훈련된다면, 다룰 수 있고 측정 가능한 목표로 전환시킨다.

저자들은 분산형 강건한 공정성이 달성 가능하지만, 다음과 같은 특정 조건에 의해 제한된다고 결론짓는다: 단계적 경합 레버리지의 존재, 주의 집중(attention)을 통한 적대자 수 추론 능력, 그리고 정책을 안정화하기 위한 적대적 리그 훈련의 사용.

Learning to Contest: Decentralized Robust Fairness in Cooperative MARL via Cross-Attention