論文の概要: Best Arm Identification for Stochastic Rising Bandits

• arxiv url: http://arxiv.org/abs/2302.07510v2
• Date: Thu, 1 Jun 2023 12:22:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-03 00:25:41.990870
• 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 (SRBs) は、選択肢の期待される報酬が選択されるたびに増加する、シーケンシャルな意思決定の問題をモデル化する。 本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。 提案手法は,UCBライクなアプローチを取り入れたR-UCBEと,連続的なリジェクション手順を用いたR-SRという2つのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 93.12525232849706
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic Rising Bandits (SRBs) model sequential decision-making problems in which the expected rewards of the available options increase every time they are selected. This setting captures a wide range of scenarios in which the available options are learning entities whose performance improves (in expectation) over time. While previous works addressed the regret minimization problem, this paper, focuses on the fixed-budget Best Arm Identification (BAI) problem for SRBs. In this scenario, given a fixed budget of rounds, we are asked to provide a recommendation about the best option at the end of the identification 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. Then, we prove that, with a sufficiently large budget, they provide guarantees on the probability of properly identifying the optimal option at the end of the learning process. Furthermore, we derive a lower bound on the error probability, matched by our R-SR (up to logarithmic factors), and illustrate how the need for a sufficiently large budget is unavoidable in the SRB setting. Finally, we numerically validate the proposed algorithms in both synthetic and real-world environments and compare them with the currently available BAI strategies.
• Abstract（参考訳）: 確率的上昇バンディット(srbs)は、選択する度に利用可能なオプションの期待報酬が増加する逐次的な意思決定問題である。 この設定は、利用可能な選択肢が、時間とともにパフォーマンスが向上する(期待して)学習エンティティである、幅広いシナリオをキャプチャします。 先行研究が後悔の最小化問題に対処する一方で,本論文はsrbsにおける固定予算最善アーム識別(bai)問題に焦点を当てている。 このシナリオでは、ラウンドの固定予算を前提として、識別プロセスの終了時に最適な選択肢について推奨することを求めます。 提案手法は, UCBのようなアプローチを取り入れたR-UCBEと, 逐次リジェクション手法を用いたR-SRという2つのアルゴリズムを提案する。 そして、十分な予算で、学習プロセスの終了時に最適な選択肢を適切に特定する確率を保証できることを証明した。 さらに、R-SR(対数因子まで)で一致した誤差確率の低い境界を導出し、SRB設定において十分に大きな予算の必要性が避けられないことを示す。 最後に,提案アルゴリズムを合成環境と実環境の両方で数値的に検証し,現在利用可能なBAI戦略と比較する。

関連論文リスト

• Contextual Bandits with Arm Request Costs and Delays [19.263086804406786]
  本稿では,時間的遅延と関連するコストを伴って,新たなアームセットを要求できるコンテキスト的バンディット問題の拡張を提案する。 この設定では、学習者は、各選択が1つの時間単位を取るように、決定セットから複数のアームを選択することができる。 我々は、武器を効果的に選択し、新しい武器を要求する適切な時間を決定するアルゴリズムを設計し、彼らの後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2024-10-17T00:44:50Z)
• Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits [0.0]
  対称な報酬分布のための分布自由データ駆動型 UCB アルゴリズムを提案する。 パラメータフリーなRMM-UCB法では,重み付き分布であっても,ほぼ最適の残差を証明した。
  論文  参考訳（メタデータ） (2024-06-09T10:06:50Z)
• Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits [3.5502600490147196]
  我々は、シャープ比(SR)が金融時系列の特徴付けにおける重要なパラメータであると考えている。 我々は、レギュレット最小化(RM)とBest Arm Identification(BAI)のために、UCB-RSSRと呼ばれるSRを最適化する新しいアルゴリズムを提案する。 UCB-RSSRは、他のSR最適化バンディットアルゴリズムであるU-UCB Cassel et al(2023)よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-05-28T14:24:36Z)
• 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)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• 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)

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

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