論文の概要: Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms

• arxiv url: http://arxiv.org/abs/2111.05486v3
• Date: Sat, 23 Dec 2023 07:00:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-28 02:19:02.531495
• Title: Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms
• Title（参考訳）: 合理化可能性への非結合バンディット学習:ベンチマーク、障壁、アルゴリズム
• Authors: Jibang Wu, Haifeng Xu, Fan Yao
• Abstract要約: 一般ゲームにおける最終点収束保証を合理化可能性へ向けて検討する。 この学習課題は、最高の腕識別問題を自然に一般化する。 そこで我々は,Exp3をDimishing Historical rewardsで調整するアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 41.307340085194625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Under the uncoupled learning setup, the last-iterate convergence guarantee towards Nash equilibrium is shown to be impossible in many games. This work studies the last-iterate convergence guarantee in general games toward rationalizability, a key solution concept in epistemic game theory that relaxes the stringent belief assumptions in both Nash and correlated equilibrium. This learning task naturally generalizes best arm identification problems, due to the intrinsic connections between rationalizable action profiles and the elimination of iteratively dominated actions. Despite a seemingly simple task, our first main result is a surprisingly negative one; that is, a large and natural class of no regret algorithms, including the entire family of Dual Averaging algorithms, provably take exponentially many rounds to reach rationalizability. Moreover, algorithms with the stronger no swap regret also suffer similar exponential inefficiency. To overcome these barriers, we develop a new algorithm that adjusts Exp3 with Diminishing Historical rewards (termed Exp3-DH); Exp3-DH gradually forgets history at carefully tailored rates. We prove that when all agents run Exp3-DH (a.k.a., self-play in multi-agent learning), all iteratively dominated actions can be eliminated within polynomially many rounds. Our experimental results further demonstrate the efficiency of Exp3-DH, and that state-of-the-art bandit algorithms, even those developed specifically for learning in games, fail to reach rationalizability efficiently.
• Abstract（参考訳）: アンカップラーニング設定の下では、ナッシュ平衡に対する最終点収束保証は多くのゲームで不可能であることが示されている。 本研究は,nashと相関均衡の両方における厳密な信念仮定を緩和する認識ゲーム理論における鍵となる解概念である,合理化可能性に対する一般ゲームにおけるラストイテレート収束保証を考察する。 この学習課題は、合理的な行動プロファイルと反復的に支配される行動の排除との間の本質的な関係により、最適な腕識別問題を自然に一般化する。 一見単純な作業ですが、私たちの最初の主な結果は驚くほど否定的な結果です。つまり、重複平均アルゴリズムのファミリー全体を含む、後悔のない、大きくて自然なクラスは、合理化可能性に到達するために指数関数的に多くのラウンドを取ります。 さらに、noスワップ後悔の強いアルゴリズムも同様の指数関数的非効率に苦しむ。 これらの障壁を克服するために, Exp3 を Diminishing Historical rewards ( Exp3-DH と呼ぶ) で調整するアルゴリズムを開発した。 すべてのエージェントがExp3-DH(つまりマルチエージェント学習におけるセルフプレイ)を実行すると、反復的に支配されるアクションは多項式的に多くのラウンドで排除される。 我々の実験結果はExp3-DHの効率をさらに証明し、ゲームで学習するために開発された最先端のバンディットアルゴリズムでさえ、効果的に合理化できないことを示した。

関連論文リスト

• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Learning Rationalizable Equilibria in Multiplayer Games [38.922957434291554]
  既存のアルゴリズムでは、帯域幅フィードバックの下で合理化可能な平衡を学習するために、プレイヤー数で指数関数的に多くのサンプルを必要とする。 本稿では、合理化可能な粗相関平衡(CCE)と相関平衡(CE)を学習するための効率的なアルゴリズムの第一線を開発する。 本アルゴリズムは,合理化可能性を保証するための新しい手法と,相関探索スキームと適応学習率を含む(スワップ-)レグレットを同時に備えている。
  論文  参考訳（メタデータ） (2022-10-20T16:49:00Z)
• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。 本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。 本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。 第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
  論文  参考訳（メタデータ） (2022-09-15T21:32:23Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)

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

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