論文の概要: Best Arm Identification in Bandits with Limited Precision Sampling
- arxiv url: http://arxiv.org/abs/2305.06082v1
- Date: Wed, 10 May 2023 12:07:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 13:20:40.907307
- Title: Best Arm Identification in Bandits with Limited Precision Sampling
- Title(参考訳): 有限精度サンプリングを用いたバンドのベストアーム識別
- Authors: Kota Srinivas Reddy, P. N. Karthik, Nikhil Karamchandani and
Jayakrishnan Nair
- Abstract要約: 学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。
非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 14.011731120150124
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study best arm identification in a variant of the multi-armed bandit
problem where the learner has limited precision in arm selection. The learner
can only sample arms via certain exploration bundles, which we refer to as
boxes. In particular, at each sampling epoch, the learner selects a box, which
in turn causes an arm to get pulled as per a box-specific probability
distribution. The pulled arm and its instantaneous reward are revealed to the
learner, whose goal is to find the best arm by minimising the expected stopping
time, subject to an upper bound on the error probability. We present an
asymptotic lower bound on the expected stopping time, which holds as the error
probability vanishes. We show that the optimal allocation suggested by the
lower bound is, in general, non-unique and therefore challenging to track. We
propose a modified tracking-based algorithm to handle non-unique optimal
allocations, and demonstrate that it is asymptotically optimal. We also present
non-asymptotic lower and upper bounds on the stopping time in the simpler
setting when the arms accessible from one box do not overlap with those of
others.
- Abstract(参考訳): 学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。
学習者は特定の探索バンドルを通してのみ腕をサンプリングできる。
特に、各サンプリングエポックにおいて、学習者はボックスを選択し、その結果、ボックス固有の確率分布に従って腕を引っ張られる。
抽出したアームとその即時報酬を学習者に明らかにし、予測停止時間を最小化し、エラー確率の上限に照らして最適なアームを見つけることを目標とする。
予測停止時間の漸近的下限を示し,誤差確率が消失するときに保持する。
下限によって提案される最適割り当ては一般には非一様であり、従って追跡することが困難であることを示す。
非一様最適割当を扱うための改良型追従ベースアルゴリズムを提案し,漸近的最適であることを示す。
また,一方のボックスからアクセス可能な腕が他方のボックスと重なり合っていない場合に,停止時間に非漸近的下限と上限を簡単な設定で提示する。
関連論文リスト
- Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed
Gaussian Bandits with Unknown Variances [10.470114319701576]
本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。
以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
論文 参考訳(メタデータ) (2023-12-20T03:28:49Z) - Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a
Fixed Budget [10.470114319701576]
本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。
分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。
GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
論文 参考訳(メタデータ) (2023-10-30T17:52:46Z) - Optimal Best Arm Identification with Fixed Confidence in Restless
Bandits [72.86567379444153]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳(メタデータ) (2023-10-20T10:04:05Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳(メタデータ) (2023-08-29T18:18:21Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。
我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-01T18:20:10Z) - Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。
本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文 参考訳(メタデータ) (2022-10-14T13:09:11Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳(メタデータ) (2022-03-29T04:58:04Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳(メタデータ) (2021-05-22T02:46:04Z) - Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
論文 参考訳(メタデータ) (2020-12-07T08:23:08Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Ballooning Multi-Armed Bandits [12.205797997133397]
バルーン式マルチアーマッドバンド(BL-MAB)について紹介する。
BL-MABでは、利用可能なアームのセットは時間とともに成長する。
ベストアームが任意のタイミングで到着する確率が等しく高い場合、サブリニアな後悔は達成できないことを示す。
論文 参考訳(メタデータ) (2020-01-24T04:35:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。