論文の概要: 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つだけ格納することで,最適なサンプル複雑性を持つ「エプシロン」-ベストアームを見つけるヒューリスティックを提案する。
関連論文リスト
- Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳(メタデータ) (2023-10-24T09:47:32Z) - Best Arm Identification in Bandits with Limited Precision Sampling [14.011731120150124]
学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。
非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-05-10T12:07:48Z) - 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) - Quantum exploration algorithms for multi-armed bandits [15.666205208594567]
我々は、$tildeObigl(sqrtsum_i=2nDeltasmash-2_ibigr)$quantum query.sqrtsum_i=2nDeltasmash-2_ibigr)を用いて、信頼度の高い最適なアームを見つけることができることを示す。
このアルゴリズムは、可変時間振幅増幅と推定に基づいて、可能な限りの古典的な結果と比較して二次的なスピードアップを与える。
論文 参考訳(メタデータ) (2020-07-14T14:15:20Z) - 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) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-23T19:52:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。