온라인 다수 인간-다수 로봇 팀 구성에 대한 선형 매칭 밴딧 접근 방식

우리는 선형 매칭 밴딧 (linear matching bandit) 프레임워크의 관점을 통해 온라인 다수 인간-다수 로봇 팀 구성 (online multi-human multi-robot teaming) 문제를 다룹니다. 이 프레임워크에서 학습자는 고정된 풀(pool)에서 가져온 미지의 특징 (features)을 가진 로봇들을 여러 라운드에 걸쳐 서로 다른 인간 에이전트 집합에 할당합니다. 이 문제를 해결하기 위해, 우리는 미지의 특징에 대한 신뢰 구간 (confidence intervals)을 업데이트하고 불확실성 하에서 낙관적 매칭 (optimistic matching)을 수행하는 온라인 학습 알고리즘인 LinMatch를 제안합니다. 본 연구의 기여와 독창성은 두 가지 측면이 있습니다. 첫째, 각 라운드에서의 낙관적 매칭 문제를 유명한 헝가리안 알고리즘 (Hungarian algorithm)으로 효율적으로 해결 가능한 최대 가중 매칭 (maximum weighted matching)의 선형 계획법 (linear program)으로 재구성했습니다. 둘째, 선형 특징 문제 (linear feature problems)가 포함된 매칭에 대한 새로운 경계 (bounds)를 제공하여, $\tilde{O}(d\sqrt{MKT})$의 상한 (upper bound)과 $\Omega(d\sqrt{MKT})$의 미니맥스 하한 (minimax lower bound)을 보여줌으로써 $\tilde{\Theta}(d\sqrt{MKT})$의 타이트한 최적 후회율 (optimal regret rate)을 확립했습니다. 이는 LinMatch가 총 라운드 수 $T$, 특징 차원 $d$, 그리고 매칭 파라미터 $M$ 및 $K$에 대해 달성 가능한 엄격하게 최적인 후회 (regret)를 달성함을 입증합니다. 제안된 알고리즘과 경계는 주거 할당 (housing allocation), 추천 시스템 (recommendation systems) 등 인간-로봇 매칭을 넘어선 다양한 매칭 문제에 적용될 수 있습니다.