論文の概要: 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つのシステムのシミュレーションによって支持される。

関連論文リスト

• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。 本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-01T09:41:45Z)
• Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces [2.2984209387877628]
  本研究では、状態-作用空間を適応的に離散化し、状態-作用空間の有望な領域に拡大するアルゴリズムZoRLを開発する。 ZoRLは実験において、他の最先端アルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2024-10-25T18:14:42Z)
• Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
  リスクに敏感な強化学習(RL)について検討する。 本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。 提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2023-11-20T17:44:40Z)
• 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)
• 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)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• 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)
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses [40.12297110530343]
  我々は、グローバルな探索を容易にするために、ポリシー更新に拡張ボーナスを追加する一般的なソリューションを開発する。 本研究は,敵対的損失と盗聴フィードバックを伴って,複数のエピソードMDP設定に適用する。 シミュレータが利用できない場合、線形 MDP の設定を考慮し、$widetildemathcalO(T14/15)$ regret を得る。
  論文  参考訳（メタデータ） (2021-07-18T02:30:48Z)
• 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)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。 我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T03:20:40Z)
• 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)
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces [26.297887542066505]
  本研究では,自然距離を持つと仮定される連続的な状態-作用空間を用いたエピソディック強化学習について考察する。 本稿では,連続的な帯域幅からアイデアを生かし,共同空間の適応的離散化を学習するオンラインアルゴリズムZoomRLを提案する。 ZoomRL が最悪の後悔点である $tildeO(Hfrac52 Kfracd+1d+2)$ ここでは$H$ が計画的地平線、$K$ がエピソード数、$d$ が空間の被覆次元であることを示す。
  論文  参考訳（メタデータ） (2020-03-09T12:32:02Z)

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

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