Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

문제 정의
본 논문은 플레이어가 누적 보상을 최대화하기 위해 행동 $A_t \in \mathcal{A} \subset \mathbb{R}^d$를 선택하는 순차적 의사결정 환경인 선형-가우시안 밴딧(linear-Gaussian bandit) 문제를 다룹다. 시간 $t$에서의 보상은 $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$로 생성되며, 여기서 $\theta_\star$는 미지의 파라미터 벡터이고 $W_{t+1}$은 분산이 $\sigma^2$인 독립 항등 분포(i.i.d.) 가우시안 노이즈이다. 목적은 사전 분포 $\rho$에 대한 $\theta_\star$의 분포를 가정할 때, 호라이즌 $T$ 동안 최적의 행동과 선택된 행동 사이의 기대 차이인 베이지안 후회(Bayesian regret)를 최소화하는 것이다. 구체적으로 저자들은 $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$이고 행동 집합이 반지름 $r$인 스케일링된 $\ell_2$-볼(ball)인 경우에 집중한다.

방법론
저자들은 톰슨 샘플링(Thompson sampling)을 분석한다. 이는 과거 이력 $H_t$가 주어졌을 때 사후 분포로부터 파라미터 추정치 $\hat{\theta}_t$를 추출하고, $\hat{\theta}_t$ 하에서의 기대 보상을 최대화하는 행동을 선택하는 사후 샘플링 알고리즘이다.

후회 상한(regret bounds)을 도출하기 위해, 저자들은 순간 후회를 두 가지 항으로 분해한다:

1. 항 (I): 샘플링된 파라미터 $\hat{\theta}_t$가 실제 파라미터 $\theta_\star$와 가까울 때(사후 정밀도 행렬에 의해 정의된 고확률 이벤트 내에 있을 때) 발생하는 후회.
2. 항 (II): 샘플링된 파라미터가 실제 파라미터와 멀 때 발생하는 후회.

핵심적인 기술적 혁신은 항 (I)의 분석에 있다. 저자들은 일반화된 타원형 포텐셜 렐마(generalized elliptical potential lemma) (Lemma 3)를 도입한다. 초기 정밀도 행렬이 0에서 떨어져 있어야 함을(예: $V_0 \succeq I$) 요구하거나 이차 오차를 바운드하는 일반적인 선형 밴딧 문헌(예: Abeille & Lazaric, 2017; Dani et al., 2008)의 타원형 포텐셜 렐마와 달리, 이 새로운 렐마는 다음과 같은 특징을 갖는다:

• 초기 정밀도 행렬 $V_0$가 임의로 작거나(또는 극한에서 0이 되더라도) 허용하여, 확산된 사전 분포(diffuse priors)를 수용한다.
• 노름(norm)의 합산에 유연한 지수 $p \in [0, 1]$를 도입한다.
• 바운드를 로그 결정식 항(장기적인 정보 획득을 포착)과 초기 정밀도 행렬을 포함하는 트레이스(trace) 항(초기 "번인(burn-in)" 비용을 포착)으로 명시적으로 분리한다.

항 (II)의 분석은 가우시안 분포에 대한 표준 집중 부등식(concentration inequalities)을 사용하여 $\hat{\theta}_t$와 $\theta_\star$ 사이의 큰 편차가 발생할 확률을 바운드하는 것에 의존한다.

주요 기여 및 결과
주된 기여는 사전 분포에 의존하는 "번인" 항을 미니맥스 후회율(minimax regret rate)에서 분리해낸 선형-가우시안 설정에서의 톰슨 샘플링에 대한 새로운 베이지안 후회 상한이다.

1. 개선된 후회 상한: 저자들은 톰슨 샘플링이 다음과 같은 후회를 달성함을 증명한다:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   여기서 $\sigma d \sqrt{T}$는 점근적 미니맥스율을 나타내며, $d r \sqrt{\text{Tr}(\Sigma_0)}$는 불확실성을 노이즈 스케일로 줄이는 데 드는 초기 비용을 나타낸다.

2. 항의 분리: 이전의 상한들(예: Kalkanli & Özgür, 2020)은 $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$와 같이 곱셈적 의존성을 보였으며, 이는 사전 분포의 확산 정도인 $\sqrt{\text{Tr}(\Sigma_0)}$가 전체 미니맥스율을 스케일링했다. 새로운 결과는 로그 인자를 제외하면, 사전 분포의 확산도가 시간 호라이즌 $T$와 무관하게 후회에 가산적(additive)인 상수로만 더해진다는 것을 보여준다.

3. 하한(Lower Bounds): 본 논문은 이 설정에 대한 모든 정책에 대한 하한을 설정하여, 가우시안 사전 분포에 대해 번인 항 $d r \sqrt{\text{Tr}(\Sigma_0)}$가 피할 수 없음을 입증한다. 이는 가산적 구조의 상한이 (로그 인자를 제외하면) 타이트하며, 사전 분포의 확산도를 완전히 제거할 수 없음을 확인시켜 준다.

4. 일반화: 저자들은 자신들의 결과가 가우시안 케이스에 국한되지 않고, 강한 로그-오목(strongly log-concave) 사전 분포 및 노이즈 분포로 확장될 수 있음을 언급한다.

의의
본 논문은 자신의 결과가 톰슨 샘플링에 존재하는 기존 후회 상한의 느슨함을 해결한다고 주장한다. 사전 분포에 의존하는 항이 곱셈적이 아니라 가산적임을 증명함으로써, 본 연구는 사전 확산도의 역할을 명확히 한다. 즉, 사전 확산도는 불확실성을 관측 노이즈 수준으로 줄이는 데 필요한 일회성 "번인" 비용으로 작용하며, 그 이후 알고리즘의 성능은 오직 노이즈 분산 $\sigma$와 차원 $d$에 의해 결정된다. 이는 특히 사전 분포가 매우 확산된(큰 $\text{Tr}(\Sigma_0)$를 가진) 영역에서 알고리즘의 효율성을 더욱 정밀하게 규명하며, 이러한 확산도가 점근적 수렴율을 영구적으로 저하시키지 않음을 보여준다. 도입된 일반화된 타원형 포텐셜 렐마는 초기 불확실성이 무한할 수 있는 확률적 최적화 문제를 보다 유연하게 분석할 수 있게 하는 도구로 제시된다.