Shapley 값을 통한 예산 제약 하에서의 조합적 다중 팔 무대 (BCMAB-FBF) 의 공정한 성과

우리는 전역 팔 피드백 (full-bandit feedback) 을 갖는 예산 제약 하의 조합적 다중 팔 무대 (Budgeted Combinatorial Multi-armed Bandits, BCMAB) 에서 공정한 성과 (Meritocratic Fairness) 를 위한 새로운 프레임워크를 제안합니다. 반팔 피드백 (semi-bandit feedback) 과 달리, 전역 팔 피드백에서는 개별 팔의 기여도가 완전히 제공되지 않아 이 설정은 훨씬 더 도전적입니다. BCMAB-FBF 에서 팔 기여도를 계산하기 위해 우리는 협력 게임 이론의 고전적인 해법 개념인 Shapley 값을 확장하여, 크기가 $K$ 이하인 집합에 제한된 에이전트의 마진 기여도를 포착하는 $K$-Shapley 값을 제안합니다. 우리는 $K$-Shapley 값이 대칭성 (Symmetry), 선형성 (Linearity), null player, 효율성 (efficiency) 속성을 만족하는 유일한 해법 개념임을 증명합니다. 다음으로, 미지의 가치 함수 (valuation function) 를 추정하며 적응적으로 $K$-Shapley 값을 계산하는 공정성 인식 팔 알고리즘인 K-SVFair-FBF 를 제안합니다. 표준 전역 팔 피드백 문헌과 달리, K-SVFair-FBF 는 전역 피드백 설정 하에서 가치 함수를 학습할 뿐만 아니라 몬테 카를로 근사 (Monte Carlo approximations) 에서 발생하는 노이즈를 완화합니다. 이론적으로, 우리는 K-SVFair-FBF 가 공정성 regret 에 대해 $O(T^{3/4})$ regret bound 을 달성함을 증명합니다. 연방 학습 (federated learning) 과 사회적 영향력 극대화 (social influence maximization) 데이터셋을 통한 실험에서, 우리의 접근법이 공정한 성과를 달성하고 기존 베이스라인보다 더 효과적으로 수행됨을 보여줍니다.