論文の概要: Markov Decision Processes with Long-Term Average Constraints

• arxiv url: http://arxiv.org/abs/2106.06680v1
• Date: Sat, 12 Jun 2021 03:44:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-19 23:49:33.810340
• Title: Markov Decision Processes with Long-Term Average Constraints
• Title（参考訳）: 長期的平均制約を伴うマルコフ決定過程
• Authors: Mridul Agarwal, Qinbo Bai, and Vaneet Aggarwal
• Abstract要約: エージェントが一鎖マルコフ決定プロセスと相互作用する制約付きマルコフ決定プロセス(CMDP)の問題を考察する。 エージェントがCMDPと対話するための最適なポリシーを学習できる後方サンプリングに基づくアルゴリズムであるCMDP-PSRLを提案する。
• 参考スコア（独自算出の注目度）: 30.939150842529052
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of constrained Markov Decision Process (CMDP) where an agent interacts with a unichain Markov Decision Process. At every interaction, the agent obtains a reward. Further, there are $K$ cost functions. The agent aims to maximize the long-term average reward while simultaneously keeping the $K$ long-term average costs lower than a certain threshold. In this paper, we propose CMDP-PSRL, a posterior sampling based algorithm using which the agent can learn optimal policies to interact with the CMDP. Further, for MDP with $S$ states, $A$ actions, and diameter $D$, we prove that following CMDP-PSRL algorithm, the agent can bound the regret of not accumulating rewards from optimal policy by $\Tilde{O}(poly(DSA)\sqrt{T})$. Further, we show that the violations for any of the $K$ constraints is also bounded by $\Tilde{O}(poly(DSA)\sqrt{T})$. To the best of our knowledge, this is the first work which obtains a $\Tilde{O}(\sqrt{T})$ regret bounds for ergodic MDPs with long-term average constraints.
• Abstract（参考訳）: エージェントが一鎖マルコフ決定プロセスと相互作用する制約付きマルコフ決定プロセス(CMDP)の問題を考察する。 全ての相互作用において、エージェントは報酬を得る。 さらに、$K$コスト関数がある。 このエージェントは、長期平均報酬を最大化しつつ、k$の長期平均コストを一定のしきい値よりも低く抑えることを目指している。 本稿では、エージェントがCMDPと対話する最適なポリシーを学習できる後方サンプリングに基づくアルゴリズムであるCMDP-PSRLを提案する。 さらに、$S$状態、$A$アクション、および直径$D$を持つMDPの場合、CMDP-PSRLアルゴリズムに従うと、エージェントは$\Tilde{O}(poly(DSA)\sqrt{T})$で最適ポリシーからの報酬を蓄積しないことを後悔する。 さらに、$K$の制約の違反も$\Tilde{O}(poly(DSA)\sqrt{T})$で制限されていることを示す。 我々の知る限りでは、これは長期平均制約を持つエルゴード MDP に対する $\Tilde{O}(\sqrt{T})$ regret bounds を得る最初の作品である。

関連論文リスト

• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。 この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
  論文  参考訳（メタデータ） (2022-03-24T08:14:12Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)
• 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)

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

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