Online Clustering of Dueling Bandits

Thanks for the valuable advice. Our responses are as follows. We will add the discussions.

Q1: Technical challenges:

A1:

Novel Algorithm Design:

• Cluster Estimation under Dueling Feedback: Our setting does not allow direct use of prior cluster vector estimation methods in classical CB with numerical feedback. With numerical feedback, closed-form ridge regression enables simple updates of user-level covariance matrices and regressors, followed by cluster vector computation using aggregated statistics (e.g., Lines 6–8 in Algo.1 of Wang et al., 2024a). In contrast, dueling feedback lacks closed-form MLE, making direct adaptation infeasible. To address this, we maintain a history buffer $\mathcal{D}_t$ (e.g., Line 10, Algo.1) recording user indices, arm choices, and dueling feedback. We then filter data for users in inferred clusters and estimate cluster vectors via MLE (e.g., Line 6, Algo.1).

• Carefully Designed Edge Deletion Thresholds: Threshold design under dueling feedback is more intricate than in absolute feedback settings and relies on refined calculations (Lemmas B.2 and C.5) to ensure correctness. In the neural setting, this is further complicated by the non-linear reward function. The required Cluster Separation assumption (Assumption 2.7) deviates from those in prior CB works, making its integration into the edge deletion rule for CONDB particularly challenging.

Novel Theoretical Analysis: We highlight the main technical challenges for CONDB as an example:

• Incorporating the novel Cluster Separation assumption (Assumption 2.7) for CONDB into the analytical framework of linear CB poses substantial difficulties. We address this by leveraging a linear approximation of the neural net as the analytical basis (Lemmas C.1 and C.2).
• Deriving $T_0$ after which all users are correctly clustered (Lemma C.5), is particularly challenging due to the non-linear and dueling nature of the reward. Classical CB analysis bounds the L2 distance between true and estimated linear parameters, which is not applicable here. To overcome this, we use neural network linearization and rigorously analyze the resulting approximation error (Lemmas C.3, C.4, and C.5).
• A key challenge in proving a sub-linear bound lies in the proper use of the effective dimension $\widetilde d$ (Eq.(16)). Direct extensions of Lemma B.5 from the COLDB (linear rewards) analysis would yield a bound linearly dependent on $p=O(m_{\text{NN}}^2)$, which becomes vacuous as $m_{\text{NN}}$ grows polynomially with $T$. To address this, we adopt techniques from neural bandits to reformulate Lemma B.5 for CONDB, allowing us to express the regret in terms of $\widetilde d$ (Lemma C.9).

Q2: Setting Importance and LLM applications:

A2:

• Motivation: Leveraging user relations to accelerate learning is well-established in CB literature (e.g., Gentile et al., 2014), particularly in recommender systems where users naturally form groups [1]. Preference-based feedback is also more aligned with human behavior and common in applications like RLHF, motivating the use of user relations under dueling feedback.
• Extension to More General Settings: Some works have explored similar-but-not-identical user preferences under numerical feedback (Ban & He, 2021b; Wang et al., 2024b). As the first to study preference feedback in CB, we focus on standard assumptions to address core challenges. Extending to those settings is left for future work.
• LLM Applications: Our methods can directly extend recent work on neural dueling bandits for prompt optimization [2] to the multi-user setting.

Q3: Optimality in $m$ and lower bounds:

A3:

• Following Wang et al. (2024a) and Saha (2021), we can derive a lower bound of $O(\sqrt{dmT})$ for linear case. Algo.1 achieves an upper bound of $O(d\sqrt{mT})$, which is tight up to $\sqrt d$—a common gap in linear bandits (e.g., LinUCB). Thus, our upper bound is optimal in $m$ for the linear case. For the neural case, lower bounds remain open even in the single-user setting. However, we hypothesize that our bound is also optimal in $m$ in the neural setting, as clustering naturally introduces a $\sqrt m$ scaling over the single-user case.
• While adversarial bandit algorithms can achieve $O(\sqrt T)$ regret, the regret definition differs: adversarial regret compares to the best fixed arm, while stochastic regret compares to the optimal dynamic policy. Direct comparisons are not meaningful.

Q4: Real-world data natively following clustering and dueling assumptions:

A4: Our dataset and clustering setup follow standard practice in prior CB works using common benchmarks. We added a real-world dataset (Yelp), where COLDB continues to outperform baselines (see figure). We'll explore other datasets in future work.

Reference

[1] ClustKNN: a highly scalable hybrid model-& memory-based CF algorithm, KDD 2006.

[2] Prompt Optimization with Human Feedback, 2024.

Thanks for your positive feedback and valuable suggestions, our responses are as follows.

Q1: Lower bounds:

A1: Thanks for the helpful suggestion. Based on prior techniques (Wang et al., 2024a; Liu et al., 2022) and the single-user dueling bandit lower bound (Saha, 2021), we can derive a lower bound of $O(\sqrt{dmT})$ for the linear setting. Our Algo.1 achieves an upper bound of $O(d\sqrt{mT})$, which is tight up to a $\sqrt d$ factor—a common gap in linear bandits (e.g., LinUCB). Thus, our upper bound is tight and optimal in $m$ for the linear case, and we will include this lower bound in the final version.

For the neural case, even the single-user non-dueling setting lacks a known lower bound, making it an open problem. However, we hypothesize that our upper bound is also optimal in $m$ for the neural setting, as clustering naturally introduces a $\sqrt m$ scaling compared to the single-user case.

Q2: Technical challenges involved in the algorithm design and its analysis:

A2:

Novel Algorithm Design:

• Cluster Estimation under Dueling Feedback: Our setting does not allow direct use of prior cluster vector estimation methods in classical CB with numerical feedback. With numerical feedback, closed-form ridge regression enables simple updates of user-level covariance matrices and regressors, followed by cluster vector computation using aggregated statistics (e.g., Lines 6–8 in Algo.1 of Wang et al., 2024a). In contrast, dueling feedback lacks closed-form MLE, making direct adaptation infeasible. To address this, we maintain a history buffer $\mathcal{D}_t$ (e.g., Line 10, Algo.1) recording user indices, arm choices, and dueling feedback. We then filter data for users in inferred clusters and estimate cluster vectors via MLE (e.g., Line 6, Algo.1).

• Carefully Designed Edge Deletion Thresholds: Threshold design under dueling feedback is more intricate than in absolute feedback settings and relies on refined calculations (Lemmas B.2 and C.5) to ensure correctness. In the neural setting, this is further complicated by the non-linear reward function. The required Cluster Separation assumption (Assumption 2.7) deviates from those in prior CB works, making its integration into the edge deletion rule for CONDB particularly challenging.

Novel Theoretical Analysis: We highlight the main technical challenges for CONDB as an example:

• Incorporating the novel Cluster Separation assumption (Assumption 2.7) for CONDB into the analytical framework of linear CB poses substantial difficulties. We address this by leveraging a linear approximation of the neural net as the analytical basis (Lemmas C.1 and C.2).
• Deriving $T_0$ after which all users are correctly clustered (Lemma C.5), is particularly challenging due to the non-linear and dueling nature of the reward. Classical CB analysis bounds the L2 distance between true and estimated linear parameters, which is not applicable here. To overcome this, we use neural network linearization and rigorously analyze the resulting approximation error (Lemmas C.3, C.4, and C.5).
• A key challenge in proving a sub-linear bound lies in the proper use of the effective dimension $\widetilde d$ (Eq.(16)). Direct extensions of Lemma B.5 from the COLDB (linear rewards) analysis would yield a bound linearly dependent on $p=O(m_{\text{NN}}^2)$, which becomes vacuous as $m_{\text{NN}}$ grows polynomially with $T$. To address this, we adopt techniques from neural bandits to reformulate Lemma B.5 for CONDB, allowing us to express the regret in terms of $\widetilde d$ (Lemma C.9).

Q3: Is it necessary for the algorithm to know the number of clusters in advance?

A3: No, our algorithms can adpatively cluster the users during the learning process, the number of clusters $m$ does not need to be known.

Thanks for your valuable suggestions. Our responses are as follows. We will incorporate them after revision.

Q1: Lemma B.2, C.5, and more robust deletion:

A1: We will emphasize these lemmas in the main text. Our edge deletion mechanism and analysis follow prior clustering of bandits (CB) works. For stronger early-stage robustness, the algorithms can be modified to restart with a complete graph each round and re-check edges involving previously served users. This ensures correct clustering w.h.p. after $T_0$, mitigating early-stage misclusterings.

Q2: Definition of f:

A2: We have defined f at the Input of Algo.1 (top of page 6) it's used in the proof without restating. We will redefinie f in the proof.

Q3: Setting of similar preference in clusters:

A3: As the first to study preference feedback in CB, we focus on standard assumptions to address its core challenges. While similar-preference settings with numerical feedback have been studied (Ban & He, 2021b; Wang et al., 2024b), extending our results to that setting is an independent direction which we leave for future work.

Q4: Terminology of "user collaboration" and the question about the limited shared information setting:

A4:

• We will replace “user collaboration” with clearer terms like “user relation” or “user similarity” as per your advice.
• For scenarios without centralized coordination or with limited shared information, these fall within the scope of federated bandits. Since our work follows the standard CB setting, such extensions are beyond our current scope, but we view this as a promising future direction.

Q5: Assumptions (particularly uniform arrival):

A5: Our assumptions follow standard practice in CB and are used solely for theoretical analysis. The uniform arrival assumption can be relaxed to general distributions (Lines 161–164).

Q6: Computation of CONDB:

A6: Even in the baseline where each user runs NDB independently, an NN must still be trained per iteration—yet this incurs higher regret (scaling with $\sqrt u$). Our CONDB trades off computation for better performance. To reduce computational overhead, we can adopt batched training strategies (e.g., "Batched Neural Bandits" (Gu et al., 2024)), updating the NN only every few iterations.

Q7: Techinical challenges

A7: The dueling (and neural) feedback introduces new technical challenges to the classic CB study. Please kindly refer to our A1 in response to Reviewer AU83 for details.

Q8: Lower bounds:

A8: Following Wang et al. (2024a) and Saha (2021), we can derive a lower bound of $O(\sqrt{dmT})$ for linear case. Algo.1 achieves an upper bound of $O(d\sqrt{mT})$, which is tight up to $\sqrt d$—a common gap in linear bandits (e.g., LinUCB). So our upper bound is tight and optimal in $m$ for the linear case.

For the neural case, lower bounds remain open even in the single-user setting. However, we hypothesize that our bound is also optimal in $m$ in the neural setting, as clustering naturally introduces a $\sqrt m$ scaling over the single-user case.

Q9: Experiments:

A9: Our main contribution is theoretical, but we have added experiments as per your advice to support our findings. Due to time constraints, we leave more extensive experiments as future work.

(1) Only two datasets: We added an experiment with the Yelp dataset (see figure).

(2) Ablation for m: We added an additional value of m=4 (see figure), the results are consistent.

(3) Non-uniform arrival: We included experiments under non-uniform arrivals, which show consistent performance gains (see figure). The user arrival probabilities are randomly sampled from a Dirichlet distribution with a concentration parameter of 10.

(4) Baselines beyond independent dueling bandits: Prior CB methods do not handle preference feedback, so direct comparisons are not applicable. Second, following standard CB practice, it is common to use independent per-user algorithms as baselines when introducing a new setting.

(5) More complex non-linear functions: We tested a more complex function: $(\theta^T x)^4 + cos(\theta^T x)$. CONDB still consistently outperforms the baseline (see figure).

(6) Confidence intervals: We have indeed included confidence intervals (Lines 369-371 and the figures).

Q10: NTK:

A10: The NTK assumption follows standard practice in neural bandit theory and is used only for analysis; in practice, very wide networks are not needed. Our experiments indeed use small NNs—1 hidden layer with 32 nodes—which already achieve strong performance.

Q11: LLM application:

A11: The recent work "Prompt Optimization with Human Feedback" uses neural dueling bandits for prompt optimization. Our methods can be directly applied to extend their method to the multi-user setting.