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.
109,340 characters · 14 sections · 0 citation commands
On the numerical approximation of minimax regret rules via fictitious play
$ \and $
$}
\setcounter{page}{1}
\setcounter{equation}{0}Consider a policymaker who has to pick one of $T$ treatments after being informed about treatment outcomes by a sample of size $N$ from the population. If there is not one treatment policy $\delta$ that is best,\footnote{A treatment rule $\delta$ is a mapping from the set of possible samples onto the space of probability distributions on the set $\{1,...T\},$ see ((ref)) for a precise definition.} in expected outcome say, uniformly over all possible data generating processes (DGPs) then it is not unambiguous how an optimal treatment policy should be defined. Typically, there is not just one rule that is admissible. One could pursue a Bayesian analysis and optimize for a given prior over the space of all possible DGPs. One could pursue a max-min analysis that looks for a treatment rule that maximizes over all possible rules the minimal (over all DGPs) expected outcome. While the Bayesian route is subjective and would lead to potentially poor finite sample performance when the prior is false, the max-min criterion is often uninformative in the sense of all treatment policies being max-min. A growing literature therefore focuses on finding minimax regret rules, see Wald (1950), Savage (1954), and Manski (2004), that is, rules that minimize over all treatment policies the maximal regret over all DGPs, where regret for a given policy and DGP measures the gap between the best possible expected outcome and the expected outcome obtained for the chosen policy. Unfortunately, there are very few examples where minimax regret rules are analytically known and therefore in many examples of empirical interest they cannot currently be used by policymakers.\footnote{Exceptions include e.g. Schlag (2006), Manski (2007), Stoye (2009, 2012), Tetenov (2012), Montiel Olea, Qiu, and Stoye (2023), Yata (2023), Chen and Guggenberger (2024), Kitagawa, Lee, and Qiu (2024), and additional references in these papers. The analytical finite sample results derived in these papers apply only under very restrictive assumptions, like an unrestricted (except for certain bounds) symmetric parameter space for the DGPs, an equal number of observations on outcomes for every treatment, or a normality assumption for observed outcomes in the partially identified examples. Guggenberger, Mehta and Pavlov (2024) derive minimax policies in the case where a policymaker is concerned with an $\alpha$-quantile rather than expected outcome. See also Manski and Tetenov (2023). Robust Bayes methods constitute an additional approach and have been studied in the context of partially-identified models in Giacomini and Kitagawa (2022) and Aradillas Fern\'{a}ndez, Montiel Olea, Qiu, Stoye, and Tinda (2024). Important references for optimal treatment choice in an asymptotic framework include Hirano and Porter (2009) and Kitagawa and Tetenov (2019).} Manski (2021) concludes that \textquotedblleft The primary challenge to use of statistical decision theory is computational.\textquotedblright\ While there have been some contributions with regards to numerical implementation of minimax regret rules, see e.g. Chamberlain (2000) who provides an approach via convex minimization, the computational burden of the currently available algorithms, at least in the types of examples considered in the paper here, is quite overwhelming especially with the complexity of the space of DGPs, the number of actions by the policymaker or the sample size $N$ increasing.\footnote{Meaningful progress has been made in some cases when one is willing to search for minimax regret rules in constrained classes of treatment rules. See e.g. Manski (2004), Manski and Tetenov (2016, 2019, 2021), Kitagawa and Tetenov (2018), and Dominitz and Manski (2024). The latter paper obtains a simple expression for the maximum regret of a simple intuitive \textquotedblleft midpoint prediction\textquotedblright\ for best prediction under square loss with missing data.}
The objective of this paper is to provide a feasible procedure for the numerical approximation of minimax regret rules. We first provide an algorithm based on Robinson (1951) to approximate minimax regret rules that applies in the case where potential outcomes $Y_{t},$ for each $t=1,...,T,$ are elements of $\{0,1\}$ and the set of possible DGPs that nature chooses from has been discretized. In the case where $Y_{t}\in\lbrack0,1]$ we obtain an approximation to a minimax regret rule via the so-called coarsening method applied to the solution from the binary case.
For the binary case, we adapt an algorithm from Robinson (1951) who considers a zero-sum two player game in which each player has finitely many actions and randomization over these actions is allowed for. The algorithm iteratively updates the strategy chosen by a player. More precisely, players take turns and each time when it is a player's turn she picks one of the finitely many actions that is a best response to the current mixed strategy of the other player that equals the empirical distribution of the strategies used by that player up to that period.\ The player then updates her strategy by setting it equal to the empirical distribution function over all best responses she played up to that point. Robinson (1951) shows that as the number of iterations goes to infinity the payoff that each player secures converges to the value of the game. In the game theory literature this approach is known as \textquotedblleft fictitious play\textquotedblright. In our scenario, the two players are the policymaker that picks a treatment rule and nature that picks the DGP with the payoff to the policymaker equal to negative regret. To conform with the setup in Robinson (1951) we discretize the set of possible DGPs that nature can choose from.\footnote{We make the discretization of nature's action space explicit in our discussion. But note that any numerical approach to approximate minimax regret rules via an iterative algorithm that relies on repeatedly calculating best responses by nature through grid search also effectively uses discretization.} We show that as the discretization gets finer the minimax regret of the discretized game converges to the one of the original game. In the binary case, the set of nonrandomized treatment rules for the policymaker is automatically finite. Applied to our setting, Robinson's (1951) result implies that the maximal regret the policymaker might suffer approaches the minimax regret value under the sequence of treatment rules produced by the algorithm. We consider modifications of Robinson's (1951) approach by using updating weights proposed by Leslie and Collins (2006) that seem to lead to faster convergence of the algorithm.
In each step of our proposed algorithm a best response has to be calculated. Crucially, calculating the policymaker's best response to a given strategy by nature can be done, in many cases of interest, computationally trivially, via Bayes' rule and comparisons of the conditional means. We do so in our main applications. Note that the main computational bottleneck of other methods proposed in the literature, e.g. Chamberlain's (2000) approach based on convex optimization, is caused by the need to either evaluate the risk of all treatment rules or the risk of a given treatment rule for all possible actions by nature for every iteration of the algorithm. As illustrated below, in our examples we deal with cases where the policymaker may be tasked to randomize among $10^{10000}$ different treatment rules (or even many more). While our approach can successfully tackle that challenge any procedure that attempts to evaluate the risk of each treatment rule must necessarily fail due to the computational burden.
For a given strategy of the player we calculate nature's best response via grid search which poses the main computational hurdle. The computational complexity of our procedure (and any other procedure we are aware of) increases exponentially in the dimension of nature's action space. We are unaware of any particular structure, like convexity, to nature's maximization problem and currently use grid search to solve it.
Importantly, at every iteration step, the algorithm produces a bound for how far the maximal regret of the currently proposed treatment rule differs from the actual minimax regret value under discretization of nature's action space. This bound converges to zero as the number of iterations increases.
We also consider the case where the policymaker uses a priori information that restricts the parameter space of nature, for example, by restricting the possible set of means of $Y_{t}.$ We show that this can be straightforwardly incorporated into our general framework. Also, the set of rules the policymaker may choose from can also be restricted in our framework to incorporate for example certain policy restrictions. The latter however may rule out the applicability of Bayes' rule and may thus lead to a substantial increase in the computation time.
In the case $Y_{t}\in\lbrack0,1]$ we immediately obtain an approximate minimax regret rule via the coarsening approach (see e.g. Schlag (2006) and Stoye (2009)) and an approximate minimax regret rule from the binary case. We illustrate how to adapt the coarsening approach to various sampling designs, arbitrary number of treatments and incorporation of a priori information on possible DGPs by the policymaker.
In given applications of the proposed algorithm, we suggest searching for symmetries in the model that allow for further reduction of computation time. Namely, often it is possible to show that Nash equilibria of the game between the policymaker and nature can be found in a class of treatment rules restricted by certain symmetry conditions. This then implies that minimax regret rules can be found as well in that restricted class.
We study the following examples. In the first example, we consider the case of a policymaker who needs to pick one of two treatments after having observed $N_{t}$ observations on each treatment$,$ $t=1,2,$ where $N_{1}$ and $N_{2}$ may be different, and aims at maximizing expected outcome. First, we consider the case where outcomes are either successes or failures, i.e. $Y_{t} \in\{0,1\}$. It is shown that in this case minimax regret rules can be found in a class of treatment rules restricted by a symmetry condition that substantially reduces the class of rules that need to be searched over. In a nutshell, the \textquotedblleft symmetric\textquotedblright\ rules $\delta$ considered are such that the value of $\delta(w_{N})$ for a sample $w_{N}=(n_{1},n_{2})$ (where $n_{t}$ denotes the number of successes for treatment $t$ in the sample) already pins down the value of $\delta (w_{N}^{\prime})$ for another sample $w_{N}^{\prime}=(n_{1}^{\prime },n_{2}^{\prime})$ such that $n_{t}+n_{t}^{\prime}=N_{t}$ for $t=1,2.$ That is, pinning down the values of a symmetric rule on about one half of the arguments already determines the entire rule. We then provide an algorithm that leverages the insights of fictitious play with the restrictions imposed by symmetry$.$\footnote{For a very restricted subcase we are able to provide analytical results for minimax rules, namely the case where $\min _{t=1,2}\{N_{t}\}=0$, that is the case where one only observes data on outcomes from one treatment.} To give some measure about the computational complexity that is being tackled here, one can show that in the case where $N_{1}=N_{2}=300$ there are $2^{N_{1}(N_{2}+1)/2+N_{2}/2}=2^{45300} \approx10^{13636.7}$ symmetric \textquotedblleft nonrandomized\textquotedblright\ treatment rules one needs to search over.\footnote{For symmetric rules, defined properly in ((ref)), one needs to set $\delta_{2}(n_{1},n_{2})=1/2$ when $n_{1}/N_{1}=n_{2} /N_{2}=1/2.$ Therefore, when we say \textquotedblleft nonrandomized\textquotedblright\ in the context of symmetric rules we mean $\delta_{2}(n_{1},n_{2})\in\{0,1\}$ except for the case $n_{1}/N_{1} =n_{2}/N_{2}=1/2.$ All computations reported in the paper are done using the Gauss software on a Dell desktop computer with an Intel(R) Core(TM) i7-14700 2.10 GHz Processor.} By Stoye (2009, Corollary 1) it is known that the minimax regret value in that case equals .006940. In 51 minutes of computation time with 2000 iterations, the algorithm produces a treatment rule (a weighted average over the $10^{13636.7}$ symmetric nonrandomized treatment rules) whose maximal regret equals .006939! We illustrate that our algorithm can lead to substantial improvements in terms of maximal regret after quite few iterations relative to an empirical success rule.
The second example we study is testing innovations against a status quo. Stoye (2009) provides analytical expressions for minimax regret rules (given as solutions to a univariate equation) when one innovation is compared to the status quo, but there is no known analytical solution for the case of more than one innovation. As in the previous example, we derive certain symmetry conditions that help reduce the computational effort and then apply the general algorithm for that example. Additional applications appear in a Supplementary Appendix.
Relative to most of the extant literature on computational approaches to approximate minimax regret rules our approach avoids the most costly step of the algorithm that requires evaluation of risk over all treatment rules. Namely, consider a finite set of treatment rules with $f$ elements to choose from and denote by $p$ a discrete probability distribution over that set, i.e. a mixed strategy. It is well known that the function $h(p)=\sup_{s\in \mathbb{S}}R(p,s)$ is convex over the $f-1$-dimensional simplex, where $R$ denotes regret (defined in ((ref)) below) and $\mathbb{S}$ denotes the set of all possible distributions for potential outcomes. Chamberlain (2000) suggests using tools from convex programming to find a minimum for the function $h(p).$ However, this step is computationally costly when $f$ is large. Instead, in our algorithm, when a best response by the policymaker needs to be calculated for the current mixed strategy used by nature, we rely on Bayes' rule. The computational hurdle is further reduced by dividing the problem into a computationally feasible numerical step and the coarsening trick.
Regarding numerical approaches for approximation of minimax regret rules, besides the early contribution by Chamberlain (2000), Masten (2023) considers nonlinear optimization packages like KNITRO and applies them to the case of unbalanced samples with $T=2$ for several small sample sizes with $\max_{t\in\{1,2\}}\{N_{t}\}\leq5.$ See Dominitz and Manski (2024) for a comprehensive discussion of computational methods. Recently, Aradillas Fern\'{a}ndez, Blanchet, Montiel Olea, Qiu, Stoye, and Tan (2024) consider a particular convex optimization routine called \textquotedblleft mirror descent\textquotedblright\ to approximate $\epsilon$-minimax regret rules. The policymaker iteratively updates her strategy using \textquotedblleft multiplicative weights\textquotedblright\ based on the subgradient of $h$ while nature computes a best response in each iteration to the policymaker's current strategy. For a bounded risk function it is shown that it takes $O(\ln f/\epsilon^{2})$ iterations to obtain an $\epsilon $-minimax regret rule. From results in Ben-Tal, Margalit, and Nemirovski (2001) it follows that the algorithm is optimal with respect to number of iterations among all iterative, first-order algorithms for convex optimization\ over the $f-1$-dimensional simplex up to the logarithmic factor $\ln f.$ In contrast, we do not provide results on the maximal number of iterations our algorithm requires to produce an $\epsilon$-minimax regret rule in a broad class of problems. We are concerned about the overall computational effort, which combines both the number of iterations and the computational effort in each iteration, in a given application. There are examples, where the convergence rate of fictitious play is rather slow, see e.g. Daskalakis and Pan (2014). But in the examples we consider in the paper, we find that the overall computational effort to obtain an $\epsilon$-minimax regret rule a is very competitive. We provide a comparison with \textquotedblleft mirror descent\textquotedblright\ in the context of our first example.
Daskalakis, Deckelbaum, and Kim (2024) focuses on computing the value of a game using the so-called \textquotedblleft excessive gap technique\textquotedblright. Using that approach requires optimization for each iteration of the algorithm which can be challenging in the applications that we consider given the strategy space for the policymaker is growing very fast. An additional related contribution regarding convex optimization is Bubeck (2015). An important reference for an algorithm to approximate a least favorable prior distribution is Kempthorne (1987).
Note that the general problematic one faces here is related to a testing scenario where several competing tests are available that all control the size. If the power curves of the tests intersect then which test to pick becomes a non-unambiguous task. Elliott, M\"{u}ller, and Watson (2015) consider finding tests that maximize weighted average power and in a scenario where the null hypothesis is composite they propose algorithms that find tests that are nearly optimal. It is shown that finding such optimal tests can be expressed as a minimax regret problem. Therefore, the numerical algorithm proposed in our paper might potentially be applied also in this scenario but would require several modifications
The paper is organized as follows. Section (ref) provides a general description of the numerical procedure to approximate minimax regret rules based on fictitious play. In Subsection (ref) the discretized model of nature's parameter space is introduced and subsection (ref) discusses the algorithm to approximate minimax regret rules. Subsection (ref) discusses how approximate minimax regret rules can be obtained in the case where outcomes live on the unit interval via the so-called coarsening approach of approximate minimax regret rules from the binary case. We then consider several examples of the general theory. Section (ref) introduces the example of treatment choice with unbalanced sample sizes. Analytical minimax regret rules are provided for the special case where $\min _{t=1,2}\{N_{t}\}=0.$ Subsection (ref) shows that there exists minimax regret rules that satisfy a symmetry condition. Subsection (ref) specializes and leverages the insights from the general algorithm from Section (ref) by incorporating symmetry. We discuss the results from the application of the algorithm in Subsection (ref) where we also consider the case where the action space of nature is restricted by a priori information of the policymaker. Finally in Section (ref) we consider the example of \textquotedblleft testing innovations\textquotedblright\ with more than one alternative. The proofs of all statements are given in the Appendix. A Supplementary Appendix contains further results on the examples in the paper.
A player has to choose one of several actions $t\in\mathbb{T}:=\{1,2,...,T\}$ with randomization being allowed for. In many applications, the player is a policymaker and $\mathbb{T}$ is the set of treatments that she considers for a population.
By $Y_{t}$ for $t\in\mathbb{T}$ we denote the random outcome if the player chooses action $t.$ The vector of potential outcomes $(Y_{t})_{t\in\mathbb{T} }$ is assumed to be an element in the set $S$. In several examples in the literature, $S=\{0,1\}^{T}$ or $S=[0,1]^{T},$ that is, the case, where the range of outcomes is the same under every action $t\in\mathbb{T}$, and where in the first case outcomes can be interpreted as success or failure. The algorithm we propose applies to the case where $S=\{0,1\}^{T}.$
The setup can be interpreted as a game of the player against an antagonistic nature that chooses a joint distribution $s\in\mathbb{S}$ for $(Y_{t} )_{t\in\mathbb{T}},$ a so-called \textquotedblleft state of the world\textquotedblright, where $\mathbb{S}$ denotes the set of possible distributions on $S.$ Oftentimes, the player is assumed to care about expected outcome. For $t\in\mathbb{T}$ define $\mu_{t}=E_{s}Y_{t}.$
Before choosing an action, the player observes a sample $w_{N}=(t_{i} ,y_{t_{i},i})_{i=1,...,N}$ of size $N$ with $y_{t_{i},i},$ for given $t_{i},$ denoting an independent draw from $Y_{t_{i},i}$ for $i=1,...,N$ (generated from a certain $s\in\mathbb{S)}$. As in Stoye (2009) several sampling designs are possible. For example, under fixed assignment, assume integers $N_{t}$ for $t\in\mathbb{T}$ are given and the sample $w_{N}$ consists of $N_{t}$ independent observations under each action $t\in \mathbb{T}$ with the sum of the $N_{t}$ equal to $N.$ Under random assignment, $P(t_{i}=t)=p_{t}$ for all $i=1,...,N$ and $t\in\mathbb{T},$ for some probabilities $p_{t}$ whose sum over $t$ equals 1. Lastly, consider the case of testing innovations, where the policymaker knows the mean outcome $\mu_{T}$ of treatment $T$ of a status quo treatment. She needs to consider whether to switch from the status quo to one of $T-1$ alternative treatments whose mean outcome is unknown. The sample $w_{N}=(t_{i},y_{t_{i} ,i})_{i=1,...,N}$ consists of $N_{t}$ independent observations under each action $t\in\mathbb{\{}1,...,T-1\mathbb{\}}$ with the sum of the $N_{t}$ for $t=1,...,T-1\mathbb{\ }$equal to $N.$ Or alternatively one could generate the sample via random assignment.
Wlog we can assume that the marginal distributions of $Y_{t}$ are independent of each other. Then, in the case where $S=\{0,1\}^{T}$ the joint distribution of $(Y_{t})_{t\in\mathbb{T}}$ is fully pinned down by the mean vector $\mu=(\mu_{1},...,\mu_{T})\in\lbrack0,1]^{T}.$ Thus, from now on, in this case, an action by nature (rather than being presented as a joint DGP for the potential outcomes) is identified with picking a mean vector $\mu\in \lbrack0,1]^{T}.$ The policymaker may have certain a priori knowledge that allows her to restrict $\mu$ to a subset $M\subset\lbrack0,1]^{T}.$
We next define the notion of a treatment rule. The task for the player is to choose a vector $\delta(w_{N})\in\lbrack0,1]^{T}$ for every possible sample realization $w_{N},$ whose components add up to one and represent the probabilities with which action $t$ is chosen. Namely, which treatment the player ultimately assigns is determined as an independent draw from the discrete random variable $B=B(\delta(w_{N}))\in\mathbb{T}$ that equals $t$ with probability $\delta_{t}(w_{N})$ for $t\in\mathbb{T},$ where $\delta _{t}(w_{N})$ denotes the $t$-th component of $\delta(w_{N}).$
For a given sampling design, denote by $\mathbb{D}$ the set of rules $\delta$ that the policymaker can choose from. Unless otherwise specified, $\mathbb{D}$ is taken as the set of all (measurable) mappings
with $\delta(w_{N})$ defining a probability distribution over the set $\mathbb{T}.$ Note that we are therefore including randomized rules. In certain applications, $\mathbb{D}$ may be restricted. For example, Ishigara and Kitagawa (2024) use only nonrandomized linear aggregation rules to gain tractability. In empirical applications, policy restrictions may rule out certain elements in $\Delta^{T-1}$ from consideration.
For given $\delta\in\mathbb{D}$ and $s\in\mathbb{S}$ denote by $u(\delta,s)$ the payoff for the player. In this paper, $u(\delta,s)=E_{s}Y_{B(\delta (w_{N}))}$ i.e. the player cares about the expected outcome.\footnote{Another possibility is$\ u(\delta,s)=q_{s,\alpha}(Y_{B(\delta(w))}),$where $q_{s,\alpha}(Y_{B(\delta(w))})$ denotes the $\alpha$-quantile of $Y_{B(\delta(w))}$ when the state of the world is $s\in\mathbb{S},$ see Manski (1988).} Given a choice $u(\delta,s)$ we use the optimality concept of minimax regret to choose a rule for the player. In particular, define regret of a rule $\delta$ when the state of nature is $s$ as
The objective is to find a rule $\delta^{\ast},$ if one exists, that satisfies
For the remainder of this paper, we assume that the player is concerned about expected outcome. Minimax regret rules have been derived analytically only in very few cases. We propose an algorithm to generate a treatment rule whose maximal regret gets arbitrary close to the minimax regret value. The algorithm is based on a result in Robinson (1951).
Robinson's (1951) algorithm
Robinson (1951) considers a finite two-player zero-sum game with payoff matrix $A=(a_{ij})$ for $i=1,..,f$ and $j=1,...,g.$ When the row-player (player 1 from now on) chooses action $i$ and the column player (player 2 from now on) chooses action $j$ then player 1 gets $a_{ij}$ and player 2 gets $-a_{ij}.$ Each player can choose a mixed strategy over her $f$ and $g$, respectively, actions, that is, player 1 can choose a probability distribution $p_{i},$ $i=1,..,f,$ such that $p_{i}\geq0$ and $ {\textstyle\sum\nolimits_{i=1}^{f}} p_{i}=1$ (and $q_{j},$ $j=1,..,g,$ such that $q_{j}\geq0$ and $ {\textstyle\sum\nolimits_{j=1}^{g}} q_{j}=1$ for player 2$,$ respectively.) By the minimax theorem there exists distributions such that the inequality (that holds for all distributions)
holds as an equality. Robinson (1951) provides an iterative procedure where in the $n$-th iteration, mixed strategies $\delta^{n}$ and $\nu^{n}$ for players 1 and 2, defined by $(p_{in})_{i=1,..,f}$ and $(q_{jn})_{j=1,...,g},$ respectively, are picked such that
and the common limit equals the value of the game. The procedure works as follows. Start with any one of the $f$ possible actions of player 1. The mixed strategy $\delta^{1}$ puts weight one on that action. Pick any one of the $g$ possible actions of player 2 that is a best response to $\delta^{1}$. The distribution $\nu^{1}$ puts weight one on that action. For the iteration, assume $\delta^{n}$ defined by $(p_{in})_{i=1,..,f}$ and $\nu^{n}$ defined by $(q_{jn})_{j=1,...,g}$ are given. Pick any one of the $f$ possible actions of player 1 that is a best response to $\nu^{n}$ i.e. maximizes player 1's payoff. The mixed strategy $\delta^{n+1}$ is then defined as $\frac{n-1} {n}\delta^{n}+\frac{1}{n}I(\delta_{BR}^{n}),$ where $\delta_{BR}^{n}$ denotes a best response by player 1 and $I(\cdot)$ denotes a point mass on the action in the brackets. Pick any one of the $g$ possible actions of player 2 that is a best response to $\delta^{n+1}$, i.e. maximizes player 2's payoff. The distribution $\nu^{n+1}$ is defined as $\frac{n-1}{n}\nu^{n}+\frac{1}{n} I(\mu_{BR}^{n}),$ where $\mu_{BR}^{n}$ denotes a best response by player 2. Theorem 1 by Robinson (1951) establishes that this algorithm guarantees that ((ref)) holds. Furthermore, Fudenberg and Levine (1998, Proposition 2.2) establish that if the distributions used in each round converge for both players, then the limits must constitute a mixed strategy Nash equilibrium.\footnote{This procedure may not work for games with generic payoffs or more than two players, because the empirical distribution of the strategies may not converge. See references in Fudenberg and Levine (1998).}
We first consider the binary case where $S=\{0,1\}^{T}$ and $\mu=(\mu _{1},...,\mu_{T})\in M\subset\lbrack0,1]^{T}.$ The policymaker and nature play the roles of players 1 and 2, respectively, in Robinson's (1951) setup above. The elements $a_{ij}$ in the payoff matrix $A$ represent negative regret when the policymaker and nature choose actions $i$ and $j,$ respectively. Player 1 aims to maximize negative regret while player 2 aims to minimize it.
In the next subsection we suggest discretizing nature's parameter space to conform with Robinson's (1951) requirement of only finitely many actions for both players. Given outcomes are assumed to be in $\{0,1\}$ and given there are $T$ possible treatments on which data might be observed, there are only finitely many different samples $w_{N}$ that can arise. Denote by $W$ the number of different samples, $(w_{N1},...w_{NW})$ say, that can arise. Any treatment policy $\delta$ can then by summarized as a $T\times W$ matrix (or a $TW$ vector), where the $w$-th column contains $\delta(w_{Nw})\in\Delta^{T-1}$ for $w=1,...,W.$ If one takes as the actions for the policymaker the set of nonrandomized treatment rules then this results in a finite set of actions\footnote{For example, if the sample contains $N_{t}$ observations for treatment $t$, $t\in\mathbb{T}$ then $W=2^{N}$, where $N=N_{1}+...+N_{T}.$and there are $T^{W}$ many different nonrandomized treatment rules. That number grows very fast in both $N$ and $T.$} and mixing these actions one obtains all treatment rules as defined in ((ref)). In some applications the finite set of actions may contain also randomized rules. In all applications considered below one needs to choose a finite set of actions, denoted by $D,$ such that, when mixing over the actions in $D$ is allowed for, then one obtains the set of all treatment rules $\mathbb{D}$ the policymaker can choose from, that is
The algorithm applies straightforwardly to any such set of action $D$ and therefore policy restrictions can be easily implemented.
In this subsection we define and discuss an $\varepsilon$-discretization of the action space of nature. Denote by $||\cdot||$ the Euclidean norm.
Definition ($\varepsilon$-discretization$\mathbf{)}$. We call a finite subset $M_{\varepsilon}\subset M$ an $\varepsilon$-discretization of the action space of nature if for any $\mu\in M$ we can find a $\mu_{\varepsilon}\in M_{\varepsilon}$\emph{ such that }$\Vert\mu_{\varepsilon}-\mu\Vert<\varepsilon.$
Comment. Often one can take $M_{\varepsilon}$ as $\{\mu=(\mu _{1},...,\mu_{T})\in M;$ $\mu_{t}=\overline{n}_{t}\varepsilon$ for any $\overline{n}_{t}\in\mathbb{N}$ for all $t=1,...,T\}$ i.e. one takes an evenly-spaced grid with step size $\varepsilon.$ However, such a construction will not always lead to an $\varepsilon$-discretization, for example, for certain choices of $M$ the resulting set $M_{\varepsilon}$ could even be empty.
We now establish that as $\varepsilon\rightarrow0$ the minimax regret value of the game in which nature is restricted to DGPs from an $\varepsilon $-discretization $M_{\varepsilon}$ converges to the minimax regret value of the original game. We assume that the regret function $R(\delta,\cdot)$ is continuous in $\mu\in M$ uniformly in $\delta\in\mathbb{D},$ i.e. $\forall\lambda>0$ there exists $\eta>0$ such that when $\Vert\mu-\mu^{\prime }\Vert<\eta$ for $\mu,\mu^{\prime}\in M$ then for all $\delta\in\mathbb{D}$ we have $|R(\delta,\mu)-R(\delta,\mu^{\prime})|<\lambda$.
Comments. 1. Continuity of $R(\delta,\cdot)$ is a weak assumption that we verify in several examples below. Together with compactness of $M$ the condition implies that $\max_{\mu\in M}R(\delta,\mu)$ exists for any $\delta\in\mathbb{D}.$ Note that in Lemma (ref) we allow for the possibility that a minimax regret rule may not exist. We define the value $V$ using the infimum over all treatment rules. Often the $\inf$ in the definition of $V$ (and $V_{m}$) can be replaced by a $\min$, e.g. if $\max_{\mu\in M}R(\delta,\mu)$ depends continuously on $\delta$ and $\mathbb{D}$ is compact.
2. Lemma (ref)(i) states that the minimax regret value for the case where nature's parameter space equals $M_{\varepsilon_{m}}$ converges to the value of the game when the parameter space equals $M$ as $\varepsilon _{m}\rightarrow0.$ Lemma (ref)(ii) states that if one uses a rule $\delta_{\varepsilon_{m}}$, that is approximately minimax regret in the case where nature's parameter space is $M_{\varepsilon_{m}},$ in a situation where nature's parameter space equals $M$ then the resulting minimax regret value converges to the value of the game with parameter space $M$ as $\varepsilon_{m}\rightarrow0.$ That is, $\delta_{\varepsilon_{m}}$ is \textquotedblleft asymptotically\textquotedblright\ minimax regret in the case where nature's parameter space equals $M$ in the sense that maximal regret for the rule $\delta_{\varepsilon_{m}}$ converges to the minimax regret value as one lets the \textquotedblleft stepsize\textquotedblright\ $\varepsilon_{m}$ in the discretization go to zero. We are not claiming that the rule $\delta_{\varepsilon_{m}}$ converges to a minimax regret rule in the original model as $\varepsilon_{m}\rightarrow0$, the convergence statement is about maximal regret$.$ In this paper, we are proposing an algorithm that produces a treatment rule whose maximal regret with parameter space equal to $M_{\varepsilon_{m}}$ converges to the minimax regret value of the discretized model (which in turn converges to the minimax regret value of the original model as $\varepsilon_{m}\rightarrow0$.)
3. We make the discretization of nature's action space explicit in our discussion. But note that any numerical approach to approximate minimax regret rules via an iterative algorithm that relies on repeatedly calculating best responses by nature through grid search also effectively uses discretization.
4. We are currently working on explicit upper bounds for $V-V_{m}$ as a function of $\varepsilon_{m}.$ Such bounds can be worked out in our lead examples below as expressions of Lipschitz constants of certain functions.
In this subsection we describe in detail the algorithm based on Robinson (1951) used to approximate minimax regret rules in the discretized setup, that is, we consider the case where $S=\{0,1\}^{T}$ and $\mu=(\mu_{1},...,\mu _{T})\in M_{\varepsilon}$ for a small $\varepsilon>0.$ The discretization $M_{\varepsilon}$ of $M$ is kept fixed throughout the iterations. We also allow for a possible modification suggested by Leslie and Collins (2006) regarding the weights used in the updating of the strategies. Recall that as specified in ((ref)) we denote by $D$ a finite set of actions, such that, when mixing over the actions in $D$ is allowed for, then one obtains the set of all treatment rules $\mathbb{D}$ the policymaker can choose from. For example, $D$ could be chosen as the set of nonrandomized treatment rules which is finite and satisfies ((ref)).
The algorithm provides a sequence of treatment rules and strategies by nature. For $n\geq1$ we denote by $\delta^{n}$ the treatment rule in the $n$-th iteration, by $\nu^{n}$ the empirical distribution of strategies for nature up to time $n,$ and by $R^{n}$ a lower bound on the minimax regret value obtained in the $n$-th iteration. To apply the algorithm, pick a small threshold $\xi>0$ and a sequence of updating weights $\alpha_{n}$ for $n=1,2,...$ that will be specified further below$.$
Comments. 1. Regarding the iteration step iv) note that for a best response $\delta_{BR}^{n}$ against $\nu^{n}$ it is necessary and sufficient that whenever
holds, $\delta_{BR}^{n}$ gives zero weight to the \textquotedblleft dominated\textquotedblright\ treatment $t^{\prime}.$\footnote{One can always find a nonrandomized best response $\delta_{BR}^{n}.$ Unless of course one imposes certain restrictions on the class of treatment rules that impose randomization.} Importantly, an application of Bayes' rule then allows for a straightforward solution to the minimization problem in iv) that provides a very significant computational gain relative to other methods, such as grid search, to solve that problem. Namely, assume nature picks the mixed strategy $\nu^{n}$ that puts nonzero weights $p_{m}$ on exactly the mean vectors $\overline{\mu}_{m}=(\mu_{1m},...,\mu_{Tm})\in M_{\varepsilon}$ for $m=1,...,\overline{m}.$ Then,
and therefore ((ref)) holds iff
For a given sample $w_{N}$ and choices of $p_{m}$ and $\overline{\mu}_{m}$ for $m=1,...,\overline{m}$ the expressions in ((ref)) can be easily calculated (where $P(w_{N}|$nature picks $\overline{\mu}_{m})$ obviously depends on the sampling design that is being employed).
2. Choosing the weights $\alpha_{n}=1/n$ corresponds to the algorithm proposed in Robinson (1951). In that case, every iteration involves optimizing against the empirical distribution function of strategies chosen up to this point. Other choices of $\alpha_{n}$ satisfying $\alpha_{n}>0,$ $\alpha _{n}\rightarrow0$, and $\sum_{n=1}^{\infty}\alpha_{n}=\infty$ have been suggested in Leslie and Collins (2006), e.g. $\alpha_{n}=(C+n)^{-\eta}$ for some constants $\eta\in(0,1]$ and $C>0$ (which nests $\alpha_{n}=1/n$ when $C=0$ and $\eta=1)$ or $\alpha_{n}=1/\log(C+n).$ Based on our experience in several examples, we find that $\alpha_{n}=(C+n)^{-\eta}$ with $\eta=.7$ and $C=5$ works quite well.
3. In the applications of the algorithm considered below regret goes to zero as the sample size $N$ goes to infinity. Therefore, a \textquotedblleft small\textquotedblright\ threshold $\xi$ in one setting may not be small in another setting. It therefore makes sense to modify the break command in ((ref)) by also making sure that the approximation error relative to the actual regret is small, that is to check whether $(R(\delta^{n},\mu_{BR}^{n})-R^{n-1})/R^{n-1}<\xi.$
4. In practice, after the algorithm terminates, one does not necessarily use the treatment rule obtained in the last iteration. One tracks the maximum regret level for the treatment rules generated during the entire iteration process, and chooses the treatment rule that has the minimum level of maximum regret among those rules. This is because there is no guarantee that maximal regret will decrease in each iteration, so it is possible that the rule generated in the last iteration is not the best one amongst the rules considered during all iterations.
5. Bounds: Note that $R^{n}=R(\delta_{BR}^{n},\nu^{n})$ denotes the minimal regret against a particular mixed strategy by nature and therefore is nonbigger than the minimax regret value. Analogously, $R(\delta^{n},\mu _{BR}^{n})$ denotes maximal regret against a particular mixed strategy by the policymaker and therefore is nonsmaller than the minimax regret value. If $R^{n}=R(\delta_{BR}^{n},\nu^{n})$ and $R(\delta^{n},\mu_{BR}^{n})$ are close to each other, they are both necessarily close to the minimax regret value of the discretized model. In any iteration of the algorithm $R(\delta^{n} ,\mu_{BR}^{n})-R^{n}$ provides an upper bound for how far away the maximal regret of the currently considered treatment rule is from the minimax regret value.
If one lets $n$ go to infinity (and never uses the break command in step ii) of the iteration) then by Robinson's (1951, Theorem 1) in the case of $\alpha_{n}=1/n$ and by Leslie and Collins (2006, Corollary 5) for the other cases in the proposition below, $R^{n}$ converges to the minimax regret value of the discretized game. We formulate this important result as a proposition.
Comment. 1. Leslie and Collins (2006) provide some evidence that for the more general choices of weights $\alpha_{n}$ one might be able to speed up the convergence rate relative to the choice $\alpha_{n}=1/n.$ An important topic for future research is to theoretically work out the convergence speed as a function of the chosen weights.
Assume one has found a minimax regret rule $\delta$ (or approximate minimax regret rule $\delta_{\varepsilon})$ in the setup with $S=\{0,1\}^{T}$ and mean vector $\mu\in M\subset\lbrack0,1]^{T}$ for a certain sampling design, such as fixed assignment with $N_{t}$ observations for $t\in\mathbb{T}$ or random assignment with $P(t_{i}=t)=p_{t}$ for all $i=1,...,N$ and $t\in\mathbb{T}.$ We show that then the so-called coarsening approach can be used to generate a minimax regret rule (or approximate minimax regret rule) for the case $S=[0,1]^{T}$ and the same restriction on the mean vector. The \textquotedblleft coarsening trick\textquotedblright\ proceeds as follows:
Coarsen the outcomes $y_{t_{1},1},...,y_{t_{N},N}$ in the sample $w_{N} =(t_{i},y_{t_{i},i})_{i=1,...,N}$ by replacing each $y_{t_{i},i}$ by an independent draw $\widetilde{y}_{t_{i},i}$ from $\widetilde{Y}_{t_{i},i} \in\{0,1\}$ from a Bernoulli random variable with success probability $y_{t_{i},i}$ for $i=1,...,N.$ Denote by $\widetilde{w}_{N}=(t_{i} ,\widetilde{y}_{t_{i},i})_{i=1,...,N\text{ }}$ the coarsened sample. Define a new treatment rule $\delta^{C}$ by setting $\delta^{C}(w_{N})=\delta (\widetilde{w}_{N})$ (or by $\delta_{\varepsilon}^{C}(w_{N})=\delta _{\varepsilon}(\widetilde{w}_{N})).$
Part i) of the following proposition states that then the treatment rule $\delta^{C}$ is minimax regret with $S=[0,1]^{T}$ with mean restriction $M.$ The coarsening approach has been introduced when $T=2$ and $M=[0,1]^{T}$, see, e.g. Cucconi (1968), Gupta and Hande (1992), Schlag (2003, 2006), and Stoye (2009), and applied with arbitrary $T$ in Chen and Guggenberger (2024) but it can also be employed here with mean restriction $M$. Part ii) of the proposition shows that coarsening can also be applied to approximate minimax regret rules in the case $S=\{0,1\}^{T}$ and given $M$ to obtain approximate minimax regret rules in the case $S=[0,1]^{T}$ with same mean restriction $M.$
Comments. 1. The proof of Proposition (ref) i) adapts the proofs in Schlag (2006) and Stoye (2009) from the case with equal sample sizes, $T=2$ and $M=[0,1]^{2}$ to the case considered here with arbitrary $T$ and $M$ and the $N_{t}$ not necessarily all equal. The proposition could likely be generalized to alternative sampling designs.
2. Proposition (ref) ii) is an important result. It establishes that approximate minimax regret rules can be obtained for complex problems through a combination of a numerical approach applied in a simpler setup and the coarsening approach. In particular, it applies to the setup of the example considered in Section (ref).
In this section we look at an important special case of the general setup in the previous section, namely the case of a policymaker who needs to choose between two treatments after being informed by a sample consisting of $N_{t}$ independent observations from each treatment $t=1,2.$ That is, here, $T=2$ and $\mathbb{T}=\{1,2\}.$ We assume that the policymaker's objective is expected outcome, $u(\delta,s)=E_{s}Y_{B(\delta(w_{N}))}$ and that realizations are either successes or failures, that is $S=\{0,1\}^{2}.$ We can then apply the coarsening approach to deal with the general case $S=[0,1]^{2}.$ Given that observations are independent wlog we can assume that under $s\in\mathbb{S}$ the marginals $(Y_{1},Y_{2})$ are independent and that therefore the joint distribution is fully pinned down by the mean vector $(\mu_{1},\mu_{2})\in M=[0,1]^{2}.$ We first consider the case here where the policymaker is completely agnostic and does not have any a priori information about the mean vector. Then, in Section (ref) we apply the algorithm to find approximate minimax regret rules when $M$ is a strict subset of $[0,1]^{2}.$ From now on, we identify any $s\in\mathbb{S}$ with its resulting mean vector.
An analytical formula for minimax regret rules is known only in the case where the $N_{t}$ are equal, that is, in the case of \textquotedblleft matched treatment assignment\textquotedblright. The following statement holds for any integer $T\geq2.$
Comments. 1. Proposition (ref) was proven by Schlag (2006) and Stoye (2009) for the case $T=2$ and for arbitrary finite $T$ by Chen and Guggenberger (2024). The proof uses the well-known Nash equilibrium approach, see e.g. Berger (1985), that is based on the insight that the action of the policymaker in any Nash equilibrium in the zero sum game between the policymaker and nature (with nature's payoff being regret and the policymaker's payoff being negative regret) is automatically a minimax regret rule. See Chen and Guggenberger (2024) for a reproduction of the simple proof of that result. Note that in the zero sum game nature is allowed to randomize over its actions where an action by nature is simply a vector of means $(\mu_{1},\mu_{2})\in\lbrack0,1]^{2}.$ From now on we denote by $\Delta \mathbb{S}$ the space of randomized rules for nature.\footnote{Note though that being part of a Nash equilibrium is a sufficient but not a necessary condition for a minimax rule. See Guggenberger, Mehta, and Pavlov (2024) for an example of a minimax rule that is not part of a Nash equilibrium.} $\medskip$
When the $N_{t}$ are not all the same then no analytical results are known about minimax regret rules - even in the case $T=2$. We make a tiny bit of progress in that regard and next provide an analytical formula for minimax regret rules in the special case where $\min_{t=1,2}\{N_{t}\}=0.$ Wlog in the following proposition assume $N_{1}=0$ and $N_{2}>0$.
Comments. 1. The proof establishes that a least favorable distribution by nature is given by randomizing uniformly between the two mean vectors $(0,1/2)$ and $(1,1/2).$
2. Note that for any $n_{2}$ and $n_{2}^{\prime}$ in $\{0,1...,N_{2}\}$ such that $n_{2}+n_{2}^{\prime}=N_{2}$, we have $\delta_{2}(0,n_{2})+\delta _{2}(0,n_{2}^{\prime})=(n_{2}+n_{2}^{\prime})/N_{2}=1.$ Thus, the treatment rule satisfies the type of symmetry condition that we formally introduce below in ((ref)).
3. We put substantial effort in deriving analytical derivations for minimax regret rules in more general cases but were not successful. Therefore, in what follows below, we will instead approximate minimax regret rules by a version of the algorithm from Section (ref) based on fictitious play.$\medskip$
In the next subsection, we show that minimax regret rules can be found in a class of treatment rules restricted by a symmetry condition. We then provide an algorithm that leverages the insights of fictitious play with the restrictions imposed by symmetry, and finally report results from the algorithm for several choices of $(N_{1},N_{2}).$
From now on, we represent a sample $w_{N}$ by the number of successes $n_{t}$ for each treatment, that is, (with some abuse of notation) we write $w_{N}=(n_{1},n_{2}).$
In the context of treatment assignment with unbalanced samples when $T=2$ and $S=\{0,1\}^{2}$ we make the following definition.
Definition (symmetric treatment rule). We call a treatment rule $\delta$ symmetric when
whenever $w_{N}=(n_{1},n_{2})$ and $w_{N}^{\prime} =(n_{1}^{\prime},n_{2}^{\prime})$ satisfy
Comments. 1. Note that when $\delta$ is symmetric then trivially also $\delta_{1}(w_{N})+\delta_{1}(w_{N}^{\prime})=1$ for all $w_{N}=(n_{1},n_{2})$ and $w_{N}^{\prime}=(n_{1}^{\prime},n_{2}^{\prime})$ that satisfy ((ref)). Further note, that when both $N_{1}$ and $N_{2}$ are even, then necessarily $\delta_{2}(w_{N})=1/2$ for $w_{N}=(N_{1}/2,N_{2}/2).$ Therefore, symmetric rules sometimes need to randomize.
2. Symmetry conditions are used in the analytical derivations of minimax regret rules in Stoye (2009, Proposition 1) and Chen and Guggenberger (2024, Proposition 1) but the symmetry condition defined here in the particular context of unbalanced samples appears to be new.
3. The main purpose of the symmetry condition employed here is to gain computational improvements. Note that if $\delta$ is symmetric then knowing $\delta_{2}(w_{N})$ automatically fixes the value for $\delta_{2} (w_{N}^{\prime}).$ E.g. if $N_{1}=1$ and $N_{2}=5$ then knowing the value of $\delta_{2}(0,n_{2})$ for $n_{2}=0,1,...,5$ pins down the value of $\delta _{2}(1,5-n_{2}).$ Therefore rather than searching over all $2\times6=12$ values of $\delta_{2}(n_{1},n_{2})$ for $n_{1}=0,1$ and $n_{2}=0,1,...,5$ one only needs to consider values for the 6 values of $\delta_{2}(0,n_{2}).$ If for instance one were to employ an algorithm whose computation time increases exponentially with $(n_{1}+1)(n_{2}+1)$ then searching in the class of symmetric rules instead would reduce the computation time by a factor $\exp((n_{1}+1)(n_{2}+1))/\exp(.5(n_{1}+1)(n_{2}+1)).\medskip$
We next show why symmetry is an important condition. The next proposition establishes that one can find an action pair $(\delta,s)$ with $\delta \in\mathbb{D}$ and $s\in\Delta\mathbb{S}$ for the policymaker and nature, respectively, that constitutes a Nash equilibrium and where $\delta$ is symmetric.
Comments. 1. In the setup of Proposition (ref)(i) nature randomizes over mean vectors that come in pairs. For every mean vector $(\mu_{1m},\mu_{2m})$ that nature picks with positive probability the mean vector $(1-\mu_{1m},1-\mu_{2m})$ is also picked with the same probability. Together with Proposition (ref)(ii) it follows that a Nash equilibrium of the unrestricted game exists in which the policymaker plays a symmetric treatment rule. The proof of Proposition (ref) (ii) establishes that if $\delta$ is symmetric then $R(\delta,(1-\mu_{1} ,1-\mu_{2}))=R(\delta,(\mu_{1},\mu_{2})).$
2. Proposition (ref) implies that if there exists a minimax regret rule that is part of a Nash equilibrium then
A mixed strategy $s\in\Delta\mathbb{S}$ by nature is a random vector with outcomes in $[0,1]^{2}$ that specifies which mean vector nature chooses. The condition ((ref)) restricts this random variable to only pick a certain number of pairs $(\mu_{1},\mu_{2})$ and $(1-\mu_{1},1-\mu_{2})$ whose two elements have to be chosen with equal probabilities. In the next subsection we are applying Algorithm (ref) to the formulation of the problem on the right side of the equality in ((ref)) using a discretized version of nature's parameter space.
3. The symmetry condition is relevant in the case where $M$ satisfies the following restriction. If
That restriction is satisfied in the lead example where $M=[0,1]^{2}.$
4. An important question for current research concerns the development of techniques that allow one to systematically determine the set of all symmetry conditions in this and any other application. We came across the above symmetry condition after we applied the algorithm for small sample sizes and noted a pattern in the obtained approximation of minimax regret rules. We don't know whether there are other symmetry conditions that we have not yet discovered.
To justify the discretization of nature's action space below, we first establish that in the example considered here, the assumption of Lemma (ref) about the regret function $R(\delta,\cdot)$ being continuous in $\mu\in M$ uniformly in $\delta\in\mathbb{D}$ is satisfied.
For any $\varepsilon=p^{-1}$ for $p\in\mathbb{N}$ we will use the set
as the $\varepsilon$-discretization of the set $(\mu_{1},\mu_{2})\in M=[0,1]^{2}.$ That guarantees that if $(\mu_{1},\mu_{2})\in M_{\varepsilon}$ then also $(1-\mu_{1},1-\mu_{2})\in M_{\varepsilon}.$
Next, we apply the general Algorithm (ref) from Subsection (ref) to the problem considered here, assuming that ((ref)) holds. Using the insights from Proposition (ref) as expressed in ((ref)) we exploit the particular symmetrical structure of the current application to simplify the complexity of the problem. Namely, we take $D$ as the finite set of symmetric rules with outcomes in $\{0,1\}$ except for samples $w_{N}=(n_{1},n_{2})$ for which $n_{1}=N_{1}/2$ and $n_{2}=N_{2}/2$ (which can only happen when both sample sizes are even). For nature, the finite set of actions, $M_{\varepsilon }^{Na}$ say, consists of those mixed strategies that uniformly randomize between a pair of $(\mu_{1},\mu_{2})$ and $(1-\mu_{1},1-\mu_{2})$ with $(\mu_{1},\mu_{2})\in M_{\varepsilon}$. The algorithm then follows the exact same steps as in the Algorithm (ref) but with the particular choices of $D$ and finite set of actions for nature as just described. For clarity, we write down the entire algorithm again.
Comment. 1. To implement the algorithm, one has to chose $p=1/\varepsilon\in\mathbb{N}.$ That choice, obviously, is a trade-off between computational effort and closeness of the minimax regret value in the original model and the $\varepsilon$-discretized one. By increasing $p$ nature becomes \textquotedblleft more powerful\textquotedblright\ and thus the minimax regret value in the $\varepsilon$-discretized model increases in $p$ and (as shown in Lemma (ref)) converges to the minimax regret value of the original model as $p\rightarrow\infty.$ Each iteration step i) is solved by a grid search over all $(p+1)^{2}$ possible choices of mean vectors.
2. Note that $\delta^{1}$ satisfies the symmetry condition. It is randomized when both $N_{1}$ and $N_{2}$ are even for samples $w_{N}$ such that $n_{1}/N_{1}=n_{2}/N_{2}=1/2.$ Alternatively, one could initiate the algorithm with any other symmetric treatment rule. We suggest picking the empirical success rule because it is a good starting point as it is known that its maximal regret converges to zero at the optimal rate, see Kitagawa and Tetenov (2018). Note that$\ \nu^{n}$ satisfies the condition given in the Proposition (ref)(i).
3. The best response of the policymaker is calculated via Bayes rule as in ((ref)) and uses the formula
when $w_{N}=(n_{1},n_{2}).$
4. Given this is a special case of the general setup, Proposition (ref) about convergence of the maximal regret of the sequence of treatment rules to the minimax regret value of the $\varepsilon $-discretized model continues to hold.
5. When potential outcomes are elements of $[0,1]$ rather than $\{0,1\}$ one applies the coarsening approach to the obtained treatment rule from Algorithm (ref).
6. If there are discrete covariates $X$ in the model then an important result in Stoye (2009) states that one obtains a minimax regret rule by simply solving the conditional-on-$X$ problems.
In this subsection, we investigate the performance of Algorithm (ref) for the example of unbalanced samples with $T=2.$
We first consider the case of balanced samples where $N_{1}=N_{2}.$ The reason is that in that case Proposition (ref) provides the minimax regret rule in analytical form and Stoye (2009, Corollary 1) provides a formula to calculate the minimax regret value. The latter allows us to directly assess the performance of the algorithm. We also use the case of balanced samples to experiment with different weighting schemes $\alpha_{n}$ and initializations of the treatment rule.
Specifically, we consider $N_{1}=N_{2}\in\{5,10,20,40,60,80,100,200\}$. In the discretization of the parameter space for nature in ((ref)) we use $p=1000$ throughout.\footnote{We also do some robustness checks by comparing the results to the case where we only take $p=500$ and the results vary only very slightly$.$ In Stoye (2009, Corollary 1) we use stepsize .000001 in a gridsearch over different values of $a$ (that appears in Stoye (2009, Corollary 1) to evaluate the formula for minimax regret given there.}
First we experiment with different choices $\eta$ and $C$ in the weighting scheme $\alpha_{n}=(C+n)^{-\eta}$ discussed in Leslie and Collins (2006) when $N_{1}=N_{2}=40$. Specifically, we consider a grid of values for $\eta \in\lbrack.1,1]$ and for $C\in\lbrack0,10].$ Note that the particular choice $C=0$ and $\eta=1$ leads to the weights proposed in Robinson (1951)$.$ \footnote{Because $\delta^{n+1}=(1-\alpha_{n+1})\delta^{n}+\alpha_{n+1} \delta_{BR}^{n}.$one obtains $\delta^{1}=\delta_{BR}^{1}$ with $\alpha _{n}=1/n$ and the impact of the initialization is only transferred through its impact on $\mu_{BR}^{n}.$} This experiment suggests that $\eta\in \lbrack.5,.7]$ and $C\in\lbrack5,10]$ work \textquotedblleft best.\textquotedblright\ We will only report results for $\alpha_{n}=1/n$ and $\alpha_{n}=(5+n)^{-.7}$ below. Those results will document the importance that the weighting scheme has on the convergence speed of maximal regret to the minimax regret value.
We also experiment with two different initializations $\delta^{1}$ of the algorithm, namely, we initialize with the particular empirical success (ES) rule suggested in Algorithm (ref). However, given that this initialization is very close to the actual minimax regret rule in the case of balanced samples, we also consider one that is very different from the actual minimax regret rule to challenge the algorithm. Namely we take the symmetric $\delta^{1}$ defined by $\delta_{2}^{1}(n_{1},n_{2})=1$ if $n_{1}/N_{1}<1/2$ or if ($n_{1}/N_{1}=1/2$ and $n_{2}/N_{2}<1/2).$ (Consequently, by symmetry, $\delta_{2}^{1}(n_{1},n_{2})=0$ if $n_{1} /N_{1}>1/2$ or ($n_{1}/N_{1}=1/2$ and $n_{2}/N_{2}>1/2)).$ For easy reference, we refer to this initialization by SO (for \textquotedblleft suboptimal\textquotedblright).
In TABLE I, we report the minimax regret value using the formula in Stoye (2009, Corollary 1) for the original model (before discretization) for the subset $N_{1}=N_{2}\in\{5,60,100,200\}$ of the sample sizes we considered. In addition, for each initialization (ES\ and SO) and each of the two weighting schemes $\alpha_{n}$ we report the maximal regret of $\delta^{n}$ for $n\in\{1,150,500,2000\}$ (over all actions by nature with $p=1000$)$.$ All digits of maximal regret of $\delta^{n}$ that coincide with the ones of the actual minimax regret value are displayed in bold, starting at the tenths place, then the hundredths place, etc. until there is a discrepancy.\footnote{The additional results for other $(N_{1},N_{2})$ values appear in the Supplementary Appendix. As discussed in Comment 1 after Algorithm (ref) minimax regret of the discretized model is smaller than the minimax regret value (but converges to the latter as $p\rightarrow\infty).$ That explains why in very few cases (like e.g. when $N_{1}=N_{2}=5)$ the reported maximal regret is (very slightly, i.e. in the 10$^{-7}$ digit) smaller than the minimax regret value of the original model.}
The key findings from the results in TABLE I are as follows. The results reflect the convergence results from Proposition (ref). As the number of iterations of the algorithm increases the maximal regret of $\delta^{n}$ approaches the minimax regret value. As suggested by the theory, this holds for both choices of $\alpha_{n}$ and initializations $\delta^{1}$ in all cases considered. We find that $\alpha_{n}=(5+n)^{-.7}$ leads to faster convergence than $\alpha_{n}=1/n.$ Namely, maximal regret of $\delta^{500}$ and $\delta^{2000}$ is identical to minimax regret up to at least four digits after the comma (and sometimes up to seven digits after the comma) for the former weighting scheme. Quite remarkably, maximal regret of $\delta^{150}$ already typically approximates minimax regret up to four digits (in very few cases only up to three or even up to five digits). Instead, for the latter weighting, maximal regret of $\delta^{500}$ (and $\delta^{2000})$ coincides with minimax regret only up to two or three (two to four) digits. Based on these results, we strongly suggest using $\alpha_{n}=(5+n)^{-.7}$ over the original weighting $1/n$ proposed by Robinson (1951). These results also reinforce an earlier remark about the importance of using a good weighting scheme and potentially obtaining theoretical insights on the convergence speed as a function of the weighting scheme.
Regarding the initialization, the values reported for maximal regret of $\delta^{1}$ illustrate that SO is indeed a very suboptimal treatment rule. E.g. for $(N_{1},N_{2})=60$ maximal regret under SO equals .3851399 while under ES it equals .0170815. Somewhat surprisingly however, Algorithm (ref) recovers quite quickly from the suboptimal initialization and displays quite similar convergence patterns when started with SO versus ES. When considering maximal regret of $\delta^{150}$ often the algorithm started with SO leads to at least equal if not smaller values! A reason for why the initialization may not matter that much is that no matter what the initialization is, given the iterative structure of the algorithm, the least favorable distribution of nature needs to build up from scratch. One might want to consider modifications of the algorithm that also start off with an informed guess on a least favorable distribution. Overall, the finding that the initialization is not crucial for fast convergence is good news.
Substantial improvements in terms of maximal regret are obtained by the algorithm after only quite few iterations. E.g. when $(N_{1},N_{2})=5$ and $\alpha_{n}=(5+n)^{-.7},$ the maximal regret of ES\ equals .0703386 while minimax regret equals .054308. After 150 iterations the algorithm generates a treatment rule whose maximal regret equals .054309.
As mentioned already, $R(\delta^{n},\mu_{BR}^{n})$ is not monotonically decreasing in $n.$ Likewise, $R^{n}$ is not monotonically increasing in $n$. In practice therefore, after a certain number of iterations, $N$ say, one should report the interval
that contains the minimax regret value (of the discretized game) and use the treatment rule $\delta^{n}$ for the $n$ that minimizes $R(\delta^{n},\mu _{BR}^{n})$ over all $n\leq N.$ For example, for ES and $\alpha_{n} =(5+n)^{-.7},$ $I_{2000}$ equals [.0542240,.0543086], [.0155017,.0155298], [.0119668,.0120253], [.0083640,.0085001] for $(N_{1},N_{2})=5,$ $60,$ $100,$ $200,$ respectively. Note again here that the upper endpoint of $I_{N}$ maybe smaller than the minimax regret value of the original (not discretized) model. E.g. that happens for $(N_{1},N_{2})=200$ but only in the 10$^{-7}$ digit.
In all examples, not only this one, as one would expect, maximal regret decreases in the sample size.
Regarding computation time (using $p=1000,$ ES,\ $\alpha _{n}=(5+n)^{-.7},$ and 2000 iterations in all cases) for $(N_{1} ,N_{2})=(10,10)$ it takes less than 5 minutes while for $(N_{1},N_{2} )=(200,200)$ it takes about 24 minutes. In the latter case, the precision for maximal regret of $\delta^{2000}$ is about $3\mathbb{\times}10^{-6}$. This is quite remarkable; namely, note that there are $2^{N_{1}(N_{2}+1)/2+N_{2}/2}$ symmetric treatment rules that take values $\delta_{2}(n_{1},n_{2})\in\{0,1\}$ except when $n_{1}/N_{1}=n_{2}/N_{2}=1/2$ (in which case $\delta_{2} (n_{1},n_{2})=1/2).$ With $(N_{1},N_{2})=(200,200)$ that number equals $2^{20200}\approx10^{6080.8}!$
Note that even larger sample sizes are possible. E.g. we also considered $(N_{1},N_{2})=(250,250)$, where maximal regret for $\delta^{n}$ equals .008007, .007665, .007615, and .007603 for $n=1,150,500,$ and $2000,$ respectively, and $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ equals .007668, .001310, .000472, and .000223 for these choices of $n$ and computation time being about 39 minutes$.$ In that case $2^{N_{1}(N_{2}+1)/2+N_{2}/2}=2^{31500} \approx10^{9482.4}!$ The minimax regret value of the original model equals .007602. When $N_{1}=N_{2}=300$ there are \ about $10^{13636.7}$ symmetric \textquotedblleft nonrandomized\textquotedblright\ rules. The theoretical minimax regret value equals .006940. Maximal regret of $\delta^{n}$ equals .007279, .007053, .006950, and .006939 for $n=1,150,500,$ and $2000,$ respectively, and $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ equals .006998, .001222, .000352, and .000271 for these choices of $n$. Computation time is 51 minutes.\ With $N_{1}=N_{2}=400$ computation time increases to 1 hour 27 minutes.
To give some idea about the complexity of least favorable distributions, when $(N_{1},N_{2})=20,$ ES,\ and $\alpha_{n}=(5+n)^{-.7}$ the best response by nature against $\delta^{2000\text{ }}$is a mixed strategy with $\overline {m}=142$ in Proposition (ref).
TABLE\ I: Maximal regret of $\delta^{n}$ for various choices of $n$, $(N_{1},N_{2}),$ weighting schemes and initializations.
$(N_{1},N_{2})=200;$\ minimax regret value=.00850086
$(N_{1},N_{2})=100;$\ minimax regret value=.01202529
$(N_{1},N_{2})=60;$\ minimax regret value=.01553018
$(N_{1},N_{2})=5;$\ minimax regret value=.05430889
Next, we apply Algorithm (ref) to unbalanced samples for which no analytical formula is known for the minimax regret rule. Namely, we consider all combinations of $N_{1}\in\{10,50,100\}$ and $N_{2}-N_{1}\in\{10,50,100\}$ using the initialization as in Algorithm (ref). Based on the insights from the simulations in the balanced case we use $\alpha_{n}=(5+n)^{-.7}.$ All reported results use $p=1000$ again. Given we do not have an analytical formula for the minimax regret value, TABLE II reports results on the maximal regret of $\delta^{n}$ together with the bound $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ (for how far the maximal regret of $\delta^{n}$ differs at most from the minimax regret value of the discretized model) for $n\in\{1,150,500,2000\}$ and six of the nine choices of $(N_{1},N_{2})$. The remaining results appear in the Supplementary Appendix. In addition, we report $I_{2000}$ introduced in ((ref)).
TABLE II: Maximal regret of $\delta^{n}$ and $R(\delta^{n},\mu _{BR}^{n})-R^{n}$ for several $n$ and $I_{2000}$ for several $(N_{1},N_{2}).$
The key findings from TABLE II are as follows. As expected from the theory, maximal regret of $\delta^{n}$ converges (to the minimax regret value of the discretized model) and $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ goes to zero as the number of iterations $n$ increases. In all cases considered $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ for $n=2000$ ranges between .000003 and .000208. Furthermore, in all cases considered the width of $I_{2000}$ falls into the interval $[10^{-6},$ $9\times10^{-5}].$ That implies that after 2000 iteration, one has found a treatment rule whose maximal regret is at most $9\times10^{-5}$ larger than the minimax regret value of the (discretized) model.
We also considered Robinson's (1951) weighting, $\alpha_{n}=n^{-1}$. Consistent with the findings above from balanced samples, in all cases $\alpha_{n}=(5+n)^{-.7}$ produced smaller maximal regret for $\delta^{2000}.$ For brevity, we do not report those results.
To give some idea about the structure of the minimax regret rule, in the Supplementary Appendix we report $\delta^{5000}$ for $N_{1}=10,$ $N_{2}=20$, ES,\ and $\alpha_{n}=(5+n)^{-.7}$.
What are the gains of incorporating symmetry as in Algorithm (ref) versus using Algorithm (ref) in terms of computation time and maximal regret after a given number of iterations? Consider e.g. the case $p=1000,$ ES, and $\alpha_{n}=(5+n)^{-.7}$. When $(N_{1},N_{2})=(200,200)$ it takes 42 minutes to run 2000 simulations (versus 24 minutes when symmetry is exploited) and maximal regret of $\delta^{2000}$ equals .008505 (versus .008503 when symmetry is exploited). For $(N_{1},N_{2})=(10,60)$ it takes 11 minutes to run 2000 simulations with maximal regret of $\delta^{2000}$ equal to .028595 while the algorithm that exploits symmetry only takes 5.5 minutes and maximal regret of $\delta^{2000}$ equals .028580. The advantage of Algorithm (ref) for these sample sizes is therefore mostly in terms of computation speed.
Next, we provide some comparisons with the \textquotedblleft multiplicative weights\textquotedblright algorithm of Aradillas Fern\'{a}ndez, Blanchet, Montiel Olea, Qiu, Stoye, and Tan (2024, ABMQST from now on).\footnote{We would like to thank Pepe Montiel for sharing very helpful insights related to this discussion.} Given the gigantic number of nonrandomized treatment rules even for moderate numbers of $N_{1}$ and $N_{2}$ it is not possible to implement that algorithm when the policymaker is the \textquotedblleft outer\textquotedblright\ player. However, using the identity $\inf_{\delta\in\mathbb{D}}\sup_{s\in S}R(\delta,s)=\sup_{s\in S}\inf _{\delta\in\mathbb{D}}R(\delta,s)$ discussed in the Appendix B of ABMQST, one could let the policymaker play the role of the \textquotedblleft inner\textquotedblright\ player and use comparisons of conditional means and Bayes' rule to solve $\inf_{\delta\in\mathbb{D}}R(\delta,s)$ for given $s$ as we suggest in ((ref))-((ref)). Using that approach, the subgradient and nature's strategy are $(p+1)^{T}$-dimensional vectors. Calculating the former, requires $(p+1)^{T}$ many regret calculations (as does grid search used in fictitious play). Storing the latter, while likely still possible when $T=2$, is likely impossible when $T>2.$ On the other hand, fictitious play only requires storing the strategies of the policymaker and nature. The former can be characterized by a $(N_{1}+1)\times(N_{2}+1)$ matrix, while the latter (in our experiments) is very sparse with support only on some 100 points after 2000 iterations. In contrast, by construction, \textquotedblleft multiplicative weights\textquotedblright\ assigns positive probability to each of the $(p+1)^{T}$ actions by nature. Thus, calculation of the sums appearing in ((ref)) requires summing $\overline{m}=(p+1)^{T}$ terms for each of the $(N_{1}+1)(N_{2}+1)$ arguments of the treatment rule. Instead, using fictitious play, $\overline{m}$ (in our experiments) is of the order of 100 even after 2000 iterations which leads to considerably less computational effort.\footnote{Potentially, using some thresholding approach could alleviate the computational burden for \textquotedblleft multiplicative weights.\textquotedblright} Thirdly, note that the maximal number of iterations $\lceil2\ln((p+1)^{T})/\epsilon ^{2}\rceil$ given in Theorem 1 of ABMQST that guarantees an $\epsilon$ minimax regret rule equals $3.4\times10^{9}$ when $T=2,p=1000,$ and $\epsilon =9\times10^{-5}$. Instead, recall that in all cases reported in TABLE\ II after just 2000 iterations, a minimax regret rule is found whose maximal regret is at most $9\times10^{-5}$ larger than the minimax regret value of the (discretized) model. Conversely, if for $T=2$ and $p=1000$ one sets $\lceil2\ln((p+1)^{T})/\epsilon^{2}\rceil$ equal to 2000 one obtains $\epsilon=0.118.$
In general, we believe that a comparison of two algorithms and the notion of optimality of an algorithm, should take into account the number of iterations and the number of operations performed in each iteration. The upper bound $\lceil2\ln((p+1)^{T})/\epsilon^{2}\rceil$ given in Theorem 1 of ABMQST is a powerful result that applies to a broad class of models. But it does not seem to be binding in the specific application considered here.
We now consider the case where the set $M$ of mean vectors no longer equals the unrestricted set $[0,1]^{2}$. Instead, we examine a scenario where the policymaker uses a priori information about certain parametric restriction on $(\mu_{1},\mu_{2}).$ Being able to accommodate such restrictions is highly empirically relevant. For example, average wage after job training should be expected to be nonsmaller. If one also factors in a fixed cost for job training into the analysis one ends up with a set of particular restrictions on the mean vectors $(\mu_{1},\mu_{2})$. For the purpose of illustration, we take
For restricted $M$, Proposition (ref) that relied heavily on symmetry, no longer applies. Therefore, we do not restrict the search to symmetric rules and use Algorithm (ref) to approximate the minimax regret rule.
We consider sample sizes $N_{1}=N_{2}\in\{5,10,20,50\},$ $(N_{1},N_{2} )\in\{(5,10),(10,5),(10,50),(50,10)\},$ $\alpha_{n}=(5+n)^{-.7},$ $p=1000,$ and use 2,000 iterations. We initialize with $\delta^{1}$ equal to the ES\ rule defined by $\delta_{2}^{1}(n_{1},n_{2})=1$ if $n_{1}/N_{1}\leq n_{2}/N_{2}$ and $\delta_{2}^{1}(n_{1},n_{2})=0$ otherwise and take $D$ to be the set of all nonrandomized rules. We take
TABLE\ III gives results on the maximal regret of $\delta^{n}$ and the bound $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ for $n\in\{1,150,500,2000\}.$
TABLE III: Maximal regret of $\delta^{n}$ and $R(\delta^{n},\mu _{BR}^{n})-R^{n}$ for $n\in\{1,150,500,2000\}.$
As the key findings TABLE\ III\ illustrates again the convergence properties of maximal regret of $\delta^{n}$ and convergence to zero of $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ as $n$ increases. After 2000 iterations the algorithm has reached treatment rules $\delta^{2000}$ whose maximal regret is at most $1.95\mathbb{\times}(10^{-4})$ away from the minimax regret value$.$ Compared to TABLE\ I for equal sample sizes we find that here maximal regret of $\delta^{n}$ is always smaller given that nature is less powerful here given the restrictions on its parameter space.
Furthermore, the results from TABLE III illustrate that when there is a priori information the ES rule may be a very suboptimal choice. For example when $(N_{1},N_{2})=(5,5)$ or $(N_{1},N_{2})=(10,5)$ its maximal regret equals .059049, more than 1.6 times or 1.8 times as much as the maximal regret of $\delta^{2000}$ which equals .035986 or .032552. With $M$ being restricted it is very hard to guess a reasonable treatment rule. This provides strong motivation for the algorithm provided in this paper whose convergence properties do not seem to be affected much by the initialization.
We describe $\delta_{2}^{2000}$ in the case where $N_{1}=N_{2}=5.$ We find that $\delta_{2}^{2000}(n_{1},n_{2})=1$ if $n_{1}<n_{2}$ and $\delta _{2}^{2000}(n_{1},n_{2})=0$ if $n_{1}>n_{2}.$ Finally, $\delta_{2} ^{2000}(n_{1},n_{1})$ equals 1, .948767, .906576, .844678, .704494, and .533296 when $n_{1}=0,1,...,5,$ respectively. Next we (partially) describe $\delta_{2}^{2000}$ in the case where $N_{1}=5$ and $N_{2}=10.$ In that case, $n_{1}/N_{1}<n_{2}/N_{2}$ still implies $\delta_{2}^{2000}(n_{1},n_{2})=1$ but it is no longer true that for all 30 cases where $n_{1}/N_{1}>n_{2}/N_{2},$ always $\delta_{2}^{2000}(n_{1},n_{2})=0$ holds$.$ In five of those cases $\delta_{2}^{2000}(n_{1},n_{2})>0.$\footnote{We ran the algorithm for 4000 iterations and now only two such cases (up to 10$^{-6}$ precision) occured. Namely $\delta_{2}^{4000}(1,0)=1$ and $\delta_{2}^{4000}(1,1)=.000280.$ So, when 1 success for treatment 1 and zero successes for treatment 2 are observed, treatment 2 should be chosen with probability 1 - that seems quite counterintuitive.}
Even though we cannot exploit any symmetry conditions for this scenario, the algorithm is still running very quickly.\footnote{What significantly reduces the running time is that the grid search over mean vectors when updating nature's strategy requires less time given the imposed restrictions on $M$.} E.g. it takes less than 4 and 4.5 minutes to obtain 2000 iterations when $N_{1}=N_{2}=5$ and $50$, respectively; virtually the same computation time in both cases.
Suppose the policymaker knows the mean outcome $\mu_{T}$ of a status quo treatment. She needs to consider whether to switch from the status quo to one of $T-1$ alternative treatments whose mean outcomes are unknown. Stoye (2009) considers the case $T=2$ and works out a minimax regret rule. In this section, we apply Algorithm (ref) to $T>2$ where a sample of equal sizes on $T-1$ alternative treatments is observed. Potential outcomes are elements of $\{0,1\};$ the general case where outcomes are in $[0,1]$ is then dealt with via the coarsening approach of Proposition (ref). A priori information on restrictions of the mean vector $\{\mu_{1},...,\mu _{T-1}\}$ can be incorporated. Without further restrictions $M=[0,1]^{T-1} \times\mu_{T}.$ As in the previous example, to reduce the computational effort, we derive certain symmetry conditions first.
As before, we can identify the DGP by the vector of means. The observed sample $w_{N}$ can be summarized by the number of observed successes $n_{t}$ for treatments $t=1,...,T-1$. For a rule $\delta$ and sample $w_{N}$ we denote by $\delta_{t}(w_{N})$ the probability that treatment $t$ (for $t=1,...,T-1)$ will be chosen and consequently by $1-\sum_{t=1}^{T-1}\delta_{t}(w_{N})$ the probability that the status quo persists. We suppress the dependence on $\mu_{T}$ in the notation when deriving a minimax regret rule for a particular $\mu_{T}.$
There are $T$ treatments to choose from and treatment $T$ is the known status quo$.$ Data of equal sample size $\overline{N}$ is observed for each of the $T-1$ innovations. We take $S=\{0,1\}^{T-1}$. Denote by $\sigma^{-1}$ the inverse of a permutation $\sigma$ in the group of permutations. We make the following definition.
Definition (symmetric treatment rule). We call a treatment rule $\delta$ symmetric\footnote{It should not be confusing that the notion of symmetry changes in different applications.} if whenever the vectors $w_{N}=(n_{1},...,n_{T-1})$ and $w_{N}^{\prime}=(n_{1}^{\prime },...,n_{T-1}^{\prime})$ are permutations of each other, i.e. $n_{\sigma(t)}=n_{t}^{\prime}$ for some permutation $\sigma$\emph{ on }$\{1,...,T-1\}$ \emph{then}
Comments. 1. As in Section (ref), the symmetry property allows for computational gains in approximating minimax regret rules. Note that ((ref)) implies that $\delta_{T}(w_{N})=\delta_{T} (w_{N}^{\prime}).$ In the case $T=3$, symmetry requires that $\delta _{1}((n_{1},n_{2}))=\delta_{2}((n_{2},n_{1}))$ for all $n_{1},n_{2} \in\{0,1,...,\overline{N}\}.$ Thus, for a symmetric treatment rule $\delta,$ given values $\delta_{2}(w_{N})$ and $\delta_{3}(w_{N})$ for $w_{N} =(n_{1},n_{2})$ one can determine $\delta_{1}(w_{N})$ and $\delta_{t} ((n_{2},n_{1}))$ for $t\in\{1,2,3\}.$ Therefore, knowing $\delta_{t} ((n_{1},n_{2}))$ for $t\in\{2,3\}$ and all $n_{2}\geq n_{1}$ one automatically knows the entire treatment rule.
The next proposition establishes that one can find an action pair $(\delta,s)$ with $\delta\in\mathbb{D}$ and $s\in\Delta\mathbb{S}$ for the policymaker and nature, respectively, that constitutes a Nash equilibrium and where $\delta$ is symmetric according to the definition just given.
Comments. 1. Proposition (ref) establishes that a Nash equilibrium of the unrestricted game exists in which the policymaker plays a symmetric treatment rule. Therefore, if there exists a minimax regret rule that is part of a Nash equilibrium then
Using the formulation of the problem as on the right side of the equation in ((ref)), one can pick as $D$ the finite set of symmetric nonrandomized rules. The proof of part (ii) follows from the fact that if $\delta$ is symmetric then $R(\delta,(\mu_{1},...,\mu_{T}))=R(\delta ,(\mu_{\sigma(1)},...,\mu_{\sigma(T-1)},\mu_{T}))$ for any permutation $\sigma$ on $\{1,...,T-1\}.$
We establish that the assumption of Lemma (ref) about the regret function $R(\delta,\cdot)$ being continuous in $\mu\in\lbrack 0,1]^{T-1}\times\mu_{T}$ uniformly in $\delta\in\mathbb{D}$ is satisfied.
We will employ the analogous discretization strategy given in ((ref)). For given $\mu_{T}\in\lbrack0,1],$ some $p\in\mathbb{N}$ and $\varepsilon=1/p$ define
We modify the general algorithm to reflect the symmetry property under the setup of testing $T-1$ innovations. Pick again a tolerance level $\xi>0.$
Comments. 1. In each iteration, the best response of the policymaker can be calculated via Bayes rule using ((ref)). The best response by nature is solved again by grid search over all $(p+1)^{T-1}$ possible choices of mean vectors.
2. If $M$ is a strict subset of $[0,1]^{T-1}\times\mu_{T}$ the symmetry property can in general not be exploited and Algorithm (ref) is used instead.
3. Note that the existence of best responses of the particular type in iteration steps i) and iv) is guaranteed by Proposition (ref).
We implement Algorithm (ref) for the case $T=3$, sample sizes $\overline{N}=N_{1}=N_{2}\in\{5,10,20,30,$ $40,50,100,200\}$ and known mean of the status quo treatment equal to $\mu_{3}\in\{.2,.5,.8\}.$ The initialization rule is the empirical success rule described in the beginning of Algorithm (ref). We choose $p=1000$ and $\alpha_{n}=(5+n)^{-.7}$. TABLE IV reports maximal regret of $\delta^{n}$ and $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ for various choices of $n$ and $I_{2000}$ for a subset of the sample sizes.\footnote{To save space we report the remaining results in the Supplementary Appendix.}$\bigskip$
TABLE IV: Maximal regret of $\delta^{n}$ and $R(\delta^{n},\mu _{BR}^{n})-R^{n}$ for several $n$ and $I_{2000}$ for several $\overline{N}$ and $\mu_{3}.$
$\bigskip$
As the key findings TABLE\ IV\ illustrates again the convergence properties of maximal regret of $\delta^{n}$ and convergence to zero of $R(\delta^{n},\mu_{BR}^{n})-R^{n}$ as $n$ increases. After 2000 iterations the algorithm has reached treatment rules $\delta^{2000}$ whose maximal regret is at most $1.7\mathbb{\times}(10^{-4})$ away from the minimax regret value. TABLE\ IV\ also illustrates that it is beneficial to keep track of the maximal regret of the treatment rules along all iterations $n$ as the right boundary of $I_{2000}$ maybe strictly smaller than maximal regret of $\delta^{2000}$ indicating that a treatment rule with smaller maximal regret occurred in an earlier iteration. What is the impact of $\mu_{3}$ on the results? The minimax regret value when $\mu_{3}=0.5$ is the largest (amongst those considered) followed by the minimax regret value when $\mu_{2}=0.2$ and $\mu_{1}=0.8$, although the difference is very small among the latter two.
We propose an algorithm to numerically approximate minimax regret rules and prove that the maximal regret of the treatment rules generated by the algorithm converges to the minimax regret of the discretized model. The latter converges to the minimax regret value of the original model as the discretization becomes finer. We illustrate in several examples that the algorithm works very well in practice. Importantly, our framework allows incorporation of a priori information that the policymaker can use regarding the set of DGPs that nature can choose from. Also, the framework allows for a restricted set of policy rules that the policymaker can choose from, reflecting the important case where policy restrictions prevent the policymaker from using certain rules. However, in the latter case one would in general not be able to use the approach based on Bayes' rule.
There are several important open questions that go beyond the scope of the current paper and require future research. In particular, we found that the choice of weights $\alpha_{n}$ in the updating step of the algorithm significantly impacted the convergence speed. Theoretical results should be developed to work out optimal choices for the weights. Second, we found that certain symmetry conditions can be exploited to significantly reduce the complexity of the algorithm. Techniques need to be developed to detect all such symmetries. Third, implementation details of the algorithm under policy restrictions are quite important in cases where the approach via Bayes' rule is no longer applicable. Fourth, progress has to be made in allowing for covariates in the model.
There are many additional examples and related applications that the algorithm or variants of it could be applied to. In particular, the proposed algorithm may be helpful in approximating optimal tests in terms of weighted average power when the null hypothesis is composite.