2019/11/06 by Othmane Mounjid, Mounjid, Othmane, Charles‐Albert Lehalle +1 · 1 citation
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1911.02319
openalex publication_date 2019/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper investigates to what extent one can improve reinforcement learning algorithms. Our study is split in three parts. First, our analysis shows that the classical asymptotic convergence rate O(1/√(N)) is pessimistic and can be replaced by O((log(N)/N)β) with (1)/(2)≤ β≤ 1 and N the number of iterations. Second, we propose a dynamic optimal policy for the choice of the learning rate (γk)k≥ 0 used in stochastic approximation (SA). We decompose our policy into two interacting levels: the inner and the outer level. In the inner level, we present the \namerefAlg:v4s algorithm (for "PAst Sign Search") which, based on a predefined sequence (γok)k≥ 0, constructs a new sequence (γik)k≥ 0 whose error decreases faster. In the outer level, we propose an optimal methodology for the selection of the predefined sequence (γok)k≥ 0. Third, we show empirically that our selection methodology of the learning rate outperforms significantly standard algorithms used in reinforcement learning (RL) in the three following applications: the estimation of a drift, the optimal placement of limit orders and the optimal execution of large number of shares.