論文の概要: Streaming Algorithms for Stochastic Multi-armed Bandits

• arxiv url: http://arxiv.org/abs/2012.05142v1
• Date: Wed, 9 Dec 2020 16:28:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-16 02:06:59.335223
• Title: Streaming Algorithms for Stochastic Multi-armed Bandits
• Title（参考訳）: 確率的マルチアーム帯域のストリーミングアルゴリズム
• Authors: Arnab Maiti, Vishakha Patil, Arindam Khan
• Abstract要約: 有界アームメモリにおけるマルチアームバンド問題について検討する。 後悔最小化のために,n が腕の数である (n-1) の腕記憶サイズへの期待において,Omega(T2/3) 累積後悔を示す。 ベストアーム識別には,2つのアルゴリズムについて検討する。 まず,O(r) アームメモリ r ラウンド適応ストリーミングアルゴリズムを用いて,エプシロンベストアームの探索を行う。
• 参考スコア（独自算出の注目度）: 1.4932318540666543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the Stochastic Multi-armed Bandit problem under bounded arm-memory. In this setting, the arms arrive in a stream, and the number of arms that can be stored in the memory at any time, is bounded. The decision-maker can only pull arms that are present in the memory. We address the problem from the perspective of two standard objectives: 1) regret minimization, and 2) best-arm identification. For regret minimization, we settle an important open question by showing an almost tight hardness. We show {\Omega}(T^{2/3}) cumulative regret in expectation for arm-memory size of (n-1), where n is the number of arms. For best-arm identification, we study two algorithms. First, we present an O(r) arm-memory r-round adaptive streaming algorithm to find an {\epsilon}-best arm. In r-round adaptive streaming algorithm for best-arm identification, the arm pulls in each round are decided based on the observed outcomes in the earlier rounds. The best-arm is the output at the end of r rounds. The upper bound on the sample complexity of our algorithm matches with the lower bound for any r-round adaptive streaming algorithm. Secondly, we present a heuristic to find the {\epsilon}-best arm with optimal sample complexity, by storing only one extra arm in the memory.
• Abstract（参考訳）: 有界アームメモリにおける確率的マルチアームバンド問題について検討する。 この設定では、アームはストリームに到達し、いつでもメモリに格納できるアームの数は境界となる。 意思決定者は記憶にある腕だけを引っ張ることができます。 1) 後悔の最小化, 2) ベストアームの識別という2つの標準目標からこの問題に対処した。 後悔の最小化のために、我々はほとんど固い硬さを示すことで重要なオープンな疑問を解決した。 我々は、(n-1) のアームメモリサイズを期待して (Omega)(T^{2/3}) 累積後悔を示し、n はアームの数である。 ベストアーム識別には2つのアルゴリズムを検討する。 まず、o(r)アームメモリのrラウンド適応型ストリーミングアルゴリズムを示し、"epsilon}-best armを求める。 最良アーム識別のためのrラウンド適応ストリーミングアルゴリズムでは、各ラウンドのアームプルは、前ラウンドの観測結果に基づいて決定される。 最善の武器はrラウンドの終了時の出力である。 我々のアルゴリズムのサンプル複雑性の上限は、任意のrラウンド適応ストリーミングアルゴリズムの下位境界と一致する。 第2に,メモリに余分なアームを1つだけ格納することで,最適なサンプル複雑性を持つ「エプシロン」-ベストアームを見つけるヒューリスティックを提案する。

関連論文リスト

• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• Continuous Time Bandits With Sampling Costs [17.412117389855222]
  連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。 サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。 目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
  論文  参考訳（メタデータ） (2021-07-12T10:00:35Z)
• 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)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。 我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2020-06-26T04:01:46Z)

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

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