論文の概要: The Survival Bandit Problem

• arxiv url: http://arxiv.org/abs/2206.03019v4
• Date: Sat, 6 Jan 2024 05:50:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-10 00:46:57.006516
• Title: The Survival Bandit Problem
• Title（参考訳）: 生存バンド問題
• Authors: Charles Riou and Junya Honda and Masashi Sugiyama
• Abstract要約: 我々は、サバイバル・バンディット問題(S-MAB)と呼ばれるマルチアーム・バンディット問題(MAB)の新たな変種を紹介し、研究する。 どちらの問題においても、いわゆる累積報酬を最大化することが目的であるが、この新しい変種では累積報酬が予め設定された閾値を下回った場合、手続きが中断される。 この単純なMABの拡張は、多くの実用的な応用から導かれる。
• 参考スコア（独自算出の注目度）: 65.68378556428861
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce and study a new variant of the multi-armed bandit problem (MAB), called the survival bandit problem (S-MAB). While in both problems, the objective is to maximize the so-called cumulative reward, in this new variant, the procedure is interrupted if the cumulative reward falls below a preset threshold. This simple yet unexplored extension of the MAB follows from many practical applications. For example, when testing two medicines against each other on voluntary patients, people's health are at stake, and it is necessary to be able to interrupt experiments if serious side effects occur or if the disease syndromes are not dissipated by the treatment. From a theoretical perspective, the S-MAB is the first variant of the MAB where the procedure may or may not be interrupted. We start by formalizing the S-MAB and we define its objective as the minimization of the so-called survival regret, which naturally generalizes the regret of the MAB. Then, we show that the objective of the S-MAB is considerably more difficult than the MAB, in the sense that contrary to the MAB, no policy can achieve a reasonably small (i.e., sublinear) survival regret. Instead, we minimize the survival regret in the sense of Pareto, i.e., we seek a policy whose cumulative reward cannot be improved for some problem instance without being sacrificed for another one. For that purpose, we identify two key components in the survival regret: the regret given no ruin (which corresponds to the regret in the MAB), and the probability that the procedure is interrupted, called the probability of ruin. We derive a lower bound on the probability of ruin, as well as policies whose probability of ruin matches the lower bound. Finally, based on a doubling trick on those policies, we derive a policy which minimizes the survival regret in the sense of Pareto, giving an answer to an open problem by Perotto et al. (COLT 2019).
• Abstract（参考訳）: 我々は、S-MABと呼ばれるマルチアームバンディット問題(MAB)の新たな変種を紹介し、研究する。 どちらの問題においても、いわゆる累積報酬を最大化することが目的であるが、この新しい変種では、累積報酬が予め設定されたしきい値を下回ると手続きが中断される。 この単純なMABの拡張は、多くの実用的な応用から導かれる。 例えば、自発的な患者に対して2つの薬剤を試験する場合、患者の健康が危うくなり、深刻な副作用が発生したり、疾患症候群が治療によって散逸しない場合、実験を中断できる必要がある。 理論的には、S-MABは、プロシージャを中断するかもしれないし、中断しないかもしれないMABの最初の変種である。 我々はまず,S-MABを形式化し,その目的を,MABの後悔を自然に一般化する,いわゆる生存後悔の最小化として定義する。 そして,S-MABの目的がMABよりもかなり難しいことを示し,MABとは対照的に,政策が合理的に小さい(サブリニアな)サバイバル後悔を達成できないことを示唆する。 代わりに、我々はパレートの意味での残忍な後悔を最小限に抑え、すなわち、別の問題のために犠牲にされることなく、ある問題に対して累積的な報酬を改善できない政策を模索する。 この目的のために、生存後悔の2つの重要な要素を同定した:(mabの後悔に相当する)無傷の後悔と、その手続きが中断される確率、すなわち崩壊の確率である。 我々は、破滅の確率と、破滅の確率が下限と一致する政策に基づいて、下限を導出する。 最後に,これらの政策の2倍のトリックに基づいて,ペロットらによるオープンな問題への回答として,パレートの意味での生存後悔を最小限に抑える政策を導出する(COLT 2019)。

関連論文リスト

• Survival Multiarmed Bandits with Bootstrapping Methods [0.0]
  Survival Multiarmed Bandits (S-MAB) 問題は、エージェントを観察された報酬に関連する予算に制限する拡張である。 本稿では, 破壊的逆転成分によってバランスの取れた目的関数を用いて, そのような双対目標に対処する枠組みを提案する。
  論文  参考訳（メタデータ） (2024-10-21T20:21:10Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals [28.94461817548213]
  条件付き良性環境と任意の環境下での学習性能におけるトレードオフの可能性について,上界と下界の整合性を証明した。 この問題を線形バンディット設定に還元することで、最初に因果バンディットのインスタンス依存境界を求める。
  論文  参考訳（メタデータ） (2024-07-01T04:12:15Z)
• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  我々は,エージェント群を協調させようとする学習者の視点で,マルチエージェント模倣学習(MAIL)問題を研究する。 MAILの以前の作業のほとんどは、基本的には、デモのサポート内で専門家の振る舞いにマッチする問題を減らすものです。 エージェントが戦略的でないという仮定の下で、学習者と専門家の間の価値ギャップをゼロにするのに十分であるが、戦略的エージェントによる逸脱を保証するものではない。
  論文  参考訳（メタデータ） (2024-06-06T16:18:20Z)
• Refining Minimax Regret for Unsupervised Environment Design [15.281908507614512]
  我々は,ミニマックス後悔目標の洗練であるレベル・パーフェクトMMRを導入する。 我々は,BLP政策がすべてのレベルにおける完全ベイズ政策と一貫して振る舞うことを示す。 また、収束時にBLPポリシーをもたらすアルゴリズムReMiDiを導入する。
  論文  参考訳（メタデータ） (2024-02-19T16:51:29Z)
• One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits [29.896865106960423]
  本稿では,emphSleeping Bandits における emphInternal Regret' の問題に対処する。 我々は, 完全に逆の損失と有効性の連続であっても, その尺度においてサブ線形後悔をもたらすアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-26T19:40:06Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Empirical or Invariant Risk Minimization? A Sample Complexity Perspective [49.43806345820883]
  In-variant risk generalization (IRM) が広く採用されている経験的リスク最小化(ERM)フレームワークよりも好まれるかどうかは不明である。 データ生成機構の種類によって、2つのアプローチは、非常に異なる有限サンプルと振舞いを持つ可能性がある。 さらに、OOD溶液からの距離に関して、異なる要因(環境の数、モデルの複雑さ、およびIRMのペナルティ重量)がIRMのサンプルの複雑さにどのように影響するかについても検討する。
  論文  参考訳（メタデータ） (2020-10-30T17:55:30Z)
• A Deep Q-learning/genetic Algorithms Based Novel Methodology For Optimizing Covid-19 Pandemic Government Actions [63.669642197519934]
  我々はSEIR疫学モデルを用いて、人口の時間とともにウイルスウイルスの進化を表現している。 報酬システムにより、アクションのシーケンス(統合、自己同化、二メートル距離、制限を取らない)を評価する。 どちらの意味でも、パンデミックの悪影響を抑えるために政府が取るべき行動を発見する上で、我々の方法論が有効な手段であることを実証する。
  論文  参考訳（メタデータ） (2020-05-15T17:17:45Z)

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

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