  In this paper we propose an efficient variance reduction approach for
additive functionals of Markov chains relying on a novel discrete time
martingale representation. Our approach is fully non-asymptotic and does not
require the knowledge of the stationary distribution (and even any type of
ergodicity) or specific structure of the underlying density. By rigorously
analyzing the convergence properties of the proposed algorithm, we show that
its cost-to-variance product is indeed smaller than one of the naive algorithm.
The numerical performance of the new method is illustrated for the
Langevin-type Markov Chain Monte Carlo (MCMC) methods.
