論文の概要: Solving Random Parity Games in Polynomial Time
- arxiv url: http://arxiv.org/abs/2007.08387v1
- Date: Thu, 16 Jul 2020 15:05:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 23:52:21.828426
- Title: Solving Random Parity Games in Polynomial Time
- Title(参考訳): 多項式時間でランダムパリティゲームを解く
- Authors: Richard Combes and Mikael Touati
- Abstract要約: パリティゲームは高い確率で時間$O(cal V|)$で解けることを示す。
また、非スパースゲームは高い確率で時間$O(cal V|)$で解けることを示し、$d=2$の場合の硬さに関する予想を出力する。
- 参考スコア(独自算出の注目度): 4.715993310546794
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of solving random parity games. We prove that parity
games exibit a phase transition threshold above $d_P$, so that when the degree
of the graph that defines the game has a degree $d > d_P$ then there exists a
polynomial time algorithm that solves the game with high probability when the
number of nodes goes to infinity. We further propose the SWCP (Self-Winning
Cycles Propagation) algorithm and show that, when the degree is large enough,
SWCP solves the game with high probability. Furthermore, the complexity of SWCP
is polynomial $O\Big(|{\cal V}|^2 + |{\cal V}||{\cal E}|\Big)$. The design of
SWCP is based on the threshold for the appearance of particular types of cycles
in the players' respective subgraphs. We further show that non-sparse games can
be solved in time $O(|{\cal V}|)$ with high probability, and emit a conjecture
concerning the hardness of the $d=2$ case.
- Abstract(参考訳): ランダムなパリティゲームを解決する問題を考察する。
我々は、パリティゲームが$d_p$以上の位相遷移しきい値を示すことを証明し、ゲームを定義するグラフの次数が $d > d_p$ であるとき、ノード数が無限大となると高い確率でゲームを解く多項式時間アルゴリズムが存在することを証明する。
さらに,scp (self-winning cycles propagation) アルゴリズムを提案し,scpが十分に大きい場合には高い確率で解くことを示す。
さらに、SWCP の複雑性は多項式 $O\Big(|{\cal V}|^2 + |{\cal V}||{\cal E}|\Big)$ である。
swcpの設計は、プレイヤーの各サブグラフにおける特定の種類のサイクルの出現のしきい値に基づいている。
さらに、非スパースゲームは高い確率で時間$o(|{\cal v}|)$で解くことができ、$d=2$ ケースの硬さに関する推測を出力できることを示した。
関連論文リスト
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳(メタデータ) (2023-05-15T05:37:32Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳(メタデータ) (2023-03-10T00:11:18Z) - Predicting Winning Regions in Parity Games via Graph Neural Networks
(Extended Abstract) [68.8204255655161]
グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。
これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
論文 参考訳(メタデータ) (2022-10-18T15:10:25Z) - Satisfiability Phase Transtion for Random Quantum 3XOR Games [0.0]
ランダムに生成された3XORゲームの動作を,多数の質問に対して数値的に検討する。
我々の実験は、ランダムに生成されたゲームが擬テレパシーである確率が 1 から遠く離れていることを強く示唆している。
また、ランダムに生成された3XORゲームが量子および古典的な「相転移」の両方を実行しているという強い証拠も見つかる。
論文 参考訳(メタデータ) (2022-09-10T12:54:53Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳(メタデータ) (2022-02-03T18:18:28Z) - The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs [6.305950347749109]
本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。
我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
論文 参考訳(メタデータ) (2021-10-08T15:24:31Z) - When Can We Learn General-Sum Markov Games with a Large Number of
Players Sample-Efficiently? [10.397170312149067]
本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。
まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。
第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-10-08T15:06:22Z) - Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal
Algorithm Escaping the Curse of Horizon [88.75843804630772]
エピソード強化学習は文脈的包帯を一般化する。
長期計画の地平線と未知の状態依存的な遷移は、サンプルの複雑さに若干の困難をもたらす。
MVPは$left(sqrtSAK + S2Aright)$ regretを楽しみ、$Omegaleft(sqrtSAK + S2Aright)$ lower bound of emphcontextual bandits to logarithmic termsに近づいている。
論文 参考訳(メタデータ) (2020-09-28T17:52:32Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-22T05:00:13Z) - Quasi-polynomial time algorithms for free quantum games in bounded
dimension [11.56707165033]
2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。
量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
論文 参考訳(メタデータ) (2020-05-18T16:55:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。