論文の概要: Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs
- arxiv url: http://arxiv.org/abs/2309.15395v5
- Date: Mon, 15 Apr 2024 03:20:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-16 23:47:12.253656
- Title: Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs
- Title（参考訳）: オンラインCMDPにおけるモデルフリー・レグレット最適政策同定
- Authors: Zihan Zhou, Honghao Wei, Lei Ying,
- Abstract要約: 本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
- 参考スコア（独自算出の注目度）: 17.62509045102346
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the best policy identification (BPI) problem in online Constrained Markov Decision Processes (CMDPs). We are interested in algorithms that are model-free, have low regret, and identify an approximately optimal policy with a high probability. Existing model-free algorithms for online CMDPs with sublinear regret and constraint violation do not provide any convergence guarantee to an optimal policy and provide only average performance guarantees when a policy is uniformly sampled at random from all previously used policies. In this paper, we develop a new algorithm, named Pruning-Refinement-Identification (PRI), based on a fundamental structural property of CMDPs proved before, which we call limited stochasticity. The property says for a CMDP with $N$ constraints, there exists an optimal policy with at most $N$ stochastic decisions. The proposed algorithm first identifies at which step and in which state a stochastic decision has to be taken and then fine-tunes the distributions of these stochastic decisions. PRI achieves trio objectives: (i) PRI is a model-free algorithm; and (ii) it outputs an approximately optimal policy with a high probability at the end of learning; and (iii) PRI guarantees $\tilde{\mathcal{O}}(H\sqrt{K})$ regret and constraint violation, which significantly improves the best existing regret bound $\tilde{\mathcal{O}}(H^4 \sqrt{SA}K^{\frac{4}{5}})$ under a model-free algorithm, where $H$ is the length of each episode, $S$ is the number of states, $A$ is the number of actions, and the total number of episodes during learning is $2K+\tilde{\cal O}(K^{0.25}).$ We further present a matching lower via an example that shows under any online learning algorithm, there exists a well-separated CMDP instance such that either the regret or violation has to be $\Omega(H\sqrt{K}),$ which matches the upper bound by a polylogarithmic factor.
- Abstract（参考訳）: 本稿では,CMDP(Constrained Markov Decision Processs)におけるBPI問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムは、最適ポリシーへの収束保証を提供しておらず、以前に使用したすべてのポリシーからランダムにポリシーがサンプリングされた場合にのみ平均的なパフォーマンス保証を提供する。
本稿では,以前に証明されたCMDPの基本構造特性に基づいて,Pruning-Refinement-Identification (PRI) と呼ばれる新しいアルゴリズムを開発した。
このプロパティは、$N$制約を持つCMDPに対して、少なくとも$N$確率的決定を持つ最適なポリシーが存在する、と言っている。
提案アルゴリズムはまず、どのステップで、どの状態で確率的決定を下さなければならないかを識別し、次にこれらの確率的決定の分布を微調整する。
PRIは以下の3つの目標を達成する。
(i)PRIはモデルフリーのアルゴリズムであり、
(二 学習の終わりに高い確率でほぼ最適な政策を出力すること。)
(iii) PRI は $\tilde{\mathcal{O}}(H\sqrt{K})$ regret and constraint violation を保証します。これは、モデルなしのアルゴリズムの下で、$H$ は各エピソードの長さ、$S$ は状態の数、$A$ はアクションの数、学習中のエピソードの総数は2K+\tilde{\mathcal O}(K^{0.25})です。
さらに、どんなオンライン学習アルゴリズムの下でも、後悔か違反かのどちらかが$\Omega(H\sqrt{K})でなければならないような、よく区切られたCMDPインスタンスが存在します。
関連論文リスト
- Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。
本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
論文 参考訳（メタデータ） (2024-06-26T17:57:13Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳（メタデータ） (2022-05-28T04:05:20Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Achieving Zero Constraint Violation for Constrained Reinforcement
Learning via Primal-Dual Approach [37.80609997145897]
強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。
決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。
CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。
ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
論文 参考訳（メタデータ） (2021-09-13T21:27:03Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳（メタデータ） (2021-02-22T18:56:26Z) - Model-Free Algorithm and Regret Analysis for MDPs with Long-Term
Constraints [38.2783003051101]
本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。
本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
論文 参考訳（メタデータ） (2020-06-10T17:19:29Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z) - Provably Efficient Exploration in Policy Optimization [117.09887790160406]
本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。
OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。
我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
論文 参考訳（メタデータ） (2019-12-12T08:40:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。