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

Adrien Prevost; Timothee Mathieu; Waris Radji; Odalric-Ambrym Maillard

cs.LGOct 15, 2026

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

Authors: Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard

Organizations: Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France

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.

Figures & tables

Work	Source data	Link source-target	Source policy
Bayesian	Prior distribution	Bayesian prior	—
Contextual	Offline samples	Context	Fixed offline
Causal	Offline samples	DAG	Fixed offline
Cooperative	Online interaction	Same environment	Known
Fixed-size transfer	Offline samples	Mean discrepancy	Fixed offline
Ours	Offline samples	Mean discrepancy	Unknown (adaptive)

Table 1: Representative transfer learning settings in stochastic bandits.

Panel of Figure 1 — Figure 1: Regret regimes of KL-UCB-Transfer as a function of the effective transfer level $\mu^{\prime}_{1}+L_{1}$ from theorem 5 .

Source	$\mu^{\prime}$	$L$	Informative for	Role
$1$	$(0.58,0.47,0.42,0.32)$	$0.05$ (all arms)	all $a$	strong source
$2$	$(0.58,0.56,0.44,0.34)$	$0.07$ (all arms)	$a\in\{3,4\}$ only	moderate source
$3$	$(0.5,0.63,0.5,0.48)$	$0.15$ (all arms)	none	uninformative source

Table 2: Parameters for the source prior

Figure 2: Cumulative regret of KL-UCB-Transfer vs. KL-UCB , well-specified regime. Left:

N^{\prime}_{a}=500

for all

a

. Right: prior generated by a KL-UCB run on

T^{\prime}=2000

rounds.

Regime	$\mu^{\prime}_{1}$	$\mu^{\prime}_{1}+L_{1}$	Guarantee (arm $a=2$ , $\mu_{2}=0.5$ )
Well-specified	$0.58$	$0.63$	log-regret, best constant ( $0.63>\mu_{1}=0.6$ )
Mildly misspecified	$0.49$	$0.54$	degraded constant ( $0.54\in(\mu_{2},\mu_{1})=(0.5,0.6)$ )
Severely misspecified	$0.40$	$0.45$	none ( $0.45\leq\mu_{2}=0.5$ )

Table 3: Parameters for the three regimes of Theorem 5

Figure 3: Cumulative regret of KL-UCB Transfer vs. KL-UCB on the 3 regimes of Theorem 5 . Left:

N^{\prime}_{a}=500

for all

a

. Right: prior from a KL-UCB run on

T^{\prime}=2000

rounds.

Figure 4: Cumulative regret of KL UCB-Transfer vs. KL-UCB , prior samples only on arm

1

N^{\prime}_{1}=1000

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 348 papers

May 1, 2026

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization Bandit Learning

Ask PDF

Mar 2, 2026

Stochastic Multi-Armed Bandits with Limited Control Variates

Motivated by wireless networks where interference or channel state estimates provide partial insight into throughput, we study a variant of the classical stochastic multi-armed bandit problem in which the learner has limited access to auxiliary information. Recent work has shown that such auxiliary information, when available as control variates, can be used to get tighter confidence bounds, leading to lower regret. However, existing works assume that control variates are available in every round, which may not be realistic in several real-life scenarios. To address this, we propose UCB-LCV, an upper confidence bound (UCB) based algorithm that effectively combines the estimators obtained from rewards and control variates. When there is no control variate, UCB-LCV leads to a novel algorithm that we call UCB-NORMAL, outperforming its existing algorithms for the standard MAB setting with normally distributed rewards. Finally, we discuss variants of the proposed UCB-LCV that apply to general distributions and experimentally demonstrate that UCB-LCV outperforms existing bandit algorithms.

Arun Verma, Manjesh Kumar Hanawal, Arun Rajkumar

Singapore-MIT Alliance for Research and Technology Centre · Department of IEOR, Indian Institute of Technology Bombay · Department of DSAI, Indian Institute of Technology Madras

Multi-Armed Bandits UCB Algorithms

Ask PDF

May 6, 2026

Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels

δ\in (0,1]

, thereby characterizing the regret distribution across the full range of

δ

. We present a simple UCBVI-style algorithm with exploration bonus

\min\{c_{1,k}/N, c_{2,k}/\sqrt{N}\}

, where

N

denotes the visit count and

(c_{1,k},c_{2,k})

are user-specified parameters. For arbitrary parameter sequences, we derive general gap-independent and gap-dependent distributional regret bounds, yielding a principled characterization of how the parameters control the trade-off between expected performance, tail risk, and instance-dependent behavior. In particular, our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes. As a special case, for multi-armed bandits with

A

arms and horizon

T

, we obtain a distributional regret bound of order

\mathcal{O}(\sqrt{AT}\log(1/δ))

, confirming the conjecture of Lattimore & Szepesvári (2020, Section 17.1) for the first time.

Harin Lee, Min-hwan Oh

University of Washington · Seoul National University

Multi-Armed Bandits Regret Minimization in RL UCB Algorithms Model-Based RL

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

Trading off rewards and errors in multi-armed bandits

Stochastic Multi-Armed Bandits with Limited Control Variates

Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning