Offline-to-Online Learning in Linear Bandits

기술 요약: 선형 밴딧에서의 오프라인-투-온라인 학습 (Offline-to-Online Learning in Linear Bandits)

문제 정의
본 논문은 확률적 선형 밴딧(stochastic linear bandit) 설정 내에서의 오프라인-투-온라인 학습 문제를 다룹니다. 이 시나리오에는 학습자가 시간 지평(horizon) $n$ 동안 누적 보상을 최대화하기 위해 집합 $\mathcal{A} \subset \mathbb{R}^d$에서 행동을 순차적으로 선택하는 상황이 포함됩니다. 이때 학습자는 기존의 오프라인 데이터셋 $\mathcal{D}$에 접근할 수 있습니다. 오프라인 데이터는 고정된 비적응형 설계(결정론적 행동 횟수)를 통해 수집되었으며, 서브가우시안 노이즈(subgaussian noise)를 따르는 선형 보상 모델을 따릅니다.

핵심 과제는 두 가지 상충하는 목표 사이의 트레이드오프에 있습니다:

1. 온라인 후회 (Online Regret, $R_n$): 최적의 행동 $\mu^*$에 대한 후회를 최소화하는 것입니다. 표준 온라인 알고리즘(예: LinUCB)은 탐색을 위해 낙관주의(optimism)에 의존하며, 아임리니어(sublinear)한 후회를 달성하지만 오프라인 데이터를 무시할 경우 초기에 높은 후회를 겪을 수 있습니다.
2. 오프라인 후회 (Offline Regret, $R_n^{off}$): 오프라인 데이터셋의 평균 보상($\mu_{off}$)에 대한 후회를 최소화하는 것입니다. 표준 오프라인 알고리즘(예: LinLCB)은 알려진 데이터를 활용하기 위해 비관주의(pessimism)에 의려하며, 이는 $\mu_{off}$에 근접한 성능을 보장하지만 탐색에 실패하여 오프라인 데이터가 차선이거나 시간 지평이 길 경우 선형적인 후회를 초래합니다.

기존 연구들은 주로 이러한 체제들을 별개로 다루거나, 후회가 행동의 수에 따라 스케일링되는 멀티 암드 밴딧(MAB)에 집중해 왔습니다. 본 논문은 후회가 행동 공간의 크기가 아닌 차원 $d$에 따라 스케일링되어야 하는 구조화된(선형) 환경에서 그 간극을 메우고자 합니다.

방법론: LinOtO 알고리즘
저자들은 **탐색 예산(exploration budget)**을 관리함으로써 탐색과 활용을 동적으로 균형 잡는 알고리즘인 LinOtO(Linear Offline-to-Online)를 제안합니다. 이 알고리즘은 오프라인 및 온라인 데이터로부터 구축된 신뢰 집합(confidence set) $C_t$를 기반으로 두 가지 전략 사이를 전환하며 작동합니다.

1. 신뢰 집합 (Confidence Sets): 알고리즘은 최소제곱 추정량 $\hat{\theta}_t$와 실제 파라미터 $\theta^*$ 주변의 신뢰 타원체 $C_t$를 유지합니다. 이 집합의 반지름은 오프라인 데이터($\beta_{off}$)와 온라인 상호작용($\beta_t$) 모두로부터 오는 불확실성을 포함합니다.
2. 낙관적 vs. 비관적 행동:
   • UCB 행동 ($U_t$): $C_t$ 내에서 상한 신뢰 경계(Upper Confidence Bound)를 최대화하는 행동입니다. 이는 탐색을 촉진하여 $R_n$을 줄이지만, $R_n^{off}$를 증가시킬 위험이 있습니다.
   • LCB 행동 ($L_t$): 하한 신뢰 경계(정확히는 시간에 따른 최소 신뢰 경계들의 최댓값)를 최대화하는 행동입니다. 이는 오프라인 데이터의 활용을 촉진하여 $R_n^{off}$를 줄이지만, 잠재적으로 $R_n$을 증가시킵니다.
3. 예산 메커니즘:
   • 알고리즘은 특정 "안전한" 행동 $L_{off}$(오프라인 데이터만으로 계산된 LCB 행동)의 보상 하한으로부터 유도된 안전 기저 보상(safe baseline reward) $r_b$를 정의합니다. 명제 2는 $L_{off}$가 높은 확률로 $\mu_{off}$에 근접함을 보장합니다.
   • 탐색 예산 $B(t)$는 알고리즘이 기저 보상 $r_b$ 대비 얻은 누적 초과 보상을 나타냅니다.
   • 의사 결정 규칙: 만약 $B(t) > 0$이면, 알고리즘은 낙관적 행동 $U_t$를 선택합니다(탐색). 만약 $B(t) \le 0$이면, 예산을 축적하기 위해 비관적 행동 $L_t$를 선택합니다(활용).
   • 이 메커니즘은 알고리즘이 오프라인 기저치에 비해 안전하게 유지됨으로써 탐색할 "권리"를 얻었을 때만 탐색하도록 보장합니다.

주요 기여

1. 알고리즘 설계: 본 논문은 예산 기반의 스위칭 메커니즘을 통해 UCB와 LCB 전략의 균형을 동시에 맞추는, 오프라인-투-온라인 선형 밴딧을 위해 특별히 설계된 최초의 알고리즘인 LinOtO를 제시합니다.
2. 이론적 보장: 저자들은 두 가지 지표 모두에 대해 고확률 후회 경계(high-probability regret bounds)를 확립했습니다:
   • 온라인 후회 ($R_n$): 정리 1은 LinOtO가 최적의 행동에 대해 아임리니어한 후회를 달성함을 보여줍니다. 이 경계는 시간 지평 $n$에 의존하는 항(LinUCB와 유사)과 오프라인 데이터 품질에 의존하는 가산 상수(additive constant)로 구성됩니다. 오프라인 데이터가 공간을 잘 커버한다면 경계가 개선됩니다.
   • 오프라인 후회 ($R_n^{off}$): 정리 2는 오프라인 참조값에 대한 후개가 $n$에 따라 선형적으로 스케일링되지만, 오프라인 샘플 수 $m$에 따라 $O(1/\sqrt{m})$으로 감소함을 입증합니다. 이는 순수 오프라인(비관적) 솔루션의 성능과 일치합니다.
3. 파레토 트레이드오프 분석: 분석 결과는 파라미터 $\alpha$에 의해 조절되는 튜닝 가능한 트레이드오프를 드러냅니다. $\alpha$를 높이면 온라인 성능(LinUCB에 근접)에 유리해지고, $\alpha$를 낮추면 오프라인 성능(LinLCB에 근접)에 유리해집니다.

실험 결과
합성 선형 밴딧 작업(차원 $d=20$, $|A|=100$)에 대한 경험적 평가를 통해 다음을 입증했습니다:

• 시간 지평 민감도: 짧은 시간 지평에서는 LinOtO가 보수적인 LinLCB 베이스라인을 추종합니다. 긴 시간 지평에서는 탐색으로 전환하여 LinUCB와 유사한 아임리니어한 후회를 달성합니다.
• 오프라인 데이터 품질:
  • 오프라인 데이터셋이 최적의 행동을 제외하는 경우, LinOtO는 오프라인 사전 정보를 벗어나 탐색을 시도함으로써 성공적으로 LinLCB(선형 후회 발생)를 능가하고, 오프라인 데이터 크기 $m$이 증가함에 따라 LinUCB의 성능에 근접합니다.
  • 오프라인 데이터셋에 최적의 행동이 포함된 경우, LinOtO는 빠르게 수렴하여 LinUCB 및 LinLCB와 대등한 성능을 보입니다.
• 강건성: 알고리즘은 순수 탐색(LinUCB)과 순수 활용(LinLCB)의 극단 사이에서 일관되게 작동하며 문제 파라미터에 적응합니다.

의의 및 주장
본 논문은 LinOtO가 구조화된 환경에서의 "잘 이해되지 않은" 오프라인-투-온라인 트레이드오프를 효과적으로 해결한다고 주장합니다. MAB 설정(예: Sentenac et al., 2025)과 달리, 이 접근 방식은 선형 구조를 활용하여 후개가 행동의 수가 아닌 차원 $d$에 따라 스케일링되도록 보장하며, 이를 통해 고차원 문제에 대한 확장성을 확보합니다.

저자들은 현재 프레임워크가 고정 설계 오프라인 데이터를 가정하며, 오프라인과 온라인 데이터 간의 분포 변화(distribution shifts)나 적응형 로깅 정책을 고려하지 않는다는 점을 겸허히 언급했습니다. 이러한 한계를 해결하고 비선형 설정으로 프레임워크를 확장하는 것이 중요한 향후 연구 방향임을 밝히고 있습니다. 본 연구는 온라인 학습에서 탐색-활용 트레이드오프를 가이드하기 위해 사전 지식(힌트, 오프라인 데이터)을 활용하는 광범 hơn 문헌에 기여합니다.