論文の概要: PAC Statistical Model Checking of Mean Payoff in Discrete- and
Continuous-Time MDP
- arxiv url: http://arxiv.org/abs/2206.01465v1
- Date: Fri, 3 Jun 2022 09:13:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-06 21:59:50.882170
- Title: PAC Statistical Model Checking of Mean Payoff in Discrete- and
Continuous-Time MDP
- Title(参考訳): 離散時間および連続時間mdpにおける平均ペイオフのpac統計モデル検証
- Authors: Chaitanya Agarwal, Shibashis Guha, Jan K\v{r}et\'insk\'y, M.
Pazhamalai
- Abstract要約: 我々は,未知のMDPにおいて,平均ペイオフをほぼ正確に計算する最初のアルゴリズムを提供する。
状態空間に関する知識は一切必要とせず、最小遷移確率の低い境界のみである。
提案アルゴリズムは, ほぼ正しいPAC境界を提供するだけでなく, 標準ベンチマークで実験を行うことにより, その実用性を実証する。
- 参考スコア(独自算出の注目度): 0.34410212782758043
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Markov decision processes (MDP) and continuous-time MDP (CTMDP) are the
fundamental models for non-deterministic systems with probabilistic
uncertainty. Mean payoff (a.k.a. long-run average reward) is one of the most
classic objectives considered in their context. We provide the first algorithm
to compute mean payoff probably approximately correctly in unknown MDP;
further, we extend it to unknown CTMDP. We do not require any knowledge of the
state space, only a lower bound on the minimum transition probability, which
has been advocated in literature. In addition to providing probably
approximately correct (PAC) bounds for our algorithm, we also demonstrate its
practical nature by running experiments on standard benchmarks.
- Abstract(参考訳): マルコフ決定過程 (MDP) と連続時間 MDP (CTMDP) は確率的不確実性を持つ非決定論的システムの基本モデルである。
平均ペイオフ(英: Mean payoff、英: long-run average reward)は、その文脈において最も古典的な目的の一つ。
我々は、未知のMDPにおいて平均ペイオフを計算する最初のアルゴリズムを提供し、さらに、未知のCTMDPに拡張する。
状態空間に関する知識は一切必要とせず、文献で提唱されている最小遷移確率の低い境界のみである。
提案アルゴリズムは, ほぼ正しいPAC境界を提供するだけでなく, 標準ベンチマークで実験を行うことにより, その実用性を実証する。
関連論文リスト
- Learning Algorithms for Verification of Markov Decision Processes [20.5951492453299]
マルコフ決定過程(MDP)の検証に学習アルゴリズムとガイダンスを適用するためのフレームワークを提案する。
提案するフレームワークは,検証における中核的な問題である確率的到達性に注目し,二つの異なるシナリオでインスタンス化される。
論文 参考訳(メタデータ) (2024-03-14T08:54:19Z) - On the Global Convergence of Policy Gradient in Average Reward Markov
Decision Processes [50.68789924454235]
我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。
我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
論文 参考訳(メタデータ) (2024-03-11T15:25:03Z) - Solving Long-run Average Reward Robust MDPs via Stochastic Games [4.833571004087541]
本稿では,長期平均ポリトピック RMDP を解くための新しいポリシーアルゴリズムである Robust Polytopic Policy Iteration (RPPI) を紹介する。
RPPIは、値反復に基づく最先端手法と比較して、長期平均報酬ポリトピー的RMDPerationの解法においてはるかに効率的である。
論文 参考訳(メタデータ) (2023-12-21T15:00:06Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳(メタデータ) (2023-10-03T04:40:38Z) - Twice Regularized Markov Decision Processes: The Equivalence between
Robustness and Regularization [64.60253456266872]
マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。
規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。
ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
論文 参考訳(メタデータ) (2023-03-12T13:03:28Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳(メタデータ) (2022-08-17T18:49:53Z) - A Fully Polynomial Time Approximation Scheme for Constrained MDPs and
Stochastic Shortest Path under Local Transitions [2.512827436728378]
我々は,(C)C-MDPの構造,特に局所遷移を伴う重要な変種について検討した。
本研究では,(C)C-MDPの最適決定性ポリシを(ほぼ)計算する完全時間近似手法を提案する。
論文 参考訳(メタデータ) (2022-04-10T22:08:33Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-01-21T16:43:03Z) - Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
我々は、Early TerminatedP(ET-MDP)の枠組みの下で、安全なRL問題に対処する新しいアプローチを導入する。
まず、ET-MDPを対応するCMDPと同じ最適値関数を持つ非制約アルゴリズムとして定義する。
そこで,文脈モデルに基づく非政治アルゴリズムを提案し,ET-MDPを解き,それに対応するCMDPをより良い性能で解き,学習効率を向上する。
論文 参考訳(メタデータ) (2021-07-09T04:24:40Z) - RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討
LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。
鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
論文 参考訳(メタデータ) (2021-02-09T16:49:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。