論文の概要: Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games

• arxiv url: http://arxiv.org/abs/2009.14521v2
• Date: Wed, 16 Dec 2020 12:11:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 23:35:03.671746
• Title: Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games
• Title（参考訳）: 大規模2人競技における量子対数爆発の複雑さとアルゴリズム
• Authors: David Milec, Jakub \v{C}ern\'y, Viliam Lis\'y, Bo An
• Abstract要約: 伝統的なゲーム理論の解の概念は、完全に合理的なプレイヤーを前提としており、従って、従属的な相手を活用できる能力は限られている。 本稿では,通常のゲームや広角ゲームにおいて,量子的対戦相手に対する効果的で堅牢な戦略を計算するためのスケーラブルなアルゴリズムを解析し,提案することを目的とする。
• 参考スコア（独自算出の注目度）: 16.43565579998679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. One type of subrationality that describes human behavior well is the quantal response. While there exist algorithms for computing solutions against quantal opponents, they either do not scale or may provide strategies that are even worse than the entirely-rational Nash strategies. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games. Our contributions are: (1) we define two different solution concepts related to exploiting quantal opponents and analyze their properties; (2) we prove that computing these solutions is computationally hard; (3) therefore, we evaluate several heuristic approximations based on scalable counterfactual regret minimization (CFR); and (4) we identify a CFR variant that exploits the bounded opponents better than the previously used variants while being less exploitable by the worst-case perfectly-rational opponent.
• Abstract（参考訳）: 伝統的なゲーム理論の解法の概念は、完全に合理的なプレイヤーを前提としており、従属的な対戦相手を搾取する能力は限られている。 人間の振舞いをうまく表現する亜合理性の一種は、量子応答である。 量子的相手に対する解を計算するアルゴリズムは存在するが、スケールしないか、完全に合理的なナッシュ戦略よりもさらに悪い戦略を提供する可能性がある。 本稿では,正規および広範囲のゲームにおいて,量子敵に対する効率的かつロバストな戦略を計算するためのスケーラブルなアルゴリズムを解析・提案することを目的とする。 Our contributions are: (1) we define two different solution concepts related to exploiting quantal opponents and analyze their properties; (2) we prove that computing these solutions is computationally hard; (3) therefore, we evaluate several heuristic approximations based on scalable counterfactual regret minimization (CFR); and (4) we identify a CFR variant that exploits the bounded opponents better than the previously used variants while being less exploitable by the worst-case perfectly-rational opponent.

関連論文リスト

• Anytime-Constrained Multi-Agent Reinforcement Learning [6.981971551979697]
  我々は、任意の時間制約均衡(ACE)に対応する解を持つマルチエージェント設定に、任意の時間制約を導入する。 実効性のあるポリシーの計算的特徴を含む,任意の時間制約付きマルコフゲームに関する包括的理論を提案する。 また、アクション制約付きマルコフゲームに対する効率的な計算の第一理論も、独立に興味を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-31T05:07:01Z)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Numerical solution of a PDE arising from prediction with expert advice [2.048226951354646]
  本研究は,エキスパート・アドバイスを用いたオンライン機械学習における予測問題について,対向的な環境で検討する。 このゲームの多くのステップに対する連続極限は、この解が両方のプレイヤーにとって最適な戦略を符号化する退化楕円型方程式である。
  論文  参考訳（メタデータ） (2024-06-09T12:17:05Z)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  マルチプレイヤーゲームにおける平衡は、一意でも爆発的でもない。 本稿では,平等な共有という自然な目的に焦点をあてることで,これらの課題に対処するための最初の一歩を踏み出す。 我々は、様々な設定でほぼ同じシェアを確実に得る、非回帰学習にインスパイアされた、一連の効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-06-06T15:59:17Z)
• Variational Methods for Computing Non-Local Quantum Strategies [1.95414377613382]
  非ローカルゲームでは、2人の非コミュニケーションプレーヤーが、ゲームのルールに違反しない戦略を持っていることを審判に納得させるために協力する。 提案アルゴリズムは,グラフカラーゲームに最適な量子戦略を実装した近距離回路を生成可能であることを示す。
  論文  参考訳（メタデータ） (2023-11-02T16:17:18Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games [95.70078702838654]
  本論文では,自然政策グラディエントアルゴリズムの自然拡張について検討する。 我々は,サンプル数,反復数,集中係数,近似誤差の観点から,アルゴリズムの性能を徹底的に評価する。
  論文  参考訳（メタデータ） (2021-02-17T17:49:57Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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