Chebyshev Schedules for Low-Budget Rollouts

At each rollout measurement $j$, the observed round mean is $$\bar Y_j = n^{-1}\sum_{i\in U_n} Y_i(Z_j).$$ The potential outcomes $Y_i(Z_j)$ depend on the contemporaneous assignment vector $Z_j$, but not on earlier rollout steps.

For every law $P$, the rollout mean curve satisfies $$m_P(u)=\sum_{\ell=0}^{\beta} a_{P,\ell}u^\ell$$ for all $u\in[0,1]$.

For every law $P$, every admissible schedule $p$, and every rollout measurement $j$, $$\operatorname{Var}_\pi(\bar Y_j)\le \frac{\sigma_0^2}{n}.$$

The rollout budget and its cap satisfy $$0<q_{\max}\quad\text{and}\quad q\le q_{\max}<1.$$

Let $n,k,\beta$ be integers, let $q\in\mathbb R$, and let $\sigma_0^2\in\mathbb R$. Fix a finite assignment space $\Omega$, a finite design $\pi$ on $\Omega$, rollout assignment vectors $Z_0,\ldots,Z_k$, round means $\bar Y_0,\ldots,\bar Y_k$, a rollout mean curve $m_P$, polynomial coefficients $a_{P,\ell}$, and a schedule $p=(p_0,\ldots,p_k)$. Suppose that

• (Order.) $1\le \beta\le k$.
• (Envelope scale.) $\sigma_0^2\ge 0$.
• (Schedule.) $p\in S_{k,q}$, in the sense of Definition P-1.
• (Law class.) The design, rollout variables, round means, mean curve, coefficients, envelope scale, and schedule satisfy the rollout law-class restrictions $\mathcal P_\beta$ in Definition P-2.

Then $W_\beta(p)$, as defined in Definition P-3, is nonempty. Moreover, for every $w\in W_\beta(p)$, $$\mathbb E_\pi\!\left[\sum_{j=0}^k w_j\bar Y_j\right]=m_P(1)-m_P(0)$$ and $$\operatorname{Var}_\pi\!\left(\sum_{j=0}^k w_j\bar Y_j\right) \le \frac{\sigma_0^2}{n}\left(\sum_{j=0}^k |w_j|\right)^2 .$$ For every such $w$, there also exists a positive semidefinite $(k+1)\times(k+1)$ matrix $\Gamma$ such that $$\Gamma_{jj}\le \frac{\sigma_0^2}{n}\quad\text{for every }j=0,\ldots,k,$$ and $$\sum_{i=0}^k\sum_{j=0}^k w_i\Gamma_{ij}w_j = \frac{\sigma_0^2}{n}\left(\sum_{j=0}^k |w_j|\right)^2 .$$ Consequently, with $A_\beta(\cdot)$ and $M_{\beta,k,q}$ as in Definition P-5, $$\inf\left\{ v:\ \exists w\in W_\beta(p)\text{ with } v=\frac{\sigma_0^2}{n}\left(\sum_{j=0}^k |w_j|\right)^2 \right\} = \frac{\sigma_0^2}{n}A_\beta(p),$$ and $$\inf\left\{ v:\ \exists p'\in S_{k,q}\text{ with } v=\frac{\sigma_0^2}{n}A_\beta(p') \right\} = \frac{\sigma_0^2}{n}M_{\beta,k,q}.$$ Finally, if $p^\star\in S_{k,q}$ satisfies $$A_\beta(p^\star)=M_{\beta,k,q},$$ then for every $p'\in S_{k,q}$, $$\frac{\sigma_0^2}{n}A_\beta(p^\star) \le \frac{\sigma_0^2}{n}A_\beta(p').$$

Fix a budget cap $q_{\max}\in(0,1)$. There exists a constant $C_-(q_{\max})>0$ such that, for every oversampling ratio $c>1$, there exists a constant $C_+(c,q_{\max})>0$ with the following property. For every pair of integers $\beta,k$, every rollout budget $q$, and every schedule $p$, suppose that

• (Order and oversampling.) $\beta\ge 1$ and $k\ge c\beta$.
• (Low-budget regime.) $q>0$ and the low-budget cap condition of Assumption A-4 holds for $(q,q_{\max})$.
• (Admissible schedule.) When $p$ is used below, $p\in S_{k,q}$ as in Definition P-1.

Then, with $A_\beta(\cdot)$ and $M_{\beta,k,q}$ as in Definition P-5 and $p^{\mathrm{Ch}}(k,q)$ as in Definition P-4, $$A_\beta(p) \ge C_-(q_{\max}) \left(\frac{(1+\sqrt{1-q})^2}{q}\right)^{2\beta},$$ and $$A_\beta\!\left(p^{\mathrm{Ch}}(k,q)\right) \le C_+(c,q_{\max}) \left(\frac{(1+\sqrt{1-q})^2}{q}\right)^{2\beta}.$$ Moreover, the minimax amplification satisfies the matching two-sided bound $$C_-(q_{\max}) \left(\frac{(1+\sqrt{1-q})^2}{q}\right)^{2\beta} \le M_{\beta,k,q} \le C_+(c,q_{\max}) \left(\frac{(1+\sqrt{1-q})^2}{q}\right)^{2\beta}.$$