論文の概要: Lenient Regret for Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2008.03959v4
• Date: Sun, 12 Sep 2021 12:22:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-31 22:19:04.699880
• Title: Lenient Regret for Multi-Armed Bandits
• Title（参考訳）: 多関節バンドに対するLenient Regret
• Authors: Nadav Merlis, Shie Mannor
• Abstract要約: エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
• 参考スコア（独自算出の注目度）: 72.56064196252498
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the Multi-Armed Bandit (MAB) problem, where an agent sequentially chooses actions and observes rewards for the actions it took. While the majority of algorithms try to minimize the regret, i.e., the cumulative difference between the reward of the best action and the agent's action, this criterion might lead to undesirable results. For example, in large problems, or when the interaction with the environment is brief, finding an optimal arm is infeasible, and regret-minimizing algorithms tend to over-explore. To overcome this issue, algorithms for such settings should instead focus on playing near-optimal arms. To this end, we suggest a new, more lenient, regret criterion that ignores suboptimality gaps smaller than some $\epsilon$. We then present a variant of the Thompson Sampling (TS) algorithm, called $\epsilon$-TS, and prove its asymptotic optimality in terms of the lenient regret. Importantly, we show that when the mean of the optimal arm is high enough, the lenient regret of $\epsilon$-TS is bounded by a constant. Finally, we show that $\epsilon$-TS can be applied to improve the performance when the agent knows a lower bound of the suboptimality gaps.
• Abstract（参考訳）: 我々は,エージェントがアクションを順次選択し,そのアクションに対する報酬を観察するマルチアームド・バンディット(mab)問題を考える。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 例えば、大きな問題や環境との相互作用が短い場合、最適な腕を見つけることは不可能であり、後悔を最小化するアルゴリズムは過剰に現れる傾向がある。 この問題を克服するために、このような設定のアルゴリズムは、ほとんど最適に近いアームをプレイすることに焦点を当てるべきである。 この目的のために私たちは、$\epsilon$よりも小さい最適化性ギャップを無視する、より寛大で後悔的な新しい基準を提案します。 次に、トンプソンサンプリング(TS)アルゴリズムの変種である$\epsilon$-TSを示し、その漸近的最適性を、寛大な後悔の観点から証明する。 重要なことに、最適アームの平均値が十分に高い場合、$\epsilon$-TSの寛大な後悔は定数で束縛される。 最後に,$\epsilon$-TSを適用することで,エージェントがサブ最適ギャップの低い境界を知っていれば,性能を向上させることができることを示す。

関連論文リスト

• Learning for Bandits under Action Erasures [20.235500642661812]
  我々は,学習者が消去チャネル上で分散エージェントにアクションを伝える必要がある,新しいマルチアーム・バンディット(MAB)について考察する。 我々のモデルでは、分散エージェントはアクションが消去されるかどうかを知っているが、中心的な学習者は知らない。 本稿では,既存のMABアルゴリズム上で動作可能な手法を提案する。
  論文  参考訳（メタデータ） (2024-06-26T05:03:00Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice [26.769372199571002]
  我々は、強い適応的後悔という厳密な概念の下で、クエリと後悔の最適包帯アルゴリズムを与える。 驚いたことに、1ラウンドあたり2つのクエリで$tildeO(sqrtn|I|)$ Adaptive Bandit Learner(StABL)を達成できる。
  論文  参考訳（メタデータ） (2024-01-17T15:32:04Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality [25.627939043735683]
  我々は後悔を最小限に抑えるために構造化された包帯について研究する。 本稿では,有限仮説に焦点をあて,有界後悔を楽しみながら最適性を達成できるかを問う。
  論文  参考訳（メタデータ） (2020-06-15T20:46:52Z)

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

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