Fugu-MT 論文翻訳(概要): The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

論文の概要: The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

arxiv url: http://arxiv.org/abs/2110.14427v1
Date: Wed, 27 Oct 2021 13:38:25 GMT
ステータス: 処理完了
システム内更新日: 2021-10-28 19:00:41.075988
Title: The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning
Title（参考訳）: 確率近似と強化学習における漸近統計量のODE法
Authors: Vivek Borkar, Shuhang Chen, Adithya Devraj, Ioannis Kontoyiannis and Sean Meyn
Abstract要約: 本論文はマルコフ雑音による近似の収束と統計に関するものである。 $theta_n+1=theta_n + alpha_n + 1 f(theta_n, Phi_n+1),,quad nge 0, $$ in ここで各$theta_ninRed$は、固定分布$pi$と$f:Redtimes textX toReを持つ一般的な状態空間 X 上の Markov チェーンである。
参考スコア（独自算出の注目度）: 6.16852156844376
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The paper concerns convergence and asymptotic statistics for stochastic approximation driven by Markovian noise: $$ \theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \Phi_{n+1}) \,,\quad n\ge 0, $$ in which each $\theta_n\in\Re^d$, $ \{ \Phi_n \}$ is a Markov chain on a general state space X with stationary distribution $\pi$, and $f:\Re^d\times \text{X} \to\Re^d$. In addition to standard Lipschitz bounds on $f$, and conditions on the vanishing step-size sequence $\{\alpha_n\}$, it is assumed that the associated ODE is globally asymptotically stable with stationary point denoted $\theta^*$, where $\bar f(\theta)=E[f(\theta,\Phi)]$ with $\Phi\sim\pi$. Moreover, the ODE@$\infty$ defined with respect to the vector field, $$ \bar f_\infty(\theta):= \lim_{r\to\infty} r^{-1} \bar f(r\theta) \,,\qquad \theta\in\Re^d, $$ is asymptotically stable. The main contributions are summarized as follows: (i) The sequence $\theta$ is convergent if $\Phi$ is geometrically ergodic, and subject to compatible bounds on $f$. The remaining results are established under a stronger assumption on the Markov chain: A slightly weaker version of the Donsker-Varadhan Lyapunov drift condition known as (DV3). (ii) A Lyapunov function is constructed for the joint process $\{\theta_n,\Phi_n\}$ that implies convergence of $\{ \theta_n\}$ in $L_4$. (iii) A functional CLT is established, as well as the usual one-dimensional CLT for the normalized error $z_n:= (\theta_n-\theta^*)/\sqrt{\alpha_n}$. Moment bounds combined with the CLT imply convergence of the normalized covariance, $$ \lim_{n \to \infty} E [ z_n z_n^T ] = \Sigma_\theta, $$ where $\Sigma_\theta$ is the asymptotic covariance appearing in the CLT. (iv) An example is provided where the Markov chain $\Phi$ is geometrically ergodic but it does not satisfy (DV3). While the algorithm is convergent, the second moment is unbounded.
Abstract（参考訳）: この論文はマルコフ雑音によって引き起こされる確率近似の収束と漸近統計に関するものである:$$ \theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \Phi_{n+1}) \,,,\quad n\ge 0, $$$ in where each $\theta_n\in\Re^d$, $ \{ \Phi_n \}$は定常分布が$\pi$, $f:\Re^d\times \text{X} \to\Re^d$。標準的なリプシッツ束の$f$と消滅するステップサイズ列 $\{\alpha_n\}$ の条件に加えて、関連するODE が大域的に漸近的に安定であり、固定点が $\theta^*$ と書かれ、$\bar f(\theta)=E[f(\theta,\Phi)]$ が$\Phi\sim\pi$ と表される。さらに、ベクトル場に関して定義されるODE@$\infty$, $$ \bar f_\infty(\theta):= \lim_{r\to\infty} r^{-1} \bar f(r\theta) \,,,\qquad \theta\in\Re^d, $$は漸近安定である。主な貢献は以下のとおりである。 (i) 列 $\theta$ が収束するのは、$\Phi$ が幾何学的にエルゴード的であり、$f$ 上の互換境界を持つときである。残りの結果はマルコフ連鎖のより強い仮定の下で確立され、ドンスカー=ヴァラダン・リャプノフのドリフト条件(dv3)のわずかに弱いバージョンである。 (ii) Lyapunov 関数は、$L_4$ における$\{ \theta_n\}$ の収束を意味するジョイントプロセス $\{\theta_n,\Phi_n\}$ に対して構成される。 (iii)正規化エラー$z_n:= (\theta_n-\theta^*)/\sqrt{\alpha_n}$に対する通常の1次元CLTと同様に関数型CLTを確立する。モーメント境界と CLT は正規化共分散の収束を暗示し、$$ \lim_{n \to \infty} E [ z_n z_n^T ] = \Sigma_\theta, $$ ここで$\Sigma_\theta$ は CLT に現れる漸近共分散である。 (iv)マルコフ連鎖 $\Phi$ が幾何学的にエルゴード的であるが、満足しないような例(DV3)。アルゴリズムは収束するが、第2モーメントは非有界である。

論文の概要: The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

関連論文リスト