기술 요약: 잠재 상태 밴딧을 위한 적응형 탐색 (Adaptive Exploration for Latent-State Bandits)

1. 문제 정의

본 논문은 보상 분포가 시간에 따라 자율적으로 진화하는 **관측되지 않는 (잠재적) 마르코프 상태(latent Markov state)**에 의존하는 비정상(non-stationary) 다중 팔 밴딧(multi-armed bandit) 문제를 다룹니다. 일반적인 컨텍스트 밴딧(contextual bandits)과 달리, 학습자는 상태 $s_t$를 직접 관찰할 수 없으며, 오직 선택한 행동 $a_t$와 그 결과로 발생하는 확률적 보상 $r_t$만을 관찰할 수 있습니다.

핵심 과제는 숨겨진 상태가 전이됨에 따라 최적의 팔(optimal arm)이 변한다는 것이지만, 학습자는 오직 행동과 보상의 이력(history)만을 통해 현재의 상태를 추론해야 합니다. 이 설정은 다음과 같은 세 가지 구체적인 기술적 어려움을 야기합니다:

1. 혼란된 보상 추정 (Confounded Reward Estimation): 표준 알고리즘은 상태 분포에 대해 보상을 평균화하며, 이는 최적의 팔이 상태마다 달라질 때 체계적인 편향(bias)을 초래합니다.
2. 시간적 보상 귀속 (Temporal Reward Attribution): 보상 성능의 변화가 학습의 진전 때문인지, 아니면 숨겨진 상태의 전이 때문인지 구분하기 어렵습니다.
3. 제한된 상태 정보 (Limited State Information): 알고리즘은 상태 특징(state features)에 직접 조건화할 수 없으며, 간접적인 신호에 의존해야 합니다. 이는 상태 공간이 커질수록 작업이 더 어려워집니다.

목표는 현재의 숨겨진 상태에 대한 최적의 팔과 실제로 선택된 팔 사이의 누적 차이로 정의되는 **동적 후회 (dynamic regret)**를 최소화하는 것입니다.

2. 방법론

저자들은 **지연된 컨텍스트 (Lagged Context)**와 **탐사 전략 (Probing Strategies)**을 LinUCB 프레임워크에 통합하는 일련의 알고리즘들을 제안합니다. 이 접근 방식은 명시적인 잠재 마르코프 전이 모델을 추정하는 대신, 상태를 분리하기 위한 저차원 통계량에 의존합니다.

2.1 지연된 컨텍스트 (LC-UCB)

첫 번째 구성 요소인 **지연 컨텍스트 UCB (LC-UCB)**는 이전의 행동-보상 쌍 $(a_{t-1}, r_{t-1})$을 컨텍스트 특징 벡터 $\phi_t$로 취급합니다.

• 직관: 느린 마르코프 상태 역학(Markovian state dynamics) 하에서, 이전 보상은 이전 상태 $s_{t-1}$에 대한 정보를 제공하며, 이는 현재 상태 $s_t$와 높은 상관관계를 갖습니다.
• 메커니즘: 알고리즘은 $(a_{t-1}, r_{t-1})$에서 현재 보상 $r_t$로의 매핑을 학습합니다. 이를 통해 학습자는 상태를 암묵적으로 추적하고, 모든 상태에 대한 평균값이 아닌 추론된 최근 상태에 최적인 팔을 선택할 수 있습니다.
• 한계: LC-UCB는 여러 상태가 동일한 행동에 대해 유사한 보상을 생성할 경우(식별 불가능성, non-identifiability), 상태 추론의 모호성을 초래하여 실패할 수 있습니다.

2.2 상태 지문(Fingerprint)을 위한 탐사

모호성을 해결하기 위해, 저자들은 숨겨진 상태를 고유하게 식별할 수 있는 여러 팔의 보상 결합 관측치인 "상태 지문(state fingerprints)"을 생성하는 탐사 전략을 도입합니다. 두 가지 패러다임이 제안됩니다:

1. 무작위 탐사 UCB (Randomized Probing UCB, RP-UCB): 여러 실험 단위(예: 사용자들)에 서로 다른 팔을 동시에 할당할 수 있는 경우에 적용 가능합니다. 이는 동일한 타임스텝에서 실제 결합 관측치 $(r_0, r_1)$을 수집합니다.
2. 순차적 탐사 UCB (Sequential Probing UCB, SP-UCB): 단일 단위 설정에 적용 가능합니다. 팔을 연속적으로 샘플링하며(예: $t$ 시점에 arm 0, $t+1$ 시점에 arm 1), 쌍 $(r_t, r_{t+1})$을 합성된 지문으로 취급합니다. 이는 상태가 "끈끈하다(sticky)"는 가정(높은 자기 전이 확률)에 의존하며, 두 번의 탐사 사이에 상태가 변하지 않아야 합니다.

2.3 적응형 탐사 (AdaRP-UCB / AdaSP-UCB)

고정된 일정의 탐사는 모델이 확신이 있는 상태에서도 후회를 발생시킵니다. 저자들은 세 가지 게이팅 메커니즘을 사용하여 필요할 때만 지문을 갱신하는 적응형 탐사 (Adaptive Probing) 변형을 제안합니다:

• 잔차 게이트 (Residual Gate): 예측 오차(Studentized residual)가 임계값을 초과할 때(모델 드리프트 또는 상태 전이를 나타냄), 탐사를 트리거합니다.
• 불확실성 게이트 (Uncertainty Gate): 상위 두 UCB 점수 사이의 마진이 작을 때(팔 선택의 불확실성이 높음을 나타냄), 탐사를 트리거합니다.
• 노후화(위험) 게이트 (Staleness/Hazard Gate): 지문이 지수적 위험 함수(exponential hazard function)로 정의된 기간 동안 업데이트되지 않았을 때, 탐사를 트리거하여 오래된 정보의 사용을 방지합니다.

이러드 게이트들은 진동 현상을 방지하기 위해 최소 탐사 간격($\tau_{min}$)을 따릅니다.

3. 주요 기여

1. 알고리즘 프레임워크: 명시적인 마르코프 모델 추정 없이도 지연된 컨텍스트와 조율된 탐사를 결합하여 잠재 상태 밴딧을 처리하는 LC-UCB, RP-UCB, SP-UCB 및 이들의 적응형 변형(AdaRP-UCB, AdaSP-UCB) 개발.
2. 이론적 분석: 동적 후제를 세 가지 구성 요소인 표현 모호성(근사 오차), 탐사 비용, 지문이 노후화된 후의 드리프트로 분해하였습니다. 본 논문은 적응형 탐사가 이러한 요소들 사이의 균형을 맞춤으로써 후회를 최소화함을 보여주는 경계(bounds)를 제공합니다.
3. 실험적 검증: 다양한 숨겨진 상태의 수($S$), 전이율(자기 전이 확률 $p_{stay}$), 보상 노이즈($\sigma$), 시간 지평($T$)에 걸친 체계적인 평가.

4. 실험 결과

알고리즘은 고전적인 베이스라인(UCB1, Thompson Sampling), 적대적 방법(EXP3), 비정상 방법(Sliding Window UCB, Discounted UCB)과 비교 평가되었습니다.

• 성능: 적응형 탐사 방법(특히 AdaRP-UCB 및 AdaSP-UCB)은 요약 정보(지문)가 상태를 구분할 수 있고 충분히 빈번하게 업데이트되는 환경에서 모든 베이스라인을 일관되게 능가했습니다.
  • AdaRP-UCB는 13개의 무작위 구성 중 12개에서 가장 낮은 후율을 달행하며, 변동성이 큰 환경에서 상당한 이득을 보여주었습니다.
  • AdaSP-UCB는 낮은 노이즈, 느린 혼합(mixing), 또는 큰 상태 공간을 가진 단일 단위 설정에서 가장 좋은 성능을 보였습니다.
• 실패 모드: 본 논문은 방법론이 성능 저하를 보이는 특정 조건을 식려합니다:
  • 높은 노이즈: 노이즈($\sigma$)가 팔 간의 차이(arm gap)에 비해 높을 때, 지문이 약해지며 비정상 베이스라인(D-UCB 등)이 더 나은 성능을 보일 수 있습니다.
  • 약한 지문 분리도: 서로 다른 상태가 유사한 결합 보상 분포를 생성할 경우, 탐사 전략이 상태를 식별할 수 없습니다.
  • 빠른 전환: 순차적 탐사(SP-UCB)는 탐사 윈도우 내에서 상태가 빈번하게 변할 때(낮은 $p_{stay}$) 합성 지문이 유효하지 않게 되어 실패합니다.
• 절제 연구 (Ablation Studies): 지문 특징($\phi_{fp}$)을 제거하면 끈끈한 상태(sticky-state) 환경에서 후율이 크게 증가하여, 결합 관측의 가치를 확인시켜 주었습니다. 지연된 컨텍스트($\phi_{lag}$)를 제거했을 때 일부 무작위 설정에서 영향이 적었는데, 이는 적응형 타이밍이 주요 동력이었음을 시사합니다.

5. 의의 및 주장

본 논문은 자율적인 마르코프 과정을 통해 환경이 진화하는 **구조적 비정상성(structured non-stationarity)**에 대한 실용적인 접근법을 제공한다고 주장합니다. 변화를 임의적인 드리프트로 취급하는 표준 비정상 밴딧이나, 전체 관측성 또는 복잡한 디코딩을 요구하는 POMDP와 달리, 이 접근 방식은 가벼운 이력 요약과 탐사를 사용하여 현재의 최적 팔을 유지합니다.

저자들은 다음과 같은 조건에서 이 방법들이 가장 효과적임을 강조합니다:

1. 잠재 상태가 짧은 지평 동안 예측 가능할 때 (느린 혼합).
2. 탐사 전략이 관련 상태를 구분할 수 있는 충분한 통계량(지문)을 생성할 수 있을 때.
3. 적응형 게이팅 메커니즘이 과도한 탐사 후회 없이 이러한 요약 정보를 최신 상태로 유지할 수 있을 때.

이 연구는 숨겨진 상태의 전체 전이 역학을 학습할 필요 없이 LinUCB를 기반으로 한 계산 효율적인 솔루션을 제공함으로써, 컨텍스트 밴딧과 잠재 상태 강화 학습 사이의 간극을 메웁니다.