論文の概要: Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2503.02428v1
• Date: Tue, 04 Mar 2025 09:18:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:21:54.403652
• Title: Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
• Title（参考訳）: シングルパスストリーミング確率的マルチアーマッド帯域のタイトギャップ依存性メモリ-レグレットトレードオフ
• Authors: Zichun Ye, Chihao Zhang, Jiahao Zhao,
• Abstract要約: Omega_alphaBig(frac(k-m+1) Tfrac1alphak1 + frac1alpha+1 sum_i:Delta_i > 0Delta_i1 - 2alphaBig)$である。 これは、ストリーミングMABに対する最初の厳密なギャップ依存の後悔境界である。
• 参考スコア（独自算出の注目度）: 3.096236408131107
• License:
• Abstract: We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). In this problem, the $n$ arms are present in a stream, and at most $m<n$ arms and their statistics can be stored in the memory. We establish tight non-asymptotic regret bounds regarding all relevant parameters, including the number of arms $n$, the memory size $m$, the number of rounds $T$ and $(\Delta_i)_{i\in [n]}$ where $\Delta_i$ is the reward mean gap between the best arm and the $i$-th arm. These gaps are not known in advance by the player. Specifically, for any constant $\alpha \ge 1$, we present two algorithms: one applicable for $m\ge \frac{2}{3}n$ with regret at most $O_\alpha\Big(\frac{(n-m)T^{\frac{1}{\alpha + 1}}}{n^{1 + {\frac{1}{\alpha + 1}}}}\displaystyle\sum_{i:\Delta_i > 0}\Delta_i^{1 - 2\alpha}\Big)$ and another applicable for $m<\frac{2}{3}n$ with regret at most $O_\alpha\Big(\frac{T^{\frac{1}{\alpha+1}}}{m^{\frac{1}{\alpha+1}}}\displaystyle\sum_{i:\Delta_i > 0}\Delta_i^{1 - 2\alpha}\Big)$. We also prove matching lower bounds for both cases by showing that for any constant $\alpha\ge 1$ and any $m\leq k < n$, there exists a set of hard instances on which the regret of any algorithm is $\Omega_\alpha\Big(\frac{(k-m+1) T^{\frac{1}{\alpha+1}}}{k^{1 + \frac{1}{\alpha+1}}} \sum_{i:\Delta_i > 0}\Delta_i^{1-2\alpha}\Big)$. This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an $O\Big(\sum_{i\colon\Delta>0} \frac{\sqrt{T}\log T}{\Delta_i}\Big)$ upper bound for the special case of $\alpha=1$ and $m=O(1)$ was established by Agarwal, Khanna and Patil (COLT'22). In contrast, our results provide the correct order of regret as $\Theta\Big(\frac{1}{\sqrt{m}}\sum_{i\colon\Delta>0}\frac{\sqrt{T}}{\Delta_i}\Big)$.
• Abstract（参考訳）: シングルパスストリーミング確率的マルチアームバンディット(MAB)におけるギャップ依存的後悔の最小化問題について検討する。 この問題では、$n$armはストリームに存在し、少なくとも$m<n$armとその統計情報をメモリに格納することができる。 アーム数$n$、メモリサイズ$m$、ラウンド数$T$と$(\Delta_i)_{i\in [n]}$など、関連するすべてのパラメータに関する厳密な非漸近的後悔境界を確立します。 これらのギャップは、プレーヤによって事前に知られていない。 具体的には、任意の定数$\alpha \ge 1$に対して、$m\ge \frac{2}{3}n$に対して、最大で$O_\alpha\Big(\frac{(n-m)T^{\frac{1}{\alpha + 1}}}{n^{1 + {\frac{1}{\alpha + 1}} {\displaystyle \sum_{i:\Delta_i > 0}\Delta_i^{1 - 2\alpha}\Big)$に対して、最大で$O_\alpha\Big(\frac{T^{\frac{1}{\alpha+1}}}{m^{\frac{1}{\alpha+1}}}}}}{m^{\pha{1}{\alpha+1}}} に対して、最大で$O_\alpha\Big(\frac{T^{\frac{1}{\alpha+1}}}}}}{m^{\frac{1}{\alpha + 1}}$2\alpha}\Big)$に該当する。 また、任意の定数 $\alpha\ge 1$ と任意の $m\leq k < n$ に対して、任意のアルゴリズムの後悔が $\Omega_\alpha\Big(\frac{(k-m+1) T^{\frac{1}{\alpha+1}}}{k^{1 + \frac{1}{\alpha+1}}} \sum_{i:\Delta_i > 0}\Delta_i^{1-2\alpha}\Big)$ であるようなハードなインスタンスが存在することを示すことによって、両方のケースの一致を証明している。 これは、ストリーミングMABに対する最初の厳密なギャップ依存の後悔境界である。 O\Big(\sum_{i\colon\Delta>0} \frac{\sqrt{T}\log T}{\Delta_i}\Big)$$$\alpha=1$および$m=O(1)$は、Agarwal, Khanna and Patil (COLT'22)によって確立された。 対照的に、我々の結果は、$\Theta\Big(\frac{1}{\sqrt{m}}\sum_{i\colon\Delta>0}\frac{\sqrt{T}}{\Delta_i}\Big)$として正しい後悔の順序を提供する。

関連論文リスト

• Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap [9.095990028343369]
  マルチパスストリーミングマルチアームバンディット(MAB)における純粋探索のためのサンプルメモリパストレードオフについて検討する。 最初に下界を示し、わずかにサブ線形メモリを持つ最適なアームを見つけるアルゴリズム -- $o(n/textpolylog(n))$ arms -- と $O(sum_i=2n1/Delta2_[i][i]cdot logn)$ arm pulls を示す。 すると、私たちはほとんど姿を現す。
  論文  参考訳（メタデータ） (2025-02-03T05:24:35Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
  我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。 その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
  論文  参考訳（メタデータ） (2023-07-14T10:38:30Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。 改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
  論文  参考訳（メタデータ） (2023-05-24T17:40:57Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• 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)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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