Environmental policy evaluation is characterised by a paucity of information. The novel technique of robust mathematical programming is introduced as a means to proactively account for this uncertainty in policy analysis. The procedure allows identification of expected bounds on the range of abatement costs associated with environmental policy. It also has the advantage of not limiting conclusions to realisations of specific point estimates or probability distributions. Empirical insights are provided in an application to a New Zealand inland lake threatened by nitrate pollution from dairy farming. Overall, this novel framework is demonstrated to have several key advantages, including explicit treatment of severe uncertainty, capacity to bound the range of expected abatement costs accruing to a given policy instrument, and the opportunity to identify robust plans that are immune to parametric variation.