We consider the problem of identifying the trade-off between tolerance level and worst case performance, for a problem where the decision variables may be disturbed within a set tolerance level. This is a special case of a bi-level optimization problem. In general, bi-level optimization problems are computationally very expensive, because a lower level optimizer is called to evaluate each solution on the upper level. In this paper, we propose and compare several strategies to reduce the number of fitness evaluations without substantially compromising the final solution quality.