In the paper "Universal confidence sets for solutions of optimization problems" we provided universal confidence sets for constraint sets, optimal values and solutions sets of deterministic decision problems. The results assume concentration-of-measure properties for the objective and/or constraint functions and some knowledge about the true problem, such as values of a growth function and a continuity function. If these values are not available, one can try to estimate them from the approximations for the true functions. We show how such estimates can be derived. Furthermore we investigate con dence sets which are obtained via relaxation of certain inequalities. These confidence sets can be derived without any knowledge about the true deterministic problem and yield, with a prescribed high probability, a superset of the true set. We consider such \superset-approximations" for the constraint sets and the solutions sets and discuss the question how their quality may be judged. Furthermore, lower and upper approximations for the optimal value are derived.