論文の概要: Tight Memory-Regret Lower Bounds for Streaming Bandits
- arxiv url: http://arxiv.org/abs/2306.07903v1
- Date: Tue, 13 Jun 2023 16:54:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 12:43:13.127640
- Title: Tight Memory-Regret Lower Bounds for Streaming Bandits
- Title（参考訳）: ストリーミング帯域における高記憶率下界
- Authors: Shaoang Li, Lan Zhang, Junhao Wang, Xiang-Yang Li
- Abstract要約: 学習者は オンラインの腕と サブリニアの腕の記憶を扱うことで 後悔を最小化することを目的としています
我々は,任意のアルゴリズムに対して,Omega left((TB)alpha K1-alpharight), α = 2B / (2B+1-1)$という,厳密な最悪ケースの残差を低く設定する。
また、一定のアームメモリを用いて、左(TB)アルファK1-αright)$の後悔の上限を達成できるマルチパスアルゴリズムも提供する。
- 参考スコア（独自算出の注目度）: 11.537938617281736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we investigate the streaming bandits problem, wherein the
learner aims to minimize regret by dealing with online arriving arms and
sublinear arm memory. We establish the tight worst-case regret lower bound of
$\Omega \left( (TB)^{\alpha} K^{1-\alpha}\right), \alpha = 2^{B} / (2^{B+1}-1)$
for any algorithm with a time horizon $T$, number of arms $K$, and number of
passes $B$. The result reveals a separation between the stochastic bandits
problem in the classical centralized setting and the streaming setting with
bounded arm memory. Notably, in comparison to the well-known
$\Omega(\sqrt{KT})$ lower bound, an additional double logarithmic factor is
unavoidable for any streaming bandits algorithm with sublinear memory
permitted. Furthermore, we establish the first instance-dependent lower bound
of $\Omega \left(T^{1/(B+1)} \sum_{\Delta_x>0} \frac{\mu^*}{\Delta_x}\right)$
for streaming bandits. These lower bounds are derived through a unique
reduction from the regret-minimization setting to the sample complexity
analysis for a sequence of $\epsilon$-optimal arms identification tasks, which
maybe of independent interest. To complement the lower bound, we also provide a
multi-pass algorithm that achieves a regret upper bound of $\tilde{O} \left(
(TB)^{\alpha} K^{1 - \alpha}\right)$ using constant arm memory.
- Abstract（参考訳）: 本稿では,オンライン到着アームとサブリニアアームメモリを扱うことで,後悔を最小限に抑えることを目的としたストリーミングバンディット問題を検討する。
我々は、時間軸$t$、アーム数$k$、パス数$b$ の任意のアルゴリズムに対して、厳密な最悪の場合には、$\omega \left( (tb)^{\alpha} k^{1-\alpha}\right), \alpha = 2^{b} / (2^{b+1}-1)$という下限を定める。
その結果,古典的集中型設定における確率的バンディット問題と,有界なアームメモリを用いたストリーミング設定との分離が明らかになった。
特に、よく知られた$\Omega(\sqrt{KT})$ lowerboundと比較して、追加の二重対数係数は、サブ線形メモリが許される任意のストリーミング帯域アルゴリズムでは避けられない。
さらに,ストリーミングブレイディットに対して,最初のインスタンス依存下界を$\Omega \left(T^{1/(B+1)} \sum_{\Delta_x>0} \frac{\mu^*}{\Delta_x}\right)$とする。
これらの下限は、おそらく独立した関心を持つ$\epsilon$-optimal arms identificationタスクの列に対する、後悔最小化設定からサンプル複雑性解析への一意な還元によって導かれる。
下限を補うために、一定のアームメモリを用いて$\tilde{o} \left( (tb)^{\alpha} k^{1 - \alpha}\right)$の後悔の上限を達成するマルチパスアルゴリズムも提供する。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - 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) - On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。
その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
論文 参考訳（メタデータ） (2023-07-14T10:38:30Z) - 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) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - 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) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。