Calibrating Regret under Weak Overlap

For a policy $\pi$, its welfare under $P$ is $$V_P(\pi)=\mathbb E_P\!\left[\pi(X)\tau_P(X)\right].$$ The oracle policy is $$\pi^\star_P(x)=\mathbf 1\{\tau_P(x)\ge 0\}.$$ The regret of $\pi$ under $P$ is $$R_P(\pi)=V_P(\pi^\star_P)-V_P(\pi).$$

Under Assumption A-4, for every deterministic policy $\pi\in\Pi$, $$R_P(\pi) = E_P\!\left[ |\tau_P(X)|\,\mathbf 1\{\pi(X)\ne\pi^\star_P(X)\} \right] = \int_{\mathcal X} |\tau_P(x)|\,\mathbf 1\{\pi(x)\ne\pi^\star_P(x)\}\,dP_X(x).$$

The parameters satisfy $0\le \alpha$, $0<C_m$, and $0<u_0$. For every $u$ with $0<u\le u_0$, $$P\{0<|\tau_P(X)|\le u\}\le C_m u^\alpha .$$

For all $u$ and $v$ with $0<u\le u_0$ and $v>0$ satisfying $$v\le c_o u^\gamma,$$ the joint small-contrast and weak-overlap probability obeys $$P\{p_P(X)\le v,\ 0<|\tau_P(X)|\le u\} \le C_o u^\alpha v^{1/\gamma},$$ with the convention that $v^{1/\gamma}=1$ when $\gamma=0$.

Suppose that the following conditions hold:

• Margin condition. Assumption A-6 holds.
• Zero-effect convention. Assumption A-7 holds.
• Bounded outcomes. Assumption A-4 holds.
• Disagreement sets. $D_\pi$ is defined as in Definition P-2.

Then there exists a constant $$C=C(C_m,u_0,\alpha)$$ such that, for every $\pi\in\Pi$, $$P_X(D_\pi) \le C\,R_P(\pi)^{\alpha/(1+\alpha)} .$$

For $\alpha\ge0$, $\gamma>0$, $h\in(0,1)$, and $\beta\ge0$, consider the tight window $$v=h^\beta, \qquad u=h^{\beta/\gamma}.$$ Then $$u^\alpha v^{1/\gamma} = h^{(\alpha+1)\beta/\gamma},$$ and $$u^\alpha v^{1/\gamma}\ge h^\alpha \quad\Longleftrightarrow\quad \beta\le \beta_{\alpha,\gamma}=\frac{\alpha\gamma}{\alpha+1},$$ with equality in the displayed power comparison whenever $\beta=\beta_{\alpha,\gamma}$. Moreover $\beta_{\alpha,\gamma}\ge0$, and for every $\beta'\ge0$, the corresponding tight window $v=h^{\beta'}$, $u=h^{\beta'/\gamma}$ satisfies $$u^\alpha v^{1/\gamma}\ge h^\alpha \quad\Longleftrightarrow\quad \beta'\le\beta_{\alpha,\gamma}.$$ Thus, within this algebraic tight-window envelope, $\beta_{\alpha,\gamma}$ is the largest admissible weak-arm exponent.

Under Assumption A-12, suppose that $\alpha,\gamma\ge0$, $C_m,C_o,c_o,c_B,\underline p>0$, $c_B\le C_m$, $c_B\le C_o$, $0<\underline p\le 1/4$, and $8c_B<\log 5$. In addition, when $\gamma>0$ and $\alpha>0$, assume $c_B\le C_o c_o^{-\alpha/\gamma}$, and when $\gamma>0$ and $\alpha=0$, assume $c_B\le C_o 4^{-1/\gamma}$. If the policy class $\Pi$ is nonempty and every $\pi\in\Pi$ is measurable, then for the minimax regret $M_n(\alpha,\gamma)$ of Definition P-8 over the law class $\mathcal P_{\alpha,\gamma}$ of Definition P-10, there is a constant $c>0$, independent of $n$, such that for all sufficiently large $n$, $$M_n(\alpha,\gamma) = \inf_{\widehat\pi} \sup_{P\in\mathcal P_{\alpha,\gamma}} \mathbb E_P R_P(\widehat\pi) \ge c\,n^{-r_\star(\alpha,\gamma)}.$$

Fix one nuisance regime $(a,c,C_\mu,C_{\mathrm{prod}})$, and set $$A_\alpha=\frac{1+\alpha}{2+\alpha}.$$ If $\gamma>0$, fix constants $$\bar u\in(0,u_0], \qquad q_0\in\bigl(0,\min\{1/2,c_o\bar u^\gamma\}\bigr].$$ For $0\le s\le 1/2$ and $0\le t\le s/\gamma$, define $$\phi(s,t) = \min\left\{ A_\alpha(1-2s),\, c-s,\, a+\frac{s}{2\gamma}+\frac{\alpha t}{2},\, 2a-t \right\}.$$ Let $(s_{\mathrm{feas}},t_{\mathrm{feas}})$ be any maximizer of $\phi$ over this compact feasible set, and set $$g_{\mathrm{joint}}(\alpha,\gamma,a,c) = \phi(s_{\mathrm{feas}},t_{\mathrm{feas}}), \qquad q_n=q_0 n^{-s_{\mathrm{feas}}}, \qquad u_n=\bar u n^{-t_{\mathrm{feas}}}.$$ Then $q_n\le c_o u_n^\gamma$ for all sufficiently large $n$, and the solved conditional feasible upper exponent is $$r_{\mathrm{up}} = r_{\mathrm{feas}} = \min\left\{r_\star(\alpha,\gamma),\,g_{\mathrm{joint}}(\alpha,\gamma,a,c)\right\}.$$ If $\gamma=0$, take a fixed clipping sequence $q_n=q_0$ with $q_0\in(0,\underline p/2]$, and set $$r_{\mathrm{up}} = r_{\mathrm{feas}} = \min\{A_\alpha,c\}.$$

Fix parameters with $0\le \gamma$ and a nuisance regime $(a,c,C_\mu,C_{\mathrm{prod}})$ satisfying Assumption A-16, with $C_\mu\ge0$ and $C_{\mathrm{prod}}\ge0$. Consider the law class $\mathcal P_{\alpha,\gamma}$ of Definition P-10, the feasible cross-fitted clipped-AIPW $1/n$-ERM $\widehat\pi_n$ of Definition P-7, formed using an enumeration of a pointwise-dense skeleton of $\Pi$, and the conditional upper risk $U_n(\alpha,\gamma,a,c;\widehat\eta)$ of Definition P-9. Let the feasible clipping and localization constants $q_0,\bar u$ lie in the input domain of Definition P-4: if $\gamma>0$, then $$0<\bar u\le u_0,\qquad 0<q_0\le \min\{1/2,c_o\bar u^\gamma\},$$ and if $\gamma=0$, then $$0<q_0\le \underline p/2.$$ Assume:

• (Policy class and skeleton.) The policy class satisfies Assumption A-9, and the enumeration used by $\widehat\pi_n$ is a pointwise-dense skeleton of $\Pi$.
• (Cross-fitting.) The number of folds satisfies Assumption A-17.
• (Nuisance boundedness.) The cross-fitted outcome nuisance estimators satisfy Assumption A-15.
• (Nuisance measurability and integrability.) For every $n$ and fold $k$, $\widehat\mu_{0,n}^{(-k)}$, $\widehat\mu_{1,n}^{(-k)}$, and $\widehat e_n^{(-k)}$ are measurable. The rate sequences satisfy $r_{\mu,n}\ge0$ and $r_{e,n}\ge0$ for all sufficiently large $n$. For all sufficiently large $n$, every $P\in\mathcal P_{\alpha,\gamma}$, and every fold $k$, the errors $\widehat\mu_{0,n}^{(-k)}-\mu_{0,P}$, $\widehat\mu_{1,n}^{(-k)}-\mu_{1,P}$, and $\widehat e_n^{(-k)}-e_P$ belong to $L^2(P_X)$.
• (Localized envelopes.) The uniform localized empirical-process and offset envelope conditions in Assumption A-11 and Assumption A-18 hold.

Then there exist constants $C,p$ with $0<C$ and $0\le p$ such that, for all sufficiently large $n$, the conditional upper risk of $\widehat\pi_n$, uniformly over the side-condition domain in Definition P-9, satisfies $$U_n(\alpha,\gamma,a,c;\widehat\eta)\le C n^{-r_{\mathrm{up}}}(\log n)^p,$$ where $r_{\mathrm{up}}$ is the feasible upper exponent supplied by Definition P-4 for the above $q_0$ and $\bar u$.

In the strict-gap branch of the conditional feasible achievability bound for the regime-indexed risk $U_n$, it is open whether a genuinely feasible estimator using estimated cross-fitted nuisance functions can attain the converse exponent $r_\star(\alpha,\gamma)$, or whether weak-arm nuisance learning imposes the slower conditional exponent derived by the feasible upper bound.