論文の概要: Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations
- arxiv url: http://arxiv.org/abs/2204.09787v1
- Date: Wed, 20 Apr 2022 21:15:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-23 03:30:04.910502
- Title: Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations
- Title(参考訳): 線形関数近似を用いたpomdpのサンプル効率強化学習
- Authors: Qi Cai, Zhuoran Yang, Zhaoran Wang
- Abstract要約: 本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 130.66193083412716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite the success of reinforcement learning (RL) for Markov decision
processes (MDPs) with function approximation, most RL algorithms easily fail if
the agent only has partial observations of the state. Such a setting is often
modeled as a partially observable Markov decision process (POMDP). Existing
sample-efficient algorithms for POMDPs are restricted to the tabular setting
where the state and observation spaces are finite. In this paper, we make the
first attempt at tackling the tension between function approximation and
partial observability. In specific, we focus on a class of undercomplete POMDPs
with linear function approximations, which allows the state and observation
spaces to be infinite. For such POMDPs, we show that the optimal policy and
value function can be characterized by a sequence of finite-memory Bellman
operators. We propose an RL algorithm that constructs optimistic estimators of
these operators via reproducing kernel Hilbert space (RKHS) embedding.
Moreover, we theoretically prove that the proposed algorithm finds an
$\varepsilon$-optimal policy with $\tilde O (1/\varepsilon^2)$ episodes of
exploration. Also, this sample complexity only depends on the intrinsic
dimension of the POMDP polynomially and is independent of the size of the state
and observation spaces. To our best knowledge, we develop the first provably
sample-efficient algorithm for POMDPs with function approximation.
- Abstract(参考訳): 関数近似によるマルコフ決定過程(MDP)に対する強化学習(RL)の成功にもかかわらず、ほとんどのRLアルゴリズムは、エージェントが状態の部分的な観察しか持たなければ容易に失敗する。
このような設定はしばしば部分的に観察可能なマルコフ決定過程(pomdp)としてモデル化される。
既存のサンプル効率のアルゴリズムは、状態と観測空間が有限となる表の設定に制限される。
本稿では,関数近似と部分可観測性の間の張力に取り組む最初の試みを行う。
具体的には、線形関数近似を持つ不完全POMDPのクラスに焦点を当て、状態と観測空間を無限にすることができる。
そのようなPOMDPに対して、最適ポリシーと値関数は有限メモリベルマン作用素の列によって特徴づけられることを示す。
本稿では,これらの演算子の楽観的推定をカーネルヒルベルト空間(rkhs)埋め込みを再現することで構成するrlアルゴリズムを提案する。
さらに,提案アルゴリズムが$\varepsilon$-optimal policy with $\tilde O (1/\varepsilon^2)$ episodes of Explorion を求めることを理論的に証明した。
また、このサンプルの複雑さは、POMDP多項式の固有次元にのみ依存し、状態と観測空間のサイズに依存しない。
我々の知る限り、関数近似を用いたPOMDPのための最初の実証可能なサンプル効率アルゴリズムを開発した。
関連論文リスト
- Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳(メタデータ) (2023-10-03T04:40:38Z) - Provably Efficient Representation Learning with Tractable Planning in
Low-Rank POMDP [81.00800920928621]
部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究
まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。
次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
論文 参考訳(メタデータ) (2023-06-21T16:04:03Z) - Computationally Efficient PAC RL in POMDPs with Latent Determinism and
Conditional Embeddings [97.12538243736705]
大規模部分観測可能決定プロセス(POMDP)の関数近似を用いた強化学習に関する研究
我々のアルゴリズムは、大規模POMDPに確実にスケールする。
論文 参考訳(メタデータ) (2022-06-24T05:13:35Z) - Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。
私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。
彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
論文 参考訳(メタデータ) (2022-03-17T11:19:41Z) - Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
そこでは,CNF式を決定論的遷移,動作の定数数,低次元線形最適値関数を備えたMDP仮説に変換する。
この結果は線形関数近似を用いた強化学習における最初の計算統計的ギャップを示す。
論文 参考訳(メタデータ) (2022-02-11T04:48:35Z) - 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) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳(メタデータ) (2020-06-22T17:58:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。