Разработка и анализ алгоритмов для задачи оптимального управления и обучения с подкреплениемDevelopment and Theoretical Analysis of the Algorithms for Optimal Control and Reinforcement Learning

In this PhD dissertation, we address the problems of optimal stopping and learning in Markov decision processes used in reinforcement learning (RL). In the first direction, we derive complexity estimates for the algorithm called Weighted Stochastic Mesh (WSM) and give a new method for comparing the complexity of optimal stopping algorithms with the semi tractability index. We show that WSM is optimal with respect to this criterion when the commonly used regression methods are much less effective. For reinforcement learning, we give a non-asymptotic convergence analysis of a stochastic approximation scheme with two time scales - gradient TD - under assumptions of "martingale increment" noise - buffer replay - and of "Markov noise" (when learning is done along a single run). We obtain upper bounds that are rate-optimal by constructing an error expansion method that provides accurate control of the remainders terms. We also present a new algorithm for variance reduction in policy gradient schemes. The proposed approach is based on minimising an estimator for the empirical variance of the weighted rewards. We establish theoretical and practical gains over the classical actor-critic (A2C) method.