論文の概要: Efficient Reinforcement Learning in Probabilistic Reward Machines

• arxiv url: http://arxiv.org/abs/2408.10381v1
• Date: Mon, 19 Aug 2024 19:51:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-21 17:53:16.035610
• Title: Efficient Reinforcement Learning in Probabilistic Reward Machines
• Title（参考訳）: 確率的リワードマシンにおける効率的な強化学習
• Authors: Xiaofeng Lin, Xuezhou Zhang,
• Abstract要約: 本稿では,PRM(Probabilistic Reward Machines)のアルゴリズムを設計し,$widetildeO(sqrtHOAT)の償却を達成した。 また,非マルコフ報酬に対する新たなシミュレーション補題を提案し,非マルコフ報酬に対する報酬のない探索を可能にする。
• 参考スコア（独自算出の注目度）: 15.645062155050732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study reinforcement learning in Markov Decision Processes with Probabilistic Reward Machines (PRMs), a form of non-Markovian reward commonly found in robotics tasks. We design an algorithm for PRMs that achieves a regret bound of $\widetilde{O}(\sqrt{HOAT} + H^2O^2A^{3/2} + H\sqrt{T})$, where $H$ is the time horizon, $O$ is the number of observations, $A$ is the number of actions, and $T$ is the number of time-steps. This result improves over the best-known bound, $\widetilde{O}(H\sqrt{OAT})$ of \citet{pmlr-v206-bourel23a} for MDPs with Deterministic Reward Machines (DRMs), a special case of PRMs. When $T \geq H^3O^3A^2$ and $OA \geq H$, our regret bound leads to a regret of $\widetilde{O}(\sqrt{HOAT})$, which matches the established lower bound of $\Omega(\sqrt{HOAT})$ for MDPs with DRMs up to a logarithmic factor. To the best of our knowledge, this is the first efficient algorithm for PRMs. Additionally, we present a new simulation lemma for non-Markovian rewards, which enables reward-free exploration for any non-Markovian reward given access to an approximate planner. Complementing our theoretical findings, we show through extensive experiment evaluations that our algorithm indeed outperforms prior methods in various PRM environments.
• Abstract（参考訳）: 本稿では,確率的リワードマシン(PRM)を用いたマルコフ決定過程における強化学習について検討する。 我々は,PRMに対して,$\widetilde{O}(\sqrt{HOAT} + H^2O^2A^{3/2} + H\sqrt{T})$,$H$が時間軸,$O$が観測回数,$A$が行動回数,$T$が時間ステップ数であるようなアルゴリズムを設計する。 この結果は最もよく知られた境界である$\widetilde{O}(H\sqrt{OAT})$ of \citet{pmlr-v206-bourel23a} for MDPs with Deterministic Reward Machines (DRMs) よりも改善される。 残念なことに、$T \geq H^3O^3A^2$と$OA \geq H$は$\widetilde{O}(\sqrt{HOAT})$に反する。 我々の知る限りでは、これはPRMにとって初めての効率的なアルゴリズムである。 さらに,非マルコフ報酬に対する新たなシミュレーション補題を提案する。 理論的な知見を補完し,提案アルゴリズムは様々なPRM環境において,従来の手法よりも優れていることを示す。

関連論文リスト

• Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning [6.236688509180343]
  政策訓練と展開環境が異なるオフダイナミックス強化学習(RL)について検討する。 We-DRIVE-Uは,平均的最適値$widetildemathcalObig(d H cdot min 1/rho, H/sqrtK big)$を満足するアルゴリズムを提案する。 また、新しいハードインスタンスを構築し、この設定で最初の情報理論の下界を導出する。
  論文  参考訳（メタデータ） (2024-09-30T17:21:15Z)
• 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)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)

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

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