論文の概要: LTL-Constrained Steady-State Policy Synthesis
- arxiv url: http://arxiv.org/abs/2105.14894v1
- Date: Mon, 31 May 2021 11:35:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-01 17:00:46.991194
- Title: LTL-Constrained Steady-State Policy Synthesis
- Title（参考訳）: LTL制約定常政策合成
- Authors: Jan K\v{r}et\'insk\'y
- Abstract要約: マルコフ決定プロセス(MDP)とこれらすべての型を組み合わせた仕様について検討する。
マルチタイプの仕様を多次元の長期平均報酬に還元する統合ソリューションを提供する。
このアルゴリズムは一般の$omega$-regularプロパティにも拡張され、LDBAと同様にMDPのサイズで実行されます。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Decision-making policies for agents are often synthesized with the constraint
that a formal specification of behaviour is satisfied. Here we focus on
infinite-horizon properties. On the one hand, Linear Temporal Logic (LTL) is a
popular example of a formalism for qualitative specifications. On the other
hand, Steady-State Policy Synthesis (SSPS) has recently received considerable
attention as it provides a more quantitative and more behavioural perspective
on specifications, in terms of the frequency with which states are visited.
Finally, rewards provide a classic framework for quantitative properties. In
this paper, we study Markov decision processes (MDP) with the specification
combining all these three types. The derived policy maximizes the reward among
all policies ensuring the LTL specification with the given probability and
adhering to the steady-state constraints. To this end, we provide a unified
solution reducing the multi-type specification to a multi-dimensional long-run
average reward. This is enabled by Limit-Deterministic B\"uchi Automata (LDBA),
recently studied in the context of LTL model checking on MDP, and allows for an
elegant solution through a simple linear programme. The algorithm also extends
to the general $\omega$-regular properties and runs in time polynomial in the
sizes of the MDP as well as the LDBA.
- Abstract（参考訳）: エージェントの意思決定ポリシーは、行動の正式な仕様が満たされるという制約でしばしば合成される。
ここでは無限ホリゾン特性に着目する。
一方、LTL(Linear Temporal Logic)は定性的な仕様に対する形式主義の一般的な例である。
一方で、定常政策合成(ssps)は、訪問する状態の頻度の観点で、より定量的でより行動的な仕様の視点を提供するため、近年多くの注目を集めている。
最後に、報酬は量的性質の古典的な枠組みを提供する。
本稿では,マルコフ決定過程(MDP)とこれら3つのタイプを組み合わせた仕様について検討する。
導出政策は、LTL仕様を与えられた確率で保証し、定常的な制約に固執する全ての政策の報酬を最大化する。
この目的のために,マルチタイプの仕様を多次元の長期平均報酬に還元する統一解を提供する。
LDBA(Limit-Deterministic B\"uchi Automata)が最近,MDP上のLTLモデルチェックの文脈で研究し,シンプルな線形プログラムによるエレガントな解を可能にする。
このアルゴリズムは一般的な$\omega$-regularプロパティにも拡張され、LDBAと同様にMDPのサイズの時間多項式で動作する。
関連論文リスト
- DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications [59.01527054553122]
リニア時間論理(LTL)は、強化学習(RL)における複雑で時間的に拡張されたタスクを特定する強力なフォーマリズムとして最近採用されている。
既存のアプローチはいくつかの欠点に悩まされており、それらは有限水平フラグメントにのみ適用でき、最適以下の解に制限され、安全制約を適切に扱えない。
本研究では,これらの問題に対処するための新しい学習手法を提案する。
提案手法は, 自動仕様のセマンティクスを明示的に表現したB"uchiaの構造を利用して, 所望の式を満たすための真理代入の順序を条件としたポリシーを学習する。
論文 参考訳（メタデータ） (2024-10-06T21:30:38Z) - Directed Exploration in Reinforcement Learning from Linear Temporal Logic [59.707408697394534]
リニア時間論理(LTL)は強化学習におけるタスク仕様のための強力な言語である。
合成された報酬信号は基本的に疎結合であり,探索が困難であることを示す。
我々は、仕様をさらに活用し、それに対応するリミット決定性B"uchi Automaton(LDBA)をマルコフ報酬プロセスとしてキャストすることで、よりよい探索を実現することができることを示す。
論文 参考訳（メタデータ） (2024-08-18T14:25:44Z) - Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-01-21T16:43:03Z) - Solving Multistage Stochastic Linear Programming via Regularized Linear
Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
AdaSO(Adaptive least absolute shrinkage and selection operator)に基づく線形決定規則(LDR)の新しい正規化手法を提案する。
実験により、MSLPを解くために古典的な非正規化LDRを使用する場合、過度に適合する脅威は無視できないことが示された。
LHDP問題に対しては、非正規化ベンチマークと比較して、提案したフレームワークの次の利点を強調した。
論文 参考訳（メタデータ） (2021-10-07T02:36:14Z) - Modular Deep Reinforcement Learning for Continuous Motion Planning with
Temporal Logic [59.94347858883343]
本稿では,マルコフ決定過程(MDP)をモデルとした自律動的システムの運動計画について検討する。
LDGBA と MDP の間に組込み製品 MDP (EP-MDP) を設計することである。
モデルフリー強化学習(RL)のためのLDGBAベースの報酬形成と割引スキームは、EP-MDP状態にのみ依存する。
論文 参考訳（メタデータ） (2021-02-24T01:11:25Z) - Verifiable Planning in Expected Reward Multichain MDPs [20.456052208569115]
エージェントの意思決定方針を導出する定常計画問題について検討する。
提案プログラムに対する最適解が、厳密な行動保証を伴う定常的な政策をもたらすことを証明した。
論文 参考訳（メタデータ） (2020-12-03T18:54:24Z) - LTLf Synthesis on Probabilistic Systems [0.0]
合成は、この行動を達成する確率を最大化するポリシーを見つけるために用いられる。
有限トレース特性を与えられた振る舞いに対するポリシー合成を解くための道具は存在しない。
本稿では,マルコフプロセスの削減による2つの問題を解決するアルゴリズムと,オートマトンフのための2番目のネイティブツールを提案する。
論文 参考訳（メタデータ） (2020-09-23T01:26:47Z) - Strengthening Deterministic Policies for POMDPs [5.092711491848192]
我々は、時間論理制約の形で洗練された仕様をサポートする新しいMILP符号化を提供する。
我々は、メモリベースの決定を包含するために、POMDPの事前処理を採用する。
提案手法の利点は, 計算的トラクタビリティを損なうことなく, 簡単な決定論的政策を強化する柔軟性と, 任意に多くの仕様の証明可能な満足度を強制する能力である。
論文 参考訳（メタデータ） (2020-07-16T14:22:55Z) - Certified Reinforcement Learning with Logic Guidance [78.2286146954051]
線形時間論理(LTL)を用いて未知の連続状態/動作マルコフ決定過程(MDP)のゴールを定式化できるモデルフリーなRLアルゴリズムを提案する。
このアルゴリズムは、トレースが仕様を最大確率で満たす制御ポリシーを合成することが保証される。
論文 参考訳（メタデータ） (2019-02-02T20:09:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。