論文の概要: Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2210.08238v1
• Date: Sat, 15 Oct 2022 09:22:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-18 20:14:02.646194
• Title: Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
• Title（参考訳）: マルチバッチ強化学習における近似的後悔限界
• Authors: Zihan Zhang, Yuhang Jiang, Yuan Zhou and Xiangyang Ji
• Abstract要約: 本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
• 参考スコア（独自算出の注目度）: 54.806166861456035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. The multi-batch reinforcement learning framework, where the agent is required to provide a time schedule to update policy before everything, which is particularly suitable for the scenarios where the agent suffers extensively from changing the policy adaptively. Given a finite-horizon MDP with $S$ states, $A$ actions and planning horizon $H$, we design a computational efficient algorithm to achieve near-optimal regret of $\tilde{O}(\sqrt{SAH^3K\ln(1/\delta)})$\footnote{$\tilde{O}(\cdot)$ hides logarithmic terms of $(S,A,H,K)$} in $K$ episodes using $O\left(H+\log_2\log_2(K) \right)$ batches with confidence parameter $\delta$. To our best of knowledge, it is the first $\tilde{O}(\sqrt{SAH^3K})$ regret bound with $O(H+\log_2\log_2(K))$ batch complexity. Meanwhile, we show that to achieve $\tilde{O}(\mathrm{poly}(S,A,H)\sqrt{K})$ regret, the number of batches is at least $\Omega\left(H/\log_A(K)+ \log_2\log_2(K) \right)$, which matches our upper bound up to logarithmic terms. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore over the unlearned states; 2) an computational efficient algorithm to explore certain directions with an approximated transition model.
• Abstract（参考訳）: 本稿では,有限水平マルコフ決定過程(MDPs)をモデルとした漸進的強化学習(RL)問題をバッチ数に制約を加えて検討する。 このマルチバッチ強化学習フレームワークは、エージェントがポリシーを事前に更新するための時間スケジュールを提供する必要があるが、エージェントがポリシーを適応的に変更することに苦しむようなシナリオに特に適している。 s$ state, $a$ actions and planning horizon $h$ の有限ホリゾン mdp が与えられると、$o\left(h+\log_2\log_2(k) \right)$k$ を用いた$k$エピソードで$\tilde{o}(\sqrt{sah^3k\ln(1/\delta)})$\footnote{$\tilde{o}(\cdot)$ 対数項$(s,a,h,k)$} の計算効率の高いアルゴリズムを設計する。 我々の知る限り、最初の$\tilde{O}(\sqrt{SAH^3K})$ regret bound with $O(H+\log_2\log_2(K))$ batch complexityである。 一方、$\tilde{o}(\mathrm{poly}(s,a,h)\sqrt{k})$ regretを達成するために、バッチの数は少なくとも$\omega\left(h/\log_a(k)+ \log_2\log_2(k) \right)$であり、これは我々の上限を対数項に一致する。 私たちの技術貢献は2つあります。 1) 未発見の状態を探索するための最適に近い設計計画 2)近似遷移モデルを用いてある方向を探索する計算効率のよいアルゴリズム。

関連論文リスト

• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints [21.412085244757336]
  適応性制約を伴うマルチエージェント強化学習(MARL)の問題について検討する。 2つのプレイヤーゼロサムマルコフゲームに対して、$widetildeO(sqrtH3 S2 ABK)$を後悔する(政治)排除に基づくアルゴリズムを設計する。 バッチ複雑性の低い$Omega(fracHlog_AK+loglog K)$を$widetildeO(sqrtK)$で証明する。
  論文  参考訳（メタデータ） (2024-02-02T03:00:40Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost [31.04961854943877]
  我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。 副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2022-02-13T19:01:06Z)
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints [94.76881135901753]
  一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。 提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。 まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
  論文  参考訳（メタデータ） (2021-01-06T18:56:07Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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