Denote the visitation counter and transition counters as

$\displaystyle\bar{N}_{t}(\zeta)$
$\displaystyle:=\sum_{t=0}^{t-1}{\mathbbm{1}_{\left\\{(s_{t},a_{t})\in\zeta\right\\}}},\zeta\in\mathcal{P}^{(\ell_{\tilde{\epsilon}})}\mbox{
and}$ $\displaystyle\bar{N}_{t}(\zeta,\xi)$
$\displaystyle:=\sum_{t=0}^{t-1}{\mathbbm{1}_{\left\\{(s_{t},a_{t},s_{t+1})\in\zeta\times\xi\right\\}}},\zeta\in\mathcal{P}^{(\ell_{\tilde{\epsilon}})},\xi\in\mathcal{P}^{\mathcal{S},\ell_{\tilde{\epsilon}}},$

where
$\ell_{\tilde{\epsilon}}=\left\lceil\log{\left(\frac{1}{\tilde{\epsilon}}\right)}\right\rceil$.
Let $\hat{p}^{\tilde{\epsilon}}_{t}$ be the estimate of $p^{\tilde{\epsilon}}$
at time $t$,

$\displaystyle\hat{p}^{\tilde{\epsilon}}_{t}(z,s^{\prime}):=\frac{\bar{N}_{t}\left(q^{-1}(z),q^{-1}(s^{\prime})\right)}{1\vee\bar{N}_{t}\left(q^{-1}(z)\right)},~{}\forall
z\in\mathcal{S}^{\tilde{\epsilon}}\times\mathcal{A}^{\tilde{\epsilon}},\forall
s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}.$ (94)

For $z\in\mathcal{S}^{\tilde{\epsilon}}\times\mathcal{A}^{\tilde{\epsilon}}$,
the confidence radius associated with the estimate
$\hat{p}^{\tilde{\epsilon}}_{t}(z,\cdot)$ is given by

$\displaystyle\eta^{\tilde{\epsilon}}_{t}(z):=\epsilon^{-d_{\mathcal{S}}/2}\sqrt{\frac{c_{1}^{\prime}\log{\left(T\right)}}{\bar{N}_{t}(\zeta)}}+\tilde{\epsilon}\frac{L_{p}}{2},$
(95)

where $q(\zeta)=z$ and $c_{1}^{\prime}$ be a constant such that
$c_{1}^{\prime}\log{\left(T\right)}=8d\cdot(c_{s})^{d_{\mathcal{S}}}\log{\left(\frac{4DT}{\delta\tilde{\epsilon}}\right)}$.
Define $\Theta^{\tilde{\epsilon}}$ and $\bar{\Theta}^{\tilde{\epsilon}}$ as
two discrete transition kernels with support on
$\mathcal{S}^{\tilde{\epsilon}}$. $\Theta^{\tilde{\epsilon}}$ is defined on
the entire state-action space $\mathcal{S}\times\mathcal{A}$, whereas
$\bar{\Theta}^{\tilde{\epsilon}}$ is defined only on
$\mathcal{S}^{\tilde{\epsilon}}\times\mathcal{A}^{\tilde{\epsilon}}$ with
support on $\mathcal{S}^{\tilde{\epsilon}}$, i.e.,

$\displaystyle\Theta^{\tilde{\epsilon}}$
$\displaystyle:=\Big{\\{}\theta\mid\theta(s,a):\mathcal{S}^{\tilde{\epsilon}}\to[0,1],\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{\theta(s,a,s^{\prime})}=1,\theta(s,a,s^{\prime})\geq
0$ $\displaystyle\qquad\mbox{ for every
}(s,a)\in\mathcal{S}\times\mathcal{A}\Big{\\}},$ (96)

and

$\displaystyle\bar{\Theta}^{\tilde{\epsilon}}$
$\displaystyle:=\Big{\\{}\theta\mid\theta(s,a):\mathcal{S}^{\tilde{\epsilon}}\to[0,1],\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{\theta(s,a,s^{\prime})}=1,\theta(s,a,s^{\prime})\geq
0$ $\displaystyle\qquad\mbox{ for every
}(s,a)\in\mathcal{S}^{\tilde{\epsilon}}\times\mathcal{A}^{\tilde{\epsilon}}\Big{\\}}.$
(97)

The confidence ball at time $t$ consists of plausible transition kernels with
discretized support and is defined as follows,

$\displaystyle\mathcal{C}^{\tilde{\epsilon}}_{t}:=\big{\\{}\theta\in\Theta^{\tilde{\epsilon}}:$
$\displaystyle\left\lVert\theta(s^{\prime},a^{\prime},\cdot)-\hat{p}^{\tilde{\epsilon}}_{t}(s,a,\cdot)\right\rVert_{1}\leq\eta^{\tilde{\epsilon}}_{t}\left(s,a\right)\mbox{
for every }(s,a)\in Z_{t},$ $\displaystyle\mbox{ for every
}(s^{\prime},a^{\prime})\in q^{-1}(s,a)\big{\\}},$ (98)

where $\eta^{\tilde{\epsilon}}_{t}$ is as in (95). UCRL-C computes an
optimistic estimate of the value of the true MDP using a value iteration-like
algorithm (100) on the uniformly discretized MDP. The following set of
discretized transition kernels plays an important role in the algorithm.

$\displaystyle\bar{\mathcal{C}}^{\tilde{\epsilon}}_{t}:=\big{\\{}\theta\in\bar{\Theta}^{\tilde{\epsilon}}:$
$\displaystyle\left\lVert\theta(z,\cdot)-\hat{p}^{\tilde{\epsilon}}_{t}(z,\cdot)\right\rVert_{1}\leq\eta^{\tilde{\epsilon}}_{t}\left(z\right)\mbox{
for every
}z\in\mathcal{S}^{\tilde{\epsilon}}\times\mathcal{A}^{\tilde{\epsilon}}\big{\\}},$
(99)

Let us consider the following extended value iterations (EVI).

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern
1.5mu^{\epsilon}_{0}(z)$ $\displaystyle=0,\quad\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu_{0}(s)=0$
$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern
1.5mu^{\epsilon}_{i+1}(z)$
$\displaystyle=r(z)+\max_{\theta\in\bar{\mathcal{C}}^{\tilde{\epsilon}}_{t}}{\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{\theta(z,s^{\prime})\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon}_{i}(s^{\prime})}}+L_{r}\tilde{\epsilon},~{}i\in\mathbb{Z}_{+},$
(100)

where

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon}_{i}(s):=\max_{a\in\mathcal{A}^{\tilde{\epsilon}}}{\mkern
1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{i}(z)},\mbox{ for every
}s\in\mathcal{S}^{\tilde{\epsilon}},i\in\mathbb{Z}_{+}.$

In Proposition C.1 of Appendix D, we show that the optimal decisions of EVI
iterates converge. Let $\bar{\phi}_{k}\in\Phi_{SD}^{\tilde{\epsilon}}$ be the
policy returned by EVI. Then, UCRL-C plays the policy $\phi_{k}$ that
satisfies the following: for every $s\in\mathcal{S}^{\tilde{\epsilon}}$,
$\phi_{k}(s^{\prime})=\bar{\phi}_{k}(s)$ whenever $s^{\prime}\in q^{-1}(s)$.

Fix $\phi\in\Phi_{SD}$. The following iteration, which we call the index
evaluation iteration, will be useful in analyzing the regret of UCRL-C.

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{0}(s)$ $\displaystyle=0,$ $\displaystyle\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i+1}(s)$
$\displaystyle=r(s,\phi(s))+\max_{\theta\in\bar{\mathcal{C}}^{\tilde{\epsilon}}_{\tau_{k}}}{\sum_{s^{\prime}\in
S^{\tilde{\epsilon}}}{\theta(s,\phi(s),s^{\prime}){\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}(s^{\prime})}}}+L_{r}~{}\tilde{\epsilon},~{}i\in\mathbb{Z}_{+},s\in\mathcal{S}^{\tilde{\epsilon}}.$
(101)

Algorithm 5 UCRL-C

Input Horizon, $T$, confidence parameter $\delta$, error tolerance $\epsilon$.

$h=0$, $k=0$

$\tilde{\epsilon}=\epsilon/c_{s}$,
$t^{\star}(\tilde{\epsilon})=\left\lceil\log{\left(\frac{2}{\varrho\tilde{\epsilon}^{d_{\mathcal{S}}}}\right)}/\log{\left(\frac{1}{\alpha}\right)}\right\rceil$.

for $t=0$ to $T-1$ do

if $n_{k}(\zeta)\geq 1\vee N_{\tau_{k}}(\zeta)$ for any
$\zeta\in\mathcal{P}^{(\ell_{\tilde{\epsilon}})}$
$h\geq\frac{24c_{2}t^{\star}(\tilde{\epsilon})}{\tilde{\epsilon}^{2d_{\mathcal{S}}}\rho^{2}}\log{\left(\frac{T}{\delta\tilde{\epsilon}}\right)}$
then

$k\leftarrow k+1$, $h\leftarrow 0$, $\tau_{k}=t$

Compute empirical estimate of discretized transition probability,
$\hat{p}^{\tilde{\epsilon}}_{\tau_{k}}$ as in (94).

Solve EVI (100) and get the policy $\phi_{k}$.

end if

$h\leftarrow h+1$

Play $a_{t}=\phi_{k}(s_{t})$ and receive new state $s_{t+1}$ and reward
$r(s_{t},a_{t})$.

end for

Regret analysis: Next, we present the regret analysis of UCRL-C. Note that
this regret analysis does not follow by using the regret bound of discrete
MDPs [55, 9] and then adding a “discretization error” to account for general
spaces. Such an exercise would be futile since the effect of discretizatin
error would propagate with time due to MDP transitions.

We begin with a concentration inequality for the estimates of the discretized
transition kernel.

######  Lemma G.1.

Define

$\displaystyle\mathcal{G}^{\prime}_{1}:=\cap_{t=0}^{T-1}{\left\\{p^{\tilde{\epsilon}}\in\mathcal{C}^{\tilde{\epsilon}}_{t}\right\\}}.$
(102)

Then, we have $\mathbb{P}\left(\mathcal{G}^{\prime}_{1}\right)\geq
1-\frac{\delta}{2}$.

###### Proof.

The proof follows along similar lines as the proof of Lemma E.2, and
additionally depends on the fact that the diameter of each cell is equal to
$\tilde{\epsilon}$. ∎

Recall that while analyzing ZoRL-$\epsilon$, we used Lemma E.3, which shows
the optimism property of EVI-B, and Lemma E.4 that provides an upper bound on
the optimistic estimate of the values that are obtained by EVI-B. The next two
results derive similar results for UCRL-C.

######  Lemma G.2 (Optimism).

Consider the EVI (100). On the set
$\cap_{t=0}^{T-1}{\left\\{p^{\tilde{\epsilon}}\in\mathcal{C}^{\tilde{\epsilon}}_{t}\right\\}}$,
we have, for all $i\in\mathbb{N}$

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern
1.5mu^{\epsilon}_{i}(s,a)$ $\displaystyle\geq
Q_{i}(s^{\prime},a^{\prime}),~{}\forall(s,a)\in\mathcal{S}^{\tilde{\epsilon}}\times\mathcal{A}^{\tilde{\epsilon}},(s^{\prime},a^{\prime})\in
q^{-1}(s,a),$ (103) $\displaystyle\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\epsilon}_{i}(s)$
$\displaystyle\geq V_{i}(s^{\prime}),~{}\forall
s\in\mathcal{S}^{\tilde{\epsilon}},s^{\prime}\in q^{-1}(s).$ (104)

where $Q_{i}$ and $V_{i}$ are as defined in (41) and (42) respectively.

###### Proof.

Proof of the claim follows similarly to the proof of Lemma E.3. ∎

The next result provides an upper bound on the EVI iterates (100).

######  Lemma G.3.

Consider an episode $k\in\mathbb{Z}_{+}$ and a policy
$\phi\in\Phi^{\tilde{\epsilon}}_{SD}$ such that

$\displaystyle N_{\tau_{k}}(\zeta)\geq
4c_{1}^{\prime}\left(1-\alpha-\epsilon\frac{L_{p}}{c_{s}}\right)^{2}\epsilon^{-d_{\mathcal{S}}}\log{\left(T\right)},$
(105)

for every $\zeta\in\mathcal{P}^{(\ell_{\tilde{\epsilon}})}$. We have, for all
$i\in\mathbb{Z}_{+}$,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}(s)\leq
V^{\phi}_{i}(s^{\prime})+\epsilon^{-d_{\mathcal{S}}/2}C_{1}^{\prime}~{}\mathbb{E}\left[\sum_{j=0}^{i-1}{\frac{1}{\sqrt{\bar{N}_{t}(\zeta_{j})}}}\middle|s_{0}=s^{\prime}\right]+i\cdot\tilde{\epsilon}~{}C_{1}^{\prime\prime},~{}\forall
s\in\mathcal{S}^{\tilde{\epsilon}},s^{\prime}\in q^{-1}(s).$

where $\zeta_{j}$ denote the cell visited in $j$-th step,

$\displaystyle C_{1}^{\prime}$
$\displaystyle:=\frac{1}{1-\alpha}\sqrt{c_{1}^{\prime}\log{\left(T\right)}},$
(106) $\displaystyle C_{1}^{\prime\prime}$
$\displaystyle:=2L_{r}+\frac{L_{p}}{2(1-\alpha)},$ (107)

and $V^{\phi}_{i},\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}$ are as in (43) and (101) respectively.

###### Proof.

We first show that if $\phi$ satisfies (105), then on
$\mathcal{G}^{\prime}_{1}$ for every $i\in\mathbb{Z}_{+}$,
$~{}\textit{sp}\left(\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\phi}_{i}\right)$ is bounded by $\frac{2}{1-\alpha}$. For
$s\in\mathcal{S}^{\tilde{\epsilon}}$,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i+1}(s)$
$\displaystyle=r(s,\phi(s))+\max_{\theta\in\bar{\mathcal{C}}_{\tau_{k}}}{\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{\theta(s,\phi(s),s^{\prime})\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}(s^{\prime})}}+L_{r}~{}\tilde{\epsilon}$
$\displaystyle\leq
r(s,\phi(s))+\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{p^{\tilde{\epsilon}}(s,\phi(s),s^{\prime})\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}(s^{\prime})}+\eta^{\tilde{\epsilon}}_{\tau_{k}}(s,\phi(s))~{}\textit{sp}\left(\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}\right)+L_{r}~{}\tilde{\epsilon}$ $\displaystyle\leq
r(s,\phi(s))+\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{p^{\tilde{\epsilon}}(s,\phi(s),s^{\prime})\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}(s^{\prime})}+\frac{1-\alpha}{2}~{}\textit{sp}\left(\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}\right)+L_{r}~{}\tilde{\epsilon},$

where the first inequality follows from definition of
$\mathcal{G}^{\prime}_{1}$ and Lemma J.6. The second inequality follows from
(105). Now, since (105) holds, we take the difference of $\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi}_{i+1}$ at any two
points, and upon taking a maximum over all pair of points, we get

$\displaystyle~{}\textit{sp}\left(\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi}_{i+1}\right)\leq
1+\left(\frac{1+\alpha}{2}\right)~{}\textit{sp}\left(\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi}_{i}\right).$

A few steps of algebraic manipulation yields that $~{}\textit{sp}\left(\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\phi}_{i}\right)\leq\frac{2}{1-\alpha}$ for all $i\in\mathbb{Z}_{+}$.
Let us prove our claim using induction. The base case $(i=0)$ is seen to hold
trivially. Next, we assume that the following holds for $i^{\prime}\in[i]$,
where $i\in\mathbb{N}$,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i^{\prime}}(s)\leq
V^{\phi}_{i^{\prime}}(s^{\prime})+\epsilon^{-d_{\mathcal{S}}/2}C_{1}^{\prime}~{}\mathbb{E}\left[\sum_{j=0}^{i^{\prime}-1}{\frac{1}{\sqrt{\bar{N}_{t}(\zeta_{j})}}}\middle|s_{0}=s\right]+i^{\prime}\cdot\tilde{\epsilon}~{}C_{1}^{\prime\prime},~{}\forall
s\in\mathcal{S}^{\tilde{\epsilon}},s^{\prime}\in q^{-1}(s).$ (108)

Pick an arbitrary $s\in\mathcal{S}^{\tilde{\epsilon}}$ and $\tilde{s}\in
q^{-1}(s)$, and denote $q^{-1}(s,\phi(s))$ by $\zeta$, then from (101) we
obtain the following,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i+1}(s)$
$\displaystyle=r(s,\phi(s))+\max_{\theta\in\bar{\mathcal{C}}_{\tau_{k}}}{\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{\theta(s,\phi(s),s^{\prime})\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\epsilon,\phi}_{i}(s^{\prime})}}+L_{r}~{}\tilde{\epsilon}$
$\displaystyle=r(\tilde{s},\phi(\tilde{s}))+\sum_{s^{\prime}\in\mathcal{S}^{\tilde{\epsilon}}}{p^{\tilde{\epsilon}}(\tilde{s},\phi(\tilde{s}),s^{\prime})\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\phi}_{i}(s^{\prime})}+2L_{r}\tilde{\epsilon}+\frac{1}{2}\eta_{\tau_{k}}(s,\phi(s))~{}\textit{sp}\left(\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi}_{i}\right)$
$\displaystyle\leq
r(s,\phi(s))+\int_{\mathcal{S}}{ds^{\prime}p(s,\phi(s),s^{\prime})V^{\phi}_{i}(s^{\prime})}+\epsilon^{-d_{\mathcal{S}}/2}C_{1}^{\prime}~{}\mathbb{E}\left[\sum_{j=1}^{i}{\frac{1}{\sqrt{\bar{N}_{t}(\zeta_{j})}}}\middle|s_{0}=s\right]$
$\displaystyle\quad+i\cdot\tilde{\epsilon}~{}C_{1}^{\prime\prime}+\epsilon^{-d_{\mathcal{S}}/2}C_{1}^{\prime}\frac{1}{\sqrt{\bar{N}_{t}(\zeta)}}+\tilde{\epsilon}~{}C_{1}^{\prime\prime}$
$\displaystyle=V^{\phi}_{i+1}(s^{\prime})+\epsilon^{-d_{\mathcal{S}}/2}C_{1}^{\prime}~{}\mathbb{E}\left[\sum_{j=0}^{i}{\frac{1}{\sqrt{\bar{N}_{t}(\zeta_{j})}}}\middle|s_{0}=s\right]+(i+1)\cdot\tilde{\epsilon}~{}C_{1}^{\prime\prime},$

where the first inequality follows using Lipschitz continuity of the reward
function, by definition of event $\mathcal{G}^{\prime}_{1}$ and by Lemma D.5.
The second inequality is obtained by invoking the induction hypothesis (75)
and using the upper bound on $~{}\textit{sp}\left(\bar{V}^{\phi}_{i}\right)$.
This concludes the induction argument, and we have proven the claim. ∎

The next lemma gives a condition for a sub-optimal policy to be not played by
UCRL-C.

######  Lemma G.4.

Let $\gamma\geq\epsilon$. On the set $\mathcal{G}_{1}$, a policy
$\phi\in\bar{\Phi}^{\tilde{\epsilon}}_{SD}$ with $\Delta(\phi)>\gamma$ will
never be played if $\bar{N}_{t}(q^{-1}(s,\phi(s))\geq
4c_{1}^{\prime}\left(1-\alpha-\epsilon\frac{L_{p}}{c_{s}}\right)^{2}\epsilon^{-d_{\mathcal{S}}}\log{\left(T\right)}$,
and

$\displaystyle\sum_{s\in\mathcal{S}^{\tilde{\epsilon}}}{\frac{\mu^{(\infty)}_{\phi,p}(q^{-1}(s))}{\sqrt{\bar{N}_{t}(q^{-1}(s,\phi(s))}}}\leq\frac{\epsilon^{d_{\mathcal{S}}/2}}{C_{1}^{\prime}}\left(\gamma-\epsilon\frac{C_{1}^{\prime\prime}}{c_{s}}\right).$

###### Proof.

The claim follows in a similar way Lemma F.1 follows from Lemma E.3 and Lemma
E.4, through Lemma I.1, Lemma I.2 and Lemma I.3. ∎

From the above Lemma, one can deduce the following sufficient condition for
not playing a $\gamma$-sub-optimal policy: A $\gamma$ sub-optimal policy
$\phi$ will never be played if each cell through which $\phi$ passes has been
visited atleast

$\displaystyle\bar{N}^{\gamma}_{\max}:=\left(\frac{C_{1}^{\prime}c_{s}}{c_{s}-C_{1}^{\prime\prime}}\right)^{2}\epsilon^{-d_{\mathcal{S}}}\gamma^{-2}$
(109)

times. Recall the set $\mathcal{G}_{2,\epsilon}$ from Corollary E.6 on which
number of visits to each cell is bounded below. As the episode duration of
UCRL-C is bounded from below by
$\frac{24c_{2}t^{\star}(\tilde{\epsilon})}{\tilde{\epsilon}^{2d_{\mathcal{S}}}\rho^{2}}\log{\left(\frac{T}{\delta\tilde{\epsilon}}\right)}$,
the results of Lemma E.5, Corollary E.6 and Lemma E.7 hold true for UCRL-C.

Also, recall the set of $[\gamma,2\gamma)$-sub-optimal policies,
$\Phi_{\gamma}$. The next lemma is an equivalent result of Lemma F.3.

######  Lemma G.5.

On the set $\mathcal{G}^{\prime}_{1}\cap\mathcal{G}_{2,\epsilon}$, UCRL-C (5)
plays policies from $\Phi_{\gamma}$ a maximum of

$\displaystyle\left(\frac{4t^{\star}(\tilde{\epsilon})(C_{1}D)^{d_{\mathcal{S}}}}{\varrho\gamma^{d_{\mathcal{S}}}}\bar{N}^{\gamma}_{\max}+\frac{24c_{2}t^{\star}(\tilde{\epsilon})(c_{s}D)^{2d_{\mathcal{S}}}}{\epsilon^{2d_{\mathcal{S}}}\varrho^{2}}\log{\left(\frac{T}{\delta\tilde{\epsilon}}\right)}\right)c_{s}^{d}~{}\mathcal{N}_{\epsilon}\left(\mathcal{Z}^{\bar{\Phi}^{\tilde{\epsilon}}_{SD}}_{\gamma}\right)$
(110)

steps.

###### Proof.

Follows from the proof of Lemma F.3. ∎

Following the same steps that were used while analyzing the regret upper bound
for ZoRL-$\epsilon$, we obtain

$\displaystyle\mathcal{R}_{\gamma}$
$\displaystyle\leq\left(\frac{4t^{\star}(\tilde{\epsilon})(c_{s}D)^{d_{\mathcal{S}}}}{\varrho\gamma^{d_{\mathcal{S}}}}\bar{N}^{\gamma}_{\max}+\frac{24c_{2}t^{\star}(\tilde{\epsilon})(c_{s}D)^{2d_{\mathcal{S}}}}{\epsilon^{2d_{\mathcal{S}}}\varrho^{2}}\log{\left(\frac{T}{\delta\tilde{\epsilon}}\right)}\right)c_{s}^{d}~{}\mathcal{N}_{\epsilon}\left(\mathcal{Z}^{\bar{\Phi}^{\tilde{\epsilon}}_{SD}}_{\gamma}\right)\cdot
2\gamma$
$\displaystyle\leq\tilde{C_{1}}\epsilon^{-(2d_{\mathcal{S}}+d)}\gamma^{-1}+\tilde{C_{2}}\epsilon^{-(2d_{\mathcal{S}}+d)}\gamma,$
(111)

where $\tilde{C_{1}}$ and $\tilde{C_{2}}$ are
$\mathcal{O}(\log{\left(T\right)})$. The next theorem gives an upper bound on
the $\epsilon$-regret of UCRL-C.

######  Theorem G.6.

With probability at least $1-\delta$, the $\epsilon$-regret of UCRL-C (5) is
upper bounded as
$\mathcal{R}_{\epsilon}(T;\textit{UCRL-C})\leq\mathcal{O}(\epsilon^{-(2d_{\mathcal{S}}+d_{\mathcal{A}}+1)}\log{\left(T\right)})$.

###### Proof.

Recall the decomposition of the regret (82).

$\displaystyle\mathcal{R}_{\epsilon}(T;\textit{UCRL-C})$
$\displaystyle=\underbrace{\sum_{k=1}^{K(T)}{H_{k}\Delta(\phi_{k})\mathbbm{1}_{\left\\{\Delta(\phi_{k})>\epsilon\right\\}}}}_{(a)}$
$\displaystyle\quad+\underbrace{\sum_{k=1}^{K(T)}{\mathbbm{1}_{\left\\{\Delta(\phi_{k})>\epsilon\right\\}}\left(H_{k}~{}J(\phi_{k},p)-\sum_{t=\tau_{k}}^{\tau_{k+1}-1}{r(s_{t},\phi_{k}(s_{t}))}\right)}}_{(b)}.$

As we have seen earlier in Section F, the term (a) can be bounded by summing
$\mathcal{R}_{2^{-i}}$ for
$i=1,2,\ldots,\left\lceil\log{\left(\frac{1}{\epsilon}\right)}\right\rceil$.
That is,

$\displaystyle\sum_{k=1}^{K(T)}{H_{k}\Delta(\phi_{k})\mathbbm{1}_{\left\\{\Delta(\phi_{k})>\epsilon\right\\}}}$
$\displaystyle\leq\sum_{\gamma:\gamma=2^{-i}>\epsilon}{\mathcal{R}_{\gamma}}$
$\displaystyle\leq\tilde{C}_{1}\epsilon^{-(2d_{\mathcal{S}}+d+1)}+\tilde{C}_{2}\epsilon^{-(2d_{\mathcal{S}}+d-1)}.$
(112)

Also, by Proposition F.4, the term (b) can be bounded from above by
$\frac{2K(T)}{1-\alpha}$. Due to the rule for starting a new episode in UCRL-C
5 and by [9, Proposition 18], we have that

$\displaystyle K(T)\leq
c_{s}^{d}\epsilon^{-d}\log_{2}{\left(\frac{8T}{c_{s}^{d}\epsilon^{-d}}\right)}.$

Putting all the results together, we get that with probability at least
$1-\delta$,

$\displaystyle\mathcal{R}_{\epsilon}(T;\textit{UCRL-C})\leq\mathcal{O}\left(\epsilon^{-(2d_{\mathcal{S}}+d+1)}\log{\left(T\right)}\right).$

This concludes the proof. ∎

##  Appendix H Non-episodic Regret Analysis of Episodic RL Algorithms

The work [4] designs zooming-based algorithms for episodic RL, in which each
episode lasts for a fixed number of steps, and the state is reset at the
beginning of a new episode. We slightly modify their algorithm by letting the
episode duration be a function of $T$ and denote this algorithm by
$\psi_{\textit{CK}}$, where the subscript is initials of last names of the
authors of [4]. In this section, we will bound the cumulative regret,

$\displaystyle\mathcal{R}(\psi_{\textit{CK}};T):=TJ^{\star}(p)-\sum_{t=0}^{T-1}{r(s_{t},a_{t})}$

when it is deployed on non-episodic RL tasks.

[4] considers an episodic RL framework. Let $H$ be the duration of each
episode, and $K$ be the total number of episodes. $V_{1}^{\star}(s)$ is the
optimal value of the corresponding episodic MDP when the system starts in
state $s$ at the beginning of the episode. Following [4], the regret of a
learning algorithm $\psi$ in episodic setup is defined as follows:

$\displaystyle\mathcal{R}_{e}(\psi;K)=\sum_{k=1}^{K}{\left(V_{1}^{\star}(s_{1}^{k})-\sum_{h=1}^{H}{r(s^{k}_{h},a^{k}_{h})}\right)},$

where $s^{k}_{h}$ and $a^{k}_{h}$ denote the state and the action,
respectively, at timestep $h$ of episode $k$, and sub-script $e$ stands for
episodic. [4] shows that with a high probability, the regret of
$\psi_{\textit{CK}}$ can be bounded as follows,

$\displaystyle\mathcal{R}_{e}(\psi_{\textit{CK}};K)\leq
CH^{\frac{5}{2}+\frac{1}{2d_{z}+4}}K^{\frac{d_{z}+1}{d_{z}+2}},$

where $d_{z}$ is the zooming dimension for episodic RL, as defined by [4], and
$C$ is a term that is polylogarithmic in $K$. We note that the definition of
zooming dimension in [4] differs from our definition. [4] defines $d_{z}$ as
follows. Let

$\displaystyle\mathcal{P}^{Q^{\star}}_{h,\gamma}:=\left\\{(s,a)\in\mathcal{S}\times\mathcal{A}:V^{\star}_{h}(s)-Q^{\star}_{h}(s,a)\leq
2(H+1+L_{V})\gamma\right\\},$ (113)

be the $\gamma$-near-optimal set, where $V^{\star}_{h}$ and $Q^{\star}_{h}$ be
the optimal value function and the optimal action-value function,
respectively, of stage $h$ and $L_{V}$ be the Lipschitz constant for the value
function. Then the zooming dimension is defined as follows:

$\displaystyle
d_{z}:=\inf{\left\\{d^{\prime}>0:\mathcal{N}_{\gamma}(\mathcal{P}^{Q^{\star}}_{h,\gamma})\leq
c_{z}\gamma^{-d^{\prime}}\right\\}}.$

Consider an algorithm that plays a single stationary policy in episodes of
constant duration. To analyze its non-episodic regret, we add to the bound on
its episodic regret, a term associated with regret arising due to “policy
switches” from one episode to another. Under Assumption D.2, we have shown in
Proposition F.4 that the regret component due to changing policies is bounded
above by $\frac{2K}{1-\alpha}$. Hence the non-episodic regret of
$\psi_{\textit{CK}}$ is bounded as,

$\displaystyle\mathcal{R}(\psi_{\textit{CK}};T)$ $\displaystyle\leq
CH^{\frac{5}{2}+\frac{1}{2d_{z}+4}}K^{\frac{d_{z}+1}{d_{z}+2}}+\frac{2K}{1-\alpha}$
$\displaystyle=CH^{\frac{3(d_{z}+3)}{2(d_{z}+2)}}T^{\frac{d_{z}+1}{d_{z}+2}}+\frac{2T}{H(1-\alpha)}.$

Upon letting $H=T^{\frac{2}{5d_{z}+13}}$, we obtain,

$\displaystyle\mathcal{R}(\psi_{\textit{CK}};T)$
$\displaystyle\leq\mathcal{O}\left(T^{\frac{5d_{z}+11}{5d_{z}+13}}\right).$

This bound has a worse dependence upon $d^{e}_{z}$ than our bound, which is
$T^{\frac{2d_{\mathcal{S}}+d_{z}+1}{2d_{\mathcal{S}}+d_{z}+2}}$. Moreover, the
zooming dimension for episodic RL defined by [4] converges to $d$ as
$H\to\infty$. To see this, fix a $h$ so that the number of remaining stages
equals $H-h$. Now, the set $\mathcal{P}^{Q^{\star}}_{h,\gamma}$ corresponding
to a fixed $\gamma>0$ is as in (113). It is evident that for values of $H$
sufficiently large, we have that each $(s,a)$ belongs to the set
$\mathcal{P}^{Q^{\star}}_{h,\gamma}$. This shows that $d^{e}_{z}$ converges to
$d$ as $H\to\infty$. Since $H=T^{\frac{2}{5d_{z}+13}}$, we have,

$\displaystyle\mathcal{R}(\psi_{\textit{CK}};T)$
$\displaystyle\leq\mathcal{O}\left(T^{\frac{5d+11}{5d+13}}\right).$

[5] is another work that studies zooming-based algorithms for episodic RL. A
similar analysis shows that the zooming dimension in [5] also converges to $d$
as $H\to\infty$.

##  Appendix I Some properties of EVI-B

In this section, we show that the EVI-B algorithm 3 does not choose a
$\gamma$-sub-optimal policy to play if its cells have already been visited
earlier sufficiently many times. In order to do that, we first show that the
long-run average of the EVI-B iterates and that of the index evaluation
iterates (34) of the optimistic policy, $\phi_{k}$ are the same. Next, Lemma
I.2 shows that the long-run average of the index evaluation iterates of the
optimistic policy is an upper bound for the optimal average reward,
$J^{\star}(p)$. Lemma I.3 shows that for any policy, the long-run average of
the index evaluation iterates is bounded above by the true average reward of
the policy and the diameter of the policy (114).

######  Lemma I.1.

Consider the EVI-B (3). For every $k\in\mathbb{Z}_{+}$, $s\in\mathcal{S}$,
$\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu_{i}(s)}=\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi_{k}}_{i}(s)}$
where $\phi_{k}$ is the policy played during episode $k$, and $\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi_{k}}_{i}$ is as
defined in (34).

###### Proof.

Recall that the optimal decisions and the maximizer transition kernels of
EVI-B(3) converge. Also, note that there are only a finite number of policies,
and the maximizer transition kernel is from the finite set of corners of the
polygon $\mathcal{C}_{\tau_{k}}$. As a result, there exists
$i_{1}\in\mathbb{N}$ such that for all $i\geq i_{1}$,
$\left(\left\\{\zeta(\xi):\xi\in\mathcal{P}^{\mathcal{S}}_{\tau_{k}}\right\\},\theta_{k}\right)$
maximizes $\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern
1.5mu_{i}(\cdot)$. Similarly, there exists $i_{2}\in\mathbb{N}$ such that for
all $i\geq i_{2}$, $\theta_{k}$ maximizes $\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi_{k}}_{i}(\cdot)$.
Also, noting that $\phi_{k}(s)\in\zeta(\xi)$ for all
$\xi\in\mathcal{P}^{\mathcal{S}}_{\tau_{k}}$, we can write,

$\displaystyle\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu_{i}(s)}=\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi_{k}}_{i}(s)}.$

We have proven the claim. ∎

######  Lemma I.2.

On the set $\mathcal{G}_{1}$ (59), we have that in each episode $k$,
$\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi_{k}}_{i}(s)}\geq
J^{\star}(p)$, for every $s\in\mathcal{S}$.

###### Proof.

We know that $\lim_{i\to\infty}{\frac{1}{i}V_{i}(s)}=J^{\star}(p)$ for every
$s\in\mathcal{S}$. By Lemma E.3, we have that for every $s\in\mathcal{S}$ and
for every $i\in\mathbb{N}$,

$\displaystyle\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu_{i}(s)\geq\frac{1}{i}V_{i}(s)$ $\displaystyle\implies$
$\displaystyle\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu_{i}(s)}\geq\lim_{i\to\infty}{\frac{1}{i}V_{i}(s)}$
$\displaystyle\implies$ $\displaystyle\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu_{i}(s)}\geq
J^{\star}(p).$

The claim then follows from Lemma I.1. ∎

Recall that the diameter of a policy $\phi\in\Phi_{SD}$ is given as follows,

$\displaystyle\mbox{diam}_{k}\left(\phi\right)=\int_{\mathcal{S}}{\mu^{(\infty)}_{p,\phi}(s)~{}\mbox{diam}\left(q_{\tau_{k}}^{-1}(s,\phi(s))\right)ds}.$
(114)

######  Lemma I.3.

Consider a policy $\phi\in\Phi_{SD}$ and an episode $k\in\mathbb{N}$ such that

$\displaystyle\max_{s\in\mathcal{S}}{\mbox{diam}\left(q^{-1}_{\tau_{k}}(s,\phi(s))\right)}\leq\frac{1-\alpha}{3(1+L_{p})}.$
(115)

Then we have,

$\displaystyle\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi}_{i}(s)}$
$\displaystyle\leq
J(\phi,p)+C_{1}~{}\mbox{diam}_{k}\left(\phi\right)~{}\forall s\in\mathcal{S},$

where $C_{1}$ is as defined in (74).

###### Proof.

Clearly,

$\displaystyle\int_{\mathcal{S}}{\mu^{(\infty)}_{p,\phi}(s)~{}\mbox{diam}\left(q_{\tau_{k}}^{-1}(s,\phi(s))\right)~{}ds}=\lim_{i\to\infty}{\frac{1}{i}\mathbb{E}\left[\sum_{j=0}^{i-1}{\mbox{diam}\left(s_{j},\phi(s_{j})\right)}\middle|s_{0}=\tilde{s}\right]},$
(116)

for any $\tilde{s}\in\mathcal{S}$. From Lemma E.4 we have that if policy
$\phi$ satisfies (115), for all $i\in\mathbb{Z}_{+}$,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern
1.5mu^{\phi}_{i}(s)\leq
V^{\phi}_{i}(s)+C_{1}~{}\mathbb{E}\left[\sum_{j=0}^{i-1}{\mbox{diam}\left(s_{j},\phi(s_{j})\right)}\middle|s_{0}=\tilde{s}\right],~{}\forall
s\in\mathcal{S}.$ (117)

Dividing both sides of the above inequality by $i$ and then taking limit
$i\to\infty$, and using (116) we obtain,

$\displaystyle\lim_{i\to\infty}{\frac{1}{i}\mkern
1.5mu\overline{\mkern-1.5muV\mkern-1.5mu}\mkern 1.5mu^{\phi}_{i}(s)}\leq
J(\phi,p)+C_{1}~{}\mbox{diam}_{k}\left(\phi\right).$

This concludes the proof. ∎

##  Appendix J Useful Results

###  J.1 Concentration Inequalities

######  Lemma J.1 (Azuma-Hoeffding inequality).

Let $X_{1},X_{2},\ldots$ be a martingale difference sequence with $|X_{i}|\leq
c\forall i$. Then for all $\epsilon>0$ and $n\in\mathbb{N}$,

$\displaystyle\mathbb{P}\left\\{\sum_{i=1}^{n}{X_{i}}\geq\epsilon\right\\}\leq
e^{-\frac{\epsilon^{2}}{2nc^{2}}}$ (118)

The following inequality is Proposition $A.6.6$ of [49].

######  Lemma J.2 (Bretagnolle-Huber-Carol inequality).

If the random vector $\left(X_{1},X_{2},\ldots,X_{n}\right)$ is multinomially
distributed with parameters $N$ and $\left(p_{1},p_{2},\ldots,p_{n}\right)$,
then for $\epsilon>0$

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}{\left|X_{i}-Np_{i}\right|}\geq
2\sqrt{N}\epsilon\right)\leq 2^{n}e^{-2\epsilon^{2}}.$ (119)

Alternatively, for $\delta>0$

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}{\left|\frac{X_{i}}{N}-p_{i}\right|}<\sqrt{\frac{2n}{N}\log{\left(\frac{2}{\delta^{\frac{1}{n}}}\right)}}\right)\geq
1-\delta.$ (120)

The following is essentially Theorem 1 of [61].

######  Theorem J.3 (Self-Normalized Tail Inequality for Vector-Valued
Martingales).

Let $\\{\mathcal{F}_{t}\\}_{t=0}^{\infty}$ be a filtration. Let
$\\{\eta_{t}\\}_{t=1}^{\infty}$ be a real-valued stochastic process such that
$\eta_{t}$ is $\mathcal{F}_{t}$ measurable and $\eta_{t}$ is conditionally $R$
sub-Gaussian for some $R>0$, i.e.,

$\displaystyle\mathbb{E}\left[\exp(\lambda\eta_{t})|\mathcal{F}_{t-1}\right]\leq\exp\left(\lambda^{2}R^{2}/2\right),\forall\lambda\in\mathbb{R}.$

Let $\\{X_{t}\\}_{t=1}^{\infty}$ be an $\mathbb{R}^{d}$ valued stochastic
process such that $X_{t}$ is $\mathcal{F}_{t-1}$ measurable. Assume that $V$
is a $d\times d$ positive definite matrix. For any $t\geq 0$, define

$\displaystyle\bar{V}_{t}:=V+\sum_{s=1}^{t}X_{s}X^{\top}_{s},$

and

$\displaystyle S_{t}:=\sum_{s=1}^{t}\eta_{s}X_{s}.$

Then, for any $\delta>0$, with a probability at least $1-\delta$, for all
$t\geq 0$,

$\displaystyle\|S_{t}\|^{2}_{\bar{V}^{-1}_{t}}\leq
2R^{2}\log{\left(\frac{\det(\bar{V}_{t})^{1/2}\det(V)^{-1/2}}{\delta}\right)}.$

######  Corollary J.4 (Self-Normalized Tail Inequality for Martingales).

Let $\\{\mathcal{F}_{i}\\}_{i=0}^{\infty}$ be a filtration. Let
$\\{\eta_{i}\\}_{i=1}^{\infty}$ be a $\\{\mathcal{F}_{i}\\}_{i=0}^{\infty}$
measurable stochastic process and $\eta_{t}$ is conditionaly $R$ sub-Gaussian
for some $R>0$. Let $\\{X_{i}\\}_{i=1}^{\infty}$ be a $\\{0,1\\}$-valued
$\mathcal{F}_{i-1}$ measurable stochastic process.

Then, for any $\delta>0$, with a probability at least $1-\delta$, for all
$k\geq 0$,

$\displaystyle\left|\sum_{i=1}^{k}{\eta_{i}X_{i}}\right|\leq
R\sqrt{2\left(1+\sum_{i=1}^{k}{X_{i}}\right)\log{\left(\frac{1+\sum_{i=1}^{k}{X_{i}}}{\delta}\right)}}.$

###### Proof.

Taking $V=1$, we have that $\bar{V}_{t}=1+\sum_{s=1}^{t}{X_{s}}$. The claim
follows from Theorem J.3. ∎

###  J.2 Other Useful Results

######  Lemma J.5.

Consider the following function $f(x)$ such that $0<a_{0}\leq\frac{a_{1}}{4}$,

$\displaystyle f(x)=a_{0}x-\sqrt{a_{1}x}-1.$

Then for all $x\geq 1.5\frac{a_{1}}{a_{0}^{2}}$, $f(x)\geq 0$.

###### Proof.

See that $f(x)\geq 0$ for all
$x\geq\left(\frac{\sqrt{a_{1}}+\sqrt{a_{1}+4a_{0}}}{2a_{0}}\right)^{2}$. Since
$a_{1}\leq 4a_{0}$, we have that for all $x\geq 1.5\frac{a_{1}}{a_{0}^{2}}$
$f(x)\geq 0$. ∎

######  Lemma J.6.

Let $\mu_{1}$ and $\mu_{2}$ be two probability measures on $Z$ and let $v$ be
an $\mathbb{R}$-valued bounded function on $Z$. Then, the following holds.

$\displaystyle\left|\int_{Z}{(\mu_{1}-\mu_{2})(z)v(z)dz}\right|\leq\frac{1}{2}\left\lVert\mu_{1}-\mu_{2}\right\rVert_{TV}~{}\textit{sp}\left(v\right).$

###### Proof.

Denote $\lambda(\cdot):=\mu_{1}(\cdot)-\mu_{2}(\cdot)$. Now let
$Z_{+},Z_{-}\subset Z$ be such that $\lambda(B)\geq 0$ for every $B\subseteq
Z_{+}$ and $\lambda(B)<0$ for every $B\subseteq Z_{-}$. We have that

$\displaystyle\lambda(Z)=\lambda(Z_{+})+\lambda(Z_{-})=0.$ (121)

Also,

$\displaystyle\lambda(Z_{+})-\lambda(Z_{-})=\left\lVert\mu_{1}-\mu_{2}\right\rVert_{TV}.$
(122)

Combining the above two, we get that

$\displaystyle\lambda(Z_{+})=\frac{1}{2}\left\lVert\mu_{1}-\mu_{2}\right\rVert_{TV}.$
(123)

Now,

$\displaystyle\left|\int_{Z}{\lambda(z)v(z)dz}\right|$
$\displaystyle=\left|\int_{Z_{+}}{\lambda(z)v(z)dz}+\int_{Z_{-}}{\lambda(z)v(z)dz}\right|$
$\displaystyle\leq\left|\lambda(Z_{+})\sup_{z\in
Z}{v(z)}+\lambda(Z_{-})\inf_{z\in Z}{v(z)}\right|$
$\displaystyle=\left|\lambda(Z_{+})\sup_{z\in
Z}{v(z)}-\lambda(Z_{+})\inf_{z\in Z}{v(z)}+\lambda(Z_{+})\inf_{z\in
Z}{v(z)}+\lambda(Z_{-})\inf_{z\in Z}{v(z)}\right|$
$\displaystyle=\lambda(Z_{+})\left(\sup_{z\in Z}{v(z)}-\inf_{z\in
Z}{v(z)}\right)$
$\displaystyle=\frac{1}{2}\left\lVert\mu_{1}-\mu_{2}\right\rVert_{TV}~{}\textit{sp}\left(v\right).$

Hence, we have proven the lemma. ∎


††thanks: These authors contributed equally††thanks: These authors contributed
equally

# 9 GHz measurement of squeezed light by interfacing silicon photonics and
integrated electronics

Joel F. Tasker  Quantum Engineering Technology Labs, H. H. Wills Physics
Laboratory and Department of Electrical & Electronic Engineering, University
of Bristol, BS8 1FD, United Kingdom  Jonathan Frazer  Quantum Engineering
Technology Labs, H. H. Wills Physics Laboratory and Department of Electrical &
Electronic Engineering, University of Bristol, BS8 1FD, United Kingdom
Quantum Engineering Centre for Doctoral Training, H. H. Wills Physics
Laboratory and Department of Electrical & Electronic Engineering, University
of Bristol, BS8 1FD, United Kingdom  Giacomo Ferranti  Quantum Engineering
Technology Labs, H. H. Wills Physics Laboratory and Department of Electrical &
Electronic Engineering, University of Bristol, BS8 1FD, United Kingdom  Euan
J. Allen  Quantum Engineering Technology Labs, H. H. Wills Physics Laboratory
and Department of Electrical & Electronic Engineering, University of Bristol,
BS8 1FD, United Kingdom  Léandre F. Brunel  Université Côte d‘Azur, CNRS,
Institut de Physique de Nice (INPHYNI), UMR 7010, Parc Valrose, Nice Cedex 2,
France  Sébastien Tanzilli  Université Côte d‘Azur, CNRS, Institut de Physique
de Nice (INPHYNI), UMR 7010, Parc Valrose, Nice Cedex 2, France  Virginia
D’Auria  Université Côte d‘Azur, CNRS, Institut de Physique de Nice (INPHYNI),
UMR 7010, Parc Valrose, Nice Cedex 2, France  Jonathan C. F. Matthews
<EMAIL_ADDRESS>Quantum Engineering Technology Labs, H. H.
Wills Physics Laboratory and Department of Electrical & Electronic
Engineering, University of Bristol, BS8 1FD, United Kingdom

Photonic quantum technology can be enhanced by monolithic fabrication of both
the underpinning quantum hardware Wang et al. [2019] and the corresponding
electronics for classical readout and control. Together, this enables
miniaturisation and mass-manufacture of small quantum devices—such as quantum
communication nodes Gisin and Thew [2007], quantum sensors Pirandola et al.
[2018] and sources of randomness Herrero-Collantes and Garcia-Escartin
[2017]—and promises the precision and scale of fabrication required to
assemble useful quantum computers et al. [2010a]. Here we combine CMOS
compatible silicon and germanium-on-silicon nano-photonics with silicon-
germanium integrated amplification electronics to improve performance of on-
chip homodyne detection of quantum light. We observe a 3 dB bandwidth of 1.7
GHz, shot-noise limited performance beyond 9 GHz and minaturise the required
footprint to 0.84 $\textrm{mm}^{2}$. We use the device to observe quantum
squeezed light, from 100 MHz to 9 GHz, generated in a lithium niobate
waveguide. This demonstrates that an all-integrated approach yields faster
homodyne detectors for quantum technology than has been achieved to-date and
opens the way to full-stack integration of photonic quantum devices.

Silicon photonics is emerging as a sophisticated chip-platform to develop
quantum technology. It is being used to realise general purpose programmable
networks to process quantum states generated on-chip, with hundreds of
individual components Wang et al. [2019], as well as more specific tasks such
as quantum random number generation et al. [2018a] and chip-to-chip quantum
communications et al. [2019a]. However, silicon quantum photonics is yet to
exploit integration with monolithic complementary metal-oxide-semiconductor
(CMOS) electronics — classical interface hardware for integrated quantum
photonics is still being implemented with large-footprint discrete electronics
that limit device scalability and performance. Fully exploiting CMOS
compatibility is of particular importance for reducing total device footprint
and where high performance classical control and readout resources must scale
with the underpinning quantum hardware.

Homodyne detectors are hardware that are routinely used for sensitive
measurement of light. Applications include coherent Ising machines et al.
[2016a], dual-comb spectroscopy et al. [2016b], quantum-secured communication
et al. [2019a], quantum state and process tomography Lvovsky and Raymer
[2009], quantum computing et al. [2006], random number generation et al.
[2010b], quantum teleportation Furusawa et al. [1998] and ultra-sensitive
interferometry, such as gravitational wave astronomy et al. [2019b]. Homodyne
detectors are also needed for recently proposed optical neural networks
performing below the Landauer limit et al. [2019c]. But the speed performance
of many applications is limited by the use of non-monolithic photonic and
electronic circuits. In particular, detector bandwidth can define the clock-
rate of continuous variables (CV) quantum computers Larsen et al. [2019], et
al. [2019d], the secure-key exchange rate for CV quantum communications et al.
[2019a], and the rate of detection and heralded preparation of pulsed quantum
states Zavatta et al. [2004].

Integrated photodiodes promise to increase homodyne detector bandwidth — tens
of GHz speed performance is already being exploited for classical silicon
photonic interconnects et al. [2017]. However, for shot-noise limited
applications — that includes quantum technology — the integrated approach has
so far been limited to 150 MHz et al. [2018a, 2019a], because the
transimpedance amplifiers (TIA)—needed to amplify the weak photocurrent
subtraction of the two photodiodes with low noise—were implemented with
discrete electronic components. This introduces parasitic capacitance that
increases noise of the circuit and limits the bandwidth of the overall
detector, thus negating the $\sim$10s GHz raw-performance of integrated
photodiodes.

Figure 1: Device schematic and characterisation. A Illustration of the PIC and
MAX3277 TIA. The homodyne signal is recorded with a Keysight N9020B electronic
spectrum analyser (ESA) and Keysight DSOS604A oscilloscope (Osc.). B
Photograph of the homodyne detector device mounted onto a PCB. C Spectral
response of the detector with increasing LO powers from bottom to top in the
range {0 mW, 0.12 mW, 0.85 mW, 1.58 mW, 2.30 mW, 3.00 mW, 3.69 mW, 4.36 mW},
corrected for PIC insertion loss. D spectral response of detector across 10
GHz of spectrum analyser bandwidth. E Raw (dots) and electronic-noise-
subtracted (crosses) signal variance with different CW LO powers integrated
over a bandwidth of 1.7 GHz. The black line represents the noise floor of the
detector. The grey line is fitted over all but the last five data points where
the photodiodes begin to saturate.

Here we show that combining microelectronics with silicon nanophotonics
enables enhanced performance homodyne detectors for measuring non-classical
light whilst miniaturising the detector’s footprint to sub-$\textrm{mm}^{2}$,
all in CMOS-compatible technology for scale. Our homodyne detector is
illustrated in Fig. 1 and implements, in a photonic integrated circuit (PIC)
chip architecture, all the integrated linear optics Masada et al. [2015]
together with on-chip photodiodes et al. [2018a] needed for a standard
homodyne detector. The silicon PIC is designed in-house and fabricated by IMEC
Foundry Services using their ISiPP50G process et al. [2019e]. A local
oscillator (LO)—used to extract phase information from a signal field—is
guided into 450 $\times$ 220nm single mode waveguides via a vertical grating
coupler before input (ii). The signal measured is input into (i). The phase
between signal and LO is controlled with a thermal phase shifter (iii) and the
two fields interfere at a beamsplitter implemented with a variable Mach-
Zehnder interferometer (MZI) comprising two directional couplers (iv) and a
second thermal phase shifter (v) to precisely tune reflectivity. The chip
exhibits crosstalk between the LO and MZI phase shifters of approximately 0.9%
which is mitigated by locking the MZI to 50% reflectivity using a PID feedback
routine (see Supplementary Information section 7 for details). Two waveguide-
integrated germanium photodiodes (vi)—approximately $100~{}\mu$m in length
with foundry target responsivities of 1.1 A/W and 50 $\Omega$ bandwidths of 17
GHz—are coupled to the two outputs of the MZI. The two photodiodes are
connected together in a balanced configuration on the metallisation layer of
the PIC with output ports accessed by bond pads. The PIC is wire bonded
directly to a commercial TIA die: an unpackaged MAX3277 (Maxim Integrated)
with typical transimpedance gain of $3.3$ k$\Omega$ and fabricated in a Si-Ge
bipolar process Maxim Integrated [2005]. The die consists of an initial TIA
stage (vii), followed by a voltage amplifier (viii) and output buffer
amplifier (ix). Direct interfacing is used to access the speed performance of
the integrated photodiodes and the TIA by minimising the parasitic capacitance
and inductance at the input to the amplifier Maxim Integrated [2005]. Both PIC
and TIA die are mounted on a custom-designed printed circuit board (PCB) for
biasing (Fig. 1 B, Supplementary Information section 1 for details).

Figure 2: Measurement of a fibre coupled squeezing source using the integrated
detector. A Experimental setup. A tunable CW pump laser centred at 1560.61 nm
is amplified with an erbium doped fibre amplifier (EDFA) before splitting into
squeezing (i) and local oscillator (ii) paths. The polarisation of the light
in both paths is set (PC) to optimise SHG and squeezed light generation via
SPDC, and PIC input coupling. Both SHG and SPDC are implemented with a lithium
niobate periodically-poled ridge waveguide (NTT Electronics WH-0780-000-F-B-
C-M). Attenuation of the 90% path controls the SHG pump power independent of
the LO. Power is monitored (Thorlabs S121C, S154C. PD in figure) in each arm
with 99:1 fibre splitters. A fibre isolator (FI) acting as a filter prevents
residual 780nm light from reaching the homodyne detector. Noise powers are
collected over 1 s with an ESA in zero-span mode set to 8 MHz resolution
bandwidth. B Estimated squeezing levels across detector bandwidth (see
Supplementary Information section 7 for method of estimation). One data point
has been removed at 4.29 GHz due to environmental RF interference. The drop in
measured squeezing at higher frequencies is expected to be due to the
reduction of shot-noise clearance which adds an effective loss (Supplementary
Information 8). C Measured squeezing and anti-squeezing levels (blue crosses)
with SHG power monitored using a 99:1 beamsplitter between PPLN modules. Eqn
(1) has been fit to find total detection efficiency $\eta_{total}$ and $\mu$
(red line). Error bars are smaller than data points. D Reconstructed Wigner
function of the squeezed vacuum integrated from 0-2 GHz. Solid and dashed
white lines represent $1/e$ points of the squeezed and vacuum states
respectively.

The utility of a homodyne detector for quantum applications can be measured by
its frequency response (including its ability to resolve the shot-noise of a
bright local oscillator field above the dark noise of the detector), common-
mode rejection ratio (CMRR), and overall quantum efficiency. Characterisation
of the detector is performed with no light (vacuum) coupled to input (i). The
frequency response and shot-noise clearance as a function of frequency
determines the time mode of quantum states that may be accurately
characterised by the detector—for our detector, this is shown in Figs. 1 C and
D. A common bandwidth metric is the 3-dB cutoff frequency of the shot-noise,
however measurements can be made beyond this provided there is sufficient
shot-noise clearance. Accounting for frequency dependent losses in the coaxial
radio frequency (RF) connecting cables, we obtain a 3-dB bandwidth of 1.7 GHz
by fitting measured data with a Butterworth response (Supplementary
Information section 2). Fig. 1 D shows that the detector enables shot-noise
limited measurements to beyond 9 GHz.

The CMRR determines how well the photocurrent subtraction suppresses common-
mode signals, such as classical laser amplitude noise. CMRR is set at DC by
the accuracy of the beamsplitter reflectivity and matching of photodiode
responsivities but is degraded at higher frequencies by optical and electronic
path length imbalances Painchaud et al. [2009]. The inherent mode-matching of
integrated optics, as well as the precise path-length matching afforded to
integrated circuits, enables a high CMRR to be achieved through the tuning of
a single thermal phase-shifter. By amplitude modulating the LO and varying the
MZI between balanced and unbalanced configurations, we measure a CMRR of $>52$
dB at 1 GHz (we attribute this limit to the dynamic range of the detector—see
Supplementary Information 3).

Quantum efficiency is determined by losses in the detector’s optics, the
efficiency of the photodiodes, and its shot-noise clearance. We cannot probe
the individual photodiode efficiencies without the presence of coupled
waveguides, so instead measure the combination of optical loss and efficiency
to be $\eta_{det}$ $\sim$88% (Supplementary Information 4). To measure the
shot-noise clearance of our detector and verify that the photocurrent noise
increases in power linearly with the LO power—a signature that the detector is
shot-noise-limited—we plot the variance of the detector output as a function
of input power on a bi-logarithmic scale (Fig. 1 E). In the linear,
unsaturated regime, we obtain a maximum shot-noise clearance of 14 dB and
noise-subtracted gradient of $1.004\pm 0.003$. This gives an efficiency
contribution of 96% and therefore a total quantum efficiency of the detector
of $0.88\times 0.96=84\%$ for measuring states guided in the PIC.

Many quantum optics applications involve measuring squeezed light and states
derived from squeezing by non-Gaussian operations Lvovsky and Raymer [2009].
We apply our device to measure broadband squeezed light generated from a
fibre-coupled periodically-poled lithium niobate (LN) ridge waveguide chip
(Fig. 2 A). The source Kaiser et al. [2016] is composed of an amplified
telecom pump laser, a frequency doubling stage (SHG) and a parametric
downconverter (SPDC) — we launch the generated squeezed vacuum into the second
input of the chip provided for the signal input. Fig. 2 B shows the measured
squeezing across the full detector bandwidth, directly observing an average of
$0.87~{}\pm~{}0.01$ dB of squeezing over the 3-dB bandwidth, diminishing to
electronic noise at 9.2 GHz. To measure the squeezing and anti-squeezing shown
in Fig. 2 C, the local oscillator phase is scanned using the on-chip phase
shifter (Supplementary Information 5) at 5 Hz. This is repeated for a range of
SHG powers (directly monitored between modules). We fit the data with
quadrature variances described by

$\Delta X^{2}_{\frac{\text{MAX}}{\text{MIN}}}=\eta_{total}\exp{(\pm
2r)}+(1-\eta_{total}),$ (1)

with overall setup efficiency $\eta_{total}$ and $r\\!=\\!\mu\sqrt{P_{SHG}}$
Kaiser et al. [2016], for anti-squeezing (MAX) and squeezing (MIN). From this
we obtain $\hat{\eta}_{total}=0.28\pm 0.01$ and $\mu=0.044\pm 0.002$ mW-1/2.

To account for the overall squeezing measurement efficiency, $\eta_{total}$,
we identify all the sources of loss. From Ref. Kaiser et al. [2016] we assume
$\sim 0.83$ transmission through the ridge waveguide and $\sim 0.8$ coupling
between the SPDC module and output fibre, followed by $0.85$ transmission
measured through the fibre isolator, polarisation controller and fibre
couplers. The coupling into the photonic chip is measured to be $-2.1$ dB
($=$0.62) per grating coupler and is monitored throughout the experiment. The
measured photodiode quantum efficiency of $\eta_{det}=88\%$ and shot-noise
contribution of $\sim 96\%$ means the device acts as a fibre-coupled module
with detection efficiency of $0.51$. We estimate the overall detection
efficiency of the squeezing experiment as $\eta_{total}\approx 0.292$, which
is in close agreement to $\hat{\eta}_{total}=0.28\pm 0.01$. After correction
for $\eta_{total}$, we estimate a squeezing value of $3.26\pm 0.15$ dB at the
SPDC module output.

To demonstrate the device’s capability to reconstruct input quantum states
with phase dependence, we perform homodyne tomography, on-chip, of the
detected squeezed vacuum. Using the input thermal phase shifter (iii, Fig. 1),
we scan the relative phase between LO and signal by applying a 100 Hz periodic
voltage—faster than the slow thermal phase fluctuations arising in the fibres
due to the environment—and acquire $2\times 10^{7}$ phase-quadrature pairs
over an integrated bandwidth of 2 GHz (see Supplementary Information 9 for
more information). From these, we obtain a reconstruction of the quantum state
by applying an iterative maximum likelihood estimation algorithm in a five
photon truncated Fock space Lvovsky [2004]. The Wigner function of the
reconstructed density matrix is shown in Fig. 2 D.

We have demonstrated that silicon-photonic homodyne detector performance is
increased by interfacing with a micro-electronics amplifier. The achieved 3 dB
bandwidth of 1.7 GHz is an order of magnitude greater than the previous
fastest integrated silicon-germanium demonstration et al. [2018a], while our
measurements of shot-noise above 9 GHz indicates potential for an order of
magnitude wider bandwidth than the state of the art in standard homodyne
detection Zhang et al. [2018]. For future use as fibre coupled modules, higher
efficiency is possible through improved coupling to optical fibre—Ref. Ding et
al. [2014] exceeds 85% coupling efficiency. Our measurement of squeezed light
from LN waveguide at sideband frequencies up to 9 GHz suggests benefit from
hybrid integration with LN et al. [2018b] and silicon nitride Dutt et al.
[2015] platforms being developed for integrated CV quantum optics, while the
sub-mm2 footprint enables the fabrication of arrays of homodyne detectors for
measuring weak fields in multiple spatial modes. We suggest integration with
germanium-silicon single photon detectors et al. [2019f] could provide all the
detection methods needed on one silicon platform for non-Gaussian quantum
optics Lvovsky and Raymer [2009].

Data availability The data that support the plots within this paper and other
findings of this study are available from the corresponding author upon
reasonable request.

## References

  * Wang et al. [2019] J. Wang, F. Sciarrino, A. Laing, and M. G. Thompson.  Integrated photonic quantum technologies.  _Nature Photonics_ , 2019.  doi: doi.org/10.1038/s41566-019-0532-1.
  * Gisin and Thew [2007] N. Gisin and R. Thew.  Quantum communication.  _Nature Photonics_ , 1:165 – 171, 2007.
  * Pirandola et al. [2018] S. Pirandola, B. R. Bardhan, T. Gehring, C. Weedbrook, and S Lloyd.  Advances in photonic quantum sensing.  _Nature Photonics_ , 12:724 – 733, 2018.
  * Herrero-Collantes and Garcia-Escartin [2017] M. Herrero-Collantes and J. C. Garcia-Escartin.  Quantum random number generators.  _Rev. Mod. Phys._ , 89:015004, 2017.
  * et al. [2010a] T. D. Ladd et al.  Quantum computers.  _Nature_ , 464:45–53, 2010a.
  * et al. [2018a] F. Raffaelli et al.  A homodyne detector integrated onto a photonic chip for measuring quantum states and generating random numbers.  _Quantum Science and Technology_ , 3(2):025003, 2018a.
  * et al. [2019a] G. Zhang et al.  An integrated silicon photonic chip platform for continuous-variable quantum key distribution.  _Nature Photonics_ , 13:839–842, 2019a.
  * et al. [2016a] P. L. McMahon et al.  A fully programmable 100-spin coherent ising machine with all-to-all connections.  _Science_ , 354:614–617, 2016a.
  * et al. [2016b] G. Millot et al.  Frequency-agile dual-comb spectroscopy.  _Nature Photonics_ , 10(1):27, 2016b.
  * Lvovsky and Raymer [2009] A. I. Lvovsky and M. G. Raymer.  Continuous-variable optical quantum-state tomography.  _Rev. Mod. Phys._ , 81:299–332, 2009.
  * et al. [2006] N. C. Menicucci et al.  Universal quantum computation with continuous-variable cluster states.  _Phys. Rev. Lett._ , 97:110501, 2006.
  * et al. [2010b] C. Gabriel et al.  A generator for unique quantum random numbers based on vacuum states.  _Nature Photonics_ , 4(10):711–715, 2010b.
  * Furusawa et al. [1998] A. Furusawa, J. L. Sørensen, S. L. Braunstein, C. A. Fuchs, H. J. Kimble, and E. S. Polzik.  Unconditional quantum teleportation.  _Science_ , 282(5389):706–709, 1998.
  * et al. [2019b] M. Tse et al.  Quantum-enhanced advanced ligo detectors in the era of gravitational-wave astronomy.  _Phys. Rev. Lett._ , 123:231107, 2019b.
  * et al. [2019c] R. Hamerly et al.  Large-scale optical neural networks based on photoelectric multiplication.  _Phys. Rev. X_ , 9:021032, 2019c.
  * Larsen et al. [2019] M. V. Larsen, X. Guo, C. R. Breum, J. S. Neergaard-Nielsen, and U. L. Andersen.  Deterministic generation of a two-dimensional cluster state.  _Science_ , 366:369–372, 2019.
  * et al. [2019d] W. Asavanant et al.  Generation of time-domain-multiplexed two-dimensional cluster state.  _Science_ , 366:373–376, 2019d.
  * Zavatta et al. [2004] A. Zavatta, S. Viciani, and M. Bellini.  Tomographic reconstruction of the single-photon fock state by high-frequency homodyne detection.  _Physical Review A_ , 70(5):053821, 2004.
  * et al. [2017] L. Virot et al.  Integrated waveguide pin photodiodes exploiting lateral si/ge/si heterojunction.  _Opt. Express_ , 25(16):19487–19496, 2017.
  * Masada et al. [2015] G. Masada, K. Miyata, A. Politi, T. Hashimoto, J. L. O’Brien, and A. Furusawa.  Continuous-variable entanglement on a chip.  _Nature Photonics_ , 9:316–319, 2015.
  * et al. [2019e] A. Rahim et al.  Open-access silicon photonics platforms in europe.  _IEEE Journal of Selected Topics in Quantum Electronics_ , 25(5):1–18, 2019e.
  * Maxim Integrated [2005] Maxim Integrated.  Maxim max3277 datasheet.  Technical report, 2005.
  * Painchaud et al. [2009] Y. Painchaud, M. Poulin, M. Morin, and M. Têtu.  Performance of balanced detection in a coherent receiver.  _Opt. Express_ , 17(5):3659–3672, 2009.
  * Kaiser et al. [2016] F. Kaiser, B. Fedrici, A. Zavatta, V. D’Auria, and S. Tanzilli.  A fully guided-wave squeezing experiment for fiber quantum networks.  _Optica_ , 3(4):362–365, 2016.
  * Lvovsky [2004] A. I. Lvovsky.  Iterative maximum-likelihood reconstruction in quantum homodyne tomography.  _Journal of Optics B: Quantum and Semiclassical Optics_ , 6(6):S556, 2004.
  * Zhang et al. [2018] X. Zhang, Y.-C. Zhang, Z. Li, S. Yu, and H. Guo.  1.2-ghz balanced homodyne detector for continuous-variable quantum information technology.  _IEEE Photonics Journal_ , 10(5):1–10, Oct 2018\.
  * Ding et al. [2014] Y. Ding, C. Peucheret, H. Ou, and K. Yvind.  Fully etched apodized grating coupler on the soi platform with- 0.58 db coupling efficiency.  _Optics letters_ , 39(18):5348–5350, 2014.
  * et al. [2018b] F. Lenzini et al.  Integrated photonic platform for quantum information with continuous variables.  _Science Advances_ , 4(12), 2018b.
  * Dutt et al. [2015] A. Dutt, K. Luke, S. Manipatruni, A. L. Gaeta, P. Nussenzveig, and M. Lipson.  On-chip optical squeezing.  _Phys. Rev. Applied_ , 3:044005, 2015.
  * et al. [2019f] P. Vines et al.  High performance planar germanium-on-silicon single-photon avalanche diode detectors.  _Nature Communications_ , 10(1):1086, 2019f.

Acknowledgements The authors are grateful to A Crimp, M Loutit and G Marshall
for technical assistance and D Mahler for helpful discussion. This work was
supported by EPSRC programme grant EP/L024020/1, EPSRC UK Quantum Technology
Hub QUANTIC (EP/M01326X/1), EPSRC Quantum Technology Capital fund: QuPIC
(EP/N015126/1) and the Centre for Nanoscience and Quantum Information (NSQI).
JF acknowledges support from EPSRC Quantum Engineering Centre for Doctoral
Training EP/LO15730/1 and Thales Group. EJA acknowledges support from EPSRC
doctoral prize (EP/R513179/1). ST, VDA, and FB acknowledge financial support
from the European Union by means of the Fond Européen de développement
regional (FEDER) through the project OPTIMAL, the Agence Nationale de la
Recherche (ANR) through the projects HyLight (ANR-17- CE30-0006-01) and SPOCQ
(ANR-14-CE32-0019), and the French government through the program “Investments
for the Future” under the Université Côte d‘Azur UCA-JEDI project
(Quantum@UCA) managed by the ANR (ANR-15-IDEX-01). JCFM acknowledges support
from an EPSRC Quantum Technology Fellowship (EP/M024385/1) and an ERC starting
grant ERC-2018-STG 803665.


# How Teachers Can Use Large Language Models and Bloom’s Taxonomy
to Create Educational Quizzes

Sabina Elkins1,2, Ekaterina Kochmar2, 3, Jackie C.K. Cheung1, 4 Iulian Serban2

###### Abstract

> Question generation (QG) is a natural language processing task with an
> abundance of potential benefits and use cases in the educational domain. In
> order for this potential to be realized, QG systems must be designed and
> validated with pedagogical needs in mind. However, little research has
> assessed or designed QG approaches with the input from real teachers or
> students. This paper applies a large language model-based QG approach where
> questions are generated with learning goals derived from Bloom’s taxonomy.
> The automatically generated questions are used in multiple experiments
> designed to assess how teachers use them in practice. The results
> demonstrate that teachers prefer to write quizzes with automatically
> generated questions, and that such quizzes have no loss in quality compared
> to handwritten versions. Further, several metrics indicate that
> automatically generated questions can even improve the quality of the
> quizzes created, showing the promise for large scale use of QG in the
> classroom setting.

##  1 Introduction

Question generation (QG) is a popular natural language processing (NLP) task.
The goal is to generate natural-language questions that are useful and fluent.
Many approaches also attempt to generate the corresponding answers, or use the
answer to generate the question (Kurdi et al. 2020; Mulla and Gharpure 2023).
Due to their recent success in NLP, recent QG research has been dominated by
the use of Transformer-based large language models (LLMs) (Kurdi et al. 2020;
Liu et al. 2023).

An obvious use case for QG is educational applications. A robust QG system
could, for example, reduce the time spent by teachers to create educational
content such as homework, quizzes, tests, in-class learning activities, and
more. Alternatively, it could serve as a practice tool for students. The range
of potential uses for educational question generation (EQG) is expansive,
especially considering the recent success of LLMs (Kasneci et al. 2023; Kurdi
et al. 2020).

Unfortunately, there is minimal documented real-world deployment of such
systems (Kasneci et al. 2023; Kurdi et al. 2020). Potential reasons for this
lack of adoption may include poor performance of older approaches, rigidity of
the systems, and mistrust of users. Wang et al. (2022a) conduct a need-finding
study with the aim to explore why QG systems are not being used in classrooms.
One of their key findings is that QG systems must meet the needs of the
educators who are using them in order to be effective and adopted. To achieve
this, it is imperative that research in developing educational QG systems
takes into account the opinions of their end users.

⬇

Generate questions in each level of Bloom’s

taxonomy.

Passage: {example_context}

Remembering = {example_question}

Understanding = {example_question}

Applying = {example_question}

Analyzing = {example_question}

Evaluating = {example_question}

Creating = {example_question}

Passage: {context}

Remembering =

((a)) Controlled prompt template. Due to space limits, a one-shot template is
demonstrated here. In actuality, five examples (with different contexts and
questions) are used.

⬇

Candidates generated using a context about

convergent evolution:

⬇

Remembering: What is convergent evolution?

Applying: Can you provide an example of

convergent evolution?

Analyzing: What is the difference between

analogous and homologous structures or traits?

((b)) Controlled prompting strategy generation examples.repo_footnote All 6
levels of Bloom’s taxonomy have generations for each input context, omitted
here to save space.

Figure 1: Controlled prompting strategy.

Given the success of LLMs in other tasks, our hypothesis is that they can
generate different types of questions from a given context that teachers find
useful for creating a quiz with quality comparable to a handwritten version.
Further, we predict that teachers will find the generated candidates more
useful when they are generated to correspond with the levels of Bloom’s
taxonomy (Krathwohl 2002). Figure 1 depicts our few-shot prompting strategy to
generate educational questions corresponding to Bloom’s taxonomy (more details
about this approach can be found in Section 3). In order to evaluate our
predictions, we conducted quiz writing experiments designed to compare and
contrast three different quiz types. Multiple aspects of ‘usefulness’ of a
quiz and quiz writing approach are considered, including the quality of the
resulting quiz, the efficiency (w.r.t. time), and the teacher’s preferences.
Our results show that the three types of quizzes are of similar quality. Some
metrics even demonstrate an improvement in quality when automatically
generated questions are used. We also find that teachers have a strong
preference for writing quizzes with the help of automatically generated
questions corresponding to Bloom’s taxonomy. These results demonstrate the
huge potential of EQG for real-world classrooms and the importance of
considering the needs of teachers when designing an EQG approach.

##  2 Background

Recent research in EQG, and QG more generally, revolves around the use of
Transformer-based LLMs. These LLMs are deep learning models trained on massive
corpora of data to improve their generative performance (Zhang et al. 2022).
The reason for applying this approach in QG research is in large part due to
its significant performance improvements over earlier rule-based and other
types of systems (Kurdi et al. 2020; Steuer et al. 2021; Mulla and Gharpure
2023).

The typical training goal for Transformer-based LLMs is next-token prediction,
meaning that they learn to predict a probable completion to an initial input
text. Recent models have begun to also include reinforcement learning in their
training procedure. This is the case for GPT-3.5, which is the LLM used in the
experiments reported in this paper. Fine-tuning with reinforcement learning
from human feedback allows GPT-3.5 to outperform its predecessors in the GPT
family (Ouyang et al. 2022).

Aligning with the common LLM training objective of the next-token prediction,
the emerging paradigm for QG is to feed a textual input, called a prompt, to
an LLM for the model to complete (Mulla and Gharpure 2023). Designing this
prompt to generate a desired output can be a difficult task, which has
resulted in a new research direction called prompt engineering. One of the
most common approaches to prompt engineering involves prepending a string to
the context given to an LLM for generation, which is called a prefix style
prompt (Liu et al. 2023). For instance, say a machine learning teacher wished
to generate questions about gradient descent. A simple strategy they could
apply is to prompt an LLM with the input:

> Generate a question about gradient descent.

To increase the specificity of the generated questions, the teacher could
provide more context. For example, they might instead write a prompt with a
textbook passage about a specific aspect of gradient descent, such as:

> Generate a question from the following passage: $<$…$>$

To further control generation, the teacher’s input could contain a control
element – a keyword that will guide the generation (Mulla and Gharpure 2023).
For instance, they could prompt an LLM with:

> Generate a multiple-choice question from the following passage: $<$…$>$

In this simple example, we have presented three different prompts, all of
which can produce different questions. Adding in different word choices and
other strategies for controlling the generation quickly makes prompt
engineering a complex problem to optimize.

Another aspect in prompt engineering is the inclusion of examples of the
desired output format and style within the prompt itself. This is often called
few-shot learning. In brief, few-shot learning prompts consist of an
instruction, a few examples, and the task at hand. The examples are used to
adapt LLMs to unseen scenarios without additional training or fine-tuning (Liu
et al. 2023). For instance, following the earlier example, a teacher might
prompt an LLM to generate a true-or-false type of question by including
examples of such questions.

The ability to add more specificity to educational QG has allowed researchers
to generate questions at different levels of difficulty, with different
pedagogical goals in mind, and more. For example, Wang et al. (2022b) try a
collection of different prompting strategies in an effort to optimize
educational QG. They conclude that using shorter input contexts and few-shot
learning results in higher quality candidate questions. Recently, Elkins et
al. (2023) have demonstrated how to generate questions at different levels of
question taxonomies, which are organizational structures taken from
pedagogical literature, such as Bloom’s taxonomy of learning goals. The
authors demonstrate successful generation of questions at various complexity
levels and with different learning goals.

Despite these exciting recent research developments with educational QG, there
are only a few documented cases of these techniques being used in real-world
classrooms (Kasneci et al. 2023; Kurdi et al. 2020). As previously mentioned,
Wang et al. (2022a) find that the lack of alignment between research goals and
what teachers actually need and want from EQG is the reason that such systems
are not deployed in real-world classrooms. Prior work aiming to explore the
needs, opinions, and attitude of teachers and students towards using
automatically generated content is few and far between. Nevertheless, there
exist a few relevant precedent papers:

  * •

The work by Van Campenhout, Hubertz, and Johnson (2022) outlines a NLP system
for translating textbooks into interactive courseware. The authors conduct a
large user study which shows equal student performance on machine-generated
and human-written questions. However, their QG system is mostly rule-based,
and their generated questions are relatively simple (i.e., concept-matching
and fill-in-the-blank).

  * •

The aforementioned work by Elkins et al. (2023) evaluated their generated
candidate questions with real teachers in an effort to more accurately assess
their pedagogical usefulness. They find that their generated questions are
highly rated by teachers. However, this work only evaluates questions at the
individual question-level rather than at a quiz-level.

  * •

The work by Laban et al. (2022) moves beyond question-level evaluations to a
quiz writing task, similar to our work in this paper. The authors design a
task where teachers make a quiz exclusively with candidate questions that were
automatically generated. The teachers also marked the candidates as acceptable
or not as they went; however, the final global acceptance rate was only
$52\%$. Thus, while the authors take important steps towards the evaluation of
QG in a realistic scenario, their generations themselves appear to leave room
for improvement.

##  3 Methods

The EQG in this work was conducted by prompting GPT-3.5 to generate questions
from a given input passage. Two different strategies are used in order to
compare the pedagogically designed generation approach to a more simplistic
approach to QG. The strategies are referred to as controlled and simple,
respectively. Individually, both types of candidate generations are supplied
to teachers in controlled experiments to assess their usefulness in practice
(the details of these experiments are explained in Section 4). The following
subsections will cover details of the input contexts, and the two prefix style
prompting strategies used.

###  3.1 Contexts

Candidate educational questions were generated from a set of $24$ passages
sourced from Wikipedia, with each passage containing $5$ context paragraphs,
$6$ to $9$ sentences in length. The total number of input contexts used to
generate questions is, thus, $120$. The length of these contexts was
determined by empirical results in preliminary work. This set of passages was
manually gathered. The specific Wikipedia articles were generally chosen via
hyperlinks from the domain’s main Wikipedia or glossary page in order to
ensure they were relevant to the foundations of the given domain. Two domains
were used: biology (BIO) and machine learning (ML). More than one domain is
included in order to take steps towards demonstrating domain-agnostic results.
Each domain has $12$ passages, totaling $60$ input contexts. The contexts
underwent minor pre-processing before use: this included removal of citations,
hyperlinks, footnotes and phonetic spellings, re-formatting of full sentence
bullet-point lists into paragraphs, and other minor data cleaning steps.111
The input contexts, more details about Bloom’s taxonomy, the human authored
few-shot examples, all of the generated candidates and quizzes, the annotator
demographics, and more can be found at
https://anonymous.4open.science/r/EQG˙in˙practice-2752/README.md.

###  3.2 Simple Prompting Strategy

The simple prompting strategy uses a generic strategy to generate questions
with GPT-3.5222The model text-davinci-003 was accessed through the OpenAI API.
The dates on which the model was queried are available in the supplementary
material. in an attempt to assess how well the model can generate
pedagogically useful questions without any additional prompt engineering. The
prompt template can be seen in Figure 2. The number of questions generated at
once is six in order to produce the same amount of questions as the controlled
strategy described below. Empirical results from preliminary experimentation
showed that generating all of the questions together produced more diverse
outputs, whereas generating them separately produced duplicate questions.

⬇

Generate 6 questions.

Passage: {context}

Questions:

((a)) Simple prompt template.

⬇

Candidates generated using a context about

convergent evolution:

⬇

What is the definition of convergent evolution?

What are some common functions found in bird,

bat, and pterosaur wings?

((b)) Simple prompting strategy generation examples.repo_footnote There are
actually 6 generations, omitted here to save space.

Figure 2: Simple prompting strategy.

###  3.3 Controlled Prompting Strategy

The controlled prompting strategy uses a pedagogical question taxonomy to
generate questions with different learning goals in mind. Bloom’s taxonomy is
a popular framework for categorizing learning objectives in educational
materials (Krathwohl 2002). The taxonomy contains six levels of learning,
arranged in a hierarchical order from ‘lower’- to ‘higher’-level thinking
skills: remembering, understanding, applying, analyzing, evaluating, and
creating.repo_footnote Bloom’s taxonomy helps teachers design instructional
content that targets specific learning goals.

The generation strategy used in this paper is designed to reduce the overlap
between generated candidates. Rather than generating one question and
taxonomic level at a time, all six questions for a given context are generated
at once, as shown in Figure 1. In preliminary experimentation, this approach
empirically showed a reduction in the generation of identical questions and a
greater diversity and adherence to the taxonomic levels.

The controlled prompting strategy also uses few-shot learning. Following
success with preliminary experimentation, five-shot learning (i.e., five
examples within the prompt) is used. As seen in Figure 1, a single example
contains a prompt and six questions, one for each level of Bloom’s taxonomy.
The examples were handcrafted by a domain expert, and reviewed by another
expert for both question quality and adherence to the intended taxonomic
level. Each domain had five sets of contexts and examples, totaling $10$
contexts and $60$ questions.repo_footnote

##  4 Evaluation

In order to assess the applicability of our two varieties of automatically
generated questions to a real-world academic setting, we must actually ask
real teachers to use them. Therefore, we designed an experiment to replicate a
teacher’s creation of a reading quiz. We wanted to compare the resulting
quizzes’ quality when teachers are writing quizzes from scratch and when they
have access to automatically generated questions while writing the quiz.
Section 4.1 introduces the measures of quiz quality considered in this paper.
Then, Section 4.2 explains the quiz writing experiments conducted by real
teachers.

###  4.1 Quiz Quality

To be able to compare the quality of questions and quizzes written with the
aid of GPT-3.5 to handwritten ones, we must first establish how to measure the
quality of a quiz in the first place. However, the quality of a quiz is often
a subjective metric. Teachers have differing opinions on what makes a good
quiz based on their individual teaching styles. We defined a set of metrics to
measure individual aspects of a quiz that capture different aspects of its
quality, with only usefulness designed to purely reflect the annotator’s
opinion.

Based on previous research, we identified the following four quiz-level
metrics to include.333The ordinal metrics also have definitions for each
category available in the supplementary material. A good reading quiz will be
relevant to the teaching material. It will be natural and coherent, meaning
that it will not confuse a student taking it. Above all, a good quiz will be
approved by a teacher for classroom use. The following metrics attempt to
assess each of these aspects:

  * •

Coverage is a numerical metric in $[0,1]$ which measures how much of the input
passage is reflected in the final quiz. To measure this, we mapped each
question to the sentences in the passage that contained pertinent information
to the answer. For consistency, all questions are mapped to any possible
answer in the text (i.e., both instances of repeated information are selected,
open-ended questions select more of the text, etc.). A coverage ratio is then
calculated from the length of the mapped text and the whole passage’s length.
This metric is inspired by the pyramid method for annotating summaries, which
uses a similar strategy (Nenkova and Passonneau 2004).

  * •

Structure is an ordinal metric from $1$ to $3$ which measures whether the set
of questions make sense together. In other words, if they are intuitively
linked together with a natural/understandable flow (e.g., from easy to
difficult, or from start to finish of the context). Previously, a similar
metric has been used for conversational QG where questions must be logically
linked in order for a conversation to be natural (Mulla and Gharpure 2023).

  * •

Redundancy is an ordinal metric from $1$ to $3$ which measures if there is
redundancy/repetition within the quiz, for example if there are two questions
that ask for the same answer without any different perspective or thought
process required from the student. Previously, a similar metric has been used
for conversational QG where questions must not be repetitive in order for a
conversation to be natural (Mulla and Gharpure 2023).

  * •

Usefulness is an ordinal metric from $1$ to $4$ which measures if a teacher
would use the quiz in an assessment they create for their own class. Note that
the quiz does not necessarily need to be entirely answerable from the context
in order to be considered useful. Previously, similar ordinal metrics have
been used in Elkins et al. (2023), and on different scales in Steuer et al.
(2021) and Mulla and Gharpure (2023).

Beyond the quality of the whole quiz, it is important to ensure that the
individual questions are also of high quality. Thus we also outlined three
question-level metrics, meaning they are evaluated for each question in a
quiz. This is not an exhaustive evaluation, but the following covers basic
aspects of a question’s quality:

  * •

Relevancy is a binary metric which measures whether the question is
semantically relevant to the input context. Previously, similar binary
approaches have been used in Steuer et al. (2021) and Elkins et al. (2023),
and on different scales by Mulla and Gharpure (2023).

  * •

Fluency is a binary metric which measures whether the set of questions are
grammatically correct and use clear language. Similarly to the previous
metric, previous approaches by Mazidi and Nielsen (2014) and Elkins et al.
(2023) have applied this binary metric, and it has been used more generally on
different scales in Mulla and Gharpure (2023).

  * •

Answerability is a binary metric which measures whether the question can be
answered from the input context. It is not necessary to be able to find a
passage from the input that is an answer to the question; it is enough if a
student could reasonably answer the question from the context (for example,
applying logic explained in the passage to a new situation makes the question
‘answerable’). As above, previous work by Steuer et al. (2021) and Elkins et
al. (2023) uses a similar binary metric, and Mulla and Gharpure (2023)
suggests similar metrics on different scales.

###  4.2 Quiz Writing Experiments

The quiz writing experiments were designed to mimic a teacher’s creation of a
reading quiz. In order to be able to measure and compare teacher’s quiz
writing processes, the setting was tightly controlled. Discussion of the
potential limitations this may introduce can be found in Section 6. Before
conducting the experiments, a pilot with four teachers in the ML domain was
conducted to ensure the metrics and annotator training were unambiguous. This
pilot resulted in minor changes to the wording in the training and metric
definitions, but no major experimental flaws were discovered.

There were $24$ quiz writing teachers, $12$ in each domain. The BIO teachers
were found through the freelance platform Upwork and have at least a high-
school level of teaching/tutoring experience. The ML teachers were recruited
through word-of-mouth at the institutions of the first author and have at
least a university level of teaching/tutoring experience. All teachers were
fairly monetarily compensated and signed a consent form before participating.
They are all proficient in the English language, and are from relatively
diverse demographics.repo_footnote The teachers completed a training module
where they were provided with example quizzes in their domain and were guided
through the creation of each quiz type to ensure they understood the task at
hand.

The process a single teacher underwent, irrespective of their domain, is
depicted in Figure 3. Each teacher wrote three quizzes, between five and ten
questions in length. With $12$ teachers and $12$ passages per domain, each
passage was used to create each type of quiz. Note that each teacher received
three different passages, to reduce the potential bias due to a teacher
working with material they have already seen. The three quiz types were:
handwritten, simple, and controlled. To create a handwritten quiz, the teacher
simply read the passage and wrote a quiz from scratch. To create a simple
quiz, the teacher read the passage and related candidates generated with the
simple prompting strategy. They then created a quiz with the freedom to copy
generated questions directly, copy and alter them, or write questions from
scratch. Similarly, to create a controlled quiz, the teacher read the passage
and related controlled candidates, and then wrote a quiz. The quizzes were
written in a random order to reduce any potential for biased results from the
ordering of the quiz writing subtasks.

\+ Simple Generations\+ Controlled GenerationsInput Passage AInput Passage
BInput Passage CTeacherHandwritten QuizSimple QuizControlled Quiz

Figure 3: Quiz writing experiment diagram depicting the three quiz writing
settings each teacher completed.

The teachers were asked to record their screen during the quiz writing
process. These videos were analyzed to assess teachers’ experiences writing
each kind of quiz. The time taken to write the quiz was measured, including
how long the reading of the passage and additional candidates took. The length
of the final quiz was measured, with a minimum of five and a maximum of $10$
questions. And finally, the source of the questions was noted. In other words,
it was recorded if the question was directly copied from the GPT-3.5
generations, if it was copied and altered by the teacher, or if it was written
completely from scratch.

Upon completion of the experiment, the teachers were asked to complete a brief
post-quiz to better understand their feedback on the three quiz writing tasks.
There was a section for free-form comments about the experiment. Then, the
teachers were asked to pick which of the three quiz types was their preferred
type and provide their reasoning.

Finally, eight other annotators (four per domain) analyzed the quality of the
resulting quizzes using the metrics introduced in Section 4.1. They were
recruited in the same way as outlined above, and have similar teaching
experience and English proficiency. Six quizzes were seen by all four of the
annotators in each domain in order to measure inter-annotator agreement. The
rest of the quizzes were seen by two annotators. Having more than one
annotator evaluate each quiz enables a more robust measurement of the quizzes’
quality. The annotators were not informed which quizzes included automatically
generated questions.

##  5 Results

This section covers the key results for the evaluations of quiz quality and
the quiz writing process. First, Section 5.1 will compare and contrast the
measured quality of the three different quiz types. Then, Section 5.2 will
discuss the teacher’s experiences in the different quiz writing settings.

###  5.1 Quiz Quality

Overall, the results from the quiz quality evaluations show that there is no
notable loss of quality between the handwritten and the two generation quiz
types. There is even an argument that an increase in quiz quality can be seen
in some of the following results.

The three question-level metrics demonstrate a low count of irrelevant,
disfluent, and unanswerable questions across all cohorts and quiz types. When
comparing across quiz types, these results are relatively consistent. This
implies that the use of generated candidates does not significantly increase
or decrease the quality of quiz questions along these three aspects. The
annotator agreement on these metrics is ‘fair’, with an average pairwise
Cohen’s $\kappa$ value of $0.3$ for the BIO cohort and $0.6$ for the ML cohort
(Landis and Koch 1977). 444Due to low percentages of irrelevant, disfluent,
and unanswerable questions the agreement values are calculated on a unbalanced
dataset and may not be an accurate representation of the real agreement on
problem cases.

Metric | Handwritten | Simple | Controlled
---|---|---|---
BIO | ML | BIO | ML | BIO | ML
Irrelevant | 0.03 | 0.00 | 0.05 | 0.05 | 0.04 | 0.00
Disfluent | 0.14 | 0.11 | 0.09 | 0.08 | 0.14 | 0.11
| Unanswer-
---
able
0.08 | 0.10 | 0.10 | 0.08 | 0.12 | 0.10
Table 1: Question-level quality metrics by cohort and quiz type. The values
are the proportion of questions that are irrelevant, disfluent, or
unanswerable.

The coverage results show significant improvement when teachers utilize
generated questions during their quiz writing process.555N.b., a single
coverage value for each quiz was annotated by the first author of this paper,
so no measurement of agreement is available for this metric. We leave this for
future work. Figure 4 depicts the increasing ratio of input text that is
covered between handwritten and simple, as well as simple and controlled quiz
types. In the ML cohort, a significant difference is observed between the
coverage ratios in the handwritten and controlled quizzes. In the BIO cohort,
we observe the same significant difference, as well as the difference between
the coverage ratios in the simple and controlled quizzes. While it is not the
only important aspect of a reading quiz, the increased coverage provided by
automatically generated questions can benefit teachers in their writing
process.

Figure 4: Context coverage by cohort and quiz type. * represents a significant
difference at the $\alpha=0.05$ level, and *** represents a significant
difference at the $\alpha=0.001$ level. The error bars represent $95\%$
confidence intervals.

The three ordinal quiz-level metrics similarly have positive results across
the board, as seen in the mean column of Table 2. The annotator agreement
values are quite high. These metric’s agreement is measured with Kendall’s
$\tau$ as it is suitable for ordinal scales (Schaeffer and Levitt 1956). All
average pairwise values are above $0.5$, and most above $0.81$.

Metric | Mean | Kendall’s $\tau$
---|---|---
BIO | ML | BIO | ML
| Structure
---
[1,3]
2.35 | 2.43 | 0.81 | 0.83
| Redundancy
---
[1,3]
2.55 | 2.80 | 0.59 | 0.80
| Usefulness
---
[1,4]
3.12 | 2.97 | 0.95 | 0.52
Table 2: Quiz-level quality metrics and annotator agreement. The structure and
redundancy metrics are on ordinal scales from 1 to 3, and the usefulness
metric is on an ordinal scale from 1 to 4.

Figure 5 shows the difference in quiz-level metrics between the three quiz
types. Notably, for all three metrics and in both cohorts, one of the
generation type quizzes is the highest rated. In the ML cohort there is even a
significant difference in the usefulness ratings between the handwritten and
simple quizzes. This points to the fact that the generations can help improve
the quality of quizzes. Further optimization of the generation process,
perhaps with input from the teachers directly on what types of questions will
be useful in a given setting, could show even stronger quality improvements.

Figure 5: Quiz-level quality metrics. The error bars represent $95\%$
confidence intervals. * represents a significant difference at the
$\alpha=0.05$ level.

###  5.2 Quiz Writing Experience

The quiz writing results demonstrate no consistent loss of efficiency when
teachers use generated questions, at least with respect to the time taken.
Figure 6 depicts the mean time to write each type of quiz for the two cohorts.
The mean values are all relatively close to one another, and the 95%
confidence intervals demonstrate that there appears to be no distinct
difference in the quiz types with respect to time. Further analysis of these
results demonstrate that the time metric is more dependent on the teacher and
the particular passage than the generated candidate questions.

Figure 6: Time taken to create a quiz by cohort and quiz type. The error bars
represent $95\%$ confidence intervals.

The average length of the quizzes was $8.14$ in the BIO cohort and $7.11$ in
the ML cohort. The mean number of questions in each quiz type was within one
question to the mean across all types, demonstrating that the use of
generations did not alter this variable. A more interesting comparison can be
seen in Figure 7, where the simple and controlled quiz types’ question sources
are compared. In both cohorts, the teachers hand write fewer questions when
they have the controlled generations at their disposal. In fact, in the ML
cohort, this difference is statistically significant. Again in both cohorts,
teachers directly copy more of the controlled generations into their quizzes
than the simple generations; and correspondingly they copy and edit fewer
questions. This finding demonstrates that teachers choose to use the questions
generated with Bloom’s taxonomy more than other generations, providing
motivation to continue QG research with pedagogical goals in mind.

Figure 7: Teachers use of generated questions by cohort. The error bars
represent $95\%$ confidence intervals. * represents a significant difference
at the $\alpha=0.05$ level.

The post-quiz results demonstrate a strong preference from the teachers in
both cohorts towards the use of controlled generations, as depicted in Figure
8. The following comments from the teachers provide additional evidence for
the fact that they find the controlled generations most useful for their quiz
writing. Teachers stated that “The generated questions for each specific type
were incredibly useful.” and “I particularly liked the ‘creating’ questions,
as I wouldn’t have come up with most of these myself.” Another teacher
commented that they “tried to incorporate different command terms and level
questions to prepare a quiz that tests the depth of a student’s
understanding”, indicating the intended usage of the questions in different
levels of Bloom’s taxonomy. This finding corroborates this paper’s guiding
intuition that QG methods should be designed with pedagogical goals in mind.

Figure 8: Teacher quiz type preference by cohort.

##  6 Limitations

It is important to note some limitations of this work. Firstly, we acknowledge
that the quiz writing setting is to some extent contrived. In reality,
teachers’ quiz writing experiences will be subjective: they might use
additional resources or existing knowledge, write a draft and return to it
later to edit, not constrain the number of questions, have different learning
goals in mind, and more. The quiz writing setting was necessary to control
certain variables for comparison within this work, but it creates the
possibility that the results do not reflect the reality of quiz writing for
teachers. Future work should aim to remove these constraints to better assess
how teachers might realistically use generated questions. Secondly, this work
only considers one LLM, two domains, the English-language setting, and a
limited number of teachers. Although out of scope for this work, future work
should aim to expand the variety of these aspects to assess how generated
questions might benefit additional educational settings. Thirdly, a missing
consideration in this work is the other half of the educational setting:
students. Future work should include student goals, opinions, and performance
in order to more comprehensively understand the implications of using
automatically generated questions in the classroom. Despite these limitations,
this work ultimately takes a step in the right direction for the future of QG
research within realistic educational use cases.

##  7 Conclusion

This paper aims to show that LLMs are capable of generating different types of
questions from a given context that teachers find useful to create a quiz that
is of comparable quality to a handwritten version. To do this, quiz writing
experiments were conducted comparing three types of quizzes: handwritten,
simple, and controlled quizzes. The controlled quizzes utilized questions
generated to correspond with the levels of Bloom’s taxonomy. The results
demonstrate that teachers strongly prefer writing quizzes with the help of
controlled generations. They also directly copy more of the controlled
generations than the simple generations, indicating that these questions are
of higher quality or better suited to a teacher’s goals. This confirms our
hypothesis that teachers find automatically generated pedagogical questions
useful for quiz writing. Additionally, an evaluation of quiz quality showed
that the quizzes with both controlled and simple generations are of comparable
quality. Some metrics even point towards their superior quality, when compared
to handwritten quizzes. We hope that these findings will help to direct the
future of educational QG research towards practical applications that meet the
goals and needs of teachers and students.

##  8 Acknowledgements

The authors would like to thank Mitacs for their grant for this project, and
CIFAR for their continued support. Additional thanks are extended to the
teachers and annotators for their time and effort and the anonymous reviewers
for their valuable feedback.

## References

  * Elkins et al. (2023) Elkins, S.; Kochmar, E.; Serban, I.; and Cheung, J. C. 2023.  How Useful Are Educational Questions Generated by Large Language Models?  In _International Conference on Artificial Intelligence in Education_ , 536–542. Springer.
  * Kasneci et al. (2023) Kasneci, E.; Seßler, K.; Küchemann, S.; Bannert, M.; Dementieva, D.; Fischer, F.; Gasser, U.; Groh, G.; Günnemann, S.; Hüllermeier, E.; et al. 2023.  ChatGPT for good? On opportunities and challenges of large language models for education.  _Learning and Individual Differences_ , 103: 102274.
  * Krathwohl (2002) Krathwohl, D. R. 2002.  A revision of Bloom’s taxonomy: An overview.  _Theory into practice_ , 41(4): 212–218.
  * Kurdi et al. (2020) Kurdi, G.; Leo, J.; Parsia, B.; Sattler, U.; and Al-Emari, S. 2020.  A systematic review of automatic question generation for educational purposes.  _International Journal of Artificial Intelligence in Education_ , 30: 121–204.
  * Laban et al. (2022) Laban, P.; Wu, C.-S.; Murakhovs’ ka, L.; Liu, W.; and Xiong, C. 2022.  Quiz design task: Helping teachers create quizzes with automated question generation.  _arXiv preprint arXiv:2205.01730_.
  * Landis and Koch (1977) Landis, J. R.; and Koch, G. G. 1977.  An application of hierarchical kappa-type statistics in the assessment of majority agreement among multiple observers.  _Biometrics_ , 363–374.
  * Liu et al. (2023) Liu, P.; Yuan, W.; Fu, J.; Jiang, Z.; Hayashi, H.; and Neubig, G. 2023.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  _ACM Computing Surveys_ , 55(9): 1–35.
  * Mazidi and Nielsen (2014) Mazidi, K.; and Nielsen, R. D. 2014.  Pedagogical evaluation of automatically generated questions.  In _Intelligent Tutoring Systems: 12th International Conference, ITS 2014, Honolulu, HI, USA, June 5-9, 2014. Proceedings 12_ , 294–299. Springer.
  * Mulla and Gharpure (2023) Mulla, N.; and Gharpure, P. 2023.  Automatic question generation: a review of methodologies, datasets, evaluation metrics, and applications.  _Progress in Artificial Intelligence_ , 12(1): 1–32.
  * Nenkova and Passonneau (2004) Nenkova, A.; and Passonneau, R. J. 2004.  Evaluating content selection in summarization: The pyramid method.  In _Proceedings of the human language technology conference of the north american chapter of the association for computational linguistics: Hlt-naacl 2004_ , 145–152.
  * Ouyang et al. (2022) Ouyang, L.; Wu, J.; Jiang, X.; Almeida, D.; Wainwright, C. L.; Mishkin, P.; Zhang, C.; Agarwal, S.; Slama, K.; Ray, A.; Schulman, J.; Hilton, J.; Kelton, F.; Miller, L.; Simens, M.; Askell, A.; Welinder, P.; Christiano, P.; Leike, J.; and Lowe, R. 2022.  Training language models to follow instructions with human feedback.
  * Schaeffer and Levitt (1956) Schaeffer, M. S.; and Levitt, E. E. 1956.  Concerning Kendall’s tau, a nonparametric correlation coefficient.  _Psychological Bulletin_ , 53(4): 338.
  * Steuer et al. (2021) Steuer, T.; Bongard, L.; Uhlig, J.; and Zimmer, G. 2021.  On the linguistic and pedagogical quality of automatic question generation via neural machine translation.  In _Technology-Enhanced Learning for a Free, Safe, and Sustainable World: 16th European Conference on Technology Enhanced Learning, EC-TEL 2021, Bolzano, Italy, September 20-24, 2021, Proceedings 16_ , 289–294. Springer.
  * Van Campenhout, Hubertz, and Johnson (2022) Van Campenhout, R.; Hubertz, M.; and Johnson, B. G. 2022.  Evaluating AI-Generated Questions: A Mixed-Methods Analysis Using Question Data and Student Perceptions.  In _Artificial Intelligence in Education: 23rd International Conference, AIED 2022, Durham, UK, July 27–31, 2022, Proceedings, Part I_ , 344–353. Springer.
  * Wang et al. (2022a) Wang, X.; Fan, S.; Houghton, J.; and Wang, L. 2022a.  Towards process-oriented, modular, and versatile question generation that meets educational needs.  _arXiv preprint arXiv:2205.00355_.
  * Wang et al. (2022b) Wang, Z.; Valdez, J.; Basu Mallick, D.; and Baraniuk, R. G. 2022b.  Towards human-like educational question generation with large language models.  In _International conference on artificial intelligence in education_ , 153–166. Springer.
  * Zhang et al. (2022) Zhang, H.; Song, H.; Li, S.; Zhou, M.; and Song, D. 2022.  A survey of controllable text generation using transformer-based pre-trained language models.  _arXiv preprint arXiv:2201.05337_.