論文の概要: A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost

• arxiv url: http://arxiv.org/abs/2101.00494v1
• Date: Sat, 2 Jan 2021 18:41:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-13 07:23:00.218144
• Title: A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Title（参考訳）: スイッチングコストの低い線形マルコフ決定過程の確率的効率的アルゴリズム
• Authors: Minbo Gao, Tianle Xie, Simon S. Du, Lin F. Yang
• Abstract要約: スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。 このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
• 参考スコア（独自算出の注目度）: 53.968049198926444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many real-world applications, such as those in medical domains, recommendation systems, etc, can be formulated as large state space reinforcement learning problems with only a small budget of the number of policy changes, i.e., low switching cost. This paper focuses on the linear Markov Decision Process (MDP) recently studied in [Yang et al 2019, Jin et al 2020] where the linear function approximation is used for generalization on the large state space. We present the first algorithm for linear MDP with a low switching cost. Our algorithm achieves an $\widetilde{O}\left(\sqrt{d^3H^4K}\right)$ regret bound with a near-optimal $O\left(d H\log K\right)$ global switching cost where $d$ is the feature dimension, $H$ is the planning horizon and $K$ is the number of episodes the agent plays. Our regret bound matches the best existing polynomial algorithm by [Jin et al 2020] and our switching cost is exponentially smaller than theirs. When specialized to tabular MDP, our switching cost bound improves those in [Bai et al 2019, Zhang et al 20020]. We complement our positive result with an $\Omega\left(dH/\log d\right)$ global switching cost lower bound for any no-regret algorithm.
• Abstract（参考訳）: 医療領域やレコメンデーションシステムなど、多くの現実世界のアプリケーションは、政策変更の数の小さな予算、すなわち、スイッチングコストの低減によって、大きな状態空間強化学習問題として定式化することができる。 本稿では, 線形マルコフ決定過程 (MDP) を最近の[Yang et al 2019, Jin et al 2020] で研究し, 大規模状態空間の一般化に線形関数近似を用いる。 スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。 我々のアルゴリズムは$\widetilde{O}\left(\sqrt{d^3H^4K}\right)$ regret bound with a near-optimal $O\left(d H\log K\right)$ global switch cost where $d$ is the feature dimension, $H$ is the planning horizon, $K$ is the number of the agent play。 我々の後悔の限界は[Jin et al 2020]による最高の多項式アルゴリズムと一致し、スイッチングコストは彼らのものよりも指数関数的に小さい。 表式MDPに特化すれば,[Bai et al 2019, Zhang et al 20020]の切り替えコストが向上します。 正の結果を$\Omega\left(dH/\log d\right)$大域的なスイッチングコストの低い非回帰アルゴリズムで補う。

関連論文リスト

• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
  本稿では,時間ホリゾン$H$において,エピソード数と線形数に切り替えコストの対数性を持たせることで,ほぼ最適の後悔を実現するアルゴリズムを提案する。 また、ELEANOR-LowSwitchingで使われる「二重化トリック」を一般化線形関数近似にさらに活用できることを示す。
  論文  参考訳（メタデータ） (2023-02-24T05:14:27Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost [31.04961854943877]
  我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。 副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2022-02-13T19:01:06Z)
• Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints [39.715977181666766]
  本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。 我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。 これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
  論文  参考訳（メタデータ） (2022-01-31T23:52:34Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)

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

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