Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

Abstract

Transfer learning in stochastic multi-armed bandits is typically studied assuming that prior data forms a fixed offline dataset or is generated by a known source. In practice, historical observations come from a previous adaptive decision process whose policy is unknown. We study this setting for bounded rewards in $[0,1]$. Before the online game starts, the learner receives, for each arm $k$, $N_k^{\prime }$ observations drawn i.i.d.\ from an unknown distribution ${\nu }_k^{\prime }$, collected by an arbitrary and possibly data-dependent strategy, so the sample sizes $N_k^{\prime }$ may be random. Source and target means satisfy $|{\mu }_k-{\mu }_k^{\prime }|<L_k$ for known constants $(L_k{)}_k$. We derive an asymptotic problem-dependent lower bound and propose KL-UCB-Transfer, which combines online and historical data and achieves logarithmic regret with an improved leading constant whenever ${\mu }_a^{\prime }<{\mu }_1-L_a$, and recovers the classical KL-UCB guarantee otherwise. Since bounding the source-target discrepancy is often unrealistic, we relax the assumption to the one-sided condition ${\mu }_k-{\mu }_k^{\prime }<L_k$ and show that logarithmic regret can survive under misspecification, characterizing three regimes ranging from improvement to a degraded logarithmic bound to a loss of guarantee. Simulations illustrate the practical benefits of exploiting process-generated historical data.

50 pages, 4 figures