論文の概要: Automated Approach for Solving Infinite-state Polynomial Reachability Games
- arxiv url: http://arxiv.org/abs/2605.10169v1
- Date: Mon, 11 May 2026 08:19:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:50.637559
- Title: Automated Approach for Solving Infinite-state Polynomial Reachability Games
- Title（参考訳）: 無限状態ポリノミアルリーチ可能性ゲームの自動解法
- Authors: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, Đorđe Žikelić,
- Abstract要約: 有限個の実変数の値上で定義された無限状態グラフ上でのターンベースリーチビリティゲームについて検討する。
本稿では, 到達性ゲームのためのランキング証明書と, $texttREACH$ playerが指定された初期状態から入賞戦略を持っていることを証明するための健全かつ完全な証明ルールを提案する。
本実験では,既存の手法の到達範囲から外れた文献から,本手法の難解な事例を解く能力について実証した。
- 参考スコア（独自算出の注目度）: 9.066824933763142
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reachability games are two-player games played on a graph, where the objective of $\texttt{REACH}$ player is to reach the target set whereas the objective of $\texttt{SAFE}$ player is to stay away from the target set. Reachability games have important applications in artificial intelligence and reactive synthesis, and many of these applications give rise to infinite-state reachability games. In this paper, we study turn-based reachability games on infinite-state graphs defined over valuations of a finite set of real variables. We consider the problem of determining the existence of and computing a winning strategy for $\texttt{REACH}$ player. Our contributions are twofold. First, we propose ranking certificates for reachability games, a sound and complete proof rule for proving that $\texttt{REACH}$ player has a winning strategy from the specified initial state. Second, we consider polynomial reachability games, where transitions and objectives are described by polynomial constraints over real variables, and propose a fully automated algorithm for computing a winning strategy for $\texttt{REACH}$ player together with a formal correctness witness in the form of a ranking certificate. The algorithm is sound, semi-complete, and runs in sub-exponential time. Our experiments demonstrate the ability of our method to solve challenging examples from the literature that were out of the reach of existing methods. Specifically, for the classical Cinderella-Stepmother game, we are able to compute an optimal winning strategy for an arbitrary precision parameter for the first time.
- Abstract（参考訳）: 到達可能性ゲームはグラフ上でプレイされる2つのプレイヤーゲームであり、$\texttt{REACH}$ player の目的はターゲットセットに到達することであり、$\texttt{SAFE}$ player の目的はターゲットセットから離れることである。
到達性ゲームは人工知能や反応合成において重要な応用であり、これらの応用の多くは無限状態到達性ゲームを生み出している。
本論文では,有限個の実変数の値上で定義された無限状態グラフ上のターンベースリーチビリティゲームについて検討する。
我々は,$\texttt{REACH}$ playerの勝利戦略を決定・計算する問題を考える。
私たちの貢献は2倍です。
まず、到達性ゲームのためのランキング証明書と、$\texttt{REACH}$ playerが指定された初期状態から勝利戦略を持つことを証明するための健全かつ完全な証明ルールを提案する。
第2に、実変数に対する多項式制約によって遷移と目的が記述される多項式到達性ゲームについて考察し、ランキング証明の形で正式な正当性証人とともに$\texttt{REACH}$プレーヤの勝利戦略を計算するための完全自動アルゴリズムを提案する。
アルゴリズムは音声で半完全であり、指数以下の時間で実行される。
本実験では,既存の手法の到達範囲から外れた文献から,本手法の難解な事例を解く能力について実証した。
具体的には、古典的なシンデレラ-ステッペマザーゲームでは、任意の精度パラメータに対する最適な勝利戦略を初めて計算することができる。
関連論文リスト
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。
我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
論文 参考訳（メタデータ） (2025-06-04T00:24:14Z) - Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End
Policy and Optimistic Smooth Fictitious Play [11.480308614644041]
我々は、2段階の戦略カードゲーム「Regends of Code and Magic」を研究する。
マルチステージゲームにおける難題を解決するために,エンド・ツー・エンドのポリシーを提案する。
私たちのアプローチはCOG2022コンペティションの2連覇です。
論文 参考訳（メタデータ） (2023-03-07T17:55:28Z) - Learning to Play Stochastic Two-player Perfect-Information Games without
Knowledge [5.071342645033634]
我々はDescentフレームワークを拡張し、完全な情報を持つ2人プレイヤゲームのコンテキストにおける学習と計画を可能にする。
我々は、最先端のアルゴリズムに対してEin wurfelt!で評価する。
最良の結果を得るのはDescentの一般化である。
論文 参考訳（メタデータ） (2023-02-08T20:27:45Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - A Ranking Game for Imitation Learning [22.028680861819215]
模倣を、$textitpolicy$と$textitreward$関数の間の2プレイヤーランキングベースのStackelbergゲームとして扱う。
このゲームは、オフラインの好みから学習する逆強化学習(IRL)法と方法の両方の多くのサブセットを含んでいる。
本研究では,均衡条件下での準最適模倣学習を容易にするために,政策性能のランク付けに使用される損失関数の要件を理論的に分析する。
論文 参考訳（メタデータ） (2022-02-07T19:38:22Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳（メタデータ） (2021-11-07T21:15:35Z) - Equilibria for Games with Combined Qualitative and Quantitative
Objectives [15.590197778287616]
我々は,各プレイヤーが独立して戦略的に行動することが想定されるプロセスである並行ゲームについて研究する。
我々の主な結果は、そのようなゲームにおける厳密なエプシロン・ナッシュ均衡の存在を決定することは2ExpTime完全であるということである。
論文 参考訳（メタデータ） (2020-08-13T01:56:24Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Efficient exploration of zero-sum stochastic games [83.28949556413717]
ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。
限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。
私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
論文 参考訳（メタデータ） (2020-02-24T20:30:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。