論文の概要: Impartial Games: A Challenge for Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2205.12787v1
• Date: Wed, 25 May 2022 14:02:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-26 19:26:58.541262
• Title: Impartial Games: A Challenge for Reinforcement Learning
• Title（参考訳）: Impartial Games:強化学習への挑戦
• Authors: Bei Zhou and S{\o}ren Riis
• Abstract要約: ゲームの最初の具体例、すなわちニムの(子供)ゲームを示す。 ボトルネックがポリシとバリューネットワークの両方に適用できることを実験的に示す。 小さなボード上では nim が学習可能であることを示すが、ボードのサイズが大きくなると、AlphaZero スタイルのアルゴリズムは急速に改善されなくなる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The AlphaZero algorithm and its successor MuZero have revolutionised several competitive strategy games, including chess, Go, and shogi and video games like Atari, by learning to play these games better than any human and any specialised computer program. Aside from knowing the rules, AlphaZero had no prior knowledge of each game. This dramatically advanced progress on a long-standing AI challenge to create programs that can learn for themselves from first principles. Theoretically, there are well-known limits to the power of deep learning for strategy games like chess, Go, and shogi, as they are known to be NEXPTIME hard. Some papers have argued that the AlphaZero methodology has limitations and is unsuitable for general AI. However, none of these works has suggested any specific limits for any particular game. In this paper, we provide more powerful bottlenecks than previously suggested. We present the first concrete example of a game - namely the (children) game of nim - and other impartial games that seem to be a stumbling block for AlphaZero and similar reinforcement learning algorithms. We show experimentally that the bottlenecks apply to both the policy and value networks. Since solving nim can be done in linear time using logarithmic space i.e. has very low-complexity, our experimental results supersede known theoretical limits based on many games' PSPACE (and NEXPTIME) completeness. We show that nim can be learned on small boards, but when the board size increases, AlphaZero style algorithms rapidly fail to improve. We quantify the difficulties for various setups, parameter settings and computational resources. Our results might help expand the AlphaZero self-play paradigm by allowing it to use meta-actions during training and/or actual game play like applying abstract transformations, or reading and writing to an external memory.
• Abstract（参考訳）: AlphaZeroアルゴリズムとその後継であるMuZeroは、チェスや囲碁、アタリのようなビデオゲームなどの競争戦略ゲームに革命をもたらした。 ルールを知る以外に、AlphaZeroは各ゲームについて事前の知識を持っていなかった。 これは、第一原理から学べるプログラムを作成するための、長年にわたるAIチャレンジにおいて、劇的に進歩した。 理論的には、NEXPTIMEの難易度が知られているため、チェス、囲碁、小木などの戦略ゲームにおける深層学習の能力には限界がある。 一部の論文は、AlphaZeroの方法論には限界があり、一般的なAIには適さないと主張している。 しかし、これらの作品のどれも特定のゲームに対する特定の制限を示唆していない。 本稿では,提案するよりも強力なボトルネックを提供する。 我々は,AlphaZeroと類似の強化学習アルゴリズムの難解なブロックであると思われるゲーム,すなわちニムの(子供)ゲームとその他の公平なゲームの最初の具体例を示す。 ポリシネットワークとバリューネットワークの両方にボトルネックが適用可能であることを実験的に示す。 nmの解法は、対数空間を用いて線形時間で行うことができるため、実験結果は、多くのゲームのPSPACE(およびNEXPTIME)完全性に基づいて、既知の理論的限界に取って代わる。 nimは小さなボードで学習できるが、ボードサイズが大きくなるとalphazeroスタイルのアルゴリズムは急速に改善されない。 様々な設定、パラメータ設定、計算資源の難しさを定量化する。 我々の結果は、AlphaZeroの自己プレイパラダイムを拡張し、トレーニング中や、抽象的な変換の適用や、外部メモリへの読み書きといった実際のゲームプレイでメタアクションを使用できるようにするのに役立つかもしれない。

関連論文リスト

• In-Context Exploiter for Extensive-Form Games [38.24471816329584]
  In-Context Exploiter (ICE) という新しい手法を導入し、ゲーム内の任意のプレイヤーとして動作し、コンテキスト内学習によって完全に対戦相手を適応的に活用できる単一モデルを訓練する。 我々のICEアルゴリズムは、多様な相手戦略の生成、強化学習アルゴリズムによる対話的履歴データの収集、そしてよく設計されたカリキュラム学習フレームワークにおけるトランスフォーマーベースのエージェントの訓練を含む。
  論文  参考訳（メタデータ） (2024-08-10T14:59:09Z)
• State-Constrained Zero-Sum Differential Games with One-Sided Information [19.964883571758502]
  状態制約と一方的な情報を持つゼロサム差分ゲームについて検討する。 我々の貢献は、状態制約のあるゲームの拡張であり、行動戦略の計算に必要な原始的および双対的準力学原理の導出である。
  論文  参考訳（メタデータ） (2024-03-05T07:51:38Z)
• Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability [2.2636685010313364]
  セルフプレイ(Self-play)は、学習アルゴリズムが自分自身のコピーと対話して学習するマルチエージェントシステムにおける機械学習のテクニックである。 両プレイヤーの定数ゲームでは、ナッシュ均衡に達するセルフプレイが保証され、ポストトレーニング中の対戦相手に対して良好に機能する戦略が作成できることを示す。 本研究は,マルチプレイヤーゲームの構造的特性を初めて同定し,多種多様なセルフプレイアルゴリズムによって生成される戦略の性能保証を実現する。
  論文  参考訳（メタデータ） (2023-10-17T18:33:21Z)
• 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)
• Online Learning in Unknown Markov Games [55.07327246187741]
  未知のマルコフゲームでオンライン学習を学ぶ。 後方視における最良の反応に対するサブ線形後悔の達成は統計的に困難であることを示す。 サブ線形$tildemathcalO(K2/3)$ regretを$K$のエピソード後に達成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-28T14:52:15Z)
• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games [30.520629802135574]
  本稿では,自己再生強化学習と探索のためのフレームワークであるReBeLを,ゼロサムゲームにおけるナッシュ均衡に確実に収束させる。 また、ReBeLは、従来のポーカーAIよりもはるかに少ないドメイン知識を使用しながら、制限なしのテキサスホールド'emポーカーのパフォーマンスを達成することを示す。
  論文  参考訳（メタデータ） (2020-07-27T15:21:22Z)
• 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)
• Smooth markets: A basic mechanism for organizing gradient-based learners [47.34060971879986]
  スムーズマーケット(SM-games)は、対角にゼロ和の相互作用を持つn-プレイヤゲームの一種である。 SMゲームは、(一部)GAN、敵対的トレーニング、その他の最近のアルゴリズムを含む、機械学習における一般的なデザインパターンを符号化する。 SMゲームは1次手法を用いて解析と最適化が可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-14T09:19:39Z)

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

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