論文の概要: Rational Verification for Probabilistic Systems
- arxiv url: http://arxiv.org/abs/2107.09119v1
- Date: Mon, 19 Jul 2021 19:24:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-21 14:50:40.438745
- Title: Rational Verification for Probabilistic Systems
- Title(参考訳): 確率システムの合理的検証
- Authors: Julian Gutierrez, Lewis Hammond, Anthony Lin, Muhammad Najib, Michael
Wooldridge
- Abstract要約: 我々は確率的システムにおける合理的な検証の理論とアルゴリズムを開発する。
複雑なマルチエージェント環境における不確実性とランダム性をモデル化するための並列ゲーム(CSG)に焦点を当てる。
- 参考スコア(独自算出の注目度): 2.4254101826561847
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Rational verification is the problem of determining which temporal logic
properties will hold in a multi-agent system, under the assumption that agents
in the system act rationally, by choosing strategies that collectively form a
game-theoretic equilibrium. Previous work in this area has largely focussed on
deterministic systems. In this paper, we develop the theory and algorithms for
rational verification in probabilistic systems. We focus on concurrent
stochastic games (CSGs), which can be used to model uncertainty and randomness
in complex multi-agent environments. We study the rational verification problem
for both non-cooperative games and cooperative games in the qualitative
probabilistic setting. In the former case, we consider LTL properties satisfied
by the Nash equilibria of the game and in the latter case LTL properties
satisfied by the core. In both cases, we show that the problem is
2EXPTIME-complete, thus not harder than the much simpler verification problem
of model checking LTL properties of systems modelled as Markov decision
processes (MDPs).
- Abstract(参考訳): 合理的検証は、システム内のエージェントが合理的に振る舞うという仮定の下で、ゲーム理論的均衡を形成する戦略を選択することによって、複数のエージェントシステムにおいてどの時相論理特性が保持されるかを決定する問題である。
この分野の以前の研究は、決定論的システムに重点を置いてきた。
本稿では,確率システムにおける合理的検証の理論とアルゴリズムについて述べる。
複雑なマルチエージェント環境における不確実性とランダム性をモデル化するために,並列確率ゲーム(CSG)に注目した。
質的確率的設定における非協力ゲームと協調ゲームの両方の合理的検証問題について検討する。
前者の場合、ゲームのナッシュ平衡で満たされたLTL特性と後者の場合、コアで満たされたLTL特性を考える。
いずれの場合においても,問題は2exptime-completeであり,マルコフ決定プロセス(mdps)としてモデル化されたシステムのltl特性の検証よりも容易である。
関連論文リスト
- On Imperfect Recall in Multi-Agent Influence Diagrams [57.21088266396761]
マルチエージェント・インフルエンス・ダイアグラム(MAID)はベイズネットワークに基づくゲーム理論モデルとして人気がある。
混合ポリシと2種類の相関平衡を用いて, 忘れ易いエージェントと不注意なエージェントでMAIDを解く方法を示す。
また,不完全なリコールがしばしば避けられないマルコフゲームやチーム状況へのMAIDの適用についても述べる。
論文 参考訳(メタデータ) (2023-07-11T07:08:34Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳(メタデータ) (2023-05-01T06:46:22Z) - On the Complexity of Rational Verification [5.230352342979224]
合理的検証とは、同時マルチエージェントシステムの時間論理特性が保持する問題を指す。
合理的な検証の複雑さは仕様によって大幅に低減できることを示す。
平均支払ユーティリティ関数によって与えられるプレイヤーの目標を考慮した場合、合理的な検証のための改善された結果を提供する。
論文 参考訳(メタデータ) (2022-07-06T12:56:22Z) - Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。
汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。
我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
論文 参考訳(メタデータ) (2021-12-15T03:33:39Z) - Logical Credal Networks [87.25387518070411]
本稿では,論理と確率を組み合わせた先行モデルの多くを一般化した表現的確率論的論理である論理的クレダルネットワークを紹介する。
本稿では,不確実性のあるマスターミンドゲームを解くこと,クレジットカード詐欺を検出することを含む,最大後部推論タスクの性能について検討する。
論文 参考訳(メタデータ) (2021-09-25T00:00:47Z) - CausalCity: Complex Simulations with Agency for Causal Discovery and
Reasoning [68.74447489372037]
本稿では,因果探索と反事実推論のためのアルゴリズムの開発を目的とした,高忠実度シミュレーション環境を提案する。
私たちの作業の中核となるコンポーネントは、複雑なシナリオを定義して作成することが簡単になるような、テキストの緊急性を導入することです。
我々は3つの最先端の手法による実験を行い、ベースラインを作成し、この環境の可利用性を強調する。
論文 参考訳(メタデータ) (2021-06-25T00:21:41Z) - Equilibrium Design for Concurrent Games [5.9873770241999]
ゲーム理論において、メカニズム設計は、ゲームの望ましい結果を達成するためのインセンティブの設計に関係している。
インセンティブの設計について検討し、例えば、所与の時間論理的性質を満たす平衡を求める。
応用として、平衡設計は、並列ゲームに対する合理的な合成と検証問題の代替解として用いられる。
論文 参考訳(メタデータ) (2021-06-18T15:45:45Z) - Online Learning Probabilistic Event Calculus Theories in Answer Set
Programming [70.06301658267125]
イベント認識(CER)システムは、事前に定義されたイベントパターンを使用して、ストリーミングタイムスタンプデータセットで発生を検出する。
本稿では,複雑なイベントパターンによる確率論的推論を,イベント計算で重み付けされたルールの形で行うことができるAnswer Set Programming(ASP)に基づくシステムを提案する。
その結果, 効率と予測の両面で, 新たなアプローチの優位性が示された。
論文 参考訳(メタデータ) (2021-03-31T23:16:29Z) - Automated Temporal Equilibrium Analysis: Verification and Synthesis of
Multi-Player Games [5.230352342979224]
マルチエージェントシステムにおいて、合理的な検証問題は、システム内でどの時相論理特性が保持されるかをチェックすることである。
パリティゲームの集合の解に有理検証問題を還元する手法を提案する。
論文 参考訳(メタデータ) (2020-08-13T01:43:31Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳(メタデータ) (2020-06-05T10:56:52Z) - Probabilistic Performance-Pattern Decomposition (PPPD): analysis
framework and applications to stochastic mechanical systems [8.975760915194765]
本稿では,システムの挙動に関する構造的特徴を得るための枠組みを提案する。
このフレームワークは Probabilistic Performance-Pattern Decomposition (PPPD) と名付けられた。
論文 参考訳(メタデータ) (2020-03-04T17:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。