論文の概要: Online POMDP Planning with Anytime Deterministic Guarantees

• arxiv url: http://arxiv.org/abs/2310.01791v2
• Date: Wed, 4 Oct 2023 19:51:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-06 11:00:23.698511
• Title: Online POMDP Planning with Anytime Deterministic Guarantees
• Title（参考訳）: 常時決定論的保証によるオンラインpomdp計画
• Authors: Moran Barenboim and Vadim Indelman
• Abstract要約: 不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。 簡便な解と理論的に最適な解との決定論的関係を導出する。
• 参考スコア（独自算出の注目度）: 11.157761902108692
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Autonomous agents operating in real-world scenarios frequently encounter uncertainty and make decisions based on incomplete information. Planning under uncertainty can be mathematically formalized using partially observable Markov decision processes (POMDPs). However, finding an optimal plan for POMDPs can be computationally expensive and is feasible only for small tasks. In recent years, approximate algorithms, such as tree search and sample-based methodologies, have emerged as state-of-the-art POMDP solvers for larger problems. Despite their effectiveness, these algorithms offer only probabilistic and often asymptotic guarantees toward the optimal solution due to their dependence on sampling. To address these limitations, we derive a deterministic relationship between a simplified solution that is easier to obtain and the theoretically optimal one. First, we derive bounds for selecting a subset of the observations to branch from while computing a complete belief at each posterior node. Then, since a complete belief update may be computationally demanding, we extend the bounds to support reduction of both the state and the observation spaces. We demonstrate how our guarantees can be integrated with existing state-of-the-art solvers that sample a subset of states and observations. As a result, the returned solution holds deterministic bounds relative to the optimal policy. Lastly, we substantiate our findings with supporting experimental results.
• Abstract（参考訳）: 現実のシナリオで動作する自律エージェントはしばしば不確実性に遭遇し、不完全な情報に基づいて意思決定を行う。 不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化することができる。 しかし、POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。 近年、木探索やサンプルベース手法などの近似アルゴリズムが、より大規模な問題に対する最先端のPOMDP解法として登場している。 有効性にもかかわらず、これらのアルゴリズムはサンプリングに依存するため最適解に対する確率的かつ漸近的な保証のみを提供する。 これらの制限に対処するため、簡単な解と理論的に最適な解との決定論的関係を導出する。 まず、各後ノードで完全な信念を計算しながら、観測のサブセットを選択して分岐する境界を導出する。 そして、完全な信念更新が計算的に要求されるため、状態と観測空間の両方の縮小をサポートするために境界を拡張する。 我々は、我々の保証が既存の状態と観測のサブセットをサンプリングする最先端のソルバとどのように統合できるかを実証する。 その結果、返却された解は最適方針に対する決定論的境界を持つ。 最後に,実験結果の裏付けとして,本研究の成果を裏付ける。

関連論文リスト

• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
  本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。 割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。 本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-05T02:33:50Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  システム力学と測定チャネルモデルが知られていると仮定したPOMDPの計画問題について検討する。 軽度非線形フィルタ安定性条件下で近似的信念モデルに対する最適ポリシーを求める。 また、有限ウィンドウメモリサイズと近似誤差境界を関連づけた収束結果のレートを確立する。
  論文  参考訳（メタデータ） (2020-10-15T00:37:51Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)
• Sparse tree search optimality guarantees in POMDPs with continuous observation spaces [39.17638795259191]
  連続状態と観測空間を持つ部分観測可能なマルコフ決定プロセス(POMDP)は、実世界の意思決定と制御問題を表現するための強力な柔軟性を有する。 観測可能性重み付けを用いた最近のオンラインサンプリングベースアルゴリズムは、連続的な観測空間を持つ領域において、前例のない有効性を示している。 この研究は、単純化されたアルゴリズム、部分的に観測可能な重み付きスパースサンプリング(POWSS)が高い確率でQ値を正確に推定し、最適解の近くで任意に実行できることを証明し、そのような正当化を提供する。
  論文  参考訳（メタデータ） (2019-10-10T02:22:55Z)

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

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