論文の概要: Power Mean Estimation in Stochastic Monte-Carlo Tree_Search

• arxiv url: http://arxiv.org/abs/2406.02235v1
• Date: Tue, 4 Jun 2024 11:56:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-05 16:32:17.872677
• Title: Power Mean Estimation in Stochastic Monte-Carlo Tree_Search
• Title（参考訳）: 確率的モンテカルロ木探索におけるパワー平均推定
• Authors: Tuan Dam, Odalric-Ambrym Maillard, Emilie Kaufmann,
• Abstract要約: Monte-Carlo Tree Search (MCTS)は、Monte-Carloサンプリングとフォワードツリー検索を組み合わせたオンラインプランニングのための広く使われている戦略である。 UCTの理論的基礎は対数的ボーナス項の誤りにより不完全である。 本稿では,MDPに適したパワー平均推定器を用いたアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 25.058008522872747
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte-Carlo Tree Search (MCTS) is a widely-used strategy for online planning that combines Monte-Carlo sampling with forward tree search. Its success relies on the Upper Confidence bound for Trees (UCT) algorithm, an extension of the UCB method for multi-arm bandits. However, the theoretical foundation of UCT is incomplete due to an error in the logarithmic bonus term for action selection, leading to the development of Fixed-Depth-MCTS with a polynomial exploration bonus to balance exploration and exploitation~\citep{shah2022journal}. Both UCT and Fixed-Depth-MCTS suffer from biased value estimation: the weighted sum underestimates the optimal value, while the maximum valuation overestimates it~\citep{coulom2006efficient}. The power mean estimator offers a balanced solution, lying between the average and maximum values. Power-UCT~\citep{dam2019generalized} incorporates this estimator for more accurate value estimates but its theoretical analysis remains incomplete. This paper introduces Stochastic-Power-UCT, an MCTS algorithm using the power mean estimator and tailored for stochastic MDPs. We analyze its polynomial convergence in estimating root node values and show that it shares the same convergence rate of $\mathcal{O}(n^{-1/2})$, with $n$ is the number of visited trajectories, as Fixed-Depth-MCTS, with the latter being a special case of the former. Our theoretical results are validated with empirical tests across various stochastic MDP environments.
• Abstract（参考訳）: Monte-Carlo Tree Search (MCTS)は、Monte-Carloサンプリングとフォワードツリー検索を組み合わせたオンラインプランニングのための広く使われている戦略である。 その成功は、マルチアームバンディットのための UCB 法の拡張である Up Confidence bound for Trees (UCT) アルゴリズムに依存している。 しかし、UCTの理論的基礎は対数的ボーナス項の動作選択の誤りにより不完全であり、探索と利用のバランスをとるための多項式探索ボーナスを持つ固定深度MCTSの開発に繋がる。 UCT と Fixed-Depth-MCTS はいずれもバイアス値の推定に苦しむ:重み付き和は最適値を過小評価し、最大値はそれ~\citep{coulom 2006efficient} を過小評価する。 パワー平均推定器は平均値と最大値の間にバランスのとれた解を提供する。 Power-UCT~\citep{dam2019 generalized} はより正確な値推定のためにこの推定器を組み込むが、理論解析はいまだ不完全である。 本稿では,パワー平均推定器を用いたMCTSアルゴリズムであるStochastic-Power-UCTについて述べる。 我々は、根ノード値の推定における多項式収束を解析し、$\mathcal{O}(n^{-1/2})$と同じ収束率と、$n$が訪問軌跡の数であり、Fixed-Depth-MCTSのように、後者が前者の特別な場合であることを示す。 本研究の理論的結果は,様々な確率的MDP環境における実証実験により検証された。

関連論文リスト

• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。 我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
  論文  参考訳（メタデータ） (2024-04-19T06:24:22Z)
• Leveraging Nested MLMC for Sequential Neural Posterior Estimation with Intractable Likelihoods [0.8287206589886881]
  SNPE法は,難解な確率でシミュレーションベースモデルを扱うために提案される。 本稿では,ネスト予測を推定するためのネスト推定APT手法を提案する。 損失関数と勾配のネスト推定器は偏りがあるため,不偏のマルチレベルモンテカルロ推定器(MLMC)を用いる。
  論文  参考訳（メタデータ） (2024-01-30T06:29:41Z)
• Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients [0.8749675983608172]
  動力学的ランゲヴィンダイナミクスに基づく後進手段の非バイアス化手法を提案する。 提案した推定器は偏りがなく、有限分散となり、中心極限定理を満たす。 以上の結果から、大規模アプリケーションでは、非バイアスアルゴリズムは「ゴールドスタンダード」なハミルトニアン・モンテカルロよりも2～3桁効率が良いことが示された。
  論文  参考訳（メタデータ） (2023-11-08T21:19:52Z)
• Monte-Carlo tree search with uncertainty propagation via optimal transport [27.931569422467835]
  本稿ではモンテカルロ木探索(MCTS)のための新しいバックアップ戦略を紹介する。 我々は確率的アプローチを採用し、値ノードとアクション値ノードの両方をガウス分布としてモデル化する。 最適政策への収束の理論的保証と、いくつかの観測可能な環境における経験的評価を提供する。
  論文  参考訳（メタデータ） (2023-09-19T16:32:04Z)
• Truncating Trajectories in Monte Carlo Reinforcement Learning [48.97155920826079]
  強化学習(RL)において、エージェントは未知の環境で動作し、外部報酬信号の期待累積割引和を最大化する。 我々は,異なる長さの軌跡の収集につながるアプリオリ予算配分戦略を提案する。 軌道の適切な切り離しが性能向上に成功することを示す。
  論文  参考訳（メタデータ） (2023-05-07T19:41:57Z)
• 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)
• Exponential Family Model-Based Reinforcement Learning via Score Matching [97.31477125728844]
  有限水平表層強化学習(RL)のための楽観的モデルベースアルゴリズムSMRLを提案する。 SMRLは、リッジ回帰によるモデルパラメータの効率的な推定を可能にする非正規化密度推定手法であるスコアマッチングを用いる。
  論文  参考訳（メタデータ） (2021-12-28T15:51:07Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。 本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。 提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
  論文  参考訳（メタデータ） (2020-10-24T10:44:02Z)

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

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