검열된 피드백 하에서의 구조적 학습 비용: 임계값 밴딧 (Threshold-Bandit) 접근 방식

많은 다중 에이전트 (multi-agent) 애플리케이션에서, 작업은 알려지지 않은 크기의 임계값 (threshold)을 충족하는 연합 (coalition)에 의해 실행될 때만 보상을 생성하며, 그렇지 않으면 피드백이 완전히 검열 (censored)됩니다. 이러한 검열은 식별 가능성 (identifiability) 문제를 야기합니다: 즉, 에이전트들이 확률적 실패 (stochastic failure)와 불충분한 조정 (insufficient coordination)을 구분할 수 없게 만듭니다. 우리는 이 설정을 임계값 활성화 협력 다중 팔 밴딧 (Threshold-Activated Cooperative Multi-Armed Bandit, TAC-MAB)으로 공식화하고, 중앙 집중식 (centralized) 및 분산식 (decentralized) 조정 하에서 이를 분석합니다. 우리는 중앙 집중식 알고리즘 (C-TAC)이 누적 후회 (cumulative regret) $O(\log T)$를 달성함을 보여주며, 이는 검열된 피드백 하에서 실행 가능성 (feasibility)을 해결하는 비용을 포착하는 구조적 탐색 (structural-search) 항과 가치 추정 (value estimation)을 위한 통계적 모니터링 (statistical-monitoring) 항으로 분해됩니다. 이어서 우리는 에이전트들이 자신의 구조적 신념 (structural beliefs)이 변할 때만 동기화하는 분산식 이벤트 트리거 프로토콜 (decentralized event-triggered protocol)인 D-TAC를 소개합니다. 실증적으로, D-TAC는 보수적인 신념 융합 (conservative belief fusion) 하에서 실행 가능성 정렬 (feasibility alignment)을 유지하면서 중앙 집중식 베이스라인 대비 통신량을 23배 감소시킵니다. 이러한 결과는 검열된 피드백 하에서의 학습에 따른 조정 비용을 특징짓고, 지속적인 동기화 없이도 중앙 집중식에 근접한 통신 효율성을 달성할 수 있음을 보여줍니다.