論文の概要: Nearly Optimal Latent State Decoding in Block MDPs
- arxiv url: http://arxiv.org/abs/2208.08480v1
- Date: Wed, 17 Aug 2022 18:49:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-19 13:23:50.871349
- Title: Nearly Optimal Latent State Decoding in Block MDPs
- Title（参考訳）: ブロックMDPにおけるほぼ最適遅延状態復号法
- Authors: Yassir Jedra, Junghyun Lee, Alexandre Prouti\`ere, Se-Young Yun
- Abstract要約: エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
- 参考スコア（独自算出の注目度）: 74.51224067640717
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the problems of model estimation and reward-free learning in
episodic Block MDPs. In these MDPs, the decision maker has access to rich
observations or contexts generated from a small number of latent states. We are
first interested in estimating the latent state decoding function (the mapping
from the observations to latent states) based on data generated under a fixed
behavior policy. We derive an information-theoretical lower bound on the error
rate for estimating this function and present an algorithm approaching this
fundamental limit. In turn, our algorithm also provides estimates of all the
components of the MDP. We then study the problem of learning near-optimal
policies in the reward-free framework. Based on our efficient model estimation
algorithm, we show that we can infer a policy converging (as the number of
collected samples grows large) to the optimal policy at the best possible rate.
Interestingly, our analysis provides necessary and sufficient conditions under
which exploiting the block structure yields improvements in the sample
complexity for identifying near-optimal policies. When these conditions are
met, the sample complexity in the minimax reward-free setting is improved by a
multiplicative factor $n$, where $n$ is the number of possible contexts.
- Abstract（参考訳）: エピソードブロックMDPにおけるモデル推定と報酬なし学習の問題について検討する。
これらのMDPでは、意思決定者は少数の潜在状態から生成される豊富な観測や文脈にアクセスすることができる。
まず, 一定の行動方針に基づいて生成されたデータに基づいて, 潜在状態復号関数(観測から潜在状態へのマッピング)を推定することに関心を寄せる。
我々は,この関数を推定するための誤り率に関する情報理論の下限を導出し,この基本極限に近づくアルゴリズムを提案する。
また,本アルゴリズムはmdpの全成分の推定値も提供する。
次に,報酬のない枠組みで最適に近い政策を学ぶ問題について検討する。
効率的なモデル推定アルゴリズムに基づき、最適なポリシーに最適なレートで(収集されたサンプルの数が大きくなるにつれて)ポリシーの収束を推測できることを示した。
興味深いことに,本解析は,ブロック構造の活用によってサンプルの複雑さが向上し,最適に近い方針を特定するために必要な条件を提供する。
これらの条件を満たすと、ミニマックスの報酬なし設定におけるサンプルの複雑さは乗算係数$n$によって改善され、$n$は可能なコンテキストの数である。
関連論文リスト
- 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) - Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。
本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
論文 参考訳（メタデータ） (2024-06-26T17:57:13Z) - Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。
私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。
彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
論文 参考訳（メタデータ） (2022-03-17T11:19:41Z) - 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) - Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation [49.502277468627035]
本稿では,関数近似を用いたバッチデータ強化学習の統計的理論について検討する。
記録履歴から新たな対象政策の累積値を推定するオフ・ポリティクス評価問題を考察する。
論文 参考訳（メタデータ） (2020-02-21T19:20:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。