論文の概要: A Simple and Optimal Policy Design for Online Learning with Safety
against Heavy-tailed Risk
- arxiv url: http://arxiv.org/abs/2206.02969v1
- Date: Tue, 7 Jun 2022 02:10:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-08 14:28:13.801990
- Title: A Simple and Optimal Policy Design for Online Learning with Safety
against Heavy-tailed Risk
- Title(参考訳): 重度リスクに対する安全を考慮したオンライン学習のためのシンプルで最適なポリシー設計
- Authors: David Simchi-Levi, Zeyu Zheng, Feng Zhu
- Abstract要約: 我々は,古典的多武装バンディット問題における重大リスクに対する安全性を確保する政策を設計する。
この重いリスクは、すべての「インスタンス依存の一貫性」ポリシーに存在します。
予想される後悔と軽微なリスクに対する最悪のケースの最適性は相容れないことを示す。
- 参考スコア(独自算出の注目度): 22.843623578307707
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We design simple and optimal policies that ensure safety against heavy-tailed
risk in the classical multi-armed bandit problem. We start by showing that some
widely used policies such as the standard Upper Confidence Bound policy and the
Thompson Sampling policy incur heavy-tailed risk; that is, the worst-case
probability of incurring a linear regret slowly decays at a polynomial rate of
$1/T$, where $T$ is the time horizon. We further show that this heavy-tailed
risk exists for all "instance-dependent consistent" policies. To ensure safety
against such heavy-tailed risk, for the two-armed bandit setting, we provide a
simple policy design that (i) has the worst-case optimality for the expected
regret at order $\tilde O(\sqrt{T})$ and (ii) has the worst-case tail
probability of incurring a linear regret decay at an exponential rate
$\exp(-\Omega(\sqrt{T}))$. We further prove that this exponential decaying rate
of the tail probability is optimal across all policies that have worst-case
optimality for the expected regret. Finally, we improve the policy design and
analysis to the general $K$-armed bandit setting. We provide detailed
characterization of the tail probability bound for any regret threshold under
our policy design. Namely, the worst-case probability of incurring a regret
larger than $x$ is upper bounded by $\exp(-\Omega(x/\sqrt{KT}))$. Numerical
experiments are conducted to illustrate the theoretical findings. Our results
reveal insights on the incompatibility between consistency and light-tailed
risk, whereas indicate that worst-case optimality on expected regret and
light-tailed risk are compatible.
- Abstract(参考訳): 我々は、古典的多武装バンディット問題における重大リスクに対する安全性を確保するためのシンプルで最適なポリシーを設計する。
まず、標準のアッパー信頼境界政策やトンプソンサンプリング政策のような広く使われている政策が重大リスクをもたらすことを示し、すなわち、線形後悔を引き起こす最悪の確率は、多項式レート1/T$で徐々に低下し、そこでは、$T$が時間的水平線であることを示す。
さらに,この重み付きリスクが,すべての"instance-dependent consistent"政策に対して存在することを示す。
このような重大リスクに対する安全性を確保するため、両腕バンディット設定では、簡単なポリシー設計を提供する。
(i)$\tilde o(\sqrt{t})$ で期待される後悔に対して最悪の場合の最適性を持つ
(ii) は指数率$\exp(-\Omega(\sqrt{T}))$で線形後悔の崩壊を起こす最悪の場合の尾の確率を持つ。
さらに, テイル確率の指数的減衰速度は, 期待される後悔に対して最悪の最適性を持つすべての方針において最適であることが証明される。
最後に、ポリシー設計と分析を一般的な$k$のバンディット設定に改善します。
当社のポリシー設計では,後悔しきい値に対するテール確率の詳細な特徴付けを行う。
つまり、$x$より大きい後悔を引き起こす最悪の確率は、$\exp(-\Omega(x/\sqrt{KT}))$で上限となる。
理論的知見を説明するための数値実験を行った。
以上の結果から,不整合性と軽度リスクの不整合性に関する知見が得られたが,軽度リスクと軽度リスクに対する最悪の最適性は相容れないことが示唆された。
関連論文リスト
- Model-Based Epistemic Variance of Values for Risk-Aware Policy
Optimization [63.32053223422317]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
特に、MDP上の分布によって誘導される値の分散を特徴付けることに焦点をあてる。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
論文 参考訳(メタデータ) (2023-12-07T15:55:58Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳(メタデータ) (2023-10-01T01:37:02Z) - Regret Distribution in Stochastic Bandits: Optimal Trade-off between
Expectation and Tail Risk [22.843623578307707]
我々は,多武装バンディット問題における後悔分布の予測とテールリスクのトレードオフについて検討した。
予測された後悔の順序が、最悪のケースとインスタンスに依存したシナリオの両方において、後悔の尾確率の減衰率にどのように影響するかを示す。
論文 参考訳(メタデータ) (2023-04-10T01:00:18Z) - Best of Both Worlds Policy Optimization [33.13041034490332]
本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。
政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
論文 参考訳(メタデータ) (2023-02-18T19:46:11Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳(メタデータ) (2023-01-31T03:49:00Z) - A Doubly Optimistic Strategy for Safe Linear Bandits [45.87122314291089]
DOSLBは、報酬と安全スコアの楽観的な推定を用いて、最高の楽観性を行使し、行動を選択する。
DOSLBが危険な行動を取ることは滅多になく、不効率と行動の安全性の欠如の両方を後悔の念として、$tildeO(d sqrtT)$ regretを得る。
論文 参考訳(メタデータ) (2022-09-27T21:13:32Z) - Stability and Deviation Optimal Risk Bounds with Convergence Rate
$O(1/n)$ [4.1499725848998965]
経験的リスク最小化法で有効な強く凸およびLipschitz損失に対する$O(log n/n)$の確率に拘束される高い確率過剰リスクを示す。
O(log n/n)$ 高確率過剰リスク境界が、通常の滑らかさの仮定なしで強い凸やリプシッツ損失の場合の射影勾配降下に対してどのように可能かについて論じる。
論文 参考訳(メタデータ) (2021-03-22T17:28:40Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳(メタデータ) (2020-06-29T21:06:52Z) - Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff
in Regret [115.85354306623368]
本研究では,未知の遷移カーネルを持つマルコフ決定過程におけるリスク感応性強化学習について検討する。
確率的に効率的なモデルレスアルゴリズムとして、リスク感性価値反復(RSVI)とリスク感性Q-ラーニング(RSQ)を提案する。
RSVIが $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big) に達したことを証明しています。
論文 参考訳(メタデータ) (2020-06-22T19:28:26Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。