  Recent Reinforcement Learning (RL) algorithms making use of Kullback-Leibler
(KL) regularization as a core component have shown outstanding performance.
Yet, only little is understood theoretically about why KL regularization helps,
so far. We study KL regularization within an approximate value iteration scheme
and show that it implicitly averages q-values. Leveraging this insight, we
provide a very strong performance bound, the very first to combine two
desirable aspects: a linear dependency to the horizon (instead of quadratic)
and an error propagation term involving an averaging effect of the estimation
errors (instead of an accumulation effect). We also study the more general case
of an additional entropy regularizer. The resulting abstract scheme encompasses
many existing RL algorithms. Some of our assumptions do not hold with neural
networks, so we complement this theoretical analysis with an extensive
empirical study.
