論文の概要: Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2210.11604v3
• Date: Sun, 21 May 2023 21:06:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 05:26:34.546060
• Title: Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes
• Title（参考訳）: 潜在マルコフ決定過程に対する水平自由・可変依存強化学習
• Authors: Runlong Zhou, Ruosong Wang, Simon S. Du
• Abstract要約: 我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
• 参考スコア（独自算出の注目度）: 62.90204655228324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. We design a novel model-based algorithmic framework which can be instantiated with both a model-optimistic and a value-optimistic solver. We prove an $\tilde{O}(\sqrt{\mathsf{Var}^\star M \Gamma S A K})$ regret bound where $\tilde{O}$ hides logarithm factors, $M$ is the number of contexts, $S$ is the number of states, $A$ is the number of actions, $K$ is the number of episodes, $\Gamma \le S$ is the maximum transition degree of any state-action pair, and $\mathsf{Var}^\star$ is a variance quantity describing the determinism of the LMDP. The regret bound only scales logarithmically with the planning horizon, thus yielding the first (nearly) horizon-free regret bound for LMDP. This is also the first problem-dependent regret bound for LMDP. Key in our proof is an analysis of the total variance of alpha vectors (a generalization of value functions), which is handled with a truncation method. We complement our positive result with a novel $\Omega(\sqrt{\mathsf{Var}^\star M S A K})$ regret lower bound with $\Gamma = 2$, which shows our upper bound minimax optimal when $\Gamma$ is a constant for the class of variance-bounded LMDPs. Our lower bound relies on new constructions of hard instances and an argument inspired by the symmetrization technique from theoretical computer science, both of which are technically different from existing lower bound proof for MDPs, and thus can be of independent interest.
• Abstract（参考訳）: 潜在マルコフ決定過程(lmdps)における強化学習(rl)に対する後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる新しいモデルベースアルゴリズムフレームワークを設計する。 我々は、$\tilde{o}(\sqrt{\mathsf{var}^\star m \gamma s a k})$ regret bound where $\tilde{o}$ hides logarithm factors, $m$ is the number of contexts, $s$ is the number of states, $a$ is the number of action, $k$ is the number of episodes, $\gamma \le s$ is the maximum transition degree of any state-action pair, $\mathsf{var}^\star$ が lmdp の決定性を表す分散量であることを証明する。 後悔のバウンドは計画の地平線と対数的にしかスケールしないので、lmdpに対して最初の(ほぼ)地平線なしの後悔となる。 これはLMDPにとって初めての問題依存の後悔でもある。 この証明の鍵は、トランケーション法で処理されるαベクトルの全分散(値関数の一般化)の分析である。 我々は、新しい $\omega(\sqrt{\mathsf{var}^\star m s a k})$ regret lower bound with $\gamma = 2$ で正の結果を補完する。 我々の下界は、ハードインスタンスの新しい構成と、理論計算機科学の対称性技術に触発された議論に依存しており、どちらもMDPの既存の下界証明と技術的に異なるため、独立した関心を持つことができる。

関連論文リスト

• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
  エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。 提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
  論文  参考訳（メタデータ） (2023-10-23T18:52:17Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation [25.60689712525918]
  本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。 本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
  論文  参考訳（メタデータ） (2022-06-23T06:04:21Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• $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)

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

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