연합 조합 다중 에이전트 다중 팔 도박 문제

본 논문은 밴딧 피드백을 갖는 온라인 조합 최적화에 맞춤화된 연합 학습 프레임워크를 소개합니다. 이 환경에서 에이전트들은 팔의 부분집합을 선택하고, 개별 팔 정보에 접근하지 않은 채로 이 부분집합에 대한 잡음이 있는 보상을 관찰하며, 특정 간격으로 협력 및 정보 공유가 가능합니다. 우리 프레임워크는 함수와 상수에 대해 로그를 생략한 O(·) 복잡도를 가진 내성 있는 오프라인 단일 에이전트 (-) -근사 알고리즘을 임의로 받아, m명의 통신 에이전트와 함께 사용되는 온라인 다중 에이전트 알고리즘으로 변환하며, -후회의 상한을 최대 O(m^-1{3+}¹3+ T²+3+)로 유지합니다. 이 접근법은 근사 오차를 제거할 뿐만 아니라 시간 지평선 T에 대해 아선형 성장을 보장하고, 통신 에이전트 수가 증가함에 따라 선형 속도 향상을 나타냅니다. 또한 알고리즘은 O(T^+1)로 정량화되는 하위선형 통신 라운드만 필요로 하여 통신 효율이 뛰어납니다. 더 나아가 이 프레임워크는 여러 오프라인 알고리즘을 활용한 온라인 확률적 부분가법 최대화에 성공적으로 적용되어 단일 및 다중 에이전트 설정 모두에 대한 최초 결과를 도출했으며, 특화된 단일 에이전트 이론 보장도 회복했습니다. 우리는 확률적 데이터 요약 문제에 대한 실험적 검증을 통해 제안된 프레임워크가 단일 에이전트 상황에서도 효과적임을 입증합니다.