Online Learning and Equilibrium Computation with Ranking Feedback

논문 제목: 순위 피드백을 통한 온라인 학습 및 균형 계산 (ONLINE LEARNING AND EQUILIBRIUM COMPUTATION WITH RANKING FEEDBACK)
발표: ICLR 2026 (Conference Paper)

이 논문은 인간이 개입하는 환경 (Human-in-the-loop) 이나 프라이버시 제약으로 인해 수치적 유틸리티 (numeric utility) 피드백을 얻기 어려운 상황에서, 순위 (Ranking) 피드백만을 사용하여 온라인 학습과 게임 이론적 균형 계산을 수행하는 문제를 다룹니다.

1. 문제 정의 (Problem)

기존의 온라인 학습 알고리즘은 환경으로부터 수치적 유틸리티 벡터 (Full-information) 또는 실현된 행동의 유틸리티 값 (Bandit) 을 관찰하여 의사결정을 합니다. 그러나 실제 응용 (예: 인간 선호도 기반 LLM 튜닝, 추천 시스템, 매칭 플랫폼) 에서는 사용자들이 정확한 점수를 매기기보다 여러 옵션 간의 상대적 순위를 제공하는 것이 더 자연스럽거나 가능합니다.

이 논문은 다음과 같은 설정을 연구합니다:

• 환경: 비확률적 (Non-stochastic) 이며 적대적 (Adversarial) 일 수 있는 환경.
• 피드백: 에이전트가 제안한 행동 집합에 대한 순서 (Permutation) 만 관찰 가능.
• 순위 생성 모델: Plackett-Luce (PL) 모델을 사용하며, 온도가 $\tau$인 확률적 모델로 가정합니다.
• 피드백 유형:
  1. InstUtil Rank: 현재 시점의 순간 유틸리티 (Instantaneous utility) 에 기반한 순위.
  2. AvgUtil Rank: 현재 시점까지의 시간 평균 유틸리티 (Time-average utility) 에 기반한 순위.
• 목표: 외부 후회 (External Regret) 를 최소화하고, 게임 설정에서는 근사적 코어 상관 균형 (Approximate Coarse Correlated Equilibrium, CCE) 을 달성하는 것.

2. 주요 기여 및 결과 (Key Contributions & Results)

2.1. 하한선 (Hardness Results) 및 불가능성

저자는 일반적인 조건에서 순위 피드백 하에 서브리니어 (Sublinear) 후회를 달성하는 것이 불가능함을 증명했습니다.

• InstUtil Rank: 온도가 충분히 작을 때 ($\tau \le O(1)$), 모든 알고리즘에 대해 후회가 선형 ($\Omega(T)$) 으로 증가하는 적대적 인스턴스가 존재합니다.
• AvgUtil Rank: 온도가 매우 작을 때 ($\tau \le O(\frac{1}{T \log T})$), 역시 후회를 최소화하는 것이 불가능합니다. 이는 순위가 거의 결정적으로 (deterministic) 주어질 때, 유틸리티 차이를 구별할 정보가 부족하기 때문입니다.

2.2. 알고리즘 및 긍정적 결과 (Positive Results)

하한선 결과를 극복하기 위해 유틸리티 벡터의 총 변동 (Total Variation) 이 서브리니어라는 추가 가정 하에 새로운 알고리즘을 제안했습니다.

• 가정 (Assumption 5.2): 유틸리티 벡터의 변화량 합 $\sum \|u(t) - u(t-1)\|$ 가 $O(T^q)$ ($q < 1$) 이하로 제한됨.
• 핵심 기법:
  • 유틸리티 추정 (Utility Estimation): 관찰된 순서를 이진 비교 (Pairwise comparison) 로 분해하고, 로지스틱 함수의 역함수를 이용하여 유틸리티를 추정하는 오라클을 설계했습니다.
  • 블랙박스 변환: 기존 수치 피드백용 후회 최소화 알고리즘 (예: FTRL, PGD) 을 유틸리티 추정기를 통해 순위 피드백 환경에 적용할 수 있도록 변환했습니다.
• 성능 보장:
  • InstUtil Rank: Full-information 및 Bandit 설정 모두에서 유틸리티 변동 가정을 통해 서브리니어 후회를 달성합니다.
  • AvgUtil Rank (Full-info): 변동 가정 없이도 온도가 상수 ($O(1)$) 일 때 서브리니어 후회를 달성할 수 있음을 보였습니다. 이는 시간 평균의 안정성 (Stability) 을 이용한 결과입니다.
  • AvgUtil Rank (Bandit): 변동 가정 하에서 서브리니어 후회를 달성합니다.

2.3. 게임 이론적 균형 계산 (Equilibrium Computation)

모든 플레이어가 제안된 알고리즘을 반복 게임 (Repeated Play) 에서 사용할 때, 시간 평균 전략이 근사적 코어 상관 균형 (Approximate CCE) 에 수렴함을 증명했습니다. 이는 온라인 학습의 후회 최소화 성질이 게임 균형 계산으로 자연스럽게 확장됨을 의미합니다.

3. 방법론 (Methodology)

1. 유틸리티 추정기 (Algorithm 1):

   • 제안된 행동 집합 $o(t)$ 내의 모든 행동 쌍에 대해 순위가 매겨진 확률을 관찰합니다.
   • PL 모델의 성질을 이용해, $P(a \succ b) = \text{sig}(\frac{u(a)-u(b)}{\tau})$ 관계를 역으로 풀어 유틸리티 차이를 추정합니다.
   • 슬라이딩 윈도우를 사용하여 최근 $m$개의 순서를 기반으로 추정 오차를 제어합니다.

2. 학습 알고리즘 (Algorithm 2 & 3):

   • InstUtil Rank (Algorithm 2): 추정된 유틸리티 $\hat{u}(t)$ 를 기존 후회 최소화 알고리즘 (Oracle) 에 입력합니다. Bandit 설정에서는 탐색을 보장하기 위해 균일 분포와 혼합 전략을 사용합니다.
   • AvgUtil Rank (Algorithm 3):
     • Full-info: 추정된 시간 평균 유틸리티를 직접 사용합니다.
     • Bandit: 시간 평균 유틸리티를 직접 관찰할 수 없으므로, 블록 (Block) 단위로 나누어 경험적 평균을 추정하고 이를 보정하여 사용합니다.

3. 안정성 분석:

   • FTRL(Follow-The-Regularized-Leader) 과 같은 알고리즘이 유틸리티 입력의 작은 변화에 대해 전략이 크게 변하지 않는 안정성 (Stability) 을 가진다는 성질을 활용하여, 추정 오차가 누적 후회에 미치는 영향을 제어했습니다.

4. 실험 결과 (Experiments)

• LLM 라우팅 (Online LLM Routing): 사용자의 쿼리에 대해 여러 LLM 모델 (GPT-4o, Llama, Phi 등) 중 하나를 선택하고, 사용자의 순위 피드백을 기반으로 최적 모델을 학습하는 시나리오를 시뮬레이션했습니다.
• 결과: 제안된 알고리즘 (Algorithm 3) 은 다양한 온도 ($\tau$) 와 제안 행동 수 ($K$) 에서 평균 후회가 시간이 지남에 따라 감소함을 보여주었습니다. 이는 알고리즘이 사용자의 선호 변화에 적응하며 최적의 고정 모델에 근접함을 의미합니다.
• 게임 실험: 무작위 생성된 일반합 게임 (General-sum games) 에서 CCE 근사 오차 ($\epsilon$) 가 감소하여 균형에 수렴함을 확인했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용성: 수치적 점수 수집이 어려운 실제 인간-기계 상호작용 (RLHF, 추천 시스템, 매칭 플랫폼) 에 적용 가능한 이론적 기반을 제공합니다.
• 이론적 기여: 순위 피드백 하의 온라인 학습에 대한 근본적인 한계 (Hardness) 를 규명하고, 이를 극복하기 위한 조건 (변동 제한, 온도 파라미터) 을 명확히 제시했습니다.
• 확장성: 단일 에이전트 학습을 넘어 다중 에이전트 게임의 균형 계산으로 자연스럽게 확장 가능하며, 이는 분산형 시스템에서의 협력적 학습에 중요한 시사점을 줍니다.

요약: 이 논문은 순위 피드백만으로도 온라인 학습과 게임 균형 계산이 가능함을 보였으나, 이는 환경의 변화가 완만하거나 온도가 적절해야 함을 증명했습니다. 제안된 알고리즘은 이러한 조건 하에서 후회를 최소화하고 균형에 도달하며, LLM 라우팅 등 실제 응용 사례에서 유효성이 입증되었습니다.