# Infinite Action Contextual Bandits with Reusable Data Exhaust

Mark Rucker
University of Virginia
&Yinglun Zhu
University of Wisconsin–Madison
&Paul Mineiro
Microsoft Research NYC

###### Abstract

For infinite action contextual bandits, smoothed regret and reduction to
regression results in state-of-the-art online performance with computational
cost independent of the action set: unfortunately, the resulting data exhaust
does not have well-defined importance-weights. This frustrates the execution
of downstream data science processes such as offline model selection. In this
paper we describe an online algorithm with an equivalent smoothed regret
guarantee, but which generates well-defined importance weights: in exchange,
the online computational cost increases, but only to order smoothness (i.e.,
still independent of the action set). This removes a key obstacle to adoption
of smoothed regret in production scenarios.

##  1 Introduction

Those who ignore history are doomed to repeat it. A modern variant of this
truth arises in controlled experimentation platforms, where offline procedures
are a critical complement to online tests, e.g., supporting counterfactual
evaluation strategies (Agarwal et al., 2016), offline model selection (Li et
al., 2015), and prioritization of scarce online experimental resources (Gomez-
Uribe & Hunt, 2015). Consequently, the utility of a learning algorithm is not
solely determined by online performance, but also by the post-hoc utility of
the data exhaust.

The recent contribution of Zhu & Mineiro (2022) exemplifies this: an online
contextual bandit algorithm for infinite action spaces with $O(1)$ space and
time complexity with respect to the action set. Unfortunately, this
performance is achieved by sampling from a distribution which is not
absolutely continuous with the reference measure. Therefore, a variety of
post-hoc evaluation procedures that rely on importance-weighting cannot be
applied, limiting adoption.

In this paper, we describe an alternative approach to infinite action spaces
which not only enjoys similar smooth regret guarantee (and empirical
performance), but also utilizes sampling distributions with well defined
importance-weights. In exchange, we pay an increased computational cost.
However, the computational cost only scales with the smoothness of the regret
guarantee, rather than the cardinality or dimensionality of the action space
per se. Furthermore the new approach does not require an
$\operatorname*{arg\,min}$ oracle, which plays a critical role in the work of
Zhu & Mineiro (2022).

#### Contributions

We highlight our main contributions:

  1. 1.

In Section 3.2, we present CappedIGW, an algorithm that achieves near-optimal
smooth regret guarantees with (i) a sampling distribution that generates
reusable data exhaust, and (ii) no dependence on an expansive
$\operatorname*{arg\,min}$ oracle (which is used by previous algorithms).

  2. 2.

In Section 3.3, we develop algorithms to efficiently implement the algorithm
CappedIGW. Our computational complexity only scales with the smoothness
parameter, but otherwise has no explicit dependence on the cardinality or
dimensionality of the action space. Our implementation leverages techniques
from betting martingales (Waudby-Smith & Ramdas, 2020) and is of independent
interest for Monte-Carlo integration.

In Section 4, we provide experimental demonstrations exhibiting a combination
of equivalent online performance to Zhu & Mineiro (2022) and superior offline
utility.

##  2 Problem Setting

Unfortunately several unusual aspects of our approach demand a tedious
exposition: we operate via reduction to regression; we use a nonstandard
(smoothed) regret criterion; and our computational complexity claims require
careful specification of oracles in the infinite action setting. The impatient
reader can skip directly to Section 3 and use this section as reference.

#### Notation

For functions $f,g:\mathcal{Z}\to{\mathbb{R}}_{+}$, we write $f=O(g)$ (resp.
$f=\Omega(g)$) if there exists a constant $C>0$ such that $f(z)\leq{}Cg(z)$
(resp. $f(z)\geq{}Cg(z)$) for all $z\in\mathcal{Z}$. We write
$f=\widetilde{O}(g)$ if $f=O(g\cdot\mathrm{polylog}(T))$,
$f=\widetilde{\Omega}(g)$ if $f=\Omega(g/\mathrm{polylog}(T))$. For a set
$\mathcal{Z}$, we let $\Delta(\mathcal{Z})$ denote the set of all Radon
probability measures over $\mathcal{Z}$. We let
$\mathbb{I}_{z}\in\Delta(\mathcal{Z})$ denote the delta distribution on $z$.
For $x\in\mathbb{R}$ we define $(x)_{+}\vcentcolon=\max\left(x,0\right)$.

###  2.1 Contextual Bandits: Reduction to regression

We consider the following standard contextual bandit problems. At any time
step $t\in[T]$, nature selects a context $x_{t}\in\mathcal{X}$ and a
distribution over loss functions $\ell_{t}:\mathcal{A}\rightarrow[0,1]$
mapping from the (compact) action set $\mathcal{A}$ to a loss value in
$[0,1]$. Conditioned on the context $x_{t}$, the loss function is
stochastically generated, i.e., $\ell_{t}\sim{\mathbb{P}}_{\ell_{t}}(\cdot\mid
x_{t})$. The learner selects an action $a_{t}\in\mathcal{A}$ based on the
revealed context $x_{t}$, and obtains (only) the loss $\ell_{t}(a_{t})$ of the
selected action. The learner has access to a set of measurable regression
functions $\mathcal{F}\subseteq(\mathcal{X}\times\mathcal{A}\rightarrow[0,1])$
to predict the loss of any context-action pair. We make the following standard
realizability assumption studied in the contextual bandit literature (Agarwal
et al., 2012; Foster et al., 2018; Foster & Rakhlin, 2020; Simchi-Levi & Xu,
2021).

######  Assumption 1 (Realizability).

There exists a regression function $f^{\star}\in\mathcal{F}$ such that
${\mathbb{E}}[\ell_{t}(a)\mid x_{t}]=f^{\star}(x_{t},a)$ for any
$a\in\mathcal{A}$ and across all $t\in[T]$.

###  2.2 Smoothed Regret

Let $(\mathcal{A},\Omega)$ be a measurable space of the action set and $\mu$
be a base probability measure over the actions. Let $\mathcal{Q}_{\tau}$
denote the set of probability measures such that, for any measure
$Q\in\mathcal{Q}_{\tau}$, the following holds true: (i) $Q$ is absolutely
continuous with respect to the base measure $\mu$, i.e., $Q\ll\mu$; and (ii)
The Radon-Nikodym derivative of $Q$ with respect to $\mu$ is no larger than
$\tau$, i.e., $\frac{dQ}{d\mu}\leq\tau$. We call $\mathcal{Q}_{\tau}$ the set
of smoothing kernels at smoothness level $\tau$, or simply put the set of
$\tau$-smoothed kernels. For any context $x\in\mathcal{X}$, we denote by
$\mathsf{Smooth}_{\tau}(x)$ the smallest loss incurred by any $\tau$-smoothed
kernel, i.e.,

$\displaystyle\mathsf{Smooth}_{\tau}(x)\vcentcolon=\inf_{Q\in\mathcal{Q}_{\tau}}{\mathbb{E}}_{a\sim
Q}[f^{\star}(x,a)].$

Rather than competing with
$\operatorname*{arg\,min}_{a\in\mathcal{A}}f^{\star}(x,a)$—which is minimax
prohibitive in infinite action spaces— we take $\mathsf{Smooth}_{\tau}(x)$ as
the benchmark and define the _smooth regret_ as follows:

$\displaystyle\mathrm{\mathbf{Reg}}_{\mathsf{CB},\tau}(T)$
$\displaystyle\coloneqq{\mathbb{E}}\left[\sum_{t=1}^{T}f^{\star}(x_{t},a_{t})-\mathsf{Smooth}_{\tau}(x_{t})\right].$
(1)

One important feature about the above definition is that the benchmark, i.e.,
$\mathsf{Smooth}_{\tau}(x_{t})$, automatically adapts to the context $x_{t}$:
this gives the benchmark more power and makes it harder to compete against,
compared to previously studied baselines (Chaudhuri & Kalyanakrishnan, 2018;
Krishnamurthy et al., 2020).

###  2.3 Computational Oracles

The first step towards designing computationally efficient algorithms is to
identify reasonable oracle models to access the sets of regression functions
or actions. Otherwise, enumeration over regression functions or actions (both
can be exponentially large) immediately invalidate the computational
efficiency. We consider two common oracle models: a regression oracle and a
sampling oracle.

#### The regression oracles

A fruitful approach to designing efficient contextual bandit algorithms is
through reduction to supervised regression with the class $\mathcal{F}$
(Foster & Rakhlin, 2020; Simchi-Levi & Xu, 2021; Foster et al., 2020, 2021a).
We provide a brief introduction to the reduction technique employed in this
paper in Appendix A. Following Foster & Rakhlin (2020), we assume that we have
access to an _online_ regression oracle $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$,
which is an algorithm for sequential prediction under square loss. More
specifically, the oracle operates in the following protocol: At each round
$t\in[T]$, the oracle makes a prediction $\widehat{f}_{t}$, then receives
context-action-loss tuple $(x_{t},a_{t},\ell_{t}(a_{t}))$. The goal of the
oracle is to accurately predict the loss as a function of the context and
action, and we evaluate its performance via the square loss
$(\widehat{f}_{t}(x_{t},a_{t})-\ell_{t}(a_{t}))^{2}$. We measure the oracle’s
cumulative performance through the square-loss regret to $\mathcal{F}$, which
is formalized below.

######  Assumption 2.

The regression oracle $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$ guarantees that,
with probability at least $1-\delta$, for any (potentially adaptively chosen)
sequence $\left\\{(x_{t},a_{t},\ell_{t}(a_{t}))\right\\}_{t=1}^{T}$,

${\mathbb{E}}\Bigg{[}\sum_{t=1}^{T}\left(\widehat{f}_{t}(x_{t},a_{t})-\ell_{t}(a_{t})\right)^{2}\Bigg{.}\Bigg{.}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\left(f(x_{t},a_{t})-\ell_{t}(a_{t})\right)^{2}\Bigg{]}\leq\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T,\delta),$

for some (non-data-dependent) function
$\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T,\delta)$.

We will consider the following operations $O(1)$ cost: (i) query the oracle’s
estimator $\widehat{f}_{t}$ with context-action pair $(x_{t},a)$ and receive
its predicted value $\widehat{f}_{t}(x_{t},a)\in[0,1]$; and (ii) update the
oracle with example $(x_{t},a_{t},\ell_{t}(a_{t}))$.

Online regression is a well-studied problem, with known algorithms for many
model classes (Foster & Rakhlin, 2020; Foster et al., 2020): including linear
models (Hazan et al., 2007), generalized linear models (Kakade et al., 2011),
non-parametric models (Gaillard & Gerchinovitz, 2015), and beyond. Using
Vovk’s aggregation algorithm (Vovk, 1998), one can show that
$\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T,\delta)=O(\log(\lvert\mathcal{F}\rvert/\delta))$
for any finite set of regression functions $\mathcal{F}$, which is the
canonical setting studied in contextual bandits (Langford & Zhang, 2007;
Agarwal et al., 2012). In the following of this paper, we use abbreviation
$\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)\vcentcolon=\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T,T^{-1})$,
and will keep the $\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)$ term in our regret
bounds to accommodate for general set of regression functions.

#### The sampling oracle

In order to design algorithms that work with large/continuous action spaces,
we assume access to a sampling oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sample}}$ to get access to the action space.
In particular, the oracle $\mathrm{\mathbf{Alg}}_{\mathsf{Sample}}$ returns an
action $a\sim\mu$ randomly drawn according to the base probability measure
$\mu$ over the action space $\mathcal{A}$. We consider this operation $O(1)$
cost.

#### Representing the actions

In practice the number of bits required to represent any action
$a\in\mathcal{A}$ scales with $O(\log\lvert\mathcal{A}\rvert)$ with a finite
set of actions and $\widetilde{O}(d)$ for actions represented as vectors in
${\mathbb{R}}^{d}$. Nonetheless we consider this $O(1)$, i.e., we elide the
representational overhead in big-$O$ notation for our computational analysis.

##  3 Algorithms

###  3.1 Background: SmoothIGW

Zhu & Mineiro (2022) designed an oracle-efficient SmoothIGW that achieves a
$\sqrt{T}$-type regret under the smooth regret defined in Eq. 1. Algorithm 1
contains the pseudo code of the SmoothIGW algorithm. At each round $t\in[T]$,
the learner observes the context $x_{t}$ from the environment, obtains the
estimator $\widehat{f}_{t}$ from the regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$, and computes the greedy action
$\widehat{a}_{t}$. It then constructs a sampling distribution $P_{t}$ by
mixing a smoothed inverse gap weighted (IGW) distribution (Abe & Long, 1999;
Foster & Rakhlin, 2020) and a delta mass at the greedy action. The algorithm
samples an action $a_{t}\sim P_{t}$ and updates the regression oracle.

Algorithm 1 SmoothIGW (Zhu & Mineiro, 2022)

0: Exploration parameter $\gamma>0$; online regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$.

1: for $t=1,2,\dots,T$ do

2: Observe context $x_{t}$.

3: Receive $\widehat{f}_{t}$ from regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$.

4: Get
$\widehat{a}_{t}\vcentcolon=\operatorname*{arg\,min}_{a\in\mathcal{A}}\widehat{f}_{t}(x_{t},a)$.

5: Set  $\displaystyle
P_{t}\vcentcolon=M_{t}+(1-M_{t}(\mathcal{A}))\cdot\mathbb{I}_{\widehat{a}_{t}}$
where $M_{t}$ is the measure defined in Eq. 2

6: Sample $a_{t}\sim P_{t}$ and observe loss $\ell_{t}(a_{t})$.

7: Update $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$ with
$(x_{t},a_{t},\ell_{t}(a_{t}))$

The measure $M_{t}$ on line 5 of Algorithm 1 is defined by the following
density with respect to the reference measure,

$\displaystyle\frac{dM_{t}}{d\mu}(a)\vcentcolon=\frac{\tau}{\tau+\gamma\cdot\left(\widehat{f}_{t}(x_{t},a)-\widehat{f}_{t}(x_{t},\widehat{a}_{t})\right)}.$
(2)

Note that $M_{t}$ is only a sub-probability measure since $dM_{t}/d\mu(a)\leq
1$, hence an additional
$(1-M_{t}(\mathcal{A}))\cdot\mathbbm{1}_{\widehat{a}_{t}}$ term is needed (to
make sure that $P_{t}$ is a probability measure).

#### The Problems

While SmoothIGW is the first oracle-efficient contextual bandit algorithm that
works with smooth regret, it is not without problems. We highlight two
problems associated with SmoothIGW below.

  * •

The $\operatorname*{arg\,min}$ oracle. Note that Algorithm 1 requires an exact
$\operatorname*{arg\,min}$ oracle to compute the greedy action
$\widehat{a}_{t}$ (on line 4), which is later on used to construct the
sampling distribution $P_{t}$ (on line 5). However, when working with large,
and potentially continuous, action spaces, it can be computationally expensive
to obtain such an exact $\operatorname*{arg\,min}$ oracle. For their
experiments, Zhu & Mineiro (2022) construct a regressor class with an $O(1)$
$\operatorname*{arg\,min}$ oracle, but their construction induces a unimodal
$\widehat{f}_{t}$, which may not always be appropriate.

  * •

Insufficient data reuse. While the $M_{t}$ term is always absolutely
continuous with respect to the base measure $\mu$, the delta distribution
$\mathbbm{1}_{\widehat{a}_{t}}$ is not absolutely continuous with respect to
$\mu$ in many common cases, e.g., when $\mu$ is the Lebesgue measure in
${\mathbb{R}}_{d}$. As a result, a variety of post-hoc procedures that rely on
importance-weighting cannot be applied. Unfortunately, to achieve
$O(\sqrt{T})$ regret, SmoothIGW uses $\gamma\propto\sqrt{T}$, which implies
that the fraction of actions sampled from the $\mathbbm{1}_{\widehat{a}_{t}}$
component increases with horizon length, e.g., Fig. 3.

These two drawbacks frustrate the deployment of SmoothIGW in real-world
applications.

###  3.2 New Approach: CappedIGW

Resolution of the above issues requires eliminating the use of the greedy
action $\widehat{a}_{t}$, which occurs in two places:

  * •

Inverse-gap weighting. In sub-probability measure $M_{t}$, its density (with
respect to $\mu$) on any action $a$ is defined to be inversely proportional to
the empirical loss gap
$\left(\widehat{f}_{t}(x_{t},a)-\widehat{f}_{t}(x_{t},\widehat{a}_{t})\right)$:
here, we use $\widehat{f}_{t}(x_{t},\widehat{a}_{t})$ as a _benchmark_ to
compute the loss gap.

  * •

Pseudo normalization. Since $M_{t}$ is only a sub-probability measure, to
actually sample from a probability measure, SmoothIGW shifts the remaining
probability mass to the delta distribution at the greedy action, i.e.,
$\mathbbm{1}_{\widehat{a}_{t}}$: here, we use $\mathbbm{1}_{\widehat{a}_{t}}$
to pseudo normalize the sub-probability measure $M_{t}$.

In the sequel we eliminate use of the greedy action.

#### Sampling Density

Let $\beta_{t},\kappa_{t}\in{\mathbb{R}}$ be two parameters (whose values will
be computed later). We consider a probability measure $P_{t}$ whose density
with respect to the base measure $\mu$ is defined as follows:

$\frac{dP_{t}}{d\mu}(a)=\kappa_{t}\frac{\tau}{1+\gamma\left(\widehat{f}_{t}(x_{t},a_{t})-\beta_{t}\right)_{+}},$
(3)

where $(x)_{+}\vcentcolon=\max\left(x,0\right)$. Relative to SmoothIGW:

  * •

We replace the old loss gap benchmark $\widehat{f}_{t}(x_{t},\widehat{a}_{t})$
by the new parameter $\beta_{t}$; we also take another $\max$ operation over
$\widehat{f}_{t}(x_{t},a)-\beta_{t}$ and $0$ to ensure the positivity of the
loss gap. This was inspired by observing the optimal $\tau$-smooth policy
plays uniformly over the $\tau^{-1}$-th quantile of the true $f^{*}$, but is
ultimately justified by the regret decomposition in the proof of Theorem 1.

  * •

We use $\kappa_{t}$ as a normalization factor instead of shifting mass to
$\mathbbm{1}_{\widehat{a}_{t}}$; the normalization factor $\kappa_{t}$ is
determined by the choice of $\beta_{t}$ via

$\displaystyle\kappa_{t}=1\Bigg{/}\mathbb{E}_{a_{t}\sim\mu}\left[\frac{\tau}{1+\gamma\left(\widehat{f}_{t}(x_{t},a_{t})-\beta_{t}\right)_{+}}\right].$

With this new sampling distribution in Eq. 3 at hand, we develop a new
algorithm for smooth regret, shown next in Algorithm 2.

Algorithm 2 CappedIGW

0: Exploration parameter $\gamma>0$; online regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$.

1: for $t=1,2,\dots,T$ do

2: Observe context $x_{t}$.

3: Receive $\widehat{f}_{t}$ from regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$.

4: Compute $\beta_{t}$. // Algorithm 3

5: Sample $a_{t}\sim P_{t}$ // Eq. 3, Algorithm 4

6: Observe loss $\ell_{t}(a_{t})$.

7: Update $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$ with
$(x_{t},a_{t},\ell_{t}(a_{t}))$

We will show in next section that $\beta_{t}$ can be computed efficiently in
$\widetilde{O}(\tau\log\tau)$ calls to the sampling oracle. First we state a
regret guarantee.

######  Theorem 1.

Fix any smoothness level $\tau\geq 1$. Suppose $\forall t:\kappa_{t}\geq 1$
and let $\kappa_{\infty}$ be an upper bound on $\kappa_{t}$ for $\forall t$.
By setting the exploration parameter
$\gamma=\sqrt{8T\kappa_{\infty}\tau/\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)}$,
Algorithm 2 ensures that

$\displaystyle\mathrm{\mathbf{Reg}}_{\mathsf{CB},\tau}(T)\leq{\sqrt{4T\,\tau\kappa_{\infty}\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)}}.$

###### Proof.

See Appendix B. ∎

The guarantee in Theorem 1 is the same as the guarantee for SmoothIGW (which
is near-optimal) up to a $\sqrt{\kappa_{\infty}}$ factor. Since we can always
find appropriate $\beta_{t},\kappa_{t}$ to ensure $\kappa_{\infty}=O(1)$, we
can efficiently achieve the near-optimal smooth regret guarantees without (i)
an $\operatorname*{arg\,min}$ oracle, and (ii) with full data exhaust reuse.

#### Adapting to an unknown smoothness level $\tau$

We can simply replace SmoothIGW with CappedIGW in Zhu & Mineiro (2022, Thm. 2)
to build (i) Pareto optimal algorithms with unknown smoothness level $\tau$,
and (ii) develop nearly minimax optimal algorithms under the standard regret
for bandits with multiple best arms Zhu & Nowak (2020) and Lipschitz/Hölder
bandits Kleinberg (2004); Hadiji (2019): see Section 4 and Section 5 in Zhu &
Mineiro (2022) for details.

###  3.3 Efficient Implementation

In this section, we discuss how to efficiently (i) compute parameter
$\beta_{t}$ and (ii) sample actions from the distribution $P_{t}$. We first
notice that the condition $\kappa_{t}\geq 1$ is critical to Theorem 1.
Intuitively, $\beta_{t}$ must be chosen so that Algorithm 2 plays a policy
which is at most $\tau$-smooth. Because we are competing with $\tau$-smooth
policies, it makes sense to be less smooth than the competitor but not to be
more smooth than the competitor (further, as described at the end of Section
3.2, the appropriate level for $\tau$ can be adaptively chosen).

Consistent with Theorem 1, our task is to find a $\beta_{t}$ such that

$\mathbb{E}_{a_{t}\sim\mu}\left[\frac{\tau}{1+\gamma\left(\widehat{f}_{t}(x_{t},a_{t})-\beta_{t}\right)_{+}}\right]\in\left[\frac{1}{\kappa_{\infty}},1\right].$
(4)

First, we establish that it is provably possible to satisfy Eq. 4 with high
probability using
$O\left(\tau\log(\nicefrac{{(\tau+\gamma)}}{{\delta}})\right)$ samples from
the reference measure.

######  Theorem 2.

With the choice $\kappa_{\infty}=24$, with probability at least $(1-\delta)$,
it is possible to estimate $\beta$ satisfying Eq. 4 using
$O\left(\tau\log(\nicefrac{{(\tau+\gamma)}}{{\delta}})\right)$ samples from
$\mu$.

###### Proof.

See Appendix C ∎

Theorem 2 uses a fixed sampling strategy which is amenable to analysis and
provably terminates after $\widetilde{O}(\tau\log\tau)$ samples. However, this
fixed sampling strategy is unnecessarily conservative in practice. To obtain a
better empirical performance, instead, we use Algorithm 3—an anytime-valid
technique–to ensure early-termination whenever possible. In lieu of proving
termination, we backstop Algorithm 3 with Theorem 2, which leads to at most
doubling the number of samples required.

Algorithm 3 Normalization CS to compute $\beta_{t}$. The subroutine
BettingMartingale.Update is defined in Appendix D.

0: $\widehat{f}_{t}$ (from regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$); exploration parameter $\gamma>0$;
failure probability $\delta$; and $\kappa_{\infty}\geq 1$. // It suffices to
take $\kappa_{\infty}=24$

1: Let $n_{\max}=O\left(\tau\log(\nicefrac{{\gamma}}{{\delta}})\right)$ //
from Theorem 2

2: $l,u\leftarrow\frac{1-\tau}{\gamma},1$ // Because
$\widehat{f}_{t}(x_{t},\cdot)\in[0,1]$

3: for $n=1,2,\dots,n_{\max}$ do

4: Sample $a_{n}\sim\mu$.

5: Let
$g_{n}(\cdot)=\frac{\tau}{1+\gamma\left(\widehat{f}_{t}(x_{t},a_{n})-(\cdot)\right)_{+}}$.

6:
$l_{n},u_{n}\leftarrow\texttt{BettingMartingale.Update}(g_{n};\kappa_{\infty};\delta)$

7: if $l_{n}>u_{n}$ then

8: return $l_{n}$ // Satisfies Eq. 4 w.p. $(1-\delta)$

9: tail call Theorem 2 // Never happens in practice

######  Theorem 3.

If Algorithm 3 returns a value on line 8, that value satisfies Eq. 4 with
probability at least $(1-\delta)$ with respect to the realizations from line
4.

###### Proof.

See Appendix E ∎

In practice, Algorithm 3 is vastly more sample efficient than the procedure
from Theorem 2: see Table 1 for an empirical comparison. Algorithm 3 operates
by maintaining two betting martingales, one of which tries to refine a lower
bound on $\beta$ and the other an upper bound. We defer complete details to
Appendix D.

As a motivation, note the combination of betting martingales and no-regret
algorithms yields a test with asymptotic optimal power (Casgrain et al.,
2022), but which can be safely composed with any stopping rule (e.g., line 8
of Algorithm 3). Early stopping is advantageous to the extent
$\widehat{f}_{t}$ is closer to a constant function, because evidence regarding
the normalization constant accumulates more rapidly than accounted for by
Theorem 2.

Algorithm 4 Sampling routine

0: $\widehat{f}_{t}$ (from regression oracle
$\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$); $\beta_{t}$ (from Algorithm 3);
exploration parameter $\gamma>0$

1: while true do

2: Sample $a_{t}\sim\mu$.

3: Compute
$p_{\text{accept}}\vcentcolon=\frac{1}{1+\gamma\left(\widehat{f}_{t}(x_{t},a_{t})-\beta_{t}\right)_{+}}$.

4: With probability $p_{\text{accept}}$, return $a_{t}$.

#### Efficiently sampling $a_{t}\sim P_{t}$

Algorithm 4 is an efficient rejection sampling on the density from Eq. 3. Note
that $p_{\text{accept}}$ on line 3 is proportional to the desired sampling
density $P_{t}$ defined in Eq. 3, but at most 1. Hence we have the following
two established properties of rejection sampling:

  1. 1.

If line 4 returns an action $a_{t}$, then the action $a_{t}$ is distributed
according to Eq. 3;

  2. 2.

The number of samples required before Algorithm 4 terminates is geometrically
distributed with mean $\kappa_{t}\tau$. In particular, with high probability
the number of samples is $O(\kappa_{t}\tau)$ due to exponential tail bounds.

#### Computing $\kappa_{t}$

The astute reader will notice that $\kappa_{t}$ need not be computed
explicitly for Algorithm 2, i.e., for online inference. However an estimate of
$\kappa_{t}$ might be useful for having more accurate importance-weights for
offline reuse. For our experiments we use the naive constant estimate
$\widehat{\kappa}_{t}=1$, and leave this an area for future work.

##  4 Experiments

We conduct multiple experiments in this section. In Section 4.1, we
empirically compare the performance of Theorem 2 and Algorithm 3. We compare
our algorithm CappedIGW with the previous state-of-the-art algorithm SmoothIGW
(Zhu & Mineiro, 2022) in terms of both the online performance (Section 4.2)
and the offline utility (Section 4.3). We also demonstrate why SmoothIGW lacks
offline utility in Section 4.4. Code to reproduce all experiments available at
https://github.com/mrucker/onoff_experiments.

###  4.1 Normalization CS

This experiment establishes the empirical validity and efficacy of Algorithm
3. For these simulations we use the unit interval as the action space;
Lebesgue reference measure; $\widehat{f}_{t}(x_{t},a_{t})=1_{2a_{t}\tau>1}$,
corresponding to loss function which is a narrow “needle in the haystack”;
failure probability $\delta=2.5\%$; and $\kappa_{\infty}=24$. As indicated in
Table 1, Algorithm 3 is a vast improvement over the procedure from Theorem 2.
Note in Table 1, $\kappa_{t}$ is the true value computed analytically from the
$\beta_{t}$ produced by Algorithm 3.

Table 1: Algorithm 3 is vastly more sample efficient than the procedure from
Theorem 2. The $n$ and $\kappa_{t}$ from Algorithm 3 are random variables:
shown are 95% bootstrap CI of the realization (_not_ the population mean) over
different sampler seeds.
$\tau$ | $\gamma$ |  $n$ (Thm 2) |  $n$ (Alg 3) |  $\kappa_{t}$ (Alg 3)
---|---|---|---|---
2 | 16 | 942 | [18, 24] | [1.3, 3.0]
20 | 304 | 13496 | [123, 227] | [10.2, 11.8]
200 | 6368 | 177141 | [2254, 2788] | [1.8, 23.6]

###  4.2 Online Regret

Figure 1: Consistent with their similar theoretical guarantees, online
performance of SmoothIGW and CappedIGW is similar, although CappedIGW enjoys a
slight advantage. Each datapoint represents a single dataset. Plotted here is
$\left(\text{Loss}({\textsf{SmoothIGW}})-\text{Loss}({\textsf{CappedIGW}})\right)$
with 90% bootstrap CIs, i.e., larger values in the plot indicate CappedIGW is
outperforming SmoothIGW. Win/tie/loss is determined by if the CI contains 0.

Here we demonstrate that SmoothIGW has similar online regret to CappedIGW. We
use twenty regression datasets converted to contextual bandit datasets with
action space $\mathcal{A}=[0,1]$ via a supervised-to-bandit transformation
Bietti et al. (2021). Each dataset is individually shifted and scaled so that
target value $y_{t}\in[0,1]$. When an algorithm plays action $a_{t}\in[0,1]$,
it receives bandit feedback $\ell_{t}(a_{t})\vcentcolon=|y_{t}-a_{t}|$.

We assess each algorithm (SmoothIGW, CappedIGW) on progressive validation
loss. Blum et al. (1999). For each dataset we run both algorithms using the
same set of $30$ different seeds, where a seed controls all non-determinism
(including data set shuffling, parameter initialization, and action sampling).
For each dataset we compute the average of the paired (by seed) differences
between each algorithm, and then compute a 90% bootstrap confidence interval.

The two algorithms are declared to have tied on a dataset when the 90% CI for
their difference contains a $0$. Otherwise one of the algorithms is declared
to win. In total we observe five ties, one small SmoothIGW win, and fourteen
small CappedIGW wins. The complete result can be seen in Figure 1.

This experiment also demonstrates the effectiveness of Algorithm 3 within
CappedIGW. In this experiment CappedIGW determines $\beta_{t}$ each iteration
using Algorithm 3 with $\kappa_{\infty}=4$.

For further details (e.g., model class for $\widehat{f}_{t}$) see Appendix F.

###  4.3 Offline Utility

This experiment provides an example of the increased utility of CappedIGW’s
data exhaust for offline learning relative to SmoothIGW’s exhaust. Here we
mimic a typical production goal of evaluating a more complicated model class
than was used online qua Gomez-Uribe & Hunt (2015, ${\mathbb{S}}4.6$). As
shown in Fig. 2, offline learners trained on CappedIGW exhaust exhibit
statistically significant smaller average loss on twelve of twenty datasets.

Figure 2: Policies trained offline using CappedIGW exhaust exhibit less
average loss online compared to policies trained offline using SmoothIGW
exhaust. Plotted here is
$\left(\text{Loss}({\textsf{SmoothIGW}})-\text{Loss}({\textsf{CappedIGW}})\right)$
with 90% bootstrap CIs, i.e., larger values in the plot indicate training on
CappedIGW exhaust is superior to training on SmoothIGW exhaust. Win/tie is
determined by the CI containing $0$. Figure 3: Over time SmoothIGW
increasingly plays its greedy action, which does not have a well defined
importance-weight. (Not shown) With CappedIGW the data exhaust always has an
importance-weight.

To generate data exhaust all
$(x_{t},a_{t},\widehat{P}_{t}(a_{t}),\ell_{t}(a_{t}))$ were logged during the
online experiments described in Section 4.2, where

$\widehat{P}_{t}(a_{t})\vcentcolon=\frac{\tau}{1+\gamma\left(\widehat{f}_{t}(x_{t},a_{t})-\beta_{t}\right)_{+}},$

i.e., we (naively) estimate $\widehat{\kappa_{t}}=1$. We use the inverse of
$\widehat{P}_{t}(a_{t})$ as the importance weight.

For each resulting dataset (SmoothIGW exhaust or CappedIGW exhaust), the best
of two off-policy learning methods was selected: the direct method Dudík et
al. (2011), which does not use importance-weights; and clipped IPS Strehl et
al. (2010), where for SmoothIGW exhaust we assign the greedy action the
maximum importance weight of 5.

To train the offline models data exhaust is split 80%-10%-10% for training,
validation and testing respectively. Training epochs are performed on the
training set until a decrease in model performance is observed on the
validation set. After training learners are assessed using the average loss on
the test set. Note validation and test evaluation are independent of what data
exhaust was used to train, as the source datasets contain the true label and
therefore admit on-policy evaluation.

For each dataset we run the offline learners 30 times using the exhaust files
generated from the 30 online seeds. For each dataset we compute the average of
the paired (by exhaust) differences between offline learners and then compute
a 90% bootstrap confidence interval.

For further details see Appendix G.

###  4.4 SmoothIGW Increasingly Plays Greedy

Here we show the frequency that SmoothIGW plays its greedy action during the
online experiment described in Section 4.2. This is not a problem for online
performance. Rather, as described in Section 3.1, this only becomes a problem
when attempting to conduct post-hoc analysis with importance-weighting
techniques. We can see in Fig. 3 that by the $1,000^{th}$ learning iteration
in the online experiment over 80% of played actions no longer have usable
importance weights for post-hoc analysis.

###  4.5 CappedIGW Sensitivity to $\kappa_{\infty}$

Here we look at the effect of varying levels of $\kappa_{\infty}$ on online
and offline performance using our 20 Datasets. For these experiments we set
$\kappa_{\infty}$ equal to 2, 4, and 24 (note, $\kappa_{\infty}$ was 4 for
experiments in Section 4.2 and 4.3).

In our experiments the value of $\kappa_{\infty}$ strongly impacted the number
of samples required to estimate $\beta_{t}$ with smaller values of
$\kappa_{t}$ requiring more samples (Fig. 4). This is expected given that
smaller values of $\kappa_{\infty}$ indicate tighter confidence bounds on
$\beta_{t}$.

Figure 4: We see an increase in the number of samples required to estimate
$\beta_{t}$ on each learning update of CappedIGW as $\kappa_{\infty}$ shrinks.

Figure 5: We see very little difference in online performance across our 20
datasets for varying levels of $\kappa_{\infty}$ in CappedIGW.

Figure 6: We tend to see increased offline performance across our 20 datasets
with data exhaust from CappedIGW when $\kappa_{\infty}$ is 4 or 24.

We observe a negligible impact in online performance for the three levels of
$\kappa_{\infty}$ (Fig. 6). In most datasets the average reward seen was
nearly identical at all levels. At the same time we observe a slight increase
in offline utility when training on the online exhaust generated with
$\kappa_{\infty}$ equal to 4 or 24 (Fig. 6).

For further details see Appendix H.

##  5 Additional Related Work

In this section, we briefly highlight related work that we have not already
mentioned in previous sections.

#### Large action spaces with additional assumptions

Unlike contextual bandits with finite action sets, infinite (or very large)
action space contextual bandits are minimax intractable—as observed from the
lower bound in Agarwal et al. (2012). Nonetheless, the setting with infinite
action spaces are highly practical in many real-world scenarios, e.g., in
large-scale recommender systems. To make progress in this setting, researchers
have develop algorithms that work with additional modeling assumptions, such
as contextual bandits with linear functions (Auer, 2002; Li et al., 2010;
Abbasi-Yadkori et al., 2011), with linearly-structured actions and general
(context) function approximation (Foster et al., 2020; Xu & Zeevi, 2020; Zhu
et al., 2022), with Lipschitz/Hölder regression functions (Kleinberg, 2004;
Hadiji, 2019), and with convex functions (Lattimore, 2020). While these
modeling assumptions have lead to fruitful theoretical guarantees, they might
be violated in practice.

#### Large action spaces with smooth regret

An alternative line of research to tackling the large action spaces problems,
in which this paper sits, is to weaker the competing benchmark to avoid the
otherwise minimax negative result. This idea was first proposed in non-
contextual bandits by Chaudhuri & Kalyanakrishnan (2018), where they compete
against the $1-\alpha$th quantile (of reward) instead of highest reward. In
the case with contextual bandits, Krishnamurthy et al. (2020) proposed a
variant of the smooth regret (defined in Section 2.2) for agnostic policy-
based analysis. Krishnamurthy et al. (2020) develops algorithms that are
statistically optimal, but computationally intractable; a computationally
tractable instantiation was later developed in Majzoubi et al. (2020) (but
with slightly weaker statistical performance). We remark here that, even
though our definition of smoothed regret (in Section 2.2) dominates the one
appearing in Krishnamurthy et al. (2020), our approach requires an additional
realizability assumption to reduce to regression (instead of classification);
Foster et al. (2020) shows how to manage misspecification within a reduction
to regression framework.

#### Offline learning in contextual bandits

Offline learning, or off-policy evaluation, considers the problem of learning
a new policy/model only using historic logging data collected from other
online policies. Because offline learning permits learning/testing without
costly online exploration, it has been used in many real-world applications,
such as recommender systems (Thomas et al., 2017) and healthcare industry (Nie
et al., 2021). Focusing on contextual bandits, the method of inverse
propensity scoring (IPS) (Horvitz & Thompson, 1952) has been extensively used
to correct the mismatch between action distributions under the offline and
online policies. Besides the IPS method, the direct method (DM) (Dudík et al.,
2011; Rothe, 2016) has also been used in offline learning where the learner
first learns a reward estimator based on the offline data and then evaluates
the new policies.

##  6 Discussion

This work exhibits a statistical free lunch: the online regret guarantee of an
algorithm is essentially unchanged, while the subsequent offline utility of
the data exhaust is increased.111Although there is a computational cost, this
is arguably mitigated by eliminating the $\operatorname*{arg\,min}$ oracle. We
speculate this is not typical but rather an artifact of the sub-optimality of
the prior technique. In other words, we anticipate that online regret and
offline utility are conflicting objectives that must be traded off, suggesting
a currently unknown Pareto frontier remains to be discovered. The empirical
study of Williams et al. (2021) provides evidence in this direction.

## References

  * Abbasi-Yadkori et al. (2011) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C.  Improved algorithms for linear stochastic bandits.  In _NIPS_ , volume 11, pp. 2312–2320, 2011.
  * Abe & Long (1999) Abe, N. and Long, P. M.  Associative reinforcement learning using linear probabilistic concepts.  In _ICML_ , pp. 3–11. Citeseer, 1999.
  * Agarwal et al. (2012) Agarwal, A., Dudík, M., Kale, S., Langford, J., and Schapire, R.  Contextual bandit learning with predictable rewards.  In _Artificial Intelligence and Statistics_ , pp. 19–26. PMLR, 2012\.
  * Agarwal et al. (2016) Agarwal, A., Bird, S., Cozowicz, M., Hoang, L., Langford, J., Lee, S., Li, J., Melamed, D., Oshri, G., Ribas, O., et al.  Making contextual decisions with low technical debt.  _arXiv preprint arXiv:1606.03966_ , 2016.
  * Auer (2002) Auer, P.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Bietti et al. (2021) Bietti, A., Agarwal, A., and Langford, J.  A contextual bandit bake-off.  _Journal of Machine Learning Research_ , 22(133):1–49, 2021.
  * Blum et al. (1999) Blum, A., Kalai, A., and Langford, J.  Beating the hold-out: Bounds for k-fold and progressive cross-validation.  In _Proceedings of the twelfth annual conference on Computational learning theory_ , pp. 203–208, 1999.
  * Casgrain et al. (2022) Casgrain, P., Larsson, M., and Ziegel, J.  Anytime-valid sequential testing for elicitable functionals via supermartingales.  _arXiv preprint arXiv:2204.05680_ , 2022.
  * Chaudhuri & Kalyanakrishnan (2018) Chaudhuri, A. R. and Kalyanakrishnan, S.  Quantile-regret minimisation in infinitely many-armed bandits.  In _UAI_ , pp. 425–434, 2018.
  * Dudík et al. (2011) Dudík, M., Langford, J., and Li, L.  Doubly robust policy evaluation and learning.  _arXiv preprint arXiv:1103.4601_ , 2011.
  * Foster & Rakhlin (2020) Foster, D. and Rakhlin, A.  Beyond UCB: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pp. 3199–3210. PMLR, 2020.
  * Foster et al. (2018) Foster, D., Agarwal, A., Dudik, M., Luo, H., and Schapire, R.  Practical contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pp. 1539–1548. PMLR, 2018.
  * Foster et al. (2021a) Foster, D., Rakhlin, A., Simchi-Levi, D., and Xu, Y.  Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective.  In _Conference on Learning Theory_ , pp. 2059–2059. PMLR, 2021a.
  * Foster et al. (2020) Foster, D. J., Gentile, C., Mohri, M., and Zimmert, J.  Adapting to misspecification in contextual bandits.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Foster et al. (2021b) Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A.  The statistical complexity of interactive decision making.  _arXiv preprint arXiv:2112.13487_ , 2021b.
  * Gaillard & Gerchinovitz (2015) Gaillard, P. and Gerchinovitz, S.  A chaining algorithm for online nonparametric regression.  In _Conference on Learning Theory_ , pp. 764–796. PMLR, 2015.
  * Gomez-Uribe & Hunt (2015) Gomez-Uribe, C. A. and Hunt, N.  The netflix recommender system: Algorithms, business value, and innovation.  _ACM Transactions on Management Information Systems (TMIS)_ , 6(4):1–19, 2015.
  * Hadiji (2019) Hadiji, H.  Polynomial cost of adaptation for X-armed bandits.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Hazan et al. (2007) Hazan, E., Agarwal, A., and Kale, S.  Logarithmic regret algorithms for online convex optimization.  _Machine Learning_ , 69(2-3):169–192, 2007.
  * Horvitz & Thompson (1952) Horvitz, D. G. and Thompson, D. J.  A generalization of sampling without replacement from a finite universe.  _Journal of the American statistical Association_ , 47(260):663–685, 1952.
  * Kakade et al. (2011) Kakade, S. M., Kanade, V., Shamir, O., and Kalai, A.  Efficient learning of generalized linear and single index models with isotonic regression.  _Advances in Neural Information Processing Systems_ , 24, 2011.
  * Karampatziakis & Langford (2011) Karampatziakis, N. and Langford, J.  Online importance weight aware updates.  In _Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence_ , pp. 392–399, 2011.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kleinberg (2004) Kleinberg, R.  Nearly tight bounds for the continuum-armed bandit problem.  _Advances in Neural Information Processing Systems_ , 17:697–704, 2004.
  * Krishnamurthy et al. (2020) Krishnamurthy, A., Langford, J., Slivkins, A., and Zhang, C.  Contextual bandits with continuous actions: Smoothing, zooming, and adapting.  _Journal of Machine Learning Research_ , 21(137):1–45, 2020.
  * Langford & Zhang (2007) Langford, J. and Zhang, T.  The epoch-greedy algorithm for contextual multi-armed bandits.  _Advances in neural information processing systems_ , 20(1):96–1, 2007.
  * Lattimore (2020) Lattimore, T.  Improved regret for zeroth-order adversarial bandit convex optimisation.  _Mathematical Statistics and Learning_ , 2(3):311–334, 2020.
  * Li et al. (2010) Li, L., Chu, W., Langford, J., and Schapire, R. E.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pp. 661–670, 2010.
  * Li et al. (2015) Li, L., Chen, S., Kleban, J., and Gupta, A.  Counterfactual estimation and optimization of click metrics in search engines: A case study.  In _Proceedings of the 24th International Conference on World Wide Web_ , pp. 929–934, 2015.
  * Majzoubi et al. (2020) Majzoubi, M., Zhang, C., Chari, R., Krishnamurthy, A., Langford, J., and Slivkins, A.  Efficient contextual bandits with continuous actions.  _Advances in Neural Information Processing Systems_ , 33:349–360, 2020.
  * Nie et al. (2021) Nie, X., Brunskill, E., and Wager, S.  Learning when-to-treat policies.  _Journal of the American Statistical Association_ , 116(533):392–409, 2021.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In Wallach, H., Larochelle, H., Beygelzimer, A., d’Alché Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Rothe (2016) Rothe, C.  The value of knowing the propensity score for estimating average treatment effects.  _Available at SSRN 2797560_ , 2016.
  * Simchi-Levi & Xu (2021) Simchi-Levi, D. and Xu, Y.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  _Mathematics of Operations Research_ , 2021.
  * Strehl et al. (2010) Strehl, A., Langford, J., Li, L., and Kakade, S. M.  Learning from logged implicit exploration data.  _Advances in neural information processing systems_ , 23, 2010.
  * Thomas et al. (2017) Thomas, P., Theocharous, G., Ghavamzadeh, M., Durugkar, I., and Brunskill, E.  Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 31(2):4740–4745, Feb. 2017.  doi: 10.1609/aaai.v31i2.19104.
  * Vanschoren et al. (2014) Vanschoren, J., Van Rijn, J. N., Bischl, B., and Torgo, L.  Openml: networked science in machine learning.  _ACM SIGKDD Explorations Newsletter_ , 15(2):49–60, 2014.
  * Vovk (1998) Vovk, V.  A game of prediction with expert advice.  _Journal of Computer and System Sciences_ , 56(2):153–173, 1998.
  * Waudby-Smith & Ramdas (2020) Waudby-Smith, I. and Ramdas, A.  Estimating means of bounded random variables by betting.  _arXiv preprint arXiv:2010.09686_ , 2020.
  * Williams et al. (2021) Williams, J. J., Nogas, J., Deliu, N., Shaikh, H., Villar, S. S., Durand, A., and Rafferty, A.  Challenges in statistical analysis of data collected by a bandit algorithm: An empirical exploration in applications to adaptively randomized experiments.  _arXiv preprint arXiv:2103.12198_ , 2021.
  * Xu & Zeevi (2020) Xu, Y. and Zeevi, A.  Upper counterfactual confidence bounds: a new optimism principle for contextual bandits.  _arXiv preprint arXiv:2007.07876_ , 2020.
  * Zhu & Mineiro (2022) Zhu, Y. and Mineiro, P.  Contextual bandits with smooth regret: Efficient learning in continuous action spaces.  In _International Conference on Machine Learning_ , pp. 27574–27590. PMLR, 2022.
  * Zhu & Nowak (2020) Zhu, Y. and Nowak, R.  On regret with multiple best arms.  _Advances in Neural Information Processing Systems_ , 33:9050–9060, 2020.
  * Zhu et al. (2022) Zhu, Y., Foster, D. J., Langford, J., and Mineiro, P.  Contextual bandits with large action spaces: Made practical.  In _International Conference on Machine Learning_ , pp. 27428–27453. PMLR, 2022.

##  Appendix A Background: Minmax Reduction Design

Our approach is based on the work of Foster et al. (2021b), which we review
here. From this work, we define the Decision-Estimation Coefficient for any
smoothness level $\tau\geq 1$, function class $\mathcal{F}$, context
$x\in\mathcal{X}$, and $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$ estimate
$\widehat{f}$:

$\mathsf{dec}_{\gamma}(\mathcal{F};\widehat{f},x)\vcentcolon=\inf_{P\in\Delta(\mathcal{A})}\sup_{Q\in\mathcal{Q}_{\tau}}\sup_{f\in\mathcal{F}}{\mathbb{E}}_{a\sim
P,a^{\star}\sim
Q}\left[f(x,a)-f(x,a^{\star})-\frac{\gamma}{4}\cdot\left(\widehat{f}(x,a)-f(x,a)\right)^{2}\right],$
(5)

where $f$ is the true loss function, $Q$ is the optimal smoothed policy with
respect to $f$, $P$ is a policy of our choosing, and $\gamma$ is a tunable
learning rate. Note that with this formulation
$\mathsf{Smooth}_{\tau}(x)=-\sup_{Q\in\mathcal{Q}_{\tau}}{\mathbb{E}}_{a\sim
Q}[-f^{\star}(x,a)]$ with respect to results in the paper.

Our goal is to construct $P$ such that we can derive an upper bound on
$\mathsf{dec}$. Because $\mathsf{dec}$ is the difference between the
expectation of $\mathrm{\mathbf{Reg}}_{\mathsf{CB},\tau}$ and
$\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}$ an upper bound on $\mathsf{dec}$ implies
that $\mathrm{\mathbf{Reg}}_{\mathsf{CB},\tau}(T)$ has an upper bound in terms
of $\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)$. This allows us to reduce the CB
problem to simply minimizing the $\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)$ via
any regression oracle $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$ of our choosing.

For our work we prove a bound on the Decision-Estimation Coefficient in
Section B.1 and from there derive a regret bound in Section B.2.

##  Appendix B Proof of Theorem 1

See 1

The proof proceeds by first bounding the Decision-Estimation Coefficient
Foster et al. (2021b), after which the regret bound follows almost directly.

###  B.1 Bounding the Decision-Estimation Coefficient

With respect to any context $x\in\mathcal{X}$ and estimator $\widehat{f}$
obtained from $\mathrm{\mathbf{Alg}}_{\mathsf{Sq}}$, we consider Eq. 5.

######  Lemma 1 (Zhu & Mineiro (2022)).

Fix constant $\gamma>0$ and context $x\in\mathcal{X}$ . For any measures $P$
and $Q$ such that $Q\ll P$, we have

$\displaystyle\sup_{f\in\mathcal{F}}{\mathbb{E}}_{a\sim P,a^{\star}\sim
Q}\left[f(x,a)-f(x,a^{\star})-\frac{\gamma}{4}\cdot\left(\widehat{f}(x,a)-f(x,a)\right)^{2}\right]$
$\displaystyle\leq{\mathbb{E}}_{a\sim
P}\big{[}\widehat{f}(x,a)\big{]}-{\mathbb{E}}_{a\sim
Q}\big{[}\widehat{f}(x,a)\big{]}+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim
P}\left[\left(\frac{dQ}{dP}(a)-1\right)^{2}\right].$

Subsequently we omit the dependence on the context $x\in\mathcal{X}$, and use
abbreviations $f(a)\vcentcolon=f(x,a)$ and
$\widehat{f}(a)\vcentcolon=\widehat{f}(x,a)$.

We first notice that for any $Q\in\mathcal{Q}_{\tau}$ we have $Q\ll P_{t}$ for
$P_{t}$ defined in Eq. 3: since (i) $Q\ll\mu$ by definition, and (ii) $\mu\ll
P_{t}$. Therefore, applying Lemma 1 we have

$\displaystyle{\mathbb{E}}_{a\sim P_{t},a^{\star}\sim
Q}\left[f(a)-f(a^{\star})-\frac{\gamma}{4}\cdot\left(\widehat{f}(a)-f(a)\right)^{2}\right]$
$\displaystyle\leq{\mathbb{E}}_{a\sim
P_{t}}\big{[}\widehat{f}(a)\big{]}-{\mathbb{E}}_{a\sim
Q}\big{[}\widehat{f}(a)\big{]}+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim
P_{t}}\left[\left(\frac{dQ}{dP_{t}}(a)-1\right)^{2}\right].$

Denote $p(a)=\frac{dP_{t}}{d\mu}(a)$ and $q(a)=\frac{dQ}{d\mu}(a)$. Continuing

$\displaystyle{\mathbb{E}}_{a\sim
P_{t}}\big{[}\widehat{f}(a)\big{]}-{\mathbb{E}}_{a\sim
Q}\big{[}\widehat{f}(a)\big{]}+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim
P_{t}}\left[\left(\frac{dQ}{dP_{t}}(a)-1\right)^{2}\right]$
$\displaystyle={\mathbb{E}}_{a\sim\mu}\left[p(a)\cdot\Big{(}\widehat{f}(a)-\beta\Big{)}\right]-{\mathbb{E}}_{a\sim\mu}\left[q(a)\cdot\Big{(}\widehat{f}(a)-\beta\Big{)}\right]+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim\mu}\left[p(a)\cdot\left(\frac{q(a)}{p(a)}-1\right)^{2}\right]$
$\displaystyle={\mathbb{E}}_{a\sim\mu}\left[p(a)\cdot\Big{(}\widehat{f}(a)-\beta\Big{)}\right]-{\mathbb{E}}_{a\sim\mu}\left[q(a)\cdot\Big{(}\widehat{f}(a)-\beta\Big{)}\right]+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim\mu}\left[q(a)\cdot\frac{q(a)}{p(a)}-2q(a)+p(a)\right]$
$\displaystyle={\mathbb{E}}_{a\sim\mu}\left[p(a)\cdot\Big{(}\widehat{f}(a)-\beta\Big{)}\right]+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim
Q}\left[\frac{q(a)}{p(a)}-\gamma\cdot\left(\widehat{f}(a)-\beta\right)\right]-\frac{1}{\gamma}$
$\displaystyle={\mathbb{E}}_{a\sim\mu}\left[p(a)\cdot\max\Big{\\{}0,\widehat{f}(a)-\beta\Big{\\}}\right]+\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim
Q}\left[\frac{q(a)}{p(a)}-\gamma\cdot\max\left\\{0,\widehat{f}(a)-\beta\right\\}\right]$
$\displaystyle\quad+{\mathbb{E}}_{a\sim\mu}\left[\left(p(a)-q(a)\right)\cdot\min\big{\\{}0,\widehat{f}(a)-\beta\big{\\}}\right]-\frac{1}{\gamma}.$
(6)

Now we note the definition of $P_{t}$ implies

$\displaystyle{\mathbb{E}}_{a\sim\mu}\left[p(a)\cdot\max\Big{\\{}0,\widehat{f}(a)-\beta\Big{\\}}\right]$
$\displaystyle\leq\frac{\kappa_{t}\tau}{\gamma};$ (7)

furthermore, the constraints $q(a)\leq\tau$ and $\kappa_{t}\geq 1$ imply

$\displaystyle\frac{1}{\gamma}\cdot{\mathbb{E}}_{a\sim
Q}\left[\frac{q(a)}{p(a)}-\gamma\cdot\max\left\\{0,\widehat{f}(a)-\beta\right\\}\right]$
$\displaystyle\leq\frac{1}{\gamma}{\mathbb{E}}_{a\sim
Q}\left[\frac{1+\gamma\cdot\max\left\\{0,\widehat{f}(a)-\beta\right\\}}{\kappa_{t}}-\gamma\cdot\max\left\\{0,\widehat{f}(a)-\beta\right\\}\right]$
$\displaystyle\leq\frac{1}{\gamma};$ (8)

and finally

$\displaystyle{\mathbb{E}}_{a\sim\mu}\left[\left(p(a)-q(a)\right)\cdot\min\big{\\{}0,\widehat{f}(a)-\beta\big{\\}}\right]$
$\displaystyle\leq(\kappa_{t}-1)\tau\
{\mathbb{E}}_{a\sim\mu}\left[\min\big{\\{}0,\widehat{f}(a)-\beta\big{\\}}\right]$
$\displaystyle\leq 0.$ (9)

Substituting Eq. 7, Eq. 8, and Eq. 9 into Eq. 6 yields

$\displaystyle{\mathbb{E}}_{a\sim P_{t},a^{\star}\sim
Q}\left[f(a)-f(a^{\star})-\frac{\gamma}{4}\cdot\left(\widehat{f}(a)-f(a)\right)^{2}\right]$
$\displaystyle\leq\frac{\kappa_{t}\tau}{\gamma}.$ (10)

###  B.2 Finishing the proof

This part is almost verbatim from Zhu & Mineiro (2022, Thm 1, Appendix A.2),
but included for completeness.

We use abbreviation $f_{t}(a)\vcentcolon=f(x_{t},a)$ for any
$f\in\mathcal{F}$. Let $a^{\star}_{t}$ denote the action sampled according to
the best smoothing kernel within $\mathcal{Q}_{\tau}$ (which could change from
round to round). We let $\mathcal{E}$ denote the good event where the regret
guarantee stated in 2 (i.e.,
$\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)\vcentcolon=\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T,T^{-1})$)
holds with probability at least $1-T^{-1}$. Conditioned on this good event,
following the analysis provided in Foster et al. (2020), we decompose the
contextual bandit regret as follows.

$\displaystyle{\mathbb{E}}\left[\sum_{t=1}^{T}f_{t}^{\star}(a_{t})-f_{t}^{\star}(a^{\star}_{t})\right]$
$\displaystyle={\mathbb{E}}\left[\sum_{t=1}^{T}f_{t}^{\star}(a_{t})-f_{t}^{\star}(a^{\star}_{t})-\frac{\gamma}{4}\cdot\left(\widehat{f}_{t}(a_{t})-f_{t}^{\star}(a_{t})\right)^{2}\right]+\frac{\gamma}{4}\cdot{\mathbb{E}}\left[\sum_{t=1}^{T}\left(\widehat{f}_{t}(a_{t})-f_{t}^{\star}(a_{t})\right)^{2}\right]$
$\displaystyle\leq
T\cdot\frac{\kappa_{\infty}\tau}{\gamma}+\frac{\gamma}{4}\cdot{\mathbb{E}}\left[\sum_{t=1}^{T}\left(\widehat{f}_{t}(a_{t})-f_{t}^{\star}(a_{t})\right)^{2}\right],$

where the bound on the first term follows from Eq. 10. We analyze the second
term below.

$\displaystyle\frac{\gamma}{4}\cdot{\mathbb{E}}\left[\sum_{t=1}^{T}\left(\left(\widehat{f}_{t}(a_{t})-\ell_{t}(a_{t})\right)^{2}-\Big{(}f^{\star}(a_{t})-\ell_{t}(a_{t})\Big{)}^{2}+2\Big{(}\ell_{t}(a_{t})-f^{\star}_{t}(a_{t})\Big{)}\cdot\Big{(}\widehat{f}_{t}(a_{t})-f^{\star}_{t}(a_{t})\Big{)}\right)\right]$
$\displaystyle=\frac{\gamma}{4}\cdot{\mathbb{E}}\left[\sum_{t=1}^{T}\left(\left(\widehat{f}_{t}(a_{t})-\ell_{t}(a_{t})\right)^{2}-\Big{(}f^{\star}_{t}(a_{t})-\ell_{t}(a_{t})\Big{)}^{2}\right)\right]$
$\displaystyle\leq\frac{\gamma}{4}\cdot\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T),$

where on the second line follows from the fact that
${\mathbb{E}}[\ell_{t}(a)\mid x_{t}]=f^{\star}(x_{t},a)$ and $\ell_{t}$ is
conditionally independent of $a_{t}$, and the third line follows from the
bound on regression oracle stated in 2. As a result, we have

$\displaystyle\mathrm{\mathbf{Reg}}_{\mathsf{CB},\tau}(T)\leq\frac{T\kappa_{\infty}\tau}{\gamma}+\frac{\gamma}{4}\cdot\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)+O(1),$

where the additional term $O(1)$ accounts for the expected regret suffered
under event $\neg\mathcal{E}$. Taking
$\gamma=\sqrt{8T\kappa_{\infty}\tau/\mathrm{\mathbf{Reg}}_{\mathsf{Sq}}(T)}$
leads to the desired result.

##  Appendix C Proof of Theorem 2

See 2

We elide the contextual dependence here, as $x_{t}$ is a constant for all of
these operations.

Define

$\displaystyle g(a;\beta)$
$\displaystyle\vcentcolon=\frac{\tau}{1+\gamma\max\left(0,\widehat{f}_{t}(a)-\beta\right)},$
$\displaystyle\beta_{\min}$ $\displaystyle\vcentcolon=\frac{1-\tau}{\gamma},$
$\displaystyle\beta_{\max}$ $\displaystyle\vcentcolon=1,$

where $\widehat{f}_{t}(a)\in[0,1]$. We note the following properties:

$\displaystyle g(a;\beta)$ $\displaystyle\in[0,\tau],$
$\displaystyle\frac{d}{d\beta}g(a;\beta)$ $\displaystyle\in[0,\gamma
g(a;\beta)],$
$\displaystyle\mathbb{E}_{a\sim\mu}\left[g(x,\beta_{\min})\right]$
$\displaystyle\leq 1,$
$\displaystyle\mathbb{E}_{a\sim\mu}\left[g(x,\beta_{\max})\right]$
$\displaystyle\geq 1,$
$\displaystyle\mathbb{E}_{a\sim\mu}\left[g^{2}(x,\beta)\right]$
$\displaystyle\leq\tau\mathbb{E}_{a\sim\mu}\left[g(x,\beta)\right].$

#### Fixed $\beta$ bound

With $n$ samples we can estimate the integral
$z(\beta)\doteq\mathbb{E}_{a\sim\mu}\left[g(a,\beta)\right]$ at any fixed
$\beta$ from the empirical mean $\bar{z}(\beta)$ via

$\displaystyle z(\beta)$
$\displaystyle\in\bar{z}(\beta)\pm\left(\sqrt{\frac{2\mathbb{E}_{a\sim\mu}\left[g^{2}(a,\beta)\right]\ln(2/\delta)}{n}}+\tau\frac{\ln(2/\delta)}{3n}\right)$
$\displaystyle\left(\text{Bernstein}\right)$
$\displaystyle\in\bar{z}(\beta)\pm\left(\sqrt{\frac{2\tau
z(\beta)\ln(2/\delta)}{n}}+\tau\frac{\ln(2/\delta)}{3n}\right)$
$\displaystyle\left(\text{self-bounding}\right)$
$\displaystyle\in\bar{z}(\beta)\pm\left(\frac{1}{2}z(\beta)+\frac{4\tau\ln(2/\delta)}{n}+\tau\frac{\ln(2/\delta)}{3n}\right),$
$\displaystyle\left(\text{AM-GM}\right)$ $\displaystyle z(\beta)$
$\displaystyle\in\left[\frac{2}{3}\left(\bar{z}(\beta)-\frac{26\tau\ln(2/\delta)}{3n}\right),2\left(\bar{z}(\beta)+\frac{26\tau\ln(2/\delta)}{3n}\right)\right].$

with probability at least $1-\delta$.

#### Picking the $\beta$ grid

Suppose

$\frac{26\tau\ln(2/\delta)}{3n}\leq\frac{1}{8},$

then

$z(\beta)\in\left[\frac{2}{3}\bar{z}(\beta)-\frac{1}{12},2\bar{z}(\beta)+\frac{1}{4}\right],$

therefore

$\displaystyle\bar{z}(\beta)\in\left[\frac{3}{16},\frac{3}{8}\right]$
$\displaystyle\implies z(\beta)\in\left[\frac{1}{24},1\right].$

Thus if we can evaluate $\bar{z}(\beta)$ on a grid where it increases by at
most a factor of 2, then we will obtain a $\beta^{*}$ such that
$z(\beta^{*})\in\left[\frac{1}{24},1\right]$.

Using the assumptions,

$\displaystyle\bar{z}^{\prime}\left(\beta\right)$
$\displaystyle\leq\gamma\bar{z}(\beta)$ $\displaystyle\implies\bar{z}(\beta)$
$\displaystyle\leq\bar{z}(\beta_{0})\exp\left(\gamma\left(\beta-\beta_{0}\right)\right)$

hence evaluation over a grid spaced as $\Delta\beta=\log(2)\gamma^{-1}$ will
ensure $\bar{z}(\beta)$ does not increase by more than a factor of 2. Using a
union bound over these points we need

$\displaystyle\frac{\beta_{\max}-\beta_{\min}}{\Delta\beta}$
$\displaystyle\leq\frac{\tau+\gamma}{\log(2)},$
$\displaystyle\frac{26\tau\left(\log(2\log(2))+\log(\tau+\gamma)-\log(\delta)\right)}{3n}$
$\displaystyle\leq\frac{1}{8},$ $\displaystyle
8\frac{26\tau\left(\log(2\log(2))+\log(\tau+\gamma)-\log(\delta)\right)}{3}$
$\displaystyle\leq n,$

thus $n=O\left(\tau\log(\nicefrac{{(\tau+\gamma)}}{{\delta}})\right)$.

##  Appendix D Explanation of Algorithm 3

Note the following discussion is localized to a single invocation of Algorithm
3, and therefore we elide the contextual dependence.

Using the notation from the proof of Theorem 2, note that
$z(\beta)\vcentcolon=\mathbb{E}_{a\sim\mu}\left[g(x,\beta)\right]$ is
continuous and non-decreasing in $\beta$. Fix $\kappa_{\infty}>1$ and define

$\displaystyle\beta_{\kappa_{\infty}}$
$\displaystyle\vcentcolon=\sup\left\\{\beta\left|z(\beta)\leq\kappa_{\infty}^{-1}\right.\right\\},$
$\displaystyle\beta_{1}$
$\displaystyle\vcentcolon=\inf\left\\{\beta\left|z(\beta)\geq
1\right.\right\\}.$

Given a failure probability $\delta$, we will construct an lower confidence
sequence $L_{n}$ for $\beta_{1}$ and an upper confidence sequence $U_{n}$ for
$\beta_{\kappa_{\infty}}$, each with failure probability $\delta/2$, i.e., a
pair of adapted random processes $L_{n}$ and $U_{n}$ satisfying

$\displaystyle\mathbb{P}\left(\forall
n\in\mathbb{N}:\beta_{\kappa_{\infty}}\leq U_{n}\right)$ $\displaystyle\geq
1-\nicefrac{{\delta}}{{2}},$ (11) $\displaystyle\mathbb{P}\left(\forall
n\in\mathbb{N}:L_{n}\leq\beta_{1}\right)$ $\displaystyle\geq
1-\nicefrac{{\delta}}{{2}},$ (12)

where our random processes are defined on the discrete-time filtered
probability space
$(\Omega,\mathcal{F},\left\\{\mathcal{F}_{n}\right\\}_{n\in\mathbb{N}},\mathbb{P})$
generated by the sampling oracle in line 4 of Algorithm 3. Standard techniques
for achieving Eq. 11 and Eq. 12 are described further below: for now, assuming
those properties, note that whenever $L_{n}\geq U_{n}$, we can conclude with
probability at least $(1-\delta)$ that

$\beta\in[U_{n},L_{n}]\implies
z(\beta)\in\left[\frac{1}{\kappa_{\infty}},1\right]$

which is the desired property from Eq. 4. Because $z(\beta)$ is non-decreasing
and we want the smallest $\kappa_{t}$ possible, we use the largest $\beta$,
and hence return $L_{n}$ on line 8 of Algorithm 3.

To achieve Eq. 11 and Eq. 12, we combine betting martingales with a no-regret
algorithm, aka ONS-m. (Waudby-Smith & Ramdas, 2020) To ease exposition, we
describe the lower bound only; the upper bound is analogous. For the lower
bound we define the wealth process

$\displaystyle W^{(-)}_{n}(\nu;\beta)$
$\displaystyle=\prod_{m=1}^{n}\left(1+\nu_{m}\left(1-g(A_{m};\beta)\right)\right),$

where $A_{m}$ is the sequence of actions generated by line 4 of Algorithm 3;
and $\nu_{n}\in[0,(\tau-1)^{-1})$ is a predictable betting sequence (to be
specified below). This wealth process is a non-negative martingale with
initial value of 1 when evaluated at $\beta=\beta_{1}$ and therefore due to
Ville’s inequality

$\mathbb{P}\left(\forall
n\in\mathbb{N}:W^{(-)}_{n}(\nu;\beta)\leq\nicefrac{{2}}{{\delta}}\right)\geq
1-\nicefrac{{\delta}}{{2}}.$

Because $g(\cdot,\beta)$ is non-decreasing in $\beta$, it follows
$L_{n}=\sup\left\\{\beta\left|W_{n}^{(-)}(\nu;\beta)\leq\nicefrac{{2}}{{\delta}}\right.\right\\}$
is a lower confidence sequence for $\beta_{1}$. It remains to specify the
betting process $\nu_{n}$: we use online Newton step to choose bets that
maximize the (log) wealth, using loss $\left(-\log
W^{(-)}_{m}(\cdot,L_{m-1})\right)$, and constraining the bet sequence
$\nu\in[0,\nicefrac{{1}}{{2\tau}}]$ to ensure a bounded gradient.

The upper bound is similar, but using a martingale of the form
$W^{(+)}_{n}(v;\beta)=\prod_{m=1}^{n}\left(1+v_{m}\left(g(A_{m};\beta)-\kappa_{\infty}^{-1}\right)\right),$
and constraining the bet sequence $v\in[0,\nicefrac{{\kappa_{\infty}}}{{2}}]$.

##  Appendix E Proof of Theorem 3

See 3

This uses the notation from Appendix D.

From Waudby-Smith & Ramdas (2020, Corollary 1), $L_{n}$ and $U_{n}$ satisfy
Eq. 11 and Eq. 12 respectively. Therefore, whenever $L_{n}\geq U_{n}$, given
the monotonicity of $g(\cdot;\beta)$ wrt $\beta$, Eq. 4 holds with probability
at least $(1-\delta)$.

##  Appendix F Online Regret Experiment: Additional Details

We perform the online regret experiment using twenty regression datasets
hosted on OpenML (Vanschoren et al., 2014) and released under a CC-
BY222https://creativecommons.org/licenses/by/2.0/ license. The exact data ids
for these datasets are: 150, 422, 1187, 41540, 41540, 42225, 42225, 44025,
44031, 44056, 44059, 44069, 44140, 44142, 44146, 44148, 44963, 44964, 44973,
and 44977.

For large datasets a random subset of $80,000$ examples is selected. Features
in every data set are transformed so that the $i$-th feature in sample
$x_{t}^{i}$ is shifted by $\min_{t}x_{t}^{i}$ and scaled by
$\nicefrac{{1}}{{\max_{t}x_{t}^{i}-\min_{t}x_{t}^{i}}}$. This transformation
is applied to the labels $y_{t}$ as well so that for every label
$y_{t}\in[0,1]$.

During evaluation of SmoothIGW and CappedIGW the contexts $x_{t}$ is revealed
to the learners in batches of eight. The learners then pick an action to play
for each context in the batch. After picking their actions learners then
receive the loss $\ell_{t}(a_{t})=|a_{t}-y_{t}|_{1}$ for each of the selected
actions. This process continues until all examples in a dataset are exhausted.

Both SmoothIGW and CappedIGW assume access to a $\widehat{f}_{t}$ and
SmoothIGW also assumes access to an $\arg\min$ orcale to compute
$\widehat{a}_{t}$. To satisfy these requirements we mirror the implementation
pattern of Zhu & Mineiro (2022) where $\theta$ are learned parameters,
$\widehat{f}_{t}(x,a;\theta):=g(\widehat{a}(x;\theta)-a;\theta)$, and $g$ is
defined so that its global minimizer is $0$. With $\theta:=(u;w;q;z;\zeta)$
our experiment defines $\widehat{a}(x;\theta)=\sigma\left(u+\langle
x,w\rangle\right)$ where $\sigma$ is the sigmoid function and, given
$z=\widehat{a}(x;\theta)-a$,

$\widehat{g}(x,a;\theta)=\begin{cases}q+\langle
w,(z,z^{3/2},z^{2})\rangle&\text{if}\ z\geq 0\\\
q+\langle\zeta,(|z|,|z|^{3/2},|z|^{2})\rangle&\text{if}\ z<0.\\\ \end{cases}.$
(13)

To optimize $\theta$ we use a mean squared error loss with Adam (Kingma & Ba,
2014) in PyTorch (Paszke et al., 2019).

We use the Corral meta-algorithm from Zhu & Mineiro (2022) to select the
smoothness parameter $\tau$ for both SmoothIGW and CappedIGW. The
hyperparameter settings for the meta-algorithm were optimized and fixed
globally to give the best average performance across all experiment datasets.
For SmoothIGW we use $\eta:=0.3$ and select $\tau$ from the set
$\\{2,3.76,7.05,13.24,24.87,46.7,87.7,164.69,309.27,580.77,1090.6,2048\\}$.
For CappedIGW we use $\eta:=0.3$ and select $\tau$ from
$\\{6,9.57,15.28,24.37,38.89,62.05,99.01,157.98,252.08,402.21,641.77,1024\\}$.

##  Appendix G Offline Utility Experiment: Additional Details

For the offline experiment we use data exhaust from the online experiment
which takes the form of
$(x_{t},a_{t},{\mathbb{P}}_{t}(a_{t}),\ell_{t}(a_{t}))$. Because of this the
datasets for the offline experiment are identical to those in the online
experiment as are the dataset transformations, both of which are described in
Appendix F.

The offline learners use the same functional form as the online learners; that
is $f(x,a;\theta):=g(a^{\star}(x;\theta)-a;\theta)$ with the definition of $g$
given in Eq. 13. The offline experiment uses a more complex form for
$a^{\star}(x;\theta)$ than the online learners. Rather than one linear layer
with a sigmoid output the offline learners use a three layer feedforward
neural network with width equal to the number of features in a dataset, ReLU
activation functions, and a sigmoid output.

We optimize offline learner parameters $\theta$ using mean squared error loss
with Adam (Kingma & Ba, 2014) in PyTorch (Paszke et al., 2019). When using
clipped IPS Strehl et al. (2010) we multiply each mean squared error by its
importance weight. It is known that this is not an optimal way to perform
importance updates Karampatziakis & Langford (2011). Even so, the offline
learners still benefit from the importance weighted updates when using
CappedIGW exhaust. During testing our offline learners follow the policy
$\pi^{\star}(x):=a^{\star}(x;\theta)$.

##  Appendix H CappedIGW Sensitivity to $\kappa_{\infty}$: Additional Details

To further understand how $\kappa_{\infty}$ influences experimental outcomes
we look here at the probabilities logged during online analysis along with the
importance weights used during offline analysis. We see in Fig. 8 that for our
20 datasets as $\kappa_{\infty}$ became larger logged CappedIGW probabilities
tended toward 0. In turn, we see a greater spread in offline importance
weights from this data Fig. 8.

Figure 7: As $\kappa_{\infty}$ grows online probability is increasingly near
0.

Figure 8: As $\kappa_{\infty}$ grows offline weight has a greater spread.

Another perspective can be found by looking at the distribution of actions
played by our learners. For this we recorded the distance a learner’s played
action was from what the learner believed the greedy action was. This
perspective is only useful in these experiments due to the unimodal
implementation of $\hat{f}_{t}$ (see Appendix F). We see that as
$\kappa_{\infty}$ increases so to does the spread of actions played around the
believed argmax Fig. 9.

Figure 9: As $\kappa_{\infty}$ grows actions have a greater spread around what
the learners believes the argmax $\hat{a}_{t}$ is.


# Towards Zero-Shot Text-To-Speech for Arabic Dialects

Khai Duy Doanξ Abdul Waheedξ Muhammad Abdul-Mageedξ,γ,λ
ξMBZUAI γThe University of British Columbia λ Invertible AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Zero-shot multi-speaker text-to-speech (ZS-TTS) systems have advanced for
English, however, it still lags behind due to insufficient resources. We
address this gap for Arabic, a language of more than 450 million native
speakers, by first adapting a sizeable existing dataset to suit the needs of
speech synthesis. Additionally, we employ a set of Arabic dialect
identification models to explore the impact of pre-defined dialect labels on
improving the ZS-TTS model in a multi-dialect setting. Subsequently, we fine-
tune the
XTTS111https://docs.coqui.ai/en/latest/models/xtts.html222https://medium.com/machine-
learns/xtts-v2-new-version-of-the-open-source-text-to-speech-model-
af73914db81f333https://medium.com/@erogol/xtts-v1-techincal-notes-eb83ff05bdc
model, an open-source architecture. We then evaluate our models on a dataset
comprising 31 unseen speakers and an in-house dialectal dataset. Our automated
and human evaluation results show convincing performance while capable of
generating dialectal speech. Our study highlights significant potential for
improvements in this emerging area of research in Arabic.

Towards Zero-Shot Text-To-Speech for Arabic Dialects

Khai Duy Doanξ Abdul Waheedξ Muhammad Abdul-Mageedξ,γ,λ ξMBZUAI γThe
University of British Columbia λ Invertible AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Over the last few years, there have been dramatic breakthroughs in speech
synthesis. The core of any text-to-speech (TTS) system lies in its capacity to
transform textual input into natural, coherent speech. This transformation,
however, is not a simple task. It involves the integration of multiple
components. Understanding and dissecting these components - from text
preprocessing and linguistic analysis to acoustic modeling and prosody
generation - is essential for enhancing the quality and naturalness of
synthesized speech and harnessing the full potential of TTS technology in
diverse applications.

While the latest TTS systems, Kong et al. (2020), Popov et al. (2021), Kim et
al. (2020), Kong et al. (2021), can synthesize high-quality speech from single
or multiple speakers, it is still a challenge to synthesize speech from unseen
speakers. Transiting from single-speaker to multi-speaker TTS, the idea of
encoding the speaker information with low dimensional embeddings is applied.
However, in the multi-speaker setting, models can only generate the speech of
the speakers including in the training dataset. Subsequently, generating the
voices of an unseen speaker based on a few seconds of the speaker’s utterance
has emerged as a challenging task. This approach is often referred as zero-
shot multi-speaker TTS (ZS-TTS), defined as a task that aims to synthesize
voices for new speakers not encountered during training, employing only a few
seconds of speech.

Figure 1: A zero-shot multi-speaker TTS system. It synthesizes speech based on
the input text as well as preserves the acoustic features of input speech
segment.

On the other hand, the research landscape for TTS in Arabic remains relatively
unexplored, particularly ZS-TTS systems. ASC Halabi (2016) is considered the
first open-source Arabic dataset curated for speech synthesis, while Kulkarni
et al. (2023) presents a speech corpus for Classical Arabic TTS (ClArTTS). In
Al-Radhi et al. (2020), the authors proposed a continuous residual-based
vocoder for speech synthesis using a small audio-visual phonetically annotated
Arabic corpus. Recently, TunArTTS Laouirine et al. (2024) addresses the lack
of development of end-to-end TTS systems for the Tunisian dialect by
presenting a small dataset including 3+ hours of a male speaker. Furthermore,
Toyin et al. (2023) proposes ArTST, a pre-trained Arabic text and speech
transformer, followed by SpeechT5 Ao et al. (2022). ArTST utilizes ClArTTS for
TTS fine-tuning. Additionally,
XTTS444https://docs.coqui.ai/en/latest/models/xtts.html, presented by
CoquiAI555https://github.com/coqui-ai, has the voice cloning ability in
different languages, including Arabic. Nevertheless, the dataset used to train
XTTS is not revealed. Although some works are carried out for Arabic TTS,
there has been no public research for Arabic ZS-TTS as of the time we are
conducting this research, particularly in multi-dialect settings. In this
paper, we offer the following contributions:

  * •

We re-target an available corpus, QASR Mubarak et al. (2021) to suit the needs
of ZS-TTS in Arabic, acquiring a rich resource for this task.

  * •

We develop highly effective ZS-TTS models for Arabic through fine-tuning XTTS
on the refined QASR corpus, incorporating supplementary Arabic dialect labels.

##  2 Related Works

Sercan et al. Arik et al. (2018) pioneered work on transmitting from multi-
speaker to few-shot TTS. They dive into the task of voice cloning within
sequence-to-sequence neural speech synthesis systems that learn to synthesize
a person’s voice from a few audio samples. Other work such as Cooper et al.
(2020) applies transfer learning for ZS-TTS by extending an improved Tacotron
system to a multi-speaker TTS framework and analyzing the effectiveness of
different speaker embeddings in capturing and modeling characteristics of
unseen speakers. The framework of Cooper et al. (2020) has a challenge to
produce a single embedding to present every utterance characteristic.
Attentron Choi et al. (2020), a novel architecture designed for few-shot text-
to-speech systems, was proposed to overcome this challenge. In addition, Kumar
et al. (2021) was introduced to better capture the prosody of unseen reference
speech such as speaker embedding, pitch, and energy in a zero-shot manner.

Although the performance of previous works is adequate to some extent, they
still suffer from some problems. For example, in the pre-training and fine-
tuning framework, the model is pre-trained on a large dataset and then fine-
tuned with a few audio samples of the target speaker, which is not applicable
to real-world setting. On the other hand, for those methods that are trained
conditionally on a latent style vector they heavily rely on the diversity of
the speakers in the source dataset. Meta-StyleSpeech Min et al. (2021)
addressed these problems by incorporating Style-Adaptive Layer Normalization
(SALN) with two discriminators trained with style prototypes and episodic
training techniques. Following the development trend of TTS systems, SC-
GlowTTS Casanova et al. (2021) explores a flow-based decoder that works in a
zero-shot scenario. Combining GlowTTS Kim et al. (2020) and HiFi-GAN Kong et
al. (2020), SC-GlowTTS is capable of synthesizing speech faster than in real-
time. Adapting the advancement of score-based diffusion model Song et al.
(2020), Kang et al. (2023) present Grad-StyleSpeech. This model excels in
generating highly natural speech with an exceptionally high resemblance to the
voice of a target speaker. Moreover, applying a score-based diffusion model,
Guided-TTS 2 Kim et al. (2022) can be successfully fine-tuned with data of
target speakers without transcription.

The aforementioned works, however, have not yet explored the multilingual TTS,
which can be useful to ZS-TTS in that it can diversify training data. One
exception is YourTTS Casanova et al. (2023), which emerged as the first work
proposing a multilingual approach to zero-shot multi-speaker TTS. Other works
include VALL-E Wang et al. (2023a), VALL-E X Zhang et al. (2023). Instead of
mel-spectrogram, VALL-E Wang et al. (2023a) utilizes discrete audio codec code
Défossez et al. (2022) as speaker representation. VALL-E is trained with
LibriLight, which is a large and diverse dataset including 60k hours of
English speech with over 7000 unique speakers. Soon afterward, the authors
published VALL-E X Zhang et al. (2023) for cross-lingual speech synthesis. The
multi-lingual in-context learning framework empowers VALL-E X to generate
cross-lingual speech while preserving the characteristics of the unseen
speaker, including their voice, emotion, and speech background, using only a
single sentence in the source language.

Inspired by large-scale generative models such as GPT and DALLE, Voicebox Le
et al. (2023) was also presented. Voicebox is trained on a text-guided speech-
infilling task by generating masked speech given surrounding audio and a text
transcript. Voicebox’s text-guided infilling method demonstrates superior
scalability in terms of data, covering various speech-generative tasks.

##  3 XTTS Model

XTTS Eren and The Coqui TTS (2021) 666We refer to XTTSv2 simply as XTTS in our
study. is a multilingual multispeaker speech synthesis model that supports
Arabic (ar) along with English (en), and multiple other languages.

Overall, XTTS can generate natural-sounding audio with as short as three
seconds of reference speech across 15 languages. It is based on autoregressive
modeling trained on discrete audio representations. The model has a VQ-VAE to
discretize audio into discrete tokens and subsequently uses GPT2 Radford et
al. (2019) model to predict these audio tokens based on the input text
conditioned upon latent speaker representation. The computation of speaker
latent is facilitated by the Perceiver model Jaegle et al. (2021), which takes
mel spectrogram as inputs and produces latent vectors representing speaker
information to prefix the GPT decoder. XTTS uses the HifiGAN model to compute
the final audio signal from the GPT2 outputs which reduces the inference
latency.

The empirical findings indicate that the Perceiver model outperforms simpler
encoders, such as Tortoise Betker (2023), and speech prompting models like
Vall-E Wang et al. (2023b), in capturing speaker characteristics. Notably, the
Perceiver exhibits a remarkable consistency in model outputs across various
runs, mitigating the occurrence of speaker shifting between different model
executions. In addition to that, the intrinsic flexibility of the Perceiver is
highlighted by its ability to accommodate multiple references without imposing
any length constraints. This feature facilitates the comprehensive capture of
diverse facets of the target speaker, and the potential to amalgamate
characteristics from different speakers, thereby enabling the creation of a
distinctive and unique voice. In XTTS, input text undergoes BPE tokenization,
and a language token is inserted at the beginning, resulting in a structured
sequence: [bots], [lang], t1, t2, …, tn, [eots]. Speaker latents are obtained
from a mel-spectrogram and these vectors directly condition the model.
Training samples are formed by appending audio tokens to the input sequence:
s1, s2, …, sk, [bots], [lang], t1, t2, …, tn, [eots], [boas], a1, a2, …, a_l,
[eoas]. The three-stage training process for XTTS involves VQVAE, GPT, and
audio decoder training. The three components of XTTS model are demonstrated in
Appendix, Fig.2.

Figure 2: The three stages of training XTTS model. Stage 1. Train the VQ-VAE
to learn the discrete audio tokens representation from audio waveform. Stage
2. A GPT2-based model is trained to autoregressively generate discrete audio
tokens from the concatenation of speaker, text, and discrete audio tokens
embeddings. Stage 3. HifiGAN is trained as a decoder to generate audio
wavefrom from the discrete audio tokens, generated by the GPT2.

XTTS is trained on publicly available datasets across different languages.
Since publicly available data varies for different languages, we believe that
Arabic has a relatively small amount of data compared to other high-resource
languages such as English, German, and Spanish that it supports. Although the
outputs from XTTS seem high quality, developers of the model do not conduct
any evaluation for any languages. To address this gap, we first train XTTS on
approximately 2000 hours of high-quality Arabic speech described in 4.1. We
then perform a comprehensive evaluation using both an automatic metric as well
human evaluation.

##  4 Experiments

###  4.1 Dataset

We use QASR Mubarak et al. (2021) as the training data which contains
approximately 2,000 hours of speech sampled at 16kHz crawled from the
Aljazeera news channel. QASR involves multiple dialects, no label yet, and
includes 1.6 million segments of 27,977 speakers. Transcripts in QASR are
aligned with audio segments using light supervision. One of the primary
considerations for selecting QASR for our experiments is that it has the
speaker identity of audio recordings.

Figure 3:  QASR data distribution across different dialects.

Text-Audio Processing. Because the audios of the QASR dataset is originally
crawled from a news channel, we need to remove the background noise to make
the dataset suitable for training the TTS system. We employ the FRCRN Zhao et
al. (2022) system777https://github.com/alibabasglab/FRCRN to suppress the
background noise of speech audios. Moreover, when exploring the dataset, we
found that some text-audio pairs are mismatched. The problem occurs when two
people are speaking at the same time in the audio segment. To filter out these
mismatched samples, we first employ the Whisper Radford et al. (2022) model to
generate the transcripts of all audio segments. Subsequently, we compute the
word error rate (WER) between the generated and ground-truth transcripts. We
then remove all samples with WER larger than zero.

Dialect Pseudo Labelling. We train our multi-dialect XTTS model on QASR,
however, the original QASR data does not have a dialect associated with each
segment. To overcome this we employ eight dialect identification models to
predict the dialect from the text then we take the label with the highest
cumulative confidence as the final dialect label. The models are collected
from Huggingface 888https://huggingface.co/AMR-KELEG/ADI-
NADI-2023999https://github.com/Lafifi-24/arabic-dialect-
identification101010https://huggingface.co/CAMeL-Lab/bert-base-arabic-
camelbert-mix-did-madar-corpus26111111https://huggingface.co/CAMeL-Lab/bert-
base-arabic-camelbert-msa-did-madar-twitter5. We provide data distribution
across dialects in Figure 3

Train-Test Splits. After the processing steps, there are 17341 remaining
speakers, of which we use 17310 speakers for training and 31 speakers for
evaluation. Those 31 speakers are excluded from training for zero-shot setting
evaluation.

In addition to testing the split of QASR, we use a small amount of in-house
dialect data to evaluate out-of-distribution generation quality. We collect
this data from YouTube and transcribe them using native speakers from the
respective dialects. Our in-house dialectal data includes country-level
dialects from Algeria, Jordan, Palestine, UAE, and Yemen.

###  4.2 Methods

In addition to the pre-trained XTTS model, we develop two models by fine-
tuning XTTS on the curated QASR dataset:

Fine-tuned without dialect token. We fine-tune the model with the same
parameters, vocabulary as the pre-trained model.

Fine-tuned with dialect token. We add a list of 22 dialect tokens (21 dialects
and MSA) to the vocabulary so the vocabulary size increases from 6681 to 6703
entries. To provide the model with the dialect information, we insert the
dialect token after the [lang] token: s1, s2, …, sk, [bots], [lang], [dialect]
t1, t2, …, tn, [eots], [boas], a1, a2, …, a_l, [eoas]. In the embedding layer,
we initialize the weights for new tokens by sampling from the standard normal
distribution.

We train the models for 300,000 steps on two NVIDIA A100-SXM4 40GB with a
batch size of 6 and gradient accumulation steps of 38. We run the evaluation
with three settings: the pre-trained XTTS model as baseline, fine-tuned
without dialect token, and fine-tuned with dialect token.

###  4.3 Evaluation

Speaker Similarity. We use speaker embedding cosine similarity (SECS) as the
quantitative metric evaluation. To compute the speaker embedding vector of
speech audio, we employ the Resemblyzer package. Afterwards, we get the cosine
similarity score between two speaker embedding vectors, which is in the range
[-1, 1], where a larger value indicates a higher similarity of input vectors.
For each sample synthesis, we randomly pick a reference utterance, which has
at least 5-second duration length, from the same speaker. We run the
experiment three times and report the average score.

Word Error Rate. In order to quantify the consistency of generated voice with
the ground-truth transcript, we employ the Word Error Rate (WER). We extract
the transcript from generated audio by using Whisper-large Radford et al.
(2022). The package Jiwer 121212https://github.com/jitsi/jiwer is used to
compute the WER.

Human Evaluation. We also conduct human evaluation to quantify the quality of
our models when it comes to naturalness and fluency. To conduct the human
evaluation, we first prepare a guideline that explains the task to human
annotators, including the ranking system employed (between 1 and 5, with
increments of 0.5) where one is lowest and 5 is highest. We then propagate the
synthesized audio for annotators to start the job. We generate ten audio
segments from each model and employ five speakers for evaluation. We conduct
the human evaluation only on the in-house dialect dataset, which was labeled
under strict supervision. Check Appendix A to listen to the generated audio
samples.

##  5 Results and Discussion

Model | WER | SECS
---|---|---
baseline | 6.42 | 0.755
ft w/o dialect token | 16.79 | 0.766
ft w/ dialect token | 17.96 | 0.766
Table 1: Evaluation results on QASR unseen speakers. Model | WER | SECS | MOS
---|---|---|---
baseline | 47.16 | 0.79 | 3.61
ft w/o dialect token | 57.47 | 0.806 | 3.53
ft w/ dialect token | 62.74 | 0.825 | 3.19
Table 2: Evaluation results on Speech-Home-Dataset with real data of Arabic
dialects.

We fine-tune the XTTS model with two settings on roughly 472 hours of multi-
dialectal Arabic speech data. We report automatic evaluation metrics SECS and
WER on held-out data 4.1 in Table 1. Our automatic evaluation reveals that
while baseline outperforms the other two models in terms of WER (6.42 vs 16.79
and 17.96), the SECS shows that the two fine-tuned models are superior. The
same scenario happens on the in-house Arabic dialect dataset, as shown in
Table 2. This result shows that while the fine-tuned models are better in
preserving the acoustic features of the reference speaker, they mess up in
mapping the text units to the corresponding speech units. Although we have
filtered out samples with high WER based on the Whisper model, we believe that
the training dataset requires further refinement to improve the performance of
the models.

In addition to the held-out dataset, we probe the performance of all models on
the clean, labeled with strict supervision, in-house dialect dataset. We
report the WER, SECS, and MOS score in Table 2. Based on our automatic
evaluation, we find that with the dialect dataset, the setting fine-tuned with
dialect token outperforms the other models with a larger margin (0.035) than
that of QASR held-out samples (0.011). In addition to this, we also conducted
human evaluation on dialect data and we found that fine-tuning with dialect
gives on-par results compared to the supervised baseline, while also being
capable of generating dialectal speech. This suggests that even though we only
use the pseudo dialect label, the dialect information does help to improve the
quality of generated speech for the Arabic dialect.

##  6 Conlusion

Generating speech from text has many critical applications particularly for
individuals with visual and hearing impairments, enabling them to access and
interact with digital content through screen readers, spreading across
different regions and languages. However, previous research focuses on
building text-to-speech systems for high-resource languages and often lacks
comprehensive evaluation. In this work, we address this gap by fine-tuning two
models for Arabic text-to-speech generation. We then conduct a thorough
evaluation and comparative analysis of pre-trained with ours. Findings reveal
that although our models are inconsistent in mapping phonemes to sounds, they
more precisely preserve acoustic features compared to the baseline.

In future work, we intend to train our models on extensive high-quality data
while ensuring that the training data is representative of the diverse
linguistic varieties of Arabic. For instance, we would like to extract a
subset of the QASR dataset and perform manual labeling to create a small,
clean dataset. Subsequently, we will employ semi-supervised learning
techniques to enhance our models’ performance. Finally, upon acceptance of our
work, we intend to release the model weights, inference pipeline, and training
protocols.

##  7 Limitations

Despite the models are capable of generating natural-sounding speech,
comprehensible by native speakers, which is often indistinguishable from
reference speakers, our work has some clear limitations which we discuss
below:

  * •

Data. Gender-wise distribution is severely imbalanced. For example, 69% of
1.6M segments are male while only 6% are female and the rest remain unknown.
This also limits our model’s capability to generate high-quality speech for
female reference speakers.

  * •

Pseudo Dialect Label. Although nine dialect identification models were used to
assign dialect labels to each sample, these labels are considered pseudo-
labels. We believe that obtaining more accurate labels will improve the
model’s performance.

  * •

Training. While we train our models on 300,000 steps with a cumulative batch
size of 228, the original models are trained for significantly more steps
(data). To overcome this, we continuously train our models and intend to
update the results as we get better checkpoints.

## Acknowledgments

We acknowledge support from Canada Research Chairs (CRC), the Natural Sciences
and Engineering Research Council of Canada (NSERC; RGPIN-2018-04267), the
Social Sciences and Humanities Research Council of Canada (SSHRC;
895-2020-1004; 895-2021-1008), Canadian Foundation for Innovation (CFI;
37771), Digital Research Alliance of Canada,131313https://alliancecan.ca and
UBC Advanced Research Computing-Sockeye.141414https://arc.ubc.ca/ubc-arc-
sockeye

## References

  * Al-Radhi et al. (2020) Mohammed Salah Al-Radhi, Omnia Abdo, Tamás Gábor Csapó, Sherif Abdou, Géza Németh, and Mervat Fashal. 2020.  A continuous vocoder for statistical parametric speech synthesis and its evaluation using an audio-visual phonetically annotated arabic corpus.  _Computer Speech & Language_, 60:101025.
  * Ao et al. (2022) Junyi Ao, Rui Wang, Long Zhou, Chengyi Wang, Shuo Ren, Yu Wu, Shujie Liu, Tom Ko, Qing Li, Yu Zhang, Zhihua Wei, Yao Qian, Jinyu Li, and Furu Wei. 2022.  Speecht5: Unified-modal encoder-decoder pre-training for spoken language processing.  _Preprint_ , arXiv:2110.07205.
  * Arik et al. (2018) Sercan Ömer Arik, Jitong Chen, Kainan Peng, Wei Ping, and Yanqi Zhou. 2018.  Neural voice cloning with a few samples.  _CoRR_ , abs/1802.06006.
  * Betker (2023) James Betker. 2023.  Better speech synthesis through scaling.  _arXiv preprint arXiv:2305.07243_.
  * Casanova et al. (2021) Edresson Casanova, Christopher Shulby, Eren Gölge, Nicolas Michael Müller, Frederico Santos de Oliveira, Arnaldo Candido Junior, Anderson da Silva Soares, Sandra Maria Aluisio, and Moacir Antonelli Ponti. 2021.  Sc-glowtts: an efficient zero-shot multi-speaker text-to-speech model.  _Preprint_ , arXiv:2104.05557.
  * Casanova et al. (2023) Edresson Casanova, Julian Weber, Christopher Shulby, Arnaldo Candido Junior, Eren Gölge, and Moacir Antonelli Ponti. 2023.  Yourtts: Towards zero-shot multi-speaker tts and zero-shot voice conversion for everyone.  _Preprint_ , arXiv:2112.02418.
  * Choi et al. (2020) Seungwoo Choi, Seungju Han, Dongyoung Kim, and Sungjoo Ha. 2020.  Attentron: Few-shot text-to-speech utilizing attention-based variable-length embedding.  _Preprint_ , arXiv:2005.08484.
  * Cooper et al. (2020) Erica Cooper, Cheng-I Lai, Yusuke Yasuda, Fuming Fang, Xin Wang, Nanxin Chen, and Junichi Yamagishi. 2020.  Zero-shot multi-speaker text-to-speech with state-of-the-art neural speaker embeddings.  _Preprint_ , arXiv:1910.10838.
  * Défossez et al. (2022) Alexandre Défossez, Jade Copet, Gabriel Synnaeve, and Yossi Adi. 2022.  High fidelity neural audio compression.  _arXiv preprint arXiv:2210.13438_.
  * Eren and The Coqui TTS (2021) Gölge Eren and The Coqui TTS. 2021.  Coqui TTS.
  * Halabi (2016) Nawar Halabi. 2016.  _Modern standard Arabic phonetics for speech synthesis_.  Ph.D. thesis, University of Southampton.
  * Jaegle et al. (2021) Andrew Jaegle, Felix Gimeno, Andrew Brock, Andrew Zisserman, Oriol Vinyals, and Joao Carreira. 2021.  Perceiver: General perception with iterative attention.  _Preprint_ , arXiv:2103.03206.
  * Kang et al. (2023) Minki Kang, Dongchan Min, and Sung Ju Hwang. 2023.  Grad-stylespeech: Any-speaker adaptive text-to-speech synthesis with diffusion models.  _Preprint_ , arXiv:2211.09383.
  * Kim et al. (2020) Jaehyeon Kim, Sungwon Kim, Jungil Kong, and Sungroh Yoon. 2020.  Glow-tts: A generative flow for text-to-speech via monotonic alignment search.  _Preprint_ , arXiv:2005.11129.
  * Kim et al. (2022) Sungwon Kim, Heeseung Kim, and Sungroh Yoon. 2022.  Guided-tts 2: A diffusion model for high-quality adaptive text-to-speech with untranscribed data.  _Preprint_ , arXiv:2205.15370.
  * Kong et al. (2020) Jungil Kong, Jaehyeon Kim, and Jaekyoung Bae. 2020.  Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis.  _Preprint_ , arXiv:2010.05646.
  * Kong et al. (2021) Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. 2021.  Diffwave: A versatile diffusion model for audio synthesis.  _Preprint_ , arXiv:2009.09761.
  * Kulkarni et al. (2023) Ajinkya Kulkarni, Atharva Kulkarni, Sara Abedalmonem Mohammad Shatnawi, and Hanan Aldarmaki. 2023.  Clartts: An open-source classical arabic text-to-speech corpus.  _Preprint_ , arXiv:2303.00069.
  * Kumar et al. (2021) Neeraj Kumar, Srishti Goel, Ankur Narang, and Brejesh Lall. 2021.  Normalization Driven Zero-Shot Multi-Speaker Speech Synthesis.  In _Proc. Interspeech 2021_ , pages 1354–1358.
  * Laouirine et al. (2024) Imen Laouirine, Rami Kammoun, and Fethi Bougares. 2024.  TunArTTS: Tunisian Arabic text-to-speech corpus.  In _Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024)_ , pages 16879–16889, Torino, Italia. ELRA and ICCL.
  * Le et al. (2023) Matthew Le, Apoorv Vyas, Bowen Shi, Brian Karrer, Leda Sari, Rashel Moritz, Mary Williamson, Vimal Manohar, Yossi Adi, Jay Mahadeokar, and Wei-Ning Hsu. 2023.  Voicebox: Text-guided multilingual universal speech generation at scale.  _Preprint_ , arXiv:2306.15687.
  * Min et al. (2021) Dongchan Min, Dong Bok Lee, Eunho Yang, and Sung Ju Hwang. 2021.  Meta-stylespeech : Multi-speaker adaptive text-to-speech generation.  _Preprint_ , arXiv:2106.03153.
  * Mubarak et al. (2021) Hamdy Mubarak, Amir Hussein, Shammur Absar Chowdhury, and Ahmed Ali. 2021.  QASR: QCRI aljazeera speech resource a large scale annotated Arabic speech corpus.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 2274–2285, Online. Association for Computational Linguistics.
  * Popov et al. (2021) Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail A. Kudinov. 2021.  Grad-tts: A diffusion probabilistic model for text-to-speech.  _CoRR_ , abs/2105.06337.
  * Radford et al. (2022) Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. 2022.  Robust speech recognition via large-scale weak supervision.  _Preprint_ , arXiv:2212.04356.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Song et al. (2020) Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. 2020.  Score-based generative modeling through stochastic differential equations.  _CoRR_ , abs/2011.13456.
  * Toyin et al. (2023) Hawau Olamide Toyin, Amirbek Djanibekov, Ajinkya Kulkarni, and Hanan Aldarmaki. 2023.  Artst: Arabic text and speech transformer.  _Preprint_ , arXiv:2310.16621.
  * Wang et al. (2023a) Chengyi Wang, Sanyuan Chen, Yu Wu, Ziqiang Zhang, Long Zhou, Shujie Liu, Zhuo Chen, Yanqing Liu, Huaming Wang, Jinyu Li, Lei He, Sheng Zhao, and Furu Wei. 2023a.  Neural codec language models are zero-shot text to speech synthesizers.  _Preprint_ , arXiv:2301.02111.
  * Wang et al. (2023b) Chengyi Wang, Sanyuan Chen, Yu Wu, Ziqiang Zhang, Long Zhou, Shujie Liu, Zhuo Chen, Yanqing Liu, Huaming Wang, Jinyu Li, Lei He, Sheng Zhao, and Furu Wei. 2023b.  Neural codec language models are zero-shot text to speech synthesizers.  _Preprint_ , arXiv:2301.02111.
  * Zhang et al. (2023) Ziqiang Zhang, Long Zhou, Chengyi Wang, Sanyuan Chen, Yu Wu, Shujie Liu, Zhuo Chen, Yanqing Liu, Huaming Wang, Jinyu Li, Lei He, Sheng Zhao, and Furu Wei. 2023.  Speak foreign languages with your own voice: Cross-lingual neural codec language modeling.  _Preprint_ , arXiv:2303.03926.
  * Zhao et al. (2022) Shengkui Zhao, Bin Ma, Karn N. Watcharasupat, and Woon-Seng Gan. 2022.  Frcrn: Boosting feature representation using frequency recurrence for monaural speech enhancement.  In _ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 9281–9285.

##  Appendix A Appendix

XTTS baseline

https://arabicnlp.aidaform.com/baseline

Fine-tuned without dialect token

https://arabicnlp.aidaform.com/fine-tuned-without-dialect-token

Fine-tuned with dialect token

https://arabicnlp.aidaform.com/fine-tuned-with-dialect-token