論文の概要: Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs
- arxiv url: http://arxiv.org/abs/2309.15395v1
- Date: Wed, 27 Sep 2023 04:33:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 16:46:33.283196
- Title: Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs
- Title（参考訳）: オンラインcmdpにおけるモデルフリー, 後悔-最適政策識別
- Authors: Zihan Zhou, Honghao Wei, Lei Ying
- Abstract要約: 本稿では,オンライン制約決定プロセス(CMDP)における最良ポリシー識別問題について考察する。
我々は、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、高い確率で最適なポリシーを特定する。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
- 参考スコア（独自算出の注目度）: 19.808835370794956
- 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 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 we discover, called 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 a near-optimal policy with a high
probability at the end of learning; and (iii) in the tabular setting, PRI
guarantees $\tilde{\mathcal{O}}(\sqrt{K})$ regret and constraint violation,
which significantly improves the best existing regret bound
$\tilde{\mathcal{O}}(K^{\frac{4}{5}})$ under a mode-free algorithm, where $K$
is the total number of episodes.
- Abstract（参考訳）: 本稿では,制約付きマルコフ決定プロセス(CMDP)におけるBPI問題について考察する。
我々は、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、高い確率で最適なポリシーを特定する。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムは、最適ポリシーへの収束保証を提供しておらず、以前に使用したすべてのポリシーからランダムにポリシーがサンプリングされた場合にのみ平均的なパフォーマンス保証を提供する。
本稿では,我々が発見するcmdpsの基本構造的性質に基づいて,pruning-refinement-identification(pri)という新しいアルゴリズムを開発した。
このプロパティは、n$制約のあるcmdpに対して、最大$n$確率的決定を持つ最適なポリシーが存在すると言っている。
提案するアルゴリズムは,まず確率的決定を行うべき段階と状態を特定し,その確率的決定の分布を微調整する。
PRIは3つの目標を達成する。
(i)PRIはモデルフリーのアルゴリズムであり、
(ii)学習の最後に高い確率で、最適に近い政策を出力する。
(iii) 表設定では、pri は$\tilde{\mathcal{o}}(\sqrt{k})$ regret and constraints violation を保証し、$k$ はエピソードの総数であるモードフリーのアルゴリズムの下で、$\tilde{\mathcal{o}}(k^{\frac{4}{5}})$ を最良に向上させる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。