Fusing Reward and Dueling Feedback in Stochastic Bandits

W1. [...] other relation between the preference probability and expected reward [...] like the Bradley-Terry model

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.

Specifically, 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).

With 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.

---

W2. [...] motivation of the regret definition [...] regret as the loss in the expected reward due to not always selecting the optimal arm

A2: We thank the reviewer again for raising this interesting question.

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.

Other regret definitions Below, we provide three perspectives on changing the definition of regret in our paper.

First, 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 $`DecoFusion`$ algorithm achieves constant regret, as discussed in Lines 409--423 (left column).

Second, 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)}$.

Third, 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.

---

• 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.

Q1: The regret bound for No Fusion algorithm seems to be different in the Table 1 and line 224 (right)

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 \}$.

We thank the reviewer for raising this concern. We will clarify this in the final version of this paper.

---

Q2: The empirical log-likelihoods seems to be defined in algorithm 2, not algorithm 1 or 4.

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.

---

Q3: In the reward explore, dueling exploit stage, is there a reason to define the dueling action as both $\hat k_t^R$

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).

---

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?

A4: We thank the reviewer for catching this delicate but important algorithm design technique.

In 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 $`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.

Q1: the practical value of the paper is not clear. [...] simplistic and niche

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:

The 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)).

Although 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.

As 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.

---

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.

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.

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.

---

Q3: [...] The statement appears to be problematic. Does "orthogonal" here imply independence? [...]

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)).

Rephrase In the final version of this paper, we will clarify the terminology and rewrite this sentence to avoid the confusion as follows,

"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."

W1): In my view, the regret bounds are of high asymptotic nature. [...] where T\geq \exp [ c K], which is quite disappointing.

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.

Firstly, 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.

Secondly, 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).$ To 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.

• Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235–256, 2002a.

---

C1) $\epsilon$ is not defined the statement of Theorem 4.1

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.

---

Q1) [...] this phenomenon is not unique and in fact arises for bandit problems with side information [...]

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.

---

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)$ [...]

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.