論文の概要: No Compromise in Solution Quality: Speeding Up Belief-dependent
Continuous POMDPs via Adaptive Multilevel Simplification
- arxiv url: http://arxiv.org/abs/2310.10274v1
- Date: Mon, 16 Oct 2023 10:59:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-17 15:08:13.626033
- Title: No Compromise in Solution Quality: Speeding Up Belief-dependent
Continuous POMDPs via Adaptive Multilevel Simplification
- Title（参考訳）: no compromise in solution quality:adaptive multilevel simplificationによる信念依存型連続pomdpの高速化
- Authors: Andrey Zhitnikov, Ori Sztyglic, Vadim Indelman
- Abstract要約: 一般的な信念に依存した報酬を持つ継続的POMDPは、オンラインでの解決が難しいことで知られている。
与えられた外部構築された信条木の設定に対する適応的多レベル単純化の完全証明可能な理論を提案する。
我々は,信念に依存した報酬で,POMDPのオンラインプランニングを高速化する3つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 7.081396107231381
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Continuous POMDPs with general belief-dependent rewards are notoriously
difficult to solve online. In this paper, we present a complete provable theory
of adaptive multilevel simplification for the setting of a given externally
constructed belief tree and MCTS that constructs the belief tree on the fly
using an exploration technique. Our theory allows to accelerate POMDP planning
with belief-dependent rewards without any sacrifice in the quality of the
obtained solution. We rigorously prove each theoretical claim in the proposed
unified theory. Using the general theoretical results, we present three
algorithms to accelerate continuous POMDP online planning with belief-dependent
rewards. Our two algorithms, SITH-BSP and LAZY-SITH-BSP, can be utilized on top
of any method that constructs a belief tree externally. The third algorithm,
SITH-PFT, is an anytime MCTS method that permits to plug-in any exploration
technique. All our methods are guaranteed to return exactly the same optimal
action as their unsimplified equivalents. We replace the costly computation of
information-theoretic rewards with novel adaptive upper and lower bounds which
we derive in this paper, and are of independent interest. We show that they are
easy to calculate and can be tightened by the demand of our algorithms. Our
approach is general; namely, any bounds that monotonically converge to the
reward can be easily plugged-in to achieve significant speedup without any loss
in performance. Our theory and algorithms support the challenging setting of
continuous states, actions, and observations. The beliefs can be parametric or
general and represented by weighted particles. We demonstrate in simulation a
significant speedup in planning compared to baseline approaches with guaranteed
identical performance.
- Abstract（参考訳）: 一般的な信念に依存した報酬を持つ継続的POMDPは、オンラインで解決するのが非常に難しい。
本稿では,探索手法を用いてハエの信念木を構成する任意の外部構成の信念木とmctsの設定のための適応的多レベル単純化の完全証明可能な理論を提案する。
提案理論は,得られたソリューションの品質を犠牲にすることなく,信念に依存した報酬でpomdp計画を促進する。
提案する統一理論において,各理論の主張を厳密に証明する。
一般的な理論結果を用いて,連続pomdpオンラインプランニングを,信念に依存した報酬で高速化する3つのアルゴリズムを提案する。
我々の2つのアルゴリズムである SITH-BSP と LAZY-SITH-BSP は、外部に信仰木を構築する方法の上に利用することができる。
第3のアルゴリズムであるSITH-PFTは、任意の探査手法をプラグインできる任意のMCTS法である。
すべてのメソッドは、単純化されていない等価値と全く同じ最適なアクションを返すことが保証されます。
本稿では,情報理論的な報酬の費用対効果を,本論文で導出する新しい適応的上下界と下界に置き換える。
計算が簡単であり,アルゴリズムの要求に応じて厳格化できることが示される。
我々のアプローチは一般に、報酬に単調に収束する任意の境界は容易にプラグインでき、性能を損なうことなく大幅なスピードアップが達成できる。
我々の理論とアルゴリズムは、連続状態、行動、観察の困難な設定をサポートする。
信念はパラメトリックまたは一般であり、重み付き粒子で表される。
シミュレーションでは,同一性能が保証されたベースラインアプローチと比較して,計画の大幅な高速化を示す。
関連論文リスト
- Is Inverse Reinforcement Learning Harder than Standard Reinforcement
Learning? A Theoretical Perspective [55.36819597141271]
逆強化学習(IRL: Inverse Reinforcement Learning)は、インテリジェントシステム開発において重要な役割を担う。
本稿では、サンプルとランタイムを用いて、バニラのオフラインおよびオンライン設定における効率的なIRLの最初のラインを提供する。
応用として、学習した報酬は適切な保証で他のターゲットMDPに転送可能であることを示す。
論文 参考訳（メタデータ） (2023-11-29T00:09:01Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳（メタデータ） (2023-10-03T04:40:38Z) - Measurement Simplification in ρ-POMDP with Performance Guarantees [6.129902017281406]
不確実性の下での意思決定は、不完全な情報で行動する自律システムの中心にある。
本稿では,高次元観測空間を分割することで,効率的な意思決定手法を提案する。
境界は適応的で、計算効率が良く、元の解に収束していることが示される。
論文 参考訳（メタデータ） (2023-09-19T15:40:42Z) - B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming
Approach to Solving POMDPs [17.956744635160568]
我々は,Belief Branch and Bound RTDP (B$3$RTDP) と呼ぶRTDP-Belアルゴリズムの拡張を提案する。
我々のアルゴリズムは有界値関数表現を使い、これを2つの新しい方法で活用する。
B$3$RTDPは、既知のPOMDP問題に対する最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に実証した。
論文 参考訳（メタデータ） (2022-10-22T21:42:59Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - 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) - Sequential Information Design: Markov Persuasion Process and Its
Efficient Reinforcement Learning [156.5667417159582]
本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。
MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。
我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
論文 参考訳（メタデータ） (2022-02-22T05:41:43Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Simplified Belief-Dependent Reward MCTS Planning with Guaranteed Tree
Consistency [11.688030627514532]
部分的に観測可能なマルコフ決定プロセス(POMDP)は解決が難しいことで知られている。
ほとんどの最先端のオンライン問題解決者はモンテカルロ木探索(MCTS)のアイデアを活用している。
本稿では,情報理論的な報奨を考慮したMCTSアルゴリズムの新たな変種を提案する。
論文 参考訳（メタデータ） (2021-05-29T07:25:11Z) - Online POMDP Planning via Simplification [10.508187462682306]
信念依存報酬を考慮したPOMDP計画への新しいアプローチを開発しています。
我々のアプローチは、元の問題の最適解を見つけることは保証されているが、かなりのスピードアップがある。
これらの境界と単純化がサンプル数の減少に対応し,計算速度が大幅に向上するシミュレーション手法を検証した。
論文 参考訳（メタデータ） (2021-05-11T18:46:08Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳（メタデータ） (2020-06-15T21:36:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。