論文の概要: Perturbational Complexity by Distribution Mismatch: A Systematic
Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space
- arxiv url: http://arxiv.org/abs/2111.03469v1
- Date: Fri, 5 Nov 2021 12:46:04 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-08 15:47:39.464990
- Title: Perturbational Complexity by Distribution Mismatch: A Systematic
Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space
- Title(参考訳): 分布ミスマッチによる摂動複雑性:カーネルヒルベルト空間再生における強化学習の体系的解析
- Authors: Jihao Long, Jiequn Han
- Abstract要約: 一般再生カーネルヒルベルト空間(RKHS)における強化学習の解析
我々は、報酬関数がRKHSの単位球に含まれるマルコフ決定過程の族 $mathcalM$ を考える。
報酬関数が高次元のRKHSにあるとき、遷移確率が知られ、作用空間が有限であるとしても、RL問題を次元性の呪いに苦しむことは可能であることを示す。
- 参考スコア(独自算出の注目度): 0.76146285961466
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Most existing theoretical analysis of reinforcement learning (RL) is limited
to the tabular setting or linear models due to the difficulty in dealing with
function approximation in high dimensional space with an uncertain environment.
This work offers a fresh perspective into this challenge by analyzing RL in a
general reproducing kernel Hilbert space (RKHS). We consider a family of Markov
decision processes $\mathcal{M}$ of which the reward functions lie in the unit
ball of an RKHS and transition probabilities lie in a given arbitrary set. We
define a quantity called perturbational complexity by distribution mismatch
$\Delta_{\mathcal{M}}(\epsilon)$ to characterize the complexity of the
admissible state-action distribution space in response to a perturbation in the
RKHS with scale $\epsilon$. We show that $\Delta_{\mathcal{M}}(\epsilon)$ gives
both the lower bound of the error of all possible algorithms and the upper
bound of two specific algorithms (fitted reward and fitted Q-iteration) for the
RL problem. Hence, the decay of $\Delta_\mathcal{M}(\epsilon)$ with respect to
$\epsilon$ measures the difficulty of the RL problem on $\mathcal{M}$. We
further provide some concrete examples and discuss whether
$\Delta_{\mathcal{M}}(\epsilon)$ decays fast or not in these examples. As a
byproduct, we show that when the reward functions lie in a high dimensional
RKHS, even if the transition probability is known and the action space is
finite, it is still possible for RL problems to suffer from the curse of
dimensionality.
- Abstract(参考訳): 強化学習(RL)の理論的解析は,高次元空間と不確実な環境との関数近似を扱うのが困難であるため,表の設定や線形モデルに限られている。
この研究は、一般再生カーネルヒルベルト空間(RKHS)におけるRLの分析により、この問題に対する新たな視点を提供する。
マルコフ決定過程の族 $\mathcal{M}$ を考えると、報酬関数は RKHS の単位球内にあり、遷移確率は与えられた任意の集合内にある。
分布ミスマッチ$\Delta_{\mathcal{M}}(\epsilon)$によって摂動複雑性と呼ばれる量を定義し、スケール$\epsilon$のRKHSの摂動に応答して許容状態-作用分布空間の複雑さを特徴づける。
我々は、$\Delta_{\mathcal{M}}(\epsilon)$が全ての可能なアルゴリズムの誤差の下位境界とRL問題に対する2つの特定のアルゴリズム(報奨と適合Q-イテレーション)の上限の両方を与えることを示した。
従って、$\epsilon$に対する$\delta_\mathcal{m}(\epsilon)$の崩壊は、$\mathcal{m}$におけるrl問題の難易度を測定する。
さらに具体例をいくつか提示し、これらの例で$\Delta_{\mathcal{M}}(\epsilon)$崩壊が速いかどうかについて議論する。
副産物として、報酬関数が高次元のRKHSにあるとき、遷移確率が知られ、作用空間が有限であるとしても、RL問題は次元性の呪いに苦しむことができることを示す。
関連論文リスト
- Demonstration-Regularized RL [41.465567768628794]
専門的な実証から,次数$widetildemathcalO(mathrmPoly(S,A,H)/(varepsilon2 NmathrmE)$の有限および$widetildemathcalO(mathrmPoly(d,H)/(varepsilon2 NmathrmE)$の線形マルコフ決定過程における最適ポリシを同定する。
論文 参考訳(メタデータ) (2023-10-26T10:54:47Z) - Settling the Sample Complexity of Online Reinforcement Learning [100.52613756483589]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳(メタデータ) (2023-07-25T15:42:11Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳(メタデータ) (2023-05-15T05:37:32Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-14T16:51:14Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳(メタデータ) (2022-08-22T17:24:55Z) - An $L^2$ Analysis of Reinforcement Learning in High Dimensions with
Kernel and Neural Network Approximation [9.088303226909277]
本稿では,カーネル法や2層ニューラルネットワークモデルを用いて関数近似を行う状況について考察する。
私たちは$tildeO(H3|mathcal A|frac14n-frac14)$を$Hn$サンプルで最適なポリシーにバインドします。
この結果はまだ有限次元の作用空間を必要とするが、誤差境界は状態空間の次元とは独立である。
論文 参考訳(メタデータ) (2021-04-15T21:59:03Z) - A Lower Bound for the Sample Complexity of Inverse Reinforcement
Learning [26.384010313580596]
逆強化学習(IRL)は、与えられたマルコフ決定過程(MDP)に対して望ましい最適ポリシーを生成する報酬関数を求めるタスクである。
本稿では, 有限状態, 有限作用IRL問題のサンプル複雑性に対する情報理論の下界について述べる。
論文 参考訳(メタデータ) (2021-03-07T20:29:10Z) - 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) - Value Function Approximations via Kernel Embeddings for No-Regret
Reinforcement Learning [10.828727066443909]
我々は,CME-RLというオンラインモデルに基づくRLアルゴリズムを提案し,Hilbert空間への埋め込みとして遷移分布の表現を学習する。
絶対定数と多対数係数のみを隠蔽する次数$tildeObig(Hgamma_NsqrtNbig)$footnote $tildeO(cdot)$の頻繁な(Worst-case)後悔境界を証明してアルゴリズムの有効性を実証する。
論文 参考訳(メタデータ) (2020-11-16T11:40:55Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。