Abstract
This paper introduces a formal framework for Best Arm Identification (BAI) in a transfer learning context, termed Additive Transfer Bandits. In this setting, a learner seeks to identify the optimal arm in a "target" environment by sampling arms in a related "source" environment, where the relationship between the two is defined by a known additive transfer function. The authors propose the Transfer Lower Upper Confidence Bound (T-LUCB) algorithm, providing rigorous theoretical guarantees for $(\epsilon, \delta)$-correctness. A key contribution is the demonstration that the sample complexity of T-LUCB is independent of the number of target arms, allowing the framework to generalize to complex combinatorial problems where the target space may be exponentially large.
Introduction
In the traditional Multi-Armed Bandit (MAB) problem, a learner interacts directly with an environment to identify the arm with the highest mean reward. However, many practical applications—ranging from clinical trials to "sim-to-real" robotics—present a significant constraint: sampling the environment of interest (the target) is often prohibitively expensive, ethically complex, or physically impossible. Instead, researchers often rely on a "source" environment (e.g., animal models or computer simulations) to make inferences about the target.
While heuristics for bridging this gap are common, "Best Arm Identification under Additive Transfer Bandits" provides a solid theoretical foundation for this process. The paper focuses on the BAI problem where the means of the target arms are linked to the means of the source arms through a known additive structure.
The Additive Transfer Framework
The authors define a transfer function $f$ that maps source means $(\mu)$ to target means $(\nu)$. The core of the framework is the additive setting, where the mean of each target arm $a$ is represented as a sum of functions of the source arms:
$$\nu_a = \sum_{i=1}^S f_{a,i}(\mu_i)$$
This structure is powerful because it allows the uncertainty of a target arm to be decomposed into the individual uncertainties of the source arms. This decomposition is the engine behind the paper's proposed algorithm.
The T-LUCB Algorithm
To solve the transfer problem, the authors introduce Transfer Lower Upper Confidence Bound (T-LUCB). The algorithm operates through four primary mechanisms:
- Confidence Sequences: The algorithm maintains time-uniform confidence intervals for each source arm based on observed samples.
- Target Mapping: These source intervals are projected through the transfer function $f$ to construct Lower Confidence Bounds (LCB) and Upper Confidence Bounds (UCB) for all potential target arms.
- Sampling Rule: In each iteration, the algorithm identifies the two most "competitive" target arms (the one with the highest LCB and the one with the highest UCB among the rest). It then samples the source arms that contribute the most to the uncertainty of these two target candidates.
- Stopping Rule: T-LUCB terminates when the LCB of the perceived best target arm exceeds the UCB of all other target arms by a specified margin, ensuring high-confidence selection.
Theoretical Insights and Generalization
A significant theoretical finding is that the sample complexity of T-LUCB is independent of the number of target arms ($T$). This is particularly relevant for combinatorial pure exploration, where the number of target configurations (e.g., all possible subsets of arms) can grow exponentially. By focusing on the source arms, the algorithm avoids the "curse of dimensionality" inherent in the target space.
Furthermore, the paper demonstrates that this framework is a unifying one. Many classic bandit problems can be recovered as special cases of additive transfer:
- Standard BAI: Where source and target arms are identical.
- Top-K Identification: Identifying the $K$ best arms in a set.
- Thresholding Bandits: Identifying all arms whose means exceed a specific threshold.
- Combinatorial Pure Exploration: Finding the best subset of arms under specific constraints.
For the specific case of Linear Transfer (where $\nu = A\mu$), the authors provide concrete complexity bounds that scale with the sparsity and scale of the transformation matrix $A$. While T-LUCB is a general-purpose algorithm, the authors note a "price of generality": it may be slightly less efficient (e.g., by a factor of $K^2$ in Top-K problems) than algorithms specifically optimized for a single task.
Conclusion and Future Work
This research provides a rigorous path forward for decision-making in environments where direct observation is impossible. By proving $(\epsilon, \delta)$-correctness and providing explicit sample complexity bounds, the authors move transfer bandits from heuristic-based approaches to a principled theoretical domain.
However, several avenues for future research remain. The current framework assumes the transfer function is known exactly; in many real-world scenarios, this relationship must be learned or is only approximately known. Additionally, extending the model to allow for "hybrid" sampling—where target arms can be sampled at a higher cost than source arms—would further increase the framework's applicability to complex experimental design.
Summary updated