論文の概要: Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

• arxiv url: http://arxiv.org/abs/2606.08977v1
• Date: Mon, 08 Jun 2026 03:21:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:06.676955
• Title: Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
• Title（参考訳）: 待ち時間によるオンライン学習:マルチアームバンドのスライディングウインドウストリーミングのためのアルゴリズム
• Authors: Vladimir Braverman, Chen Wang, Liudeng Wang, Samson Zhou,
• Abstract要約: 本稿では,シングルパス*スライディングウインドウストリーミングマルチアームバンディット(MAB)のアルゴリズムについて検討する。 この設定では、未知のガウスの報酬分布を持つ$n$アームとパラメータ$W$が与えられる。 アームはシングルパスストリームに到達し、最新の$W$アームのみが有効と考えられる。
• 参考スコア（独自算出の注目度）: 28.239402296592967
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the recency effect in online learning, we study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper. In this setting, we are given $n$ arms with unknown sub-Gaussian reward distributions and a parameter $W$. The arms arrive in a single-pass stream, and only the most recent $W$ arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.
• Abstract（参考訳）: 本稿では,オンライン学習における遅延効果に触発され,シングルパス*スライディングウインドウ・ストリーミングマルチアーム・バンディット(MABs)のアルゴリズムについて研究する。 この設定では、未知のガウスの報酬分布を持つ$n$アームとパラメータ$W$が与えられる。 アームはシングルパスストリームに到達し、最新の$W$アームのみが有効と考えられる。 このアルゴリズムは、記憶された武器の数として定義された限られたメモリで純粋な探索と後悔の最小化を実行するために必要である。 このモデルは、近年広く研究されているストリーミングマルチアームバンディットモデルの自然な拡張である。 モデルにおける純粋探索と後悔の最小化の問題の両方を包括的に分析する。 純粋な探索において、最適なアームを見つけることは、線形メモリでは困難である一方で、近似した最適なアームを見つけることは、効率的なアルゴリズムを持つことを証明している。 後悔の最小化のために、後悔の新たな概念を探求し、任意のシングルパスアルゴリズムに対してシャープなメモリ-レグレットトレードオフを与える。 理論的結果を実験で補完し、サンプル、後悔、記憶のトレードオフを実証する。

関連論文リスト

• On the Problem of Best Arm Retention [2.9772441757190746]
  BAR(Best Arm Retention)の問題について検討し、最近マルチアームバンディットのストリーミングアルゴリズムに応用されている。 まず,異なる基準下でのBAR問題の純粋探索と,特定の制約による後悔の最小化について検討する。
  論文  参考訳（メタデータ） (2025-04-16T08:41:20Z)
• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  本論文は、連続マルチアーマッドバンド(MAB)の分野である。 我々は,腕の期待される報酬が単調に非減少性であり,結束する残留包帯の特定の症例について検討した。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2024-11-06T22:00:46Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
  本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。 我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。 また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
  論文  参考訳（メタデータ） (2021-06-08T21:26:57Z)
• 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 Algorithms for Stochastic Multi-armed Bandits [1.4932318540666543]
  有界アームメモリにおけるマルチアームバンド問題について検討する。 後悔最小化のために,n が腕の数である (n-1) の腕記憶サイズへの期待において,Omega(T2/3) 累積後悔を示す。 ベストアーム識別には,2つのアルゴリズムについて検討する。 まず,O(r) アームメモリ r ラウンド適応ストリーミングアルゴリズムを用いて,エプシロンベストアームの探索を行う。
  論文  参考訳（メタデータ） (2020-12-09T16:28:05Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。 我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2020-06-26T04:01:46Z)

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

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