# Learning the Distribution Map in Reverse Causal Performative Prediction

Daniele Bracale
Department of Statistics
University of Michigan
Ann Arbor, MI 48109
<EMAIL_ADDRESS>
&Subha Maity*
Department of Statistics
University of Michigan
Ann Arbor, MI 48109
<EMAIL_ADDRESS>
&Moulinath Banerjee
Department of Statistics
University of Michigan
Ann Arbor, MI 48109
<EMAIL_ADDRESS>
Yuekai Sun
Department of Statistics
University of Michigan
Ann Arbor, MI 48109
<EMAIL_ADDRESS>
Euqal contributions.

###### Abstract

In numerous predictive scenarios, the predictive model affects the sampling
distribution; for example, job applicants often meticulously craft their
resumes to navigate through a screening systems. Such shifts in distribution
are particularly prevalent in the realm of social computing, yet, the
strategies to learn these shifts from data remain remarkably limited. Inspired
by a microeconomic model that adeptly characterizes agents’ behavior within
labor markets, we introduce a novel approach to learn the distribution shift.
Our method is predicated on a _reverse causal model_ , wherein the predictive
model instigates a distribution shift exclusively through a finite set of
agents’ actions. Within this framework, we employ a microfoundation model for
the agents’ actions and develop a statistically justified methodology to learn
the distribution shift map, which we demonstrate to be effective in minimizing
the performative prediction risk.

##  1 Introduction

Predictive models frequently guide decisions in strategic settings, but their
environmental impact is often ignored. For example, a lender assessing loan
default risk to set interest rates might inadvertently increase default risk
for riskier applicants by charging higher rates, creating a self-fulfilling
prophecy. In addition, borrowers might manipulate their profiles to appear
less risky and secure lower rates. These influences are widespread: crime
predictions shape police resource allocation, affecting crime rates, while
recommendations alter user preferences and consumption. Goodhart’s law
(Strathern, 1997), summarized as “when a measure becomes a target, it ceases
to be a good measure," also hints how predictive models affect their
environments through performative _agents_.

From a probabilistic perspective, performativity manifests itself as a shift
in distribution; agents adapt to prediction models by altering their
attributes over time. Returning to the default risk assessment example, the
self-fulfilling prophecy leads to label shift (Lipton et al., 2018), while
borrowers manipulating their profiles cause a class conditional shift (Maity
et al., 2022). To mitigate these changes, while practitioners often retrain
models (Cormier et al., 2016), a more proactive measure is to incorporate
environmental impacts during model training, known as strategic/performative
prediction (Hardt et al., 2015; Perdomo et al., 2020), which adjusts risk
minimization to account for distribution shifts. This method, while effective,
requires understanding these shifts – a topic not well-covered in the
literature. _Our paper proposes a framework to estimate these distribution
shifts_ , which makes training of prediction tools for performative
environments more accessible to practitioners.

model ($\theta$)action ($A$)$(X,Y)$ Figure 1: Reverse causal performative
prediction

In this paper, we reformulate the setup of reverse causal performative
prediction as introduced in Somerstep et al. (2024), which can be roughly
stated as “the agents doctor their attributes by taking appropriate actions,
and the distributions of modified attributes depend on the predictive model
only through these actions”. To formalize the assumption, we denote the _ex-
post_ distribution of attribute
$(X,Y,A)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$ after deploying a
model $\theta$ as $\mathcal{D}_{\theta}$, where $X$ denotes the covariates,
$Y$ is the response and $A$ is the action. Our reformulation states that
$\mathcal{D}_{\theta}$ depends only through the distribution of agents’
action, i.e. having specified an action $a\in\mathcal{A}$ the
$\mathcal{D}_{\theta}(X,Y\mid A=a)$ is invariant of $\theta$ and therefore,
denoting the invariant distribution as $\mathcal{D}(X,Y\mid A)$ the
$\mathcal{D}_{\theta}$ is decomposed as

$\textstyle\mathcal{D}_{\theta}=\mathcal{D}_{\theta}(A)\times\mathcal{D}(X,Y\mid
A)\,.$ (1.1)

In the second paragraph of our conclusion section 6 we discuss where does this
reverse causal model fit into the broader context of performative prediction,
but for now we move on toward our goal of learning $\mathcal{D}_{\theta}$
within this reverse causal model. To learn $\mathcal{D}_{\theta}$, in our
paper, we assume that the learner has access to adequate ${\sf i.i.d.}$
samples from each of the $\mathcal{D}(X,Y\mid A)$, or better yet, we assume
that $\mathcal{D}(X,Y\mid A)$ is known. Then, the only part that remains to be
learned is $\mathcal{D}_{\theta}(A)$, i.e. the distribution map for the
actions of the agents. In our paper, we propose a framework for learning this
$\mathcal{D}_{\theta}(A)$.

To estimate $\mathcal{D}_{\theta}(A)$, we consider a microfoundation framework
whose motivation comes from the Caote-Loury labor market model (Coate and
Loury, 1993) (see Example 2.2). The best course of action of an agent is
formalized by the _cost-adjusted utility maximization problem_ :

$\textstyle
A\triangleq{\arg\max}_{a\in\mathcal{A}}\operatorname{B}(a,\theta)-C_{a}\,,$
(1.2)

where $\operatorname{B}(a,\theta)$ is the benefit of taking an action $a$
under the model $\theta$, and $C_{a}$ is the cost of the same $a$. Typically,
the $\operatorname{B}(a,\theta)$ is known to the learner. Furthermore, we
frame $C_{a}$ as a random quantity, which encodes an agent’s own preference
for the action $a$. For example, while preparing for a test, a candidate from
a wealthier background would be more willing to enroll for a test-prep course.
Given that $\operatorname{B}(a,\theta)$ is known, in this microfoundation
setting, we learn $\mathcal{D}_{\theta}(A)$ through learning the distribution
of $\\{C_{a};a\in\mathcal{A}\\}$. To keep things simple, in this paper we
assume that _agent’s action space $\mathcal{A}$ is finite_. While it may be
possible to learn this distribution for an arbitrary $\mathcal{A}$, this will
involve considerably more technical challenges and beyond the scope of this
paper; further related discussion is deferred to the concluding section 6.

At this point, it may seem that we have restricted our reverse causal setting
to merely a microfoundation setting described in (1.2), where the agents are
necessarily strategic. But we argue in Section 2.2 (cf. Lemma 2.5) that by
incorporating a random cost into our microfoundation we make it completely
general in the reverse causal setting, as any $\mathcal{D}_{\theta}(A)$ can be
expressed by our microfoundation setup with a suitable choice of benefit
$\mathbf{B}(\theta)\triangleq\\{\operatorname{B}(a,\theta):a\in\mathcal{A}\\}$
and random cost $\mathbf{C}\triangleq\\{C_{a}:a\in\mathcal{A}\\}$. This is not
possible in a usual strategic prediction setting (Hardt et al., 2015), where
the deterministic cost can only allow a strategic agent. In contrast, our
setting also allows for _non-strategic agents_. By _non-strategic_ we mean
that two agents with the same _ex-ante_ $z$ do not necessarily have the same
_ex-post_ $z^{\prime}$ if the cost is random. We defer further related
discussion to Section 2.2.

We end the introductory section with a description of our contribution,
followed by a brief survey of the related literature.

  1. 1.

In Section 2 we introduce the microfoundations in reverse causal models for
learning the distribution map, and we show that any distribution shit in a
reverse causal model can be recovered by a microfoundation framework by
randomizing the cost.

  2. 2.

In Section 3 we provide a method to estimate the distribution map non-
parametrically, for a general number of actions.

  3. 3.

In Section 4 we provide a sequential optimal design algorithm based on the
doubling trick (i.e., every episode is twice the previous one) with $2$
actions. We prove a convergence result of the relative efficiency of the
estimated design density.

  4. 4.

In Section 5 we propose an algorithm based on the doubling trick to estimate
the distribution map $\mathcal{D}_{\theta}$ with a regret bound of
$\widetilde{\mathcal{O}}(M^{\frac{1}{1+\eta}})$, where $\eta$ is the degree of
uniform convergence of the distribution map in the exploration phase and
$\widetilde{\mathcal{O}}$ excludes factors $\log(M)$.

  5. 5.

We consider the Coate-Loury labor market model Coate and Loury (1993) as a
baseline, for which we show convergence results of the relative efficiency in
both theoretical and numerical experiments.

###  1.1 Related work

The performative prediction problem, initially introduced by Perdomo et al.
(2020), encompasses various aspects, with a notable instance being strategic
classification Hardt et al. (2016); Shavit et al. (2020); Levanon and
Rosenfeld (2022). In the context of strategic prediction, agents are presumed
to be utility-maximizing, leading to an implicit determination of the
distribution map by the agents’ utilities. A burgeoning body of literature
focuses on developing algorithms for computing performative optimal policies
Izzo et al. (2021); Levanon and Rosenfeld (2021); Miller et al. (2021). A
related line of research addresses performativity in online settings, with the
objective of devising algorithms that effectively minimize Stackelberg regret
Dong et al. (2018); Chen et al. (2020); Jagadeesan et al. (2022).

A key challenge that impedes the broader adoption of performative prediction
lies in practitioners often not knowing the distribution map. In general,
there are two ways to bypass this problem. The first treats the performative
prediction problem (2.3) as a zeroth-order (i.e. derivative free) optimization
problem, relying on samples from $\mathcal{D}(\theta_{t})$ ($\theta_{t}$ being
optimization algorithm iterates) to solve it without explicit knowledge of the
distribution map $\mathcal{D}(\theta)$ Izzo et al. (2021); Miller et al.
(2021). However, as the authors Miller et al. (2021) state, this method often
leads to slow convergence and curse of dimensionality. The second approach
deals with unknown agent responses by imposing microfoundation models Jang et
al. (2022). This approach benefits from fast convergence rates, leveraging
white-box access to the distribution map Hardt et al. (2016); Levanon and
Rosenfeld (2021); Cutler et al. (2021), but the distribution map is often
unknown in practice, and a misspecification in this map can hinder the finding
of the correct solutions Lin and Zrnic (2023). Our proposed approach
complements the second approach: by learning in a non-parametric way the
microfoundations model from agent response data, we address issues related to
misspecified distribution map, while benefiting from faster optimization
algorithms by utilizing the white-box access to the distribution map. To the
best of our knowledge, current results for estimating the distribution map
assume a parametric model on $\mathcal{D}_{\theta}$, for example, Miller et
al. (2021) assumes a location-scale distribution map generated by the linear
transformation $z_{\theta}=z_{0}+\mu\theta$.

##  2 Reverse causal performative prediction

In a standard strategic prediction setting, agents update their covariates
$X$, but do not update their responses $Y$. Horowitz and Rosenfeld (2023)
considered a more general setting in which agents modify both $X$ and $Y$
using a causal/structural model. Here, agents still change their covariates,
but such changes can propagate through the causal model and (indirectly) lead
to changes in their responses. In their reverse causal model, Somerstep et al.
(2024) assumes that the agents update their $Y\to Y^{\prime}$, which leads to
a change in $X\sim\Phi(\cdot\mid Y^{\prime})$. We further generalize this by
assuming that the agents can modify both $Z=(X,Y)$ as a response to $\theta$,
but only through their action $A$, leading to the structural model in Figure
1. Thus, the _ex-post_ distribution $\mathcal{D}_{\theta}$ depends on $\theta$
only through the marginal distribution of $A$, i.e. through
$\mathcal{D}_{\theta}(A)$. Since $\mathcal{D}_{\theta}$ can be decomposed as
$\mathcal{D}_{\theta}=\mathcal{D}_{\theta}(A)\times\mathcal{D}_{\theta}(Z\mid
A)$, the reverse causal setting is equivalently stated in the following
assumption.

######  Assumption 2.1 (Reverse causal model).

The $\mathcal{D}_{\theta}(Z\mid A)$ are not affected by the prediction model
$\theta$. Moving forward, we drop this dependence on $\theta$ and simply
denote this by $\mathcal{D}(Z\mid A)$.

Our reverse causal model simplifies to the one in Somerstep et al. (2024,
Section 2) if we let $A=Y$.

A key example of our reverse causal model is the Coate-Loury (CL) labor market
model (Coate and Loury, 1993). We describe a variation of this model below,
which will serve as a running example throughout our paper.

######  Example 2.2 (Coate-Loury labor market model (Coate and Loury, 1993)).

Employers seek to hire skilled workers, but while making hiring decisions, are
uncertain whether the workers are skilled ($Y=1$) or unskilled ($Y=0$).
Instead, they observe a score $X$, which is an (imperfect) skill assessment of
workers and hire those whose scores exceed a threshold $\theta$, i.e. hires if
$X>\theta$. Workers respond strategically to the hiring policy by making skill
investments:

$A\triangleq{\arg\max}_{a\in\\{0,1\\}}\omega\bar{F}(\theta\mid a)-C\cdot a,$
(2.1)

where $\omega>0$ is the wage paid to hired workers and $\bar{F}(\theta\mid
a)=\mathbb{P}(X>\theta|Y=a)$ is the survival function of $X$, interpreted as
the probability of hiring a (skilled and unskilled) worker, and finally, $C>0$
is a random cost of worker-specific investment for acquiring skill $Y=1$.
Here, the action $A$ is identical to the response $Y$: whether to be skilled
($A=Y=1$) by making an investment or not ($A=Y=1$), and thus we absorb $Y$
within $A$ while describing the distribution shift. As the distribution of
$X\mid A$ remains unaffected by the threshold $\theta$, the only component of
the distribution of $(X,A)$ that changes is the marginal distribution of $A$,
leading to the distribution shift map

$\textstyle\mathcal{D}_{\theta}(X,A)=\mathcal{D}_{\theta}(A)\times\mathcal{D}(X\mid
A),~{}~{}\mathcal{D}_{\theta}(A)\stackrel{{\scriptstyle\textrm{d}}}{{=}}\operatorname{Bernoulli}(\pi(\theta))$

where $\stackrel{{\scriptstyle\textrm{d}}}{{=}}$ denotes ‘equally distributed’
and $\pi(\theta)$ is the proportion of skilled workers, determined by the
workers whose (expected) wage incentive $I(\theta)$ as below:

$\pi(\theta)\triangleq{\mathbb{P}}_{\theta}\big{\\{}A=1\big{\\}}={\mathbb{P}}\big{\\{}C\leq
I(\theta)\big{\\}},~{}~{}I(\theta)\triangleq\omega\big{\\{}\bar{F}(\theta\mid
1)-\bar{F}(\theta\mid 0)\big{\\}}\,.$ (2.2)

###  2.1 Learning prediction model in reverse causal model

As a proactive approach to learning a model in a performative prediction
setting, Hardt et al. (2015); Perdomo et al. (2020) propose to minimize
_performative risk_ by modifying the standard risk minimization problem to
account for the shift in the underlying distribution:

$\textstyle\min_{\theta}{\mathrm{PR}}(\theta),\quad\textstyle{\mathrm{PR}}(\theta)\triangleq{\mathbb{E}}_{\mathcal{D}_{\theta}}[\ell(\theta;Z)]\,,$
(2.3)

where $\ell$ is an appropriate loss function. For our reverse causal model
(Assumption 2.1), the performative risk simplifies to

$\displaystyle\textstyle{\mathrm{PR}}(\theta)=\textstyle\sum\nolimits_{a\in\mathcal{A}}\mathcal{D}_{\theta}(A=a){\mathbb{E}}\big{[}\ell(\theta;Z)\mid
A=a\big{]}\,,$ (2.4)

where ${\mathbb{E}}[\ell(\theta;Z)\mid A]$ is efficiently estimated once we
have adequate samples from the distribution of $Z\mid A=a$. To keep things
simple, we assume that $\mathcal{D}(Z\mid A=a)$ is known for the moment.

######  Example 2.3 (Coate-Loury model).

Returning to example 2.2, assume that the firm with hiring policy
$\widehat{Y}_{\theta}(X)=\mathbbm{I}\\{X>\theta\\}$ incurs a loss of
$\delta_{0}>0$ (resp. gain of $\delta_{1}>0$) for hiring an unskilled (resp.
skilled) worker. Expressing the gain as a negative loss, we can express the
loss function as
$\ell(\theta;Z)\triangleq\widehat{Y}_{\theta}(X)\\{-\delta_{1}Y+\delta_{0}(1-Y)\\}$.
In this case the performative risk is:

$\textstyle{\mathrm{PR}}(\theta)=\sum\nolimits_{a\in\\{0,1\\}}\mathcal{D}_{\theta}(A=a){\mathbb{E}}\big{[}\ell(\theta;Z)\mid
A=a\big{]}=-\pi(\theta)\delta_{1}\bar{F}(\theta\mid
1)+(1-\pi(\theta))\delta_{0}\bar{F}(\theta\mid 0)\,.$

###  2.2 Microfoundation framework for learning the distribution shift

In order to learn a prediction model by minimizing the performative risk
(2.4), we require $\mathcal{D}_{\theta}$. Since we assume that we know
${\mathbb{E}}[\ell(\theta;Z)\mid A]$, the final puzzle that remains is to
learn $\mathcal{D}_{\theta}(A)$. For this purpose, we propose a
microfoundation framework: an agent pays a random cost $C_{a}$ for their
action $a$ and strategically chooses their best course of action by maximizing
their cost-adjusted utility, as described in (1.2)

$\textstyle
A\triangleq{\arg\max}_{a\in\mathcal{A}}\operatorname{B}(a,\theta)-C_{a}$

where, for an action $a$, $\operatorname{B}(a,\theta)$ is the benefit realized
under the model $\theta$, and $C_{a}$ is the random cost that encodes the
agent’s own preference for the action. We eliminate the edge cases where the
above ${\arg\max}$ has multiple solutions and an agent is in conflict between
multiple actions. Such conflictions can be easily eliminated by assuming that
the distributions of $C_{a}$’s are continuous, for which the ${\arg\max}$ is
unique with probability one.

######  Example 2.4 (Coate-Loury model).

In our example 2.2, one may set
$\operatorname{B}(a,\theta)=\omega\bar{F}(\theta\mid A=a)$, $C_{1}=C$ and
$C_{0}\equiv 0$.

Under this microfoundation framework (1.2) the $\mathcal{D}_{\theta}(A)$ is
expressed as:

$\mathcal{D}_{\theta}(A=a)={\mathbb{P}}\big{\\{}\operatorname{B}(a,\theta)-C_{a}\geq\operatorname{B}(a^{\prime},\theta)-C_{a^{\prime}},~{}\text{for
all}~{}a^{\prime}\neq a\big{\\}}\,.$ (2.5)

Typically, the $\operatorname{B}(a,\theta)$ is known to the learner, e.g. in
Coate Loury example 2.2, the firm typically has access to $\mathcal{D}(X\mid
A)$ from a historical dataset, and can easily calculate
$\operatorname{B}(a,\theta)=\mathbb{P}(X>\theta\mid A=a)$. It only remains to
learn the distribution of $\mathbf{C}\triangleq\\{C_{a};a\in\mathcal{A}\\}$
and, moving ahead, in Section 3 we propose an algorithm for learning this.
But, before moving ahead, we make the following remark about the generality of
the microfoundation framework in the broader context of learning
$\mathcal{D}_{\theta}$ in a reverse causal model.

#### Generality of microfoundation framework:

How restrictive is our framework (1.2), given that agents are strategic? As we
show here, by incorporating a random cost in our microfoundation, we made it
completely general in the reverse causal model that may include _non-
strategic_ agents as well. By _non-strategic_ we mean that two agents with the
same _ex-ante_ $z$ do not necessarily have the same _ex-post_ $z^{\prime}$ if
the cost is random. Moreover, in the following lemma, we show that, for a
suitably chosen benefit, any $\mathcal{D}_{\theta}(A)$ can be expressed using
the microfoundation framework.

######  Lemma 2.5.

For _any_ $\mathcal{D}_{\theta}(A)$ and a benefit function
$\mathbf{B}(\theta)\triangleq\\{\operatorname{B}(a,\theta);a\in\mathcal{A}\\}$
satisfying the property that for every $a,a^{\prime}\in\mathcal{A}$ with
$a\neq a^{\prime}$, $\mathcal{D}_{\theta}(A=a)$ can be written as a fixed
increasing function of
$\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)$, there exists
a random cost vector $\mathbf{C}$, that induces $\mathcal{D}_{\theta}(A)$
through the microfoundation equation (1.2).

The complete proof is in Appendix E, but here we explain the key idea in the
simple case of $|\mathcal{A}|=2$, i.e. $\mathcal{A}=\\{0,1\\}$. We set
$C_{0}\equiv 0$. Since $\mathcal{D}_{\theta}(A=1)$ increases with
$\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta)$, i.e.
$\mathcal{D}_{\theta}(A=1)=G(\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta))$
for an increasing function $G:{\mathbb{R}}\to[0,1]$, we extend $G$ to an
appropriate c.d.f. $\tilde{G}$ over ${\mathbb{R}}$, for which a random cost
$C_{1}\sim\tilde{G}$ leads to microfoundation (1.2), because

$\textstyle{\mathbb{P}}\big{\\{}C_{1}\leq\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta)\big{\\}}=\tilde{G}(\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta))=G(\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta))=\mathcal{D}_{\theta}(A=1)\,.$

#### Misspecification of benefit function:

Although the learner must specify a $\mathbf{B}(\theta)$ for the
microfoundation, Lemma 2.5 indicates that for any choice of
$\mathbf{B}(\theta)$ that meets the the lemma’s condition, the microfoundation
can accurately express $\mathcal{D}_{\theta}(A)$. This allows a flexible
choice of $\mathbf{B}(\theta)$, as any misspecifications in the benefit are
corrected within the estimated cost distribution, thereby ensuring the proper
specification of $\mathcal{D}_{\theta}(A)$.

##  3 Learning the distribution of agents’ action

In this section, we propose a simple algorithm for estimating the
$\mathcal{D}_{\theta}(A)$, which was the remaining unknown part of the
distribution shift. Recall the expression of
$\mathcal{D}_{\theta}(a)\triangleq\mathcal{D}_{\theta}(A=a)$ in (2.5), which
we first re-express in a compact vector inequality form with a matrix
$\mathbf{L}_{a}\in{\mathbb{R}}^{(\mathcal{A}-\\{a\\})\times\mathcal{A}}$
defined as

$\textstyle\\{\mathbf{L}_{a}(u,v);u\in\mathcal{A}-\\{a\\},v\in\mathcal{A}\\}=\begin{cases}1&\text{if}~{}v=a,u\in\mathcal{A}-\\{a\\}\\\
-1&\text{if}~{}u=v\neq a\\\ 0&\text{otherwise}\end{cases}$

With the $\mathbf{L}_{a}$ the $\mathcal{D}_{\theta}(a)$ can be compactly
expressed as

$\displaystyle\mathcal{D}_{\theta}(a)$
$\displaystyle=\textstyle{\mathbb{P}}\big{\\{}C_{a}-C_{a^{\prime}}\leq\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta),\forall
a^{\prime}\neq
a\big{\\}}={\mathbb{P}}\\{\mathbf{L}_{a}\mathbf{C}\preceq\mathbf{L}_{a}\mathbf{B}(\theta)\\}=\operatorname{F}_{a}\big{(}\mathbf{L}_{a}\mathbf{B}(\theta)\big{)}$
(3.1)

where $\preceq$ is the element-wise inequality operator,
$\mathbf{C}\triangleq\\{C_{a};a\in\mathcal{A}\\}$,
$\mathbf{B}(\theta)\triangleq\\{\operatorname{B}(a,\theta);a\in\mathcal{A}\\}$,
$\operatorname{F}_{a}$ is the multivariate cumulative distribution function
(cdf) of $\mathbf{L}_{a}\mathbf{C}$. Learning ${\mathcal{D}}_{\theta}(A)$
reduces to learning $\\{\operatorname{F}_{a};a\in\mathcal{A}\\}$. For this
purpose, we assume that the learner deploys predictive models
$\theta_{1},\dots,\theta_{M}$ and observes the estimated proportions of the
actions of agents $\hat{\pi}_{1},\dots,\hat{\pi}_{M}$, i.e., for each $m$ the
$\hat{\pi}_{m}=\\{\hat{\pi}_{m}(a),a\in\mathcal{A}\\}$ consists of the
estimated proportion of agents $\hat{\pi}_{m}(a)$ who chose to take the action
$a$ as a response to the model $\theta_{m}$. In the following remark, we
explain how a learner may estimate these proportions.

######  Remark 3.1.

We explain two settings for estimating $\hat{\pi}_{m}$: with or without direct
access to agents’ actions. For the model $\theta_{m}$

  1. (1)

If the learner has access to the actions $\\{A_{m,i};i\in[n_{m}]\\}$ from
$n_{m}$ ${\sf i.i.d.}$ draws from $\mathcal{D}_{\theta_{m}}$ then she can
directly estimate the proportions as
$\hat{\pi}_{m}(a)=\nicefrac{{1}}{{n_{m}}}\sum\nolimits_{i=1}^{n_{m}}\mathbbm{I}\\{A_{m,i}=a\\}$.

  2. (2)

If the actions are not directly accessible to the learner, who can only access
${\sf i.i.d.}$ $\\{Z_{m,i};i\in[n_{m}]\\}$ from $\mathcal{D}_{\theta_{m}}$,
the moment matching approach from Lipton et al. (2018) for estimating label
shift can be easily adapted here. Since we assume that we know
$\mathcal{D}_{\theta_{m}}(Z\mid A)$, for a ‘suitable’ choice of
$h_{m}:\mathcal{Z}\to{\mathbb{R}}^{\mathcal{A}}$, that has a good
discriminating power over $\mathcal{D}_{\theta_{m}}(Z\mid A)$, i.e. smallest
singular value of the following matrix is sufficiently larger than zero

$\textstyle\Delta_{m}\triangleq\big{[}{\mathbb{E}}_{\mathcal{D}_{\theta_{m}}}[h_{m}(Z)\mid
A=a];a\in\mathcal{A}\big{]}\in{\mathbb{R}}^{\mathcal{A}\times\mathcal{A}}\,,$

the $\hat{\pi}_{m}$ can then be simply estimated as
$\hat{\pi}_{m}=\Delta_{m}^{-1}\\{\nicefrac{{1}}{{n_{m}}}\sum\nolimits_{i=1}^{n_{m}}h_{m}(Z_{m,i})\\}$.
As explained in Lipton et al. (2018, Theorem 3), the error in this estimator
is smaller for a higher value of smallest singular value of $\Delta_{m}$.

Having estimated the $\hat{\pi}_{m}$’s, the
$\\{\operatorname{F}_{a};a\in\mathcal{A}\\}$ can be learned by solving a least
squares (LS) problem with an appropriate monotone shape constraint. Recall
that $\operatorname{F}_{a}$ is the cdf of $\mathbf{L}_{a}\mathbf{C}$ and thus
a coordinate-wise monotone function. We incorporate this shape constraint in
the following LS problem:

$\big{\\{}\widehat{\operatorname{F}}_{a};a\in\mathcal{A}\big{\\}}\in\underset{\\{F_{a};a\in\mathcal{A}\\}\in\mathcal{F}}{{\arg\min}}\left\\{\begin{aligned}
&\textstyle\sum\nolimits_{a\in\mathcal{A}}\sum\nolimits_{m=1}^{M}n_{m}\big{\\{}\operatorname{F}_{a}\big{(}\mathbf{L}_{a}\mathbf{B}(\theta_{m})\big{)}-\hat{\pi}_{m}(a)\big{\\}}^{2},\\\
&\textstyle\text{subject
to}~{}\sum\nolimits_{a\in\mathcal{A}}\operatorname{F}_{a}\big{(}\mathbf{L}_{a}\mathbf{B}(\theta_{m})\big{)}=1~{}\text{for
all}~{}m\in[M]\,,\\\ \end{aligned}\right.$ (3.2)

where $\mathcal{F}$ is the collection of coordinate-wise monotone non-negative
functions. The loss corresponding to the estimate $\hat{\pi}_{m}$ is weighted
by $n_{m}$ based on its estimation error: a $\hat{\pi}_{m}$ calculated from a
larger sample of size $n_{m}$ is statistically more accurate and therefore is
weighted with a weight of higher importance $n_{m}$. The LS problem in (3.2)
is a coordinate-wise monotone regression problem (Chatterjee et al., 2018; Han
et al., 2019); it is a convex quadratic program that can be efficiently
solved. Armed with these $\widehat{\operatorname{F}}_{a}$, the learner plugs
them in to obtain (an estimate of) the distribution map
$\widehat{{\mathcal{D}}}_{\theta}(A)$, where for an $a\in\mathcal{A}$ the
$\widehat{\mathcal{D}}_{\theta}(a)=\widehat{\operatorname{F}}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta))$.
We summarize our approach in Algorithm 1.

Algorithm 1 Learning discrete agent responses

1: Observe agent responses
$\hat{\pi}_{1},\dots,\hat{\pi}_{M}\in\Delta^{|\mathcal{A}|-1}$ to predictive
models $\theta_{1},\dots,\theta_{M}$

2: Estimate $\\{\operatorname{F}_{a}$, $a\in\mathcal{A}\\}$ as
$\\{\widehat{\operatorname{F}}_{a};a\in\mathcal{A}\\}$ with (coordinate-wise)
monotone regression (3.2)

3: Estimate distribution map ${\mathcal{D}}_{f}(A)$ as
$\widehat{\mathcal{D}}_{\theta}(a)\leftarrow\widehat{\operatorname{F}}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta))$,
$a\in\mathcal{A}$

An alternative to LS is the maximum likelihood estimator (MLE) to estimate
$\operatorname{F}_{a}$ (see Appendix A). However, under isotonic shape
constraint, it is well established that the MLE and LS estimators coincide
(Robertson et al., 1988).

###  3.1 Example. Univariate cost: CL model.

Consider the CL model in Example 2.2, where let $\\{\hat{\pi}_{m}:m\in[M]\\}$
be the estimated proportions of qualified workers (i.e.
$\pi_{m}\triangleq\mathcal{D}_{\theta}(A=1)$) after they have been exposed to
the thresholds $\\{\theta_{m}:m\in[M]\\}$; see Remark 3.1 for their
estimation. At this point, we set the cost of $A=0$ (the worker remains
unskilled) to zero and only estimate the random cost of becoming skilled
($A=1$). Denoting this cost by $C$, the optimization in (3.2) simplifies to
just estimating $F_{C}$ (c.d.f. of $C$) as

$\textstyle\hat{F}_{C}\leftarrow\arg\min_{F\in\mathcal{F}}\sum\nolimits_{m=1}^{M}n_{m}\\{F(b_{m})-\hat{\pi}_{m}\\}^{2},$
(3.3)

where $b_{m}=I(\theta_{m})$ and $\mathcal{F}$ is a collection of non-negative
and monotonically increasing functions.

Next, we provide a uniform convergence result for the estimated c.d.f. in
(3.3) assuming that the learner observes the $A_{m,i}$’s. While it is possible
to establish a similar result for the second estimator proposed in Remark 3.1
which does not require these $A_{m,i}$’s, we leave it for future research
interest as we believe this will be technically more challenging and verify
the quality of estimated c.d.f. obtained from such $\hat{\pi}_{m}$ in a
synthetic experiment. To establish the uniform convergence we assume that the
true $F_{C}$ is smooth and the design points $b_{m}$ in (3.3) are “regular”,
which are formalized below.

######  Assumption 3.2.

  1. (A1)

For an $0\leq\alpha<1$ the true $F_{C}$ is $\alpha$-Hölder smooth, i.e. there
exists a $K>0$ such that $\left|F_{C}(b)-F_{C}(b^{\prime})\right|\leq
K|b-b^{\prime}|^{\alpha}$ for any $b,b^{\prime}\in{\mathbb{R}}$.

  2. (A2)

The design points $b_{m}$ are either equidistant over the range of
$\\{I(\theta):\theta\in{\mathbb{R}}\\}$ or drawn as ${\sf i.i.d.}$ from a
density which is bounded away from zero.

Now we establish a uniform convergence result in the following proposition,
which follows from a direct application of (Mösching and Dümbgen, 2020,
Theorem 3.3).

######  Proposition 3.3.

Suppose that
$\hat{\pi}_{m}=\nicefrac{{1}}{{n_{m}}}\sum\nolimits_{i=1}^{n_{m}}A_{m,i}$ and
define $n\triangleq\sum\nolimits_{m}n_{m}$. Under assumptions (A1) & (A2) the
$\hat{F}_{C}$ defined in (3.3) has the following rate of convergence:

$\textstyle\sup_{b\in[\delta_{n},w-\delta_{n}]}|\hat{F}_{C}(b)-F_{C}(b)|=\mathcal{O}_{P}\big{\\{}\big{(}\nicefrac{{\log
n}}{{n}}\big{)}^{\nicefrac{{\alpha}}{{(2\alpha+1)}}}\big{\\}}$

where, the $\delta_{n}=\kappa\big{(}\nicefrac{{\log
n}}{{n}}\big{)}^{\nicefrac{{1}}{{(2\alpha+1)}}}$ with an universal constant
$\kappa$ (see Mösching and Dümbgen (2020, Remark 3.1 & 3.2)).

---
Figure 2: Estimation of $F_{C}$

#### Estimating proportions with unknown actions:

Here we employ the second method proposed in Remark 3.1, where the
discriminating function $h_{m}$ is chosen simply as the classifier for action
$A$ using $X$. This classifier can be fitted on a previously collected
dataset, where both $A$ and $X$ are observed. Having obtained the
$\hat{\pi}_{m}$ for thresholds $\theta_{m}$, we use (3.3) to estimate
$\hat{F}_{C}$. In Figure 2 we compare the $\hat{F}_{C}$ with the true $F_{C}$,
where we utilized two techniques for estimating a monotonically increasing
functions: isotonic regression (Robertson et al., 1988) and monotone quadratic
spline (Meyer, 2008). As the latter approach yields a smooth estimate, this is
a better estimator, because the true $F_{C}$ is smooth.

While we move on to design of model $\theta_{m}$ that is to be deployed, in
the appendix, we demonstrate how $F_{C}$ can be estimated within an
appropriate parametric model (see Appendix B), and results for estimating
distribution map with multiple actions $|\mathcal{A}|\geq 3$ (see Appendix C).

##  4 Optimal design for deploying models under binary actions

Assuming $\mathcal{A}=\\{0,1\\}$, we now discuss the optimal design/choice for
$\\{\theta_{m}:m\in[M]\\}$ to minimize the mean square error (MSE) between the
true $\operatorname{F}\triangleq\operatorname{F}_{1}$,
($\operatorname{F}_{0}=1-\operatorname{F}$) and the estimated
$\hat{\operatorname{F}}\triangleq\hat{\operatorname{F}}_{0}$ as defined in
Section 3. Our optimal design algorithm aims to find the values of
$b_{m}=b(\theta_{m})\triangleq\mathbf{L}_{0}\mathbf{B}(\theta_{m})=\operatorname{B}_{0}(\theta_{m})-\operatorname{B}_{1}(\theta_{m})\in[0,1]$
that minimize the integrated MSE for the target $\operatorname{F}$. Whenever
we say that we draw a $b_{m}$, we also mean dawning the corresponding
$\theta_{m}$ that leads to $b_{m}=b(\theta_{m})$. To build an intuition,
assume that for each $m\in[M]$

$\textstyle\hat{\pi}_{m}=\operatorname{F}(b_{m})+\epsilon(b_{m}),~{}~{}{\mathbb{E}}[\epsilon(b_{m})]=0,\mathrm{var}[\epsilon(b_{m})]=\sigma^{2}(b_{m})\,.$

Then for our estimator in (3.3), which is
$\hat{\operatorname{F}}={\arg\min}_{F\in\mathcal{F}}\sum\nolimits_{m}n_{m}(\hat{\pi}_{m}-F(b_{m}))^{2}$,
the design density $d$ (i.e. ${\sf i.i.d.}$ $b_{m}\sim d$) that minimizes the
mean integrated squared error
$\operatorname{MISE}\\{\hat{\operatorname{F}}\mid
d\\}\triangleq\int\mathbb{E}\\{\hat{\operatorname{F}}(b)-\operatorname{F}(b)\\}^{2}db$
is given by

$d^{\star}(b)=\nicefrac{{\sigma(b)}}{{\int\sigma(u)du}},$ (4.1)

(see Müller (1984); Zhao and Yao (2012)) which, intuitively affirms that more
design points are needed in areas with a higher noise level for
$\hat{\pi}_{m}$. In particular, if $\sigma(\cdot)$ is constant, then
$d^{\star}(\cdot)$ is the uniform density. Although the design density takes
the form of (4.1), we’re yet to learn $\sigma(\cdot)$, which we learn through
a sequential method.

###  4.1 Sequential method with doubling trick

Different approaches have been developed to estimate the optimal design; most
related is episode-sequential design by Zhao and Yao (2012). Further
developing on this design algorithm, we propose our new algorithm that uses a
doubling trick to minimize the relative efficiency loss (Zhao and Yao, 2012)
with respect to the optimal design $d^{\star}$ (as described in (4.1)):

$\textstyle\operatorname{REL}(d)\triangleq
1-\frac{\operatorname{MISE}\\{\hat{F}\mid
d^{\star}\\}}{\operatorname{MISE}\\{\hat{F}\mid d\\}}.$

We divide the model choices $[M]$ into $K$ episodes that increase
exponentially as $L_{k}=(\tau_{o}2^{k-1})^{\alpha}$, where $\tau_{o}$ is the
length of the first episode and $\alpha\in(0,1]$ is fixed. With this choice of
$L_{k}$, we have
$K=\lfloor\log_{q}(1+\nicefrac{{M(q-1)}}{{\tau_{o}^{\alpha}}})\rfloor$ where
$q=2^{\alpha}$. We state our algorithm in 2 and establish an upper bound for
relative efficiency in Theorem 4.1.

Algorithm 2 Sequential Design Algorithm with doubling trick

1: Fix $\tau_{o}\in\mathbb{N}$,
$K=\log_{q}(1+\nicefrac{{M(q-1)}}{{\tau_{o}^{\alpha}}})$, $q=2^{\alpha}$ and
$L_{k}=(\tau_{o}2^{k-1})^{\alpha}$. Define the episodes
$\mathcal{I}_{1}=\\{1,\dots,L_{1}\\}$ and
$\mathcal{I}_{k}=\\{1+\sum\nolimits_{j=1}^{k-1}L_{j},\ldots,\sum\nolimits_{j=1}^{k}L_{j}\\}$,
for $k=2,\dots,K$.

2: Let the initial density $\hat{d}_{1}^{*}$ be the uniform in $[0,1]$.

3: for $k$ in $[1,K]$ do

4: For every $m\in\mathcal{I}_{k}$ sample $b_{m}\overset{{\sf
i.i.d.}}{\sim}\hat{d}_{k}^{*}$ and record $\hat{\pi}_{m}$ (see Remark 3.1).

5: Based on $\\{\hat{\pi}_{m}\\}_{m\in\mathcal{I}_{k}}$ update
$\hat{F}_{k}(b)$, $\hat{\sigma}_{k}(b)$ and the design density
$\hat{d}_{k+1}^{*}(b)\propto\hat{\sigma}_{k}(b)$.

6: end for

######  Theorem 4.1.

Assume that for a $\delta\in(0,1)$ the $\hat{d}^{\star}_{k}$ at $k$-th episode
(as defined in Algorithm 2) satisfies
$\|\hat{d}^{\star}_{k}-d^{\star}\|_{\infty}=\mathcal{O}_{P}((\nicefrac{{\log(L_{k})}}{{L_{k}}})^{\delta})$.
Then, as $M\rightarrow\infty$

$\displaystyle\operatorname{REL}(\hat{d}^{\star}_{K})=\mathcal{O}_{P}(\log^{\delta}\\{\tau_{o}^{\alpha}+M(2^{\alpha}-1)\\}\\{2^{-\alpha}+M(1-2^{-\alpha})\\}^{-\delta})=\mathcal{O}_{P}([\nicefrac{{\log(M)}}{{M}}]^{\delta}).$
(4.2)

In Theorem 4.1, for every fixed $\alpha$,
$\operatorname{REL}(\hat{d}^{\star}_{K})$, has the same rate of convergence of
the method proposed by Zhao and Yao (2012) (Zhao and Yao, 2012, Theorem 2).
The advantage of Theorem 4.1 is that, being $\hat{d}_{k+1}^{*}$ a function of
${\sf i.i.d.}$ data, then the unknown $\delta$ can be determined, which was
not possible in Zhao and Yao (2012), where the data are not ${\sf i.i.d.}$

Figure 3: Relative efficiencies and their $95\%$ confidence intervals for
three different $F_{C}$’s.

When $\sigma(\cdot)$ is a continuous function of $\operatorname{F}$ (see ${\it
e.g.}$ Example 4.2, where
$\sigma^{2}\propto\operatorname{F}\bar{\operatorname{F}}$) the value $\delta$
coincides with the value of $\eta$ that satisfies
$\|\hat{\operatorname{F}}_{k}-\operatorname{F}\|_{\infty}=\mathcal{O}_{P}((\nicefrac{{\log(L_{k})}}{{L_{k}}})^{\eta})$.
In such cases, for standard non-parametric estimates such as kernel and spline
(see e.g. (Zhao and Yao, 2012, §3)), we have
$\delta=\eta=\nicefrac{{\beta}}{{2\beta+1}}$ where $\beta$ is the degree of
smoothness of $\operatorname{F}$.

######  Example 4.2 (CL model).

Going back to Example 2.2, continued in Section 3.1, suppose that $w=1$, so
that $b_{m}\in[0,1]$. Suppose that for every $b_{m}$ we observe
$\hat{\pi}(b_{m})=\nicefrac{{1}}{{n_{m}}}\sum\nolimits_{i=1}^{n_{m}}A_{m,i}$,
where $n_{m}$ is the number of observations at point $b_{m}$. We have
$\hat{\pi}(b_{m})=\textstyle F_{C}(b_{m})+\epsilon(b_{m})$ where
$\epsilon(b_{m})\triangleq\nicefrac{{1}}{{n_{m}}}\sum\nolimits_{i=1}^{n_{m}}\left(A_{m,i}-F_{C}(b_{m})\right)$,
$\mathbb{E}[\epsilon(b)]=0$ and $\sigma^{2}(b)=\mathbb{V}[\epsilon(b)]\propto
F_{C}(b)\bar{F}_{C}(b)$. Thus, the optimal density design would be
$d^{\star}(b)\propto(F_{C}(b)\bar{F}_{C}(b))^{1/2}$. Since $F_{C}$ is not
known, we use Algorithm 2 to estimate it. In particular, at episode $k$, we
estimate $\sigma^{2}$ with splines, using data
$\\{b_{m},\hat{\sigma}^{2}(b_{m})\propto\hat{\pi}(b_{m})(1-\hat{\pi}(b_{m}))\\}_{m\in\mathcal{I}_{k}}$.
In Figure 3 we see that the relative efficiency converges to zero as $K$
increases.

##  5 Regret analysis on performative risk

In this section, we demonstrate how performative risk can be easily minimized
by “plugging-in” the estimated distribution map. As in the previous section,
assume that $\mathcal{A}=\\{0,1\\}$. In order to find the performative optimum
the learner would minimize the performative risk (2.4)

$\textstyle\theta^{\star}\in{\arg\min}_{\theta}{\mathrm{PR}}(\theta)\triangleq\sum\nolimits_{a\in\mathcal{A}}\mathcal{D}_{\theta}(a){\mathbb{E}}\big{[}\ell(\theta;Z)\mid
A=a\big{]}\,,$ (5.1)

where $\mathcal{D}_{\theta}(a)$ remains unknown. In a plug-in approach, the
learner estimates $\theta^{\star}$ by plugging-in an estimate
$\hat{\mathcal{D}}_{\theta}(A)$ as in Algorithm 1, and then minimizes the
performative prediction risk. Toward this goal of minimizing
${\mathrm{PR}}(\theta)$ what $\\{\theta_{m};m\in[M]\\}$ should be deployed? In
this section, we explore this question: an optimal design choice of
$\\{\theta_{m};m\in[M]\\}$ that minimizes the total regret

$\textstyle\operatorname{Reg}(M)\triangleq\sum\nolimits_{m\in[M]}\\{{\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m})\\}$
(5.2)

To this end, we propose a design algorithm similar to Algorithm 2 that relies
on a doubling trick and alternates between exploration and exploitation. We
divide drawing $M$ models into $K=\log_{2}(1+M/\tau_{0})$ episodes denoted as
$\\{\mathcal{J}_{k};k\in[K]\\}$, where the lengths of the episodes are
$|\mathcal{J}_{k}|=\tau_{0}2^{k-1}$ and $\tau_{0}$ is the number of models
drawn in the first episode (initial phase) and does not affect the rate of
convergence. We then divide each episode $\mathcal{J}_{k}$ into two sub-
phases: the exploration phase ($\mathcal{I}_{k}$), where we use Algorithm 2 to
estimate $\mathcal{D}_{\theta}(a)$ and then exploitation phase
($\mathcal{I}^{\prime}_{k}$), where we constantly deploy

$\displaystyle\textstyle\hat{\theta}_{k}\in{\arg\min}_{\theta}\big{\\{}\widehat{{\mathrm{PR}}}_{k}(\theta)\triangleq\sum\nolimits_{a\in\mathcal{A}}\hat{\mathcal{D}}_{\theta}^{(k)}(a){\mathbb{E}}[\ell(\theta;Z)|A=a]\big{\\}}.$
(5.3)

We summarize our procedure in Algorithm 3.

Algorithm 3 Sequential Design with Doubling trick

1: Let $\mathcal{J}_{1},\dots,\mathcal{J}_{K}$ sequential episodes with
$\mathcal{J}_{1}=\\{1,\dots,\tau_{o}\\}$, and
$\mathcal{J}_{k}=\mathcal{I}_{k}\cup\mathcal{I}^{\prime}_{k}$ for
$k=2,\dots,K$, where $\mathcal{I}_{k}=\\{\tau_{o}(2^{k-1}-1)+1,\dots,a_{k}\\}$
is the exploration index phase, where $a_{k}=(\tau_{o}2^{k-1})^{\alpha}$ for
some $\alpha\in(0,1)$, and
$\mathcal{I}^{\prime}_{k}=\\{a_{k}+1,\dots,\tau_{o}(2^{k}-1)\\}$ is the
exploitation index phase.

2: For $k=1$ let $\hat{d}_{1}^{*}$ be the uniform density in $[0,1]$.

3: for $k=1,\dots K$ do

4: For every $m\in\mathcal{I}_{k}$ sample $b_{m}\overset{{\sf
i.i.d.}}{\sim}\hat{d}_{k}^{*}$ and record $\hat{\pi}_{m}$ (see Remark 3.1).

5: Based on $\\{\hat{\pi}_{m}\\}_{m\in\mathcal{I}_{k}}$ update
$\\{\hat{\mathcal{D}}_{\theta}^{(k)}(a);a\in\mathcal{A}\\}$,
$\hat{\sigma}_{k}^{2}$ and the design density
$\hat{d}_{k+1}^{*}\propto\hat{\sigma}_{k}$.

6: For every $m\in\mathcal{I}^{\prime}_{k}$ deploy the same
$\hat{\theta}_{k}={\arg\max}_{\theta}\widehat{{\mathrm{PR}}}_{k}(\theta)$,
where $\widehat{{\mathrm{PR}}}_{k}$ is defined in (5.3).

7: end for

Next we evaluate the goodness of Algorithm 3 in terms of the total regret
(5.2). Notice that there is a trade-off between the exploration and
exploitation phases: a larger exploration phase produces a more accurate
$\widehat{{\mathrm{PR}}}_{k}(\theta)$, but does not decrease overall regret.
For this reason, in Algorithm 3 we balance between these two phases by letting
the length of exploration phase
$a_{k}=|\mathcal{I}_{k}|=|\mathcal{J}_{k}|^{\alpha}=(\tau_{o}2^{k-1})^{\alpha}$
where $\alpha\in(0,1)$ is chosen optimally by looking at the rate of
convergence in regret. This choice of $\alpha$, along with the rate of
convergence for both regret and relative efficiencies, is provided in the
following theorem.

######  Theorem 5.1.

Assume that ${\mathbb{E}}[\ell(\theta,X)|A=a]$ is uniformly bounded in
$\theta$ and $a$. Consider the procedure of Algorithm 3. Suppose that there
exist $\eta,\delta\in(0,1)$ such that
$\|\mathcal{D}_{\theta}(1)-\hat{\mathcal{D}}_{\theta}^{(k)}(1)\|_{\infty}=\mathcal{O}_{P}\left((\nicefrac{{\log(|\mathcal{I}_{k}|)}}{{|\mathcal{I}_{k}|}})^{\eta}\right)$
and
$\|\hat{d}^{*}_{k}-d^{*}\|_{\infty}=\mathcal{O}_{P}\left((\nicefrac{{\log(|\mathcal{I}_{k}|)}}{{|\mathcal{I}_{k}|}})^{\delta}\right)$.
Then the total regret is minimized at $\alpha=\nicefrac{{1}}{{1+\eta}}$ for
with the regret and relative efficiencies are

$\displaystyle\operatorname{Reg}(M)=\mathcal{O}_{P}\big{(}M^{\nicefrac{{1}}{{1+\eta}}}\log^{\eta}(M)\big{)},\quad\operatorname{REL}(\hat{d}^{*}_{K})=\mathcal{O}_{P}\big{(}M^{-\nicefrac{{\delta}}{{1+\eta}}}\log^{\delta}(M)\big{)}$
$\displaystyle\text{ as }M\rightarrow\infty.$

######  Remark 5.2.

As we mention in Section 4.1, when $\sigma(\cdot)$ is a continuous function of
$F$ (see ${\it e.g.}$ Example 4.2, where $\sigma^{2}\propto F\bar{F}$), then
$\delta\equiv\eta$.

######  Remark 5.3.

For one-dimensional isotonic regression we have $\eta=\nicefrac{{1}}{{3}}$
(see Proposition 3.3) that leads to regret
$\mathcal{O}(M^{\nicefrac{{3}}{{4}}})$. For other standard non-parametric
estimates, such as kernel and spline, see e.g. (Zhao and Yao, 2012, Section
3), $\eta=\nicefrac{{\beta}}{{2\beta+1}}$ where $\beta$ is the smoothness
parameter for $\operatorname{F}$, leading to regret
$\mathcal{O}(M^{\nicefrac{{2\beta+1}}{{3\beta+1}}})$.

Comparing our Theorem 5.1 with Jagadeesan et al. (2022, Theorem 3), the key
difference lies in our use of a plug-in estimator for the
$\mathcal{D}_{\theta}$ shift versus their need for ${\sf i.i.d.}$ samples from
$\mathcal{D}_{\theta}$ in each optimization step of ${\mathrm{PR}}$. Their
regret bound is $\mathcal{O}(M^{\nicefrac{{d+1}}{{d+2}}})$, where $d$ is the
zooming dimension of $\theta$, which in the worst case is identical to
$\text{dim}(\theta)$. In contrast, our bound is independent of
$\text{dim}(\theta)$,because the distribution map itself depends on $\theta$
only through the unidimensional $b(\theta)=\mathbf{L}_{0}\mathbf{B}(\theta)$.
Consequently, we achieve
$\operatorname{Reg}(M)=\widetilde{\mathcal{O}}_{P}(M^{\nicefrac{{2\beta+1}}{{3\beta+1}}})$
(Remark 5.3), which is of lower order than
$\mathcal{O}(M^{\nicefrac{{d+1}}{{d+2}}})$ whenever $\beta\geq 1$ and $d\geq
2$.

##  6 Conclusions

We propose a microfoundation framework with random cost to learn the
distribution map in reverse causal performative prediction settings. We also
provide a design choice of predictive models for the learner to efficiently
estimate the distribution map and minimize the performative risk. The
performative prediction settings are extremely relevant in ML research, as
they are routinely realized in many strategic environments. We believe that
our proposal of learning the distribution map will make the problem of
performative risk minimization more accessible to practitioners.

_Where does our reverse causal framework fit into learning the distribution
map in broader performative prediction problems?_ Our focus is primarily on
finite action spaces, but the reverse causal model with an arbitrary $A$
offers significant potential in performative prediction. Specifically, any
$\mathcal{D}_{\theta}(X,Y)$ can be fit into reverse causal model by setting
$A=(X,Y)$, making $\mathcal{D}_{\theta}(X,Y\mid A)$ trivially independent of
$\theta$. A balance can be struck between this general $A$ and finite action
spaces by choosing an action variable $A$ that captures all relevant
information about $\theta$, ensuring $\mathcal{D}_{\theta}(X,Y\mid A)$ remains
independent of $\theta$. Extending our approach to arbitrary action spaces may
involve using generative models, such as a generative model $h$ with a latent
variable $U$ (with a known distribution), to express $\mathcal{D}_{\theta}(A)$
via $h(U,\theta)$. For instance, in the CL model 2.2, setting
$U\sim\text{unif}(0,1)$ and $h(U,\theta)=\mathbbm{I}\\{U\leq\pi(\theta)\\}$
allows $A$ to be modeled as $h(U,\theta)$, where
$\mathcal{D}_{\theta}(A=1)=P(h(U,\theta)=1)=\pi(\theta)$, making $A$ and
$h(U,\theta)$ identically distributed. Learning the generative map $h$ could
benefit from the techniques in Goodfellow et al. (2014); Arjovsky et al.
(2017). While exploring this further could broaden learning of distribution
shifts, it is outside this paper’s scope.

## References

  * Arjovsky et al. (2017) Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In _International conference on machine learning_ , pages 214–223. PMLR, 2017.
  * Chatterjee et al. (2018) Sabyasachi Chatterjee, Adityanand Guntuboyina, and Bodhisattva Sen.  On matrix estimation under monotonicity constraints.  _Bernoulli_ , 24(2):1072–1100, May 2018.  ISSN 1350-7265.  doi: 10.3150/16-BEJ865.
  * Chen et al. (2020) Yiling Chen, Yang Liu, and Chara Podimata.  Learning strategy-aware linear classifiers.  _Advances in Neural Information Processing Systems_ , 33:15265–15276, 2020.
  * Coate and Loury (1993) Stephen Coate and Glenn C. Loury.  Will Affirmative-Action Policies Eliminate Negative Stereotypes?  _The American Economic Review_ , 83(5):1220–1240, 1993.  ISSN 0002-8282.
  * Cormier et al. (2016) Q. Cormier, M. Milani Fard, K. Canini, and M. R. Gupta.  Launch and iterate: Reducing prediction churn.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , NIPS’16, pages 3179–3187, Red Hook, NY, USA, December 2016. Curran Associates Inc.  ISBN 978-1-5108-3881-9.
  * Cutler et al. (2021) Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui.  Stochastic optimization under time drift: iterate averaging, step decay, and high probability guarantees.  _arXiv preprint arXiv:2108.07356_ , 2021.
  * Dong et al. (2018) Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu.  Strategic Classification from Revealed Preferences.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , EC ’18, pages 55–70, New York, NY, USA, June 2018. Association for Computing Machinery.  ISBN 978-1-4503-5829-3.  doi: 10.1145/3219166.3219193.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27, 2014.
  * Han et al. (2019) Qiyang Han, Tengyao Wang, Sabyasachi Chatterjee, and Richard J. Samworth.  Isotonic regression in general dimensions.  _The Annals of Statistics_ , 47(5):2440–2471, October 2019.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/18-AOS1753.
  * Hardt et al. (2015) Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic Classification.  _arXiv:1506.06980 [cs]_ , November 2015.
  * Hardt et al. (2016) Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic Classification.  In _Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science_ , ITCS ’16, pages 111–122, New York, NY, USA, January 2016. Association for Computing Machinery.  ISBN 978-1-4503-4057-1.  doi: 10.1145/2840728.2840730.
  * Horowitz and Rosenfeld (2023) Guy Horowitz and Nir Rosenfeld.  Causal strategic classification: A tale of two shifts.  In _International Conference on Machine Learning_ , pages 13233–13253. PMLR, 2023.
  * Izzo et al. (2021) Zachary Izzo, Lexing Ying, and James Zou.  How to Learn when Data Reacts to Your Model: Performative Gradient Descent.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 4641–4650. PMLR, July 2021.
  * Jagadeesan et al. (2022) Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Dünner.  Regret Minimization with Performative Feedback.  In _Proceedings of the 39th International Conference on Machine Learning_ , pages 9760–9785. PMLR, June 2022.
  * Jang et al. (2022) Sooyong Jang, Sangdon Park, Insup Lee, and Osbert Bastani.  Sequential covariate shift detection using classifier two-sample tests.  In _International Conference on Machine Learning_ , pages 9845–9880. PMLR, 2022.
  * Levanon and Rosenfeld (2021) Sagi Levanon and Nir Rosenfeld.  Strategic Classification Made Practical, June 2021.
  * Levanon and Rosenfeld (2022) Sagi Levanon and Nir Rosenfeld.  Generalized strategic classification and the case of aligned incentives.  In _International Conference on Machine Learning_ , pages 12593–12618. PMLR, 2022.
  * Lin and Zrnic (2023) Licong Lin and Tijana Zrnic.  Plug-in performative optimization.  _arXiv preprint arXiv:2305.18728_ , 2023.
  * Lipton et al. (2018) Zachary C. Lipton, Yu-Xiang Wang, and Alex Smola.  Detecting and Correcting for Label Shift with Black Box Predictors.  _arXiv:1802.03916 [cs, stat]_ , July 2018.
  * Maity et al. (2022) Subha Maity, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun.  Understanding new tasks through the lens of training data via exponential tilting.  In _The Eleventh International Conference on Learning Representations_ , September 2022.
  * Meyer (2008) Mary C Meyer.  Inference using shape-restricted regression splines.  2008\.
  * Miller et al. (2021) John P. Miller, Juan C. Perdomo, and Tijana Zrnic.  Outside the Echo Chamber: Optimizing the Performative Risk.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 7710–7720. PMLR, July 2021.
  * Mösching and Dümbgen (2020) Alexandre Mösching and Lutz Dümbgen.  Monotone least squares and isotonic quantiles.  2020\.
  * Müller (1984) Hans-Georg Müller.  Optimal designs for nonparametric kernel regression.  _Statistics & Probability Letters_, 2(5):285–290, 1984.
  * Perdomo et al. (2020) Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt.  Performative Prediction.  _arXiv:2002.06673 [cs, stat]_ , June 2020.
  * Robertson et al. (1988) Tim Robertson, Richard Dykstra, and FT Wright.  Order restricted statistical inference.  _(No Title)_ , 1988.
  * Shavit et al. (2020) Yonadav Shavit, Benjamin Edelman, and Brian Axelrod.  Causal strategic linear regression.  In _International Conference on Machine Learning_ , pages 8676–8686. PMLR, 2020.
  * Somerstep et al. (2024) Seamus Somerstep, Yuekai Sun, and Yaacov Ritov.  Learning in reverse causal strategic environments with ramifications on two sided markets.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=vEfmVS5ywF.
  * Strathern (1997) Marilyn Strathern.  ‘improving ratings’: audit in the british university system.  _European review_ , 5(3):305–321, 1997.
  * Zhao and Yao (2012) Zhibiao Zhao and Weixin Yao.  Sequential design for nonparametric inference.  _Canadian Journal of Statistics_ , 40(2):362–377, 2012.

##  Appendix A Maximum Likelihood Estimator for estimating the distribution
map

Alternatively to problem (3.2), one may estimate $g$ by non-parametric maximum
likelihood as follows. Suppose that
$\hat{\pi}_{a}(\theta_{m})=\tilde{A}_{m,a}/n_{m}$, where $\tilde{A}_{m,a}$ is
the number of agents that chose action $a$ under model $\theta_{m}$. We can
consider estimating the density map
$\mathcal{D}_{\theta}=\\{\operatorname{F}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta));a\in\mathcal{A}\\}$
by maximum likelihood. Indeed

$[\tilde{A}_{m,a}]_{a\in\mathcal{A}}\sim\text{Multinomial}(n_{m};[\operatorname{F}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta_{m}))]_{a\in\mathcal{A}}),$

and the part of the log-likelihood that only depends on
$[\operatorname{F}_{a}]_{a\in\mathcal{A}}$ is

$l([\operatorname{F}_{a}]_{a\in\mathcal{A}})=\sum_{m=1}^{M}\sum_{a\in\mathcal{A}}n_{m}\hat{\pi}_{a}(\theta_{m})\log\left(\operatorname{F}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta_{m}))\right).$

However, it is well known that maximum likelihood and least square estimators
coincide under isotonicity constraints (see ${\it e.g.}$ Robertson et al.
(1988)).

##  Appendix B Parametric model the distribution of the cost in the CL model

Suppose that $F_{C}$ is the cdf of a Gaussian $\mathcal{N}(\mu,\sigma)$ that
is $g(b)=\Phi(\frac{b-\mu}{\sigma})$, where $\Phi$ is the cdf of a
$\mathcal{N}(0,1)$. We have $F_{C}(b(\theta))=\Phi(\frac{b-\mu}{\sigma})$. If
we observe models $\\{\theta_{m}\\}_{m\in[M]}$ and corresponding proportions
$\\{\hat{\pi}_{m}\\}_{m\in[M]}$ and benefits $\\{b_{m}\\}_{m\in[M]}$, to
estimate $F_{C}$ we can solve the linear model

$\phi_{m}\equiv\Phi^{-1}(\hat{\pi}_{m})=\frac{b_{m}}{\sigma}-\frac{\mu}{\sigma}+\epsilon_{m}$

with the constraint that $\sigma>0$. The solution is

$\hat{\sigma}_{M}=\begin{cases}\frac{\sum_{m=1}^{M}\Delta
b_{m}\Delta\phi_{m}}{\sum_{m=1}^{M}\Delta b_{m}^{2}}&\text{when
}\sum_{m=1}^{M}\Delta b_{m}\Delta\phi_{m}>0\\\ 0&\text{otherwise }\end{cases}$

and $\hat{\mu}_{M}=\bar{b}-\hat{\sigma}_{M}\bar{\phi}$, where $\Delta
b_{m}=b_{m}-\bar{b}$, $\Delta\phi_{m}=\phi_{m}-\bar{\phi}$, and $\bar{b}$ and
$\bar{\phi}$ are the average of the $b_{m}$ and $\phi_{m}$, respectively.
Similarly, we can choose a logistic model by replacing the standard Gaussian
cdf with $\Phi(b)=1/(1+e^{-b})$, the standard logistic cdf. The advantages of
parametric models are simplicity of interpretation, computational efficiency,
and convergence rate $\mathcal{O}_{P}(\sqrt{M})$.

##  Appendix C Simulation: multivariate cost estimation

|
---|---
Figure 4: Multivariate distribution map estimation.

In this section, we provide a simulation setup for a general number of actions
$|\mathcal{A}|$. We set
$\mathbf{C}\sim\mathcal{N}_{|\mathcal{A}|}(\bm{\mu},\Sigma)$, with
$\bm{\mu}=\mathbb{0}$ and $\Sigma=\mathbf{I}$. We select random benefits
$\\{\mathbf{B}(\theta_{m}),m\in[M]\\}$ with $M=500$. For every
$a\in\mathcal{A}$, we define $\hat{\pi}_{m}(a)=\pi_{m}(a)+\epsilon_{m}(a)$,
where $\pi_{m}(a)=\operatorname{F}_{a}(L_{a}\mathbf{B}(\theta_{m}))$, where
$\operatorname{F}_{a}$ is the cdf of
$\mathbf{L}_{a}\mathbf{C}\sim\mathcal{N}_{|\mathcal{A}|-1}(\mathbf{L}_{a}\bm{\mu},\mathbf{L}_{a}\Sigma\mathbf{L}_{a}^{\top})$
and ${\sf i.i.d.}$ $\epsilon_{m}(a)\sim\mathcal{N}(0,\tau)$, with $\tau=0.1$.
We redefined
$\hat{\pi}_{m}(a)\leftarrow\max\\{0,\min\\{1,\hat{\pi}_{m}(a)\\}\\}$ since
they represents probabilities. For $a\in\mathcal{A}\setminus\\{0\\}$, we get
$\hat{F}_{a}$ as multivariate isotonic regression with data
$\\{(\hat{\pi}_{m}(a),\mathbf{L}_{a}\mathbf{B}(\theta_{m})),m\in[M]\\}$, and
$\hat{\operatorname{F}}_{0}=1-\sum\nolimits_{a\in\mathcal{A}\setminus\\{0\\}}\hat{\operatorname{F}}_{a}$.
Then we have
$\hat{\mathcal{D}}_{\theta_{m}}(A)=\\{\hat{\operatorname{F}}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta_{m}));a\in\mathcal{A}\\}$
and
$\mathcal{D}_{\theta_{m}}(A)=\\{\operatorname{F}_{a}(\mathbf{L}_{a}\mathbf{B}(\theta_{m}));a\in\mathcal{A}\\}$
and we plot the quantity
$\sum\nolimits_{m\in[N]}\|\mathcal{D}_{\theta_{m}}(A)-hat\mathcal{D}_{\theta_{m}}(A)\|_{2}^{2}$,
for $N\in\\{50,100,150,200,\dots,500\\}$. We repeat this process for $10$
times, with the same $\mathbf{C}$ and $\\{\mathbf{B}(\theta_{m}),m\in[M]\\}$
and with different seed to simulate $\\{\pi_{m}(a),a\in\mathcal{A},m\in[M]\\}$
and we show the result in Figure 4.

##  Appendix D Regret Analysis: comparison with zero order methods

We compare our result stated in Theorem 5.1, with the result provided by
Jagadeesan et al. (2022). They define

$\operatorname{Reg}_{\textit{mean}}(M)=\textstyle\sum_{m=1}^{M}\big{[}\min_{\theta}{\mathrm{PR}}(\theta)-\mathbb{E}[{\mathrm{PR}}(\theta_{m})]\big{]}$

where the expectation is taken over the possible randomness in the choice of
$\\{\theta_{m}\\}_{m\in[M]}$, a sequence of deployed models. The main
difference between the two algorithms is that, while we estimate
${\mathrm{PR}}$ by plugging in an estimate of the distribution shift, they
sample from the distribution shift to estimate ${\mathrm{PR}}$. In Theorem 4.2
they prove that

$\operatorname{Reg}_{\textit{mean}}(M)=\mathcal{O}(M^{\frac{d+1}{d+2}}\epsilon^{\frac{d}{d+2}}+\sqrt{M})$

where $d$ is the zooming dimensions (which is equal to the dimension of
$\theta$ in the worst-case scenario) and $\epsilon$ is the sensitivity of the
distribution map, which is a value proportional to the amount of distribution
shift. They assume that:

  1. $i)$

the loss $\ell$ is bounded in $[0,1]$ (it is the same as our Assumption in
Theorem 5.1).

  2. $ii)$

$\ell$ is Lipschitz in the two variables (which we don’t require);

When $\epsilon=0$, meaning that the performative effect vanishes,
$\operatorname{Reg}_{\textit{mean}}(M)$ achieves the standard bound
$\mathcal{O}(\sqrt{M})$ in an essentially dimension-independent manner. In our
work, we assume that the distribution shift is non-trivial (${\it i.e.}$
$\epsilon>0$). Indeed, when $\epsilon\approx 0$, the agents don’t move, which
means that the cost $c$ is always null, and then, there is no need to estimate
it. For this reason, our regret bound can be compared to Jagadeesan et al.
(2022) when $\epsilon>0$ and is independent of $M$, which leads to
$\operatorname{Reg}_{\textit{mean}}(M)=\mathcal{O}(M^{\frac{d+1}{d+2}})$..
However, our result is independent of the dimension of $\theta$, because the
distribution map only depends on $\theta$ throw the unidimensional variable
$b(\theta)=\mathbf{L}_{0}\mathbf{B}(\theta)$. As mentioned in Remark 5.3, we
can achieve
$\operatorname{Reg}(M)=\widetilde{\mathcal{O}}_{P}(M^{\nicefrac{{2\beta+1}}{{3\beta+1}}})$,
which upper-bound is lower than $\mathcal{O}(M^{\nicefrac{{d+1}}{{d+2}}})$
(excluding $\log(M)$ factors) whenever $\beta\geq\nicefrac{{1}}{{(d-1)}}$,
i.e. $\beta\geq 1$ and $d\geq 2$.

##  Appendix E Proofs

###### Proof of Lemma 2.5.

The necessary direction is trivially realized once $\mathcal{D}_{\theta}(A=a)$
is expressed as

$\textstyle\mathcal{D}_{\theta}(A=a)={\mathbb{P}}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq a\big{\\}}\,.$ (E.1)

because this necessarily implies that $\mathcal{D}_{\theta}(A=a)$ increases
with $\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)$ for any
$a^{\prime}\neq a$. Establishing the sufficient direction is more non-trivial,
which we establish using an induction argument. We start with the case of
$|\mathcal{A}|=2$, where, without loss of generality, we let
$\mathcal{A}=\\{0,1\\}$. Furthermore, we set $C_{0}\equiv 0$. In this case,
since $\mathcal{D}_{\theta}(A=1)$ increases with
$\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta)$ we can define a random
variable $C_{1}$ such that

$\textstyle\mathcal{D}_{\theta}(A=1)={\mathbb{P}}\big{\\{}C_{1}\leq\operatorname{B}(1,\theta)-\operatorname{B}(0,\theta)\big{\\}}\,.$

For such $\\{C_{0},C_{1}\\}$ we have the desired microfoundation for
$\mathcal{A}=\\{0,1\\}$.

For a more general $|\mathcal{A}|=K+1>2$ let $\mathcal{A}=\\{0,1,\dots,K\\}$.
To establish our induction step we assume that there exists a joint
distribution for the $\mathbf{C}_{-K}=\\{C_{a};a=0,\dots,K-1\\}$ such that the
microfoundation holds on $\mathcal{A}-\\{K\\}$, i.e. for any $a<K$ we have

$\textstyle\mathcal{D}_{\theta}(A=a\mid A\neq
K)=\frac{\mathcal{D}_{\theta}(A=a)}{1-\mathcal{D}_{\theta}(A=K)}={\mathbb{P}}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}<K,a^{\prime}\neq
a\big{\\}}\,.$ (E.2)

Now, we show that there exists a random variable $C_{K}$ such that

$\mathcal{D}_{\theta}(A=K)={\mathbb{P}}\big{\\{}\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{K}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}<K\big{\\}}\,.$ (E.3)

For the process, we further simplify the above expression in the right hand
side as:

$\displaystyle\textstyle{\mathbb{P}}\big{\\{}\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{K}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}<K\big{\\}}$ (E.4)
$\displaystyle\textstyle={\mathbb{P}}\big{\\{}C_{K}\leq
C_{a^{\prime}}+\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta),~{}\text{for
all}~{}a^{\prime}<K\big{\\}}$
$\displaystyle\textstyle={\mathbb{P}}\big{\\{}C_{K}\leq\min_{a^{\prime}<K}\big{(}C_{a^{\prime}}+\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\big{)}\big{\\}}$
$\displaystyle\textstyle=\int{\mathbb{P}}\big{\\{}C_{K}\leq\min_{a^{\prime}<K}\big{(}C_{a^{\prime}}+\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\big{)}\mid\mathbf{C}_{-K}\big{\\}}d\mathbb{P}(\mathbf{C}_{-K})$

At this point, for any fixed value for $\mathbf{C}_{-K}$ we can find a
distribution for $C_{K}\mid\mathbf{C}_{-K}$ such that

$\mathcal{D}_{\theta}(A=K)={\mathbb{P}}\big{\\{}C_{K}\leq\min_{a^{\prime}<K}\big{(}C_{a^{\prime}}+\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\big{)}\mid\mathbf{C}_{-K}\big{\\}}$

This is possible because $\mathcal{D}_{\theta}(A=K)$ increases with each
$\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)$ and thus with
$\min_{a^{\prime}<K}\big{(}C_{a^{\prime}}+\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\big{)}$.
Denote the c.d.f. of the conditional distribution of
$C_{K}\mid\mathbf{C}_{-K}$ by
$\operatorname{F}_{k}(\cdot\mid\mathbf{C}_{-K})$. We combine this conditional
distribution with the joint distribution of $\mathbf{C}_{-K}$ to obtain our
desired joint distribution of $\mathbf{C}$.

To complete the proof, we need to show that such a choice of $\mathbf{C}$
satisfies (E.1). We have already established it for $a=K$, i.e. (E.3) because
according to (E.4)

$\displaystyle\textstyle{\mathbb{P}}\big{\\{}\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{K}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}<K\big{\\}}$
$\displaystyle\textstyle=\int{\mathbb{P}}\big{\\{}C_{K}\leq\min_{a^{\prime}<K}\big{(}C_{a^{\prime}}+\operatorname{B}(K,\theta)-\operatorname{B}(a^{\prime},\theta)\big{)}\mid\mathbf{C}_{-K}\big{\\}}d\mathbb{P}(\mathbf{C}_{-K})$
$\displaystyle\textstyle=\int\mathcal{D}_{\theta}(A=K)d\mathbb{P}(\mathbf{C}_{-K})=\mathcal{D}_{\theta}(A=K).$

To show this for $a\neq K$ we follow the identities:

$\displaystyle\textstyle{\mathbb{P}}\big{[}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq a\big{]}$
$\displaystyle=\textstyle{\mathbb{P}}\big{[}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq
a,a^{\prime}<K\big{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\&\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(K,\theta)\geq
C_{a}-C_{K}\big{\\}}\big{]}$
$\displaystyle=\textstyle{\mathbb{P}}\big{[}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq
a,a^{\prime}<K\big{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\&\big{\\{}\operatorname{B}(a^{\prime},\theta)-\operatorname{B}(K,\theta)>C_{a^{\prime}}-C_{K}~{}\text{for
some}~{}a^{\prime}<K\big{\\}}\big{]}~{}~{}(\text{since dist. of $C_{a}$ are
continuous})$ $\displaystyle=\textstyle\int
d\mathbb{P}(\mathbf{C}_{-K})\mathbbm{I}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq
a,a^{\prime}<K\big{\\}}$
$\displaystyle\textstyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\times{\mathbb{P}}\big{\\{}\operatorname{B}(a^{\prime},\theta)-\operatorname{B}(K,\theta)>C_{a^{\prime}}-C_{K},~{}\text{for
some}~{}a^{\prime}<K\mid\mathbf{C}_{-K}\big{\\}}$
$\displaystyle=\textstyle\int
d\mathbb{P}(\mathbf{C}_{-K})\mathbbm{I}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq
a,a^{\prime}<K\big{\\}}\mathcal{D}_{\theta}(A\neq K)~{}~{}(\text{by
\eqref{eq:tech-cost-exists-1}})$
$\displaystyle=\textstyle\mathcal{D}_{\theta}(A\neq K)\textstyle\int
d\mathbb{P}(\mathbf{C}_{-K})\mathbbm{I}\big{\\{}\operatorname{B}(a,\theta)-\operatorname{B}(a^{\prime},\theta)\geq
C_{a}-C_{a^{\prime}},~{}\text{for all}~{}a^{\prime}\neq
a,a^{\prime}<K\big{\\}}$ $\displaystyle=\textstyle\mathcal{D}_{\theta}(A\neq
K)\mathcal{D}_{\theta}(A=a\mid A\neq K)~{}~{}(\text{by \eqref{eq:tech-cost-
exists-2}})$ $\displaystyle\textstyle=\mathcal{D}_{\theta}(A=a)\,.$

This completes the proof. ∎

Proof of Proposition 4.1

###### Proof.

Let $L_{k}=(\tau_{o}2^{k-1})^{\alpha}$ for some constant $\alpha\in(0,1]$ and
integer $\tau_{o}$. From the proof of Theorem 2-3 of Zhao and Yao (2012) we
have that $\operatorname{REL}(\hat{d})=\frac{4}{3}\rho_{M}+o(\rho_{M}^{2})$ as
$M\rightarrow\infty$ where

$\rho_{M}\triangleq(U_{M}-c^{2})/U_{M}$

with

$U_{M}\triangleq\int\frac{\sigma^{2}(b)}{\bar{d}(b)}\mathrm{d}b\quad\text{and}\quad
c\triangleq\int\sigma(b)\mathrm{d}b,$

so that $d^{*}=\sigma/c$. Without loss of generality, we assume that
$b\in(0,1)$.

Step 1.

The assumption
$\|\hat{d}_{k}^{*}-d^{*}\|_{\infty}=\mathcal{O}_{P}\left(\log(L_{k})^{\delta}L_{k}^{-\delta}\right)$,
where $L_{k}=(\tau_{o}2^{k-1})^{\alpha}$, for each $k$ implies
$\|\hat{d}_{K}^{*}-d^{*}\|_{\infty}=\mathcal{O}_{P}\left(M^{-\delta}\right)$.
Indeed, defining $q=2^{\alpha}$, since
$K=\log_{q}(1+M(q-1)/\tau_{o}^{\alpha})$

$\displaystyle\|\hat{d}_{K}^{*}-d^{*}\|_{\infty}$
$\displaystyle\lesssim_{P}\log(L_{K})^{\delta}L_{K}^{-\delta}$
$\displaystyle=\log^{\delta}(\tau_{o}^{\alpha}q^{(K-1)})(\tau_{o}^{\alpha}q^{(K-1)})^{-\delta}$
$\displaystyle=\left[\log(\tau_{o}^{\alpha})+(K-1)\log(q)\right]^{\delta}(\tau_{o}^{\alpha}q^{(K-1)})^{-\delta}$
$\displaystyle\lesssim[\log(\tau_{o}^{\alpha})+K\log(q)]^{\delta}(\tau_{o}^{\alpha}q^{(K-1)})^{-\delta}$
$\displaystyle=\left[\log(\tau_{o}^{\alpha})+\log_{q}(1+M(q-1)/\tau_{o}^{\alpha})\log(q)\right]^{\delta}\tau_{o}^{-\alpha\delta}\left(\frac{1+M(q-1)}{\tau_{o}^{\alpha}q}\right)^{-\delta}$
$\displaystyle=\left[\log(\tau_{o}^{\alpha})+\log(1+M(q-1)/\tau_{o}^{\alpha})\right]^{\delta}\left(\frac{1+M(q-1)}{q}\right)^{-\delta}$
$\displaystyle=\log^{\delta}(\tau_{o}^{\alpha}+M(q-1))\left(\frac{1+M(q-1)}{q}\right)^{-\delta}$
(E.5)

Then, we have

$\bar{d}\lesssim_{P}\xi+d^{*}\quad\text{ and
}\quad\bar{d}\gtrsim_{P}-\xi+d^{*},\quad\text{where}\quad\xi\triangleq\log^{\delta}(\tau_{o}^{\alpha}+M(q-1))\left(\frac{1+M(q-1)}{q}\right)^{-\delta}.$

Step 2.

We use the notation $a_{n}\asymp_{P}(\pm 1)\epsilon_{n}+a^{*}$ to denote
$|a_{n}-a|=\mathcal{O}_{P}(\epsilon_{n})$ that is
$a_{n}\lesssim_{P}\epsilon_{n}+a^{*}$ and
$a_{n}\gtrsim_{P}-\epsilon_{n}+a^{*}$. Then we have $\bar{d}\asymp_{P}(\pm
1)\xi+d^{*}$ which implies

$U_{M}=\int\frac{\sigma^{2}(b)}{\hat{d}_{K}^{*}}\mathrm{d}b\asymp_{P}\int\frac{\sigma^{2}(b)}{(\pm
1)\xi+d^{*}(b)}\mathrm{d}b$

Then

$\displaystyle\frac{U_{M}-c^{2}}{c}\asymp_{P}\int\frac{\sigma^{2}(b)}{c((\pm
1)\xi+d^{*}(b))}\mathrm{d}b-\int\sigma(b)\mathrm{d}b=\int\frac{\sigma^{2}(b)-c\sigma(b)((\pm
1)\xi+d^{*}(b))}{c((\pm 1)\xi+d^{*}(b))}\mathrm{d}b$

Using that $d^{*}(b)=\sigma(b)/c$ we have

$\displaystyle\frac{U_{M}-c^{2}}{c}\asymp_{P}-(\pm
1)\int\frac{\xi\sigma(b)}{\xi+d^{*}(b)}\mathrm{d}b$

By the Taylor expansion $\tfrac{zc_{1}}{zc_{2}}=\frac{c_{1}}{c_{2}}z+o(z^{2})$
as $z\rightarrow 0$, since $\xi\rightarrow 0$ as $M\rightarrow\infty$, we have

$\frac{U_{M}-c^{2}}{c}\asymp_{P}-(\pm
1)\xi\int\frac{\sigma(b)}{d^{*}(b)}\mathrm{d}b+o(\xi^{2})=-(\pm 1)\xi
c+o(\xi^{2}),\quad M\rightarrow\infty$

Then using that
$U_{M}=\int\frac{\sigma^{2}(b)}{\xi+d^{*}(b)}\mathrm{d}b\rightarrow\int\frac{\sigma^{2}(b)}{d^{*}(b)}\mathrm{d}b=c\int\sigma(b)\mathrm{d}b=c^{2}$
as $M\rightarrow\infty$ we have

$\displaystyle\rho_{M}$
$\displaystyle=\frac{U_{M}-c^{2}}{U_{M}}=\frac{U_{M}-c^{2}}{c}\frac{c}{U_{M}}\asymp_{P}-(\pm
1)\xi+o(\xi^{2})$

then as $M\rightarrow\infty$, $\rho_{M}\asymp_{P}(\pm 1)\xi=(\pm
1)\log^{\delta}(\tau_{o}^{\alpha}+M(q-1))\left(\frac{1+M(q-1)}{q}\right)^{-\delta}$
that is
$\rho_{M}=\mathcal{O}_{P}\left(\log^{\delta}(\tau_{o}^{\alpha}+M(q-1))\left(\frac{1+M(q-1)}{q}\right)^{-\delta}\right)$.
∎

Proof of Theorem 5.1

###### Proof.

From definition (5.2)

$\displaystyle\operatorname{Reg}(M)$
$\displaystyle=\sum_{k=1}^{K}\sum_{m\in\mathcal{J}_{k}}\left[{\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m,k})\right]$
(E.6)
$\displaystyle=\sum_{k=1}^{K}\left[\sum_{m\in\mathcal{I}_{k}}{\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m,k})+\sum_{m\in\mathcal{I}_{k}^{\prime}}{\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m,k})\right]$
(E.7)

For $m\in\mathcal{I}_{k}$ we have that $\theta_{m,k}$ do not minimize the
$\widehat{\mathrm{PR}}$, but using the assumption of boundedness of the loss
function we have that
${\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m,k})$ is
bounded, then

$\displaystyle\sum_{m\in\mathcal{I}_{k}}{\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m,k})\lesssim|\mathcal{I}_{k}|$
(E.8)

For $m\in\mathcal{I}_{k}^{\prime}$, where $\mathcal{I}_{k}^{\prime}$ is the
time-index of the exploitation phase, from definition (5.1) and (5.3) we have

$\theta^{\star}\in{\arg\min}_{\theta}{\mathrm{PR}}(\theta)=\sum_{a\in\mathcal{A}}{\mathbb{E}}_{Z}[\ell(\theta;Z)|A=a]\mathcal{D}_{\theta}(a)$

and

$\theta_{m,k}\in{\arg\min}_{\theta}\widehat{\mathrm{PR}}(\theta)=\sum_{a\in\mathcal{A}}{\mathbb{E}}_{Z}[\ell(\theta;Z)|A=a]\hat{\mathcal{D}}_{\theta}^{(k)}(a).$

Then

${\mathrm{PR}}(\theta^{\star})-\widehat{\mathrm{PR}}(\theta_{m,k})={\mathrm{PR}}(\theta^{\star})-{\mathrm{PR}}(\theta_{m,k})+{\mathrm{PR}}(\theta_{m,k})-\widehat{\mathrm{PR}}(\theta_{m,k})\leq{\mathrm{PR}}(\theta_{m,k})-\widehat{\mathrm{PR}}(\theta_{m,k})$

where we used that
${\mathrm{PR}}(\theta^{\star})\leq{\mathrm{PR}}(\theta_{m,k})$. Now, given
that ${\mathrm{PR}}(\theta_{m,k})\geq\widehat{\mathrm{PR}}(\theta_{m,k})$,
then

$\displaystyle 0$
$\displaystyle\leq{\mathrm{PR}}(\theta_{m,k})-\widehat{\mathrm{PR}}(\theta_{m,k})$
$\displaystyle=\left|{\mathrm{PR}}(\theta_{m,k})-\widehat{\mathrm{PR}}(\theta_{m,k})\right|$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\Big{|}{\mathbb{E}}_{Z}[\ell(\theta_{m,k};Z)|A=a]\mathcal{D}_{\theta_{m,k}}(a)-{\mathbb{E}}_{Z}[\ell(\theta_{m,k};Z)|A=a]\hat{\mathcal{D}}_{\theta_{m,k}}^{(k)}(a)\Big{|}$
$\displaystyle=\sum_{a\in\mathcal{A}}{\mathbb{E}}_{Z}[\ell(\theta_{m,k};Z)|A=a]\Big{|}\mathcal{D}_{\theta_{m,k}}(a)-\hat{\mathcal{D}}_{\theta_{m,k}}^{(k)}(a)\Big{|}$
$\displaystyle\lesssim\sum_{a\in\mathcal{A}}\Big{|}\mathcal{D}_{\theta_{m,k}}(a)-\hat{\mathcal{D}}_{\theta_{m,k}}^{(k)}(a)\Big{|}$
$\displaystyle\lesssim\|\mathcal{D}-\hat{\mathcal{D}}^{(k)}\|_{\infty}.$

Thus, by assumption, we have
${\mathrm{PR}}(\theta^{\star})-\hat{\mathrm{PR}}(\theta_{m,k})\lesssim\|\mathcal{D}-\hat{\mathcal{D}}^{(k)}\|_{\infty}=\mathcal{O}_{P}\left([\log(|\mathcal{I}_{k}|)/|\mathcal{I}_{k}|]^{\eta}\right)$,
and from (E.6) and (E.8)

$\displaystyle\sum_{m\in\mathcal{J}_{k}}\left[{\mathrm{PR}}(\theta^{\star})-\widehat{{\mathrm{PR}}}(\theta_{m,k})\right]$
$\displaystyle\lesssim|\mathcal{I}_{k}|+|\mathcal{I}^{\prime}_{k}||\mathcal{I}_{k}|^{-\eta}\log^{\eta}(|\mathcal{I}_{k}|)$
$\displaystyle\lesssim 2^{\alpha k}+2^{k}2^{-\alpha
k\eta}\log^{\eta}(2^{\alpha k})$ $\displaystyle\lesssim k^{\eta}(2^{\alpha
k}+2^{k}2^{-\alpha k\eta}).$

The optimal $\alpha$ is achieved when the two exponents are equal that is
$\alpha=1-\alpha\eta$, that implies $\alpha=1/(1+\eta)$. Then we conclude

$\operatorname{Reg}(M)\lesssim_{P}\sum_{k=1}^{K}k^{\eta}2^{\alpha k}\lesssim
K^{\eta}\sum_{k=1}^{K}2^{\alpha k}\lesssim K^{\eta}2^{\alpha
K}\lesssim\log^{\eta}(M)M^{\alpha}=\log^{\eta}(M)M^{1/(1+\eta)},$

where we used that $K=\log_{2}(1+M/\tau_{o})$. To prove the convergence of the
relative efficiency, we apply Theorem 4.1 with some changes in the proof.
Specifically, in Step 1 the number of episodes changes to
$K=\log_{2}(1+M/\tau_{o})$, and as a consequence, the line E becomes

$\displaystyle\|\hat{d}_{K}^{*}-d^{*}\|_{\infty}$
$\displaystyle\lesssim_{P}\log(L_{K})^{\delta}L_{K}^{-\delta}$
$\displaystyle=\log^{\delta}(\tau_{o}^{\alpha}2^{\alpha(K-1)})(\tau_{o}^{\alpha}2^{\alpha(K-1)})^{-\delta}$
$\displaystyle\lesssim
K^{\delta}\tau_{o}^{-\alpha\delta}\left(\frac{1+M}{\tau_{o}}\right)^{-\alpha\delta}$
$\displaystyle\lesssim\log^{\delta}(M)M^{-\alpha\delta}$
$\displaystyle=\log^{\delta}(M)M^{-\frac{\delta}{1+\eta}}$

Then we replace $\xi\leftarrow\log^{\delta}(M)M^{-\frac{\delta}{1+\eta}}$, and
the rest of the proof (that is Step 2) does not change. ∎