論文の概要: Optimal Regret for Single Index Bandits

• arxiv url: http://arxiv.org/abs/2605.09454v1
• Date: Sun, 10 May 2026 10:13:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.257615
• Title: Optimal Regret for Single Index Bandits
• Title（参考訳）: シングルインデックス帯域の最適レグレット
• Authors: Devdan Dey, Sujoy Bhore, Avishek Ghosh,
• Abstract要約: 我々は、高次元文脈の未知の一次元射影に依存するような$textitsingle-index bandit$問題を研究する。 我々は、一般的な単一インデックスの盗賊に対する最適な後悔を確立する。
• 参考スコア（独自算出の注目度）: 10.765936017864766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the $\textit{single-index bandit}$ problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being $\tilde{\mathcal{O}}(T^{3/4})$ (under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound ($\texttt{ZoomSIB-UCB}$), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of $\tilde{\mathcal{O}}(T^{2/3})$, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of $\tildeΩ(T^{2/3})$, showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.
• Abstract（参考訳）: 我々は、未知の報酬関数を通じて高次元文脈の未知の1次元射影に依存するような$\textit{single-index bandit}$問題を研究する。 このモデルは線形および一般化された線形帯域幅を非パラメトリックな設定に拡張し、前もって報酬関数が知られていない場合に特に関係がある。 最適な後悔の保証は単調な報酬関数に対して知られているが、一般の非単調なケースはよく理解されておらず、最もよく知られている境界は$\tilde{\mathcal{O}}(T^{3/4})$ (標準有界性と報酬関数上のリプシッツの仮定 [Kang et al , 2025])である。 一般の単一インデックスの盗賊にとって最適な後悔を確立することで、このギャップを埋める。 そこで我々は,まず正規化スタイン推定器を用いて投影方向を推定し,その問題を離散化を用いて1次元の帯域に還元し,最終的に UCB を用いる,単純な2相アルゴリズム,すなわち上信頼境界付きZoomed Single Index Bandit(\texttt{ZoomSIB-UCB}$)を提案する。 このアプローチは$\tilde{\mathcal{O}}(T^{2/3})$を後悔し、追加の仮定なしで先行作業で大幅に改善する。 また、一致するミニマックス下限の$\tildeΩ(T^{2/3})$を証明し、上限が本質的にきついことを示す。 我々の上と下の境界は、シングルインデックス・バンディットにおける後悔の鋭い特徴を与えてくれる。 さらに,実験結果は,我々のアプローチの有効性とロバスト性をさらに示している。

関連論文リスト

• Parameter-Free Dynamic Regret for Unconstrained Linear Bandits [21.35587581980097]
  直交線形帯域問題における動的後悔について検討した。 順序の最適後悔保証を達成するために,線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-26T21:16:18Z)
• Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions [8.48717433940334]
  我々は、報酬関数が未知な一般化線形バンドイット(英語版)の新たな問題、いわゆるシングルインデックスバンドイット(英語版)を導入する。 まず,未知の報酬関数が単調に増加している場合について考察し,新しいアルゴリズムであるSTORとESTORを提案する。 次に,提案手法を高次元スパース設定に拡張し,空間指数で同じ後悔率が得られることを示す。
  論文  参考訳（メタデータ） (2025-06-15T07:19:00Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• A conversion theorem and minimax optimality for continuum contextual bandits [64.9814493154015]
  本研究では,学習者が側情報ベクトルを逐次受信し,凸集合内の行動を選択する,文脈連続帯域幅問題について検討する。 目標は、受信したコンテキストのすべての基盤関数を最小化することです。 サブ線形の静的な後悔を達成するアルゴリズムを拡張して、サブ線形の文脈的後悔を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-06-09T10:12:08Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits [8.508198765617198]
  一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。 また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
  論文  参考訳（メタデータ） (2022-09-15T00:20:38Z)
• Leveraging Initial Hints for Free in Stochastic Linear Bandits [38.58449930961883]
  本研究では,学習者の事前知識を付加した帯域フィードバックによる最適化の設定について,最適行動の最初のヒントとして検討する。 我々は、このヒントを用いて、ヒントが正確である場合にその後悔を$tilde O(sqrtT)$に改善する新しいアルゴリズムを提案する。 おそらく驚くべきことに、私たちの研究は、最悪のパフォーマンスを犠牲にすることなく、ヒントを活用することで、証明可能な利益が得られていることを示している。
  論文  参考訳（メタデータ） (2022-03-08T18:48:55Z)
• Smooth Bandit Optimization: Generalization to H\"older Space [37.15553727896912]
  我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。 私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。 私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
  論文  参考訳（メタデータ） (2020-12-11T01:43:25Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。