Before revision: In this work we present an approach for building tight model-free confidence intervals for the optimal value function V ^\star in general infinite horizon MDPs via the upper solutions. We suggest a novel upper value iterative procedure (UVIP) to construct upper solutions for a given agent's policy. UVIP leads to a model free method of policy evaluation. We analyze convergence properties of the approximate UVIPunder rather corresponding to a policy \pi does not provide reliable information on how far is the policy \pi from the optimal one.
After revision: In this work we present an approach for building tight model-free confidence intervals for the optimal 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.