Improving reinforcement learning algorithms: towards optimal learning
  rate policies
  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.
