論文の概要: Payoff-based learning with matrix multiplicative weights in quantum games

• arxiv url: http://arxiv.org/abs/2311.02423v1
• Date: Sat, 4 Nov 2023 14:56:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-07 17:44:30.871891
• Title: Payoff-based learning with matrix multiplicative weights in quantum games
• Title（参考訳）: 量子ゲームにおける行列乗法重みを用いたペイオフ学習
• Authors: Kyriakos Lotidis and Panayotis Mertikopoulos and Nicholas Bambos and Jose Blanchet
• Abstract要約: 量子ゲーム(および半定値ゲーム)における学習の問題を、スカラーでペイオフに基づくフィードバックを用いて研究する。 本稿では,情報フレームワークに合わせた最小情報行列乗法(3MW)を提案する。 決定論的ペイオフフィードバックを持つ3MW法は,量子ミニマックスゲームにおけるバニラ,フル情報MMWアルゴリズムの収束率を保っていることを示す。
• 参考スコア（独自算出の注目度）: 35.111876815522116
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the $\mathcal{O}(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $\mathcal{O}(T^{-1/4})$ rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
• Abstract（参考訳）: 本稿では,量子ゲーム(および半定値ゲーム)における学習の問題について,スカラー,ペイオフに基づくフィードバックを用いて検討する。 具体的には、広く使われている行列乗算重み (MMW) アルゴリズムに焦点をあて、プレイヤーにゲーム(および/またはそれぞれの選択した状態)の完全な知識を求める代わりに、異なる情報フレームワークに合わせた最小情報行列乗算重み (3MW) 法一式を導入する。 この設定において収束を達成するのが難しいのは、古典的な有限ゲームとは対照的に、量子ゲームは純粋状態(純粋戦略の量子的等価性)の無限連続体を持つため、ペイオフベクトルを推定するための標準的な重要性重み付け技術は適用できないことである。 その代わり、バンディット凸最適化のアイデアを借用し、問題の半定義幾何学に適応したゼロ次勾配サンプラーを設計する。 最初の結果として,決定論的ペイオフフィードバックを持つ3MW法は,プレイヤーが1つのスカラーのみを観測したとしても,バニラの収束率$\mathcal{O}(1/\sqrt{T})$であり,量子ミニマックスゲームにおける完全情報MMWアルゴリズムであることを示す。 その後、アルゴリズムの情報要求をさらに緩和し、3MW法を提供し、プレイヤーは彼らのペイオフ観測可能なランダムな実現を観測するだけで、$\mathcal{O}(T^{-1/4})$レートで平衡に収束する。 最後に、ゼロサムゲームを超えて、提案した3MW法の正規化変種が、ある一階安定性条件を満たす全ての平衡に対して高い確率で局所収束を保証することを示す。

関連論文リスト

• $\mathcal{PT}$-symmetric mapping of three states and its implementation on a cloud quantum processor [0.9599644507730107]
  3つの純量子状態のマッピングのための新しい$mathcalPT$-symmetricアプローチを開発する。 我々は,Hermitianの場合,参照ベクトルの平均射影の保存,およびQuantum Fisher Informationと整合性を示す。 我々の研究は、量子通信、コンピューティング、暗号に$mathcalPT$-symmetricを適用するための新しい扉を開く。
  論文  参考訳（メタデータ） (2023-12-27T18:51:33Z)
• Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
  独立な連鎖と未知の遷移行列を持つゲームについて研究する。 このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。 我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-04T03:04:09Z)
• 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)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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