論文の概要: Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set

• arxiv url: http://arxiv.org/abs/2607.23679v1
• Date: Sun, 26 Jul 2026 14:24:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:15.186732
• Title: Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
• Title（参考訳）: 全可変バリアを破る:固定アクションセット付きリニア・ヘテロシダスティックバンドのシャープ試料複合体
• Authors: Heyang Zhao, Tianyuan Jin, Weixin Wang, Vincent Y. F. Tan, Pan Xu, Quanquan Gu,
• Abstract要約: 本稿では,学習過程を通じて動作セットをプレフィックスするヘテロセシダスティックノイズによる線形帯域問題を再検討する。 本稿では,情報ゲインを最大化するアクションを積極的に探求する,大規模アクション集合のための分散適応アルゴリズムのtexttVAEEを提案する。 音素平均依存率が避けられないことを示す固定作用集合に対して、ほぼ一致する下界を確立する。
• 参考スコア（独自算出の注目度）: 93.03556214432615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning. In these works, the cumulative variance of the noise $Λ= \sum_{t=1}^T σ_t^2$, where $σ_t^2$ is the variance of the noise at round $t$, is used to characterize the statistical complexity of the problem, yielding \emph{simple regret} bounds of order $\tilde{\cal{O}}(d \sqrt{Λ/ T^2})$ for $d$-dimensional linear bandits with heteroscedastic noise. However, with a closer look, $Λ$ remains the same order even if the noise is close to zero at half of the rounds, which indicates that the $Λ$-dependence is not optimal. In this paper, we revisit the stochastic linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process. We propose a novel variance-adaptive algorithm \texttt{VAEE} (Variance-Aware Exploration with Elimination) for large action set, which actively explores actions that maximizes the information gain among a candidate set of actions that are not eliminated. With the active-exploration strategy, we show that \texttt{VAEE} achieves a \emph{simple regret} with a nearly \emph{harmonic-mean} dependent rate. For finitely many actions, we propose a variance-aware variant of G-optimal design based exploration, which achieves a simple regret with sharper dependence on $d$. We also establish a nearly matching lower bound for the fixed action set setting indicating that \emph{harmonic-mean} dependent rate is unavoidable. To the best of our knowledge, this is the first work that breaks the $\sqrtΛ$ barrier for stochastic linear bandits with heteroscedastic noise.
• Abstract（参考訳）: 近年では、盗賊や強化学習における異所性雑音に対処することへの関心が高まっている。 これらの研究において、ノイズの累積分散は、$σ_t^2$であり、ラウンド$t$におけるノイズの分散である$σ_t^2$は、その問題の統計的複雑さを特徴づけるために用いられ、次数$\tilde{\cal{O}}(d \sqrt{*/T^2})$の$d$次元線形包帯に対して、ヘテロスセサスティックノイズを持つ$emph{simple regret}境界を与える。 しかし、よりよく見ると、このノイズがラウンドの半分でゼロに近い場合でも、$=$は同じ順序のままであり、これは$$-dependenceが最適でないことを示している。 本稿では,学習過程を通じて動作セットがプレフィックスされるヘテロシダスティックノイズによる確率線形帯域問題を再検討する。 本研究では,大きなアクション集合に対する分散適応型アルゴリズム \texttt{VAEE} を提案する。 積極的探索戦略により, ほぼ単調な音素依存率で \texttt{VAEE} が \emph{simple regret} を達成することを示す。 有限個の作用に対して、G-最適設計に基づく探索のばらつきを意識した変種を提案する。 また、固定された作用集合集合に対してほぼ一致する下界を確立し、 \emph{harmonic-mean} 依存率が避けられないことを示す。 我々の知る限りでは、これは不連続雑音を持つ確率線型包帯に対する$\sqrt'$障壁を破る最初の作品である。

関連論文リスト

• Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts [19.395115096998108]
  MED戦略の線形バージョンから着想を得たアルゴリズムであるDri-MEDを紹介する。 Dri-MEDはドリフトや嗜好構造を無視した保守的なベースラインを著しく上回ることを示す。
  論文  参考訳（メタデータ） (2026-06-08T17:53:29Z)
• Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization [15.275864909088577]
  事前の未知のノイズレベルに適応することは、シーケンシャルな意思決定において非常に重要であるが難しい問題である。 未知のガウスパラメータ $sigma_*2$ に半適応的な新しい信頼集合を提案する。 有界報酬に対しては,先行技術により数値性能が大幅に向上した新しい分散適応信頼セットを提案する。
  論文  参考訳（メタデータ） (2024-02-12T00:19:09Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  我々は、敵対コストと既知の移行で最短経路問題を研究します。 ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T20:55:28Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• 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)

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

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