Stochastic Linear Bandits with Parameter Noise

기술적 요약: 매개변수 노이즈가 있는 확률적 선형 밴딧

문제 정의
본 연구는 매개변수 노이즈가 있는 확률적 선형 밴딧 모델을 조사합니다. 이 설정에서 학습자는 시간 범위 $T$ 동안 행동 집합 $\mathcal{A} \subseteq \mathbb{R}^d$ 에서 행동 $a_t$ 를 선택하여 환경과 상호작용합니다. 고정된 $\theta^\star$ 와 노이즈 $\eta_t$ 를 가진 reward 가 $X_t = a_t^\top \theta^\star + \eta_t$ 로 주어지는 표준적인 가법 노이즈 모델과 달리, 매개변수 노이즈 모델은 reward 가 $X_t = a_t^\top \theta_t$ 로 주어지며, 여기서 $\theta_t$ 는 평균 $\theta^\star$ 와 공분산 행렬 $\Sigma$ 를 갖는 고정된 미지의 분포 $\nu$ 에서 i.i.d.로 샘플링된다고 가정합니다.

이 논문은 매개변수 노이즈 모델에서 학습자가 reward 의 분산을 영향을 미칠 수 있다는 중요한 차이를 강조합니다. 구체적으로, $\text{Var}(X_t) = a_t^\top \Sigma a_t$ 인 반면, 가법 노이즈 모델에서는 분산이 환경에 의해 전적으로 결정됩니다. 저자들은 매개변수 노이즈 모델이 $\theta_t$ 를 적대자가 선택하는 적대적 선형 밴딧 모델의 완화 형태이지만, 특정 기하학적 설정에서 가법 노이즈 모델보다 잠재적으로 더 엄격한 후회 (regret) 상한을 허용하는 고유한 구조적 특성을 지닌다고 지적합니다.

방법론 및 알고리즘
저자들은 서로 다른 행동 집합 기하학에 맞춘 두 가지 알고리즘을 제안합니다:

1. VASE (분산 인지 최적 설계 연속 제거):

   • 대상: 일반적인 유한 행동 집합 (및 덮개 논의를 통한 무한 집합).
   • 메커니즘: 분산 정보를 활용하는 연속 제거 알고리즘입니다. 각 단계에서 G-최적 설계 $\pi_\ell$ 을 계산하여 행동을 선택합니다. 정지 규칙 알고리즘 (SR) 을 사용하여 설계의 지지 (support) 내 행동들의 분산을 명시적으로 추정합니다.
   • 주요 혁신: 이 알고리즘은 추정된 분산을 두 가지 방식으로 사용합니다: 탐색에 필요한 샘플 수를 줄이기 위해, 그리고 가중 최소제곱 추정기에서 가중치로 활용하기 위해입니다. 이 가중치는 샘플 수가 적더라도 추정기의 공분산이 제어되도록 보장하여 분산 의존적 후회 상한을 이끌어냅니다.

2. VALEE (분산 인지 선형 탐색 - 활용):

   • 대상: $p \in (1, 2]$ 인 $\ell_p$ 단위 구 (및 그 쌍대 노름 $q \ge 2$).
   • 메커니즘: 간단한 탐색 - 활용 알고리즘입니다.
     • 탐색: 알고리즘은 표준 기저 벡터 $e_i$ 를 플레이합니다. Median-of-Means (MoM) 기법을 사용하여 좌표별로 평균 벡터 $\theta^\star$ 를 추정합니다. 공분산 행렬 $\Sigma$ 를 알 수 없는 경우, 먼저 기저 벡터들의 분산을 추정합니다.
     • 활용: 추정 오차가 분산 및 시간 범위에 비해 충분히 작아지면, 알고리즘은 추정된 평균 $\hat{\theta}$ 에서 유도된 행동 $\hat{a}$ 에 전념합니다. 구체적으로 $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$ 입니다.
   • 주요 혁신: 분석은 $\ell_p$ 구의 기하학과 매개변수 노이즈 구조를 활용합니다. 저자들은 기저 벡터를 탐색하는 것이 가법 노이즈 모델의 표준 $\epsilon$ 경계보다 더 엄격한 $\sqrt{\sigma^2(e_i)}$ 에 비례하는 추정 오차를 산출함을 보여줍니다. 이를 통해 알고리즘은 reward 분포의 분산 구조에 의존하는 최적의 후회 상한을 달성할 수 있습니다.

주요 결과
본 논문은 상한과 하한을 모두 수립하여 제안된 알고리즘이 특정 설정에서 (로그 인자까지) 최소 - 최대 최적 (minimax optimal) 임을 입증합니다.

• 일반 유한 행동 집합 ($K$ 개 행동):

  • 상한: VASE 는 $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$ 의 후회를 달성하며, 여기서 $M_\sigma$ 는 $\max_a \sigma^2(a)$ 로 제한된 분산 의존량입니다.
  • 하한: $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ 의 하한이 증명되었으며, $\log(K) \approx d$ 일 때 상한이 로그 인자까지 엄격함을 보여줍니다.

• $\ell_p$ 단위 구 ($p \le 2$):

  • 알려진 공분산: VALEE 는 $\tilde{O}(d + \sqrt{dT \sigma^2_q})$ 의 후회를 달성하며, 여기서 $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$ 입니다. 이는 $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$ 의 일치하는 하한을 통해 최적임이 입증되었습니다.
  • 알려지지 않은 공분산: VALEE 는 추가적인 가법 항을 수반하여 $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$ 의 후회를 초래합니다. 저자들은 이 가법 항이 분산 추정 단계에서 비롯된다고 지적합니다.

• $\ell_p$ 단위 구 ($p > 2$):

  • 논문은 $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ 의 하한을 제공하며, 이는 이러한 기하학에서 알려진 적대적 설정의 하한과 일치합니다.

의의 및 주장
이 논문은 $\ell_2$ 단위 구와 같은 특정 행동 집합에 대해 가법 노이즈 모델이 종종 적대적 모델 ($\sqrt{dT}$) 보다 더 나쁜 후회 상한 ($d\sqrt{T}$) 을 산출하는 "호기심 어린 사례"를 해결했다고 주장합니다. 저자들은 매개변수 노이즈 모델이 확률적 모델이 적대적 모델보다 쉬워야 한다는 직관과 더 잘 부합함을 입증합니다.

• 엄격한 경계: $p \le 2$ 인 $\ell_p$ 구의 경우, 매개변수 노이즈 모델은 $\sqrt{dT \sigma^2_q}$ 차수의 후회 상한을 허용하며, 분산이 작을 때 가법 노이즈 모델의 전형적인 $d\sqrt{T}$ 경계보다 훨씬 작을 수 있습니다.
• 구조적 이점: 결과들은 기대값뿐만 아니라 *실현 (realization)*의 선형성과 학습자가 분산에 영향을 미칠 수 있는 능력이 이러한 개선된 상한을 달성하는 데 중요함을 강조합니다.
• 간단함: 놀랍게도 $p \le 2$ 인 $\ell_p$ 구에 대한 최적 후회는 매우 간단한 탐색 - 활용 알고리즘 (VALEE) 을 사용하여 달성 가능하며, 이는 종종 가법 노이즈 설정에서 필요한 복잡한 최적 설계 알고리즘과 대조됩니다.

저자들은 $p \le 2$ 에 대한 결과가 공분산이 알려진 경우 (로그 인자까지) 최적임을 결론지으며, 알려지지 않은 공분산 사례는 미래 연구가 해결할 수 있는 $T^{1/3}$ 항과 같은 열린 간극을 남긴다고 말합니다. 또한 $p > 2$ 에 대한 하한을 만족하는 알고리즘 설계는 열린 과제로 남깁니다.