論文の概要: First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach
- arxiv url: http://arxiv.org/abs/2112.03432v1
- Date: Tue, 7 Dec 2021 00:29:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-08 13:53:49.572027
- Title: First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach
- Title(参考訳): 線形関数近似を用いた強化学習における一次回帰:ロバスト推定手法
- Authors: Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S. Du, Kevin
Jamieson
- Abstract要約: 我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
- 参考スコア(独自算出の注目度): 57.570201404222935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Obtaining first-order regret bounds -- regret bounds scaling not as the
worst-case but with some measure of the performance of the optimal policy on a
given instance -- is a core question in sequential decision-making. While such
bounds exist in many settings, they have proven elusive in reinforcement
learning with large state spaces. In this work we address this gap, and show
that it is possible to obtain regret scaling as $\mathcal{O}(\sqrt{V_1^\star
K})$ in reinforcement learning with large state spaces, namely the linear MDP
setting. Here $V_1^\star$ is the value of the optimal policy and $K$ is the
number of episodes. We demonstrate that existing techniques based on least
squares estimation are insufficient to obtain this result, and instead develop
a novel robust self-normalized concentration bound based on the robust Catoni
mean estimator, which may be of independent interest.
- Abstract(参考訳): 最短ケースではなく、あるインスタンス上での最適なポリシーのパフォーマンスを測った、後悔の限界である一階の後悔の限界を達成することは、シーケンシャルな意思決定における中核的な問題である。
このような境界は、多くの設定に存在しているが、それらは大きな状態空間を持つ強化学習において解明されている。
本研究では, このギャップに対処し, 線形 MDP 設定による強化学習において, $\mathcal{O}(\sqrt{V_1^\star K})$ として後悔のスケーリングが得られることを示す。
ここで$v_1^\star$は最適ポリシーの値、$k$はエピソード数である。
この結果を得るためには, 最小二乗推定に基づく既存手法が不十分であることを示すとともに, 独立興味を持つロバストなカトーニ平均推定値に基づく新しいロバストな自己正規化濃度を求める。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。
AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-10-04T17:11:15Z) - Provably Efficient Model-Free Constrained RL with Linear Function
Approximation [4.060731229044571]
我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。
本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
論文 参考訳(メタデータ) (2022-06-23T17:54:31Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55:55Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳(メタデータ) (2021-03-24T10:11:49Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。