論文の概要: Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent

• arxiv url: http://arxiv.org/abs/2007.14358v2
• Date: Mon, 8 Mar 2021 04:15:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-06 02:11:34.172733
• Title: Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent
• Title（参考訳）: 予測的ブラックウェルアプローチによるより高速なゲーム解決:レギュレットマッチングとミラーディフレッシュを接続
• Authors: Gabriele Farina and Christian Kroer and Tuomas Sandholm
• Abstract要約: FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
• 参考スコア（独自算出の注目度）: 119.5481797273995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Blackwell approachability is a framework for reasoning about repeated games with vector-valued payoffs. We introduce predictive Blackwell approachability, where an estimate of the next payoff vector is given, and the decision maker tries to achieve better performance based on the accuracy of that estimator. In order to derive algorithms that achieve predictive Blackwell approachability, we start by showing a powerful connection between four well-known algorithms. Follow-the-regularized-leader (FTRL) and online mirror descent (OMD) are the most prevalent regret minimizers in online convex optimization. In spite of this prevalence, the regret matching (RM) and regret matching+ (RM+) algorithms have been preferred in the practice of solving large-scale games (as the local regret minimizers within the counterfactual regret minimization framework). We show that RM and RM+ are the algorithms that result from running FTRL and OMD, respectively, to select the halfspace to force at all times in the underlying Blackwell approachability game. By applying the predictive variants of FTRL or OMD to this connection, we obtain predictive Blackwell approachability algorithms, as well as predictive variants of RM and RM+. In experiments across 18 common zero-sum extensive-form benchmark games, we show that predictive RM+ coupled with counterfactual regret minimization converges vastly faster than the fastest prior algorithms (CFR+, DCFR, LCFR) across all games but two of the poker games, sometimes by two or more orders of magnitude.
• Abstract（参考訳）: Blackwell Approachabilityは、ベクター値のペイオフを持つ繰り返しゲームについて推論するためのフレームワークである。 我々は,次の支払ベクトルの見積を行う予測的なブラックウェルアプローチ性を導入し,その推定器の精度に基づいて,意思決定者によるより良い性能の達成を試みる。 予測的なブラックウェルアプローチ性を実現するアルゴリズムを導出するために、まず4つのよく知られたアルゴリズム間の強力な接続を示す。 FTRL(Follow-the-regularized-leader)とOMD(Online mirror descent)は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 この傾向にもかかわらず、大規模なゲーム(反実的後悔最小化フレームワーク内の局所的後悔最小化器として)を解く実践において、後悔マッチング(RM)と後悔マッチング+(RM+)アルゴリズムが好まれている。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 この接続にFTRLまたはOMDの予測変種を適用することにより、予測的なブラックウェルアプローチ性アルゴリズムとRMとRM+の予測変種を得る。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では、RM+と反ファクト的後悔の最小化の組み合わせは、全てのゲームで最速の先行アルゴリズム(CFR+, DCFR, LCFR)よりもはるかに早く収束するが、ポーカーゲームのうち2つは、時には2桁以上のオーダーで収束することを示した。

関連論文リスト

• Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent [44.080852682765276]
  本研究は,楽観的オンラインミラードライザー(OMD)による重み付き反事実的後悔の最小化を探求する。 PCFR+とDiscounted CFR(DCFR)を原則的に統合し、支配的な作用の負の効果を迅速に緩和する。 PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。
  論文  参考訳（メタデータ） (2024-04-22T05:37:22Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [72.43065138581589]
  RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。 本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。 そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• Regret Matching+: (In)Stability and Fast Convergence in Games [68.13214224119024]
  RM+とその予測バージョンは不安定であり,他のプレイヤーが大きな後悔を味わう可能性がある。 これらの修正は、RM+による通常のゲームにおいて、個々の後悔に対して$O(T1/4)$$と$O(1)$の社会的後悔を得るのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-05-24T04:26:21Z)
• Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent [67.60077332154853]
  反実的回帰最小化(英: Counterfactual Regret Minimization, CFR)は、局所的反実的後悔を最小化することにより、全遺を最小化する後悔最小化アルゴリズムである。 FTRL(Follow-the-Regularized-Lead)アルゴリズムとOMD(Online Mirror Descent)アルゴリズムは,オンライン凸最適化における最小化アルゴリズムである。 本稿では,CFR と Regret Matching+ の CFR が FTRL および OMD の特別な形式であることを証明し,CFR を解析・拡張する新しい方法を提案する。
  論文  参考訳（メタデータ） (2021-10-11T02:12:25Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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