論文の概要: 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の指数時間仮説に基づく計画の整合性を証明する。
関連論文リスト
- 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) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳(メタデータ) (2022-08-17T18:49:53Z) - 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 [105.5082667181805]
半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。
本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。
textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
論文 参考訳(メタデータ) (2022-05-26T19:13:55Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。