論文の概要: Extreme Value Monte Carlo Tree Search

• arxiv url: http://arxiv.org/abs/2405.18248v1
• Date: Tue, 28 May 2024 14:58:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 18:09:42.673704
• Title: Extreme Value Monte Carlo Tree Search
• Title（参考訳）: 極値モンテカルロ木探索
• Authors: Masataro Asai, Stephen Wissow,
• Abstract要約: UCB1 Multi-Armed Bandit (MAB)はドメインに依存しない計画において最近まで限られた成功を収めてきた。 UCB1-Uniform/Power という2つのバンドレットを提案し,それをモンテカルロ木探索 (MCTS) に適用して古典的計画を行う。
• 参考スコア（独自算出の注目度）: 1.6574413179773757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite being successful in board games and reinforcement learning (RL), UCT, a Monte-Carlo Tree Search (MCTS) combined with UCB1 Multi-Armed Bandit (MAB), has had limited success in domain-independent planning until recently. Previous work showed that UCB1, designed for $[0,1]$-bounded rewards, is not appropriate for estimating the distance-to-go which are potentially unbounded in $\mathbb{R}$, such as heuristic functions used in classical planning, then proposed combining MCTS with MABs designed for Gaussian reward distributions and successfully improved the performance. In this paper, we further sharpen our understanding of ideal bandits for planning tasks. Existing work has two issues: First, while Gaussian MABs no longer over-specify the distances as $h\in [0,1]$, they under-specify them as $h\in [-\infty,\infty]$ while they are non-negative and can be further bounded in some cases. Second, there is no theoretical justifications for Full-Bellman backup (Schulte & Keller, 2014) that backpropagates minimum/maximum of samples. We identified \emph{extreme value} statistics as a theoretical framework that resolves both issues at once and propose two bandits, UCB1-Uniform/Power, and apply them to MCTS for classical planning. We formally prove their regret bounds and empirically demonstrate their performance in classical planning.
• Abstract（参考訳）: ボードゲームや強化学習(RL)で成功を収めたにもかかわらず、UCT(Monte-Carlo Tree Search)とUCB1 Multi-Armed Bandit(MAB)を組み合わせたMCTS(Monte-Carlo Tree Search)は、最近までドメインに依存しない計画において限られた成功を収めてきた。 以前の研究では、UCB1は$[0,1]$-bounded rewardsのために設計されており、古典的な計画で用いられるヒューリスティック関数のような$\mathbb{R}$で非バウンドの可能性のある距離を推定するには適切でないことが示され、その後、ガウスの報酬分布用に設計されたMABとMCTSを組み合わせることを提案し、性能の改善に成功した。 本稿では,計画課題に対する理想的な帯域幅の理解をさらに深めている。 既存の作業には2つの問題がある: まず、ガウスMABはもはや$h\in [0,1]$として距離を過剰に指定しないが、それらが非負であり、さらに有界である場合もあるが、これらを$h\in [-\infty,\infty]$として定義する。 第二に、Full-Bellmanバックアップ(Schulte & Keller, 2014)は最小/最大サンプルをバックプロパゲートする理論上の正当化はない。 我々は,両問題を同時に解決する理論的枠組みとして \emph{extreme value} の統計を同定し,UCB1-Uniform/Power という2つの帯域を提案し,それらをMCTS に適用した。 私たちは彼らの後悔の限界を正式に証明し、古典的な計画においてそのパフォーマンスを実証的に実証します。

関連論文リスト

• Combinatorial Logistic Bandits [30.829239785016934]
  我々はロジスティック・バンディット(CLogB)と呼ばれる新しいフレームワークを紹介する。 各ラウンドでは、ベースアームのサブセット(スーパーアームと呼ばれる)が選択され、各ベースアームの結果はバイナリとなる。 実世界のデータセットの実験では、ベンチマークアルゴリズムと比較してアルゴリズムの性能が優れていた。
  論文  参考訳（メタデータ） (2024-10-22T14:52:46Z)
• Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning [1.6574413179773757]
  我々は,MAB文献のより詳細な理論的理解が,既存の計画アルゴリズムの改善に役立つことを示す。 本稿では, UCB1-Normal bandit を用いた MCTS/THTS アルゴリズムである GreedyUCT-Normal を提案する。
  論文  参考訳（メタデータ） (2023-05-16T22:46:37Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。 我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-29T02:02:40Z)

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

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