論文の概要: AlphaSnake: Policy Iteration on a Nondeterministic NP-hard Markov Decision Process

• arxiv url: http://arxiv.org/abs/2211.09622v1
• Date: Thu, 17 Nov 2022 16:15:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 16:11:17.881896
• Title: AlphaSnake: Policy Iteration on a Nondeterministic NP-hard Markov Decision Process
• Title（参考訳）: AlphaSnake:非決定論的NPハードマルコフ決定過程のポリシー反復
• Authors: Kevin Du, Ian Gemp, Yi Wu, Yingying Wu
• Abstract要約: ハミルトンサイクル問題は非常に解析が難しい。 本稿では,モンテカルロ木探索(MCTS)を用いて,スネークのゲームを学習する自律エージェントを作成する。
• 参考スコア（独自算出の注目度）: 8.43220675950501
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning has recently been used to approach well-known NP-hard combinatorial problems in graph theory. Among these problems, Hamiltonian cycle problems are exceptionally difficult to analyze, even when restricted to individual instances of structurally complex graphs. In this paper, we use Monte Carlo Tree Search (MCTS), the search algorithm behind many state-of-the-art reinforcement learning algorithms such as AlphaZero, to create autonomous agents that learn to play the game of Snake, a game centered on properties of Hamiltonian cycles on grid graphs. The game of Snake can be formulated as a single-player discounted Markov Decision Process (MDP) where the agent must behave optimally in a stochastic environment. Determining the optimal policy for Snake, defined as the policy that maximizes the probability of winning - or win rate - with higher priority and minimizes the expected number of time steps to win with lower priority, is conjectured to be NP-hard. Performance-wise, compared to prior work in the Snake game, our algorithm is the first to achieve a win rate over $0.5$ (a uniform random policy achieves a win rate $< 2.57 \times 10^{-15}$), demonstrating the versatility of AlphaZero in approaching NP-hard environments.
• Abstract（参考訳）: 強化学習は、グラフ理論におけるよく知られたNPハード組合せ問題に近づいた。 これらの問題のうち、ハミルトンサイクル問題は、たとえ構造的に複雑なグラフの個々のインスタンスに制限されたとしても、非常に分析が難しい。 本稿では,AlphaZeroのような最先端の強化学習アルゴリズムの背後にある探索アルゴリズムであるMonte Carlo Tree Search (MCTS) を用いて,格子グラフ上のハミルトンサイクルの性質に着目したゲームであるSnakeのゲームを学習する自律エージェントを作成する。 スネークのゲームは、エージェントが確率的環境で最適に振る舞う必要があるマルコフ決定過程 (MDP) として定式化することができる。 スネークの最適政策の決定は、高い優先度で勝利の確率を最大化し、より低い優先度で勝つ予定の時間ステップ数を最小化する政策として定義され、np-hardであると推測される。 性能面では、Snakeゲームにおける先行研究と比較して、我々のアルゴリズムは0.5ドルを超える勝利率を達成した最初のアルゴリズムである(一様ランダムポリシーは勝利率$<2.57 \times 10^{-15}$を達成し、NPハード環境に近づく際のAlphaZeroの汎用性を実証する)。

関連論文リスト

• Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning [0.0]
  政策アルゴリズムの収束率に関する新しい結果を示す。 このアルゴリズムは、$tildeO(SAK3log3frac1delta)$ sampled episodesの後に最適なポリシーを返す。
  論文  参考訳（メタデータ） (2024-10-03T21:11:29Z)
• Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games [18.11805544026393]
  本研究はマルコフポテンシャルゲームにおけるマルチエージェント強化学習問題に対する独立自然ポリシー勾配(NPG)アルゴリズムについて研究する。 技術的に微妙な仮定では、正確なポリシーを提供するオラクルを持つ独立したNPG法は、$mathcalO(1/epsilon)$イテレーション内で$epsilon$-Nash Equilibrium (NE)に達することが示されている。
  論文  参考訳（メタデータ） (2023-10-15T04:10:44Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
  状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。 我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。 我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
  論文  参考訳（メタデータ） (2022-02-08T20:09:47Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

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

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