Given an initial state, what is the best possible action that can be returned by a planning algorithm that is given a finite numerical budget (e.g. number of calls to a model of the state-transition and reward functions). We investigate optimistic strategies and provide regret bounds in terms of a new measure of the complexity of the planning problem.