論文の概要: Fast Rates for the Regret of Offline Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2102.00479v1
• Date: Sun, 31 Jan 2021 16:17:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-02 16:55:43.232245
• Title: Fast Rates for the Regret of Offline Reinforcement Learning
• Title（参考訳）: オフライン強化学習における後悔の速さ
• Authors: Yichun Hu, Nathan Kallus, Masatoshi Uehara
• Abstract要約: 無限水平割引マルコフ決定過程(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
• 参考スコア（独自算出の注目度）: 82.49300293077583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the regret of reinforcement learning from offline data generated by a fixed behavior policy in an infinite-horizon discounted Markov decision process (MDP). While existing analyses of common approaches, such as fitted $Q$-iteration (FQI), suggest a $O(1/\sqrt{n})$ convergence for regret, empirical behavior exhibits much faster convergence. In this paper, we present a finer regret analysis that exactly characterizes this phenomenon by providing fast rates for the regret convergence. First, we show that given any estimate for the optimal quality function $Q^*$, the regret of the policy it defines converges at a rate given by the exponentiation of the $Q^*$-estimate's pointwise convergence rate, thus speeding it up. The level of exponentiation depends on the level of noise in the decision-making problem, rather than the estimation problem. We establish such noise levels for linear and tabular MDPs as examples. Second, we provide new analyses of FQI and Bellman residual minimization to establish the correct pointwise convergence guarantees. As specific cases, our results imply $O(1/n)$ regret rates in linear cases and $\exp(-\Omega(n))$ regret rates in tabular cases.
• Abstract（参考訳）: 無限水平割引マルコフ決定プロセス(MDP)における固定行動政策によって生成されたオフラインデータからの強化学習の後悔について研究する。 適合した$Q$-イテレーション(FQI)のような一般的なアプローチの既存の分析は、後悔のために$O(1/\sqrt{n})$収束を示唆するが、経験的行動ははるかに速い収束を示す。 本稿では,後悔の収束速度を速くすることで,この現象を正確に特徴づける,より細かい後悔の分析を行う。 まず、最適品質関数 $Q^*$ の任意の推定値を考えると、それが定義するポリシーの後悔は、$Q^*$-推定値の点収束率の指数付けによって与えられた速度で収束し、それによってそれを高速化する。 指数のレベルは、推定問題ではなく、意思決定問題における雑音のレベルに依存する。 線形および表式MDPのノイズレベルを例に挙げます。 第二に、FQIとベルマン残差最小化の新しい分析を行い、正しい点収束保証を確立する。 具体例では, 線形症例では$O(1/n)=後悔率, 表例では$\exp(-\Omega(n))$後悔率は$O(1/n)。

関連論文リスト

• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• On the Linear Convergence of Policy Gradient under Hadamard Parameterization [4.182089296199263]
  本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。 すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
  論文  参考訳（メタデータ） (2023-05-31T05:51:15Z)
• On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluation [1.575865518040625]
  連続状態と行動を伴う無限水平マルコフ決定過程における非政治評価問題について検討する。 我々は、$Q$関数推定を非パラメトリックインスツルメンタル変数(NPIV)推定問題の特別な形式に再キャストする。
  論文  参考訳（メタデータ） (2022-01-17T01:09:38Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
  一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。 SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
  論文  参考訳（メタデータ） (2020-06-14T11:12:05Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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