論文の概要: The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits

• arxiv url: http://arxiv.org/abs/2309.03145v2
• Date: Tue, 25 Jun 2024 17:20:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-26 21:09:52.019981
• Title: The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
• Title（参考訳）: The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits (特集:ユビキタス・バイオサイバネティックスとバイオサイバネティックス)
• Authors: Sepehr Assadi, Chen Wang,
• Abstract要約: 我々は、$O(fracnDelta2)$の最適なサンプル複雑さを利用するサブ線形メモリを持つストリーミングアルゴリズムは、$Omega(fraclog (1/Delta)log (1/Delta)$ passを必要とすることを示した。 この結果は,[ICML'21] の$O(log(frac1Delta))$-passアルゴリズムと一致し, [ICML'21] は$O(1)$メモリしか使用せず, Assadi と Wang が提案したオープンな質問に答える。
• 参考スコア（独自算出の注目度）: 10.329863009504303
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a near-optimal sample-pass trade-off for pure exploration in multi-armed bandits (MABs) via multi-pass streaming algorithms: any streaming algorithm with sublinear memory that uses the optimal sample complexity of $O(\frac{n}{\Delta^2})$ requires $\Omega(\frac{\log{(1/\Delta)}}{\log\log{(1/\Delta)}})$ passes. Here, $n$ is the number of arms and $\Delta$ is the reward gap between the best and the second-best arms. Our result matches the $O(\log(\frac{1}{\Delta}))$-pass algorithm of Jin et al. [ICML'21] (up to lower order terms) that only uses $O(1)$ memory and answers an open question posed by Assadi and Wang [STOC'20].
• Abstract（参考訳）: O(\frac{n}{\Delta^2})$ requires $\Omega(\frac{\log{(1/\Delta)}}{\log{(1/\Delta)}}$ pass。 ここでは、$n$は腕の数であり、$\Delta$はベストとセカンドベストの腕の間の報酬ギャップである。 この結果は、[ICML'21]の$O(\log(\frac{1}{\Delta})$-passアルゴリズムと一致し、[ICML'21]は$O(1)$メモリしか使用せず、[STOC'20]とAssadiによるオープンな質問に答える。

関連論文リスト

• Optimal Streaming Algorithms for Multi-Armed Bandits [28.579280943038555]
  ストリーミングBAI問題では,最大報酬が1-delta$の確率でアームを識別することが目的である。 我々は,O(log Delta-1)$パス内で,ほぼインスタンス依存の最適なサンプル複雑性を実現するシングルアームメモリアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-23T12:54:04Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Tight Memory-Regret Lower Bounds for Streaming Bandits [11.537938617281736]
  学習者は オンラインの腕と サブリニアの腕の記憶を扱うことで 後悔を最小化することを目的としています 我々は,任意のアルゴリズムに対して,Omega left((TB)alpha K1-alpharight), α = 2B / (2B+1-1)$という,厳密な最悪ケースの残差を低く設定する。 また、一定のアームメモリを用いて、左(TB)アルファK1-αright)$の後悔の上限を達成できるマルチパスアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2023-06-13T16:54:13Z)
• Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits [3.5955736977697073]
  K$アームと$T$トライアルを持つシングルパス設定では、$o(K)$メモリを持つ任意のアルゴリズムに対して、後悔の少ない$Omega(T2/3)$が証明されている。 本稿では,o(K)$メモリを持つアルゴリズムに対して,Omega(K/3log/3(T))$に制限された後悔の低減を図る。 提案アルゴリズムはベンチマーク均一探索アルゴリズムを大きなマージンで一貫して上回り、時には後悔を最大70%削減することを示した。
  論文  参考訳（メタデータ） (2023-06-03T22:41:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。 我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2021-06-05T14:11:01Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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