論文の概要: 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)。
関連論文リスト
- Refining Minimax Regret for Unsupervised Environment Design [16.048230822567806]
我々は,ミニマックス後悔目標の洗練であるレベル・パーフェクトMMRを導入する。
我々は,BLP政策がすべてのレベルにおける完全ベイズ政策と一貫して振る舞うことを示す。
また、収束時にBLPポリシーをもたらすアルゴリズムReMiDiを導入する。
論文 参考訳(メタデータ) (2024-02-19T16:51:29Z) - Is Epistemic Uncertainty Faithfully Represented by Evidential Deep
Learning Methods? [12.88166582566313]
本稿では,顕在的深層学習の新たな理論的考察について述べる。
これは二階損失関数の最適化の難しさを強調している。
第二次損失最小化における識別可能性と収束性の問題に関する新たな洞察を提供する。
論文 参考訳(メタデータ) (2024-02-14T10:07:05Z) - On Penalization in Stochastic Multi-armed Bandits [22.04356596828437]
本稿では,マルチアーム・バンディット(MAB)問題の重要な変種について検討し,ペナルティ化を考慮に入れた。
フェアネス、ほぼ最適の後悔、報酬とフェアネスのトレードオフの改善など、多くのメリットを享受する難解なUPBライクなアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-15T17:13:09Z) - 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) - MIRST-DM: Multi-Instance RST with Drop-Max Layer for Robust
Classification of Breast Cancer [62.997667081978825]
MIRST-DMと呼ばれるドロップマックス層を用いたマルチインスタンスRTTを提案し、小さなデータセット上でよりスムーズな決定境界を学習する。
提案手法は1,190画像の小さな乳房超音波データセットを用いて検証した。
論文 参考訳(メタデータ) (2022-05-02T20:25:26Z) - 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) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳(メタデータ) (2020-08-20T03:48:14Z) - A Deep Q-learning/genetic Algorithms Based Novel Methodology For
Optimizing Covid-19 Pandemic Government Actions [63.669642197519934]
我々はSEIR疫学モデルを用いて、人口の時間とともにウイルスウイルスの進化を表現している。
報酬システムにより、アクションのシーケンス(統合、自己同化、二メートル距離、制限を取らない)を評価する。
どちらの意味でも、パンデミックの悪影響を抑えるために政府が取るべき行動を発見する上で、我々の方法論が有効な手段であることを実証する。
論文 参考訳(メタデータ) (2020-05-15T17:17:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。