  Policy evaluation is an important instrument for the comparison of different
algorithms in Reinforcement Learning (RL). Yet even a precise knowledge of the
value function $V^{\pi}$ corresponding to a policy $\pi$ does not provide
reliable information on how far is the policy $\pi$ from the optimal one. We
present a novel model-free upper value iteration procedure $({\sf UVIP})$ that
allows us to estimate the suboptimality gap $V^{\star}(x) - V^{\pi}(x)$ from
above and to construct confidence intervals for $V^\star$. Our approach relies
on upper bounds to the solution of the Bellman optimality equation via
martingale approach. We provide theoretical guarantees for ${\sf UVIP}$ under
general assumptions and illustrate its performance on a number of benchmark RL
problems.
