기술 요약: 로그 평활화를 활용한 순차적 오프-폴리시 학습

문제 정의

오프-폴리시 학습은 행동 정책 (behavior policy) 이 생성한 기록된 상호작용 데이터를 통해 정책을 학습할 수 있게 합니다. 오프-폴리시 학습의 이론적 기반은 배치 설정(한 개의 행동 정책이 생성한 정적 데이터셋에서 단일 정책을 학습하는 경우) 에서 잘 정립되어 있지만, 실제 시스템은 다르게 운영됩니다. 실제로는 정책이 순차적으로 반복 업데이트되고 재배포됩니다: 정책이 모든 역사적 데이터를 기반으로 학습된 후, 새로운 상호작용을 생성하기 위해 배포되고, 그 다음 반복을 위해 확장된 데이터셋으로 재학습됩니다.

추천 시스템 및 광고 배치와 같은 응용 분야에서 이러한 순차적 패러다임이 널리 사용됨에도 불구하고, 이론적으로 크게 탐구되지 않았습니다. 기존 순차적 접근법은 행동 공간의 균일한 커버리지나 비현실적인 데이터 수집 전략 (예: 기하급수적으로 증가하는 배치 크기) 과 같은 강력한 가정에 종종 의존합니다. furthermore, **비관적 원리 (pessimism principle)**와 PAC-베이지안 (PAC-Bayesian) 프레임워크를 활용하는 최신 오프라인 알고리즘들은 엄격한 수렴 보장을 갖춘 순차적 설정으로 성공적으로 확장되지 못했습니다. 본 논문은 실제 순차적 배포와 이론적 보장 사이의 격차를 해소하여, 이론적으로 타당하고 경험적으로 효과적인 순차적 오프-폴리시 학습 알고리즘을 개발하는 것을 목표로 합니다.

방법론

저자들은 시간 단계 $k \geq 0$에 걸쳐 에이전트가 데이터 스트림과 상호작용하는 컨텍스트 밴딧 (Contextual Bandits) 기반 프레임워크를 제안합니다. 각 단계에서 새로운 행동 정책 $\pi_k$가 배포되어 데이터 배치 $S_k$를 수집하고, 에이전트는 누적된 역사 $S_{0:k}$를 사용하여 정책을 업데이트합니다.

이 방법론은 온라인 PAC-베이지안 (Online PAC-Bayesian) 학습 도구와 로그 평활화 (Logarithmic Smoothing, LS) 추정기를 모두 활용하는 두 가지 주요 알고리즘적 기여에 기반합니다.

1. 순차적 로그 평활화 (알고리즘 1)

첫 번째 기여는 Sakhi 외 (2024) 가 도입한 오프라인 로그 평활화 추정기를 순차적 설정으로 확장한 것입니다.

• 추정기: 알고리즘은 표준 LS 정규화항 $h_{LS}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q})$를 사용합니다.
• 메커니즘: 각 단계 $k$에서 알고리즘은 모든 누적 데이터 $S_{0:k}$에 대한 경험적 LS 위험과 사전 분포 $P$에 대한 KL-발산 항을 결합하여 위험의 PAC-베이지안 상한을 최소화합니다.
• 이론적 보장: 정리 3.2 는 순차적 출력 $\pi_{k+1}$에 대한 일반화 경계를 확립합니다. 수렴 속도는 총 샘플 수 $N_k$에 대해 $O(1/\sqrt{N_k})$임이 입증되었으며, 이는 배치 설정의 최적 속도와 일치하지만 데이터의 순차적 누적에 적용됩니다.
• 한계: 저자들은 수렴 경계 내의 의사-분산 (pseudo-variance) 항이 행동 정책이 최적 정책에 접근하더라도 사라지지 않는다고 지적하며, 이로 인해 수렴 속도가 $O(1/\sqrt{N_k})$를 초과하여 가속화되지 않는다고 밝힙니다.

2. 순차적 조정 로그 평활화 (알고리즘 2)

알고리즘 1 의 느린 수렴을 극복하기 위해, 저자들은 새로운 조정 로그 평활화 (Adjusted Logarithmic Smoothing, AdjLS) 추정기를 도입합니다.

• 추정기: 새로운 정규화항이 정의됩니다: $h_{adj}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q(1+\lambda c)})$. 이 조정은 현재 정책의 위험과 과거 위험의 가중 평균 간의 차이를 제어하도록 성능 목표를 수정합니다.
• 메커니즘: 알고리즘 2 는 누적 데이터에 대해 조정된 위험 추정기를 최소화합니다.
• 이론적 보장: 정리 4.4 는 mild 한 가정 하에 (구체적으로, 최적 행동이 정책 클래스에 의해 커버되고 문제가 $\Delta_u > 0$로 정량화된 일정한 분리성을 가진다는 가정), 알고리즘 2 가 임의의 $\alpha \in [0.5, 1)$에 대해 가속화된 수렴 속도 $O(1/N_k^\alpha)$를 달성함을 증명합니다.
• 핵심 통찰: 표준 LS 추정기와 달리, 조정된 추정기의 오차 항 $L(\pi^*, \pi_j)$는 행동 정책 $\pi_j$가 최적 정책 $\pi^*$에 접근함에 따라 사라져 더 빠른 수렴을 가능하게 합니다.

주요 기여

1. 최초의 순차적 PAC-베이지스 알고리즘: 본 논문은 완전히 배치된 상태와 완전히 온라인 상태 사이를 보간하는 이론적 수렴 보장을 제공하는, 순차적 설정을 위해 특별히 설계된 최초의 오프-폴리시 PAC-베이지안 알고리즘을 제시합니다.
2. 조정을 통한 가속화된 수렴: 저자들은 표준 오프라인 추정기를 순차적으로 적용하는 데 있어 근본적인 한계를 식별하고, 합리적인 가정 하에 증명 가능한 가속화된 수렴 속도를 산출하는 원칙적인 조정 (AdjLS) 을 제안합니다.
3. 완화된 가정: 이론적 분석은 정책 클래스가 최적 행동을 커버한다는 가정 (가정 3.4) 만을 요구하며, 이는 이전 순차적 연구들 (예: Zenati 외, 2023) 이 요구했던 균일한 커버리지 가정보다 엄격하게 약합니다.
4. 비-IID 컨텍스트로의 일반화: 이 프레임워크는 컨텍스트 분포가 시간에 따라 진화하는 비정상적 환경에서도 적응 가능함이 입증되어, 컨텍스트에 대한 i.i.d. 가정을 완화했습니다.

경험적 결과

저자들은 컨텍스트 밴딧 문제로 변환된 표준 다중 클래스 데이터셋 (MNIST, FashionMNIST, EMNIST, CIFAR100) 에서 방법론을 평가했습니다.

• 순차적 대 배치: 실험은 단일 배치 업데이트 ($k=1$) 에 비해 중간 정책 업데이트 횟수 ($k$) 를 증가시키는 것이 최종 정책 성능을 일관되게 향상시킨다는 것을 보여줍니다. 이는 순차적 프레임워크의 이점을 검증합니다.
• 알고리즘 비교:
  • **SeqAdjLS(알고리즘 2)**는 **SeqLS(알고리즘 1)**보다 일관되게 우월한 성능을 보이며, 조정된 추정기의 이론적 이점을 확인시켜 줍니다.
  • 두 제안된 방법 모두 SCRM(Zenati 외, 2023, 순차적 반사적 위험 최소화) 을 크게 능가합니다. 저자들은 SCRM 이 특히 작은 배치 크기의 초기 라운드에서 지나치게 보수적이며, 역사적 데이터를 폐기하는 비현실적인 데이터 수집 전략 (기하급수적으로 증가하는 배치) 에 의존한다고 지적합니다.
• 초기 정책의 영향: 순차적 접근법은 초기 행동 정책이 최적에서 멀리 떨어져 있을 때, 특히 고차원 행동 공간 (예: 100 개의 행동을 가진 CIFAR100) 에서 상당한 이득을 보입니다.

중요성과 주장

본 논문은 실제 순차적 오프-폴리시 학습과 엄격한 보장 사이의 이론적 격차를 해소했다고 주장합니다. 온라인 PAC-베이지스 기법과 새로운 로그 평활화 추정기를 결합함으로써, 저자들은 다음과 같은 알고리즘을 제공합니다:

• 일반화: 배치 한계에서 성능을 일치시킴으로써 최첨단 오프라인 접근법을 일반화합니다.
• 가속화: 행동 정책의 점진적 정제를 활용하여 순차적 설정에서의 학습을 가속화합니다.
• 회피: 기존 순차적 방법의 적용성을 저해하는 비현실적인 가정 (예: 균일한 커버리지) 을 피합니다.

저자들은 이론적 분석이 정책 클래스가 최적 행동을 커버한다는 가정에 의존하지만, 이는 이전 연구에 비해 중요한 완화라고 강조합니다. 결론적으로, 온라인 PAC-베이지스와 순차적 컨텍스트 밴딧의 결합은 동적인 실제 시스템에서 견고하고 효율적인 학습을 위한 유망한 방향을 제시합니다.