When and why randomised exploration works (in linear bandits)

기술 요약: 선형 밴딧(Linear Bandits)에서 무작위 탐색이 언제, 왜 작동하는가

문제 설정
본 논문은 에이전트가 $\mathbb{R}^d$의 단위 유클리드 구(unit Euclidean ball) 내의 닫힌 부분 집합 $\mathcal{X}$로부터 행동 $X_t$를 선택하는 순차적 의사결정 환경인 선형 밴딧 문제를 다룹니다. 에이전트는 평균이 $\langle X_t, \theta^\star \rangle$인 보상 $Y_t$를 받으며, 여기서 $\theta^\star$는 미지의 파라미터 벡터입니다. 목표는 최적의 행동과 실제로 취해진 행동 사이의 누적 차이인 $n$-단계 후회(regret)를 최소화하는 것입니다.

UCB(Upper Confidence Bound)와 같은 낙관적 알고리즘은 선형 밴딧에 대해 $O(d\sqrt{n} \log n)$의 빈도주의적 후회 상한을 확립했지만, 톰슨 샘플링(Thompson sampling)과 같은 무작위 탐색 알고리즘은 이 환경에서 분석하기가 역사적으로 더 어려웠습니다. 무작위 방법론에 대한 이전의 빈도주의적 분석들은 종종 "강제된 낙관성(forced optimism)" 또는 "사후 분포 팽창(posterior inflation)"—즉, 높은 확률로 낙관성을 보장하기 위해 사후 분포의 분산을 인위적으로 키우는 방식—에 의존했습니다. 이러한 수정 방식은 일반적으로 $O((d \log n)^{3/2}\sqrt{n})$과 같이 낙관적 알고리즘에 비해 추가적인 $\sqrt{d}$ 인자를 도입하여 하위 최적(suboptimal)인 후회 상한을 초래했습니다. 더욱이, 최근의 하한(lower bounds) 연구(Hamidi and Bayati, 2023; Zhang, 2022)는 수정되지 않은 톰슨 샘플링이 특정 병리적인 설정에서 선형 후회(linear regret)를 유발할 수 있음을 입증하였으며, 이는 구조적 가정이 없다면 무작위 탐색이 보편적으로 최적은 아님을 시사합니다.

방법론 및 가정
저자들은 무작위 알고리즘을 수정하지 않는(즉, 강제된 낙관성이나 사후 분포 팽창을 사용하지 않는) 새로운 분석 프레임워크를 제안합니다. 대신, 이 분석은 행동 집합 $\mathcal{X}$의 구체적인 기하학적 성질에 의존합니다.

1. 알고리즘 프레임워크: 본 논문은 각 단계 $t$에서 파라미터 $\theta_t$가 $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$로 샘플링되는 무작위 알고리즘 클래스를 고려합니다. 여기서 $\hat{\theta}_{t-1}$은 정규화된 최소제곱 추정치이고, $V_{t-1}$은 디자인 행렬이며, $\eta_t$는 회전 불변 섭동(rotationally invariant perturbation)입니다. 행동은 $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$로 선택됩니다.
2. 섭동 가정: 섭동 $\eta_t$는 유계된 2차 및 4차 모멘트를 가진 독립적이고 회전 불변인 확률 변수(예: 가우시안 또는 구 위의 균등 분포)라고 가정됩니다.
3. 행동 집합 가정 (매끄러움 및 강볼록성): 핵심적인 이론적 기여는 가정 4.2에 기반하며, 이는 행동 집합 $\mathcal{X}$가 단위 구의 닫힌 흡수 부분 집합(closed, absorbing subset)이면서, 그 지지 함수(support function)의 제곱인 $J_{\mathcal{X}}^2$가 특정 노름 $\|\cdot\|_*$에 대해 $m$-강볼록(strongly convex)하고 $M$-매끄러움(smooth)을 만족할 것을 요구합니다.
   • 강볼록성(Strong Convexity): 지지 함수가 "평탄한(flat)" 영역을 갖지 않도록 보장하여, 파라미터 공간의 작은 변화가 의미 있는 행동 공간의 변화로 이어지게 합니다.
   • 매끄러움(Smoothness): 지지 함수의 그래디언트(파라미터를 행동으로 매핑하는 함수)가 립시츠 연속(Lipschitz)임을 보장하여, 작은 파라미터 섭동으로 인해 후회가 크게 급증하는 것을 방지합니다.
   • 예시: 이 클래스에는 $q \in (1, \infty)$인 재조정된 $\ell_q$-볼(ball)들이 포함됩니다.

주요 기여 및 분석
본 논문은 "불확실성에 직면한 낙관성(optimism in the face of uncertainty)" 프레임워크에 의존하지 않는 새로운 빈도주의적 후회 분석을 제공합니다. 대신, 탐색 과정의 역학(dynamics)과 신뢰 집합(confidence sets)의 진화를 직접 분석합니다.

• 후회 분해: 저자들은 기대 후회를 알고리즘이 "낙관적"인 단계(샘플링된 파라미터가 실제 최적값보다 높은 값을 갖는 단계)와 그렇지 않은 단계로 분해합니다.
• 비낙관적 탐색: 중요한 통찰은 샘플이 낙관적이지 않을 때조차도 여전히 신뢰 집합을 축소시키는 가치 있는 정보를 제공한다는 점입니다. 저자들은 단계별 후율을 브레그만 발산(Bregman divergence) 형식인 $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$로 기술하고, $J_{\mathcal{X}}^2$의 강볼록성과 매끄러움을 활용하여 이 발산을 제한합니다.
• 정보 성장: 본 증명은 기대 정보 획득량 $\mathbb{E}_{t-1}[X_t X_t^\top]$를 신뢰 타원체의 기하학적 구조와 연관시킴으로써 디자인 행렬 $V_t$의 성장에 대한 하한을 확립합니다. 이는 파라미터 공간의 "크기"(측정값 $V_t^{-1/2}$로 표현됨)를 실제 수행된 탐색과 연결합니다.
• 팽창 회피: 이전 연구들과 달리, 이 분석은 샘플링 분포의 분산을 팽창시킬 필요가 없습니다. 이는 알고리즘의 자연스러운 무작위성이 행동 공간의 기하학적 특성과 결합되어 탐색을 유도하고 후회를 제어하기에 충분함을 보여줍니다.

주요 결과
명시된 가정 하에, 저자들은 섭동 조건을 만족하는 모든 무작위 알고리즘이 다음의 빈도주의적 후회 상한을 달성함을 증명합니다:
$$R_n \lesssim O(d\sqrt{n} \log n)$$
구체적으로, 정리 4.1은 (로그 인자 $n$ 및 $\delta$를 제외하면) $O(d\sqrt{n} \log n)$ 차수의 상한을 제공합니다. 이는 로그 인자를 제외하면 알려진 선형 밴딧의 하한(Rusmevichientong and Tsitsiklis, 2010)과 일치합니다.

의의 및 주장
본 논문은 선형 밴딧에서 톰슨 샘플링의 차원 의존성(dimension dependence)에 관한 중요한 미해결 문제를 해결했다고 주장합니다.

• 최적의 차원 의존성: 구조화된 선형 밴딧 설정(특히 행동 공간이 매끄럽고 강볼록한 경우)에서 수정되지 않은(비팽창된) 톰슨 샘플링이 최적의 차원 의존성($O(d)$)을 달성할 수 있음을 최초로 입증했습니다.
• 성공 메커니즘: 본 연구는 왜 무작위 탐색이 이러한 설정에서 작동하는지를 밝힙니다. 즉, 파라미터 공간에서의 섭동이 인위적인 낙관성을 요구하지 않고도 효과적으로 행동 공간을 탐색할 수 있도록 하는 행동 집합의 기하학적 성질 때문입니다.
• 한계 및 범위: 저자들은 본 결과가 매끄럽지 않거나 흡수적이지 않은 행동 공간(예: "함정" 팔이 존재하는 경우)에서 톰슨 샘플링의 선형 후회를 보여주는 기존 하한과 모순되지 않음을 인정합니다. 이 방법의 성공은 행동 집합이 매끄러움 및 강볼록성 가정을 충족해야 한다는 조건에 달려 있습니다. 본 논문은 이러한 조건이 필수적이라고 주장하는 것이 아니라, 알고리즘 수정 없이 최적의 비율을 달기 위한 충분조건임을 밝히는 것입니다.

요약하자면, 본 논문은 광범위하고 잘 정의된 행동 집합( $\ell_q$-볼 포함)에 대해 무작위 탐색 알고리즘이 자연스럽게 최적의 후율을 달성함을 입증하며, 이전에 이론적 보장을 위해 필요하다고 여겨졌던 임의적인 분산 팽창 기법의 필요성을 제거했습니다.