Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity
This paper proposes to develop a new variant of the two-time-scale stochastic approximation to find the roots of two coupled nonlinear operators, assuming only noisy samples of these operators can be observed. Our key idea is to leverage the classic Ruppert-Polyak averaging technique to dynamically estimate the operators through their samples. The estimated values of these averaging steps will then be used in the two-time-scale stochastic approximation updates to find the desired solution. Our main theoretical result is to show that under the strongly monotone condition of the underlying nonlinear operators the mean-squared errors of the iterates generated by the proposed method converge to zero at an optimal rate $O(1/k)$, where $k$ is the number of iterations. Our result significantly improves the existing result of two-time-scale stochastic approximation, where the best known finite-time convergence rate is $O(1/k^{2/3})$. We illustrate this result by applying the proposed method to develop new reinforcement learning algorithms with improved performance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
Two-time-scale stochastic approximation, a generalized version of the popular stochastic approximation, has found broad applications in many areas including stochastic control, optimization, and machine learning. Despite…
Vocal Bursts Valence PredictionActor-Critic or Critic-Actor? A Tale of Two Time Scales
We revisit the standard formulation of tabular actor-critic algorithm as a two time-scale stochastic approximation with value function computed on a faster time-scale and policy computed on a slower time-scale. This emul…
Vocal Bursts Valence PredictionSub- and Super-solution Approach to Accuracy Analysis of Portfolio Optimization Asymptotics in Multiscale Stochastic Factor Market
The problem of portfolio optimization when stochastic factors drive returns and volatilities has been studied in previous works by the authors. In particular, they proposed asymptotic approximations for value functions a…
Portfolio OptimizationFinite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation
Whittle index policy is a heuristic to the intractable restless multi-armed bandits (RMAB) problem. Although it is provably asymptotically optimal, finding Whittle indices remains difficult. In this paper, we present Neu…
Multi-Armed BanditsQ-LearningNonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It
Recent finite-time analyses of nonlinear two-time-scale stochastic approximation show that under contractive assumptions the slow iterate $Y_k$ with stepsizes $β_k=Θ(k^{-1})$ and $α_k=Θ(k^{-a})$, $a\in(1/2,1)$, generally…