論文の概要: Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms

• arxiv url: http://arxiv.org/abs/2112.10890v3
• Date: Tue, 5 Dec 2023 22:12:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-07 11:57:28.263267
• Title: Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms
• Title（参考訳）: Revisiting Game Representations:シークエンシャル決定アルゴリズムにおける隠れた効率のコスト
• Authors: Vojt\v{e}ch Kova\v{r}\'ik, David Milec, Michal \v{S}ustr, Dominik Seitz, Viliam Lis\'y
• Abstract要約: 不完全な情報の下でのシーケンシャルな意思決定アルゴリズムの進歩は、大きなゲームで顕著な成功を収めている。 これらのアルゴリズムは伝統的に広義のゲーム形式を用いてゲームを形式化する。 プレイヤー固有の情報状態木に基づく特殊表現の使用が,一般的な回避策であることを示す。
• 参考スコア（独自算出の注目度）: 0.6749750044497732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent advancements in algorithms for sequential decision-making under imperfect information have shown remarkable success in large games such as limit- and no-limit poker. These algorithms traditionally formalize the games using the extensive-form game formalism, which, as we show, while theoretically sound, is memory-inefficient and computationally intensive in practice. To mitigate these challenges, a popular workaround involves using a specialized representation based on player specific information-state trees. However, as we show, this alternative significantly narrows the set of games that can be represented efficiently. In this study, we identify the set of large games on which modern algorithms have been benchmarked as being naturally represented by Sequential Bayesian Games. We elucidate the critical differences between extensive-form game and sequential Bayesian game representations, both theoretically and empirically. We further argue that the impressive experimental results often cited in the literature may be skewed, as they frequently stem from testing these algorithms only on this restricted class of games. By understanding these nuances, we aim to guide future research in developing more universally applicable and efficient algorithms for sequential decision-making under imperfect information.
• Abstract（参考訳）: 不完全な情報の下でのシーケンシャルな意思決定アルゴリズムの進歩は、リミットポーカーやノーリミットポーカーのような大きなゲームで顕著な成功を収めている。 これらのアルゴリズムは伝統的に広義のゲーム形式を用いてゲームを形式化するが、これは理論上は正しいが、実際はメモリ非効率で計算集約的である。 これらの課題を軽減するために、人気のある回避策はプレイヤー固有の情報状態木に基づく特殊表現を使用することである。 しかし、我々が示すように、この代替手段は効率的に表現できるゲームの集合を著しく狭める。 本研究では,現代のアルゴリズムが逐次ベイズゲームで自然に表現されているとベンチマークされた大規模ゲームの集合を同定する。 拡張型ゲームとシーケンシャルベイズゲーム表現の臨界差を理論的および経験的に解明する。 さらに、文献でしばしば引用される印象的な実験結果は、これらのアルゴリズムをこの制限された種類のゲームでのみテストすることに起因するため、歪曲される可能性があると論じる。 これらのニュアンスを理解することで、不完全な情報の下でシーケンシャルな意思決定のためのより普遍的に適用可能で効率的なアルゴリズムを開発するための将来の研究を導くことを目指している。

関連論文リスト

• History Filtering in Imperfect Information Games: Algorithms and Complexity [16.23892847804002]
  本稿では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。 サブゲームのルートから単一の履歴を構築することは、一般的には難解であることを示す。 また,トリックテイクカードゲームのためのマルコフチェインモンテカルロベース生成アルゴリズムについても紹介する。
  論文  参考訳（メタデータ） (2023-11-24T18:34:36Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。 ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-25T20:28:55Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• Spatial State-Action Features for General Games [5.849736173068868]
  汎用ゲームのための空間状態対応機能の設計と効率的な実装を定式化する。 これらは、局所的な状態の変数にマッチするかどうかに基づいて、アクションをインセンティブまたは非インセンティブ化するようにトレーニングできるパターンである。 任意の機能セットに対して,アクティブな機能を評価するための効率的なアプローチを提案する。
  論文  参考訳（メタデータ） (2022-01-17T13:34:04Z)
• Student of Games: A unified learning algorithm for both perfect and imperfect information games [22.97853623156316]
  Students of Gamesは、ガイド付き検索、自己学習、ゲーム理論推論を組み合わせたアルゴリズムである。 学生ゲームは,計算能力と近似能力が増大するにつれて,完全プレイに収束し,健全であることを示す。 学生はチェスと囲碁で強い成績を収め、無期限のテキサスホールディングスのポーカーで最強の公開エージェントを破り、スコットランドヤードで最先端のエージェントを倒した。
  論文  参考訳（メタデータ） (2021-12-06T17:16:24Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。 品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。 その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
  論文  参考訳（メタデータ） (2021-04-17T20:33:24Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)

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

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