betaFeedback

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 TT rounds with b(t)=⌊ρt⌋b(t)=\lfloor\rho t\rfloor cumulative conversational queries, where ρ\rho controls the query frequency. We report the case r=dr=d, where dd is the feature dimension and rr is the dimension spanned by conversational queries (see Eq. (10) for general rr). Here, κ−1\kappa^{-1} and κ⋆−1\kappa_{\star}^{-1} denote the worst-case and average optimal-arm curvatures, respectively; vˉ\bar{v} is the maximum reward curvature; and η=σρd/4\eta=\sigma\rho d/4 measures conversational information. The ConDuel bound is obtained by adapting its analysis to our setting. O~\widetilde{O} 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].

Image not extracted

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.

AlgorithmLeading termLower-order term
Reward-only [4]O~(dT/κ⋆)\widetilde{O}\left(d\sqrt{T/\kappa_{\star}}\right)O~(κd2)\widetilde{O}(\kappa d^{2})
ConDuel (adapted) [2]O~(κdT/κ⋆)\widetilde{O}\left(\kappa d\sqrt{T/\kappa_{\star}}\right)O~(κ2d2)\widetilde{O}(\kappa^{2}d^{2})
HyConUCB (ours)O~(dT/κ⋆1+ηvˉ−1)\widetilde{O}\left(d\sqrt{\frac{T/\kappa_{\star}}{1+\eta\bar{v}^{-1}}}\right)O~(d2/(κ−1+η))\widetilde{O}\left(d^{2}/(\kappa^{-1}+\eta)\right)

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 xTθ∗\mathbf{x}^{\mathsf{T}}\theta^{*} and mean μ(xTθ∗)\mu(\mathbf{x}^{\mathsf{T}}\theta^{*}), where θ∗\theta^{*} 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 θ∗\theta^{*} 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 yy, given a natural parameter u∈Ru \in\mathbb{R}, belongs to an exponential family and is specified by

p(y∣u)=exp⁡{yu−m(u)a+c(y)}.p(y \mid u) = \exp\left\{\frac{yu-m(u)}{a}+c(y)\right\}.

Here mm is the log-partition function, aa is the known dispersion factor and cc is the log base measure. We use p(y∣u)p(y \mid u) to denote the conditional probability density or mass function of yy given uu. A fundamental property of GLMs is that the conditional mean of yy is given by

E[y∣u]=m′(u)=:μ(u),\mathbb{E}[y \mid u] = m'(u) =: \mu(u),

where μ(⋅)\mu(\cdot) is the mean function (inverse link function). For convenience, we define ν(u):=μ˙(u)a\nu(u) := \frac{\dot{\mu}(u)}{a}.

Conversational Generalized Linear Bandits with Hybrid Feedback

We consider a sequential decision-making problem where the learner interacts with a user over TT rounds. Let A\mathcal{A} denote a set of KK arms and K\mathcal{K} denote a set of PP key-terms. The relationship between the arms and the key-terms can be characterized by a weighted bipartite graph (A,K,W)(\mathcal{A},\mathcal{K},\mathcal{W}), whose nodes are divided into two sets A\mathcal{A} and K\mathcal{K}, and weighted edges are represented by the matrix W:=[Wa,k]K×PW := [W_{a,k}]_{K \times P} with Wa,kW_{a,k} representing the relationship between arm aa and key-term kk.

At round tt, the learner observes a candidate set At⊆A\mathcal{A}_t \subseteq\mathcal{A}. It then selects an arm at∈Ata_t \in\mathcal{A}_t and receives an absolute reward rtr_t from the user. Each arm is associated with a dd-dimensional feature vector xax_a. The corresponding feature vector pool at round tt is Xt\mathcal{X}_t. We write xt=xatx_t = x_{a_t} for the feature vector of the selected arm. Let ∥xa∥2≤1\lVert x_a \rVert_2 \le1 for every arm feature. The user’s preference is represented by a vector θ⋆∈Θ\theta^\star\in\Theta, where Θ:={θ∈Rd:∥θ∥2≤S}\Theta:= \{\theta\in\mathbb{R}^d : \lVert\theta\rVert_2 \le S\}. Then the reward is defined as

rt∼pc(⋅∣xt⊤θ⋆).(1)r_t \sim p_c(\cdot\mid x_t^\top\theta^\star). \tag*{(1)}

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

x~k:=∑a∈AWa,kxa∑a∈AWa,k.\widetilde{x}_k := \frac{\sum_{a \in\mathcal{A}} W_{a,k}x_a}{\sum_{a \in\mathcal{A}} W_{a,k}}.

A nondecreasing integer-valued function b(t)b(t), with b(0)=0b(0) = 0, is defined to model the frequency of conversations. Before selecting an arm, the learner conducts qt=b(t)−b(t−1)q_t = b(t) - b(t-1) conversations. For each i∈{1,2,…,qt}i \in\{1,2,\ldots,q_t\}, the learner selects a key-term pair (kt,i,kt,i′)∈K2(k_{t,i}, k'_{t,i}) \in\mathcal{K}^2. Define its comparison feature vector as

d~t,i:=x~kt,i−x~kt,i′.\widetilde{d}_{t,i} := \widetilde{x}_{k_{t,i}}-\widetilde{x}_{k'_{t,i}}.

Thus ∥d~t,i∥2≤2\lVert\widetilde{d}_{t,i} \rVert_2 \le2, and the learner observes the dueling feedback o~t,i∈{0,1}\widetilde{o}_{t,i} \in\{0,1\} with distribution

o~t,i∼pd(⋅∣d~t,iTθ⋆).(2)\widetilde{o}_{t,i} \sim p_d\left(\cdot\mid\widetilde{d}_{t,i}^{\mathsf{T}}\theta^\star\right). \tag*{(2)}

where o~t,i=1\widetilde{o}_{t,i}=1 indicates preference for kt,ik_{t,i}.

Both arm reward and conversational dueling feedback are modeled as GLMs with a shared parameter θ⋆\theta^\star, but possibly different mean functions μc\mu_c and μd\mu_d. We use subscripts cc and dd 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 Q:={qe}e=1NQ\mathcal{Q}:=\{q_e\}_{e=1}^{N_Q} contain all pairwise differences x~k−x~k′\tilde{x}_k-\tilde{x}_{k'} from the key-term pool, and let U:=span⁡(Q)\mathcal{U}:=\operatorname{span}(\mathcal{Q}) and r=dim⁡(U)r=\dim(\mathcal{U}). Unlike prior works that assume full-dimensional conversational coverage (r=dr=d) [2, 5], our algorithm also applies when conversations cover only a subspace (r<dr<d).

Under the conversational GLBs with hybrid feedback problem described above, our objective is to minimize the cumulative regret in TT rounds. Let xt,⋆=arg⁡max⁡x∈Xtx⊤θ⋆x_{t,\star}=\arg\max_{x\in\mathcal{X}_t}x^\top\theta^\star. Following the definition in Filippi et al. [8], we define the regret as

R(T)=∑t=1T{μc(xt,⋆⊤θ⋆)−μc(xt⊤θ⋆)}.R(T)=\sum_{t=1}^{T}\{\mu_c(x_{t,\star}^\top\theta^\star)-\mu_c(x_t^\top\theta^\star)\}.

Following Lee et al. [4], Zeng et al. [15], we assume that the log-partition functions mc,mdm_c,m_d are three times continuously differentiable, with μ˙c,μ˙d>0\dot{\mu}_c,\dot{\mu}_d>0. For modality j∈{c,d}j\in\{c,d\}, we use a self-concordance bound RsR_s and curvature bound Rμ˙R_{\dot{\mu}}:

∣μ¨j(u)∣≤Rsμ˙j(u),Rμ˙=max⁡j∈{c,d}sup⁡uμ˙j(u).|\ddot{\mu}_j(u)|\le R_s\dot{\mu}_j(u),\qquad R_{\dot{\mu}}=\max_{j\in\{c,d\}}\sup_u\dot{\mu}_j(u).

Hybrid Conversational UCB Algorithm

Confidence Sequences

We construct confidence sequences for the unknown user preference vector θ⋆\theta^\star. 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 tt as

Lt(θ)=∑s<t−rsxs⊤θ+mc(xs⊤θ)ac+∑s≤t∑i=1qs−o~s,id~s,i⊤θ+md(d~s,i⊤θ)ad.(3)\mathcal{L}_t(\theta)=\sum_{s<t}\frac{-r_sx_s^\top\theta+m_c(x_s^\top\theta)}{a_c} +\sum_{s\le t}\sum_{i=1}^{q_s}\frac{-\tilde{o}_{s,i}\tilde{d}_{s,i}^\top\theta+m_d(\tilde{d}_{s,i}^\top\theta)}{a_d}. \tag*{(3)}

Following Lee et al. [4], we define θ^t∈arg⁡min⁡θ∈ΘLt(θ)\hat{\theta}_t\in\arg\min_{\theta\in\Theta}\mathcal{L}_t(\theta) and

Ct:={θ∈Θ:Lt(θ)−Lt(θ^t)≤βt2},\mathcal{C}_t:=\{\theta\in\Theta:\mathcal{L}_t(\theta)-\mathcal{L}_t(\hat{\theta}_t)\le\beta_t^2\},

where

βt2:=log⁡2δ+inf⁡c∈(0,1]{dlog⁡1c+2SLtc}≤log⁡2δ+dlog⁡(e∨2eSLtd).\begin{aligned} \beta_t^2:=\log\frac{2}{\delta}+\inf_{c\in(0,1]}\left\{d\log\frac{1}{c}+2SL_tc\right\} \\ &\le\log\frac{2}{\delta}+d\log\left(e\vee\frac{2eSL_t}{d}\right). \end{aligned}

and LtL_t is the Lipschitz constant of Lt\mathcal{L}_t on Θ\Theta.

Lemma 4.1. With probability at least 1−δ21-\frac{\delta}{2}, we have θ⋆∈Ct\theta^\star\in\mathcal{C}_t for all t≤Tt\le T.

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 tt, there are Nt=t−1+b(t)N_t=t-1+b(t) observations. Write the resulting sequence as (jn,zn,yn)n=1Nt(j_n,z_n,y_n)_{n=1}^{N_t}, where jn∈{c,d}j_n\in\{c,d\} denotes the modality and (zn,yn)(z_n,y_n) denotes (xs,rs)(x_s,r_s) for an arm reward or (d~s,i,o~s,i)(\tilde{d}_{s,i},\tilde{o}_{s,i}) for a key-term comparison. Eventually, we have

Lt(θ)=∑n=1Nt−ynzn⊤θ+mjn(zn⊤θ)ajn.\mathcal{L}_t(\theta)=\sum_{n=1}^{N_t}\frac{-y_nz_n^\top\theta+m_{j_n}(z_n^\top\theta)}{a_{j_n}}.

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 (A,K,W)(\mathcal{A},\mathcal{K},\mathcal{W}), conversational frequency function b(t)b(t), parameter norm bound SS

  1. Construct the query pool Q\mathcal{Q}.

  2. for t=1,…,Tt=1,\ldots,T do

  3. &nbsp;&nbsp;Set qt←b(t)−b(t−1)q_t \gets b(t)-b(t-1).

  4. &nbsp;&nbsp;for i=1,…,qti=1,\ldots,q_t do

  5. &nbsp;&nbsp;&nbsp;&nbsp;Solve query distribution pt,i\mathbf{p}_{t,i} according to Eq. (5).

  6. &nbsp;&nbsp;&nbsp;&nbsp;Sample (kt,i,kt,i′)(k_{t,i},k'_{t,i}) according to pt,i\mathbf{p}_{t,i}.

  7. &nbsp;&nbsp;&nbsp;&nbsp;Query (kt,i,kt,i′)(k_{t,i},k'_{t,i}) and observe o~t,i\widetilde{o}_{t,i}, and set Ft−1←Ft−1∪(kt,i,kt,i′,o~t,i)\mathcal{F}_{t-1}\gets\mathcal{F}_{t-1}\cup(k_{t,i},k'_{t,i},\widetilde{o}_{t,i}).

  8. &nbsp;&nbsp;end for

  9. &nbsp;&nbsp;Compute θ^t∈arg⁡min⁡θ∈ΘLt(θ)\hat{\theta}_t\in\arg\min_{\theta\in\Theta}\mathcal{L}_t(\theta).

  10. &nbsp;&nbsp;Select at∈arg⁡max⁡a∈At{xa⊤θ^t+γt∥xa∥Ht−1}a_t\in\arg\max_{a\in\mathcal{A}_t}\left\{\mathbf{x}_a^\top\hat{\theta}_t+\gamma_t\lVert\mathbf{x}_a\rVert_{\mathbf{H}_t^{-1}}\right\}.

  11. &nbsp;&nbsp;Observe rtr_t and set Ft←Ft−1∪(at,rt)\mathcal{F}_t\gets\mathcal{F}_{t-1}\cup(a_t,r_t).

  12. end for

Let λ>0\lambda>0. The regularized joint Hessian at θ^t\hat{\theta}_t is

Ht=λId+∇2Lt(θ^t)=λId+∑s<tνc(xs⊤θ^t)xsxs⊤+∑s≤t∑i=1qsνd(d~s,i⊤θ^t)d~s,id~s,i⊤.(4)\begin{aligned} \mathbf{H}_t=\lambda\mathbf{I}_d+\nabla^2\mathcal{L}_t(\hat{\theta}_t) \\ &=\lambda\mathbf{I}_d+\sum_{s<t}\nu_c(\mathbf{x}_s^\top\hat{\theta}_t)\mathbf{x}_s\mathbf{x}_s^\top+\sum_{s\le t}\sum_{i=1}^{q_s}\nu_d(\widetilde{\mathbf{d}}_{s,i}^\top\hat{\theta}_t)\widetilde{\mathbf{d}}_{s,i}\widetilde{\mathbf{d}}_{s,i}^\top. \tag*{(4)} \end{aligned}

Following the ellipsoidal construction of Lee et al. [4 Theorem 3.2], let γt2:=2(1+2SRs)(4λS2+βt2)\gamma_t^2:=2(1+2SR_s)(4\lambda S^2+\beta_t^2), we define

Et:={θ∈Rd:∥θ−θ^t∥Ht≤γt}.\mathcal{E}_t:=\{\theta\in\mathbb{R}^d:\lVert\theta-\hat{\theta}_t\rVert_{\mathbf{H}_t}\le\gamma_t\}.

Lemma 4.2. For every t≤Tt\le T, Ct⊆Et\mathcal{C}_t\subseteq\mathcal{E}_t. Consequently, with probability at least 1−δ21-\frac{\delta}{2}, θ⋆∈Et\theta^\star\in\mathcal{E}_t, for all t≤Tt\le T.

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 tt, the learner first conducts qt=b(t)−b(t−1)q_t=b(t)-b(t-1) 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., (kt,i,kt,i′)∈arg⁡max⁡k,k′∈K∥x~k−x~k′∥Mt,i−1(k_{t,i},k'_{t,i})\in\arg\max_{k,k'\in\mathcal{K}}\lVert\widetilde{\mathbf{x}}_k-\widetilde{\mathbf{x}}_{k'}\rVert_{\mathbf{M}_{t,i}^{-1}}, where Mt,i\mathbf{M}_{t,i} is the joint Hessian immediately before query ii in round tt.

For each query qe∈Q\mathbf{q}_e\in\mathcal{Q}, calculate

at,i,e=∥qe∥Mt,i−12andst,i,e=at,i,emax⁡fat,i,f∈[0,1],a_{t,i,e}=\lVert\mathbf{q}_e\rVert_{\mathbf{M}_{t,i}^{-1}}^2 \qquad\text{and}\qquad s_{t,i,e}=\frac{a_{t,i,e}}{\max_f a_{t,i,f}}\in[0,1],

where at,i,ea_{t,i,e} is the MaxInp score of qe\mathbf{q}_e.

Next we consider directional coverage. For a query distribution p\mathbf{p} on Q\mathcal{Q}, the matrix V(p)=∑epeqeqe⊤\mathbf{V}(\mathbf{p})=\sum_e p_e\mathbf{q}_e\mathbf{q}_e^\top 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 UU, we use the minimum eigenvalue of this matrix restricted to UU. Define

j(p)=λmin⁡,U(V(p)),j(\mathbf{p})=\lambda_{\min,U}(V(\mathbf{p})),

where λmin⁡,U\lambda_{\min,U} denotes the minimum eigenvalue restricted to UU.

Finally, we solve

pt,i∈arg⁡max⁡p∈ΔNq{∑epest,i,e+ξlog⁡j(p)},0<ξ<1.(5)\mathbf{p}_{t,i}\in\arg\max_{\mathbf{p}\in\Delta_{N_q}}\left\{\sum_e p_e s_{t,i,e}+\xi\log j(\mathbf{p})\right\},\qquad0<\xi<1. \tag*{(5)}

According to pt,i\mathbf{p}_{t,i}, we sample d~t,i\tilde{\mathbf{d}}_{t,i} from Q\mathcal{Q}.

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 ξ\xi 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 θ^t\hat{\boldsymbol{\theta}}_t using all feedback observed so far. Based on Lemma 4.2, we define the UCB score of each arm a∈Ata\in\mathcal{A}_t as

ut,a:=xa⊤θ^t+γt∥xa∥Ht−1.u_{t,a}:=\mathbf{x}_a^\top\hat{\boldsymbol{\theta}}_t+\gamma_t\lVert\mathbf{x}_a\rVert_{\mathbf{H}_t^{-1}}.

The learner then selects an arm that maximizes the UCB score, i.e.,

at∈arg⁡max⁡a∈Atut,a,a_t\in\arg\max_{a\in\mathcal{A}_t}u_{t,a},

breaking ties arbitrarily. Finally, the learner observes the arm reward rtr_t, which is incorporated into the parameter estimation in subsequent rounds.

Lemma 4.3. Let Ft:=σ((as,rs),{(ks,i,ks,i′,os,i)}i=1qs:1≤s≤t)\mathcal{F}_t:=\sigma\left((a_s,r_s),\{(k_{s,i},k'_{s,i},o_{s,i})\}_{i=1}^{q_s}:1\le s\le t\right) denote the σ\sigma-algebra generated by the history through the end of round tt. Under the query rule in Eq. (5), there exists a constant σ>0\sigma>0 such that, almost surely, for every t∈[T]t\in[T],

E[∑i=1qtνd(d~t,i⊤θ∗)d~t,id~t,i⊤∣Ft−1]⪰σqtPU,(6)\mathbb{E}\left[\left.\sum_{i=1}^{q_t}\nu_d(\tilde{\mathbf{d}}_{t,i}^{\top}\boldsymbol{\theta}^*)\tilde{\mathbf{d}}_{t,i}\tilde{\mathbf{d}}_{t,i}^{\top}\right|\mathcal{F}_{t-1}\right]\succeq\sigma q_tP_U, \tag*{(6)}

where PUP_U is the orthogonal projection matrix onto UU.

Regret Analysis

In this section, we establish a regret bound for HyConUCB. We use the notations

κ=max⁡t≤T, x∈Xt, θ∈Θ1μ˙c(x⊤θ),κ∗=T/∑t=1Tμ˙c(xt,∗⊤θ∗),\kappa=\max_{t\le T,\,\mathbf{x}\in\mathcal{X}_t,\,\boldsymbol{\theta}\in\Theta}\frac{1}{\dot{\mu}_c(\mathbf{x}^{\top}\boldsymbol{\theta})},\qquad \kappa_* = T\bigg/\sum_{t=1}^{T}\dot{\mu}_c(\mathbf{x}_{t,*}^{\top}\boldsymbol{\theta}^*),
νˉ=max⁡t≤T, x∈Xtμ˙c(x⊤θ∗),Rμ,∗=sup⁡t≤T, x∈Xt∣μc(x⊤θ∗)∣.\bar{\nu}=\max_{t\le T,\,\mathbf{x}\in\mathcal{X}_t}\dot{\mu}_c(\mathbf{x}^{\top}\boldsymbol{\theta}^*),\qquad R_{\mu,*}=\sup_{t\le T,\,\mathbf{x}\in\mathcal{X}_t}\left|\mu_c(\mathbf{x}^{\top}\boldsymbol{\theta}^*)\right|.

For the analysis, set γˉT=max⁡t≤Tγt\bar{\gamma}_T=\max_{t\le T}\gamma_t, qmax⁡=max⁡{1,q1,…,qT}q_{\max}=\max\{1,q_1,\ldots,q_T\} and GT=max⁡{RsγˉT,Rμ˙/ac}G_T=\max\left\{R_s\bar{\gamma}_T,\sqrt{R_{\dot{\mu}}/a_c}\right\}.

For ε>0\varepsilon>0, define

n0≜4σmax⁡{8qmax⁡Rμadlog⁡2rTδ, 16(1+max⁡s≤Tβs2)(1ε+Rs2)2},n_0\triangleq\frac{4}{\sigma}\max\left\{8q_{\max}\frac{R_{\mu}}{a_d}\log\frac{2rT}{\delta},\ 16\left(1+\max_{s\le T}\beta_s^2\right)\left(\frac{1}{\varepsilon}+\frac{R_s}{2}\right)^2\right\},
t0≜∣{t≤T:b(t)<n0}∣.t_0\triangleq\left|\{t\le T:b(t)<n_0\}\right|.

Let

DT(h):=(d−r)log⁡(1+Th2λ(d−r))+r∑t=1Tlog⁡(1+h2λr+(t−1)h+e−Rsεσrb(t)/2).(7)D_T(h):=(d-r)\log\left(1+\frac{Th}{2\lambda(d-r)}\right) +r\sum_{t=1}^{T}\log\left(1+\frac{h}{2\lambda r+(t-1)h+e^{-R_s\varepsilon\sigma r b(t)/2}}\right). \tag*{(7)}

We now establish the theoretical guarantees of Algorithm 1.

Theorem 5.1. With probability at least 1−δ1-\delta, Algorithm 1 satisfies

R(T)≤2Rμ,⋆t0+8e3/2acγˉTDT(vˉ/ac)Tκ⋆+16e3acRsγˉTDT(vˉ/ac)+32Rμ,⋆acκGT2log⁡2DT(1/(acκ)).(8)R(T) \le2R_{\mu,\star}t_0 + 8e^{3/2}\sqrt{a_c}\bar{\gamma}_T\sqrt{\frac{D_T(\bar{v}/a_c)T}{\kappa_\star}} + 16e^3a_cR_s\bar{\gamma}_TD_T(\bar{v}/a_c) + \frac{32R_{\mu,\star}a_c\kappa G_T^2}{\log2}D_T(1/(a_c\kappa)). \tag*{(8)}

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 νc(xsTθ^t)\nu_c(x_s^\mathsf{T}\hat{\theta}_t). The analysis of ConDuel [2] handles this dependence by scaling based on the global worst-case curvature, which introduces a factor κ\kappa 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 κ\kappa. The second challenge is to retain the information from both arm rewards and key-term comparisons when bounding the elliptical potential sum

∑t=1T∥xt∥Ht−12.(9)\sum_{t=1}^{T}\lVert x_t\rVert_{H_t^{-1}}^2. \tag*{(9)}

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 HtH_t. Let θˉs\bar{\theta}_s minimize μ˙c(xsTθ)\dot{\mu}_c(x_s^\mathsf{T}\theta) over ⋃ℓ=sTCℓ\bigcup_{\ell=s}^{T}\mathcal{C}_\ell, as in Eq. (18), and define

Vt≜2λId+∑s<tνc(xsTθˉs)xsxsT+e−Rsεδb(t)2PU.V_t \triangleq2\lambda I_d+\sum_{s<t}\nu_c(x_s^\mathsf{T}\bar{\theta}_s)x_sx_s^\mathsf{T}+\frac{e^{-R_s\varepsilon}\delta b(t)}{2}P_U.

Lemma 5.2. With probability at least 1−δ1-\delta, for every t0<t≤Tt_0<t\le T, we have

Ht⪰12Vt.H_t \succeq\frac{1}{2}V_t.

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 h>0h>0 and θˉ1,…,θˉT∈Θ\bar{\theta}_1,\ldots,\bar{\theta}_T\in\Theta satisfy νc(xtTθˉt)≤h\nu_c(x_t^\mathsf{T}\bar{\theta}_t)\le h. Then

∑t=1Tlog⁡(1+νc(xtTθˉt)∥xt∥Vt−12)≤DT(h),\sum_{t=1}^{T}\log\left(1+\nu_c(x_t^\mathsf{T}\bar{\theta}_t)\lVert x_t\rVert_{V_t^{-1}}^2\right)\le D_T(h),

where DT(h)D_T(h) is defined in Eq. (7). The same bound holds for arbitrary coefficients wt∈[0,h]w_t\in[0,h] in place of νc(xtTθˉt)\nu_c(x_t^\mathsf{T}\bar{\theta}_t), with the same replacements in VtV_t.

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. □\square

Regret order. Now we give the regret order of HyConUCB. Consider b(t)=⌈ρt⌉b(t)=\lceil\rho t\rceil with ρ>0\rho>0, and define η≜σρr/4\eta\triangleq\sigma\rho r/4. Let O~\widetilde{O} hide logarithmic factors and constants depending on SS, λ\lambda, ε\varepsilon, and the GLM coefficients. In this case, our regret bound is

R(T)=O~(d(d−r)Tκ∗+κd(d−r)⏟U⊥+drTκ∗(1+η/vˉ)+drκ−1+η⏟U).(10)R(T)=\widetilde{O}\left(\underbrace{\sqrt{\frac{d(d-r)T}{\kappa_*}}+\kappa d(d-r)}_{U^\perp}+\underbrace{\sqrt{\frac{drT}{\kappa_*(1+\eta/\bar{v})}}+\frac{dr}{\kappa^{-1}+\eta}}_{U}\right). \tag*{(10)}

The two groups represent the contributions from subspace U⊥U^\perp and UU, respectively. Conversations improve the contribution from UU, while the contribution from U⊥U^\perp retains its reward-only order. It is intuitive because the conversational information only covers this subspace.

We derive this regret order by bounding DT(h)D_T(h). For h>0h>0, the second term of DT(h)D_T(h) satisfies

DT(h)(2)≤(1+e−Rsεσ4λ)rhh+2e−Rsεη×log⁡(1+T(h+2e−Rsεη)2λr).D_T(h)^{(2)}\leq\left(1+\frac{e^{-R_s\varepsilon}\sigma}{4\lambda}\right)\frac{rh}{h+2e^{-R_s\varepsilon}\eta} \times\log\left(1+\frac{T(h+2e^{-R_s\varepsilon}\eta)}{2\lambda r}\right).

The proof is given in Appendix § 11.§ 1. Combining this bound with the first term of DT(h)D_T(h) gives

DT(h)=O~((d−r)+rhh+η).(11)D_T(h)=\widetilde{O}\left((d-r)+r\frac{h}{h+\eta}\right). \tag*{(11)}

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 rr-dimensional subspace UU only. The reward-only bound [4] has a contribution from UU of O~(drTκ∗+κdr)\widetilde{O}\left(\sqrt{\frac{drT}{\kappa_*}}+\kappa dr\right). Compared with it, our leading term is reduced by a factor of 1/1+η/vˉ1/\sqrt{1+\eta/\bar{v}}. If σ=Ω(1/d)\sigma=\Omega(1/d), the lower-order term in Eq. (10) is O~(d2)\widetilde{O}(d^2), removing κ\kappa from the reward-only lower-order term. The condition σ=Ω(1/d)\sigma=\Omega(1/d) 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 UU of O~(κdrTκ∗+κ2dr)\widetilde{O}\left(\kappa\sqrt{\frac{drT}{\kappa_*}}+\kappa^2dr\right). Relative to our bound, this bound has an additional factor of κ\kappa 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 η\eta 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 da,b=xa−xbd_{a,b}=x_a-x_b and dt=dat,at′d_t=d_{a_t,a'_t}. At each round, the learner collects qtq_t responses r~t,i∼pc(⋅∣zt,iTθ∗)\tilde{r}_{t,i}\sim p_c(\cdot\mid z_{t,i}^{\mathsf{T}}\theta^*), with zt,i=x~kt,iz_{t,i}=\tilde{x}_{k_{t,i}} for i=1,…,qti=1,\ldots,q_t, then selects (at,at′)(a_t,a'_t) and observes ot∼pd(⋅∣dtTθ∗)o_t\sim p_d(\cdot\mid d_t^{\mathsf{T}}\theta^*).

The cumulative negative log-likelihood is

Lt(θ)=∑s<t−osdsTθ+md(dsTθ)ad+∑s≤t∑i=1qs−r~s,izs,iTθ+mc(zs,iTθ)ac.(12)\mathcal{L}_t(\theta)=\sum_{s<t}\frac{-o_s d_s^{\mathsf{T}}\theta+m_d(d_s^{\mathsf{T}}\theta)}{a_d} +\sum_{s\leq t}\sum_{i=1}^{q_s}\frac{-\tilde{r}_{s,i}z_{s,i}^{\mathsf{T}}\theta+m_c(z_{s,i}^{\mathsf{T}}\theta)}{a_c}. \tag*{(12)}

Using this loss and its Lipschitz constant LtL_t, 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:

Pt={a∈At:db,aTθ^t≤γt∥db,a∥Ht−1, ∀b∈At}.\mathcal{P}_t = \left\{a \in\mathcal{A}_t : d_{b,a}^{\mathsf{T}}\hat{\theta}_t \le\gamma_t \lVert d_{b,a} \rVert_{\mathbf{H}_t^{-1}},\ \forall b \in\mathcal{A}_t \right\}.

Then select the pair with the largest uncertainty in its utility difference:

(at,at′)∈arg⁡max⁡a,b∈Pt ∥xa−xb∥Ht−1.(a_t,a'_t) \in\underset{a,b\in\mathcal{P}_t}{\arg\max}\ \lVert x_a-x_b\rVert_{\mathbf{H}_t^{-1}}.

Following Saha [16], we define the cumulative dueling regret as

Rduel(T)=∑t=1T(xt,⋆−xat+xat′2)Tθ⋆.(13)R_{\mathrm{duel}}(T) = \sum_{t=1}^{T} \left(x_{t,\star} - \frac{x_{a_t}+x_{a'_t}}{2}\right)^{\mathsf{T}}\theta^\star. \tag*{(13)}

On the confidence event, an optimal arm belongs to Pt\mathcal{P}_t, so this selection rule bounds the instantaneous regret by 2γt∥dt∥Ht−12\gamma_t\lVert d_t\rVert_{\mathbf{H}_t^{-1}}, following the MaxInp analysis of Saha [16 Theorem 3]. Summing over rounds and applying Cauchy–Schwarz gives

Rduel(T)=∑t=1T(xt,⋆−xat+xat′2)Tθ⋆≤2γˉTT∑t=1T∥dt∥Ht−12.(14)\begin{aligned} R_{\mathrm{duel}}(T) &= \sum_{t=1}^{T} \left(x_{t,\star} - \frac{x_{a_t}+x_{a'_t}}{2}\right)^{\mathsf{T}}\theta^\star\\ &\le2\bar{\gamma}_T \sqrt{T\sum_{t=1}^{T}\lVert d_t\rVert_{\mathbf{H}_t^{-1}}^2}. \tag*{(14)} \end{aligned}

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 ξ=0.05\xi= 0.05 and use the mean functions μc(x)=μd(x)=1/(1+e−x)\mu_c(x) = \mu_d(x) = 1/(1 + e^{-x}).

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 ii in round tt, it selects

kt,i∈arg⁡max⁡k∈K ∥x~k∥Mt,i−1,k_{t,i} \in\underset{k\in\mathcal{K}}{\arg\max}\ \lVert\widetilde{x}_k\rVert_{\mathbf{M}_{t,i}^{-1}},

where Mt,i\mathbf{M}_{t,i} is defined in Section 4.

Experiments on Synthetic Data

Data Generation. We construct the synthetic data following [1]. We set the dimension to d=10d=10, the number of users to N=100N=100, the size of the key-term pool to ∣K∣=500|\mathcal{K}|=500, and the size of the arm pool to ∣A∣=5000|\mathcal{A}|=5000. We generate the arm feature vectors as follows. First, for each key-term k∈Kk\in\mathcal{K}, we sample a pseudo-feature vector x˙k∈Rd\dot{x}_k\in\mathbb{R}^d, whose coordinates are drawn independently from the uniform distribution U(−1,1)\mathcal{U}(-1,1). For each arm a∈[K]a\in[K], we randomly sample an integer ma∈{1,2,3}m_a\in\{1,2,3\} and then select uniformly without replacement a subset Ka⊆K\mathcal{K}_a\subseteq\mathcal{K} such that ∣Ka∣=ma|\mathcal{K}_a|=m_a. The weights are defined by Wa,k=1ma1{k∈Ka}W_{a,k}=\frac{1}{m_a}\mathbf{1}\{k\in\mathcal{K}_a\}. For each arm aa, we first draw an unnormalized feature vector from xˉa∼N(∑k∈KaWa,kx˙k,σx2Id)\bar{x}_a\sim\mathcal{N}\left(\sum_{k\in\mathcal{K}_a}W_{a,k}\dot{x}_k,\sigma_x^2I_d\right), where σx=0.02\sigma_x=0.02, and then normalize it as xa=xˉa∥xˉa∥2x_a=\frac{\bar{x}_a}{\|\bar{x}_a\|_2}. Thus, every arm satisfies ∥xa∥2=1\|x_a\|_2=1. After generating all arm features, we compute the feature vector of each key-term kk as x~k=∑a∈AWa,kxa∑a∈AWa,k\tilde{x}_k=\frac{\sum_{a\in\mathcal{A}}W_{a,k}x_a}{\sum_{a\in\mathcal{A}}W_{a,k}}. Finally, for each user u∈[N]u\in[N], we independently sample gu∼N(0,Id)g_u\sim\mathcal{N}(0,I_d) and define the user parameter as θu⋆=Sgu∥gu∥2\theta_u^\star=S\frac{g_u}{\|g_u\|_2} for S∈{4,6,8}S\in\{4,6,8\}. In our simulations, we set the time horizon to T=5000T=5000 and the conversation-frequency function to b(t)=10⌊t50⌋b(t)=10\left\lfloor\frac{t}{50}\right\rfloor. At each round tt, we randomly select 100 arms from A\mathcal{A} without replacement to form At\mathcal{A}_t. The same At\mathcal{A}_t 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 SS. HyConUCB achieves the lowest final mean regret for S=4S=4 and S=6S=6, while Var-Random performs slightly better for S=8S=8. As SS 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.

Image not extracted

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

Parameter Estimation Error. We measure estimation accuracy by the mean error ∥θ^t−θ⋆∥2\|\hat{\theta}_t-\theta^\star\|_2, 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 S=4S=4 and S=6S=6 and remains competitive for S=8S=8, 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.

Image not extracted

Figure 3. Parameter estimation error on synthetic data for different values of SS. 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 ua∈Rru_a \in\mathbb{R}^r and user directions vu∈Rrv_u \in\mathbb{R}^r using the sampling procedure above and normalize both to unit length, so that ∥ua∥2=∥vu∥2=1\lVert u_a\rVert_2 = \lVert v_u\rVert_2 = 1. We then set d=r+1d = r + 1 and construct xa=12(1,ua)x_a = \frac{1}{\sqrt{2}}(1,u_a) and θu∗=2(B,Cvu)\theta_u^* = \sqrt{2}(B,Cv_u). Consequently, we have S=2(B2+C2)S = \sqrt{2(B^2 + C^2)} and xaTθu∗=B+CuaTvux_a^\mathsf{T}\theta_u^* = B + C u_a^\mathsf{T}v_u. We set r=10r = 10, d=11d = 11, C=1C = 1, and vary B∈{2,4,6}B \in\{2, 4, 6\}. The common intercept BB 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 BB. ConDuel also outperforms OFUGLB-UCB, consistent with the value of relative conversational feedback in this setting. As BB increases, Var-AM’s relative advantage over OFUGLB-UCB diminishes, and their regret curves nearly coincide at B=6B = 6. 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.

Image not extracted

Figure 4. Cumulative regret on synthetic data for different values of the common intercept BB. As BB 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 uu, we estimate the preference parameter by solving the following ℓ2\ell_2-ball-constrained least-squares problem: θu∗=arg⁡min⁡∥θ∥2≤S∑a∈Iu(yu,a−xaTθ)2\theta_u^* = \mathop{\arg\min}_{\lVert\theta\rVert_2 \le S} \sum_{a \in\mathcal{I}_u} (y_{u,a} - x_a^\mathsf{T}\theta)^2. We set S=2S = 2 because preliminary unconstrained estimates show that 93 of the 100 users have parameter norms below 2. Both arm and conversational feedback are generated using θu∗\theta_u^*. For each user, we run T=5,000T = 5{,}000 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.

Image not extracted

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, P=K=4P = K = 4. Our choice of K=4K = 4 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 pt∈R4p_t \in\mathbb{R}^4, whose components represent the predicted probabilities for the four task categories. We append a constant coordinate of 1 to ptp_t to obtain ht∈R5h_t \in\mathbb{R}^5. For each model kk, we define vt,k=ek⊗htv_{t,k} = e_k \otimes h_t. Finally, we normalize this vector and append a global intercept, yielding xt,k∈R21x_{t,k} \in\mathbb{R}^{21}. Hence, d=21d = 21.

For arm feedback, we use the logged outcomes in the dataset. We associate each task with its designated expert model. Thus the weight matrix W=I4W = I_4. Because the dataset does not contain conversational feedback records, we generate this feedback synthetically. We first estimate the user parameter θ⋆\theta^\star via maximum likelihood using the training split. It should be noted that θ⋆\theta^\star 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 ∥θ⋆∥2≈5.504\lVert\theta^\star\rVert_2 \approx5.504, we set S=6S = 6. During the online experiment, we generate conversational feedback according to Eq. (2). We run each experiment for T=5,000T = 5{,}000 rounds on the test split and set the conversation-frequency function b(t)=⌊t/5⌋b(t) = \lfloor t/5 \rfloor.

Metrics. Let QtQ_t denote the query at round tt, and let rQt,k∈{0,1}r_{Q_t,k} \in\{0,1\} indicate whether model kk answers it correctly. Define the cumulative oracle regret

RT=∑t=1T(max⁡krQt,k−rQt,at).R_T = \sum_{t=1}^{T} \left(\max_k r_{Q_t,k} - r_{Q_t,a_t}\right).

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 RTexpertR_T^{\mathrm{expert}} as our primary metric. Let kexpert(Qt)k^{\mathrm{expert}}(Q_t) be the expert model on query QtQ_t. Define

RTexpert=∑t=1T(rQt,kexpert(Qt)−rQt,at).R_T^{\mathrm{expert}} = \sum_{t=1}^{T} \left(r_{Q_t,k^{\mathrm{expert}}(Q_t)} - r_{Q_t,a_t}\right).

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 Θ\Theta is convex and θ^t\hat{\theta}_t minimizes Lt\mathcal{L}_t over Θ\Theta, we have for θ∈Θ\theta\in\Theta,

∇Lt(θ^t)⊤(θ−θ^t)≥0.\nabla\mathcal{L}_t(\hat{\theta}_t)^{\top}(\theta-\hat{\theta}_t)\ge0.

Every observation feature vv in Lt\mathcal{L}_t satisfies ∥v∥2≤2\lVert v\rVert_2\le2, and hence ∣v⊤(θ−θ^t)∣≤4S\lvert v^{\top}(\theta-\hat{\theta}_t)\rvert\le4S. By Lemma D.1 in Lee et al. [4], we have

∫01(1−s)μ˙(v⊤((1−s)θ^t+sθ)) ds≥μ˙(v⊤θ^t)2(1+2SRs).\int_0^1(1-s)\dot{\mu}\bigl(v^{\top}((1-s)\hat{\theta}_t+s\theta)\bigr)\,ds\ge\frac{\dot{\mu}(v^{\top}\hat{\theta}_t)}{2(1+2SR_s)}.

By Taylor’s formula and the first-order optimality condition, we obtain

βt2≥Lt(θ)−Lt(θ^t)≥∫01(1−s)∥θ−θ^t∥∇2Lt((1−s)θ^t+sθ)2 ds≥∥θ−θ^t∥∇2Lt(θ^t)22(1+2SRs).\begin{aligned} \beta_t^2\ge\mathcal{L}_t(\theta)-\mathcal{L}_t(\hat{\theta}_t) \\ &\ge\int_0^1(1-s)\lVert\theta-\hat{\theta}_t\rVert_{\nabla^2\mathcal{L}_t((1-s)\hat{\theta}_t+s\theta)}^2\,ds \\ &\ge\frac{\lVert\theta-\hat{\theta}_t\rVert_{\nabla^2\mathcal{L}_t(\hat{\theta}_t)}^2}{2(1+2SR_s)}. \end{aligned}

Adding the regularization term and using ∥θ−θ^t∥2≤2S\lVert\theta-\hat{\theta}_t\rVert_2\le2S therefore gives

∥θ−θ^t∥Ht2≤2(1+2SRs)βt2+4λS2\lVert\theta-\hat{\theta}_t\rVert_{H_t}^2\le2(1+2SR_s)\beta_t^2+4\lambda S^2
≤2(1+2SRs)(βt2+4λS2)=γt2.\le2(1+2SR_s)(\beta_t^2+4\lambda S^2)=\gamma_t^2.

Thus Ct⊆EtC_t\subseteq E_t, which completes the proof. □

Guarantees for the Query Selection Rule

Suppress the query indices and write A(p)=∑epeseA(p)=\sum_e p_e s_e and jgeo=max⁡p∈ΔNqj(p)>0j_{\mathrm{geo}}=\max_{p\in\Delta_{N_q}}j(p)>0. Let p⋆p^\star solve Eq. (5). For emax⁡∈arg⁡max⁡esee_{\max}\in\arg\max_e s_e and pτ=(1−τ)p⋆+τδemax⁡p_\tau=(1-\tau)p^\star+\tau\delta_{e_{\max}}, we have j(pτ)≥(1−τ)j(p⋆)j(p_\tau)\ge(1-\tau)j(p^\star). Optimality of p⋆p^\star therefore gives

0≥τ{1−A(p⋆)}+ξlog⁡(1−τ).0\ge\tau\{1-A(p^\star)\}+\xi\log(1-\tau).

Dividing by τ\tau and letting τ↓0\tau\downarrow0 yields

A(p⋆)≥1−ξ.(15)A(p^\star)\ge1-\xi. \tag*{(15)}

Thus, the expected MaxInp score under p⋆p^\star is at least 1−ξ1-\xi.

Next, take pgeo∈arg⁡max⁡p∈ΔNqj(p)p^{\mathrm{geo}}\in\arg\max_{p\in\Delta_{N_q}}j(p) and set pτ=(1−τ)p⋆+τpgeop_\tau=(1-\tau)p^\star+\tau p^{\mathrm{geo}}. Since A(p)∈[0,1]A(p)\in[0,1] and jj is concave, optimality gives

0≥−τ+ξlog⁡(1+τ{jgeoj(p⋆)−1}).0\ge-\tau+\xi\log\left(1+\tau\left\{\frac{j_{\mathrm{geo}}}{j(p^\star)}-1\right\}\right).

Again dividing by τ\tau and letting τ↓0\tau\downarrow0 gives

j(p⋆)≥ξ1+ξjgeo.(16)j(p^\star)\ge\frac{\xi}{1+\xi}j_{\mathrm{geo}}. \tag*{(16)}

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 c⋆=min⁡eνd(qe⊤θ⋆)>0c_\star=\min_e\nu_d(q_e^{\top}\theta^\star)>0, and let H\mathcal{H} be the history immediately before the current query, including earlier queries in the same round. Then

E[νd(q~⊤θ⋆)q~q~⊤∣H]=∑epe⋆νd(qe⊤θ⋆)qeqe⊤\mathbb{E}\left[\nu_d(\tilde q^{\top}\theta^\star)\tilde q\tilde q^{\top}\mid\mathcal{H}\right] =\sum_e p_e^\star\nu_d(q_e^{\top}\theta^\star)q_eq_e^{\top}
⪰c⋆V(p⋆)⪰ξ1+ξc⋆jgeoPU.\succeq c_\star V(p^\star)\succeq\frac{\xi}{1+\xi}c_\star j_{\mathrm{geo}}P_U.

Thus each query satisfies the information bound with

σ=ξ1+ξc⋆jgeo.(17)\sigma=\frac{\xi}{1+\xi}c_\star j_{\mathrm{geo}}. \tag*{(17)}

Summing over the qtq_t queries proves Lemma 4.3.

Statistical Guarantees

Lemma A.1. For j∈{c,d}j \in\{\mathrm{c},\mathrm{d}\} and any u,vu,v,

mj(u)+mj(v)2−mj(u+v2)≥μ˙j(u)(u−v)28(1+Rs∣u−v∣/2)2.\frac{m_j(u)+m_j(v)}{2}-m_j\left(\frac{u+v}{2}\right)\geq\frac{\dot{\mu}_j(u)(u-v)^2}{8(1+R_s|u-v|/2)^2}.

Proof. For s∈[0,1]s \in[0,1], self-concordance gives

mj′′(u+s(v−u))≥μ˙j(u)e−sRs∣u−v∣.m_j^{\prime\prime}(u+s(v-u))\geq\dot{\mu}_j(u)e^{-sR_s|u-v|}.

Taylor’s formula therefore gives

mj(u)+mj(v)2−mj(u+v2)=(u−v)2(∫01/2s2mj′′(u+s(v−u)) ds+∫1/211−s2mj′′(u+s(v−u)) ds)≥μ˙j(u)2Rs2(1−e−Rs∣u−v∣/2)2≥μ˙j(u)(u−v)28(1+Rs∣u−v∣/2)2.\begin{aligned} \frac{m_j(u)+m_j(v)}{2}-m_j\left(\frac{u+v}{2}\right) &=(u-v)^2\left(\int_0^{1/2}\frac{s}{2}m_j^{\prime\prime}(u+s(v-u))\,\mathrm{d}s\right.\\ &\qquad\left.+\int_{1/2}^1\frac{1-s}{2}m_j^{\prime\prime}(u+s(v-u))\,\mathrm{d}s\right)\\ &\geq\frac{\dot{\mu}_j(u)}{2R_s^2}\left(1-e^{-R_s|u-v|/2}\right)^2\\ &\geq\frac{\dot{\mu}_j(u)(u-v)^2}{8(1+R_s|u-v|/2)^2}. \end{aligned}

The last step uses e−x/2≤(1+x/2)−1e^{-x/2}\leq(1+x/2)^{-1}.

Lemma A.2. Let

Ftq=∑s=1t∑i=1qsνd(d~s,i⊤θ⋆)d~s,id~s,i⊤.F_t^q=\sum_{s=1}^t\sum_{i=1}^{q_s}\nu_d(\widetilde d_{s,i}^{\top}\theta^\star)\widetilde d_{s,i}\widetilde d_{s,i}^{\top}.

For every t≤Tt\leq T,

P(Ftq⋡σb(t)2PU)≤rexp⁡(−adσb(t)32qmax⁡Rμ˙).\mathbb{P}\left(F_t^q\nsucceq\frac{\sigma b(t)}{2}P_U\right)\leq r\exp\left(-\frac{a_d\sigma b(t)}{32q_{\max}R\dot{\mu}}\right).

Consequently, with probability at least 1−δ/21-\delta/2,

Ftq⪰σb(t)2PUfor all t≤T withF_t^q\succeq\frac{\sigma b(t)}{2}P_U\quad\text{for all }t\leq T\text{ with}
b(t)≥32qmax⁡Rμ˙adσlog⁡2rTδ.b(t)\geq\frac{32q_{\max}R\dot{\mu}}{a_d\sigma}\log\frac{2rT}{\delta}.

Proof. Set F0q=0F_0^q=0 and restrict matrices to UU, an rr-dimensional space. The round increments Xs=(Fsq−Fs−1q)∣UX_s=(F_s^q-F_{s-1}^q)|_U satisfy

0⪯Xs⪯4qmax⁡Rμ˙adIU,E[Xs∣Fs−1]⪰σqsIU,0\preceq X_s\preceq\frac{4q_{\max}R\dot{\mu}}{a_d}I_U,\qquad\mathbb{E}[X_s\mid\mathcal{F}_{s-1}]\succeq\sigma q_sI_U,

by ∥d~s,i∥2≤2\lVert\widetilde d_{s,i}\rVert^2\leq2, νd≤Rμ˙/ad\nu_d\leq R\dot{\mu}/a_d, and Lemma 4.3. Hence the conditional expectations sum ∑s=1tE[Xs∣Fs−1]\sum_{s=1}^t\mathbb{E}[X_s\mid\mathcal{F}_{s-1}] is at least σb(t)IU\sigma b(t)I_U. Then by adapted matrix Chernoff inequality [21 Theorem 3.1], with relative deviation 1/21/2 and the bounds above, we have

P(Ftq⋡σb(t)2PU)≤rexp⁡(−adσb(t)32qmax⁡Rμ˙).\mathbb{P}\left(F_t^q\nsucceq\frac{\sigma b(t)}{2}P_U\right)\leq r\exp\left(-\frac{a_d\sigma b(t)}{32q_{\max}R\dot{\mu}}\right).

Here all query directions lie in UU, so the restriction controls exactly the claimed lower bound. Under the stated threshold, the right-hand side is at most δ/(2T)\delta/(2T). A union bound on TT proves the simultaneous conclusion.

Let E\mathcal{E} be the intersection of the simultaneous events in Lemmas 4.1 and A.2, so that P(E)≥1−δ\mathbb{P}(\mathcal{E})\geq1-\delta.

Lemma A.3. On E\mathcal{E}, for every t0<t≤Tt_0 < t \le T,

sup⁡θ∈Ctsup⁡v∈U∥v∥2≤2∣v⊤(θ−θ⋆)∣≤ε.\sup_{\theta\in C_t}\sup_{\substack{v\in U\\ \lVert v\rVert_2\le2}} \left|v^\top(\theta-\theta^\star)\right|\le\varepsilon.

Proof. Fix t>t0t>t_0 and θ∈Ct\theta\in C_t on E\mathcal{E}. Monotonicity of bb gives b(t)≥n0b(t)\ge n_0, so the bound in Lemma A.2 applies. Since θ,θ⋆∈Ct\theta,\theta^\star\in C_t and their midpoint lies in Θ\Theta, optimality of θ^t\hat{\theta}_t gives

Lt(θ)+Lt(θ⋆)2−Lt(θ+θ⋆2)≤βt2.\frac{\mathcal{L}_t(\theta)+\mathcal{L}_t(\theta^\star)}{2}-\mathcal{L}_t\left(\frac{\theta+\theta^\star}{2}\right)\le\beta_t^2.

The linear terms in the losses cancel. The remaining terms are nonnegative by convexity of mcm_c and mdm_d. Keeping the query terms gives

1ad∑s≤t∑i=1qs[md(d~s,i⊤θ)+md(d~s,i⊤θ⋆)2−md(d~s,i⊤(θ+θ⋆)2)]≤βt2.\frac{1}{a_d}\sum_{s\le t}\sum_{i=1}^{q_s}\left[\frac{m_d(\widetilde d_{s,i}^{\top}\theta)+m_d(\widetilde d_{s,i}^{\top}\theta^\star)}{2}-m_d\left(\frac{\widetilde d_{s,i}^{\top}(\theta+\theta^\star)}{2}\right)\right]\le\beta_t^2.

Every query satisfies ∣d~s,i⊤(θ−θ⋆)∣≤u\left|\widetilde d_{s,i}^{\top}(\theta-\theta^\star)\right|\le u, where u=2∥PU(θ−θ⋆)∥2u=2\lVert P_U(\theta-\theta^\star)\rVert_2. By Lemmas A.1 and A.2,

βt2≥(θ−θ⋆)⊤Ftq(θ−θ⋆)8(1+Rsu/2)2≥σb(t)64u2(1+Rsu/2)2.\beta_t^2\ge\frac{(\theta-\theta^\star)^\top F_t^q(\theta-\theta^\star)}{8(1+R_su/2)^2}\ge\frac{\sigma b(t)}{64}\frac{u^2}{(1+R_su/2)^2}.

The definition of n0n_0 gives

b(t)≥n0≥64(1+max⁡s≤Tβs2)σ(1ε+Rs2)2.b(t)\ge n_0\ge\frac{64(1+\max_{s\le T}\beta_s^2)}{\sigma}\left(\frac{1}{\varepsilon}+\frac{R_s}{2}\right)^2.

Combining these bounds, and using βt2<1+max⁡s≤Tβs2\beta_t^2<1+\max_{s\le T}\beta_s^2, yields

u1+Rsu/2≤ε1+Rsε/2.\frac{u}{1+R_su/2}\le\frac{\varepsilon}{1+R_s\varepsilon/2}.

The function u/(1+Rsu/2)u/(1+R_su/2) is increasing for u≥0u\ge0, so u≤εu\le\varepsilon. For every v∈Uv\in U with ∥v∥2≤2\lVert v\rVert_2\le2,

∣v⊤(θ−θ⋆)∣=∣v⊤PU(θ−θ⋆)∣≤2∥PU(θ−θ⋆)∥2=u≤ε.\left|v^\top(\theta-\theta^\star)\right|=\left|v^\top P_U(\theta-\theta^\star)\right|\le2\lVert P_U(\theta-\theta^\star)\rVert_2=u\le\varepsilon.

The Regret Analysis

Proof of Theorem 5.1. Work on E\mathcal{E}, which is defined in Section A.3. Following Lee et al. [4, Appendix E], choose

θˉt∈arg⁡min⁡θ∈⋃ℓ=tTCℓ μ˙c(xt⊤θ).(18)\bar{\theta}_t\in\underset{\theta\in\bigcup_{\ell=t}^{T} C_\ell}{\arg\min}\ \dot{\mu}_c(x_t^\top\theta). \tag*{(18)}

Let Δt=μc((xt,⋆)⊤θ⋆)−μc(xt⊤θ⋆)\Delta_t=\mu_c((x_{t,\star})^\top\theta^\star)-\mu_c(x_t^\top\theta^\star), and define

T={t0<t≤T:∥xt∥Vt−1≤14GT},RT=∑t∈TΔt.\mathcal{T}=\left\{t_0<t\le T:\lVert x_t\rVert_{V_{t-1}}\le\frac{1}{4G_T}\right\},\qquad R_{\mathcal{T}}=\sum_{t\in\mathcal{T}}\Delta_t.

Lemma B.2 and Δt≤2Rμ,⋆\Delta_t\le2R_{\mu,\star} give

R(T)≤RT+2Rμ,⋆t0+32Rμ,⋆acκGT2log⁡2DT(1/(acκ)).(19)R(T)\le R_{\mathcal{T}}+2R_{\mu,\star}t_0+\frac{32R_{\mu,\star}a_c\kappa G_T^2}{\log2}D_T(1/(a_c\kappa)). \tag*{(19)}

By the confidence ellipsoid and UCB selection, (xt,⋆)⊤θ⋆≤xt⊤θ^t+γt∥xt∥Ht−1(x_{t,\star})^\top\theta^\star\le x_t^\top\hat{\theta}_t+\gamma_t\lVert x_t\rVert_{H_t^{-1}}. Thus Lemma 5.2 gives, for t>t0t>t_0,

0≤(xt,⋆−xt)⊤θ⋆≤2γt∥xt∥Ht−1≤22γˉT∥xt∥Vt−1−1.0\le(x_{t,\star}-x_t)^\top\theta^\star\le2\gamma_t\lVert x_t\rVert_{H_t^{-1}}\le2\sqrt{2}\bar{\gamma}_T\lVert x_t\rVert_{V_{t-1}^{-1}}.

On T\mathcal{T}, we have

Rs(xt,⋆−xt)⊤θ⋆≤22RsγˉT∥xt∥Vt−1−1≤12≤34.R_s(x_{t,\star}-x_t)^\top\theta^\star\le2\sqrt{2}R_s\bar{\gamma}_T\lVert x_t\rVert_{V_{t-1}^{-1}}\le\frac{1}{\sqrt{2}}\le\frac{3}{4}.

Integrating Lemma B.1 over this gap yields

Δt=∫xt⊤θ⋆(xt,⋆)⊤θ⋆μ˙c(u) du≤22e3/4γˉTμ˙c(xt⊤θ⋆)∥xt∥Vt−1−1.\Delta_t = \int_{x_t^\top\theta^\star}^{(x_{t,\star})^\top\theta^\star} \dot{\mu}_c(u)\,du \le2\sqrt{2}e^{3/4}\bar{\gamma}_T\dot{\mu}_c(x_t^\top\theta^\star)\lVert x_t\rVert_{V_{t-1}^{-1}}.

For t∈Tt \in\mathcal{T}, choose ℓt≥t\ell_t \ge t with θˉt∈Cℓt\bar{\theta}_t \in\mathcal{C}_{\ell_t}. Both θˉt\bar{\theta}_t and θ⋆\theta^\star belong to this confidence set, so ∥θˉt−θ⋆∥Hℓt≤2γℓt\lVert\bar{\theta}_t-\theta^\star\rVert_{H_{\ell_t}}\le2\gamma_{\ell_t}. Since Vℓt⪰VtV_{\ell_t}\succeq V_t, Lemma 5.2 implies

∣xt⊤(θˉt−θ⋆)∣≤2γℓt∥xt∥Hℓt−1≤22γˉT∥xt∥Vt−1−1≤γˉT2GT.\left|x_t^\top(\bar{\theta}_t-\theta^\star)\right| \le2\gamma_{\ell_t}\lVert x_t\rVert_{H_{\ell_t}^{-1}} \le2\sqrt{2}\bar{\gamma}_T\lVert x_t\rVert_{V_{t-1}^{-1}} \le\frac{\bar{\gamma}_T}{\sqrt{2G_T}}.

Using RsγˉT≤GTR_s\bar{\gamma}_T\le G_T and Lemma B.1, we obtain

μ˙c(xt⊤θˉt)≥e−3/4μ˙c(xt⊤θ⋆).\dot{\mu}_c(x_t^\top\bar{\theta}_t)\ge e^{-3/4}\dot{\mu}_c(x_t^\top\theta^\star).

Also, self-concordance gives, for z≤z⋆z\le z^\star,

μ˙c(z)−μ˙c(z⋆)≤Rs∫zz⋆μ˙c(u) du=Rs{μc(z⋆)−μc(z)}.\dot{\mu}_c(z)-\dot{\mu}_c(z^\star)\le R_s\int_z^{z^\star}\dot{\mu}_c(u)\,du=R_s\{\mu_c(z^\star)-\mu_c(z)\}.

Consequently,

ac∑t∈Tνc(xt⊤θˉt)≤∑t∈Tμ˙c(xt⊤θ⋆)≤∑t∈Tμ˙c((xt,⋆)⊤θ⋆)+RsRT≤T/κ⋆+RsRT.\begin{aligned} a_c\sum_{t\in\mathcal{T}}\nu_c(x_t^\top\bar{\theta}_t) \le\sum_{t\in\mathcal{T}}\dot{\mu}_c(x_t^\top\theta^\star) \\ &\le\sum_{t\in\mathcal{T}}\dot{\mu}_c((x_{t,\star})^\top\theta^\star)+R_sR_T \\ &\le T/\kappa_\star+R_sR_T. \end{aligned}

Combining these bounds and applying Cauchy–Schwarz gives

RT≤22e3/2acγˉT∑t∈Tνc(xt⊤θˉt)∥xt∥Vt−1−1R_T\le2\sqrt{2}e^{3/2}\sqrt{a_c}\bar{\gamma}_T\sum_{t\in\mathcal{T}}\nu_c(x_t^\top\bar{\theta}_t)\lVert x_t\rVert_{V_{t-1}^{-1}}
≤22e3/2acγˉTT/κ⋆+RsRT∑t∈Tνc(xt⊤θˉt)∥xt∥Vt−1−12\le2\sqrt{2}e^{3/2}\sqrt{a_c}\bar{\gamma}_T\sqrt{T/\kappa_\star+R_sR_T}\sqrt{\sum_{t\in\mathcal{T}}\nu_c(x_t^\top\bar{\theta}_t)\lVert x_t\rVert_{V_{t-1}^{-1}}^2}
≤4e3/2acγˉTDT(vˉ/ac)(T/κ⋆+RsRT).\le4e^{3/2}\sqrt{a_c}\bar{\gamma}_T\sqrt{D_T(\bar{v}/a_c)(T/\kappa_\star+R_sR_T)}.

The last step uses Theorem 5.3 with h=vˉ/ach=\bar{v}/a_c and u≤2log⁡(1+u)u\le2\log(1+u) for 0≤u≤10\le u\le1; indeed, on T\mathcal{T},

u=νc(xt⊤θˉt)∥xt∥Vt−1−12≤Rμ/ac16GT2≤116.u=\nu_c(x_t^\top\bar{\theta}_t)\lVert x_t\rVert_{V_{t-1}^{-1}}^2\le\frac{R_\mu/a_c}{16G_T^2}\le\frac{1}{16}.

Applying xy≤x+y2\sqrt{xy}\le\frac{x+y}{2} yields

RT≤8e3/2acγˉTDT(vˉ/ac)T/κ⋆+16e3acRsγˉT2DT(vˉ/ac).R_T\le8e^{3/2}\sqrt{a_c}\bar{\gamma}_T\sqrt{D_T(\bar{v}/a_c)T/\kappa_\star}+16e^3a_cR_s\bar{\gamma}_T^2D_T(\bar{v}/a_c).

Combining this with Eq. (19) proves Eq. (8). □

Proof of Lemma 5.2. For s<ts<t, the definition of θˉs\bar{\theta}_s and θ^t∈Ct\hat{\theta}_t\in C_t give νc(xs⊤θ^t)≥νc(xs⊤θˉs)\nu_c(x_s^\top\hat{\theta}_t)\ge\nu_c(x_s^\top\bar{\theta}_s). For t>t0t>t_0, Lemma A.3 gives ∣d~s,i⊤(θ^t−θ⋆)∣≤ε\lvert\tilde{d}_{s,i}^{\top}(\hat{\theta}_t-\theta^\star)\rvert\le\varepsilon. So, by Lemma B.1,

νd(d~s,i⊤θ^t)≥e−Rsενd(d~s,i⊤θ⋆).\nu_d(\tilde{d}_{s,i}^{\top}\hat{\theta}_t)\ge e^{-R_s\varepsilon}\nu_d(\tilde{d}_{s,i}^{\top}\theta^\star).

Hence, by Lemma A.2,

Ht⪰λId+∑s<tνc(xs⊤θˉs)xsxs⊤+e−RsεFtqH_t\succeq\lambda I_d+\sum_{s<t}\nu_c(x_s^\top\bar{\theta}_s)x_sx_s^\top+e^{-R_s\varepsilon}F_t^q
⪰λId+∑s<tνc(xs⊤θˉs)xsxs⊤+e−Rsεσb(t)2PU⪰12Vt.□\succeq\lambda I_d+\sum_{s<t}\nu_c(x_s^\top\bar{\theta}_s)x_sx_s^\top+\frac{e^{-R_s\varepsilon}\sigma b(t)}{2}P_U\succeq\frac{1}{2}V_t. \quad\square

Proof of Theorem 5.3. We prove the general situation for arbitrary wt∈[0,h]w_t \in[0,h] and Vt=2λId+∑s<twsxsxs⊤+e−Rsεσ2b(t)PUV_t = 2\lambda I_d + \sum_{s<t} w_s x_s x_s^\top+ \frac{e^{-R_s\varepsilon}\sigma}{2}b(t)P_U. Set J0=2λIdJ_0 = 2\lambda I_d and Jt=Vt+wtxtxt⊤J_t = V_t + w_t x_t x_t^\top. By the determinant lemma and telescoping, we can get

ΦT:=∑t=1Tlog⁡(1+wt∥xt∥Vt−12)=log⁡det⁡JTdet⁡J0−∑t=1Tlog⁡det⁡Vtdet⁡Jt−1.\Phi_T := \sum_{t=1}^{T}\log(1+w_t\lVert x_t\rVert_{V_t^{-1}}^2) = \log\frac{\det J_T}{\det J_0}-\sum_{t=1}^{T}\log\frac{\det V_t}{\det J_{t-1}}.

Let QU,Q⊥Q_U,Q_\perp have orthonormal columns spanning U,U⊥U,U^\perp, respectively. Define Bt=QU⊤JtQUB_t=Q_U^\top J_tQ_U and Ft=Q⊥⊤JtQ⊥F_t=Q_\perp^\top J_tQ_\perp. Schur complements give

det⁡Jt≤det⁡Btdet⁡Ft,QU⊤Jt−1QU⪰Bt−1.\det J_t\leq\det B_t\det F_t,\qquad Q_U^\top J_{t}^{-1}Q_U\succeq B_t^{-1}.

When r=dr=d, we have det⁡Jt=det⁡Bt\det J_t=\det B_t and QU⊤Jt−1QU=Bt−1Q_U^\top J_t^{-1}Q_U=B_t^{-1}. For the ease of telescoping later, we set zt=2λr+th+e−Rsεσ2rb(t)z_t=2\lambda r+th+\frac{e^{-R_s\varepsilon}\sigma}{2}rb(t). Then

tr⁡Bt=2λr+∑s≤tws∥QU⊤xs∥2+e−Rsεσ2rb(t)≤zt,\operatorname{tr} B_t=2\lambda r+\sum_{s\leq t}w_s\lVert Q_U^\top x_s\rVert^2+\frac{e^{-R_s\varepsilon}\sigma}{2}rb(t)\leq z_t,
tr⁡Ft≤2λ(d−r)+th(r<d).\operatorname{tr} F_t\leq2\lambda(d-r)+th\qquad(r<d).

Let D⊥=(d−r)log⁡(1+Th/(2λ(d−r)))D_\perp=(d-r)\log(1+Th/(2\lambda(d-r))) for r<dr<d, and D⊥=0D_\perp=0 for r=dr=d. By det⁡A≤(tr⁡Am)m\det A\leq\left(\frac{\operatorname{tr}A}{m}\right)^m, we have

log⁡det⁡JTdet⁡J0≤D⊥+rlog⁡zTz0.\log\frac{\det J_T}{\det J_0}\leq D_\perp+r\log\frac{z_T}{z_0}.

Since Vt=Jt−1+e−Rsεσ2qtPUV_t=J_{t-1}+\frac{e^{-R_s\varepsilon}\sigma}{2}q_tP_U, the determinant lemma gives

log⁡det⁡Vtdet⁡Jt−1=log⁡det⁡(Ir+e−Rsεσ2qtQU⊤Jt−1−1QU)≥log⁡det⁡(Ir+e−Rsεσ2qtBt−1−1)≥rlog⁡(1+e−Rsεσrqt2tr⁡Bt−1)≥rlog⁡(1+e−Rsεσrqt2zt−1).\begin{aligned} \log\frac{\det V_t}{\det J_{t-1}} =\log\det\left(I_r+\frac{e^{-R_s\varepsilon}\sigma}{2}q_tQ_U^\top J_{t-1}^{-1}Q_U\right) \\ &\geq\log\det\left(I_r+\frac{e^{-R_s\varepsilon}\sigma}{2}q_tB_{t-1}^{-1}\right) \\ &\geq r\log\left(1+\frac{e^{-R_s\varepsilon}\sigma rq_t}{2\operatorname{tr}B_{t-1}}\right)\geq r\log\left(1+\frac{e^{-R_s\varepsilon}\sigma rq_t}{2z_{t-1}}\right). \end{aligned}

The second inequality holds by the convexity of f(x)=log⁡(1+cqt/x)f(x)=\log(1+cq_t/x) on (0,∞)(0,\infty). Finally, zt=zt−1+e−Rsεσ2rqt+hz_t=z_{t-1}+\frac{e^{-R_s\varepsilon}\sigma}{2}rq_t+h implies

ΦT≤D⊥+r∑t=1Tlog⁡ztzt−1+e−Rsεσ2rqt=D⊥+r∑t=1Tlog⁡(1+h2λr+(t−1)h+e−Rsεσ2rb(t))=DT(h).\begin{aligned} \Phi_T\leq D_\perp+r\sum_{t=1}^{T}\log\frac{z_t}{z_{t-1}+\frac{e^{-R_s\varepsilon}\sigma}{2}rq_t} \\ &=D_\perp+r\sum_{t=1}^{T}\log\left(1+\frac{h}{2\lambda r+(t-1)h+\frac{e^{-R_s\varepsilon}\sigma}{2}rb(t)}\right) \\ &=D_T(h). \end{aligned}

Taking wt=νc(xt⊤θˉt)w_t=\nu_c(x_t^\top\bar{\theta}_t) proves the stated case. □

Lemma B.1. For j∈{c,d}j\in\{c,d\} and all a,ba,b,

e−Rs∣a−b∣μ˙j(b)≤μ˙j(a)≤eRs∣a−b∣μ˙j(b).e^{-R_s\lvert a-b\rvert}\dot{\mu}_j(b)\leq\dot{\mu}_j(a)\leq e^{R_s\lvert a-b\rvert}\dot{\mu}_j(b).

The same inequalities hold for νj=μ˙j/aj\nu_j=\dot{\mu}_j/a_j.

Proof. Self-concordance gives ∣(log⁡μ˙j)′∣≤Rs\lvert(\log\dot{\mu}_j)'\rvert\leq R_s. Integrating between a,ba,b and exponentiating proves the claim. □

Lemma B.2. On E\mathcal{E},

∣{t0<t≤T:∥xt∥Vt−1>14GT}∣≤16acκGT2log⁡2DT(1/(acκ)).\left|\left\{t_0<t\leq T:\lVert x_t\rVert_{V_t^{-1}}>\frac{1}{4G_T}\right\}\right|\leq\frac{16a_c\kappa G_T^2}{\log2}D_T(1/(a_c\kappa)).

Proof. Define

V~t=2λId+1acκ∑s<txsxs⊤+e−Rsεσb(t)2PU.\widetilde{V}_t=2\lambda I_d+\frac{1}{a_c\kappa}\sum_{s<t}x_sx_s^\top+\frac{e^{-R_s\varepsilon}\sigma b(t)}{2}P_U.

Since Vt⪰V~tV_t\succeq\widetilde{V}_t, every round counted in the lemma satisfies

1acκ∥xt∥V~t−12>116acκGT2.\frac{1}{a_c\kappa}\lVert x_t\rVert_{\widetilde{V}_t^{-1}}^2>\frac{1}{16a_c\kappa G_T^2}.

Theorem 5.3, with wt=h=1/(acκ)w_t=h=1/(a_c\kappa), gives

∣{t0<t≤T:∥xt∥Vt−1>14GT}∣log⁡(1+116acκGT2)≤∑t=1Tlog⁡(1+1acκ∥xt∥V~t−12)≤DT(1/(acκ)).\left|\left\{t_0<t\leq T:\lVert x_t\rVert_{V_t^{-1}}>\frac{1}{4G_T}\right\}\right|\log\left(1+\frac{1}{16a_c\kappa G_T^2}\right) \leq\sum_{t=1}^{T}\log\left(1+\frac{1}{a_c\kappa}\lVert x_t\rVert_{\widetilde{V}_t^{-1}}^2\right)\leq D_T(1/(a_c\kappa)).

Since acκGT2≥κRμ˙≥1a_c\kappa G_T^2\geq\kappa R\dot{\mu}\geq1, applying log⁡(1+u)≥ulog⁡2\log(1+u)\geq u\log2 for u∈[0,1]u\in[0,1] proves the bound.

Additional Discussions

Potential Bound under Linear Query Schedules

Suppose b(t)=⌊ρt⌋b(t)=\lfloor\rho t\rfloor with ρ>0\rho>0 and h>0h>0. Write

zt=2λr+(t−1)(h+2e−Rsεη).z_t=2\lambda r+(t-1)(h+2e^{-R_s\varepsilon}\eta).

Replacing ⌊ρt⌋\lfloor\rho t\rfloor by ρt\rho t increases each denominator in DT(h)(2)D_T(h)^{(2)} by less than e−Rsεσr/2e^{-R_s\varepsilon}\sigma r/2, so each new denominator is at most 1+e−Rsεσ4λ1+\frac{e^{-R_s\varepsilon}\sigma}{4\lambda} times its original value. Using log⁡(1+cx)≤clog⁡(1+x)\log(1+cx)\leq c\log(1+x) for c≥1c\geq1 and x≥0x\geq0, we obtain

DT(h)(2)≤(1+e−Rsεσ4λ)γ∑t=1Tlog⁡(1+hzt+2e−Rsεη).D_T(h)^{(2)}\leq\left(1+\frac{e^{-R_s\varepsilon}\sigma}{4\lambda}\right)\gamma\sum_{t=1}^{T}\log\left(1+\frac{h}{z_t+2e^{-R_s\varepsilon}\eta}\right).

By concavity of the logarithm,

log⁡(1+hzt+2e−Rsεη)≤hh+2e−Rsεηlog⁡zt+1zt.\log\left(1+\frac{h}{z_t+2e^{-R_s\varepsilon}\eta}\right)\leq\frac{h}{h+2e^{-R_s\varepsilon}\eta}\log\frac{z_{t+1}}{z_t}.

Telescoping the sum yields

∑t=1Tlog⁡zt+1zt=log⁡(1+T(h+2e−Rsεη)2λr),\sum_{t=1}^{T}\log\frac{z_{t+1}}{z_t}=\log\left(1+\frac{T(h+2e^{-R_s\varepsilon}\eta)}{2\lambda r}\right),

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 μc(z)=μd(z)=1/(1+e−z)\mu_c(z)=\mu_d(z)=1/(1+e^{-z}), with ac=ad=1a_c=a_d=1 and Rs=1R_s=1. Let

xa=12(1,ua),θ∗=2(B,Cv),x_a=\frac{1}{\sqrt{2}}(1,u_a),\qquad\theta^*=\sqrt{2}(B,Cv),

where ua,v∈Rd−1u_a, v \in\mathbb{R}^{d-1}, ∥ua∥2=∥v∥2=1\lVert u_a\rVert_2 = \lVert v\rVert_2 = 1, and B,C>0B, C > 0. Therefore,

∥θ⋆∥2=2(B2+C2),∥xa∥2=1\lVert\theta^\star\rVert_2 = \sqrt{2(B^2 + C^2)}, \qquad\lVert x_a\rVert_2 = 1
xa⊤θ⋆=B+Cua⊤v∈[B−C,B+C].x_a^\top\theta^\star= B + C u_a^\top v \in[B-C, B+C].

For B≥CB \ge C, all arm utilities are nonnegative. Since the logistic curvature μ˙c(z)=μc(z)(1−μc(z))\dot{\mu}_c(z) = \mu_c(z)(1-\mu_c(z)) decreases on [0,∞)[0,\infty), we have

μ˙c(xa⊤θ⋆)≤μ˙c(B−C)≤e−(B−C).\dot{\mu}_c(x_a^\top\theta^\star) \le\dot{\mu}_c(B-C) \le e^{-(B-C)}.

Thus, the information in an absolute arm response can decay exponentially with the common intercept BB.

The definition of key-term vectors gives

x~k=12(1,u~k),∥u~k∥2≤1.\widetilde{x}_k = \frac{1}{\sqrt{2}}(1,\widetilde{u}_k), \qquad\lVert\widetilde{u}_k\rVert_2 \le1.

Suppose the relative key-term vectors u~k\widetilde{u}_k include {±ej}j=1r\{\pm e_j\}_{j=1}^r, where eje_j are the standard basis vectors of Rd−1\mathbb{R}^{d-1}. In a pairwise comparison, the common intercept cancels out:

qk,k′=x~k−x~k′=12(0,u~k−u~k′),qk,k′⊤θ⋆=C(u~k−u~k′)⊤v.q_{k,k'} = \widetilde{x}_k - \widetilde{x}_{k'} = \frac{1}{\sqrt{2}}(0,\widetilde{u}_k-\widetilde{u}_{k'}), \qquad q_{k,k'}^\top\theta^\star= C(\widetilde{u}_k-\widetilde{u}_{k'})^\top v.

Consequently,

∣qk,k′⊤θ⋆∣≤2C,μ˙d(qk,k′⊤θ⋆)≥μ˙d(2C),\lvert q_{k,k'}^\top\theta^\star\rvert\le2C, \qquad\dot{\mu}_d(q_{k,k'}^\top\theta^\star) \ge\dot{\mu}_d(2C),

and this lower bound is independent of BB.

For fixed CC and a large BB, we have c⋆=min⁡eνd(qe⊤θ⋆)≥μ˙d(2C)=O(1)c_\star= \min_e \nu_d(q_e^\top\theta^\star) \ge\dot{\mu}_d(2C) = O(1), where c⋆c_\star is defined in Appendix § 9.§ 2. Uniformly sampling the corresponding opposite pairs gives V(p)=2PU/rV(p)=2P_U/r, so jgeo≥2/rj_{\mathrm{geo}} \ge2/r, where jgeoj_{\mathrm{geo}} is defined in Appendix § 9.§ 2. Thus, for fixed ξ>0\xi> 0, Eq. (17) yields

σ=ξ1+ξc⋆jgeo≥ξ1+ξ2μ˙d(2C)r=Ω(1/r).\sigma= \frac{\xi}{1+\xi}c_\star j_{\mathrm{geo}} \ge\frac{\xi}{1+\xi}\frac{2\dot{\mu}_d(2C)}{r} = \Omega(1/r).

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [16]Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050–30062, 2021.
  17. [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. [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. [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. [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. [21]Joel A. Tropp. User-friendly Tail Bounds for Matrix Martingales, January 2011.DOI

Paper details

vlnc:W_xemb4a3f
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents