기술적 요약: 지연 피드백을 가진 선형 및 신경 대결 밴딧

1. 문제 정의

본 논문은 확률적 지연 피드백 (Stochastic Delayed Feedback) 하의 맥락적 대결 밴딧 (Contextual Dueling Bandits, CDB) 문제를 다룹니다. 표준 CDB 설정에서 에이전트는 암 (후보) 의 쌍을 선택하고 잠재적 보상 함수를 학습하기 위해 즉각적인 이진 선호도 피드백 (예: $x_1 \succ x_2$) 을 받습니다. 그러나 대규모 언어 모델 (LLM) 정렬, 프롬프트 최적화, 디스플레이 광고와 같은 실제 응용 분야에서는 피드백이 종종 비동기적으로 발생합니다.

본 작업에서 형식화된 특정 설정은 다음과 같습니다:

• 확률적 지연: $s$라운드에서 취한 행동에 대한 피드백은 무작위 지연 $D_s$후에 도착합니다.
• 하드 임계값: 최대 관찰 창 $M$이 존재합니다. 만약 $D_s > M$이라면, 피드백은 누락된 것으로 간주 (검열) 됩니다.
• 관찰 확률: 창 내에서 피드백이 도착할 확률은 $\rho = P(D_s \le M)$입니다.
• 편향 도전 과제: 선형 밴딧에서는 추정기가 폐형식 해 (예: 릿지 회귀) 를 갖는 것과 달리, 대결 밴딧은 Bradley-Terry-Luce (BTL) 모델 하에서 최대우도추정 (MLE) 에 의존합니다. 이러한 폐형식 해의 부재는 단순한 대체나 누락된 데이터 무시와 같은 표준 지연 피드백 기법의 단순한 적응이 체계적인 편향을 초래하며, 이를 쉽게 경계하거나 보정할 수 없음을 의미합니다.

2. 방법론

저자들은 휴리스틱 대체 없이 이러한 지연을 처리하도록 설계된 두 가지 새로운 알고리즘을 제안합니다: 지연 피드백을 가진 선형 대결 밴딧 (LDB-DF) 과 지연 피드백을 가진 신경 대결 밴딧 (NDB-DF) 입니다.

핵심 메커니즘: 역확률 가중치 (IPW)

중앙 혁신은 역확률 가중치 (Inverse Probability Weighting, IPW) 메커니즘을 손실 함수에 직접 통합하는 것입니다.

• 가중치 전략: $t$라운드 ($s < t$) 에서 관찰된 피드백 인스턴스 $y_s$에 대해, 알고리즘은 $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$라는 가중치를 할당합니다.
• 편향 보정: 관찰된 피드백의 기여도를 $1/\rho$로 스케일링함으로써, 대리 손실의 기대 기울기가 실제 기울기의 편향 없는 추정기가 되어, 확률적 관찰 메커니즘과 누락된 데이터로 인해 도입된 편향을 효과적으로 중화시킵니다.

알고리즘 1: LDB-DF (선형 설정)

• 모델: 선형 보상 함수 $f(x) = \theta^\top \phi(x)$를 가정합니다.
• 추정: "도착한" 피드백만을 사용하여 IPW 정규화 로지스틱 손실을 최소화합니다.
• 탐색: 상한 신뢰 구간 (UCB) 전략을 활용합니다. 첫 번째 암은 현재 추정치 $\theta_t$에 기반하여 탐욕적으로 선택됩니다. 두 번째 암은 첫 번째 암에 대한 선호도 차이의 UCB 를 최대화하도록 선택되며, 여기에는 확률적 노이즈와 지연으로 인한 불확실성을 모두 고려하는 신뢰 반경 $\beta_t$가 포함됩니다.
• 정보 행렬: 피드백 지연과 무관하게 선택된 쌍의 특징 벡터를 사용하여 즉시 업데이트됩니다.

알고리즘 2: NDB-DF (신경 설정)

• 모델: ReLU 활성화 함수를 가진 완전 연결 신경망 $h(x; \theta)$를 사용하여 비선형 보상 함수를 근사합니다.
• 추정: 동일한 IPW 가중치 교차 엔트로피 손실을 사용하여 네트워크를 온라인으로 훈련하며, 유효 창 내에서 도착한 피드백 하위 집합에서만 학습합니다.
• 이론적 프레임워크: 분석은 신경 탄성 커널 (Neural Tangent Kernel, NTK) 영역에서 수행됩니다. 이 알고리즘은 네트워크가 충분히 넓어서 ($m$) 초기화 시 기울기 특징 공간에서 선형 함수처럼 행동한다고 가정합니다.
• 탐색: 선형 경우와 유사하게 UCB 전략을 사용합니다. 탐색 보너스는 NTK 특징 공간에서 유도되어 선호도 차이에 대한 인식적 불확실성을 정량화합니다.

3. 이론적 기여

본 논문은 지연 매개변수 ($M$ 및 $\rho$) 의 영향을 명시적으로 특징짓는 두 설정 모두에 대한 엄격한 후회 경계를 제공합니다.

• 선형 후회 경계: LDB-DF 의 누적 후회는 $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$로 확립됩니다.

  • 항 $\frac{M}{\rho}$는 곱셈적 패널티로 작용합니다. 더 작은 관찰 확률 $\rho$(더 적은 샘플) 와 더 큰 임계값 $M$(더 긴 잠재적 지연) 은 후회를 선형적으로 증가시킵니다.
  • $\rho=1$이고 $M=1$(지연 없음) 일 때, 이 경계는 표준 선형 대결 밴딧에 대한 최첨단 $\tilde{O}(d\sqrt{T})$를 회복합니다.

• 신경 후회 경계: NDB-DF 의 누적 후회는 $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$로 확립되며, 여기서 $\tilde{d}$는 NTK 행렬의 유효 차원입니다.

  • 증명은 지연으로 인한 체계적 편향과 마팅게일 노이즈를 분리하기 위한 새로운 "덧셈 및 뺄셈" 분해 기법에 의존합니다.
  • 분석은 복잡한 비선형 함수 근사기가 있더라도 관찰 가능성과 지연 크기 간의 근본적인 문제의 어려움 (트레이드오프) 이 지속됨을 확인합니다.

4. 실험 결과

저자들은 지연을 무시하거나 휴리스틱 대체를 사용하는 베이스라인에 대해 LDB-DF 와 NDB-DF 를 평가합니다.

• 베이스라인:
  • 무시 (Ignore): 동일한 모델 아키텍처를 사용하지만 가중치 없이 도착할 때까지 대기 중인 피드백을 폐기합니다.
  • 휴리스틱 (Heuristic): 현재 모델의 예측된 선호도를 사용하여 누락된 피드백을 대체합니다 (편향된 대리 변수).
• 데이터셋:
  • 합성: 확률적 기하 지연을 가진 선형, 이차, 그리고 3 차 보상 함수.
  • 실제 세계: InstructZero 벤치마크 (29 개 지시 유도 작업) 를 사용한 자동화된 프롬프트 최적화.
• 발견:
  • 제안된 두 알고리즘 모두 누적 후회 측면에서 베이스라인을 크게 능가합니다.
  • 비선형 설정에서 휴리스틱 베이스라인은 종종 자기 강화 예측 오류 (환각) 로 인해 비최적 영역으로 수렴하는 반면, 무시 베이스라인은 데이터 희소성으로 고통받습니다.
  • LDB-DF 와 NDB-DF 는 피드백 지연에 대한 견고성을 보여주며, 프롬프트 최적화 작업에서 검색 공간을 효과적으로 탐색합니다.

5. 중요성과 주장

본 논문은 다음을 동시에 처리하는 최초의 통합 프레임워크를 제공함으로써 선호도 기반 학습의 중요한 간극을 해소했다고 주장합니다:

1. 선호도 피드백 (대결): 절대적 보상이 아닌 이진 상대적 결과.
2. 비선형 근사 (신경): 신경망을 통한 복잡한 보상 지형.
3. 확률적 지연/누락 데이터: 현실적인 피드백 지연 및 검열.

저자들은 휴리스틱 대체에서 벗어난 원칙적이고 편향 없는 IPW 기반 솔루션을 제공한다고 강조합니다. 이론적 분석은 이 특정 설정에 대한 최초의 후회 경계를 확립하여, 성능 저하가 예측 가능하고 지연 특성 ($M/\rho$) 에 선형적으로 의존함을 보여줍니다. 이 작업은 특히 LLM 정렬 및 프롬프트 최적화를 위한 인간 - 루프 시스템에서 비동기 선호도 학습을 개선하기 위한 기초적인 단계로 위치합니다.