論文の概要: Convergence analysis and acceleration of the smoothing methods for solving extensive-form games

• arxiv url: http://arxiv.org/abs/2303.11046v1
• Date: Mon, 20 Mar 2023 11:57:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-21 15:46:22.405705
• Title: Convergence analysis and acceleration of the smoothing methods for solving extensive-form games
• Title（参考訳）: 広義ゲーム解決のための平滑化法の収束解析と加速
• Authors: Keigo Habara, Ellen Hidemi Fukuda, Nobuo Yamashita
• Abstract要約: 2人のプレイヤーとゼロサムを持つ拡張形式のゲームを考える。 このようなゲームでは、最適戦略を求める問題は双線型サドルポイント問題として定式化することができる。 このような大規模双線形サドルポイント問題を解決するために, 平滑化法である過剰ギャップ法 (EGT) が研究されている。 我々のゴールは、大規模なゲームに適用できるように、広範囲なゲームを解決するための平滑化法を改善することである。
• 参考スコア（独自算出の注目度）: 0.6875312133832078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The extensive-form game has been studied considerably in recent years. It can represent games with multiple decision points and incomplete information, and hence it is helpful in formulating games with uncertain inputs, such as poker. We consider an extended-form game with two players and zero-sum, i.e., the sum of their payoffs is always zero. In such games, the problem of finding the optimal strategy can be formulated as a bilinear saddle-point problem. This formulation grows huge depending on the size of the game, since it has variables representing the strategies at all decision points for each player. To solve such large-scale bilinear saddle-point problems, the excessive gap technique (EGT), a smoothing method, has been studied. This method generates a sequence of approximate solutions whose error is guaranteed to converge at $\mathcal{O}(1/k)$, where $k$ is the number of iterations. However, it has the disadvantage of having poor theoretical bounds on the error related to the game size. This makes it inapplicable to large games. Our goal is to improve the smoothing method for solving extensive-form games so that it can be applied to large-scale games. To this end, we make two contributions in this work. First, we slightly modify the strongly convex function used in the smoothing method in order to improve the theoretical bounds related to the game size. Second, we propose a heuristic called centering trick, which allows the smoothing method to be combined with other methods and consequently accelerates the convergence in practice. As a result, we combine EGT with CFR+, a state-of-the-art method for extensive-form games, to achieve good performance in games where conventional smoothing methods do not perform well. The proposed smoothing method is shown to have the potential to solve large games in practice.
• Abstract（参考訳）: 幅広い形態のゲームは近年かなり研究されている。 複数の決定ポイントと不完全な情報を持つゲームを表現することができ、ポーカーのような不確実な入力を持つゲームを定式化するのに役立つ。 2人のプレイヤーとゼロサム、すなわち彼らの報酬の合計が常にゼロである拡張フォームゲームを考える。 このようなゲームでは、最適戦略を求める問題は双線型サドルポイント問題として定式化することができる。 この定式化はゲームのサイズによって大きくなり、各プレイヤーのすべての決定点における戦略を表す変数を持つ。 このような大規模双線形サドルポイント問題を解決するため, 平滑化法である過剰ギャップ法(EGT)が研究されている。 この方法は、誤差が$\mathcal{o}(1/k)$で収束することを保証された近似解の列を生成する。 しかし、ゲームサイズに関する誤差の理論的境界が低くなるという欠点がある。 これは大きなゲームには適用できない。 当社の目標は,大規模ゲームに適用可能なように,広範なフォームゲーム解決のための平滑化方法を改善することにある。 この目的のために、私たちはこの仕事に2つの貢献をしています。 まず,ゲームサイズに関する理論的境界を改善するため,平滑化法で用いられる強凸関数をわずかに修正した。 第2に,平滑化法を他の手法と組み合わせることで,現実の収束を加速するヒューリスティックな「中心化トリック」を提案する。 その結果,EGT と CFR+ を組み合わせることで,従来の平滑化手法がうまく動作しないゲームにおいて,優れたパフォーマンスを実現することができた。 提案手法は,大規模ゲームを現実的に解く可能性を秘めている。

関連論文リスト

• Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Games [115.77438739169155]
  汎用ゲームにおける状態値関数の一般化であるtextitEnforceable Payoff Frontier (EPF) の学習を提案する。 Stackelbergの設定にFAを適用する最初の方法です。
  論文  参考訳（メタデータ） (2022-12-29T19:05:50Z)
• Safe Subgame Resolving for Extensive Form Correlated Equilibrium [47.155175336085364]
  相関平衡(Correlated Equilibrium)は、ナッシュ平衡(NE)よりも一般的な解概念であり、社会福祉の改善につながる。 テキストサブゲーム解決は,ゼロサムゲームにおけるNEの発見に極めて成功した手法であり,一般サム EFCE の解法である。 サブゲーム解決は、テキストトン方式で相関計画を洗練させる: ゲーム全体を前もって解決するのではなく、実際のプレイで到達したサブゲームにおける戦略のためにのみ解決する。
  論文  参考訳（メタデータ） (2022-12-29T14:20:48Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
  論文  参考訳（メタデータ） (2022-10-26T11:41:57Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization [20.718016474717196]
  我々は,非regretゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。 これらの戦略の一般的な選択は、いわゆるno-regret学習アルゴリズムである。 コンベックス最適化のための古典的な一階法の多くは、我々のフレームワークの特別なケースとして解釈できることを示す。
  論文  参考訳（メタデータ） (2021-11-22T16:10:18Z)
• Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games [95.70078702838654]
  本論文では,自然政策グラディエントアルゴリズムの自然拡張について検討する。 我々は,サンプル数,反復数,集中係数,近似誤差の観点から,アルゴリズムの性能を徹底的に評価する。
  論文  参考訳（メタデータ） (2021-02-17T17:49:57Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。 この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。 各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-21T17:51:57Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)
• Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
  滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。 スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。 バイリニアゲームに最適なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-02T19:21:48Z)

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

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