Often the most practical way to define a Markov Decision Process (MDP) is as a simulator that, given a state and an action, produces a resulting state and immediate reward sam- pled from the corresponding distributions. Simulators in nat- ural resource management can be very expensive to execute, so that the time required to solve such MDPs is dominated by the number of calls to the simulator. This paper presents an algorithm, DDV, that combines improved confidence inter- vals on the Q values (as in interval estimation) with a novel upper bound on the discounted state occupancy probabilities to intelligently choose state-action pairs to explore. We prove that this algorithm terminates with a policy whose value is within $ε$ of the optimal policy (with probability 1−$δ$) after making only polynomially-many calls to the simulator. Ex- periments on one benchmark MDP and on an MDP for inva- sive species management show very large reductions in the number of simulator calls required.