Unfortunately, regret bounds beyond the discrete setup are much less common in the literature. Even more crucial drawback of the regret-based comparison is that regret bounds are typically pessimistic and rely on the unknown quantities of the underlying MDP's. A simpler, but related, quantity is the suboptimality gap (policy error) \(\Delta _\pi (x) \doteq V^\star (x)-V^\pi (x)\) . Since we do not know \(V^\star \) , the suboptimality gap can not be calculated directly. There is a vast amount of literature devoted to theoretical guarantees for \(\Delta _\pi (x)\) , see e.g. [1]}, [2]}, [3]} and references therein. However, these bounds share the same drawbacks as the regret bounds. Moreover, known bounds does not apply to the general policy \(\pi \)  and depends heavily on the particular algorithm which produced it. For instance, in Approximate Policy Iteration (API, [4]}) all existing bounds for \(\Delta _\pi (x)\)  depend on the one-step error induced by the approximation of the action-value function. This one-step error is difficult to quantify since it depends on the unknown smoothness properties of the action-value function. Similarly, in policy gradient methods (see e.g. [5]}), there is always an approximation error due to the choice of family of policies that can be hardly quantified. The approach based on the policy optimism principle (see [6]}) suggests to initialise the value iteration algorithm using an upper bound (optimistic value) for \(V^\star \) , yielding a sequence of upper bounds converging to \(V^\star \) . However this approach is tailored to finite state- and action space MDPs and is not applicable to evaluate the quality of the general policy \(\pi \) . To summarise, such bounds can not be used to construct tight model-free confidence bounds for \(V^\star .\)
