In this talk a novel simulation-based algorithm for solving optimal stopping problems in discrete and continuous time will be proposed. The algorithm involves the optimization of a genuinely penalized dual objective functional over a class of adapted martingales. The convergence analysis of the proposed algorithm reveals that the variance of the resulting estimate can be bounded from above by a multiple of the smallest approximation error within the class of martingales we optimize over, i.e. the better are the approximation properties of the martingale class, the less paths are needed to estimate the value of the underlying optimal stopping problem. The latter rather attractive variance 'self-reduction' property not shared with other existing simulation-based algorithms, will be illustrated by several numerical examples.