Fusing Reward and Dueling Feedback in Stochastic Bandits
Authors: Xuchuang Wang
Qirun Zeng
Jinhang Zuo
Xutong Liu
Mohammad Hajiesmaili
John C.S. Lui
Adam Wierman
Venue: ICML 2025 poster (2025)
Keywords: Relative Feedback
Stochastic Bandits
Dueling Bandits
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: Effective algorithms fusing reward and dueling feedback in stochastic bandits.

Abstract: This paper investigates the fusion of absolute (reward) and relative (dueling) feedback in stochastic bandits,
    where both feedback types are gathered in each decision round.
    We derive a regret lower bound, demonstrating that an efficient algorithm may incur only the smaller among the reward and dueling-based regret for each individual arm.
    We propose two fusion approaches:
    (1) a simple elimination fusion algorithm that leverages both feedback types to explore all arms and unifies collected information by sharing a common candidate arm set,
    and (2) a decomposition fusion algorithm that selects the more effective feedback to explore the corresponding arms
    and
    randomly assigns one feedback type for exploration and the other for exploitation in each round.
    The elimination fusion experiences a suboptimal multiplicative term of the number of arms in regret due to the intrinsic suboptimality of dueling elimination.
    In contrast, the decomposition fusion achieves regret matching the lower bound up to a constant under a common assumption.
    Extensive experiments confirm the efficacy of our algorithms and theoretical results.

Fusing Reward and Dueling Feedback in Stochastic Bandits
Xuchuang Wang' Qirun Zeng² Jinhang Zuo Xutong Liu Mohammad Hajiesmaili' Adam Wierman
John C.S. Lui
Abstract
Rafailov et al., 2024), the human annotators are asked to compare the quality of two LLM-generated sentences, rather than scoring them using absolute values. Given LLMs' pop- ularity, designing algorithms that can effectively leverage relative feedback has become a critical research topic in the online learning community, c.g., reinforcement learning with human feedback (RLHF) (Wang et al., 2023a; Xiong et al., 2024), bandits with human preferences (Ji et al., 2023), dueling bandits (Yan et al., 2022; Saha & Gaillard, 2022), etc. This line of work complements the traditional online learning algorithms that rely on absolute feedback, e.g., re- ward in bandits and reinforcement learning (Lai & Robbins, 1985; Szepesvári, 2022). We refer to Appendix A for detailed discussion on related works.
This paper investigates the fusion of absolute (re- ward) and relative (dueling) feedback in stochastic bandits, where both feedback types are gathered in each decision round. We derive regret lower bound, demonstrating that an efficient algorithm may incur only the smaller among the reward and dueling-based regret for each individual arm. We propose two fusion approaches: (1) a simple elimination fusion algorithm that leverages both feedback types explore all arms and unifies collected information by sharing a common can- didate arm set, and (2) decomposition fusion algorithm that selects the more effective feedback to explore the corresponding arms and randomly assigns one feedback type for exploration and the other for exploitation in each round. The elimina- tion fusion experiences a suboptimal multiplica- tive term of the number of arms in regret due the intrinsic suboptimality of dueling elimination. In contrast, the decomposition fusion achieves re- gret matching the lower bound up to a constant under a common assumption. Extensive experi- ments confirm the efficacy of our algorithms and theoretical results.
Most of the prior literature has mainly focused on algorithms that leverage either relative or absolute feedback alone. In many real-world applications, however, these two types of feedback coexist. For example, in LLM training, the human annotators may provide both absolute scores and relative comparisons (Ouyang et al., 2022). Another example is in recommendation systems, where the user feedback can be both absolute ratings and pairwise comparisons (choose one among two recommendations) (Zhang et al., 2020). Despite its practical relevance, there is no prior literature where the underlying algorithms simultaneously utilize (dubbed as fuse) the absolute and relative feedback.
In this paper, we investigate how to fuse the absolute and relative feedback under the framework of the stochastic multi-armed bandit (MAB) (Lattimore & Szepesvári, 2020), which is a fundamental problem in online learning. To align with the terminology in bandit literature, absolute feedback as reward and the relative feedback as dueling feedback. We consider MAB with K E N+ arms, where each arm k is associated with a reward distribution with an unknown mean, and each arm pair (k1, k2) is asso- ciated with an unknown dueling probability. representing the probability that arm hy is preferred over arm h2 in a comparison. In each round t, the learner selects a tuple of arms {ke, (K1,,, k2,c)), where the reward feedback is the observed reward drawn from the reward distribution of arm kt and the dueling feedback is the observed winning arm from the comparison between arms ki, and k2,1-
1. Introduction
Relative feedback is type of feedback that provides infor- mation about the relative quality of two or more items (i.e., which is better) rather than their absolute quality. The power of relative feedback has been widely recognized various fields. For example, the human alignment stage of the large language model (LLM) training (Ouyang al., 2022:
refer to the
'University of Massachusetts, Amherst, MA University of Science and Technology of China 'City University of Hong Kong, Hong Kong *Carnegie Mellon University, Pittsburgh, PA 'The Chinese University of Hong Kong, Hong Kong CCalifornia Institute of Technology, Pasadena, CA. Correspondence to: Xutong Liu <xutongl @
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
Table 1: Regret bounds for DR-MAB
ELIMFUSION (Alg. 1) (Eii (odf (100))))))
Algorithm
Regret Bound
O T)
Olog T)
(
ke1 (m -0) (a log,"
No Fusion!
min((a) )2, (AA()))
ELIMFUSION (Alg. 1)
Exef (AA"
(ad 1 o] ) T
a
DECOFUSION (Alg. 2) log o (Ix#I
a 1
DECOFUSION (Alg. 2)
EnA max{ (A) Ri /a, / (1-aa)
log
Constant
max /o. /a--a))
Constant
Simplified LB (Cor. 2.4)
Ω
Exst max _ /a, A /0--o)]
log
Figure I: Impact of parameter a on regret RT
1 Two separate algorithms for reward and dueling feedback.
The goal of the learner is to minimize the accumulative regret RT over T E N+ rounds. The regret attributes to reward and dueling feedback, called reward-based regret R2R)) and dueling-based regret R& The R&R (resp. 127 measures the difference between the reward (resp., duel- ing probability) of the selected arms (resp., arm pairs) and that of the optimal arm (resp., optimal arm pair) in hind- sight. One notable advantage of the dueling feedback is that querying relative feedback from suboptimal arm pairs often more cost-efficient than that of the absolute feed- back (Ouyang al., 2022). Taking this cost difference into account, we introduce weight parameter a E [0. 1] and de- fine the final regret as RT= == a.l + (1 - a) refi We call this model duellnngrreaard reward mulli-arred bandit (DR-MAB) and present its details in Section 2. In this paper, we aim to answer the following central questions:
tion, derive a simplified version as 9 min fa/ (a/4 (R) (1- o) a)/4m") log T),, where the (R) and A are the reward and dueling gaps of arm & (defimition in Section 2). This bound highlights the benefit of fusing reward and duel- ing feedback: for each suboptimal arm k. among the two weighted regret costs induced from reward and dueling feed- back, fusion makes it possible only pay the smaller one.
We first propose simple climination fusion (ELIMFUSION) algorithm in Section 3. ELIMFUSION applies the elimi- nation algorithms for stochastic and dueling bandits sep- arately to both types of feedback and then fuses their in- formation by sharing two algorithms' candidate arm sets (arms not identified as suboptimal yet). ELIMFUSION en- joys the benefit of fusion suggested by the lower bound and achieves regret bound of (aE + (1 a) () (iint : K/(A
log T), where the re- gret cost of dueling feedback suboptimal in terms of the factor K, which is inherited from the intrinsic suboptimality of the dueling elimination algorithm.
How do we fuse reward and dueling feedback DR-MAB so as to reduce the accumulative regret? How does the weight factor a influence the fusion process and the regret?
Technical challenges. One key challenge comes from the separated nature of reward and dueling feedback, each pro- viding information on one aspect of the arms (i.e., reward means vs. dueling probabilities), both of which are incom- parable. That is, the heterogeneity of both feedback types makes it difficult to fuse them. Furthermore, the relative costs of reward and dueling feedback (parameter in the regret) further complicate the fusion process. For example, while in general, the learner needs to balance the utilization of two feedback types to minimize regret, there exist cases where one feedback much cheaper than the other, making more beneficial to rely solely on the cheaper one.
We then devise a decomposition fusion (DECOFUsION) al- gorithm in Section 4. Notice that the lower bound suggests a dccomposition of the suboptimal arms into two subsets: one with the smaller regret cost induced by reward feedback and the other smaller by dueling feedback. DECOFUSION leverages this insight by approximating this arm decom- position. However, without the knowledge of the reward and dueling gaps, the approximated decomposition may deviate from the ground-truth one, which we further ad- dress by proposing a novel randomized decision decision-making strategy that explicitly separates the exploration and ex- ploitation. Putting all together. DECOFUSION achieves a regret bound of oiE, min(a// A (1 - at/ (P) log T), which matches the simplified lower bound (instead of the general form) and outperforms ELIMFUSION.
1.1. Contributions
This paper investigates the fusion of reward and dueling feedback in stochastic MAB setting. We summarize all our technical contributions in Table 1. Below are the details of our technical contributions.
Furthermore, as Figure 1 shows, DECOFUSION is able to fully utilize a free exploration property when either a = 0 (free reward) or a = 1 (free dueling), to achieve a constant
We formulate the reeling-reward MAB problem and study its regret lower bound in Section 2. We first provide a general lower bound and then, with an additional assump-
'Most big O and big- formulas in the introduction are infor- mally tailored for readability. We refer the readers to corresponding theorems for their formal expressions.
2

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
(i.e., independent from 7) regret, which is impossible for ELIMFUSION. Lastly, we conduct simulations to evaluate the performance of the proposed algorithms in Section 5.
picked arm pairs (kiLes kig,), i.e.
T
T
(()
(R)
=
T
p1
Phat
2. Model Formulation
t=1
(D)
(D)
R
12.4
V1, + 11,
Consider dueling-reward multi-armed bandit (DR-MAB)
2
2
with K E N+ arms. Each arm & K = (I. K is associated with Bernoulli reward distribution with un- known mean (4 (0, 1). Each arm pair (k, f) E XC? is asso-
Lastly, we introduce a parameter a E [0. 1] to balance the impact of the reward-based and the dueling- bbaing regrets the aggregated regret Rr, defined follows,
ciated with a dueling probability VR,e E (0, 1). representing the probability that arm k wins arm E in a duel. Especially, VK,e > 0.5 if lAk > pe and Vk,e= = 0.5 if j4 = μig. and arm pairs (k, f) and (e, are symmetric, i.e., Uk, = 1 111-44 Me,k- Besides this ordering relation between reward means μl and dueling probabilities Mk,e, we do not assume or utilize any other specific relation between μı and Mk,e. For simplicity, we assume all reward means are distinct, and these arms are labeled in descending order regarding their reward means, i.e. PI > > .... > р.k- Therefore, arm is the unique optimal arm and the Condorcet winner (i.c., 1/1,k > 0.5 for any arm >> 1) (Urvoy et al., 2013).
RT == R + (1 a)
(1)
2.1. Lower Bound
This section provides the regret lower bound for any con- sistent algorithm (Definition 2.1) in DR-MAB. We denote Ng., as the number of times arm & is picked in the first & rounds for reward feedback, and Mg,e,t as the number of times the pairs (k, E) and k) (due to their symmetry) are picked in the first t rounds for dueling feedback.
Consider T N+ rounds in DR-MAB. In each round t {1,2, T' the learner picks tuple (kr, (k1,e; k2,)) consisting of an arm k and pair of arms (k k2,)) Then, the learner observes the reward realization Xh. of the chosen arm hy and the winner of the pair duel Ys, Vs,,,, tot where X is sampled from the Bernoulli distribution with mean jk,, and Ys .k..t. t is determined by a sam- ple from the Bernoulli distribution with mean d ,2. a if the sample is 1, and Y ,a. = k2, if it O. Both X and YR A2..t at are independent across rounds and arms (pairs). We call the XA, as the reward feedback (absolute) and the c2, as the dueling feed- back (relative), following the convention of bandit literature.
Definition 2.1 (Consistent algorithm). An algorithm is called consistent for DR-MAB if for any suboptimal arm k # and parameter ? 0, it fulfills E[Nx,r] (T and E[MA.I.T] (T)) for any arm l + k.
The consistent definition covers all algorithms that achieve logarithmic regrets in DR-MAB, e.g.. UCB and elimina- tion (Auer, 2002: Auer & Ortner, 2010). This definition is "generalization" of the consistent policy in stochastic bandits (Lai & Robbins, 1985). We first provide a lemma to bound the number of arm pulling and pair dueling.
Lemma 2.2. For any suboptimal arm h: # 1, under any consistent algorithm, we have
Regret objective. The learner aims to minimize the accu- mulative regret Rr over T rounds, composed by the reward- based regret R/R) and the dueling- based regret R(P). Denote A = μı μr and A == V1,A 0.5 as the reward and dueling gaps between the optimal arm and the suboptimal arm ks respectively. Then, R(f)) is defined as the accumu- lation of the reward gaps (() of all chosen arms ht over the T' rounds, while I2(D) is defined as the accumulation of the average of the dueling gaps (A + 1/2 of the
NE. ke.Tkl( + Σ
Mr..TT kl (vk,e,
tck
> (1-o(1))log7)
where kl(p, q) == popoog P +11-p) log I-P is Kiveevgreeece between two Bernoulli distributions with means p and q.
1-9
The proof of Lemma 2.2 (formally in Appendix C) is based on the ceemmation-theoretii lower bounds for MAB (Lai & Robbins, 1985) and the dueling bandits (Komiyama et al., 2015). This proof needs a careful selection of pairs of the DR-MAB instances and constructions of the key informa- tion quantities, so that the attributions from reward and dueling feedback would both appear in the LHS of (2).
'The choice of Bemoulli distributions is mainly for simplicity. One can extend the assumption to distributions with bounded inter- val support, i.e., [0, bouuded, via more sophisticated analysis.
The LHS of (2) can be interpreted as the amount of "infor- mation" collected by the learner for arm k in the T rounds, and its two terms are "information" from the reward and
3

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
dueling feedback. Their additive relation in the LHS im- plies that the "information" can be attributed to two parts: the reward-based (first term) and the dueling-based (sec- ond term). Especially, the second term for dueling- based information of suboptimal arm k is the sum over all pairs between the arm and other better arms é (< k), implying that the effective dueling-basee information collected by dueling with better arms.
1/max(A) (h) /a, A /01 - -a)3 This simplification is sum- marized in the following corollary.
Corollary 2.4. If for each suboptimal arm k o 1, the most
effectivve dueling arm f is the optimal arm 1, the regret lower bound in Theorem 2.3 can be simplifted as follows, for some universal positive constant C.
B[RT]]
1
lim inf T-00 log T
(4)
Although Lemma 2.2 suggests that the necessary exploration on a suboptimal arm k may be fulfilled by aggregating information collected from the reward and dueling feedback, we prove the following theorem to show that the potentially optimal way to minimize regret due to each suboptimal arm k is to focus on either the reward-based bbased or the dueling-based exploration, exclusively.
max
(R) /a, / (
((1 - a)}
k
From the regret lower bounds in (3) and (4), one may get a counter-intuitive observation: when a = 0 or 1, the regret lower bound would become sub-logarithmic for any consistent algorithm, which is unusual in the bandit literature. Later in this paper, we will show that a sub- logarithmic o(log T) regret is actually achievable (in fact, T T-independent constant regret) in these two scenarios, re- vealing a novel phenomenon of DR-MAB.
Theorem 2.3. For any consistent algorithm and regret bal- anced by a E [0, 1}, the following regret lower bound holds,
E[Rr]
lim inf T T-000
log T
3. ELIMFUSION: Fusing Reward and Dueling via Elimination
(R)
(1 (1-a)(A (AA )
(D) kl (ve,e:5 2
(3)
min
min
kl(HR,
rck
As the reward means and dueling probabilities only have a weak ordering relation-the dueling probability of arm k winning over arm E is greater than 0.5 if and only if arm k has a higher reward mean than arm e-and their observations are independently sampled from distributions with different parameters, the estimations of reward means Me and dueling probabilities Vk,e are intrinsically separated. This separation makes it difficult to combine these two types of feedback in online learning directly.
A full proof is given in Appendix Cand is based on minimiz- ing the regret decomposed in terms of the sampling times NR,T and MR.eTT- given the constraints in Lemma 2.2. As both the regret minimization objective and the constraints are linear expressions, the minimization can be solved by linear programming, yielding the minimal attained in one of two end nodes of the constraint line segment in (2).
Theorem 2.3 provides regret lower bound for any consis- tent algorithm in DR-MAB The sum in the RHS of (3) is over all suboptimal arms & + 1. The two terms inside the outer minimization in the RHS correspond to the reward- based and dueling-based regrets for arm k. The outer min- imization indicates that for arm k. an effective algorithm should explore it through either the reward or dueling feed- back, depending on which yields smaller regret.
To address this challenge, in this section, we introduce our first approach to fusing reward and dueling feedback in DR-MAB, named Elimination Fusion (ELIMFUSION). Al- though ELIMFUSION has suboptimal regret in DR-MAB, it suggests a simple and effective way to fuse absolute and relative feedback. As the uitimate goal is to address the fusion in general online learning problems beyond bandits, the intuitive high-level idea of ELIMFUSION may have a broader application to other learning settings.
The second term (inner minimization) in the RHS of (3) implies that for each suboptimal arm k, there exists a most effective arm (competitor) to duel with, denoted as fx = mins<c ( + A )/kl (vi,e, 2). However, as dis- cussed in Komiyama et al. (2015, $3.2), the most effective arm Et is usually the optimal arm, i.e., fi 1, in many real world applications. Then, by assuming E = 1, the key term in the lower bound for any suboptimal arm k be- comes min (a (R) /kl((,, /1), (1 - -a) (b) /kl (VE,1, }) Further noticing the kl(a,b) = O((a - b)2) prop- erty for the KL-divergence between two Bernoulli dis- tributions (Lattimore & Szepesvári, 2020, $16), this
3.1. Algorithm Design of ELIMFUSION
Arm elimination is a common technique in multi-armed bandits (Auer & Ortner, 2010) and dueling bandits (Saha & Gaillard, 2022). The main idea is maintaining a candi- date arm set C, initialized as the full arm set K, and as the learning proceeds, one gradually identifies and eliminates suboptimal arms from the set C based on the observed feed- back, until only the optimal arm remains. ELIMFUSION leverages the maintained candidate arm set as a bridge to connect the two types of feedback. Specifically, ELIMFU- SION maintains a single candidate arm set C, and arms in
term can be simplified as min(a/A (R) (1 - ( =
4

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
this set can be eliminated according either reward or dueling feedback, whichever is first triggered.
Algorithm 1 Elimination Fusion (ELIMFUSION)
1: Input: Arm set K. confidence parameter 5
ELIMFUSION in Algorithm I starts with warm-up phase (detained in Algorithm 3 in Appendix B) to initialize the reward and dueling statistics, where each pair of arms is dueled once, and each arm is queried for rewards in a round- robin manner in the same time. In each time slots, ELIM- FUSION picks the arm and arm pair with smallest number of pulls and dueling times, respectively, which uniformly explores arms (Lines 7-10). With the new reward and du- eling observations, ELIMFUSION updates the reward and dueling statistics for each arm pair and arm, respectively (Line 11, detailed in Algorithm 4 in Appendix B). Then, FLIMFUSION eliminates arms based on the observed feed- back (Line 14). To illustrate the arm elimination, we define the confidence radius CR 2og (Kt/ and
2: Initialize: Candidate arm set C <- K, time slot ( <- 0. reward pull counter NE.: <- 0 and reward estimate iu, + 0 for all arms k E K. dueling pull counter Mg.g,t < 0 and dueling estimate Dx,E, + for all pairs (k. E) K2²
3: Warm-up (Algorithm 3)
4: for each time slot do
5: # decision making:
6: if [C] > 1 then # {uniform explore)
7:
kt 4- arg mitkkee NR.1
8:
(k,,1, k2,2) f- arg (e, jett Mg,,,t Pull arm ke and observe arm reward Xk,,t
9:
10:
Duel (kt,1 k2,2) and observe winner Yk.
11:
Statistics update (Algorithm 4)
CR = / log Kt/8)/ MR,e, for the estimated reward mean and dueling probability, where d > 0 is the input con- fidence parameter of ELIMFUSION. Then, ELIMFUSION eliminates an arm k if either its upper confidence bound (UCB) of reward mean estimate ( + CR is less than the lower confidence bound (LCB) of highest mean (8)
12:
# Farm elimination:
13:
(RR M(1 + arg max Pr,+11
C+ KEE:
14:
either El ElEC)(K), UK,6,+1++ K,E,++1
2
or Px,,41 + CR k,4+1 & &ugm 1441 -CR (R)
estimate Agg +++++++1 CR
2 .++1 (the ( is the estimated optimal arm in Line 13) or there exists an arm in C such that the UCB of its dueling probability Vk,E,0+1 + CR..) k.L+41 is less than 1/2 (i.e., arm l outperforms arm k). ELIMFU- SION keeps eliminating arms via the above loop, and when only the optimal arm remains in C, i.e., [C] = 1, it switches to exploitation (Lines 15-17).
2 +++
15:
else # (exploit when only the optimal arm left)
16:
k <- the only remaining arm set C
17:
Pull arm for reward and duel pair (k:, k:)
via sharing the same candidate arm set in ELIMFUSION. We note that the bound in (6) is not as tight as the one in Table I for the "No Fusion" algorithm.
3.2. Regret Analysis of FLIMOUSSON USION
Theorem 3.1 provides the regret upper bound of ELIMFU- SION. Its proof is deferred to Appendix D.I.
While the fusion via the candidate arm set the elimination algorithm is effective and easy to implement, the 1/K factor in the 2)2) K term of (5) is suboptimal, which is inher- ited from the suboptimality of the elimination algorithm in the dueling bandits literature (Saha & Gaillard, 2022, Re- mark 1). Furthermore, the dependence on the parameter in (5), compared to the lower bound in (4), is also subopti- mal, reflecting the limitation of the elimination algorithm design for more sophisticated optimization in DR-MAB, In the next section, we introduce an advanced algorithm to address these limitations and achieve the optimal regret balance and dependence on the problem parameters.
Theorem 3.1. Letting 8 + 1/K and taking the expecta- tion, the regret upper bound of ELIMFUSION can be upper bounded as follows.
(a ( + (1- (1-a1))00 2) log
E[Rr] <O
(5)
K max (A 1 )2, (1)))2/K]
Applying elimination algorithms reward and dueling feed- back individually without sharing the candidate arm set yields the regret upper bound as follows,
4. DECOFUSION: Fusing Reward and Dueling via Suboptimal Arm Decomposition
(a (R) + (1 - (1 (D)) T
E [T] $0
(6)
min (A (1 R2)2 (2 KK}
This section presents a novel approach to fusing the re- ward and dueling feedback, called decomposition fusion (DecoFusION). We first present the high-level ideas and technical challenges of DECOFUSION in Section 4.1, and then provide its detailed algorithm design in Section 4.2.
where the denominator is the minimum of the two gap- dependent terms and can be much worse than the maximum in the denominator in (5) of ELIMFUSION. This indicates the improvement of fusing the reward and dueling feedback
5

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
Finally, we present the theoretical regret upper bound of DECOFUSION in Section 4.3.
4.2. Algorithm Design of DECOFUSION
To address the above challenges, we propose the decom- position fusion (DecoFusION) algorithm. DECOFUSION, presented in Algorithm 2, consists of three main compo- nents: (i) decomposition arm set construction (Lines 5-9), (ii) randomized decision making (Lines 10-22), and (iii) exploration arm set update (Lines 23-27). Specifically, for the challenge of unknown decomposition sets, we conser- vatively maintain two sets KC() and K..)) in terms of the collected information instead of the incurred regret (details in Section 4.2.1). However, this set construction leads to mismatch between the constructed and ground-trul truth decom- positions, which our proposed randomized decision-making strategy in Section 4.2.2 can address. Finally, for the "dead- lock" challenge of the conflict between the decomposed exploration policy and the calculation of information mea- sures T( and 7,(b) k.,.r" in Section 4.2.3, we devise novel approach to update the exploration arm set & based on the
4.1. High-Level Ideas and Technical Challenges
Decomposed exploration for two set of suboptimal arms. We denote K = {kr E K. a /kl(pt p1) < ming<s (1 -1- a1 (D) + D (Mn,e, 1)3 as the subset of suboptimal arms incurring smaller regret from reward feedback, and ATD): K: \ (K-R)) U {T}} as that of du- eling feedback. Then, the RHS of regret lower bound in (3) can be decomposed as ExEKo aAk ExEXO min (1-a) (4 + )/kl (ve.e:2) 2). This lower bound decomposition implies that to minimize re- gret, arms in A. and K.(D) should be explored by reward and dueling feedback, respectively. Inspired by this obser- vation, an algorithm with this minimal regret also needs to decompose arms as above and explore them accordingly, which we call that the algorithm has a decomposed explo- ration policy. However, the above decomposition relies on the reward and dueling gaps ( and A which are unknown priori. This poses significant challenge for designing near-optimal algorithm.
(R) /kl(uu, u1) +
revised definitions of the information measures f(R) /,, and k,t.
and the approximated arm sets R and K.D)
4.2.1. 1. DECOMPOSITION ARM SET CONSTRUCTION
Before delving into the details of our algorithm design, we introduce "empirical log-likelihoods" " as the measures of the amount of information collected for distinguish- ing arm up to time slot & from the reward and duel- ing feedback, E.. = NN., kl (fxk,e maxrxx (e,)) 11 EeeK-Are. Mg,e, kl (fx.e.:)). introduced by Honda & Takemura (2010) and Komiyama et al. (2015) for de- vising optimal algorithms in stochastic and dueling ban- dits, respectively. Their algorithms use the conditions of T(R) < log f f(K) and r.Ds mingex 1200 < 1ogt+fol ((K) for choosing arms to explore, and the function [(K) is in- dependent of time horizon T and determined later.
After the warm-up (Line 3), each time slot, DECOFUSION constructs two arm sets, K(R) and K:P) as analogs (not estimates) of the sets KC and ACID), The reason that K(R) and K.t) are only analogs, not estimates, is because that the lack of knowledge of reward and dueling gaps A and A makes it hard to decompose arms according to the weighted reward and dueling- regrets. Instead, we utilize the revised information measures (IR) (defined in Section 4.2.3) to construct the arm sets. Because this information-basee set construction does not consider the weight a, the constructed sets KR)) and (D()) mismatches the optimal decomposition sets K(R) and IC(D), even when the information measures are accurate at the end of the time horizon; thus only analogs. We also note that while the optimal decomposition (C and K(D), together with the singleton of optimal arm {1}, forms an exclusive partition of the arm set K., the conservatively constructed sets (R(R) and ()D) often overlap, and their intersection K()) n ( contains the optimal arm in almost all time slots.
k, and i
Decomposition deadlock. The information measures k.t
and R.t cannot work with the decomposed exploration pol- icy. Because both definitions involve the full arm set IC and thus need accuracy estimates of all arms. But under the decomposed arm exploration policy, arms in (C()) only have good estimates of reward mean Pk.c. while arms in (C()) only have good estimates of dueling probability fx,r,t. as explor- ing these arms by feedback other than the corresponding one would incur redundant regrets. This is "decomposition deadlock": applying the decomposed exploration policy makes the kk and ( bbased optimal bandit algorithms design invalid, and deploying the bandit algorithm design makes the decomposed exploration policy invalid. Simi- lar "deadlock" challenges also exist when considering other bandit algorithms, e.g., KL-UCB (Cappé et al., 2013).
Specifically, X:()) = {k E K.
: & log + S(K) is h.
defined in Line 6, where the condition j(R) < &log! L + S(K) implies the insufficient information on arm l from reward feedback. This is a conservative approximation of the duel- ing arm set K( as long as there is insufficient information from reward feedback to exclude an arm from exploration, that arm is included in dueling feedback's 's corresponding set. The other set K: is constructed similarly, as detailed in Line 8. Note that the construction of dueling arm set R. does not rely on strictly exclusion from the reward arm, and vice versa. Because for the actual decomposition is
y(8)
6

---

unknown prior in DECOFUSION, one needs be conser- vative (i.e., allow both sets X((P) and (-()) to have some overlap instead of taking exclusion) to ensure enough explo- rations from both feedback sides for uncertain arms so to learn the ground-truth decomposition at the end. Especially, Fusing Reward and Ducling Feedback in Stochastic Bandits
calculate the estimated optimal arms Ri)) and k(K) among the approximated dueling and reward arm sets, respectively,
in Lines 7 and 9. Because arms outside the corresponding
Algorithm 2 DECOFUSION: Decomposition Fusion
sets may not have good estimate accuracy and thus are not considered.
1: Input: Arm set K. parameter a, function fKK
2: Initialize: Exploration arm set E < K. time slot +- 0, decomposition arm set K(R), X.P)) + K, (()) (D) < for all arms k, and other initializations in Algorithm
4.2.2. RANDOMIZED DECISION MAKING
To tackle the mismatch between the constructed (KiT)) K(P))) and the ground truth (AC*), (.(D)) and realize the decom- posed exploration policy, we devise a randomized decision- making strategy. In each time slot, DECOFUSION picks one arm ke from the exploration arm set & according to some fixed order Line 11, e.g., the arm with the smallest index in the set. Then, DECOFUSION randomly chooses either the reward or dueling feedback to explore the arm k. in Line 12. Specifically, if the round's realization of the uniform distribution Uniform(0, 1] is greater than thresh- a=-11- then the algorithm explores the arm koap by the reward feedback and exploits the pair of the reward estimated optimal arm (R ((()) by the dueling feedback; otherwise, the algorithm explores the arm keeD by the du- eling feedback and exploits the dueling estimated optimal arm k by the reward feedback. When exploring keup via dueling feedback, we follow the RMED1 algorithm of Komiyama et al. (2015) for dueling bandits to pick the comparison arm R-quel (Lines 17-19). One key difference is that our comparison arm kquel is selected from the set (C()) instead of the full arm set K.
3: Warm-up (Algorithm 3)
4: for each time slot t do
5: # decomposition arm set update:
6: ( + E K: f(0) & logt f(K))
7: b +- arg migminnee kER j(D
8:
((R) + {k K ((D) io 2,t k.
< logt + [(K)
9: ((R) arg maxxxxx""" juR
10: # trandmiized decision making:
11: Pick an arm kn from & according to fixed order
old a²
12:
if Uniform(0, 1] +11-aa then
o²
13:
# (reward explore, dueling exploit)
14:
hes & h and (Ni,,, t (R(R)) ((R)
15:
else # (dueling explore, reward exploit)
16:
K(P)) (kkpp) : if R E E or Ouqu, = then kiquet + (
O
17:
18:
19:
else kquell arg min mi (apoy Pet
di 2,D) and (ki,e, k2,)) (Resp, Adue))
20:
21:
Pull arm h, and observe arm reward Xha
a² Finally, the threshold o²#(1-0)2 is chosen to compensate for the mismatch in the decomposition arm set construction. Although chosen by careful derivations, the threshold has an intuitive explanation: take individual squares on all terms in a+i1-a a. The square exponent can be regarded the compensation for the mismatch between the optimal set (R) (omit AC according to the regret with a linear dependence on 1/ and the constructed set KAR) via the collected information f(R) k,t with quadratic (1/2) k R))2 dependence.
22:
Duel k2,)) and observe winner ke,
23:
# exploration arm set update:
24:
E + E\ (ke0)) # fremove the explored arm}
25:
B- Bulk E Kg
(R))
E: ((R) & (og[+S(K))UEE
K.P) EE: E i!D) j(D < logt+ [(K)]
26:
is empty then # (last was traversed)
27:
++ B and B +-g O # (renew E}
28:
Statistics update (Algorithm4) 4)
29:
((R)
k11-1 + kl( max Pe.))
30:
F(D)
k1++1 + wenee Mr,e kl(ix,e,,
4.2.3. EXPLORATION ARM SET CONSTRUCTION
Besides sets R-1)) and K(P) DECOFUSION also maintains an exploration arm set È and an auxiliary arm B for updating E. In each time slot, the exploration arm set E outputs an arm to explore and removes it after exploration (Line 24). and the auxiliary arm set B adds arms that need further exploration regarding either the reward or dueling feedback, as detailed in Line 25, and each arm in the set is unique and not duplicated. When all arms in are explored,
7

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
i.e., E 0, the algorithm renews the exploration arm set & by the auxiliary arm set B (Line 27).
1, may not be the most effective comparison arm cz- This issue also exists in the design of optimal dueling bandit algorithms (Komiyama et al., 2015, RMEDI and RMED2), which is only partially resolved by assuming the knowledge of time horizon T in dueling bandit literature.
At the end of a time slot, DECOFUSION updates the statistics via Algorithm 4 (Line 28) as well as the revised empirical log-likelihoods f(R) and / in Lines 29 and 30. The key difference between the revised empirical log-likelihoods lie and f and the original ones ! and I is that the revised ones only involve the arms in the approximated sets K:())
Physical meanings for regret when a = 0 or a 1. When either a 0 or a 1, the leading term of the regret bound in (7) vanishes, and the regret becomes a T- independent constant. Because when = 0, the reward- based regret 125) is not counted in the regret, i.e., reward feedback is free! this case, the threshold - - 0 in the randomized decision-making, and the algorithm al- ways explores arms via reward feedback (i.c., free explo- ration) and exploit the estimated optimal arm R, by the dueling feedback, which only incurs a constant regret. Simi- larly when a = 1, the duel feedback is free, and the algo- rithm enjoys free exploration from dueling feedback and achieves a constant regret as well. As illustrated in Figure 1, such an advantage is only achieved by DECOFUSION, while ELIMFUSION always suffers Ollog T) regret cost.
and kip) instead of the full arm set K.
4.3. Regret Analysis of DECOFUSION
a²
Theorem 4.1 (Regret upper bound of Algorithm 2). For sufficiently small & > and a constant 0 depending on the bandit instance, DECOFUSION has the regret bound,
E B[RT] & O(K2) + +(5 ((( ((eK-11))))
(R) /a 2/ ((1-0)) log +
T [(K))
(7)
max (KK(pR ki(pE,, ()/
Simplifying the above bound by letting T + oc, f(K) =
cKi+s, and noticing kl(p, 4) = O(p - )) we have
5. Experiments
log T
This section reports the numerical experiments of the pro- posed fusion algorithms. We compare our algorithms with two baselines: 1) ELIMNOFUSION that maintains two sepa- rate sets for arm elimination, one based on reward feedback and the other on dueling: 2) MEDNoFUSION (Minimum Empirical Divergence) that deploys the optimal algorithms from Honda & Takemura (2010) and Komiyama et al. (2015) to choose arm k2 and dueling pair (2,) separately.
E Rr E
CO
lighl max { /a A /(L /1) - (8)
The proof of Theorem 4.1 consists of two key claims (steps 2 and 3 of the proof in Appendix D.2): (i) in most time slots, the estimated optimal arms ki and ki from both feedback types are exactly the optimal arm 1, i... Ee= BTE(") (:")) 1] T O(). and (ii under the first claim, the regret of the randomized decision-making maaiing policy is upper bounded by the last regret term in (7). While the claim (i) is proved via similar techniques in Honda & Takemura (2010) and Komiyama et al. (2015), the proof of claim (ii) needs a novel analysis to handle the regret costs of randomized decision decision-making. It needs to construct a sampling threshold regarding both feedback and then bounds actual sampling times of reward feedback NN,T for each arm and dueling feedback for each pair MR.e,r when é = 1 and E + 1 case- a² by-case. The choice of the threshold a²+(1-a)² is crucial for balancing the regret costs of both feedback types.
Figures 2(a), 2(b), and 2(c) illustrate the trends of aggre- gated regret (ar = 0.5) in various settings. The setup details are in Appendix F. DECOFUSION outperforms all other al- gorithms across all settings. In Figure 2(a), the aggregated regret of DECOFUSIOn is around 41 times lower than that of ELIMFUSION. While FLIMFNSSION outperforms EL.M FUSION by 81.3%, and DECOFUSIOn outperforms MED- NOFUSION by 47.5%, both elimination approaches are worse than the other two due to the suboptimality of the elimination mechanism. Figures 2(b) and 2(c) examine the impact of reward and dueling gaps on total regret. As either gap increases, distinguishing suboptimal arms becomes eas- ier, thereby reducing the regret cost of the algorithms. The slight increase in the regret of DECOFUSIOn in Figure 2(c) is due to the regret incurred during the warm-up (Line 3), which scales with the dueling gap and constitutes a large portion of the relatively small total regret.
Near-optimal regret when C = 1. The simplified regret upper bound in (8) tightly matches the simplified regret lower bound in (4) in terms of all non-trivial factors (except for a universal constant). However, this simplified lower bound only holds when the most effective comparison arm f is the optimal arm 1 for all arms k. Without this condition, the regret upper bounds in Theorem 4.1 are worse than the general lower bound in (3), where the main gap comes from that DECOFUSIOn often uses the dueling estimated optimal arm 2.(D) to duel with the exploration arm cxp where the
Figure 2(d) investigates the impact of the parameter a on DECOFUSION. The aggregated regret (blue) reaches its maximum when a 0.5 and decreases as a is close to either 0 or 1, which verifies its free exploration property and
8

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
Revort saeed legget RC Turdin cin ingert A7 Aggiogetod rogst
Apgreattee pvpree 10
Dinlehaaoon
an
Diniklaaian
10'
18
Rosard
Minimal reward gap
Mininal dualing CAp
Parameter o
(a) Aggregated regret Rr
(b)
Vary reward gap A2
(c) Vary ducling gap A
(d) Vary a in DECOFUSION
Figure 2: Regret comparison in different settings
constant regrets when a = 0 or 1. The curves of reward- based and dueling-based regrets (red and green) corroborate the effectiveness the randomized decision- decision-making policy: when a = O, the algorithm assigns all explorations to reward feedback, while the case of a assigns all explorations to dueling feedback, and one tune a to balance the regret cost between the two types of feedback.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A Acknowledgements
6. Conclusion
The work of Jinhang Zuo was supported by CityUHK 9610706. The work of Mohammad Hajiesmaili was CAREER-2045641 CPS-2136199, and CNS-2325956. The work of John C.S. Lui was supported in part by the RGC SRFS2122-495 122-4522. The work of Adam Wierman was sup- ported by NSF grants CCF-2326609, CNS-2146814, CPS- 2136197, CNS-2106403, and NGSDI-2105648, as well as
This paper studies the fusion of reward and dueling feed- back in stochastic multi-armed bandits, called DR-MAB We derived regret lower bounds for DR-MAB, and pro- posed two algorithms,, ELIMFUSION and DECOFUSION. ELIMFUSSION provides simple and efficient way to fusion both feedback types via sharing the same candidate arm set, but its regret is suboptimal regarding a multiplicative factor of the number of arms. DECOFUSION, on the other hand, designed achieve the optimal regret up to constant factor, by decoupling the suboptimal arms into sets for reward and ducling feedback. Both algorithms and the lower bound suggest that the ad advantage of fusing both feedback types is that it saves the higher regret costs among both feedback types for each suboptimal arm, achieving a better regret than solely relying on any one of the two.
funding from the Resnick Sustainability Institute. Xutong Liu is the corresponding author.
References
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Ailon, N., Karnin, Z., and Joachims, T. Reducing dueling bandits to cardinal bandits. International Conference on Machine Learning, pp. 856-864. PMLR, 2014.
The standard LLM training usually has two separate steps: (1) the responses from human experts (absolute feed- back) to conduct supervised learning, called supervised fine-tuning (SFT), and (2) use the human preference (rel- ative feedback) among multiple responses generated from the SFT model to conduct a preference directly training (either directed preference optimization (DPO) (Rafailov al., 2024) or reinforcement learning from human feedback (RLHF) (Ouyang al., 2022)). Although not exactly the same, these two steps correspond to the reward (absolute) and dueling (relative) feedback in our bandits setting. Our algorithms suggest training approach to conduct these two steps in parallel, which can potentially save the human la- beling cost and improve the training efficiency (as our regret upper bounds improve over the existing ones). Investigating this potential approach in LLM training is interesting direction.
Auer, P.
Using confidence bounds for exploitation- exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397 2002.
Auer, P. and Ortner, R. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, (1(1-)):55-6. 65, 2010.
Auer, P., Cesa-Bianchi. N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM journal on computing. 32(1):48 2002.
Bhaskara, A., Gollapudi, S., Im, S., Kollias, K., and Muna- gala, K. Online learning and bandits with queried hints. arXiv preprint 1..0v:2211.020000 2022.

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
Bubeck, S. Bandits games and clustering foundations. PhD thesis, Université des Sciences et Technologie de Lille- Lille I, 2010.
Lindståhl, S., Proutiere, A., and Johnsson, A. Predictive bandits. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 1170-1176. IEEE, 2020.
Bubeck, S., Cesa-Bianchi, N., et al. Regret analysis of stochastic and nonstochastic nulti-armed bandit prob- lems. Foundations and Trends@ in Machine Learning, 5 (1):1-122, 2012.
Orabona, F. modern introduction to online learning, arXiv preprint arXiv: 19t.:::992..113.3. 2019.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., al. Training language models follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744 2022.
Cappé, O., Garivier, A., Maillard, O.-A., Munos, R., and Stoltz, G. Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pp. 1516-1541, 2013.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances in Neural Information Processing Systems, 36, 2024.
Chen, W. Wang, Y., and Yuan, Y. Combinatorial multi- armed bandit: General framework and applications. In International conference on machine learning. pp. 151- 159. PMLR, 2013.
Cutkosky, A., Dann, C.,, Das, A., and Zhang. Q Leveraging initial hints for free in stochastic linear bandits. In Inter- national Conference on Algorithmic Learning Theory, pp. 282-318. PMLR, 2022.
Saha, A. and Gaillard, P. Versatile dueling bandits: Best-of- both world analyses for learning from relative preferences. In International Conference on Machine Learning, pp. 19011-19026, PMLR, 2022.
Faury, L., Abeille, M.. Calauzènes, C., and Fercoq. O. Im- proved optimistic algorithms for logistic bandits. In In- ternational Conference on Machine Learning, pp. 3052- 3060. PMLR, 2020.
Saha, A., Koren, T., and Mansour, Y. Adversarial duel- ing bandits. In International Conference Machine Learning, pp. 9235-9244 PMLR, 2021.
Slivkins, A. Introduction nulti-armed bandits. Founda- tions and Trends@ in Machine Learning, 12(1-2):1-288 2019. ISSN 1935-8237. doi: 10.1561/2200000066 URL http: dxx doi. www.doow....o.ooooo..........o.. / 10 15 61 011//111//20000///
Honda, J. and Takemura, A. An asymptotically optimal bandit algorithm for bounded support models. In COLT. pp. 67-79. Citeseer, 2010.
Sui, Y., Zoghi, M., Hofmann, K., and Yue, Y. Advancements in dueling bandits. In IJCAI, pp. 5502-5510, 2018.
Ji, X., Wang, H., Chen, M., Zhao, T., and Wang, M. Provable benefits of policy learning from human pref- erences in contextual bandit problems. arXiv preprint arXiv:2307. 12975, 2023.
Sutton, R. S., Barto, A. G., et al. Introduction to reinforce- ment learning, volume 135. MIT press Cambridge, 1998.
Komiyama, J., Honda, J., Kashima, H., and Nakagawa, H. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory. pp. 1141-1154. PMLR, 2015.
Szepesvári, C. Algorithms for reinforcement learning. Springer nature, 2022.
Urvoy, T., Clerot, F., Féraud, R., and Naamane, S. Generic exploration and k-armed voting bandits. Interna- tional conference on machine learning, pp. 91-99. PMLR, 2013.
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1): 4-22, 1985.
Wang, Y., Liu, Q., and Jin, C. Is rlhf more difficult than standard rl? arXiv preprint arXiv:2306. 14111, 2023a.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Wang, Z., Liu, X., Li, S., and Lui, J. C. Efficient explorative key-term selection strategies for conversational contex- tual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 10288-10295, 2023b.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-banne approach to personalized news article recommendation. In Proceedings of the 19th interna- tional conference World wide web, pp. 661-670, 2010.
Li, Z., Liu, M., and Lui, J. Fedconpe: Efficient federated conversational bandits with heterogeneous clients. arXiv preprint X4055 220..2281. 2024.
Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. Iterative preference learning from human feedback: Bridging theory and practice for
10

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
rlhf under kl-constraint, In Forty-forst International Con- ference Machine Learning, 2024.
Yan, X., Luo, C., Clarke, C. L., Craswell, N., Voorhees, E. M., and Castells, P. Human preferences as dueling ban- dits. In Proceedings of the 45th international ACM SIGIR conference research and development in information retrieval, pp. 567-577, 2022.
Yue, Y., Broder, J., Kleinherg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 7865):1538-1556 2012.
Yun, D., Proutiere, A., Ahn, S., Shin, J., and Yi, Y. Multi- armed bandit with additional observations. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(1):1-22, 2018.
Zhang. X., Xie, H., Li, H., and CS Lui, J. Conversational contextual bandit: Algorithm and application. In Pro- ceedings of the web conference 2020, pp. 662 672, 2020.

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
A. Related Works
Stochastic bandits with absolute or relative feedback. Stochastic multi-armed bandits (MAB) is a fundamental online learning model, introduced by Lai & Robbins (1985) and later comprchensively studied, e.g., by Bubeck et al. (2012); Slivkins (2019): Lattimore Szepesvári (2020). Later on, various extensions of the stochastic bandits have been proposed, such the linear bandits (Abbasi-Yadkori Yadkori et al., 2011), contextual bandits (Li et al., 2010), and combinatorial bandits (Chen et al., 2013). The relative feedback in the stochastic bandits setting is known as dueling bandits, which is initialized by Yue et al. (2012) and studied by Ailon et al. (2014); Komiyama et al. (2015); Sui et al. (2018); Saha & Gaillard (2022), etc. All of the above models assume that the learner receives either the absolute feedback, i.e., the reward of the selected arm, or the relative feedback, i.e., the winning arm in pair of arms, but not both, which are different from the study on fusion of absolute and relative feedback in this paper.
Bandits with additional information. While we are the first study the fusion of absolute and relative feedback in the stochastic bandits setting, there are prior works considering the absolute (reward) feedback with some types of "augmentation" feedback. In the line of works of conversational bandits (Zhang et al., 2020; Wang et al., 2023b; Li et al., 2024), a learner interacts with a contextual linear bandit model, and besides receiving the reward feedback from puling arms, the learner can also occasionally query "key-terms" to collect some side information of the bandit model. Another line of works considers the bandits with "hints", where the "hint" can be additional reward observations (Yun et al., 2018; Lindstähl et al., 2020), initial reward mean guesses (Cutkosky et al., 2022), or the order of the reward realizations among two or more arms (Bhaskara et al., 2022), etc. However, these types of augmentation feedback provide information directly related the reward mean parameters (i.e., used to estimate the reward means), which is different from the relative feedback depending on dueling probabilities in the dueling bandits setting, and therefore, they are different from our study on the fusion of absolute and relative feedback in this paper.
Beyond stochastic bandits. The stochastic bandit literature is only a small subset of the wide online learning research area (Orabona, 2019). In contrast to the stochastic setting, the adversarial bandits-including adversarial MAB (Auer et al., 2002) and adversarial dueling bandits (Saha et al., 20slmeassume assume that the environment determined by an adversary and may adapt the learner's strategy. Generalizing the bandits setting with state transition, reinforcement learning (RI.) (Sutton et al., 1998) is another popular online learning model, where the learner interacts with the environment and receives reward feedback based on the state-action pairs. Noticeably, there is reinforcement learning with human feedback (RLHF) model (Wang et al.. 2023a; Ouyang et al., 2022) in RL literature, which can be regarded as a counterpart of the dueling bandits in bandits literature, where the learner receives pairwise comparison (relative) feedback. While there is vast online learning literature beyond the stochastic bandits, due ot the importance of the stochastic MAB, our study on the fusion of the absolute and relative feedback on bandits is a novel and unexplored topic.
B. Deferred Pseudo-code
This section presents the pseudo-code of initial warm-up phase (Algorithm 3) and the statistics update phase (Algorithm 4) of the proposed DR-MAB algorithms.
Algorithm 3 Warm-up (Initial phase)
1: Duel each pair of arms (k:, E) for k + l once (in total K(K 1) times), meanwhile, query each arm for rewards in a round-robin manner
2: t (KK-1)
3: Update Me,e, and dr,e, for all pairs (k, K K. (k + f), and Ne.,, Pu. for all arms k E IC
C. Proof of Lower Bound
Proof of Lemma 2.2. Step 1. Instance and event construction. Pick any suboptimal arm k * 1. We use the standard parameters defined in model section as the original instance I and then construct an alternative instances I' with parameters with a prime, e.g., uhe and v/ee- as follows.
-SE Me
il k
* Reward means 1/=- =
U1 + i
12

---

Fusing Reward and Dueling Feedback in Stochastic Bandits
Algorithm 4 Statisties update
1: for all arm pairs (k, f) K. K do
2:
if (k:, (i,,) or (kr,2, k2,1) then
3:
MA,e,1+1 Mx, +1
(Yv
4: Dx,6,t+1 &-
Mk.ca111
5: else
6:
Mr.ect+1 + Ma,ee and Pkieet1 t ikee for all arms h E IC do
7:
8:
if - kr then
9:
NA.++1 + Nx.t
Pe, t
10: iAN,++1
Na.441
11: else
12:
NA.111 f- Nr. and Ax,411 t Pixe
if k and lz < k
Dueling probabilities U81.22
ce,
if f < k and & = k.
V81.82
otherwise
where the e 0 is a small constant to be determined later, and the eş parameters are chosen such that kl(vk,, 1 + = kl(,,, 1) + c. Under this instance construction, the optimal arms are arm and arm the original and alternative instances, respectively. All reward distributions are Bernoulli. We denote E, P and E', Ip' as the expectation and probability under the original and alternative instances, respectively.
To facilitate the rest of the analysis, we define the empirical KL-divergence as follows,
(D) KL (n) = Σ
YK (1 Y (1, vk.ee
log
Yo. k,e + (1 (x.e,())) 1/,1))
#=1
KL (R)
(n) = Σ log
XR.W)HH + (1 (1 (1-1k)
[R.WW)H/ + + - (x,))) 1bb
KL(I,I') = KL (Ne.T)
(R)
ΣKLE (ME.TT)
KL (D)
Bek
where the subscript (s) refers to the th observation of the corresponding random variable, which differs from the time index. With these empirical Kl.-divergences defined, for any event &, we have the following relation holds (change measure),
PP(E) = E exp(
expl (xp(ex(((((ZZ))))
In the end the first step, we define two events as follows.
D =
kl (Vn,e, vhe) Mr,e.T + kl(us, MA) < <1 e)) log log
Esc
D2 IKL < (1- log r
In the remaining of this proof, we use two steps to prove that PP())) = o(1), which then implies the lemma.
Step 2. Prove PPD, n D2) o(1). We first apply the change of measure argument to transfer the measure of the event
Dj ( D2 from instance I to instance I'.
PP(DD D2) EE D2) exp(-KKL(Z,T)) > EL[(P) (2-))
13

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
which yields
P(D1nD)) < <T' T FP
NN.T (1 (1-e) log
TT--PP'
kl(/ux 14%)
T T-NE. > T (1 c) log
-T-ip
kl 19))
T EE' [Nu.T]
T 4 - ((1 - <) log T (a(mk:P()
(9)
Σ Eethr E' 8'[NN,,T
- T ((1 c) log T T Pk)
<( = o())
(10)
where inequality (9) is due the Markov incquality, and incquality (10) is due to the consistent policy assumption (Definition 2.1) that for any suboptimal arm e k under instance I', we have E' [NNerl = o(T") for any positive y.
Step 3. Prove P(D, D2) = o(1). To prove this claim, we first telescope the IP(Di D2) and focus on bounding of the empirical KL-divergence as follows,
P(D1 \ D2)
Σ kl (UR,,, MK,e.T + (Mp,,14))) < (1 - lo) log (T,(I,T') > (1- <) log T
2
< PP
Σ Bcc
kl (us,e, Vp.e) ME,T +
< e) log T
max DE,myENT W Vick: al ) (llp (1- log
KL (nx) + Σ
(R)
KLç
(D)
(m²) > (1- ;) log T
2
8cc
< P
max NL+ veck: 1. )mc
KL (nx) + Σ
KL
(D) (me) >
>11 1) 2) log T
tick
+ kl, )m, mn (1-e) log
Next, we variant of the maximal law of large numbers (LLN) (Bubeck, 2010, Lemma 10.5) to bound the empirical KL-divergence. To guarantee that all sample times N&,T and Ma, are large enough to apply LLN, we set the lower bound of NA.r and Mr,er as 5 log T for some small constant
as follows,
(R) KL (nL) + Eich KLg (m²)
(D)
max m. EN veck: (l( m 2f log
log T
(R) KL (nx) + Ecer KL, (me)
(D)
memmeNt mmme log veck
Eecr kl(pe,e. (aleserr.mmmttttleetme (met <(1 T
(11)
log
ō(k 1) mineck kl (v
5
+
kl( 146)
Then, because the maximal LLM (Bubeck, 2010, Lemma 10.5) implies lim maxignEN
kl(px, 1%) and
lim M-sos M
KL (m)
kl(Mn,,, v4,)) for any arm k. almost surely (a.s.), we bound the first term in the
M
14

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
right-hand side of (11) by the maximal LLN follows,
(R) KT.a (mx) Eeck KI. (m²)
1D)
max
ENT log. Leck el ) tha <
log
lim sup T-400
$ 1 66
(12)
log T
Therefore, combining (11) and (12), we have
(R) KL (nx) + Eech KL (me)
(D)
max EN wick: (//, )
+ +klpp (1--)) log
-1 +(0),
log
Noticing c 1 2 and letting + O, we proved that
P(D1 D2) E
KL
(R)
(nx) + Σ
KL
(D) (me) (1- 2) log T
2
MammENN YECk: kl(ve (k kl(ax,n <(1-
Bck
= o1))
Lastly, by letting be infinitesimally small, we have P(D1) = o(1), which implies the lemma.
Proof of Theorem 2.3 (regret lower bound). We first present the regret dccomposition terms of the reward and dueling feedback as follows.
RT
Σ 4>
(R) ask
Ne. +
E(1 (A + ( Muer.)
(13)
t<c
Then, with Lemma 2.2, its corresponding regret of each suboptimal arm + 1 can be lower bounded by the following optimizing problem,
aA (R) NA.T+ + Σ(1 a)) (4 + A MR.LTT
min
tak
s.t. Σ kl
(Riei 2
MR.er + kl(pk: p1 Na.r 2 (1 o(1)) log
Bcck
whose asymptotical solution is as follows,
E (R) T + Eeen (1 (1- a) + + MAeTl
adx kl(lee, un)
min (1 - (A + A
lim inf 7-000
min
log
(Vn,es
Lastly, we substitute the above lower bound for each terms in (13) and obtain the regret lower bound.
15

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
D. Proof of Upper Bounds
D.I. Regret Upper Bound for ELIMFUSION (Algorithm 1, Theorem 3.1)
Proof of Theorem 3.1. Step 1. Bound small probability event. We first show the concentration of the reward and dueling probabilities as follows,
2 log(Kt/0)
llog(Kt/o
| - mal 2 PP
Σ
P
jike
NE. - n1 IP (NNKe =n)
(14)
Nk.t
n=l
2 2og 2log(Kt/0 Kt/6))
P
Pixit - MAd
n=1
2 exp (-4log(Kt/8)
(15)
==1
25
K&6
where inequality (14) follows from the formula of total probability, and inequality (15) follows from Hoeffding's 's inequality, Therefore, we have
log (Ki/K)/))
(a)
T
K
T
35
P v KET,KEK,, p&l
(16)
NR.e
K443
K
2K
A=1
where inequality (a) follows from the union bound and the above concentration.
With a similar argument, we can show that the dueling probabilities also concentrate as follows,
2 2log(Kt/8)
38
P vt E T,k, E..,TT,EKK, vk.el >
Mx,c,
4K2
where the RHS's dominator different from (16) is because the number of arm pairs is K(K - 1)/2.
Step 2. Bound the maximal sample times for both types of feedback.
Elimination with reward feedbuck. One suboptimal arm is eliminated by reward feedback the following event happens,
log 2log(KL) (Kt/))
log (log(Kt/))
in, PiK, 2 141
2/
2
NR.t
NR.1
which would happen before the rearranged expression follows,
32 log( Kt/8)
No.1
(A()))
In other words, from the reward feedback and corresponding elimination, the sample times of arm i are upper bounded by 32 (Kg (1
Elimination with dueling feedback. The sample times for an arm from the dueling feedback is given by noticing that for any arm k, when
21og (log(Kt/8)
(log(Kt/O)
D4.e, + +1
< Vx.t +2
< 2.
Ma.e
Mk.t.
that is,
8log (Kt/8)
(1))
16

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
for all arms L, then the arm k must have been eliminated from the candidate arm set C. by Line 14 of Algorithm Therefore, the sampling times of arm pair (k: E) is upper bounded by (6)
)A
Step Bound the regret. Each suboptimal arm & may be eliminated by either reward or dueling feedback. So, the regret incurred by the reward querying of arm & is upper bounded as follows,
32 log( KT
K
8 llog KT)
4 log KT//) max )1 /2/
& k min
(R)
RTT
2
(A 1
where the factor K-1 is an upper bound of the ratio of sampling collection rate between reward and dueling feedback 2
because the number of arms in the candidate arm set C. is most K-1 times smaller than the number of arm pairs in the set. Next, we bound the regret incurred by the dueling querying of arm k. If the arm k is eliminated by the ducling feedback, then the dueling regret due to arm & can be upper bounded as follows,
(D) (A
+
(D) - 1) x
MEAT & Σ> ADD) KT/8) (1)
8(k 1) log( KT/5)
<
2
4
ECk
tcck
If the arm is eliminated by the reward feedback, implying the algorithm has queried the reward of arm le for at most 32 (878) times. During this period, dueling regret cost of any arm pair (k:, E) from some arm E < 1 is upper bounded as (1) follows.
(A ())
+ A (D)
1) 2 2
32 log log(K//))
644 (D) log (KT/8)
(A 12
(A (1)))
where the factor every reward query of arm is accompanied by at most two dueling comparison of arm pairs (k, E) from some arm e < k.
Taking the minimal among the above two cases, we have the dueling regret upper bound as follows,
64 (oloo(KT/0) 8(k: - 1oggo(TT/// )
8 log (T (ax (A -)}}
DD < (D) min
(A)))
(1)
Lastly, we bound the total regret as follows,
RT
(R) + (1- a1
40 (R) log( KT/0)
8(1 a) 1D) (KT())))
max (1 (2) 2//8 (A (D) )2 (K - 1)}
max (2))) (4 (2) 1)}
8(a (R) (1 4 (1) log(KT))
max (A
(2) (2)88 ( 11)}
17

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
D.2. Regret Upper Bound for DECOFUSION (Algorithm 2, Theorem 4.1)
Proof of Regret Upper Bound of Algorithm Step 1. Event definition. We start the proof by defining the following events,
1 2 Pao Vk E (RR) fii, 3 pi - 6, and Di 2 2 vk E R } j
A =
Gr =
&
max Me + 8
k KER (11)
H4 =
U
(Aum i = Pui and picee pkl > 8).
kER,
Uc U
(DLAs& 3 2. vh E E and Snd
u, < 5. vk K2t /8].
Se2"t ((0)
where the parameter 8 is small positive constant that satisfies < 5 < A The A. refers a good event, implying that the algorithm has correctly estimated the optimal arm at time slot I, i.e, ki = ((D) 1, and the other three refer to the bad events that the algorithm may not correctly estimate the optimal arm, either due to bad reward estimates or bad ducling probability estimates.
Notice that (1) if both events G. and Hf do not happen, i.e., 9 n HCC then the first condition of event A holds, and (2) if event U4 does not happen, then the second condition of event A₁ holds. Putting these together, we have the following relation between these events,
Gf nH nut S As, that is, A C CGUH,
In the rest of this proof, show claims: (1) the number of times that any of these three bad events Gt, Hr, and 24 happens is bounded by O(1) (a term independent of time horizon 7",, and (2) for the time slots that the good event A, happens, the regret of DECOFUSION is upper bounded as (7) shows.
Step 2. Bound the number of happening times of the bad events. Following Honda & Takemura (2010, Lemmas 16 and 17), we bound E. bound
Σ [G.) < O(1), and IF
Σ 1 (74) < O(1). Following Komiyama al. (2015, Lemma 5), we
E [{8)]
< ((eK-)(K)) Putting these results together, we have
T E
T
T
T +
1 [
E
Σ (
+
Σ
192
Σ
1(8)
< 0(1) 0(1) + Oeee & O(eck-I(k)
for some constant c > 0.
Step 3. Bound regret. Denote = [=oo as the threshold in Line of Algorithm 2. We first define the following three quantities as the sufficient number of times for exploring arm & from different types of feedback, for sufficiently small 6 0,
(1 + e) log T ((K)
(Suth
kl(ju, (11)
(1 + E) log T + ((K
M M(fuff)
k.1
kl(vn.1, 11)
(1 + é) eog T + +(KK
[Suff)
= min (N(S /(1 (B), //Stt// /8]
max {(1 - 3) kll klluu, u1), k
18

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
Next, we bound the expected number of times of exploring & for different types of feedback follows,
T
T
B[N & K/2+ + E
Σ
1
{AA)]
+11-3) 3) .
+11 (11-8)
Σ [Jr, and Ar}
(17)
1=1
T
B[M +1+B Σ [[49}
B.B
Σ
1 MT and Ar}
(18)
B[M <1+E
Σ [149)
VI<G<h
(19)
where the first constant term comes from the initialization of the algorithm (Algorithm 3), the last terms of (17) and (18) due to the imbalanced exploration in Line 12 of Algorithm 2, and the missing third term of (19) is because when event A, happens, the algorithm does not explore arm pair (k, E) for any suboptimal arm & o 1.
T
E
1 k k and A.}
(Sull)
Σ
E [1 (Jr, and Ae and NE. n, MA.1.t m]]
k
1=1 n,m> L.
(Bum
(Sul))
Σ
max (RR) k.t: k.0
1
} < logt + f(K) and A and Nu. = n, Mr = m]]
k
n,m Lik
max [a((aa()). 6), kl((xx, 1 }) < log T + {(K)
(Suu)
E
1
(uaD L
(20)
n.m3 L (Sum
(1( 2) $ max {kl(ux, M1 kl(uk,1 2/
}{
(Sul)
Σ
E
max kK((As(n))) (o0.0110),,k,......
(21)
k
1
n.m> (Sum
< Lx
(Suft)
Σ
IE p (l) -c)
kl(pk: M1)
}
+
Σ E
[IANCDAAam) )
kl(uk, 2)
}
1
1
n> L,
m
(Sul))
+ +0(c)))
(22)
where inequality (20) applies the (n) to denote the reward mean estimate with n samples, and (m)) to denote the dueling probability estimate with samples, inequality (21) is by substituting L I.(Suu)) the definition of L.k is for that the last two terms are bounded as (E)-2) in Honda & Takemura (2010, Lemma 15) and Komiyama et al. (2015, Lemma 6), respectively.
(S(fff)) inequality (22)
Therefore, the final regret upper bound is given as follows,
E Rr = [4 + E[R L4
(R) /a A /(1 a)) + Tog f(K))
max [E m1)/a², kl(kk, ()/(1 0(K3) +0())) + O(ecK-((K))
19

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
Dueling-basen bas-based regret R(D)
10a
10
Reward- Reward-based E--based regret
10a
10a.
102
102
- ElimNoFusiin MEDNoFusion
ElimFusion DecoFusion
Elimnoousion MEDNoFusion
ElimFusion DecoFusion
.....
10
10a
0
2
Round
x10
Round
x10
(a) Reward regret H
(b) Dueling regret 1!7
Figure 3: Regret comparison different settings (continue)
where we individual bound the two terms as follows,
E[ <
a E + (1 (1- ( M
1
(a(1 - 3 + (1 a)
( (1)
log + f(K)) + +((E
{(1 3) kl (1+: m1), 8 k1,,1,1 }
/a 4 / a (1 <) log T + f(K)) O
max [1(p /1)/a² kl ()((1
where the last inequality is by substituting the definition of parameter 3, and
E[ & (as (R) + (1 a) max 10)
(K(K- 1)
Σ 11481)
T
REK
K +
Σ 1149
+
1=1
where the K(K - 1) comes from the initialization of the algorithm (Algorithm 3).
E. Experimental Setup and Additional Experiments
E.1. Additional Experiments
This section further reports other experiments in Figure 3. Figures 3(a) and 3(b) plots the decomposed reward- and dueling-based regrets of the aggregated regret in Figure 2(a) in the main paper. They illustrate that the two fusion algorithms outperform the no-fusion algorithms regarding reward- based and ducling-basee regrets, respectively, highlighting the effectiveness of the fusion algorithms in mitigating regret costs the other feedback.
E.2. Experiment Setup
The experiments of Figures 2(a), 2(d), 3(a), 3(b) are conducted with = 16 arms, where their Bernoulli reward distributions are with means f = (0.86, 0.80, 0.75, 0.70, 0.65, 0.60, 0.55, 0.50, 0.45, 0.40, 0.35, 0.30, 0.25, 0.20, 0.15, 0.10). A dueling
20

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
probability matrix determines the dueling feedback follows,
0.50
0.54
0.57
0.60
0.63
0.65
0.69
0.71
0.73
0.76
0.78
0.82
0.86
0.91
0.95
0.98
0.46
0.50
0.54
0.58
0.61
0.64
0.67
0.70
0.74
0.76
0.79
0.81
0.84
0.87
0.89
0.92
0.43
0.46
0.50
0.54
0.58
0.60
0.63
0.66
0.69
0.72
0.76
0.79
0.83
0.85
0.88
0.91
0.40
0.42
0.46
0.50
0.54
0.58
0.61
0.64
0.66
0.69
0.72
0.76
0.79
0.82
0.85
0.88
0.37
0.39
0.42
0.46
0.50
0.54
0.56
0.59
0.63
0.66
0.69
0.72
0.76
0.78
0.82
0.86
0.35
0.36
0.40
0.42
0.46
0.50
0.54
0.57
0.59
0.63
0.67
0.70
0.73
0.76
0.79
0.82
0.31
0.33
0.37
0.39
0.44
0.46
0.50
0.54
0.58
0.61
0.64
0.68
0.71
0.72
0.75
0.79
0.29
0.30
0.34
0.36
0.41
0.43
0.46
0.50
0.54
0.57
0.59
0.62
0.65
0.68
0.72
0.76
0.27
0.26
0.31
0.34
0.37
0.41
0.42
0.46
0.50
0.54
0.58
0.61
0.63
0.66
0.69
0.73
0.24
0.24
0.28
0.31
0.34
0.37
0.39
0.43
0.46
0.50
0.54
0.56
0.59
0.62
0.66
0.69
0.22
0.21
0.24
0.28
0.31
0.33
0.36
0.41
0.42
0.46
0.50
0.54
0.56
0.58
0.61
0.65
0.18
0.19
0.21
0.24
0.28
0.30
0.32
0.38
0.39
0.44
0.46
0.50
0.54
0.57
0.58
0.62
0.14
0.16
0.17
0.21
0.24
0.27
0.29
0.35
0.37
0.41
0.44
0.46
0.50
0.54
0.56
0.59
0.09
0.13
0.15
0.18
0.22
0.24
0.28
0.32
0.34
0.38
0.42
0.43
0.46
0.50
0.54
0.56
0.05
0.11
0.12
0.15
0.18
0.21
0.25
0.28
0.31
0.34
0.39
0.42
0.44
0.46
0.50
0.54
0.02
0.08
0.09
0.12
0.14
0.18
0.21
0.24
0.27
0.31
0.35
0.38
0.41
0.44
0.46
0.50
where the value of Vi,j between arm pairs (1,J) is row column j. The algorithms are run for 200, 000 rounds with the following parameters for DECOFUSION and ELIMFUSION: experiment is repeated 100 times, and we report the average regret and the standard deviation of all runs.
0.5, 5 1/T, and f(K) 0.05 Each
Then, Figures 2(b) and 2(c) report the final aggregated regrets under the following two experiments.
Fixing v, varying j:: Fixing the dueling probability as in the matrix:
0.50
0.53
0.56
0.59
0.62
0.47
0.50
0.53
0.56
0.59
0.44
0.47
0.50
0.53
0.56
0.41
0.44
0.47
0.50
0.53
0.38
0.41
0.44
0.47
0.50
Vary μ (0.9,0.9- A, 0.0.9-22 2 0, 0,
4 x A), where A {0.06, 0.11, 0.21).
Fixing 14, varying Fixing μ {0.9, 0.78, 0.72, 0.66]. we consider vary preference matrix in:
0.5
0.5+xA
0 A
0.5 A
0 x A
0.5 A
0.5
0.5+1xA
0.5
0.5 A
V
0.5 2 A
0
0.5
0.5+2x A 0.5+1xA
3:5-3x4 A
0.5-1xA 0
0.5+1xA 0.5
0.5 - 4 A
0.5
0.5
0.5-1xA
0.5
where A E (0.03, 0.05, 0.07, 0.09, J. All other settings of the two experiments are the same as above.
F. Extended Discussions on Regret Definition
If the preference probability e ing a relation between the preference probability and reward mean, like the Bradley-Terry model V1,2 exp(x1)+exp(pe)
e is generated according to the reward means Pk, Pe for any arm pair (k:, E). Assum-
exp(s))
exp(y1-we or utility dueling bandits v1,2 1-(p-pp (Ailon et al., 2014). is stronger than the one in our paper and will exp(ai I
lead to better regret result.
Specifically, with this parametric relation, one only needs to focus one set of the parameters, either the reward means or the ducling probabilities. Let us consider the case that the reward mean (Fi .2,..., (K) as the basic parameters to estimate, and all observations from dueling feedback can be translated into reward feedback via the parametric relation. Under this point of view, the reward feedback provides direct observations from the reward mean parameters, and the dueling (preference) feedback between arms and can be considered "parametric reward feedback" depending on the reward

---

Fusing Reward and Ducling Feedback in Stochastic Bandits
mean parameters. For example, with the Bradley-Terry relation, the parametric form is a logistic function, which is similar to the logistic bandits (Faury et al., 2020), while with the utility dueling relation, the parametric form is linear function, which is similar to the linear bandits (Abbasi-Yadkori Yadkori et al., 2011).
With this interpretation, we believe that the final regret bound would depend reward gaps 4 (R) and have explicit
dependence on the dueling gaps 4 (D) (or the other way round if we consider the dueling probabilities as the basic parameters), and the regret improvement may be in the actual dependence of the reward gaps A ( (e.g.. the prefactor or the exponential order of this gap would be strictly less than than the best one without the dueling feedback option). To rigorously investigate the improvement in regret bounds under these stronger assumptions (out of the scope of current paper) an interesting research direction.
Motivation of current regret definition in Eq. (1) The current linear combination definition-esseciillll. the parameter [0. 1| is motivated by the cost difference between querying a reward feedback, as dueling feedback, as the dueling (relative) feedback is usually cost-efficient (Ouyang et al., 2022). Furthermore, this flexible definition covers many interesting scenarios, e.g., the case of a = 1 is the regret from reward feedback only, and the case of a = 0 is the regret from dueling feedback only, and the case of a = 1.2 the regret the simple sum of the two types of feedback.
Below, we provide three perspectives on changing the definition of regret in our paper. First, one only considers the regret from reward feedback ("define the regret as the loss in the expected reward"), and treat the dueling feedback as a side free observations, then this regret reduces the case of setting DECOFUSION algorithm achieves constant regret, as discussed in Lines 409-423 (left column).
1 in our regret definition. In this scenario, our
Second, if one also considers the regret cost due to dueling feedback but count this part of the regret in terms of the expected regret instead of the dueling (preference) probability in the current definition, then the new regret cost in each decision round would be the sum of the reward gaps of the pulled three arms (one for reward, a pair for dueling). For this new regret definition, our algorithm and analysis still works, and the only modification is in the regret upper bound results, where one needs to change the dueling gap A (D) in the nominator of Eq. (5) in Theorem 3.1 and Eq. (8) in Theorem 4.1 to the reward gap 21 (R) 4
Third, if one further assumes the Bradley-Tery model relation between reward means and dueling probabilities upon the new regret definition, this would lead to problem that is similar to logistic bandits (Faury et al., 2020), as discussed in the previous response, which is an interesting research direction.
22


Reviews:
[{"review_id": "khvRBEE1ol", "reviewer": "Reviewer_6nVK", "summary": "This manuscript considers a new bandit problem where the learner, at each step,  simultaneously chooses any of the K arms and any couple of the K arms and observe an absolute reward as well as a dueling reward. The incurred regret is a convex combination (with parameter $\\alpha$) of the absolute regret and the strong dueling regret.  Assuming that the ordering of the expected rewards is compatible with the dueling expected, the authors prove an asymptotic lower bound of the cumulative regret and introduce two new algorithms, the second one asymptotically matching the lower bound. Interestingly for $\\alpha$ close to zero or $\\alpha$ close to one, this corresponds to bandit problem with side information and the authors, in which case their algorithm DecoFusion achieves a constant regret.\n\n## update after rebuttal\nI understand the authors viewpoint that earlier papers on bandits (e.g Auer et al., 2002) only focused on purely asymptotic regimes. However, there has been a lot of literature in the last ten years (and in particular in the duelling literature) to weaken assumptions of the form $T> \\exp( cK)$; see again the introduction of Saha and Gaillard. In any case, I admit that this is perhaps a personal bias on the objective of being tightly asymptotically optimal versus non-asymptotically optimal, but there is a huge gap here between $T> \\exp(cK)$ and weaker conditions such as $T>K^2$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *W1): In my view, the regret bounds are of high asymptotic nature. [...] where T\\geq \\exp [ c K], which is quite disappointing.* \n\n**A1:** We respectfully disagree with the reviewer's characterization of our results as \"disappointing,\" particularly regarding the fact that our upper bound matches the lower bound asymptotically.  As detailed below, achieving asymptotic optimality in this context is a well-established practice in bandit literature. We hope the reviewer will reconsider the contributions of our paper in light of these points.\n\nFirstly, we clarify that our (gap-dependent) upper bound alone is non-asymptotic for any $T$, and it is expected to only match the lower bound asymptotically. Because the (gap-dependent) lower bounds in bandits literature (as well as our Theorem 3.1) are usually asymptotic (holds when $T\\to\\infty$), and thus the upper bounds can only match them in an asymptotic manner. This is a common practice for optimal bandit algorithms. For example, the regret upper bounds of the known optimal stochastic bandit algorithms, e.g., KL-UCB (Cappe et al., 2013, Theorem 1) and DMED (Honda & Takemura, 2010, Theorem 4), also match the lower bound only asymptotically.\n\nSecondly, the condition $T\\ge \\exp(cK)$ for matching lower bounds is common and needed in most bandits algorithms (omitted by default, so this is often unaware). For example, the regret upper bound of the seminal UCB1 algorithm (Auer et al., 2002a, Theorem 1) can be expressed as $$R_T \\le O\\left( \\sum_{k>1}\\frac{\\log T}{\\Delta_k} + K \\right).$$\nTo match the $\\Omega\\left( \\sum_{k>1}\\frac{\\log T}{\\Delta_k}\\right)$ lower bound, it needs $T \\ge \\exp (cK)$ as well. This condition is required for any bandit algorithm whose finite (gap-dependent) regret upper bound has an additive $O(K)$ term---a common upper bound term in the literature. Therefore, the required condition $T\\ge \\exp(cK^{1+\\xi})$ in our Theorem 4.1 is very basic as $\\xi$ can be as close to zero as possible.\n\n- Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235–256, 2002a.\n\n---\n> *C1) $\\epsilon$ is not defined the statement of Theorem 4.1*\n\n**A2:** We thank the reviewer for pointing this typo out. The $\\xi$ and $\\epsilon$ are the same in the statement of Theorem 4.1, and we will correct this in the final version.\n\n---\n> *Q1) [...] this phenomenon is not unique and in fact arises for bandit problems with side information [...]*\n\n**A3:** We thank the reviewer for mentioning this reference. We will add it to the final version of this paper. We will also clarify that the phenomenon's uniqueness is in the context of the fusion of reward and dueling feedback in comparison to the bandits with either reward or dueling feedback.\n\n---\n> *Q2) Following W1, [...] what extent using more recent approaches in duelling bandits allows to bypass the limitation [...of...] $T\\ge \\exp\\left( cK^{1+\\xi} \\right)$ [...]*\n\n**A4:** Although there is indeed some recent progress on dueling bandits, e.g., the best-of-both world algorithm by Saha & Gaillard (2022, Theorem 3) (whose stochastic regret upper bound has a suboptimal prefactor $4$ in the dominating $\\log T$ term), to the knowledge of the authors, the best-known regret bounds for stochastic dueling bandits are still the RMED algorithm by Komiyama et al. (2015, Theorem 3), which also relies on the $T\\ge \\exp\\left( cK^{1+\\xi} \\right)$ condition. We will add this discussion to the final version of this paper and raise it as an open question for future research on dueling bandits.", "claims_and_evidence": "I feel that it is a bit overclaimed that \"DecoFusion achieves the optimal regret\". While the main theorem (Theorem 4.1) seems valid, the result is so asymptotic, that the optimality is not achieved as soon as the number of arms K is not constant (see W1)", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proofs of the main theorem (Theorem 4.1).", "experimental_designs_or_analyses": "Yes, but the numerical experiments are only here for illustration.", "relation_to_broader_scientific_literature": "This manuscript considers a new bandit problem where the learner both plays an arm and a duel of arms. As such, I am not aware of any previous on this topic. However, the authors build upon previous works on K-arms bandits (mostly Honda & Takemura (2010)) and duelling bandits (Komiyama et al. (2015)). That being said, the combination of the above approaches in DecoFusion is clearly new and original.", "essential_references_not_discussed": "I am not aware of any, although the authors could further discussed the recent literature in duelling bandits (see e.g. the references in Saha and Gaillard or the survey of Bengs et al., 2018).", "other_strengths_and_weaknesses": "S1) This is the first manuscript that deals with this problem, although the motivations are somewhat allusive. The authors establishes almost asymptotic matching lower and upper bounds for the problem, but see W1. \n \nS2) The manuscript is mostly well written and the authors manage to provide the intuition behind their algorithms and the different rates. \n\nW1) In my view, the regret bounds are of high asymptotic nature. For instance,   the regret bound in Theorem 4.1 only matches the lower bound only in the regime where T\\geq \\exp [ c K], which is quite disappointing.", "other_comments_or_suggestions": "C1) $\\epsilon$ is not defined the statement of Theorem 4.1", "questions_for_authors": "Q1) In Section 2, you write \"Later in this paper, we will show that a sublogarithmic o(log T ) regret is actually achievable (in fact, T -independent constant regret) in these two scenarios, revealing a unique phenomenon of DR-MAB\". Up to my knowledge, this phenomenon is not unique and in fact arises for bandit problems with side information (e.g. the player plays several arms and only incurs the regret of a single arm). \n\nQ2) Following W1, I am wondering to what extent using more recent approaches in duelling bandits allows to bypass the limitation that we need $T\\geq \\exp(c K^{1+\\zeta})$ for optimality.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FxoR0ZZF7X", "reviewer": "Reviewer_YVjo", "summary": "The paper investigates a K-armed bandit problem in which, in addition to the standard observations of arm rewards (modeled by a Bernoulli distribution), the learner has the option to select two additional arms at each time step. The feedback received includes comparisons between the selected arms, which are also based on a Bernoulli feedback mechanism, with preferences that align with the mean rewards. I.e., the paper \"fuses\" standard bandits with duelling bandits.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *Q1: the practical value of the paper is not clear. [...] simplistic and niche*\n\n**A1:** **Practical value** While the authors agree that the bandits setting (a framework in favor of theoretical analysis) of this paper is indeed simplified, we believe that the proposed algorithms and theoretical results are still valuable for practice for the following reasons:\n\nThe standard LLM training usually has two separate steps: (1) use the responses from human experts (absolute feedback)  to conduct a supervised learning, called supervised fine-tuning (SFT), and (2) use the human preference (relative feedback) among multiple responses generated from the SFT model to conduct a preference directly training (either directed preference optimization (DPO) or reinforcement learning from human feedback (RLHF)).\n\nAlthough not exactly the same, these two steps correspond to the reward (absolute) and dueling (relative) feedback in our bandits setting. Our algorithm suggests a training approach to conduct these two steps in parallel, potentially saving the human labeling cost and improving the training efficiency (as our regret upper bounds improve over the existing ones). Investigating this potential approach in LLM training is an interesting direction.\n\nAs our ultimate goal is to effectively combine the absolute and relative feedback (e.g., in realistic RLHF alignment for LLM), the proposed algorithms and theoretical results in the bandits framework are meaningful and concrete steps toward this goal. We thank the reviewer for raising this concern. We will discuss this point in the final version of this paper.\n\n---\n> *Q2: [...] the theoretical results appear to be a combination of existing tools and findings [...] the algorithms do not appear to align with this lower bound.*\n\n**A2:** **Novelty** First, we clarify that our paper focuses on fusing both reward and dueling feedback, each drawn from distributions from a different set of parameters, and the information on either type of feedback can not be translated into the other type. Due to this separation, it is intrinsically difficult to incorporate them to optimize performance on the same bandit task. To address the difficulty, we propose two novel algorithmic frameworks: elimination fusion and decomposition fusion, neither of which is known in prior literature. The elimination fusion is simple and more straightforward to be extended to other applications. In contrast, the decomposition fusion is optimized for the stochastic bandit scenario and achieves near-optimal regret performance. \n\n**Open Problem** Secondly, we agree with the reviewer that removing the condition that \"the best relative arm for eliminating a suboptimal arm is the one with the highest reward\" (i.e., $\\ell_k^*=1$) is indeed an interesting direction, as we discussed in the paper (Lines 382--384 (right column) and Lines 396--408 (left column)), However, this required condition is a reminiscence of the dueling bandits setting, and it is still a partially open problem (Komiyama et al., 2015). Once this problem is fully addressed in the basic dueling bandits, one can apply our two fusion algorithm techniques to the new dueling bandits algorithms to remove this condition in our setting.\n\n---\n> *Q3: [...] The statement appears to be problematic. Does \"orthogonal\" here imply independence? [...]*\n\n**A3:** We thank the reviewer for suggesting the improvement of this phrase. Although there is indeed an ordering relation that \"the dueling probability of arm $k$ winning over arm $\\ell$ is greater than $0.5$ if and only if arm $k$ has a higher expected reward than arm $\\ell$,\" we clarify that the reward feedback cannot be directly translated into dueling feedback in the general case, unless some stronger relations are assumed between the reward means and dueling probabilities (e.g., the Bradley-Terry model suggested by Reviewer qwFm (hyperref)).\n\n**Rephrase** In the final version of this paper, we will clarify the terminology and rewrite this sentence to avoid the confusion as follows,\n\n\"As the reward means and dueling probabilities only have a weak ordering relation---the dueling probability of arm $k$ winning over arm $\\ell$ is greater than $0.5$ if and only if arm $k$ has a higher reward mean than arm $\\ell$---and their observations are independently sampled from distributions with different parameters, the estimations of reward means $\\mu_k$ and dueling probabilities $\\nu_{k,\\ell}$ are intrinsically separated. This separation makes it difficult to combine these two types of feedback in online learning directly.\"", "claims_and_evidence": "Yes, the results are supported by proofs and appear to be correct to me.", "methods_and_evaluation_criteria": "The theoretical presentation is consistent with standard practices in the literature. The experiments utilize synthetic data. The paper leans more towards a theoretical approach.", "theoretical_claims": "Yes, Theorem 2.3 on the lower bound, as well as Theorems 3.1 and 4.1 on the regret performance of algorithms, make sense and appear to be correct to me. I have reviewed the proofs.", "experimental_designs_or_analyses": "Yes, the proofs appear correct. The experiments are standard and use synthetic data.", "relation_to_broader_scientific_literature": "The paper mainly derives theoretical regret bounds on fusion of standard and duelling bandits and also presents some basic synthetic experiments.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "The fusion of reward-based and preference-based feedback is an intriguing problem, and I assume many practitioners employ heuristics in their algorithm deployments. This paper adopts a theoretical approach and models the problem mathematically using the multi-armed bandit (MAB) framework, which could potentially be interesting.\n\nHowever, I have some reservations regarding the scope and contribution of the paper.\n\nFirst, the practical value of the paper is not clear. The setting and framework are too simplistic and niche, making them inapplicable to motivating examples such as large language models (LLMs), which utilize inherently different algorithms and techniques.\n\nSecond, the theoretical results appear to be a combination of existing tools and findings, which makes them somewhat expected. While the lower bound seems complete and logical, the algorithms do not appear to align with this lower bound. The only aspect that seems specific to this paper is the method of fusing these two feedback models and eliminating arms based on the best statistics (relative feedback or reward), which remains an open question. Specifically, the results align with the lower bound only when the best relative arm for eliminating a suboptimal arm is the one with the highest reward. This limitation also constrains the theoretical contribution, which seems to be the primary focus of the paper.", "other_comments_or_suggestions": "-", "questions_for_authors": "\"The estimations of reward means $\\mu_k$ and dueling probabilities $\\nu_{k,l}$ are orthogonal as their observations are independently sampled from distributions with different parameters. This orthogonality makes it difficult to directly combine these two types of feedback in online learning.\"\n\nThe statement appears to be problematic. In what sense are these estimations considered orthogonal? Does \"orthogonal\" here imply independence? The reward feedback can clearly be translated into relative feedback, which suggests a relationship between the two types of feedback rather than a complete orthogonality. It may be beneficial to clarify this terminology to avoid confusion.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "-"}}, {"review_id": "AEL6ksEkUS", "reviewer": "Reviewer_TSNv", "summary": "This paper looks into the problem of stochastic bandits with fusing reward and dueling feedback where the regret is defined as linear combination of the normal regret and averaged dueling regret.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *Q1: The regret bound for No Fusion algorithm seems to be different in the Table 1 and line 224 (right)*\n\n**A1:** Indeed, they are different. The regret bound in Table 1 combines two separate (optimal) regret bounds for the reward and dueling bandits, respectively. Therefore, the deminonator is $\\min\\{(\\Delta_k^{(R)})^2,\\Delta_k^{(D)})^2 \\}$ as both are in the best dependence. Nevertheless, the regret bound in line 224 is by combining two elimination algorithms for reward and dueling bandits, respectively (for comparison with our fusion elimination algorithm). As the elimination algorithm in dueling bandits is suboptimal, the denominator becomes  $\\min\\{(\\Delta_k^{(R)})^2,\\Delta_k^{(D)})^2 / K \\}$. \n\nWe thank the reviewer for raising this concern. We will clarify this in the final version of this paper.\n\n---\n\n> *Q2: The empirical log-likelihoods seems to be defined in algorithm 2, not algorithm 1 or 4.*\n\n**A2:**  Yes, it is the case because the empirical log-likelihoods are only used in Algorithm 2 (also updated in Algorithm 2 at Lines 29-30). Algorithms 1 and 4 do not need the empirical log-likelihoods.\n\n---\n\n> *Q3: In the reward explore, dueling exploit stage, is there a reason to define the dueling action as both $\\hat k_t^R$*\n\n**A3:** Yes, as the arm $\\hat k_t^{(R)}$ is the current empirical best arm, we choose the empirical best arm pair $(\\hat k_t^{(R)}, \\hat k_t^{(R)})$ as the dueling action to exploit the empirical good arms (for the sake of minimizing the dueling regret since we only explore via reward feedback in that case).\n\n---\n\n> *Q4: The algorithm line 6 and 8 does not do the exclusion of the reward set form dueling set as in line 264(right). Is there an intuition that this kind of non-approximate design works?*\n\n**A4:** We thank the reviewer for catching this delicate but important algorithm design technique.\n\nIn Line 264 (right), as the ground-truth decomposition is known, one should exclude the reward set from the dueling set and vice versa. However, as the actual decomposition is unknown a prior in $\\texttt{DecoFusion}$, we need to be conservative (i.e., allow both sets $\\hat{\\mathcal K}_t^{(D)}$ and $\\hat{\\mathcal K}_t^{(R)}$ to have some overlap instead of taking exclusion) to ensure enough explorations from both feedback sides for uncertain arms so to learn the ground-truth decomposition at the end. We will add this discussion in the final version of this paper to clarify the intuition behind this design.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "- I checked the lower bound proof but did not review the rest, as I am not familiar with the proof of the dueling bandit.  \n\n- I have a question regarding the proof of the lower bound. In the construction of the original and alternative instances, the proof seems to define the reward means and dueling probabilities separately. My question is: when the reward mean is defined, aren’t the dueling probabilities automatically determined?", "experimental_designs_or_analyses": "Yes, looks good to me.", "relation_to_broader_scientific_literature": "This problem is related to general bandit problem beyond natural reward feedback and has it's application in real world systems such as recommendation system.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper proposes the fusing problem and presents two algorithms to solve it. The algorithms are well-designed, and the achievable upper bounds match the order of the lower bounds. I did not find any significant weaknesses in this paper, as it is self-contained and inspiring.", "other_comments_or_suggestions": "- The regret bound for No Fusion algorithm seems to be different in the Table 1 and line 224 (right)\n- The empirical log-likelihoods seems to be defined in algorithm 2, not algorithm 1 or 4.", "questions_for_authors": "- In the reward explore, dueling exploit stage, is there a reason to define the dueling action as both $\\hat {k}_t^{R}$\n- The algorithm line 6 and 8 does not do the exclusion of the reward set form dueling set as in line 264(right). Is there an intuition that this kind of non-approximate design works?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qhaIWDDjAY", "reviewer": "Reviewer_qwFm", "summary": "This paper investigates the fusion of numerical and preference feedback in stochastic bandits, where both feedback types are gathered in each timestep. The authors derive a regret lower bound, demonstrating that an efficient algorithm may incur only the smaller among the reward and dueling-based regret for each arm. The authors propose two fusion algorithms: (1) a simple elimination fusion algorithm that leverages both feedback types to explore all arms and unifies collected information by sharing a common candidate arm set, and (2) a decomposition fusion algorithm that selects the more effective feedback to explore the corresponding arms and randomly assigns one feedback type for exploration and the other for exploitation in each round. The elimination fusion experiences a suboptimal multiplicative term of the number of arms in regret due to the intrinsic suboptimality of dueling elimination. In contrast, the decomposition fusion achieves regret matching the lower bound up to a constant under a common assumption. Extensive experiments validate the efficacy of the provided algorithms and theoretical results.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *W1. [...] other relation between the preference probability and expected reward [...] like the Bradley-Terry model*\n\n**A1:** We thank the reviewer for raising this intriguing question. A relation between the preference probability and expected reward, like the Bradley-Terry model $\\nu_{1,2} = \\frac{\\exp(\\mu_1)}{\\exp(\\mu_1) + \\exp(\\mu_2)} = \\frac{\\exp(\\mu_1-\\mu_2)}{\\exp(\\mu_1-\\mu_2) + 1}$ or utility dueling bandits $\\nu_{1,2} = \\frac{1 + (\\mu_1 - \\mu_2)}{2}$ (Ailon et al., 2014), is indeed stronger than the one in our paper and will lead to a better regret result.\n\nSpecifically, with this parametric relation, one only needs to focus on one set of parameters: the reward means or the dueling probabilities. Let us consider the case that the reward means $(\\mu_1, \\mu_2, \\dots, \\mu_K)$ as the basic parameters to estimate, and all observations from dueling feedback can be translated into reward feedback via the parametric relation. Under this point of view, the reward feedback provides direct observations from the reward mean parameters, and the dueling (preference) feedback between arms $k$ and $\\ell$ can be considered as a \"parametric reward feedback\" depending on the reward mean parameters. For example, with the Bradley-Terry relation, the parametric form is a logistic function, which is similar to the logistic bandits (Faury et al., 2020), while with the utility dueling relation,  the parametric form is a linear function, which is similar to the linear bandits (Abbasi-Yadkori et al., 2011). \n\nWith this interpretation, the authors believe that the final regret bound would depend on reward gaps $\\Delta_k^{(R)}$ and have no explicit dependence on the dueling gaps $\\Delta_k^{(D)}$ (or the other way round if we consider the dueling probabilities as the basic parameters), and the regret improvement may be in the actual dependence of the reward gaps $\\Delta_k^{(R)}$ (e.g., the prefactor or the exponential order of this gap would be strictly less than than the best one without the dueling feedback option). To rigorously investigate the improvement in regret bounds under these stronger assumptions (out of the scope of the current paper) is an interesting research direction. We will add this discussion in the final version of this paper to clarify the potential improvement in regret bounds under these stronger assumptions.\n\n---\n> *W2. [...] motivation of the regret definition [...] regret as the loss in the expected reward due to not always selecting the optimal arm*\n\n**A2:** We thank the reviewer again for raising this interesting question.\n\n**Motivation** The current linear combination definition --- especially, the parameter $\\alpha\\in[0,1]$---is motivated by the cost difference between querying reward feedback and dueling feedback, as the dueling (relative) feedback is usually cost-efficient (Ouyang et al., 2022). Furthermore, this flexible definition covers many interesting scenarios, e.g., the case of $\\alpha = 1$ is the regret from reward feedback only, and the case of $\\alpha = 0$ is the regret from dueling feedback only, and in the case of $\\alpha = \\frac{1}{2}$, the regret is the simple sum of the two types of feedback. We will add this discussion to this paper's final version to clarify the regret definition's motivation.\n\n**Other regret definitions** Below, we provide three perspectives on changing the definition of regret in our paper.\n\nFirst, if the reviewer means to only consider the regret from reward feedback (\"define the regret as the loss in the expected reward\"), and treat the dueling feedback as side free observations, then this regret reduces to the case of setting $\\alpha = 1$ in our regret definition. In this scenario, our $\\texttt{DecoFusion}$ algorithm achieves constant regret, as discussed in Lines 409--423 (left column).\n\nSecond, if the reviewer means also to consider the regret cost due to dueling feedback but counts this part of the regret in terms of the expected regret instead of the dueling (preference) probability in the current definition, then the new regret cost in each decision round would be the sum of the reward gaps of the pulled three arms (one for reward, a pair for dueling). For this new regret definition, our algorithm and analysis still work. The only modification is in the regret upper bound results, where one needs to change the dueling gap $\\Delta_k^{(D)}$ in the nominator of Eq. (4) in Theorem 3.1 and Eq. (5) in Theorem 4.1 to the reward gap $2\\Delta_k^{(R)}$.\n\nThird, if one further assumes the Bradley-Terry model relation between reward means and dueling probabilities upon the new regret definition, this would lead to a problem that is similar to logistic bandits (Faury et al., 2020), as discussed in the previous response, which is an interesting research direction.\n\n---\n- Faury, L., Abeille, M., Calauz`enes, C., and Fercoq, O. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pp. 30523060. PMLR, 2020.", "claims_and_evidence": "The claims made in this paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "The theoretical results look reasonable, but I didn’t go through every proof.", "experimental_designs_or_analyses": "The experiments look reasonable.", "relation_to_broader_scientific_literature": "This paper is relevant to the literature.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper is very well-written and the considered problem is well-motivated from real-world decision-making scenarios where numerical feedback and preference feedback are simultaneously collected, e.g., recommendation systems.\n2.\tThe algorithm design and theoretical results are complete and well executed. The authors design two fusion algorithms, one of which achieves an optimal regret. Rigorous regret upper and lower bounds are provided. The presented table and figure for result summary (Table 1 and Figure 1) are clear.\n3.\tExperimental results are presented to validate the empirical effectiveness of the proposed algorithms and the provided theoretical findings.\n\nWeaknesses:\n\n1. (Not a weakness, just a comment) In the formulation, this paper only considers that the preference probability of choosing arm a over arm b is greater than 0.5 if arm a has a higher expected reward than arm b. Besides this ordering relation, this paper does not assume or utilize any other relation between the preference probability and expected reward.\n\nWhat if the preference probability is generated according to the expected reward, like the Bradley-Terry model used in the RLHF literature? Will this additional assumption allow a better regret result? More discussion is needed here.\n\n2. What is the motivation of the regret definition (the equation above Section 2.1), which is a linear combination between the regret in classic bandits and the regret in dueling bandits? It seems that this is not very natural. Isn’t it more natural to define the regret as the loss in the expected reward due to not always selecting the optimal arm, which may need an additional assumption that the preference probability is generated according to the expected reward, like the Bradley-Terry model?", "other_comments_or_suggestions": "Please see the weaknesses above.", "questions_for_authors": "Please see the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a setting of stochastic multi-armed bandits where the feedback contains both absolute and relative values. The authors provide an algorithm to solve this problem, along with a rigorous analysis of its performance.  

According to the reviews the paper is well written and easy to follow. The proofs are sound, and the results of the algorithm match the lower bound, up to constants (for constant number of arms). The two major issues raised were about (1) the guarantees of the algorithm, (2) the motivation. 

For (1), 6nVK mentions that for non-constant K (number of arms) the regret bound is no longer tight. YVjo mentions that the assumption that the best arm for elimination w.r.t relative feedback has the best absolute reward is too strict. For (2), the problem presented is new. The authors did not provide a concrete application using it as-is, but reviews mentioned motivation for it from recommendation systems. 

In both cases, the flaw mentioned is subjective. For (1) the solution for the limitations does not seem to be trivial, so this is not a clear incompleteness of the paper, rather an open problem. For (2), the question of whether a new problem is or isn’t interesting is clearly subjective. Since 2 out of the 4 reviewers did find the problem interesting (e.g. qwFm: "the considered problem is well-motivated from real-world decision-making scenarios .."), it is likely that more people in ICML will find it interesting as well. 

To conclude, in my opinion the weaknesses pointed out are mild and the paper provides a well written and sufficiently thorough analysis of a new problem.
Decision: Accept (poster)