論文の概要: Replicability in Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2305.19562v2
- Date: Fri, 27 Oct 2023 23:53:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 21:51:04.239305
- Title: Replicability in Reinforcement Learning
- Title(参考訳): 強化学習における再現性
- Authors: Amin Karbasi, Grigoris Velegkas, Lin F. Yang, Felix Zhou
- Abstract要約: 生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。
ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
- 参考スコア(独自算出の注目度): 46.89386344741442
- 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)$の改善されたサンプル複雑性を示す。
関連論文リスト
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳(メタデータ) (2024-03-05T12:28:00Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳(メタデータ) (2021-03-17T18:18:57Z) - On Robust Optimal Transport: Computational Complexity, Low-rank
Approximation, and Barycenter Computation [14.80695185915604]
我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。
離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-13T03:55:52Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。