論文の概要: Satisficing Exploration in Bandit Optimization
- arxiv url: http://arxiv.org/abs/2406.06802v1
- Date: Mon, 10 Jun 2024 21:15:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-12 20:05:58.669538
- Title: Satisficing Exploration in Bandit Optimization
- Title(参考訳): 帯域最適化における満足度探索
- Authors: Qing Feng, Tianyi Ma, Ruihao Zhu,
- Abstract要約: 本稿では,LowEr Confidence bound TestingによるSatificing Explorationのための一般的なアルゴリズムテンプレートを提案する。
われわれはこの託宣を利用して、後悔の少ない潜在的な満足のいく腕を特定する。
補体として、SELECTは非実現可能な場合のオラクルと同じ(標準的な)後悔の保証を享受する。
- 参考スコア(独自算出の注目度): 5.03122566946086
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by the concept of satisficing in decision-making, we consider the problem of satisficing exploration in bandit optimization. In this setting, the learner aims at selecting satisficing arms (arms with mean reward exceeding a certain threshold value) as frequently as possible. The performance is measured by satisficing regret, which is the cumulative deficit of the chosen arm's mean reward compared to the threshold. We propose SELECT, a general algorithmic template for Satisficing Exploration via LowEr Confidence bound Testing, that attains constant satisficing regret for a wide variety of bandit optimization problems in the realizable case (i.e., a satisficing arm exists). Specifically, given a class of bandit optimization problems and a corresponding learning oracle with sub-linear (standard) regret upper bound, SELECT iteratively makes use of the oracle to identify a potential satisficing arm with low regret. Then, it collects data samples from this arm, and continuously compares the LCB of the identified arm's mean reward against the threshold value to determine if it is a satisficing arm. As a complement, SELECT also enjoys the same (standard) regret guarantee as the oracle in the non-realizable case. Finally, we conduct numerical experiments to validate the performance of SELECT for several popular bandit optimization settings.
- Abstract(参考訳): 意思決定における満足度の概念に触発され,帯域最適化における満足度探索の問題を考える。
この設定では、学習者は、満足度の高いアーム(一定の閾値を超える平均報酬を持つアーム)をできるだけ頻繁に選択することを目的とする。
この性能は、選択した腕の平均報酬の累積損失である後悔を満足させることによって測定される。
本稿では,SELECTを提案する。SELECTは,低信頼境界試験による探索を満足させる汎用的なアルゴリズムテンプレートであり,実現可能な場合(つまり,満足度アームが存在する)において,幅広い帯域最適化問題に対して常に満足のいく後悔を実現する。
具体的には、一連の帯域最適化問題と、サブ線形(標準)後悔の上界を持つ学習オラクルが与えられた場合、SELECTは、そのオラクルを反復的に使用して、後悔の少ない潜在的な満足する腕を特定する。
そして、この腕からデータサンプルを収集し、識別された腕の平均報酬のLCBをしきい値と比較し、それが満足のいく腕かどうかを判定する。
補体として、SELECTは非実現可能な場合のオラクルと同じ(標準的な)後悔の保証も享受する。
最後に,SELECTの性能評価のための数値実験を行った。
関連論文リスト
- Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳(メタデータ) (2024-09-27T16:46:02Z) - Neural Dueling Bandits [58.90189511247936]
ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。
次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
論文 参考訳(メタデータ) (2024-07-24T09:23:22Z) - Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Proportional Response: Contextual Bandits for Simple and Cumulative
Regret Minimization [29.579719765255927]
本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。
我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
論文 参考訳(メタデータ) (2023-07-05T08:34:54Z) - Best Arm Identification with Fairness Constraints on Subpopulations [11.349636358427485]
サブポピュレーション(BAICS)におけるフェアネス制約によるベストアーム識別の問題を定式化し,解析し,解決する。
BAICSの問題は、選択された腕が全てのサブ集団に公平でなければならないことである。
我々は、閉形式表現を用いて、標本複雑性の最も達成可能な下界を証明した。
論文 参考訳(メタデータ) (2023-04-08T19:41:02Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-09-15T16:59:19Z) - Break your Bandit Routine with LSD Rewards: a Last Switch Dependent
Analysis of Satiation and Seasonality [6.146046338698175]
そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。
我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。
我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
論文 参考訳(メタデータ) (2021-10-22T14:53:13Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。