論文の概要: 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境界を提供するだけでなく, 標準ベンチマークで実験を行うことにより, その実用性を実証する。
関連論文リスト
- Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。
このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
論文 参考訳（メタデータ） (2024-06-12T06:41:47Z) - What Are the Odds? Improving the foundations of Statistical Model Checking [3.789219860006095]
マルコフ決定プロセス(MDP)は不確実性の下での意思決定の基本的なモデルである。
従来の検証アルゴリズムは、MDPの振る舞いを管理する確率の正確な知識を前提としている。
我々はMDPの知識を活用する専門的なアプローチを提案する。
論文 参考訳（メタデータ） (2024-04-08T11:47:46Z) - 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) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳（メタデータ） (2023-10-03T04:40:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。