Calendar Site

Loading Events

« All Events

  • This event has passed.

Concentration Bounds for Stochastic Approximation with Applications to Reinforcement Learning

November 8, 2017 @ 10:30 am - 11:30 am

Stochastic Approximation (SA) is useful in finding optimal points, or zeros of a function, given only noisy
estimates. In this talk, we will review our recent advances in techniques for SA analysis. In the first part, we
will see a motivating application of SA to network tomography and also discuss the convergence of a novel
stochastic Kaczmarz method. Next, we shall discuss a novel tool based on Alekseev’s formula to obtain rate
of convergence of a nonlinear SA to a specific solution, when there are multiple locally stable solutions. In
the third part, we shall extend the previous tool to the two timescale but linear SA setting, also discussing
how this tool applies to gradient Temporal Dierence (TD) methods such as GTD(0), GTD2, and TDC used in
reinforcement learning. For much of the foregoing analysis, the initial step size must be chosen suiciently
small, depending on unknown problem-dependent parameters. Since this is oen impractical, we finally
discuss a trick to obviate this in context of the one timescale, linear TD(0) method, and also provide a novel
expectation bound.


November 8, 2017
10:30 am - 11:30 am
Event Category:


AB 7/107