論文の概要: Planning in Observable POMDPs in Quasipolynomial Time
- arxiv url: http://arxiv.org/abs/2201.04735v1
- Date: Wed, 12 Jan 2022 23:16:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-14 14:04:16.294404
- Title: Planning in Observable POMDPs in Quasipolynomial Time
- Title（参考訳）: 準ポリリノミカル時間における観測可能なPMDPの計画
- Authors: Noah Golowich, Ankur Moitra, and Dhruv Rohatgi
- Abstract要約: 我々は観測可能なPOMDPの計画のための準ポリノミカル時間アルゴリズムを開発した。
我々は、状態上のよく分断された分布が観察上のよく分断された分布をもたらすと仮定する。
観測可能なPOMDPの指数時間仮説の下での計画に適合する硬さを実証する。
- 参考スコア（独自算出の注目度）: 21.03037504572896
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partially Observable Markov Decision Processes (POMDPs) are a natural and
general model in reinforcement learning that take into account the agent's
uncertainty about its current state. In the literature on POMDPs, it is
customary to assume access to a planning oracle that computes an optimal policy
when the parameters are known, even though the problem is known to be
computationally hard. Almost all existing planning algorithms either run in
exponential time, lack provable performance guarantees, or require placing
strong assumptions on the transition dynamics under every possible policy. In
this work, we revisit the planning problem and ask: are there natural and
well-motivated assumptions that make planning easy?
Our main result is a quasipolynomial-time algorithm for planning in
(one-step) observable POMDPs. Specifically, we assume that well-separated
distributions on states lead to well-separated distributions on observations,
and thus the observations are at least somewhat informative in each step.
Crucially, this assumption places no restrictions on the transition dynamics of
the POMDP; nevertheless, it implies that near-optimal policies admit
quasi-succinct descriptions, which is not true in general (under standard
hardness assumptions). Our analysis is based on new quantitative bounds for
filter stability -- i.e. the rate at which an optimal filter for the latent
state forgets its initialization. Furthermore, we prove matching hardness for
planning in observable POMDPs under the Exponential Time Hypothesis.
- Abstract（参考訳）: 部分的に観察可能なマルコフ決定過程(POMDPs)は、エージェントの現在の状態に対する不確実性を考慮した強化学習の自然な一般モデルである。
POMDPの文献では、問題の計算が困難であるにもかかわらず、パラメータが知られているときに最適なポリシーを演算するプランニングオラクルへのアクセスを仮定するのが慣例である。
既存の計画アルゴリズムのほとんどすべてが指数関数的に実行されるか、保証可能な性能保証を欠いているか、あるいはあらゆる可能なポリシーの下で遷移ダイナミクスに強い仮定を課す必要がある。
この作業では、計画の問題を再検討し、次のような質問をする。 計画を簡単にする自然で動機づけられた仮定はありますか?
我々の主な成果は、観測可能なPOMDPを計画するための準ポリノミカル時間アルゴリズムである。
具体的には、状態のよく区切られた分布が観測上のよく区切られた分布をもたらすと仮定し、各段階において観測は少なくとも何らかの意味を持つと仮定する。
重要なことに、この仮定はPOMDPの遷移力学に制限を課さないが、しかしながら、準簡潔な記述をほぼ最適に記述することは、一般には正しくない(標準的な硬さの仮定では)。
我々の分析は、フィルタ安定性のための新しい定量的境界、すなわち潜伏状態の最適フィルタがその初期化を忘れる速度に基づいている。
さらに,観測可能なPOMDPの指数時間仮説に基づく計画の整合性を証明する。
関連論文リスト
- 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) - Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。
このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
論文 参考訳（メタデータ） (2024-06-12T06:41:47Z) - Learning Logic Specifications for Policy Guidance in POMDPs: an
Inductive Logic Programming Approach [57.788675205519986]
我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。
我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。
ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
論文 参考訳（メタデータ） (2024-02-29T15:36:01Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳（メタデータ） (2023-10-03T04:40:38Z) - Learning in Observable POMDPs, without Computationally Intractable
Oracles [23.636033995089587]
我々は,PMDPのための最初のオラクルフリー学習アルゴリズムを合理的な仮定で開発する。
具体的には、「観測可能」なPOMDPで学習するための準ポロリノミカル時間終端アルゴリズムを与えるが、観測可能性とは、状態上のよく分断された分布が観察よりもよく分断された分布を誘導するという仮定である。
論文 参考訳（メタデータ） (2022-06-07T17:05:27Z) - Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。
本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。
textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-05-26T19:13:55Z) - Efficient Belief Space Planning in High-Dimensional State Spaces using
PIVOT: Predictive Incremental Variable Ordering Tactic [11.878820609988693]
我々は,不確実性の下でのオンライン意思決定の問題点を考察し,信頼空間における計画として定式化する。
このアプローチを PIVOT: Predictive Incremental Variable Ordering Tactic と呼ぶ。
この戦術を適用することで、状態推論の効率も向上する。
論文 参考訳（メタデータ） (2021-12-29T07:30:47Z) - Rule-based Shielding for Partially Observable Monte-Carlo Planning [78.05638156687343]
一部観測可能なモンテカルロ計画(POMCP)への2つの貢献を提案する。
1つ目は、POMCPが選択した予期しない行動を、タスクのエキスパートの事前知識に関して識別する方法です。
2つ目は、POMCPが予期せぬ動作を選択するのを防ぐ遮蔽アプローチである。
我々は,pomdpsの標準ベンチマークであるtigerに対するアプローチと,移動ロボットナビゲーションにおける速度規制に関する実世界問題を評価する。
論文 参考訳（メタデータ） (2021-04-28T14:23:38Z) - Adaptive Belief Discretization for POMDP Planning [7.508023795800546]
多くのPOMDPソルバは、信念空間を均一に識別し、(一般に不明な)カバー数の観点から計画誤差を与える。
適応的信念の識別方式を提案し,それに関連する計画誤差を与える。
私達は私達のアルゴリズムがさまざまなシナリオの最先端の技術と競争が高いことを証明します。
論文 参考訳（メタデータ） (2021-04-15T07:04:32Z) - Stein Variational Model Predictive Control [130.60527864489168]
不確実性の下での意思決定は、現実の自律システムにとって極めて重要である。
モデル予測制御 (MPC) 法は, 複雑な分布を扱う場合, 適用範囲が限られている。
この枠組みが、挑戦的で非最適な制御問題における計画の成功に繋がることを示す。
論文 参考訳（メタデータ） (2020-11-15T22:36:59Z) - Near Optimality of Finite Memory Feedback Policies in Partially Observed
Markov Decision Processes [0.0]
システム力学と測定チャネルモデルが知られていると仮定したPOMDPの計画問題について検討する。
軽度非線形フィルタ安定性条件下で近似的信念モデルに対する最適ポリシーを求める。
また、有限ウィンドウメモリサイズと近似誤差境界を関連づけた収束結果のレートを確立する。
論文 参考訳（メタデータ） (2020-10-15T00:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。