Conversational Generalized Linear Bandits with Hybrid Feedback

Yurui Zou; Qirun Zeng; Jinhang Zuo

cs.LGOct 26, 2026

Conversational Generalized Linear Bandits with Hybrid Feedback

Authors: Yurui Zou, Qirun Zeng, Jinhang Zuo

Organizations: University of Science and Technology of China, Hefei, China · City University of Hong Kong, Hong Kong SAR, China

Abstract

Conversational bandits improve recommendations by actively querying users about key-terms to elicit their item preferences. However, existing methods typically assume homogeneous feedback for items and key-terms, using either absolute rewards or pairwise comparisons. In practice, item feedback often takes the form of clicks or ratings, while comparisons are more natural for key-terms. To address this gap, we study conversational generalized linear bandits with hybrid feedback, combining absolute item rewards and relative key-term comparisons. We propose Conversational UCB with Hybrid Feedback (HyConUCB), which constructs unified confidence bounds from heterogeneous feedback and adaptively selects key-term comparisons by balancing information gain and directional coverage. Through a refined regret analysis that jointly exploits both feedback sources, we establish a regret bound that improves upon reward-only and adapted dueling-only benchmarks. Experiments on synthetic and real-world datasets validate the effectiveness of our algorithm.

Figures & tables

Figure 1: An illustration of conversational bandits with hybrid feedback in a movie recommender system. Users provide absolute feedback on recommended movies through likes or dislikes. The system also occasionally asks users to compare movie genres, such as comedies and horror movies, to elicit relative preferences.

Algorithm	Leading term	Lower-order term
Reward-only [ 4 ]	$\tilde{O}\left(d\sqrt{T/\kappa_{\star}}\right)$	$\tilde{O}(\kappa d^{2})$
ConDuel (adapted) [ 2 ]	$\tilde{O}\left(\kappa d\sqrt{T/\kappa_{\star}}\right)$	$\tilde{O}(\kappa^{2}d^{2})$
HyConUCB (ours)	$\tilde{O}\left(d\sqrt{\frac{T/\kappa_{\star}}{1+\eta\bar{v}^{-1}}}\right)$	$\tilde{O}\left({d^{2}}/(\kappa^{-1}+\eta)\right)$

Table 1: Regret bound comparison between HyConUCB and homogeneous-feedback benchmarks.

Figure 2: Cumulative regret on synthetic data for different values of the parameter norm bound $S$ . The advantage of HyConUCB and its variants over other baselines becomes more distinct as $S$ increases, consistent with our theoretical analysis.

Figure 3: Parameter estimation error on synthetic data for different values of $S$ . Lower values indicate more accurate estimates. HyConUCB and its variants generally achieve lower estimation errors than other baselines.

Figure 4: Cumulative regret on synthetic data for different values of the common intercept $B$ . As $B$ increases, relative feedback becomes more informative than absolute feedback. The deteriorating performance of Var-AM is consistent with this trend.

Figure 5: Results on real-world data. For LLM routing, oracle regret in panel (b) grows approximately linearly, making differences between algorithms less apparent. We therefore use expert regret in panel (c) as our primary metric.

Bandit Learning

See all 54 papers

Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback
May 7, 2026Qirun Zeng, Xuchuang Wang, Jiayi Shen +3Multi-Armed Bandits Best-Arm Identification
Department of Computer Science City University of Hong Kong, Hong Kong SAR, China · Manning College of Information & Computer Science University of Massachusetts Amherst, Amherst, MA, USA · School of Management University of Science and Technology of China, Hefei, Anhui, China +3
Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries
Jun 7, 2026Linfeng Cao, Ming Shi, Ness B. ShroffMulti-Armed Bandits Combinatorial Multi-Armed Bandits
Department of Computer Science and Engineering, The Ohio State University · Department of Electrical Engineering, University at Buffalo · Department of Electrical and Computer Engineering, The Ohio State University
On the Complexity of Preference-Based Bandits
Sep 30, 2026Ahmed Ben Yahmed, Marc Abeille, Clément CalauzènesPairwise Preference Learning Multi-Armed Bandits
CREST, ENSAE Paris, FAIRPLAY · FAIRPLAY

May 7, 2026J/K move · Enter open · S save

Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

Qirun Zeng, Xuchuang Wang, Jiayi Shen, Xutong Liu+2

Department of Computer Science City University of Hong Kong, Hong Kong SAR, China · Manning College of Information & Computer Science University of Massachusetts Amherst, Amherst, MA, USA · School of Management University of Science and Technology of China, Hefei, Anhui, China+3

Multi-Armed Bandits Best-Arm Identification Dueling Bandits Generalized Linear Bandits

Open paper AskPDF arXiv

We study fixed-confidence best arm identification in generalized linear bandits under a hybrid feedback model: at each round, the learner may query either (i) absolute reward feedback from a single arm or (ii) relative (dueling) feedback from an arm pair, both governed by generalized linear models. We introduce a likelihood-ratio--based confidence sequence that unifies heterogeneous generalized linear observations and yields an explicit ellipsoidal confidence set under a self-concordance assumption. Building on this confidence set, we propose a hybrid Track-and-Stop algorithm that adaptively allocates queries by tracking a minimax-optimal design over a joint action space of arms and pairs. We establish

δ

-correctness and provide high-probability upper bounds on the stopping time. We further extend the framework to a cost-aware setting that accounts for heterogeneous acquisition costs across feedback modalities. Empirical experiments demonstrate that the proposed algorithms significantly improve sample efficiency over baseline methods.

Abstract

Bandit Learning

Explore similar work

Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries

On the Complexity of Preference-Based Bandits