Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

기술 요약: 서브 가우시안 보상을 갖는 위험 회피형 밴딧을 위한 톰슨 샘플링의 점근적 최적성

문제 정의
본 논문은 위험 회피형 목적 함수 하에서의 멀티 암드 밴딧(Multi-Armed Bandit, MAB) 문제를 다룹니다. 기대 보상을 최대화하는 표준 MAB 설정과 달리, 위험 회피형 설정은 일반적인 위험 범함수 $\rho$(예: 조건부 가치-위험(CVaR), 평균-분산, 샤프 지수 또는 왜곡 위험 측정치)를 최적화하는 것을 목표로 합니다. 본 연구가 다루는 구체적인 과제는 $\rho$-NPTS(Chang 및 Tan [2022]이 제안한 비매개변수적 톰슨 샘플링 알고리즘)의 이론적 분석입니다. Chang와 Tan은 매개변수적 동반 모델인 $\rho$-MTS에 대해서는 사례 최적적(instance-optimal) 후회를 증명했으나, 비매개변수적 $\rho$-NPTS의 최적성 문제는 미해결 과제로 남겨두었습니다.

근본적인 장애물은 $\rho$-NPTS가 관측치 수($N_k$)에 따라 유효 알파벳 크기가 증가하는 디리클레 사후 분포를 구성한다는 점입니다. 기존 꼬리 확률 경계(tail bounds) 결과를 직접 적용할 경우 $(N_k)^{N_k/2}$라는 초지수적 전계수(prefactor)가 발생하여, 로그 후회(logarithmic regret) 경계 증명을 가로막습니다. 또한, 이전 결과들은 "지배(dominance)" 조건(매개변수적 방법의 경우)이나 리프시츠 연속성(UCB 유형 알고리즘의 경우)과 같은 강력한 조건을 요구했는데, 이는 샤프 지수와 같이 리프시츠 연속성이 없는 중요한 범함수들을 배제합니다.

방법론
저자들은 유계 밀도와 서브 가우시안 꼬리($P(B, \sigma)$)를 가진 분포를 위해 설계된, 앵커 프리(anchor-free) 방식의 비매개변수적 톰슨 샘씨 알고리즘 변형인 $\rho$-NPTSSG를 도입합니다. 핵심적인 기술적 혁신은 성장하는 알파벳의 디리클레 사후 분포를 고정된 격자(grid) 위로 투영하는 이산화 레마(discretisation lemma)(및 서브 가우시안 꼬리를 위한 절단된 형태의 레마)입니다.

1. 이산화 및 집계:
   본 논문은 크기 $M$인 고정 격자 $G_M$을 정의합니다. 임의의 관측된 보상 시퀀스에 대해, 경험적 측도(empirical measure)는 동일한 격자 빈(bin) 내에 떨어지는 관측치들에 대응하는 디리클레 가중치를 집계함으로써 이 격자 위로 투영됩니다.

   • 핵심 통찰: 디리클레 분포의 집계 성질에 의해, 점유된 빈(bin)에 대한 투영된 가중치는 관측치 수 $N_k$와 무관하게 고정된 차원($M^+ \le M$)을 갖는 디리클레 분포를 따릅니다.
   • 결과: 이 투영은 꼬리 경계의 다항식 전계수를 $N_k$에 의존하지 않는 차수인 $(M-1)/2$로 제한합니다. 이는 이전의 증명을 가로막았던 초지수적 장벽을 깨뜨립니다.

2. 알고리즘 변형:

   • $\rho$-NPTS (유계 지지 집합): $[0, 1]$ 범위의 지지 집합과 유계 밀도를 가진 분포에서 작동합니다. 고정된 앵커(우측 끝점)와 균등 격자를 사용합니다.
   • $\rho$-NPTSSG (서브 가우시안): 유계 밀도와 서브 가우시안 꼬리를 가진 $\mathbb{R}$ 상의 분포에서 작동합니다. 고정 앵커를 제거하고(라운드 로빈 초기화 사용) 절단된 이산화(truncated discretisation) 레마를 채택합니다. 이 레마는 샘플 크기가 증가함에 따라 폭이 좁아지는 경험적 평균 중심의 격자를 사용하며, 오버플로 확률을 제어하기 위해 꼬리를 절단합니다.

3. 후회 분석:
   증명은 알고리즘이 "높은" 톰슨 점수를 가진 하위 최적 암(arm)을 뽑는 경우와 "낮은" 점수를 뽑는 경우로 나누어 후회를 분해하는 표준적인 방식을 따릅니다.

   • 상한(Upper Bound): 고정 격자 투영에 Chang 및 Tan [2022]의 꼬리 경계를 적용하기 위해 이산화 레마를 활용합니다. $\rho$의 연속성($D_\infty$-연속성)은 투영된 측도가 실제 위험을 근사함을 보장합니다.
   • 하한(Lower Bound): Chang 및 Tan [2022]이 확립한 쿨백-라이블러(KL) 발산 최소화 문제 $K^\rho_{\inf}$에 기반한 사례 의존적 하한과 일치합니다.

주요 기여

1. 미해결 문제 해결: 본 논문은 유계 밀도와 서브 가우시안 꼬리를 가진 분포 클래스에 대해 $\rho$-NPTSSG가 $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$의 사례 최적적 후회를 달eric함을 증명했습니다.
2. 더 약한 조건: 본 결과는 $\rho$의 연속성(구체적으로 르베그-프로코로프 메트릭에 대한 연속성)만을 요구합니다. 이는 다음보다 엄격히 완화된 조건입니다:
   • 매개변수적 $\rho$-MTS에 필요한 "지배" 조건.
   • UCB 유형 알고리즘에 필요한 리프시츠 조건.
     이를 통해 매개변수적 보상 분포를 가정하지 않고도 샤프 지수와 같은 비-리프시츠 범함수에 대한 최초의 사례 최적 보장을 제공합니다.
3. 이산화 레마: 본 논문은 성장하는 지원(support)을 가진 디리클레 프로세스를 포함하는 모든 문제에 독립적으로 활용될 수 있는 기술적 레마를 소개합니다.
4. 서브 가우시안 확장: 저자들은 고정된 지지 구간을 지정할 필요 없이 절단된 이산화 접근법을 통해 유계 지지 집합 결과를 더 넓은 클래스인 서브 가우시안 분포(가우시안 암 포함)로 확장했습니다.

결과

• 정리 1 (유계 지지 집합): 연속성만으로 $P(B)$에 대한 $\rho$-NPTS의 점근적 최적성을 확립합니다.
• 정리 2 (서브 가우시안): $P(B, \sigma)$에 대한 $\rho$-NPTSSG의 점근적 최적성을 확립합니다.
• 실험적 검증: 본 논문은 이론을 검증하는 네 가지 실험을 제시합니다:
  1. $\rho$-NPTS는 Beta 암에 대한 CVaR에 대해 사례 최적 하한을 추적하며, Risk-LCB 베이스라인($\log^2 n$ 보장)보다 우수한 성능을 보입니다.
  2. $\rho$-NPTS는 절단된 정규 분포 암에 대해 샤프 지수에 대한 $O(\log n)$ 후회를 달성하며, 이는 기존에 어떤 알고리즘도 보장을 제공하지 못했던 사례입니다.
  3. $\rho$-NPTS는 수정 없이 합성 범함수(예: $0.5 \text{CVaR} + 0.5 \text{Sharpe}$)를 처리할 수 있습니다.
  4. $\rho$-NPTSSG는 가우시안 암에 대해 사례 최적 하한으로 수렴하며, 가우시안 보상을 가정하지 않고도 특화된 Normal-Gamma 톰슨 샘플링 알고리즘(Shah et al. [2025])과 대등한 성능을 보입니다.

의의 및 주장
본 논문은 위험 회피형 밴딧을 위한 비매개변수적 톰슨 샘플링의 이론적 지위를 확립한다고 주장합니다. 저자들은 이러한 알고리즘들이 단순한 경험적 휴리스틱이 아니라 증명 가능한 점근적 최적성을 갖추고 있음을 보여줍니다.

의의는 다음과 같은 가정의 완화에 있습니다:

• 실무자는 보상 격자를 미리 지정하거나 알파벳 크기를 튜닝할 필요 없이 가공되지 않은 관측치를 그대로 사용할 수 있습니다.
• 이 방법은 이전의 최적 방법들보다 엄격히 더 넓은 클래스의 위험 범함수(샤프 지수 포함)와 분포 클래스(서브 가우시안)에 적용 가능합니다.
• 본 결과는 가우시안 공액 사전 분포나 매개변수적 가정을 요구하지 않고 샤프 지수에 대한 더 날카로운 사례 최적 상수를 제공함으로써 Shah et al. [2025]의 연구를 포괄합니다.

저자들은 유계 밀도 가정이 빈 확률 경계에 사용된 증명에 필수적이며, 베르누이와 같이 점 질량(point mass)을 가진 분포에는 적용되지 않는다고 언급했습니다. 이러한 경우 매개변수적 $\rho$-MTS가 보완적인 솔루션이 됩니다. 향후 연구 방향으로는 컨텍스추얼 밴딧, 헤비 테일(heavy-tailed) 보상, 이산 분포 등이 포함됩니다.