論文の概要: B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming
Approach to Solving POMDPs
- arxiv url: http://arxiv.org/abs/2210.12556v1
- Date: Sat, 22 Oct 2022 21:42:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 17:01:00.314520
- Title: B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming
Approach to Solving POMDPs
- Title（参考訳）: b$^3$rtdp:pomdpに対する信念分岐と境界付きリアルタイム動的プログラミングアプローチ
- Authors: Sigurdur Orn Adalgeirsson, Cynthia Breazeal
- Abstract要約: 我々は,Belief Branch and Bound RTDP (B$3$RTDP) と呼ぶRTDP-Belアルゴリズムの拡張を提案する。
我々のアルゴリズムは有界値関数表現を使い、これを2つの新しい方法で活用する。
B$3$RTDPは、既知のPOMDP問題に対する最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に実証した。
- 参考スコア（独自算出の注目度）: 17.956744635160568
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partially Observable Markov Decision Processes (POMDPs) offer a promising
world representation for autonomous agents, as they can model both transitional
and perceptual uncertainties. Calculating the optimal solution to POMDP
problems can be computationally expensive as they require reasoning over the
(possibly infinite) space of beliefs. Several approaches have been proposed to
overcome this difficulty, such as discretizing the belief space, point-based
belief sampling, and Monte Carlo tree search. The Real-Time Dynamic Programming
approach of the RTDP-Bel algorithm approximates the value function by storing
it in a hashtable with discretized belief keys. We propose an extension to the
RTDP-Bel algorithm which we call Belief Branch and Bound RTDP (B$^3$RTDP). Our
algorithm uses a bounded value function representation and takes advantage of
this in two novel ways: a search-bounding technique based on action selection
convergence probabilities, and a method for leveraging early action convergence
called the \textit{Convergence Frontier}. Lastly, we empirically demonstrate
that B$^3$RTDP can achieve greater returns in less time than the
state-of-the-art SARSOP solver on known POMDP problems.
- Abstract（参考訳）: 部分的に観察可能なマルコフ決定プロセス(POMDP)は、過渡的および知覚的不確実性の両方をモデル化できるため、自律的なエージェントに将来的な世界表現を提供する。
POMDP問題に対する最適解を計算することは、(おそらく無限の)信念空間の推論を必要とするため、計算的にコストがかかる。
信念空間の離散化、点に基づく信念サンプリング、モンテカルロ木探索など、この困難を克服するためのいくつかのアプローチが提案されている。
RTDP-Belアルゴリズムのリアルタイム動的プログラミング手法は、識別された信念キーを持つハッシュテーブルに格納することで、値関数を近似する。
本稿では,Belief Branch と Bound RTDP (B$^3$RTDP) と呼ばれるRTDP-Belアルゴリズムの拡張を提案する。
提案手法は有界値関数表現を用い,2つの新しい手法でこれを利用する:行動選択収束確率に基づく探索境界法と, \textit{convergence frontier} と呼ばれる早期行動収束を利用する方法である。
最後に、B$^3$RTDPは、既知のPOMDP問題における最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に示す。
関連論文リスト
- 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) - Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。
割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。
本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-05T02:33:50Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳（メタデータ） (2023-10-03T04:40:38Z) - Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation [10.159501412046508]
マルコフ決定過程(MDP)におけるモデルベース強化学習(RL)について検討する。
我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。
我々の知る限りでは、証明可能な保証付き多項ロジスティック関数近似を用いたモデルベースRLアルゴリズムとしてはこれが初めてである。
論文 参考訳（メタデータ） (2022-12-27T16:25:09Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-01-21T16:43:03Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。