論文の概要: Optimistic Online Learning in Symmetric Cone Games

• arxiv url: http://arxiv.org/abs/2504.03592v1
• Date: Fri, 04 Apr 2025 16:59:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-07 14:46:58.759792
• Title: Optimistic Online Learning in Symmetric Cone Games
• Title（参考訳）: シンメトリコーンゲームにおける最適オンライン学習
• Authors: Anas Barakat, Wayne Lin, John Lazarsfeld, Antonios Varvitsiotis,
• Abstract要約: そこで我々は,Optimistic Symmetric Cone Multiplicative Weights Updateアルゴリズムを導入し,$mathcalO(1/epsilon)$の反復複雑性を確立し,$epsilon$-saddle点に達する。 重要な技術的貢献は、トレースワンノルムに対する対称錐負のエントロピーの強い凸性の新たな証明である。
• 参考スコア（独自算出の注目度）: 3.124884279860061
• License:
• Abstract: Optimistic online learning algorithms have led to significant advances in equilibrium computation, particularly for two-player zero-sum games, achieving an iteration complexity of $\mathcal{O}(1/\epsilon)$ to reach an $\epsilon$-saddle point. These advances have been established in normal-form games, where strategies are simplex vectors, and quantum games, where strategies are trace-one positive semidefinite matrices. We extend optimistic learning to symmetric cone games (SCGs), a class of two-player zero-sum games where strategy spaces are generalized simplices (trace-one slices of symmetric cones). A symmetric cone is the cone of squares of a Euclidean Jordan Algebra; canonical examples include the nonnegative orthant, the second-order cone, the cone of positive semidefinite matrices, and their products, all fundamental to convex optimization. SCGs unify normal-form and quantum games and, as we show, offer significantly greater modeling flexibility, allowing us to model applications such as distance metric learning problems and the Fermat-Weber problem. To compute approximate saddle points in SCGs, we introduce the Optimistic Symmetric Cone Multiplicative Weights Update algorithm and establish an iteration complexity of $\mathcal{O}(1/\epsilon)$ to reach an $\epsilon$-saddle point. Our analysis builds on the Optimistic Follow-the-Regularized-Leader framework, with a key technical contribution being a new proof of the strong convexity of the symmetric cone negative entropy with respect to the trace-one norm, a result that may be of independent interest.
• Abstract（参考訳）: 最適オンライン学習アルゴリズムは平衡計算、特に2プレーヤのゼロサムゲームにおいて、$\mathcal{O}(1/\epsilon)$の反復複雑性を達成し、$\epsilon$-saddleポイントに達した。 これらの進歩は、戦略が単純ベクトルである正規形式ゲームや、戦略がトレース1正の半定値行列である量子ゲームで確立されている。 戦略空間が一般化された単純性(対称錐のトラスワンスライス)を持つ2プレイヤーゼロサムゲーム(英語版)のクラスである対称錐ゲーム(SCG)に楽観的な学習を拡張する。 対称錐(英: symmetric cone)はユークリッド・ヨルダン・アルゲブラの平方体の錐であり、標準的な例としては、非負のオルサント、二階の円錐、正半定値行列の錐、およびそれらの積、すべて凸最適化の基本である。 SCGは通常のゲームと量子ゲームを統一し、モデリングの柔軟性を大幅に向上させ、距離メートル法学習問題やFermat-Weber問題といったアプリケーションをモデル化できるようにします。 SCGにおける近似的なサドル点を計算するために、最適対称コーン乗算重み更新アルゴリズムを導入し、$\mathcal{O}(1/\epsilon)$の反復複雑性を確立し、$\epsilon$-saddle点に達する。 我々の分析は最適化的フォロー・ザ・レギュラライズド・リーダー・フレームワークに基づいており、これは対称円錐負のエントロピーの強い凸性の新たな証明であり、これは無関心であるかもしれない。

関連論文リスト

• Computing Game Symmetries and Equilibria That Respect Them [77.72705755558839]
  ゲームにおける対称性の同定と利用の計算について検討する。 ゲーム対称性とグラフ自己同型の間には強い関係がある。 与えられた対称性の集合を尊重するナッシュ均衡を求めることは、ブラウワーの不動点や勾配降下問題と全く同じほど難しいことを示す。
  論文  参考訳（メタデータ） (2025-01-15T16:15:16Z)
• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。 行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。 ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
  論文  参考訳（メタデータ） (2024-09-02T20:07:25Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Hierarchies for Semidefinite Optimization in $\mathcal{C}^\star$-Algebras [0.0]
  本稿では,$mathcalCstar$-algebras上での一般コーンプログラムの有限次元緩和法を提案する。 我々は NPA のような一般化された問題に対するよく知られた階層性やラッサール階層、一般 SDP の拡張対称性の低下を示す。
  論文  参考訳（メタデータ） (2023-09-25T09:01:30Z)
• Multiplicative Updates for Online Convex Optimization over Symmetric Cones [28.815822236291392]
  任意の対称コーンのトレースワンスライスに対するオンライン最適化のためのプロジェクションフリーアルゴリズムであるSymmetric-Cone Multiplicative Weights Update (SCMWU)を導入する。 SCMWUは, 対称錐負エントロピーを正則化器とするFollow-the-Regularized-LeaderおよびOnline Mirror Descentと等価であることを示す。
  論文  参考訳（メタデータ） (2023-07-06T17:06:43Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• An algorithmic solution to the Blotto game using multi-marginal couplings [27.35514815248438]
  ヘテロジニアスな値を持つn個の戦場での一般2人プレイヤBlottoゲームに対する解を計算するための効率的なアルゴリズムについて述べる。 提案アルゴリズムは,予算と戦場価値とは無関係に,時間O(n2 + eps-4)のeps最適解から抽出する。 最適解が存在しない非対称値の場合、ナッシュ平衡は、同様の複雑さを持つeps-Nash平衡からアルゴリズムをサンプリングする。
  論文  参考訳（メタデータ） (2022-02-15T11:07:31Z)
• Multiplicative updates for symmetric-cone factorizations [0.0]
  コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。 SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
  論文  参考訳（メタデータ） (2021-08-02T09:23:39Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。