論文の概要: Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals
- arxiv url: http://arxiv.org/abs/2306.07071v2
- Date: Tue, 15 Aug 2023 10:55:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-16 16:29:42.498174
- Title: Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals
- Title（参考訳）: 非対称信頼区間を有する予算付きマルチアームバンディット
- Authors: Marco Heyden, Vadim Arzamasov, Edouard Fouch\'e, Klemens B\"ohm
- Abstract要約: 予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
- 参考スコア（独自算出の注目度）: 0.9831489366502302
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study the stochastic Budgeted Multi-Armed Bandit (MAB) problem, where a
player chooses from $K$ arms with unknown expected rewards and costs. The goal
is to maximize the total reward under a budget constraint. A player thus seeks
to choose the arm with the highest reward-cost ratio as often as possible.
Current state-of-the-art policies for this problem have several issues, which
we illustrate. To overcome them, we propose a new upper confidence bound (UCB)
sampling policy, $\omega$-UCB, that uses asymmetric confidence intervals. These
intervals scale with the distance between the sample mean and the bounds of a
random variable, yielding a more accurate and tight estimation of the
reward-cost ratio compared to our competitors. We show that our approach has
logarithmic regret and consistently outperforms existing policies in synthetic
and real settings.
- Abstract（参考訳）: 確率的Budgeted Multi-Armed Bandit (MAB) 問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
目標は、予算制約の下での全報酬を最大化することです。
プレイヤーは、最も高い報酬コスト比率の腕をできるだけ頻繁に選択しようとする。
この問題に対する現在の最先端のポリシーにはいくつかの問題がある。
そこで本稿では,非対称な信頼区間を用いた新しい高信頼境界(UCB)サンプリングポリシーである$\omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、我々の競合相手と比較してより正確で厳密な報酬コスト比を推定する。
我々のアプローチは対数的後悔であり、合成および実環境における既存のポリシーを一貫して上回っていることを示す。
関連論文リスト
- Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。
目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。
我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
論文 参考訳（メタデータ） (2024-05-23T22:35:11Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances [12.00630538470713]
不均一な報酬分散を伴う固定予算設定におけるベストアーム識別(BAI)の問題について検討する。
本稿では, 既知報酬分散に対するSHVarと未知報酬分散に対するSHAdaVarの2つの分散適応型BAIアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-13T05:41:38Z) - Covariance Adaptive Best Arm Identification [0.0]
ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。
武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。
この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
論文 参考訳（メタデータ） (2023-06-05T06:57:09Z) - BanditQ: Fair Bandits with Guaranteed Rewards [10.74025233418392]
古典的な非レグレットなマルチアームバンディットアルゴリズムは本質的に不公平である。
我々は、後悔と目標レート違反を容認しつつ、目標報酬率を達成する、BanditQと呼ばれる新しいオンラインポリシーを提案する。
提案手法は効率的で,公正な予測問題から標準逆MAB問題へのブラックボックス削減を許容する。
論文 参考訳（メタデータ） (2023-04-11T13:39:47Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-16T17:52:32Z) - A Farewell to Arms: Sequential Reward Maximization on a Budget with a
Giving Up Option [5.1629297054995265]
エージェントが一度にひとつのアクションを採り、各アクションが時間的範囲を持つような、シーケンシャルな意思決定問題を考える。
我々は、対数的、問題依存的後悔境界を確立する上で、高い信頼度に基づくアルゴリズム(WAIT-UCB)を導入する。
論文 参考訳（メタデータ） (2020-03-06T22:16:20Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。