論文の概要: Replicability in Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2305.19562v1
- Date: Wed, 31 May 2023 05:16:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 18:29:35.953445
- Title: Replicability in Reinforcement Learning
- Title（参考訳）: 強化学習における再現性
- Authors: Amin Karbasi, Grigoris Velegkas, Lin F. Yang, Felix Zhou
- Abstract要約: 生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。
ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
- 参考スコア（独自算出の注目度）: 45.99116106264407
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We initiate the mathematical study of replicability as an algorithmic
property in the context of reinforcement learning (RL). We focus on the
fundamental setting of discounted tabular MDPs with access to a generative
model. Inspired by Impagliazzo et al. [2022], we say that an RL algorithm is
replicable if, with high probability, it outputs the exact same policy after
two executions on i.i.d. samples drawn from the generator when its internal
randomness is the same. We first provide an efficient $\rho$-replicable
algorithm for $(\varepsilon, \delta)$-optimal policy estimation with sample and
time complexity $\widetilde
O\left(\frac{N^3\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$,
where $N$ is the number of state-action pairs. Next, for the subclass of
deterministic algorithms, we provide a lower bound of order
$\Omega\left(\frac{N^3}{(1-\gamma)^3\cdot\varepsilon^2\cdot\rho^2}\right)$.
Then, we study a relaxed version of replicability proposed by Kalavasis et al.
[2023] called TV indistinguishability. We design a computationally efficient TV
indistinguishable algorithm for policy estimation whose sample complexity is
$\widetilde
O\left(\frac{N^2\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$.
At the cost of $\exp(N)$ running time, we transform these TV indistinguishable
algorithms to $\rho$-replicable ones without increasing their sample
complexity. Finally, we introduce the notion of approximate-replicability where
we only require that two outputted policies are close under an appropriate
statistical divergence (e.g., Renyi) and show an improved sample complexity of
$\widetilde
O\left(\frac{N\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$.
- Abstract（参考訳）: 強化学習(RL)の文脈におけるアルゴリズム特性としての複製性に関する数学的研究を開始する。
生成モデルにアクセス可能なディスカウントタブ状MDPの基本的な設定に焦点をあてる。
Impagliazzoらにインスパイアされた。
2022] では、RLアルゴリズムが複製可能であるのは、高い確率で、内部ランダム性が同じ場合、ジェネレータから引き出されたサンプルを2回実行した後で全く同じポリシーを出力した場合である。
まず、(\varepsilon, \delta)$-optimal Policy Estimation with sample and time complexity $\widetilde O\left(\frac{N^3\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2right)$に対して効率的な$\rho$-replicableアルゴリズムを提供する。
次に、決定論的アルゴリズムのサブクラスに対して、次数 $\Omega\left(\frac{N^3}{(1-\gamma)^3\cdot\varepsilon^2\cdot\rho^2}\right)$ の下界を与える。
そこで,Kalavasisらによって提案されたレプリカ化の緩和版について検討した。
【2023年】テレビの区別がつかない。
計算効率のよいテレビ識別可能アルゴリズムを設計し、サンプルの複雑さを$\widetilde O\left(\frac{N^2\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$とする。
実行時間$\exp(N)$のコストで、これらのテレビの区別できないアルゴリズムを、サンプルの複雑さを増大させることなく$\rho$-replicableに変換する。
最後に、2つの出力されたポリシーが適切な統計的発散(例えば、Renyi)の下で近いことを要求し、$\widetilde O\left(\frac{N\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$の改善されたサンプル複雑性を示す。
関連論文リスト
- Replicable Uniformity Testing [1.5883812630616523]
この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。
我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
論文 参考訳（メタデータ） (2024-10-12T02:55:17Z) - Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization [28.497079108813924]
本研究では,滑らかでも凸でもない実験対象に対して,DP最適化アルゴリズムについて検討する。
1/alphabeta3+d/epsilonalphabeta2+d3/4/epsilonalpha1/2beta3/2right)$を返却するシングルパス$(alpha,beta)$-DPアルゴリズムを提供する。
次に、サンプルの複雑さを$widetildeOmegaleft()に改善するマルチパス時間アルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-10-08T10:15:49Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - 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) - 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) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。