AbstractIn this work, we consider optimal stopping problems with model uncertainty incorporated into the formulation of the underlying objective function. Typically the robust, efficient hedging of American options in incomplete markets may be described as the optimal stopping of such kind. Based on a generalisation of the additive dual representation of Rogers (Monte carlo valuation of american options. Mathematical Finance, 12:271--286, 2002) to the case of optimal stopping under model uncertainty, we develop a novel regression-based Monte Carlo algorithm for the approximation of the corresponding value function. The algorithm involves optimising a genuinely penalised empirical dual objective functional over a class of adapted martingales. This formulation allows us to construct upper bounds for the optimal value with reduced complexity. Finally, we carry out the convergence analysis of the proposed algorithm and illustrate its performance by several numerical examples.