論文の概要: Stochastic Regret Minimization in Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2002.08493v1
• Date: Wed, 19 Feb 2020 23:05:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 13:37:16.394520
• Title: Stochastic Regret Minimization in Extensive-Form Games
• Title（参考訳）: 集中型ゲームにおける確率回帰最小化
• Authors: Gabriele Farina, Christian Kroer, and Tuomas Sandholm
• Abstract要約: Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
• 参考スコア（独自算出の注目度）: 109.43344748069933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte-Carlo counterfactual regret minimization (MCCFR) is the state-of-the-art algorithm for solving sequential games that are too large for full tree traversals. It works by using gradient estimates that can be computed via sampling. However, stochastic methods for sequential games have not been investigated extensively beyond MCCFR. In this paper we develop a new framework for developing stochastic regret minimization methods. This framework allows us to use any regret-minimization algorithm, coupled with any gradient estimator. The MCCFR algorithm can be analyzed as a special case of our framework, and this analysis leads to significantly-stronger theoretical on convergence, while simultaneously yielding a simplified proof. Our framework allows us to instantiate several new stochastic methods for solving sequential games. We show extensive experiments on three games, where some variants of our methods outperform MCCFR.
• Abstract（参考訳）: Monte-Carlo counterfactual regret minimization (MCCFR) は、木を横断するには大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 サンプリングによって計算可能な勾配推定を使用することで動作する。 しかし、シーケンシャルゲームに対する確率的手法はMCCFRを超えては広く研究されていない。 本稿では,確率的後悔最小化手法を開発するための新しい枠組みを開発する。 このフレームワークは、あらゆる遅延最小化アルゴリズムを、任意の勾配推定器と組み合わせることができる。 MCCFRアルゴリズムは我々のフレームワークの特別なケースとして分析でき、この分析は、単純な証明を同時に生成しながら収束に関する理論を著しく強めている。 我々のフレームワークは、シーケンシャルゲームを解くためのいくつかの新しい確率的手法をインスタンス化する。 3つのゲームで広範な実験を行い,mccfrに勝る手法を示した。

関連論文リスト

• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization [20.718016474717196]
  我々は,非regretゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。 これらの戦略の一般的な選択は、いわゆるno-regret学習アルゴリズムである。 コンベックス最適化のための古典的な一階法の多くは、我々のフレームワークの特別なケースとして解釈できることを示す。
  論文  参考訳（メタデータ） (2021-11-22T16:10:18Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)
• Reparameterized Variational Divergence Minimization for Stable Imitation [57.06909373038396]
  確率的発散の選択における変動が、より高性能なILOアルゴリズムをもたらす可能性について検討する。 本稿では,提案する$f$-divergence最小化フレームワークの課題を軽減するために,逆模倣学習のための再パラメータ化手法を提案する。 経験的に、我々の設計選択は、ベースラインアプローチより優れ、低次元連続制御タスクにおける専門家のパフォーマンスとより密に適合するIOOアルゴリズムを許容することを示した。
  論文  参考訳（メタデータ） (2020-06-18T19:04:09Z)

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

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