당신이 드론 함대의 선장이거나, 혹은 비디오 게임 캐릭터 팀의 매니저라고 상상해 보세요. 당신에게는 나누어 줄 작업 목록이 있습니다. 컴퓨터 과학의 세계에서 이것은 "멀티 암드 밴딧(Multi-Armed Bandit)" 문제라고 불리는 것으로 알려져 있습니다. 이는 아주 세련된 이름이지만, 실제로는 단순한 딜레마입니다. 당신에게는 여러 가지 선택지(슬롯머신의 "팔")가 있지만, 어떤 것이 가장 좋은 보상을 주는지 알지 못합니다. 배우기 위해서는 시도해 봐야 하지만, 시도할 때마다 보상을 얻을 기회를 놓치게 됩니다. 이제, 당신이 단순히 이러한 선택을 하는 한 명의 개인이 아니라, 하나의 팀 전체를 이끄는 사람이라고 상상해 보세요. 그리고 모든 사람이 공평하게 좋은 보상을 받을 수 있도록 하고 싶습니다. 단지 운이 좋아 최고의 과업을 맡게 된 소수만이 아니라 말이죠. 이것이 바로 "멀티 에이전트(Multi-Agent)" 부분입니다. 연구자들이 던져온 핵심 질문은 이것입니다: 어떻게 하면 학습(탐색, exploration)과 수익 창출(착취, exploitation) 사이의 균형을 맞추면서, 동시에 아무도 뒤처져 아무것도 얻지 못하는 일이 없도록 만들 것인가?

"Probing을 이용한 공정 알고리즘: 멀티 에이전트 멀티 암드 밴딧(Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits)"이라는 제목의 이 논문은 바로 그 문제를 다룹니다. 툴레인 대학교(Tulane University)와 일리노이 대학교(University of Illinois)의 연구진인 저자들은 이 결정을 내리기 위한 영리하고 새로운 방법을 제안합니다. 그들은 "프로빙(probing, 탐사)" 메커니즘을 도입했는데, 이는 팀 전체를 투입하기 전에 정찰병을 먼저 보내는 것과 같습니다. 드라이버를 특정 구역에 무작정 배정하고 탑승객이 나타나길 기도하는 대신, 먼저 몇몇 구역을 살짝 들여다봄으로써 실제로 어떤 일이 일어나고 있는지 확인하는 것입니다. 이 추가적인 정보를 수집함으로써 시스템은 더 똑똑하고 공정한 배정을 할 수 있습니다. 연구진은 "내쉬 사회적 후생(Nash Social Welfare)"이라는 특정 수학적 척도를 사용하면—이는 단순히 전체 합을 극대화하는 것이 아니라 모두의 행복의 곱을 극대화하는 것을 의미합니다—팀원 중 누군가가 보상을 받지 못해 낙오되는 상황을 방지할 수 있음을 보여줍니다. 그들은 규칙이 알려진 경우(오프라인)에는 그들의 방법이 잘 작동함을 수학적으로 증명했으며, 규칙이 숨겨진 경우(온라인)에도 빠르게 학습하며 정체되지 않는다는 것을 증명했습니다.

문제: 배고픈 팀과 미스터리 박스

승차 공유 앱을 상상해 보세요. 당신에게는 여러 명의 드라이버(에이전트)와 여러 개의 도시 동네(암)가 있습니다. 앱은 어떤 드라이버를 어느 동네로 보낼지 결정해야 합니다. 만약 앱이 오직 회사의 전체 수익만을 극대화하려고 한다면, 모든 드라이버를 가장 붐비는 하나의 동네로 보낼 수도 있습니다. 그 결과는 어떨까요? 그 동네의 드라이버들은 부유해지겠지만, 조용한 동네의 드라이버들은 아무것도 얻지 못할 것입니다. 그들은 일거리로부터 "굶주리게(starved)" 됩니다. 이것이 "합계(sum)"의 보상을 극대화할 때 발생하는 전형적인 함정입니다. 즉, 불평등을 초래합니다.

이를 해결하기 위해 저자들은 단순히 모두의 수입을 더해서는 안 된다고 제안합니다. 대신 "내쉬 사회적 후생"을 고려해야 합니다. 이것은 팀 점수와 같은데, 만약 팀원 중 누구라도 점수가 0점이라면 팀 전체의 점수도 0점이 되는 방식입니다. 이는 시스템이 누군가를 뒤처지게 만들지 않도록 주의하게 만듭니다. 이는 몇몇이 모든 것을 가져가고 나머지는 아무것도 얻지 못하는 대신, 모두가 적절한 몫을 가질 수 있는 균형 잡힌 분배를 장려합니다.

반전: 정찰병 (프로빙)

하지만 여기 문제가 있습니다. 앱은 실제로 어느 동네가 붐비는지 알지 못합니다. 단지 추측만 할 뿐입니다. 현실 세계에서는 교통 상황이 변하고, 날씨가 바뀌며, 수요가 요동칩니다. 만약 앱이 잘못 추측한다면, 드라이버를 유령 도시로 보내 시간과 연료를 낭비하게 될 수도 있습니다.

이 지점에서 논문의 핵심 아이디어가 등장합니다. 바로 **프로빙(Probing)**입니다.

당신이 전장에 병사들을 보내는 장군이라고 상상해 보세요. 군대 전체를 보내기 전에, 지형을 확인하기 위해 소규모 정찰대를 먼저 보냅니다. 이 논문의 세계에서 "의사 결정자(decision-maker, 앱)"는 드라이버를 배정하기 전에 몇몇 동네를 "프로빙(탐사)"할 수 있습니다. 프로빙이란 실시간 데이터를 확인하는 것을 의미합니다—예를 들어, 현재 특정 격자 구역에 차가 얼마나 대기 중인지, 혹은 사람들이 얼마나 많은 승차 요청을 하고 있는지 확인하는 것입니다. 이는 약간의 시간이나 에너지(오버헤드)를 소모하지만, 시스템에 훨씬 더 명확한 현실의 그림을 제공합니다.

저자들은 적절한 동네를 프로빙한다면 훨씬 더 공정한 배정을 할 수 있다는 점을 깨달았습니다. A 동네가 사실은 죽은 곳이라는 것을 알게 되면, 그곳에 드라이버를 보내는 대신 활기찬 B 동네로 보내는 식입니다. 이를 통해 잘못된 추측에 기반하여 엉뚱한 곳으로 보내졌을 드라이버들의 "굶주림"을 방지할 수 있습니다.

해결 방법: 탐욕적 정찰병 (Greedy Scout)

논문은 문제를 두 가지 시나리오로 나눕니다.

1. 오프라인 설정 (지도가 알려진 경우): 당신이 도시의 완벽한 지도와 각 동네에서 평균적으로 얼마나 많은 승차가 발생하는지에 대한 정확한 지식을 가지고 있다고 가정해 봅시다. 심지어 이런 완벽한 지식이 있더라도, 프로빙할 최적의 동네 세트와 드라이버를 배정하는 최선의 방법을 찾아내는 것은 매우 어렵습니다(수학적으로 "NP-hard"). 이는 모든 조각이 다른 조각의 가치를 변화시키는 거대한 퍼즐을 푸는 것과 같습니다.

   • 해결책: 저자들은 "그리디(Greedy, 탐욕적)" 알고리즘을 설계했습니다. 이것은 다음 동네를 체크할 때 팀의 공정성 점수를 가장 크게 높일 수 있는 곳을 고르는 정찰병과 같습니다. 그들은 이 단순한 단계별 접근 방식이 완벽한 해답에 매우 근접하게(상수 인자 이내로) 도달할 수 있음을 증명했습니다. 즉, 모든 동네를 일일이 확인하지 않고도 훌륭한 결과를 얻을 수 있다는 것입니다.

2. 온라인 설정 (지도가 알려지지 않은 경우): 이것이 실제 세상의 시나리오입니다. 앱은 수요를 알지 못하며, 운행하면서 배워나가야 합니다.

   • 해결책: 그들은 OFMUP(Online Fair Multi-Agent UCB with Probing)이라는 알고리즘을 만들었습니다. 이 알고리즘은 스마트한 학습자와 같습니다. 먼저 기초를 배우기 위해 정찰병을 보냅니다. 그런 다음, 데이터를 수집함에 따라 "신뢰 구간(confidence bound)" 전략을 사용합니다. 특정 동네에 대해 확신이 없다면, 확실히 하기 위해 더 많이 프로빙합니다. 확신이 생기면, 시간을 낭비하지 않고 드라이버를 배정합니다.
   • 결과: 그들은 이 방법이 빠르게 학습된다는 것을 수학적으로 증명했습니다. "후회(regret, 완벽한 선택을 하지 못해 잃게 된 기회 비용)"는 시간이 흐름에 따라 매우 느리게 증가합니다. 실제로, 이들의 프로빙 방식은 프로빙을 전혀 하지 않는 방식보다 훨씬 더 우수한 성능을 보입니다.

실험 결과

저자들은 아이디어를 테스트하기 위해 시뮬레이션을 실행하고, 2016년 뉴욕시 옐로우 택시(New York City Yellow Taxi) 데이터셋을 사용했습니다. 그들은 택시를 에이전트로, 도시 블록을 암으로 간주했습니다.

• 설정: 팀 규모(드라이버 1220명)와 동네 수(810개)에 따른 다양한 테스트를 진행했습니다. 또한 다양한 유형의 "보상"도 테스트했습니다.
• 비교 대상: 그들의 방법론을 다음 모델들과 비교했습니다:
  • 비-프로빙(Non-Probing): 확인 없이 추측만 함.
  • 무작위 프로빙(Random Probing): 무작위로 동네를 확인하고 드라이버를 무작위로 배정함.
  • 무작위 배정을 결합한 그리디 프로빙(Greedy Probing with Random Assignment): 똑똑하게 확인하지만, 배정은 무작위로 함.
• 결과: 저자들의 방법인 OFMUP은 경쟁자들을 압도했습니다. 일부 테스트에서 OFMUP은 무작위 프로빙 대비 85%, 무작위 배정을 결합한 그리디 프로빙 대비 **60%**의 "후회(regret)"를 줄였습니다. 더욱 인상적인 점은, 문제가 커지고 복잡해질수록 다른 방법들은 어려움을 겪는 반면, 그들의 방법은 오히려 더 잘 대응하며 성과를 유지했다는 것입니다.

핵심 요약

이 논문은 단순히 "프로빙이 좋다"라고 말하는 데 그치지 않습니다. 어떻게 프로빙하고 어떻게 과업을 배정해야 공정성을 확보할 수 있는지에 대한 엄격한 수학적 프레임워크를 제공합니다. 저자들은 단순히 총 보상의 합을 극대화하는 것이 종종 에이전트들에게 불공정한 "굶주림"을 초래한다는 점을 지적하며, 기존의 방식에 반론을 제기합니다. 대신, "내쉬 사회적 후생" 지표를 사용하고 능동적인 정보 수집(프로빙) 층을 추가함으로써, 효율적이면서도 형평성을 갖춘 시스템을 구축할 수 있다고 주장합니다.

저자들은 불확실성이 가득한 세상에서, 뛰어들기(배정하기) 전에 잠시 훔쳐보는 것(프로빙)이 팀 전체를 행복하고 성공적으로 만드는 열쇠임을 보여줍니다. 그들의 연구는 적절한 알고리즘이 있다면, 시스템의 높은 성능과 개별 에이전트의 공정한 몫이라는 두 마리 토끼를 모두 잡을 수 있음을 시사합니다.