WorksComputer Science
Conversational Generalized Linear Bandits with Hybrid Feedback
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.
Introduction
Conversational recommender systems (CRSs) improve recommendation quality by actively interacting with users to elicit their preferences. Unlike traditional recommender systems that primarily learn from feedback on recommended items, CRSs can proactively query users about key-terms associated with groups of items, such as movie genres or news categories. These additional interactions help alleviate the cold-start problem by enabling more efficient preference learning. To formalize this process, Zhang et al. [1] introduced conversational contextual bandits, where the learner sequentially recommends items (i.e., arms) and observes user feedback in the form of rewards. In addition, the learner can occasionally initiate conversations by querying users about selected key-terms and collecting additional feedback. By jointly leveraging item-level and key-term-level feedback, conversational bandits can learn user preferences more efficiently and improve recommendation performance.
Existing conversational bandit methods primarily consider two types of user feedback: absolute rewards and pairwise comparisons. Early studies on conversational contextual bandits [1] assume that users provide absolute feedback, such as clicks or ratings, for both recommended items and queried key-terms. More recently, Yang et al. [2] introduced conversational dueling bandits, where user preferences are elicited through pairwise comparisons of items and key-terms. While both feedback types provide valuable preference information, assuming a homogeneous feedback form may not fully reflect practical recommendation scenarios. In particular, users can readily provide absolute feedback on recommended items, whereas pairwise comparisons are often more natural for abstract
We consider rounds with cumulative conversational queries, where controls the query frequency. We report the case , where is the feature dimension and is the dimension spanned by conversational queries (see Eq. (10) for general ). Here, and denote the worst-case and average optimal-arm curvatures, respectively; is the maximum reward curvature; and measures conversational information. The ConDuel bound is obtained by adapting its analysis to our setting. hides logarithmic factors and fixed constants.
key-terms. This motivates the study of conversational bandits with hybrid feedback, combining absolute item rewards and relative key-term comparisons.
For example, in a movie recommender system illustrated in Figure 1, users may click on or rate recommended movies, providing absolute feedback on items. Meanwhile, the system can occasionally ask users to compare movie genres, such as “Do you prefer comedies or horror movies?”, obtaining relative feedback on key-terms. Combining these two feedback types allows the system to learn user preferences more effectively without requiring pairwise comparisons for every recommendation. However, integrating heterogeneous feedback into conversational bandits with theoretical guarantees remains challenging, as absolute rewards and pairwise comparisons follow different statistical observation models. Existing work has only partially addressed this problem [3].
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.
Motivated by these observations, we study conversational generalized linear bandits with hybrid feedback, focusing on absolute arm rewards and relative key-term comparisons1. We adopt generalized linear models (GLMs) to capture diverse user responses within a unified framework. To overcome the limitations of existing conversational dueling bandits [2], whose confidence bounds depend on the global worst-case curvature, we extend the confidence sequence construction of Lee et al. [4] to conversational bandits setting, handling heterogeneous arm and key-term feedback without this dependence in the confidence radius. Building on these confidence sequences, we propose Conversational UCB with Hybrid Feedback (HyConUCB), which selects arms using upper confidence bounds and adaptively queries key-term pairs by balancing information gain and directional coverage. Through a refined regret analysis that jointly exploits information from both feedback sources, we establish improved regret guarantees over reward-only and adapted dueling-only benchmarks, as summarized in Table 1. Our analysis explicitly quantifies the benefits of conversational feedback. We also demonstrate the effectiveness of HyConUCB through experiments on synthetic and real-world datasets.
Table 1. Regret bound comparison between HyConUCB and homogeneous-feedback benchmarks.
Our main contributions are summarized as follows:
We formulate conversational generalized linear bandits (GLBs) with hybrid feedback, integrating absolute arm rewards and relative key-term comparisons under a unified generalized linear model. This framework captures heterogeneous user feedback commonly encountered in conversational recommendation systems.
We develop HyConUCB, which constructs time-uniform confidence sequences from heterogeneous feedback without relying on global worst-case curvature scaling. The algorithm combines UCB-based arm selection with an adaptive key-term querying strategy that balances information gain and directional coverage.
We establish improved regret guarantees through a refined analysis that jointly exploits information from both feedback sources. In particular, we develop a new elliptical potential bound that incorporates conversational information despite the nonlinear curvature of GLMs, yielding improved regret bounds over reward-only and adapted dueling-only benchmarks.
We conduct extensive experiments on synthetic data and two real-world datasets, Yelp and xRouteBench, covering restaurant recommendation and LLM routing. The results demonstrate the effectiveness of HyConUCB in reducing cumulative regret and improving preference estimation, highlighting the benefits of hybrid feedback across different settings.
Related Work
Our work builds on several research areas, and we review some recent work in the most related areas.
Conversational Bandits. Zhang et al. [1] introduced ConUCB, which augments item feedback with key-term queries to accelerate preference learning. Building on this framework, Xie et al. [3] proposed RelativeConUCB to incorporate relative key-term feedback. Although its feedback configuration is similar to ours, RelativeConUCB is a simple empirical extension of ConUCB [1] and does not establish regret guarantees. Wang et al. [5] proposed ConLinUCB, jointly estimating user preferences from arm-level and key-term-level feedback. Based on this framework, Yang et al. [2] studied conversational dueling GLBs, and Liu et al. [6] developed more effective query strategies for linear conversational bandits. However, the former’s regret analysis yields a suboptimal bound in the GLM setting and the latter’s techniques cannot be directly extended to GLBs because of the nonlinear terms introduced by GLMs. We therefore develop new techniques for regret analysis in conversational GLBs. To the best of our knowledge, we provide the first regret guarantees for conversational bandits with hybrid feedback.
Generalized Linear Bandits. In a canonical generalized linear model, an exponential-family response has natural parameter and mean , where is unknown [7]. Filippi et al. [8] introduced GLM-UCB for generalized linear bandits and established regret guarantees. Subsequent work has improved confidence estimation and regret analysis in GLBs, including through the use of self-concordance [9]. In particular, Lee et al. [4] developed a unified likelihood-ratio confidence sequence for GLMs, with convex confidence regions and an ellipsoidal relaxation under self-concordance. We adapt this confidence construction to the joint likelihood of absolute arm rewards and relative key-term feedback.
Relative and Hybrid Feedback. Relative feedback has been widely studied in bandit learning and preference-based learning [10, 11, 12]. Relative key-term feedback has also been studied in conversational recommendation [2, 3]. More recently, Wang et al. [13] studied stochastic bandits that combine reward and dueling feedback. He et al. [14] considered hybrid bandits with heterogeneous offline and online feedback, and Zeng et al. [15] took a step further by studying best-arm identification in GLBs with hybrid feedback, where a shared latent parameter links absolute rewards and relative comparisons. We adopt this shared-parameter formulation to represent user preferences, while focusing on regret minimization and studying hybrid feedback across the item and key-term levels: absolute rewards on items and relative comparisons between key-terms.
Problem Formulation
Generalized Linear Model
We formulate both types of feedback using GLMs, so we begin by introducing the generalized linear model (GLM). In a canonical GLM, the conditional distribution of observation , given a natural parameter , belongs to an exponential family and is specified by
Here is the log-partition function, is the known dispersion factor and is the log base measure. We use to denote the conditional probability density or mass function of given . A fundamental property of GLMs is that the conditional mean of is given by
where is the mean function (inverse link function). For convenience, we define .
Conversational Generalized Linear Bandits with Hybrid Feedback
We consider a sequential decision-making problem where the learner interacts with a user over rounds. Let denote a set of arms and denote a set of key-terms. The relationship between the arms and the key-terms can be characterized by a weighted bipartite graph , whose nodes are divided into two sets and , and weighted edges are represented by the matrix with representing the relationship between arm and key-term .
At round , the learner observes a candidate set . It then selects an arm and receives an absolute reward from the user. Each arm is associated with a -dimensional feature vector . The corresponding feature vector pool at round is . We write for the feature vector of the selected arm. Let for every arm feature. The user’s preference is represented by a vector , where . Then the reward is defined as
The learner obtains additional user feedback through key-term conversations. We set the conversational feedback to be relative, that is, the learner selects a pair of key-terms and receives the dueling result of them.
We define the key-term feature vector as
A nondecreasing integer-valued function , with , is defined to model the frequency of conversations. Before selecting an arm, the learner conducts conversations. For each , the learner selects a key-term pair . Define its comparison feature vector as
Thus , and the learner observes the dueling feedback with distribution
where indicates preference for .
Both arm reward and conversational dueling feedback are modeled as GLMs with a shared parameter , but possibly different mean functions and . We use subscripts and to distinguish reward and dueling quantities. We define the feedback modality to be c for absolute feedback and d for relative feedback.
Let the query pool contain all pairwise differences from the key-term pool, and let and . Unlike prior works that assume full-dimensional conversational coverage () [2, 5], our algorithm also applies when conversations cover only a subspace ().
Under the conversational GLBs with hybrid feedback problem described above, our objective is to minimize the cumulative regret in rounds. Let . Following the definition in Filippi et al. [8], we define the regret as
Following Lee et al. [4], Zeng et al. [15], we assume that the log-partition functions are three times continuously differentiable, with . For modality , we use a self-concordance bound and curvature bound :
Hybrid Conversational UCB Algorithm
Confidence Sequences
We construct confidence sequences for the unknown user preference vector . Following the procedure in Zeng et al. [15] and Lee et al. [4], we first give a likelihood-ratio–based confidence sequence. Then we relax it to ellipsoidal confidence sequence which is more suitable for our algorithm design and analysis.
Define the cumulative negative log-likelihood function at round as
Following Lee et al. [4], we define and
where
and is the Lipschitz constant of on .
Lemma 4.1. With probability at least , we have for all .
Proof Sketch. To prove it, we index the arm rewards and key-term comparisons in their actual order of observation. Before arm selection in round , there are observations. Write the resulting sequence as , where denotes the modality and denotes for an arm reward or for a key-term comparison. Eventually, we have
This function has the same form as the cumulative negative log-likelihood function in Zeng et al. [15]. Applying Zeng et al. [15, Lemma 3.1] gives Lemma 4.1.
Algorithm 1 HyConUCB
Require: The weighted bipartite graph , conversational frequency function , parameter norm bound
Construct the query pool .
for do
Set .
for do
Solve query distribution according to Eq. (5).
Sample according to .
Query and observe , and set .
end for
Compute .
Select .
Observe and set .
end for
Let . The regularized joint Hessian at is
Following the ellipsoidal construction of Lee et al. [4 Theorem 3.2], let , we define
Lemma 4.2. For every , . Consequently, with probability at least , , for all .
The proof is given in Appendix § 9.§ 1.
Algorithm Design
Building on the confidence sequences above, we present the Conversational UCB with Hybrid Feedback algorithm (HyConUCB; Algorithm 1). The central idea of HyConUCB is to balance information gain and directional coverage in key-term selection, while employing the UCB principle for arm selection.
At each round , the learner first conducts conversations to gather additional information about user preferences through key-term comparisons. It then updates its parameter estimate using both arm rewards and key-term comparisons, and selects an arm according to the UCB principle.
We first describe the key-term selection rule. For information gain, we adopt the MaxInp principle [16]. This principle selects the key-term that maximizes the information uncertainty, i.e., , where is the joint Hessian immediately before query in round .
For each query , calculate
where is the MaxInp score of .
Next we consider directional coverage. For a query distribution on , the matrix summarizes how the sampled query features cover different directions. Its eigenvalues reflect how strongly the queries explore the corresponding eigenvector directions. To encourage coverage of every direction in , we use the minimum eigenvalue of this matrix restricted to . Define
where denotes the minimum eigenvalue restricted to .
Finally, we solve
According to , we sample from .
The first term in Eq. (5) favors queries with large MaxInp scores, while the second term encourages information coverage in the least-observed direction. The parameter controls this trade-off. So the resulting query rule balances the information gain and directional coverage. It also guarantees the conditional information lower bound in Lemma 4.3. The proof is provided in Appendix § 9.§ 2.
After completing the conversational queries, the learner computes the updated parameter estimate using all feedback observed so far. Based on Lemma 4.2, we define the UCB score of each arm as
The learner then selects an arm that maximizes the UCB score, i.e.,
breaking ties arbitrarily. Finally, the learner observes the arm reward , which is incorporated into the parameter estimation in subsequent rounds.
Lemma 4.3. Let denote the -algebra generated by the history through the end of round . Under the query rule in Eq. (5), there exists a constant such that, almost surely, for every ,
where is the orthogonal projection matrix onto .
Regret Analysis
In this section, we establish a regret bound for HyConUCB. We use the notations
For the analysis, set , and .
For , define
Let
We now establish the theoretical guarantees of Algorithm 1.
Theorem 5.1. With probability at least , Algorithm 1 satisfies
Proof Sketch. There are two main challenges in the regret analysis of conversational generalized linear bandits. First, the information contributed by each observation is weighted by a nonlinear term, that is, the joint Hessian contains curvature weights such as . The analysis of ConDuel [2] handles this dependence by scaling based on the global worst-case curvature, which introduces a factor into the confidence width and leads to a suboptimal confidence set.
Thanks to the confidence sequences in Lee et al. [4], we can now obtain tighter confidence sequences whose radii do not explicitly depend on . The second challenge is to retain the information from both arm rewards and key-term comparisons when bounding the elliptical potential sum
Although ConDuel and ConLinUCB combine both sources when estimating the user parameter, key steps in their regret analyses lower-bound the joint information matrix using only one source [2, 5]. Such bounds do not retain the full information from both feedback sources. Moreover, the techniques developed for linear conversational bandits, including those of Liu et al. [6], do not directly handle the curvature weights in our joint Hessian. These limitations motivate us to develop more effective techniques for regret analysis.
Our first step is to construct a tractable lower surrogate for . Let minimize over , as in Eq. (18), and define
Lemma 5.2. With probability at least , for every , we have
Lemma 5.2 replaces the comparison term in the joint Hessian by an information lower bound, which is more convenient for later analysis.
We next bound the potential sum. To jointly exploit information from both the arm side and the key-term side, we modify the classical elliptical potential lemma and get Theorem 5.3.
Theorem 5.3. Let and satisfy . Then
where is defined in Eq. (7). The same bound holds for arbitrary coefficients in place of , with the same replacements in .
Combining these results with the regret decomposition similar to Lee et al. [4] yields the final regret bound. Detailed proofs are given in Appendix § 10.
Regret order. Now we give the regret order of HyConUCB. Consider with , and define . Let hide logarithmic factors and constants depending on , , , and the GLM coefficients. In this case, our regret bound is
The two groups represent the contributions from subspace and , respectively. Conversations improve the contribution from , while the contribution from retains its reward-only order. It is intuitive because the conversational information only covers this subspace.
We derive this regret order by bounding . For , the second term of satisfies
The proof is given in Appendix § 11.§ 1. Combining this bound with the first term of gives
Substituting Eq. (11) into Theorem 5.1 gives Eq. (10).
Regret comparisons. We compare our bound with the reward-only benchmark and ConDuel. For an explicit comparison, consider the -dimensional subspace only. The reward-only bound [4] has a contribution from of . Compared with it, our leading term is reduced by a factor of . If , the lower-order term in Eq. (10) is , removing from the reward-only lower-order term. The condition is attainable, as illustrated in Appendix § 11.§ 2.
Next, we adapt the analysis of ConDuel [2] to our regret definition and arm-selection rule, retaining its confidence set construction and approach to bounding the potential sum in Eq. (9). This gives a contribution from of . Relative to our bound, this bound has an additional factor of in both its leading and lower-order terms. This factor is from its suboptimal confidence set. Moreover, it does not exhibit the improvement over the reward-only benchmark captured by in Eq. (10), while our new potential sum bounding techniques establish this improvement for our algorithm.
Extension to Reverse Configuration
The hybrid feedback setting considered above can also be extended to reverse configuration: users compare arms and provide absolute feedback on a single key-term at a time. Let and . At each round, the learner collects responses , with for , then selects and observes .
The cumulative negative log-likelihood is
Using this loss and its Lipschitz constant , construct the likelihood-ratio confidence sequence and its ellipsoidal relaxation as in § 4.1. Lemmas 4.1 and 4.2 still apply, with appropriate adjustments to the feature-norm bounds for the two feedback types.
For each conversation, apply Eq. (5) to the pool of single key-term feature vectors. The argument of Lemma 4.3 yields the same form of conditional information lower bound on the span of these vectors, with the absolute-feedback curvature weights.
For arm selection, first retain arms that are not confidently worse than any competitor:
Then select the pair with the largest uncertainty in its utility difference:
Following Saha [16], we define the cumulative dueling regret as
On the confidence event, an optimal arm belongs to , so this selection rule bounds the instantaneous regret by , following the MaxInp analysis of Saha [16 Theorem 3]. Summing over rounds and applying Cauchy–Schwarz gives
We bound the potential sum in Eq. (14) by adapting Lemma 5.2 and Theorem 5.3, with arm differences and single key-term feature vectors replacing arm features and key-term differences, respectively. The proofs follow the same arguments as before and are omitted for brevity.
Experiments
In this section, we describe experimental settings and results on both synthetic data and real-world data. We set the trade-off parameter of HyConUCB to and use the mean functions .
Baselines. We compare our algorithm with the following baselines:
ConDuel [2]: ConDuel is designed for conversational dueling bandits, in which both arm-level and key-term-level observations are dueling feedback. To adapt it to our experimental setting, we modify its arm-selection rule to a UCB rule.
OFUGLB-UCB [4]: OFUGLB is developed for generalized linear bandits in Lee et al. [4]. We adapt its original optimism in the face of uncertainty (OFU) rule to a UCB rule, which is more suitable for our conversational bandit setting.
Var-Random: A variant of our algorithm that selects a key-term pair uniformly at random.
Var-AM: A variant of our algorithm that obtains absolute conversational feedback. Its MLE and confidence sequences are adjusted accordingly. For query in round , it selects
where is defined in Section 4.
Experiments on Synthetic Data
Data Generation. We construct the synthetic data following [1]. We set the dimension to , the number of users to , the size of the key-term pool to , and the size of the arm pool to . We generate the arm feature vectors as follows. First, for each key-term , we sample a pseudo-feature vector , whose coordinates are drawn independently from the uniform distribution . For each arm , we randomly sample an integer and then select uniformly without replacement a subset such that . The weights are defined by . For each arm , we first draw an unnormalized feature vector from , where , and then normalize it as . Thus, every arm satisfies . After generating all arm features, we compute the feature vector of each key-term as . Finally, for each user , we independently sample and define the user parameter as for . In our simulations, we set the time horizon to and the conversation-frequency function to . At each round , we randomly select 100 arms from without replacement to form . The same is presented to all algorithms.
Cumulative Regret. We repeat each experiment over 10 random seeds, averaging over all users within each run. As shown in Figure 2, HyConUCB reduces the final mean cumulative regret by more than 40% relative to OFUGLB-UCB, the reward-only baseline, for every tested value of . HyConUCB achieves the lowest final mean regret for and , while Var-Random performs slightly better for . As increases, ConDuel’s advantage over OFUGLB-UCB narrows. This pattern is consistent with ConDuel’s sensitivity to the worst-case curvature, which can become small as the parameter norm grows.
Figure 2. Cumulative regret on synthetic data for different values of the parameter norm bound . The advantage of HyConUCB and its variants over other baselines becomes more distinct as increases, consistent with our theoretical analysis.
Parameter Estimation Error. We measure estimation accuracy by the mean error , with smaller values indicating more accurate estimates. Figure 3 shows that the error generally decreases over time for all algorithms. HyConUCB achieves the lowest final mean error for and and remains competitive for , where Var-Random achieves the lowest error and Var-AM also finishes slightly below HyConUCB. Across all three settings, HyConUCB yields more accurate estimates than OFUGLB-UCB, demonstrating the benefit of conversational feedback for parameter estimation.
Figure 3. Parameter estimation error on synthetic data for different values of . Lower values indicate more accurate estimates. HyConUCB and its variants generally achieve lower estimation errors than other baselines.
Advantage of Hybrid Feedback. To examine the benefit of hybrid feedback, we use the common intercept construction in Appendix § 11.§ 2. More concretely, we first generate the relative arm features and user directions using the sampling procedure above and normalize both to unit length, so that . We then set and construct and . Consequently, we have and . We set , , , and vary . The common intercept cancels out in key-term comparisons, making relative feedback more informative than absolute responses in this setting.
Figure 4 shows that HyConUCB achieves the lowest final mean cumulative regret for all three values of . ConDuel also outperforms OFUGLB-UCB, consistent with the value of relative conversational feedback in this setting. As increases, Var-AM’s relative advantage over OFUGLB-UCB diminishes, and their regret curves nearly coincide at . While Var-AM performs similarly to HyConUCB in the preceding synthetic experiments, it falls further behind HyConUCB here. This larger performance gap provides further evidence for the benefit of hybrid feedback in this setting.
Figure 4. Cumulative regret on synthetic data for different values of the common intercept . As increases, relative feedback becomes more informative than absolute feedback. The deteriorating performance of Var-AM is consistent with this trend.
Experiments on the Yelp Dataset
Data Generation. We conduct experiments on the Yelp dataset, which we preprocess following Zhang et al. [1]. We retain restaurants with at least 50 reviews and users with at least 100 reviews, and then randomly select 100 users for the simulations. Each restaurant is treated as an arm, and its associated categories are treated as key-terms. The 500 key-terms with the largest restaurant coverage are retained. We construct restaurant feature vectors from the city, categories, star rating, review count, and 34 additional common business attributes, and then apply PCA to obtain 10-dimensional arm feature vectors. Finally, we convert the original five-point ratings into binary feedback. For each user , we estimate the preference parameter by solving the following -ball-constrained least-squares problem: . We set because preliminary unconstrained estimates show that 93 of the 100 users have parameter norms below 2. Both arm and conversational feedback are generated using . For each user, we run rounds and compute cumulative regret.
Results. We repeat this experiment 10 times, and Figure 5a shows the mean cumulative regret. HyConUCB achieves the lowest cumulative regret on the Yelp dataset. ConDuel performs second best, followed by Var-AM and Var-Random, whereas OFUGLB-UCB has the highest cumulative regret.
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.
Experiments on LLM Routing
In large language model (LLM) routing systems, a router selects an LLM from the candidate pool to answer a query. We formulate LLM routing as a conversational bandit problem, treating candidate LLMs as arms and task categories as key-terms.
Dataset. We conduct our experiments on the xRouteBench dataset [17], using its llmrouter_generic configuration. This configuration contains 13 tasks and 18 candidate LLMs. For each question, the dataset records the performance score of every candidate LLM. We divide the data into a 60% training split, a 20% validation split, and a 20% test split. The validation split is used for preliminary evaluation and hyperparameter selection. We select 4 tasks and 4 models. Hence, . Our choice of is consistent with the small model pools used in prior LLM routing studies, including RouteLLM with two models [18], MetaLLM with four models [19], and greedy LinUCB with six models [20]. For each selected task, we designate the model with the highest accuracy on that task as its expert. The selected tasks and their expert models are ARC-Challenge (Qwen3-Coder-Next), GSM8K (Llama-4-Maverick), MATH (Mistral-Small-3-24B-Instruct), and MMLU (Llama-3.3-70B-Instruct-Turbo).
Feature and Feedback Construction. We construct the feature vectors as follows. First, we use BAAI/bge-small-en-v1.5 to obtain a query embedding. We then train a classifier using data from the training split. The classifier takes a query embedding as input and outputs a probability vector , whose components represent the predicted probabilities for the four task categories. We append a constant coordinate of 1 to to obtain . For each model , we define . Finally, we normalize this vector and append a global intercept, yielding . Hence, .
For arm feedback, we use the logged outcomes in the dataset. We associate each task with its designated expert model. Thus the weight matrix . Because the dataset does not contain conversational feedback records, we generate this feedback synthetically. We first estimate the user parameter via maximum likelihood using the training split. It should be noted that is used exclusively to generate conversational feedback, while arm-side rewards are taken directly from the dataset’s logged model outcomes. Because the resulting estimate has norm , we set . During the online experiment, we generate conversational feedback according to Eq. (2). We run each experiment for rounds on the test split and set the conversation-frequency function .
Metrics. Let denote the query at round , and let indicate whether model answers it correctly. Define the cumulative oracle regret
However, it can grow linearly even when the task expert is always selected, because another model may answer a query correctly when the task expert answers it incorrectly. So we take the cumulative expert regret as our primary metric. Let be the expert model on query . Define
This metric measures the gap between the selected model and the task expert.
Results. We repeat the experiment over 200 random seeds and report the mean cumulative oracle and expert regret in Figure 5b and Figure 5c, respectively. HyConUCB and its variants outperform other baselines in terms of final mean cumulative regret, with Var-Random ranking first, followed closely by HyConUCB and then Var-AM. ConDuel incurs the highest regret, slightly higher than that of OFUGLB-UCB.
Concluding Remarks
In this paper, we formulate the conversational generalized linear bandits with hybrid feedback problem. We develop time-uniform confidence sequences for heterogeneous arm and key-term feedback and propose the HyConUCB algorithm. Our theoretical analysis shows that HyConUCB can achieve a tighter regret bound than the reward-only benchmark and prior conversational generalized linear bandit methods. Experiments on synthetic and real-world datasets further demonstrate its effectiveness.
Several directions remain open. From the hybrid feedback perspective, we consider a setting in which arm interactions and key-term queries use different feedback types. A natural extension is a fully hybrid setting, in which both channels support absolute and relative feedback and the learner can adaptively select the feedback type.
From the conversation perspective, we assume that conversations incur no cost and schedule them according to a fixed frequency function. In practice, however, conversations may incur costs. Developing algorithms that account for these costs and adaptively decide when to conduct conversations is therefore a promising direction for future work.
Auxiliary Results
Ellipsoidal Confidence Sequence
Proof of Lemma 4.2. Since is convex and minimizes over , we have for ,
Every observation feature in satisfies , and hence . By Lemma D.1 in Lee et al. [4], we have
By Taylor’s formula and the first-order optimality condition, we obtain
Adding the regularization term and using therefore gives
Thus , which completes the proof. □
Guarantees for the Query Selection Rule
Suppress the query indices and write and . Let solve Eq. (5). For and , we have . Optimality of therefore gives
Dividing by and letting yields
Thus, the expected MaxInp score under is at least .
Next, take and set . Since and is concave, optimality gives
Again dividing by and letting gives
Equations (15) and Eq. (16) formalize the balance in the query rule: the first preserves the MaxInp score, while the second guarantees coverage of the query subspace. Next, we prove Lemma 4.3.
Let , and let be the history immediately before the current query, including earlier queries in the same round. Then
Thus each query satisfies the information bound with
Summing over the queries proves Lemma 4.3.
Statistical Guarantees
Lemma A.1. For and any ,
Proof. For , self-concordance gives
Taylor’s formula therefore gives
The last step uses .
Lemma A.2. Let
For every ,
Consequently, with probability at least ,
Proof. Set and restrict matrices to , an -dimensional space. The round increments satisfy
by , , and Lemma 4.3. Hence the conditional expectations sum is at least . Then by adapted matrix Chernoff inequality [21 Theorem 3.1], with relative deviation and the bounds above, we have
Here all query directions lie in , so the restriction controls exactly the claimed lower bound. Under the stated threshold, the right-hand side is at most . A union bound on proves the simultaneous conclusion.
Let be the intersection of the simultaneous events in Lemmas 4.1 and A.2, so that .
Lemma A.3. On , for every ,
Proof. Fix and on . Monotonicity of gives , so the bound in Lemma A.2 applies. Since and their midpoint lies in , optimality of gives
The linear terms in the losses cancel. The remaining terms are nonnegative by convexity of and . Keeping the query terms gives
Every query satisfies , where . By Lemmas A.1 and A.2,
The definition of gives
Combining these bounds, and using , yields
The function is increasing for , so . For every with ,
The Regret Analysis
Proof of Theorem 5.1. Work on , which is defined in Section A.3. Following Lee et al. [4, Appendix E], choose
Let , and define
Lemma B.2 and give
By the confidence ellipsoid and UCB selection, . Thus Lemma 5.2 gives, for ,
On , we have
Integrating Lemma B.1 over this gap yields
For , choose with . Both and belong to this confidence set, so . Since , Lemma 5.2 implies
Using and Lemma B.1, we obtain
Also, self-concordance gives, for ,
Consequently,
Combining these bounds and applying Cauchy–Schwarz gives
The last step uses Theorem 5.3 with and for ; indeed, on ,
Applying yields
Combining this with Eq. (19) proves Eq. (8). □
Proof of Lemma 5.2. For , the definition of and give . For , Lemma A.3 gives . So, by Lemma B.1,
Hence, by Lemma A.2,
Proof of Theorem 5.3. We prove the general situation for arbitrary and . Set and . By the determinant lemma and telescoping, we can get
Let have orthonormal columns spanning , respectively. Define and . Schur complements give
When , we have and . For the ease of telescoping later, we set . Then
Let for , and for . By , we have
Since , the determinant lemma gives
The second inequality holds by the convexity of on . Finally, implies
Taking proves the stated case. □
Lemma B.1. For and all ,
The same inequalities hold for .
Proof. Self-concordance gives . Integrating between and exponentiating proves the claim. □
Lemma B.2. On ,
Proof. Define
Since , every round counted in the lemma satisfies
Theorem 5.3, with , gives
Since , applying for proves the bound.
Additional Discussions
Potential Bound under Linear Query Schedules
Suppose with and . Write
Replacing by increases each denominator in by less than , so each new denominator is at most times its original value. Using for and , we obtain
By concavity of the logarithm,
Telescoping the sum yields
which completes the proof.
A Good Case
We give a concrete setting in which pairwise conversational feedback is much more informative than absolute arm reward. Consider the logistic special case , with and . Let
where , , and . Therefore,
For , all arm utilities are nonnegative. Since the logistic curvature decreases on , we have
Thus, the information in an absolute arm response can decay exponentially with the common intercept .
The definition of key-term vectors gives
Suppose the relative key-term vectors include , where are the standard basis vectors of . In a pairwise comparison, the common intercept cancels out:
Consequently,
and this lower bound is independent of .
For fixed and a large , we have , where is defined in Appendix § 9.§ 2. Uniformly sampling the corresponding opposite pairs gives , so , where is defined in Appendix § 9.§ 2. Thus, for fixed , Eq. (17) yields
References
- [1]Xiaoying Zhang, Hong Xie, Hang Li, and John C.S. Lui. Conversational contextual bandit: Algorithm and application. In Proceedings of The Web Conference 2020, WWW ’20, page 662–672, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370233. doi: 10.1145/3366423.3380148. URL https://doi.org/10.1145/3366423.3380148.
- [2]Shuhua Yang, Hui Yuan, Xiaoying Zhang, Mengdi Wang, Hong Zhang, and Huazheng Wang. Conversational dueling bandits in generalized linear models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 3806–3817, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704901. doi: 10.1145/3637528.3671892.DOI
- [3]Zhihui Xie, Tong Yu, Canzhe Zhao, and Shuai Li. Comparison-based conversational recommender system with relative bandit feedback. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’21, page 1400–1409, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380379. doi: 10.1145/3404835.3462920.DOI
- [4]Junghyun Lee, Se-Young Yun, and Kwang-Sung Jun. A unified confidence sequence for generalized linear models, with applications to bandits. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9798331314385.arxiv.org/abs/2407.13977
- [5]Zhiyong Wang, Xutong Liu, Shuai Li, and John C.S. Lui. Efficient explorative key-term selection strategies for conversational contextual bandits. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence, AAAI ’23/IAAI ’23/EAAI ’23. AAAI Press, 2023. ISBN 978-1-57735-880-0. doi: 10.1609/aaai.v37i8.26225.DOI
- [6]Maoli Liu, Zhuohua Li, Xiangxiang Dai, and John C.S. Lui. Leveraging the power of conversations: Optimal key term selection in conversational contextual bandits. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, KDD ’25, page 1833–1844, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400714542. doi: 10.1145/3711896.3737025.DOI
- [7]Peter McCullagh and John A. Nelder. Generalized Linear Models. Chapman & Hall/CRC Monographs on Statistics and Applied Probability. Routledge, New York, NY, 2 edition, 2019. ISBN 978-1-351-44584-9. doi: 10.1201/9780203753736. URL https://doi.org/10.1201/9780203753736.
- [8]Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: the generalized linear case. In Proceedings of the 24th International Conference on Neural Information Processing Systems - Volume 1, NIPS ’10, page 586–594, Red Hook, NY, USA, 2010. Curran Associates Inc.
- [9]Yoan Russac, Louis Faury, Olivier Cappé, and Aurélien Garivier. Self-concordant analysis of generalized linear bandits with forgetting. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 658–666. PMLR, 13–15 Apr 2021.
- [10]Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML ’11, page 241–248, Madison, WI, USA, 2011. Omnipress. ISBN 9781450306195.
- [11]Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538–1556, 2012.
- [12]Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue. Advancements in dueling bandits. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI’18, page 5502–5510. AAAI Press, 2018. ISBN 9780999241127.DOI
- [13]Xuchuang Wang, Qirun Zeng, Jinhang Zuo, Xutong Liu, Mohammad Hajiesmaili, John C.S. Lui, and Adam Wierman. Fusing reward and dueling feedback in stochastic bandits. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 65346–65367. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/v267/wang25eh.html.arxiv.org/abs/2504.15812
- [14]Qijia He, Minghan Wang, Xutong Liu, Zhiyong Wang, and Fang Kong. Learning across the gap: Hybrid multi-armed bandits with heterogeneous offline and online data. Advances in Neural Information Processing Systems, 38:20138–20182, 2026.DOI
- [15]Qirun Zeng, Xuchuang Wang, Jiayi Shen, Xutong Liu, Fang Kong, and Jinhang Zuo. Best arm identification in generalized linear bandits via hybrid feedback, 2026.
- [16]Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050–30062, 2021.
- [17]Tao Feng, Fangxu Yu, Haozhen Zhang, Zhongjie Dai, Lianqgi Yuan, Zijie Lei, Weizhi Zhang, Kunlun Zhu, Haodong Yue, Keyang Xuan, Ge Liu, and Jiaxuan You. Llmrouter: Unified infrastructure for developing, evaluating, and deploying llm routers, 2026. URL https://arxiv.org/abs/2608.06867.
- [18]Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, M Kадous, and Ion Stoica. Routellm: Learning to route llms from preference data. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu, editors, International Conference on Learning Representations, volume 2025, pages 34433–34448, 2025. URL https://proceedings.iclr.cc/paper_files/paper/2025/file/5503a7c69d48a2f86fc00b3dc09de686-Paper-Conference.pdf.arxiv.org/abs/2406.18665
- [19]Quang H. Nguyen, Thinh Dao, Duy C. Hoang, Juliette Decugis, Saurav Manchanda, Nitesh V. Chawla, and Khoa D. Doan. Metallm: A high-performant and cost-efficient dynamic framework for wrapping llms, 2025.arxiv.org/abs/2407.10834
- [20]Manhin Poon, Xiangxiang Dai, Xutong Liu, Fang Kong, John C.S. Lui, and Jinhang Zuo. Online multi-llm selection via contextual bandits under unstructured context evolution. In Proceedings of the Fortieth AAAI Conference on Artificial Intelligence and Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence and Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI’26/IAAI’26/EAAI’26. AAAI Press, 2026. ISBN 978-1-57735-906-7. doi: 10.1609/aaai.v40i29.39672. URL https://doi.org/10.1609/aaai.v40i29.39672.
- [21]Joel A. Tropp. User-friendly Tail Bounds for Matrix Martingales, January 2011.DOI