技術的サマリー：ハイブリッドフィードバックを介した一般化線形バンディットにおける最良腕の特定

問題定式化

本論文は、ハイブリッドフィードバックモデルの下における**一般化線形バンディット（GLB）の枠組み内での固定信頼度最良腕特定（BAI）**問題を取り扱います。

• 設定: 学習者は、既知の特徴ベクトル $x_i \in \mathbb{R}^d$ と未知の潜在パラメータ $\theta^*$ がそれぞれ関連付けられた $K$ 個の腕と相互作用します。目的は、確率 $1-\delta$ 以上で期待報酬 $\mu_c(x_i^\top \theta^*)$ を最大化する腕 $i^*$ を特定し、そのために必要なサンプル数を最小化することです。
• ハイブリッドフィードバック: 単一のフィードバックタイプに依存する標準的なバンディット設定とは異なり、学習者は各ラウンド $t$ で 2 つのモダリティから選択できます：
  1. 絶対報酬: 腕 $i$ を選択し、ノイズを含む報酬 $R_t \sim p_c(\cdot | x_i^\top \theta^*)$ を観測します。
  2. 相対的（デュエリング）フィードバック: 腕のペア $(j, k)$ を選択し、$Y_t=1$ が $j$ への選好を示すように、$p_d(\cdot | (x_j - x_k)^\top \theta^*)$ から引き出された二値選好 $Y_t \in \{0, 1\}$ を観測します。
• 統計モデル: 両方のフィードバックタイプは、同じ潜在パラメータ $\theta^*$ を共有しつつ、異なるリンク関数、分散パラメータ、および曲率プロファイルを持つ可能性のある一般化線形モデル（GLM）としてモデル化されます。目的は、停止時間（または総コスト）を最小化するために、フィードバックモダリティと照会する特定の腕/ペアを適応的に選択することです。

手法

提案される解決策 HyTS-GLB（GLB 向けのハイブリッド Track-and-Stop）は、フィードバックの不均一性に対処するために、統計的推論と実験デザインを統合します。

1. 統合された信頼度系列

核心的な統計的貢献は、不均質な観測を統合する尤度比に基づく信頼度系列です。

• 尤度比の構築: 著者らは Lee ら [2024] の枠組みをハイブリッド観測に拡張します。彼らは、報酬損失とデュエリング損失の両方を集約する累積負の対数尤度 $L_t(\theta)$ を定義します。
• 楕円形信頼度集合: 自己共鳴性（有界な 3 階微分を保証するリンク関数の性質）の仮定の下、著者らは明示的な楕円形信頼度集合 $E_t(\delta)$ を導出します。
  • この集合は $\{ \theta : \|\theta - \hat{\theta}_t\|_{A_t}^2 \leq \beta_t(\delta) \}$ と定義され、ここで $\hat{\theta}_t$ は制約付き最尤推定量（MLE）です。
  • 行列 $A_t$ は、両方のフィードバックモダリティからの曲率情報を、そのサンプリング頻度と特徴幾何学によって重み付けして結合した集約情報行列です。これにより、アルゴリズムは絶対フィードバックと相対フィードバックを、潜在パラメータに関する統合された情報源として扱うことができます。

2. ハイブリッド Track-and-Stop アルゴリズム

信頼度集合に基づき、著者らはTrack-and-Stop戦略を提案します：

• ミニマックス最適デザイン: アルゴリズムは、すべての腕のペアにわたる最悪ケースの信頼度幅を最小化するサンプリング割合ベクトル $w$ を追跡します。具体的には、現在の経験的最良腕 $\hat{i}^*_t$ に対して $\max_{i \neq \hat{i}^*_t} \|x_{\hat{i}^*_t, i}\|_{A(w, \hat{\theta}_t)^{-1}}^2$ を最小化するミニマックス問題を解きます。
• 追跡ルール: 学習者は、情報行列が非退化であることを保証するために減衰する強制探索メカニズムを組み込みながら、目標割合 $w^*(t)$ に一致するように行動を選択します。
• 停止ルール: アルゴリズムは、現在の経験的最良腕が信頼度集合 $E_t(\delta)$ 内のすべての競合他社に対して最適であると認証されたときに終了します。

3. コスト感知拡張

この枠組みは、報酬とデュエリング照会が異なる取得コスト（$c_{reward}$ 対 $c_{dueling}$）を持つコスト感知設定に拡張されます。

• アルゴリズムは、生きたサンプリング割合ではなく、コストあたりのサンプリング強度であるコスト正規化デザインベクトル $p$ を最適化します。
• これにより、学習者は情報獲得と金銭的または計算コストの間のトレードオフを最適化し、よりコスト効率の高いモダリティを適応的に優先することができます。

主要な貢献

1. ハイブリッド GLM 定式化: 本論文は、共有された GLM パラメータ化の下で、報酬とデュエリングの両方のフィードバックを用いた純粋な探索を定式化します。非構造化ハイブリッドモデルとは異なり、このアプローチは異なる尤度と曲率を受け入れつつ、モダリティ間で情報を転送するために共有された潜在構造を利用します。
2. ハイブリッド信頼度系列: 著者らは、報酬チャネルとデュエリングチャネルの両方からの不均質なフィッシャー曲率を集約する、単一の明示的な楕円形信頼度領域を開発しました。これにより、推論と停止を統合し、個別の信頼度集合を調整する必要を回避します。
3. 幾何学認識アルゴリズム（HyTS-GLB）: 彼らは、腕と腕のペアの結合行動空間にわたるミニマックス最適デザインを追跡するアルゴリズムを提案します。このアルゴリズムは $\delta$-correct であることが証明され、停止時間に対する高確率の上限を提供します。
4. 理論的保証: 停止時間は、ハイブリッドフィードバックの結合情報効率を捉えるミニマックス特性時間 $T^*(\theta^*)$ に比例してスケーリングすることが示されています。コスト感知バリアントは、総取得コストに対して同様の上限を達成します。
5. 実証的検証: 実験により、ハイブリッドアプローチが単一モダリティのベースライン（報酬のみまたはデュエリングのみ）と比較して、サンプル複雑性を大幅に削減することが示されました。コスト感知バリアントは、非対称な照会コストに適応することに成功しました。

結果と性能

• サンプル効率: ロジスティック観測モデルを用いた合成実験において、HyTS-GLB はさまざまな次元にわたり、ベースライン手法（Rage-GLM、ReTS-GLB、DuelTS-GLB）を一貫して上回りました。特に報酬とデュエリングフィードバックが異なる方向に沿って補完的な情報を提供する構成において、ほとんどの設定で最小の平均停止時間を達成しました。
• コスト適応: フィードバックコストが非対称な場合、コスト感知バリアントは、正確性を犠牲にすることなく、より安価なモダリティへのサンプリングをシフトさせることで、標準的な HyTS-GLB と比較して総コストを削減します。
• 複雑性分析: 理論的分析により、サンプル複雑性は特性時間 $T^*(\theta^*)$ によって支配されることが示されています。本論文は、インスタンスの幾何学に応じて報酬またはデュエリングフィードバックのどちらがより有益であるかを具体的に示す例を提供し、ハイブリッドアルゴリズムが単一のモダリティにコミットするのではなく、これらの条件に動的に適応することを示しています。

意義と主張

本論文は、ハイブリッドフィードバックを伴う一般化線形バンディットにおける固定信頼度 BAI のための統合された統計的およびアルゴリズム的枠組みを提供すると主張しています。

• 統計的統合: この研究は、単純な淘汰などのアルゴリズム的融合を超えて、絶対フィードバックと相対フィードバックを共有された潜在効用の異なる観測としてモデル化する統計的統合へと移行します。これにより、共有パラメータ構造を利用することで、データの効率的な利用が可能になります。
• 不均一性の処理: 提案された信頼度系列は、不均質な尤度と曲率プロファイルによって引き起こされる統計的課題を成功裡に処理し、停止と割り当ての両方を導く最適性に対する単一の証明を提供します。
• 実用性: この枠組みは、システムが混合フィードバック（評価対ペアごとの選好）を受け取り、照会コストが変動する可能性のある現実世界のシナリオ（例：RLHF、会話型レコメンダー）に対処します。
• 最適性における謙虚さ: 著者らは、設計基準が情報理論的下限の局所二次緩和と整合するものの、有限時間保証には保守的な定数と対数因子が含まれることを認めています。彼らは、GLM における KL 発散の非線形性のために、一般的な GLM に対する完全にインスタンス最適のアルゴリズムを取得することは依然として未解決の問題であると指摘しています。

要約すると、本論文は、自己共鳴信頼度系列を備えた統合 GLM 枠組みを通じて処理された場合、ハイブリッドフィードバックは、サンプル効率とコスト効率の点で単一モダリティ戦略を厳密に上回ることを確立しています。