論文の概要: The complexity of approximate (coarse) correlated equilibrium for incomplete information games
- arxiv url: http://arxiv.org/abs/2406.02357v1
- Date: Tue, 4 Jun 2024 14:35:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-05 15:50:54.778184
- Title: The complexity of approximate (coarse) correlated equilibrium for incomplete information games
- Title（参考訳）: 不完全情報ゲームにおける近似(粗相関平衡の複雑さ
- Authors: Binghui Peng, Aviad Rubinstein,
- Abstract要約: 不完全情報ゲームにおける近似平衡の分散学習の複雑さについて検討する。
我々の下限は、$epsilon$-approximate $mathitco$ correlation equilibriumというより簡単な解の概念にも当てはまる。
- 参考スコア（独自算出の注目度）: 16.96984593866157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{extensive}$-$\mathit{form}$ $\mathit{games}$, assuming $\mathsf{PPAD} \not\subset \mathsf{TIME}(n^{\mathsf{polylog}(n)})$, any polynomial-time learning algorithms must take at least $2^{\log_2^{1-o(1)}(|\mathcal{I}|)}$ iterations to converge to the set of $\epsilon$-approximate correlated equilibrium, where $|\mathcal{I}|$ is the number of nodes in the game and $\epsilon > 0$ is an absolute constant. This nearly matches, up to the $o(1)$ term, the algorithms of [PR'24, DDFG'24] for learning $\epsilon$-approximate correlated equilibrium, and resolves an open question of Anagnostides, Kalavasis, Sandholm, and Zampetakis [AKSZ'24]. Our lower bound holds even for the easier solution concept of $\epsilon$-approximate $\mathit{coarse}$ correlated equilibrium On the positive side, we give uncoupled dynamics that reach $\epsilon$-approximate correlated equilibria of a $\mathit{Bayesian}$ $\mathit{game}$ in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.
- Abstract（参考訳）: 不完全情報ゲームにおける近似平衡の分散学習の繰り返し複雑性について検討する。
負の面において、$\mathit{extensive}$-$\mathit{form}$$\mathit{games}$,suming $\mathsf{PPAD} \not\subset \mathsf{TIME}(n^{\mathsf{polylog}(n)})$, any polynomial-time learning algorithm must take least $2^{\log_2^{1-o(1)}(|\mathcal{I}|)} $|\mathcal{I}|$$$$$$\epsilon$-approximate correlation equilibrium, ここで、$|\mathcal{I}|$$はゲームのノードの数であり、$$\epsilon>0はゲーム内のノードの数である。
これは、$o(1)$の項までほぼ一致し、$\epsilon$-approximate correlation equilibrium を学ぶための [PR'24, DDFG'24] アルゴリズムが、アナグノステイド、カラバシス、サンドホルム、ザンペタキスの開問題(AKSZ'24)を解決する。
我々の下界は、より簡単な解の概念である $\epsilon$-approximate $\mathit{coarse}$ correlation equilibrium に対してさえ成り立つが、正の面では、型の数に依存することなく、$$\epsilon$-approximate correlation equilibria of a $\mathit{Bayesian}$ $\mathit{game}$$ のような非結合な力学を与える。
これはベイズゲームとワイドフォームゲームとの分離を示す。
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - Fast swap regret minimization and applications to approximate correlated
equilibria [20.047624953965965]
任意の定数$varepsilon>0$に対して、我々のアルゴリズムは$varepsilon T$-swap regretを$T = Mathsfpolylog(n)$ roundsで取得する。
我々のアルゴリズムは$varepsilon$に指数関数的依存を持つが、我々は一致する新しい下界を証明している。
論文 参考訳（メタデータ） (2023-10-30T15:35:24Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - 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) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。