Learning Across the Gap: Hybrid Multi-armed Bandits with Heterogeneous Offline and Online Data
Authors: Qijia He
Minghan Wang
Xutong Liu
Zhiyong Wang
Fang Kong
Venue: NeurIPS 2025 poster ()
Keywords: online learning
multi-armed bandit
dueling bandit
hybrid feedback
Primary area: theory

Abstract: The multi-armed bandit (MAB) is a fundamental online decision-making framework that has been extensively studied over the past two decades. To mitigate the high cost and slow convergence of purely online learning, modern MAB approaches have explored _hybrid_ paradigms that leverage offline data to warm-start online learning. However, existing approaches face a significant limitation by assuming that the offline and online data are homogeneous—they share the same feedback structure and are drawn from the same underlying distribution. This assumption is often violated in practice, where offline data often originate from diverse sources and evolving environments, resulting in feedback heterogeneity and distributional shifts. In this work, we tackle the challenge of learning across this offline-online gap by developing a general hybrid bandit framework that incorporates heterogeneous offline data to improve online performance. We study two hybrid settings: (1) using reward-based offline data to accelerate online learning in preference-based bandits (i.e., dueling bandits), and (2) using preference-based offline data to improve online standard MAB algorithms. For both settings, we design novel algorithms and derive tight regret bounds that match or improve upon existing benchmarks despite heterogeneity. Empirical evaluations on both synthetic and real-world datasets show that our proposed methods significantly outperform baseline algorithms.

Learning Across the Gap: Hybrid Multi-armed Bandits with Heterogeneous Offline and Online Data
Qijia He
Southern University of Science and Technology heqj2021 @mail. wus.esh.shehhh...... edu. cn
Minghan Wang
Xutong Liu
Southern University of Science and Technology (25322576mail) sustech, edu. cn
University of Washington xutongl@u edu
Zhiyong Wang
Fang Kong"
The University of Edinburgh zhiyonganngzzyggaal.. com
Southern University of Science and Technology kongf @ongffsustech.. edu. cn
Abstract
The multi-armed bandit (MAB) a fundamental online socision-mmaing frame- work that has been extensively studied the past two decades. To mitigate the high cost and slow convergence of purely online learning, modern MAB ap- proaches have explored hybrid paradigms that leverage offline data warm-start online learning. However, existing approaches face a significant limitation by assuming that the offline and online data are homogeneous- share the same feedback structure and are drawn from the same underlying distribution. This assumption is often violated practice, where offline data often originate from diverse sources and evolving environments, resulting in feedback heterogeneity and distributional shifts. In this work, we tackle the challenge of learning across this offfine-onling gap by developing general hybrid bandit framework that incor- porates heterogeneous offline data improve online performance. We study two hybrid settings: (1) using reward-basse based offline data to accelerate online learning preference-basee bandits (i.e., dueling bandits), and (2) using preference- based offline data to improve online standard MAB algorithms. For both settings, we design novel algorithms and derive tight regret bounds that match or improve upon existing benchmarks despite heterogeneity. Empirical evaluations on both synthetic and real-world datasets further show the superior performance of our proposed methods over baseline algorithms.
Introduction
The multi-armed bandit (MAB) problem a fuuddamental online sequential decision-making frame- work that has been extensively studied over the past two decades (Lattimore and Szepesvári 2020). In the standard MAB setting, learning agent chooses one action (i.e., pulls one arm) at each round and receives a stochastic reward (absolute value) feedback. The goal of the agent is to maximize the cumulative reward over time by balancing exploration and exploitation. This framework has been widely applied in domains such online advertising, recommendation systems, and information retrieval (Bouneffouf and Rish 2019).
"Corresponingg author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To deal with the limitations of cold start problem (Bubeck et al. 2009) in online learning and the bias absolute feedback (Wirth and Fürnkranz 2013). two extensions of MAB have been proposed: The first is the warm-start bandits (Li et al. 20T0), where the agent can access historical offline data before online deployment. The second is the dueling bandits framework (Yue et al. (012). where feedback is provided as stochastic preference between two selected arms rather than stochastic rewards.
However, existing warm-start bandit studies-whether under stochastic or dueling settings-typiclll assume that offline data and online feedback share the same data structure (Oetomo et al. 2023
Cheung and Lyu 2024 Zhang et al., (2019) (e.g., both provide either stochastic rewards or preference comparisons). But real world scenarios, two types of data usually coexist. For example: Recom- mendation systems may combine offline explicit ratings with online pairwise comparison feedback (Zhang al. 2020), and reinforcement learning Robotics frequently use offline preference-ranked trajectories with online reward signals from environmental interactions (Brown et al. 2019). Further- more, existing methods often overlook the potential distributional shift between offline and online
data (Bu et al., 2020 Hao al. 2023). This raises a natural but fundamental research question:
How can we effectively leverage heterogeneous offline data with potential bias accelerate online bandit learning?
To answer the above questions, made the following key contributions:
This work investigates the MAB problem under both absolute and relative feedback settings, considering two transition scenarios: from relative to absolute feedhack, and from absolute to relative feedback. The framework captures the offline-to-online transition, where offline data can be biased or distributionally shifted. Addressing this framework could significantly enhance the flexibility in the choice offline data. To the best of our knowledge, this is the first work to propose and analyze such a hybrid MAB setting combining offline-online heterogeneous feedback.
Problem Formulation:
The central challenge lies in effectively integrating these heterogeneous types of data while mitigating bias inherent in the offline dataset. To tackle this, we propose novel hybrid estimator that leverages absolute feedback enhance the learning efficiency of preference-based models, along with a valid bias bound that quantifies the extent of distributional shift. Under the two settings, we propose HybUCB-AR, which integrates offline absolute data with online dueling bandits, and HybElim UCB-RA which combines offline preference data with online stochastic bandits. While the hybrid estimator enables effective combination of offline data, the pessimistic bias bound allows selective utilization of offline data, ensuring performance aligns with classical MAB algorithms when offline data is uninformative.
Algorithm Design:
We provide a rigorous and comprehensive regret analysis for both algorithms, including instance dependent regret upper bound, instance independent regret upper bound, instance dependent regret lower bound and instance independent regret lower bound. To be specific, for HlyUUB--AR, and HybElimUCB-RA we derive a instance-dependent regret upper bound of
Theoretical Analysis:
(A, A1)) log max A? A3}
log T
Saving
and o Σ
Saving
A
respectively, where the "Saving" term quantifies the benefit derived from offline data. We provided a tighter and precise analysis compared to Cheung and Lyu (2024), with a new discovered "intermediate phase" where the existence of "Saving" is both determined by offline sample size and distribution shift. A key insight in HybUCB-AR is that, by maximizing informative pairs within the confidence set, we improve the RUCB bound Zoghi et al. (2014) by replacing the denominator min A3) with max A?, A3}.
Empirical Validation: Finally, we conduct extensive experiments on both synthetic and real-world datasets. HybUCB-AR outperforms RUCB by 15% to 40%. Both algorithms outperform sfate-of-the- art online baselines when leveraging offline heterogencous data, demonstrating their effectiveness.

---

2 Related Work
Our work is closely related to research on multi-armed bandits, dueling bandits, and bandits with offline data. Below, we provide brief overview of the relevant literature. A detailed comparison with closely related works is presented in Appendix B
Multi-armed Bandits and Dueling Bandits The concept of Multi-armed Bandits (MAB) was first introduced in Robbins (1522) and has since been extensively studied (Bubeck et al. 2009 Karnin et al. 2013; Slivkins et al. 2019 Lattimore and Szepesvári] (020). Building on this foundation,
dueling bandits were proposed as variant of MAB to model settings where only relative feedback between pairs of actions is available (Yue and Joachims 2011 Yue et 2012). This framework has gained increasing attention due to the prevalence of preference-basct feedback in practical applications such as recommendation systems and reinforcement learning from human feedback
(RLHF) (Zhao et al. 2016 Christiano et al. 2017 Wirth al.
2017). Early works dueling
bandits focused on fundamental algorithms and theoretical guarantees (Urvoy et al. 2013 Zoghi
et al., 2015; Dudík et al., 2015 Komiyama et al., 2016 Chen and Frazier 2017). More recent
research has expanded the framework to various settings such as acceleration in multi-user settings
Wang et al. (2025b), robustness to corrupted feedback (Agarwal et al. (021), best-of-both-wool
guarantees (Saha and Gaillard 2022), adversarial environments (Saha et al. [202)) ) and delayed or
biased feedback eY al.] (024)). Despite extensive literature on multi-armed and dueling bandits, few studies have explored hybrid settings where agents leverage both absolute and relative feedback simultaneously. The closest work by Wang et al. (2025a), who proposed a framework that allows the agent to access both types of feedback in each round. However, their setting differs from ours, as it does not consider either offline data or potential bias.
Bandits with Offline Data Multi-armed bandits (MAB) with offline data have been studied in several prior works. Early approaches, such as those by (Shivaswamy and Joachims (2012) and Banerjee et al. (022),, primarily assumed that the offline and online environments share the same distributions, and assume homogeneity between offline and online data -itherr both are stochastic or relative (Bu et al. 2020 Hao et al. 2023 Gur and Momeni (0022). Only recently have researchers started addressing the challenge of biased offline data (Zhang et al. 2019 Agnihotri et al. [0224] Cheung and Lyu 2024| Qu et al. 2024). Other studies, such as Sentenac et al. (2025), examine the tradeoff between online exploration budget and offline sample size. But works of heterogeneous offline-online feedback remains understudied, with only recent works making preliminary progress. Xia et al. (2024) investigated hybrid data for linear bandits, albeit without theoretical guarantees, while Agmihotri et al. (2024) adopted a Bayesian posterior approach for the same setting. However, under the MAB framework, none of the previous works simultaneously address both heterogeneous offline data and potential distributional bias-a critical gap our work bridges for the first time.
3 Preliminaries
In this paper, we propose hybrid multi-arma bandit (MAB) framework designed to enhance the efficiency of online learning by incorporating offiine heterogeneous data with potential bias. The problem is formulated arm set A is (1,2....,K') K).
K-armed bandit model, where K 24 is the number of arms, and the
Initially, focus scenario in which the agent explores its preferences using relative feedback by selecting pairs of arms during the online interaction process, while the offline data provides absolute feedback. Another scenario involving heterogencous feedback will be provided later.
The learning agent sequentially interacts with the environment for T E Z+ time steps. At each step E (T), the agent selects pair of arms (t)(t), , Az (t)), and receives pairwise comparison feedback. For simplicity, if the selected pair is (a;, a,), the agent receives the feedback (t, with denoting a, wins aj and 0 vice versa. For the preference model, we follow the widely adopted Bradley-Terr (BT) model (Yue et al.] 2012; Sun et al. 2024 Zhu et al. 2023 Dong et al., 2024) to characterize the winning probability. Specifically, let μ4 denote the expected reward of arm during the online
3

---

process. The winning probability of arm over aj is
exp (p
Pij 014 (1")) exp (1QTT) + exp (129m)
where ar (.) denotes the logistic sigmoid function. The comparison result , can be regarded as Bernoulli random variable with expectation pi.- Following prior works (Zoghi et al. 2014 Chen and Frazier 2017; Saha and Gaillard 2022). we assume the existence of a Condorcet winner an arm that is preferred over all other arms. Without loss of generality, we assume this to be arm d1, which satisfies p 1/2 for j 1.
The agent typically possesses a substantial amount offline data, such as historical user click data in recommendation system (Cheung and Lyu 2024 Bu et al. 2020 Agnihotri et al. 2024). However, the format of these data may not be entirely consistent with the online tasks. For instance, offline data may exist in the form of absolute click feedback, but the online task aims identify the relative preference of the users. Besides, the changes user preferences may lead to differences in expected rewards between offline and online environments. To characterize this phenomenon, we consider that the offline data set contains heterogencous feedback from the online task. Specifically, for each arm denote the number of offline observations associated with arm The offline data set D = {it, x,,)) E [K],k k E [Ni]] consists of absolute feedback from the arms, where X, is assumed to be 1- l-subgaussian with expectation n.a"" Further define {pr [ije((]] as the preference value derived from )e(") under the BT model.
i [K] let N;
The objective of the agent is to maximize its cumulative reward over given horizon T by effectively utilizing the heterogeneous feedback available in the offline dataset. Equivalently, this objective can be framed as minimizing the cumulative regret:
T Σ
AAi(e) + A A2(0)) ).
Reg =
2
where the expectation is taken over the randomness of the agent's policy, and A == Pf,; denotes the sub-optimality gap of arm i [K].
3.1 Alternative Setting: Stochastic Bandits with Offline Relative feedback
In some applications such as recommendation system Silva et al. 2022). robotics (Nemlekar et al. 2023 Brown et al. 2019) and RLHF (Das af., (024), the learning agent tasked with making decisions providing recommendations and observes absolute feedback, such as whether the user accepts or rejects a given option. However, the offline dataset often consists of relative feedback because, during the "hot start" phase when new user first arrives, many platforms gather information through relative preferences rather than absolute ratings. In this scenario, users are typically asked to express their preferences between pairs of options, such as choosing between two different alternatives. So we further consider the learning task where the online agent is faced with stochastic bandits but with access to offline data set consisting of relative (pairwise) feedback.
In this setting, the online interaction process follows the standard stochastic bandit formulation. At each time step i, the agent selects arm A(t) and receives stochastic reward X (t)) which is assumed to be I-subgaussian with mean AA())
The agent additionally has access to an offline dataset D = (i.j, i, E [K], E N., where Ni, denotes the number of recorded comparisons between arms a; and a; and Y, Vi represents the k-th comparison outcome. Following prior works on relative feedback (Yue et al., 2012 Ji al. 2023). we assume the comparisons are generated according to the BT model. That is, Yijjk is Bernoulli random variable with mean paff a(ugft -1gf).
Without loss of generality, we assume arm di is the optimal arm in the online setting, i.e., u > p for all E [K]. To ensure consistency in our definitions throughout the paper, we define the sub-optimality gap for each arm as A, = Pı: = ( 144) 2 The agent aims to minimize the cumulative regret over the online horizon by leveraging information from the offline dataset.

---

Specifically, the regret is defined as:
Reg (T) E
A A(t)
where the randomness is taken the stochastic rewards of the arms.
For notational convenience, throughout the remainder of the paper, we continue to use the 'off" superscript to indicate quantities derived from offline data, and omit the 'on' superseript where ambiguity arises.
4
Dueling Bandits with Offline Absolute Feedback
In this section, we present HybUCB-AR for the dueling bandits with an offline data set consisting of absolute feedback.
4.1 Algorithm
Constructing a reliable estimator for the utility each arm is essential for effective learning in the hybrid bandit problem with heterogeneous feedback considered in this work. Since dueling feedback provides only relative information among arms, directly estimating the absolute utility of individual arms based on relative data remains challenging task. To leverage the offline dataset containing absolute feedback, we transform its data format into a unified relative feedback type. For data collected during online interactions, it is natural to estimate the relative preference of arm a; over arm as Pt.j = E Y.J,,/TT,, For the offline dataset, we apply the Bradley-Terry (BT) model to construct estimation of pt. P a (Att ") where po k= X.&/N, is the empirical mean the offline data set.
The key challenge is to integrate these two heterogeneous sources of feedback into single estimator that maximizes information utility while maintaining unbiasedness. To this end, we construct the Minimum Variance Unbiased Estimator (MVUE) for Pr, by optimally combining empirical observations from both sources. Specifically, since Pt,j is 1/ //T. -....auuuuauaussin with mean Ps.j+ P.. / + / / //(NNN, subbuasssan with mean p... and pr.j- p.j are independent of each other,
.hyb we construct Pi.j as
N.N,
Pij
hyb
Ts N.N, N,+N,
D.s
N.+N, N.N, Pig. Th N++N,
T
which is 1/V4(T.,) N,N,,(NNN,NNN N. Gaussianity deferred to Appendix C.I
The proof of the sub- subgaussian with mean Pij"
hyb
Due to the distributional mismatch in rewards between the offline data set and online setting, directly applying such hybrid estimator may lead the offline data bias adversely affecting the online learning process. To mitigate this issue. the reward estimator for each arm should explicitly account for the potential bias present in the offline data. Inspired by Cheung and Lyu (2024). we introduce a hyper--paaee parameter Vi,j to characterize the difference in the offline and online reward distributions. Specifically, Vi,j plays the role of an upper bound for P Pi.j. where
Vi 2
off P.j piul. for each arm pair (a,, a,) E A.A.
The quantity Ve, serves as an upper bound on the amount of distributional shift from offline to online. In the extreme case, setting Vi, In contrast, Vi, < imply nontrivial prior knowledge regarding the difference Ir Pi.jl tighter bound leads to better utility of the offline dataset.
corresponds having no additional knowledge about the shift.
Remark 1. In practice, directly computing V., is often challenging. as the probabilities Pi.j. Pi.k- and Pj.k typically dependent espeecaalyy when the number of arms K is large. When Va, is unavailable for all i.j [K], we instead require that V, 2 11t - - Vi E [K]. and define the pairwise term as Vt, = oV.++ VJ). The justification for this construction is provided in Appendix C.2
5

---

The construction of HybU'B-AR is based on the upper confidence bound (UCB) estimators. Specifi- cally, we can construct two UCBs for each arm pair (at, aj) based on the pure online data and the hybrid offline and online data as below:
log(1/6.)
UCB(a, a4) Pis + -2
(3)
2
N. N.+N, V Th. + NetN
log(1/82) N.N, 2 + N.v,,
UCB (at, ag)
phyb =
(4)
N.N,
We will later show in Appendix C.3 that both UCBs represent upper bound estimates on the real online reward Pi,j. i... Pi. I (a, az), UCB a,)} with high probability. However, they reflect different levels of reliance on the offline data. When the offline data is highly informative and the variance term Vi,j is small, the hybrid UCB provides a tighter upper bound. Conversely, when the offline data is less informative, the online-only UCB offers more reliable upper bound estimate.
Algorithm 1 HybUCB-AR (Hybrid UCB: Offline Absolute Online Relative)
Require: Arm set A, offline dataset D = {(i, : [K] E [Ni]], hyperparameter 8, and estimated bias Vi, for all (a,, aÿ) pairs.
Initialization:
for all as aj E E do
2: Tij 0.
b Number of comparisons between and aj
3: UCB a,) +00.
4:
UCB (a;; (Q::a;) = o of fffff (1 +
log(1/6)) 2(NNN)/(N++N;)) + V1.j-
5: end for
6: for t= to T do
7:
Construct candidate sets:
1 C₂ {a; E A UCB (a,, a,) 2 Va, E EA},
(5)
c..s {a, E E UCB (a:, ag) 2 Va, E A}.
(6)
2'
C. = C n nily clyb
8:
9:
if C. + 0 then
10:
At))) arg maxo, EC, min( 0,) (ii) a,)),
11:
else
12:
(t), arg maxa,,yee EA min(UCB((,, a;), UCB (a; az)l end
13:
Select the pair (A),)), A2()).
15:
Update the selection times (0) 1,,
16: Record the observation YiJ.: and Y,,,, e for = A2()), = T (1).
17: For all pairs j E [K]. update UCB, UCB according to equation 33 44
end for
In general, the core idea of HybUCB-AR is construct candidate set of optimal arms and to explore the arms within this set that have the highest UCBs. To fully leverage the advantages of offline data while mitigating the impact of bias, we employ both hybrid UCB and purely online UCB for constructing the candidate set and selecting arms. Specifically, the candidate set includes all arms that could potentially be optimal. Therefore, once an arm defeated by another- -.e. its corresponding hy UCB or pure online UCB falls below 1/2 1/2-it is removed from the candidate set (Line 8h. After constructing the candidate set, the agent would select the arm pair with the highest min UCB (a, a,), UCB (a,, a,)} (Line 9-12).
4.2 Theoretical Results
In this section, we provide the regret upper bound for HybUCB-AR and the corresponding lower bound for the problem.

---

Theorem 1. Choosing òG 2k(K+1) the regret of HybUCB-AR satisfies: (a) Instance-dependent bound:
A + ココ i
log max A A
N,N
max {max [i, Aj} Awi. 0F
2
N4 + N
max ( ii
(aving(a..n,)
where Wi.j Vi.j + + Pig with Vig 1o Pi.l- (b) Instance-independent bounds:
o (min V V log Saving(a;, ay),
(Vonn max Vis
$51
where Ta is the optimal solution the following linear program:
maX TA
T
N,N, +44s
subject
Vi,j [K],
N N₂
=T,
iSJ
T T 0, 4. 20
In Theorem 7 we have provided two versions of mustance-indepente bound. The first is an extension of depende-d bounds, while the second combines the saving term with the term proportional to T. According to the linear programming formulation in (7.. the effect of offtine data maximized when the offline data are uniformly distributed and decreases as the offliee data become highly skewed, especially when T is relatively small. This achieves similar result to Sentenac et al. (025).
Remark 2.
Remark 3 (Saving). The complete proof is deferred to Appendix C.5 From the instance dependent case, it is obvious that the effectiveness of offline data is summarized in the "Saving" term. First, note that the Saving is always non-negative. When the condition Awa,j max Dj} holds for all j E A. the total Saving become zero, and the result degenerates to the pure online regret upper bound. In contrast, when max (i A.) > Awi.j the offline data becomes beneficial. Specifically, this implies either (i) the offline and online distributions are sufficiently close such that the bias is small, or (ii) P.. This aligns with our intuition that small distribution bias leads greater utility of offline data, and the bias created by the distributional shift could be neutralized if the shift direction is well-predicte Furthermore, under the second condition (that is, max D,, A,) 4wi,j,). ). the Saving proportional to the harmonic mean of the offline sample sizes, namely N,Nz/(N: + +NN). This value is maximized when the offline data for N; and N; is uniformly distributed, which is consistent with our discussion of the instance instance-independe independent bound in Remark 2 A more precise and comprehensive analysis of the Saving, including the "intermediate phuse", deferred to Appendix C.6
off < Pt.j, so the direction of the distributional shift is correctly estimated by V1.--
Corollary 1. V1, 0 and the offline data uniformly distributed such that N; n. for all i E [K), then the regret upper bound simplifies to:
0 11). and o
( 2K(K +1)T2 log RK(K + 4T
A + +
log
71
max
max A A3)
respectively. Under this setting, the contribution of offline data regret reduction is captured by the terms - and nK(K 1), respectively. As the amount of offline data becomes sufficiently large, the regret upper bound approaches constant.
7

---

Remark 4 (Comparisons with homogeneous offline data). Under this setting, a natural ques- tion arises: Compared homogeneous offline data (absolute feedback), is heterogeneous of- fline data (preference feedback) less informative or harder to leverage? For HybUCB-AR, if we replace the offline stochastic data with preference feedback, the resulting hybrid estima- for Pi.j would depend on a confidence radius of v1/2-
+ N.g). rather than NNN + N2)) in equation + This suggests that preference data
/1/2 log(1/5.)/(I, can yield a tighter bound for a given pair (i.3) under the same amount of data. However, this result critically relies the Bradley-Ters model and the 1-subGaussian assumption. As shown in Appendix [ transforming stochastic data into relative data via the BT model enlarges the esti- mation variance, and such variance misalignment directly impacts the ulility of heterogeneous data. these assumptions are altered, the subGaussian properties of the estimator P... under stochastic feedback may also change, potentially leading to different concentration behaviors or confidence bounds. Despite this, as the number of arms K grows, stochastic data will eventually provide more information, since each stochastic sample X; can be jointly utilized to estimate pairwise preferences across all arms, whereas preference feedback only provides information about the specific pair (i. being compared.
Finally, we establish the regret lower bound of the proposed algorithm, whose analysis relies on the definition of Cp-consistency, which is a generalization to the consistent policy in stochastic bandits (Lai and Robbins 1985).
Definition 1. For C > O, E (0,1) and a collection I of instances, an Algorithm is said to be Cy-consistent on I, for all I holds that Reg(T) S CTP.
Corollary 2. Define Iv be collection of instance satisfies V; 2 1190-1ul for all i E [K]. By Theorem 7 and Definition HybUCB-AR is Cp-consistent on Iv.
Theorem 2 (Regret Lower Bounds). (a) Instance-dependee
bound: Let V be arbitrary bias bound, and let A (0. 3) be the gap between the optimal arm and all suboptimal arms. For all I Iv. the regret of HybUCB-AR satisfy the following lower bounds:
K 4A
(1-
A 64C
Σ
max
wi, 03 N;
4A
2
EE[R]
where C, are constants from Definition and wi = VG + س 44 with V; 2 11 usl- (b) Instance-independee bound:
Let Vmaxx be fixed and arbitrary, and let V; = Vmma for all i E [K]. then there exists a Gaussian instance I E Iv satisfying the following regret lower bound:
Ω min (KTT, (V==+ + Vinas } -7)
(8)
where T,, is the optimal solution to the following Linear Programming problem:
max T's
T'
subject to
Vie [K], Σ 4=
< 4, + N
0, 4 2
EE[R]
The proof of Theorem 2 deferred to Appendix D.I and D.2 Both the gap-dependent and gap- independent lower bounds closely match the regret upper bound provided in Theorem [ In particular, for the special case where N; = n and A; = A, we show in Appendix bounds differ by at most factor of K. Notice that the term VKT in Equation (8) does not contain "Saving", under our construction the worst case could be that the Saving is zero.
[oppedix[D.Ippp [D. that the upper and lower
5 Stochastic Bandits with Offline Relative Feedback
In contrast to the previous setting, we now consider classical MAB problem augmented with offline preference data. Due to the switch between offline and online data, we redefine pof

---

Ek Yis.k/ Pij o(A; (.j), where ir; = -i= W E [K]. and Pij opp
byb
(1 - -o)Dii. where a = Ni// T:Y, + Na.). The upper confidence bound becomes:
1og(1/6)) Tj T T
UCB(a;; =Bis + V
(9)
(1(() T:T; T:+T; + +Ne.s
Ni.
UCB byb (a;, az) = .hyb + =Pry
Ves
(10)
T:T, T,TT, + NNi
Algorithm HybElimUCB-RA (Hybrid Elimination UCB: Offline Relative Online Absolute)
Require: arm set A, offline dataset D {(,, Y,,.)), E [K], k E [Nag]], hyperparameter
6, and estimated bias Vi, for all (a;, a,) pairs.
Initialization: Let C A, T₁ = 0. vi [K]. and for all i,j [K], let UCB(a,, a,) +00,
UCB (a;; aj) - Pij V
log 1/6.
No.
1: for 1, T do
2: Select Action At)) arg min EC Ti(f).
3: Update selection times Ta()) = TA,1) +
4: Record observation i, for i = A(t), k = TT())-
5: For all pairs i,j E [K]. update UCB, UCB according to equation
(
6: C Ma; E C, 3 a, E (ar) s.t. min min(UCB(a,,
(a, (a;;a;)) UCB
7: end for
In Section 4 used absolute offline data to estimate Pt, based BT model. However, using preference data to estimate l4 is hard, as it provides less information. in HybElimUCB-RR we approach this problem by continuing using preference based estimation model, with elimination approach. In each round, we select the arm that has been played the least, and eliminate suboptimal
arm a if 3 aj E A s.t. min (UCB (a, a, UCB (a;, a₂)} < 1/2. Under the worst case where the hybrid terms provides additional information, it's performance matches the vanilla elimination UCB algorithm.
Remark 5. One might question how to align with vanilla UCB when offline data cannot provide additional information. As mentioned, estimating μ from preference data is mathematically chal- lenging due to the absence of explicit reward signals. An alternative approach is to maintain pure online UCB and hybrid UCB separately, which similar to the ElimFusion Algorithu in Wang et al. 2025a A detailed implementation of this approach is provided in Appendix
Theorem 3.
Let 8 2K(K+1)T2. The instance dependent regret upper bound of HybElimUCB-RA
satisfies:
log(T) A
2N max(A, A, 2w..1.
TE[K]
Saving(a.)
where Wi,1 == V1,1 + P1,1 P:,1 with VL, 2
off
P1.1 Pt.1l
Remark Due space limits, we defer the instance-inde instence-ineeeendentt regret bound and lower bound to Appendix E.2 and [.3] The proof of Theorem iss provided in the Appendix E.I The regret bound follows form similar to that Section 4 a larger offline dataset and smaller bias in the offline data lead to greater regret reduction. Notably, one key insight is that, under the relative to stochastic setting, uniformly distributed offline data no longer leads to good Saving. As shown in Theorem 3 the regret reduction for each suboptimal arm E [K]][1} depends critically the comparisons with the optimal arm an Specifically, offline data concentrated on comparisons with on leads to higher efficiency in the online phase.

---

Experiments
We evaluate HybUCB-AR and HybElimuCB--RA on synthetic and real-world datasets to assess their performance in hybrid feedback bandit settings. Figure presents four subpiots comparing their performance against classic bandit baselines. Specifically, for online preference setting, we compared our result with IF (uue et al. 2012) and RUCB (Zoghi et al. 20144) while for online stochastic setting we set the baseline ETC, vanilla UCB (Lattimore and Szepesvári, 2020) and Thompson Samping (Agrawal and Goyal 2013). Without offline data, HybUCB-ARK by maximizing the informative pair in the candidate set, outperforms RUCB by 15 40%. Both algorithms surpass baseline when heterogeneous offline data is included. These results highlight the robust performance of our algorithms across diverse scenarios. Details and supplemental experiments, including algorithm's performance across varying K, sensitivity to parameters, and efficacy in real-world datasets, are provided in Appendix
Syrtheric Data
Novi
Syrthericc Data
MovieLers
4000
3030
20
200.2
20:00
A002
10:00
300
20.2
0.00
10.0
1007
11.00
500 X000 300
250
13000
Figure 1: Cumulative regret comparison HybUCB-AR (left) and HybElimUCB-PP (right) against baselines. Left two subplots: HybUCB-AR on synthetic data and the Moviel dataset; right two subplots: HybElimUCB-RA on the same datasets.
7 Conclusion
This paper investigates multi-armed bandits with heterogeneous offline data, we propose a novel hybrid estimator that effectively leverages hybrid data enhance online learning, with comprehensive theoretical guarantees. This significantly expands the practical applicability of bandit frameworks by offering greater flexibility in incorporating offline data. Future directions include generalization to linear bandits and adversarial environments, as well as more flexible settings where heterogeneity exists within offline or online data.
Acknowledgement
The corresponding author Fang Kong is supported by the Guangdong Basic and Applied Basic Research Foundation 2025A1515011412.
References
Agarwal, A., Agarwal, S., and Patil. P. (2021). Stochastic dueling bandits with adversarial corruption. In Algorithmic Learning Theory, pages 217-248. PMLR.
Agnihotri, A., Jain, R., Ramachandran, D., and Wen, Z. (2024). Online handit learning with offline preference data. arXiv preprint arXiv:2400.09574,
Agrawal, S. and Goyal, N. (2013). Further optimal regret bounds for thompson sampling. Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS), 31.
Banerjec, S., Sinclair, S. R., Tambe, M., Xu, L., and Yu, L. (2022). Artificial replay: meta-algorithm for harnessing historical data in bandits. arXiv preprint arXiv:2210.00025.
Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration Inequalities: Nonasymptotic Theory of Independence. Oxford University Press, Oxford.
Bouneffouf, D. and Rish. L (2019). A survey practical applications of multi-arma and contextual bandits. arXiv preprint arXiv: arXiv:1904.100 1904.10040
10

---

Brown, D., Goo, W., Nagarajan, P., and Niekum, S. (2019). Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International conference machine learning, pages 783-792. PMLR.
Bu, J., Simchi-Levi, D., and Xu, Y. (2020). Online pricing with offline data: Phase transition and inverse square law. International Conference on Machine Learning, pages 1202-1210. PMLR.
Bubeck, S., Munos, R., and Stoltz, G. (2009). Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer.
Chen, B. and Frazier, P. (2017). Dueling bandits with weak regret. International Conference on Machine Learning, pages 731-739. PMLR.
Cheung. C. and Lyu, (2024). Leveraging (biased) information: multi- bandits with offline data, In Proceedings of the 41st International Conference on Machine Learning, pages 8286 8309.
Christiano, F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, (2017). Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30.
Das, N., Chakraborty, S., Pacchiano, A., and Chowdhury, R. (2024). Active preference optimization for sample efficient rlhf. arXiv preprint arXiv:2402.10500
Dong, H., Xiong, W., Pang, B., Wang, H., Zhao, H., Zhou, Y., Jiang, N., Sahoo, D., Xiong, C., and Zhang, T. (2024). Rlhf workflow: From reward modeling to online rlhf comprehensive practical alignment recipe of iterative preference learning. Transuctions on Machine Learning Research, 2024.
Dudik, M., Hofmann, K., Schapire, R. E.,, Slivkins, A., and Zoghi, M. (2015). Contextual dueling bandits. In Conference on Learning Theory, pages 563-587. PMLR.
Gur, Y. and Momeni, A. (2022). Adaptive sequential experiments with unknown information arrival processes. Manufacturing & Service Operations Monagement, 24(5):2666-288,
Hao, B., Jain, R., Lattimore. T., Van Roy. B., and Wen, Z. (2023). Leveraging demonstrations to improve online learning: Quality matters. In International Conference on Machine Learning, pages 12527-12545. PMLR.
Ji, X., Wang, H., Chen, M.. Zhao, T., and Wang. M. (2023). Provable benefits of policy learning from human preferences in contextual bandit problems. arXiv preprint arX1v:2307.12975
Karnin, Z., Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In International conference machine learning, pages 1238-1246. PMLR.
Komiyama, J., Honda, J., and Nakagawa, H. (2016). Copeland ducling bandit problem: Regret lower bound, optimal algorithm, and computationally efficient algorithm. In International Conference on Machine Learning, pages 1235-1244. PMLR.
Lai, T. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules, Advances applied mathematics, 6(1):422..
Lattimore, T. and Szepesvári, (2020). Bandit algorithms. Cambridge University Press.
Li, L.. Chu, W., Langford. J., and Schapire. R. E. (2010). A contextual-banie approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670.
Nemlekar, H., Dhanaraj, N., Guan, A., Gupta, K., and Nikolaidis, S. (2023). Transfer learning of human pref- erences for proactive robot assistance in assembly tasks. In Pruceedings of the 2023 ACM/IEEE International Conference on Human Robot Interaction, pages 375-583.
Oetomo, B., Perera, R. M., Borovica- Borjvica-Gaaii, R. and Rubinstein, B. L. (2023). Cutting to the chase with warm-start contextual bandits. Knowledge and Information Systems, 65(9):3533-3566
Qu, C. Shi, L.,, Panaganti, K., You, P., and Wierman, A. (2024). Hybrid transfer reinforcement learning: Provable sample efficiency from shifted-dynamics data. In The 28th International Conference on Artificial Intelligence and Statistics.
Robbins, H. (1952). Some aspocts of the sequential design of experiments.
Saha, A. and Gaillard, P. (2022). Versatile dueling bandits: Best-of-bolt world analyses for learning from relative preferences. In International Conference Machine Learning, pages 1901 190266. PMLR.
11

---

Saha, A., Koren, T., and Mansour, Y. (2021), Adversarial dueling bandits. In International Conference on Machine Learning, pages 9235-9244. PMLR.
Sentenac, F., Lee, I., and Szepesvari, C. (2025). Balancing optimism and pessimism in offlne-to--nline learning. arXiv preprint arX2222502.08255.
Shivaswamy, P. and Joachims, T. (2012). Multi-armed bandit problems with history. In Artificial intelligence and statistics,, pages 1054.1054. PMLR.
Silva, N., Wemeek, H., Silva, T., Percira, A. C., and Rocha, I.. (2022). Multi-armed bandits in recommendation systems: A survey of the ofate-of-the-rr and future directions. Expert Systems with Applications, 197: 16669.
Slivkins, A. et al. (2019). Introduction multi-armed bandits. Foundations and Trends@ in Machine Learning. 12(1-))
Sun, H., Shen, Y., and Ton, J.-F. (2024), Rethinking bradley-terry models in preference-basee reward modeling: Foundations, theory, and alternatives. arXiv preprint 1.X19:2411.09911.
Urvoy, T., Clerot, F., Féraud, R., and Naamane, S. (2013). Generic exploration and k-armed voting handits. In International conference machine learning, pages 91-99. PMLR.
Wang. X., Zeng, Q. Zuo, J. Liu, X., Hajiesmaili, M., Lui, J. C., and Wierman, A. (2025a). Fusing reward and dueling feedback in stochastic bandits. In Forty-second International Conference on Machine Learning.
Wang. Z., Sun, J., Kong, M., Xie, J., Hu, Q. Lui, J. C., and Dai, Z. (2025b). Online clustering of ducling bandits. In secty-second International Conference on Machine Learning.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. (2017). A survey of preference-bast based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46.
Wirth, C. and Fürnkranz. J. (2013). Preference-based reinforeement learning: A preliminary survey, In Proceedings of the ECML/PKDD-13 Workshop on Reinforcement Learning from Generalized Feedback: Beyond Numeric Rewards.
Xia, Y., Xie, Z.,, Yu, T., Zhao, C., and Li, (2024). Toward joint utilization of absolute and relative handit feedback for conversational recommendation. User Modeling and User-Adapted Interaction, 34(5):1707- 1744.
Yi, B., Kang, Y., and Li, Y. (2024). Biased dueling bandits with stochastic delayed feedback. Transactions on Machine Learning Research.
Yuc, Y., Broder, J., Kleinberg, R., and Joachims, T. (2012). The k-armed ducling bandits problem. Journal of Computer and System Sciences, 1865)11577-158..
Yue, and Joachims, (2011), Beat the mean handit. Proceedings of the 28th international conference on machine learning (ICMI.-II), pages 241-248.
Zhang, C., Agarwal, A., lii, H. D., Langford, J., and Negahban, S. (2019). Warm Strm-starting contextual bandits: Robustly combining supervised and bandit feedback. In International Conference on Machine Learning. pages 7335-7344. PMLR.
Zhang, X., Xie, H., Li, H., and CS Lui, J. (2020). Conversational contextual bandit: Algorithm and application. In Proceedings of the web conference 2020, pages 662-672.
Zhao, 7., Lu, H., Cai, D., He, X., and Zhuang, Y. (2016). User preference learning for online social recommen- dation. IEEE Transactions Knowledge and Data Engineering, 2809):2522-2534
Zhu, B., Jordan, M., and Jiao, J. (2023), Principled reinforcement learning with human feedback from pairwise or wiie comparisons. In International Conference on Machine Learning, pages 43037-43066 PMLR
Zoghi, M., Karnin, 7. S., Whiteson, S., and De Rijke, M. (2015). Copeland dueling bandits. Advances in neural information proessing systems, 28.
Zoghi. M., Whiteson. S., Munos, R., and Rijke, M. (2014). Relative upper confidence bound for the k-armed ducling bandit problem. In International conference machine learning, pages 10- 18. PMLR.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the Introduction Section D. we clearly listed four our main contributions: Problem Formulation, Algorithm Design, Theoretical Analysis and Empirical Validation, each of them has clear map to the content in the paper: Problem Formulation is in Section 3 Algorithm Design and Theoretical Analysis are in Section and Empirical Validation is in Section 6 Furthermore, In Section 2 detailedly discussed existed works, which matches to the brief introduction in the abstract.
Guidelines:
The answer NA means that abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theorctical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: Yes
Justification; As discussed in Section when comparing with homogencous offline data, point bbyb out that Po relics on both BT model assumption and the sub- Gaussian assumption. Furthermore, In Section [ Offline Relative Online Stochastic, our hybrid algorithm HybElimUCB- B-RA does not match vanilla UCB when offline data is uninformative. Even though provided approach in the Appendix, it's theoretical guarantee is not desired.
Guidelines:
The answer NA means that paper has no limitation while answer means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "L.imitations" section their paper.
The paper should point out any strong assumptions and how robust the results are violations of
these assumptions (c.g., independence assumptions, noiseless settings, model well-speett sell--secifiiation. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should he articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If a'applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
their best judgment and recognize
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: Assumptions are provided in [] All theorems the main text are formally proven in Appendix, with explicit pointers linking cach theorem to its proof. For auxiliary lemmas whose proofs omitted, we cite prior works (e.g.. [Author et al., Ycarl) that contain complete derivations, ensuring full verifiability without redundancy.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly refereneed.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide detailed experimental setup in Appendix G along with additional experi- mental results. Furthermore, the source code our experiment will be attached the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on contribution, reproducibility can accomplished various ways. example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g.. with an open-source dataset or instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the of gosed-source models, it may be that access to model is limited some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open faithfully reproduce the main experimental results, described supplemental material?
the data and code, with sufficient instructions
Answer: [Yes]
14

---

The paper states that source code will be provided in supplemental materials, with plans for full open access upon acceptance. The README. mdd file contains sufficient instructions for reproduction. All datasets used are publicly available, ensuring full reproducibility of the main experimental results.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines httpae////naaacccpppppeee
for more details.
While we encourage release of code and data, we understand that this might not possible,
so "Na" an acceptable answer. Papers cannot rejected simply not including code, unless this is central to the contribution (e.g., for a new open-source henchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (httpa: htap::///nia.... cc/public/ for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental sefting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand results?
Answer:[Yor Yes]
The setup and details, including the selection of hyperparameters, are provided in Appendix complete code provided in the supplemental materials.
Justification:
Guidelines:
answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [Yes]
Justification: In each plot of the result, we not only plot the means but also the error bands: In bandit experiment, we set as: Std Error / # experiments. Furthermore, provide brief report about the experiment in Section and detail information in Appendix G
Guidelines:
The answer means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI. if the hypothesis of Normality of errors is not verified.
15

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric bars that would yield results that are of range (e.g. negative If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding ligures tables in the text.
rates).
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
workstation with an AMD Ryzen Threadripper PRO 7985WX 64-core CPU (128 threads, up 5.367 GHz), 124GB of RAM, and 926GB NVMe SSD (with 761GB available), meeting the requirements for compute worker type, memory, and storage. Each experiment's setup is detailed, including the number of rounds (e.g.. 50,000 for Algorithm synthetic experiments, 10,000 for real-world experiments), trials (100 and 3), and arms (K Sto 32). The datasets small (MovieLens-22 20M 533.4 MB, Yelp at 196.1 MB, totaling 729.5 MB), well within the workstation's 's memory and storage capacity. The workstation high-performance configuration (64-core CPU, 124GB RAM, NVMc SSD) ensures efficient experiment execution, and the detailed experiment parameters allow cstimation of total compute requirements.
Justification: The paper specifies that experiments were
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, every respect, with the NeurIPS Code of Ethics https:/ http:::///eurip...o wwtpppubblc//hhicccuu...e..lllll
Answer: [Yes]
Justification: We ensure that all claims made in the paper are either rigorously proven or supported by appropriate citations. When our proofs are based on the frameworks of prior work, we explicitly acknowledge the original sources before presenting
own contributions. All individuals who contributed to the research are included in the author list. To the best of our knowledge, the rescarch does not raise concerns related to safety, security, discrimination, surveillance, environmental impact, or human rights.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain special circumstances that require deviation from Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Section we mention that this work could enhance the flexibility in selecting offline data for online learning. This has the potential to influence online algorithms used in industry by improving their robustness and overall performance.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g..
disinformation, generating fake profiles, surveillance). fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms monitor- ing misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datascts)?
Question:
Answer: [NA]
Justification: This paper primarily focuses on learning theory and docs not involve the development release of high-risk models (c.g., pretrained language models or image generators) or potentially sensitive datasets. The experiments serve only to validate our theorctical guarantees using standard, non-sensitive data (Yelp and MovieLens). Therefore, safeguards for responsible release were not necessary in this context.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners assets (e.g., code, data, models), used the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected??
Answer: [Yes]
Justification; All experimental code used in the paper was developed by the authors. For real-world experiments, we use the MovicLens and Yelp datasets. These datasets are properly cited the Appendix, and their licenses and terms of use have been respected in accordance with their respective guidelines.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL..
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppppppppaaaaaa
wwwrswiwthhhd.... com/ datasets has curated licenses for
some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that are re-packaged. both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification: This is primarily a theoretical contribution. While we include small-scale experimental validation with code provided in supplemental materials, no substantial new assets (datasets, models, or benchmarks) were created. The code merely reproduces analytical results from our theoretical framework.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, rememher to anonymize your assets (if applicahle). You can either create an anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing experiments or research with human subjects.
Guidelines:
The NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
This paper does not involve human subjects user studies, and therefore no IRB
approval was required.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and Incations, and we expect authors adhere to the NeurlPS Code of Ethics the guidelines for their institution.
For initial submissions, not include any information that would break anonymity applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs it an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the methodology, scientific rigorousness, originality of the research, declaration is required.
Answer: [NA]
Justification: We used LLMs to assist with writing refinement and to help implement the baselines compared algorithms. These uses not affect the core methodology scientific rigor our
work.
Guidelines:
18

---

The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components. Please refer to our I.I. policy should should not be described.
for what
19

---

A Notations and Models
Notation
Meaning
K
of arms arm i
ag a As
the estimated mean reward of ag offline and online respectively
our 14y
the ground truth mean reward of ag for offline and online respectively
PL.+ D
ground truth Ber(p) s.t. a, wins against a, for offline and online data respectively the estimated value of Pa, only using online data the estimated value of Pı,j using offline data the estimated value of Pt,j using offline and online data(hybrid)
Pij
Pas
A
Pi, 5. d1 refers the Condorcet winner # of times that played (ag, az) online,
Ti
especially, we use T.,, (t) to refer the of times that play (a,, aj ay)at the start of # of times that a; is selected for online comparison times that played a; in the offline dataset the kt reward of a; the k-th feedbcak of (a,, aay a input valid bound for pairwise data, where Va, 2 1pth - PiJl
T(())
N
X1A
YiJ.A
Vi,
&
good event, & = [[ (Ee()).)) nety (p..))
wi
Vi, p. - Pi. the UCB using pure online data and hybrid data sigmoid function
UCB, UCB hyb (-))
B
More Detail Comparisons with Existing Works
B.1
Comparison with Cheung and Lyu 2024
Cheung and Lyu (2024) proposed Policy MIN-UCB algorithm, which is the first to deal with bias dataset under MAB setting with input valid bias bound (aa), our work extends heterogeneous data setting and refine its regret upper bound. According Lemma 4.8 in Cheung and Lyu (2024).
log(1Kt*) (s(a) max {1- w(a) A(a)²
A(a) of
Ne(a) 2 32
where (a) is the number of times arm a is selected online, and (a) denotes its offfine sample size. Following the derivation in Appendix B.2 Cheung and Lyu 22024) and adapting it setting, simplify the above inequality into the following form, used our Lemma and
w T' 2 8 8' Nº max 11-2000 of
One difference in our setting lies in the preference-bart basedd feedback model, which assumes 1/2 / sub-Gaussian distribution. This changes the confidence radius from /2 logooll/ /log(1/d:). / (2T..). leading different constant factor in the incquality.
However, the thcoretical analysis in Cheung and Lyu (2024) is limited in that only examines the Saving when there is no online data at all (Case Ia in Appendix B.2, where it directly scales online data (a) = 0). To achieve a regret bound with a "Saving" term, their analysis doubles the coefficient of the standard log A term of UCB. Specifically, traditional online UCB yields a regret of the form C log T/A where C is constant term, but the regret upper bound for the hybrid setting in Cheung and Lyu 2024 2C' log T/A Saving This means that when the Saving term is small, their regret can even exceed that of pure online UCB, Our analysis resolves this issue from a different theoretical analysis perspective. and restores the regret bound back to C' log T/A Saving. Furthermore, the Case la in Cheung and Lyu 2024) is actually a subcase of our more general analysis, the following chain of inequalities shows:
20

---

N' (1-
w/
88'
2
48'
2 w
2
A
48'
(2 w')
A
where the first inequality corresponds to the condition in Case la in Cheung Lyu (024), the second holds due to the assumption A' 2 w', and the resulting expression aligns with the condition stated in our Lemma S
B.2
Comparison with Wang et al. 2025a
Wang al. 2025a proposed online hybrid MAB setting where the agent could observes both rewards and pang
specific, Wang et al. (2025a) proposed two algorithms to address the hybrid feedback multi-armed bandit (MAB) problem: Elimination Fusion (EIIMFUSION) and Decomposition Fusion (DECOFUSION) EUMMFUSION eliminates an arm a, if either (CB(a,) < (CB(a:) or UCB(aa, ai) < holds, this method closely related to our MlybElimUCB-RA. DECOFUSION employs more complex and cooperative policy between dueling and reward-based feedback, randomly using of the feedback to explore the arm space and the other to exploit. Under the regret definition Rr a R + (1 a) RD. where D refers "dueling" and refers "reward", and a is an input parameter. The regret upper bound of EIIMFUSION and DECOFUSION algorithms are:
pairwise preferences per round.
(ad (R) + +11 a) log
E[RT] 40
max (4) (1/ )2 (A (D) ) {
and
log T
B[R]] &
max (1) aa (D) /(1 (1-a)}
(R)
respectively.
In our setting, the fusion arises from the integration of offline and online data. Within each source (offline or online). the data homogeneous; therefore, in the online learning phase, only type feedback is available. To effectively leverage both sources, we adopt the Bradlcy-Terry model and construct a unified estimator for
Pr.y, capturing the pairwise preference probability. In contrast, the method in Wang et al. (2025a) treats the estimation of each arm or arm pair independently, the joint utility of heterogencous data comes by constructing candidate set together.
B.3
Comparison with Zoghi et al. (2014)
Zoghi et al. (2014) proposed the RUCB algorithm to address preference-base feedback without relying on the strong stochastic transitivity and stochastic triangle incquality assumptions required by carlier works such as
Yue et al.] (2012). However, RUCB does not fully exploit the information in its candidate set, as it selects the second (corresponding (t) in HybUCB-AR) uniformly random. As result, it can only guarantee
a regret bound of
(A; + A,) log min A A3)
In this work, we improve upon this by maximizing informative pair in the candidate set:
(2()))
arg max UCB(a, ay). EC, ",.",EC XC2
This change allows us to better utilize candidate set information, leading to a tighter regret bound of
A + A,) logT max A A3)
B.4 Comparison with Qu et al. 2024)
Qu et al. 2024) proposed a hybrid transfer reinforcement learning (HTRL) algorithm, HySRL, which selectively uses historical data exhibiting shifted dynamics reduce the sample complexity of online reinforcement learning.
21

---

Similar to the findings in Cheung and Lyu (024)) it proved in general HTRL, when no addition knowledge restriction in applied to historical dataset, the sample complexity could not be improved.
To address the distributional shift between offline and online samples, HySRL introduces the concept of B- separable shift, which classifies offline data as either distributionally identical to different from the online environment. For offline samples deemed identical, the algorithm directly incorporates them into online estimation, In contrast, samples identified as distributionally different are entirely excluded during the online learning phase. Under this framework, the sample complexity of HySRL is:
δ min
SA
181
5²
(o3)² )
+
E²
e²
where a, 9, are their input parameters, H is the length of episode, S, A refer to state and action space respectively.
Qu et al. (2024). the distribution shift region detected online, and under the theoretical sample complexity bounds, the shifted region can be correctly identified with high probability. Despite flexibility, this approach the choice of B3. Moreover, it does not account for the sample size of the historical dataset. In contrast, our method assumes valid bias bound as input, which climinates the need for warm-start estimation of the shift region, but requires prior knowledge about the or the transition probability functions.
relies on strong assumptions regarding the 3-separability definition
C Proof for Theorem 1
C.1 Lub-Gaussian Properties
Lemma (sub-Gaussie Gaussian Properties of Estimators). Let Pi.) denote estimator the preference probability benween and j. The Sub-Gaussian parameter of f..j depends on the type of data used for estimation:
For relative preference data, where
T
1
PE.
Yig.
Tes
the estimator is 2V T..s sub-Gaussian. For stochastic utility data, where
N2
Pi. =
L.k
Σ
j,
N
N₂
k=1
the estimator is
2/
No+N N.N;
sub-Gaussian.
3. For a hybrid estimator combining both types of data:
Tes
N.N N,+
N,
Ayb P
Ted
N.N, No+N,
Σ
+
Tess +
N:N;
No
Xx.
N,
Σ Nz.k
N.NN;
the sub-Gaussian parameter is
N.W To. Ny+N3
Proof. We prove each case separately.
Pure Relative Preference Estimator. Let Y Bernoulli(p) with values in [0, 1]. By Hoeffding's Lemmal for any R,
22
E eexp (A(Y - E[-]))] I exp
8
This corresponds to a 2 sub-Gaussian variable, since
(1/2)
As fo. is the average of (t) independent Bemoulli samples, Lemma 5.4 in Lattimore and Szepesvári (2020) imply that P.,, 2 T.,(t) Gbb-Gasssian.
22

---

2. Pure Stochastic Utility Estimator. Assume that each Xz,x and X5,4 is sub-Gaussian. Since sub- Sub-Gaussianity preserved under averaging, have:
N
1 N
Sub-Gausiinn,
X
sub- nub-Gaussian.
Therefore, the difference of these averages sub- Gaussian with parameter VI/N, + Since sigmoid function is 1/4-Lipschitz continuous, applying Lemma parameter:
I0
yields the final sub- Gaussian
1
1
N
2
N
N
3. Hybrid Estimator. Let
N.N,
Tiss
B
Z ==
X
Σ
Xzik
N + N₁
N:
Nj
km
The estimator is a convex combination:
Jobb PiJ
Σ Viile + -38
Since Σi=1 Yu,.a is 1 Va sub-Gaussian and Z is 2 N. N2
sub- Gaussian, by Lemma 5.4 Latti-
more and Szepesvári (2020), the entire sum has sub-Gaussian parameter:
1 5z
(
1 N₂
a
B
N
2/ B
Substituting back yields the desired result.
C.2
Justification Valid Bias Bound
Lemma 2. Given V, 2 1A psl. Vi E [K]. under the Brudley-Terry model, we could derive the valid bias upper bound for pairwise term as Veg p Pusl Vi,j E [K].
Proof. Since V, 2 off and V3 2 derives
Mi off
Hí. we have V, + V, 2 (Mi H1) - (4 -4 - which further
(V + v3) 2 a(w - mJ) (ui af ) 2 onμo pU) o (14 off
14 Pij Pi.
The first inequality is by the monotonically increasing property of sigmoid function, and the second inequality by the property of sigmoid function where ox + 8) S (π) + aty), Vx, R.
Similarly, could derive oVV. + V3) P. Pig. hence (VV V2) 1 Pu.l completes the proof.
C.3 Good Event and High Probability Bound
Define good event = - (Ei(D..) ne (eh""(()s))
where
log(1/6.)
Pis S UCB(a,, Sps +2 E((p)))
(11)
2T;,;
N,
chr (pis)
Pi. S UCB (as, S Pis + 2
((T.,
log(1/6)
N.N,
TT,(() + N,+N,
N++N,
N:N, Wi
(12)
N.tN,
with Wii = Vig + pht - Psj. we have the following lemma:
Lemma 3. The good event satisfies the following lower bound: Pr(Et) 2 1 - -2K(K 1)6c.
23

---

Proef. This proof largely follows the argument of Appendix B.1 in Cheung and Lyu (022)). We begin by applying the Chernoff bound for sub-Gaussian random variables. Consider the estimator p., of the true pairwise comparison probability Pt.j. Since the difference X Pi.j Pt,j is aub-Gaussian with parameter vI/T.,
by Lemma apply the Chernoff inequality (see Lemma 8
obtain:
log(1/6.) (t)
Pr Pi.. pt,l
I 26,.
This establishes the condition for the 'bad event' E3 (p(L))) by rearranging the incquality ahove.
Next, we analyze the 'bad event" &t (pts)) which occurs when either of the following two conditions is violated. The first case corresponds violation of the first inequality in Equation (12). For this case, we aim derive upper bound the prohahility of violation:
Pr ps. 2 UCB"" (as: a.))
where
Ti,())ps + N.+N,
N,N, 08; - -x,)
log(1/6))
N,Ng No+
UCB aa)
Vis-
(es(t) N,+N,
N.N,
2 (t) N.t,N
Te,(1) + Ni+N5
N,N,
This probability can be rewritten as:
Tf.(()pa. N:N; Ne+N, Pi.3
N,+N; (pi.) Pi.
N;N,
Pr
(t,(t) - N,tN,
N.N;
N.N, (t) + N.+N,
(1)o + N.+N; a(x, X2))
N:N,
log(1/6:)
No+N
Va.
N.N, (t,(1) + NANN
N.N, (t) N:-NN
(1,(t)
N,N, N.+N
NyN; (t,(t)pts N.+N, Pi.
(thi. + N,+N, (8, - -x,)
N.N;
log(1/5.)
< Pr
(t)(1) + NG+NG
N,Ng
(t)(1) + NctNg
N;N,
(1)
N.N, N,+N,
< 6t.
where the penultimate inequality uses the fact that Vi, 2 Iy Pr and the last incquality comes by applying the Cherooff inequality the hyhrid estimator, which
sub-Gaussian (by Lemma
V Ti,(0 NETNY
For the second case, consider:
N,N, No+N
log(1/66)
Pr
UCB (a;,a) 2 phu +
(Vi, P.. off ps.5)
M.N. 2 (1) + N.+N,
(t) + N,+Ny
N;N,
This can written as:
Ti5(0) + N.N, N.-N, (x: xxx
N.N, N.+Ny
log(1/6.)
Pr
2 Pi.j + (TT + No+N,
(pi off
Pio))
(1)(1) N.+N;
N.N,
N.N,
T1, N.+NG
N,N,
(1p() + N,N,
N (X. X1) Tes(1)Pss + N.+N, Pi.j
N.N,
log(1/6;)
Pr
Te((1) + N
N.N;
N,N. T:5(1) + N,FN
(T, + N,N; No+N,
< 6t.
The final incquality is by applying the Chernoff inequality
Since there are K(K+1) distinct pairs of arms, and for each pair the probability of E, is at most 48,, applying this all arms gives:
24

---

1 1 P-(E)))) = Pr(E.)
Pr(E)(pes) + E (pas)) (union bound)
2 1)8.
(since Pr(E)(pLs) + etth (prs) - $46.)
hence,
Pr(E,) 21-2K(K + 1)6,,
which concludes the proof.
C.4 Property of Algorithm
!
Lemma 4. (HybUCB-AR's property) Conditioned on & the arm pair (as, az) will not be selected in round if it satisfies the following Inequality:
N,N.
log(1/6.) (1)
log(1/8)) 2 (i,(1)) + NEFN,) +
N.
max [A, min
(
(t)(t)
N.N,
Wi
N
Proof. Conditioned on &s. Suppose arm pair (a;, az) selected, there are two possible cases this selection:
(Ai(t),A2tt) (a., a,),
2. (a)()) (a,, a.).
We analyze the first case, while the second case follows symmetrically. By HybUCB-AR's selection criterion (Line-7), when (a;, az) is chosen, it must hold that:
log(1/6.) (1) pss + +2/
log(1/6)) (1)
1
P&j +
UCB(a;; 4:) 2
(13)
and
log(1/88 (
log(1/6)) (1);s(t)
1
- Ps. + 2
(T,s(t) phs + +
> UCB(a; az) 2
(14)
Equation
13 and
14
implics that
log(1/6.) (1)
log(1/6))
Pt. S
V
and Ps. S +
(15)
(t)
Given A, lox(1/6.) 2T.,(t)
we have the following:
1og(1/8) (t)
1og(1/52 (t)
UCB(a, az) S 22
+4
pl. S min {UCB(ar,a)) as): UCB (a,, a.)
(16)
The first and fourth inequalitics in Equation 16 follow from condition &., while the second inequal- ity is derived from the first inequality Equation
The third incquality holds by the given condi-
tion A, > 4v /og(11h))) (1) Recalling that HybUCB-AR's selection criterion (Line 10) satisfies (a,, (a.)a;) =
arg maxoqin, EC, min (UCB(U:, a,), UCB (a., a;)), we observe that [66 leads to contradiction.
Following the same reasoning, the condition A 4, This implies that the arm pair (a., a,) cannot be selected when the following holds:
Tog (1/6) would also lead to analogous contradiction.
(7)
log (1/,))
max M A, 4
(17)
(T)
Since the candidate set is constructed by C. C.m clyb applying the argument clob yields that (as, a5) will also not selected
N.N N
(1/b)/)))
max A,, A
N,N, (Tes
+ N.tN,
2
T
N,FN;
N.N.
Wid
(18)
25

---

Combining Equation 17 and (18) leads to the desired result. By symmetry, the analysis for the second case (2((1) (aj.az) az) mirrors that of ag) and leads the conclusion, desired.
C.5 Proof of Instance Dependent Regret Upper Bound
Before we provide the proof, we present general lemma concerning the solution to the key inequalities derived Lemma
Lemma 5. Consider the notation N'. T', w', 8', and A these variables are defined to simplify the structure of the equations while preserving their form, enhancing clarity and generality. Let T be the smallest integer satisfying
8 T
8' N
N' T N }
A' min
2
2
(19)
T
then
T
max
N'' (W/
A
48
48884448
if Condition Saving, otherwise,
where:
Condition Saving= (2w' S A') or (N' 48' A') A' 2/2
Proof. established, Equation represent bounds derived from the HybUCB-AR's framework, correspond- ing to pure online and pure hybrid data scenarios, respectively. Our proposed algorithm requires that T' satisfies at least one of these conditions. The use of offline data reduces regret when the smallest 7" satisfying
8
A
> 2
(20)
T
is less than that required by
8'
N T N
A'
2 T + N
(21)
For Equation direct manipulation yields:
T AZ
(22)
Equation
define /I" No
x.
2 and N'w. The inequality becomes:
B
<.
x
Solving this for æ 2 0, obtain:
A A + 1BA
2A'
2 1 2BA
V + BA'
2A
This implies:
T'd 28 +NW / 2 W''' N' 28 +N'A'W - A' + V 18 + 1''
A2
A
Since T 2 0, we have:
28' + N'W'WW A') 2 + 18 N''
T' > max
(23)
A
Combining these, the general bound is:
48'
28' + N'A'
A
40
48' N' A
T' > min
A max
(24)
A /2
26

---

Next, we identify conditions under which Equation 21 yields smaller T than Equation 20 Saving
Define the
48' (28' N' A
40
W0'
Saving
A
From Equation 24). Saving positive only if A' > w/, since w/ A' < 0 the sole negative contribution,
potentially reducing T". This condition also ensures the left-hand side of the subsequent second inequality (Equation (5 remains non-negative.
We roquire Saving 2 O:
16' 28' N A)
V + W''
20
A
26' N A) 2 V + N''
(25)
N A (w'' A) 48 N' - 28)2'''''
N' - - 4' -
Hence the final inequality, guaranteeing that saving 2 0, holds if either
2w <
48 42' 2\)
(ii)
2A 2w
A
and
N' 2 A' - 2')
These conditions together validate case distinction stated the lemma.
Proof. (Complete Proof of Instance Dependent Regret Upper Bound in Theorem
By Lemma and Lemma 4, take A' max (A,, A,). 8' 1/ log(L/8t), w' wiys N' N; (t),)), under the good event &,, the number of times the arm pair (a., 0²) played satisties:
N.+Ny+ T"
max (A:, A3} > 2wiy > max(A:. and N,N, No+N5
max (A, A, max mu [A,,)] then:
2 2 /8, (2wm, max AA
N, (t)(t) max 4log(1/6)) + N.tN, max A., As maxfA; A,H)+ vD
0
(26)
max A7, 4/}
N,N, where D= =loo"((1/6) log(1/6)) N,4N, was max A., A,}.
otherwise:
8log(1/8, max A A7}
(1)(1)
(27)
Define g(a;, az) and [as, az) as follows. Here, g(a; az) denotes the upper bound of (() in the presence of Saving, while [as, a;) characterizes the condition under which Saving occur. Specifically, Saving exist if [a. a,) < O.
N.N, No+,, max(Ar, Ag) (2wr. max (,)) VD max A7
o(a), max (1/8) (A; A3)
+
-1
if Awn., & max{ Ai. As}. max/A, Ay A2 -mar -m No. if (max(Ai, A,} Awi,s max max 4y}.
a(a;,
otherwise.
(28)
The expected is:
27

---

A Aitt: + AAuii))
Reg(T) =
Σ
(1(E.) + 1(E))
Σ
T
E
A Az(e)
+ Azite)
I(E))
+ A max Σ E [(())
2
t=1
A Aj
T 1(E,) Amax B((EE))
Let 6. 1/(2K(1 + K){)),
under the had event, the regret is:
r B[I(ET)]
T
x
A Amax
- max
B[((ET)
2K(1 + K)6
max
Amax, (29)
under good event, the regret is:
E E (T):
Σ S ka
g(as, 0z)
A
8(A++ log( (2((22K 22 K)T)
2
max (A, A3}
Sh flo.ay)20
(30)
20 and obtain the desired result. The simplified regret upper bound is obtained by applying the following inequality g(as ) in Equation 330
Combining Equation
v x² + 2ax < a a
(31)
where x = log(1/6.), a=
N.N, NJJ
max A;, D } we derive:
Reg(T) x²
Aaax
Σ
max
A +
16 log( 2K(K + 177)
N.N, max [A,, A,} 4wi.j. 0}
2
max (47, A3}
N + N2
max (A,, A,
iSJ
(32)
C.6 Saving: Further Analysis
Remark 7. To facilitate concise notation, we denote by (UC(UBB) and Te (UCB the upper bounds Tip under the UCB and oCB selection rules, respectively. Specifically,
48' A
TUCCCB)
28 - N'A A)
V 48
48'
Tiy(UCBhh) max
A
This is the result we derived from Equation 22 and 23 in Lemma In the context of Theorem (UC(UB) and anyToy OUCB becomes Equation and respectively.
After establishing Theorem] I we provided a brief analysis of the "Saving" term in its regret bound in Remark
3
Note that Theorem D is simplified version derived by applying Equation (31) to Equations 29) and (30
Below, we present
precise analysis of the conditions under which "Saving" exists. By Equation 28
could divide condition into three different cases:
1. Significant Saving: When max A., A,} 2 Awi.j, offline data guarantees regret reduction.
2. DattaDeeendent Saving: If Awi,, > max A, A,} 2wi,jj Saving exist only when the offline data size satisfies:
4 log(1166.) (Aw.,,, max A, ,, N + N, max A,, A, (2wxk - max A,, 2
N.N,
3. No Saving: For max A,, A 2wi,j, offline data provides benefit.
28

---

This result aligns with our Saving analysis in Section 3] which shows that Saving depends on the similarity between offline and online data distributions, with the magnitude of Saving influenced by the offline data size. But the detail analysis further shows there exist an intermediate phase: where existence of Saving data dependent, Here, we provide deeper insight into the three regimes. When the distributions are sufficiently close (max A,, A,} 2 4er.g), the Tú (UCB) is consistently at most that of Tay (UCB"" ensuring Saving regardless of the offline data size. As wi,j increases, indicating greater distributional divergence, the (UC( grows, potentially exceeding that of Te, ). In this intermediate regime (Awi,, > max A., A5} > 2wh,s) Saving is possible only if the offline data size Nij large enough reduce Tú, (UCB "), compensating for the increased why- However, when the distributions are too dissimilar (max A,, A,} < 2ws,)). (UCB"") is dominated by wi.j, and no amount of offinne data yield Saving. These cases illustrate spectrum of outcomes driven by distributional similarity and the size of offline data.
In Lemma 3 established conditions for the existence of Saving. but their magnitude remains unanalyzed. For instance, when A' > 2w', Saving are guaranteed regardless of the offline dataset size N'. However, N' small, the confidence radius may remain large, resulting in negligible Saving. To further quantify the saving term, we analyze a specific setting where inferior arms can be identified without online data, thereby maximizing Saving.
Given the following Lemma 6 this implies online exploration is needed for HybUCB-A when the following condition holds:
4,} was) N: + N max D; (2ws. max A:, 42})²
N.N,
16
and 2 max (.., A5
Lemma 6. Suppose w' < A and
42' w²) N'
A'A'' w/)²
Then, under the good event, online exploration is needed for this suboptimal arm.
Prouf. Continuing from Equation 23 aim to identify the condition under which the following expression becomes non-positive:
28' + (' A') + 28 + W 0.
A
It is clear that this inequality can only hold when w' < A: otherwise, all terms in the numerator would be positive and the entire expression strictly positive.
Under the substitution from Equation
we consider the equivalent condition:
N' A' - -')- 26' 2 v 18 1
Squaring both sides yields:
N A w/ N''N'''''' wd) 2 N'''
Rearranging terms, we obtain:
N' 46 42' w') A(A' - w/)
as desired.
Remark 8. Specifically, when w/ = 0, the condition simplifies to N' > / which degenerate the algorithm property of vanilla UCB. In contrast, under the Saving condition in Lemma (2A > 2w' A'). Saving begin when the offline data size N,N,/(N + N,) meets a certain threshold, but fully replacing online exploration requires larger N N,N5/(N, + N₂)- The difference in N,Ng/(N; + N2) between these two thresholds is given by:
48 (22' W') A w/)? A' - D' A w')²
42' -A) 43' 3w")
C.7 Proof of Instance Independent Regret Upper Bounds
As shown in Theorem | we provide two instance-indepeneen regret upper bounds, and the final bound is obtained by taking the minimum of the two. The details of these bounds are presented in the following two Sections C.7.1 and C.7.2).
29

---

C.7.1
Analysis 1
Proof. We derive the instance independent upper bound through modification of the instance dependent regret upper bound. Let A be variable between (0, 1). For (as, ey) E A x A such that max[A,, A, 2 A, take & = =1)² the core term in the instance regret upper bound (Equation (32 e.g., the leading A dedeendentt term) is bounded by:
1(A, A5) ())(1
8 (18((1/8))
16 log( (08(v2K(K + 1)2) 8log(1/8r)
max 43}
max A., A3}
A
A
where the first inequality comes by taking A, + D S 2 max Az}. For arm pair (as, ag) E A A satisfying max A., A < optimal pairs is upper bounded by TA. Let Saving(a:; az)
A. the total regret incurred by these sub-
م N,N, max maxe (A, 3-dwi,
N:
(A,
and Saving' (as, az) min
A.+A;
NLN, NotNy
maxi max/max, D. A, J- duri.;:0) M(A++A,) 1og (v (K (1 11
for
max (3
max B3 (1,)
all i.j [K]. Combining these results yields:
Reg(T) S Amax +
π
Σ max
16 16 ( 2K(K + +1]") Saving a,).0
max A,)
n² A + +T+ SK(K + 1) log( /2K(K -)T)
Saving' (as, az)
A
π A max + 4V 14422K 2K(K + 1) log( /2K(K + 1)T)
Σ
Saving' (as, Qz),
V ( / (K +1)Z)
where the inequality follows by taking
desired.
C.7.2 Analysis 2
This theoretical analysis extends the framework of Appendix B.3 in Cheung and Lyu (2024, + generalizing its regret analysis from the classical multi armed bandit (MAB) setting to preference- based model.
Lemma 7. Let (2ig hissen] is the optimal solution to the following maximization problem:
Tej
(Tig)egs
N.N,
N.+N;
s.t.
Tes =
iS)
Ti E No0. $ [K].
then it must hold that T?, S max
N:N, for all a, ag E A.
N,N,
Proof.
We proof this lemma contradiction. Suppose there's 's arm pair (ai; az) such that Thy max [T.]] N,N,
0] + 1, then must hold that there exist at least one arm pair (ar,ay)) such that Tyy S max{[T.]
NE+NN N 0} - 1, otherwise we have: Tigg 2 max{[T.] - Nery, 0} for all 1" j E A. Particularly,
T 2 max N.HN,
N.N, 0} this implies:
N.N, Thss max No N 0) 2 max N. N,
N.N,
0)
4. =T
(33)
where the penultimate equality comes by the property of the optimal solution of Linear Programming problem in Theorem ! Since by the Linear Programming problem, Vk, E [K], k S I, let es.i = G.
max(r. T. Ni+ 0} 2 0. 3r E [K] such that c > O, then the solution (7, (Lx,) (x.ee)) defined 2 as т. KTK fx.1 = t + æ(K for (k, E [K] [K]][( 1'), (I', K²)}, and ie
Nr
2eg
Grr R(K+1)-2 egr could also be feasible solution the linear programming problem. This implies
F > hence the optimal case could only have 0, implying the establishment of the equality.
30

---

Hence, Equation 33 violated the feasible region of the Linear Programming problem in Lemma 7 have two distinct arm pairs (as, az) and (ay:ay.) such that:
Thereby, we
T + N;N,
N,N; } ++1, 1, in particular T7 2 1,
2 max
N. + N
N. + N
No
Nr
T N + N
S max[[T.]:
[T.]
Ny + Nr
establish the contradiction argument, let k S with k, E [K] x [K]. consider another feasible solution:
Tha Th + The
if (k, = (i.j),
Te.
if (k = (i' otherwise.
but then we have:
That
N, Led +
L
No
No+Ni
sx,==
Nx+M
1
No Thy + NotNy
+1
TN, +
N,N, No+N3
2
0,
max [Tx]
N;N; Ng+
this implies Ti is not the optimal solution, thereby TV S
[T.[[[T]]
N.N;
0}, as desired.
N,+Ny
Proof. (Complete Proof of Instance Independent Upper Bound) By Lemma arm pair (as, a,) has the chance be selected only if:
N.N.
max D., A,} S min 4
log(1/6.) 2Ta,
N,N; Thi No+N,
log ((1/6))
NE+N T
N.N;
Wi.
N++Ny
Denote rad,.j
and rad 1/6.1 27.
1og(1/6))
Vis hence we have:
1.j
N,N, 2 Tu.s 8,tN3
T N,-5
(1) + AAa(1)
R2g(2))
max(DA Asse
(t)) 4rad A2
Ti
Tie
< min
rad 4
rad hyb
45.
1=1
The Inequality (*) established due to Lemma and the fact that wi. = Vi.i + piu
Piu S. 2V.,. For the first
term 4 Ee Sisj Din rads,j, have:
T
log(1 (5,))
Σ
Tes log(1/ōr) = 8/log(1/or)
Tr,
2Ti,
15
15)
K(K
12
T 8
Tlog (1/8r).
(34)
2
The last inequality follows from applying the Cauchy-Schwarz Schwarz inequality. Since this bound corresponds to the vanilla UCB setting without offline data, it is already covered by the result provided in Section C.7.1 and is therefore omitted from the final regret bound.
31

---

For the Second term E ig Ligs
Edi rad!y"
hyy
we have:
N,W,
log (1/ōr)
No+N,
+
Vis
N.N. 2 ++ N(tN,)
+ N;N;
Nct.N
T2
S 4 max Vi. T
V log
(35)
ST
2 t+ N:-N,
Let Tū, be the optimal solution of the LP problem in Lemma
By applying Lemma
we obtain:
T&e
93
N,K, No+N,
N,N No+N,
N,Ng N.+N,
5
thus:
max [r.]
N:N; N,+N, (03
max [Tx
N.N,
0}
[r_]
N.+N5
Σ
N.N. N,+N;
[Ta]
1=1
1=1
N,N;
2
max maxi[T.]
N. N, -0
VT.
40
47
VT.
where the last inequality follows by applying the feasibility of the LP problem in Theorem
Replacing term Eig E 4
with
162 Vp"
in Equation (35)
leads to the desired result.
N.N, W,TK,
D Proof of Theorem 2
The proof regret lower bound builds upon the approach Cheung and Lyu (2024), which we have extended to accommodate the hybrid setting.
Theorem Let P, Q be probability distributions on (I, For event (FF), holds that
Pr(E) Pr((E)) exp (-L(P))))))))
Theorem 5. Consider two instances Ip and Ia that share the same arm set A, online phase horizon T, and offline sample size (Niheek), but have different reward distributions P = (P,, )e(K) and Q (Qu, Q )iE(K]. For any non con--nniciiptorry policy n, holds that
KI(P.Q) Σ BP.. KL(Ps Q13)+
Σ N. KI(P," KE[K]
Theorem 4 is direct restatement Lemma 15.1 from Lattimore and Szepesvári (2020) while Theorem is
adapted from Theorem C.2 in Cheung and Lyu (2024). The only difference in our setting is that the relative feedback data follows discrete distribution; nonetheless, by following the original proof strategy, we are able to derive Jacordill....d.iiglly
Claim 1.
For P = NNp,, where i (1,2). we have
PL)P,PP.) (M1 22
20²
Claim 2. For P. = Bernoull((ps). where E (1,2), we have
KL(P,, P2) = pı log P1
+ (1 pı) log
1-
S
(p) p2)
p2
1-
p2
P2)
where the last inequality of Claim 2 comes by applying logæ S
32

---

D.1 Instance dependent lower bound
Proof. We begin by denoting jrr and μe; the means of the Gaussian distributions of 17 and P,, respectively, for each arm E A. Assume μi corresponds to the optimal arm, while the remaining arms are suboptimal, with J4 = for all j.j # 1. The gap between the optimal arm or and the suboptimal arms (az,..., ak ) is denoted by A, where A =
E (0, 2
Next, we introduce an alternative distribution Q. Let & be a fixed arm in {2,-.. ; and Ti(t) represents the number of times arm is selected pairs and pulled up to time For i [K] \ {k), define Qi = P? and Q. P.. For arm & let Qu N(u + 2A, 1). Define Q% as follows:
Qx
[( .) N(us + + VA, 1)
off if
PE P
2
+ 2A Vi.
(36)
< PA + 2A V&s
where Vi 2. 1/4g" px|-- The construction Q% in Equation 36 governed by Vg. The high-level idea behind it is to maximize the regret lower bound by minimizing the KI. divergence between Q% and Px However, directly setting Qt pht may violate the constraint E Iv. When the constraint is violated (e.g. 14g < pa 2A- Va), we instead define Q NNus + 2A Vx, 1), which yields the smallest KI. divergence possible while preserving Q E Iv.
Under the dueling bandit setting with the Bradley-Tert model, the pairwise preference gaps under distribution P is given by:
A PLP 2 a =
1 Wi
Under the perturbed distribution Q, the pairwise gaps are defined as
A = Phai ((2) 2 Vi (K](,,), and Ax,1= - 1
Using the definition regret under distribution P, we derive:
(T) = [ 2) (o(A) 1)
Ep [mi))) (((())
T (((A) - 1)
(o(A) - 1)
Bp [1((T)) (o(2) - 11)
Ep [T(())
2
2
-T (((A) 1
T' (o(A) }
(( (
1 2
(T) TT) -
Pr (T) > T)
2
2
(a(A
(T)
2
p
For distribution Q, the regret lower bounded as:
Rego (T) = Σ Eo(TH(T))
K A:
a(A)
&
(TT
((a(A)- - 1
Pr(Ti(T) > T).
2
2
2
Q
Combining these, obtain:
2011" > Regp (T) Rega (7)
T (a(A) b
(T) < < + T))
2
p
T (a(A)) -
TA 32 (xp(-KL(P,Q))
(37)
where the first inequality follows from the definition of Cp-consistent, the penult inequality applies Theorem
and the final incquality comes by our restriction on A: Since A E (0, 1)), we have (AA) 2 A +
By Theorem the KL divergence is:
KL(P,Q) = Σ Er(T,s(T) (L.))..Q..)+
Σ N "P. QQ. KE[K]
33

---

For the first term, using d(p,g) ====lllggg plog !)) + (1 p) log [1-
(o-o)²
all-o)- have:
K
(2.0(21)) +7
Σ
(T[T..())KL((P)) Qxy) )
Er Er [k. (T)jd Σ
1 +
2
Ep (p(Ta.((T)
222
+ BP(T...
2'2
A
A
Ep (Tk, (T)
+ +BPT (T)
1 A2
1 A
A²
(P([T((T] 1-
s <Er((T(TT)22'
(38)
where inequality (a) follows by o(A) - 1 + 1.2 this implies:
d (2-o(a)) d
1 2' 2 : and d(1 ((1-o(A) ((L-o(A),((A)) ( 1 / 2
For the second term, by our setup, we have:
N; KL(P," (((P)""Q()== max 22 - wk. 0}2
Σ
(39)
2
[EIK]
where We Vv + 14
1kk Combining Inequality
and Equation (39 we get:
TA
max(2A ww. 0|
2CT 2
exp
[T](TT(T 24
No:
32
isolate (T)], we natural logarithm of both sides and rearrange inequality, yielding:
1
(1 - log log
max (2A
wk. 0}2 N₂
(TT(TT) 2
2A²
64C
Summing over arms E [K], total regret lower bound becomes:
Σ
ELTTT
K
(a- (1-p)
(1-p) In
max - w/, 0 No.
2
4
64C
4A
[E|K]
(E[X]
as desired.
Discussion about upper and lower bounds. Consider the special case where N, = for all i [K] and A, A for sub-optimal arms. In this case, the upper and lower bounds differ by most factor K.
Proof. We compare the upper and lower bounds separately for the iestene--nddeeendent and imstance-depente dependenn cases. For the instance- iestanceinndeenndeent bounds, we first compare the first term in the upper bound (Theorem Ib)) and the lower bound (Theorem 2))). Specifically, the first term in the upper bound O( K2T log T), while corresponding term in the lower bound is 52 KK)). This implies gap /K log I between upper and lower bounds for this term. We then compare the second terms. The second term in the upper bound can be written O((ylog T/r. Vmax) T), and the corresponding term the lower bound is 22(( M(((1/7T Vina)): T). To compare the different parameter т, and r., consider special where N. for all E [K). In this case,
2T
27 K
+/=
2
K(K +1)
Under this setting, it can be shown that the gap between the upper and lower bounds for the second term again most factor of /K log T.
For the instance-dependen case, to better compare the upper and lower bounds, we consider the special case where N, for all i [K] and A. A for all sub-optimal arms. Then the upper bound in Theorem 2(a) simplifies
K2 log
K2n
max Awis:03 0))
34

---

and the lower bound is in the form of:
Ω
K
log T
K 4A
log
A
Kn
Σ
max (A
wx/2.03
64C
[E|K]
From this comparison, we observe that the upper bound is approximately a factor K worse than the lower bound this case.
D.2
Instance independent regret lower bound
Proof. The divide the proof into three distinct cases:
Case 1: 2VKT > T (Vmax + v 22/T2), and Vinax
S LL/VT. we derive a regret lower bound of:
Ω min KT. (VT: Vmaxx ) 52
V
At this point, we consider setting where the bias between offline and online feedback is negligible. We define the Gaussian reward distributions as follows, assuming discrepancy between offline and online feedback:
1)
i 1, if k. E [K]VE
I( = 1)
P.t P:
0fth =
(222,
1f
(N
where 1/V72 and arg mi N. (T)).).
Obviously P,Q Lv, since 1uA - pil 0 Vmax. Without loss of generality, assume that arm 1 has the largest offline sample size, that 1 arg max No.
Subcase 1.1:
In this case, have:
Ep Bp[2i]+ Ni & Bp[2]]] + N. for i [K] (1).
Since we assume 1 = (aX N;, it follows that:
Er([T)] < Ey [7:] + N; - N₁ S [T].. for all [K] (1}.
Therefore, arm has both the largest offline sample size the smallest expected number of online pulls among all arms. By the pigeonhole principle, this implies that the optimal arm è o is pulled at most 2T/ times. Thereby, the expected cumulative regret can then be bounded as:
2T K
A
(K
D)T
(K K -1T
Reg(T) 2
27
2
K
KVT!
Subcase 1.2: of
1
1
(7) + Rega (T)
(AA)
(P((E[Ti] S) Pr((E( Ti)
2
2
P
T
[T(A)
K exp Σ
B[T] KL(P Qu.i) No MKLK Qit))
4
TA
32 exp
(-2E(T.JA* 2N&
TA
exp(- exp(-2r(A3)
32
3
1
T
32e²
VT!
where inequality (1) follows by applying the same technique D.I inequality (2) hold since k:
arg min N. + [T] 5 Th, and the final equality (3) comes by applying A 1/V7..
KT > T (Vmax + v2/T<), and Vinax 1/VTV, we derive regret lower bound of: Case 2: KT
min { WKT, (V T/ VVaax - r1)
(T' Vmax))
35

---

We construct another instance such that:
(N(A,) =f==1,
Ps 1), VE [K], P.
((0,1)) fi
1)
11 ifi=k, if [K]](, 1}.
QT = -N0,11, V Qi
1)
1)
where & arg min, E[Ti], and take A -1/2. Vmax.
Since 1A4" pil < 22 = Vmar = Vi for all i E [K], this implics P,Q E Iv. Furthermore:
Regp(7) (7) + Rega (T)
2
1
((A)
1
(Pr(E[TT] S T)
Pr( (T( 7))
2
2
7'
(A()
K
B[T:] KL Qu.i) - Noo (L. Q:th)
exp
4
TA
exp 22E(T]]A2)
32
T max
TV
exp
K
TV
64
where the last inequality by the condition 2 KT TVmaz + 22/T T' this implies
TV /KK 1) S 1K/(K-11 S 8
Case 3: When 2VKT ST (Vmax + 22/T(), we derive lower bound
Ω min { VKT, (V Vinax T ((KT))
analysis for case largely follows Case 2. We use same construction reward distributions P. Q, but now take A /(K 1)/(TT).
From the properties of the associated Linear Program problem in Theorem know that r. 2 2T this implies: V2T/VT.= < /KT, them by the condition under this case, gel:
v KT S TVmax + /2TT VT. VKT
TV
which further leads to:
K
14 S 24
KT S Vmax=
Vi E [K].
Hence, the constructed distributions P. Q satisfy the bias constraint and belong to the class Iv.
Following the same procedure in Case 2, we have:
RCg + Reg (T)
>
1
o(A)
1
(Pr(ENTi) < <T) ST) T))
2
TA
exp (-2[((])))))
32
>
-K-1)T.
61c
The Theorem is proved.
E Proof of Theorem 3 and Supplementary Regret Bounds
E.1 Instance Dependent Regret Upper Bound
The analysis of this algorithm is similar to Algorithm [ the only key change here is the position of the relative data and the stochastic data, therefore, the bo UCB and good event & changed to the structure below. Note
36

---

that elimination based algorithm shuold consider all cases from / = 1,.." T, first we define good events for both hybrid and online UCBs, let
log(1/ó.)
No.
(prs) =
Pi.j I UCB Oz) Pis +2
2(N,,J + 2,002,
NI.
Wid
7(((++;311)
(11(1/5)) Ti Tj
E(prs))
14 S &UC((as, az) S Pts +21
T.T
with
8 n n (E((p),) n E/ (pss)) xEjT] [œE[K]
Following the proof Lemma derive Pr(E) 1 2K (K 1) Ei 6c.
Then we move the analysis of property of this algorithm, which to detect point of which an arm eliminated time t. we claim the result as follows:
Claim 3. For Algorithm under good event E, arm will be eliminated if it satisfies the following inequality:
(1g(1/):) 2N Ti(()
2N1 2N1, Ti(1) WI, 2
log(1/6))
A min (2V
T:(1)
Prouf of the claim. According the elimination criterion of HybUCB-RA (Line will be eliminated either the following inequalities holds:
UCB(ai; aj) < 1, Vaj= A.
UCBbb(a; (a;, a,) < Vaj- E A.
This includes:
UCB(a;, 01) <
UCB (a., a1)
When A, > 2
[og(1/6))
and the event holds, we derive Ti(0)
UCB(a; S Pt,1 + +2 log(1/ó, Ti + P&1 +2 Ti(1) 2
log(1/8.)
T.T;
where first inequality follows from the definition of event E, and the final incquality results from
condition A 2 1og(1/6.)
T(0) The approximation holds because when remains active in round we have
(Ti(1) Ti (4) < 1, making (e)
T.(0)
O(1). The case for UCB a;) follows symmetrically, 2N
71(0)+71(()
derive when A; +77,0
1og(1/861
2N T.0) W9,1, the following condition holds:
log(1/6))
1 Wi,1 < 2 2N,, + T:())
2N1
(a;,a)
2N + +.(())
Combining them together completes the proof.
Now move the complete proof of this algorithm.
Proof. (Complete Proof Algorithm
Define
log(1/6.) + 2N, Ad(un, - A:) + v 4 (1/6.) (e) A: 00.
g(a.) = max A
2f Ai,
f(a.)
2 A,(,, -A.)
No.1 if24; > 20111 > A.,
otherwise.
37

---

By Lemma 5 and Claim
taking A' = A., w'
1 = 1N,,1, T T 8' 1/66,
could derive:
(11((1/)))
if ((a)) 2
T((t)
A
[g(as)
otherwise.
Take 6;
1 3K(K+I)T the expected regret for bad event becomes:
1
TA max x Pr(E") & T'Amax 2K(K + 1)T
Amax.
2K(K + 1)1?
Combining the good event together, the regret is:
Regz (T)
B (I(E) + ((F)]]
T
E [A 1(8.) Amax
Σ [(E
1=1
E=
8 8log( 8log( 22K( + 1)2)
$
Amax
Σ A.+
Σ
A;
f(a))50
M(e))20
Applying v²² < a x final regret leads to simplified version, which
8 log
(K + +)1)
Reg(T)= = Amax +
Σ
max
2N,,1 max(A: 2wi,1, 03.0
A
AE[K]
E.2
Instance Independent Regret Upper Bound
Theorem 6. Choosing 6 2R(K+1yTT the gap independent bound of HybElttmUCB-RA satisfies:
(v (log(T) + Vinax .T -T))
min
/ KT log(T)
Σ
Saving(as),
kE[K]
8 Boogl Blog( (2((
2NN,11 maxfA: 2ur,,,, 03 03} and the optimal solution
where Saving(a.) min
the below linear programming problem:
max v.t;
s.t.
T 1// No.1
Wi [K],
Σ
iE[K]
2 0,4 2 0
Vi.j E [K].
Proof. The proof of this instance regret lower bound is symmetric the proof of the instance dependent bound of HybUCB-AR, which C.7.I and C.7.2 By the definition of regret bound and Claim 3 the expected
regret is upper bounded by:
Reg(? T)
(Aa)
2N
(1,.)
min 2 2N1 + (t)
log
2N, 2N1,a00 + TA, (t) W1,4()) 2
5z
Ta (t)
1
4N1,,00
log(1/52)
min 2' 2N1.A0) + +',
log
2N1.Aco + T' (1) ViLASO), 2V
T' (1)
(40)
The second term Equation 40) follows conventional regret analysis, as provided in Appendix C.7.2
Equation (34). The upper bound for the first term can be derived similarly by following the same technique in Section C.7.2 where we replace the term N,N,,(N,, + NV3) with N1.; and t. with t. 22, For the sake of
conciseness, omit the detailed of the proof here.
L
38

---

E.3
Regret Lower Bound
Theorem 7. Let A E (0, 1t) be the gap between the optimal arm and all suboptimal arms. The regret lower bounds of HybEIimUCB-RA satisfy:
(a) Instance-dependent bound:
22
8K A
(1-p)logT+ log A
max (2A WL N3
BAC
EE|
where C, are constants from Definition (b) Instance-independern bound:
1 Land wi Vi + 14, Mu with V, 2 11 -16l-
Ω min { (KRT. (V Vinaxx -T])
where T'. is the optimul solution to the following Linear Programming problem:
max Pif
T',
subject to
T' st No.
V
Σ E4=T, 2 0, 420. EE[K]
Proof. This proof follows similar structure to lower bound argument presented Appendix D Specifically, let & be fixed arm in {2, ... K}, we construct two instances and Q such that
N(u+ 1,1)
=i= if # 1.
pat N(u V
P.
1(
N(H + 1,
ifi=1, 1, if = k,
Q
Wh +2 Va, 1) ifi and of [N(1e"t 1)
< < x 24
Ve. Q
N(H 12,
otherwise,
1
if E [K]]LL,)].
where 1 and could be any values such that 1,t S V. for all [K]([) and 1ASt (p A)I s Vi. addition, P Iv implies Q Iv. Following the conventional analysis, we have:
Rege (T) = ((A)
(A()) Ep [T((T) 7(T))
2
2 ((A)=
2)
1
(((A)
(o(A)- ((A)) - -11 (T(Ti(T) (T/))))T////-1 -T (((A))
2) Ep [T((T)mmm777]] -(op)))))((())))))))))() - 2 Ep [T((T))mmssr
1
1
T
-(((())- -1))-1 1 Pr(Ti Pr(Ti> > T/2)
=T T ((A)
2
T
(a(A))
(T) 4T/2).
2
and
K Regg (T)
Σ AABO(TT(T 2 (o(A) Ee](i(T)] ((a(A) - 1)
Pr(Ti(T) T/2).
2
Following the same procedure we obtain:
TA
2CT Regp(T) Rega (T) >
exp( KL(P.Q))
(41)
32
where
KL(P.Q) Σ (LLL Σ Nos KL Q
[E[A]
For the first term, we have:
[T(T](T) KL Qi) = ET(Tu(T) (a(2A) 1/2)²
Ep [T
Σ
(42)
ie K
39

---

For the second term, let N₂ denotes the number of time we selected in each pair, we have:
Σ No KL(P Q::
No. 2( max
025 wx)))
1
Nu (5 maxt 2- 24 wk 51))
- N max 22 Wk, 0]
(max w4 )²,03
Nu max wa)² ,0.
(43)
Putting Equation 42 and Inequality 443 and 41
together, we have:
TA
(r[T
max -) 0}2
2C 2 Regp (T) + Regg (T)
exp
No
32
reorganize the structure of the above equation following Appendix D.I leads to the gap independent bound, which is:
8K
max
(2A (24
wi 0)2
(1 (1-p) log
log
N;
64C
K
as desired.
Gap-Ind hop-Independent Regret Bound. The proof of the gap- iap-independent lower bound largely follows the argument in Appendix D.2] with the only difference being the switch of the offline and online data. Therefore, we provide only sketch of the modified proof. In Case 1, since the offline and online share the same distributions, the switch does not affect the analysis. In Case 2 and Case 3, where the discrepancy hetween and Q appears only
online distributions, the divergence term is updated from the original expression to 2i=1 T: KL(P,, Q.) 27,- A, but the conclusion remains unchanged. The only modification lies in the boundary condition for each casc, which now compares 2 KT with T (Vmax + 1/ 1/VT.). This adjustment arises hecause, in the online-stochastic setting, we have Σ T, = T rather than 2T.
>x
Stochastic Bandits with Offline Relative Feedback: An Alternative Approach
As previously discussed, preference data typically provide less information compared to stochastic feedback. Estimating the underlying utility values μ4, for all E [K] solely from preference data is extremely challenging, unless additional structural assumptions are imposed. For the sake of theoretical completeness, we still adopt preference based model in Algorithm 2 algorithms cannot match performance vanilla UCB when offline data absent (i.e., when the offline dataset is empty) or provides no additional information.
and build upon the elimination framework. However, this class of
Algorithm 3 Offline Relative Online Stochastic: An Alternative Approach
Require: arm set A, offline dataset D {(A,, Aj, Yija),, i,j E [K]. (Na,) hyperparameter 5, and estimated bias Vi,, for all (a;, a,) pairs.
Initialization: Let C A, T; = 0, vi [K]. and for all i,j e [K]. let UCB(a;, a;) = +o0,
UCB hyh (a;, a2) P. V
log 1/6.
N..
1: for 1, do
2: Select Action A(t) arg maxa,ec UCB(a,).
3: Update selection times TA(o) = TA,0) + 1.
4: Record observation Xi, for = A(t), k TA(0-
5: For all pairs i,j E [K]. update UCB, byb according equation p
10
6: C= C Ma, C, aa (aa(a s.t. UCB ag) 11
7: end for
In practice, more tlexible algorithmic designs can be considered. In Algorithm 3 we present an alternative approach that aligns with vanilla UCB by utilizing UCB and lt separately. Specifically, we construct the
40

---

candidate set ci using hybrid data, and then apply the standard UCB selection rule to choose A(l) within this
While such variants may perform well empirically, they lack the strong theoretical guarantees provided by Algorithm [
particular, these methods longer ensure balanced exploration across arms during the online phase. As a result, the sample counts Tt(t) for each arm a, E C can become highly imbalanced.
Moreover, since vanilla UCB docs not guarantee theoretical lower bound on min (T)))) for all i E [K] the
confidence radius in UCB given by 1/ (NL, + T. (0200
degrade to V1/N., the worst case.
(.0+)7(())
Thereby. the theoretical analysis falls back to naive two-stage procedure: (i) using offline data eliminate suboptimal arms, followed by (ii) applying vanilla UCB to the surviving set. Under this simplified strategy, the regret bound becomes:
(Σ T
(T) =0
ALEC
where A denotes the set arms retained after offline filtering. Compared Algorithm D. such two- phase strategies lack a continuous and elegant theoretical guarantee throughout the learning process. Bridging this gap by designing practical algorithms that maintain strong regret guarantees even under hybrid and heterogeneous reedback-remains important direction for future work.
G Supplemental Experiments
We conduct comprehensive evaluation of HybUCB-AR and HybElimUCB -RA in hybrid bandit settings with heterogeneous offline-online feedback. The experiments aim demonstrate the algorithms' robustmess and superiority over established baselines across diverse scenarios. Our evaluation encompasses two primary environments: (I) synthetic datascts, where we assess scalability with varying numbers of arms K and sensitivity to key parameters, (2) real-world datasets, where we validate practical efficacy using authentic data. For all experiments, we set of random seeds to ensure the reproducibility of the experiments. Our experiments were implemented Python.
G.1 Synthetic Data Experiments
To evaluate the performance of HybUCB-AR and HybElimUCB--R in controlled settings, conduct experi- ments on synthetic datasets. In the first set experiments, we assess the algorithms' scalability by varying the number of arms K, comparing their performance against established basclines to demonstrate their effectiveness across different scales. In the second set of experiments, we analyze the sensitivity of HybUCB-AR and HybElimUCB--AA to key parameters (N;, A, and V/),, focusing how different parameter values affect their convergence behavior. The synthetic environment allows precise control over reward distributions and feedback mechanisms, enabling robust analysis of algorithmic behavior.
G.1.1 Data Generation
We generate a synthetic K-armed bandit environment to simulate the heterogeneous feedhack setting. For each arm a; E A, generate the offline and online reward means, μ4, and μt, as follows. The offline mean of the best arm, a is drawn uniformly from [0.5 A, 1]. where A E (0, 0.5) denotes the gap between f and pa we then set n2 141 A. For the remaining K 2 arms, alll is drawn uniformly from [0, p2"). The online reward mean is defined as
N4 14 oll
d; bias,
where d, E (-,, is chosen uniformly at random,
Vi [K].
All absolute feedback {i, Xz} > for each i E [K] is generated from Gaussian distribution. N N(ss, 1), and relative feedback ji. Yi,} for all i,j E [K] is generated from a Bernoulli distribution Bernoulli(p..)) according to the Bradley-Terry model.
G.1.2 Experiments for HybUCB-AR
HybUCB-AR leverages offline absolute rewards to enhance online dueling bandit learning. We compare it against three baselines: HybUCB-AR without offline data (N, 0), Relative Upper Confidence Bound (RUCB) (Zoghi et al. 2014), and Interleaved Filter (IF2) (Yue et al. 2012).
Performance Comparison and Scalability (K 8, 16, 24, 32) Setup. We evaluate HybUCB-
scalability across K 8, 16, 24, 32 arms. We set the sub- sub-optimal gap A = 0.1. the affline-onling bias to 0.I. and the number of offline samples N; 500. Each algorithm for T 50, 000 rounds with 100
41

---

K--18
CX24
XX-32
000
5X0
3000
3000
3000
fo.rd
Fourd
found
found
Figure 2: Average cumulative regret of HybUCB-AR for K = 8, 16, 32 over 100 runs, with shaded area indicating standard deviation.
Varying Read
Varying
Varying V.
660
500
130
100
200
Naaio
Figure 3: Parameter sensitivity HybUCB-AR, showing effects of N,, A, and V, on cumulative regret, with vertical lines indicating standard deviation every 6,000 rounds.
independent trials. We set 0.02, RUCB, we set the confidence parameter a 0.51, following Zoghi at. (ral))2001))
Results. Figure shows the average cumulative regret over 100 trials, with shaded area indicating standard deviation. Without offline data, HybUCB-AR, by maximizing the informative pair in the confidence set, achieves a regret reduction of 15-40% compared RUCB across all K. The performance advantage grows with larger K, highlighting its scalability. And across all K, HybUCB-AR surpass baseline when heterogeneous offline data is included.
Parameter Sensitivity Analysis Setup. analyze HybUCB-AR's sensitivity three parameters: For all i [K]. we set the number of offiine samples, N, E {100, 300, 500 the sub-optimal gap E (0.05, 0.1, 0.2), and the offlinc-online bias, V2 E (0.01, 0.05, 0.1}. We fix K 20, run for 30,000 rounds with 100 trials, and default values (N, 500, A = 0.1, V 0) for all parameters unless otherwise specified.
Results. Figure 3 shows the cumulative regret. As N; increases, the algorithm converges faster, leading to lower cumulative regret. Smaller A increases regret due harder differentiation. Larger V4 reduces the ability to utilize offline data, resulting in slower convergence. One key insight does not decrease linearly with the size of the offline data, while the increase in regret caused by bias shift grows approximately linearly with the magnitude of the bias. This observation is consistent with our theoretical regret analysis in Theorem
accumulated regret
G.1.3 Experiments for HybElimUCB-RAA
HlyEElimUCB-R. uses offline relative preferences to improve online stochastic learning. We compare it against four baselines: HybElimUCB-RR. without oflline data (with N; 0). Explore-Then-Comee (ETC) (Robbins
1952. , Upper Confidence Bound (UCB) (Lai and Robbins 1985), and Thompson Sampling (TS) (Agrawal and
Goyal 2013).
Performance Comparison and Scalability (K = 8, 16, 24, 32) Setup. We evaluate HybElimUCB-
RA's scalability across K 8, 16, 24, 32 arms. The sub-optimal gap A is set to 0.1. the offline-online bias to 0.01, and the number of offline samples to N; 500. Each algorithm runs for T = 30, 000 rounds with 100 independent trials. HybElimUCB--R and UCB assumes Gaussian prior with variance 1.
0.05, ETC uses exploration phase of 500, and TS
Results. Figure shows the average cumulative regret over trials, shaded area indicating standard deviation. When leveraging offline relative preferences, HybElimUCB- --B-RA outperforms all baselines. The performance advantage grows with larger K, highlighting its scalability. Without offline data, HybElimUCB RA matches the performance of ciminationn-asee UCB.
42

---

Cr224
Cx32
3000
1250
200
10.04
K0.ed
nest
Thompsariamppig
Figure 4: Average cumulative regret of HybElimUCB-RA for K -8, 8,16, 24, 32 over 100 trials, with shaded area indicating standard deviation.
Verying for fieed and
Verying for nwed N, and
Verying V. for tixed and
000
100
100
A-50
230
K-331
9931
1993 23303
35000
1993
70006
3000
18332
19660
20000
20000
99313
Figure 5: Parameter sensitivity of HybElimUCB-RR, showing effects of No. A, and V/ on cumulative regret, with vertical lines indicating standard deviation every 6,000 rounds.
Parameter Sensitivity Analysis Setup. analyze HybElimUCB-RAA. sensitivity to three parameters: For all i E [K]. we set the number offline samples N, E {100, 200, 500), the sub-optimal gap E (0.05, 0.1,0.1....... 0.2), and the offline-onlien bias, V2 E f0.01, 0.05, 0.1}. We fix K 10, run for 25,000 rounds with 100 trials, and use default values (N. 100. A 0.1, V, 0.01) for all parameters unless otherwise specified.
Results. Figure 5 shows the cumulative regret, with vertical lines indicating standard deviation every 6,000 rounds. N; increases, the algorithm converges faster, leading to lower cumulative regret. Smaller A increases regret due to harder arm differentiation. Larger VG reduces the ability to utilize offline data, resulting in slower convergence. This result is similar to the result we obtained in Figure 3 demonstrating the consistent of our algorithm.
G.2 Real Data Experiments
We evaluate HybUCB-AR and HybElimUCB-Re RA MovieLens-20M and Yelp datasets to validate their performance in collw hybrid bandit settings. Experiments compare both algorithms against established baselines, leveraging offline data to enhance online learning, All experiments are implemented in Python.
G.2.1 Data Preparation
The MovieLens-20MM dataset contains 20,000,000 ratings (1-5) for movies. We normalize ratings [0,1] by dividing by 5, select movies with at least 100 ratings, take the top 100 by rating count, and randomly sample K = 10 movies as arms. For SybUCB-AR, offline data consists of 100,000 normalized ratings. For HybElimUCB-RA offline data includes 1,000 preference duels per arm pair, generated by sampling ten ratings per and comparing their means.
The Yelp dataset, sourced from the Yelp Academic Dataset, includes business reviews with ratings (1-5). normalize ratings to [0. 1]. select businesses with least 100 ratings, take the top 100 by rating count, and businesses. Offline data follows the same structure as MovieLens.
randomly sample
Online feedback is generated using the environment module designed by us. For HybUCB-AR, duels sample 3 ratings arm, with the higher average rating winning (ties resolved randomly). For HybElimUCB RA, rewards are the average of 30 sampled ratings per arm.
43

---

MovieLans
Yalp
120
Cimmatte Baggee
60
2002
5002
3000
0000
HybUCB-OR
HYSUCHBAR without
IteerisseedFiter
Figure 6: Performance of HybUCB-AR AR on Movielens 20M (K 10), with shaded areas showing standard deviation across 50 trials.
Mov elaens
Yllp
302
182
Cummintiee Regret
132
300
100
75-
2000
10000
2000
HybEImUCD-RO
HyBE IMUCD without offinne
ThompsonSampiing
Figure 7: Performance of HybElimUCB--R -RA on MovieLens-2001 and Yelp with (K = 10). Shaded areas showing standard deviation across runs.
G.2.2 Experiments for HybUCB-AR
HybUCB-AR leverages offline absolute rewards improve online dueling bandit learning, using V-matrix defined (Ve.)).e((K). compare it against HybUCB-AR without offline data (Nv 0), RUCB (Zoghi ct 2014). and Interleaved Filter 2 (IF2) (Yue 2012).
Performance Comparison Setup. We set K = 10, run each algorithm for 10,000 rounds over 50 trials. The enviromment module samples 3 ratings per amm for duels. We set dz 0.02. Offline data comprises 100,000 normalized ratings.
Results. Figures 6 show the average cumulative regret, with shaded indicating standard deviation. Without offline data, HybUCB-AR outperforms RUCB by 15-25% on both datasets. HyhUCB-A AR shows same gond performance as in the synthetic experiments.
G.2.3 Experiments for HybElimUCB-RA
HybElimUCB--RA offline relative preferences enhance online absolute reward learning, employing same V-matrix as HybUCB-AR. We compare it against HybElimUUCB-RA without offline data (N; 0).
Explore-Then-Coomee (ETC) (Robbins) 1952, Upper Confidence Bound (UCB) (Lai and Robbins 1985 and
Thompson Sampling (TS) (Agrawal and Goyal 2013).
Performance Comparison Sctup. We K
each algorithm for 10,000 total pulls 50
trials. The environment module samples 30 ratings per arm compute rewards. HybElimUCB-R, use & = 0.05, ETC uses an exploration phase of 200 pulls per arm, and TS assumes a Gaussian prior with mean 0.5 and variance 1. Offline data consists of 1,000 relative preference duels per arm pair.
UCB
Results. Figure 7 shows the average cumulative regret. In two real data environments, HybElimUUB..N combined with offiine data can achieve good results and is better than the baseline.
44

---

H
Useful Lemmas
Lemma 8 (Chernoff Inequality, Theorem 5.3 in Lattimore and Szepesvári 2020 ). If X is a sub-Gaussian, then for any
E²
Pr 2 e) S exp
2
Lemma 9 (Hoeffding's 's Lemma). Let X be any real-valued random variable such that a S X S b almost surely, Le., with probability one. Then, for all X E R.
2² 12 a)²
B
AX
exp
[XB[a]
8
equivalently.
MX EX-
(22
I exp
Lemma 10 (sub-Gaussian Property of Lipschitz Transformations). Let X be random variable that is
sub-Gar Gaussian, meaning B[[eAx] < x²2021 for all E If R + IR is L-Lipschitz continuous, then f(X)
is 2La sub-Gaussian
Proof. A related result appears in Theorem 5.5 of Boucheron al. (2013 which shows that f(X) Lo sub-Gaui Sub-Gaussian when is strictly Gaussian. general sub-Gaussian we establish that f(X) 2Lo
sub-Gaussian.
Let Y be an independent copy of X. We aim to bound the moment-generating function of (f(X) (x)))
Consider constant > 0:
(f(X) - E[S(X))2
(f(X) -((X)-B((()))))
exp
exp
(f(x) -(()) )
(f(z) E[S()11)
P(X E exp
P(X de)E
exp
(J(X)- -((1))
E
exp
6²
L²(X - -1)
< E
exp
2L2 x2 + 22
S
exp
c²
x2
13
exp
C²
[4L. x2
K E
exp
2.
c²
Here, the second equality uses the of total expectation; the first inequality applies Jensen's inequality: the second inequality uses the L-Lipschitz property, If(x) - f(v) I L|æ yl: the third inequality uses (X - YY2 < 2X² + 2Y2; and the final steps exploit the independence of X and Y. The last inequality holds
because X is nub-Gaussian, so 10 < 2. Setting AL" / 1/0", we 2La sub-Gaussian, desired.
2oo. Thus, f(X) is
Lemma 11 (MVUE). Let Ns, R2 be independent estimator of μ. with variance of and oz, then the minimum variance unbiased estimator of X is:
X
02
0
with variance oi03 o7-03
45


Reviews:
[{"review_id": "LFY2LbeXw3", "reviewer": "Reviewer_eSEX", "summary": "This paper is the first work to analyze hybrid MAB settings with heterogeneous offline-online feedback, addressing two scenarios:\n- Offline preference data $\\to$ online absolute rewards\n- Offline absolute data $\\to$ online dueling bandits\n\nThis paper proposes two algorithms HybUCB-AR and HybElimUCB-RA for Offline absolute data + online dueling bandits and Offline preference data + online stochastic bandits, respectively.\n\nEmpirical results show that both algorithms outperform state-of-the-art online methods when using heterogeneous offline data", "questions": "See weaknesses.", "limitations": "Yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n- Providing both theoretical foundations and practical performance improvements while maintaining safety guarantees.\n- Although I didn't go through all the proof details, the theoretical part looks correct and well-organized.\n\nWeaknesses:\n- The results seem to be a heterogeneous version of [1]. While in practice considering heterogeneous data type is useful, the novelty in theoretical aspect is not enough.\n- The algorithm follows the standard UCB-based exploration technique and incorporate the information from offline dataset by taking the minimum of two UCB rewards, which is not surprising. And the algorithms require knowledge of the bias for each data, which is not practical enough.\n\n[1] Wang Chi Cheung, Lixing Lyu. Leveraging (Biased) Information: Multi-armed Bandits with Offline Data.", "was_revised": true, "final_justification": "After reading the rebuttal from the authors, I still believe that this result is an extension of previous work[1], since handling offline-to-online conversion by taking min of UCB is not so interesting to me.\n\n[1] Wang Chi Cheung, Lixing Lyu. Leveraging (Biased) Information: Multi-armed Bandits with Offline Data.", "rebuttal": "# Response to Reviewer eSEX\n\nWe thank the reviewer eSEX for the valuable comments and suggestions. Please find our detailed response below. \n\n## 1 .Theoretical novelty\n\nWe present our theoretical contributions from three distinct perspectives: (1) the analytical advancements over [1] in handling the off2online learning problem with reward bias; (2) the novelty of addressing heterogeneous feedback; and (3) the improvements over [2] in tackling the (pure online) dueling bandit problem.\n\nAlthough our algorithmic framework appears similar to that of [1] in handling reward bias, our theoretical analysis fundamentally differs. We point out a hidden issue in [1]: to achieve a regret bound with a \"saving\" term, their analysis doubles the coefficient of the standard $\\log T / \\Delta$ term of UCB. Specifically, traditional online UCB yields a regret of the form $C \\log T / \\Delta$ where $C$ is a constant term and $\\Delta$ is the minimum preference gap. However, the regret upper bound for the hybrid setting in [1] is $2C \\log T / \\Delta - \\mathrm{Saving}$. This means that when the $\\mathrm{Saving}$ term is small, their regret can even exceed that of pure online UCB. Our analysis resolves this issue. Rather than first bounding $N_i$ (the number of offline samples for arm $i$) to derive a regret of the form $C \\log T / \\Delta^2 - \\mathrm{Saving}$, and then artificially enlarging the threshold $T_i$ (number of online pulls) to $2C \\log T / \\Delta^2 - \\mathrm{Saving}$ to leverage the properties of pure online UCB (Appendix B.2 Sub-case 1(b) in [1]), we avoid reasoning about the range of $N_i$ altogether, and instead directly analyze the required $T_i$ for eliminating suboptimal arms under hybrid UCB parameters (Appendix C.5 in our paper). This avoids unnecessary pessimism in the standard term and yields a regret of the form $C \\log T / \\Delta - \\mathrm{Saving}$. While the asymptotic order remains the same, our analysis constitutes a fundamental advance: it retains the intrinsic performance of pure online UCB without incurring the additional overhead present in [1], demonstrating a deeper understanding of the algorithm's optimality for hybrid learning. \n\nPrior works on hybrid learning have considered absolute and relative feedback separately. However, combining the two remains a challenging and largely unexplored direction. Though work [3] considers to utilize different types of reward, their approach is to construct candidate sets independently for each feedback type. In contrast, our approach introduces a unified statistic $p_{i,j}^{\\text{hyb}}$—along with a corresponding confidence radius—that simultaneously incorporates both absolute and relative feedback. This unified estimation strategy allows for more efficient use of all available data, particularly in scenarios where each individual feedback signal may be insufficiently informative on its own. We believe that this hybrid estimator is of independent interest beyond our specific setting, and can provide a useful foundation for addressing heterogeneous feedback in broader learning problems.\n\nIn the reduced pure online setting with no offline data, our analysis for the dueling bandits also leads to an improved regret bound over [2]. Specifically, [2] establishes a regret upper bound of $O\\left(\\sum_{i \\le j} \\frac{\\log T}{\\min\\set{\\Delta_i, \\Delta_j}} \\right)$. By modifying the algorithm to select arm pairs that maximize information gain, we improve the regret bound to $O\\left(\\sum_{i \\le j} \\frac{\\log T}{\\max\\set{\\Delta_i, \\Delta_j}} \\right)$.\n\n[1] Cheung, W. C., & Lyu, L. (2024). Leveraging (Biased) Information: Multi-armed Bandits with Offline Data. In International Conference on Machine Learning.\n\n[2] Zoghi, M., Whiteson, S., Munos, R., & Rijke, M. (2014). Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem. In International Conference on Machine Learning.\n\n[3] Wang, X., Zeng, Q., Zuo, J., Liu, X., Hajiesmaili, M., Lui, J., & Wierman, A. (2025). Fusing Reward and Dueling Feedback in Stochastic Bandits. In International Conference on Machine Learning. In International Conference on Machine Learning.\n\n\n\n## 2. The valid bias bound $V$\n\nAs rigorously proven in Section 3 of [1] and [4], no algorithm can outperform, or even match, the performance of a purely online approach in the absence of any prior knowledge about bias. This fundamental lower bound underscores the necessity of incorporating some form of prior information when attempting to leverage offline data effectively.\n\nTo the best of our knowledge, existing theoretical works that address distributional bias typically assume that an upper bound $V$ is known in advance [1], or require the bias to exceed a certain threshold to safely exclude misleading offline data [4]. Compared with [4], our algorithm makes no distributional assumptions about the offline or online data. It only requires a hyperparameter $V$, which does not need to be exact—any valid upper bound on the bias suffices. When this bound is tight, the offline data can be effectively utilized, yielding improved performance. Even under limited prior knowledge and loose bias bounds, our method still matches the performance of vanilla UCB, thus ensuring robustness.\n\nFor practical use, we recommend estimating the bias through a small number of online interactions, which can provide a reasonably prior. We agree that further reducing the reliance on the parameter $V$ is an important and promising research direction, and we leave this as future work.\n\n\n[4] Qu, C., Shi, L., Panaganti, K., You, P., & Wierman, A. (2024). Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data. In Artificial Intelligence and Statistics.\n\n\n\n## 3. UCB-based algorithm\n\nWe agree that UCB is a well-established method in a broad range of online learning applications. For our considered hybrid learning problem, it is natural and intuitive to leverage offline data to update UCB-style confidence intervals while controlling for bias. The core challenge in our work does not lie in the use of UCB itself, but in designing principled UCB-style statistics that can effectively handle heterogeneous feedback and providing regret guarantees that are no weaker than their pure online counterparts. To the best of our knowledge, no prior work has addressed these challenges."}, {"review_id": "ZJInSxg2qi", "reviewer": "Reviewer_Q1f6", "summary": "This paper studies how users can utilize two different types of heterogeneous data that arise within a single game. In particular, motivated by the recent emergence of RLHF, it investigates how two commonly encountered observation types—preference-based observations and conventional direct bandit rewards—can coexist and complement each other. The paper further explores how such offline data can be mutually beneficial. Moreover, it presents the results in a highly general setting that allows for heterogeneity not only in observation types but also in the underlying data distributions.", "questions": "Please check the Strength & Weakness section above.", "limitations": "No.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This is a personal opinion as a reviewer, but I found this paper to propose an interesting approach to fusing two types of data that, while intuitively complementary, are not straightforward to combine. The significance and novelty of the topic addressed in this work are, at least from my personal perspective, quite clear.\n\nMoreover, the paper is formulated in a very general framework that can accommodate heterogeneous cases that are likely to arise in practice. By employing a \"minimum UCB\" approach, the authors propose a mechanism that naturally discards offline data when its quality is not sufficiently helpful for online learning. I found this to be a particularly interesting idea.\n\nRegarding **soundness**, I unfortunately was not able to carefully verify all the proofs. However, assuming the results are correct, the fact that the authors provide a matching lower bound (Theorem 2) to their upper bound strongly supports the optimality of their results. The logical flow and the implications drawn by the authors seem reasonable to me, and while my confidence is not high due to limited verification, I intuitively believe there is no major issue with the soundness. I plan to examine the validity of the proofs more closely during the rebuttal period.\n\n---\n\n**Weaknesses**:\n\nA few points remain unclear:\n\n1. The authors appear to have made efforts to clearly delineate their contributions. However, the results themselves depend on many variables and are presented in quite a complex form (e.g., involving a prior upper bound referred to as $V$, or a quantity represented as $\\tau^*$, which arises from some complicated optimization). While it is clear that the \"saving\" offers some degree of benefit, it is difficult to assess how impactful or innovative this actually is. It would be helpful if the authors could provide a carefully chosen, perhaps even \"cherry-picked,\" example that most dramatically illustrates the benefit—preferably in an environment where offline data can dramatically help, such as a homogeneous setting where greedy algorithms suffice online, and then quantify how many offline samples are needed to guarantee such behavior.\n\n2. Remark 4 is difficult to understand. Is the author claiming that there are situations in which preference-based feedback is more useful than direct reward observations? While I appreciate the authors' honesty in noting this, I think the explanation—that it is due to subgaussianity and the BT model—could be expanded. A mathematical example or deeper explanation of why preference feedback is more helpful in such cases would be much appreciated.", "was_revised": true, "final_justification": "The authors have responded sincerely to my questions, and I still believe that the paper’s value—providing a general approach to combining two different types of data—is sufficient. Based on the other reviewers’ comments, it appears they share a similar impression. Therefore, I have decided to maintain my current score.", "rebuttal": "# Response to Reviewer Q1f6\n\nWe thank the reviewer Q1f6 for the valuable comments and suggestions. Please find our detailed response below. \n\n## 1. Example Demonstrating Offline Data Effectiveness\n\nIn Remark 3, we briefly discuss the conditions under which offline data becomes beneficial, with a comprehensive analysis deferred to Appendix C.6. Here, we present a special case under which the regret upper bound simplifies significantly, thereby helping readers better understand the effect of offline data.\n\nConsider the case where $V_{i,j} = 0$ and offline data is uniformly distributed (i.e., $N_i = n$ for all $i \\in [K]$). Under this scenario, the regret upper bound simplifies to:\n$$\nO\\left( \\sum_{i \\leq j} \\frac{\\Delta_i + \\Delta_j}{2} \\left[ \\max \\left\\\\{ \\frac{16\\operatorname{log}(\\sqrt{2K(K+1)}T)}{\\max\\\\{\\Delta_i^2, \\Delta_j^2\\\\}} - \\frac{n}{2}, 0 \\right\\\\} \\right] \\right)\n$$\n\n\nand\n\n$$\nO\\left( \\sqrt{\\frac{2K(K+1)T^2 \\log T}{nK(K+1) + 4T}} \\right),\n$$\nrespectively. For the instance-dependent bound, the effectiveness of offline data is captured by the $-\\frac{n}{2}$ term, while for the instance-independent bound, it is reflected in the $nK(K+1)$ term. Both bounds demonstrate that regret approaches zero (a constant) as the amount of offline data grows sufficiently large. To determine when online exploration is unnecessary for arm pair $i, j \\in [K]$, we compute:\n\n\\begin{align*}\n\\frac{16\\log (\\sqrt{2K(K+1)}T)}{\\max\\\\{\\Delta_i^2,\\Delta_j^2\\\\}} - \\frac{n}{2} &\\leq 0, \\\\\\\\\nn &\\geq \\frac{32\\log (\\sqrt{2K(K+1)}T)}{\\max\\\\{\\Delta_i^2,\\Delta_j^2\\\\}} .\n\\end{align*}\nWe will put these discussions in the next version for better clarity.\n\n**Note:** To help better understand how the savings depend on key parameters, we provide experimental illustrations in Appendix G (Figures 3 and 5), showing the effects of $V_{i,j}$, $\\Delta_i$, and $N_i$ on regret convergence rate.\n\n## 2. Comparisons with homogeneous offline data\n\nRemark 4 compares the utility of homogeneous (relative feedback) versus heterogeneous (absolute feedback) offline data in the HybUCB-AR algorithm. The logical flow proceeds as follows: (1) First we directly compare the mathematical form of the confidence radius, which suggests that relative feedback appears more efficient. (2) Further analysis of the derived result reveals that the preliminary conclusion lacks robustness (due to model assumptions). (3) Finally, we clarify absolute data is generally more effective. Here, we present our reasoning process in detail. \n\nTo compare the effectiveness of samples, a key metric for evaluating data utility is the convergence rate of the confidence radius with respect to the number of samples. As shown in Equation (4) in our paper, when the bias is zero, the confidence radius for heterogeneous offline data is:\n\n\\begin{align*}\n\\sqrt{\\frac{1}{2} \\cdot \\frac{\\log(1/\\delta_t)}{T_{i,j} + \\frac{N_i N_j}{N_i + N_j}}} \n\\end{align*}\n\nFor homogeneous offline data (relative feedback), the confidence radius (While the paper focuses on the heterogeneous case, the homogeneous version can be derived analogously) is:\n\n\\begin{align*}\n\\sqrt{\\frac{1}{2} \\cdot \\frac{\\log(1/\\delta_t)}{T_{i,j} + N_{i,j}}}.\n\\end{align*}\n\nConsider the homogeneous case where $N_{i,j} = n$. To achieve an equivalent or tighter confidence radius using heterogeneous offline data, we solve:\n\n\\begin{align*}\n\\min \\quad & N_i + N_j \\\\\\\\\n\\text{s.t.} \\quad & \\frac{N_i N_j}{N_i + N_j} \\geq n, \\\\quad N_i, N_j\\geq 0\n\\end{align*}\n\nThis yields $N_i = N_j = 2n$, indicating that absolute feedback requires at least twice as many samples as relative feedback to achieve the same confidence radius. This result suggests that relative feedback is more efficient in this context, which may seem counterintuitive.\n\nAt first glance, this appears anomalous since absolute feedback typically provides more information per sample. However, upon closer examination, we find this phenomenon is fundamentally tied to the Bradley-Terry model and our sub-Gaussian assumptions:\n\n- **Relative feedback** (modeled as Bernoulli comparisons) is inherently 1/2-sub-Gaussian (Lemma 1.1, Appendix C.1).\n- **Absolute feedback**, while initially assumed to be 1-sub-Gaussian, becomes 1/2-sub-Gaussian after transformation through the Bradley-Terry model (Lemma 10, Appendix G).\n\nCrucially, these results are model-dependent: Different modeling assumptions (e.g., alternative link functions or sub-Gaussian parameters) would alter the weighting between $ T_{i,j} $ and $ \\frac{N_i N_j}{N_i + N_j} $ in Equation (\\*). Thus, data utility depends not only on the data type (absolute vs. relative), but also on the underlying statistical assumptions.\n\nOn the other hand (from the \"In practice\" sentence in Remark 4), absolute feedback inherently contains more information and thus offers greater practical utility. For example:\n\n- **Relative feedback** ($N_{i,j}$) only provide information about the relative performance between arms $i$ and $j$.\n- **Absolute feedback** ($N_i$) enables joint estimation of multiple probabilities ($p_{i,j}, p_{i,k}, \\dots$) by combining data across all arms ($N_j, N_k, \\dots$).\n\n\n\nThis fundamental difference explains why absolute feedback often proves more valuable in real-world applications despite its theoretically higher sample requirements under specific model assumptions. We will refine the presentation in the next version of the paper."}, {"review_id": "JLvv8q6n2e", "reviewer": "Reviewer_qfCy", "summary": "The paper analyzes the hybrid multi-armed bandit setting, where the learner has access to an offline dataset before interacting with an online learning environment. Interestingly, this setting considers the heterogeneous across the offline versus online: one is the preference relative data, the other is the typical reward data.\n\nEven though Agnihotri et al., 2024 have studied a similar setting previously, in this paper, the authors also analyze the distribution shift problem, where the offline dataset may not be informative to the online phase. I think that the warm-start setting with heterogeneous data and distribution shift is a very interesting and practical problem.\n\nThe authors provide the instance-dependent and instance-independent bounds for both the lower bound and the upper bound of their proposed algorithms, for both of their settings. They also provided an experiment section to demonstrate the effectiveness of their algorithms.", "questions": "Already discussed above.", "limitations": "The author should discuss the limitations clearly in the paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality: The submission is technically sound. The theorem's results make sense to me, although I haven't checked all the proofs.\nThe idea of using pessimism to address mis-specification (or distribution shift in this case) is valid and well-known on a high level, but its application to construct the confidence set in this paper is novel.\n\nClarity: The submission is clearly written and organized. Still, it would help a lot if the authors gave a high-level and intuitive explanation for their algorithms and analysis. For example, I still don't have a good high-level understanding of the exploration term in equations 4 and 10, as well as the significance of the terms in the upper and lower bounds.\n\nAnother suggestion on clarity is on the Remarks. I think they are all important discussions, but they may be written in a better way. For example, Theorem 1b bounds include the term Saving(a_i, a_j). I understand that keeping it like this helps generalize different amounts of saving, which is problem-dependent, but it makes the reader have a harder time evaluating whether the saving can make a difference to the bound or not. Instead of making a remark like the one in the paper, maybe you can just add a corollary that, assuming x and y, the upper bound is z.\n\nSignificance and Originality: This paper analyzes a practical setting, with novel analysis and algorithms. I think there's a significant contribution from this compared to the previous work. I think the related work section shows good and relevant previous and related work.\n\nNotes:\n- I'm not sure if the instance-dependent upper-bound and lower-bound in Theorems 1 and 2 \"closely match\" or are tight.\n- I can't comment on the correctness of the proof of the significance (impact) of the bounds (about how much this paper improves on the previous results)", "was_revised": true, "final_justification": "I will maintain my positive score. I wish you the best of luck with the final results.", "rebuttal": "# Response to Reviewer qfCy\n\nWe thank the reviewer qfCy for the valuable comments and suggestions. Please find our detailed response below. \n\n## 1. High level intuition\n\n### 1.1 Intuition of the algorithm design\n\nThe purpose of our algorithm is to effectively utilize offline heterogeneous data to enhance online multi-armed bandit (MAB) learning by extending the UCB framework. Intuitively, when there is no bias and the data is homogeneous, it is straightforward to directly use offline data to estimate $\\mu_i$ or $p_{i,j}$, for all $i, j\\in [K]$. However, under our setting, two questions would arise:\n\n1. How to construct a unified statistic and an upper confidence bound for heterogeneous data?\n2. How to deal with the potential bias in the offline data?\n\nTo address the first challenge, we construct the unified statistic $p_{i,j}^{\\text{hyb}}$ using the Bradley-Terry model and the sub-Gaussian property of the data (Lemma 1, Appendix C.1). The detailed construction of $\\text{UCB}^{\\text{hyb}}$ (Equations 4 and 10) is based on rigorous theoretical analysis, which is presented in the next section.\n\nFor the second challenge, we introduce a valid bias bound that confines the distributional shift within a predefined region. Since the precise bias is unknown, our approach is to conservatively incorporate the bias term into the unified statistic, forming $ \\text{UCB}^{\\text{hyb}} $. However, naively applying $ \\text{UCB}^{\\text{hyb}} $ would yield suboptimal results—for some arms, the bound may be loose and it lacks information about the shift direction. To address this, we adopt a \"minimum UCB criterion\": When $ \\text{UCB}^{\\text{hyb}} < \\text{UCB} $, offline data helps reduce online exploration; conversely, when $ \\text{UCB}^{\\text{hyb}} \\geq \\text{UCB} $, offline data provides no benefit, and we revert to the vanilla upper confidence bound.\n\n### 1.2 Intuition of the algorithm analysis\n\nSimilar to existing UCB algorithms, our theoretical analysis is mainly derived from two steps:\n\n1. Define a good event, such that the real value of the UCB statistic lies within the estimated confidence region with high probability (e.g. $1-\\delta$).\n2. Under the good event, for a given time step $T$, find an upper bound on the number of times each arm (or arm pair) can be selected.\n\n\nTo address the first issue, we introduce Equations (4) and (10). Given the presence of bias and heterogeneous data, their mathematical formulation is complex, as shown in the equations. The design of these equations is to ensure the probability of the good event (Equation (12) in our paper), with details provided in Lemma 3 (Appendix C.3).\n\nThe intuition behind the second step stems from the following key observation: as sample sizes increase, confidence radius  contract. Once these radius  become sufficiently small, the UCB of any suboptimal arm will satisfy:\n$$\n\\mathrm{UCB}(a_i)<\\mu_1<\\mathrm{UCB}(a_1),\n$$\nThis inequality guarantees that suboptimal arms will no longer satisfy the algorithm's selection criterion. We formalize this intuition in Lemma 4 and Lemma 5 (Appendix C.4–C.5). \n\nFinally, the regret upper bound is derived by combining the regret under \"bad\" event (with low probability, bounded by a constant) and the sum of each arm's regret under good event, computed as the product of its selection frequency and $\\Delta_i$.\n\n## 2. Clarifying the \"Saving\" term with a corollary\n\nFor Theorem 1(b), the Saving term follows the same formulation as in Theorem 1(a). The transition from an instance-dependent bound to an instance-independent bound involves purely mathematical transformations. The explicitly mathematical expression of the Saving term is: \n$$\n\\text{Saving}(a_i,a_j)=\\frac{\\Delta_i+\\Delta_j}{2}\\cdot\\frac{N_iN_j}{N_i+N_j}\\cdot\\frac{\\max\\\\{\\max\\\\{\\Delta_i,\\Delta_j\\\\}-4\\omega_{i,j},0\\\\}}{\\max\\\\{\\Delta_i,\\Delta_j\\\\}}.\n$$\nRegarding Remark 2, as you pointed out, since the \"Saving\" term is rather complex, providing a special case along with its regret upper bound could help readers better understand the effectiveness of offline data. Building on the discussed approach, we present the following corollary:\n\n**Corollary**: When $V_{i,j} = 0$ and offline data is uniformly distributed (i.e., $N_i = n$ for all $i \\in [K]$), the regret upper bound reduces to:\n$$\nO\\left(\\sum_{i\\leq j}\\frac{\\Delta_i+\\Delta_j}{2}\\left[\\max \\left\\\\{\\frac{\\log T}{\\max\\\\{\\Delta_i^2,\\Delta_j^2\\\\}}-\\frac{n}{2},0\\right\\\\}\\right]\\right),$$\nand \n$$\nO\\left(\\sqrt{\\frac{2K(K+1)T^2\\log T}{nK(K+1)+4T}}\\right)\n$$\nrespectively. \nUnder this setting, the contribution of offline data to regret reduction is captured by the terms $-\\frac{n}{2}$ and $nK(K+1)$, respectively. As the amount of offline data becomes sufficiently large, the regret upper bound approaches a constant.\n\nThis presentation will be refined in the next version of the paper.\n\n\n\n## 3. Discussion about upper and lower bounds\n\nWe compare the upper and lower bounds separately for the instance-independent and instance-dependent cases.\n\nFor the instance-independent bounds, we first compare the first term in the upper bound (Theorem 1(b)) and the lower bound (Theorem 2(b)). Specifically, the first term in the upper bound is $O(\\sqrt{K^2 T \\log T})$, while the corresponding term in the lower bound is $\\Omega(\\sqrt{KT})$. This implies a gap of $\\sqrt{K \\log T}$ between the upper and lower bounds for this term. We then compare the second terms. The second term in the upper bound can be written as $O((\\sqrt{{\\log T}/{\\tau_*}} + V_{\\max}) \\cdot T)$, and the corresponding term in the lower bound is $\\Omega( (\\sqrt{{1}/{\\tau_*'}} + V_{\\max})\\cdot T)$. To compare the different parameter $\\tau_*$ and $\\tau_*'$, we consider a special case where $N_i = n$ for all $i \\in [K]$. In this case, \n$$\n\\tau_* = \\frac{n}{2} + \\frac{2T}{K(K+1)}, \\quad \\tau_*' = n + \\frac{2T}{K}.\n$$\nUnder this setting, it can be shown that the gap between the upper and lower bounds for the second term is again at most a factor of $\\sqrt{K \\log T}$.\n\nFor the instance-dependent case, to better compare the upper and lower bounds, we consider the special case where $N_i=n$ for all $i\\in[K]$ and $\\Delta_i = \\Delta$ for all sub-optimal arms. Then the upper bound in Theorem 2(a) simplifies to \n$$\nO\\left(\\frac{K^2\\log T}{\\Delta}-\\frac{K^2n}{4}\\sum_{i\\leq j}\\max\\\\{\\Delta-4\\omega_{i,j},0\\\\} \\right),\n$$\n and the lower bound is in the form of:\n$$\n\\Omega\\left(\\frac{K\\log T}{\\Delta}+\\frac{K}{4\\Delta}\\log\\frac{\\Delta}{64C}-Kn\\sum_{i\\in[K]}{\\max\\\\{\\Delta-\\omega_i/2,0\\\\}^2}\\right).\n$$\nFrom this comparison, we observe that the upper bound is approximately a factor of $K$ worse than the lower bound in this case. We will include a discussion on the tightness of the bounds in the next version of the paper."}, {"review_id": "c2hMKlv9ZA", "reviewer": "Reviewer_5U6k", "summary": "This paper studies hybrid stochastic MAB. That is, warm starting the online interaction stage with offline dataset. this paper considers that the offline and online feedback are of different types, one is absolute signal and the other is pairwise comparison. The main challenge is how to fuse these two types of feedback\n\nIn both settings, there are algorithms proposed that leverege offline dataset whenever it is helpful, and does not suffer from it otherwise. Lower bounds are also provided. Lastly, experiments validate the effectiveness of the proposed algorithms.", "questions": "1. Does the offline data never hurt the online regret, even if they are not helpful at all?\n2. \"closely match\" in line 279 is not precise enough. I expect more discussion on the gap between upper and lower bounds\n3. Now two settings have different types of alg. design (UCB vs. elimination). What's the challenge to unify them?\n\ntypos\n\n1. $\\\\mathcal{C}_t$ in Eq. (5) should be $\\\\mathcal{C}^{\\\\mathrm{on}}_t$?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. It's a well-motivated problem due to RLHF\n2. Algorithm design is not obvious or trivial\n3. Remarks which interpret the results are very informative and sharp\n4. Lower bound results complement upper bound results.\n\nWeaknesses\n\n1. The performance depends on hyper-parameter tuning, which further relies on some unknown knowledge.", "was_revised": true, "final_justification": "my final recommendation would be 5: Accept. The studied problem is highly important, and technically I don't see major weakness.", "rebuttal": "# Response to Reviewer 5U6k\n\nWe thank the reviewer 5U6k for the valuable comments and suggestions. Please find our detailed response below. \n\n## 1. Hyper-parameter tuning\n\n\nOur algorithm involves only two hyper-parameters: the confidence level and the bias bound $V$. The confidence level can be set using standard theoretical analysis, leaving $V$ as the only parameter requiring prior knowledge. We thus believe the reviewer is primarily referring to $V$.\n\nWe agree that in the off2online learning with distribution bias setting, it would be desirable to eliminate the need for such a parameter. However, as rigorously shown in Section 3 of [1], no algorithm can outperform—or even match—the performance of a purely online approach without any prior knowledge of the bias. This lower bound fundamentally highlights the necessity of incorporating some prior information in order to leverage offline data effectively.\n\nAlthough our hyper-parameter $V$ encodes prior knowledge about the bias, it does not need to be exact—any valid upper bound suffices. When the learner has sufficient knowledge about the offline and online environments, the bound can be tight, allowing our algorithm to effectively leverage offline data for improved performance. In contrast, when the prior is loose or even unavailable, the algorithm gracefully degrades to the performance of vanilla UCB, thereby ensuring robustness.\n\nWe fully acknowledge that further reducing reliance on this parameter is a valuable and promising research direction, and we leave this as an open problem for future work.\n\n[1] Cheung, W. C., & Lyu, L. (2024). Leveraging (Biased) Information: Multi-armed Bandits with Offline Data. In International Conference on Machine Learning.\n\n## 2. Response to questions\n\n### 2.1 Offline data does not hurt online regret\n\nNote that our algorithm incorporates a valid bias bound as an input. When the bias is either uncertain (i.e., not helpful) or substantially large (i.e., exceeding practical limits), we could set this valid bias bound to infinity. Consequently, due to the minimum UCB criterion implemented in our algorithm, both HybUCB-AR and HybElimUCB-RA will at least retain the performance of their pure online exploration form.\n\n### 2.2 Discussion about upper and lower bounds\n\n\nWe compare the upper and lower bounds separately for the instance-independent and instance-dependent cases.\n\nFor the instance-independent bounds, we first compare the first term in the upper bound (Theorem 1(b)) and the lower bound (Theorem 2(b)). Specifically, the first term in the upper bound is $O(\\sqrt{K^2 T \\log T})$, while the corresponding term in the lower bound is $\\Omega(\\sqrt{KT})$. This implies a gap of $\\sqrt{K \\log T}$ between the upper and lower bounds for this term. We then compare the second terms. The second term in the upper bound can be written as $O((\\sqrt{{\\log T}/{\\tau_*}} + V_{\\max}) \\cdot T)$, and the corresponding term in the lower bound is $\\Omega( (\\sqrt{{1}/{\\tau_*'}} + V_{\\max})\\cdot T)$. To compare the different parameter $\\tau_*$ and $\\tau_*'$, we consider a special case where $N_i = n$ for all $i \\in [K]$. In this case, \n$$\n\\tau_* = \\frac{n}{2} + \\frac{2T}{K(K+1)}, \\quad \\tau_*' = n + \\frac{2T}{K}.\n$$\nUnder this setting, it can be shown that the gap between the upper and lower bounds for the second term is again at most a factor of $\\sqrt{K \\log T}$.\n\nFor the instance-dependent case, to better compare the upper and lower bounds, we consider the special case where $N_i=n$ for all $i\\in[K]$ and $\\Delta_i = \\Delta$ for all sub-optimal arms. Then the upper bound in Theorem 2(a) simplifies to \n$$\nO\\left(\\frac{K^2\\log T}{\\Delta}-\\frac{K^2n}{4}\\sum_{i\\leq j}\\max\\\\{\\Delta-4\\omega_{i,j},0\\\\} \\right),\n$$\n and the lower bound is in the form of:\n$$\n\\Omega\\left(\\frac{K\\log T}{\\Delta}+\\frac{K}{4\\Delta}\\log\\frac{\\Delta}{64C}-Kn\\sum_{i\\in[K]}{\\max\\\\{\\Delta-\\omega_i/2,0\\\\}^2}\\right).\n$$\nFrom this comparison, we observe that the upper bound is approximately a factor of $K$ worse than the lower bound in this case. We will include a discussion on the tightness of the bounds in the next version of the paper.\n\n### 2.3 Challenges in unifying different types of algorithm\n\nThanks for this good question. We invested significant effort in attempting to unify the two algorithms, particularly aiming to make the second setting (relative to absolute) align with vanilla UCB when offline data is unavailable. Before we formed HybElimUCB-RA, two ways have been proposed:\n\n- For HybUCB-AR (offline absolute with online relative feedback), we simultaneously utilize both offline and online data to maintain estimates $p_{i,j}^{\\text{hyb}}$ for all $i, j \\in [K]$. In contrast, when adapting this to the online absolute feedback setting, we need to maintain estimates $\\mu_i$ instead. Here, a key challenge emerges: the offline relative feedback data, due to its pairwise nature, lacks absolute value information, making it intrinsically challenging to employ for maintaining absolute value estimates (Especially under the Condorcet winner assumption).\n\n- An alternative approach involves employing a hybrid method, which uses offline and online data to estimate $p_{i,j}^{\\text{hyb}}$ and pure online feedback to estimate $\\mu_i$. This algorithm can be divided into three parts: \n\n  **For** each time step $t$, **do**\n\n  1. Construct candidate set $C_t$ based on the hybrid estimator $p_{i,j}^{\\text{hyb}}$ and its confidence radius.\n  2. Select and play an arm $a$ such that $a = \\arg\\max_{i \\in [K]} \\text{UCB}(a_i)$ (vanilla UCB).\n  3. Update the statistics $\\mu_i$, $p_{i,j}^{\\text{hyb}}$ and their upper confidence bound for all $i, j \\in [K]$ based on the observed feedback.\n\n  This algorithm is detailed in Appendix F. \n\n  From a practical viewpoint, this algorithm is expected to perform well since: (1) it matches vanilla UCB in the worst case, and (2) the hybrid estimator utilizes offline and online data jointly in the elimination process. However, note that the upper confidence bound for $p_{i,j}^{\\text{hyb}}$ is given by\n   $$\\hat{p}\\_{i,j}^{\\text{hyb}} + \\sqrt{\\frac{\\log(1/\\delta\\_t)}{2\\left(\\frac{T\\_i T\\_j}{T\\_i + T\\_j} + N\\_{i,j}\\right)}} + \\frac{N\\_{i,j}}{\\frac{T\\_i T\\_j}{T\\_i + T\\_j} + N_{i,j}} V\\_{i,j}$$\n  (Equation 10 in the paper), which is directly influenced by $\\frac{T_i T_j}{T_i + T_j}$. Since vanilla UCB does not guarantee the minimum selection times for each arm, in the worst case—due to insufficient exploration for some arms $i, j \\in [K]$, $\\frac{T_i T_j}{T_i + T_j} = 0$—the theoretical analysis degenerates into a two-stage algorithm:\n\n  1. Eliminate some arms based on the offline dataset.\n  2. Perform vanilla UCB.\n\n  This approach lacks the robust theoretical guarantees provided by HybElimUCB-RA.\n\nFinally, we developed HybElimUCB-RA. Unifying the use of offline relative data for absolute online feedback remains an important and promising direction for future research.\n\n## 3. Typos\n\nYes, this should be a typo. Thanks for pointing it out!"}]

Author rebuttal:

Meta-review: (a) Summary: This paper studies the problem of using offline data for online decision-making in the MAB problem, when the online and offline data belong to different feedback types. Specifically, it studies how offline, preference data can help with MAB with reward feedback, and how offline reward data can help with online dueling bandits. This work proposes algorithms for both settings, establishes their regret guarantees, and shows that the algorithm-specific guarantees are nearly tight. Finally, experiments show that the proposed algorithms outperform baselines. 

(b) Strengths:
- The paper’s problem formulation is conceptually novel and well-motivated. Including both preference feedback and reward feedback makes the setting practically relevant.
- The proposed algorithms are technically sound and the theoretical analysis is solid.
- The paper is well-organized and mostly well-written.
- Some reviewers appreciate the technical significance and novelty of the proposed algorithms.

(c) Weaknesses:
- Practicality of the algorithms: the algorithms need to know the bias of the offline data, which is often difficult in practice. Tuning this hyperparameter can require many runs of the algorithm, making its applications less straightforward.
- Theoretical novelty: Reviewer eSEX raised the issue that the theoretical novelty is limited. The reviewer considers the work to be an extension of a previous paper that studies hybrid offline-online learning in multi-armed bandits under the homogeneous setting. The main difference here is the heterogeneous setting, but the algorithm design was found to be not sufficiently novel. The algorithms use standard UCB techniques, and incorporate the offline data by taking a minimum between the two UCB rewards (online and hybrid). 
- Some reviewers (Q1f6, qfCy) found the clarity of the theoretical bounds can be improved. 

(d) Reasons for decision: The primary reason for acceptance is that the paper studies a new and practically motivated setting, and gives a technically sound solution. While there were concerns about the degree of theoretical novelty and the practicality of the algorithm, the paper nevertheless makes a valuable contribution to the timely problem of leveraging heterogeneous offline data in online learning. 

(e) Summary of rebuttal: During the rebuttal, the authors provided detailed responses to address the reviewers’ concerns. While 3 reviewers maintained their positive scores, one reviewer still found the work to be too incremental. 
- On the bias hyperparameter: the authors explained that without any prior knowledge of offline data, there is an existing lower bound showing that one cannot improve upon vanilla UCB. They also mentioned that only an upper bound is required for their algorithms. This answer seems to address reviewer 5U6k’s concerns but not for reviewer eSEX.
- On theoretical novelty: reviewer eSEX expressed that the work is an extension of a previous work to the heterogeneous setting. The authors addressed this in detail in their rebuttal: they pointed out the differences between their analysis and prior work, and emphasized that this work was the first to introduce a "unified statistic" to handle heterogeneous feedback, distinct from prior work on homogeneous data. Reviewer eSEX was not convinced and maintained their score, but the other reviewers found the paper's originality and significance to be high.
- The authors also addressed clarity issues and the tightness of their upper / lower bounds.
Decision: Accept (poster)