An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

기술 요약: 환원을 통한 개선된 적대적 선형 컨텍스추얼 밴딧 알고리즘

문제 정의

본 논문은 적대적 선형 컨텍스추얼 밴딧(adversarial linear contextual bandit) 문제를 다룬다. 이 설정에서 무관심한 적대자(oblivious adversary)는 상호작용이 시작되기 전에 숨겨진 손실 벡터 $\theta_t \in \mathbb{R}^d$의 시퀀스를 선택한다. 각 라운드 $t$에서 액션 집합 $A_t \subset \mathbb{R}^d$는 고정되어 있으나 알려지지 않은 분포 $\mathcal{D}$로부터 i.i.d.로 추출되어 학습자에게 공개된다. 학습자는 액션 $a_t \in A_t$를 선택해야 하며, 기대 손실 $\mathbb{E}[\ell_t] = a_t^\top \theta_t$를 입는다. 목표는 최적의 고정 정책 $\pi$에 대한 후회(regret)를 최소화하는 것이다. 여기서 정책 $\pi$는 임의의 관찰된 액션 집합 $A$에 대해 그 볼록 껍질(convex hull) $\text{conv}(A)$ 내의 한 점을 매핑한다.

이 설정은 액션 집합(컨텍스트)이 시간에 따라 확률적으로 변할 수 있도록 함으로써 고전적인 선형 밴딧을 일반화하며, 동시에 손실은 적대적이다. 결정적인 과제는 분포 $\mathcal{D}$를 알 수 없으며, 학습자가 $\mathcal{D}$로부터 자유롭게 샘플을 생성할 수 있는 시뮬레이터에 접근할 수 없다는 점이다. 또한, 가능한 액션의 수 $K$가 차원 $d$에 대해 지수적으로 클 수 있어(예: 최단 경로와 같은 조합론적 문제), $K$에 대한 다항식 복잡도를 갖는 알고리즘은 실행 불가능하다.

방법론

핵심 기여는 적대적 선형 컨텍스추얼 밴딧 문제를 고정된 액션 집합을 가진 미스스펙리피케이션 강건(misspecification-robust) 적대적 선형 밴딧 문제로 변환하는 **계산 효율적인 환원(reduction)**이다.

1. 고정 액션 집합으로의 환원:
   저자들은 정책 $\pi$를 그 평균 액션으로 매핑하는 함수 $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$를 정의한다. $\mathcal{D}$는 알려져 있지 않으므로, 실제 평균 액션의 집합 $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$에 직접 접근할 수 없다. 대신, 알고리즘은 $\mathcal{D}$에서 추출된 $N$개의 i.i.d. 액션 집합 샘플을 사용하여 경험적 근사치 $\hat{\Omega}$를 구축한다.

   • $\hat{\Omega}$는 샘플링된 액션 집합들의 볼록 껍질의 민코프스키 합(Minkowski sum)으로 정의된다: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • 이 환원은 선형 분류기 정책(linear classifier policies)의 경우, 실제 분포에서의 기대 손실과 경험적 분포에서의 기대 손실 사이의 차이가 충분히 큰 $N$에 대해 작다(균등 수렴)는 사실에 기반한다.

2. 불일치를 통한 미스스펙리피케이션 대응:
   학습자는 $\Omega$가 아닌 $\hat{\Omega}$ 상에서 작동하므로, 하위 선형 밴딧 알고리즘이 받는 피드백은 "미스스펙리피케이션(misspecified)" 상태가 된다. 구체적으로, 선형 밴딧 알고리즘이 관찰하는 기대 손실은 실제 기대 손실과 유계된 오차 항 $\epsilon$만큼 차이가 난다.

   • 저자들은 블랙박스로서 $\alpha$-미스스펙리피케이션 강건 적대적 선형 밴딧 알고리즘을 활용한다. 이 알고리즘은 피드백이 $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$를 만족할 때도 낮은 후회를 보장한다.
   • 선형 밴딧 알고리즘이 제안한 점 $y_t \in \hat{\Omega}$를 실행하기 위해, 학습자는 Frank-Wolfe 기반 분해(알고리즘 2)를 사용하여 $y_t$를 $\hat{\Omega}$ 경계 위의 점들의 볼록 결합으로 표현한다. 이 경계 점들은 선형 분류기 정책 $\pi_\phi$에 대응하며, 이는 개별 액션 집합 $A_t$에 대한 **선형 최적화 오라클(linear optimization oracle)**을 사용하여 실행될 수 있다.

3. 알고리즘 구성 요소:

   • 알고리즘 1: 환경과 상호작로는 하며, 선형 밴딧의 제안을 선형 정책들의 혼합으로 분해하고, 결과로 나온 손실을 선형 밴딧 알고리즘에 다시 전달하는 메인 프레임워크이다.
   • 알고리즘 3 (미스스펙리피케이션 강건 연속 지수 가중치): 강건한 선형 밴딧 알고리즘의 특정 구현체이다. 이는 절단된 연속 지수 가중치(clipped continuous exponential weights) 방법(Ito et al., 2020)에 "보너스 항" $b_t$를 추가하여 변형한 것으로, 이 보너스는 탐색을 장려하고 미스스펙리피케이션으로 인한 후회 오버헤드를 상쇄한다.
   • 더블링 트릭(Doubling Trick): 알려지지 않은 최적 샘플 크기 $N$을 처리하기 위해, 알고리즘은 $2, 4, 8, \dots$ 에폭마다 프로세스를 재시작하고 축적된 모든 컨텍스트 샘플을 사용하여 $\hat{\Omega}$를 정교화하는 더블링 트릭을 사용한다.

주요 기여

• 오라클 효율적 알고리즘: 본 논문은 계산 복잡도 측면에서 액션의 수 $K$와 독립적인 후회 경계를 달이는, 확률적 액션 집합을 가진 적대적 선형 컨텍스추얼 밴딧에 대한 최초의 알고리즘을 제시한다. 이 알고리즘은 각 라운드의 개별 액션 집합에 대한 선형 최적화 오라클만을 필요로 한다.
• 조합론적 적용 가능성: 이 방법은 확률적 액션 집합과 적대적 손실을 가진 조합론적 밴딧에 대해 다항 시간 내에 $\text{poly}(d)\sqrt{T}$ 후회를 달성하는 최초의 방법이다. 기존 알고리즘들은 세미-밴딧(semi-bandit) 피드백을 요구하거나, $d$에 대해 지수인 $K$에 다항식적으로 스케일링되는 계산 복잡도를 가졌다.
• 새로운 환원: 본 연구는 적대적 선형 컨텍스추얼 밴딧을 미스스펙리피케이션 강건 선형 밴딧으로 연결하는 다항 시간 환원을 확립한다. 확률적 설정에 집중하거나 다항 시간 구현이 부족했던 이전의 환원들(예: Hanna et al., 2023)과 달리, 이 환원은 적대적 손실 하에서도 작동하며 계산적으로 효율적이다.

결과

알고리즘은 다음과 같은 후회 경계(로그 인자 제외)를 달성한다:

• 시뮬레이터가 없는 경우: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • 이는 $K$와 무관하게 $\text{poly}(d)\sqrt{T}$ 후제를 다항 시간 내에 달성할 수 있는지에 대한 Liu et al. (2023)의 열린 질문을 해결한다.
  • 계산 복잡도는 $\text{poly}(d, T)$와 $\text{poly}(d, T)$번의 선형 최적화 오라클 호출로 구성된다.
• 시뮬레이터가 있는 경우: 학습자가 자유로운 컨텍스트를 생성할 수 있는 시뮬터에 접근할 수 있다면, 후회 경계는 $\tilde{O}(d\sqrt{L^*})$로 개선된다. 여기서 $L^*$는 최적 정책의 누적 손실이다. 이는 문제 인스턴스의 난이도에 적응하는 1차 경계이다.

의의 및 주장

저자들은 본 연구가 컨텍스트 분포에 대한 지식이나 시뮬레이터 없이도 지수적으로 큰 액션 공간(예: 최단 경로, 흐름, 이분 매칭)을 가진 적대적 선형 컨텍스추얼 밴딧의 적용 범위를 크게 넓히는 일반적인 프레임워크를 제공한다고 주장한다.

논문은 $\tilde{O}(d^2\sqrt{T})$ 경계가 $K$에 의존하는 이전의 다항 시간 결과들보다 개선되었지만, 시뮬레이터 없이 근사 최적치인 $\tilde{O}(d\sqrt{T})$ 경계를 달로 달성할 수 있는지 여부는 여전히 미해결 과제로 남아 있음을 명시한다. 또한, 저자들은 특정 공식화로 특화될 때 일부 선행 연구(Olkhovskaya et al., 2023)에서 요구되었던 로그-오목(log-concave) 컨텍스트 분포라는 비현실적인 가정을 제거했음을 강조한다. 마지막으로, 이 환원 프레임워크가 고정된 전이(transition)와 적대적 손실을 가진 선형 MDP와 같은 다른 설정에도 적용될 수 있음을 시사한다.