The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning

By Vivek Shripad Borkar, Sean P. Meyn. 2000

451 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Finance, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Finance

In Reinforcement Learning

Citations in the corpus

Gradient descent GAN optimization is locally stable (2017, methodology): “er come from the ﬁelds of stochastic approximation algorithm and the analysis of nonlinear differential equations – notably the “ODE method” for analyzing convergence properties of dynamical systems [Borkar and Meyn, 2000, Kushner and Yin, 2003]. Consider a general stochastic process driven by the u”
GANs Trained by a Two Time-Scale Update Rule Converge to a Nash Equilibrium (2017, background): “Since Adam can be expressed as differential equation and has a Lyapunov function, the idea of (T, δ) perturbed ODEs [7, 23, 8] carries over to Adam.”
On Convergence of Emphatic Temporal-Difference Learning (2015, background): “The stability criterion of (Borkar and Meyn, 2000) (see also (Borkar, 2008, Chap.”
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, methodology): “in focus of the current paper. 5 Related work The Q-learning algorithm and its variants. The Q-learning algorithm, originally proposed in Watkins (1989), has been analyzed in the asymptotic regime by Borkar and Meyn (2000); Jaakkola et al. (1994); Szepesvári (1998); Tsitsiklis (1994) since more than”
Reinforcement Learning: A Tutorial Survey and Recent Advances (2009, background): “A more general ODE result that can be used for both discounted and average reward cases was proposed later (Borkar and Meyn, 2000); this result employs notions of fluid limits (Dai and Meyn, 1995).”
On stochastic gradient and subgradient methods with adaptive steplength sequences (2011, unknown): “More recently, there has been a signiﬁcant interest in the application of ODE-based methods for investigating the stability and convergence of the associated stochastic approximation schemes [14], [15].”
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation (2018, methodology): “Most asymptotic convergence proofs in reinforcement learning use a technique known as the ODE method [Borkar and Meyn, 2000].”
A New Learning Algorithm for Optimal Stopping (2009, unknown): “q3;m(l)’3l(n;Xm))2( j(n + 1;X0 m+1) j(n;Xm)) +r m(j)) ( 12 )”
Empirical Dynamic Programming (2013, methodology): “method [28, 12], establishing rate of convergence has been quite di cult [22].”
Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents (2018, background): “It is usually veriﬁed separately using some other su ﬃ cient conditions (Borkar and Meyn, 2000; Andrieu et al., 2005).”
Distributed Policy Evaluation Under Multiple Behavior Strategies (2013, background): “, [8], [9], [48]) that simplifies the analys is because the tuples {xk,i,ak(i),xk,i+1, rk(i)} become i.”
GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium (2017, background): “According to Attouch et al. [3] the energy, that is, a Lyapunov function, is | | − | | Since Adam can be expressed as differential equation and has a Lyapunov function, the idea of ( T, δ ) perturbed ODEs [7, 22, 8] carries over to Adam.”
PAC Bounds for Multi-armed Bandit and Markov Decision Processes (2002, background): “This result was extended to more general settings in [5, 19, 6] and other algorithms as well (see [5] for a review).”
Zap Q-Learning (2017, methodology): “It is known that Watkins’ Q-learning algorithm can be regarded as a stochastic approximation method [26, 5] to obtain the solution θ∗ ∈ R to the steady-state mean equations, E [{ c(Xn, Un) + βQ θ∗(Xn+1)−Qθ ∗ (Xn, Un) } ζn(i) ] = 0, 1 ≤ i ≤ d (4) where {ζn} are d-dimensional Fn-measurable functions a”
Online Learning for Offloading and Autoscaling in Energy Harvesting Mobile Edge Computing (2017, unknown): “It is proven in [26] that the convergence of our proposed algorithm is equivalent to the convergence of the associated ordinary differential equation:”
Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time Popularities (2017, background): “Under this and the usual stochastic approximation conditions that will be specified later, Q̂t (·, ·) converges to Q∗ (·, ·) with probability 1; see [27] for a detailed description.”
Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems (2006, background): “Generic convergence rate bounds for stochastic approximation (e.g., Borkar and Meyn, 2000) or speciﬁc rates for Q-learning (see, Kearns and Singh, 1998, Even-Dar and Mansour, 2003) are somewhat disappointing.”