論文の概要: Optimistic Online Learning in Symmetric Cone Games
- arxiv url: http://arxiv.org/abs/2504.03592v2
- Date: Mon, 25 Aug 2025 17:35:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-26 14:31:50.580824
- Title: Optimistic Online Learning in Symmetric Cone Games
- Title（参考訳）: シンメトリコーンゲームにおける最適オンライン学習
- Authors: Anas Barakat, Wayne Lin, John Lazarsfeld, Antonios Varvitsiotis,
- Abstract要約: 対称コーンゲーム(SCG)
オンライン学習アルゴリズム: 最適対称性コーン乗算重み更新(OSCMWU)
我々は、対称錐負のエントロピーがトレースワンノルムに対して強く凸であることを証明する。
- 参考スコア（独自算出の注目度）: 5.4831302830611195
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce symmetric cone games (SCGs), a broad class of multi-player games where each player's strategy lies in a generalized simplex (the trace-one slice of a symmetric cone). This framework unifies a wide spectrum of settings, including normal-form games (simplex strategies), quantum games (density matrices), and continuous games with ball-constrained strategies. It also captures several structured machine learning and optimization problems, such as distance metric learning and Fermat-Weber facility location, as two-player zero-sum SCGs. To compute approximate Nash equilibria in two-player zero-sum SCGs, we propose a single online learning algorithm: Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU). Unlike prior methods tailored to specific geometries, OSCMWU provides closed-form, projection-free updates over any symmetric cone and achieves an optimal $\tilde{\mathcal{O}}(1/\epsilon)$ iteration complexity for computing $\epsilon$-saddle points. Our analysis builds on the Optimistic Follow-the-Regularized-Leader framework and hinges on a key technical contribution: We prove that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm. This result extends known results for the simplex and spectraplex to all symmetric cones, and may be of independent interest.
- Abstract（参考訳）: 対称コーンゲーム (SCGs) は、各プレイヤーの戦略が一般化された単純体(対称コーンのトレースワンスライス)に置かれる多人数ゲームである。
このフレームワークは、通常の形式ゲーム(複雑な戦略)、量子ゲーム(密度行列)、ボール制約された戦略を持つ連続ゲームを含む幅広い設定を統一する。
また、距離メートル法学習やFermat-Weberの施設位置といった、構造化された機械学習と最適化の問題を2つのプレイヤーゼロサムSCGとして捉えている。
本研究では,2プレイヤーゼロサムSCGにおけるNash平衡を近似的に計算するために,1つのオンライン学習アルゴリズム,Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU)を提案する。
特定の測地線に合わせて調整された以前の方法とは異なり、OSCMWUは任意の対称錐体に対してクローズドなプロジェクションフリーな更新を提供し、$\epsilon$-saddleポイントを計算するのに最適な$\tilde{\mathcal{O}}(1/\epsilon)$イテレーション複雑性を達成する。
我々の分析はOptimistic Follow-the-Regularized-Leaderフレームワークに基づいており、重要な技術的貢献に基づいている。
この結果は、すべての対称錐体に対して単純体とスペクトル体の既知の結果を拡張し、独立した興味を持つかもしれない。
関連論文リスト
- Approximating fixed size quantum correlations in polynomial time [8.099700053397278]
固定サイズの2プレーヤフリーゲームの最適値に対する$varepsilon$-additive近似が時間内に計算可能であることを示す。
我々の主な結果は、制約付き量子分離性問題に適した新しいボース対称量子デフィネッティ定理に基づいている。
論文 参考訳（メタデータ） (2025-07-16T15:01:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。