論文の概要: Adaptive Discretization-based Non-Episodic Reinforcement Learning in Metric Spaces

• arxiv url: http://arxiv.org/abs/2405.18793v1
• Date: Wed, 29 May 2024 06:18:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 18:38:40.063600
• Title: Adaptive Discretization-based Non-Episodic Reinforcement Learning in Metric Spaces
• Title（参考訳）: 距離空間における適応的離散化に基づく非エポゾディック強化学習
• Authors: Avik Kar, Rahul Singh,
• Abstract要約: 状態作用空間を距離空間とし、遷移核と報酬をリプシッツ関数とするリプシッツ MDP に対する非絶対強化学習について検討する。 我々は、状態-作用空間を適応的に離散化する、計算効率の良い UCB ベースのアルゴリズム $textitZoRLepsilon$ を開発した。
• 参考スコア（独自算出の注目度）: 2.2984209387877628
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study non-episodic Reinforcement Learning for Lipschitz MDPs in which state-action space is a metric space, and the transition kernel and rewards are Lipschitz functions. We develop computationally efficient UCB-based algorithm, $\textit{ZoRL-}\epsilon$ that adaptively discretizes the state-action space and show that their regret as compared with $\epsilon$-optimal policy is bounded as $\mathcal{O}(\epsilon^{-(2 d_\mathcal{S} + d^\epsilon_z + 1)}\log{(T)})$, where $d^\epsilon_z$ is the $\epsilon$-zooming dimension. In contrast, if one uses the vanilla $\textit{UCRL-}2$ on a fixed discretization of the MDP, the regret w.r.t. a $\epsilon$-optimal policy scales as $\mathcal{O}(\epsilon^{-(2 d_\mathcal{S} + d + 1)}\log{(T)})$ so that the adaptivity gains are huge when $d^\epsilon_z \ll d$. Note that the absolute regret of any 'uniformly good' algorithm for a large family of continuous MDPs asymptotically scales as at least $\Omega(\log{(T)})$. Though adaptive discretization has been shown to yield $\mathcal{\tilde{O}}(H^{2.5}K^\frac{d_z + 1}{d_z + 2})$ regret in episodic RL, an attempt to extend this to the non-episodic case by employing constant duration episodes whose duration increases with $T$, is futile since $d_z \to d$ as $T \to \infty$. The current work shows how to obtain adaptivity gains for non-episodic RL. The theoretical results are supported by simulations on two systems where the performance of $\textit{ZoRL-}\epsilon$ is compared with that of '$\textit{UCRL-C}$,' the fixed discretization-based extension of $\textit{UCRL-}2$ for systems with continuous state-action spaces.
• Abstract（参考訳）: 状態作用空間を距離空間とし、遷移核と報酬をリプシッツ関数とするリプシッツ MDP に対する非絶対強化学習について検討する。 計算効率の良い UCB-based algorithm, $\textit{ZoRL-}\epsilon$ は、状態-作用空間を適応的に離散化し、それらの後悔が $\epsilon$-optimal policy に対して $\mathcal{O}(\epsilon^{-(2d_\mathcal{S} + d^\epsilon_z + 1)}\log{(T)} として有界であることを示し、$d^\epsilon_z$ は $\epsilon$-zooming dimension である。 対照的に、MDP の固定離散化にバニラ $\textit{UCRL-}2$ を使用する場合、後悔 w.r.t. a $\epsilon$-optimal policy scales as $\mathcal{O}(\epsilon^{-(2 d_\mathcal{S} + d + 1)}\log{(T)}$ として、d^\epsilon_z \ll d$ のとき、適応性は巨大になる。 連続 MDP の大きな族に対する「一様良い」アルゴリズムの絶対的後悔は、少なくとも$\Omega(\log{(T)})$として漸近的にスケールする。 適応的な離散化は、エピソード RL において $\mathcal{\tilde{O}}(H^{2.5}K^\frac{d_z + 1}{d_z + 2})$ regret をもたらすことが示されているが、$d_z \to d$ as $T \to \infty$ であるから、持続時間が $T$ で増加する一定期間のエピソードを用いてこれを非エピソードケースに拡張しようとする試みは無駄である。 現在の研究は、非エポゾディックRLに対する適応性ゲインを得る方法を示している。 理論的結果は、連続的な状態作用空間を持つシステムに対する$\textit{ZoRL-}\epsilon$ と '$\textit{UCRL-C}$' の固定離散化に基づく $\textit{UCRL-}2$ の性能を比較する2つのシステムのシミュレーションによって支持される。

関連論文リスト

• Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces [2.2984209387877628]
  本研究では、状態-作用空間を適応的に離散化し、状態-作用空間の有望な領域に拡大するアルゴリズムZoRLを開発する。 ZoRLは実験において、他の最先端アルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2024-10-25T18:14:42Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• 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)
• Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
  文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。 我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
  論文  参考訳（メタデータ） (2022-11-27T20:38:47Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism [34.54294677335518]
  我々は、未知マルコフ決定過程(MDP)における報酬最大化ポリシーの学習を目標とするオフライン強化学習(オフラインRL)問題について検討する。 本研究では、適応悲観的値反復法(APVI)アルゴリズムを分析し、[Oleft(sum_h=1Hsum_s_h,a_hdpistar_h(s_h,a_h)sqrtfracmathrmmathrmVar_]とほぼ一致する準最適上限を導出する。
  論文  参考訳（メタデータ） (2021-10-17T01:21:52Z)
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
  タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。 このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。 情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
  論文  参考訳（メタデータ） (2021-08-11T20:42:46Z)
• Model Selection with Near Optimal Rates for Reinforcement Learning with General Model Classes [27.361399036211694]
  有限地平線エピソディック強化学習(RL)問題に対するモデル選択の問題に対処する。 モデル選択フレームワークでは、$mathcalP*$の代わりに、遷移カーネルのネストされたファミリーが$M$を与えられる。 textttARL-GENが$TildemathcalO(d_mathcalE* H2+sqrtd_mathcalE* mathbbM* H2T)$の後悔を得ることを示す。
  論文  参考訳（メタデータ） (2021-07-13T05:00:38Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。