Restarting Thompson Sampling for Non-stationary Contextual Bandits = 비정상 컨텍스트 밴딧을 위한 재시작 기반 톰슨 샘플링

다국어 초록 (Multilingual Abstract)

This paper addresses the challenge of non-stationarity in contextual bandit problems by augmenting Linear Thompson Sampling (LinTS) with a simple periodic restart strategy. While existing approaches—such as sliding windows or weighted least squares—adapt to changing environments, they often require prior knowledge of the variation budget or entail significant implementation complexity. Building on the insight that regular restarts alone can provide strong theoretical guarantees in UCB-type methods, we propose Simple Restart Thompson Sampling (\emph{RestartTS}), which (i) mitigates non-stationarity through straightforward periodic resets, and (ii) maintains the empirical robustness characteristic of Thompson Sampling.

Specifically, by introducing a surrogate parameter that decouples non-stationary and stationary components of regret, we first prove that \emph{RestartTS} achieves a dynamic regret bound of $\widetilde{\mathcal{O}}(d^{5/4} T^{3/4} P_T^{1/4})$ matching the best-known results under the assumption of an oracle access to the path-length $P_T$. To eliminate this oracle requirement, we integrate \emph{Bandits-over-Bandits} (BoB) as a meta-learner over \emph{RestartTS} instances with different restart periods. The resulting parameter-free algorithm retains the same $\widetilde{\mathcal{O}}(d^{5/4} T^{3/4} P_T^{1/4})$ regret bound without prior knowledge of $P_T$.

Finally, we conduct experiments on various non-stationary settings — such as periodically and occasionally abrupt changes, randomly and frequently abrupt changes, smooth gradual changes, and rapid gradual changes — and demonstrate that \emph{RestartTS} is an effective algorithm for controlling non-stationarity and is beneficial when parameters change periodically. Furthermore, \emph{BoB-RestartTS} shows robust performance regardless of the variability of the environment.

국문 초록 (Abstract)

이 논문은 문맥적 밴딧(contextual bandit) 문제에서 비정상성(non-stationarity)을 다루기 위해, 선형 톰슨 샘플링(Linear Thompson Sampling, LinTS) 알고리즘에 간단한 주기적 재시작 전략을 결합하는 방법을 제안합니다. 기존의 대표적인 적응 기법들 -- 예를 들어 슬라이딩 윈도우(sliding window)나 가중 최소제곱(weighted least squares) -- 은 환경 변화에 대응할 수 있으나, 비정상성의 정도(variation budget)에 대한 사전 지식이 필요하거나 구현 복잡성을 수반하는 경우가 많습니다. 본 논문은 단순한 주기적 재시작만으로도 UCB 계열 알고리즘에서 이론적 보장을 얻을 수 있다는 통찰에 기반하여, (i) 간단한 주기적 리셋을 통해 비정상성을 완화하고 (ii) 톰슨 샘플링의 경험적 견고성 특성을 유지하는 Simple Restart 톰슨 샘플링(\emph{RestartTS})을 제안합니다.

구체적으로, 본 논문은 비정상성과 정상이 혼합된 후회를 분리할 수 있는 대리 매개변수(surrogate parameter)를 도입함으로써, \emph{RestartTS}가 경로 길이(path-length) $P_T$에 대한 오라클 지식이 있다는 가정하에서 가장 잘 알려진 결과와 일치하는 $\widetilde{\mathcal{O}}(d^{5/4} T^{3/4} P_T^{1/4})$의 동적 후회(dynamic regret) 상한을 달성함을 이론적으로 증명합니다. 또한 이 오라클 가정을 제거하기 위해, 여러 개의 재시작 주기를 가진 \emph{RestartTS} 인스턴스를 메타 학습하는 \emph{Bandits-over-Bandits} (BoB) 방법을 통합하고, 이를 통해 비모수 알고리즘이 $P_T$에 대한 사전 지식 없이도 동일한 $\widetilde{\mathcal{O}}(d^{5/4} T^{3/4} P_T^{1/4})$ 후회 상한을 유지합니다.

마지막으로, 주기적이거나 때때로 발생하는 급격한 변화, 무작위로 자주 발생하는 급격한 변화, 완만한 점진적 변화, 빠른 점진적 변화와 같은 다양한 비정상(non-stationary) 환경에서 실험을 수행하였으며, \emph{RestartTS}가 비정상성을 제어하는 데 효과적인 알고리즘이며 파라미터가 주기적으로 변화할 때 특히 유익함을 입증합니다. 또한 \emph{BoB-RestartTS}는 환경의 변동성에 관계없이 견고한 성능을 보여주었습니다.

목차 (Table of Contents)

• Chapter 1. Introduction 1
• Chapter 2. Related Work 3
• Chapter 3. Preliminaries 6
• 3.1 Notations 6
• 3.2 Contextual Linear Bandit 6
• 3.3 Randomized Exploration and Thompson Sampling 7
• 3.4 Contextual Linear Bandit with Non-stationary Rewards 9
• Chapter 4. RestartTS Algorithm 10
• 4.1 Restarting Thompson Sampling (RestartTS) Algorithm 10
• 4.1.1 Overview and Core Principles 10
• 4.1.2 Problem Setup 11
• 4.1.3 Algorithm Description 13
• 4.2 Dynamic Regret Analysis of RestartTS 15
• 4.2.1 Theoretical Guarantees 15
• 4.2.2 Regret Analysis 16
• Chapter 5. Bandits-over-Bandits: Parameter-Free Adaptation 22
• 5.1 Motivation: Needs for Meta-Learning Framework 22
• 5.2 BoB-RestartTS Framework 23
• 5.3 Dynamic Regret Analysis of the BoB-RestartTS 25
• 5.3.1 The Proof of Theorem4 25
• Chapter 6. Experiments 29
• 6.1 Non-Stationary Environment Settings 30
• 6.2 Algorithms and Baselines Compared 32
• 6.3 Experimental Setup and Parameters 34
• 6.3.1 Feature Distribution and Reward Noise 34
• 6.3.2 Horizon and Repetition 35
• 6.3.3 Hyperparameter Tuning 35
• 6.3.4 Evaluation Metric 36
• 6.4 Result and Discussion 36
• 6.4.1 Abrupt Environment 37
• 6.4.2 Gradual Environment 38
• 6.4.3 Influence of environment variation on parameter-free algorithms 39
• 6.4.4 Final Remarks 41
• Chapter 7. Conclusion 43
• Bibliography 45
• Appendix 47
• 초록 51
• Acknowledgement 52