Accelerating Optimization and Reinforcement Learning with Quasi Stochastic Approximation
Accelerating Optimization and Reinforcement Learning with Quasi Stochastic Approximation
复制标题
使用准随机逼近加速优化和强化学习
DOI：
10.23919/acc50511.2021.9482825
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sean P. Meyn
中科院分区：
文献类型：
--
作者：
Shuhang Chen;Adithya M. Devraj;A. Bernstein;Sean P. Meyn
本文旨在获得准随机逼近（QSA）的精确收敛率，并将其应用于优化和强化学习。主要贡献是在一般非线性算法的假设下，在最优参数 $\theta^{\ast}$ 附近存在明确定义的线性化，并使用 Hurwitz 线性化矩阵 $A^{\ast}$。受限于算法的稳定性（本文调查了一般条件）： (i)如果算法增益选择为 $a_{t}=g/(1+t)^{\rho}$，其中 $g > 0$ 且 $\rho\in(0,1)$，则获得“有限 t”近似值 \begin{equation*} a_{t}^{-1}\{\Theta_{t}-\theta^{\ast}\}=\bar{Y}+\Xi_{t}^{\mathrm{I}}+o(1) \end{equation*} 其中 $\Theta_{t}$ 是参数估计，$\bar{Y}\in \mathbb{R}^{d}$ 是论文中确定的向量，并且$\{\Xi_{t}^{\mathrm{I}}\}$ 以零均值为界。 (ii) 在 $I+gA^{\ast}$ 是 Hurwitz 的更强假设下，$a_{t}=g/(1+t)$ 的近似继续成立。 (iii) 将 Ruppert-Polyak 平均技术扩展到此设置，其中使用 (i) 中的增益获得估计值 $\{\Theta_{t}\}$，并将 $\Theta_{t}^{\mathbf{RP}}$ 定义为运行平均值。当且仅当$\bar{Y}=0$时，收敛率为$1/t$。 (iv)通过无梯度优化和强化学习的策略梯度算法的应用来说明该理论。
The paper sets out to obtain precise convergence rates for quasi-stochastic approximation (QSA), with applications to optimization and reinforcement learning. The main contributions are obtained for general nonlinear algorithms, under the assumption that there is a well defined linearization near the optimal parameter $\theta^{\ast}$, with Hurwitz linearization matrix $A^{\ast}$. Subject to stability of the algorithm (general conditions are surveyed in the paper): (i)If the algorithm gain is chosen as $a_{t}=g/(1+t)^{\rho}$ with $g > 0$ and $\rho\in(0,1)$, then a “finite-t” approximation is obtained \begin{equation*} a_{t}^{-1}\{\Theta_{t}-\theta^{\ast}\}=\bar{Y}+\Xi_{t}^{\mathrm{I}}+o(1) \end{equation*} where $\Theta_{t}$ is the parameter estimate, $\bar{Y}\in \mathbb{R}^{d}$ is a vector identified in the paper, and $\{\Xi_{t}^{\mathrm{I}}\}$ is bounded with zero mean. (ii)The approximation continues to hold with $a_{t}=g/(1+t)$ under the stronger assumption that $I+gA^{\ast}$ is Hurwitz. (iii)The Ruppert-Polyak averaging technique is extended to this setting, in which the estimates $\{\Theta_{t}\}$ are obtained using the gain in (i), and $\Theta_{t}^{\mathbf{RP}}$ is defined to be the running average. The convergence rate is $1/t$ if and only if $\bar{Y}=0$. (iv)The theory is illustrated with applications to gradient-free optimization, and policy gradient algorithms for reinforcement learning.
DOI：
--
发表时间：
2020-02
期刊：
ArXiv
影响因子：
--
作者：
Shuhang Chen;Adithya M. Devraj;A. Bušić;Sean P. Meyn
通讯作者：
Shuhang Chen;Adithya M. Devraj;A. Bušić;Sean P. Meyn
DOI：
10.23919/acc45564.2020.9147814
发表时间：
2019-09
期刊：
2020 American Control Conference (ACC)
影响因子：
--
作者：
Yue-Chun Chen;A. Bernstein;Adithya M. Devraj;Sean P. Meyn
通讯作者：
Yue-Chun Chen;A. Bernstein;Adithya M. Devraj;Sean P. Meyn
DOI：
10.1109/cdc40024.2019.9029247
发表时间：
2019
期刊：
Proceedings of the IEEE Conference on Decision Control
影响因子：
--
作者：
Bernstein, Andrey;Chen, Yue;Colombino, Marcello;Dall'Anese, Emiliano;Mehta, Prashant;Meyn, Sean
通讯作者：
Meyn, Sean