Transfer learning improves decision making with unknown prior policies
Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds
Machine Learning
Summary
When making decisions based on past experience, the past data often comes from an unknown way of choosing, not a fixed recipe. The authors study how to use such unpredictable past data to make better choices now. They create a method called KL-UCB-Transfer that mixes past and new data to reduce mistakes over time. They also analyze when and how this helps, especially if past and current situations differ in certain ways. Their tests show practical benefits from using historical data generated by unknown decision processes.
What this means in practice
- •For online advertising teams: Improve real-time ad selection by leveraging historical user interaction data collected from unknown prior algorithms.
- •For recommendation system engineers: Enhance recommendation quality by combining legacy user feedback from previous unknown policies with new interaction data.
Authors
Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard
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$ observations drawn i.i.d.\ from an unknown distribution $ν'_k$, collected by an arbitrary and possibly data-dependent strategy, so the sample sizes $N'_k$ may be random. Source and target means satisfy $|μ_k-μ'_k|<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 $μ'_a<μ_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 $μ_k-μ'_k<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.