論文の概要: Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions

• arxiv url: http://arxiv.org/abs/2604.22161v1
• Date: Fri, 24 Apr 2026 02:21:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-27 15:36:26.310617
• Title: Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions
• Title（参考訳）: $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions
• Authors: Seoungbin Bae, Dabeen Lee,
• Abstract要約: SupSplitLogは、コンテキストの多様性を仮定せずに$tildemathcalO(sqrtdT)$ regretを達成するロジスティックバンディットのための最初のアルゴリズムである。 SupSplitLogは、後悔の上限における次元$d$への依存の観点から、既存のアルゴリズムを厳密に改善する。
• 参考スコア（独自算出の注目度）: 1.0098114696565863
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the $K$-armed logistic bandit problem, where at each round, the agent observes $K$ feature vectors associated with $K$ actions. Existing approaches that achieve a rate-optimal $\tilde{\mathcal{O}}(\sqrt{dT})$ regret bound rely heavily on context diversity assumptions, such as strict positivity of the minimum eigenvalue of a context covariance matrix. These assumptions, however, impose strong restrictions on the context process, as they rule out the situation where the context vectors are concentrated in a low-dimensional subspace. In this paper, we propose SupSplitLog, which, to the best of our knowledge, is the first algorithm for logistic bandits that achieves $\tilde{\mathcal{O}}(\sqrt{dT})$ regret without any context diversity assumption. The key idea is to split the collected samples into two disjoint subsets when constructing estimators; one is used to compute an initial-point estimator, while the other is used to apply a Newton-type one-step correction procedure. The splitting rule is carefully designed to balance the accuracy requirements of the initial-point estimator and the one-step correction procedure. Moreover, SupSplitLog strictly improves on the existing algorithms in terms of the dependence on dimension $d$ in the regret upper bound. Furthermore, SupSplitLog can be adapted simply to deduce a regret bound that grows with a data-dependent complexity measure, avoiding a direct dependence on $d$, which is favorable when the context vectors are concentrated in a low-dimensional subspace. We also provide experimental results that demonstrate numerically the superiority of our algorithm, validating the theoretical results.
• Abstract（参考訳）: 各ラウンドでエージェントが$K$アクションに関連する特徴ベクトルを観察する。 既存のアプローチは、文脈共分散行列の最小固有値の厳密な正則性など、文脈の多様性の仮定に大きく依存している。 しかし、これらの仮定は文脈ベクトルが低次元の部分空間に集中している状況を排除するため、文脈過程に強い制約を課す。 本稿では,SupSplitLogを提案する。SupSplitLogは,我々の知る限り,文脈の多様性を前提とせず,$\tilde{\mathcal{O}}(\sqrt{dT})を後悔するロジスティックバンディットのための最初のアルゴリズムである。 1つは初期点推定器の計算に、もう1つはニュートン型ワンステップ補正手順に使用される。 分割規則は、初期点推定器の精度要件とワンステップ補正手順のバランスをとるように慎重に設計されている。 さらに、SupSplitLogは、後悔の上限における次元$d$への依存の観点から、既存のアルゴリズムを厳密に改善する。 さらに、SupSplitLogは単にデータ依存の複雑性尺度で成長する後悔のバウンダリを推論するために適応することができ、コンテキストベクトルが低次元のサブ空間に集中すると、$d$への直接的な依存を避けることができる。 また,提案アルゴリズムの優位性を数値的に証明し,理論的結果を検証する実験結果も提供する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
  ニューラルネットワークを利用して非線形ユーティリティ関数を近似する分散認識アルゴリズムを提案する。 十分広いニューラルネットワークに対して,我々のアルゴリズムが次数$bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt)のサブ線形累積平均後悔を達成できることを示す理論的保証を確立する。
  論文  参考訳（メタデータ） (2025-06-02T01:58:48Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Minimum mean-squared error estimation with bandit feedback [10.660855209170586]
  平均二乗誤差 (MSE) の意味で, 逐次的に推定を学習する問題を考察する。 2つのMSE推定器を提案し,その濃度特性を解析した。
  論文  参考訳（メタデータ） (2022-03-31T05:33:32Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)

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

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