論文の概要: The Update Equivalence Framework for Decision-Time Planning
- arxiv url: http://arxiv.org/abs/2304.13138v1
- Date: Tue, 25 Apr 2023 20:28:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-27 16:35:02.842316
- 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要約: 公的な情報に依存しない,原則的意思決定計画アルゴリズムを新たに導入する。
実験では、このファミリーのメンバーは、ハナビの最先端のアプローチと比較して、同等または優れた結果を生み出す。
- 参考スコア（独自算出の注目度）: 95.09506009344315
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The process of revising (or constructing) a policy immediately prior to
execution -- known as decision-time planning -- is key to achieving superhuman
performance in perfect-information settings like chess and Go. A recent line of
work has extended decision-time planning to more general imperfect-information
settings, leading to superhuman performance in poker. However, these methods
requires considering 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 subgames but rather
on the notion of update equivalence. In this framework, decision-time planning
algorithms simulate updates of synchronous learning algorithms. This framework
enables us to introduce a new family of principled decision-time planning
algorithms that do not rely on public information, opening the door to sound
and effective decision-time planning in settings with large amounts of
non-public information. In experiments, members of this family produce
comparable or superior results compared to state-of-the-art approaches in
Hanabi and improve performance in 3x3 Abrupt Dark Hex and Phantom Tic-Tac-Toe.
- Abstract（参考訳）: 実行直前にポリシーを修正(あるいは構築)するプロセス – 決定時間計画(decisive-time planning)と呼ばれる – は、チェスやゴーといった完璧な情報設定で超人的なパフォーマンスを達成する上でキーとなる。
最近の作業では、意思決定時間の計画をより一般的な不完全な情報設定に拡張し、ポーカーにおける超人的なパフォーマンスに繋がった。
しかし,これらの手法では,非公開情報の量が多い場合には,そのサイズが急速に大きくなるサブゲームを考える必要がある。
本稿では,サブゲームではなく,更新等価性の概念に基づく,意思決定時計画のための代替フレームワークを提案する。
このフレームワークでは、決定時間計画アルゴリズムが同期学習アルゴリズムの更新をシミュレートする。
この枠組みにより,公的な情報に依存しない意思決定時間計画手法を新たに導入し,非公的な情報量の多い設定において,健全かつ効果的な意思決定計画への扉を開くことができる。
実験では、このファミリーのメンバーは、ハナビの最先端のアプローチと同等または優れた結果を生成し、3x3のAbrupt Dark HexとPhantom Tic-Tac-Toeのパフォーマンスを改善した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。