for any arbitrary functions $\Delta q^{(t)}(Z_{t},A_{t})$ and $\Delta
h^{(t)}(W_{t},A_{t})$ for each $t\in[H]$ that have finite supremum norm, we
have

$\left.\frac{\partial}{\partial
r}\right|_{r=0}\mathbb{E}_{\mathcal{P}_{b}}[\psi_{\text{DR}}(\tau_{H})|_{r}]=0\,.$

###### Proof of Lemma 8.

First, we note that

$\psi_{\text{DR}}(\tau_{H})|_{r}=\sum_{a\in\mathcal{A}}h^{(1)}_{r}(W_{1},a)+q^{(1)}_{r}(Z_{1},A_{1})\left(\mathds{1}\\{A_{1}=E_{1}\\}Y_{1,r}-h^{(1)}_{r}(W_{1},A_{1})\right)\,,$

where

$\displaystyle Y_{t,r}$
$\displaystyle=R_{t}+\gamma\left(\sum_{a\in\mathcal{A}}h^{(t+1)}_{r}(W_{t},a)+q^{(t+1)}_{r}(Z_{t},A_{t})\left(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t+1,r}-h^{(t+1)}_{r}(W_{t},A_{t})\right)\right)\quad\forall
t<H$ $\displaystyle Y_{H,r}$ $\displaystyle=R_{H}\,.$

Therefore, we have

$\displaystyle\left.\frac{\partial}{\partial
r}\right|_{r=0}\psi_{\text{DR}}(\tau_{H})|_{r}$
$\displaystyle=\sum_{a\in\mathcal{A}}\Delta
h^{(1)}(W_{1},a)-q^{(1)}(Z_{1},A_{1})\Delta h^{(1)}(W_{1},A_{1})$
$\displaystyle\quad+\left(\Delta
q^{(1)}(Z_{1},A_{1})\right)\left(\mathds{1}\\{A_{1}=E_{1}\\}Y_{1,0}-h^{(1)}(W_{1},A_{1})\right)$
$\displaystyle\quad+q^{(1)}(Z_{1},A_{1})\mathds{1}\\{A_{1}=E_{1}\\}\left.\frac{\partial}{\partial
r}\right|_{r=0}Y_{1,r}\,.$

Now, following an identical argument as in Lemma 6, for any $t\in[H]$ and
arbitrary functions $\tilde{h}$ and $\tilde{q}$ with he same signature as
$h^{(t)}$ and $q^{(t)}$ we have

$\displaystyle\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\tilde{h}(W_{t},a)-q^{(t)}(Z_{t},A_{t})\tilde{h}(W_{t},A_{t})\right]$
$\displaystyle=0$ (12)
$\displaystyle\mathbb{E}^{*}_{t}\left[\tilde{q}(Z_{t},A_{t})\left(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t,0}-h^{(t)}(W_{t},A_{t})\right)\right]$
$\displaystyle=0\,.$ (13)

In addition, it is straightforward to argue via backward induction on $t$ that

$\mathbb{E}^{*}_{t}\left[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t})\\}\left.\frac{\partial}{\partial
r}\right|_{r=0}Y_{t,r}\right]=0\,,$

for every $t\in[H]$. For the base case where $t=H$, this is straightforward
since $Y_{H,r}=R_{H}$, which doesn’t depend on $r$. Otherwise, for the
inductive case, we first note that following Lemma 4, for any $t\leq H$ we
have

$\mathbb{E}^{*}_{t-1}\left[q^{(t-1)}(Z_{t-1},A_{t-1})\mathds{1}\\{A_{t-1}=E_{t-1})\\}\left.\frac{\partial}{\partial
r}\right|_{r=0}Y_{t-1,r}\right]=\mathbb{E}^{*}_{t}\left[\left.\frac{\partial}{\partial
r}\right|_{r=0}Y_{t-1,r}\right]\,,$

and furthermore we have

$\displaystyle\left.\frac{\partial}{\partial r}\right|_{r=0}Y_{t-1,r}$
$\displaystyle=\gamma\sum_{a\in\mathcal{A}}\Delta h^{(t)}(W_{t},a)-\gamma
q^{(t)}(Z_{t},A_{t})\Delta h^{(t)}(W_{t},A_{t})$
$\displaystyle\quad+\gamma\Delta
q^{(t)}(Z_{t},A_{t})\left(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t,0}-h^{(t)}(W_{t},A_{t})\right)$
$\displaystyle\quad+\gamma
q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}\left.\frac{\partial}{\partial
r}\right|_{r=0}Y_{t,r}\,.$

Now, given Eqs. 12 and 13 it immediately follows that the first three terms
have mean zero under $\mathbb{E}^{*}_{t}$. Furthermore, the final term also
has mean zero by the inductive assumption. This completes the backward
induction, and therefore putting the above together we have

$\mathbb{E}_{\mathcal{P}_{b}}\left[\left.\frac{\partial}{\partial
r}\right|_{r=0}\psi_{\text{DR}}(\tau_{H})|_{r}\right]=0\,.$

It only remains to argue that we can swap the order of differentiation and
integration in this equation. By the mean value theorem, we have

$\frac{\psi_{\text{DR}}(\tau_{H})|_{r}-\psi_{\text{DR}}(\tau_{H})}{r}=\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}\psi_{\text{DR}}(\tau_{H})|_{r}\,,$

for some $r^{\prime}\in(0,r)$. Therefore, it follows that

$\left.\frac{\partial}{\partial
r}\right|_{r=0}\mathbb{E}_{\mathcal{P}_{b}}\left[\psi_{\text{DR}}(\tau_{H})|_{r}\right]=\lim_{r^{\prime}\to
0}\mathbb{E}_{\mathcal{P}_{b}}\left[\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}\psi_{\text{DR}}(\tau_{H})|_{r}\right]\,.$

Now, clearly $\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}\psi_{\text{DR}}(\tau_{H})|_{r}$ converges point-wise
to $\left.\frac{\partial}{\partial
r}\right|_{r=0}\psi_{\text{DR}}(\tau_{H})|_{r}$ as $r^{\prime}\to 0$.
Furthermore, it follows trivially from the definitions of $q_{r}^{(t)}$ and
$h_{r}^{(t)}$ that $\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}q^{(t)}_{r}=\Delta q^{(t)}$, and
$\left.\frac{\partial}{\partial r}\right|_{r=r^{\prime}}h^{(t)}_{r}=\Delta
h^{(t)}$ for every $t\in[H]$ and $r^{\prime}\in[0,1]$. Therefore, for any
$r^{\prime}\in[0,1]$ we have

$\displaystyle\left\|\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}\psi_{\text{DR}}(\tau_{H})|_{r}\right\|_{\infty}$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\|\Delta h^{(1)}(W_{1},a)\|_{\infty}$
$\displaystyle\quad+\|\Delta
q^{(1)}(Z_{1},A_{1})\|_{\infty}\left(\|Y_{1,r^{\prime}}\|_{\infty}+\|h^{(1)}(W_{1},A_{1})\|_{\infty}+\|\Delta
h^{(1)}(W_{1},A_{1})\|_{\infty}\right)$
$\displaystyle\quad+\left(\|q^{(1)}(Z_{1},A_{1})\|_{\infty}+\|\Delta
q^{(1)}(Z_{1},A_{1})\|_{\infty}\right)$
$\displaystyle\qquad\cdot\left(\|\Delta
h^{(1)}(W_{1},A_{1})\|_{\infty}+\left\|\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}Y_{1,r}\right\|_{\infty}\right)\,.$

Now, by assumption we know that $q^{(t)}$, $h^{(t)}$, $\Delta q^{(t)}$, and
$\Delta h^{(t)}$ all have bounded supremum norm, so therefore
$\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}(\psi_{\text{DR}}(\tau_{H}))_{r}$ is uniformly bounded
in supremum norm over $r^{\prime}\in[0,1]$, as long as we can uniformly bound
$\|Y_{1,r^{\prime}}\|_{\infty}$ and $\|\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}Y_{1,r}\|_{\infty}$. Therefore, our final result would
follow by the dominated convergence theorem as long as we can show these two
bounds. In order to show this, bote that for any $t<H$ and
$r^{\prime}\in[0,1]$ we can bound

$\displaystyle\left\|Y_{t,r}\right\|_{\infty}$
$\displaystyle\leq\|R_{t}\|_{\infty}+\gamma\sum_{a\in\mathcal{A}}\left(\|h^{(t+1)}(W_{t+1},a)\|_{\infty}+\|\Delta
h^{(t+1)}(Z_{t+1},a)\|_{\infty}\right)$
$\displaystyle\quad+\gamma\left(\|q^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}+\|\Delta
q^{(t+1)}(Z_{t+1},A_{t+1})\|_{\infty}\right)$
$\displaystyle\qquad\cdot\left(\|Y_{t+1,r}\|_{\infty}+\|h^{(t+1)}(W_{t+1},a)\|_{\infty}+\|\Delta
q^{(t+1)}(Z_{t+1},A_{t+1})\|_{\infty}\right)\,,$

and

$\displaystyle\left\|\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}Y_{t,r}\right\|_{\infty}$
$\displaystyle\leq\gamma\sum_{a\in\mathcal{A}}\|\Delta
h^{(t+1)}(W_{1},a)\|_{\infty}$ $\displaystyle\quad+\gamma\|\Delta
q^{(t+1)}(Z_{t+1},A_{t+1})\|_{\infty}$
$\displaystyle\qquad\cdot\left(\|Y_{t+1,r^{\prime}}\|_{\infty}+\|h^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}+\|\Delta
h^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}\right)$
$\displaystyle\quad+\gamma\left(\|q^{(t+1)}(Z_{t+1},A_{t+1})\|_{\infty}+\|\Delta
q^{(t+1)}(Z_{t+1},A_{t+1})\|_{\infty}\right)$
$\displaystyle\qquad\cdot\left(\|\Delta
h^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}+\left\|\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}Y_{t+1,r}\right\|_{\infty}\right)\,,$

and for $t=H$ we have $\|Y_{H,r^{\prime}}\|_{\infty}=\|R_{H}\|_{\infty}$ and
$\left\|\left.\frac{\partial}{\partial
r}\right|_{r=r^{\prime}}Y_{H,r}\right\|_{\infty}=0$ for all $r^{\prime}$.
Therefore, given this and the fact that all rewards are bounded by assumption,
it follows from backward induction that $\|Y_{1,r^{\prime}}\|_{\infty}$ and
$\|\left.\frac{\partial}{\partial r}\right|_{r=r^{\prime}}Y_{1,r}\|_{\infty}$
are uniformly bounded over $r^{\prime}\in[0,1]$. Thus, the final result
follows by the dominated convergence theorem as discussed above.

Before

∎

###### Proof.

Proof of Theorem 3

We will establish this proof based on directly applying Chernozhukov et al.
[2016, Theorem 3.1]. We note that this theorem immediately implies Theorem 3,
as long as we can establish that its conditions hold. We will proceed by
establishing these conditions one by one. Specifically, we need to establish
their Assumption 3.1 and Assumption 3.2.

We note that Chernozhukov et al. [2016, Theorem 3.1] considers linear scores,
where the parameter of interest $\theta$ is the solution to

$\mathbb{E}[\psi(\tau_{H};\theta,\xi)]=\mathbb{E}[\psi^{a}(\tau_{H};\xi)\theta+\psi^{b}(\tau_{H};\xi)]=0\,,$
(14)

where $\xi$ represents the nuisance functions, and
$\psi(\tau_{H};\theta,\xi)=\psi^{a}(\tau_{H};\xi)\theta+\psi^{b}(\tau_{H};\xi)$.
In our case, the notation above corresponds to our quantities of interest as
follows: $\theta=v_{\gamma}(\pi_{e})$ is the target policy value;
$\xi=q^{(1)},\ldots,q^{(H)},h^{(1)},\ldots,h^{(H)}$;
$\psi^{a}(\tau_{H};\xi)=-1$; and $\psi^{b}(\tau_{H};\xi)$ is equal to
$\psi_{\text{DR}}(\tau_{H})$ with the true nuisances replaced with $\xi$.

Define
$\mathcal{G}_{a}=\\{q^{(t)}(Z_{t},A_{t}):t\in[H]\\}\cup\\{h^{(t)}(W_{t},a):t\in[H]\\}$,
and let $\Xi(c,c^{\prime},c^{\prime\prime})$ denote the set of all possible
nuisances $\xi$ such that, for all $a\in\mathcal{A}$ and
$\Psi,\Psi^{\prime}\in\mathcal{G}_{a}$ _s.t._ $\Psi\neq\Psi^{\prime}$, we
have:

$\displaystyle\|\Delta\Psi\|_{\infty}$ $\displaystyle\leq c$
$\displaystyle\|\Delta\Psi\|_{2,\mathcal{P}_{b}}$ $\displaystyle\leq
c^{\prime}$
$\displaystyle\|\Delta\Psi\Delta\Psi^{\prime}\|_{2,\mathcal{P}_{b}}$
$\displaystyle\leq c^{\prime\prime}\,.$

In addition, let $\xi_{0}$ denote the value of the true nuisances, and let
$\hat{\xi}_{n}$ denote the estimated nuisances using $n$ trajectories
$\tau_{H}^{(1)},\ldots,\tau_{H}^{(n)}$. We note that by Assumption 4 there
must exist some constant $c^{*}$ and sequences $c^{\prime}_{n}\in o(1)$ and
$c^{\prime\prime}_{n}\in o(n^{-1/2})$ such that
$P(\hat{\xi}_{n}\in\Xi(c^{*},c^{\prime}_{n},c^{\prime\prime}_{n}))\to 1$ as
$n\to\infty$, and let
$\Xi_{n}=\Xi(c^{*},c^{\prime}_{n},c^{\prime\prime}_{n})$. We also note that
according to the above definitions
$\psi_{\text{DR}}(\tau_{H})=\psi^{b}(\tau_{H};\xi_{0})$, and
$\xi_{0}\in\Xi_{n}$ for all $n$.

First, let us establish Chernozhukov et al. [2016, Assumption 3.1]. For (i)
and (ii) we note that $v_{\gamma}(\pi_{e})$ satisfies Eq. 14 trivially given
Theorem 2, and that this score is linear in $\theta$. For (iii) we note that
following an almost identical argument as in the proof of Lemma 8 by applying
the dominated convergence theorem, it is trivial that
$\mathbb{E}[\psi_{\text{DR}}(\tau_{H})]$ is twice Gateaux differentiable for
any $\xi-\xi_{0}\in\Xi_{n}$, since for all such directions we have $\|\Delta
q^{(t)}(Z_{t},A_{t})\|_{\infty}<\infty$ and $\|\Delta
h^{(t)}(W_{t},A_{t})\|_{\infty}<\infty$. Condition (iv) holds trivially with
nuisance set $\Xi_{n}$ for _any_ sequence $\delta_{n}$, since by Lemma 8 we
have exact Neyman orthogonality. Finally, (v) holds trivially for _any_
$c_{0}\in(0,1)$ and $c_{1}\in(1,\infty)$, since $\psi^{a}(\tau_{H};\xi)$ is
constant.

Next, let us establish Chernozhukov et al. [2016, Assumption 3.2]. For (i), we
note that by Assumption 4 we have that $\hat{\xi}_{n}\in\Xi_{n}$ with
probability approaching one. For (ii), we note that given the definition of
$\Xi_{n}$ and the fact that rewards are bounded, it trivially follows that for
_any_ $q>2$ we have

$\sup_{\xi\in\Xi(c^{*})}\|\psi^{b}(\tau_{H};\xi)\|_{q,\mathcal{P}_{b}}\leq\sup_{\xi\in\Xi(c^{*})}\|\psi^{b}(\tau_{H};\xi)\|_{\infty}<\infty\,,$

from which (ii) follows trivially, since we showed that part (v) of
Chernozhukov et al. [2016, Assumption 3.2] holds for _any_ arbitrary
$c_{1}\in(1,\infty)$. For (iii), we can first note that clearly

$\sup_{\xi\in\Xi(c^{*})}|\mathbb{E}_{\mathcal{P}_{b}}[\psi^{a}(\tau_{H};\xi)]-\mathbb{E}_{\mathcal{P}_{b}}[\psi^{a}(\tau_{H};\xi_{0})]|=0\,,$

since $\psi^{a}$ is constant. Second, we note that for any
$\hat{\xi}\in\Xi_{n}$, we have

$\displaystyle\|\psi(\tau_{H};v_{\gamma}(\pi_{e}),\hat{\xi})-\psi(\tau_{H};v_{\gamma}(\pi_{e}),\xi_{0})\|_{2,\mathcal{P}_{b}}$
$\displaystyle=\|\Delta\psi^{b}(\tau_{H};\xi)\|_{2,\mathcal{P}_{b}}$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\left\|\Delta
h^{(1)}(W_{1},a)\right\|_{2,\mathcal{P}_{b}}+\|q^{(1)}(Z_{1},A_{1})\|_{\infty}\left(\left\|\Delta
h^{(1)}(W_{1},A_{1})\right\|_{2,\mathcal{P}_{b}}+\left\|\Delta
Y_{1}\right\|_{2,\mathcal{P}_{b}}\right)$ $\displaystyle\qquad+\|\Delta
q^{(1)}(Z_{1},A_{1})\|_{2,\mathcal{P}_{b}}\left(\left\|h^{(1)}(W_{1},A_{1})\right\|_{\infty}+\left\|Y_{1}\right\|_{\infty}\right)$
$\displaystyle\qquad+\|\Delta
q^{(1)}(Z_{1},A_{1})\|_{2,\mathcal{P}_{b}}\left(\left\|\Delta
h^{(1)}(W_{1},A_{1})\right\|_{2,\mathcal{P}_{b}}+\left\|\Delta
Y_{1}\right\|_{2,\mathcal{P}_{b}}\right)$
$\displaystyle\leq|\mathcal{A}|c^{\prime}_{n}+c^{*}(c^{\prime}_{n}+\left\|\Delta
Y_{1}\right\|_{2,\mathcal{P}_{b}})+(c^{*}+\left\|\Delta
Y_{1}\right\|_{\infty})c^{\prime}_{n}+(c^{\prime}_{n}+\left\|\Delta
Y_{1}\right\|_{2,\mathcal{P}_{b}})c^{\prime}_{n}\,,$

and furthermore for each $1<t\leq H$ we have

$\displaystyle\left\|\Delta Y_{t-1}\right\|_{2,\mathcal{P}_{b}}$
$\displaystyle\leq\gamma\sum_{a\in\mathcal{A}}\left\|\Delta
h^{(t)}(W_{t},a)\right\|_{2,\mathcal{P}_{b}}+\gamma\|q^{(t)}(Z_{t},A_{t})\|_{\infty}\left(\left\|\Delta
h^{(t)}(W_{t},A_{t})\right\|_{2,\mathcal{P}_{b}}+\left\|\Delta
Y_{t}\right\|_{2,\mathcal{P}_{b}}\right)$ $\displaystyle\qquad+\gamma\|\Delta
q^{(t)}(Z_{t},A_{t})\|_{2,\mathcal{P}_{b}}\left(\left\|h^{(t)}(W_{t},A_{t})\right\|_{\infty}+\left\|Y_{t}\right\|_{\infty}\right)$
$\displaystyle\qquad+\gamma\|\Delta
q^{(t)}(Z_{t},A_{t})\|_{2,\mathcal{P}_{b}}\left(\left\|\Delta
h^{(t)}(W_{t},A_{t})\right\|_{2,\mathcal{P}_{b}}+\left\|\Delta
Y_{t}\right\|_{2,\mathcal{P}_{b}}\right)$
$\displaystyle\leq\gamma|\mathcal{A}|c^{\prime}_{n}+\gamma
c^{*}(c^{\prime}_{n}+\left\|\Delta
Y_{t}\right\|_{2,\mathcal{P}_{b}})+\gamma(c^{*}+\left\|\Delta
Y_{t}\right\|_{\infty})c^{\prime}_{n}+\gamma(c^{\prime}_{n}+\left\|\Delta
Y_{t}\right\|_{2,\mathcal{P}_{b}})c^{\prime}_{n}\,.$

Now, as argued in the proof of Lemma 8, it easily follows by backward
induction on $t$ that $\|Y_{t}\|_{\infty}<\infty$. Therefore, given the above
equation it easily follows again by backward induction on $t$ that $\|\Delta
Y_{t}\|_{2,\mathcal{P}_{b}}\leq\delta^{(1)}_{n}$ and
$\|\Delta\psi^{b}(\tau_{H};\xi)\|_{2,\mathcal{P}_{b}}\leq\delta^{(1)}_{n}$ for
all $\hat{\xi}\in\Xi_{n}$, where the sequence $\delta^{(1)}_{n}\in o(1)$ does
not depend on $\hat{\xi}$. Thus, we have

$\sup_{\xi\in\Xi_{n}}\left\|\psi(\tau_{H};v_{\gamma}(\pi_{e}),\hat{\xi})-\psi(\tau_{H};v_{\gamma}(\pi_{e}),\xi_{0})\right\|_{2,\mathcal{P}_{b}}\leq\delta^{(1)}_{n}\,.$

Similarly, recalling that

$\psi_{\text{DR}}(\tau_{H})=\sum_{t=1}^{H}\gamma^{t-1}\left(\eta_{t+1}R_{t}+\eta_{t}\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)-\eta_{t}q^{(t)}(Z_{t},A_{t})h^{(t)}(W_{t},A_{t})\right)\,,$

for any $\hat{\xi}\in\Xi_{n}$ we also have

$\displaystyle\frac{\partial^{2}}{\partial r^{2}}\psi^{b}(\tau_{H};\xi|_{r})$
$\displaystyle=\sum_{t=1}^{H}\gamma^{t-1}\frac{\partial^{2}}{\partial
r^{2}}\eta_{t+1,r}\left(R_{t}+\sum_{a\in\mathcal{A}}h_{r}^{(t)}(W_{t},a)-q_{r}^{(t)}(Z_{t},A_{t})h_{r}^{(t)}(W_{t},A_{t})\right)$
$\displaystyle\qquad+\sum_{t=1}^{H}\gamma^{t-1}\frac{\partial}{\partial
r}\eta_{t,r}\left(\sum_{a\in\mathcal{A}}\Delta h^{(t)}(W_{t},a)+\Delta
q^{(t)}(Z_{t},A_{t})h_{r}(W_{t},A_{t})+q_{r}^{(t)}(Z_{t},A_{t})\right)$

and

$\displaystyle\frac{\partial}{\partial r}\eta_{t,r}$
$\displaystyle=\sum_{s\in[t]}\Delta q^{(s)}(Z_{s},A_{s})b_{r}(s)$
$\displaystyle\frac{\partial^{2}}{\partial r^{2}}\eta_{t,r}$
$\displaystyle=\sum_{s\in[t]}\sum_{s^{\prime}\in[t]\setminus\\{s\\}}\Delta
q^{(s)}(Z_{s},A_{s})\Delta
q^{(s^{\prime})}(Z_{s^{\prime}},A_{s^{\prime}})b_{r}(s,s^{\prime})$

where

$\displaystyle b_{r}(s)$
$\displaystyle=\mathds{1}\\{E_{s}=A_{s}\\}\prod_{h\in[t]\setminus\\{s\\}}\mathds{1}\\{E_{h}=A_{h}\\}q_{r}^{(h)}(Z_{h},A_{h})$
$\displaystyle b_{r}(s,s^{\prime})$
$\displaystyle=\mathds{1}\\{E_{s}=A_{s}\\}\mathds{1}\\{E_{s^{\prime}}=A_{s^{\prime}}\\}\prod_{h\in[t]\setminus\\{s,s^{\prime}\\}}\mathds{1}\\{E_{h}=A_{h}\\}q_{r}^{(h)}(Z_{h},A_{h})\,.$

Therefore, it easily follows from the above and the definition of $\Xi_{n}$
that for all $\hat{\xi}\in\Xi_{n}$ we have

$\displaystyle\left\|\frac{\partial^{2}}{\partial
r^{2}}\psi^{b}(\tau_{H};\xi|_{r})\right\|_{\infty}\leq k_{1}$
$\displaystyle\left\|\frac{\partial^{2}}{\partial
r^{2}}\psi^{b}(\tau_{H};\xi|_{r})\right\|_{1,\mathcal{P}_{b}}\leq
k_{2}c^{\prime\prime}_{n}\,,$

for some constants $k_{1}$ and $k_{2}$ that don’t depend on $\hat{\xi}$ or on
$r$. Therefore, we can apply the dominated convergence theorem to obtain

$\sup_{r\in(0,1),\xi\in\Xi_{n}}\left|\mathbb{E}_{\mathcal{P}_{b}}{\psi(\tau_{H};v_{\gamma}(\pi_{e}),r\xi+(1-r)\xi_{0})}\right|\leq
k_{2}c^{\prime\prime}_{n}\,.$

Putting the above together, we have condition (iii) with
$\delta_{n}=\max(\delta^{(1)}_{n},k_{2}\sqrt{n}c^{\prime\prime}_{n})$.
Finally, condition (iv) follows since by assumption the variance of
$\psi_{\text{DR}}(\tau_{H})$ is non-zero.

Therefore, we have established the conditions of Chernozhukov et al. [2016,
Theorem 3.1], so applying this theorem we have

$\sqrt{n}(\hat{v}^{(n)}_{\gamma}(\pi_{e})-v_{\gamma}(\pi_{e}))=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\psi_{\text{DR}}(\tau_{H}^{(i)})+o_{p}(1)\,,$

which by the central limit theorem and Slutsky’s theorem converges in
distribution to $\mathcal{N}(0,\sigma^{2}_{\textup{DR}})$.

∎

###  C.5 Proof of Theorem 4

We will define the following notation in this appendix: for each $t\in[H]$ let
$T_{t,\epsilon}=T_{t,\mathcal{P}_{\epsilon}}$, where $T_{t,\mathcal{P}}$ are
defined as in Definition 1, and let $T_{t,\epsilon}$, $q^{(t)}_{\epsilon}$,
$h^{(t)}_{\epsilon}$, $Y_{t,\epsilon}$, $\mu_{t,\epsilon}$ be defined
analogously following the corresponding definitions in Definition 1 with
$\mathcal{P}_{\epsilon}$ replaced in the notation with $\epsilon$ for brevity.
In addition, let $\mathbb{E}_{\epsilon}$ denote expectation under
$\mathcal{P}_{\epsilon}$, and $P_{\epsilon}$ denote probability of discrete
variables under $\mathcal{P}_{\epsilon}$.

Before we present the main proof, we will provide the following technical
lemmas, which will allow us to establish that $V(\mathcal{P})$ is pathwise
differentiable at $\mathcal{P}_{b}$ and show that
$\psi_{\text{DR}}(\tau_{H})-v_{\gamma}(\pi_{e})$ is a gradient. First, the
following core lemma is useful for differentiating through functionals of
$\mathcal{P}_{\epsilon}$. We note that something similar to this lemma is
often implicitly assumed in other work, however often the regularity
conditions on the parametric submodel and functional needed to apply the
dominated convergence theorem are often not justified

######  Lemma 9.

Let $\mathcal{P}_{\epsilon}$ be a parametric submodel, and suppose that
function $f_{\epsilon}(\tau_{H})$ indexed by $\epsilon$ converges point-wise
to $f(\tau_{H})$ as $\epsilon\to 0$. Suppose in addition that it is uniformly
bounded for small $\epsilon$; that is, $\limsup_{\epsilon\to
0}\|f_{\epsilon}(\tau_{H})\|_{\infty}<\infty$. Then, we have

$\lim_{\epsilon\to
0}\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}[f_{\epsilon}(\tau_{H})]-\mathbb{E}_{0}[f_{\epsilon}(\tau_{H})]\right)=\mathbb{E}_{0}[s(\tau_{H})f(\tau_{H})]$

###### Proof of Lemma 9.

Let $\mu(\tau_{H})$ be a dominating measure for all measures in the parametric
submodel, and let
$p_{\epsilon}(\tau_{H})=(d\mathcal{P}_{\epsilon}/d\mu)(\tau_{H})$. Then, we
have

$\displaystyle\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}[f_{\epsilon}(\tau_{H})]-\mathbb{E}_{0}[f_{\epsilon}(\tau_{H})]\right)$
$\displaystyle=\int\frac{1}{\epsilon}\left(p_{\epsilon}(\tau_{H})-p_{0}(\tau_{H})\right)f_{\epsilon}(\tau_{H})d\mu(\tau_{H})$
$\displaystyle=\int
p_{\epsilon^{\prime}}(\tau_{H})s_{\epsilon^{\prime}}(\tau_{H})f_{\epsilon}(\tau_{H})d\mu(\tau_{H})\,,$

where in the second equality we apply the mean value theorem, and
$\epsilon^{\prime}\in(0,\epsilon)$. Then, given the boundedness condition on
$p_{\epsilon^{\prime}}(\tau_{H})s_{\epsilon^{\prime}}(\tau_{H})$ for
parametric submodels assumed in Appendix A, as well as the uniform boundedness
and point-wise convergence assumed on $f_{\epsilon}$, applying the dominated
convergence theorem gives us

$\displaystyle\lim_{\epsilon\to
0}\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}[f_{\epsilon}(\tau_{H})]-\mathbb{E}_{0}[f_{\epsilon}(\tau_{H})]\right)$
$\displaystyle=\int
p_{0}(\tau_{H})s_{0}(\tau_{H})f_{0}(\tau_{H})d\mu(\tau_{H})$
$\displaystyle=\mathbb{E}_{0}[s(\tau_{H})f(\tau_{H})]\,,$

as required. ∎

Next, the following lemma shows that the set of functions indexed by
$\epsilon$ satisfying a particular pair of boundedness conditions, which we
will consider below, is closed under addition and multiplication.
Specifically, for any $u>0$, we will consider the following set

$\mathcal{F}_{\textup{bounded}}(u)=\left\\{f_{\epsilon}(\tau_{H}):\sup_{|\epsilon^{\prime}|\leq
u}\|f_{\epsilon^{\prime}}(\tau_{H})\|_{\infty}<\infty\quad\text{and}\quad\sup_{|\epsilon^{\prime}|\leq
u}\left\|\frac{1}{\epsilon^{\prime}}\left(f_{\epsilon^{\prime}}(\tau_{H})-f_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}<\infty\right\\}\,.$
(15)

The second condition in this definition is important since in our main proof
of Theorem 4 we will need to uniformly bound some terms of the form
$(1/\epsilon)(f_{\epsilon}(\tau_{H})-f_{0}(\tau_{H}))$, that are not
necessarily differentiable, in order to apply dominated convergence theorem-
based arguments. In particular, we do _not_ assume in our definition of
$\mathcal{M}_{\textup{PCI}}$ or by Assumption 5 that $q_{\epsilon}^{(t)}$ or
$h_{\epsilon}^{(t)}$ are differentiable with respect to $\epsilon$.

######  Lemma 10.

Let $\mathcal{F}_{\textup{bounded}}(u)$ be defined as in Eq. 15 for each, and
suppose that $f_{\epsilon}(\tau_{H})\in\mathcal{F}_{\textup{bounded}}(u)$ and
$g_{\epsilon}(\tau_{H})\in\mathcal{F}_{\textup{bounded}}(u)$ for some $u>0$.
Then
$f_{\epsilon}(\tau_{H})+g_{\epsilon}(\tau_{H})\in\mathcal{F}_{\textup{bounded}}(u)$
and
$f_{\epsilon}(\tau_{H})g_{\epsilon}(\tau_{H})\in\mathcal{F}_{\textup{bounded}}(u)$.

###### Proof of Lemma 10.

Let $c_{1},c_{2},d_{1},d_{2}<\infty$ be constants such that

$\displaystyle\sup_{|\epsilon|\leq u}\|f_{\epsilon}(\tau_{H})\|_{\infty}$
$\displaystyle\leq c_{1}\qquad\qquad\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(f_{\epsilon}(\tau_{H})-f_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}\leq
d_{1}$ $\displaystyle\sup_{|\epsilon|\leq
u}\|g_{\epsilon}(\tau_{H})\|_{\infty}$ $\displaystyle\leq
c_{2}\qquad\qquad\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(g_{\epsilon}(\tau_{H})-g_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}\leq
d_{2}\,.$

First consider the case of $f_{\epsilon}(\tau_{H})+g_{\epsilon}(\tau_{H})$. It
easily follows from the triangle inequality that

$\displaystyle\sup_{|\epsilon|\leq
u}\|f_{\epsilon}(\tau_{H})+g_{\epsilon}(\tau_{H})\|_{\infty}\leq c_{1}+c_{2}$
$\displaystyle\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left((f_{\epsilon}(\tau_{H})+g_{\epsilon}(\tau_{H}))-(f_{0}(\tau_{H})+g_{0}(\tau_{H}))\right)\right\|_{2,\mathcal{P}_{0}}\leq
d_{1}+d_{2}\,,$

which clearly establishes that
$f_{\epsilon}(\tau_{H})+g_{\epsilon}(\tau_{H})\in\mathcal{F}_{\textup{bounded}}(u)$.

Now, consider the case of $f_{\epsilon}(\tau_{H})g_{\epsilon}(\tau_{H})$. For
the first required bound, we clearly have

$\sup_{|\epsilon|\leq
u}\|f_{\epsilon}(\tau_{H})g_{\epsilon}(\tau_{H})\|_{\infty}\leq c_{1}c_{2}\,.$

The second required bound requires slightly more work. There, we have

$\displaystyle\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(f_{\epsilon}(\tau_{H})g_{\epsilon}(\tau_{H})-f_{0}(\tau_{H})g_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}$
$\displaystyle\leq\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(f_{\epsilon}(\tau_{H})g_{\epsilon}(\tau_{H})-f_{0}(\tau_{H})g_{\epsilon}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}+\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(f_{0}(\tau_{H})g_{\epsilon}(\tau_{H})-f_{0}(\tau_{H})g_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}$
$\displaystyle\leq c_{2}\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(f_{\epsilon}(\tau_{H})-f_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}+c_{1}\sup_{|\epsilon|\leq
u}\left\|\frac{1}{\epsilon}\left(g_{\epsilon}(\tau_{H})-g_{0}(\tau_{H})\right)\right\|_{2,\mathcal{P}_{0}}$
$\displaystyle\leq c_{2}d_{1}+c_{1}d_{2}\,.$

Therefore, we also have
$f_{\epsilon}(\tau_{H})g_{\epsilon}(\tau_{H})\in\mathcal{F}_{\textup{bounded}}(u)$.
∎

Next, the following lemmas allow us to bound functions in the range of
$(T_{t,\epsilon})^{-1}$ and $(T^{*}_{t,\epsilon})^{-1}$.

######  Lemma 11.

Under the conditions of Theorem 4, there exists some $u>0$ and constants
$C_{1},C_{2}<\infty$ such that for every $t\in[H]$, and functions
$f_{\epsilon}^{*}(Z_{t},A_{t})$ and $g_{\epsilon}^{*}(W_{t},A_{t})$ indexed by
$\epsilon$, we have

$\displaystyle\sup_{|\epsilon|\leq
u}\|(T_{t,\epsilon})^{-1}g_{\epsilon}^{*}(W_{t},A_{t})\|_{\infty}$
$\displaystyle\leq C_{1}\sup_{|\epsilon|\leq
u}\|g_{\epsilon}^{*}(W_{t},A_{t})\|_{\infty}$
$\displaystyle\sup_{|\epsilon|\leq
u}\|(T^{*}_{t,\epsilon})^{-1}f_{\epsilon}^{*}(Z_{t},A_{t})\|_{\infty}$
$\displaystyle\leq C_{2}\sup_{|\epsilon|\leq
u}\|f_{\epsilon}^{*}(Z_{t},A_{t})\|_{\infty}\,.$

###### Proof of Lemma 11.

For the first required bound, we have

$\displaystyle\sup_{|\epsilon|\leq
u}\|(T_{t,\epsilon})^{-1}g_{\epsilon}^{*}(W_{t},A_{t})\|_{\infty}$
$\displaystyle=\sup_{|\epsilon|\leq
u,\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\leq
1}\mathbb{E}_{\epsilon}[f(Z_{t},A_{t})(T_{t,\epsilon})^{-1}g_{\epsilon}^{*}(W_{t},A_{t})]$
$\displaystyle=\sup_{|\epsilon|\leq
u,\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\leq
1}\mathbb{E}_{\epsilon}[g_{\epsilon}^{*}(W_{t},A_{t})(T^{*}_{t,\epsilon})^{-1}f(Z_{t},A_{t})]$
$\displaystyle\leq\sup_{|\epsilon|\leq
u}\|g_{\epsilon}^{*}(W_{t},A_{t})\|_{\infty}\sup_{\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\leq
1}\|(T^{*}_{t,\epsilon})^{-1}f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\,.$

where the first equality follows from the fact that the $1$\- and
$\infty$-norms are dual, the second equality follows from the fact that the
inverse of the adjoint is the adjoint of the inverse, and the inequality
follows from Hölders inequality. Next, we can further bound

$\displaystyle\sup_{\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\leq
1}\|(T^{*}_{t,\epsilon})^{-1}f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}$
$\displaystyle=\sup_{f(Z_{t},A_{t})}\frac{\|(T^{*}_{t,\epsilon})^{-1}f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}}{\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}}$
$\displaystyle=\sup_{g(W_{t},A_{t})}\frac{\|g(W_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}}{\|T^{*}_{t,\epsilon}g(W_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}}$
$\displaystyle=\left(\inf_{\|g(W_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\geq
1}\|T^{*}_{t,\epsilon}g(W_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\right)^{-1}\,.$

Now, we have from Assumption 5 that $\liminf_{\epsilon\to
0}\inf_{\|g(W_{t},A_{t})\|_{q,\mathcal{P}_{\epsilon}}\geq
1}\|T^{*}_{t,\epsilon}g(W_{t},A_{t})\|_{q,\mathcal{P}_{\epsilon}}>0$.
Therefore, the above must be bounded by some $C_{1}$, for sufficiently small
$\epsilon$, which establishes the first required bound.

The second required bound follows from an almost-identical argument, except
that here we instead apply the assumption that $\liminf_{\epsilon\to
0}\inf_{\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}\geq
1}\|T_{t,\epsilon}f(Z_{t},A_{t})\|_{1,\mathcal{P}_{\epsilon}}>0$. ∎

######  Lemma 12.

Under the conditions of Theorem 4, there exists some $u>0$ and constants
$C^{(2)}_{1},C^{(2)}_{2}<\infty$ such that for every $t\in[H]$, and functions
$f_{\epsilon}^{*}(Z_{t},A_{t})$ and $g_{\epsilon}^{*}(W_{t},A_{t})$ indexed by
$\epsilon$, we have

$\displaystyle\sup_{|\epsilon|\leq
u}\|(T_{t,0})^{-1}g_{\epsilon}^{*}(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}$
$\displaystyle\leq C^{(2)}_{1}\sup_{|\epsilon|\leq
u}\|g_{\epsilon}^{*}(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}$
$\displaystyle\sup_{|\epsilon|\leq
u}\|(T^{*}_{t,0})^{-1}f_{\epsilon}^{*}(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}$
$\displaystyle\leq C^{(2)}_{2}\sup_{|\epsilon|\leq
u}\|f_{\epsilon}^{*}(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\,.$

###### Proof of Lemma 12.

The proof of this is very similar to that of Lemma 11, except using
$\mathcal{P}_{0}$ instead of $\mathcal{P}_{\epsilon}$. For the first required
bound, we have

$\displaystyle\sup_{|\epsilon|\leq
u}\|(T_{t,0})^{-1}g_{\epsilon}^{*}(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}$
$\displaystyle=\sup_{|\epsilon|\leq
u,\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\leq
1}\mathbb{E}_{0}[f(Z_{t},A_{t})(T_{t,0})^{-1}g_{\epsilon}^{*}(W_{t},A_{t})]$
$\displaystyle=\sup_{|\epsilon|\leq
u,\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\leq
1}\mathbb{E}_{0}[g_{\epsilon}^{*}(W_{t},A_{t})(T^{*}_{t,0})^{-1}f(Z_{t},A_{t})]$
$\displaystyle\leq\sup_{|\epsilon|\leq
u}\|g_{\epsilon}^{*}(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}\sup_{\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\leq
1}\|(T^{*}_{t,0})^{-1}f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\,.$

where the first equality follows from the fact that the $2$-norm is self-dual,
the second equality follows from the fact that the inverse of the adjoint is
the adjoint of the inverse, and the inequality follows from Cauchy Schwartz.
Next, we can further bound

$\displaystyle\sup_{\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\leq
1}\|(T^{*}_{t,0})^{-1}f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}$
$\displaystyle=\sup_{f(Z_{t},A_{t})}\frac{\|(T^{*}_{t,0})^{-1}f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}}{\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}}$
$\displaystyle=\sup_{g(W_{t},A_{t})}\frac{\|g(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}}{\|T^{*}_{t,0}g(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}}$
$\displaystyle=\left(\inf_{\|g(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}\geq
1}\|T^{*}_{t,0}g(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}\right)^{-1}\,.$

But we know from Assumption 5 that this term is finite, which gives us our
first required bound.

The second required bound follows from an almost-identical argument, except
that here we instead apply the fact that
$\inf_{\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}\geq
1}\|T_{t,0}f(Z_{t},A_{t})\|_{2,\mathcal{P}_{0}}>0$, which also follows from
Assumption 5. ∎

Now, given the previous lemma, as well as the definition of
$\mathcal{F}_{\textup{bounded}}(u)$ and Lemma 10, the following lemmas
establish that $q_{\epsilon}^{(t)}(Z_{t},A_{t})$ and
$h_{\epsilon}^{(t)}(W_{t},A_{t})$ lie within this set for some $u>0$. This
will along with Lemma 9 will allow us to compute the derivative of
$V(\mathcal{P}_{\epsilon})$ in the main proof of Theorem 4.

######  Lemma 13.

Under the conditions of Theorem 4, there exists some $u>0$ such that for every
$t\in[H]$ we have $\sup_{|\epsilon|\leq
u}\|q_{\epsilon}^{(t)}(Z_{t},A_{t})\|_{\infty}<\infty$ and
$\sup_{|\epsilon|\leq u}\|h_{\epsilon}^{(t)}(Z_{t},A_{t})\|_{\infty}<\infty$.

###### Proof of Lemma 13.

First consider the case of $q^{(t)}_{\epsilon}$. First, by Assumption 5 it
must be the case that for some $u>0$ and some constant $C_{3}<\infty$, we have

$\sup_{|\epsilon|\leq u}\|P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})^{-1}\|_{\infty}\leq C_{3}\,,$

simultaneously for every $t\in[H]$. Now, let $u>0$ be such that the above
holds, as well as as Lemma 11, and let $C_{1}$ and $C_{2}$ be defined as in
Lemma 11. Note that clearly for $|\epsilon|\leq u$ we have
$\mathcal{P}_{\epsilon}\in\mathcal{M}_{\textup{PCI}}$, so let us restrict our
attention to such $\epsilon$. Next, note that for any $|\epsilon|\leq u$ we
have

$q^{(t)}_{\epsilon}(Z_{t},A_{t})=T^{-1}_{t,\epsilon}P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})^{-1}\,,$

and so given Lemma 11 we have

$\|q^{(t)}_{\epsilon}(Z_{t},A_{t})\|_{\infty}\leq C_{2}C_{3}\,.$

We note that this bound does not depend on $\epsilon$, so therefore we have
our desired result for $q^{(t)}_{\epsilon}$.

Next, for $h_{\epsilon}^{(t)}$, we note that

$q^{(t)}_{\epsilon}(Z_{t},A_{t})=(T^{*}_{t,\epsilon})^{-1}\mu_{t,\epsilon}(Z_{t},A_{t})\,.$

Therefore, we can proceed with a near-identical argument again using Lemma 11,
as long as we can uniformly bound $\|\mu_{t,\epsilon}(Z_{t},A_{t})\|_{\infty}$
over $|\epsilon|\leq u$ for each $t$. First, note that given the above bound
for $q^{(t)}_{\epsilon}$ and the definition of $\mu_{t,\epsilon}$, for each
$t\in[H]$ we have

$\|\mu_{t,\epsilon}(Z_{t},A_{t})\|_{\infty}\leq(C_{2}C_{3})^{t-1}\|Y_{t,\epsilon}\|_{\infty}\,.$

Therefore it is sufficient to uniformly bound $Y_{t,\epsilon}$ for each $t$.
We will do this by backward induction on $t$. For the base case where $t=H$,
we trivially have $\|Y_{H,\epsilon}\|_{\infty}\leq R_{\textup{max}}$, where
$R_{\textup{max}}$ is a bound on the absolute value of all rewards. Now,
suppose that $\|Y_{t+1,\epsilon}\|_{\infty}\leq C_{4,t+1}$ for some
$C_{4,t+1}$ that doesn’t depend on $\epsilon$. Then we have

$\|Y_{t,\epsilon}\|_{\infty}\leq
R_{\textup{max}}+\gamma(|\mathcal{A}|+(C_{3}C_{2}))\|h_{\epsilon}^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}+\gamma(C_{3}C_{2})\|Y_{t+1,\epsilon}\|_{\infty}\\\
$

Now, by the inductive hypothesis $Y_{t+1,\epsilon}$ is uniformly bounded and
therefore so is $\mu_{t+1,\epsilon}(Z_{t+1},A_{t+1})$, and therefore following
an identical argument as above as for bounding $q_{\epsilon}^{(t)}$ we have
that $\|h_{\epsilon}^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}$ is uniformly
bounded. Specifically, by Lemma 11 we have

$\displaystyle\|\mu_{t+1,\epsilon}(Z_{t+1},A_{t+1})\|_{\infty}$
$\displaystyle\leq(C_{3}C_{2})^{t}C_{4,t+1}$
$\displaystyle\|h_{\epsilon}^{(t+1)}(W_{t+1},A_{t+1})\|_{\infty}$
$\displaystyle\leq C_{1}(C_{3}C_{2})^{t}C_{4,t+1}\,,$

and therefore $Y_{t,\epsilon}$ is uniformly bounded. This completes the
induction, so therefore we conclude that we have a uniform bound on
$\|h_{\epsilon}^{(t)}(W_{t},A_{t})\|_{\infty}$ over $|\epsilon|\leq u$. ∎

######  Lemma 14.

Under the conditions of Theorem 4, there exists $u>0$ such that
$q_{\epsilon}^{(t)}(Z_{t},A_{t})\in\mathcal{F}_{\textup{bounded}}(u)$ and
$h_{\epsilon}^{(t)}(W_{t},A_{t})\in\mathcal{F}_{\textup{bounded}}(u)$ for
every $t\in[H]$.

###### Proof of Lemma 14.

Let $u$, $C_{1}$, $C_{2}$, and $C_{3}$ be defined as in the proof of Lemma 13,
and define

$\displaystyle\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})$
$\displaystyle=\frac{1}{\epsilon}\left(q_{\epsilon}^{(t)}(Z_{t},A_{t})-q_{0}^{(t)}(Z_{t},A_{t})\right)$
$\displaystyle\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})$
$\displaystyle=\frac{1}{\epsilon}\left(h_{\epsilon}^{(t)}(W_{t},A_{t})-h_{0}^{(t)}(W_{t},A_{t})\right)\,.$

Now, given Lemma 13 it is sufficient to prove that
$\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})$ and
$\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})$ are uniformly bounded over
$|\epsilon|\leq u$, in $2$-norm. We will prove this for each
$\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})$ term via forward induction on $t$,
and then for each $\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})$ term via backward
induction on $t$. Furthermore, noticing that
$\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})=(T_{t,0})^{-1}T_{t,0}\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})$
and
$\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})=(T^{*}_{0,\epsilon})^{-1}T^{*}_{0,\epsilon}\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})$,
for each $t\in[H]$, it follows from Lemma 12 that it is sufficient to show

$\sup_{|\epsilon|\leq
u}\left\|T_{t,0}\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})\right\|_{2,\mathcal{P}_{0}}<\infty\quad\text{and}\quad\sup_{|\epsilon|\leq
u}\left\|T^{*}_{t,0}\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})\right\|_{2,\mathcal{P}_{0}}<\infty\,.$

First, we can show that show that

$\displaystyle T_{t,0}\delta^{(q,t)}_{\epsilon}(Z_{t},A_{t})$
$\displaystyle=\frac{1}{\epsilon}\left(T_{t,\epsilon}q^{(t)}_{\epsilon}(Z_{t},A_{t})-T_{t,0}q^{(t)}_{0}(Z_{t},A_{t})\right)-\frac{1}{\epsilon}(T_{t,\epsilon}-T_{t,0})q_{\epsilon}^{(t)}(Z_{t},A_{t})$
$\displaystyle=\frac{1}{\epsilon}\left(P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})^{-1}-P^{*}_{t,0}(A_{t}\mid W_{t})^{-1}\right)$
$\displaystyle\qquad-\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}[\eta_{t,\epsilon}q_{\epsilon}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]-\mathbb{E}_{0}[\eta_{t,0}q_{\epsilon}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]\right)$
$\displaystyle=\frac{1}{\epsilon}\left(P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})^{-1}-P^{*}_{t,0}(A_{t}\mid
W_{t})^{-1}\right)-\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}-\mathbb{E}_{0}\right)[\eta_{t,0}q_{\epsilon}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]$
$\displaystyle\qquad-\mathbb{E}_{\epsilon}\left[\frac{1}{\epsilon}\left(\eta_{t,\epsilon}-\eta_{t,0}\right)q_{\epsilon}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}\right]$ (16)

We will proceed by bounding the three terms in Eq. 16 one by one. for the
first, we have

$\displaystyle\frac{1}{\epsilon}\left(P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})^{-1}-P^{*}_{t,0}(A_{t}\mid W_{t})^{-1}\right)$
$\displaystyle=\left(\frac{P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})^{-1}-P^{*}_{t,0}(A_{t}\mid W_{t})^{-1}}{P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})-P^{*}_{t,0}(A_{t}\mid
W_{t})}\right)\left(\frac{P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})-P^{*}_{t,0}(A_{t}\mid W_{t})}{\epsilon}\right)$
$\displaystyle=-(aP^{*}_{t,\epsilon}(A_{t}\mid
W_{t})+(1-a)P^{*}_{t,0}(A_{t}\mid
W_{t}))^{-2}\left(\frac{P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})-P^{*}_{t,0}(A_{t}\mid W_{t})}{\epsilon}\right)\,,$

where the second equation follows from the mean value theorem, for some
$a\in(0,1)$ that may depend on $t$, $A_{t}$, and $W_{t}$. Now, clearly
$\|(aP^{*}_{t,\epsilon}(A_{t}\mid W_{t})+(1-a)P^{*}_{t,0}(A_{t}\mid
W_{t}))^{-2}\|_{\infty}\leq C_{3}^{2}$. Furthermore, we have

$P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})=\mathbb{E}_{\epsilon}[\eta_{t,\epsilon}\mid
W_{t},A_{t}]P_{\epsilon}(A_{t}\mid W_{t})\,.$

In addition, applying the mean value theorem again we have

$\displaystyle\left\|\frac{1}{\epsilon}\left(P_{\epsilon}(A_{t}\mid
W_{t})-P_{0}(A_{t}\mid W_{t})\right)\right\|_{2,\mathcal{P}_{0}}$
$\displaystyle=\|P_{\epsilon^{\prime}}(A_{t}\mid
W_{t})s_{\epsilon^{\prime}}(A_{t}\mid W_{t})\|_{2,\mathcal{P}_{0}}$
$\displaystyle\leq\|s_{\epsilon^{\prime}}(A_{t},W_{t})\|_{2,\mathcal{P}_{0}}+\|s_{\epsilon^{\prime}}(A_{t})\|_{2,\mathcal{P}_{0}}\,,$

for some $\epsilon^{\prime}\in(0,1)$. Therefore, since by our definition of
score functions in Appendix A score functions have uniformly bounded euclidean
norm, it follows that $P_{\epsilon}(A_{t}\mid
W_{t})\in\mathcal{F}_{\textup{bounded}}(u)$.

Now, in the base case where $t=1$ we have $P^{*}_{t,\epsilon}(A_{t}\mid
W_{t})=P_{\epsilon}(A_{t}\mid W_{t})$, and otherwise in the inductive case
where $t>1$, by the inductive assumption and Lemma 10 it easily follows that
$\mathbb{E}_{\epsilon}[\eta_{t,\epsilon}\mid
W_{t},A_{t}]\in\mathcal{F}_{\textup{bounded}}(u)$, and therefore by Lemma 10
so is $P^{*}_{t,\epsilon}(A_{t}\mid W_{t})$. In either case, this implies the
required bound for the first term of Eq. 16.

For the second term of Eq. 16, by the mean value theorem we have

$\displaystyle\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}-\mathbb{E}_{0}\right)[\eta_{t,0}q_{0}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]$
$\displaystyle=\mathbb{E}_{\epsilon^{\prime}}[s_{\epsilon^{\prime}}(\tau_{t-1},Z_{t}\mid
W_{t},A_{t})\eta_{t,0}q_{0}^{(t)}(Z_{t},A_{t})\mid W_{t},A_{t}]$
$\displaystyle=\mathbb{E}_{\epsilon^{\prime}}[s_{\epsilon^{\prime}}(\tau_{t-1},Z_{t},W_{t},A_{t})\eta_{t,0}q_{0}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]-\mathbb{E}_{\epsilon^{\prime}}[s_{\epsilon^{\prime}}(W_{t},A_{t})\eta_{t,0}q_{0}^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]\,,$

where $\epsilon^{\prime}\in(0,\epsilon)$ and may be measurable _w.r.t._ the
other random variables inside the expectation. Now, by Lemma 13 we have
$\|\eta_{t,0}q_{0}^{(t)}(Z_{t},A_{t})\|_{\infty}<\infty$. Furthermore, by our
definition of score functions in parametric submodels in Appendix A we have
$\sup_{|\epsilon|\leq
u}\|s_{\epsilon}(\tau_{t-1},Z_{t},W_{t},A_{t})\|_{2,\mathcal{P}_{0}}<\infty$
and $\sup_{|\epsilon|\leq
u}\|s_{\epsilon}(W_{t},A_{t})\|_{2,\mathcal{P}_{0}}<\infty$.

Finally, for the third term of Eq. 16, in the base case that $t=1$ we have
$\eta_{t,\epsilon}=\eta_{t,0}=1$, so this term vanishes. Otherwise, in the
inductive case where $t>1$, by the inductive assumption and Lemma 10 we know
that
$\frac{1}{\epsilon}(\eta_{t,\epsilon}-\eta_{0,\epsilon})\in\mathcal{F}_{\textup{bounded}}(u)$.
Therefore, combined with the fact that $q_{0}^{(t)}(Z_{t},A_{t})$ is bounded,
it follows that this third term is uniformly bounded over $|\epsilon|\leq u$.

Therefore, we have completed the forward induction and proved that
$q_{\epsilon}^{(t)}(Z_{t},A_{t})\in\mathcal{F}_{\textup{bounded}}(u)$ for all
$t\in[H]$. Now, we proceed to the backward induction to prove that
$h_{\epsilon}^{(t)}(W_{t},A_{t})\in\mathcal{F}_{\textup{bounded}}(u)$ for all
$t\in[H]$. Proceeding similarly as above, we have

$\displaystyle T^{*}_{t,\epsilon}\delta^{(h,t)}_{\epsilon}(W_{t},A_{t})$
$\displaystyle=\frac{1}{\epsilon}\left(\mathds{1}\\{E_{t}=A_{t}\\}Y_{t,\epsilon}-\mathds{1}\\{E_{t}=A_{t}\\}Y_{t,0}\right)-\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}-\mathbb{E}_{0}\right)[\eta_{t,0}h_{\epsilon}^{(t)}(W_{t},A_{t})\mid
Z_{t},A_{t}]$
$\displaystyle\qquad-\mathbb{E}_{\epsilon}\left[\frac{1}{\epsilon}\left(\eta_{t,\epsilon}-\eta_{t,0}\right)h_{\epsilon}^{(t)}(W_{t},A_{t})\mid
Z_{t},A_{t}\right]$

The second two terms can be bounded in infinity norm uniformly over
$|\epsilon|\leq u$ following an identical argument as for the second two terms
in Eq. 16, so we only need to bound the first term. In the base case, where
$t=H$, we have $Y_{H,\epsilon}=Y_{H,0}=R_{H}$, so this first term simply
disappears. Otherwise, in the inductive case where $t<H$, we note that
$Y_{t,\epsilon}=R_{t}+\gamma\Omega_{t,\epsilon}$, where $\Omega_{t,\epsilon}$
is defined in terms of addition and multiplication of terms of the kind
$R_{t^{\prime}}$, $\mathds{1}\\{E_{t^{\prime}}=A_{t^{\prime}}\\}$,
$q_{\epsilon}^{(t^{\prime})}(Z_{t^{\prime}},A_{t^{\prime}})$, and
$h_{\epsilon}^{(t^{\prime})}(W_{t^{\prime}},A_{t^{\prime}})$, for
$t^{\prime}>t$. Therefore, noting that rewards by assumption are bounded, it
follows from the inductive assumption and Lemma 10 that
$Y_{t,\epsilon}\in\mathcal{F}_{\textup{bounded}}(u)$, and therefore this first
term is bounded.

This completes the backward induction, and establishes that
$h_{\epsilon}^{(t)}(W_{t},A_{t})\in\mathcal{F}_{\textup{bounded}}(u)$ for all
$t\in[H]$, so therefore we can conclude.

∎

###### Proof of Theorem 4.

Following Appendix A, in order to prove this theorem we need to: (1) derive
the tangent space of $\mathcal{M}_{\textup{PCI}}$ at $\mathcal{P}_{b}$; (2)
justify that $\psi_{\text{DR}}$ lies within this tangent space; and (3) show
that $\psi_{\text{DR}}$ is a gradient of $v_{\gamma}(\pi_{e})$. For the first
two parts, we note that by Assumption 5 it easily follows that any parametric
submodel $\mathcal{P}_{\epsilon}$ passing through $\mathcal{P}_{b}$ at
$\epsilon=0$ must lie within $\mathcal{M}_{\textup{PCI}}$ for sufficiently
small $\epsilon$, so therefore the tangent space is simply the set of all
square integrable functions. Given this, $\psi_{\text{DR}}$ clearly lies
within this tangent space. Given this, we only need to justify that it is a
gradient. That is, we need to show that for every parametric submodel

$\left.\frac{\partial
V(\mathcal{P}_{\epsilon})}{\partial\epsilon}\right|_{\epsilon=0}=\mathbb{E}_{\mathcal{P}_{b}}[s(\tau_{H})(\psi_{\text{DR}}(\tau_{H})-v_{\gamma}(\pi_{e}))]\,,$

where $s(\tau_{H})$ is the score function of the parametric submodel. Note
that we have _not_ assumed that the nuiances $q^{(t)}_{\epsilon}$ and
$h^{(t)}_{\epsilon}$ are differentiable, so we must proceed with caution.

First, note that

$\displaystyle\frac{1}{\epsilon}(V(\mathcal{P}_{\epsilon})-V(\mathcal{P}_{b}))$
$\displaystyle=\frac{1}{\epsilon}\mathbb{E}_{\epsilon}\left[\sum_{a\in\mathcal{A}}h^{(1)}_{\epsilon}(W_{1},a)\right]-\frac{1}{\epsilon}\mathbb{E}_{0}\left[\sum_{a\in\mathcal{A}}h^{(1)}_{0}(W_{1},a)\right]$
$\displaystyle=\frac{1}{\epsilon}(\mathbb{E}_{\epsilon}-\mathbb{E}_{0})\left[\sum_{a\in\mathcal{A}}h^{(1)}_{\epsilon}(W_{1},a)\right]+\mathbb{E}_{0}\left[\sum_{a\in\mathcal{A}}\frac{1}{\epsilon}(h^{(1)}_{\epsilon}(W_{1},a)-h^{(1)}_{0}(W_{1},a))\right]\,.$

Now, since
$h_{\epsilon}^{(1)}(W_{1},A_{1})\in\mathcal{F}_{\textup{bounded}}(u)$ for some
$u>0$, it trivially follows that $h_{\epsilon}^{(1)}(w,a)$ converges to
$h_{0}^{(1)}(w,a)$ for every $w,a$. Combined with Lemma 13 and Lemma 9, this
implies that the first term above converges to
$\mathbb{E}_{0}[s(\tau_{H})\sum_{a\in\mathcal{A}}h^{(1)}_{\epsilon}(W_{1},a)]$.
For the second term, we have

$\displaystyle\mathbb{E}_{0}\left[\sum_{a\in\mathcal{A}}\frac{1}{\epsilon}(h^{(1)}_{\epsilon}(W_{1},a)-h^{(1)}_{0}(W_{1},a))\right]$
$\displaystyle=\mathbb{E}_{0}\left[P_{0}(A_{1}\mid
W_{1})^{-1}\frac{1}{\epsilon}(h^{(1)}_{\epsilon}(W_{1},A_{1})-h^{(1)}_{0}(W_{1},A_{1}))\right]$
$\displaystyle=\mathbb{E}_{0}\left[q_{0}^{(1)}(Z_{1},A_{1})\frac{1}{\epsilon}(h^{(1)}_{\epsilon}(W_{1},A_{1})-h^{(1)}_{0}(W_{1},A_{1}))\right]$
$\displaystyle=\frac{1}{\epsilon}(\mathbb{E}_{0}-\mathbb{E}_{\epsilon})\left[q_{0}^{(1)}(Z_{1},A_{1})h^{(1)}_{\epsilon}(W_{1},A_{1})\right]$
$\displaystyle\qquad+\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}\left[q^{(1)}_{0}(Z_{1},A_{1})h^{(1)}_{\epsilon}(W_{1},A_{1})\right]-\mathbb{E}_{0}\left[q^{(1)}_{0}(Z_{1},A_{1})h^{(1)}_{0}(W_{1},A_{1})\right]\right)$
$\displaystyle=\frac{1}{\epsilon}(\mathbb{E}_{0}-\mathbb{E}_{\epsilon})\left[q_{0}^{(1)}(Z_{1},A_{1})h^{(1)}_{\epsilon}(W_{1},A_{1})\right]$
$\displaystyle\qquad+\frac{1}{\epsilon}\left(\mathbb{E}_{\epsilon}\left[q^{(1)}_{0}(Z_{1},A_{1})\mathds{1}\\{E_{1}=A_{1}\\}Y_{1,\epsilon}\right]-\mathbb{E}_{0}\left[q^{(1)}_{0}(Z_{1},A_{1})\mathds{1}\\{E_{1}=A_{1}\\}Y_{1,0}\right]\right)$
$\displaystyle=\frac{1}{\epsilon}(\mathbb{E}_{\epsilon}-\mathbb{E}_{0})\left[q_{0}^{(1)}(Z_{1},A_{1})\left(\mathds{1}\\{E_{1}=A_{1}\\}Y_{1,\epsilon}-h^{(1)}_{\epsilon}(W_{1},A_{1})\right)\right]$
$\displaystyle\qquad+\mathbb{E}_{0}\left[q^{(1)}_{0}(Z_{1},A_{1})\mathds{1}\\{E_{1}=A_{1}\\}\frac{1}{\epsilon}\left(Y_{1,\epsilon}-Y_{1,0}\right)\right]\,.$

Now, again applying Lemmas 9 and 14 the first term above converges to

$\mathbb{E}_{0}[s(\tau_{H})q_{0}^{(1)}(Z_{1},A_{1})(\mathds{1}\\{E_{1}=A_{1}\\}Y_{1,\epsilon}-h^{(1)}_{\epsilon}(W_{1},A_{1}))]\,.$

Combining this with the previous result and the fact that $s(\tau_{H})$ has
mean zero, as well as Lemma 4, we get

$\left.\frac{\partial
V(\mathcal{P}_{\epsilon})}{\partial\epsilon}\right|_{\epsilon=0}=\mathbb{E}_{0}[s(\tau_{H})(\psi_{\text{DR}}(\tau_{H})-v_{\gamma}(\tau_{e}))]+\lim_{\epsilon\to
0}\mathbb{E}^{*}_{2}\left[\frac{1}{\epsilon}\left(Y_{1,\epsilon}-Y_{1,0}\right)\right].$

Therefore, all that remains to show is that the second term above vanishes. We
will argue this by backward induction, by showing that for all $t\leq H$ we
have

$\lim_{\epsilon\to
0}\mathbb{E}^{*}_{t+1}\left[\frac{1}{\epsilon}\left(Y_{t,\epsilon}-Y_{t,0}\right)\right]=0\,.$
(17)

First, for the base case $t=H$, this is trivial, since $Y_{H,\epsilon}=R_{H}$
for all $\epsilon$. Next, suppose that Eq. 17 holds for all $t\geq s$, for
some $s\leq H$. We will argue that it also holds for $t=s-1$. Specifically,
plugging in the definitions of $Y_{s,\epsilon}$ and $Y_{s-1,0}$, we have

$\displaystyle\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(Y_{s-1,\epsilon}-Y_{s-1,0}\right)\right]$
$\displaystyle=\gamma\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\sum_{a\in\mathcal{A}}\left(h^{(s)}_{\epsilon}(W_{s},a)-h^{(s)}_{0}(W_{s},a)\right)\right]+\gamma\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})\Delta_{s,\epsilon}-q^{(s)}_{0}(Z_{s},A_{s})\Delta_{s,0}\right)\right]$
$\displaystyle=\gamma\mathbb{E}^{*}_{s}\left[q_{0}^{(s)}(Z_{s},A_{s})\frac{1}{\epsilon}\left(h^{(s)}_{\epsilon}(W_{s},A_{s})-h^{(s)}_{0}(W_{s},A_{s})\right)\right]+\gamma\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})\Delta_{s,\epsilon}-q^{(s)}_{0}(Z_{s},A_{s})\Delta_{s,0}\right)\right]$
$\displaystyle=\gamma\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})-q^{(s)}_{0}(Z_{s},A_{s})\right)\Delta_{s,\epsilon}\right]+\gamma\mathbb{E}^{*}_{s}\left[q^{(s)}_{0}(Z_{s},A_{s})\mathds{1}\\{E_{s}=A_{s}\\}\frac{1}{\epsilon}(Y_{s,\epsilon}-Y_{s,0})\right]\,,$

where
$\Delta_{s,\epsilon}=\mathds{1}\\{E_{s}=A_{s}\\}Y_{s,\epsilon}-h^{(s)}(W_{s},A_{s})$.
Now, by Lemma 4 the second term is equal to
$\mathbb{E}^{*}_{s+1}[\frac{1}{\epsilon}(Y_{s,\epsilon}-Y_{s,0})]$, which
converges to zero by the inductive hypothesis. Furthermore, since
$\mathbb{E}^{*}_{s}[\Delta_{s,0}\mid Z_{s},A_{s}]=0$, we can derive

$\displaystyle\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})-q^{(s)}_{0}(Z_{s},A_{s})\right)\Delta_{s,\epsilon}\right]$
$\displaystyle=\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})-q^{(s)}_{0}(Z_{s},A_{s})\right)(\Delta_{s,\epsilon}-\Delta_{s,0})\right]$
$\displaystyle=\mathbb{E}_{0}\left[\eta_{t,0}\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})-q^{(s)}_{0}(Z_{s},A_{s})\right)(\Delta_{s,\epsilon}-\Delta_{s,0})\right]$
$\displaystyle\leq\epsilon\|\eta_{t,0}\|_{\infty}\left\|\frac{1}{\epsilon}\left(q^{(s)}_{\epsilon}(Z_{s},A_{s})-q^{(s)}_{0}(Z_{s},A_{s})\right)\right\|_{2,\mathcal{P}_{0}}\left\|\frac{1}{\epsilon}\left(\Delta_{s,\epsilon}-\Delta_{s,0}\right)\right\|_{2,\mathcal{P}_{0}}\,,$

where the inequality follows from Cauchy Schwartz. Also, by Lemma 14 we have
$q_{\epsilon}^{(s)}(Z_{t},A_{t})\in\mathcal{F}_{\textup{bounded}}(u)$ for some
$u>0$, and further by Lemma 10 we have
$\Delta_{s,\epsilon}\in\mathcal{F}_{\textup{bounded}}(u)$. In addition, by
Lemma 13 we have $\|\eta_{t,0}\|_{\infty}<\infty$. Therefore, the first term
also converges to zero. Thus, putting the above together, we have
$\lim_{\epsilon\to
0}\mathbb{E}^{*}_{s}\left[\frac{1}{\epsilon}\left(Y_{s-1,\epsilon}-Y_{s-1,0}\right)\right]=0$,
which proves the inductive case, and therefore our proof is complete.

∎

###  C.6 Proof of Lemma 2

The proof of this lemma follows in a very straightforward way by successively
applying Lemma 4. The details are as follows.

###### Proof of Lemma 2.

We will first deal with the case of $q^{(t)}$. We first note that Eq. 2 is
equivalent to

$\mathbb{E}^{*}_{t}\left[g(W_{t},A_{t})\left(q^{(t)}(Z_{t},A_{t})-P^{*}_{t}(A_{t}\mid
W_{t})^{-1}\right)\right]=0\,,$

for all measurable $g$. Next, following the same argument as in Lemma 6, the
above is equivalent to

$\mathbb{E}^{*}_{t}\left[g(W_{t},A_{t})q^{(t)}(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right]=0\qquad\forall
g\,.$

Next, we can argue by backward induction that for all $s\in[t]$ we have

$\displaystyle\mathbb{E}^{*}_{s}\left[\prod_{s^{\prime}=s}^{t-1}q^{(s^{\prime})}(Z_{s^{\prime}},A_{s^{\prime}})\mathds{1}\\{E_{s^{\prime}}=A_{s^{\prime}}\\}\left(g(W_{t},A_{t})q^{(t)}(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right)\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[g(W_{t},A_{t})q^{(t)}(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right]\,.$

The base case is trivially true, and the inductive case follows by applying
Lemma 4. Therefore, noting that

$\eta_{t}=\prod_{s^{\prime}=0}^{t-1}q^{(s^{\prime})}(Z_{s^{\prime}},A_{s^{\prime}})\mathds{1}\\{E_{s^{\prime}}=A_{s^{\prime}}\\}\,,$

we can put the above together to conclude that Eq. 2 is equivalent to

$\mathbb{E}_{\mathcal{P}_{b}}\left[\eta_{t}\left(g(W_{t},A_{t})q^{(t)}(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right)\right]=0\qquad\forall
g\,.$

Finally, we can deal with the case of $h^{(t)}$ almost identically. We can
first note that Eq. 4 is equivalent to

$\mathbb{E}^{*}_{t}\left[f(Z_{t},A_{t})\left(h^{(t)}(W_{t},A_{t})-\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\right)\right]=0\qquad\forall
f\,,$

and applying an almost identical backwards induction argument this is
equivalent to

$\mathbb{E}_{\mathcal{P}_{b}}\left[\eta_{t}f(Z_{t},A_{t})\left(h^{(t)}(W_{t},A_{t})-\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\right)\right]=0\qquad\forall
f\,,$

which in turn is equivalent to

$\mathbb{E}_{\mathcal{P}_{b}}\left[\eta_{t}\left(h^{(t)}(W_{t},A_{t})-\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\right)\,\Big{|}\,Z_{t},A_{t}\right]=0\,.$

∎

##  Appendix D Derivation of Algorithm 1

Following Bennett and Kallus [2021], the kernel VMM estimators work by solving

$\hat{q}^{(t)}=\operatorname*{arg\,min}_{q\in\mathcal{Q}^{(t)}}J_{n}(q;\alpha^{(q,t)})+\mathcal{R}^{(q,t)}(q)\,,$

where

$\displaystyle J_{n}(q;\alpha^{(q,t)})$
$\displaystyle=\sup_{g}\mathbb{E}_{n}\left[\eta_{t}\left(g(W_{t},A_{t})q(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right)\right]$
$\displaystyle\qquad-\frac{1}{4}\mathbb{E}_{n}\left[\eta_{t}^{2}\left(g(W_{t},A_{t})\tilde{q}^{(t)}(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right)^{2}\right]+\alpha^{(q,t)}\|g\|_{K^{(q,t)}}\,,$

where $\mathbb{E}_{n}$ is the empirical expectation using the $n$ observed
trajectories, and $\|\cdot\|_{K^{(q,t)}}$ is the RKHS norm with kernel
$K^{(q,t)}$. First, by Representer Theorem, we only need to optimize over $g$
of the form

$g=\sum_{j=1}^{N(W_{t};\mathcal{A})}\beta_{j}K^{(q,t)}(\mathbb{S}(W_{t};\mathcal{A})_{j},\cdot)\,.$

Now, plugging this into the above equation for $J_{n}(q;\alpha_{t})$, we
obtain

$J_{n}(q;\alpha_{t})=\sup_{\beta}\beta^{T}\rho(q)-\frac{1}{4}\beta^{T}Q\beta\,,$

where $Q$ and $\rho(q)$ are defined as in function ComputeQ in Algorithm 1.
Given $Q$ is invertible, it is straightforward to verify that the above is
maximized by $\beta=2Q^{-1}\rho(q)$, giving
$J_{n}(q;\alpha_{t})=\rho(q)^{T}Q^{-1}\rho(q)$. Therefore, the kernel VMM
solution is given by

$\hat{q}^{(t)}=\operatorname*{arg\,min}_{q\in\mathcal{Q}^{(t)}}\rho(q)^{T}Q^{-1}\rho(q)+\mathcal{R}^{(q,t)}(q)\,,$

which verifies the correctness of ComputeQ.

Next, for ComputeH, following an almost identical argument as above the kernel
VMM estimator is given by

$\hat{h}^{(t)}=\operatorname*{arg\,min}_{h\in\mathcal{H}^{(t)}}J_{n}(h;\alpha^{(h,t)})+\mathcal{R}^{(h,t)}(h)\,,$

where

$\displaystyle J_{n}(h;\alpha^{(h,t)})$
$\displaystyle=\sup_{f}\mathbb{E}_{n}\left[\eta_{t}f(Z_{t},A_{t})\left(h(W_{t},A_{t})-\mu_{t}\right)\right]$
$\displaystyle\qquad-\frac{1}{4}\mathbb{E}_{n}\left[\eta_{t}^{2}f(Z_{t},A_{t})^{2}\left(h(W_{t},A_{t})-\mu_{t}\right)^{2}\right]+\alpha^{(h,t)}\|f\|_{K^{(h,t)}}\,,$

where $\mu_{t}=\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}$. Again, by the Representer
Theorem, we only need to optimize over $f$ of the form

$f=\sum_{j=1}^{N(Z_{t},A_{t})}\beta_{j}K^{(h,t)}(\mathbb{S}(Z_{t},A_{t})_{j},\cdot)\,,$

and plugging this in to the above gives us

$J_{n}(h;\alpha_{t})=\sup_{\beta}\beta^{T}\rho(h)-\frac{1}{4}\beta^{T}Q\beta\,,$

where $\rho(h)$ and $Q$ are defined as in ComputeH. This is clearly minimized
by $\beta=2Q^{-1}\rho(h)$, and plugging this into the original objective gives
us

$\hat{h}^{(t)}=\operatorname*{arg\,min}_{h\in\mathcal{H}^{(t)}}\rho(h)^{T}Q^{-1}\rho(h)+\mathcal{R}^{(h,t)}(h)\,,$

which verifies the correctness of ComputeH.

Finally, for the main part of the algorithm, we observe that it works by
sequentially estimating each $q^{(t)}$ for increasing $t$ according to
ComputeQ, using an estimate of $\eta_{t}$ given by plugging in our estimates
of $q^{(t^{\prime})}$ for $t^{\prime}<t$, and then sequentially estimating
each $h^{(t)}$ for decreasing $t$ according to ComputeH, using an estimate of
$\eta_{t}$ given by plugging in our estimates of $q^{(t)}$ for $t^{\prime}<t$
and an estimate of $\mu_{t}$ by plugging in our estimates of
$q^{(t^{\prime})}$ and $h^{(t^{\prime})}$ for $t^{\prime}>t$. We note that in
the computation of the estimate of $\mu_{t}$, we use the fact that

$\mu_{t}=\mathds{1}\\{E_{t}=A_{t}\\}\left(R_{t}+\gamma\omega_{t}\right)\,,$

where $\omega_{H}=0$, and for $t<H$ we have

$\omega_{t}=\sum_{a\in\mathcal{A}}h^{(t+1)}(W_{t+1},a)+q^{(t+1)}(Z_{t+1},A_{t+1})\left(\mu_{t+1}-h^{(t+1)}(W_{t+1},A_{t+1})\right)\,.$

##  Appendix E Additional Experiment Details

###  E.1 Selection of Hyperparameters for Sequential Kernel VMM Algorithm

For each setting (given by combination of $\pi_{e}$ and
$\epsilon_{\textup{noise}}$), we experimenting with
$\alpha\in\\{10^{-2},10^{-4},10^{-6},10^{-8}\\}$, and
$\lambda\in\\{1,10^{-2},10^{-4},10^{-6}\\}$. In all cases, we set all values
of $\alpha^{(q,t)}$ and $\alpha^{(h,t)}$ to the same $\alpha$, and similarly
we set all values of $\lambda^{(q,t)}$ and $\lambda^{(h,t)}$ to the same
$\lambda$. In each setting, we performed grid search by experimenting with all
of the above combinations of $\alpha$ and $\lambda$, and hand-selected and
presented results for a combination of $(\alpha,\lambda)$ for which the
algorithm performed well. Our hand-selected $(\alpha,\lambda)$ for each
setting is summarized in Table 2.

We emphasize that this process is _not_ meant to simulate what would be done
in real applications, where the true target policy value is unknown. Rather,
our intention is demonstrate the proof of concept of our theory, and show that
an algorithm such as Algorithm 1 can produce accurate policy value estimates
when the hyperparameters are well-calibrated. We leave the problem of
automatically selecting such hyperparameters in a data-driven way to future
work.

| $\pi_{e}^{\textup{easy}}$ | $\pi_{e}^{\textup{hard}}$ | $\pi_{e}^{\textup{optim}}$
---|---|---|---
$\epsilon_{\textup{noise}}=0$ | $(10^{-4},10^{-4})$ | $(10^{-2},10^{-2})$ | $(10^{-4},10^{-2})$
$\epsilon_{\textup{noise}}=0.2$ | $(10^{-4},10^{-4})$ | $(10^{-2},10^{-4})$ | $(10^{-4},10^{-4})$
Table 2: Summary of hand-chosen hyperparameter combinations for each setting.
Each tuple gives the chosen value for $\alpha$ and $\lambda$ respectively.


# Automatically Generating CS Learning Materials with Large Language Models

Stephen MacNeil  Temple University1801 N Broad StPhiladelphiaPAUSA19122
<EMAIL_ADDRESS>0000-0003-2781-6619 ,  Andrew Tran  Temple
University1801 N Broad StPhiladelphiaPAUSA19122<EMAIL_ADDRESS>,
Juho Leinonen  Aalto UniversityEspooFinland<EMAIL_ADDRESS>0000-0001-6829-9449 ,  Paul Denny  The University of AucklandAucklandNew
Zealand<EMAIL_ADDRESS>0000-0002-5150-9806 ,  Joanne Kim  Temple
University1801 N Broad StPhiladelphiaPAUSA19122<EMAIL_ADDRESS>,  Arto
Hellas  Aalto UniversityEspooFinland<EMAIL_ADDRESS>0000-0001-6502-209X
,  Seth Bernstein  Temple University1801 N Broad StPhiladelphiaPAUSA19122
<EMAIL_ADDRESS>and  Sami Sarsa  Aalto UniversityEspooFinland
<EMAIL_ADDRESS>0000-0002-7277-9282

(2023)

###### Abstract.

Recent breakthroughs in Large Language Models (LLMs), such as GPT-3 and Codex,
now enable software developers to generate code based on a natural language
prompt. Within computer science education, researchers are exploring the
potential for LLMs to generate code explanations and programming assignments
using carefully crafted prompts. These advances may enable students to
interact with code in new ways while helping instructors scale their learning
materials. However, LLMs also introduce new implications for academic
integrity, curriculum design, and software engineering careers. This workshop
will demonstrate the capabilities of LLMs to help attendees evaluate whether
and how LLMs might be integrated into their pedagogy and research. We will
also engage attendees in brainstorming to consider how LLMs will impact our
field.

large language models, explanations, computer science education

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
54th ACM Technical Symposium on Computing Science Education V. 2; March 15–18,
2023; Toronto, ON, Canada††booktitle: Proceedings of the 54th ACM Technical
Symposium on Computing Science Education V. 2 (SIGCSE 2023), March 15–18,
2023, Toronto, ON, Canada††doi: 10.1145/3545947.3569630††isbn:
978-1-4503-9433-8/23/03††ccs: Social and professional topics Computing
education††ccs: Computing methodologies Natural language generation

##  1\. Introduction

Educational technology can have a transformational effect on teaching and
learning in computer science classrooms. Intelligent tutoring systems provide
students with real-time formative feedback on their work to help them get
unstuck (Marwan et al., 2019) when peers and instructors are not available.
Online tutorials and videos have enabled instructors to ‘flip their classes’
and consider new methods for content delivery (Giannakos et al., 2014; Lee and
Ko, 2015), making necessary space for active learning and collaboration during
class time. Anchored collaboration (Kolodner, 1998; Dorn et al., 2015) and
subgoal labeling (Kim et al., 2013; Decker et al., 2020) have created more
engaging online learning spaces where students co-construct their knowledge
and build on each other’s ideas. Clicker quizzes and peer instruction methods
enable instructors to evaluate students’ misconceptions within large classes
in real-time (Crouch and Mazur, 2001). Technology advances and education
technology can not only improve classroom experiences but also create new
models and opportunities for teaching and learning.

Large language Models (LLMs) are similarly poised to impact computer science
classrooms. LLMs are machine learning models that are trained on a large
amount of text data. These models are designed to learn the statistical
properties of language in order to predict the next word in a sequence or
generate new text. LLMs are capable of natural language understanding and text
generation which enables many use cases ranging from creative story writing
(Yuan et al., 2022) to using LLMs to write about themselves (Thunström and
Steingrimsson, 2022). In computer science classroom settings, LLMs have the
potential to provide high-quality code explanations for students at scale
(MacNeil et al., 2022, 2023; Sarsa et al., 2022).

In this workshop, we will demonstrate LLMs’ capabilities to inspire
instructors and researchers to consider how this new technology might
integrate with their existing pedagogy. We also will discuss the potential
impacts that LLMs might have on curricula and students’ careers. Given that
LLMs can generate code based on a natural language prompt, the skills and job
requirements may change for software engineers. Software engineers may take on
more design-oriented roles and serve as software architects while LLMs write
(most of) the source code. This might lead to courses that focus on prompt
engineering, code evaluation, and debugging.

Figure 1. An example code snippet with an explanation generated using GPT-3.
Figure 2. An example code snippet with an analogy-based explanation generated.

###  1.1. Generating Explanations of Code

High-quality code explanations enable students to better understand code and
efficiently learn programming concepts (Marwan et al., 2020). Common automated
methods to explain code snippets and coding concepts include tracing program
execution (Guo, 2013), defining terms (Head et al., 2015), providing hints
(Price et al., 2017), and presenting feedback on errors (Marwan et al., 2020;
Price et al., 2017). These techniques either leverage heuristics which limits
their generalizability or rely on instructors to manually configure and
pregenerate content. However, LLMs have the potential to scale these efforts
and generalize to multiple languages and programming contexts. Our research
team has developed code-explanations with the LLMs Codex (Sarsa et al., 2022)
and GPT-3 (MacNeil et al., 2022, 2023) which resulted in the development of a
design space for LLM-generated code explanations (MacNeil et al., 2022).

###  1.2. Generating Assignments

Students benefit from frequent hands-on practice with programming assignments
(Höök and Eckerdal, 2015). Assignments are most engaging when they are
personalized toward a student’s personal interests (Haungs et al., 2012) and
when they provide sufficient instructions and examples. However, it is time-
consuming to create and maintain high-quality assignments. Previous
researchers have techniques to automatically generate assignments, but they
require instructors to build and maintain templates (Wakatani and Maeda,
2015). To provide high-quality assignments at scale, our team has developed
prompts to generate programming assignments using OpenAI Codex (Sarsa et al.,
2022). Based on these prior experiences, we will share best practices with
attendees.

###  1.3. Generating Code

Large language models have the potential to change the roles and
responsibilities of software developers. For example, GitHub’s Copilot can
generate code for programmers based on natural language prompts (Chen et al.,
2021). The generated code is high enough quality to lead researchers to raise
concerns about cheating (Finnie-Ansley et al., 2022). This ability to generate
high-quality code may affect software engineering jobs. Engineers may be
expected to elicit code requirements, write prompts, and debug the resulting
code. In the workshop, we will explore how LLMs may affect the way we prepare
our students.

##  2\. Workshop Attendees

Our workshop is designed primarily with educators and researchers in mind;
however, we plan to encourage student attendees at SIGCSE to participate in
our workshop and share their perspectives. Our research team consists of
faculty, researchers, and undergraduate students to provide a balanced
perspective and to make the workshop welcoming to attendees at various points
in their careers. We have considered additional methods to make our workshop
an inclusive space. We greet attendees and create space for them to share
their names and the pronouns they use. We will also provide building
information including the nearest gender-neutral bathroom, elevator, and quiet
rooms to reduce barriers to participation.

##  3\. Schedule

The goal of our workshop is to give participants an awareness of the
capabilities of LLMs to support their pedagogy, to get practice using LLMs and
learn best practices in prompt engineering, and to brainstorm with their
colleagues the ways large language models can support their pedagogy.

  * •

Pre-workshop Activities: We will share a tutorial to guide attendees through
creating Github Copilot and OpenAI accounts with sample prompts to try on
their own before the workshop. Free credits are currently available.

  * •

Introductions (20 mins): The team and attendees introduce themselves.
Attendees will engage in a speed dating activity to get to know others one-on-
one.

  * •

Demonstration (10 mins): Our team will demonstrate the capabilities of GPT-3
(supported by materials).

  * •

Guided Activity 1 (20 mins): Participants will work in pairs to solve
programming assignments with Github Copilot.

  * •

Break (10 mins)

  * •

Guided Activity 2 (25 mins): Participants will work in pairs to generate code
explanations using GPT-3.

  * •

Guided Activity 3 (25 mins): Participants will work in pairs to create
programming assignments using Codex.

  * •

Break (10 mins)

  * •

Group brainstorming (25 mins): As a think-pair-share activity, attendees will
work in pairs on a shared Miro board to brainstorm ideas for integrating LLMs
into their courses.

  * •

Exploratory learning (25): attendees will use our resources to further explore
LLMs, explore ways to realize brainstormed ideas, and explore LLMs beyond the
workshop activities, including testing unique prompt ideas.

  * •

Debrief (10 mins): Summarization of the workshop and key insights, initiating
collaborations, etc.

##  4\. Disseminating Workshop Results

Our workshop team will create a website leading up to the workshop which will
host and maintain resources on using LLMs in CS classrooms. After the
workshop, we will update the website with content from the Miro boards and a
joint reflection written by workshop organizers on the challenges and
opportunities identified by attendees. This idea is inspired by existing
websites with advice for CS Teaching (e.g.: https://www.csteachingtips.org/).

##  5\. Organizers

Our team has extensive experience using LLMs to write code (Finnie-Ansley et
al., 2022), generate code explanations (MacNeil et al., 2023, 2022), and
create assignments (Sarsa et al., 2022). Our team includes three faculty
members, two researchers, and three undergraduate students who have all
published research on using LLMs for CS Education. We strongly believe that
this diverse convergence of faculty, researchers, and students will be
essential to ensure that LLMs have the most positive potential impact on
computing education.

## References

  * (1)
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021\.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Crouch and Mazur (2001) Catherine H Crouch and Eric Mazur. 2001.  Peer instruction: Ten years of experience and results.  _American journal of physics_ 69, 9 (2001), 970–977.
  * Decker et al. (2020) Adrienne Decker, Briana B Morrison, and Lauren Margulieux. 2020\.  Using subgoal labeling in teaching introductory programming.  _Journal of Computing Sciences in Colleges_ 35, 8 (2020), 249–251.
  * Dorn et al. (2015) Brian Dorn, Larissa B Schroeder, and Adam Stankiewicz. 2015\.  Piloting TrACE: Exploring spatiotemporal anchored collaboration in asynchronous learning. In _Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing_. 393–403.
  * Finnie-Ansley et al. (2022) James Finnie-Ansley, Paul Denny, Brett A. Becker, Andrew Luxton-Reilly, and James Prather. 2022\.  The Robots Are Coming: Exploring the Implications of OpenAI Codex on Introductory Programming. In _Australasian Computing Education Conference_ (Virtual Event, Australia) _(ACE ’22)_. ACM, New York, NY, USA, 10–19.  https://doi.org/10.1145/3511861.3511863
  * Giannakos et al. (2014) Michail N. Giannakos, John Krogstie, and Nikos Chrisochoides. 2014\.  Reviewing the Flipped Classroom Research: Reflections for Computer Science Education. In _Proceedings of the Computer Science Education Research Conference_ (Berlin, Germany) _(CSERC ’14)_. Association for Computing Machinery, New York, NY, USA, 23–29.  https://doi.org/10.1145/2691352.2691354
  * Guo (2013) Philip J Guo. 2013\.  Online python tutor: embeddable web-based program visualization for cs education. In _Proceeding of the 44th ACM technical symposium on Computer science education_. 579–584.
  * Haungs et al. (2012) Michael Haungs, Christopher Clark, John Clements, and David Janzen. 2012.  Improving first-year success and retention through interest-based CS0 courses. In _Proceedings of the 43rd ACM technical symposium on Computer Science Education_. 589–594.
  * Head et al. (2015) Andrew Head, Codanda Appachu, Marti A Hearst, and Björn Hartmann. 2015.  Tutorons: Generating context-relevant, on-demand explanations and demonstrations of online code. In _2015 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)_. IEEE, 3–12.
  * Höök and Eckerdal (2015) Lars Josef Höök and Anna Eckerdal. 2015.  On the Bimodality in an Introductory Programming Course: An Analysis of Student Performance Factors. In _2015 International Conference on Learning and Teaching in Computing and Engineering_. 79–86.  https://doi.org/10.1109/LaTiCE.2015.25
  * Kim et al. (2013) Juho Kim, Robert C Miller, and Krzysztof Z Gajos. 2013\.  Learnersourcing subgoal labeling to support learning from how-to videos.  In _CHI’13 Extended Abstracts on Human Factors in Computing Systems_. 685–690.
  * Kolodner (1998) L Kolodner. 1998\.  Integrating and guiding collaboration: Lessons learned in computer-supported collaborative learning research at Georgia Tech.  _Proceedings of Computer Support for Collaborative Learning’97 (cscl’97)_ (1998), 91\.
  * Lee and Ko (2015) Michael J. Lee and Amy J. Ko. 2015.  Comparing the Effectiveness of Online Learning Approaches on CS1 Learning Outcomes. In _Proceedings of the Eleventh Annual International Conference on International Computing Education Research_ (Omaha, Nebraska, USA) _(ICER ’15)_. Association for Computing Machinery, New York, NY, USA, 237–246.  https://doi.org/10.1145/2787622.2787709
  * MacNeil et al. (2023) Stephen MacNeil, Andrew Tran, Arto Hellas, Joanne Kim, Sami Sarsa, Paul Denny, Seth Bernstein, and Juho Leinonen. 2023\.  Experiences from Using Code Explanations Generated by Large Language Models in a Web Software Development E-Book. In _Proceedings of the ACM Technical Symposium on Computing Science Education_ (Toronto, Canada). ACM, 6 pages.  https://doi.org/10.1145/3545945.3569785
  * MacNeil et al. (2022) Stephen MacNeil, Andrew Tran, Dan Mogil, Seth Bernstein, Erin Ross, and Ziheng Huang. 2022\.  Generating Diverse Code Explanations Using the GPT-3 Large Language Model. In _Proceedings of the 2022 ACM Conference on International Computing Education Research - Volume 2_ (Lugano and Virtual Event, Switzerland) _(ICER ’22)_. Association for Computing Machinery, New York, NY, USA, 37–39.  https://doi.org/10.1145/3501709.3544280
  * Marwan et al. (2020) Samiha Marwan, Ge Gao, Susan Fisk, Thomas W. Price, and Tiffany Barnes. 2020.  Adaptive Immediate Feedback Can Improve Novice Programming Engagement and Intention to Persist in Computer Science. In _Proceedings of the 2020 ACM Conference on International Computing Education Research_ (Virtual Event, New Zealand) _(ICER ’20)_. Association for Computing Machinery, New York, NY, USA, 194–203.  https://doi.org/10.1145/3372782.3406264
  * Marwan et al. (2019) Samiha Marwan, Nicholas Lytle, Joseph Jay Williams, and Thomas Price. 2019.  The Impact of Adding Textual Explanations to Next-Step Hints in a Novice Programming Environment. In _Proceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education_ (Aberdeen, Scotland Uk) _(ITiCSE ’19)_. Association for Computing Machinery, New York, NY, USA, 520–526.
  * Price et al. (2017) Thomas W Price, Yihuan Dong, and Dragan Lipovac. 2017\.  iSnap: towards intelligent tutoring in novice programming environments. In _Proceedings of the 2017 ACM SIGCSE Technical Symposium on computer science education_. 483–488.
  * Sarsa et al. (2022) Sami Sarsa, Paul Denny, Arto Hellas, and Juho Leinonen. 2022\.  Automatic Generation of Programming Exercises and Code Explanations Using Large Language Models. In _Proceedings of the 2022 ACM Conference on International Computing Education Research - Volume 1_ (Lugano and Virtual Event, Switzerland) _(ICER ’22)_. Association for Computing Machinery, New York, NY, USA, 27–43.  https://doi.org/10.1145/3501385.3543957
  * Thunström and Steingrimsson (2022) Almira Osmanovic Thunström and Steinn Steingrimsson. 2022.  Can GPT-3 write an academic paper on itself, with minimal human input?  (2022).
  * Wakatani and Maeda (2015) Akiyoshi Wakatani and Toshiyuki Maeda. 2015.  Automatic generation of programming exercises for learning programming language. In _2015 IEEE/ACIS 14th International Conference on Computer and Information Science (ICIS)_. 461–465.
  * Yuan et al. (2022) Ann Yuan, Andy Coenen, Emily Reif, and Daphne Ippolito. 2022\.  Wordcraft: Story Writing With Large Language Models. In _27th International Conference on Intelligent User Interfaces_. 841–852.