기술 요약: Nash Social Welfare를 이용한 다중 사용자 듀얼링 밴딧의 공정 접근법

문제 정의

본 논문은 에이전트가 $K$개의 팔(arm)을 가진 시간 지평 $T$ 동안 $D$개의 서로 다른 사용자로부터 제공되는 쌍별 선호도 데이터를 통해 학습하는 공정한 다중 사용자 듀얼링 밴딧(Fair Multi-User Dueling Bandit) 문제를 다룹니다. 단일 선호 모델을 가정하거나 선호도를 하나의 행렬로 통합하는 표준적인 듀얼링 밴딧과 달리, 본 연구는 각 사용자 $d$가 잠재적으로 고유한 선호 행렬 $P_d$를 보유할 수 있는 시나리오를 고려합니다.

핵심 과제는 이질적인 사용자들의 이해관계를 저해하지 않으면서 이들의 이익 사이에서 균형을 잡는 정책을 학습하는 것입니다. 평균(공리주의적) 복지를 최적화하는 표준적인 접근 방식은 종종 통계적 다수에게 유리하게 작용하여, 상이한 선호도를 가진 소수 집단에게 불공정한 결과를 초래할 수 있습니다. 이를 해결하기 위해 저자들은 사용자 효용의 곱을 최대화하는 **Nash Social Welfare (NSW)**를 사용하여 목적 함수를 정의합니다. 이 목적 함수는 본질적으로 불평등에 페널티를 부여하여, 특정 사용자의 효용이 0으로 수렴하는 것을 방지합니다.

이 설정에서의 결정적인 기술적 난관은 절대적인 보상이 결여되어 있으며, 피드백이 순수하게 상대적(두 팔 중 어느 쪽이 선호되는지를 나타내는 이진 결과)이라는 점입니다. 상대적인 설정에서 효용을 정의하기 위해, 저자들은 각 사용자에게 콘도르세 승자(Condorcet winner)(다른 모든 팔을 확률 $0.5$ 초과로 이기는 팔)가 존재한다는 가정을 도입합니다. 사용자의 효용은 해당 사용자의 특정 콘도르세 승자를 상대로 특정 팔이 승리할 확률으로부터 유도된 점수로 정의됩니다.

방법론

이론적 프레임워크

저자들은 점수 함수 $s_d(i) = 2P_{d, i, a^*_d}$ (여기서 $a^*_d$는 사용자 $d$의 콘도르세 승자)를 정의하여 문제를 공식화합니다. 정책 $\pi$에 대한 사용자 $d$의 효용은 기대 점수 $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$입니다. 전역 목적 함수는 Nash Social Welfare입니다:
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
목표는 이 곱을 최대화하는 최적 정책 $\pi^*$에 대한 기대 누적 후회(expected cumulative regret)를 최소화하는 것입니다.

난이도 분석

본 논문은 $\Omega(T^{2/3} \min(K, D)^{1/3})$의 근본적인 **후회 하한선(regert lower bound)**을 설정합니다. 이 결과는 상충하는 콘도르세 승자를 가진 사용자들 사이에서 NSW를 최대화해야 하는 요구사항이 표준 듀얼링 밴딧(통상적으로 $O(\log T)$ 후회를 달성)에 비해 상당한 난이도를 도입함을 입증합니다. 이러한 어려움은 알고리즘이 '좋은' 승자를 구별하기 위해 '나쁜' 콘도르세 승자(한 사용자에게는 최적이지만 다른 사용자들에게는 거의 0에 가까운 효용을 주는 팔)를 수행해야 하며, 이 과정에서 탐색 비용과 즉각적인 후회 사이의 트레이드오프가 발생하기 때문입니다.

알고리즘

목적을 달ato하기 위해 두 가지 알고리즘이 제안되었으며, 두 알고리즘 모두 콘도르세 승자 식별 단계를 포함합니다:

1. Fair-Explore-Then-Commit (Fair-ETC):

   • 1단계 (식별): 수정된 Dvoretzky-Kiefer-Wolfowitz Tournament (DKWT) 알고리즘을 사용하여 모든 $D$ 사용자에 대한 콘도르세 승자 집합 $\hat{A}^*$를 식별합니다. 이 단계는 공유된 상호작용을 활용하여 모든 사용자에 대한 경험적 마진(empirical margins)을 동시에 업데이트합니다.
   • 2단계 (탐색): 식별된 콘도르세 승자들에 대한 모든 팔의 점수를 추정합니다.
   • 3단계 (확정): 경험적 NSW를 최대화하는 정책 $\hat{\pi}$를 계산하고 남은 시간 지평 동안 이를 확정하여 수행합니다.

2. Fair-$\epsilon$-Greedy:

   • 이 알고리즘은 시간 지평 전체에 걸쳐 탐색과 활용을 교차합니다.
   • 동일한 콘도르세 승자 식별 단계로 시작합니다.
   • 각 단계 $t$에서, 확률 $\epsilon_t$로, 점수 추정을 정교화하기 위해 (라운드 로빈 스케줄을 사용하여) 콘도르세 승자를 포함하는 쌍들을 플레이하며 탐색합니다.
   • 확률 $1-\epsilon_t$로, 현재의 경험적 NSW를 최대화하는 정책을 플레이하며 활용합니다.
   • 탐색률 $\epsilon_t$는 수렴을 보장하기 위해 시간이 지남에 따라 감소합니다.

두 알고리즘 모두 로그 인자를 제외한 $T$에 대한 의존성 측면에서 하한선과 일치하는 $\tilde{O}(T^{2/3})$의 후회 상한선을 달성함이 증명되었습니다.

주요 기여

1. 문제 공식화: 개별 콘도르세 승자에 기반한 뚜렷한 사용자 효용을 모델링하고 NSW를 공정성 목적으로 채택한, 최초의 공정 다중 사용자 듀얼링 밴딧 문제 공식화.
2. 후회 하한선: 이질적인 선호도를 가진 듀얼링 밴딧에서 공정성의 비용을 정량화하는 최초의 결과인 $\Omega(T^{2/3} \min(K, D)^{1/3})$ 하한선 도출.
3. 알고리즘 솔루션: 하한선의 $T$ 의존성과 일치하는 이론적 후회 상한을 갖춘 Fair-ETC 및 Fair-$\epsilon$-Greedy 알고리즘 제안.
4. 실험적 검증: 제안된 알고리즘이 공정성 지표(지니 계수, 최소 사용자 복지)에서 공리주의적 베이스라인을 능가하면서도 경쟁력 있는 누적 후회를 유지함을 보여주는 광범한 시뮬레이션.

실험 결과

저자들은 무작위 생성된 선호도와 실제 데이터(클러스터링된 거시적 사용자로 분류된 Sushi 데이터셋) 모두에서 알고리즘을 평가했습니다.

• 무작위 선호도: 다양한 사용자($D$) 및 팔($K$) 구성에 대해, Fair-ETC와 Fair-$\epsilon$-Greedy 모두 아래 선형(sublinear) 후회를 보여주었으며, 공리주의적 베이스라인 및 사용자 균등 분포(uniform-over-users) 베이스라인보다 일관되게 우수한 성능을 보였습니다.
• 공정성 지표: 제안된 알고리즘은 공리주의적 접근 방식에 비해 가장 높은 Nash Social Welfare와 현저히 낮은 지니 계수를 달성했습니다. 또한 더 높은 최소 사용자 복지를 유지하여 소수 선호도를 더 잘 보호함을 보여주었습니다.
• 클러스터링된 선호도: 뚜렷한 다수 및 소수 클러스터가 존재하는 시나리오(양극화된 선호도 시뮬레이션)에서, 공리주의적 알고리즘은 다수에게 유리하게 작용하여 높은 불평등을 초래했습니다. 제안된 공정 알고리즘은 낮은 지니 계수와 높은 최소 복지를 유지하며 이해관계를 성공적으로 균형 잡았습니다.
• Sushi 데이터셋: 실제 데이터에서 제안된 방법은 $D=5$와 $D=10$ 클러스터 설정 모두에서 가장 낮은 누적 후회를 달성했습니다. 균등 베이스라인이 매우 파편화된 $D=10$ 케이스에서 약간 더 나은 공정성을 보였으나, 후회 측면에서는 훨씬 열등한 성능을 보였습니다.

의의 및 주장

본 논문은 이질적인 선호도를 가진 듀얼링 밴딧에서 공정성의 비용을 정량화한 최초의 연구임을 주장하며, $\Omega(T^{2/3})$의 근본적인 후회 하한선을 설정합니다. 저자들은 평균 선호도를 최적화하는 것이 충분하지 않으며 소수 집단에게 해로울 수 있는, 인간 중심적 머신러닝을 향한 필수적인 단계로서 본 연구를 위치시킵니다.

Nash Social Welfare 목적 함수를 듀얼링 밴딧 프레임워크에 통합함으로써, 본 연구는 효율성과 공정성 사이의 균형을 맞추는 정책을 학습하기 위한 이론적, 알고리즘적 토대를 제공합니다. 저자들은 본 연구가 절대적 보상이 아닌 상대적 선호도 설정에서 작동하며, 이로 인해 근본적으로 다른 효용 추정 기술이 필요하다는 점에서 기존의 다중 에이전트 밴딧 연구(예: Hossain et al., 2021; Jones et al., 2023)와 구별된다고 명시했습니다.

본 논문은 향-컨텍스추얼 듀얼링 밴딧(contextual dueling bandits), 연속적 행동 공간, 그리고 콘도르세 승자 가정이 성립하지 않는 설정(Copeland 또는 Borda 점수를 사용할 수 있음)으로 확장될 수 있음을 언급하며 마무리합니다.