Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

Qirun Zeng, Xuchuang Wang, Jiayi Shen, Xutong Liu, Fang Kong, Jinhang Zuo · 2026

Read Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback by Qirun Zeng, Xuchuang Wang, Jiayi Shen, Xutong Liu, Fang Kong, Jinhang Zuo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05745.txt.

Introduction

Choosing the best option under uncertainty usually means tasting each arm directly. Qirun Zeng and five co-authors study a hybrid: at each round the learner may take an absolute reward from one arm, or a relative duel between two. Both feedback types follow generalized linear models, and the goal is fixed-confidence identification of the best arm.

They build a likelihood-ratio confidence sequence that unifies the two observation kinds into one ellipsoidal confidence set. Their Track-and-Stop algorithm then allocates queries by following a minimax-optimal design over arms and pairs jointly. Correctness and sample-complexity bounds accompany the method.

Catalog record

CREATORQirun Zeng, Xuchuang Wang, Jiayi Shen, Xutong Liu, Fang Kong, Jinhang Zuo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.05745

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback Qirun Zeng, Xuchuang Wang, Jiayi Shen, Xutong Liu, Fang Kong, Jinhang Zuo Abstract We study fixed-confidence best arm identification in generalized linear bandits under a hybrid feedback model: at each round, the learner may query either (i) absolute reward feedback from a single arm or (ii) relative (dueling) feedback from an arm pair, both governed by generalized linear models. We introduce a likelihood-ratio–based confidence sequence that unifies heterogeneous generalized linear observations and yields an explicit ellipsoidal confidence set under a self-concordance assumption. Building on this confidence set, we propose a hybrid Track-and-Stop algorithm that adaptively allocates queries by tracking a minimax-optimal design over a joint action space of arms and pairs. We establish δ \delta -correctness and provide high-probability upper bounds on the stopping time. We further extend the framework to a cost-aware setting that accounts for heterogeneous acquisition costs across feedback modalities. Empirical experiments demonstrate that the proposed algorithms significantly improve sample efficiency over baseline methods. 1 Introduction Large-scale interactive learning systems increasingly rely on heterogeneous user feedback. In modern conversational and recommendation platforms, especially LLM assistants trained with reinforcement learning from human feedback (RLHF) ( 3 ; 20 ) , supervision often comes from pairwise preferences, while absolute signals such as ratings, clicks, or task completion indicators may also be available. Although these feedback modalities are induced by a shared latent utility structure, they correspond to fundamentally different statistical observation models: absolute feedback provides noisy evaluations of individual actions, whereas relative feedback conveys comparative information that is invariant to shifts in scale. Designing learning algorithms that can systematically exploit such heterogeneous yet complementary feedback remains a central challenge in interactive learning. From a theoretical perspective, existing bandit models mostly treat different feedback modalities in isolation. Stochastic and linear bandits focus exclusively on reward-based observations, while dueling bandits and preference-based learning frameworks assume access only to pairwise comparisons ( 31 ; 30 ; 27 ) . Recent work has started to bridge this gap by studying hybrid feedback bandits ( 28 ) . However, existing approaches mainly combine reward and dueling feedback at the algorithmic level via joint elimination procedures. As a result, they do not fully exploit the shared latent structure underlying the two modalities within a unified statistical inference framework. A natural way to move from algorithmic fusion to statistical integration is to model absolute and relative feedback as different observations of a shared latent utility. Generalized linear bandits (GLBs) provide such a framework: absolute observations provide noisy nonlinear feedback on individual arm utilities, while dueling observations provide noisy nonlinear feedback on utility differences. Thus, the two modalities inform the same latent parameter through distinct observation channels. This motivates our study of fixed-confidence best-arm identification (BAI) with hybrid feedback under generalized linear structure, where the goal is to identify the best arm with high confidence while adaptively choosing between absolute and relative queries. Addressing this problem requires more than simply combining two feedback channels, and introduces several new challenges. First, reward and dueling feedback carry heterogeneous information: reward queries observe individual arm utilities, while dueling queries observe utility differences. Their distinct nonlinear likelihoods and curvature profiles make naive aggregation statistically inefficient. Second, fixed-confidence inference is harder under generalized linear structure, since uncertainty depends on both the unknown latent parameter and the queried arm or arm pair. This complicates the construction of time-uniform confidence regions for adaptive sampling and stopping. Third, exploration must be optimized jointly over actions and feedback modalities. The learner must decide which arms or arm pairs to query, when to use absolute or relative feedback, and how to account for potentially heterogeneous acquisition costs. Together, these challenges call for a unified inference, stopping, and allocation framework that estimates the shared latent utility, certifies the best arm, and adaptively balances absolute and relative feedback during pure exploration. Table 1: Comparison of fixed-confidence BAI across feedback models and structural assumptions. Model C_{\text{reward}} C_{\text{dueling}} ∗ Opt. † Sample Complexity ‡ 10 Linear 1 \emptyset ✓ \tilde{\mathcal{O}}\big(T^{\star}_{1,\emptyset}(\bm{\theta}^{\star})\log\frac{1}{\delta}\big) 12 Logistic 1 ( \emptyset ) \emptyset (1) ✗ \tilde{\mathcal{O}}\left(T^{\prime}_{1(\emptyset),\emptyset(1)}(\bm{\theta}^{\star})\log\frac{1}{\delta}\right) 22 Logistic 1 \emptyset ✓ \tilde{\mathcal{O}}\left(T^{\star}_{1,\emptyset}(\bm{\theta}^{\star})\log^{2}\frac{1}{\delta}\right) 14 GLM 1 \emptyset ✗ \tilde{\mathcal{O}}\left(T^{\prime\prime}_{1,\emptyset}(\bm{\theta}^{\star})\log^{2}\frac{1}{\delta}\right) HyTS (Sec. 4.1 ) Hybrid GLM 1 1 ✓ \tilde{\mathcal{O}}\big(T^{\star}_{1,1}(\bm{\theta}^{\star})\log\frac{1}{\delta}\big) Cost-aware-HyTS (Sec. 4.2 ) Hybrid GLM a b ✓ \tilde{\mathcal{O}}\big(T^{\star}_{a,b}(\bm{\theta}^{\star})\log\frac{1}{\delta}\big) ∗ C_{\text{reward}} and C_{\text{dueling}} denote the acquisition cost of reward and dueling feedback, respectively, with \emptyset indicating unavailable. † Opt. indicates whether the algorithm matches the displayed characteristic time up to logarithmic factors. For our hybrid rows, this refers to the confidence-width design criterion; the appendix discusses its relation to a local information-theoretic lower-bound relaxation for general GLMs. ‡ T^{\star}_{a,b}(\bm{\theta}^{\star}) denotes the relevant characteristic time under costs (a,b) ; in our hybrid rows, it is the minimax confidence-width characteristic time. T^{\prime}(\cdot) and T^{\prime\prime}(\cdot) denote finite-time complexity measures used in prior work. We defer detailed discussions and precise definitions of the characteristic times to the appendix. 1.1 Our Contributions We study fixed-confidence BAI in generalized linear bandits under a hybrid feedback model that allows both reward and dueling queries. Table 1 summarizes representative BAI results and highlights the gap addressed by this work. Our main contributions are summarized as follows. Hybrid GLM BAI formulation. We formulate structured pure exploration with both reward and dueling feedback under a shared GLM parameterization. Unlike unstructured hybrid-bandit models ( 28 ) , this setting transfers information through a latent parameter while allowing the two modalities to have different likelihoods and curvatures. Hybrid confidence sequences. We extend likelihood-ratio–based confidence sequences for self-concordant GLMs to hybrid observations. Despite the heterogeneous likelihoods induced by reward and dueling feedback, the resulting confidence region admits a single explicit ellipsoidal form, enabling unified inference and fixed-confidence stopping. Geometry-aware Track-and-Stop. Building on these confidence sets, we design HyTS-GLB, a Track-and-Stop–style algorithm that tracks a plug-in minimax design over the joint query space of arms and arm pairs. We prove \delta -correctness and high-probability stopping-time guarantees, and further relate the allocation rule to a local minimax experimental-design lower bound. Cost-aware extension. We extend HyTS-GLB to heterogeneous acquisition costs and provide high-probability guarantees on total cost. This lets the learner trade off both information and cost across reward and dueling queries. Empirical validation. We conduct experiments showing that hybrid feedback reduces sample complexity relative to single-modality baselines, while the cost-aware variant further adapts to asymmetric query costs across modalities. Together, these contributions yield a unified statistical and algorithmic framework for fixed-confidence best-arm identification with hybrid feedback in generalized linear bandits. All detailed proofs are deferred to the appendix due to space limitations. 1.2 Related Work Generalized Linear Bandits. GLMs ( 18 ) model exponential-family observations with natural parameter \bm{x}^{\top}\bm{\theta}^{\star} and mean \mu(\bm{x}^{\top}\bm{\theta}^{\star}) . 6 introduced GLM-based structured bandits, followed by work on regret and inference under assumptions such as self-concordance ( 23 ) . 17 developed likelihood-ratio–based confidence sequences for self-concordant GLMs, yielding convex and numerically tight confidence regions. We go beyond 17 by developing confidence sequences for hybrid reward–dueling feedback, where adaptive queries may arise from different GLM channels. This requires a single confidence certificate that aggregates heterogeneous Fisher curvature and feature geometry across modalities, a setting absent in prior single-channel GLM analyses. Beyond that, 16 ; 4 also construct similar confidence

Read the complete text