속도 최적 큐 길이 후회(Regret)를 갖는 문맥적 큐잉 밴딧(Contextual Queueing Bandits) 알고리즘

문맥적 큐잉 밴딧 (Contextual queueing bandits)은 알려지지 않은 문맥 의존적 서비스 속도 (context-dependent service rates) 하에서 이질적인 작업 (heterogeneous jobs)을 스케줄링하는 법을 학습하기 위한 프레임워크를 제공합니다. 확률적 문맥 (stochastic contexts) 하에서 기존 알고리즘들은 시간 지평 (horizon) $T$에서 학습자와 오라클 (oracle)의 큐 길이 사이의 기대 차이로 정의되는 $\widetilde{\mathcal{O}}(T^{-1/4})$의 큐 길이 후회 (queue length regret)를 달성합니다. 본 논문에서는 이 속도를 $\widetilde{\mathcal{O}}(T^{-1/2})$로 개선합니다. 핵심 관찰 결과는 무작위 탐색 (random exploration)이 전체 시간 지평 동안이 아니라, 신중하게 선택된 컷오프 라운드 (cutoff round)까지만 필요하다는 것입니다. 우리는 세 단계 알고리즘인 CQB-$η$-2를 제안합니다: (i) 초기 추정치 (estimator)를 구축하기 위한 순수 무작위 탐색 (pure random exploration), (ii) 음의 드리프트 (negative drift)를 유지하면서 학습을 지속하기 위해 UCB 규칙과 결합된 $η$-무작위 탐색 ($η$-random exploration), (iii) 탐색 컷오프 이후의 순수 UCB (pure UCB). 우리의 증명은 컷오프 라운드에서의 큐 길이 후회를 분해합니다. 컷오프 전에는 음의 드리프트가 최적이 아닌 선택으로 인해 발생하는 큐 길이 차이를 억제합니다. 컷오프 후에는 처음 두 단계가 충분한 무작위 탐색 샘플을 제공하여, UCB 결정이 작은 출발 속도 차이 (departure-rate gaps)를 유발하도록 보장합니다. 이 두 경계 (bounds)를 결합하면 $\widetilde{\mathcal{O}}(T^{-1/2})$ 차수의 큐 길이 후회를 얻을 수 있습니다. 우리는 더 나아가 $Ω(T^{-1/2})$ 차수의 미니맥스 하한 (minimax lower bound)을 증명합니다. 증명 과정에서는 마지막 서비스 결정 전까지 통계적으로 구별할 수 없는 두 가지 어려운 사례 (hard instances)를 구성하고, 큐 특유의 결합 (coupling) 논법을 사용하여 결과적인 테스트 오차 (testing error)를 큐 길이 후회로 변환합니다. 결과적으로, 우리의 상한 (upper bound)과 하한 (lower bound)은 로그 인자 (logarithmic factors)를 제외하고 시간 지평 $T$에 대한 미니맥스 의존성을 규명합니다.