선형 상황 밴딧의 분산 의존적 후회 하한에 대한 새로운 연구

He와 Gu (2025)의 연구는 선형 상황 밴딧에서 분산 의존적 후회 하한에 대한 새로운 결과를 제시합니다. 기존 연구의 한계를 극복하여, 사전 설정 및 적응형 분산 시퀀스 설정에서 새로운 하한을 제시하며, 기존 상한과의 차이를 최소화했습니다. 이 연구는 선형 상황 밴딧에 대한 이론적 이해를 심화시키고, 효율적인 알고리즘 개발에 기여할 것으로 예상됩니다.

선형 상황 밴딧의 분산 의존적 후회 하한: 기존 연구의 한계를 넘어서

최근 몇 년 동안 선형 상황 밴딧(linear contextual bandits)에 대한 연구가 활발히 진행되고 있습니다. 특히, 고전적인 (\tilde{O}(d\sqrt{K})) 후회(regret) 상한을 개선하여 (\tilde{O}(d\sqrt{\sum_{k=1}^K\sigma_k^2})) 와 같은 분산 의존적(variance-dependent) 후회 상한을 얻는 연구가 주목받았습니다. 여기서 (d)는 context 차원, (K)는 라운드 수, (\sigma_k^2)는 k번째 라운드의 노이즈 분산을 나타냅니다.

그러나 기존 연구들은 주로 후회 상한에 집중했고, 하한에 대한 연구는 부족했습니다. Jia et al. (2024)의 연구는 분산 의존적 하한 (\Omega(\sqrt{d_{\textbf{elu}}\Lambda})) 를 제시했지만, 기존 상한과의 차이(gap)가 존재하고, 고정된 총 분산 예산 (\Lambda)만을 고려하여 일반적인 분산 시퀀스 ({\sigma_1^2, \ldots, \sigma_K^2}) 에 적용되지 못하는 한계가 있었습니다.

He와 Gu의 연구: 이러한 한계를 극복하기 위해, He와 Gu (2025)는 일반적인 분산 시퀀스를 두 가지 설정에서 고려했습니다.

• 사전 설정 시퀀스(Prefixed sequence): 학습 과정 초기에 전체 분산 시퀀스가 학습자에게 공개되는 경우, (\Omega(d\sqrt{\sum_{k=1}^K\sigma_k^2}/\log K)) 의 분산 의존적 하한을 제시했습니다.
• 적응형 시퀀스(Adaptive sequence): 적대자가 과거 관측값을 기반으로 각 라운드의 분산 (\sigma_k^2)를 생성하는 경우, 적대자가 결정 집합 (\mathcal{D}k)를 관찰하기 전에 (\sigma_k^2)를 생성해야 한다면 (\Omega(d\sqrt{\sum{k=1}^K\sigma_k^2}/\log^6(dK))) 의 유사한 하한이 성립함을 보였습니다.

두 설정 모두에서, 그들의 결과는 Zhao et al. (2023)의 SAVE 알고리즘의 상한과 로그 계수까지 일치합니다. 이는 선형 상황 밴딧에 대한 이론적 이해를 심화시키는 중요한 결과입니다. 이는 향후 더욱 효율적인 알고리즘 개발에 기여할 것으로 기대됩니다. 하지만 적응형 시퀀스 설정에서의 하한은 여전히 상한과 로그 차수만큼의 차이가 존재하므로, 향후 연구에서 이 부분의 개선이 필요할 것으로 보입니다.