Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

기술적 요약: 분리된 밴딧을 위한 Perturbed-Leader 추종 (Follow-the-Perturbed-Leader)

문제 설정
본 논문은 분리된 다중-팔 밴딧 (Multi-Armed Bandit, MAB) 문제를 다루며, 이는 학습자가 매 라운드 $t$에서 두 개의 서로 다른 팔을 선택하는 설정입니다. 하나는 활용 (exploitation) 을 위한 팔 $i_t$로 손실 $\ell_{t, i_t}$를 입지만 관찰하지는 않으며, 다른 하나는 탐색 (exploration) 을 위한 팔 $j_t$로 손실 $\ell_{t, j_t}$를 관찰하지만 손실은 입지 않습니다. 이 프레임워크는 전송 채널과 다른 채널을 감지하는 초광대역 (ultra-wideband) 통신 시스템이나 로봇공학의 시뮬레이션 - 현실 (sim-to-real) 전이와 같은 시나리오를 모델링합니다. 목표는 학습자의 활용 선택으로 인해 발생한 누적 손실과 사후에 본 최선의 고정된 팔의 누적 손실 사이의 차이로 정의된 의사-후회 (pseudo-regret) 를 최소화하는 것입니다.

본 논문은 양쪽 세계의 최적 (Best-of-Both-Worlds, BOBW) 보장을 목표로 하여 다음을 달성하려 합니다:

1. 적대적 환경 (adversarial regime) (손실이 적응형 적대자에 의해 결정됨) 에서 $O(\sqrt{KT})$의 최적 후회 (optimal regret).
2. 확률적 제약 하의 적대적 (Stochastically Constrained Adversarial, SCA) 환경 (표준 확률적 설정을 포함함) 에서 $\Delta_{\min}$이 최소 비최적성 갭일 때 $O(K/\Delta_{\min})$의 거의 최적이며 시간에 무관한 후회 (near-optimal, time-independent regret).

방법론
저자들은 분리된 설정에서 기존 BOBW 정책들의 계산 병목 현상을 극복하도록 특별히 설계된 Perturbed-Leader 추종 (Follow-the-Perturbed-Leader, FTPL) 프레임워크 기반의 새로운 정책을 제안합니다.

• 활용 전략: 학습자는 교란된 누적 손실 추정을 최소화하는 팔을 활용 팔 $i_t$로 선택합니다:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  여기서 $\hat{L}_{t,i}$는 추정된 누적 손실, $\eta_t$는 학습률이며, $r_{t,i}$는 모양 매개변수 $\alpha > 1$을 갖는 파레토 분포 (Pareto distribution) $P_\alpha$에서 샘플링된 i.i.d. 무작위 교란입니다. 이 교란 유형은 BOBW 보장을 달성하는 것으로 알려진 $\beta$-Tsallis-INF 정책 (여기서 $\alpha = 1/(1-\beta)$) 에 해당합니다.

• 탐색 전략 (핵심 혁신): 표준 FTPL 밴딧 알고리즘에서는 편향되지 않은 중요도 가중 (IW) 손실 추정자를 구성하려면 팔 $i$를 선택할 정확한 확률 $w_{t,i}$를 알아야 합니다. 그러나 분리된 밴딧에서는 탐색 확률 $p_{t,i}$가 $w_{t,i}$에 기반하여 설정되어야 합니다. 하지만 FTPL은 FTRL과 달리 $w_{t,i}$에 대한 폐쇄형 표현식을 제공하지 않으며, 기하학적 재샘플링을 통해 전체 벡터를 추정하는 것은 계산 비용이 매우 높습니다 ($O(K^2)$ 이상).
  이를 해결하기 위해 저자들은 재샘플링이나 볼록 최적화 없이 현재 손실 추정치로부터 직접 계산할 수 있는 대리 확률 (surrogate probability) $q_{t,i}$를 도입합니다:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  여기서 $\sigma_{t,i}$는 모든 팔 중 $\hat{L}_{t,i}$의 순위입니다. 그런 다음 탐색 팔 $j_t$는 정규화된 분포 $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$에 따라 선택됩니다. 이 접근법은 명시적인 $w_{t,i}$ 값의 필요성을 피하면서도 BOBW 보장에 필요한 이론적 속성을 유지합니다.

주요 기여

1. 분리된 밴딧을 위한 최초의 FTPL 기반 BOBW 정책: 본 논문은 FTRL 기반 접근법 (Decoupled-Tsallis-INF 등) 이 요구하는 볼록 최적화 문제를 해결하거나 FTPL 확률 추정에 일반적으로 필요한 재샘플링 절차를 수행하지 않고도 분리된 밴딧에서 BOBW 보장을 달성하는 최초의 정책을 제시합니다.
2. 계산 효율성: 전체 확률 벡터 계산을 효율적으로 계산 가능한 대리값 $q_{t,i}$로 대체함으로써 제안된 정책은 단계당 계산 복잡도를 줄입니다. 손실 추정치를 정렬하는 데 $O(K \log K)$가 소요되지만, 저자들은 순위 변화를 점진적으로 추적하는 최적화된 구현을 통해 $O(K)$ 업데이트를 달성할 수 있다고 지적합니다. 이는 매 단계마다 반복적인 볼록 최적화 (예: 뉴턴법) 가 필요한 FTRL 정책과 대조됩니다.
3. 이론적 보장:
   • 적대적 환경: 정책은 분리된 밴딧에 대한 알려진 하한과 일치하는 $O(\sqrt{KT})$ 후회 상한을 달성합니다.
   • 확률적/SCA 환경: 정책은 $O(K/\Delta_{\min})$의 후회 상한을 달성합니다 (구체적으로 $\alpha=3$인 경우 $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$). 이는 거의 최적이며 표준 확률적 밴딧의 시간 의존적 상한보다 개선된 것입니다.

결과

• 이론적: 본 논문은 안정성 및 페널티 항으로 후회를 분해하여 엄밀한 증명을 제공하며, 대리 확률 $q_{t,i}$가 필요한 후회 상한을 유지하기에 실제 활용 확률과 충분히 근접함을 보여줍니다.
• 실증적: 합성 데이터 (적대적 및 확률적 환경 모두) 와 MovieLens 100K 데이터셋을 사용한 실제 시뮬레이션에 대한 실험은 제안된 FTPL 정책이 다음을 보여준다고 입증합니다:
  • 기존 BOBW 정책 (Decoupled-Tsallis-INF/FTRL 및 EXP3) 보다 낮은 누적 후회를 달성합니다.
  • 우수한 계산 효율성을 보여줍니다. 적대적 환경에서 제안된 정책은 FTRL 기반 베이스라인보다 훨씬 빠르게 실행됩니다. $K=64$인 경우, FTRL과 FTPL의 실행 시간 비율은 약 1363 배 더 느린 것으로 관찰되었습니다.
  • 팔의 수 $K$에 따라 효과적으로 확장되며, 다양한 갭 크기 $\Delta$ 전반에 걸쳐 견고성을 유지합니다.

의의 및 주장
본 논문은 분리된 밴딧 맥락에서 FTRL 기반 BOBW 정책의 이론적 최적성과 FTPL 의 계산 효율성 사이의 간극을 해소하는 것이 주요 기여라고 주장합니다. 볼록 최적화와 재샘플링의 필요성을 제거함으로써 제안된 방법은 FTPL 이 후회 성능을 희생하지 않고도 그 효율성 이점을 완전히 실현할 수 있게 합니다. 저자들은 정확한 확률 벡터 대신 효율적으로 계산 가능한 대리 확률을 사용하는 기법이 FTPL 을 넘어 다른 알고리즘 프레임워크 (예: Prod 계열) 에도 적용 가능할 수 있으며, 이는 더 넓은 밴딧 설정에서 계산 효율성을 개선할 잠재력을 가진다고 시사합니다. 이 연구는 단계당 계산 지연이 중요한 통신 시스템 및 로봇공학의 실제 응용 분야에서 동기부여를 받았습니다.