論文の概要: Non-asymptotic Performances of Robust Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2105.03863v1
- Date: Sun, 9 May 2021 07:40:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-11 15:16:54.092010
- Title: Non-asymptotic Performances of Robust Markov Decision Processes
- Title(参考訳): ロバストマルコフ決定プロセスの非漸近的性能
- Authors: Wenhao Yang, Zhihua Zhang
- Abstract要約: 真の遷移ダイナミクスを持つロバスト値関数に対する最適ポリシーの非漸近的性能について検討する。
最適なロバストポリシは、真の遷移ダイナミクスにアクセスせずに生成モデルやオフラインデータセットから解決される。
- 参考スコア(独自算出の注目度): 23.68403314354797
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the non-asymptotic performance of optimal policy on
robust value function with true transition dynamics. The optimal robust policy
is solved from a generative model or offline dataset without access to true
transition dynamics. In particular, we consider three different uncertainty
sets including the $L_1$, $\chi^2$ and KL balls in both $(s,a)$-rectangular and
$s$-rectangular assumptions. Our results show that when we assume
$(s,a)$-rectangular on uncertainty sets, the sample complexity is about
$\widetilde{O}\left(\frac{|\mathcal{S}|^2|\mathcal{A}|}{\varepsilon^2\rho^2(1-\gamma)^4}\right)$
in the generative model setting and
$\widetilde{O}\left(\frac{|\mathcal{S}|}{\nu_{\min}\varepsilon^2\rho^2(1-\gamma)^4}\right)$
in the offline dataset setting. While prior works on non-asymptotic
performances are restricted with the KL ball and $(s,a)$-rectangular
assumption, we also extend our results to a more general $s$-rectangular
assumption, which leads to a larger sample complexity than the
$(s,a)$-rectangular assumption.
- Abstract(参考訳): 本稿では,真の遷移ダイナミクスを持つロバスト値関数に対する最適ポリシーの非漸近的性能について検討する。
最適なロバストポリシは、真の遷移ダイナミクスにアクセスせずに生成モデルやオフラインデータセットから解決される。
特に、$(s,a)$-rectangular と $s$-rectangular の両方において、$l_1$、$\chi^2$、kl 球を含む3つの異なる不確実性集合を考える。
我々の結果は、不確実性集合上で$(s,a)$-rectangularを仮定すると、サンプルの複雑さは約$\widetilde{O}\left(\frac{|\mathcal{S}|^2|\mathcal{A}|}{\varepsilon^2\rho^2(1-\gamma)^4}\right)$および$\widetilde{O}\left(\frac{|\mathcal{S}|}{\nu_{\min}\varepsilon^2\rho^2(1-\gamma)^4}\right)$であることを示している。
非漸近的パフォーマンスに関する先行研究は、klボールと$(s,a)$-rectangular の仮定で制限されているが、より一般的な $s$-rectangular の仮定にも拡張し、$(s,a)$-rectangular の仮定よりも大きなサンプルの複雑さをもたらす。
関連論文リスト
- Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳(メタデータ) (2023-06-28T17:43:19Z) - Learning linear dynamical systems under convex constraints [5.025654873456756]
線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。
フロベニウスノルムの非漸近誤差境界は、$A*$で$mathcalK$の局所サイズに依存する。
論文 参考訳(メタデータ) (2023-03-27T11:49:40Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳(メタデータ) (2022-09-30T04:15:44Z) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳(メタデータ) (2022-04-22T07:03:13Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳(メタデータ) (2021-05-28T17:49:39Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳(メタデータ) (2021-01-29T18:57:52Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - How isotropic kernels perform on simple invariants [0.5729426778193397]
等方性カーネル手法のトレーニング曲線は、学習すべきタスクの対称性に依存するかを検討する。
大規模な帯域幅では、$beta = fracd-1+xi3d-3+xi$, where $xiin (0,2)$ がカーネルのストライプを原点とする指数であることを示す。
論文 参考訳(メタデータ) (2020-06-17T09:59:18Z) - 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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。