論文の概要: Reinforcement Learning for General LTL Objectives Is Intractable

• arxiv url: http://arxiv.org/abs/2111.12679v1
• Date: Wed, 24 Nov 2021 18:26:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-25 14:41:07.954170
• Title: Reinforcement Learning for General LTL Objectives Is Intractable
• Title（参考訳）: 一般ltl目標のための強化学習は難解である
• Authors: Cambridge Yang, Michael Littman, Michael Carbin
• Abstract要約: 我々は、マルコフ決定プロセス(PACMDP)フレームワークにおいて、おそらく正しい学習の下で問題を定式化する。 この結果から, 強化学習アルゴリズムでは, 学習ポリシーの性能に対するPAC-MDP保証を得ることは不可能であることが示唆された。
• 参考スコア（独自算出の注目度）: 10.69663517250214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, researchers have made significant progress in devising reinforcement-learning algorithms for optimizing linear temporal logic (LTL) objectives and LTL-like objectives. Despite these advancements, there are fundamental limitations to how well this problem can be solved that previous studies have alluded to but, to our knowledge, have not examined in depth. In this paper, we address theoretically the hardness of learning with general LTL objectives. We formalize the problem under the probably approximately correct learning in Markov decision processes (PAC-MDP) framework, a standard framework for measuring sample complexity in reinforcement learning. In this formalization, we prove that the optimal policy for any LTL formula is PAC-MDP-learnable only if the formula is in the most limited class in the LTL hierarchy, consisting of only finite-horizon-decidable properties. Practically, our result implies that it is impossible for a reinforcement-learning algorithm to obtain a PAC-MDP guarantee on the performance of its learned policy after finitely many interactions with an unconstrained environment for non-finite-horizon-decidable LTL objectives.
• Abstract（参考訳）: 近年、線形時間論理(LTL)の目的とLTLのような目的を最適化するための強化学習アルゴリズムの開発に大きな進歩を遂げている。 これらの進歩にもかかわらず、この問題がどの程度うまく解決できるかには根本的な制限があるが、我々の知識では、深く調べられていない。 本稿では,一般LTL目標を用いた学習の難しさを理論的に論じる。 我々は,マルコフ決定過程 (PAC-MDP) フレームワークにおけるほぼ正しい学習条件の下で問題を定式化し,強化学習におけるサンプルの複雑さを測定するための標準フレームワークである。 この形式化において、任意の LTL 公式の最適ポリシーが PAC-MDP-learnable であることは、式が LTL 階層において最も限られたクラスであり、有限水平決定性のみからなる場合に限る。 本研究の結果は, 有限個の制約のないLTL目標に対して, 有限個の制約のない環境と相互作用した上で, PAC-MDPの保証が得られないことを示唆している。

関連論文リスト

• Rethinking Multi-Objective Learning through Goal-Conditioned Supervised Learning [8.593384839118658]
  多目的学習は、1つのモデルで複数の目的を同時に最適化することを目的としている。 正確な学習プロセスを形式化し実行することの難しさに悩まされる。 本稿では,既存のシーケンシャルデータに基づいて,複数の目的を自動学習する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-12-12T03:47:40Z)
• 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)
• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  強化学習(Reinforcement Learning, RL)は、将来の行動方針をフィードバックで改善することにより、シーケンシャルな意思決定問題の事実上の標準的実践となった。 大規模言語モデル(LLM)の最近の発展は、言語理解と生成において印象的な能力を示したが、探索と自己改善能力に欠けていた。 我々はLINVITというアルゴリズムを開発し、LLMガイダンスを値ベースRLの正規化因子として組み込んで学習に必要なデータ量を大幅に削減する。
  論文  参考訳（メタデータ） (2024-02-25T20:07:13Z)
• A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs [5.946838062187346]
  意思決定プロセス(MDP)におけるオメガ規則目的のためのモデルベース近似ほぼ正(PAC)学習アルゴリズムを提案する。 我々のアルゴリズムは、我々の理論を裏付ける実験を行うために、多くのサンプルしか必要としていないことを証明している。
  論文  参考訳（メタデータ） (2023-10-18T18:33:41Z)
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable [12.700911432945151]
  強化学習では、割引と有限水平累積報酬を最大化する古典的な目的はPAC学習可能である。 近年、研究者は古典的な累積報酬を超える目的とそれに対応する強化学習アルゴリズムを導入している。 本研究は, 汎用強化学習目標のPAC学習性を示す。
  論文  参考訳（メタデータ） (2023-03-09T16:05:10Z)
• Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice [54.03076395748459]
  メタラーニング文学の中心的な疑問は、目に見えないタスクへの一般化を保証するために、いかに正規化するかである。 本稿では,Rothfussらによって最初に導かれたメタラーニングの一般化について述べる。 PAC-Bayesian per-task 学習境界におけるメタラーニングの条件と程度について,理論的解析および実証事例研究を行った。
  論文  参考訳（メタデータ） (2022-11-14T08:51:04Z)
• PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees [77.67258935234403]
  PAC-Bayesianフレームワークを用いた理論的解析を行い、メタ学習のための新しい一般化境界を導出する。 我々は、性能保証と原則付きメタレベル正規化を備えたPAC最適メタ学習アルゴリズムのクラスを開発する。
  論文  参考訳（メタデータ） (2020-02-13T15:01:38Z)
• Certified Reinforcement Learning with Logic Guidance [78.2286146954051]
  線形時間論理(LTL)を用いて未知の連続状態/動作マルコフ決定過程(MDP)のゴールを定式化できるモデルフリーなRLアルゴリズムを提案する。 このアルゴリズムは、トレースが仕様を最大確率で満たす制御ポリシーを合成することが保証される。
  論文  参考訳（メタデータ） (2019-02-02T20:09:32Z)

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

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