Fugu-MT 論文翻訳(概要): Towards Minimax Optimality of Model-based Robust Reinforcement Learning

論文の概要: Towards Minimax Optimality of Model-based Robust Reinforcement Learning

arxiv url: http://arxiv.org/abs/2302.05372v3
Date: Thu, 6 Jun 2024 12:32:02 GMT
ステータス: 処理完了
システム内更新日: 2024-06-08 01:09:36.987744
Title: Towards Minimax Optimality of Model-based Robust Reinforcement Learning
Title（参考訳）: モデルに基づくロバスト強化学習の極小最適化に向けて
Authors: Pierre Clavier, Erwan Le Pennec, Matthieu Geist,
Abstract要約: EmphRobust discounted Markov Decision Processes (RMDPs) における$epsilon$-optimal Policy のサンプル複雑性について検討した。この問題は、非ロバストの場合において広く研究されており、$tildemathcalO(fracH4mid S mid2mid A midepsilon2)$サンプルが$epsilon$-Optimal Policyを提供し、最小限最適である。
参考スコア（独自算出の注目度）: 22.244735904754215
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the sample complexity of obtaining an $\epsilon$-optimal policy in \emph{Robust} discounted Markov Decision Processes (RMDPs), given only access to a generative model of the nominal kernel. This problem is widely studied in the non-robust case, and it is known that any planning approach applied to an empirical MDP estimated with $\tilde{\mathcal{O}}(\frac{H^3 \mid S \mid\mid A \mid}{\epsilon^2})$ samples provides an $\epsilon$-optimal policy, which is minimax optimal. Results in the robust case are much more scarce. For $sa$- (resp $s$-)rectangular uncertainty sets, the best known sample complexity is $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid^2\mid A \mid}{\epsilon^2})$ (resp. $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid^2\mid A \mid^2}{\epsilon^2})$), for specific algorithms and when the uncertainty set is based on the total variation (TV), the KL or the Chi-square divergences. In this paper, we consider uncertainty sets defined with an $L_p$-ball (recovering the TV case), and study the sample complexity of \emph{any} planning algorithm (with high accuracy guarantee on the solution) applied to an empirical RMDP estimated using the generative model. In the general case, we prove a sample complexity of $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid\mid A \mid}{\epsilon^2})$ for both the $sa$- and $s$-rectangular cases (improvements of $\mid S \mid$ and $\mid S \mid\mid A \mid$ respectively). When the size of the uncertainty is small enough, we improve the sample complexity to $\tilde{\mathcal{O}}(\frac{H^3 \mid S \mid\mid A \mid }{\epsilon^2})$, recovering the lower-bound for the non-robust case for the first time and a robust lower-bound when the size of the uncertainty is small enough.
Abstract（参考訳）: 我々は,名目カーネルの生成モデルにのみアクセス可能なMarkov Decision Processs (RMDPs) において,$\epsilon$-optimal Policy を得る際のサンプル複雑性について検討した。この問題は、非ロバストの場合において広く研究されており、$\tilde{\mathcal{O}}(\frac{H^3 \mid S \mid\mid A \mid}{\epsilon^2})と推定される経験的 MDP に適用される任意の計画的アプローチは、極小値が最適である$\epsilon$-optimal Policy を提供することが知られている。堅牢なケースの結果は、はるかに少ない。 Sa$- (resp $s$-) 矩形不確実集合に対して、最もよく知られたサンプル複雑性は$\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid S \mid A \mid}{\epsilon^2})$ (resp) である。 $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid^2\mid A \mid^2}{\epsilon^2})$) 特定のアルゴリズムに対して、不確実性集合が総変分(TV)、KL、またはチ二乗発散に基づいている場合。本稿では、$L_p$-ballで定義された不確実性集合について検討し、生成モデルを用いて推定した経験的RMDPに適用した「emph{any}計画アルゴリズム」のサンプル複雑性について検討する。一般の場合、サンプルの複雑さを$\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid\mid A \mid}{\epsilon^2})$と$s$-正方形の場合(それぞれ$\mid S \mid$と$\mid S \mid A \mid$)に証明する。不確実性の大きさが十分小さい場合には、サンプルの複雑さを$\tilde{\mathcal{O}}(\frac{H^3 \mid S \mid\mid A \mid }{\epsilon^2})$に改善し、不確実性のサイズが十分小さい場合には、初めて非破壊ケースの低いバウンドを回復する。

関連論文リスト

Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文参考訳（メタデータ） (2024-11-08T17:10:38Z)
Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-01T17:59:53Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-05-27T12:24:14Z)
Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文参考訳（メタデータ） (2023-10-13T03:08:59Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文参考訳（メタデータ） (2022-12-01T15:57:58Z)
Near-Optimal Model Discrimination with Non-Disclosure [19.88145627448243]
まず、二乗損失を持つよく特定された線形モデルについて考察する。類似した形態のサンプルの複雑さは、たとえ不特定であっても引き起こされる。
論文参考訳（メタデータ） (2020-12-04T23:52:54Z)
Proving Non-Inclusion of B\"uchi Automata based on Monte Carlo Sampling [19.09848789158933]
B"uchiautoa non-inclusion $mathcalL(mathcalA) notsubseteq mathcalL(mathcalB)$を証明するための具体的なアルゴリズムを提案する。 $mathsfIMC2$は、B"uchiautoaのインクルージョンに対する反例を見つける高速で信頼性の高い方法である。
論文参考訳（メタデータ） (2020-07-05T10:17:02Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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