論文の概要: Nonstationary Reinforcement Learning with Linear Function Approximation
- arxiv url: http://arxiv.org/abs/2010.04244v3
- Date: Sat, 13 Apr 2024 06:52:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 00:52:57.688794
- Title: Nonstationary Reinforcement Learning with Linear Function Approximation
- Title(参考訳): 線形関数近似を用いた非定常強化学習
- Authors: Huozhi Zhou, Jinglin Chen, Lav R. Varshney, Ashish Jagmohan,
- Abstract要約: ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。
まず、周期的再起動を伴う最小二乗値の楽観的な修正を開発し、変動予算が分かっている場合にその動的後悔を束縛する。
非定常線型 MDP に対する最初の minimax dynamic regret lower bound を導出し、副生成物として Jin らによって未解決の線型 MDP に対する minimax regret lower bound を定めている。
- 参考スコア(独自算出の注目度): 19.521419943509784
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider reinforcement learning (RL) in episodic Markov decision processes (MDPs) with linear function approximation under drifting environment. Specifically, both the reward and state transition functions can evolve over time but their total variations do not exceed a $\textit{variation budget}$. We first develop $\texttt{LSVI-UCB-Restart}$ algorithm, an optimistic modification of least-squares value iteration with periodic restart, and bound its dynamic regret when variation budgets are known. Then we propose a parameter-free algorithm $\texttt{Ada-LSVI-UCB-Restart}$ that extends to unknown variation budgets. We also derive the first minimax dynamic regret lower bound for nonstationary linear MDPs and as a byproduct establish a minimax regret lower bound for linear MDPs unsolved by Jin et al. (2020). Finally, we provide numerical experiments to demonstrate the effectiveness of our proposed algorithms.
- Abstract(参考訳): ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習(RL)について考察する。
具体的には、報酬関数と状態遷移関数の両方が時間とともに進化するが、その総変分は$\textit{variation budget}$を超えない。
このアルゴリズムは, 周期的再起動による最小二乗値反復の楽観的な修正であり, 変動予算が分かっていれば, その動的後悔を和らげるものである。
次にパラメータフリーアルゴリズム $\texttt{Ada-LSVI-UCB-Restart}$ を提案する。
また、非定常線形 MDP に対する最初の minimax dynamic regret lower bound を導出し、Jin et al (2020) によって未解決の線型 MDP に対する minimax regret lower bound を副生成物として確立する。
最後に,提案アルゴリズムの有効性を示す数値実験を行った。
関連論文リスト
- Settling Constant Regrets in Linear Markov Decision Processes [57.34287648914407]
強化学習(RL)における絶え間ない後悔の保証について検討する。
我々は不特定線形マルコフ決定過程(MDP)に対するアルゴリズムCert-LSVI-UCBを導入する。
Cert-LSVI-UCB は $tildemathcalO(d3H5/Delta)$ の累積後悔と高い確率を持つ MDP に対して、$zeta$ が $tildemathcalO(Delta / (sqrtd) 以下であることを仮定する。
論文 参考訳(メタデータ) (2024-04-16T17:23:19Z) - Learning Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback [30.23951525723659]
本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。
政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
論文 参考訳(メタデータ) (2023-11-14T03:12:43Z) - Non-stationary Reinforcement Learning under General Function
Approximation [60.430936031067006]
まず,非定常MDPに対する動的ベルマンエルダー次元(DBE)と呼ばれる新しい複雑性指標を提案する。
提案する複雑性指標に基づいて,SW-OPEAと呼ばれる新しい信頼度セットに基づくモデルフリーアルゴリズムを提案する。
SW-OPEAは,変動予算がそれほど大きくない限り,有効に有効であることを示す。
論文 参考訳(メタデータ) (2023-06-01T16:19:37Z) - Provably Efficient Model-Free Algorithms for Non-stationary CMDPs [10.930095238723327]
非定常制約マルコフ決定過程におけるモデルフリー強化学習アルゴリズムについて検討した。
非定常環境では、累積変動が一定の変動予算を超えない限り、報酬、ユーティリティ関数、遷移カーネルは時間とともに任意に変化する。
本稿では,非定常CMDPに対するサブ線形後悔と制約違反をゼロとする,モデルフリーでシミュレータフリーなRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-10T06:33:38Z) - Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
本稿では,時間ホリゾン$H$において,エピソード数と線形数に切り替えコストの対数性を持たせることで,ほぼ最適の後悔を実現するアルゴリズムを提案する。
また、ELEANOR-LowSwitchingで使われる「二重化トリック」を一般化線形関数近似にさらに活用できることを示す。
論文 参考訳(メタデータ) (2023-02-24T05:14:27Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-21T00:17:24Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳(メタデータ) (2022-12-12T18:58:59Z) - Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究
OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。
我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文 参考訳(メタデータ) (2020-10-24T11:02:45Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z) - Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
有限水平強化学習(RL)における探索・探索ジレンマの検討
本稿では,ランダム化最小二乗値 (RLSVI) の楽観的な変種を紹介する。
マルコフ決定過程が低ランク遷移ダイナミクスを持つという仮定の下で、RSVIの頻繁な後悔は、$widetilde O(d2 H2 sqrtT)$$ d $ が特徴次元であり、$ H $ が地平線であり、$ T $ が総数であることを示す。
論文 参考訳(メタデータ) (2019-11-01T19:48:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。