Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

# Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback
Source: [https://arxiv.org/html/2605.05745](https://arxiv.org/html/2605.05745)
Qirun Zeng Department of Computer Science City University of Hong Kong, Hong Kong SAR, China &Xuchuang Wang Manning College of Information & Computer Science University of Massachusetts Amherst, Amherst, MA, USA &Jiayi Shen School of Management University of Science and Technology of China, Hefei, Anhui, China &Xutong Liu Computer Science and Systems University of Washington, St\. Louis, Missouri, USA &Fang Kong School of Computer Science and Technology Southern University of Science and Technology, Shenzhen, Guangdong, China &Jinhang Zuo Department of Computer Science City University of Hong Kong

###### 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\.

## 1Introduction

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\)\(Christianoet al\.,[2017](https://arxiv.org/html/2605.05745#bib.bib12); Ouyanget al\.,[2022](https://arxiv.org/html/2605.05745#bib.bib11)\), 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\(Yue and Joachims,[2011](https://arxiv.org/html/2605.05745#bib.bib7); Yueet al\.,[2012](https://arxiv.org/html/2605.05745#bib.bib26); Suiet al\.,[2018](https://arxiv.org/html/2605.05745#bib.bib8)\)\. Recent work has started to bridge this gap by studying hybrid feedback bandits\(Wanget al\.,[2025](https://arxiv.org/html/2605.05745#bib.bib17)\)\. 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\.∗CrewardC\_\{\\text\{reward\}\}andCduelingC\_\{\\text\{dueling\}\}denote the acquisition cost of reward and dueling feedback, respectively, with∅\\emptysetindicating 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\. ‡Ta,b⋆​\(𝜽⋆\)T^\{\\star\}\_\{a,b\}\(\\bm\{\\theta\}^\{\\star\}\)denotes the relevant characteristic time under costs\(a,b\)\(a,b\); in our hybrid rows, it is the minimax confidence\-width characteristic time\.T′​\(⋅\)T^\{\\prime\}\(\\cdot\)andT′′​\(⋅\)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\.1Our Contributions

We study fixed\-confidence BAI in generalized linear bandits under a hybrid feedback model that allows both reward and dueling queries\. Table[1](https://arxiv.org/html/2605.05745#S1.T1)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\(Wanget al\.,[2025](https://arxiv.org/html/2605.05745#bib.bib17)\), 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\.2Related Work

Generalized Linear Bandits\.GLMs\(McCullagh,[2019](https://arxiv.org/html/2605.05745#bib.bib13)\)model exponential\-family observations with natural parameter𝒙⊤​𝜽⋆\\bm\{x\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}and meanμ​\(𝒙⊤​𝜽⋆\)\\mu\(\\bm\{x\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\)\.Filippiet al\.\([2010](https://arxiv.org/html/2605.05745#bib.bib27)\)introduced GLM\-based structured bandits, followed by work on regret and inference under assumptions such as self\-concordance\(Russacet al\.,[2021](https://arxiv.org/html/2605.05745#bib.bib39)\)\.Leeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33)\)developed likelihood\-ratio–based confidence sequences for self\-concordant GLMs, yielding convex and numerically tight confidence regions\. We go beyondLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33)\)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,Kirschneret al\.\([2025](https://arxiv.org/html/2605.05745#bib.bib2)\); Clericoet al\.\([2025](https://arxiv.org/html/2605.05745#bib.bib3)\)also construct similar confidence sequences for GLMs\.

Best\-Arm Identification and Track\-and\-Stop\.Best\-arm identification has been widely studied for stochastic and linear bandits\(Bubecket al\.,[2009](https://arxiv.org/html/2605.05745#bib.bib10); Audibert and Bubeck,[2010](https://arxiv.org/html/2605.05745#bib.bib9); Soareet al\.,[2014](https://arxiv.org/html/2605.05745#bib.bib25); Jourdan and Degenne,[2022](https://arxiv.org/html/2605.05745#bib.bib5); Shao and Fang,[2025](https://arxiv.org/html/2605.05745#bib.bib6)\)\.Kaufmannet al\.\([2016](https://arxiv.org/html/2605.05745#bib.bib23)\)established a general fixed\-confidence lower bound for multi\-armed bandits and proposed Track\-and\-Stop, which asymptotically achieves it\. For linear bandits,Soare \([2015](https://arxiv.org/html/2605.05745#bib.bib20)\)derived an instance\-dependent lower bound, andJedra and Proutiere \([2020](https://arxiv.org/html/2605.05745#bib.bib31)\)gave a matching algorithm\.Degenneet al\.\([2020](https://arxiv.org/html/2605.05745#bib.bib34)\)showed that iterative saddle\-point solvers can design asymptotically optimal BAI algorithms for structured bandits\. For GLBs,Kazerouni and Wein \([2021](https://arxiv.org/html/2605.05745#bib.bib29)\)studied\(ϵ,δ\)\(\\epsilon,\\delta\)\-PAC BAI and provided corresponding sample\-complexity guarantees\.

Relative and Hybrid Feedback\.Relative \(dueling\) feedback has been studied extensively in bandit learning, particularly in dueling bandits and preference\-based learning\(Yue and Joachims,[2011](https://arxiv.org/html/2605.05745#bib.bib7); Yueet al\.,[2012](https://arxiv.org/html/2605.05745#bib.bib26); Suiet al\.,[2018](https://arxiv.org/html/2605.05745#bib.bib8)\)\. It is also practically attractive because relative feedback can be easier to elicit than absolute rewards in conversational recommendation\(Zhanget al\.,[2020](https://arxiv.org/html/2605.05745#bib.bib36); Yanget al\.,[2024](https://arxiv.org/html/2605.05745#bib.bib35)\)\. Most closely related,Wanget al\.\([2025](https://arxiv.org/html/2605.05745#bib.bib17)\)study stochastic bandits with reward and dueling feedback and propose regret\-minimization algorithms based on elimination and decomposition, showing that hybrid feedback helps even without structure\. We instead study fixed\-confidence BAI under shared GLM structure, which requires time\-uniform confidence sequences, confidence\-based stopping, and design\-based allocation over arms and arm pairs\. Related hybrid settings have also been explored byHeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib1)\)for multi\-armed bandits, dueling bandits, and bandits with offline data\.

## 2Problem Formulation

Generalized Linear Model\.We begin by introducing the generalized linear model\(McCullagh,[2019](https://arxiv.org/html/2605.05745#bib.bib13)\)underlying both reward and dueling feedback\. Letr∈ℝr\\in\\mathbb\{R\}denote a generic scalar observation\. In a GLM, the conditional distribution ofrrgiven a scalar parameterη∈ℝ\\eta\\in\\mathbb\{R\}belongs to an exponential family and is specified by

p​\(r∣η\)=exp⁡\(r​η−b​\(η\)ζ​\(φ\)\+c​\(r,φ\)\),p\(r\\mid\\eta\)=\\exp\\\!\\left\(\\frac\{r\\eta\-b\(\\eta\)\}\{\\zeta\(\\varphi\)\}\+c\(r,\\varphi\)\\right\),\(1\)whereη\\etais the canonical \(natural\) parameter,φ\\varphiis a dispersion parameter,b​\(⋅\)b\(\\cdot\)is the log\-partition function, andc​\(r,φ\)c\(r,\\varphi\)is the base measure\. We usep​\(r∣η\)p\(r\\mid\\eta\)to denote the conditional probability density \(or mass\) function ofrrgivenη\\eta\. A fundamental property of GLMs is that the conditional mean ofrris given by𝔼​\[r∣η\]=b′​\(η\)≜μ​\(η\)\\mathbb\{E\}\[r\\mid\\eta\]=b^\{\\prime\}\(\\eta\)\\triangleq\\mu\(\\eta\), whereμ​\(⋅\)\\mu\(\\cdot\)is the mean function \(link function\)\. Many common observation models, including Gaussian, Poisson, and Bernoulli distributions, fall within this framework\.

Hybrid Generalized Linear Bandits\.We consider a stochastic decision\-making problem withKKarms indexed by𝒦≜\{1,2,…,K\}\\mathcal\{K\}\\triangleq\\\{1,2,\\dots,K\\\}\. Each armi∈𝒦i\\in\\mathcal\{K\}is associated with a known feature vector𝒙i∈ℝd\\bm\{x\}\_\{i\}\\in\\mathbb\{R\}^\{d\}, and the environment is governed by an unknown parameter𝜽⋆∈ℝd\\bm\{\\theta\}^\{\\star\}\\in\\mathbb\{R\}^\{d\}\. We assume the set of arms𝒦\\mathcal\{K\}spansℝd\\mathbb\{R\}^\{d\}\. The learner interacts with the environment sequentially and may acquire information through two different feedback modalities\.

At each roundtt, the learner chooses either a*reward query*or a*dueling query*\. In the former, it selectsit∈𝒦i\_\{t\}\\in\\mathcal\{K\}and observesRt∼pc\(⋅∣𝒙it⊤𝜽⋆\)R\_\{t\}\\sim p\_\{\\mathrm\{c\}\}\(\\cdot\\mid\\bm\{x\}\_\{i\_\{t\}\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\)\. In the latter, it selects\(jt,kt\)∈𝒢≜\{\(j,k\)∈𝒦2:j<k\}\(j\_\{t\},k\_\{t\}\)\\in\\mathcal\{G\}\\triangleq\\\{\(j,k\)\\in\\mathcal\{K\}^\{2\}:j<k\\\}and observesYt∈\{0,1\}Y\_\{t\}\\in\\\{0,1\\\}drawn frompd\(⋅∣𝒙jt,kt⊤𝜽⋆\)p\_\{\\mathrm\{d\}\}\(\\cdot\\mid\\bm\{x\}\_\{j\_\{t\},k\_\{t\}\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\), where𝒙j,k≜𝒙j−𝒙k\\bm\{x\}\_\{j,k\}\\triangleq\\bm\{x\}\_\{j\}\-\\bm\{x\}\_\{k\}, andYt=1Y\_\{t\}=1indicates preference forjtj\_\{t\}\.

Both feedback modalities are modeled as GLMs with a shared parameter𝜽⋆\\bm\{\\theta\}^\{\\star\}, but possibly different observation spaces and mean functionsμc\\mu\_\{\\mathrm\{c\}\}andμd\\mu\_\{\\mathrm\{d\}\}\. We use subscriptsc\\mathrm\{c\}andd\\mathrm\{d\}to distinguish reward and dueling quantities\. Define the joint action space𝒜≜𝒦∪𝒢\\mathcal\{A\}\\triangleq\\mathcal\{K\}\\cup\\mathcal\{G\}and, fora=\(j,k\)∈𝒢a=\(j,k\)\\in\\mathcal\{G\}, write𝒙a=𝒙j,k\\bm\{x\}\_\{a\}=\\bm\{x\}\_\{j,k\}\. For eacha∈𝒜a\\in\\mathcal\{A\}, we define the feedback modalitym​\(a\)m\(a\)to bec\\mathrm\{c\}fora∈𝒦a\\in\\mathcal\{K\}andd\\mathrm\{d\}fora∈𝒢a\\in\\mathcal\{G\}\. Selectingat∈𝒜a\_\{t\}\\in\\mathcal\{A\}corresponds to querying a single arm \(at∈𝒦a\_\{t\}\\in\\mathcal\{K\}\) or a pair \(at∈𝒢a\_\{t\}\\in\\mathcal\{G\}\), with observations generated by the corresponding modelpm​\(at\)\(⋅∣𝒙at⊤𝜽⋆\)p\_\{m\(a\_\{t\}\)\}\(\\cdot\\mid\\bm\{x\}\_\{a\_\{t\}\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\)\.

Best Arm Identification Objective\.Under the hybrid generalized linear bandit problem described above, we study a fixed\-confidence best arm identification \(BAI\) problem\. The learner sequentially queries reward or dueling feedback and aims to identify the single arm with the highest expected reward using as few samples as possible\. Formally, the optimal arm is defined as

i⋆≜argmaxi∈𝒦μc​\(𝒙i⊤​𝜽⋆\),i^\{\\star\}\\triangleq\\mathop\{\\mathrm\{argmax\}\}\\limits\_\{i\\in\\mathcal\{K\}\}\\mu\_\{\\mathrm\{c\}\}\\\!\\left\(\\bm\{x\}\_\{i\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\\right\),and we assume it is unique\. We consider adaptive strategies that select both the feedback modality and the queried arms over time\. Letτ\\taudenote a stopping time and leti^τ⋆\\hat\{i\}^\{\\star\}\_\{\\tau\}be the arm recommended upon termination\.

###### Definition 2\.2\.

Given a confidence levelδ∈\(0,1\)\\delta\\in\(0,1\), an exploration strategy is said to be*δ\\delta\-correct*if

Pr⁡\(i^τ⋆≠i⋆\)≤δ​and​Pr⁡\(τ<\+∞\)=1\.\\Pr\(\\hat\{i\}^\{\\star\}\_\{\\tau\}\\neq i^\{\\star\}\)\\leq\\delta\\text\{ and \}\\Pr\(\\tau<\+\\infty\)=1\.

The goal is to design aδ\\delta\-correct exploration strategy with a small stopping time\. We adopt the following standard assumptions from the generalized linear bandit literature\(Russacet al\.,[2021](https://arxiv.org/html/2605.05745#bib.bib39); Leeet al\.,[2024](https://arxiv.org/html/2605.05745#bib.bib33)\)\.

###### Assumption 2\.3\(Bounded parameter\)\.

The unknown parameter satisfies𝜽⋆∈Θ⊆ℬd​\(S\)≜\{𝜽∈ℝd:‖𝜽‖2≤S\}\\bm\{\\theta\}^\{\\star\}\\in\\Theta\\subseteq\\mathcal\{B\}^\{d\}\(S\)\\triangleq\\\{\\bm\{\\theta\}\\in\\mathbb\{R\}^\{d\}:\\\|\\bm\{\\theta\}\\\|\_\{2\}\\leq S\\\}, whereΘ\\Thetais compact and convex\.

###### Assumption 2\.4\(Bounded features\)\.

The arm feature set satisfies𝒳≜\{𝒙i:i∈𝒦\}⊆ℬd​\(1\)\\mathcal\{X\}\\triangleq\\\{\\bm\{x\}\_\{i\}:i\\in\\mathcal\{K\}\\\}\\subseteq\\mathcal\{B\}^\{d\}\(1\)\. This implies‖𝒙j,k‖2≤2\\\|\\bm\{x\}\_\{j,k\}\\\|\_\{2\}\\leq 2for all\(j,k\)∈𝒢\(j,k\)\\in\\mathcal\{G\}\.

###### Assumption 2\.5\(Smoothness and convexity\)\.

The log\-partition functionsbc​\(⋅\)b\_\{\\mathrm\{c\}\}\(\\cdot\)andbd​\(⋅\)b\_\{\\mathrm\{d\}\}\(\\cdot\)are three times continuously differentiable and convex, withμm​\(a\)′​\(⋅\)=bm​\(a\)′′​\(⋅\)≥0\\mu\_\{m\(a\)\}^\{\\prime\}\(\\cdot\)=b\_\{m\(a\)\}^\{\\prime\\prime\}\(\\cdot\)\\geq 0for everya∈𝒜a\\in\\mathcal\{A\}\.

## 3Confidence Sequences for Hybrid GLB

In this section, we develop time\-uniform confidence sequences for𝜽⋆\\bm\{\\theta\}^\{\\star\}under the hybrid feedback model\. Our construction follows the likelihood\-ratio framework ofLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33)\), adapted to mixed feedback\. We first build a likelihood\-ratio–based sequence, then use self\-concordance to derive an explicit ellipsoidal set for algorithmic design\.

### 3\.1Maximum Likelihood Estimation

To distinguish between reward and dueling feedback, we define the following index sets according to the actionasa\_\{s\}selected at roundss:𝒞t≜\{s≤t:as∈𝒦\}\\mathcal\{C\}\_\{t\}\\triangleq\\\{s\\leq t:a\_\{s\}\\in\\mathcal\{K\}\\\}and𝒟t≜\{s≤t:as∈𝒢\}\\mathcal\{D\}\_\{t\}\\triangleq\\\{s\\leq t:a\_\{s\}\\in\\mathcal\{G\}\\\}\. LetZsZ\_\{s\}denote the observation at roundss, i\.e\.,Zs=RsZ\_\{s\}=R\_\{s\}ifas∈𝒦a\_\{s\}\\in\\mathcal\{K\}andZs=YsZ\_\{s\}=Y\_\{s\}ifas∈𝒢a\_\{s\}\\in\\mathcal\{G\}\.

Under the GLM in Eq\. \([1](https://arxiv.org/html/2605.05745#S2.E1)\), the cumulative negative log\-likelihood at timettcan be decomposed as

ℒt​\(𝜽\)≜∑s=1tbm​\(as\)​\(𝒙as⊤​𝜽\)−Zs​𝒙as⊤​𝜽ζm​\(as\)​\(φm​\(as\)\)\.\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\\triangleq\\sum\_\{s=1\}^\{t\}\\frac\{b\_\{m\(a\_\{s\}\)\}\(\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\bm\{\\theta\}\)\-Z\_\{s\}\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\bm\{\\theta\}\}\{\\zeta\_\{m\(a\_\{s\}\)\}\(\\varphi\_\{m\(a\_\{s\}\)\}\)\}\.We define theℓ2\\ell\_\{2\}\-constrained maximum likelihood estimator \(MLE\) as

𝜽^t≜argmin𝜽∈Θℒt​\(𝜽\),\\hat\{\\bm\{\\theta\}\}\_\{t\}\\triangleq\\mathop\{\\mathrm\{argmin\}\}\\limits\_\{\\bm\{\\theta\}\\in\\Theta\}\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\),\(2\)whereΘ⊂ℝd\\Theta\\subset\\mathbb\{R\}^\{d\}is a compact, convex parameter set\. Equivalently, whenever𝜽^t\\hat\{\\bm\{\\theta\}\}\_\{t\}lies in the interior ofΘ\\Theta, it satisfies the first\-order optimality condition∇ℒt​\(𝜽^t\)=0\\nabla\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)=0\.

### 3\.2Likelihood\-Ratio Confidence Sequences

We first construct a likelihood\-ratio confidence sequence based on the cumulative loss\. LetLtL\_\{t\}be any almost\-sure upper bound on the Lipschitz modulus ofℒt\\mathcal\{L\}\_\{t\}overΘ\\Theta:

Lt≥sup𝜽,𝜽′∈Θ\|ℒt​\(𝜽\)−ℒt​\(𝜽′\)\|‖𝜽−𝜽′‖2\.L\_\{t\}\\geq\\sup\_\{\\bm\{\\theta\},\\bm\{\\theta\}^\{\\prime\}\\in\\Theta\}\\frac\{\|\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}^\{\\prime\}\)\|\}\{\\\|\\bm\{\\theta\}\-\\bm\{\\theta\}^\{\\prime\}\\\|\_\{2\}\}\.As inLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33)\), we use a high\-probability bound in place of the exact modulus\. In the hybrid model,LtL\_\{t\}decomposes over reward and dueling observations and thus scales with their sample counts\. Since‖𝒙i,j‖2≤2\\\|\\bm\{x\}\_\{i,j\}\\\|\_\{2\}\\leq 2while‖𝒙i‖2≤1\\\|\\bm\{x\}\_\{i\}\\\|\_\{2\}\\leq 1, the dueling term incurs an additional factor of22\.

###### Lemma 3\.1\(Unified likelihood\-ratio CS for hybrid GLMs, Theorem 3\.1 ofLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33)\)\)\.

Suppose Assumptions[2\.3](https://arxiv.org/html/2605.05745#S2.Thmtheorem3)–[2\.5](https://arxiv.org/html/2605.05745#S2.Thmtheorem5)hold\. Then for anyδ∈\(0,1\)\\delta\\in\(0,1\),

ℙ\(∃t≥1:ℒt\(𝜽⋆\)−ℒt\(𝜽^t\)≥βt\(δ\)\)≤δ,\\mathbb\{P\}\\big\(\\exists\\,t\\geq 1:\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}^\{\\star\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\\geq\\beta\_\{t\}\(\\delta\)\\big\)\\leq\\delta,with a time\-uniform confidence radius:

βt​\(δ\)≜log⁡1δ\+infct∈\(0,1\]\{d​log⁡1ct\+2​S​Lt​ct\}≤log⁡1δ\+d​log⁡\(max⁡\{e,2​e​S​Ltd\}\)\.\\beta\_\{t\}\(\\delta\)\\triangleq\\log\\tfrac\{1\}\{\\delta\}\+\\inf\_\{c\_\{t\}\\in\(0,1\]\}\\left\\\{d\\log\\\!\\tfrac\{1\}\{c\_\{t\}\}\+2SL\_\{t\}c\_\{t\}\\right\\\}\\leq\\log\\tfrac\{1\}\{\\delta\}\+d\\log\\\!\\left\(\\max\\\!\\left\\\{e,\\;\\tfrac\{2eSL\_\{t\}\}\{d\}\\right\\\}\\right\)\.\(3\)

Using the high\-probability Lipschitz bound inLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33), Table 1\), we haveLt=O​\(t\)L\_\{t\}=O\(t\)w\.h\.p\. and henceβt​\(δ\)=O​\(log⁡\(1/δ\)\+d​log⁡t\)\\beta\_\{t\}\(\\delta\)=O\(\\log\(1/\\delta\)\+d\\log t\)\. The proof follows the same arguments asLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33), Theorem 3\.1\)with a minor modification in the Lipschitz constant, and is therefore omitted\.

### 3\.3Ellipsoidal Confidence Sequences under Self\-Concordance

The likelihood\-ratio CS controls the loss difference but is not directly helpful to algorithmic design\. We therefore exploit self\-concordance to convert it into an ellipsoidal confidence sequence\.

###### Assumption 3\.2\(Self\-concordant GLMs\(Russacet al\.,[2021](https://arxiv.org/html/2605.05745#bib.bib39)\)\)\.

The GLMs of reward and dueling feedback are self\-concordant\. That is, there exist finite constantsMcM\_\{\\mathrm\{c\}\}andMdM\_\{\\mathrm\{d\}\}such that, for alla∈𝒜a\\in\\mathcal\{A\},\|μm​\(a\)′′​\(η\)\|≤Mm​\(a\)​μm​\(a\)′​\(η\),∀η∈\{𝒙a⊤​𝜽:𝜽∈Θ\}\|\\mu\_\{m\(a\)\}^\{\\prime\\prime\}\(\\eta\)\|\\leq M\_\{m\(a\)\}\\mu\_\{m\(a\)\}^\{\\prime\}\(\\eta\),\\forall\\,\\eta\\in\\\{\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}:\\bm\{\\theta\}\\in\\Theta\\\}\.

Although𝜽^t\\hat\{\\bm\{\\theta\}\}\_\{t\}minimizes the combined lossℒt\\mathcal\{L\}\_\{t\}rather than each component, self\-concordance holds uniformly overΘ\\Thetaand does not require it to minimizeℒtc\\mathcal\{L\}\_\{t\}^\{\\mathrm\{c\}\}orℒtd\\mathcal\{L\}\_\{t\}^\{\\mathrm\{d\}\}\. This is what lets the two feedback streams share one estimator and one confidence certificate rather than producing two separate ellipsoids that would have to be reconciled afterward\. To unify the two feedback modalities in inference and design, we define the aggregated information matrix

𝑨t≜∑s=1tμm​\(as\)′​\(𝒙as⊤​𝜽^t\)2​\(1\+S​ρas​Mm​\(as\)\)​ζm​\(as\)​\(φm​\(as\)\)​𝒙as​𝒙as⊤,\\bm\{A\}\_\{t\}\\triangleq\\sum\_\{s=1\}^\{t\}\\frac\{\\mu\_\{m\(a\_\{s\}\)\}^\{\\prime\}\(\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\}\{2\(1\+S\\rho\_\{a\_\{s\}\}M\_\{m\(a\_\{s\}\)\}\)\\zeta\_\{m\(a\_\{s\}\)\}\(\\varphi\_\{m\(a\_\{s\}\)\}\)\}\\bm\{x\}\_\{a\_\{s\}\}\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\},whereρa=1\\rho\_\{a\}=1fora∈𝒦a\\in\\mathcal\{K\}andρa=2\\rho\_\{a\}=2fora∈𝒢a\\in\\mathcal\{G\}\. Intuitively, the matrix𝑨t\\bm\{A\}\_\{t\}aggregates curvature information from both feedback types and serves as the effective information matrix in the ellipsoidal confidence set\.

Identifiability\.Throughout, we impose the identifiability condition \(Kazerouni and Wein \([2021](https://arxiv.org/html/2605.05745#bib.bib29)\)\): there exists a \(random but finite\) timeEEsuch that the matrix𝑨E\\bm\{A\}\_\{E\}is positive definite\. Consequently,𝑨t≻0\\bm\{A\}\_\{t\}\\succ 0for allt≥Et\\geq E, and𝑨t−1\\bm\{A\}\_\{t\}^\{\-1\}is well defined\.

Despite heterogeneous curvature induced by reward and dueling observations, their contributions combine additively into a single information matrix, yielding a unified ellipsoidal confidence region\.

###### Theorem 3\.3\(CS for hybrid GLMs\)\.

Defineℰt​\(δ\)≜\{𝛉∈ℝd:‖𝛉−𝛉^t‖𝐀t2≤βt​\(δ\)\}\\mathcal\{E\}\_\{t\}\(\\delta\)\\triangleq\\\{\\bm\{\\theta\}\\in\\mathbb\{R\}^\{d\}:\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|\_\{\\bm\{A\}\_\{t\}\}^\{2\}\\leq\\beta\_\{t\}\(\\delta\)\\\}\. We have

ℙ\(∃t≥1:𝜽⋆∉ℰt\(δ\)\)≤δ\.\\mathbb\{P\}\\\!\\left\(\\exists\\,t\\geq 1:\\bm\{\\theta\}^\{\\star\}\\notin\\mathcal\{E\}\_\{t\}\(\\delta\)\\right\)\\leq\\delta\.

This ellipsoidal form enables a simple stopping rule and a design\-based allocation strategy\.

###### Proof sketch\.

It suffices to show‖𝜽−𝜽^t‖At2≤ℒt​\(𝜽\)−ℒt​\(𝜽^t\)\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{A\_\{t\}\}\\leq\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\. ByLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33), Lemma D\.1\)and Assumption[3\.2](https://arxiv.org/html/2605.05745#S3.Thmtheorem2), each component loss admits the corresponding quadratic lower bound at𝜽^t\\hat\{\\bm\{\\theta\}\}\_\{t\}; summing yieldsℒt​\(𝜽\)−ℒt​\(𝜽^t\)≥‖𝜽−𝜽^t‖At2\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\\geq\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|\_\{A\_\{t\}\}^\{2\}, which with[Lemma˜3\.1](https://arxiv.org/html/2605.05745#S3.Thmtheorem1)concludes the proof\. ∎

Our construction builds on the framework ofLeeet al\.\([2024](https://arxiv.org/html/2605.05745#bib.bib33)\)and adapts it to hybrid feedback\. The resulting confidence ellipsoid aggregates curvature information from each modality according to its sampling frequency and feature geometry, enabling a unified treatment of heterogeneous feedback\. This is the statistical object used by the stopping and allocation rules below: the same matrix that certifies optimality also tells the algorithm whether the next most valuable observation is an absolute reward or a relative comparison\.

## 4Hybrid Track\-and\-Stop Algorithms

This section introduces a hybrid sampling framework that integrates reward and dueling feedback within a unified pure\-exploration procedure\. The central idea is to exploit the complementary statistical information provided by the two feedback modalities, while adaptively allocating samples across them\. Our approach extends the Track\-and\-Stop paradigm\(Garivier and Kaufmann,[2016](https://arxiv.org/html/2605.05745#bib.bib21); Jedra and Proutiere,[2020](https://arxiv.org/html/2605.05745#bib.bib31)\)to hybrid generalized linear bandits\.

### 4\.1HyTS\-GLB Algorithm

Minimax\-Optimal Design\.Following the Track\-and\-Stop principle, we define sampling proportions through a minimax optimal\-design problem\. The criterion allocates samples so as to minimize the largest confidence width among all comparisons between the current best arm and its competitors\. It is closely related to classicalGG\-optimal design\(Kiefer and Wolfowitz,[1960](https://arxiv.org/html/2605.05745#bib.bib14); Pukelsheim,[2006](https://arxiv.org/html/2605.05745#bib.bib16)\), which has played a central role in best\-arm identification for linear bandits\(Soareet al\.,[2014](https://arxiv.org/html/2605.05745#bib.bib25)\)\.

To leverage the ellipsoidal confidence sets for efficient pure exploration, we now specify how samples should be allocated across actions\. Let𝜽^t\\hat\{\\bm\{\\theta\}\}\_\{t\}denote the maximum likelihood estimator at timett, and define the current empirical best arm, with ties broken arbitrarily, asi^t⋆=argmaxi∈𝒦𝒙i⊤​𝜽^t\\hat\{i\}\_\{t\}^\{\\star\}=\{\\mathop\{\\mathrm\{argmax\}\}\\limits\}\_\{i\\in\\mathcal\{K\}\}\\bm\{x\}\_\{i\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t\}\.

Given a sampling weight vector𝒘∈Δ𝒜≜\{𝒘∣wa≥0∧∑a∈𝒜wa=1\}\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\\triangleq\\\{\\bm\{w\}\\mid w\_\{a\}\\geq 0\\land\\sum\_\{a\\in\\mathcal\{A\}\}w\_\{a\}=1\\\}, we define the hybrid information matrix

𝑨​\(𝒘,𝜽\)≜∑a∈𝒜𝒘a​μm​\(a\)′​\(𝒙a⊤​𝜽\)2​\(1\+S​ρa​Mm​\(a\)\)​ζm​\(a\)​\(φm​\(a\)\)​𝒙a​𝒙a⊤\.\\bm\{A\}\(\\bm\{w\},\\bm\{\\theta\}\)\\triangleq\\sum\_\{a\\in\\mathcal\{A\}\}\\bm\{w\}\_\{a\}\\,\\frac\{\\mu\_\{m\(a\)\}^\{\\prime\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}\)\}\{2\(1\+S\\rho\_\{a\}M\_\{m\(a\)\}\)\\zeta\_\{m\(a\)\}\(\\varphi\_\{m\(a\)\}\)\}\\,\\bm\{x\}\_\{a\}\\bm\{x\}\_\{a\}^\{\\top\}\.The minimax\-optimal sampling proportions𝒘⋆​\(t\)\\bm\{w\}^\{\\star\}\(t\)are any solution to

𝒘⋆​\(t\)=argmin𝒘∈Δ𝒜ϕ​\(𝜽^t,𝒘\)≜\{maxi≠i^t⋆⁡‖𝒙i^t⋆,i‖𝑨​\(𝒘,𝜽^t\)−12,if​𝑨​\(𝒘,𝜽^t\)≻0,\+∞,otherwise\.\\bm\{w\}^\{\\star\}\(t\)=\\mathop\{\\mathrm\{argmin\}\}\\limits\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\phi\(\{\\hat\{\\bm\{\\theta\}\}\_\{t\}\},\\bm\{w\}\)\\triangleq\\begin\{cases\}\\max\_\{i\\neq\\hat\{i\}^\{\\star\}\_\{t\}\}\\left\\\|\\bm\{x\}\_\{\\hat\{i\}^\{\\star\}\_\{t\},i\}\\right\\\|^\{2\}\_\{\\bm\{A\}\(\\bm\{w\},\{\\hat\{\\bm\{\\theta\}\}\_\{t\}\}\)^\{\-1\}\},&\\text\{if \}\\bm\{A\}\(\\bm\{w\},\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\\succ 0,\\\\ \+\\infty,&\\text\{otherwise\}\.\\end\{cases\}Since they specify asymptotic sampling frequencies rather than an explicit sequential policy, we adopt a tracking rule to realize these proportions online\.

Tracking Rule\.The learner tracks the target proportions by selecting the most under\-sampled action relative to its cumulative target mass, while incorporating a vanishing forced\-exploration mechanism to guarantee persistent excitation\. Let𝒜0⊂𝒜\\mathcal\{A\}\_\{0\}\\subset\\mathcal\{A\}be a fixed subset of arms such thatλmin​\(∑a∈𝒜0𝒙a​𝒙a⊤\)\>0,\\lambda\_\{\\min\}\\\!\\bigl\(\\sum\_\{a\\in\\mathcal\{A\}\_\{0\}\}\\bm\{x\}\_\{a\}\\bm\{x\}\_\{a\}^\{\\top\}\\bigr\)\>0,whereλmin​\(⋅\)\\lambda\_\{\\min\}\(\\cdot\)denotes the smallest eigenvalue, and letπ0\\pi\_\{0\}denote a probability distribution supported on𝒜0\\mathcal\{A\}\_\{0\}\(e\.g\., the uniform distribution\)\. Let𝒯t\\mathcal\{T\}\_\{t\}be the set of tracking rounds up to timett, and let𝑵𝒯​\(t\)\\bm\{N\}^\{\\mathcal\{T\}\}\(t\)and𝑾𝒯​\(t\)\\bm\{W\}^\{\\mathcal\{T\}\}\(t\)denote the corresponding pull counts and cumulative target mass\. At each round,

at∈\{argmina∈𝒜\(Na𝒯​\(t−1\)−Wa𝒯​\(t−1\)\),w\.p\.​1−ϵt,a∼π0,w\.p\.​ϵt,a\_\{t\}\\in\\begin\{cases\}\\mathop\{\\mathrm\{argmin\}\}\\limits\_\{a\\in\\mathcal\{A\}\}\\big\(N^\{\\mathcal\{T\}\}\_\{a\}\(t\\\!\-\\\!1\)\-W^\{\\mathcal\{T\}\}\_\{a\}\(t\\\!\-\\\!1\)\\big\),&\\text\{w\.p\. \}1\-\\epsilon\_\{t\},\\\\ a\\sim\\pi\_\{0\},&\\text\{w\.p\. \}\\epsilon\_\{t\},\\end\{cases\}\(4\)whereϵt=t−α\\epsilon\_\{t\}=t^\{\-\\alpha\}for someα∈\(0,1\)\\alpha\\in\(0,1\)\. The forced\-exploration component guarantees the non\-degeneracy of the information matrix at only an asymptotically lower\-order cost, while the tracking component ensures convergence to𝒘⋆\\bm\{w\}^\{\\star\}\. Moreover, we assume the curvature is bounded away from zero on the relevant domain \([Assumption˜4\.1](https://arxiv.org/html/2605.05745#S4.Thmtheorem1)\), a standard condition in best arm identification that ensures each exploration action provides non\-vanishing curvature\(Junet al\.,[2021](https://arxiv.org/html/2605.05745#bib.bib32); Kazerouni and Wein,[2021](https://arxiv.org/html/2605.05745#bib.bib29)\); in these works, the sample complexity also depends onκ−1\\kappa^\{\-1\}\.

###### Assumption 4\.1\.

There existsκ\>0\\kappa\>0such thatinfa∈𝒜,𝜽∈Θμm​\(a\)′​\(𝒙a⊤​𝜽\)≥κ\\inf\_\{a\\in\\mathcal\{A\},\\bm\{\\theta\}\\in\\Theta\}\\mu^\{\\prime\}\_\{m\(a\)\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}\)\\geq\\kappa\.

Stopping Rule\.The algorithm stops at the first timettsuch that the current empirically best armi^t⋆\\hat\{i\}\_\{t\}^\{\\star\}is certified optimal against all competitors with high confidence:

∀j≠i^t⋆:inf𝜽∈ℰt​\(δ\)𝒙i^t⋆,j⊤𝜽\>0\.\\forall j\\neq\\hat\{i\}\_\{t\}^\{\\star\}:\\quad\\inf\_\{\\bm\{\\theta\}\\in\\mathcal\{E\}\_\{t\}\(\\delta\)\}\\bm\{x\}\_\{\\hat\{i\}\_\{t\}^\{\\star\},j\}^\{\\top\}\\bm\{\\theta\}\>0\.\(5\)
###### Theorem 4\.3\(Correctness of the stopping rule\)\.

The stopping rule \([5](https://arxiv.org/html/2605.05745#S4.E5)\) guarantees that, upon stopping, the returned arm satisfiesi^τ⋆=i⋆\\hat\{i\}\_\{\\tau\}^\{\\star\}=i^\{\\star\}with probability at least1−δ1\-\\delta\.

###### Proof\.

Eq\. \([5](https://arxiv.org/html/2605.05745#S4.E5)\) implies that if𝜽⋆∈ℰt​\(δ\)\\bm\{\\theta\}^\{\\star\}\\in\\mathcal\{E\}\_\{t\}\(\\delta\),𝒙i^t⋆,j⊤​𝜽⋆\>0,∀j≠i^t⋆,\\bm\{x\}\_\{\\hat\{i\}\_\{t\}^\{\\star\},j\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\>0,\\forall j\\neq\\hat\{i\}\_\{t\}^\{\\star\},which yieldsi^t⋆=argmaxi𝒙i⊤​𝜽⋆\\hat\{i\}\_\{t\}^\{\\star\}=\{\\mathop\{\\mathrm\{argmax\}\}\\limits\}\_\{i\}\\bm\{x\}\_\{i\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\. The time\-uniform coverage ofℰt​\(δ\)\\mathcal\{E\}\_\{t\}\(\\delta\)ensures this event holds with probability at least1−δ1\-\\delta\. ∎

We now describe our proposed algorithm, Hybrid Track\-and\-Stop for GLBs, in[Algorithm˜1](https://arxiv.org/html/2605.05745#algorithm1)\.

1

Input:Confidence level

δ\\delta, warm\-up rounds

EE
2

3Warm\-up: select actions for

EErounds to ensure

𝑨E\\bm\{A\}\_\{E\}is positive definite;

4

5for*t=E\+1,E\+2,…t=E\+1,E\+2,\\ldots*do

6Compute the MLE

𝜽^t←argmin𝜽∈Θℒt−1​\(𝜽\)\\hat\{\\bm\{\\theta\}\}\_\{t\}\\leftarrow\{\\mathop\{\\mathrm\{argmin\}\}\\limits\}\_\{\\bm\{\\theta\}\\in\\Theta\}\\mathcal\{L\}\_\{t\-1\}\(\\bm\{\\theta\}\);

7

8if*the stopping condition \([5](https://arxiv.org/html/2605.05745#S4.E5)\) is satisfied*then

9return

i^t⋆=argmaxi∈𝒦𝒙i⊤​𝜽^t\\hat\{i\}\_\{t\}^\{\\star\}=\{\\mathop\{\\mathrm\{argmax\}\}\\limits\}\_\{i\\in\\mathcal\{K\}\}\\bm\{x\}\_\{i\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t\};

10

11end if

12

13Compute the target proportions

𝒘⋆​\(t\)\\bm\{w\}^\{\\star\}\(t\)and then select action

ata\_\{t\}according to Eq\. \([4](https://arxiv.org/html/2605.05745#S4.E4)\);

14

15Execute action

ata\_\{t\}and observe feedback

ZtZ\_\{t\}, then record the information;

16

17end for

Algorithm 1HyTS\-GLB###### Definition 4\.4\(Minimax characteristic time\)\.

For a given instance𝜽⋆\\bm\{\\theta\}^\{\\star\}, define the minimax characteristic time

T⋆​\(𝜽⋆\)≜inf𝒘∈Δ𝒜maxi≠i⋆⁡‖𝒙i⋆,i‖𝑨​\(𝒘,𝜽⋆\)−12Δmin2,T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\inf\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\frac\{\\max\_\{i\\neq i^\{\\star\}\}\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|^\{2\}\_\{\\bm\{A\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\}\{\\Delta\_\{\\min\}^\{2\}\},whereΔmin≜mini≠i⋆⁡𝒙i⋆,i⊤​𝜽⋆\\Delta\_\{\\min\}\\triangleq\\min\_\{i\\neq i^\{\\star\}\}\\bm\{x\}\_\{i^\{\\star\},i\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}denotes the smallest optimality gap\.

This design\-dependent quantity measures the cost of statistically separating the optimal arm from suboptimal arms under the worst comparison induced by the confidence\-width stopping rule\. Appendix[B\.1](https://arxiv.org/html/2605.05745#A2.SS1)discusses an information\-theoretic lower bound for hybrid GLM BAI and shows that its local quadratic relaxation has the same minimax experimental\-design form asT⋆​\(𝜽⋆\)T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\. This supports interpreting HyTS\-GLB as tracking the minimax allocation induced by our confidence\-width criterion, while stopping\-time guarantees still incur conservative constants and logarithmic factors\.

###### Theorem 4\.5\(Stopping time bound\)\.

Assume[Assumptions˜2\.4](https://arxiv.org/html/2605.05745#S2.Thmtheorem4),[2\.5](https://arxiv.org/html/2605.05745#S2.Thmtheorem5),[3\.2](https://arxiv.org/html/2605.05745#S3.Thmtheorem2),[2\.3](https://arxiv.org/html/2605.05745#S2.Thmtheorem3)and[4\.1](https://arxiv.org/html/2605.05745#S4.Thmtheorem1)hold\. Fix anyδ∈\(0,1/2\)\\delta\\in\(0,1/2\), with probability at least1−δ1\\\!\-\\\!\\delta, the stopping timeτ\\tausatisfies

τ≲T⋆​\(𝜽⋆\)​\(log⁡1δ\+d​log⁡T⋆​\(𝜽⋆\)\+d​log⁡log⁡eδ\)\.\\tau\\lesssim T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\big\(\\log\\tfrac\{1\}\{\\delta\}\+d\\log T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\+d\\log\\log\\tfrac\{e\}\{\\delta\}\\big\)\.

###### Proof sketch\.

Ignoring the negligible forced exploration phase, we focus on tracking\. If the design converges to the minimax\-optimal allocation, the uncertainty concentrates around the minimax characteristic timeT⋆​\(𝜽⋆\)T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\. Stopping is ensured once the confidence radius is belowΔmin/2\\Delta\_\{\\min\}/2\. Hencet≳T⋆​\(𝜽⋆\)​βt​\(δ\)t\\gtrsim T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\beta\_\{t\}\(\\delta\)suffices, and the claim follows by a standard fixed\-point argument\. ∎

[Theorem˜4\.5](https://arxiv.org/html/2605.05745#S4.Thmtheorem5)shows that HyTS\-GLB achieves instance\-dependent sample complexity governed by the minimax characteristic timeT⋆​\(𝜽⋆\)T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\), which captures the joint information from reward and dueling feedback under the adopted confidence\-width criterion\. Unlike single\-modality strategies, the minimax design underlyingT⋆​\(𝜽⋆\)T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)balances absolute and relative information, enabling faster separation along informative directions\. Consequently, HyTS\-GLB can strictly outperform reward\-only or dueling\-only methods when neither modality alone is sufficient\.

### 4\.2Cost\-Aware HyTS\-GLB

In many applications, different feedback modalities incur heterogeneous acquisition costs\. To capture this asymmetry, we extend HyTS\-GLB to a cost\-aware setting, where the objective is to minimize the*total acquisition cost*required to identify the best arm with high confidence\. All statistical modeling, confidence sequences, and stopping rules remain unchanged from the time\-minimization setting\.

Cost Model\.Each actiona∈𝒜a\\in\\mathcal\{A\}incurs a known acquisition costca\>0c\_\{a\}\>0\. For example, if all reward queries have costCrewardC\_\{\\mathrm\{reward\}\}and all dueling queries have costCduelingC\_\{\\mathrm\{dueling\}\}, thenca=Crewardc\_\{a\}=C\_\{\\mathrm\{reward\}\}fora∈𝒦a\\in\\mathcal\{K\}andca=Cduelingc\_\{a\}=C\_\{\\mathrm\{dueling\}\}fora∈𝒢a\\in\\mathcal\{G\}\. The cumulative cost up to timettis

Bt≜∑s=1tcas\.B\_\{t\}\\triangleq\{\\sum\}\_\{s=1\}^\{t\}c\_\{a\_\{s\}\}\.
The goal is to design aδ\\delta\-correct strategy that minimizesBτB\_\{\\tau\}\.

Cost\-normalized Design and Tracking\.Let𝒄∈ℝ\|𝒜\|\\bm\{c\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}denote the vector of action costs\. We introduce a cost\-normalized design vector𝒑∈ℝ≥0𝒜\\bm\{p\}\\in\\mathbb\{R\}^\{\\mathcal\{A\}\}\_\{\\geq 0\}satisfying⟨𝒄,𝒑⟩=1\\langle\\bm\{c\},\\bm\{p\}\\rangle=1, wherepap\_\{a\}represents the sampling intensity per unit cost\. The induced information matrix is𝑨​\(𝒑,𝜽\)\\bm\{A\}\(\\bm\{p\},\\bm\{\\theta\}\)\. Given the current estimate𝜽^t\\hat\{\\bm\{\\theta\}\}\_\{t\}, the cost\-aware minimax\-optimal design is defined as

𝒑⋆​\(t\)=argmin𝒑≥0:⟨𝒄,𝒑⟩=1maxi≠i^t⋆⁡‖𝒙i^t⋆,i‖𝑨​\(𝒑,𝜽^t\)−12\.\\bm\{p\}^\{\\star\}\(t\)=\\mathop\{\\mathrm\{argmin\}\}\\limits\_\{\\bm\{p\}\\geq 0:\\,\\langle\\bm\{c\},\\bm\{p\}\\rangle=1\}\\max\_\{i\\neq\\hat\{i\}^\{\\star\}\_\{t\}\}\\\|\\bm\{x\}\_\{\\hat\{i\}^\{\\star\}\_\{t\},i\}\\\|^\{2\}\_\{\\bm\{A\}\(\\bm\{p\},\\hat\{\\bm\{\\theta\}\}\_\{t\}\)^\{\-1\}\}\.\(6\)To implement the design in a round\-based procedure, we normalize𝒑¯⋆​\(t\)=𝒑⋆​\(t\)/∑a∈𝒜pa⋆​\(t\)\\bar\{\\bm\{p\}\}^\{\\star\}\(t\)=\\bm\{p\}^\{\\star\}\(t\)/\\sum\_\{a\\in\\mathcal\{A\}\}p^\{\\star\}\_\{a\}\(t\)and apply the same tracking rule as in HyTS\-GLB\.

###### Definition 4\.6\(Cost\-aware characteristic time\)\.

The cost\-aware characteristic time is

Tcost⋆​\(𝜽⋆\)≜inf𝒑≥0:⟨𝒄,𝒑⟩=1maxi≠i⋆⁡‖𝒙i⋆,i‖𝑨​\(𝒑,𝜽⋆\)−12Δmin2\.T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\inf\_\{\\bm\{p\}\\geq 0:\\,\\langle\\bm\{c\},\\bm\{p\}\\rangle=1\}\\frac\{\\max\_\{i\\neq i^\{\\star\}\}\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|^\{2\}\_\{\\bm\{A\}\(\\bm\{p\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\}\{\\Delta\_\{\\min\}^\{2\}\}\.

###### Theorem 4\.7\(Cost bound\)\.

Under the same assumptions as in[Theorem˜4\.5](https://arxiv.org/html/2605.05745#S4.Thmtheorem5), for anyδ∈\(0,1/2\)\\delta\\in\(0,1/2\), with probability at least1−δ1\-\\delta,

Bτ≲Tcost⋆​\(𝜽⋆\)​\(log⁡1δ\+d​log⁡Tcost⋆​\(𝜽⋆\)\+d​log⁡log⁡eδ\)\.B\_\{\\tau\}\\lesssim T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\big\(\\log\\tfrac\{1\}\{\\delta\}\+d\\log T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\+d\\log\\log\\tfrac\{e\}\{\\delta\}\\big\)\.

Compared with standard HyTS\-GLB, which implicitly assumes uniform query costs, the cost\-aware variant optimizes sampling in a cost\-normalized design space\. By minimizing the worst\-case uncertainty per unit cost, the algorithm adaptively favors the more cost\-efficient feedback modality while preserving the same confidence sequences and stopping rule\. When acquisition costs differ, this can reduce total cost, while recovering standard HyTS\-GLB as a special case under uniform costs\.

## 5Experiments

2233445566778899101010310^\{3\}10410^\{4\}10510^\{5\}10610^\{6\}DimensionStopping TimeRage\-GLMReTS\-GLBRandomDuelTS\-GLBHyTS\-GLB\(a\)Stopping time vs\. dimension1:31:21:12:13:101,0001\{,\}0002,0002\{,\}0003,0003\{,\}0004,0004\{,\}000Cost Ratio \(Creward:CduelingC\_\{\\text\{reward\}\}:C\_\{\\text\{dueling\}\}\)Total CostHyTS\-CduelingC\_\{\\text\{dueling\}\}Cost\-Aware\-CduelingC\_\{\\text\{dueling\}\}HyTS\-CrewardC\_\{\\text\{reward\}\}Cost\-Aware\-CrewardC\_\{\\text\{reward\}\}\(b\)Cost decomposition
Figure 1:Experimental results under different settingsOur experiments examine two questions: whether hybrid feedback improves sample efficiency over single\-modality baselines, and whether the cost\-aware design adapts to heterogeneous acquisition costs\. Due to the high cost of exact optimal allocation, we followJedra and Proutiere \([2020](https://arxiv.org/html/2605.05745#bib.bib31)\)and compute designs with Frank–Wolfe\(Jaggi,[2013](https://arxiv.org/html/2605.05745#bib.bib18)\)\. All methods are evaluated on the same generated instances under the same logistic observation model and confidence level\. We setK=d\+1K=d\+1withd∈\{2,4,6,8,10\}d\\in\\\{2,4,6,8,10\\\},δ=0\.05\\delta=0\.05, and𝜽⋆=\(S−1\)⋅𝟏/d\\bm\{\\theta\}^\{\\star\}=\(S\-1\)\\cdot\\mathbf\{1\}/\{\\sqrt\{d\}\}withS=5S=5\. Arms are constructed so that𝒙1⊤​𝜽⋆=0\.9​‖𝜽⋆‖2\\bm\{x\}\_\{1\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}=0\.9\\\|\\bm\{\\theta\}^\{\\star\}\\\|\_\{2\}, while fori≥2i\\geq 2,𝒙i⊤​𝜽⋆=0\.8​\(K−i\)​‖𝜽⋆‖2/\(K−1\)\\bm\{x\}\_\{i\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}=0\.8\(K\-i\)\\\|\\bm\{\\theta\}^\{\\star\}\\\|\_\{2\}/\{\(K\-1\)\}, with remaining coordinates random\. We compare HyTS\-GLB with RageGLM\(Junet al\.,[2021](https://arxiv.org/html/2605.05745#bib.bib32)\), ReTS\-GLB, DuelTS\-GLB, and a random hybrid baseline\. We also tested GLGapE\(Kazerouni and Wein,[2021](https://arxiv.org/html/2605.05745#bib.bib29)\), but it did not terminate within the simulation budget, consistent with observations inJunet al\.\([2021](https://arxiv.org/html/2605.05745#bib.bib32)\)\. Results report means over1010runs on shared instances\. As shown in[Figure˜1](https://arxiv.org/html/2605.05745#S5.F1)\(a\), HyTS\-GLB consistently outperforms RageGLM and ReTS\-GLB, and remains competitive with DuelTS\-GLB across all dimensions\. It achieves the smallest mean stopping time ford=4,6,10d=4,6,10, while DuelTS\-GLB is slightly better atd=2,8d=2,8\. This suggests that hybrid allocation is most useful when reward and dueling feedback reduce uncertainty along complementary directions, especially as the dimension grows\. We further evaluate cost\-aware allocation withCreward\+Cdueling=2C\_\{\\text\{reward\}\}\+C\_\{\\text\{dueling\}\}=2andCreward/Cdueling∈\{1/3,1/2,1,2,3\}\{C\_\{\\text\{reward\}\}\}/\{C\_\{\\text\{dueling\}\}\}\\in\\\{1/3,1/2,1,2,3\\\}\.[Figure˜1](https://arxiv.org/html/2605.05745#S5.F1)\(b\) reports the reward and dueling cost decomposition forK=3,d=2K=3,d=2\. The cost\-aware variant uniformly reduces total cost relative to standard HyTS\-GLB by shifting samples toward the cheaper modality; whenCreward/Cdueling=1\{C\_\{\\text\{reward\}\}\}/\{C\_\{\\text\{dueling\}\}\}=1, the two coincide, matching[Section˜4\.2](https://arxiv.org/html/2605.05745#S4.SS2)\.

Beyond these main experiments, we provide additional evidence for the role of hybrid allocation in the appendix\. We include experiments on a structured basis\-plus\-rotated\-arm construction and on the effect of the parameter scaleSS, showing that HyTS\-GLB remains competitive beyond the random\-arm setting\. We also give two concrete complexity comparisons: one where dueling feedback is more informative and one where reward feedback is more informative\. These examples reinforce the main message that HyTS\-GLB does not commit to a single feedback modality, but adapts its sampling allocation to the instance geometry and feedback utility\.

## 6Concluding Remarks

This work studies fixed\-confidence best\-arm identification in generalized linear bandits with hybrid reward and dueling feedback\. We develop a unified likelihood\-based confidence sequence that aggregates heterogeneous absolute and relative observations, combine it with a geometry\-aware Track\-and\-Stop sampling rule, and obtain correctness and instance\-dependent stopping\-time guarantees\. Our analysis shows that hybrid feedback enriches the information geometry of pure exploration while preserving a modular confidence\-stopping\-allocation structure\. In particular, the same confidence matrix both certifies the best arm and guides whether reward or dueling feedback is more informative for reducing uncertainty\. The cost\-aware extension further illustrates how this framework can adapt when feedback modalities have different acquisition costs\.

Several directions remain open\. One is to sharpen the connection between the proposed design criterion and fully instance\-optimal lower bounds for general GLMs\. Another is to extend the framework to time\-varying costs, contextual or non\-stationary environments, and richer preference models, where the usefulness of absolute and relative feedback may evolve during learning\.

## References

- J\. Audibert and S\. Bubeck \(2010\)Best arm identification in multi\-armed bandits\.InCOLT\-23th Conference on learning theory\-2010,Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- S\. Bubeck, R\. Munos, and G\. Stoltz \(2009\)Pure exploration in multi\-armed bandits problems\.InInternational conference on Algorithmic learning theory,pp\. 23–37\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- P\. F\. Christiano, J\. Leike, T\. Brown, M\. Martic, S\. Legg, and D\. Amodei \(2017\)Deep reinforcement learning from human preferences\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2605.05745#S1.p1.1),[Remark 2\.1](https://arxiv.org/html/2605.05745#S2.Thmtheorem1.p1.3)\.
- E\. Clerico, H\. Flynn, G\. Neu,et al\.\(2025\)Confidence sequences for generalized linear models via regret analysis\.arXiv preprint arXiv:2504\.16555\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p1.2)\.
- R\. Degenne, P\. Ménard, X\. Shang, and M\. Valko \(2020\)Gamification of pure exploration for linear bandits\.InInternational Conference on Machine Learning,pp\. 2432–2442\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- S\. Filippi, O\. Cappe, A\. Garivier, and C\. Szepesvári \(2010\)Parametric bandits: the generalized linear case\.Advances in neural information processing systems23\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p1.2)\.
- A\. Garivier and E\. Kaufmann \(2016\)Optimal best arm identification with fixed confidence\.InConference on Learning Theory,pp\. 998–1027\.Cited by:[§4](https://arxiv.org/html/2605.05745#S4.p1.1)\.
- Q\. He, M\. Wang, X\. Liu, Z\. Wang, and F\. Kong \(2024\)Learning across the gap: hybrid multi\-armed bandits with heterogeneous offline and online data\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1)\.
- M\. Jaggi \(2013\)Revisiting frank\-wolfe: projection\-free sparse convex optimization\.InInternational conference on machine learning,pp\. 427–435\.Cited by:[§5](https://arxiv.org/html/2605.05745#S5.p1.15)\.
- Y\. Jedra and A\. Proutiere \(2020\)Optimal best\-arm identification in linear bandits\.Advances in Neural Information Processing Systems33,pp\. 10007–10017\.Cited by:[Lemma A\.4](https://arxiv.org/html/2605.05745#A1.Thmtheorem4),[Lemma A\.5](https://arxiv.org/html/2605.05745#A1.Thmtheorem5),[Lemma A\.6](https://arxiv.org/html/2605.05745#A1.Thmtheorem6),[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1),[Table 1](https://arxiv.org/html/2605.05745#S1.T1.7.7.3),[§4](https://arxiv.org/html/2605.05745#S4.p1.1),[§5](https://arxiv.org/html/2605.05745#S5.p1.15)\.
- M\. Jourdan and R\. Degenne \(2022\)Choosing answers in epsilon\-best\-answer identification for linear bandits\.InInternational Conference on Machine Learning,pp\. 10384–10430\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- K\. Jun, L\. Jain, B\. Mason, and H\. Nassif \(2021\)Improved confidence bounds for the linear logistic model and applications to bandits\.InInternational Conference on Machine Learning,pp\. 5148–5157\.Cited by:[§B\.2](https://arxiv.org/html/2605.05745#A2.SS2.p3.1.1),[§B\.2](https://arxiv.org/html/2605.05745#A2.SS2.p4.1),[§B\.2](https://arxiv.org/html/2605.05745#A2.SS2.p6.1),[Table 1](https://arxiv.org/html/2605.05745#S1.T1.10.10.4),[§4\.1](https://arxiv.org/html/2605.05745#S4.SS1.p4.13),[§5](https://arxiv.org/html/2605.05745#S5.p1.15)\.
- E\. Kaufmann, O\. Cappé, and A\. Garivier \(2016\)On the complexity of best\-arm identification in multi\-armed bandit models\.The Journal of Machine Learning Research17\(1\),pp\. 1–42\.Cited by:[§B\.1](https://arxiv.org/html/2605.05745#A2.SS1.1.p1.5),[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- A\. Kazerouni and L\. M\. Wein \(2021\)Best arm identification in generalized linear bandits\.Operations Research Letters49\(3\),pp\. 365–371\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1),[Table 1](https://arxiv.org/html/2605.05745#S1.T1.14.14.3),[§3\.3](https://arxiv.org/html/2605.05745#S3.SS3.p3.5),[§4\.1](https://arxiv.org/html/2605.05745#S4.SS1.p4.13),[§5](https://arxiv.org/html/2605.05745#S5.p1.15)\.
- J\. Kiefer and J\. Wolfowitz \(1960\)The equivalence of two extremum problems\.Canadian Journal of Mathematics12,pp\. 363–366\.Cited by:[§4\.1](https://arxiv.org/html/2605.05745#S4.SS1.p1.1)\.
- J\. Kirschner, A\. Krause, M\. Meziu, and M\. Mutny \(2025\)Confidence estimation via sequential likelihood mixing\.arXiv preprint arXiv:2502\.14689\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p1.2)\.
- J\. Lee, S\. Yun, and K\. Jun \(2024\)A unified confidence sequence for generalized linear models, with applications to bandits\.arXiv preprint arXiv:2407\.13977\.Cited by:[§A\.1](https://arxiv.org/html/2605.05745#A1.SS1.p1.1),[Lemma A\.1](https://arxiv.org/html/2605.05745#A1.Thmtheorem1),[§B\.2](https://arxiv.org/html/2605.05745#A2.SS2.p1.1.1),[§B\.2](https://arxiv.org/html/2605.05745#A2.SS2.p2.1),[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p1.2),[§2](https://arxiv.org/html/2605.05745#S2.p6.1),[§3\.2](https://arxiv.org/html/2605.05745#S3.SS2.p1.7),[§3\.2](https://arxiv.org/html/2605.05745#S3.SS2.p2.2),[§3\.3](https://arxiv.org/html/2605.05745#S3.SS3.1.p1.3),[§3\.3](https://arxiv.org/html/2605.05745#S3.SS3.p6.1),[Lemma 3\.1](https://arxiv.org/html/2605.05745#S3.Thmtheorem1),[§3](https://arxiv.org/html/2605.05745#S3.p1.1)\.
- P\. McCullagh \(2019\)Generalized linear models\.Routledge\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p1.2),[§2](https://arxiv.org/html/2605.05745#S2.p1.3)\.
- S\. Negahban, S\. Oh, and D\. Shah \(2012\)Iterative ranking from pair\-wise comparisons\.InAdvances in Neural Information Processing Systems,F\. Pereira, C\.J\. Burges, L\. Bottou, and K\. Weinberger \(Eds\.\),Vol\.25,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2012/file/9adeb82fffb5444e81fa0ce8ad8afe7a-Paper.pdf)Cited by:[Remark 2\.1](https://arxiv.org/html/2605.05745#S2.Thmtheorem1.p1.3)\.
- L\. Ouyang, J\. Wu, X\. Jiang, D\. Almeida, C\. Wainwright, P\. Mishkin, C\. Zhang, S\. Agarwal, K\. Slama, A\. Ray,et al\.\(2022\)Training language models to follow instructions with human feedback\.Advances in neural information processing systems35,pp\. 27730–27744\.Cited by:[§1](https://arxiv.org/html/2605.05745#S1.p1.1)\.
- F\. Pukelsheim \(2006\)Optimal design of experiments\.SIAM\.Cited by:[§4\.1](https://arxiv.org/html/2605.05745#S4.SS1.p1.1)\.
- E\. O\. Rivera and A\. Tewari \(2024\)Near optimal pure exploration in logistic bandits\.arXiv preprint arXiv:2410\.20640\.Cited by:[§B\.2](https://arxiv.org/html/2605.05745#A2.SS2.p7.1),[Table 1](https://arxiv.org/html/2605.05745#S1.T1.12.12.3)\.
- Y\. Russac, L\. Faury, O\. Cappé, and A\. Garivier \(2021\)Self\-concordant analysis of generalized linear bandits with forgetting\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 658–666\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p1.2),[§2](https://arxiv.org/html/2605.05745#S2.p6.1),[Assumption 3\.2](https://arxiv.org/html/2605.05745#S3.Thmtheorem2)\.
- Y\. Shao and Z\. Fang \(2025\)Linear streaming bandit: regret minimization and fixed\-budget epsilon\-best arm identification\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.39,pp\. 20354–20361\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- M\. Soare, A\. Lazaric, and R\. Munos \(2014\)Best\-arm identification in linear bandits\.Advances in neural information processing systems27\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1),[§4\.1](https://arxiv.org/html/2605.05745#S4.SS1.p1.1)\.
- M\. Soare \(2015\)Sequential resource allocation in linear stochastic bandits\.Ph\.D\. Thesis,Université Lille 1\-Sciences et Technologies\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p2.1)\.
- Y\. Sui, M\. Zoghi, K\. Hofmann, and Y\. Yue \(2018\)Advancements in dueling bandits\.\.InIJCAI,pp\. 5502–5510\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1),[§1](https://arxiv.org/html/2605.05745#S1.p2.1)\.
- X\. Wang, Q\. Zeng, J\. Zuo, X\. Liu, M\. Hajiesmaili, J\. Lui, and A\. Wierman \(2025\)Fusing reward and dueling feedback in stochastic bandits\.arXiv preprint arXiv:2504\.15812\.Cited by:[§1\.1](https://arxiv.org/html/2605.05745#S1.SS1.p2.1),[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1),[§1](https://arxiv.org/html/2605.05745#S1.p2.1)\.
- S\. Yang, H\. Yuan, X\. Zhang, M\. Wang, H\. Zhang, and H\. Wang \(2024\)Conversational dueling bandits in generalized linear models\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 3806–3817\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1),[Remark 2\.1](https://arxiv.org/html/2605.05745#S2.Thmtheorem1.p1.3)\.
- Y\. Yue, J\. Broder, R\. Kleinberg, and T\. Joachims \(2012\)The k\-armed dueling bandits problem\.Journal of Computer and System Sciences78\(5\),pp\. 1538–1556\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1),[§1](https://arxiv.org/html/2605.05745#S1.p2.1),[Remark 2\.1](https://arxiv.org/html/2605.05745#S2.Thmtheorem1.p1.3)\.
- Y\. Yue and T\. Joachims \(2011\)Beat the mean bandit\.InProceedings of the 28th international conference on machine learning \(ICML\-11\),pp\. 241–248\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1),[§1](https://arxiv.org/html/2605.05745#S1.p2.1)\.
- X\. Zhang, H\. Xie, H\. Li, and J\. CS Lui \(2020\)Conversational contextual bandit: algorithm and application\.InProceedings of the web conference 2020,pp\. 662–672\.Cited by:[§1\.2](https://arxiv.org/html/2605.05745#S1.SS2.p3.1)\.

## Appendix

###### Contents

1. [1Introduction](https://arxiv.org/html/2605.05745#S1)1. [1\.1Our Contributions](https://arxiv.org/html/2605.05745#S1.SS1) 2. [1\.2Related Work](https://arxiv.org/html/2605.05745#S1.SS2)
2. [2Problem Formulation](https://arxiv.org/html/2605.05745#S2)
3. [3Confidence Sequences for Hybrid GLB](https://arxiv.org/html/2605.05745#S3)1. [3\.1Maximum Likelihood Estimation](https://arxiv.org/html/2605.05745#S3.SS1) 2. [3\.2Likelihood\-Ratio Confidence Sequences](https://arxiv.org/html/2605.05745#S3.SS2) 3. [3\.3Ellipsoidal Confidence Sequences under Self\-Concordance](https://arxiv.org/html/2605.05745#S3.SS3)
4. [4Hybrid Track\-and\-Stop Algorithms](https://arxiv.org/html/2605.05745#S4)1. [4\.1HyTS\-GLB Algorithm](https://arxiv.org/html/2605.05745#S4.SS1) 2. [4\.2Cost\-Aware HyTS\-GLB](https://arxiv.org/html/2605.05745#S4.SS2)
5. [5Experiments](https://arxiv.org/html/2605.05745#S5)
6. [6Concluding Remarks](https://arxiv.org/html/2605.05745#S6)
7. [References](https://arxiv.org/html/2605.05745#bib)
8. [Appendix](https://arxiv.org/html/2605.05745#Ax1)
9. [AProofs](https://arxiv.org/html/2605.05745#A1)1. [A\.1Proof ofTheorem˜3\.3](https://arxiv.org/html/2605.05745#A1.SS1) 2. [A\.2Proof ofTheorem˜4\.5](https://arxiv.org/html/2605.05745#A1.SS2) 3. [A\.3Proof ofTheorem˜4\.7](https://arxiv.org/html/2605.05745#A1.SS3)
10. [BAdditional Discussions](https://arxiv.org/html/2605.05745#A2)1. [B\.1A Common Lower\-Bound Principle](https://arxiv.org/html/2605.05745#A2.SS1) 2. [B\.2Comparisons and Extensions](https://arxiv.org/html/2605.05745#A2.SS2) 3. [B\.3Limitations](https://arxiv.org/html/2605.05745#A2.SS3)
11. [CAdditional Experiments](https://arxiv.org/html/2605.05745#A3)
12. [DConcrete Complexity Comparisons](https://arxiv.org/html/2605.05745#A4)1. [D\.1Case 1: Dueling Feedback is More Informative](https://arxiv.org/html/2605.05745#A4.SS1) 2. [D\.2Case 2: Reward Feedback is More Informative](https://arxiv.org/html/2605.05745#A4.SS2)

## Appendix AProofs

### A\.1Proof of[Theorem˜3\.3](https://arxiv.org/html/2605.05745#S3.Thmtheorem3)

We follow the proof ofLeeet al\.\[[2024](https://arxiv.org/html/2605.05745#bib.bib33), Theorem 3\.2\]\.

Define

G~tc​\(𝜽,𝝂\)≜1ζc​\(φc\)​∑s∈𝒞tα~sc​\(𝜽,𝝂\)​𝒙is​𝒙is⊤,\\displaystyle\\tilde\{G\}^\{\\mathrm\{c\}\}\_\{t\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)\\triangleq\\frac\{1\}\{\\zeta\_\{c\}\(\\varphi\_\{c\}\)\}\\sum\_\{s\\in\\mathcal\{C\}\_\{t\}\}\\tilde\{\\alpha\}^\{\\mathrm\{c\}\}\_\{s\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)\\bm\{x\}\_\{i\_\{s\}\}\\bm\{x\}\_\{i\_\{s\}\}^\{\\top\},G~td​\(𝜽,𝝂\)≜1ζd​\(φd\)​∑s∈𝒟tα~sd​\(𝜽,𝝂\)​𝒙as​𝒙as⊤,\\displaystyle\\tilde\{G\}^\{\\mathrm\{d\}\}\_\{t\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)\\triangleq\\frac\{1\}\{\\zeta\_\{d\}\(\\varphi\_\{d\}\)\}\\sum\_\{s\\in\\mathcal\{D\}\_\{t\}\}\\tilde\{\\alpha\}^\{\\mathrm\{d\}\}\_\{s\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)\\bm\{x\}\_\{a\_\{s\}\}\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\},where

α~sc​\(𝜽,𝝂\)\\displaystyle\\tilde\{\\alpha\}^\{\\mathrm\{c\}\}\_\{s\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)≜∫01\(1−v\)​μc′​\(⟨𝒙as,𝜽\+v​\(𝝂−𝜽\)⟩\)​dv,\\displaystyle\\triangleq\\int\_\{0\}^\{1\}\(1\-v\)\\mu\_\{\\mathrm\{c\}\}^\{\\prime\}\(\\langle\\bm\{x\}\_\{a\_\{s\}\},\\bm\{\\theta\}\+v\(\\bm\{\\nu\}\-\\bm\{\\theta\}\)\\rangle\)\\mathrm\{d\}v,α~sd​\(𝜽,𝝂\)\\displaystyle\\tilde\{\\alpha\}^\{\\mathrm\{d\}\}\_\{s\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)≜∫01\(1−v\)​μd′​\(⟨𝒙as,𝜽\+v​\(𝝂−𝜽\)⟩\)​dv\.\\displaystyle\\triangleq\\int\_\{0\}^\{1\}\(1\-v\)\\mu\_\{\\mathrm\{d\}\}^\{\\prime\}\(\\langle\\bm\{x\}\_\{a\_\{s\}\},\\bm\{\\theta\}\+v\(\\bm\{\\nu\}\-\\bm\{\\theta\}\)\\rangle\)\\mathrm\{d\}v\.
###### Lemma A\.1\(Leeet al\.,[2024](https://arxiv.org/html/2605.05745#bib.bib33), Lemma D\.1\)\.

Letμc,μd\\mu\_\{\\mathrm\{c\}\},\\mu\_\{\\mathrm\{d\}\}be increasing \(μc′,μd′≥0\\mu\_\{\\mathrm\{c\}\}^\{\\prime\},\\mu\_\{\\mathrm\{d\}\}^\{\\prime\}\\geq 0\) and self\-concordant with constantsMc,MdM\_\{\\mathrm\{c\}\},M\_\{\\mathrm\{d\}\}\. Let𝒵c,𝒵d⊂ℝ\\mathcal\{Z\}^\{\\mathrm\{c\}\},\\mathcal\{Z\}^\{\\mathrm\{d\}\}\\subset\\mathbb\{R\}be bounded\. Then, for anyz1c,z2c∈𝒵cz\_\{1\}^\{\\mathrm\{c\}\},z\_\{2\}^\{\\mathrm\{c\}\}\\in\\mathcal\{Z\}^\{\\mathrm\{c\}\}andz1d,z2d∈𝒵dz\_\{1\}^\{\\mathrm\{d\}\},z\_\{2\}^\{\\mathrm\{d\}\}\\in\\mathcal\{Z\}^\{\\mathrm\{d\}\},

∫01\(1−v\)​μc′​\(z1c\+v​\(z2c−z1c\)\)​dv\\displaystyle\\int\_\{0\}^\{1\}\(1\-v\)\\mu\_\{\\mathrm\{c\}\}^\{\\prime\}\(z\_\{1\}^\{\\mathrm\{c\}\}\+v\(z\_\{2\}^\{\\mathrm\{c\}\}\-z\_\{1\}^\{\\mathrm\{c\}\}\)\)\\mathrm\{d\}v≥μc′​\(z1c\)2\+Mc​\|z1c−z2c\|,\\displaystyle\\geq\\frac\{\\mu\_\{\\mathrm\{c\}\}^\{\\prime\}\(z\_\{1\}^\{\\mathrm\{c\}\}\)\}\{2\+M\_\{\\mathrm\{c\}\}\|z\_\{1\}^\{\\mathrm\{c\}\}\-z\_\{2\}^\{\\mathrm\{c\}\}\|\},∫01\(1−v\)​μd′​\(z1d\+v​\(z2d−z1d\)\)​dv\\displaystyle\\int\_\{0\}^\{1\}\(1\-v\)\\mu\_\{\\mathrm\{d\}\}^\{\\prime\}\(z\_\{1\}^\{\\mathrm\{d\}\}\+v\(z\_\{2\}^\{\\mathrm\{d\}\}\-z\_\{1\}^\{\\mathrm\{d\}\}\)\)\\mathrm\{d\}v≥μd′​\(z1d\)2\+Md​\|z1d−z2d\|\.\\displaystyle\\geq\\frac\{\\mu\_\{\\mathrm\{d\}\}^\{\\prime\}\(z\_\{1\}^\{\\mathrm\{d\}\}\)\}\{2\+M\_\{\\mathrm\{d\}\}\|z\_\{1\}^\{\\mathrm\{d\}\}\-z\_\{2\}^\{\\mathrm\{d\}\}\|\}\.Consequently, since\|z1−z2\|≤‖𝐱i⊤‖2​‖𝛎−𝛉‖2≤2​S\|z\_\{1\}\-z\_\{2\}\|\\leq\\\|\\bm\{x\}\_\{i\}^\{\\top\}\\\|\_\{2\}\\\|\\bm\{\\nu\}\-\\bm\{\\theta\}\\\|\_\{2\}\\leq 2Sfor reward observations and\|z1−z2\|≤‖𝐱j,k⊤‖2​‖𝛎−𝛉‖2≤4​S\|z\_\{1\}\-z\_\{2\}\|\\leq\\\|\\bm\{x\}\_\{j,k\}^\{\\top\}\\\|\_\{2\}\\\|\\bm\{\\nu\}\-\\bm\{\\theta\}\\\|\_\{2\}\\leq 4Sfor dueling observations,

G~tc​\(𝜽,𝝂\)\\displaystyle\\tilde\{G\}\_\{t\}^\{\\mathrm\{c\}\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)⪰∇2ℒtc​\(𝜽\)2​\(1\+S​Mc\),\\displaystyle\\succeq\\frac\{\\nabla^\{2\}\\mathcal\{L\}^\{\\mathrm\{c\}\}\_\{t\}\(\\bm\{\\theta\}\)\}\{2\(1\+SM\_\{\\mathrm\{c\}\}\)\},G~td​\(𝜽,𝝂\)\\displaystyle\\tilde\{G\}\_\{t\}^\{\\mathrm\{d\}\}\(\\bm\{\\theta\},\\bm\{\\nu\}\)⪰∇2ℒtd​\(𝜽\)2​\(1\+2​S​Md\)\.\\displaystyle\\succeq\\frac\{\\nabla^\{2\}\\mathcal\{L\}^\{\\mathrm\{d\}\}\_\{t\}\(\\bm\{\\theta\}\)\}\{2\(1\+2SM\_\{\\mathrm\{d\}\}\)\}\.

Let

ℒtc≜∑s∈𝒞t\(bc​\(𝒙as⊤​𝜽\)−Rs​𝒙as⊤​𝜽\)/ζc​\(φc\),\\mathcal\{L\}\_\{t\}^\{\\mathrm\{c\}\}\\triangleq\\sum\_\{s\\in\\mathcal\{C\}\_\{t\}\}\{\(b\_\{\\mathrm\{c\}\}\(\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\bm\{\\theta\}\)\-R\_\{s\}\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\bm\{\\theta\}\)\}/\{\\zeta\_\{\\mathrm\{c\}\}\(\\varphi\_\{\\mathrm\{c\}\}\)\},ℒtd≜∑s∈𝒟t\(bd​\(𝒙as⊤​𝜽\)−Ys​𝒙as⊤​𝜽\)/ζd​\(φd\)\\mathcal\{L\}\_\{t\}^\{\\mathrm\{d\}\}\\triangleq\\sum\_\{s\\in\\mathcal\{D\}\_\{t\}\}\{\(b\_\{\\mathrm\{d\}\}\(\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\bm\{\\theta\}\)\-Y\_\{s\}\\bm\{x\}\_\{a\_\{s\}\}^\{\\top\}\\bm\{\\theta\}\)\}/\{\\zeta\_\{\\mathrm\{d\}\}\(\\varphi\_\{\\mathrm\{d\}\}\)\}denote the cumulative loss incurred by reward observation and dueling observation separately\. By Taylor’s theorem with integral remainder,

ℒtc​\(𝜽\)−ℒtc​\(𝜽^t\)\\displaystyle\\mathcal\{L\}^\{\\mathrm\{c\}\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}^\{\\mathrm\{c\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)=⟨∇ℒtc​\(𝜽^t\),𝜽−𝜽^t⟩\+‖𝜽−𝜽^t‖G~tc​\(𝜽^t,𝜽\)2,\\displaystyle=\\langle\\nabla\\mathcal\{L\}^\{\\mathrm\{c\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\),\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\rangle\+\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\tilde\{G\}^\{\\mathrm\{c\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{\\theta\}\)\},ℒtd​\(𝜽\)−ℒtd​\(𝜽^t\)\\displaystyle\\mathcal\{L\}^\{\\mathrm\{d\}\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}^\{\\mathrm\{d\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)=⟨∇ℒtd​\(𝜽^t\),𝜽−𝜽^t⟩\+‖𝜽−𝜽^t‖G~td​\(𝜽^t,𝜽\)2\.\\displaystyle=\\langle\\nabla\\mathcal\{L\}^\{\\mathrm\{d\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\),\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\rangle\+\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\tilde\{G\}^\{\\mathrm\{d\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{\\theta\}\)\}\.Summing the two equalities yields

ℒt​\(𝜽\)−ℒt​\(𝜽^t\)=⟨∇ℒt​\(𝜽^t\),𝜽−𝜽^t⟩\+‖𝜽−𝜽^t‖G~tc​\(𝜽^t,𝜽\)2\+‖𝜽−𝜽^t‖G~td​\(𝜽^t,𝜽\)2\.\\displaystyle\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)=\\langle\\nabla\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\),\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\rangle\+\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\tilde\{G\}^\{\\mathrm\{c\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{\\theta\}\)\}\+\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\tilde\{G\}^\{\\mathrm\{d\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{\\theta\}\)\}\.Since𝜽^t∈argmin𝜽∈Θℒt​\(𝜽\)\\hat\{\\bm\{\\theta\}\}\_\{t\}\\in\{\\mathop\{\\mathrm\{argmin\}\}\\limits\}\_\{\\bm\{\\theta\}\\in\\Theta\}\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)andΘ\\Thetais convex, the first\-order optimality condition implies that for any𝜽∈Θ\\bm\{\\theta\}\\in\\Theta,

⟨∇ℒt​\(𝜽^t\),𝜽−𝜽^t⟩≥0\.\\langle\\nabla\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\),\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\rangle\\geq 0\.Therefore,

ℒt​\(𝜽\)−ℒt​\(𝜽^t\)\\displaystyle\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)≥‖𝜽−𝜽^t‖G~tc​\(𝜽^t,𝜽\)2\+‖𝜽−𝜽^t‖G~td​\(𝜽^t,𝜽\)2\.\\displaystyle\\geq\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\tilde\{G\}^\{\\mathrm\{c\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{\\theta\}\)\}\+\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\tilde\{G\}^\{\\mathrm\{d\}\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{\\theta\}\)\}\.
###### Lemma A\.2\.

Fort≥1t\\geq 1, consider a hybrid cumulative loss

ℒt​\(𝜽\)=ℒtc​\(𝜽\)\+ℒtd​\(𝜽\),\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)=\\mathcal\{L\}\_\{t\}^\{\\mathrm\{c\}\}\(\\bm\{\\theta\}\)\+\\mathcal\{L\}\_\{t\}^\{\\mathrm\{d\}\}\(\\bm\{\\theta\}\),with𝐇tc​\(𝛉\)≜∇2ℒtc​\(𝛉\)\\bm\{H\}\_\{t\}^\{\\mathrm\{c\}\}\(\\bm\{\\theta\}\)\\triangleq\\nabla^\{2\}\\mathcal\{L\}\_\{t\}^\{\\mathrm\{c\}\}\(\\bm\{\\theta\}\)and𝐇td​\(𝛉\)≜∇2ℒtd​\(𝛉\)\\bm\{H\}\_\{t\}^\{\\mathrm\{d\}\}\(\\bm\{\\theta\}\)\\triangleq\\nabla^\{2\}\\mathcal\{L\}\_\{t\}^\{\\mathrm\{d\}\}\(\\bm\{\\theta\}\)\. Let𝛉^t∈arg⁡min𝛉∈Θ⁡ℒt​\(𝛉\)\\hat\{\\bm\{\\theta\}\}\_\{t\}\\in\\arg\\min\_\{\\bm\{\\theta\}\\in\\Theta\}\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\. Then for all𝛉∈Θ\\bm\{\\theta\}\\in\\Theta,

ℒt​\(𝜽\)−ℒt​\(𝜽^t\)≥‖𝜽−𝜽^t‖𝑨t2\.\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\\geq\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\bm\{A\}\_\{t\}\}\.

###### Proof of[Lemma˜A\.2](https://arxiv.org/html/2605.05745#A1.Thmtheorem2)\.

Combining the above inequalities yields

ℒt​\(𝜽\)−ℒt​\(𝜽^t\)\\displaystyle\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)≥‖𝜽−𝜽^t‖𝑯tc​\(𝜽^t\)22​\(1\+S​Mc\)\+‖𝜽−𝜽^t‖𝑯td​\(𝜽^t\)22​\(1\+2​S​Md\)\\displaystyle\\geq\\frac\{\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\bm\{H\}\_\{t\}^\{\\mathrm\{c\}\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\}\}\{2\(1\+SM\_\{\\mathrm\{c\}\}\)\}\+\\frac\{\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\bm\{H\}\_\{t\}^\{\\mathrm\{d\}\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\}\}\{2\(1\+2SM\_\{\\mathrm\{d\}\}\)\}=\(𝜽−𝜽^t\)⊤​\(𝑯tc​\(𝜽^t\)2​\(1\+S​Mc\)\+𝑯td​\(𝜽^t\)2​\(1\+2​S​Md\)\)​\(𝜽−𝜽^t\)\\displaystyle=\(\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\)^\{\\top\}\\left\(\\frac\{\\bm\{H\}\_\{t\}^\{\\mathrm\{c\}\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\}\{2\(1\+SM\_\{\\mathrm\{c\}\}\)\}\+\\frac\{\\bm\{H\}\_\{t\}^\{\\mathrm\{d\}\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\}\{2\(1\+2SM\_\{\\mathrm\{d\}\}\)\}\\right\)\(\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\)=‖𝜽−𝜽^t‖𝑨t2,\\displaystyle=\\\|\\bm\{\\theta\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\bm\{A\}\_\{t\}\},as claimed\. ∎

###### Proof of[Theorem˜3\.3](https://arxiv.org/html/2605.05745#S3.Thmtheorem3)\.

By[Lemma˜A\.2](https://arxiv.org/html/2605.05745#A1.Thmtheorem2),

‖𝜽⋆−𝜽^t‖𝑨t2≤ℒt​\(𝜽⋆\)−ℒt​\(𝜽^t\)≤βt​\(δ\)\.\\\|\\bm\{\\theta\}^\{\\star\}\-\\hat\{\\bm\{\\theta\}\}\_\{t\}\\\|^\{2\}\_\{\\bm\{A\}\_\{t\}\}\\leq\\mathcal\{L\}\_\{t\}\(\\bm\{\\theta\}^\{\\star\}\)\-\\mathcal\{L\}\_\{t\}\(\\hat\{\\bm\{\\theta\}\}\_\{t\}\)\\leq\\beta\_\{t\}\(\\delta\)\.∎

### A\.2Proof of[Theorem˜4\.5](https://arxiv.org/html/2605.05745#S4.Thmtheorem5)

We first analyze the tracking rounds and then translate the resulting bound to the total number of rounds\. Let

nt≜\|𝒯t\|,nτ≜\|𝒯τ\|n\_\{t\}\\triangleq\|\\mathcal\{T\}\_\{t\}\|,\\qquad n\_\{\\tau\}\\triangleq\|\\mathcal\{T\}\_\{\\tau\}\|denote the number of tracking rounds up to timesttandτ\\tau, respectively\. The key tracking statement is

𝑨tnt≳𝑨​\(𝒘⋆,𝜽⋆\)a\.s\.\\frac\{\\bm\{A\}\_\{t\}\}\{n\_\{t\}\}\\gtrsim\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\\qquad\\text\{a\.s\.\}
###### Lemma A\.3\(Asymptotic tracking of an optimal design\)\.

Assume that: \(i\)𝛉^t→𝛉⋆\\hat\{\\bm\{\\theta\}\}\_\{t\}\\to\\bm\{\\theta\}^\{\\star\}a\.s\.; \(ii\) the tracking rule ensures‖𝐍𝒯​\(t\)−𝐖𝒯​\(t\)‖∞≤C\\\|\\bm\{N\}^\{\\mathcal\{T\}\}\(t\)\-\\bm\{W\}^\{\\mathcal\{T\}\}\(t\)\\\|\_\{\\infty\}\\leq C; \(iii\)𝒲⋆​\(𝛉⋆\)\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)is compact, convex, and nonempty\.

Then there exists𝐰⋆∈argmin𝐰∈Δ𝒜ϕ​\(𝐰,𝛉⋆\)\\bm\{w\}^\{\\star\}\\in\{\\mathop\{\\mathrm\{argmin\}\}\\limits\}\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\phi\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)such that

1nt​𝑨t𝒯→t→∞a\.s\.𝑨​\(𝒘⋆,𝜽⋆\)\.\\frac\{1\}\{n\_\{t\}\}\\bm\{A\}^\{\\mathcal\{T\}\}\_\{t\}\\xrightarrow\[t\\to\\infty\]\{\\mathrm\{a\.s\.\}\}\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\.Consequently,

1nt​𝑨t≳𝑨​\(𝒘⋆,𝜽⋆\)a\.s\.\\frac\{1\}\{n\_\{t\}\}\\bm\{A\}\_\{t\}\\gtrsim\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\\qquad\\text\{a\.s\.\}

We use four auxiliary lemmas to establish the asymptotic tracking statement\.

###### Lemma A\.4\(Adapted from Lemma 3 ofJedra and Proutiere \[[2020](https://arxiv.org/html/2605.05745#bib.bib31)\]\)\.

Assume that the sampling rule satisfiesliminft→∞λmin​\(t−α​𝐀t\)\>0\\lim\\inf\_\{t\\to\\infty\}\\lambda\_\{\\min\}\(t^\{\-\\alpha\}\\bm\{A\}\_\{t\}\)\>0a\.s\. for someα∈\(0,1\)\\alpha\\in\(0,1\)\. Then𝛉^t→𝛉⋆\\hat\{\\bm\{\\theta\}\}\_\{t\}\\to\\bm\{\\theta\}^\{\\star\}a\.s\.

This condition is satisfied by the exploration rounds and[Assumption˜4\.1](https://arxiv.org/html/2605.05745#S4.Thmtheorem1)\.

###### Lemma A\.5\(Adapted from Lemmas 1 and 2 ofJedra and Proutiere \[[2020](https://arxiv.org/html/2605.05745#bib.bib31)\]\)\.

The mapϕ\\phiis continuous in both𝛉\\bm\{\\theta\}and𝐰\\bm\{w\}, and it attains its minimum overΔ𝒜\\Delta\_\{\\mathcal\{A\}\}at a point𝐰⋆\\bm\{w\}^\{\\star\}such that𝐀​\(𝐰⋆,𝛉⋆\)≻0\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\\succ 0\. Let

ϕ⋆​\(𝜽⋆\)≜min𝒘∈Δ𝒜⁡ϕ​\(𝒘,𝜽⋆\),𝒲⋆​\(𝜽⋆\)≜argmin𝒘∈Δ𝒜ϕ​\(𝒘,𝜽⋆\)\.\\phi^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\min\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\phi\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\),\\qquad\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\mathop\{\\mathrm\{argmin\}\}\\limits\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\phi\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)\.Thenϕ⋆​\(⋅\)\\phi^\{\\star\}\(\\cdot\)is continuous at𝛉⋆\\bm\{\\theta\}^\{\\star\}, and𝒲⋆​\(𝛉⋆\)\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)is convex, compact, and nonempty\.

###### Lemma A\.6\(Deterministic tracking error bound; adapted from Lemma 6 ofJedra and Proutiere \[[2020](https://arxiv.org/html/2605.05745#bib.bib31)\]\)\.

Let\(𝐰s\)s≥1\(\\bm\{w\}\_\{s\}\)\_\{s\\geq 1\}be any sequence of distributions on𝒜\\mathcal\{A\}\. Let𝒯⊂ℕ\\mathcal\{T\}\\subset\\mathbb\{N\}be the set of tracking rounds and definent≜\|𝒯∩\{1,…,t\}\|n\_\{t\}\\triangleq\|\\mathcal\{T\}\\cap\\\{1,\\dots,t\\\}\|\. Suppose that on each tracking rounds∈𝒯s\\in\\mathcal\{T\},

as∈argmina∈𝒜\(Na𝒯​\(s−1\)−Wa𝒯​\(s−1\)\)\.a\_\{s\}\\in\\mathop\{\\mathrm\{argmin\}\}\\limits\_\{a\\in\\mathcal\{A\}\}\\bigl\(N^\{\\mathcal\{T\}\}\_\{a\}\(s\-1\)\-W^\{\\mathcal\{T\}\}\_\{a\}\(s\-1\)\\bigr\)\.Then there exists a constantC\>0C\>0, depending only on\|𝒜\|\|\\mathcal\{A\}\|, such that for allt≥1t\\geq 1and alla∈𝒜a\\in\\mathcal\{A\},

−C≤Na𝒯​\(t\)−Wa𝒯​\(t\)≤C\.\-C\\leq N^\{\\mathcal\{T\}\}\_\{a\}\(t\)\-W^\{\\mathcal\{T\}\}\_\{a\}\(t\)\\leq C\.Consequently,

‖𝑵𝒯​\(t\)nt−𝒘¯t𝒯‖∞≤Cnt,\\left\\\|\\frac\{\\bm\{N\}^\{\\mathcal\{T\}\}\(t\)\}\{n\_\{t\}\}\-\\bar\{\\bm\{w\}\}^\{\\mathcal\{T\}\}\_\{t\}\\right\\\|\_\{\\infty\}\\leq\\frac\{C\}\{n\_\{t\}\},where𝐰¯t𝒯≜nt−1​∑s∈𝒯∩\{1,…,t\}𝐰s\\bar\{\\bm\{w\}\}^\{\\mathcal\{T\}\}\_\{t\}\\triangleq n\_\{t\}^\{\-1\}\\sum\_\{s\\in\\mathcal\{T\}\\cap\\\{1,\\dots,t\\\}\}\\bm\{w\}\_\{s\}\.

###### Lemma A\.7\(Cesàro stability of asymptotically minimax\-optimal designs\)\.

Let\(𝐰t\)t≥1⊂Δ𝒜\(\\bm\{w\}\_\{t\}\)\_\{t\\geq 1\}\\subset\\Delta\_\{\\mathcal\{A\}\}and let𝒲⋆​\(𝛉⋆\)⊂Δ𝒜\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\subset\\Delta\_\{\\mathcal\{A\}\}be nonempty, compact, and convex\. Ifdist​\(𝐰t,𝒲⋆​\(𝛉⋆\)\)→0\\mathrm\{dist\}\(\\bm\{w\}\_\{t\},\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\)\\to 0a\.s\. and the Cesàro means converge, then there exists a \(possibly random\)𝐰⋆∈𝒲⋆​\(𝛉⋆\)\\bm\{w\}^\{\\star\}\\in\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)such that

𝒘¯t=1t​∑s=1t𝒘s→𝒘⋆a\.s\.\\bar\{\\bm\{w\}\}\_\{t\}=\\frac\{1\}\{t\}\\sum\_\{s=1\}^\{t\}\\bm\{w\}\_\{s\}\\to\\bm\{w\}^\{\\star\}\\qquad\\text\{a\.s\.\}

###### Proof\.

Fix an outcomeω\\omegafor whichdist​\(𝒘t,𝒲⋆​\(𝜽⋆\)\)→0\\mathrm\{dist\}\(\\bm\{w\}\_\{t\},\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\)\\to 0and𝒘¯t\\bar\{\\bm\{w\}\}\_\{t\}converges\. Since𝒲⋆​\(𝜽⋆\)\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)is closed and convex, every limit point of the Cesàro means lies in𝒲⋆​\(𝜽⋆\)\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\. The limit of𝒘¯t​\(ω\)\\bar\{\\bm\{w\}\}\_\{t\}\(\\omega\)is therefore some𝒘⋆∈𝒲⋆​\(𝜽⋆\)\\bm\{w\}^\{\\star\}\\in\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\. ∎

###### Proof of[Lemma˜A\.3](https://arxiv.org/html/2605.05745#A1.Thmtheorem3)\.

By[Lemma˜A\.4](https://arxiv.org/html/2605.05745#A1.Thmtheorem4),𝜽^t→𝜽⋆\\hat\{\\bm\{\\theta\}\}\_\{t\}\\to\\bm\{\\theta\}^\{\\star\}a\.s\. Together with the continuity and compactness properties in[Lemma˜A\.5](https://arxiv.org/html/2605.05745#A1.Thmtheorem5), the target designs approach the optimal set𝒲⋆​\(𝜽⋆\)\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\.[Lemma˜A\.6](https://arxiv.org/html/2605.05745#A1.Thmtheorem6)implies that the empirical tracking frequencies have the same Cesàro limit as the target designs\. Thus, by[Lemma˜A\.7](https://arxiv.org/html/2605.05745#A1.Thmtheorem7), for some𝒘⋆∈𝒲⋆​\(𝜽⋆\)\\bm\{w\}^\{\\star\}\\in\\mathcal\{W\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\),

1nt​𝑨t𝒯→t→∞a\.s\.𝑨​\(𝒘⋆,𝜽⋆\)\.\\frac\{1\}\{n\_\{t\}\}\\bm\{A\}^\{\\mathcal\{T\}\}\_\{t\}\\xrightarrow\[t\\to\\infty\]\{\\mathrm\{a\.s\.\}\}\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\.Since𝑨t⪰𝑨t𝒯\\bm\{A\}\_\{t\}\\succeq\\bm\{A\}\_\{t\}^\{\\mathcal\{T\}\}, the claimed lower bound for𝑨t/nt\\bm\{A\}\_\{t\}/n\_\{t\}follows\. ∎

###### Lemma A\.8\(Sufficient stopping condition\)\.

On the event\{𝛉⋆∈ℰt​\(δ\)\}\\\{\\bm\{\\theta\}^\{\\star\}\\in\\mathcal\{E\}\_\{t\}\(\\delta\)\\\}, the stopping rule is satisfied if

βt​\(δ\)​‖𝒙i⋆,j‖𝑨t−1<Δj2,∀j≠i⋆\.\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},j\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}<\\frac\{\\Delta\_\{j\}\}\{2\},\\qquad\\forall j\\neq i^\{\\star\}\.\(7\)

###### Proof\.

The stopping rule is satisfied when

⟨𝒙i⋆,j,𝜽^t⟩≥βt​\(δ\)​‖𝒙i⋆,j‖𝑨t−1,∀j≠i⋆\.\\langle\\bm\{x\}\_\{i^\{\\star\},j\},\\hat\{\\bm\{\\theta\}\}\_\{t\}\\rangle\\geq\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},j\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\},\\qquad\\forall j\\neq i^\{\\star\}\.On the event\{𝜽⋆∈ℰt​\(δ\)\}\\\{\\bm\{\\theta\}^\{\\star\}\\in\\mathcal\{E\}\_\{t\}\(\\delta\)\\\},

⟨𝒙i⋆,j,𝜽^t⟩\\displaystyle\\langle\\bm\{x\}\_\{i^\{\\star\},j\},\\hat\{\\bm\{\\theta\}\}\_\{t\}\\rangle≥⟨𝒙i⋆,j,𝜽⋆⟩−βt​\(δ\)​‖𝒙i⋆,j‖𝑨t−1\\displaystyle\\geq\\langle\\bm\{x\}\_\{i^\{\\star\},j\},\\bm\{\\theta\}^\{\\star\}\\rangle\-\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},j\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}=Δj−βt​\(δ\)​‖𝒙i⋆,j‖𝑨t−1\.\\displaystyle=\\Delta\_\{j\}\-\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},j\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}\.Therefore the stopping rule holds whenever

Δj−βt​\(δ\)​‖𝒙i⋆,j‖𝑨t−1\>βt​\(δ\)​‖𝒙i⋆,j‖𝑨t−1,∀j≠i⋆,\\Delta\_\{j\}\-\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},j\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}\>\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},j\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\},\\qquad\\forall j\\neq i^\{\\star\},which is exactly \([7](https://arxiv.org/html/2605.05745#A1.E7)\)\. ∎

###### Proof of[Theorem˜4\.5](https://arxiv.org/html/2605.05745#S4.Thmtheorem5)\.

By[Lemma˜A\.3](https://arxiv.org/html/2605.05745#A1.Thmtheorem3), there exists an a\.s\. finite timet0t\_\{0\}such that, for allnt≥t0n\_\{t\}\\geq t\_\{0\}and everyi≠i⋆i\\neq i^\{\\star\},

nt​‖𝒙i⋆,i‖𝑨t−12≤2​‖𝒙i⋆,i‖𝑨​\(𝒘⋆,𝜽⋆\)−12\.n\_\{t\}\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}^\{2\}\\leq 2\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}^\{2\}\.Equivalently,

‖𝒙i⋆,i‖𝑨t−1≤2nt​‖𝒙i⋆,i‖𝑨​\(𝒘⋆,𝜽⋆\)−1\.\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}\\leq\\sqrt\{\\frac\{2\}\{n\_\{t\}\}\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\.Combining this with[Lemma˜A\.8](https://arxiv.org/html/2605.05745#A1.Thmtheorem8), it suffices that

βt​\(δ\)​2nt​‖𝒙i⋆,i‖𝑨​\(𝒘⋆,𝜽⋆\)−1<Δmin2,\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\sqrt\{\\frac\{2\}\{n\_\{t\}\}\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}<\\frac\{\\Delta\_\{\\min\}\}\{2\},or, equivalently,

nt\>8​βt​\(δ\)​‖𝒙i⋆,i‖𝑨​\(𝒘⋆,𝜽⋆\)−12Δmin2=8​βt​\(δ\)​T⋆​\(𝜽⋆\)\.n\_\{t\}\>8\\,\\beta\_\{t\}\(\\delta\)\\frac\{\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}^\{2\}\}\{\\Delta\_\{\\min\}^\{2\}\}=8\\,\\beta\_\{t\}\(\\delta\)T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\.
Letmt≜t−ntm\_\{t\}\\triangleq t\-n\_\{t\}be the number of forced exploration rounds up to timett\. Then

𝔼​\[mt\]=∑s=1ts−α≈t1−α1−α,α∈\(0,1\)\.\\mathbb\{E\}\[m\_\{t\}\]=\\sum\_\{s=1\}^\{t\}s^\{\-\\alpha\}\\approx\\frac\{t^\{1\-\\alpha\}\}\{1\-\\alpha\},\\qquad\\alpha\\in\(0,1\)\.Sincemt\+nt=tm\_\{t\}\+n\_\{t\}=t, we havemt/nt→0m\_\{t\}/n\_\{t\}\\to 0and hencet<2​ntt<2n\_\{t\}for all sufficiently largett\. Usingβt​\(δ\)≤c0​log⁡\(1/δ\)\+c1​d​log⁡\(1\+t\)\\beta\_\{t\}\(\\delta\)\\leq c\_\{0\}\\log\(1/\\delta\)\+c\_\{1\}d\\log\(1\+t\), it is therefore enough that

nt\>8​c0​T⋆​\(𝜽⋆\)​log⁡1δ\+8​c1​T⋆​\(𝜽⋆\)​d​log⁡\(1\+nt\)\.n\_\{t\}\>8c\_\{0\}T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\log\\frac\{1\}\{\\delta\}\+8c\_\{1\}T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)d\\log\(1\+n\_\{t\}\)\.A standard fixed\-point argument gives that, for a constantC\>0C\>0depending only onc0,c1c\_\{0\},c\_\{1\}, any

nt\>C​T⋆​\(𝜽⋆\)​\(log⁡1δ\+d​log⁡T⋆​\(𝜽⋆\)\+d​log⁡log⁡eδ\)\+O​\(1\)n\_\{t\}\>CT^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\left\(\\log\\frac\{1\}\{\\delta\}\+d\\log T^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\+d\\log\\log\\frac\{e\}\{\\delta\}\\right\)\+O\(1\)satisfies the previous display\. The negligible exploration factor is absorbed into the constantCC\.

SincePr⁡\[𝜽⋆∈ℰt​\(δ\)\]≥1−δ\\Pr\[\\bm\{\\theta\}^\{\\star\}\\in\\mathcal\{E\}\_\{t\}\(\\delta\)\]\\geq 1\-\\delta, the claimed bound onτ\\tauholds with probability at least1−δ1\-\\delta\. ∎

### A\.3Proof of[Theorem˜4\.7](https://arxiv.org/html/2605.05745#S4.Thmtheorem7)

###### Proof\.

The proof follows the same stopping argument as[Theorem˜4\.5](https://arxiv.org/html/2605.05745#S4.Thmtheorem5), with the per\-round design replaced by a cost\-normalized design\. Let𝒑⋆∈argmin𝒑≥0:⟨𝒄,𝒑⟩=1maxi≠i⋆⁡‖𝒙i⋆,i‖𝑨​\(𝒑,𝜽⋆\)−12\\bm\{p\}^\{\\star\}\\in\{\\mathop\{\\mathrm\{argmin\}\}\\limits\}\_\{\\bm\{p\}\\geq 0:\\langle\\bm\{c\},\\bm\{p\}\\rangle=1\}\\max\_\{i\\neq i^\{\\star\}\}\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|^\{2\}\_\{\\bm\{A\}\(\\bm\{p\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\. Write

P⋆≜∑a∈𝒜pa⋆,𝒘⋆≜𝒑⋆P⋆∈Δ𝒜\.P^\{\\star\}\\triangleq\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}^\{\\star\},\\qquad\\bm\{w\}^\{\\star\}\\triangleq\\frac\{\\bm\{p\}^\{\\star\}\}\{P^\{\\star\}\}\\in\\Delta\_\{\\mathcal\{A\}\}\.If the round\-based tracking rule tracks𝒘⋆\\bm\{w\}^\{\\star\}, then the average cost per tracking round converges to

⟨𝒄,𝒘⋆⟩=⟨𝒄,𝒑⋆⟩P⋆=1P⋆\.\\langle\\bm\{c\},\\bm\{w\}^\{\\star\}\\rangle=\\frac\{\\langle\\bm\{c\},\\bm\{p\}^\{\\star\}\\rangle\}\{P^\{\\star\}\}=\\frac\{1\}\{P^\{\\star\}\}\.Consequently, ifBt𝒯B\_\{t\}^\{\\mathcal\{T\}\}denotes the cost spent on tracking rounds, thenBt𝒯/nt→1/P⋆B\_\{t\}^\{\\mathcal\{T\}\}/n\_\{t\}\\to 1/P^\{\\star\}\. Since𝑨​\(⋅,𝜽\)\\bm\{A\}\(\\cdot,\\bm\{\\theta\}\)is linear in the design weights,

𝑨​\(𝒘⋆,𝜽⋆\)=1P⋆​𝑨​\(𝒑⋆,𝜽⋆\)\.\\bm\{A\}\(\\bm\{w\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)=\\frac\{1\}\{P^\{\\star\}\}\\bm\{A\}\(\\bm\{p\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\.Combining this identity with the tracking statement in[Lemma˜A\.3](https://arxiv.org/html/2605.05745#A1.Thmtheorem3)yields the cost\-normalized information lower bound

𝑨tBt≳𝑨​\(𝒑⋆,𝜽⋆\)a\.s\.,\\frac\{\\bm\{A\}\_\{t\}\}\{B\_\{t\}\}\\gtrsim\\bm\{A\}\(\\bm\{p\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)\\qquad\\text\{a\.s\.\},where the vanishing forced\-exploration rounds are absorbed into the asymptotic inequality because the action costs are finite and strictly positive on the finite action set\.

On the event\{𝜽⋆∈ℰt​\(δ\)\}\\\{\\bm\{\\theta\}^\{\\star\}\\in\\mathcal\{E\}\_\{t\}\(\\delta\)\\\},[Lemma˜A\.8](https://arxiv.org/html/2605.05745#A1.Thmtheorem8)shows that the stopping rule is satisfied whenever, for alli≠i⋆i\\neq i^\{\\star\},

βt​\(δ\)​‖𝒙i⋆,i‖𝑨t−1<Δmin2\.\\sqrt\{\\beta\_\{t\}\(\\delta\)\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}<\\frac\{\\Delta\_\{\\min\}\}\{2\}\.By the cost\-normalized information bound, for all sufficiently largett,

‖𝒙i⋆,i‖𝑨t−1≤2Bt​‖𝒙i⋆,i‖𝑨​\(𝒑⋆,𝜽⋆\)−1\.\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\_\{t\}^\{\-1\}\}\\leq\\sqrt\{\\frac\{2\}\{B\_\{t\}\}\}\\,\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|\_\{\\bm\{A\}\(\\bm\{p\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\.Thus it is sufficient that

Bt\>8​βt​\(δ\)​‖𝒙i⋆,i‖𝑨​\(𝒑⋆,𝜽⋆\)−12Δmin2≤8​βt​\(δ\)​Tcost⋆​\(𝜽⋆\)\.B\_\{t\}\>8\\,\\beta\_\{t\}\(\\delta\)\\frac\{\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|^\{2\}\_\{\\bm\{A\}\(\\bm\{p\}^\{\\star\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\}\{\\Delta\_\{\\min\}^\{2\}\}\\leq 8\\,\\beta\_\{t\}\(\\delta\)T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\.Letcmin≜mina∈𝒜⁡ca\>0c\_\{\\min\}\\triangleq\\min\_\{a\\in\\mathcal\{A\}\}c\_\{a\}\>0\. SinceBt≥cmin​tB\_\{t\}\\geq c\_\{\\min\}t, the logarithmic term inβt​\(δ\)\\beta\_\{t\}\(\\delta\)can be bounded by a logarithm ofBtB\_\{t\}up to constants depending only on the cost vector\. Usingβt​\(δ\)≤c0​log⁡\(1/δ\)\+c1​d​log⁡\(1\+t\)\\beta\_\{t\}\(\\delta\)\\leq c\_\{0\}\\log\(1/\\delta\)\+c\_\{1\}d\\log\(1\+t\)and the same fixed\-point argument as in the proof of[Theorem˜4\.5](https://arxiv.org/html/2605.05745#S4.Thmtheorem5), it is enough that

Bt\>C​Tcost⋆​\(𝜽⋆\)​\(log⁡1δ\+d​log⁡Tcost⋆​\(𝜽⋆\)\+d​log⁡log⁡eδ\)\+O​\(1\),B\_\{t\}\>CT\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\left\(\\log\\frac\{1\}\{\\delta\}\+d\\log T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\+d\\log\\log\\frac\{e\}\{\\delta\}\\right\)\+O\(1\),for a constantC\>0C\>0depending only on the confidence\-radius constants and the bounded cost vector\. Therefore, with probability at least1−δ1\-\\delta,

Bτ≲Tcost⋆​\(𝜽⋆\)​\(log⁡1δ\+d​log⁡Tcost⋆​\(𝜽⋆\)\+d​log⁡log⁡eδ\),B\_\{\\tau\}\\lesssim T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\\left\(\\log\\frac\{1\}\{\\delta\}\+d\\log T\_\{\\mathrm\{cost\}\}^\{\\star\}\(\\bm\{\\theta\}^\{\\star\}\)\+d\\log\\log\\frac\{e\}\{\\delta\}\\right\),as claimed\. ∎

## Appendix BAdditional Discussions

This section places our results in the broader landscape of fixed\-confidence best\-arm identification \(BAI\), with emphasis on how the information geometry changes from stochastic and linear bandits to generalized linear models \(GLMs\)\.

### B\.1A Common Lower\-Bound Principle

Across pure\-exploration bandit models, fixed\-confidence lower bounds are based on the same change\-of\-measure principle: aδ\\delta\-correct algorithm must collect enough evidence to distinguish the true instance from every alternative instance under which a different arm is optimal\. Let𝒫⋆\\mathcal\{P\}^\{\\star\}denote the true instance and letAlt​\(𝒫⋆\)\\mathrm\{Alt\}\(\\mathcal\{P\}^\{\\star\}\)be the set of alternatives with a different best arm\. For any𝒫′∈Alt​\(𝒫⋆\)\\mathcal\{P\}^\{\\prime\}\\in\\mathrm\{Alt\}\(\\mathcal\{P\}^\{\\star\}\), a necessary condition takes the form

∑x∈𝒳𝔼𝒫⋆​\[Nx​\(τ\)\]​KL​\(Px⋆∥Px′\)≳log⁡\(1δ\),\\sum\_\{x\\in\\mathcal\{X\}\}\\mathbb\{E\}\_\{\\mathcal\{P\}^\{\\star\}\}\[N\_\{x\}\(\\tau\)\]\\,\\mathrm\{KL\}\(P\_\{x\}^\{\\star\}\\,\\\|\\,P\_\{x\}^\{\\prime\}\)\\;\\gtrsim\\;\\log\\\!\\left\(\\frac\{1\}\{\\delta\}\\right\),\(8\)wherePx⋆P\_\{x\}^\{\\star\}andPx′P\_\{x\}^\{\\prime\}are the observation laws for queryxxunder the true and alternative instances\.

The role of \([8](https://arxiv.org/html/2605.05745#A2.E8)\) is conceptually simple: every incorrect hypothesis must receive enough statistical evidence against it\. What differs across models is the structure of the per\-sample information termKL​\(Px⋆∥Px′\)\\mathrm\{KL\}\(P\_\{x\}^\{\\star\}\\,\\\|\\,P\_\{x\}^\{\\prime\}\)\. When this term has a tractable quadratic form, lower bounds can often be written as finite\-dimensional experimental\-design problems\. When the term depends nonlinearly on an unknown global parameter, as in GLMs, the same principle remains valid but becomes much harder to evaluate and optimize\.

We now instantiate this principle for the hybrid GLM model\. Following the notation in[Section˜2](https://arxiv.org/html/2605.05745#S2),m​\(a\)m\(a\)denotes the feedback modality of actiona∈𝒜a\\in\\mathcal\{A\}\. For two parameters𝜽,𝝀∈Θ\\bm\{\\theta\},\\bm\{\\lambda\}\\in\\Theta, let

da\(𝜽,𝝀\)≜KL\(pm​\(a\)\(⋅∣𝒙a⊤𝜽\)∥pm​\(a\)\(⋅∣𝒙a⊤𝝀\)\)\.d\_\{a\}\(\\bm\{\\theta\},\\bm\{\\lambda\}\)\\triangleq\\mathrm\{KL\}\\\!\\left\(p\_\{m\(a\)\}\(\\cdot\\mid\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}\)\\,\\middle\\\|\\,p\_\{m\(a\)\}\(\\cdot\\mid\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\lambda\}\)\\right\)\.By the exponential\-family form in \([1](https://arxiv.org/html/2605.05745#S2.E1)\),

da​\(𝜽,𝝀\)=bm​\(a\)​\(𝒙a⊤​𝝀\)−bm​\(a\)​\(𝒙a⊤​𝜽\)−μm​\(a\)​\(𝒙a⊤​𝜽\)​𝒙a⊤​\(𝝀−𝜽\)ζm​\(a\)​\(φm​\(a\)\)\.d\_\{a\}\(\\bm\{\\theta\},\\bm\{\\lambda\}\)=\\frac\{b\_\{m\(a\)\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\lambda\}\)\-b\_\{m\(a\)\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}\)\-\\mu\_\{m\(a\)\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}\)\\bm\{x\}\_\{a\}^\{\\top\}\(\\bm\{\\lambda\}\-\\bm\{\\theta\}\)\}\{\\zeta\_\{m\(a\)\}\(\\varphi\_\{m\(a\)\}\)\}\.Let

Alt​\(𝜽⋆\)≜\{𝝀∈Θ:argmaxi∈𝒦𝒙i⊤​𝝀≠i⋆\}\\mathrm\{Alt\}\(\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\\{\\bm\{\\lambda\}\\in\\Theta:\{\\mathop\{\\mathrm\{argmax\}\}\\limits\}\_\{i\\in\\mathcal\{K\}\}\\bm\{x\}\_\{i\}^\{\\top\}\\bm\{\\lambda\}\\neq i^\{\\star\}\\\}be the set of parameters under which the best arm is noti⋆i^\{\\star\}, with ties broken arbitrarily using the same rule as the recommendation rule\.

###### Theorem B\.1\(Information\-theoretic lower bound for hybrid GLM BAI\)\.

For anyδ\\delta\-correct algorithm and any𝛉⋆∈Θ\\bm\{\\theta\}^\{\\star\}\\in\\Thetawith a unique best arm,

𝔼𝜽⋆​\[τ\]≥kl​\(δ,1−δ\)sup𝒘∈Δ𝒜inf𝝀∈Alt​\(𝜽⋆\)∑a∈𝒜wa​da​\(𝜽⋆,𝝀\),\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[\\tau\]\\geq\\frac\{\\mathrm\{kl\}\(\\delta,1\-\\delta\)\}\{\\displaystyle\\sup\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\inf\_\{\\bm\{\\lambda\}\\in\\mathrm\{Alt\}\(\\bm\{\\theta\}^\{\\star\}\)\}\\sum\_\{a\\in\\mathcal\{A\}\}w\_\{a\}d\_\{a\}\(\\bm\{\\theta\}^\{\\star\},\\bm\{\\lambda\}\)\},wherekl​\(p,q\)\\mathrm\{kl\}\(p,q\)denotes the binary relative entropy\. Consequently, asδ→0\\delta\\to 0,

lim infδ→0𝔼𝜽⋆​\[τ\]log⁡\(1/δ\)≥TLB​\(𝜽⋆\),TLB​\(𝜽⋆\)≜\[sup𝒘∈Δ𝒜inf𝝀∈Alt​\(𝜽⋆\)∑a∈𝒜wa​da​\(𝜽⋆,𝝀\)\]−1\.\\liminf\_\{\\delta\\to 0\}\\frac\{\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[\\tau\]\}\{\\log\(1/\\delta\)\}\\geq T\_\{\\mathrm\{LB\}\}\(\\bm\{\\theta\}^\{\\star\}\),\\qquad T\_\{\\mathrm\{LB\}\}\(\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\left\[\\sup\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\inf\_\{\\bm\{\\lambda\}\\in\\mathrm\{Alt\}\(\\bm\{\\theta\}^\{\\star\}\)\}\\sum\_\{a\\in\\mathcal\{A\}\}w\_\{a\}d\_\{a\}\(\\bm\{\\theta\}^\{\\star\},\\bm\{\\lambda\}\)\\right\]^\{\-1\}\.

###### Proof\.

If𝔼𝜽⋆​\[τ\]=\+∞\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[\\tau\]=\+\\infty, the claim is trivial\. Hence assume𝔼𝜽⋆​\[τ\]<\+∞\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[\\tau\]<\+\\infty\. Fix an alternative parameter𝝀∈Alt​\(𝜽⋆\)\\bm\{\\lambda\}\\in\\mathrm\{Alt\}\(\\bm\{\\theta\}^\{\\star\}\)\. By the transportation lemma forδ\\delta\-correct pure\-exploration algorithms\[Kaufmannet al\.,[2016](https://arxiv.org/html/2605.05745#bib.bib23)\], applied to the event that the algorithm recommendsi⋆i^\{\\star\}, we have

∑a∈𝒜𝔼𝜽⋆​\[Na​\(τ\)\]​da​\(𝜽⋆,𝝀\)≥kl​\(1−δ,δ\)=kl​\(δ,1−δ\)\.\\sum\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[N\_\{a\}\(\\tau\)\]d\_\{a\}\(\\bm\{\\theta\}^\{\\star\},\\bm\{\\lambda\}\)\\geq\\mathrm\{kl\}\(1\-\\delta,\\delta\)=\\mathrm\{kl\}\(\\delta,1\-\\delta\)\.Letn=𝔼𝜽⋆​\[τ\]n=\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[\\tau\]andwa=𝔼𝜽⋆​\[Na​\(τ\)\]/nw\_\{a\}=\\mathbb\{E\}\_\{\\bm\{\\theta\}^\{\\star\}\}\[N\_\{a\}\(\\tau\)\]/n\. Then𝒘∈Δ𝒜\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}and, since the last display holds for every alternative,

n​inf𝝀∈Alt​\(𝜽⋆\)∑a∈𝒜wa​da​\(𝜽⋆,𝝀\)≥kl​\(δ,1−δ\)\.n\\inf\_\{\\bm\{\\lambda\}\\in\\mathrm\{Alt\}\(\\bm\{\\theta\}^\{\\star\}\)\}\\sum\_\{a\\in\\mathcal\{A\}\}w\_\{a\}d\_\{a\}\(\\bm\{\\theta\}^\{\\star\},\\bm\{\\lambda\}\)\\geq\\mathrm\{kl\}\(\\delta,1\-\\delta\)\.The denominator is upper bounded by the supremum over all designs𝒘∈Δ𝒜\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}, which gives the claimed finite\-δ\\deltabound\. The asymptotic statement follows fromkl​\(δ,1−δ\)∼log⁡\(1/δ\)\\mathrm\{kl\}\(\\delta,1\-\\delta\)\\sim\\log\(1/\\delta\)\. ∎

This lower bound is exact at the level of KL information, but it is generally nonlinear in the alternative parameter𝝀\\bm\{\\lambda\}\. A local quadratic form is obtained by expanding the KL divergence around𝜽⋆\\bm\{\\theta\}^\{\\star\}\. Define the local Fisher version of the hybrid design matrix as

𝑨F​\(𝒘,𝜽⋆\)≜∑a∈𝒜wa​μm​\(a\)′​\(𝒙a⊤​𝜽⋆\)ζm​\(a\)​\(φm​\(a\)\)​𝒙a​𝒙a⊤\.\\bm\{A\}\_\{\\mathrm\{F\}\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)\\triangleq\\sum\_\{a\\in\\mathcal\{A\}\}w\_\{a\}\\frac\{\\mu\_\{m\(a\)\}^\{\\prime\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\)\}\{\\zeta\_\{m\(a\)\}\(\\varphi\_\{m\(a\)\}\)\}\\bm\{x\}\_\{a\}\\bm\{x\}\_\{a\}^\{\\top\}\.For local alternatives,

∑a∈𝒜wa​da​\(𝜽⋆,𝝀\)=12​‖𝝀−𝜽⋆‖𝑨F​\(𝒘,𝜽⋆\)2\+o​\(‖𝝀−𝜽⋆‖2\)\.\\sum\_\{a\\in\\mathcal\{A\}\}w\_\{a\}d\_\{a\}\(\\bm\{\\theta\}^\{\\star\},\\bm\{\\lambda\}\)=\\frac\{1\}\{2\}\\\|\\bm\{\\lambda\}\-\\bm\{\\theta\}^\{\\star\}\\\|^\{2\}\_\{\\bm\{A\}\_\{\\mathrm\{F\}\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)\}\+o\(\\\|\\bm\{\\lambda\}\-\\bm\{\\theta\}^\{\\star\}\\\|^\{2\}\)\.If𝜽⋆\\bm\{\\theta\}^\{\\star\}is an interior point ofΘ\\Thetaand the closest alternatives are obtained by crossing one decision boundary𝒙i⋆,i⊤​𝝀≤0\\bm\{x\}\_\{i^\{\\star\},i\}^\{\\top\}\\bm\{\\lambda\}\\leq 0, the quadratic relaxation gives

inf𝝀:𝒙i⋆,i⊤​𝝀≤012​‖𝝀−𝜽⋆‖𝑨F​\(𝒘,𝜽⋆\)2=Δi22​‖𝒙i⋆,i‖𝑨F​\(𝒘,𝜽⋆\)−12,\\inf\_\{\\bm\{\\lambda\}:\\,\\bm\{x\}\_\{i^\{\\star\},i\}^\{\\top\}\\bm\{\\lambda\}\\leq 0\}\\frac\{1\}\{2\}\\\|\\bm\{\\lambda\}\-\\bm\{\\theta\}^\{\\star\}\\\|^\{2\}\_\{\\bm\{A\}\_\{\\mathrm\{F\}\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)\}=\\frac\{\\Delta\_\{i\}^\{2\}\}\{2\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|^\{2\}\_\{\\bm\{A\}\_\{\\mathrm\{F\}\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\},whereΔi=𝒙i⋆,i⊤​𝜽⋆\\Delta\_\{i\}=\\bm\{x\}\_\{i^\{\\star\},i\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\. Thus the local oracle characteristic time is

Tloc​\(𝜽⋆\)=2​inf𝒘∈Δ𝒜maxi≠i⋆⁡‖𝒙i⋆,i‖𝑨F​\(𝒘,𝜽⋆\)−12Δi2\.T\_\{\\mathrm\{loc\}\}\(\\bm\{\\theta\}^\{\\star\}\)=2\\inf\_\{\\bm\{w\}\\in\\Delta\_\{\\mathcal\{A\}\}\}\\max\_\{i\\neq i^\{\\star\}\}\\frac\{\\\|\\bm\{x\}\_\{i^\{\\star\},i\}\\\|^\{2\}\_\{\\bm\{A\}\_\{\\mathrm\{F\}\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)^\{\-1\}\}\}\{\\Delta\_\{i\}^\{2\}\}\.This expression has the same experimental\-design structure as the characteristic time used by HyTS\-GLB, but with the true Fisher information matrix and arm\-dependent gaps\. Thus, the lower\-bound discussion should be interpreted as a local comparison rather than a full instance\-optimality result for hybrid GLMs\. It shows that the confidence\-induced design tracked by HyTS\-GLB is aligned with the minimax structure suggested by the local KL lower bound, while the matrix𝑨​\(𝒘,𝜽⋆\)\\bm\{A\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)in our upper bound is a conservative self\-concordant lower approximation of𝑨F​\(𝒘,𝜽⋆\)\\bm\{A\}\_\{\\mathrm\{F\}\}\(\\bm\{w\},\\bm\{\\theta\}^\{\\star\}\)\. This explains why our stopping\-time guarantee carries conservative constants and logarithmic factors\.

The oracle design induced byTloc​\(𝜽⋆\)T\_\{\\mathrm\{loc\}\}\(\\bm\{\\theta\}^\{\\star\}\)is not directly implementable in the GLM setting\. The main obstruction, compared with homoscedastic linear bandits, is that the information matrix itself depends on the unknown parameter through the local curvaturesμm​\(a\)′​\(𝒙a⊤​𝜽⋆\)\\mu\_\{m\(a\)\}^\{\\prime\}\(\\bm\{x\}\_\{a\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}\)\. In linear Gaussian bandits this curvature is constant, so the design geometry is fixed by the known features and can be separated from parameter estimation\. In hybrid GLMs, by contrast, the most informative actions depend on where𝜽⋆\\bm\{\\theta\}^\{\\star\}lies through both the reward and dueling links, in addition to the unknown best arm and gapsΔi\\Delta\_\{i\}\. These quantities are precisely what the learner must infer during the best\-arm\-identification process\. HyTS\-GLB therefore uses a plug\-in, confidence\-induced minimax design based on the current estimate𝜽^t\\hat\{\\bm\{\\theta\}\}\_\{t\}and tracks the corresponding allocation online\. This makes the sampling rule implementable while preserving fixed\-confidence correctness through the time\-uniform confidence sequence\.

### B\.2Comparisons and Extensions

Relation toLeeet al\.\[[2024](https://arxiv.org/html/2605.05745#bib.bib33)\]\.

Our confidence construction builds on the self\-concordant likelihood\-ratio analysis ofLeeet al\.\[[2024](https://arxiv.org/html/2605.05745#bib.bib33)\], but adapts it to a heterogeneous feedback model\. In their setting, observations are generated from a single generalized linear model\. In contrast, our model combines reward and dueling observations, each with its own link function, dispersion scale, and curvature contribution\. The resulting confidence ellipsoid therefore aggregates two modality\-specific Hessian terms, weighted by the realized sampling frequencies\. This distinction is important: the confidence set does not merely pool observations, but preserves the information geometry of each feedback channel\.

Relation toJunet al\.\[[2021](https://arxiv.org/html/2605.05745#bib.bib32)\]\.

The work ofJunet al\.\[[2021](https://arxiv.org/html/2605.05745#bib.bib32)\]also studies best\-arm identification with both reward and comparison feedback, but under a more specialized logistic structure\. Their analysis treats the feedback through a logistic\-bandit model and develops curvature\-aware confidence bounds to control the difficulty caused by vanishing Fisher information\. Our formulation is broader in two respects\. First, it allows reward and dueling feedback to follow potentially different GLM observation models\. Second, it combines the two modalities through a unified likelihood\-ratio confidence sequence rather than reducing the problem to a single logistic likelihood\. Thus, the two approaches are complementary: RAGE\-GLM provides a refined algorithmic treatment for logistic\-type models, while our framework emphasizes a general mechanism for fusing heterogeneous GLM feedback\.

Possible extensions\.

The proposed framework is modular\. The confidence sequence can be paired with allocation rules other than the minimax\-optimal tracking rule used in HyTS\-GLB, including variants inspired by RAGE\-GLM\[Junet al\.,[2021](https://arxiv.org/html/2605.05745#bib.bib32)\]or by future instance\-optimal GLM designs\. It can also accommodate cost\-aware sampling, as discussed in the main text, by replacing per\-round information with cost\-normalized information\.

Another promising direction is to sharpen the connection between our design criterion and information\-theoretic lower bounds for general GLM BAI\. Recent work such as Log\-TS\[Rivera and Tewari,[2024](https://arxiv.org/html/2605.05745#bib.bib30)\]suggests that approximate instance\-specific objectives may be tractable in logistic models\. However, the effect of the approximation and its interaction with hybrid feedback require further investigation\. Our framework is flexible enough to incorporate such allocation rules once their guarantees are established in the heterogeneous\-feedback setting\. Overall, this suggests a path toward more refined hybrid BAI algorithms without changing the underlying confidence\-sequence machinery\.

### B\.3Limitations

Our results rely on several structural assumptions that are standard in generalized linear bandit analysis but may be restrictive in some applications\. The confidence construction assumes correctly specified GLM observation models, bounded parameters and features, self\-concordance, and a curvature lower bound on the relevant domain\. These conditions ensure that the likelihood\-ratio confidence sequence can be converted into an explicit ellipsoid and that each exploration action provides non\-vanishing information\. When feedback is misspecified, heavy\-tailed, strategically biased, or generated from non\-stationary users, additional robustness tools would be needed\.

The optimality guarantees should also be interpreted with respect to the confidence\-width design criterion used in HyTS\-GLB\. For general GLMs, the exact information\-theoretic lower bound is nonlinear in the alternative parameter and is difficult to optimize globally\. We therefore connect our design to a local quadratic relaxation of the KL lower bound, while the finite\-time stopping guarantee carries conservative constants and logarithmic factors\. Closing this gap and obtaining fully instance\-optimal hybrid GLM BAI algorithms remain open problems\.

From a computational perspective, the algorithm requires repeated MLE updates and repeated solutions of a minimax design problem over the enlarged action space𝒜=𝒦∪𝒢\\mathcal\{A\}=\\mathcal\{K\}\\cup\\mathcal\{G\}\. Since\|𝒢\|=O​\(K2\)\|\\mathcal\{G\}\|=O\(K^\{2\}\), exact optimization can become expensive for large arm sets\. Our experiments use Frank–Wolfe updates to make the design computation practical, but scaling to very large candidate sets may require pair screening, lazy updates, or approximate design oracles\.

Finally, the empirical evaluation is synthetic and focuses on logistic observation models\. The experiments are intended to isolate the information\-geometric behavior of hybrid feedback rather than to validate deployment in a specific application\. Real interactive systems may involve changing feedback costs, contextual effects, abstentions, correlated comparisons, or richer preference signals; extending the theory and experiments to these settings is an important direction for future work\.

## Appendix CAdditional Experiments

We present two additional synthetic experiments that complement the random\-arm results in[Section˜5](https://arxiv.org/html/2605.05745#S5)\. All experiments use the same logistic observation model, confidence level, implementation of the stopping rule, and Frank–Wolfe design solver as in the main text\. The goal is to test whether the proposed hybrid allocation remains competitive beyond the main random construction, and to illustrate how its behavior changes with the geometry and scale of the instance\.

Basis\-plus\-rotated\-arm construction\.In[Figure˜2](https://arxiv.org/html/2605.05745#A3.F2)\(a\), the arm set is

𝒳=\{𝒆1,𝒆2,…,𝒆d,cos⁡\(0\.1\)​𝒆1\+sin⁡\(0\.1\)​𝒆2\},\\mathcal\{X\}=\\\{\\bm\{e\}\_\{1\},\\bm\{e\}\_\{2\},\\ldots,\\bm\{e\}\_\{d\},\\cos\(0\.1\)\\bm\{e\}\_\{1\}\+\\sin\(0\.1\)\\bm\{e\}\_\{2\}\\\},withd∈\{2,3,4,5,6,7,8\}d\\in\\\{2,3,4,5,6,7,8\\\}andS=5S=5\. This instance creates a hard comparison between the best basis arm and a nearby rotated arm\. The relevant separating direction has a small component along𝒆1−cos⁡\(0\.1\)​𝒆1\\bm\{e\}\_\{1\}\-\\cos\(0\.1\)\\bm\{e\}\_\{1\}and a larger component along𝒆2\\bm\{e\}\_\{2\}, so reward queries on basis arms can be highly informative even when the final decision is pairwise\. We do not report the dueling\-only variant because it required more than20,000,00020,\\\!000,\\\!000samples in this construction, exceeding our computational limit\. As shown in[Figure˜2](https://arxiv.org/html/2605.05745#A3.F2)\(a\), HyTS\-GLB remains close to the best\-performing baseline across dimensions and improves over Rage\-GLM and the random hybrid baseline in most settings\. This indicates that the hybrid design does not rely on the random geometry used in the main experiment\.

Effect of the parameter scale\.In[Figure˜2](https://arxiv.org/html/2605.05745#A3.F2)\(b\), we return to the random\-arm construction from the main text, fix\(K,d\)=\(5,4\)\(K,d\)=\(5,4\), and varyS∈\{2,3,4,5\}S\\in\\\{2,3,4,5\\\}\. ChangingSSchanges the magnitude of the linear scores and therefore the local curvature of the logistic model\. This is a useful stress test for GLM bandits because saturated regions can make some observations much less informative\. HyTS\-GLB achieves the smallest mean stopping time for all tested values ofSS, with the largest relative gains at largerSS\. The result suggests that adaptively combining absolute and relative observations is particularly helpful when the curvature varies across actions and feedback types\.

Overall, these additional experiments support the conclusions of[Section˜5](https://arxiv.org/html/2605.05745#S5): HyTS\-GLB is competitive with specialized logistic\-bandit baselines on structured arm sets and can outperform them on random arm sets, despite being designed for the more general hybrid GLM setting\.

22334455667788105\.510^\{5\.5\}10610^\{6\}DimensionStopping TimeRage\-GLMRandomReTS\-GLBHyTS\-GLB\(a\)Basis\_Batch arm construction withS=5S=522334455104\.510^\{4\.5\}10510^\{5\}105\.510^\{5\.5\}ParameterSSStopping TimeRage\-GLMReTS\-GLBRandomDuelTS\-GLBHyTS\-GLB\(b\)Random\-arm construction with fixed\(K,d\)=\(5,4\)\(K,d\)=\(5,4\)and varyingSS
Figure 2:Additional experiments\.
## Appendix DConcrete Complexity Comparisons

We give two logistic examples that specialize the leading complexity terms to reward\-only and dueling\-only feedback\. Throughout this section, letμc=μd=σ\\mu\_\{\\mathrm\{c\}\}=\\mu\_\{\\mathrm\{d\}\}=\\sigma,𝜽⋆=\(1,0\)⊤\\bm\{\\theta\}^\{\\star\}=\(1,0\)^\{\\top\}, and

Bc≜2​\(1\+S​Mc\)​ζc​\(φc\),Bd≜2​\(1\+2​S​Md\)​ζd​\(φd\)\.B\_\{\\mathrm\{c\}\}\\triangleq 2\(1\+SM\_\{\\mathrm\{c\}\}\)\\zeta\_\{\\mathrm\{c\}\}\(\\varphi\_\{\\mathrm\{c\}\}\),\\qquad B\_\{\\mathrm\{d\}\}\\triangleq 2\(1\+2SM\_\{\\mathrm\{d\}\}\)\\zeta\_\{\\mathrm\{d\}\}\(\\varphi\_\{\\mathrm\{d\}\}\)\.The leading sample complexity is of order

O~​\(T​log⁡1δ\),\\widetilde\{O\}\\\!\\left\(T\\log\\frac\{1\}\{\\delta\}\\right\),whereTTis the corresponding characteristic term\.

### D\.1Case 1: Dueling Feedback is More Informative

LetK=d=2K=d=2,𝒙1=𝒆1\\bm\{x\}\_\{1\}=\\bm\{e\}\_\{1\}, and𝒙2=−𝒆2\\bm\{x\}\_\{2\}=\-\\bm\{e\}\_\{2\}\. Then arm11is optimal and

𝒈12≜𝒙1−𝒙2=\(1,1\)⊤,Δ12≜𝒈12⊤​𝜽⋆=1\.\\bm\{g\}\_\{12\}\\triangleq\\bm\{x\}\_\{1\}\-\\bm\{x\}\_\{2\}=\(1,1\)^\{\\top\},\\qquad\\Delta\_\{12\}\\triangleq\\bm\{g\}\_\{12\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}=1\.
Reward\-only\.Reward feedback estimates the two coordinates separately\. With reward weightsw1\+w2=1w\_\{1\}\+w\_\{2\}=1,

𝑨R​\(w1,w2\)=\(σ′​\(1\)​w1/Bc00σ′​\(0\)​w2/Bc\)\.\\bm\{A\}\_\{\\rm R\}\(w\_\{1\},w\_\{2\}\)=\\begin\{pmatrix\}\\sigma^\{\\prime\}\(1\)w\_\{1\}/B\_\{\\mathrm\{c\}\}&0\\\\ 0&\\sigma^\{\\prime\}\(0\)w\_\{2\}/B\_\{\\mathrm\{c\}\}\\end\{pmatrix\}\.Optimizing the uncertainty in direction𝒈12\\bm\{g\}\_\{12\}gives

TR=Bc​\(σ′​\(1\)−1/2\+σ′​\(0\)−1/2\)2\.T\_\{\\rm R\}=B\_\{\\mathrm\{c\}\}\\left\(\\sigma^\{\\prime\}\(1\)^\{\-1/2\}\+\\sigma^\{\\prime\}\(0\)^\{\-1/2\}\\right\)^\{2\}\.Sinceσ′​\(1\)\\sigma^\{\\prime\}\(1\)andσ′​\(0\)\\sigma^\{\\prime\}\(0\)are absolute constants, the reward\-only sample complexity is

O~​\(Bc​log⁡1δ\)\.\\widetilde\{O\}\\\!\\left\(B\_\{\\mathrm\{c\}\}\\log\\frac\{1\}\{\\delta\}\\right\)\.
Dueling\-only\.Dueling feedback can query the pair\(1,2\)\(1,2\), which directly observes the separating direction𝒈12\\bm\{g\}\_\{12\}\. Thus

TD=Bdσ′​\(1\)​Δ122=Bdσ′​\(1\)\.T\_\{\\rm D\}=\\frac\{B\_\{\\mathrm\{d\}\}\}\{\\sigma^\{\\prime\}\(1\)\\Delta\_\{12\}^\{2\}\}=\\frac\{B\_\{\\mathrm\{d\}\}\}\{\\sigma^\{\\prime\}\(1\)\}\.The dueling\-only sample complexity is therefore

O~​\(Bd​log⁡1δ\)\.\\widetilde\{O\}\\\!\\left\(B\_\{\\mathrm\{d\}\}\\log\\frac\{1\}\{\\delta\}\\right\)\.WhenBcB\_\{\\mathrm\{c\}\}andBdB\_\{\\mathrm\{d\}\}are comparable, the dueling constant is smaller because it measures the only relevant direction in one query, whereas reward feedback must learn both coordinates\.

### D\.2Case 2: Reward Feedback is More Informative

LetK=3K=3,d=2d=2, and

𝒙1=𝒆1,𝒙2=𝒆2,𝒙3=c​𝒆1\+s​𝒆2,c=cos⁡\(0\.1\),s=sin⁡\(0\.1\)\.\\bm\{x\}\_\{1\}=\\bm\{e\}\_\{1\},\\qquad\\bm\{x\}\_\{2\}=\\bm\{e\}\_\{2\},\\qquad\\bm\{x\}\_\{3\}=c\\bm\{e\}\_\{1\}\+s\\bm\{e\}\_\{2\},\\qquad c=\\cos\(0\.1\),\\quad s=\\sin\(0\.1\)\.Seta≜1−ca\\triangleq 1\-c\. Then arm11is optimal, and the hard comparison is between arms11and33:

𝒈13≜𝒙1−𝒙3=\(a,−s\)⊤,Δ13≜𝒈13⊤​𝜽⋆=a\.\\bm\{g\}\_\{13\}\\triangleq\\bm\{x\}\_\{1\}\-\\bm\{x\}\_\{3\}=\(a,\-s\)^\{\\top\},\\qquad\\Delta\_\{13\}\\triangleq\\bm\{g\}\_\{13\}^\{\\top\}\\bm\{\\theta\}^\{\\star\}=a\.Herea=1−cos⁡\(0\.1\)a=1\-\\cos\(0\.1\)is much smaller thans=sin⁡\(0\.1\)s=\\sin\(0\.1\), so the hard direction is dominated by its𝒆2\\bm\{e\}\_\{2\}component\.

Reward\-only\.Reward feedback can query arm22and therefore estimate the dominant𝒆2\\bm\{e\}\_\{2\}coordinate directly\. Using reward queries only on arms11and22gives

𝒈13⊤​𝑨R​\(w1,w2\)−1​𝒈13=Bc​a2σ′​\(1\)​w1\+Bc​s2σ′​\(0\)​w2,w1\+w2=1\.\\bm\{g\}\_\{13\}^\{\\top\}\\bm\{A\}\_\{\\rm R\}\(w\_\{1\},w\_\{2\}\)^\{\-1\}\\bm\{g\}\_\{13\}=\\frac\{B\_\{\\mathrm\{c\}\}a^\{2\}\}\{\\sigma^\{\\prime\}\(1\)w\_\{1\}\}\+\\frac\{B\_\{\\mathrm\{c\}\}s^\{2\}\}\{\\sigma^\{\\prime\}\(0\)w\_\{2\}\},\\qquad w\_\{1\}\+w\_\{2\}=1\.Optimizing overw1,w2w\_\{1\},w\_\{2\}yields

TR≤Bc​\(a​σ′​\(1\)−1/2\+s​σ′​\(0\)−1/2\)2a2\.T\_\{\\rm R\}\\leq\\frac\{B\_\{\\mathrm\{c\}\}\\left\(a\\sigma^\{\\prime\}\(1\)^\{\-1/2\}\+s\\sigma^\{\\prime\}\(0\)^\{\-1/2\}\\right\)^\{2\}\}\{a^\{2\}\}\.Since the sigmoid derivatives are constants anda≪sa\\ll s, this gives

TR=O​\(Bc​s2a2\),T\_\{\\rm R\}=O\\\!\\left\(B\_\{\\mathrm\{c\}\}\\frac\{s^\{2\}\}\{a^\{2\}\}\\right\),and hence the reward\-only sample complexity is

O~​\(Bc​s2a2​log⁡1δ\)\.\\widetilde\{O\}\\\!\\left\(B\_\{\\mathrm\{c\}\}\\frac\{s^\{2\}\}\{a^\{2\}\}\\log\\frac\{1\}\{\\delta\}\\right\)\.
Dueling\-only\.Dueling feedback may query all three pairs\. In particular, the hard pair\(1,3\)\(1,3\)is available directly, and its curvature isσ′​\(a\)\\sigma^\{\\prime\}\(a\)\. This gives the characteristic term

TD=Bdσ′​\(a\)​a2\.T\_\{\\rm D\}=\\frac\{B\_\{\\mathrm\{d\}\}\}\{\\sigma^\{\\prime\}\(a\)a^\{2\}\}\.Sinceaais small,σ′​\(a\)\\sigma^\{\\prime\}\(a\)is an absolute constant, so the dueling\-only sample complexity is

O~​\(Bd​1a2​log⁡1δ\)\.\\widetilde\{O\}\\\!\\left\(B\_\{\\mathrm\{d\}\}\\frac\{1\}\{a^\{2\}\}\\log\\frac\{1\}\{\\delta\}\\right\)\.Thus, whenBcB\_\{\\mathrm\{c\}\}andBdB\_\{\\mathrm\{d\}\}are comparable,

O~​\(Bc​s2a2​log⁡1δ\)versusO~​\(Bd​1a2​log⁡1δ\)\.\\widetilde\{O\}\\\!\\left\(B\_\{\\mathrm\{c\}\}\\frac\{s^\{2\}\}\{a^\{2\}\}\\log\\frac\{1\}\{\\delta\}\\right\)\\quad\\text\{versus\}\\quad\\widetilde\{O\}\\\!\\left\(B\_\{\\mathrm\{d\}\}\\frac\{1\}\{a^\{2\}\}\\log\\frac\{1\}\{\\delta\}\\right\)\.The extra factors2=sin2⁡\(0\.1\)s^\{2\}=\\sin^\{2\}\(0\.1\)makes reward feedback more informative in this instance\. The reason is that arm2=𝒆22=\\bm\{e\}\_\{2\}directly probes the dominant coordinate of𝒈13\\bm\{g\}\_\{13\}, while dueling feedback must resolve the small preference gapaathrough pairwise differences\. Through these two simple examples, we see that reward and dueling feedback can be useful in different scenarios\. Together with[Figure˜1](https://arxiv.org/html/2605.05745#S5.F1)\(b\), these examples show that HyTS\-GLB does not always commit to observing a single modality\. Instead, it dynamically allocates samples between reward and dueling observations, thereby making fuller use of the available information\.