Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift

Bochao LiYao FuWei ChenFang-yuan Kong

article2026arXiv0 citations

Proposes Anchor-TS, a Thompson sampling algorithm that uses a median-based anchoring rule to safely incorporate distribution-shifted offline data into online bandit learning with provable regret guarantees.

Listen

Sequential decision-making systems—such as recommendation platforms, clinical trials, and dynamic pricing models—often aim to accelerate live learning by incorporating pre-collected historical data. However, real-world deployment frequently suffers from distribution shift, where the offline historical environment differs from the online operational environment due to system updates, evolving user preferences, or simulation-to-reality discrepancies. While existing approaches primarily rely on optimism-driven confidence-bound algorithms, developing practical Bayesian methods like Thompson sampling has remained an unresolved challenge because posterior samples are neither strictly optimistic nor pessimistic, making biased historical data difficult to filter safely.

The article introduces and evaluates a novel algorithm called Sample-Mean Anchored Thompson Sampling (Anchor-TS). Its main objective is to establish a principled mechanism that leverages potentially biased offline data to accelerate online bandit learning while rigorously guarding against performance degradation caused by distribution shift.

To achieve this, Anchor-TS calculates a decision score for each available action by taking the median of three values: a purely online posterior sample, a hybrid posterior sample combining offline and online data with a protective right-hand shift, and the unbiased online sample mean serving as a stabilizing anchor. The authors establish theoretical cumulative regret bounds to quantify learning speed and performance guarantees. They also conduct extensive empirical evaluations across varying environments, testing different offline dataset sizes, bias magnitudes, action set sizes, and offline sample distributions over ten thousand interaction rounds.

The analysis yields several key findings in order of importance. First, the proposed median anchoring provides provable robustness: cumulative regret is guaranteed to be no worse than purely online Thompson sampling, and it strictly decreases when distribution shift is mild. Second, unlike confidence-bound methods, Anchor-TS uniquely reduces regret by accelerating convergence on the optimal action when historical data contain abundant samples of the best choice—a common scenario in practice when logs are generated by expert policies. Third, empirical simulations show that Anchor-TS consistently and substantially outperforms both standard Thompson sampling baselines and confidence-bound algorithms across all tested bias levels and sample sizes. Finally, even in purely online settings with zero offline data, the median-aggregation mechanism reduces the exploration threshold by half, effectively curtailing the excessive exploration caused by the variance of single posterior samples.

These findings demonstrate that organizations can safely reuse legacy logs and domain simulations without risking severe policy degradation from unmodeled shifts. By converting biased historical logs into faster convergence, systems can significantly lower operational learning costs and user-facing exploration risks. Furthermore, because Anchor-TS captures unique efficiencies when historical data favor the optimal decision, it offers superior real-world utility over traditional confidence-bound architectures.

Stakeholders deploying adaptive decision engines should consider adopting median-anchored Thompson sampling frameworks when historical data are available. Prior to full deployment, teams should establish loose but sound upper bounds on expected historical bias across key actions to calibrate the hybrid adjustments. Promising operational next steps include running controlled pilot deployments in production and extending the anchoring architecture into high-dimensional, contextual decision systems.

Decision-makers should note that the current theoretical guarantees assume bounded distribution shifts and sub-Gaussian reward structures. Confidence in the reported performance is high for standard multi-armed decision settings, but caution is advised in highly dynamic environments where distribution shifts fluctuate unpredictably over time.

Microsoft Southern University of Science and Technology bayesian methods online environments estimation method sample-mean anchored Thompson Sampling offline-to-online learning distribution shift

arXiv: 2605.10289

Paper: An Empirical Evaluation of Thompson Sampling, Olivier Chapelle et al. (2011). Provides the foundational empirical and algorithmic benchmark for Thompson sampling in bandit settings, establishing the baseline Bayesian exploration method that Anchor-TS adapts for offline-to-online learning.
Paper: Introduction to Multi-Armed Bandits, Aleksandrs Slivkins (2019). Offers essential prerequisite foundations on multi-armed bandit algorithms, regret analysis, and posterior sampling principles central to evaluating online decision-making.
Paper: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Sébastien Bubeck et al. (2012). Establishes core regret analysis frameworks and concentration properties for multi-armed bandit algorithms that underpin the theoretical safety guarantees in the source.
Paper: Finite-time Analysis of the Multiarmed Bandit Problem, Peter Auer et al. (2002). Introduces standard finite-time regret analysis and upper confidence bounds, contrasting the optimistic index methods that Anchor-TS seeks to match in robustness using Thompson sampling.
Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). Develops self-normalized martingale concentration techniques essential for understanding confidence bounds and sample-mean behavior in sequential decision problems.
Paper: Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems, Sergey Levine et al. (2020). Presents a comprehensive review of the challenges of distributional shift and overestimation when transitioning from logged offline data to online decision-making.
Paper: Counterfactual Risk Minimization: Learning from Logged Bandit Feedback, Adith Swaminathan et al. (2015). Formulates the foundational principles of learning and variance control under logged bandit feedback, directly motivating offline data reuse in sequential environments.

No sufficiently relevant recommendations were found.

Cover for Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift

Abstract

Offline-to-online learning aims to improve online decision-making by leveraging offline logged data. A central challenge in this setting is the distribution shift between offline and online environments. While some existing works attempt to leverage shifted offline data, they largely rely on UCB-type algorithms. Thompson sampling (TS) represents another canonical class of bandit algorithms, well known for its strong empirical performance and naturally suited to offline-to-online learning through its Bayesian formulation. However, unlike UCB indices, posterior samples in TS are not guaranteed to be optimistic with respect to the true arm means. This makes indices constructed from purely online and hybrid data difficult to compare and complicates their use. To address this issue, we propose sample-mean anchored TS (Anchor-TS), which introduces a novel median-based anchoring rule that defines the arm index as the median of an online posterior sample, a hybrid posterior sample, and the online sample mean. The median anchoring systematically corrects bias induced by distribution shift by mitigating over-estimation for suboptimal arms and under-estimation for optimal arms, while exploiting offline information to obtain more accurate estimates when the shift is small. We establish theoretical guarantees showing that the proposed algorithm safely leverages offline data to accelerate online learning, and quantifying how the degree of distribution shift and the size of offline data affect the resulting regret reduction. Extensive experiments demonstrate consistent improvements of our algorithm over baselines.

Topics

bayesian methods online environments estimation method adaptive algorithms optimization problems

Keywords

sample-mean anchored Thompson Sampling offline-to-online learning distribution shift bandit algorithms hybrid posterior distributions biased priors regret decomposition instance-dependent regret offline bias

1 Introduction
2 Related Work
3 Preliminaries
4 Algorithm
5 Theoretical Results and Discussions
6 Proof Sketch
7 Experiments
8 Conclusion
References
A Proof of Theorem
B Theoretical Analysis and Experiments in the Pure Online Setting
B.1 1/21/2 improvement on the leading log⁡T\log T-term
B.2 Experiments in the pure online setting
C Proof of Lemmas
D Useful Lemmas

Knowls

Knowl 1 — Offline-to-Online Multi-Armed Bandit Formulation with Bounded Distribution Shift
definition
In the offline-to-online stochastic multi-armed bandit (MAB) setting with distribution shift, an agent interacts with a set of $K$ arms $[K] = \{1, \dots, K\}$ over an online horizon $T$ .

Each arm $i \in [K]$ is associated with:
1. An unknown online reward distribution $P_i^{(\text{on})}$ supported on $[0, 1]$ with unknown online mean $\mu_i^{(\text{on})} = \mathbb{E}_{X \sim P_i^{(\text{on})}}[X]$ . Arm $1 \in \arg\max_{j \in [K]} \mu_j^{(\text{on})}$ is the unique optimal arm, and each suboptimal arm $i \ne 1$ has a sub-optimality gap $\Delta_i = \mu_1^{(\text{on})} - \mu_i^{(\text{on})} > 0$ .
2. A pre-collected offline dataset $S_i = \{X_{i,1}, \dots, X_{i,N_i}\}$ of size $N_i$ , where samples are independent and identically distributed draws from an offline reward distribution $P_i^{(\text{off})}$ supported on $[0, 1]$ with unknown offline mean $\mu_i^{(\text{off})} = \mathbb{E}_{X \sim P_i^{(\text{off})}}[X]$ .
3. A known upper bound $V_i \ge 0$ on the distribution shift magnitude such that: $|\mu_i^{(\text{off})} - \mu_i^{(\text{on})}| \le V_i.$
At each round $t = 1, \dots, T$ , the agent selects an action $A(t) \in [K]$ and observes an online reward $R_{A(t)}(t) \sim P_{A(t)}^{(\text{on})}$ . The objective is to minimize the cumulative expected regret over horizon $T$ : $\text{Reg}(T) = T \mu_1^{(\text{on})} - \mathbb{E}\left[\sum_{t=1}^T R_{A(t)}(t)\right] = \sum_{i \ne 1} \Delta_i \mathbb{E}\left[T_i(T)\right],$ where $T_i(T) = \sum_{t=1}^T \mathbf{1}\{A(t) = i\}$ is the number of times arm $i$ is pulled online up to horizon $T$ .
Knowl 2 — Sample-Mean Anchored Thompson Sampling (Anchor-TS)
algorithm
Sample-Mean Anchored Thompson Sampling (Anchor-TS) balances purely online observations and potentially biased offline data by selecting arm indices through a median-of-three rule. For each arm, Anchor-TS maintains an online sample mean $\hat{\mu}_i^{(\text{on})}$ , an online posterior sample $\theta_i^{(\text{on})}$ , and a right-shifted hybrid posterior sample $\theta_i^{(\text{hyb})}$ . The arm index is set to the median of these three quantities.
Input: Arm set $[K]$ , offline sample means $\hat{\mu}_i^{(\text{off})}$ , offline sample sizes $N_i$ , and shift bounds $V_i$ for all $i \in [K]$
Initialization:
  for each arm $i \in [K]$ :
     $T_i(1) \leftarrow 0$
     $\hat{\mu}_i^{(\text{on})}(1) \leftarrow 0$
     $\hat{\sigma}_{i,\text{on}}^2(1) \leftarrow 1$
     $\hat{\mu}_i^{(\text{hyb})}(1) \leftarrow \hat{\mu}_i^{(\text{off})}$
     $\hat{\sigma}_{i,\text{hyb}}^2(1) \leftarrow 1 / (N_i + 1)$
     $Z_{i,1} \leftarrow V_i$
for $t = 1, 2, \dots, T$ :
  for each arm $i \in [K]$ :
    Sample $\theta_i^{(\text{on})}(t) \sim \mathcal{N}\left(\hat{\mu}_i^{(\text{on})}(t), \hat{\sigma}_{i,\text{on}}^2(t)\right)$
    Sample $\theta_i^{(\text{hyb})}(t) \sim \mathcal{N}\left(\hat{\mu}_i^{(\text{hyb})}(t) + Z_{i,t}, \hat{\sigma}_{i,\text{hyb}}^2(t)\right)$
     $\hat{\theta}_i(t) \leftarrow \text{median}\left(\hat{\mu}_i^{(\text{on})}(t), \theta_i^{(\text{on})}(t), \theta_i^{(\text{hyb})}(t)\right)$
  Select arm $A(t) \leftarrow \arg\max_{i \in [K]} \hat{\theta}_i(t)$ and observe reward $R_{A(t)}(t)$
   $T_{A(t)}(t+1) \leftarrow T_{A(t)}(t) + 1$
   $\hat{\mu}_{A(t)}^{(\text{on})}(t+1) \leftarrow \frac{T_{A(t)}(t) \cdot \hat{\mu}_{A(t)}^{(\text{on})}(t) + R_{A(t)}(t)}{T_{A(t)}(t+1) + 1}$
   $\hat{\sigma}_{A(t),\text{on}}^2(t+1) \leftarrow \frac{1}{T_{A(t)}(t+1) + 1}$
   $\hat{\mu}_{A(t)}^{(\text{hyb})}(t+1) \leftarrow \frac{T_{A(t)}(t+1) \cdot \hat{\mu}_{A(t)}^{(\text{on})}(t+1) + N_{A(t)} \cdot \hat{\mu}_{A(t)}^{(\text{off})}}{T_{A(t)}(t+1) + N_{A(t)} + 1}$
   $\hat{\sigma}_{A(t),\text{hyb}}^2(t+1) \leftarrow \frac{1}{T_{A(t)}(t+1) + N_{A(t)} + 1}$
   $Z_{A(t),t+1} \leftarrow \frac{N_{A(t)} V_{A(t)}}{T_{A(t)}(t+1) + N_{A(t)}}$
  for each unselected arm $i \ne A(t)$ :
     $\hat{\mu}_i^{(\text{on})}(t+1) \leftarrow \hat{\mu}_i^{(\text{on})}(t)$
     $\hat{\sigma}_{i,\text{on}}^2(t+1) \leftarrow \hat{\sigma}_{i,\text{on}}^2(t)$
     $\hat{\mu}_i^{(\text{hyb})}(t+1) \leftarrow \hat{\mu}_i^{(\text{hyb})}(t)$
     $\hat{\sigma}_{i,\text{hyb}}^2(t+1) \leftarrow \hat{\sigma}_{i,\text{hyb}}^2(t)$
     $Z_{i,t+1} \leftarrow Z_{i,t}$
Knowl 3 — Regret Upper Bound of Anchor-TS under Distribution Shift
theoretical result
Let $T$ be the online time horizon, $K$ be the number of arms, arm $1$ be the unique optimal arm with online mean $\mu_1^{(\text{on})}$ , and $\Delta_i = \mu_1^{(\text{on})} - \mu_i^{(\text{on})}$ be the sub-optimality gap for each suboptimal arm $i \in [K] \setminus \{1\}$ . Let $N_i$ denote the number of offline samples for arm $i$ , and let $\omega_i := V_i + \mu_i^{(\text{off})} - \mu_i^{(\text{on})}$ be the effective discrepancy of arm $i$ induced by shift bound $V_i \ge |\mu_i^{(\text{off})} - \mu_i^{(\text{on})}|$ .

The cumulative expected regret of Sample-Mean Anchored Thompson Sampling (Anchor-TS) satisfies: $\text{Reg}(T) \le O\left( \sum_{i \ne 1} \Delta_i \left( \left( \frac{C_1 \log T}{\Delta_i^2} - N_i \left( 1 - \frac{3\omega_i}{\Delta_i} \right)_+ \right)_+ + \left( \frac{C_2 \log T}{\Delta_i^2} - N_1 \right)_+ + \frac{C_3}{\Delta_i^2} \right) \right),$ where $(x)_+ = \max\{0, x\}$ , and $C_1, C_2, C_3 > 0$ are universal constants independent of problem parameters.

This bound guarantees that:
1. Robustness: Regret is never asymptotically worse than purely online Thompson Sampling ( $O(\sum_{i \ne 1} \frac{\log T}{\Delta_i})$ ).
2. Suboptimal arm benefit: When the distribution shift is mild ( $3\omega_i < \Delta_i$ ), the offline sample size $N_i$ directly offsets the regret term from suboptimal arm estimation, scaled by the discount factor $(1 - 3\omega_i / \Delta_i)$ .
3. Optimal arm benefit: Offline samples $N_1$ on the optimal arm reduce the exploration regret associated with arm 1 directly without any discount factor, providing a speedup unique to the Thompson Sampling framework.
Knowl 4 — Median-of-Three Aggregation Mechanism for Robust Posterior Sampling
model/method
In standard upper confidence bound (UCB) algorithms under distribution shift, robustness is achieved by taking the minimum of an online UCB and a bias-corrected hybrid UCB because UCB indices are guaranteed to be optimistic upper bounds. For Thompson Sampling (TS), posterior samples are not inherently optimistic or pessimistic, so taking the minimum would risk underestimating the optimal arm, while taking the maximum would overestimate suboptimal arms.

Anchor-TS solves this by aggregating three statistics via the median: $\hat{\theta}_i(t) = \text{median}\left(\hat{\mu}_i^{(\text{on})}(t), \theta_i^{(\text{on})}(t), \theta_i^{(\text{hyb})}(t)\right),$ where $\hat{\mu}_i^{(\text{on})}(t)$ is the online sample mean (serving as an unbiased anchor), $\theta_i^{(\text{on})}(t) \sim \mathcal{N}\left(\hat{\mu}_i^{(\text{on})}(t), \frac{1}{T_i(t)+1}\right)$ , and $\theta_i^{(\text{hyb})}(t) \sim \mathcal{N}\left(\hat{\mu}_i^{(\text{hyb})}(t) + Z_{i,t}, \frac{1}{T_i(t)+N_i+1}\right)$ .

The median acts as an adaptive filter:
- When offline data has low bias, the hybrid posterior sample $\theta_i^{(\text{hyb})}$ concentrates more tightly around the true mean than the online sample due to the larger sample size $T_i(t) + N_i$ , and the median favors this lower-variance hybrid estimate to accelerate learning.
- When offline data has substantial bias, the hybrid posterior deviates from the true mean and behaves as an outlier, prompting the median to select the unbiased online sample $\theta_i^{(\text{on})}$ and filter out the biased offline distortion.
Knowl 5 — Right-Hand Shift of the Hybrid Posterior Distribution
model/method
In Thompson Sampling, regret can accumulate rapidly if the optimal arm (arm 1) is underestimated, even if suboptimal arms are accurately estimated. Under distribution shift where offline rewards underestimate the optimal arm ( $\mu_1^{(\text{off})} < \mu_1^{(\text{on})}$ ), a pessimistic online sample mean $\hat{\mu}_1^{(\text{on})}(t)$ combined with a biased hybrid posterior sample $\theta_1^{(\text{hyb})}(t)$ can cause the median index $\hat{\theta}_1(t)$ to fall below the true mean. This leads to severe under-exploration of arm 1, incurring regret that grows exponentially with the offline size $N_1$ before online corrections can occur.

To prevent under-exploration of arm 1 without knowing which arm is optimal, Anchor-TS applies a right-hand shift of magnitude $Z_{i,t}$ to the hybrid posterior mean of every arm $i \in [K]$ : $Z_{i,t} = \frac{N_i V_i}{T_i(t) + N_i},$ where $N_i$ is the offline sample size, $T_i(t)$ is the number of online pulls of arm $i$ up to round $t-1$ , and $V_i \ge |\mu_i^{(\text{off})} - \mu_i^{(\text{on})}|$ is the known shift bound.

Because $|\mu_i^{(\text{off})} - \mu_i^{(\text{on})}| \le V_i$ , adding $Z_{1,t}$ ensures that the expected value of the shifted hybrid mean for arm 1 satisfies: $\mathbb{E}\left[\hat{\mu}_1^{(\text{hyb})}(t) + Z_{1,t}\right] = \frac{T_1(t)\mu_1^{(\text{on})} + N_1\mu_1^{(\text{off})}}{T_1(t)+N_1} + \frac{N_1 V_1}{T_1(t)+N_1} \ge \mu_1^{(\text{on})}.$ For suboptimal arms $i \ne 1$ , the shift $Z_{i,t}$ quickly decays to $0$ as online pulls $T_i(t)$ accumulate, and any transient overestimation is mitigated by the median aggregation rule.
Knowl 6 — Halved Leading Regret Constant of Median-Based Thompson Sampling in Pure Online Settings
theoretical result
When no offline data is available ( $N_i = 0$ for all $i \in [K]$ ), the hybrid posterior distribution is identical to the online posterior. In this pure online setting, Anchor-TS simplifies to selecting arm indices as: $\hat{\theta}_i(t) = \text{median}\left(\theta_{i,1}^{(\text{on})}(t), \theta_{i,2}^{(\text{on})}(t), \hat{\mu}_i^{(\text{on})}(t)\right),$ where $\theta_{i,1}^{(\text{on})}(t), \theta_{i,2}^{(\text{on})}(t) \sim \text{i.i.d. } \mathcal{N}\left(\hat{\mu}_i^{(\text{on})}(t), \frac{1}{T_i(t)+1}\right)$ and $\hat{\mu}_i^{(\text{on})}(t)$ is the online sample mean.

This median aggregation preserves the standard logarithmic regret rate while reducing the leading $\log T$ constant by a factor of $1/2$ relative to vanilla Thompson Sampling:
1. Suboptimal arm overestimation: Under the good event $\hat{\mu}_i^{(\text{on})}(t) \le x_i < y_i$ , the median exceeds $y_i$ if and only if both independent posterior samples exceed $y_i$ : $\Pr\left(\hat{\theta}_i(t) > y_i \mid \mathcal{F}_{t-1}\right) = \Pr\left(\theta_i^{(\text{on})}(t) > y_i \mid \mathcal{F}_{t-1}\right)^2.$ Squaring the Gaussian tail probability halves the required exploration threshold from $L_i(T)$ to $\frac{1}{2} L_i(T)$ .
2. Optimal arm under-exploration: Under the good event $\hat{\mu}_1^{(\text{on})}(\tau_k+1) > y_i$ , the optimal arm index exceeds $y_i$ if either posterior sample exceeds $y_i$ , resulting in hitting probability $p_{i,\tau_k+1} = 1 - (1 - p_{i,\tau_k+1}^{(\text{on})})^2$ , which satisfies: $\frac{1 - p_{i,\tau_k+1}}{p_{i,\tau_k+1}} \le \frac{1}{2} \cdot \frac{1 - p_{i,\tau_k+1}^{(\text{on})}}{p_{i,\tau_k+1}^{(\text{on})}}.$ This halves the leading optimal-arm regret term.
Knowl 7 — Empirical Superiority of Anchor-TS in Unbiased Offline-to-Online Regimes
empirical result
In synthetic multi-armed bandit experiments with $K=10$ arms, horizon $T=10{,}000$ , total offline sample size $2{,}000$ , and Gaussian rewards of unit variance (comparing sub-optimality gaps $\Delta \in \{0.1, 0.3\}$ with optimal arm online mean $0.8$ and suboptimal arm means $0.5$ or $0.7$ ), Anchor-TS was compared against standard UCB, standard TS, Hybrid UCB, Hybrid TS, and MINUCB across three offline data coverage regimes: uniform coverage, 80% coverage on optimal arm 1, and 80% coverage on suboptimal arm 2.

Key empirical findings:
1. Anchor-TS consistently achieved lower cumulative regret than both Hybrid TS and all UCB-based baselines across all non-trivial coverage regimes.
2. When offline samples were concentrated on optimal arm 1 (80% coverage on arm 1), Anchor-TS achieved substantial performance gains, substantially outperforming UCB-based algorithms (UCB, MINUCB, Hybrid UCB) which cannot exploit optimal-arm offline data to reduce exploration.
3. In hard bandit instances with small gap $\Delta = 0.1$ , Hybrid UCB and MINUCB underperformed purely online UCB due to excessive shrinkage of the optimal arm's confidence interval, whereas Anchor-TS maintained superior performance.
4. Compared to Hybrid TS, Anchor-TS reduced excess exploration caused by high posterior variance by anchoring decisions to the online sample mean.
Knowl 8 — Empirical Robustness and Scalability of Anchor-TS under Biased Offline Data
empirical result
In experiments with adversarial distribution shift where the optimal arm is underestimated offline ( $\mu_1^{(\text{off})} = 0.5$ vs $\mu_1^{(\text{on})} = 0.8$ ) and suboptimal arms are overestimated offline ( $\mu_i^{(\text{off})} = 0.6$ vs $\mu_i^{(\text{on})} = 0.5$ ), Anchor-TS was evaluated against UCB, MINUCB, and vanilla TS across varying parameter sweeps over $T = 10{,}000$ rounds (50 runs):
1. Offline sample size sweep ( $\sum_i N_i \in [1000, 10000]$ ): Anchor-TS maintained the lowest regret throughout and steadily improved as offline sample size increased under uniform coverage.
2. Shift magnitude sweep ( $\delta = \mu_1^{(\text{on})} - \mu_1^{(\text{off})} \in [-0.2, 0.6]$ ): Despite severe underestimation of the optimal arm in the offline data, Anchor-TS maintained a stable low-regret trajectory, consistently outperforming MINUCB and purely online methods.
3. Prior bound parameter sweep ( $V \in [0.1, 1.0]$ ): When $V$ was tight, Anchor-TS exploited offline data aggressively; as $V$ increased, its performance degraded gracefully toward, but never fell below, purely online TS.
4. Arm set scalability sweep ( $K \in [5, 30]$ ): As the number of arms $K$ scaled up, cumulative regret of UCB-based methods grew rapidly, whereas Anchor-TS exhibited much slower regret growth due to median-based suppression of unnecessary exploration.

Coverage note — No substantial contributed material was omitted; intermediate proof lemmas were excluded in favor of the main theoretical guarantees and algorithmic principles.

References

1.Milton Abramowitz, Irene A Stegun, and Robert H Romer. Handbook of mathematical functions with formulas, graphs, and mathematical tables. American Journal of Physics, 56(10):958–958, 1988.
2.Akhil Agnihotri, Rahul Jain, Deepak Ramachandran, and Zheng Wen. Online bandit learning with offline preference data for improved rlhf. arXiv preprint arXiv:2406.09574, 2024.
3.Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39–1. JMLR Workshop and Conference Proceedings, 2012.
4.Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, pages 127–135. PMLR, 2013.
5.Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1–24, 2017.
6.Hyun-Soo Ahn, Mengzhenyu Zhang, and Zijin Zhang. Online decisions with (biased) offline data. Available at SSRN 5350921, 2025.
7.Peter Auer, N Cesa-Bianchi, and P Fischer. Finite time analysis of the multiarmed bandit problem. Machine Learning, 47:235–256, 2002.
8.Philip J Ball, Laura Smith, Ilya Kostrikov, and Sergey Levine. Efficient online reinforcement learning with offline data. In Proceedings of the 40th International Conference on Machine Learning, pages 1577–1594. PMLR, 2023.
9.Siddhartha Banerjee, Sean R Sinclair, Milind Tambe, Lily Xu, and Christina Lee Yu. Artificial replay: a meta-algorithm for harnessing historical data in bandits. arXiv preprint arXiv:2210.00025, 2022.
10.Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Proceedings of the 25th International Conference on Neural Information Processing Systems, pages 2249–2257, 2011.
11.Wang Chi Cheung and Lixing Lyu. Leveraging (biased) information: multi-armed bandits with offline data. In Proceedings of the 41st International Conference on Machine Learning, pages 8286–8309. PMLR, 2024.
12.J Russo Daniel, Van Roy Benjamin, Kazerouni Abbas, Osband Ian, and Wen Zheng. A tutorial on thompson sampling. Foundations and Trends® in Machine Learning, 11(1):1–99, 2018.
13.Ole-Christoffer Granmo. Solving two-armed bernoulli bandit problems using a bayesian learning automaton. International Journal of Intelligent Computing and Cybernetics, 3(2):207–234, 2010.
14.Qijia He, Minghan Wang, Xutong Liu, Zhiyong Wang, and Fang Kong. Learning across the gap: Hybrid multi-armed bandits with heterogeneous offline and online data. In The 39th Annual Conference on Neural Information Processing Systems, 2025.
15.Ruiquan Huang, Donghao Li, Chengshuai Shi, Cong Shen, and Jing Yang. Augmenting online rl with offline data is all you need: A unified hybrid rl algorithm design and analysis. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025.
16.Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. In Proceedings of the 38th International Conference on Machine Learning, pages 5074–5083. PMLR, 2021.
17.Tianyuan Jin, Xianglin Yang, Xiaokui Xiao, and Pan Xu. Thompson sampling with less exploration is fast and optimal. In Proceedings of the 40th International Conference on Machine Learning, pages 15239–15261. PMLR, 2023.
18.Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International Conference on Algorithmic Learning Theory, pages 199–213. Springer, 2012.
19.Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays. In Proceedings of the 32nd International Conference on Machine Learning, pages 1152–1161. PMLR, 2015.
20.TL Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22, 1985.
21.Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
22.Seunghyun Lee, Younggyo Seo, Kimin Lee, Pieter Abbeel, and Jinwoo Shin. Offline-to-online reinforcement learning via balanced replay and pessimistic q-ensemble. In Conference on Robot Learning, pages 1702–1712. PMLR, 2022.
23.Che-Yu Liu and Lihong Li. On the prior sensitivity of thompson sampling. In International Conference on Algorithmic Learning Theory, pages 321–336. Springer, 2016.
24.Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09359, 2020.
25.Mitsuhiko Nakamoto, Simon Zhai, Anikait Singh, Max Sobol Mark, Yi Ma, Chelsea Finn, Aviral Kumar, and Sergey Levine. Cal-ql: Calibrated offline rl pre-training for efficient online fine-tuning. Proceedings of the 37th International Conference on Neural Information Processing Systems, pages 62244–62269, 2023.
26.Bastian Oetomo, R Malinga Perera, Renata Borovica-Gajic, and Benjamin IP Rubinstein. Cutting to the chase with warm-start contextual bandits. Knowledge and Information Systems, 65(9):3533–3565, 2023.
27.Chengrui Qu, Laixi Shi, Kishan Panaganti, Pengcheng You, and Adam Wierman. Hybrid transfer reinforcement learning: Provable sample efficiency from shifted-dynamics data. In International Conference on Artificial Intelligence and Statistics, pages 1054–1062. PMLR, 2025.
28.Steven L Scott. A modern bayesian look at the multi-armed bandit. Applied Stochastic Models in Business and Industry, 26(6):639–658, 2010.
29.Flore Sentenac, Ilbin Lee, and Csaba Szepesvari. Balancing optimism and pessimism in offline-to-online learning. arXiv preprint arXiv:2502.08259, 2025.
30.Pannagadatta Shivaswamy and Thorsten Joachims. Multi-armed bandit problems with history. In Artificial Intelligence and Statistics, pages 1046–1054. PMLR, 2012.
31.Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu, Thodoris Lykouris, Miroslav Dudík, and Robert Schapire. Bayesian decision-making under misspecifed priors with applications to meta-learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 26382–26394, 2021.
32.Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make rl efficient. In The 11th International Conference on Learning Representations, 2023.
33.Kevin Tan and Ziping Xu. A natural extension to online algorithms for hybrid rl with limited coverage. Reinforcement Learning Journal, 1, 2024.
34.William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294, 1933.
35.Timothy Verstraeten, Eugenio Bargiacchi, Pieter JK Libin, Jan Helsen, Diederik M Roijers, and Ann Nowé. Multi-agent thompson sampling for bandit applications with sparse neighbourhood structures. Scientific Reports, 10(1):6728, 2020.
36.Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, pages 35300–35338. PMLR, 2023.
37.Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In Proceedings of the 35th International Conference on Machine Learning, pages 5114–5122. PMLR, 2018.
38.Yu Xia, Zhihui Xie, Tong Yu, Canzhe Zhao, and Shuai Li. Toward joint utilization of absolute and relative bandit feedback for conversational recommendation. User Modeling and User-Adapted Interaction, 34(5):1707–1744, 2024.
39.Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. In 35th Conference on Neural Information Processing Systems, pages 27395–27407, 2021.
40.Le Yang, Vincent YF Tan, and Wang Chi Cheung. Best arm identification with possibly biased offline data. arXiv preprint arXiv:2505.23165, 2025.
41.Zechen Yin and Zhixuan Fang. Multi-armed bandits with biased and heteroscedastic auxiliary rewards. In Proceedings of the 34th ACM International Conference on Information and Knowledge Management, pages 3899–3908, 2025.
42.Zishun Yu and Xinhua Zhang. Actor-critic alignment for offline-to-online reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, pages 40452–40474. PMLR, 2023.
43.Chicheng Zhang, Alekh Agarwal, Hal Daumé Iii, John Langford, and Sahand Negahban. Warm-starting contextual bandits: Robustly combining supervised and bandit feedback. In Proceedings of the 36th International Conference on Machine Learning, pages 7335–7344. PMLR, 2019.
44.Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In The 9th International Conference on Learning Representations, 2021.
45.Yixuan Zhang, Ruihao Zhu, and Qiaomin Xie. Contextual online pricing with (biased) offline data. In The 39th Annual Conference on Neural Information Processing Systems, 2025.
46.Kongchang Zhou, Tingyu Zhang, Wei Chen, and Fang Kong. Hybrid combinatorial multi-armed bandits with probabilistically triggered arms. arXiv preprint arXiv:2512.21925, 2025.

Citation

MLA

Li, B., et al. “Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift”. arXiv, 2026, http://arxiv.org/abs/2605.10289v2.

APA

Li, B., Fu, Y., Chen, W., & Kong, F. (2026). Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift. arXiv. http://arxiv.org/abs/2605.10289v2

Chicago

Li, B., Y. Fu, W. Chen, and F. Kong. 2026. “Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift”. arXiv. http://arxiv.org/abs/2605.10289v2.

Harvard

Li, B. et al. (2026) “Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2605.10289v2.

Vancouver

1. Li B, Fu Y, Chen W, Kong F (2026) Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift. arXiv

BibTeX

@article{li2026sample,
  title = {Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift},
  author = {Li, Bochao and Fu, Yao and Chen, Wei and Kong, Fang},
  year = {2026},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2605.10289v2},
  eprint = {2605.10289}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Offline-to-Online Multi-Armed Bandit Formulation with Bounded Distribution Shift

Knowl 2 — Sample-Mean Anchored Thompson Sampling (Anchor-TS)

Knowl 3 — Regret Upper Bound of Anchor-TS under Distribution Shift

Knowl 4 — Median-of-Three Aggregation Mechanism for Robust Posterior Sampling

Knowl 5 — Right-Hand Shift of the Hybrid Posterior Distribution

Knowl 6 — Halved Leading Regret Constant of Median-Based Thompson Sampling in Pure Online Settings

Knowl 7 — Empirical Superiority of Anchor-TS in Unbiased Offline-to-Online Regimes

Knowl 8 — Empirical Robustness and Scalability of Anchor-TS under Biased Offline Data

References

Citation

BibTeX

Access the Paper