안정적인 무작위 선택을 위한 매끄러운 부분 복권 (Smooth Partial Lotteries)

요약

기존의 부분 복권(Partial Lotteries) 방식은 후보자의 점수가 미세하게 변할 때 선택 확률이 급격히 변하는 불안정성 문제를 가지고 있습니다. 본 논문은 점수와 선택 확률 사이의 매핑에 Lipschitz 조건을 적용한 '매끄러움(Smoothness)' 개념을 제안하며, 이를 구현하기 위한 Clipped Linear Lottery 메커니즘을 소개합니다.

핵심 포인트

• 기존 부분 복권 설계의 불안정성 문제를 해결하기 위해 '매끄러움'을 설계 원칙으로 제안함
• Clipped Linear Lottery는 상한 및 하한 임계값 사이에서 선택 확률이 점수에 선형적으로 비례하는 방식임
• Clipped Linear Lottery가 모든 매끄러운 선택 규칙의 최악의 후회(Worst-case Regret) 하한선과 일치함을 증명함
• ICLR, NeurIPS 등 실제 동료 검토 데이터를 통해 제안된 방식이 기존 방식보다 매끄러움-효용 트레이드오프 측면에서 우수함을 입증함