論文の概要: Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
- arxiv url: http://arxiv.org/abs/2312.12558v3
- Date: Mon, 3 Jun 2024 06:17:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-04 19:52:07.791584
- Title: Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
- Title（参考訳）: 部分動力学知識を用いたサンプル高能率強化学習
- Authors: Meshal Alharbi, Mardavij Roozbehani, Munther Dahleh,
- Abstract要約: オンラインQ-ラーニング手法のサンプル複雑性について,動的知識が利用可能であったり,効率的に学習できたりした場合に検討する。
我々は,$f$の完全知識の下で,$tildemathcalO(textPoly(H)sqrtSAT)$ regretを達成する楽観的なQ-ラーニングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.704590071265998
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of sample complexity of online reinforcement learning is often studied in the literature without taking into account any partial knowledge about the system dynamics that could potentially accelerate the learning process. In this paper, we study the sample complexity of online Q-learning methods when some prior knowledge about the dynamics is available or can be learned efficiently. We focus on systems that evolve according to an additive disturbance model of the form $S_{h+1} = f(S_h, A_h) + W_h$, where $f$ represents the underlying system dynamics, and $W_h$ are unknown disturbances independent of states and actions. In the setting of finite episodic Markov decision processes with $S$ states, $A$ actions, and episode length $H$, we present an optimistic Q-learning algorithm that achieves $\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{T})$ regret under perfect knowledge of $f$, where $T$ is the total number of interactions with the system. This is in contrast to the typical $\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{SAT})$ regret for existing Q-learning methods. Further, if only a noisy estimate $\hat{f}$ of $f$ is available, our method can learn an approximately optimal policy in a number of samples that is independent of the cardinalities of state and action spaces. The sub-optimality gap depends on the approximation error $\hat{f}-f$, as well as the Lipschitz constant of the corresponding optimal value function. Our approach does not require modeling of the transition probabilities and enjoys the same memory complexity as model-free methods.
- Abstract（参考訳）: オンライン強化学習のサンプル複雑性の問題は、学習過程を加速させる可能性のあるシステム力学に関する部分的な知識を考慮せずに、文献でしばしば研究される。
本稿では,オンラインQ-ラーニング手法のサンプル複雑性について,ダイナミックスに関する事前知識が利用可能であったり,効率的に学習できたりした場合に検討する。
S_{h+1} = f(S_h, A_h) + W_h$, ここで$f$は基礎となるシステムダイナミクスを表し、$W_h$は状態や動作に依存しない未知の乱れである。
S$状態、$A$アクション、およびエピソード長$H$の有限エピソードマルコフ決定プロセスの設定において、$\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{T})$を達成できる楽観的なQ学習アルゴリズムを示す。
これは、既存のQ-ラーニングメソッドに対する典型的な $\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{SAT})$ regret とは対照的である。
さらに、ノイズの多い$\hat{f}$ of $f$しか得られない場合、状態空間と作用空間の濃度に依存しない多くのサンプルにおいて、我々の手法は、ほぼ最適なポリシーを学習することができる。
準最適性ギャップは近似誤差 $\hat{f}-f$ と対応する最適値関数のリプシッツ定数に依存する。
我々の手法は遷移確率のモデリングを必要とせず、モデルフリーの手法と同じメモリの複雑さを享受する。
関連論文リスト
- 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) - When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Online Learning in Dynamically Changing Environments [11.731001328350983]
一般的な未知の非定常過程からサンプルを引き出す際に,オンライン学習とオンライン後悔の問題を考察する。
我々は、任意の有限VC-次元クラスに対する予想される最悪のケースに対する厳密な($sqrtlog T$ factorまで)有界な$O(sqrtKTcdotmathsfVC(mathcalH)log T)$を証明する。
我々はこれらの結果を、未知の基準測度を持つ一般的なスムーズな逆過程に拡張する。
論文 参考訳（メタデータ） (2023-01-31T21:10:03Z) - Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic
Shortest Path [106.37656068276902]
本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。
学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
論文 参考訳（メタデータ） (2022-10-10T18:34:32Z) - Tractable Optimality in Episodic Latent MABs [75.17357040707347]
我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。
エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。
我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
論文 参考訳（メタデータ） (2022-10-05T22:53:46Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Near-optimal Offline and Streaming Algorithms for Learning Non-Linear
Dynamical Systems [45.17023170054112]
X_t+1 = phi(A* X_t) + eta_t$, where $eta_t$ is unbiased noise and $phi : mathbbR to mathbbR$ is a known link function that certain em expansivity properties。
論文 参考訳（メタデータ） (2021-05-24T22:14:26Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - Learning to extrapolate using continued fractions: Predicting the
critical temperature of superconductor materials [5.905364646955811]
人工知能(AI)と機械学習(ML)の分野では、未知のターゲット関数 $y=f(mathbfx)$ の近似が共通の目的である。
トレーニングセットとして$S$を参照し、新しいインスタンス$mathbfx$に対して、このターゲット関数を効果的に近似できる低複雑さの数学的モデルを特定することを目的としている。
論文 参考訳（メタデータ） (2020-11-27T04:57:40Z) - Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems [34.394552166070746]
本研究では,1つの有限軌跡から得られた標本からシステム力学を学習するための勾配に基づくアルゴリズムについて検討する。
既存の作業とは異なり、我々の限界はノイズに敏感で、精度が高く、サンプルの複雑さも小さい。
論文 参考訳（メタデータ） (2020-02-20T02:36:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。