Frequent Directions를 통한 효율적인 다항 로지스틱 밴딧 (Multinomial Logistic Bandit)

본 논문은 $K+1$개의 결과에 대한 피드백 분포가 $d$차원 액션 벡터의 다항 로지스틱 모델 (multinomial logistic model)을 따르는 다항 로지스틱 밴딧 (multinomial logistic bandits, MLogB)을 위한 효율적인 온라인 알고리즘을 연구합니다. 대표적인 UCB 유형 알고리즘인 OFUL-MLogB는 $\tilde{\mathcal{O}}(Kd\sqrt{T})$의 후회 한계 (regret bound)를 달성하지만, 파라미터 추정 (parameter estimation) 및 낙관적 보상 (optimistic reward) 구축으로 인해 라운드당 $\mathcal{O}(K^3d^3)$의 시간과 $\mathcal{O}(K^2d^2)$의 공간이 여전히 필요하며, 이는 고차원 설정에서 매우 부담스럽습니다. 이러한 한계를 해결하기 위해, 우리는 Frequent Directions 행렬 스케칭 (matrix sketching)을 OFUL-MLogB에 통합한 EOFD-MLogB를 제안합니다. 누적된 헤시안 (Hessian)의 저계수 SVD 스케치 (low-rank SVD sketch)를 유지함으로써, 파라미터 추정에서의 제약된 온라인 뉴턴 업데이트 (constrained online Newton updates)와 보상 보너스 (reward bonus)에서의 $Kd \times K$ 스펙트럼 노름 (spectral-norm) 계산은 각각 1차원 근 찾기 (root-finding) 작업과 $K \times K$ 고유값 (eigenvalue) 계산으로 축소됩니다. 이를 통해 라운드당 지배적인 시간 복잡도는 $\mathcal{O}(Kd(m+K)^2)$, 공간 복잡도는 $\mathcal{O}(Kd(m+K))$가 되며, 여기서 $m \ll d$는 스케치 크기 (sketch size)입니다. 우리는 더 나아가 $\tilde{\mathcal{O}}(\Delta_T(Kd\ln\Delta_T+m)\sqrt{T})$의 후회 한계를 증명하며, 여기서 스케칭 오차 요인 $\Delta_T$는 헤시안의 $m$-절단 스펙트럼 꼬리 (m-truncated spectral tail)에 의해 제어됩니다. 따라서 헤시안이 근사적으로 저계수 (low-rank)일 때, 후회는 OFUL-MLogB의 후회와 유사합니다. 실험을 통해 계산 효율성과 경쟁력 있는 성능을 검증합니다.