Improving reinforcement learning algorithms: towards optimal learning
rate policies
rate policies
File(s)
Working paper
Author(s)
Mounjid, Othmane
Lehalle, Charles-Albert
Type
Working Paper
Abstract
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/\sqrt{N})$ is pessimistic and
can be replaced by $O((\log(N)/N)^{\beta})$ with $\frac{1}{2}\leq \beta \leq 1$
and $N$ the number of iterations. Second, we propose a dynamic optimal policy
for the choice of the learning rate $(\gamma_k)_{k\geq 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
\nameref{Alg:v_4_s} algorithm (for "PAst Sign Search") which, based on a
predefined sequence $(\gamma^o_k)_{k\geq 0}$, constructs a new sequence
$(\gamma^i_k)_{k\geq 0}$ whose error decreases faster. In the outer level, we
propose an optimal methodology for the selection of the predefined sequence
$(\gamma^o_k)_{k\geq 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.
algorithms. Our study is split in three parts. First, our analysis shows that
the classical asymptotic convergence rate $O(1/\sqrt{N})$ is pessimistic and
can be replaced by $O((\log(N)/N)^{\beta})$ with $\frac{1}{2}\leq \beta \leq 1$
and $N$ the number of iterations. Second, we propose a dynamic optimal policy
for the choice of the learning rate $(\gamma_k)_{k\geq 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
\nameref{Alg:v_4_s} algorithm (for "PAst Sign Search") which, based on a
predefined sequence $(\gamma^o_k)_{k\geq 0}$, constructs a new sequence
$(\gamma^i_k)_{k\geq 0}$ whose error decreases faster. In the outer level, we
propose an optimal methodology for the selection of the predefined sequence
$(\gamma^o_k)_{k\geq 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.
Date Issued
2020-04-21
Citation
2020
Publisher
arXiv
Copyright Statement
© 2020 The Author(s)
Identifier
http://arxiv.org/abs/1911.02319v4
Subjects
cs.LG
cs.LG
math.OC
stat.ML
Publication Status
Published