論文の概要: The Update-Equivalence Framework for Decision-Time Planning
- arxiv url: http://arxiv.org/abs/2304.13138v2
- Date: Sun, 17 Mar 2024 20:58:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 06:28:31.120621
- Title: The Update-Equivalence Framework for Decision-Time Planning
- Title（参考訳）: 決定時間計画のための更新等価フレームワーク
- Authors: Samuel Sokota, Gabriele Farina, David J. Wu, Hengyuan Hu, Kevin A. Wang, J. Zico Kolter, Noam Brown,
- Abstract要約: 本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。
ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
- 参考スコア（独自算出の注目度）: 78.44953498421854
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The process of revising (or constructing) a policy at execution time -- known as decision-time planning -- has been key to achieving superhuman performance in perfect-information games like chess and Go. A recent line of work has extended decision-time planning to imperfect-information games, leading to superhuman performance in poker. However, these methods involve solving subgames whose sizes grow quickly in the amount of non-public information, making them unhelpful when the amount of non-public information is large. Motivated by this issue, we introduce an alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. In this update-equivalence framework, decision-time planning algorithms replicate the updates of last-iterate algorithms, which need not rely on public information. This facilitates scalability to games with large amounts of non-public information. Using this framework, we derive a provably sound search algorithm for fully cooperative games based on mirror descent and a search algorithm for adversarial games based on magnetic mirror descent. We validate the performance of these algorithms in cooperative and adversarial domains, notably in Hanabi, the standard benchmark for search in fully cooperative imperfect-information games. Here, our mirror descent approach exceeds or matches the performance of public information-based search while using two orders of magnitude less search time. This is the first instance of a non-public-information-based algorithm outperforming public-information-based approaches in a domain they have historically dominated.
- Abstract（参考訳）: チェスや囲碁といった完全情報ゲームにおいて、実行時にポリシーを改訂(あるいは構築)するプロセスは、超人的なパフォーマンスを達成するための鍵となった。
最近の研究は、不完全な情報ゲームに対する意思決定時間を延長し、ポーカーにおける超人的なパフォーマンスにつながった。
しかし,これらの手法は,非公開情報の量が多い場合,そのサイズが急速に大きくなるサブゲームの解決に関係している。
この問題に触発されて、サブゲームの解決ではなく、更新等価性に基づく意思決定時計画のための代替フレームワークを導入する。
この更新等価フレームワークでは、決定時計画アルゴリズムは、公開情報に頼る必要のない最終段階のアルゴリズムの更新を複製する。
これにより、大量の非公開情報を持つゲームへのスケーラビリティが向上する。
この枠組みを用いて,ミラー降下に基づく完全協調型ゲームに対する検証可能な音声探索アルゴリズムと,磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
完全協調不完全情報ゲームにおける検索の標準ベンチマークであるハナビにおいて,これらのアルゴリズムの性能を協調的・敵対的領域で検証する。
ここでは, ミラー降下法は, 検索時間を大幅に短縮しながら, 公開情報に基づく検索性能を上回り, 一致させる。
これは、歴史的に支配されてきた領域において、公開情報に基づくアルゴリズムが公開情報に基づくアプローチを上回った最初の例である。
関連論文リスト
- Increasing the Value of Information During Planning in Uncertain Environments [0.0]
我々は,情報収集行動の価値をよりよく反映して,最先端のオンライン計画を改善する新しいアルゴリズムを開発した。
結果,新しいアルゴリズムはPOMCPよりも高い性能を示した。
論文 参考訳（メタデータ） (2024-09-14T22:04:34Z) - Playing Board Games with the Predict Results of Beam Search Algorithm [0.0]
本稿では,PROBS(Predict Results of Beam Search)と呼ぶ完全情報を持つ2プレイヤー決定型ゲームのための新しいアルゴリズムを提案する。
提案手法は,ベースライン対戦相手に対する勝利率の増大を連続的に示すボードゲームの中から,アルゴリズムの性能を評価する。
この研究の重要な結果は、ビーム探索サイズがゲームの平均ターン数よりもかなり小さい場合でも、PROBSアルゴリズムが効果的に動作することである。
論文 参考訳（メタデータ） (2024-04-23T20:10:27Z) - History Filtering in Imperfect Information Games: Algorithms and
Complexity [16.23892847804002]
本稿では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。
サブゲームのルートから単一の履歴を構築することは、一般的には難解であることを示す。
また,トリックテイクカードゲームのためのマルコフチェインモンテカルロベース生成アルゴリズムについても紹介する。
論文 参考訳（メタデータ） (2023-11-24T18:34:36Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Revisiting Game Representations: The Hidden Costs of Efficiency in
Sequential Decision-making Algorithms [0.6749750044497732]
不完全な情報の下でのシーケンシャルな意思決定アルゴリズムの進歩は、大きなゲームで顕著な成功を収めている。
これらのアルゴリズムは伝統的に広義のゲーム形式を用いてゲームを形式化する。
プレイヤー固有の情報状態木に基づく特殊表現の使用が,一般的な回避策であることを示す。
論文 参考訳（メタデータ） (2021-12-20T22:34:19Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-21T17:51:57Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。