Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
79,496 characters · 13 sections · 109 citation commands
Epsilon-Minimax Solutions of Statistical Decision Problems
\onehalfspacing
\doublespacing
Under Wald50's minimax criterion different statistical decision rules are ranked based on their worst possible expected loss. Searching for a minimax-optimal decision rule---i.e., a rule with the smallest worst-case expected loss---is computationally challenging. It is known that obtaining the minimax solution of a decision problem---and sometimes even deciding whether a minimax solution exists---is NP-hard in general du1995minimax, daskalakis2021complexity.
In this paper, we consider a particular class of decision problems in which the decision maker is restricted to choose from a menu of $I$ available decision rules, all of which are assumed to have risk between zero and a known positive constant $M$. Our motivation is that, while it is always theoretically interesting to look for the best overall decision rule, there are situations in which it is equally desirable to “evaluate the performance of relatively simple statistical decision functions that researchers use in practice” manski2024comprehensive and choose optimally among them. When we allow the decision maker to choose randomly among $I$ options, the corresponding minimax problem can be viewed as a nonlinear convex optimization problem over the $(I-1)$-dimensional simplex.chamberlain2000econometric
We show that it is possible to make substantial progress in solving our class of statistical decision problems if, instead of insisting in finding an exact minimax solution, we make our goal to find an approximate minimax solution. In particular, we search for a rule that attains the smallest worst-case expected loss, but up to a given additive factor $\epsilon$. The statistical decision theory literature refers to such a rule as an $\epsilon$-minimax optimal decision rule Ferguson67.
We show that we can provably obtain an $\epsilon$-minimax rule by using a mirror subgradient descent routine for convex optimization (Theorem 1). The methods of mirror descent nemirovski1983problem are a family of iterative procedures recommended in the optimization literature for approximately solving convex problems of high dimensions. These methods are iterative, first-order optimization algorithms, in that they require repeated evaluations of the objective function and its subgradient but do not exploit any further smoothness information about the objective function.
We present an explicit upper bound on the number of evaluations of the objective function and its subgradient required by our suggested algorithm. In particular, we show that it suffices to stop the mirror subgradient descent routine after $T = \lceil2 M^2\ln(I) / \epsilon^2 \rceil$ iterations.\footnote{$\lceil \cdot \rceil$ is the ceiling function: the function that returns the smallest integer that is greater than or equal to a given number.} We use results in ben2001ordered to argue that the smallest number of iterations required by any iterative, first-order algorithm for finding an $\epsilon$-minimax rule is $O(1)M^2/ \epsilon^2$, provided $\epsilon \geq M / \sqrt{I}$. Thus, there is a sense in which the recommended algorithm, and the suggested number of iterations, achieve the optimal dependence on $M$ and $\epsilon$, up to the logarithmic factor $\ln(I)$.
The algorithm herein suggested is known in the computer science literature as the Hedge algorithm (a particular case of the Multiplicative Weights update method); see Section 2.1 in arora2012multiplicative. This method is used in problems where a decision maker chooses randomly among $I$ alternatives repeatedly (an online decision-making problem), but after each round he obtains a payoff for all of the $I$ available actions. The Hedge algorithm is commonly used in algorithmic game theory as a practical tool to find approximate solutions of two-person zero-sum games. To the best of our knowledge, the use of the Hedge algorithm in statistical decision problems is novel. This is rather surprising in light of the straightforward connection between statistical decision problems and two-person zero-sum games, and the origins of Multiplicative Weights in iterative dynamics for game play---see the notion of $\kappa$-exponential fictitious play in fudenberg1995consistency and the references to the work of blume1993statistical therein.\footnote{ freund1999adaptive use the Hedge algorithm to approximately solve the mixed extension of two-person zero-sum games where both players have finitely many pure strategies. However, for games in which one player has infinitely many pure strategies, some other algorithms have been suggested in the literature; see, for example, filar1982algorithm and our discussion of related literature below.}
Although our suggested algorithm is designed to obtain $\epsilon$-minimax solutions of statistical decision problems, we show that the algorithm's output can also be used to provably construct an $\epsilon$-maximin solution; see Remark (ref). Moreover, it is straightforward to use our algorithm to directly find $\epsilon$-maximin solutions to statistical decision problems in which the parameter space is finite: instead of doing mirror descent, we simply do mirror ascent based on the maximin problem. Thus, mirror ascent provides a natural, and theoretically grounded alternative, to the sequential quadratic programming algorithm used by chamberlain2000econometric to find approximate least-favorable distributions in maximin problems.
We illustrate the usefulness of our suggested algorithm by analyzing a simple and stylized binary treatment choice problem with partial identification based on the work of stoye2012minimax. We use this example to compare the output of our algorithm with known exact solutions. We consider two types of minimax problems: minimizing worst-case regret and minimizing worst-case Bayes risk using the class of priors in giacomini2021robust.
Finally, we present an empirical application to the problem of optimally selecting sites to maximize the external validity of an experimental policy evaluation. This site selection problem has been recently introduced in the work of gechter2023site and egamidesigning. Broadly speaking, a policy maker wishes to experimentally evaluate the effects of a new policy with the end goal of recommending its implementation on a set of different sites. There are two types of sites: policy-relevant and experimental sites. There are also covariates $X_s \in \mathbb{R}^d$ available for each site. The site selection problem asks the following question: if the policy maker can pick at most $k$ experimental sites, what are the sites that optimize external validity? Our approach provides an algorithm for deciding how to \emph{randomly} select sites to approximately optimize external validity, taking into account information about baseline covariates. When the policy maker is restricted to select only one site for experimentation, the output of our algorithm is a selection probability for each of the sites available for experimentation. Our application has two main messages. First, choosing uniformly at random where to experiment does not tend to be $\epsilon$-minimax optimal. Instead, the $\epsilon$-minimax solution adjusts the probability of sampling a site based on its baseline covariates. Second, there are cases---for example, when one experimental site is closest to each of the policy-relevant sites---in which the $\epsilon$-minimax solution places almost probability one on such most \emph{representative} site.
{ Related Literature:} Different algorithms have been suggested for approximating the solutions of minimax problems like the ones considered in this paper. Some classical references include troutt1978algorithms, filar1982algorithm, kempthorne1987numerical, chamberlain2000econometric, and elliott2015nearly. More recently, guggenberger2025numerical have shown that it is possible to obtain numerical approximations to minimax regret treatment rules in certain treatment choice problems by using a fictitious play algorithm. One important difference between our work and this existing literature is that---once a desired approximation error $\epsilon$ has been selected, and once the bound $M$ on the risk function has been obtained---there are no further inputs that the user needs to specify in order to run the algorithm. This means that we are explicit about the number of iterations, step size, and also the initial condition. Importantly, we are able to guarantee that, upon termination after our suggested number of rounds, the algorithm provably generates an $\epsilon$-minimax rule---in the sense of Ferguson67---provided our assumptions are satisfied. As discussed before, there is also a sense in which our algorithm is, up to a logarithmic term, as good as any other iterative, first-order algorithm.
Relatedly, there is also recent interest in approximating the solution of minimax problems in which the strategies for both the statistician and nature are parameterized via neural networks, with weights that are updated iteratively using versions of what is called subgradient ascent-descent; see the recent work of luedtke2020learning and also luedtke2021adversarial. These algorithms where two players use subgradient descent are similar to the approaches used when optimizing Generative Adversarial Networks (GANs); see, for example, kaji2023adversarial. These subgradient ascent-descent algorithms are also commonly used to approximate the equilibrium of two-person zero-sum games by invoking simultaneous no-regret dynamics; see, for example, Section 3.1 in lewis2018adversarial and the references therein. Convergence rates for these subgradient ascent-descent algorithms, as well some performance guarantees for a finite number of iterations, are available under some conditions. It is known, however, that the (approximate) stationary points of these gradient ascent-descent algorithms are not necessarily $\epsilon$-minimax strategies. Instead, they are close to what the literature refers to as local min-max solutions; see the seminal work of daskalakis2021complexity. As we discuss in the conclusion, it would be interesting to further explore the differences between $\epsilon$-minimax strategies and the notion of a local min-max point.
Finally, we emphasize again that we have decided to focus on decision problems in which the decision maker chooses randomly from $I$ available decision rules. While we think there are cases (as in our applications) in which such set of finitely many decision rules can be chosen naturally, there are precedents in the literature that view such finite set as arising from a discretization of the space of decision rules; see, for example ghosh1964uniform and the references therein.\footnote{For instance, Section 5 in ghosh1964uniform gives an illustration of the construction of one such finite set of decision rules when estimating a bounded mean of a normal distribution under quadratic loss.} While there are cases in which the error from the discretization can be derived explicitly, we think whenever the problem of interest has infinitely many decision rules it is more natural to use the $\epsilon$-minimax/maximin solutions to provide upper/lower bounds on the minimax value of the problem of interest; see Remark (ref).
{ Outline:} The rest of the paper is organized as follows. Section 2 introduces notation, main assumptions, and presents the convex programming representation of the minimax problems analyzed herein. Section 3 defines an $\epsilon$-minimax decision rule and presents the algorithm. Section 4 applies the algorithm to two illustrative examples that involve solving treatment choice problems with partial identification. Our algorithm is then used to solve for $\epsilon$-minimax (regret) optimal rules; but we also argue that it can be applied to solve other minimax problems, such as (ex-ante) Robust Bayes analysis with the priors suggested by giacomini2021robust. Section 5 presents the main application. Section 6 discusses some extensions. Section 7 concludes.
A decision maker must choose an action $a$ that belongs to some set $\mathcal{A}$. Prior to choosing the action, he observes data: the realization of a random variable $X$ taking values in a set $\mathcal{X}$. A data-driven choice of action is summarized by a decision rule: a mapping from data to actions, which is herein denoted by the function $d:\mathcal{X} \rightarrow \mathcal{A}$.
We restrict our analysis to the case in which the decision maker only considers $I$ decision rules that belong to the finite set $\mathcal{D} \equiv \{d_1, \ldots, d_{I}\}$. These rules can be nonrandomized or randomized, in the sense of Ferguson67 pp. 24-25. An important aspect of our analysis is that we allow the decision maker to choose randomly from the set of decision rules $\mathcal{D}$ and we represent such a random choice by an element in the $I-1$ simplex: \[ \Delta(\mathcal{D}) \equiv \left\{(p_1,...,p_I) \in \mathbb{R}^{I} \: \Bigg| \: \sum_{i=1}^I p_i = 1, p_i \geq 0\right\}.\] It is well known that allowing the decision maker to choose randomly is usually to his advantage.\footnote{Consider a “matching pennies” game with two players, each with two actions: left and right. Suppose that column player gets $M$ when matched and $-M$ when unmatched. If neither player is allowed to choose actions randomly, the worst-case payoff obtained by the column player is $-M$ regardless of the action chosen. If the column player can randomize, but the row player cannot, the worst-case payoff for the column player if he chooses each action at random with probability 1/2 is zero.} Moreover, there are two additional reasons why we would like to allow for the possibility of randomization. The first one is that in the main application we will consider in the paper (the site selection problem described in Section (ref)), the random choice of experimental sites is viewed as the default practice in applied work. The second reason is that, as we will explain in Section (ref) (Remark (ref)), allowing for random choice of actions can reduce the computational burden of selecting a good decision rule.
A risk function is used to summarize the performance of each decision rule $d_i \in \mathcal{D}$. This performance is contingent on the data generating process, which we parameterize by an element $\theta$ belonging to some space $\Theta$. Thus, we write the risk function of each decision rule $d \in \mathcal{D}$ as a mapping $R:\mathcal{D} \times \Theta \rightarrow \mathbb{R}$. We refer to $\theta$ as a parameter, and to $\Theta$ as the parameter space. We are particularly interested in the case in which $\Theta$ is an infinite set; for example, when $\Theta$ equals all of $\mathbb{R}^{d}$. We also want to allow for the possibility that each element in the parameter space is an infinite dimensional object (for example, when $\theta$ itself is a function). We impose the following assumption on the risk function:
In Section (ref) we explain how this assumption can be verified for each of the illustrative examples we consider. We view Assumption (ref) as a minimal regularity condition for the minimax problem to be well-behaved. We also note that the assumption holds if each of the $I$ decision rules under consideration has a finite worst-case risk.
In a slight abuse of notation, we extend the original domain of the risk function---which was defined over decision rules in $\mathcal{D}$---to all possible random selections in $\Delta(\mathcal{D})$. We do this by defining, for any $p \in \Delta(\mathcal{D})$ and $\theta \in \Theta$, the function:
We view a decision problem as a triplet $(\mathcal{D},\Theta,R(\cdot,\cdot))$ and we define the minimax value of the decision problem as the scalar
A random selection $p^* \in \Delta(\mathcal{D})$ is said to be a minimax decision rule if
The use of the minimax criterion as a solution concept in statistical decision problems is traditional, dating back to Wald50. manski2021econometrics argues that the primary challenge to use the minimax criterion and Wald50's statistical decision theory is computational.
We first show that the minimax solution of the decision problems considered in this paper can be computed via convex programming. This observation is based on an analogous result in chamberlain2000econometric; see Equation 5, p. 630, and the discussion therein. The argument is as follows. For $p \in \Delta(\mathcal{D})$, define the nonlinear function
This function is the upper envelope---over all possible values in the parameter space---of the risk of $p$.
Lemma (ref) shows that solving the minimax problem in (ref) can be viewed as a nonlinear convex program over the $(I-1)$ simplex. We note that the connection to convex programming is helpful, but should not be viewed as a computational panacea. Evaluating the objective function of the convex program and its subgradient could remain computationally costly.
To make sure that the subgradient in (ref) is well defined, we make the following assumption.
The assumption says that for any $p \in \Delta(\mathcal{D})$ it is possible to find an element $\theta_{p}$ such that $R(p,\theta_p)=f(p)$. This means that there is an algorithm that is capable to i) evaluate the function $f(p)$ and to ii) find a maximizer that evaluates to $f(p)$.
Assumption (ref) requires that the worst-case risk is attained and that there is an algorithm to find $\theta_{p}$. Later we discuss the extent to which Assumption (ref) can be relaxed, by, for example, only requiring that we can get a $\delta$-approximation to $f(p)$. See Remark (ref). We note, however, that Assumption (ref) is crucial for our algorithm and should not be taken for granted. Solving the optimization problem over $\theta$ could be computationally challenging depending on the structure of the risk function. Assumptions similar to our Assumption (ref) are not uncommon in the optimization literature and are usually presented as the existence of an oracle that can evaluate the objective function of interest (in our case, the worst-case risk of a particular $p \in \Delta(\mathcal{D})$).
A popular algorithmic approach for approximately solving convex optimization problems (in particular, those of high dimensions) is to use the methods of mirror descent of nemirovski1983problem. It is known that the rate of convergence of mirror descent for convex problems in the simplex (as the one associated to our minimax problems) improves over regular subgradient descent bubeck2015convex.
This section starts out by presenting a formal definition of an approximate minimax solution. Then, this section presents an off-the-shelf implementation of mirror subgradient descent bubeck2015convex that provably finds such an approximate solution (see Algorithm (ref)).
We note that the risk of an $\epsilon$-minimax decision rule is smaller---up to an additive factor of size $\epsilon$---than the worst-case risk of any other decision rule. That is: \[R(p_\epsilon^\star,\theta) \leq \sup_{\theta \in \Theta} R(p,\theta) + \epsilon, \: \forall \theta \in \Theta, \: \forall p \in \Delta(\mathcal{D}).\] The definition of a minimax decision rule further implies that \[\Bar{v} \leq \sup_{\theta \in \Theta} R(p_\epsilon^\star,\theta) \leq \Bar{v} + \epsilon.\]
We now show that a mirror subgradient descent for convex optimization can provably find an $\epsilon$-minimax solution.
The pseudocode below describes a mirror subgradient descent routine for finding the minimum of (ref) over the simplex $\Delta(D)$.\footnote{The routine is taken from bubeck2015convex (Section 4.3, p. 301), where the mirror map is chosen to be the negative entropy $\phi(x) = \sum_{i=1}^{n} x_i \log x_i$, the routine $\nabla \phi(x_{t+1}) = \nabla \phi(x_t) - \eta \nabla f(x_t)$ becomes $x_{t+1, i} = x_{t, i} \exp(- \eta \nabla f(x_t)_i)$. We simply adjust the notation to our problem.}
As shown in Lemma (ref), the gradient vector $g_{t}$ collects the risk associated to each decision rule at $\theta_t$ (the point in the parameter space associated to the worst-case performance of $p_t$). The mirror descent update in Algorithm (ref) is intuitive: decision rules with high risk at $\theta_t$ are used less frequently in the following round. Algorithm (ref) assumes that the subgradient, $g_t$, is known. However, there are versions of the algorithm that replace $g_t$ by an unbiased estimator; see our Remark (ref) about stochastic mirror descent and Chapter 6 in bubeck2015convex.
The mirror subgradient routine in Algorithm (ref) is also known in the computer science literature as the Hedge Algorithm (a particular case of the Multiplicative Weights update method).\footnote{The Multiplicative Weights update method is a popular algorithm in computer science that has found different applications in machine learning; see arora2012multiplicative. The specific version of the Multiplicative Weights algorithm used in this paper uses an exponential function of each of the coordinates of the gradient to update the weights and is known as the Hedge algorithm. See Section 2.1 in arora2012multiplicative.} The Hedge algorithm is used in algorithmic game theory as a practical tool to find approximate solutions of two-person zero-sum games. Importantly, the mirror subgradient descent routine typically uses $(1/T)\sum_{t=1}^{T} p_{t}$ (and not the last $p$ obtained in the iteration) as the approximate minimizer.\footnote{Averaging the trajectories of a gradient-descent routine is commonly referred to as Polyak-Ruppert averaging. See ruppert1988efficient and polyak1992acceleration. See also forneron2024estimation for a discussion of Polyak-Ruppert averaging in the context of estimation and inference by stochastic optimization of nonlinear econometric models.}
We now show that if we set the step size to $\eta \equiv \epsilon/M^2$ and stop the routine after $T = \lceil 2 M^2\ln(I) / \epsilon^2 \rceil$ epochs, the mirror subgradient descent routine in Algorithm (ref) can provably find an $\epsilon$-minimax solution (in the sense of Definition (ref)). Our main result---which follows directly from the properties of mirror subgradient descent in convex optimization problems---is the following:
Theorem (ref) presents a concrete computational strategy to approximately solve the statistical decision problems considered in this paper. The only tuning parameter that needs to be chosen is $\epsilon$, which controls the approximation error. We note that in cases where it is difficult to commit to a value of $\epsilon$ explicitly, one can solve for the value of $\epsilon$ if there is a specific target for the runtime of the algorithm and we know the time it takes for each iteration to run.
We make some important remarks about Theorem (ref).
Consider the following example taken from stoye2012minimax and yata2021. A policy maker uses experimental data to decide whether to implement a new policy in a target population of interest. The treatment effect of action $a=1$ is $\mu^*\in\mathbb{R}$, while the effect of action $a=0$ is normalized to be equal to $0$. Thus, the policy maker's expected payoff equals $W(a,\mu^*) \equiv a \cdot \mu^*$.
The data available to the policy maker is an estimated treatment effect, $\hat{\mu}$, for the experimental population. The policy maker assumes that
where $\sigma>0$ is known and where $\mu \in\mathbb{R}$ is the true effect of the policy in the population where the experiment was conducted. The policy maker is concerned about the external validity of the experiment at hand. This is captured by allowing the effect of the policy in the experimental population ($\mu$) to be different from the effect in the target population ($\mu^*$). The policy maker is willing to work under the assumption that $\left\vert \mu^*-\mu \right\vert \leq k$ for some known $k \geq 0$. In this example, $\theta=(\mu,\mu^*)^{\top}$ and $\Theta \equiv \{(\mu,\mu^*) \in \mathbb{R}^2 \: | \: | \mu - \mu^* | \leq k \}\subseteq \mathbb{R}^2$.
A decision rule for the policy maker is a mapping $d: \mathbb{R} \rightarrow[0,1]$ from the observed experimental data (ref) to an action $a\in[0,1]$. The action is interpreted as the fraction of the target population that will be treated. Consider the regret loss associated to $W(a,\mu^*)$ given by $L(a,\theta) \equiv \mu^*[ \mathbf{1}\{ \mu^* \geq 0\} - a ]$. Define the risk function \[ R(d,\theta) \equiv \mathbb{E}_{\theta}[L(d,\theta)]. \]
{ Exact Minimax Solution Over all Decision Rules:} Let $\mathcal{D}^*$ denote the set of all decision rules. stoye2012minimax derived a solution to the minimax (regret) problem
as a function of $(\sigma^2,k)$. stoye2012minimax showed that when $k \geq \sqrt{\pi/2} \sigma$, Equation $\eqref{eqn:mmr-stoye}$ equals $k/2$. MQS2023decision further showed that, when $k \geq \sqrt{\pi/2} \sigma$, there are infinitely many minimax-regret optimal rules. One such solution takes the form \[d_{MQS}^\star(\hat{\mu}) =
,\] where $\rho^*<k$ is the unique strictly positive solution to
see Theorem 3 in MQS2023decision.
{ Approximate Minimax Regret Solution over a Class of Threshold Rules:} Suppose that instead of considering all decision rules, we focus on a class $\mathcal{D} \subset \mathcal{D}^*$ that contains only “threshold” rules; that is, decision rules of the form \[ d_i(\hat{\mu}) \equiv \mathbf{1}\{ \hat{\mu} \geq c_i\}, \] where $c_i \in \mathbb{R}$. For concreteness, we consider 500 different values for $c_i$ equally spaced in the interval $[-k,k]$. These threshold rules seem natural for this problem. For example, if one observes a realization of $\widehat{\mu} \geq k$, any of these rules would suggest to implement the policy at scale.
Algebra shows that, in this example, the largest worst-case risk among all threshold rules in $\mathcal{D}$ is bounded above by $M \equiv \sigma \max_{x \geq 0} x \Phi \left( (2k/\sigma) - x \right)$, where $\Phi \left( \cdot \right)$ denotes the standard normal c.d.f..\footnote{The formula corresponds to the worst-case risk of the rule that uses the threshold $c_{i}=k$ (or -$k$).} Since the expected loss is nonnegative, Assumption (ref) is satisfied.
We can also show that, for a given $p \in \Delta(\mathcal{D})$, the values $(\mu,\mu^*) \in \Theta$ that verify Assumption (ref) can be obtained by solving three optimization problems. Define the parameter $\mu^*_{+}$ to solve \[ \max_{\mu^* \geq 0} \mu^* \left( \sum_{i=1}^{I} p_{i} \Phi \left( \frac{c_i-\mu^*}{\sigma} + \frac{k}{\sigma} \right) \right), \] and $\mu_{+} \equiv \mu_{+}^*-k$. Define the parameter $\mu^*_{-}$ to be the solution of the problem \[ \max_{\mu^* \leq 0} -\mu^* \left( \sum_{i=1}^{I} p_{i} \Phi \left( \frac{\mu^*-c_i}{\sigma} + \frac{k}{\sigma} \right) \right), \] and $\mu_{-}= \mu^*_{-}+k$. Set $\theta_{p}$ to be the maximizer of \[ \{ R(p,\mu_{+},\mu^*_{+}), R(p,\mu_{-},\mu^*_{-}) \}. \]
Since we have verified Assumption (ref) and (ref), we proceed to applying Algorithm (ref). We consider the case in which $\sigma = 1$ and $k=2$. The value of the bound $M$ is $M = 2.5294$. Since we know that the value of the problem in Equation (ref) is 1 (under the parameters we have chosen), we can set $\epsilon=.1$ (that is, we are willing to tolerate 10% relative error). We later discuss how to pick $\epsilon$ in more realistic problems in which there is no information about the minimax value. The number of epochs in Theorem (ref) then becomes \[ T = \lceil 2 M^2 \ln (I)/ \epsilon^2 \rceil = 7,953. \] The runtime of Algorithm (ref) is about 30 seconds (on a personal ASUS Vivobook Pro 15 @ 2.5GHz Intel Core Ultra 9 185H). Figure (ref) presents a comparison of $d^*_{MQS}$ and the $\epsilon$-minimax rule. The value of $\Bar{v}^{\epsilon}$ is 1.0033.
Consider the same example as in Section (ref), but instead of focusing on minimax-regret optimality as in stoye2012minimax, we are interested in computing ex-ante Robust Bayes rules as in aradillas2024robust.
Let $\pi$ be a prior over $(\mu,\mu^\star)$. We are interested in obtaining the rule that minimizes worst-case expected risk over the class of priors suggested by giacomini2021robust. We will denote this class of priors by $\Gamma$. Broadly speaking, the priors in this class fix a marginal prior over $\mu$, but allow for arbitrary priors over $\mu^*| \mu$ (as long as the joint distribution over $(\mu,\mu^*)$ is supported on $\Theta$). For this example, we will first consider the “two-point prior” for $\mu$ analyzed in aradillas2024robust. That is, we assume that the prior of $\mu$ is supported on the set $\mathcal{M} = \{-\Bar{\mu},\Bar{\mu}\}$. We first assume that the policy maker has a discrete uniform prior $\pi_\mu$ on $\mathcal{M}$, meaning that $\pi_{\mu}(\mu = \Bar{\mu}) = \pi_{\mu}(\mu = -\Bar{\mu}) = 1/2$.
Just as we did in Section (ref), we consider the regret loss $L(a,\theta) \equiv \mu^\star [\mathbf{1}\{\mu^\star \geq 0\}-a]$ and the risk function \[R(d,\theta) \equiv \mathbb{E}_\theta[L(d,\theta)].\] However, we are now interested in the average (or Bayesian) risk of a decision rule defined as \[ r(d,\pi) \equiv E_{\pi} [ R(d,\theta) ]. \] Let $\mathcal{D}^*$ be the set of all decision rules. The minimax problem of interest is thus
We follow the literature and refer to any decision rule that solves this problem as either ex-ante $\Gamma$-minimax or ex-ante Robust Bayes.
aradillas2024robust showed that, under some conditions, the problem in Equation (ref) for the two-point priors on $\mu$ described before has infinitely many solutions. One such solution takes the form \[d^\star(\hat{\mu}) =
,\] where $\rho^\star$ uniquely solves \[\int_0^1 \Phi\left(\frac{2\rho^\star x - \rho^\star - (\Bar{\mu}/\sigma^2)}{\Bar{\mu}/\sigma}\right)dx = \frac{-\Bar{\mu} + k}{2k}.\]
We compare this $\Gamma$-minimax optimal rule with the $\epsilon$-approximation obtained via the Hedge algorithm. We again consider the class $\mathcal{D}$ of decision rules of the form \[d_i = \mathbf{1}\{\hat{\mu} \geq c_i\},\] where $c_i \in \mathbb{R}$. We again start with an equally spaced grid of 500 points over $[-k,k]$.
In order to apply the Hedge algorithm we extend the Bayes risk $r(d,\pi)$ to any element $p \in \Delta(\mathcal{D})$ by defining \[ r(p,\pi) \equiv \sum_{i=1}^{I} p_i r(d_{i},\pi) = \sum_{i=1}^I p_i \mathbb{E}_{\pi}\left[ R(d_i,\mu,\mu^\star)\right] = \mathbb{E}_{\pi}\left[\sum_{i=1}^I p_i R(d_i,\mu,\mu^\star)\right]. \]
We note that Assumption (ref) is satisfied with the same $M$ as in Subsection (ref). In order to verify Assumption (ref), we note that the results in giacomini2021robust show that
where
This relation immediately gives the prior $\pi \in \Gamma$ associated to the worst-case Bayes risk of any vector $p \in \Delta(\mathcal{D})$. In particular, the prior $\pi^p \in \Gamma$ that achieves the worst-case Bayes risk in (ref) sets the marginal prior over $\mu$ to be $\pi_{\mu}$, and the conditional prior of $\mu^*|\mu$ to be a point mass concentrated in the argument that maximizes (ref). Thus, the subgradient $g$ used in the mirror descent update is
When $\pi_{\mu}$ has a discrete uniform prior supported on the set $\mathcal{M} = \{-\Bar{\mu},\Bar{\mu}\}$, the $i$-th coordinate of $g$ is \[g_t^i = (1/2) \cdot R(d_i,\Bar{\mu},\Bar{\mu}_t^\star) + (1/2) \cdot R(d_i,-\Bar{\mu}, (-\Bar{\mu})_t^\star),\] where $\Bar{\mu}_t^\star$ and $(-\Bar{\mu})_t^\star$ are the corresponding values of $\mu^\star$ for $\mu=\Bar{\mu}$ and $\mu=-\Bar{\mu}$, that solve (ref). We can show that the solutions of $\mu^*$ (as a function of $\mu$) are given by \[\mu^\star =
.\]
We consider the case in which $\sigma = 1$, $k = 2$, and $\Bar{\mu} = 0.5$. We set $\epsilon = 0.1$. The number of epochs in Theorem (ref) is again \[ T = \lceil 2 M^2 \ln (I)/ \epsilon^2 \rceil = 7,953. \] The algorithm runs for $T = 7,953$ iterations and finishes in about 25 seconds (on a personal ASUS Vivobook Pro 15 @ 2.5GHz Intel Core Ultra 9 185H).
Figure (ref) shows the true solution versus its $\epsilon$-approximate solution. Qualitatively, the two are very close. The minimax values are close as well, with the $\epsilon$-approximation having a minimax value of $.9377$ and the true solution having a minimax value of $0.9375$. Note that here, the term referred to as $\rho^\star$-adjusted is
lee2021poverty conducted a randomized controlled trial in Bangladesh to estimate the effects of encouraging rural households to receive money transfers from migrant family members. They specifically conducted an encouragement design where poor rural households with family members who had migrated to a larger urban destination receive a 30--45 minute training about how to register and use the mobile banking service “bKash” to send instant remittances back home.
The experiment was conducted in the Gaibandha district, one of Bangladesh's poorest regions. It focused on households that had migrant workers in the Dhaka district, the administrative unit in which the capital of Bangladesh is located. lee2021poverty measure several outcomes of both receiving households and sender migrants; see their Figures 3 and 4. To give a concrete example of the measured outcomes, one question of interest is whether families that adopt the mobile banking technology are more (or less) likely to declare that the monga---the seasonal period of hunger in September through November---was not a problem for their household. Table 9, Column 7, p. 60 in lee2021poverty presents results for this specific variable showing that households that used a bKash account in the treatment group are 9.2 percentage points more likely to declare that monga was not a problem. The standard error of the estimator is 4.5 percentage points.
Is the corridor selected by lee2021poverty a good choice for a researcher who is concerned about external validity?\footnote{Following gechter2023site, we name the corridors using a destination-origin format; for example, the migration corridor studied in lee2021poverty is “Dhaka-Gaibandha”.} Two recent papers provided answers to this question. gechter2023site use an elegant decision-theoretic framework to argue that the Dhaka-Noakhali corridor would have been a better choice from the perspective of maximizing average welfare. olea2024externally use the framework of gechter2023site to argue that the Dhaka-Pabna corridor would have been a better choice from the minimax (welfare) regret criterion perspective (restricting the policy maker to consider only nonrandomized selection of corridors). The Dhaka-Pabna corridor is also recommended by the synthetic purposive sampling approach in egamidesigning. One important comment is that the Dhaka-Pabna corridor is the most representative in terms of covariates, in the sense that it minimizes the average distance (measured using the euclidean distance between covariates) to the $41$ migration corridors analyzed in gechter2023site.
In our application, we consider a situation where a policy maker is considering the three sites mentioned above to run an experiment: Dhaka-Gaibandha (the original site in lee2021poverty), Dhaka-Noakhali (the site suggested by gechter2023site) and Dhaka-Pabna (the site suggested in olea2024externally). Each of these sites (migration corridor) have site characteristics $X_s \in \mathbb{R}^{d}$, with $d=13$.\footnote{The covariates include mean household income, mean household size, migrant density, mean remittances. See Figure 2 in olea2024externally.} We index these three sites by $1,2,3$ respectively and refer to the set $\mathcal{S}_E \equiv \{1,2,3\}$ as the set of experimental sites. Once we exclude these three sites, we have 38 migration corridors. We use the distance between the covariates of each of these sites and Dhaka-Pabna to order them in increasing order and index them with integers $4$ to 41. Figure (ref) presents the distances. The figure shows that for most of the sites the corridor Dhaka-Pabna is the “closest” in terms of the Euclidean distance between covariates.
We assume that the sites $\mathcal{S}_{p} \equiv \{ 4, \ldots, 41 \}$ in the $x$-axis of Figure (ref) are the policy-relevant sites. This means that policy maker is interested in deciding whether the training program discussed in lee2021poverty should be rolled out in these sites. We assume that the outcome variable of interest for the policy maker is the likelihood that the households declare that the monga was not a problem.
Treatment Effect Heterogeneity: Treatment effect heterogeneity is allowed, but only via the observable site characteristics. The effects of the policy in each site, denoted by $\tau_{s}$, are restricted to be a Lipschitz function (with respect to a Euclidean norm $||\cdot||$) with known constant $C$; that is, $\tau_{s} = \tau(X_s)$, where \[|\tau(x)-\tau(x')| \leq C||x-x'||, \hspace{1em} \forall x,x' \in \mathbb{R}^{13}.\] One first issue that we need to address in order to conduct our exercise is the value of $C$ that will be used in our application. We do this by using the available point estimates of the treatment effect of the program in lee2021poverty. Let $x_{DG}$ denote the covariates of the corridor Dhaka-Gaibandha. Assume that the we entertained the possibility that the true effect, $\tau(x_{DG})$, coincides with the estimated effect 9.2. We consider a “low $C$” regime.
Suppose that we want to consider a value of $C$ that imposes that if 9.2 were the true effect, then even the corridor that is the most different (in terms of covariates) to Dhaka-Gaibandha the effect of the program must be nonnegative. Dhaka-Bhola is the most different site and $\| x_{\textrm{DG}}- x_{\textrm{DB}} \| = 7.7736$. Since the Lipschitz restriction imposes that \[ \tau(x_{\textrm{DG}}) - C \| x_{\textrm{DG}}- x_{\textrm{DB}} \| \leq \tau(x_{\textrm{DB}}),\] we could pick $C$ as \[ C = 9.2 / 7.7736 \approx 1.1834. \]
Treatment Rules: The policy maker makes two choices. First, the policy maker must pick one site on which to experiment. Second, the policy maker must decide how to make treatment choices in all the sites of interest given the available data. We assume that if the policy maker decides to experiment on site $s$, the available data becomes $\widehat{\tau}_s$, with
and, as in gechter2023site, we assume $\sigma^2_s$ is known. In order to conduct our exercise, we assume that $\sigma_s$ is the same for all experimental sites, and that it matches the standard error of the estimated effect of the program in the Dhaka-Gaibhanda site. That is $\sigma_{s}=4.5$ for all $s \in \mathcal{S}_{E}$.
The treatment rule is a mapping $T:\mathbb{R} \rightarrow [0,1]^{\#\mathcal{S}_{P}}$. For $s \in \mathcal{S}_{E}$ we further denote by $T_s$ the specific policy choice for site $s$. We refer to a tuple $(s,T)$ as a policy, and we use $d$ to denote it. We consider three nonrandomized policies \[\mathcal{D} \equiv \left\{d_1, d_2, d_3 \right \}. \] Under policy $d_s$, the policy maker experiments on site $s \in \mathcal{S}_{E}$ and its recommendation for any policy relevant site is $\mathbf{1}\{\widehat{\tau}_s \geq 0\}$. That is, the policy maker makes the same policy recommendation for every policy-relevant site depending on the sign of $\widehat{\tau}_{s}$. \footnote{The results in olea2024externally suggest that this type of policy is likely to be suboptimal. The policy maker could improve its welfare by allowing the treatment choice to be randomly selected, depending on the distance between the policy-relevant site and the experimental site.} We focus on this special form of policy rule because we think it captures the policy recommendations that are given based on randomized controlled trials.
We consider the following regret function for the policy $d_s$,
This expression can be simplified to
The minimax (regret) problem that we are interested in solving is
where $\text{Lip}_{C}(\mathbb{R}^{13})$ refers to the space of all Lipschitz functions $f:\mathbb{R}^{13} \rightarrow \mathbb{R}$ with constant $C$.
We report results for the case in which $C=1.1834$. We consider four different scenarios that vary in terms of the number of sites that are policy relevant. The scenarios we consider have either 1, 5, 15, or 38 policy-relevant sites. In each of these cases, we choose to include the sites that are closest to Dhaka-Pabna. For example, when we include only one policy-relevant site we include Dhaka-Faridpur. We do this because, in light of the results in olea2024externally, the best nonrandomized choice of experimental site is Dhaka-Pabna. And we would like to use this application to understand how the probability of selecting this site changes as we include sites that perhaps are closer to some of the other experimental sites under consideration.
Figure (ref) presents the $\epsilon$-minimax selection of sites obtained via the Hedge algorithm. Note first that when there is only one policy-relevant site (and this site is closest to Dhaka-Pabna) the probability of choosing Dhaka-Pabna is close to 1. This is measured by the height of the first yellow bar in Figure (ref). We think this is an interesting result as it shows that even if randomization is allowed, it is possible that choosing the site that is most representative for the policy-relevant site is still approximately minimax regret optimal.
The results with five policy relevant sites are also worth discussing. By construction, the five policy-relevant sites that we considered are those that are closest to Dhaka-Pabna. According to Figure (ref), Dhaka-Pabna is the nearest neighbor for all of them, with the exception of Dhaka-Kishoregonj. For the latter site, the nearest neighbor is Dhaka-Gaibandha. Figure (ref) shows that, with 5 sites, the $\epsilon$-minimax selection of experimental sites places probability slightly above $.2$ on Dhaka-Gaibandha (corresponding to the height of the second blue bar) and probability close to .7 on Dhaka-Pabna (corresponding to the height of the second yellow bar).
We finally discuss the cases in which there are 15 or 38 policy-relevant sites. The corresponding $\epsilon$-minimax solutions are very similar, though the computation times and numbers of iterations are not; see Tables (ref). The recommended probability of experimenting on Dhaka-Pabna is close to .6 (height of the last yellow bar). The recommended probability of experimenting on Dhaka-Noakhali is close to .1. Interestingly, the ordering of the probabilities is also consistent with the ordering of the three experimental sites in terms of how frequently they are the nearest neighbor of each of the policy-relevant sites.
We can also reframe our results to start from setting a target runtime for Algorithm (ref). We next show how, after picking a desired run time, we can obtain a value of $\epsilon$ that matches this target.
For the sake of concreteness, suppose that we are willing to spend $\tau = 1,800$ seconds running Algorithm (ref) for the case of one policy site. Most of the time spent in each of the epochs is used to compute nature's best response. As suggested in Table (ref), suppose that calling the oracle that calculates nature's best response takes $r\equiv .35$ seconds. Thus, the total number of iterations that we could afford to run becomes $\lfloor \tau / r \rfloor = 5,142$. Since $M^2$ and $I$ are known, we can solve for the value of $\epsilon$ using the formula for the number of iterations, $T$, presented in Algorithm (ref): \[\epsilon(\tau) \equiv \sqrt{\frac{2 \cdot M^2 \cdot \ln(I)}{\tau / r}}.\] Taking $M^2 = 4.5739$ and $I=3$ gives $\epsilon(1,800) = .044$. Table (ref) shows various values of $\epsilon$ needed for different runtimes (for different number of policy-relevant sites). These values can be thought of as the maximum amount of precision (lowest $\epsilon$) attainable for each possible number of policy-relevant sites if the policy maker is only willing to spend the amount of compute time in each of the columns of Table (ref).
This paper presented an algorithm for obtaining $\epsilon$-minimax solutions of statistical decision problems where the statistician is allowed to choose randomly among $I$ decision rules. The notion of an $\epsilon$-minimax decision rule was taken from Ferguson67 (Chapter 1, Definition 4) and it refers to a decision rule whose worst-case expected loss exceeds the minimax value of the decision problem by at most an additive factor of $\epsilon$.\footnote{We note that the definition given in Ferguson67 differs of the usage of $\epsilon$-minimax decision rules in other contexts. Most notably, from the work of manski2016sufficient, who use the term $\epsilon$-minimax to refer to a decision rule whose worst-case regret is at most $\epsilon$.}
Once we allow for randomized selection over the $I$ decision rules, the minimax problem admits a convex programming representation over the $(I-1)$-simplex, an observation which has been previously documented in the literature by chamberlain2000econometric. Both the objective function and the subgradient of this problem are in general difficult to evaluate, the reason being that the objective function of the convex problem involves solving a nonconvex maximization problem to find the worst-case performance (over the model's parameter space) of a specific randomized selection over the $I$ rules. This type of problem arises commonly in the convex optimization literature; see bubeck2015convex and the seminal work of nemirovski1983problem. The algorithm herein suggested is a mirror subgradient descent (with negative entropy as a mirror map), initialized with uniform weights and stopped after a finite number of iterations. The early stopping of the algorithm tries to minimize the number of calls to the objective function and its subgradient, but it provably generates an approximate solution with the desired tolerance $\epsilon$.
The iterative procedure arising from this mirror descent routine described in this paper is known in the computer science literature as the Hedge Algorithm, and it is used in algorithmic game theory as a practical tool to find approximate solutions of two-person zero-sum games.
The paper applies the suggested algorithm to different minimax problems in the econometrics literature. In some of these problems, the minimax solution is known, and we show numerically that in these examples the $\epsilon$-minimax solution is practically the same as the true minimax solution.
Finally, we apply the algorithm to the site selection problem of gechter2023site; namely, how to optimally selecting sites to maximize the external validity of an experimental policy evaluation. Our algorithm allows the researcher to choose randomly where to experiment, but adjusting optimally for the available baseline covariate information.
We think there are several interesting areas for future work, both from an applied and from a more theoretical perspective. From a purely applied angle, our algorithm could be useful in approximately solving certain minimax problems, such as the one described in the recent work of armstrong2024adapting.
From a more theoretical perspective, it would be interesting to further explore the differences between $\epsilon$-minimax strategies and the notion of a local min-max point in daskalakis2021complexity. There are very interesting results about the relation between this notion and the stationary points of sugbradient ascent-descent dynamics. But it would be great to understand, theoretically and empirically, what are the potential benefits of searching for these type of points as opposed to $\epsilon$-minimax strategies.