Algorithms for Stochastic Optimization Statistical Estimation and Markov Decision Processes

Abstract

Stochastic approximation deals with the problem of finding zeros of a function expressed as an expectation of a random variable. In this thesis we propose convergent algorithms for problems in optimization, statistical estimation and reinforcement learning. We first formulate these problems in the stochastic approximation setting. Subsequently we utilize the ordinary differential equations based analysis of stochastic approximation algorithms to prove the convergence of our proposed algorithms. Additionally we explore second order methods in the context of Markov Decision Processes. Through experimental evaluations, we validate our theoretical results. First, we consider a Stochastic Optimization (SO) problem where the aim is to optimize a given objective function in the presence of noise. Most of the solution techniques in SO estimate gradients from the noise corrupted observations of the objective and adjust parameters of the objective along the direction of the estimated gradients to obtain locally optimal solutions. Two prominent algorithms in SO namely Random Direction Kiefer-Wolfowitz (RDKW) and Simultaneous Perturbation Stochastic Approximation (SPSA) obtain noisy gradient estimates by randomly perturbing all the parameters simultaneously. This forces the search direction to be random in these algorithms and causes them to suffer additional noise on top of the noise incurred from the samples of the objective. Owing to this additional noise, the idea of using deterministic perturbations instead of random perturbations for gradient estimation has also been studied in the past. Specifically, two constructions of the deterministic perturbation sequence using lexicographical ordering and Hadamard matrices have been explored in the context of SPSA algorithms and encouraging results have been reported in the literature. In our work, we characterize the class of deterministic perturbation sequences that can be utilized in the RDKW algorithm...