論文の概要: Ensemble sampling for linear bandits: small ensembles suffice

• arxiv url: http://arxiv.org/abs/2311.08376v2
• Date: Wed, 6 Mar 2024 12:31:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-07 17:43:34.220726
• Title: Ensemble sampling for linear bandits: small ensembles suffice
• Title（参考訳）: 線形バンディットのためのアンサンブルサンプリング:小アンサンブルsuffice
• Authors: David Janz, Alexander E. Litvak, Csaba Szepesv\'ari
• Abstract要約: 線形バンディット設定のためのアンサンブルサンプリングの最初の有用かつ厳密な解析を行う。 当社は、$T$で線形にスケールするためにアンサンブルのサイズを必要とせず、$smashsqrtT$の注文を後悔する、構造化された設定の最初の結果です。
• 参考スコア（独自算出の注目度）: 51.27199732324335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide the first useful and rigorous analysis of ensemble sampling for the stochastic linear bandit setting. In particular, we show that, under standard assumptions, for a $d$-dimensional stochastic linear bandit with an interaction horizon $T$, ensemble sampling with an ensemble of size of order $\smash{d \log T}$ incurs regret at most of the order $\smash{(d \log T)^{5/2} \sqrt{T}}$. Ours is the first result in any structured setting not to require the size of the ensemble to scale linearly with $T$ -- which defeats the purpose of ensemble sampling -- while obtaining near $\smash{\sqrt{T}}$ order regret. Ours is also the first result that allows infinite action sets.
• Abstract（参考訳）: 確率線形バンディット設定のためのアンサンブルサンプリングの,最初の有用かつ厳密な解析を提供する。 特に、標準的な仮定の下では、相互作用の地平線を持つ$d$-次元確率線型バンドイットに対して、$T$, アンサンブルサンプリングは位数$\smash{d \log T}$のアンサンブルで、ほとんどの位数$\smash{(d \log T)^{5/2} \sqrt{T}}$で後悔を引き起こす。 oursは、アンサンブルのサイズを$t$(アンサンブルサンプリングの目的を損なう)で線形にスケールする必要がなく、ほぼ$\smash{\sqrt{t}}$order regretを得るような構造化された設定の最初の結果である。 oursは無限のアクションセットを可能にする最初の結果でもある。

関連論文リスト

• Improved Regret of Linear Ensemble Sampling [9.410437324336275]
  アンサンブルサイズを$T$とすると、線形アンサンブルサンプリングは$tildemathcalO(d3/2sqrtT)$の頻繁な残差を達成できる。 我々の貢献は、アンサンブルサンプリングの理論的な基礎を前進させ、他のランダム化探索アルゴリズムの最もよく知られた境界と一致させた。
  論文  参考訳（メタデータ） (2024-11-06T14:09:11Z)
• Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
  私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。 また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-10-01T13:45:55Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
  我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。 逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。 我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
  論文  参考訳（メタデータ） (2023-11-02T03:41:58Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)

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

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