論文の概要: Solving Stochastic Orienteering Problems with Chance Constraints Using a GNN Powered Monte Carlo Tree Search

• arxiv url: http://arxiv.org/abs/2409.04653v1
• Date: Fri, 6 Sep 2024 23:31:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-10 21:14:48.321396
• Title: Solving Stochastic Orienteering Problems with Chance Constraints Using a GNN Powered Monte Carlo Tree Search
• Title（参考訳）: GNNを用いたモンテカルロ木探索による環境制約による確率的オリエンテーリング問題の解法
• Authors: Marcos Abel Zuzuárregui, Stefano Carpin,
• Abstract要約: 本稿では,モンテカルロ木探索法(MCTS)を提案する。 割り当てられた旅行予算を順守しながら、アルゴリズムは、旅行コストを発生させながら収集された報酬を最大化する。 トレーニングデータセットの特性を超えて、このアプローチがいかに一般化できるかを実証する。
• 参考スコア（独自算出の注目度）: 3.3088495893219885
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Leveraging the power of a graph neural network (GNN) with message passing, we present a Monte Carlo Tree Search (MCTS) method to solve stochastic orienteering problems with chance constraints. While adhering to an assigned travel budget the algorithm seeks to maximize collected reward while incurring stochastic travel costs. In this context, the acceptable probability of exceeding the assigned budget is expressed as a chance constraint. Our MCTS solution is an online and anytime algorithm alternating planning and execution that determines the next vertex to visit by continuously monitoring the remaining travel budget. The novelty of our work is that the rollout phase in the MCTS framework is implemented using a message passing GNN, predicting both the utility and failure probability of each available action. This allows to enormously expedite the search process. Our experimental evaluation shows that with the proposed method and architecture we manage to efficiently solve complex problem instances while incurring in moderate losses in terms of collected reward. Moreover, we demonstrate how the approach is capable of generalizing beyond the characteristics of the training dataset. The paper's website, open-source code, and supplementary documentation can be found at ucmercedrobotics.github.io/gnn-sop.
• Abstract（参考訳）: メッセージパッシングによるグラフニューラルネットワーク(GNN)のパワーを活用したモンテカルロ木探索(MCTS)手法を提案する。 割り当てられた旅行予算を順守しながら、アルゴリズムは確率的な旅行コストを発生させながら収集された報酬を最大化する。 この文脈では、割り当てられた予算を超える許容確率をチャンス制約として表す。 我々のMCTSソリューションは、計画と実行を交互に変更するオンラインかついつでも利用できるアルゴリズムであり、残りの旅行予算を継続的に監視することで、訪問すべき次の頂点を決定する。 我々の研究の新規性は、MCTSフレームワークのロールアウトフェーズがメッセージパッシングGNNを使用して実装され、利用可能な各アクションの実用性と失敗の確率を予測することである。 これにより、検索プロセスが大幅に高速化される。 実験により,提案手法とアーキテクチャを用いることで,複雑な問題を効率よく解きながら,回収した報酬の点からある程度の損失を被ることができた。 さらに,本手法がトレーニングデータセットの特性を超えて一般化可能であることを示す。 論文のWebサイト、オープンソースコード、補足的なドキュメントはucmercedrobotics.github.io/gnn-sopで見ることができる。

関連論文リスト

• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  モンテカルロシミュレーションによる政策評価は多くのMC強化学習(RL)アルゴリズムの中核にある。 本研究では,異なる長さの軌跡を用いた回帰推定器の平均二乗誤差のサロゲートとして品質指標を提案する。 本稿では,Robust and Iterative Data Collection Strategy Optimization (RIDO) という適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-17T11:47:56Z)
• Learning to Explore for Stochastic Gradient MCMC [15.286308920219446]
  マルチモーダルなターゲット分布を効率的に探索できるglssgmcmcを構築するメタラーニング戦略を提案する。 我々のアルゴリズムは、学習したSGMCMCが後部景観の高密度領域を迅速に探索することを可能にする。
  論文  参考訳（メタデータ） (2024-08-17T08:36:42Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。 我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。 本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T15:29:32Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。 代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。 提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:11:28Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Distributed Stochastic Bandit Learning with Context Distributions [0.0]
  本研究では,未知のコンテキストを持つ分散マルチアームコンテキスト帯域幅の問題について検討する。 本モデルでは, エージェントはコンテキスト分布のみを観察し, エージェントに正確なコンテキストが不明である。 我々のゴールは、累積報酬を最大化するために最適な行動列を選択する分散アルゴリズムを開発することである。
  論文  参考訳（メタデータ） (2022-07-28T22:00:11Z)
• Solving the optimal stopping problem with reinforcement learning: an application in financial option exercise [0.0]
  我々はモンテカルロシミュレーションを用いて、人工ニューラルネットワークのトレーニングとテストを行うデータ駆動方式を採用している。 我々は、畳み込みニューラルネットワーク(CNN)を用いて価格の歴史全体をマルコフ状態に変換する際に生じる次元問題に対処する別のアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2022-07-21T22:52:05Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。 関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。 我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
  論文  参考訳（メタデータ） (2021-10-19T07:26:33Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  本研究では,不確かさを意識した分類器が,強化学習の難しさを解消できることを示す。 正規化最大度(NML)分布の計算法を提案する。 得られたアルゴリズムは、カウントベースの探索法と、報酬関数を学習するための先行アルゴリズムの両方に多くの興味深い関係を持つことを示す。
  論文  参考訳（メタデータ） (2021-07-15T08:19:57Z)
• An Efficient Algorithm for Deep Stochastic Contextual Bandits [10.298368632706817]
  コンテキスト境界の問題では、エージェントは特定の観察されたコンテキストに基づいてアクションを選択し、反復よりも報酬を最大化します。 近年、ディープニューラルネットワーク(DNN)を用いて行動に対する期待される報酬を予測する研究がいくつか行われ、勾配に基づく手法で訓練されている。
  論文  参考訳（メタデータ） (2021-04-12T16:34:43Z)

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

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