論文の概要: 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問題は次元性の呪いに苦しむことができることを示す。
関連論文リスト
- 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) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。