論文の概要: Best Arm Identification for Stochastic Rising Bandits
- arxiv url: http://arxiv.org/abs/2302.07510v1
- Date: Wed, 15 Feb 2023 08:01:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 15:44:57.929031
- Title: Best Arm Identification for Stochastic Rising Bandits
- Title(参考訳): 確率的ライジングバンドのためのベストアーム識別
- Authors: Marco Mussi, Alessandro Montenegro, Francesco Trov\'o, Marcello
Restelli and Alberto Maria Metelli
- Abstract要約: Rising Banditsは、利用可能なオプションの期待される報酬の値が選択される度に増加する設定である。
このフレームワークは、利用可能な選択肢が時間とともにパフォーマンスが向上する学習エンティティである幅広いシナリオをモデル化する。
提案手法は,UCBライクなアプローチを取り入れたR-UCBEと,連続的なリジェクション手順を用いたR-SRという2つのアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 93.12525232849706
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic Rising Bandits is a setting in which the values of the expected
rewards of the available options increase every time they are selected. This
framework models a wide range of scenarios in which the available options are
learning entities whose performance improves over time. In this paper, we focus
on the Best Arm Identification (BAI) problem for the stochastic rested rising
bandits. In this scenario, we are asked, given a fixed budget of rounds, to
provide a recommendation about the best option at the end of the selection
process. We propose two algorithms to tackle the above-mentioned setting,
namely R-UCBE, which resorts to a UCB-like approach, and R-SR, which employs a
successive reject procedure. We show that they provide guarantees on the
probability of properly identifying the optimal option at the end of the
learning process. Finally, we numerically validate the proposed algorithms in
synthetic and realistic environments and compare them with the currently
available BAI strategies.
- Abstract(参考訳): 確率的ライジングバンド(Stochastic Rising Bandits)は、オプションが選択されるたびに、期待される報酬の値が増加する設定である。
このフレームワークは、利用可能なオプションが時間とともにパフォーマンスが向上するエンティティを学習する幅広いシナリオをモデル化する。
本稿では,確率的レストアップバンディットにおけるベストアーム識別(BAI)問題に着目した。
このシナリオでは、一定の予算が与えられたラウンドに対して、選択プロセスの終了時に最適な選択肢を推奨するように求められます。
提案手法は, UCBのようなアプローチを取り入れたR-UCBEと, 逐次リジェクション手法を用いたR-SRという2つのアルゴリズムを提案する。
学習プロセスの最後に最適な選択肢を適切に特定する確率を保証していることを示す。
最後に,提案したアルゴリズムを合成・現実的に検証し,現在利用可能なBAI戦略と比較する。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳(メタデータ) (2022-12-12T21:37:36Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳(メタデータ) (2022-12-07T17:30:45Z) - Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。
本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。
また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
論文 参考訳(メタデータ) (2022-11-27T08:58:16Z) - Semiparametric Best Arm Identification with Contextual Information [10.915684166086026]
バンディット問題において,固定予算と文脈情報を用いたベストアーム識別について検討した。
本研究では,ターゲットアロケーション比とレコメンデーションルールを追跡するランダムサンプリングルールとからなる「コンテキストRS-AIPW戦略」を開発する。
提案手法は,予算が無限に進むと,誤識別確率の上限が半下限と一致するため,最適である。
論文 参考訳(メタデータ) (2022-09-15T14:38:47Z) - Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。
このアプローチは多くの実装と最適化の課題をもたらします。
提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
論文 参考訳(メタデータ) (2021-03-18T14:26:26Z) - Correlated Bandits for Dynamic Pricing via the ARC algorithm [2.7564955518050693]
漸近ランダム化制御(Asymptotic Randomized Control)は、ベイズバンドの幅広いクラスに対する最適な戦略に厳密な近似を与える。
これにより、意思決定者は報酬に加えて信号を観察し、異なる選択の結果の相関を組み込むことができ、見積もりに非自明なダイナミクスを持つことができる。
論文 参考訳(メタデータ) (2021-02-08T14:54:26Z) - Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
問合せ予算で意思決定問題を定式化する。
我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。
我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
論文 参考訳(メタデータ) (2021-02-05T19:56:31Z) - Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
マルコフ連鎖の適応制御のためのRBMLE(Reward-Biased Maximum Likelihood Estimate)を提案した。
我々は、現在最先端のアルゴリズムと同様に、$mathcalO( log T)$が$T$の時間的水平線上で後悔していることを示します。
論文 参考訳(メタデータ) (2020-11-16T06:09:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。