論文の概要: Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints

• arxiv url: http://arxiv.org/abs/2006.05961v2
• Date: Sat, 30 Jan 2021 21:06:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 05:34:01.989185
• Title: Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints
• Title（参考訳）: 長期制約付きMDPのモデルフリーアルゴリズムとレグレト解析
• Authors: Qinbo Bai and Vaneet Aggarwal and Ather Gattami
• Abstract要約: 本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。 本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
• 参考スコア（独自算出の注目度）: 38.2783003051101
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the optimization of dynamical systems, the variables typically have constraints. Such problems can be modeled as a constrained Markov Decision Process (CMDP). This paper considers a model-free approach to the problem, where the transition probabilities are not known. In the presence of long-term (or average) constraints, the agent has to choose a policy that maximizes the long-term average reward as well as satisfy the average constraints in each episode. The key challenge with the long-term constraints is that the optimal policy is not deterministic in general, and thus standard Q-learning approaches cannot be directly used. This paper uses concepts from constrained optimization and Q-learning to propose an algorithm for CMDP with long-term constraints. For any $\gamma\in(0,\frac{1}{2})$, the proposed algorithm is shown to achieve $O(T^{1/2+\gamma})$ regret bound for the obtained reward and $O(T^{1-\gamma/2})$ regret bound for the constraint violation, where $T$ is the total number of steps. We note that these are the first results on regret analysis for MDP with long-term constraints, where the transition probabilities are not known apriori.
• Abstract（参考訳）: 力学系の最適化において、変数は通常制約を持つ。 このような問題は、マルコフ決定過程(CMDP)としてモデル化することができる。 本稿では,遷移確率が不明な問題に対するモデルフリーアプローチについて考察する。 長期的な(または平均的な)制約が存在する場合、エージェントは、各エピソードの平均的な制約を満たすだけでなく、長期的な平均報酬を最大化するポリシーを選択する必要がある。 長期的制約の鍵となる課題は、最適ポリシーが一般に決定論的ではないため、標準的なQ-ラーニングアプローチを直接使用できないことである。 本稿では,制約付き最適化とQ学習の概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。 任意の$\gamma\in(0,\frac{1}{2})$に対して、提案されたアルゴリズムは、得られる報酬に対して$o(t^{1/2+\gamma})$ regret bound、制約違反に対して$o(t^{1-\gamma/2})$ regret boundを達成する。 本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。

関連論文リスト

• Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
  SDMU (Sequential Decision Making Under Uncertainty) は、エネルギー、金融、サプライチェーンといった多くの領域において、ユビキタスである。 いくつかのSDMUは、自然にマルチステージ問題(MSP)としてモデル化されているが、結果として得られる最適化は、計算の観点からは明らかに困難である。 本稿では,2段階の一般決定規則(TS-GDR)を導入し,線形関数を超えて政策空間を一般化する手法を提案する。 TS-GDRの有効性は、TS-LDR(Two-Stage Deep Decision Rules)と呼ばれるディープリカレントニューラルネットワークを用いたインスタンス化によって実証される。
  論文  参考訳（メタデータ） (2024-05-23T18:19:47Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• Anytime-Constrained Reinforcement Learning [6.981971551979697]
  制約付きマルコフ決定過程(cMDP)を任意の制約で導入・研究する。 累積コストを付加した最適決定主義的政策が存在することを示す。 非自明な概略的ポリシーの計算は一般にNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-09T16:51:26Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• 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)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。