論文の概要: 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}))$で上限となる。
理論的知見を説明するための数値実験を行った。
以上の結果から,不整合性と軽度リスクの不整合性に関する知見が得られたが,軽度リスクと軽度リスクに対する最悪の最適性は相容れないことが示唆された。
関連論文リスト
- Distributionally Robust Policy Learning under Concept Drifts [33.44768994272614]
本稿では、より曖昧な問題、つまり、コンセプトドリフトの下でのロバストな政策学習について研究する。
まず、与えられた政策の最悪の平均報酬を評価するための2倍のロバスト推定器を提供する。
次に、所定のポリシークラス内で推定されたポリシー値を最大化するポリシーを出力する学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-18T19:53:56Z) - Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
論文 参考訳（メタデータ） (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) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds
Globally Optimal Policy [95.98698822755227]
本研究は,リスクに敏感な深層強化学習を,分散リスク基準による平均報酬条件下で研究する試みである。
本稿では,ポリシー,ラグランジュ乗算器,フェンシェル双対変数を反復的かつ効率的に更新するアクタ批判アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-28T05:02:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。