기술 요약: 비정상적 컨텍스트ual 밴딧을 위한 흐름 교정 톰슨 샘플링 (Flow-Corrected Thompson Sampling)

문제 정의

본 논문은 컨텍스트와 행동, 그리고 보상 사이의 관계가 시간에 따라 진화하는 설정인 비정상적 선형 컨텍스트ual 밴딧(non-stationary linear contextual bandits) 문제를 다룹로다. 고전적인 컨텍스트ual 밴딧에서는 파라미터 벡터 $w_t$가 정적(stationary)이라고 가정합니다. 그러나 실제 응용 분야(예: 추천 시스템, 동적 가격 책정, 금융)에서는 사용자 선호도와 시장 조건이 변동하므로, 과거 데이터를 단순히 사용하면 체계적인 편향(bias)이 발생할 수 있습니다.

핵심적인 어려움은 과거 데이터를 유지하여 사후 분산을 줄이는 것과, 오래된 데이터를 버림으로써 구식 모델로부터 발생하는 편향을 피하는 것 사이의 트레이드오프에 있습니다. 슬라이딩 윈도우, 지수적 할인(exponential discounting), 주기적 재시작과 같은 기존 방식들은 과거 데이터를 단순히 일률적으로 버리거나 가중치를 낮추어 관리해야 할 부채로 취급합니다. 저자들은 비정상성이 예측 가능한 구조(예: 점진적 표류, 주기성 또는 반복되는 레짐)를 가질 때, 과거의 관측치가 적절히 교정된다면 유용한 정보를 담고 있다고 주장합니다.

방법론: 흐름 교정 톰슨 샘플링 (FC-TS)

저자들은 과거의 관측치를 사후 분포에 통합하기 전 "현재 시점의 의사 관측치(present-time pseudo-observations)"로 변환하는 베이지안 프레임워크인 **흐름 교정 톰슨 샘플링(FC-TS)**을 제안합니다. 이 방법은 비정상성 처리를 **전송 연산자(transport operator)**와 **신뢰도 가중치 규칙(confidence weighting rule)**이라는 두 가지 별개의 구성 요소로 분리합니다.

1. 핵심 메커니즘

매 라운드 $t$마다, 모든 과거 관측치 $(x_s, a_s, r_s)$에 대해 FC-TS는 다음과 같이 전송된 보상(transported reward) $\hat{r}_{s \to t}$를 구축합니다:
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
여기서 $\hat{\Delta}_{s \to t}$는 시간 $s$에서 $t$까지의 평균 보상 변화량을 추정합니다. 이는 과거의 보상을 현재의 보상 모델에 맞게 정렬하도록 효과적으로 "흐르게(flow)" 만듭니다.

부정확한 드리프트 추정치로 인한 노이즈를 방지하기 위해, 각 전송된 관측치에는 $[0, 1]$ 범위의 신뢰도 가중치 $\omega_{s,t}$가 할당됩니다. 이 가중치는 교정이 불확실할 경우 해당 관측치의 유효 노이즈 분산을 팽창시켜, 사후 분포에 미치는 영향력을 조절합니다.

행동 $a$에 대한 사후 분포는 다음과 같이 가중치가 부여되고 전송된 관측치들을 사용하여 업데이트됩니다:
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
행동 선택은 가우시안 사후 분포 $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$를 사용하는 표준 톰슨 샘플링을 통해 진행됩니다.

2. 구조화된 구체화 사례 (Structured Instantiations)

이 프레임워크는 세 가지 흔한 비정상 패턴에 대해 구체적인 구현을 제공하는 통합 템플릿을 제공합니다:

• 선형 표류 (Linear Drift): 파라미터가 $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$로 진화한다고 가정합니다. 전송 연산자는 온라인 리지 회귀 추정치 $\hat{\delta}_t^{(a)}$를 사용하여 보상을 이동시킵니다: $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. 가중치는 외삽(extrapolation) 불확실성을 고려하여 지수적으로 감소합니다 ($\omega_{s,t} = \gamma^{t-s}$).
• 주기적 변동 (Periodic Variation): 파라미터가 주기 $P$에 따라 반복된다고 가정합니다. 전송 연산자는 동일한 위상(phase)에 있는 관측치에 대해 항등 연산자($\hat{r}_{s \to t} = r_s$)를 사용합니다. 가중치는 위상 간의 원형 거리(circular distance)에 의해 결정되며, 이를 통해 알고리즘이 이전 사이클의 데이터를 재사용할 수 있게 합니다 ($\omega_{s,t}$는 위상 근접성에 의존).
• 반복되는 레짐 (Recurring Regimes): 환경이 유한한 수의 레짐 사이를 전환하는 경우를 다룹니다. 알고리즘은 레짐별 사후 분포 뱅크를 유지합니다. 변화점(CUSUM을 통한 예측 잔차 기반)이 감지되면, 처음부터 다시 시작하는 대신 재발생하는 레짐의 사후 분포를 다시 로드합니다.

이 프레임워크는 또한 각각의 전송 및 가중치 규칙을 결합하여 선형 표류와 주기성을 동시에 처리할 수 있는 **조합(composition)**을 지원합니다.

주요 기여

1. 흐름 교정 사후 분포 업데이트: 본 논문은 과거 보상을 현재 시점의 의사 관측치로 교정하여 가중치가 부여된 베이지안 업데이트를 통해 통합하는, 단순한 데이터 폐기가 아닌 전송 기반의 비정상성 관점을 도입했습니다.
2. 모듈형 알고리즘 설계: FC-TS는 범용적인 전송 연산자와 가중치 규칙으로 정의되며, 선형 표류, 주기적 변동, 반복되는 레짐을 위해 구체화되었습니다. 여기에는 트렌드와 다중 주기성을 결합한 적응형 변형도 포함됩니다.
3. 경험적 검증: 다섯 가지 케이스 스터디(선형 표류, 주기적 변동, 반복되는 레짐, 복합 비정상성, 반합성 포트폴리오 선택)에 대한 광범위한 평가를 통해 FC-TS가 기존의 망각 기반 베이스라인들을 능가함을 입증했습니다.

실험 결과

저자들은 FC-TS를 네 가지 베이스라인인 Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS), Restarting TS (R-TS)와 비교 평가했습니다.

• 성능 향상: FC-TS는 모든 다섯 가지 설정에서 가장 낮은 누적 후회(cumulative regret)를 달 기록했으며, 각 특정 환경의 가장 강력한 베이스라인 대비 **14.1%에서 59.0%**까지 개선된 성능을 보였습니다.

• 사례별 통찰:

  • 선형 표류: FC-TS는 웜업 단계 동안 SW-TS와 유사한 성능을 보였으나, 드리프트 추정치가 안정됨에 따라 점진적으로 격차를 벌리며 10개 시드 중 8개에서 승리했습니다.
  • 주기적 변동: FC-TS는 "위상 기억(phase memory)" 덕분에 이전 사이클의 데이터를 축적함으로써 가장 큰 합성적 이득(50.0%)을 보였습니다. 사이클당 후회는 약 70에서 4로 감소한 반면, 베이스라인들은 정체되었습니다.
  • 반복되는 레지만: FC-TS는 스위치 감지 시 레짐별 사후 분포를 다시 로드함으로써 재시작에 따른 "콜드 스타트(cold start)" 페널티를 피하여 59.0%의 개선을 달성했습니다.
  • 복합 비정상성: 드리프트와 급격한 변화점이 공존하는 환경에서, FC-TS는 드리프트 교정(매끄러운 진화용)과 레짐 리셋(급격한 변화용)을 성공적으로 결-합하여 29.5%의 개선을 이끌어냈습니다.
  • 반합성 포트폴리오: 월간/분기별 사이클과 성장주-가치주 드리프트가 겹치는 금융 과제에서, 적응형 FC-TS 변형은 최적의 베이스라인(D-TS)보다 후회를 28.1% 개선했습니다. 절제 연구(ablation study)를 통해 드리프트 교정이 이러한 이득의 주된 요인임을 확인했습니다.

• 절제 연구 결과:

  • 유효 샘플 크기: 전송 교정 없이 더 많은 데이터를 유지하는 경우("no-transport" 절제 모델) 데이터를 버리는 방식보다 오히려 더 높은 후율을 기록했습니다. 이는 오래된 데이터가 체계적인 편향을 유발함을 확인해 줍니다.
  • 전송의 가치: 다양한 드리프트 규모에서 전송 연산자 자체가 "no-transport" 모델 대비 47~57%의 후회 감소를 설명했습니다. 이는 성능을 견인하는 것이 단순한 사후 분포 재구축이 아니라 교정 메커니즘임을 증명합니다.

의의 및 주장

본 논문은 구조화된 비정상성은 경험을 일률적으로 버리는 것보다 교정하고 재사용함으로써 더 잘 해결될 수 있다고 주장합니다.

저자들은 환경의 드리프트가 예측 가능할 때(점진적, 주기적 또는 반복적), 과거 데이터는 부채가 아니라 자산이라고 강조합니다. 시간의 흐름에 따른 보상 분포의 "흐름"을 명시적으로 모델링함으로써, FC-TS는 망각 기반 방식보다 훨씬 더 큰 유효 샘플 크기를 유지합니다. 결과적으로, 비정상적 밴딧의 샘플 효율성의 핵심은 단일한 일률적 망각 규칙을 적용하는 것이 아니라, 환경의 특정 시간적 구조에 따라 과거 관측치를 재가중치 설정하고 교정하는 데 있음을 시사합니다.

논문은 향로 작업으로서 드리프트 구조를 보정된 불확실성과 함께 온라인으로 학습하는 것, 프레임워크를 일반화된 선형 또는 신경망 밴딧으로 확장하는 것, 그리고 모델링되지 않은 분포 변화가 존재하는 고위험 환경을 위한 안전장치를 개발하는 것을 언급하며 겸허하게 마무리합니다.