  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.
