기술 요약: 적대적 오염이 존재하는 이종 분산 일반화 선형 밴딧을 위한 공동 효율적 및 최적 알고리즘

1. 문제 설정

본 논문은 **적대적 오염(adversarial corruptions)**이 존재하는 상황에서의 이종 분산 일반화 선형 밴딧(Heteroskedastic Generalized Linear Bandits, GLBs) 문제를 다룹니다. 이 설정은 세 가지 도전적인 측면을 통합합니다:

1. 일반화 선형 모델 (GLMs): 팔(arm) $x_t \in \mathbb{R}^d$에 대한 기대 보상은 GLM, 즉 $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$를 따릅니다. 여기서 $\mu$는 알려진 역 링크 함수(inverse link function)이고 $\theta^\star$는 미지의 파라미터입니다. 이 프레임워크는 로지스틱, 포아송, 가우시안 선형 밴딧을 모두 포함합니다.
2. 이종 분산 (Heteroskedasticity): 보상 분산은 일정하지 않으며 팔과 타임스텝에 따라 변합니다. 구체적으로, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$이며, 여기서 $g(\tau_t)$는 외생적으로 시간에 따라 변하거나(예: 가우시안 밴딧) 내생적으로 팔 선택에 의해 결정될 수 있는(예: 로지스틱/포아송 밴딧) 분산 파라미터입니다.
3. 적대적 오염 (Adversarial Corruptions): 적응형 적대자(adaptive adversary)가 각 단계 $t$에서 관측된 보상에 오염 $c_t$를 더함으로써 관측값을 조작합니다. 즉, 학습자는 $\tilde{r}_t = r_t + c_t$를 관찰하게 됩니다. 적대자는 총 예산 제약 조건 $\sum_{t=1}^T |c_t| \le C$ 하에서 작동합니다.

목표는 $T$ 라운드 동안 최적의 팔의 기대 보상과 선택된 팔의 보상 차이인 누적 의사 후회(cumulative pseudo-regret)를 최소화하는 것입니다.

2. 방법론: HCW-GLB-OMD

저자들은 HCW-GLB-OMD(Hessian-Confidence Weighted GLB-OMD)를 제안합니다. 이 알고리즘은 계산 효율성과 통계적 최적성을 모두 갖추도록 설계되었습니다. 이 알고리즘은 두 가지 주요 구성 요소를 통합합니다:

A. 온라인 OMD 추정기 (Online OMD Estimator)

로컬 가중치와 글로벌 추정치 사이의 시간 인덱스 불일치를 유발하는 기존의 배치 최대 가능도 추정(MLE) 방식과 달리, HCW-GLB-OMD는 온라인 OMD 추정기를 사용합니다. 단계 $t$에서의 파라미터 업데이트는 다음과 같이 정의됩니다:
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
여기서 $\tilde{\ell}_t$는 가중치가 적용된 음의 로그 가능도(negative log-likelihood)입니다. 이러한 온라인 접근 방식은 추정기, 팔, 그리고 가중치가 동일한 로컬 타임 스텝에 정렬되도록 보장하여, 오염의 영향을 엄밀하게 분석할 수 있게 합니다.

B. 헤시안 기반 신뢰 가중치 (Hessian-Based Confidence Weights)

오염에 대한 강건성을 확보하기 위해, 알고리즘은 링크 함수의 로컬 헤시안(곡률)과 분산 파라미터를 기반으로 각 관측치에 신뢰 가중치 $w_t$를 할당합니다:
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
여기서 $\|x_t\|_{H_t^{-1}}$는 $x_t$ 방향에 따른 불확실성을 정량화합니다.

• 메커니즘: 만약 팔의 방향이 분산에 비해 매우 불확실하다면(역 헤시안에서의 노름이 크다면), 가중치 $w_t$는 감소합니다($<1$). 이는 적대적 조작에 취약한 방향으로부터 오는 관측치의 가중치를 낮추는 역할을 합니다.
• 곡률 인식 (Curvature Awareness): 디자인 행렬을 사용하는 선형 밴딧 방법과 달리, 이 방법은 로컬 기울기 $\dot{\mu}$를 포함하는 헤시안 $\nabla^2 \tilde{\ell}_t$를 사용합니다. 이를 통해 알고리즘이 GLM의 특정 기하학적 구조(예: 로지스틱 밴딧의 포화 상태)에 적응할 수 있게 합니다.

C. 오염 강건 신뢰 시퀀스 (Corruption-Robust Confidence Sequences)

저자들은 추정 오차와 적대적 오염을 모두 고려하는 신뢰 집합 $C_t(\delta)$를 구축합니다. 이 집합의 반지름에는 오염 예산 $C$에 비례하는 가산 항이 포함됩니다:
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
이 시퀀스의 증명은 가중치가 적용된 로그 가능도 비율에 적용된 슈퍼마팅게일(supermartingale) 논법에 기초하며, $w_t < 1$인 경우를 처리하기 위해 매핑 $x \mapsto x^{w_t}$의 오목성(concavity)을 활용합니다.

3. 주요 기여 및 결과

A. 후회 상한 (Regret Upper Bound)

저자들은 링크 함수 $\mu$가 **자기 수렴적(self-concordant)**이라는 가정(Assumption 3) 하에 HCW-GLB-OMD의 후회 상한을 도출합니다. 확률 적어도 $1-\delta$로, 후회는 다음과 같이 제한됩니다:
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
여기서:

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$는 최적의 팔에서의 링크 함수 기울기입니다.
• $g_{\max} = \max_t g(\tau_t)$는 최대 분산입니다.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$는 곡률 파라미터입니다.
• $C$는 총 오염 예산입니다.

상한의 의의:

• 인스턴스별 최적성 (Instance-Wise Optimality): 선행 항 $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$은 최악의 경우의 곡률 $\kappa$가 아닌, 실제 최적의 팔에서의 기울기에 의존합니다. 이는 오염이 없는 GLB에 대한 미니맥스 하한과 일치합니다.
• 오염 강건성: 오염 항은 $C$에 선형적으로 비례하며(구체적으로 $d(g_{\max} + \kappa)C$), 이는 곡률 인자 $\kappa$를 제외하면 미니맥스 최적입니다.
• 통합: 이 상한은 이종 분산 선형 밴딧, 로지스틱 밴딧, 포아송 밴딧에 대한 최첨단 결과들을 동시에 회복합니다.

B. 통합 후회 하한 (Unified Regret Lower Bound)

저자들은 적대적 오염이 존재하는 모든 자기 수렴적 이종 분산 GLB에 대한 통합 하한을 증명합니다:
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
이 하한은 다음을 포함합니다:

• 기존의 문제별 하한들(로지스틱 밴딧, 이종 분산 선형 밴딧, 오염된 선형 밴딧)을 포괄합니다.
• 알고리즘의 선행 항이 인스턴스별 미니맥스 최적임을 확인시켜 줍니다.
• 오염 항 $dC$가 피할 수 없는 것임을 보여주지만, 현재 상한에는 오염 항에 추가적인$\kappa$인자($d\kappa C$)가 포함되어 있습니다.

C. 계산 효율성

이 알고리즘의 핵심적인 기여는 효율성입니다. 온라인 OMD 업데이트와 재귀적 헤시안 업데이트를 사용함으로써, HCW-GLB-OMD는 반복당 $O(1)$의 공간 및 시간 복잡도를 달s합니다. 이는 배치 처리나 복잡한 신뢰 집합 구축으로 인해 종종 $O(t)$의 복잡도를 요구하는 기존의 GLM용 오염 강건 알고리즘(예: CR-Eluder-UCB, GAdaOFUL)과 대조됩니다.

4. 의의 및 주장

본 논문은 적대적 오염 하의 이종 분산 GLB를 위한 최초의 공동 효율적 및 최적 알고리즘을 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

1. 격차 해소: 오염된 GLB에서 계산 효율성과 통계적 최적성 사이의 트레이드오프를 해결합니다. 기존 연구들은 최적성을 달 Achieve 하려면 높은 계산 비용이 필요하거나, 효율성을 달성하더라도 최적에 못 미치는 후회 상한(종종 최악의 경우 곡률 $\kappa$에 비례함)을 가졌습니다.
2. 인스턴스별 최적성: 알고리즘은 오염이 존재하는 상황에서도 최악의 가정(곡률 $\kappa$)에 의존하지 않고, 인스턴스의 특성($\dot{\mu}_{t,\star}$)에 적응하는 후회 상한을 달성합니다.
3. 통합 프레임워크: 문제별 알고리즘 수정 없이 광범한 범위의 밴딧 문제(선형, 로지스틱, 포아송, 이종 분산)를 아우르는 단일 이론적 프레임워크를 제공합니다.

저자들은 남은 과제를 언급합니다: 상한의 오염 항은 $d\kappa C$로 스케일링되는 반-면, 하한은 $dC$입니다. 저자들은$\kappa$인자가 분석 과정에서 발생한 부산물일 것이라고 추측하며,$O(dC)$상한이 가능할 것이라고 보지만 이는 여전히 미해결 과제로 남아 있습니다. 또한, 현재 분석은 분산 파라미터$\tau_t$를 학습자가 알고 있다고 가정하며, 모르는$\tau_t$를 다루는 것을 향후 연구 방향으로 제시했습니다.