arXiv:2602.04125v2 stat.ML

선형 및 매끄러운 문맥적 밴딧을 위한 공격 저항적 균일 공정성

Attack-Resistant Uniform Fairness for Linear and Smooth Contextual Bandits

Qingwen Zhang, Wenjia Wang

제출 2026-09-22

한국어 초록

현대 디지털 플랫폼은 경쟁하는 참가자들 사이에 가치 있는 노출과 기회를 배분하기 위해 문맥적 밴딧(contextual bandits)을 사용합니다. 따라서 공정한 처우는 중요한 관심사이지만, 보상 극대화만으로는 우대 배분이 참가자의 역량(merit)을 반영하도록 보장하지 못합니다. 본 논문에서는 모든 문맥과 라운드에 걸쳐 보상 순서가 우대 배분을 정당화하도록 요구하는 균일 역량 기반 공정성(uniform merit-based fairness) 하에서 선형 및 매끄러운(smooth) 문맥적 밴딧을 위한 알고리즘을 개발하고, 적대적 보상 오염(adversarial reward corruption)이 이러한 보장에 미치는 영향을 연구합니다. 제안된 알고리즘은 \((1-\widetilde O(1/T))\)-공정성을 달성하며, 선형 보상에 대해서는 공정한 정책 중 미니맥스 최적(minimax optimal), 매끄러운 보상에 대해서는 거의 미니맥스 최적인 리그렛(regret)을 보입니다. 선형 환경에서 일치하는 하한(lower bound)을 통해 공정성의 대가(price of fairness)를 정확히 규명하며, 미니맥스 리그렛은 \(\log T\)에서 \(\log^2 T\)로 증가합니다. 매끄러운 보상의 경우 공정성 비용은 기껏해야 폴리로가리듬(polylogarithmic) 수준입니다. 나아가 리그렛과 공정성 강건성(robustness) 간의 분리를 규명하여, \(\widetilde O(1)\)의 오염 예산(corruption budget)만으로도 리그렛의 차수(order)를 악화시키지 않으면서 심각한 공정성 침해를 유발할 수 있음을 보입니다. 이에 따라 샘플링, 추정, 공정성 인증을 오염에 맞게 조정하는 강건한 알고리즘을 개발하여 균일 공정성을 보존하고 선형 및 매끄러운 보상 각각에 대해 미니맥스 최적 및 거의 최적인 리그렛을 달성합니다. 수치 및 준합성(semi-synthetic) 실험을 통해 이러한 발견을 실증합니다.

원문 초록

Modern digital platforms use contextual bandits to allocate valuable exposure and opportunities among competing participants. Fair treatment is therefore an important concern, yet reward maximization alone does not ensure that preferential allocation reflects participants' merits. We develop algorithms for linear and smooth contextual bandits under uniform merit-based fairness, requiring the reward ordering to justify preferential allocation across all contexts and rounds, and study how these guarantees are affected by adversarial reward corruption. Our algorithms achieve \((1-\widetilde O(1/T))\)-fairness, with regret that is minimax optimal among fair policies for linear rewards and nearly minimax optimal for smooth rewards. In the linear setting, matching lower bounds identify the price of fairness exactly: minimax regret increases from \(\log T\) to \(\log^2 T\). For smooth rewards, the cost of fairness is at most polylogarithmic. We further establish a separation between regret and fairness robustness: an \(\widetilde O(1)\) corruption budget can cause substantial fairness violations without worsening the regret order. We therefore develop robust algorithms that adapt sampling, estimation, and fairness certification to corruption, which preserve uniform fairness and achieve minimax-optimal and nearly optimal regrets for linear and smooth rewards, respectively. Numerical and semi-synthetic experiments illustrate these findings.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2602.04125v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.