Robust rare-event performance analysis with natural non-convex constraints

We consider a common type of robust performance analysis that is formulated as maximizing an expectation among all probability models that are within some tolerance of a baseline model in the Kullback-Leibler sense. The solution of such concave program is tractable and provides an upper bound which is robust to model misspecification. However, this robust formulation fails to preserve some natural stochastic structures, such as i.i.d. model assumptions, and as a consequence, the upper bounds might be pessimistic. Unfortunately, the introduction of i.i.d. assumptions as constraints renders the underlying optimization problem very challenging to solve. We illustrate these phenomena in the rare event setting, and propose a large-deviations based approach for solving this challenging problem in an asymptotic sense for a natural class of random walk problems.