論文の概要: Value Function Approximations via Kernel Embeddings for No-Regret
Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2011.07881v3
- Date: Tue, 28 Jun 2022 16:01:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-25 00:41:18.094099
- Title: Value Function Approximations via Kernel Embeddings for No-Regret
Reinforcement Learning
- Title（参考訳）: No-Regret Reinforcement Learningのためのカーネル埋め込みによる値関数近似
- Authors: Sayak Ray Chowdhury, Rafael Oliveira
- Abstract要約: 我々は,CME-RLというオンラインモデルに基づくRLアルゴリズムを提案し,Hilbert空間への埋め込みとして遷移分布の表現を学習する。
絶対定数と多対数係数のみを隠蔽する次数$tildeObig(Hgamma_NsqrtNbig)$footnote $tildeO(cdot)$の頻繁な(Worst-case)後悔境界を証明してアルゴリズムの有効性を実証する。
- 参考スコア（独自算出の注目度）: 10.828727066443909
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the regret minimization problem in reinforcement learning (RL) in
the episodic setting. In many real-world RL environments, the state and action
spaces are continuous or very large. Existing approaches establish regret
guarantees by either a low-dimensional representation of the stochastic
transition model or an approximation of the $Q$-functions. However, the
understanding of function approximation schemes for state-value functions
largely remains missing. In this paper, we propose an online model-based RL
algorithm, namely the CME-RL, that learns representations of transition
distributions as embeddings in a reproducing kernel Hilbert space while
carefully balancing the exploitation-exploration tradeoff. We demonstrate the
efficiency of our algorithm by proving a frequentist (worst-case) regret bound
that is of order $\tilde{O}\big(H\gamma_N\sqrt{N}\big)$\footnote{
$\tilde{O}(\cdot)$ hides only absolute constant and poly-logarithmic factors.},
where $H$ is the episode length, $N$ is the total number of time steps and
$\gamma_N$ is an information theoretic quantity relating the effective
dimension of the state-action feature space. Our method bypasses the need for
estimating transition probabilities and applies to any domain on which kernels
can be defined. It also brings new insights into the general theory of kernel
methods for approximate inference and RL regret minimization.
- Abstract（参考訳）: エピソディクス設定における強化学習(rl)における後悔の最小化問題を考える。
多くの実世界のRL環境では、状態空間と作用空間は連続的あるいは非常に大きい。
既存のアプローチは、確率遷移モデルの低次元表現または$Q$-函数の近似によって、後悔の保証を確立する。
しかし、状態値関数に対する関数近似スキームの理解はほとんど失われていない。
本稿では,再生成カーネルHilbert空間への埋め込みとして遷移分布の表現を学習し,エクスプロレーションと探索のトレードオフを慎重にバランスさせるオンラインモデルベースRLアルゴリズム,すなわちCME-RLを提案する。
我々は,次数 $\tilde{O}\big(H\gamma_N\sqrt{N}\big)$\footnote{ $\tilde{O}(\cdot)$ 絶対定数と多元対数要素のみを隠蔽する頻繁な(Worst-case)後悔境界を証明することによって,アルゴリズムの効率を実証する。
h$ がエピソードの長さ、$n$ は時間ステップの総数、$\gamma_n$ は状態-アクション特徴空間の有効次元に関する情報理論量である。
提案手法は遷移確率を推定する必要性を回避し,カーネル定義可能な任意の領域に適用する。
また、近似推論とRL後悔最小化のためのカーネルメソッドの一般理論に新たな洞察をもたらす。
関連論文リスト
- Learning Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback [30.23951525723659]
本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。
政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
論文 参考訳（メタデータ） (2023-11-14T03:12:43Z) - Kernelized Reinforcement Learning with Order Optimal Regret Bounds [11.024396385514864]
$pi$KRVI は最小自明なヒルベルト二乗値の楽観的な修正である。
我々は、一般的な設定の下で、最初の順序最適後悔保証を証明します。
マタン核の場合、順序が最適である部分線型後悔境界を示す。
論文 参考訳（メタデータ） (2023-06-13T13:01:42Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Perturbational Complexity by Distribution Mismatch: A Systematic
Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space [0.76146285961466]
一般再生カーネルヒルベルト空間(RKHS)における強化学習の解析
我々は、報酬関数がRKHSの単位球に含まれるマルコフ決定過程の族 $mathcalM$ を考える。
報酬関数が高次元のRKHSにあるとき、遷移確率が知られ、作用空間が有限であるとしても、RL問題を次元性の呪いに苦しむことは可能であることを示す。
論文 参考訳（メタデータ） (2021-11-05T12:46:04Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z) - Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
モデルに基づく楽観的アルゴリズムであるKernel-UCBVIを導入する。
スパース報酬を伴う連続MDPにおける我々のアプローチを実証的に検証する。
論文 参考訳（メタデータ） (2020-04-12T12:23:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。