論文の概要: A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
- arxiv url: http://arxiv.org/abs/2205.00984v1
- Date: Mon, 2 May 2022 15:30:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-03 13:59:47.863006
- Title: A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
- Title（参考訳）: マルチパスストリーミング帯域のためのシャープメモリ-レグレットトレードオフ
- Authors: Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
- Abstract要約: 本稿では,アームをストリームに表示するストリーミング環境について考察し,アルゴリズムは限られたメモリを用いてこれらのアームを処理する。
O(1)$メモリは$widetildeThetaBig(Tfrac12 + frac12B+2-2Big)を達成するのに十分である。
我々の主な技術的貢献は、情報理論の手法とラウンド・エミネーションのアイデアを併用することであり、*残留問題*がその後のパスよりも挑戦的であることを示しています。
- 参考スコア（独自算出の注目度）: 13.146885920912025
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The stochastic $K$-armed bandit problem has been studied extensively due to
its applications in various domains ranging from online advertising to clinical
trials. In practice however, the number of arms can be very large resulting in
large memory requirements for simultaneously processing them. In this paper we
consider a streaming setting where the arms are presented in a stream and the
algorithm uses limited memory to process these arms. Here, the goal is not only
to minimize regret, but also to do so in minimal memory. Previous algorithms
for this problem operate in one of the two settings: they either use
$\Omega(\log \log T)$ passes over the stream (Rathod, 2021; Chaudhuri and
Kalyanakrishnan, 2020; Liau et al., 2018), or just a single pass (Maiti et al.,
2021).
In this paper we study the trade-off between memory and regret when $B$
passes over the stream are allowed, for any $B \geq 1$, and establish tight
regret upper and lower bounds for any $B$-pass algorithm. Our results uncover a
surprising *sharp transition phenomenon*: $O(1)$ memory is sufficient to
achieve $\widetilde\Theta\Big(T^{\frac{1}{2} + \frac{1}{2^{B+2}-2}}\Big)$
regret in $B$ passes, and increasing the memory to any quantity that is $o(K)$
has almost no impact on further reducing this regret, unless we use $\Omega(K)$
memory. Our main technical contribution is our lower bound which requires the
use of information-theoretic techniques as well as ideas from round elimination
to show that the *residual problem* remains challenging over subsequent passes.
- Abstract（参考訳）: 確率的k$武装のバンディット問題は、オンライン広告から臨床試験まで様々な分野に応用されているため、広く研究されている。
しかし実際には、アームの数がとても多くなり、同時に処理するためのメモリの要求が大きくなる。
本稿では,アームをストリームに表示するストリーミング環境について考察し,アルゴリズムは限られたメモリを用いてこれらのアームを処理する。
ここでの目標は、後悔を最小化するだけでなく、最小限のメモリでそれを行うことです。
この問題の以前のアルゴリズムは、2つの設定のうちの1つで動作する:$\Omega(\log \log T)$pass over the stream(Rathod, 2021; Chaudhuri and Kalyanakrishnan, 2020; Liau et al., 2018)または1つのパス(Maiti et al., 2021)。
本稿では,任意の$B \geq 1$に対して,ストリームを渡れば$B$が許される場合のメモリと後悔のトレードオフについて検討し,任意の$B$-passアルゴリズムに対して,厳密な後悔の上限と低い境界を確立する。
o(1)$ メモリは$\widetilde\theta\big(t^{\frac{1}{2} + \frac{1}{2^{b+2}-2}}\big)$ パスで後悔し、$o(k)$ の任意の量へのメモリ増加は、$\omega(k)$ メモリを使用しない限り、この後悔を減少させる効果はほとんどない。
我々の主な技術的貢献は、情報理論技術の使用とラウンド・エライズからのアイデアを必要とする低い境界であり、*残留問題*がその後のパスよりも挑戦的であることを示します。
関連論文リスト
- Optimal Streaming Algorithms for Multi-Armed Bandits [28.579280943038555]
ストリーミングBAI問題では,最大報酬が1-delta$の確率でアームを識別することが目的である。
我々は,O(log Delta-1)$パス内で,ほぼインスタンス依存の最適なサンプル複雑性を実現するシングルアームメモリアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-23T12:54:04Z) - Tight Time-Space Lower Bounds for Constant-Pass Learning [1.7387739961208148]
サンプルストリームを$q$で通過するパリティ学習アルゴリズムに対して,メモリサンプルの少ないバウンダリを厳密に証明する。
このような学習者には、メモリサイズが$Omega(n2)$か、少なくとも$Omega(n)$サンプルが必要である。
これまでの研究と同様に、この結果は、ほぼ直交的な概念を多く含んだ学習問題にまで及んでいる。
論文 参考訳（メタデータ） (2023-10-12T06:36:31Z) - 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) - 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) - Smooth Non-Stationary Bandits [49.19728527803684]
本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。
スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
論文 参考訳（メタデータ） (2023-01-29T06:03:20Z) - 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) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。