커널 밴딧(Kernel Bandits)에서의 알고리즘 및 미니맥스 복잡도

가우시안 프로세스 상한 신뢰 구간 (Gaussian-process upper confidence bound, GP-UCB) 방식과 결정 추정 계수 (decision-estimation-coefficient, DEC) 방식은 언뜻 보기에 서로 다른 이론에 속하는 것처럼 보일 수 있습니다. 본 논문은 빈도주의적 RKHS 밴딧 (RKHS bandits)을 위해 이 두 가지 관점을 공통된 알고리즘 정보 언어로 통합합니다. GP-UCB는 실제 가우시안 프로세스 사전 확률 (Gaussian-process prior) 대신 알고리즘적 사전 확률을 고정하며, 계산적 용이성(computational tractability)과 함께 실현된 궤적의 복잡도 (realized-trajectory complexity)를 활용하는 반면, MAMS는 강건한 클래스 전체의 MAIR/DEC 엔벨로프 (envelope)를 최적화합니다. 통합된 MAIR 프레임워크와 이질적인 양의 준정부호 (positive-semidefinite) 알고리즘 사전 확률을 통해, 우리는 GP-UCB 분석과 MAMS 알고리즘을 모두 일반화하고, 이들의 장점을 결합한 보호된 마스터 (safeguarded master)를 제안하며, 과잉 매개변수화된 모델 (overparameterized models)에서 알고리즘 복잡도가 클래스 전체의 미니맥스 (minimax) 또는 DEC 인증서보다 더 많은 정보를 제공할 수 있음을 보여주는 커널 밴딧 (kernel-bandit) 구성을 제공합니다. 결과적인 메시지는 알고리즘 정보와 클래스 전체의 미니맥스 계수가 서로 다른 질문에 답하며 서로 다른 격차 (gaps)를 유발할 수 있다는 것이며, 커널 밴딧은 이러한 구분이 수학적으로 명확하게 드러나는 깔끔한 환경을 제공합니다.