다중 클래스 및 희소 컨텍스트 방디트의 표본 복잡성

The Sample Complexity of Multiclass and Sparse Contextual Bandits

본 연구에서는 확률적 독립 동일 분포(i.i.d.) 환경에서 작동하는 컨텍스트 방디트를 다룹니다. 학습자는 알려지지 않은 분포에서 추출된 컨텍스트를 관찰하고, 유한 집합 $A$에서 액션을 선택하며, 방디트 피드백을 기반으로 주어진 클래스 내에서 근사적으로 최적의 정책을 식별하는 것을 목표로 합니다. 0-1 보상을 갖는 방디트 다중 분류 문제에 착안하여, 본 연구는 모든 컨텍스트에 대해 보상 벡터의 $L_1$ 노름이 $s extless} |A|$인 extit{s-희소(s-sparse)} 환경에 초점을 맞춥니다. 주요 결과로, 높은 확률로 정책 클래스 $Π$와 비교하여 $ ilde{O} ((s/ε^2 + |A|/ε)rac{ ext{log } |Π|}{ ext{δ}})$개의 표본을 사용하여 ε-최적의 정책을 출력하는 알고리즘을 설계했습니다. 이 경계를 일반 Natarajan 클래스로 확장하고, 이에 상응하는 하한(로그 인자 제외)을 제시함으로써 기존 연구(Erez et al., 2024, 2025)가 가진 상당한 격차를 해소합니다. 기존 연구는 추가적으로 $Θ(|A|^9)$의 의존성을 가졌습니다. 이러한 결과는 두 가지 상호 보완적인 접근 방식을 통해 얻어졌습니다. 첫째, 컨텍스트 방디트를 구조화된 관측을 갖는 컨텍스트 의사 결정 문제의 관점에서 분석하고, 탐색-최적화 알고리즘을 설계하여 표본 복잡성이 extit{의사 결정-추정 계수}(DEC; Foster et al., 2021, 2022)에 의해 결정되도록 했습니다. s-희소 보상을 갖는 경우, 유도된 모델 클래스는 DEC에 대한 명확한 경계를 가지며, 이는 $s$에 따라 스케일링되고 최적의 수렴률을 직접적으로 제공합니다. 이 접근 방식은 주로 정보 이론적인 측면을 다루고 복잡한 최소-최대 최적화 문제를 포함하므로, 두 번째로 더 특수한 알고리즘 방법인 저분산 탐색 기법 기반 방법을 개발했습니다. 이 접근 방식은 구체적이고 실용적인 알고리즘을 제공하며, 컨텍스트 조합 준-방디트로 자연스럽게 확장되어 방디트 다중 클래스 목록 분류에 대한 개선된 표본 복잡성 보장을 가능하게 합니다.

We study contextual bandits in the stochastic i.i.d.\ setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set $A$, and aims to identify an approximately optimal policy from a given class based on bandit feedback. Motivated by bandit multiclass classification with zero-one rewards, we focus on the \emph{$s$-sparse} setting in which, for every context, the reward vector has $L_1$-norm at most $s \ll |A|$. Our main result is the design of algorithms that, with high probability, output an $ε$-optimal policy compared to policy class $Π$ using $\tilde{O} ((s/ε^2 + |A|/ε)\log |Π|/δ)$ samples. We extend this bound to general Natarajan classes and complement it with a matching lower bound (up to logarithmic factors), thereby closing a substantial gap left by prior work (Erez et al., 2024, 2025), which incurred an additional $Θ(|A|^9)$ dependence. We obtain these results via two complementary approaches. First, we analyze contextual bandits through the lens of contextual decision making with structured observations, designing an exploration-by-optimization algorithm whose sample complexity is governed by the \emph{decision-estimation coefficient} (DEC; Foster et al., 2021, 2022). We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate. Since this approach is largely information-theoretic and involves solving complex min-max optimization problems, we also develop a second, more specialized algorithmic method based on a low-variance exploration technique. This approach leads to concrete, tractable algorithms and naturally extends to contextual combinatorial semi-bandits, leading to improved sample complexity guarantees for bandit multiclass list classification.