論文の概要: Natural Strategic Ability in Stochastic Multi-Agent Systems

• arxiv url: http://arxiv.org/abs/2401.12170v1
• Date: Mon, 22 Jan 2024 18:04:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-23 13:01:08.712305
• Title: Natural Strategic Ability in Stochastic Multi-Agent Systems
• Title（参考訳）: 確率的マルチエージェントシステムにおける自然戦略能力
• Authors: Rapha\"el Berthon, Joost-Pieter Katoen, Munyque Mittelmann, Aniello Murano
• Abstract要約: 本稿では,自然戦略下での確率論的時間論理PATLとPATL*について考察する。 我々は,MASにおいて,能動連立が決定論的戦略に制限されている場合,NatPATLモデルチェックはNP完全であることを示す。
• 参考スコア（独自算出の注目度）: 6.685412769221565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Strategies synthesized using formal methods can be complex and often require infinite memory, which does not correspond to the expected behavior when trying to model Multi-Agent Systems (MAS). To capture such behaviors, natural strategies are a recently proposed framework striking a balance between the ability of agents to strategize with memory and the model-checking complexity, but until now has been restricted to fully deterministic settings. For the first time, we consider the probabilistic temporal logics PATL and PATL* under natural strategies (NatPATL and NatPATL*, resp.). As main result we show that, in stochastic MAS, NatPATL model-checking is NP-complete when the active coalition is restricted to deterministic strategies. We also give a 2NEXPTIME complexity result for NatPATL* with the same restriction. In the unrestricted case, we give an EXPSPACE complexity for NatPATL and 3EXPSPACE complexity for NatPATL*.
• Abstract（参考訳）: 形式的手法を用いて合成された戦略は複雑であり、しばしば無限のメモリを必要とするが、マルチエージェントシステム(MAS)をモデル化しようとする場合の期待した振る舞いに対応しない。 このような振る舞いを捉えるために、Natural Strategyは近年提案されたフレームワークであり、エージェントがメモリで戦略を立てる能力とモデルチェックの複雑さのバランスを保っている。 まず,自然戦略(NatPATL,NatPATL*,resp.)の下で,確率論的時間論理PATLとPATL*を考える。 その結果, 確率MASでは, 能動連立が決定論的戦略に制限された場合, NatPATLモデルチェックはNP完全であることがわかった。 また、同じ制約でNatPATL*に対して2NEXPTIMEの複雑性結果を与える。 非制限の場合、NatPATLにはEXPSPACE複雑性、NatPATLには3EXPSPACE複雑性を与える。

関連論文リスト

• REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
  生成モデルの時代における最小限のRLアルゴリズムであるREBELを提案する。 理論的には、自然ポリシーグラディエントのような基本的なRLアルゴリズムはREBELの変種と見なすことができる。 我々はREBELが言語モデリングと画像生成に一貫したアプローチを提供し、PPOやDPOとより強くあるいは類似した性能を実現することを発見した。
  論文  参考訳（メタデータ） (2024-04-25T17:20:45Z)
• Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
  モデルに基づく関数近似を用いた平均フィールドゲーム(MFG)における強化学習のサンプル複雑性について検討した。 本稿では、モデルクラスの複雑性を特徴付けるためのより効果的な概念である部分モデルベースエルダー次元(P-MBED)を紹介する。
  論文  参考訳（メタデータ） (2024-02-08T14:54:47Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• The Alternating-Time \mu-Calculus With Disjunctive Explicit Strategies [1.7725414095035827]
  同時ゲーム構造におけるエージェントの連立の戦略能力について検討する。 論理の重要な要素は、あるエージェントの連立が与えられた目標を強制するための共同戦略を持つことを示す経路定量化器である。 我々は, ATLES を固定点演算子と戦略解離で拡張し, 明示的な戦略で時相の $mu$-calculus に到達する。
  論文  参考訳（メタデータ） (2023-05-30T07:16:59Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。 我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。 我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-12T17:57:17Z)
• Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
  我々は構造化出力予測(SOP)のための予測層を設計する。 予測が事前に定義されたシンボリック制約のセットと一致していることを保証するため、任意のニューラルネットワークにプラグインすることができる。 我々のセマンティック確率層(SPL)は、構造化された出力空間上で複雑な相関や制約をモデル化することができる。
  論文  参考訳（メタデータ） (2022-06-01T12:02:38Z)
• Computing Complexity-aware Plans Using Kolmogorov Complexity [0.9137554315375922]
  有限水平決定性有限オートマトンを出力として計算する複雑性を考慮した計画法を提案する。 本稿では,2つのアルゴリズムで低複素性ポリシーを求め,第1のアルゴリズムで低複素性最適ポリシーを求める。 移動ロボットの単純なナビゲーションタスクにおけるアルゴリズムの評価を行い,そのアルゴリズムは直感と一致する低複雑さのポリシーを導出する。
  論文  参考訳（メタデータ） (2021-09-21T16:25:04Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization [21.879621917722613]
  政策空間の一般化を伴う大規模強化学習(RL)問題における最適なサンプル複雑性について検討する。 既存の結果は、一般化モデルがなければ、RLアルゴリズムのサンプルの複雑さは必然的に状態空間と行動空間の濃度に依存することを示している。 本稿では,政策学習の本質的な複雑さを特徴付ける,政策空間におけるユーラダー次元の新たな概念を提案する。
  論文  参考訳（メタデータ） (2020-08-17T14:26:18Z)
• Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs [13.922754427601491]
  我々は,安全性の制約と,所望の精度を確保するために必要なサンプル数との関係を特徴付ける。 我々の主な発見は、制約のない状態の最もよく知られた境界と比較して、制約されたRLアルゴリズムのサンプルは制約の数に対数的な因子によって増加することである。
  論文  参考訳（メタデータ） (2020-08-01T18:17:08Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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