論文の概要: Optimal Streaming Algorithms for Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2410.17835v1
• Date: Wed, 23 Oct 2024 12:54:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-24 13:55:19.335695
• Title: Optimal Streaming Algorithms for Multi-Armed Bandits
• Title（参考訳）: マルチアーマッド帯域に対する最適ストリーミングアルゴリズム
• Authors: Tianyuan Jin, Keke Huang, Jing Tang, Xiaokui Xiao,
• Abstract要約: ストリーミングBAI問題では,最大報酬が1-delta$の確率でアームを識別することが目的である。 我々は,O(log Delta-1)$パス内で,ほぼインスタンス依存の最適なサンプル複雑性を実現するシングルアームメモリアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 28.579280943038555
• License:
• Abstract: This paper studies two variants of the best arm identification (BAI) problem under the streaming model, where we have a stream of $n$ arms with reward distributions supported on $[0,1]$ with unknown means. The arms in the stream are arriving one by one, and the algorithm cannot access an arm unless it is stored in a limited size memory. We first study the streaming \eps-$top$-$k$ arms identification problem, which asks for $k$ arms whose reward means are lower than that of the $k$-th best arm by at most $\eps$ with probability at least $1-\delta$. For general $\eps \in (0,1)$, the existing solution for this problem assumes $k = 1$ and achieves the optimal sample complexity $O(\frac{n}{\eps^2} \log \frac{1}{\delta})$ using $O(\log^*(n))$ ($\log^*(n)$ equals the number of times that we need to apply the logarithm function on $n$ before the results is no more than 1.) memory and a single pass of the stream. We propose an algorithm that works for any $k$ and achieves the optimal sample complexity $O(\frac{n}{\eps^2} \log\frac{k}{\delta})$ using a single-arm memory and a single pass of the stream. Second, we study the streaming BAI problem, where the objective is to identify the arm with the maximum reward mean with at least $1-\delta$ probability, using a single-arm memory and as few passes of the input stream as possible. We present a single-arm-memory algorithm that achieves a near instance-dependent optimal sample complexity within $O(\log \Delta_2^{-1})$ passes, where $\Delta_2$ is the gap between the mean of the best arm and that of the second best arm.
• Abstract（参考訳）: 本稿では,ストリーミングモデルにおけるベストアーム識別(BAI)問題の2つの変種について検討する。 ストリーム内のアームは1つずつ到着し、限られたサイズのメモリに格納されない限り、アルゴリズムはアームにアクセスすることができない。 我々はまず、ストリーミング \eps-$top$-k$腕識別問題を研究し、報酬手段が$k$のベストアームよりも低い$k$を、少なくとも1-\delta$の確率で$\eps$で求める。 一般的な$\eps \in (0,1)$の場合、この問題の既存の解は$k = 1$と仮定し、最適なサンプル複雑性を$O(\frac{n}{\eps^2} \log \frac{1}{\delta})$ using $O(\log^*(n))$$$$$$\log^*(n)$は、結果が1に満たない前に$n$で対数関数を適用する必要がある回数とストリームの1パスに等しい。 我々は,任意の$k$で動作するアルゴリズムを提案し,単一アームメモリとストリームの単一パスを用いて最適なサンプル複雑性を$O(\frac{n}{\eps^2} \log\frac{k}{\delta})$とする。 第2に,最大報酬平均が1-\delta$の確率でアームを識別することを目的としたストリーミングBAI問題について,単一メモリと入力ストリームの少ないパスで検討する。 O(\log \Delta_2^{-1})$pass($\Delta_2$は、ベストアームの平均と2番目のベストアームの平均とのギャップである)内で、ほぼインスタンス依存の最適なサンプル複雑性を実現するシングルアームメモリアルゴリズムを提案する。

関連論文リスト

• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits [10.329863009504303]
  我々は、$O(fracnDelta2)$の最適なサンプル複雑さを利用するサブ線形メモリを持つストリーミングアルゴリズムは、$Omega(fraclog (1/Delta)log (1/Delta)$ passを必要とすることを示した。 この結果は,[ICML'21] の$O(log(frac1Delta))$-passアルゴリズムと一致し, [ICML'21] は$O(1)$メモリしか使用せず, Assadi と Wang が提案したオープンな質問に答える。
  論文  参考訳（メタデータ） (2023-09-06T16:41:41Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Variance-Dependent Best Arm Identification [12.058652922228918]
  マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。 武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。 このアルゴリズムは2つの対数項に最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-19T04:13:54Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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