論文の概要: Reducing Planning Complexity of General Reinforcement Learning with
Non-Markovian Abstractions
- arxiv url: http://arxiv.org/abs/2112.13386v1
- Date: Sun, 26 Dec 2021 14:26:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-29 04:02:45.204256
- Title: Reducing Planning Complexity of General Reinforcement Learning with
Non-Markovian Abstractions
- Title（参考訳）: 非マルコフ抽象を用いた一般強化学習の計画複雑性の低減
- Authors: Sultan J. Majeed and Marcus Hutter
- Abstract要約: 一般に、一般強化学習(GRL)における準最適政策は、完全な歴史の関数である。
我々は、より優れた$Oleft(varepsilon-1 cdot (1-gamma)-2 cdot A cdot 2Aright)$を許容する新しい非MDP抽象化を提案する。
我々は、この境界が$Oleft(varepsilon-1 cdot (1-gamma)-2 cdotにさらに改善できることを示します。
- 参考スコア（独自算出の注目度）: 21.574781022415365
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The field of General Reinforcement Learning (GRL) formulates the problem of
sequential decision-making from ground up. The history of interaction
constitutes a "ground" state of the system, which never repeats. On the one
hand, this generality allows GRL to model almost every domain possible, e.g.\
Bandits, MDPs, POMDPs, PSRs, and history-based environments. On the other hand,
in general, the near-optimal policies in GRL are functions of complete history,
which hinders not only learning but also planning in GRL. The usual way around
for the planning part is that the agent is given a Markovian abstraction of the
underlying process. So, it can use any MDP planning algorithm to find a
near-optimal policy. The Extreme State Aggregation (ESA) framework has extended
this idea to non-Markovian abstractions without compromising on the possibility
of planning through a (surrogate) MDP. A distinguishing feature of ESA is that
it proves an upper bound of $O\left(\varepsilon^{-A} \cdot
(1-\gamma)^{-2A}\right)$ on the number of states required for the surrogate MDP
(where $A$ is the number of actions, $\gamma$ is the discount-factor, and
$\varepsilon$ is the optimality-gap) which holds \emph{uniformly} for
\emph{all} domains. While the possibility of a universal bound is quite
remarkable, we show that this bound is very loose. We propose a novel non-MDP
abstraction which allows for a much better upper bound of
$O\left(\varepsilon^{-1} \cdot (1-\gamma)^{-2} \cdot A \cdot 2^{A}\right)$.
Furthermore, we show that this bound can be improved further to
$O\left(\varepsilon^{-1} \cdot (1-\gamma)^{-2} \cdot \log^3 A \right)$ by using
an action-sequentialization method.
- Abstract（参考訳）: 一般強化学習(GRL)の分野は、逐次意思決定の問題を根本から定式化している。
相互作用の歴史はシステムの"接地"状態を構成し、決して繰り返されない。
一方、この一般化によりGRLは、バンド、MDP、POMDP、PSR、履歴ベースの環境など、ほぼ全ての領域をモデル化できる。
一方、一般論として、GRLの準最適政策は完全な歴史の関数であり、GRLの学習だけでなく、計画も妨げている。
計画部分の通常の方法は、エージェントが基礎となるプロセスのマルコフ的抽象化を与えられることである。
したがって、任意のMDP計画アルゴリズムを使用して、ほぼ最適ポリシーを見つけることができる。
Extreme State Aggregation (ESA)フレームワークは、このアイデアを非マルコフ抽象に拡張した。
ESA の際立った特徴は、サロゲート MDP ($A$ はアクションの数、$\gamma$ は割引因子、$\varepsilon$ は最適値-ギャップ) に対して$O\left(\varepsilon^{-A} \cdot (1-\gamma)^{-2A}\right)$ の上限を証明し、これは \emph{all} ドメインに対して \emph{uniformly} を保持する。
普遍境界の可能性は非常に顕著であるが、この境界は非常に緩いことを示す。
我々は、より優れた$O\left(\varepsilon^{-1} \cdot (1-\gamma)^{-2} \cdot A \cdot 2^{A}\right)$の上限を許容する新しい非MDP抽象化を提案する。
さらに、この境界は作用列化法を用いてさらに$o\left(\varepsilon^{-1} \cdot (1-\gamma)^{-2} \cdot \log^3 a \right)$に改善できることを示した。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2023-11-22T15:34:44Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2020-10-12T17:51:19Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。