Technical Summary: Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

Problem Formulation

This paper addresses the fixed-confidence Best Arm Identification (BAI) problem within the framework of Generalized Linear Bandits (GLBs) under a hybrid feedback model.

• Setting: A learner interacts with $K$ arms, each associated with a known feature vector $x_i \in \mathbb{R}^d$ and an unknown latent parameter $\theta^*$. The goal is to identify the arm $i^*$ that maximizes the expected reward $\mu_c(x_i^\top \theta^*)$ with probability at least $1-\delta$, using the minimum number of samples.
• Hybrid Feedback: Unlike standard bandit settings that rely on a single feedback type, the learner can choose between two modalities at each round $t$:
  1. Absolute Reward: Select an arm $i$ and observe a noisy reward $R_t \sim p_c(\cdot | x_i^\top \theta^*)$.
  2. Relative (Dueling) Feedback: Select a pair of arms $(j, k)$ and observe a binary preference $Y_t \in \{0, 1\}$ drawn from $p_d(\cdot | (x_j - x_k)^\top \theta^*)$, where $Y_t=1$ indicates a preference for $j$.
• Statistical Model: Both feedback types are modeled as Generalized Linear Models (GLMs) sharing the same latent parameter $\theta^*$ but potentially possessing different link functions, dispersion parameters, and curvature profiles. The objective is to adaptively choose the feedback modality and the specific arms/pairs to query to minimize the stopping time (or total cost).

Methodology

The proposed solution, HyTS-GLB (Hybrid Track-and-Stop for GLBs), integrates statistical inference with experimental design to handle the heterogeneity of feedback.

1. Unified Confidence Sequences

The core statistical contribution is a likelihood-ratio-based confidence sequence that unifies heterogeneous observations.

• Likelihood-Ratio Construction: The authors extend the framework of Lee et al. [2024] to hybrid observations. They define a cumulative negative log-likelihood $L_t(\theta)$ that aggregates both reward and dueling losses.
• Ellipsoidal Confidence Sets: Under the assumption of self-concordance (a property of the link functions ensuring bounded third derivatives), the authors derive an explicit ellipsoidal confidence set $E_t(\delta)$.
  • The set is defined as $\{ \theta : \|\theta - \hat{\theta}_t\|_{A_t}^2 \leq \beta_t(\delta) \}$, where $\hat{\theta}_t$ is the constrained Maximum Likelihood Estimator (MLE).
  • The matrix $A_t$ is an aggregated information matrix that combines curvature information from both feedback modalities, weighted by their sampling frequencies and feature geometries. This allows the algorithm to treat absolute and relative feedback as a unified source of information regarding the latent parameter.

2. Hybrid Track-and-Stop Algorithm

Building on the confidence sets, the authors propose a Track-and-Stop strategy:

• Minimax-Optimal Design: The algorithm tracks a sampling proportion vector $w$ that minimizes the worst-case confidence width over all arm pairs. Specifically, it solves a minimax problem to minimize $\max_{i \neq \hat{i}^*_t} \|x_{\hat{i}^*_t, i}\|_{A(w, \hat{\theta}_t)^{-1}}^2$, where $\hat{i}^*_t$ is the current empirical best arm.
• Tracking Rule: The learner selects actions to match the target proportions $w^*(t)$ while incorporating a vanishing forced-exploration mechanism to ensure the information matrix remains non-degenerate.
• Stopping Rule: The algorithm terminates when the current empirical best arm is certified as optimal against all competitors within the confidence set $E_t(\delta)$.

3. Cost-Aware Extension

The framework is extended to a cost-aware setting where reward and dueling queries have different acquisition costs ($c_{reward}$ vs. $c_{dueling}$).

• The algorithm optimizes a cost-normalized design vector $p$ (sampling intensity per unit cost) rather than raw sampling proportions.
• This allows the learner to trade off information gain against monetary or computational cost, adaptively favoring the more cost-efficient modality.

Key Contributions

1. Hybrid GLM Formulation: The paper formulates pure exploration with both reward and dueling feedback under a shared GLM parameterization. Unlike unstructured hybrid models, this approach leverages the shared latent structure to transfer information between modalities while accommodating different likelihoods and curvatures.
2. Hybrid Confidence Sequences: The authors develop a single, explicit ellipsoidal confidence region that aggregates heterogeneous Fisher curvature from both reward and dueling channels. This unifies inference and stopping, avoiding the need to reconcile separate confidence sets.
3. Geometry-Aware Algorithm (HyTS-GLB): They propose an algorithm that tracks a minimax-optimal design over the joint action space of arms and arm pairs. The algorithm is proven to be $\delta$-correct and provides high-probability upper bounds on the stopping time.
4. Theoretical Guarantees: The stopping time is shown to scale with a minimax characteristic time $T^*(\theta^*)$, which captures the joint information efficiency of the hybrid feedback. The cost-aware variant achieves similar bounds on total acquisition cost.
5. Empirical Validation: Experiments demonstrate that the hybrid approach significantly reduces sample complexity compared to single-modality baselines (reward-only or dueling-only). The cost-aware variant successfully adapts to asymmetric query costs.

Results and Performance

• Sample Efficiency: In synthetic experiments with logistic observation models, HyTS-GLB consistently outperforms baseline methods (Rage-GLM, ReTS-GLB, DuelTS-GLB) across various dimensions. It achieves the smallest mean stopping time in most configurations, particularly when reward and dueling feedback provide complementary information along different directions.
• Cost Adaptation: When feedback costs are asymmetric, the cost-aware variant reduces the total cost compared to the standard HyTS-GLB by shifting sampling toward the cheaper modality without sacrificing correctness.
• Complexity Analysis: Theoretical analysis shows that the sample complexity is governed by the characteristic time $T^*(\theta^*)$. The paper provides concrete examples where either reward or dueling feedback is more informative depending on the instance geometry, demonstrating that the hybrid algorithm dynamically adapts to these conditions rather than committing to a single modality.

Significance and Claims

The paper claims to provide a unified statistical and algorithmic framework for fixed-confidence BAI in generalized linear bandits with hybrid feedback.

• Statistical Integration: The work moves beyond algorithmic fusion (e.g., simple elimination) to statistical integration, modeling absolute and relative feedback as distinct observations of a shared latent utility. This allows for a more efficient use of data by leveraging the shared parameter structure.
• Handling Heterogeneity: The proposed confidence sequence successfully handles the statistical challenges posed by heterogeneous likelihoods and curvature profiles, providing a single certificate for optimality that guides both stopping and allocation.
• Practical Relevance: The framework addresses real-world scenarios (e.g., RLHF, conversational recommenders) where systems receive mixed feedback (ratings vs. pairwise preferences) and where query costs may vary.
• Modesty in Optimality: The authors acknowledge that while their design criterion aligns with a local quadratic relaxation of the information-theoretic lower bound, the finite-time guarantees involve conservative constants and logarithmic factors. They note that obtaining fully instance-optimal algorithms for general GLMs remains an open problem, particularly due to the nonlinearity of the KL divergence in GLMs.

In summary, the paper establishes that hybrid feedback, when processed through a unified GLM framework with self-concordant confidence sequences, can strictly outperform single-modality strategies in terms of sample and cost efficiency.