기술적 요약: 적대적 커널 밴드트에서의 근사 최적 후회

1. 문제 정의

본 논문은 손실 함수가 재생 커널 힐베르트 공간 (RKHS) 에 속하는 적대적 선형 밴드트의 일반화인 적대적 커널 밴드트 문제를 다룹니다.

• 설정: 각 라운드 $t \in [T]$에서 학습자는 유한한 행동 집합 $\mathcal{X} \subset \mathbb{R}^d$로부터 행동 $x_t$를 선택합니다. 동시에, 무관심한 (oblivious) 적대자는 RKHS $\mathcal{H}$ 내의 벡터 $w_t$를 선택합니다.
• 손실: 학습자는 $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$의 손실을 입으며, 여기서 $\Phi: \mathcal{X} \to \mathcal{H}$는 대칭 양의 정부호 커널 $K$에 연관된 특징 매핑입니다.
• 피드백: 학습자는 벡터 $w_t$나 전체 손실 함수가 아닌 스칼라 손실 $\ell_t(x_t)$만을 관찰합니다.
• 목표: 사후 (hindsight) 에서의 최선의 고정 행동 $x^*$에 대한 기대 후회 $R_T$를 최소화합니다:
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• 가정: 적대자는 유계 ($\|w_t\|_{\mathcal{H}} \le B$) 이며, 커널 또한 유계 ($K(x,x) \le 1$) 입니다. Chatterji 등 [2019] 의 이전 연구와 달리, 적대자는 단일 랭크 (rank-one) 손실로 제한되지 않습니다 (즉, $w_t$가 $\Phi(z_t)$ 형태일 필요가 없음); $w_t$는 유계 노름을 가진 $\mathcal{H}$의 임의의 원소가 될 수 있습니다.

2. 방법론 및 알고리즘

저자들은 무한 차원 특징 공간에 적합하도록 조정된 지수 가중치 (Exp2) 기반 알고리즘을 제안합니다. 핵심적인 도전 과제는 선형 밴드트에서의 표준 중요도 가중 추정기 (importance-weighted estimator) 가 공분산 연산자의 고유값이 0 에 가까워짐에 따라 무한 차원 RKHS 에 있는 특징 매핑으로 인해 무계 (unbounded) 가 된다는 점입니다.

이를 극복하기 위해 저자들은 두 가지 주요 수정을 도입합니다:

1. 정규화된 중요도 가중 추정기:
   경험적 공분산 연산자 $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$를 역전하는 대신, 알고리즘은 리지 정규화 버전인 $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$를 사용합니다. 추정기는 다음과 같이 정의됩니다:
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   이 정규화는 $\Sigma_t$의 고유값이 0 에 가까울 때도 추정기가 유계로 유지되도록 보장합니다. 그러나 이는 체계적인 편향을 도입합니다: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. 명시적 편향 보정 항:
   정규화 편향을 보상하기 위해 알고리즘은 보정된 손실 대리 변수 $\hat{\ell}_t(x)$를 구성합니다:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   여기서 보정 항은 $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$입니다.

   • 메커니즘: 보정 항은 폐쇄형 편향 표현식에서 직접 유도됩니다. 이는 편향에 대한 점별 상한 (pointwise upper bound) 으로 작용하여, 비교 대상 (최선의 고정 행동) 에 대해 기대 손실 대리 변수가 실제 손실을 과소평가하도록 보장합니다. 이 구조적 선택은 후회 분해에서 비교 대상 측 잔여항이 음수가 아니게 하여, 제어 가능한 학습자 측 잔여항만 남게 합니다.

3. 탐색 전략:
   알고리즘은 현재 지수 가중치 분포 $q_t$와 고정된 탐색 분포 $\nu_G$의 혼합인 분포 $p_t$를 유지합니다. 탐색 분포는 유효 차원이 제어되도록 정규화된 G-최적 설계 (G-optimal design) 를 통해 선택됩니다.

3. 주요 기여

• 알고리즘 설계: 지수 가중치와 정규화된 추정기 및 명시적 편향 보정 항을 결합한 원칙적인 알고리즘입니다. 이 접근법은 Chatterji 등 [2019] 이 요구했던 제한적인 단일 랭크 적대자 가정을 피합니다.
• 유효 차원을 통한 후회 분석: 저자들은 커널의 유효 차원 $d^*(\lambda)$에 의존하는 후회 상한을 유도합니다. 이는 다음과 같이 정의됩니다:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• 단일 랭크 가정 제거: 이 프레임워크는 임의의 유계 RKHS 손실을 허용하여, 단일 랭크 제약이 필요한 투영 기반 추정기에 의존했던 이전 연구에 비해 적용 범위를 크게 확장합니다.

4. 주요 결과

본 논문은 다음과 같은 형태의 후회 상한을 확립합니다:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
여기서 $d^*(\lambda)$는 커널의 복잡성을 포착합니다. 이 속도는 (로그 인자까지) 확률적 커널 밴드트 문제에 대해 알려진 최적 속도와 일치합니다.

특정 커널 속도:

• Matérn$(\nu, d)$ 커널: $\mathbb{R}^d$에서 매끄러움 $\nu$를 가진 Matérn 커널의 경우, 유효 차원은 다음과 같은 후회 상한을 산출합니다:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  이는 Chatterji 등 [2019] 의 이전 최선 알려진 속도 $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$를 개선하며, 로그 인자까지 동시 연구 [Iwazaki, 2026] 의 하한과 일치합니다. 주목할 점은 이전 속도는 $\nu < d/2$일 때조차 비선형 (sublinear) 이 아니었으나, 새로운 상한은 항상 비선형이라는 것입니다.
• 제곱 지수 (SE) 커널: 이 상한은 Chatterji 등 [2019] 과 일치하지만 단일 랭크 제한 없이 근사 최적인 $\tilde{O}(\sqrt{T})$ 속도를 회복합니다.
• 일반 고유값 감쇠:
  • 다항식 감쇠 ($\mu_j \le C j^{-\beta}$): $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$를 달성합니다.
  • 지수 감쇠 ($\mu_j \le C e^{-\beta j}$): $R_T = \tilde{O}(\sqrt{T})$를 달성합니다.

5. 의의 및 주장

본 논문은 적대적 및 확률적 커널 밴드트 성능 간의 격차를 해소한다고 주장합니다. 구체적으로:

• 최적성: 유도된 속도는 로그 인자까지 (SupKernelUCB 또는 베이지안 최적화 방법을 통한) 확률적 커널 밴드트에 대해 알려진 최적 속도와 일치합니다.
• 이론적 발전: 단일 랭크 적대자 가정을 제거함으로써, 손실 함수가 RKHS 의 임의의 유계 원소인 더 일반적이고 현실적인 적대적 환경 클래스에 결과가 적용됩니다.
• 이전 연구와의 비교: 이 연구는 Matérn 커널 및 일반 다항식 감쇠에 대해 Chatterji 등 [2019] 을 개선하여, 이전 상한이 비선형이 아니었던 조건 하에서 더 엄격한 상한을 제공합니다.
• 동시 연구: 저자들은 정규화된 추정기와 편향 보정을 사용하는 밀접하게 관련된 접근법으로 유사한 결과를 달성한 Iwazaki [2026] 의 독립적인 동시 연구를 인정합니다. 논문은 문제 설정 (예: 무관심 대 적응형 적대자, 특정 복잡성 측정치) 에서의 미묘한 차이를 지적하지만, 핵심 알고리즘 및 분석적 기여는 본질적으로 동등하다고 주장합니다.

본 논문은 제안된 방법이 정규화와 명시적 편향 보정을 통해 무한 차원 특징 공간의 도전을 효과적으로 처리함으로써 적대적 커널 밴드트 문제에 대한 근사 최적 솔루션을 제공한다고 결론지었습니다.