Fugu-MT 論文翻訳(概要): Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)

論文の概要: Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)

arxiv url: http://arxiv.org/abs/2210.09924v2
Date: Thu, 27 Jul 2023 08:55:04 GMT
ステータス: 処理完了
システム内更新日: 2023-07-28 20:41:34.174703
Title: Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)
Title（参考訳）: グラフニューラルネットワークによるパリティゲームにおける勝利領域予測(拡張抽象)
Authors: Tobias Hecking and Swathy Muthukrishnan and Alexander Weinert
Abstract要約: グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
参考スコア（独自算出の注目度）: 68.8204255655161
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Solving parity games is a major building block for numerous applications in reactive program verification and synthesis. While they can be solved efficiently in practice, no known approach has a polynomial worst-case runtime complexity. We present a incomplete polynomial-time approach to determining the winning regions of parity games via graph neural networks. Our evaluation on 900 randomly generated parity games shows that this approach is effective and efficient in practice. It correctly determines the winning regions of $\sim$60\% of the games in our data set and only incurs minor errors in the remaining ones. We believe that this approach can be extended to efficiently solve parity games as well.
Abstract（参考訳）: パリティゲームの解決は、リアクティブプログラム検証と合成における多くの応用のための主要な構成要素である。実際に効率的に解けるが、多項式最悪の実行時複雑性を持つ手法は知られていない。グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全多項式時間アプローチを提案する。ランダムに生成した900個のパリティゲームに対する評価は,本手法が実際に有効かつ効果的であることを示す。これは、データセット内のゲームのうち$\sim$60\%の勝利領域を正しく決定し、残りのゲームでのみ小さなエラーを発生させる。このアプローチはパリティゲームを効率的に解くためにも拡張できると考えています。

関連論文リスト

Runtime analysis of a coevolutionary algorithm on impartial combinatorial games [1.104960878651584]
進化的アルゴリズム(CoEA)は、現代人との相互作用に基づいて最強を反復的に選択し、次の世代で両親として選択した個体群を用いて、個体群を進化させる。しかし,CoEAのゲームプレイへの応用はサイクリングなどの病理的行動のため,実行時のペイオフ状況において特に問題となる。本稿では,解析の範囲を推し進め,公平なゲームのための最適な戦略を見出す。この結果はどんな公平なゲームにも当てはまり、多くのゲームでは、インプリッド・バウンドは数の関数として、あるいは準ポリノミアルである。
論文参考訳（メタデータ） (2024-09-06T10:39:17Z)
History Filtering in Imperfect Information Games: Algorithms and Complexity [16.23892847804002]
本稿では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。サブゲームのルートから単一の履歴を構築することは、一般的には難解であることを示す。また,トリックテイクカードゲームのためのマルコフチェインモンテカルロベース生成アルゴリズムについても紹介する。
論文参考訳（メタデータ） (2023-11-24T18:34:36Z)
Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文参考訳（メタデータ） (2023-03-22T03:28:12Z)
Convergence analysis and acceleration of the smoothing methods for solving extensive-form games [0.6875312133832078]
2人のプレイヤーとゼロサムを持つ拡張形式のゲームを考える。このようなゲームでは、最適戦略を求める問題は双線型サドルポイント問題として定式化することができる。このような大規模双線形サドルポイント問題を解決するために, 平滑化法である過剰ギャップ法 (EGT) が研究されている。我々のゴールは、大規模なゲームに適用できるように、広範囲なゲームを解決するための平滑化法を改善することである。
論文参考訳（メタデータ） (2023-03-20T11:57:13Z)
Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文参考訳（メタデータ） (2022-08-22T08:31:46Z)
Public Information Representation for Adversarial Team Games [31.29335755664997]
対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
論文参考訳（メタデータ） (2022-01-25T15:07:12Z)
Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文参考訳（メタデータ） (2021-01-21T10:35:09Z)
Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文参考訳（メタデータ） (2020-10-31T18:19:29Z)
Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-21T17:51:57Z)

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