論文の概要: Bandit Learning with General Function Classes: Heteroscedastic Noise and Variance-dependent Regret Bounds

• arxiv url: http://arxiv.org/abs/2202.13603v1
• Date: Mon, 28 Feb 2022 08:25:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-01 15:47:04.617924
• Title: Bandit Learning with General Function Classes: Heteroscedastic Noise and Variance-dependent Regret Bounds
• Title（参考訳）: 一般機能クラスを用いた帯域学習:ヘテロセダスティックノイズと分散依存性レグレト境界
• Authors: Heyang Zhao and Dongruo Zhou and Jiafan He and Quanquan Gu
• Abstract要約: 我々は、報酬関数が一様有界関数の一般クラスに属するバンディットモデルを学ぶことを考える。 一般帯域モデルのための多段階学習フレームワークを提案する。 本稿では,まず,経験的リスク最小化に基づく分散認識信頼セットを構築するアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 88.6139446295537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider learning a stochastic bandit model, where the reward function belongs to a general class of uniformly bounded functions, and the additive noise can be heteroscedastic. Our model captures contextual linear bandits and generalized linear bandits as special cases. While previous works (Kirschner and Krause, 2018; Zhou et al., 2021) based on weighted ridge regression can deal with linear bandits with heteroscedastic noise, they are not directly applicable to our general model due to the curse of nonlinearity. In order to tackle this problem, we propose a multi-level learning framework for the general bandit model. The core idea of our framework is to partition the observed data into different levels according to the variance of their respective reward and perform online learning at each level collaboratively. Under our framework, we first design an algorithm that constructs the variance-aware confidence set based on empirical risk minimization and prove a variance-dependent regret bound. For generalized linear bandits, we further propose an algorithm based on follow-the-regularized-leader (FTRL) subroutine and online-to-confidence-set conversion, which can achieve a tighter variance-dependent regret under certain conditions.
• Abstract（参考訳）: 我々は、報酬関数が一様有界関数の一般クラスに属し、付加雑音がヘテロシドスティックである確率的バンディットモデルを学ぶことを検討する。 本モデルは,文脈線形バンディットと一般化線形バンディットを特殊ケースとして捉える。 重み付きリッジ回帰に基づくこれまでの研究(kirschner and krause, 2018; zhou et al., 2021)は、ヘテロ科学的ノイズを伴う線形バンディットを扱うことができるが、非線形性の呪いのため、我々の一般的なモデルには直接適用できない。 そこで本研究では,一般バンドイットモデルのための多レベル学習フレームワークを提案する。 我々のフレームワークの核となる考え方は、観察したデータをそれぞれの報酬のばらつきに応じて異なるレベルに分割し、協調してオンライン学習を行うことです。 本手法では,実験的リスク最小化に基づく分散認識信頼セットを構成するアルゴリズムをまず設計し,分散依存の後悔を証明した。 一般化線形ブレイディットに対しては、従順化リーダ(FTRL)サブルーチンとオンライン信頼セット変換に基づくアルゴリズムを提案し、特定の条件下でより厳密な分散依存的後悔を実現する。

関連論文リスト

• Improved Regret of Linear Ensemble Sampling [9.410437324336275]
  アンサンブルサイズを$T$とすると、線形アンサンブルサンプリングは$tildemathcalO(d3/2sqrtT)$の頻繁な残差を達成できる。 我々の貢献は、アンサンブルサンプリングの理論的な基礎を前進させ、他のランダム化探索アルゴリズムの最もよく知られた境界と一致させた。
  論文  参考訳（メタデータ） (2024-11-06T14:09:11Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Max-Linear Regression by Convex Programming [5.366354612549172]
  我々は、最大線形回帰問題の推定器として、アンカーレグレッション(AR)によって与えられるスケーラブルな凸プログラムを定式化し、解析する。 以上の結果から, 対数係数まで, 正確な回復スケールについて, 十分な数のノイズのない観測結果が得られた。
  論文  参考訳（メタデータ） (2021-03-12T00:55:54Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。 特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-06-15T08:25:50Z)

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

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