We present an algorithm for obtaining ϵ-minimax solutions of statistical decision problems. We are interested in problems where i) the statistician is allowed to choose randomly among I decision rules, and ii) the statistical model may have an infinite dimensional parameter space. The minimax solution of these problems admits a convex programming representation over the (I - 1)-simplex, and the algorithm suggested herein to obtain an ϵ-approximation of the minimax solution is a version of mirror subgradient descent, initialized with uniform weights and stopped after a finite number of iterations. The resulting iterative procedure is known in the computer science literature as the hedge algorithm (a particular case of the multiplicative weights update method) and it is used in algorithmic game theory as a practical tool to find approximate solutions of two-person zero-sum games. We apply the suggested algorithm to different minimax problems in the econometrics literature. An empirical application to the problem of optimally selecting sites to maximize the external validity of an experimental policy evaluation illustrates the usefulness of the suggested procedure. The full paper can be found at https://joseluismontielolea.com/epsilon_minimax_v2.pdf.

We present a decision-theoretic justification for viewing the question of how to best choose where to experiment in order to optimize external validity as a k-median (clustering) problem, a popular problem in computer science and operations research. We present conditions under which minimizing the worst-case, welfare-based regret among all nonrandom schemes that select k sites to experiment is approximately equal—and sometimes exactly equal—to finding the k most central vectors of baseline site-level covariates. The k-median problem can be formulated as a linear integer program. Two empirical applications illustrate the theoretical and computational benefits of the suggested procedure.