論文の概要: Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs
with Short Burn-In Time
- arxiv url: http://arxiv.org/abs/2305.15546v1
- Date: Wed, 24 May 2023 20:22:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 18:52:08.936565
- Title: Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs
with Short Burn-In Time
- Title(参考訳): バーンイン時間を短縮した割引mdpのモデルフリー強化学習
- Authors: Xiang Ji, Gen Li
- Abstract要約: 本稿では,分散削減を利用したモデルフリーアルゴリズムと,実行方針を低速かつ適応的に切り替える新しい手法を提案する。
これは割引設定における最初の後悔の最適モデルフリーアルゴリズムであり、バーンイン時間の短縮によるメリットがある。
- 参考スコア(独自算出の注目度): 13.947875780164775
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A crucial problem in reinforcement learning is learning the optimal policy.
We study this in tabular infinite-horizon discounted Markov decision processes
under the online setting. The existing algorithms either fail to achieve regret
optimality or have to incur a high memory and computational cost. In addition,
existing optimal algorithms all require a long burn-in time in order to achieve
optimal sample efficiency, i.e., their optimality is not guaranteed unless
sample size surpasses a high threshold. We address both open problems by
introducing a model-free algorithm that employs variance reduction and a novel
technique that switches the execution policy in a slow-yet-adaptive manner.
This is the first regret-optimal model-free algorithm in the discounted
setting, with the additional benefit of a low burn-in time.
- Abstract(参考訳): 強化学習における重要な問題は、最適方針の学習である。
本研究は,オンライン環境下でのテーブル型無限ホライゾンディスカウントマルコフ決定プロセスで行った。
既存のアルゴリズムは、後悔の最適性を達成できないか、高いメモリと計算コストを発生させるかのいずれかである。
さらに、既存の最適アルゴリズムはすべて、最適なサンプル効率を達成するために長いバーンイン時間を必要とし、すなわち、サンプルサイズが高い閾値を超えない限り、その最適性は保証されない。
分散削減を用いたモデルフリーなアルゴリズムと,実行ポリシーを緩やかに切り換える新しい手法を導入することで,オープンな問題を両立する。
これは割引設定における最初の後悔の最適モデルフリーアルゴリズムであり、バーンイン時間の短縮によるメリットがある。
関連論文リスト
- Accelerated First-Order Optimization under Nonlinear Constraints [97.16266088683061]
制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。
これらのアルゴリズムの重要な性質は制約の数である。
我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Bring Your Own Algorithm for Optimal Differentially Private Stochastic
Minimax Optimization [44.52870407321633]
これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。
微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。
我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
論文 参考訳(メタデータ) (2022-06-01T10:03:20Z) - Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
オンライン学習における自由とは、後ろ向きの最適決定に対するアルゴリズムの適応性を指す。
本稿では,パラメータフリーで要求される楽観的な更新を,スイッチングコストを前提として,そのようなアルゴリズムを設計する。
本稿では,オンライン線形最適化 (OLO) のための簡易かつ強力なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-13T18:44:27Z) - Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。
そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。
後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
論文 参考訳(メタデータ) (2022-03-19T13:39:49Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes [4.355567556995855]
ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。
標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
論文 参考訳(メタデータ) (2021-03-23T00:28:15Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
政治政策の最適化は強化学習において難しい問題である。
オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
論文 参考訳(メタデータ) (2020-09-14T16:22:46Z) - Better Parameter-free Stochastic Optimization with ODE Updates for
Coin-Betting [31.60239268539764]
PFSGDアルゴリズムは最適理論性能を達成しながら、学習速度の設定を必要としない。
そこで本稿では, トランク型モデル上での連続時間Coin-Bettingに基づく新しいパラメータフリーアルゴリズムにより, 経験的ギャップを埋める。
この新しいパラメータフリーアルゴリズムは「最良のデフォルト」学習率でアルゴリズムを上回り、チューニングの必要なく微調整されたベースラインの性能とほぼ一致していることを示す。
論文 参考訳(メタデータ) (2020-06-12T23:10:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。