# QCD Reference Frames and False Jet Individualism

Lawrence Lee<EMAIL_ADDRESS>Charles Bell  John Lawless  Emery
Nibigira  University of Tennessee, Knoxville, Tennessee, 37996

###### Abstract

In collider physics, the properties of hadronic jets are often measured as a
function of their lab-frame momenta. However, jet fragmentation must occur in
the particular rest frame of all color-connected particles. Since this frame
need not be the lab frame, the fragmentation of a jet depends on the
properties of its sibling objects. This non-factorizability of jets has
consequences for jet techniques such as jet tagging, boosted boson
measurements, and searches for physics Beyond the Standard Model. In this
paper, we will describe the effect and show its impact as predicted by
simulation.

At particle colliders, collimated sprays of hadrons known as jets are commonly
produced. Roughly, jet activity is the collider signature for parton
production in scattering processes. QCD confinement forbids free particles
from carrying color charge such that a fragmentation and hadronization process
yields an observable jet of color-singlet hadrons. This process results in
small angle particle production, which leads to the observed collimation of
fragmentation products.

Experiments measure the momenta and properties of these hadrons and cluster
the reconstructed objects into jets using various algorithms [1, 2]. The
properties of the aggregate jet objects are roughly used as a proxy for the
properties of the initiating partons in some leading-order approximation [3].
In this approximation, an initiating parton will fragment into additional
partons with energies as dictated by non-perturbative fragmentation functions.
The overall particle multiplicity and the distribution of energy across these
particles is stochastically determined by these fragmentation functions.

Beyond the measurement of a four-momentum, modern collider experiments
frequently measure the internal structure of a jet, usually to determine the
“origin” of the jet. Classical methods to determine if a jet originated from
heavy-flavor quarks or $\tau$ leptons long predate the Large Hadron Collider
(LHC) [4]. Within the LHC era, additional tools such as quark vs. gluon
($q/g$) tagging and the industry of jet substructure continue to use the
distribution of jet constituents as a discriminating tool [5, 6, 3, 7]. Both
angular and longitudinal distributions of energy flow can carry crucial
information about the origin of a jet 111More unconventional signatures can
also lead to anomalous distribution of energy within a jet due to displaced
decays, showering via a hidden dark sector, and via other mechanisms [42, 43,
44]..

In the jet physics industry, it is common to consider a jet to be defined by
its progenitor particle species and its momentum; e.g., a light quark jet of a
particular momentum should have a set of properties drawn from the same
distributions as every other light quark jet of that momentum scale. Under
this jet individualism view, each jet is assumed to have a largely independent
fragmentation process, modulo small-but-measurable colorflow effects [9, 10,
11]. We may obtain independent samples of jets in a particular momentum value
from other physical processes in data to develop data-driven background
estimates, building flavor- and momentum-dependent templates for jet structure
distributions [12, 13, 14, 15]. In flavor-tagging, it is often stated that an
experiment has a particular tagging performance for $b$-jets with a given
momentum.

In this paper, we will present an argument that, in retrospect, seems obvious:
The ubiquitous experimental assumption that jets of a given flavor and
momentum can be thought of as independent, identically-distributed objects is
invalidated by a simple, first-principles consideration. We describe a
hadronic jet’s color rest frame dependence, example processes where this
effect can be observed, and how different event generators model these
effects. We then identify techniques where the effect is under-appreciated at
modern experiments and explain a potential strategy to use this effect for
process discrimination.

Figure 1: Illustration of some example color-flow topologies at a lepton
collider. (Left) The collision of two leptons (purple) is producing two color
singlets, each decaying to a $q\bar{q}$ pair. The color rest frames are the
frames where each of the color-connected $q\bar{q}$ systems is at rest.
(Right) Another collision of leptons producing a “Mercedes star” trijet event
where the $q\bar{q}$ system is recoiling off of a high momentum gluon. In this
case, all three initial partons are color connected, and the color frame is
the same as the lab frame. Cones schematically represent the fragmentation and
hadronization process that gives a jet.

Jet properties are often discussed as a function of the jet’s momentum or
energy as seen in the detector. We think about the fragmentation properties of
an $X$ GeV jet as a function of its kinematics. In collider data analysis, it
is common to find “standard candles” of kinematically similar jets from well-
understood processes for calibration. For example, we can calibrate jet
measurements in well-balanced dijet events and use that understanding in
searches for a new particle decaying to jets with similar kinematics [16, 17].

This way of thinking about jets relies on the assumption that kinematically
similar jets of similar origin are all produced from the same underlying
physics distributions. The angular distribution of particles, the energy
sharing between them, and the total number of final state particles in a jet
are assumed to be entirely dictated by the kinematics and origin of the jet.
However, this jet individualism assumption and our ordinary language in jet
physics use the lab frame momentum to discuss these properties.

This assumption fails once requiring that observers in all frames must have a
Lorentz-consistent view of these jets. Since one can boost into a frame where
that lab-frame $X$ GeV jet is now $Y$ GeV, not all the properties of a jet can
be solely defined by its lab-frame momentum. There must be a special frame in
which a parton’s fragmentation occurs. The only well-defined special frame for
QCD fragmentation is the rest frame of all color-connected objects, or to
leading-order, the rest frame of the relevant color dipoles.

The clearest example of this effect is in a popular jet observable – the
particle multiplicity [14, 15, 18, 19, 20]. While measuring this by counting
the number of charged particle tracks within the jet is infrared and collinear
(IRC) unsafe, it’s a common observable for jet discrimination in practice.
It’s well established that the average $n_{trk}$ of these jets is strongly
dependent on momentum scale; jets at larger momentum contain more particles
[19]. However, since observers in all Lorentz frames must agree on the
_number_ of particles produced in the fragmentation process, there must be a
preferred frame in which the fragmentation function is valid. To understand
the particle multiplicity of a jet, not only is the jet’s momentum needed, but
all jets color-connected to its “initiating” partons need to be considered, as
its the jet’s momentum in the _“color rest frame”_ (or maybe “ _center of
color_ ” frame) that dictates the fragmentation behavior. Instead of
considering individual jets in the lab frame, jet fragmentation must be
considered in the rest frame of all color-sibling particles.

This Frame of Fragmentation and Showering (FFS) effect is at odds with many of
the assumptions in modern experimental jet physics at the LHC where lab frame
fragmentation is assumed and process- and color-flow-dependent effects are
usually ignored 222The effects of color flow on the jet pull observable have
been measured at the LHC [9, 10, 11]. In these measurements, the fragmentation
patterns of pairs of jets is used to infer parton-level color connection..
This effect can lead to large differences in fragmentation patterns in very
common final states. A simple illustration can be seen in the collision of two
color-singlet fundamental particles, like those at lepton colliders. In
multijet final states at symmetric $e^{+}e^{-}$ colliders from pure QCD
processes, the color rest frame is the same as the lab frame, since all
outgoing partons are color connected and there is no net momentum in the lab
frame. However, if two jets are produced in the decay of a $Z$ boson, the
color rest frame is the rest frame of the $Z$, which may be significantly
boosted with respect to the lab frame. The fragmentation of these jets is set
by the energy scale $m_{Z}/2$ and has no dependence on the energy measured by
the detector or the boost of the $Z$ 333This was explicitly noted in Ref.
[45].. The same is true for any hadronically-decaying color singlet.

In analyses looking for boosted vector bosons $V$ decaying hadronically, the
signal jet fragmentation is set by $m_{V}/2$, whereas multijet backgrounds
most likely have complex color connections with the whole final state (and the
beam remnant at hadron colliders), which leads to very different underlying
fragmentation distributions. In the case of the “Mercedes” star topology that
led to the discovery of the gluon, two quarks and one gluon are produced. The
color octet gluon is color connected to both of the color triplet quarks. In
such cases, the fragmentation frame is the rest frame of all three jet
objects, which at a lepton collider, will be the same as the lab frame. The
difference between these color topologies is illustrated in Figure 1. The
effect may be even larger at hadron colliders like the LHC. In QCD multijet
processes at hadron colliders, in addition to potential color connections
between final state jets, color connection to high-energy beam remnants can
lead to very highly boosted color rest frames.

To investigate how the color rest frame dependence of jet fragmentation is
handled by Monte Carlo generators, samples were produced with various parton
shower models. MadGraph5_aMC@NLO 3.3.1 [23] was used to produce 50,000 parton-
level events of two processes: $e^{+}e^{-}\to jjj$ and $e^{+}e^{-}\to ZZ\to
jjjj$, both with a collision energy of $\sqrt{s}=1$ TeV. In the first process,
the color rest frame is coincident with the lab frame, such that jet
observables show an expected lab-frame momentum dependence. In the second, the
color rest frames are always the rest frames of the $Z$ bosons such that some
jet observables will be set by $m_{Z}/2$ and not scale with the lab-frame
momentum.

These parton-level events were then showered using three different models:
Pythia 8.306 [24, 25] using “simple showers,” Vincia [26], and Herwig 7.2.2
[27, 28]. Jet clustering was performed at particle level using Fast-Jet [29]
as interfaced in the Delphes 3.5.1 [30] framework. These particle-level truth
jets were clustered using the anti-kt algorithm with an $R=0.4$ radius
parameter [2]. To decouple the FFS effect from the fragmentation differences
between quarks and gluons, gluon-initiated jets are not considered in these
studies by requiring that, within the jet cone, the highest momentum parton in
the particle record is not a gluon. For similar reasons, $b$-jets are also
excluded.

We define $n_{x}$ as the minimum number of particles in a jet that give $x\%$
of the jet’s total momentum. Figure 2 shows $n_{90}$, the minimum number of
particles that could account for 90% of the jet’s energy as a function of the
lab-frame momentum of the jet. While $n_{90}$ varies with the lab-frame
momentum for $e^{+}e^{-}\to jjj$, this depedence is significantly weaker in
the $e^{+}e^{-}\to ZZ\to jjjj$ case. Figure 2 also shows the lab-frame
momentum dependence of the average multiplicity $\langle n_{90}\rangle$,
comparing the three shower models considered. Since each sample uses the same
matrix element level events, statistical uncertainties can be ignored up to
the parton shower level. All considered models demonstrate the FFS effect in
the process dependence of the mean at high momentum. While small differences
exist, the qualitative behaviors are similar. For jets with a measured
momentum of 200 GeV, differences in $\langle n_{90}\rangle$ as large as
roughly 50% are predicted for different color topologies; this FFS effect can
be sizable at typical collider energy scales.

Figure 2: (Top) Split violin plots showing the normalized $n_{90}$
distributions, as modeled in Pythia using the “simple shower” model, for two
$ee$ collider processes as a function of lab-frame momentum. In $ee\to jjj$
(blue, left), the color rest frame and lab frame are coincident, and the
particle multiplicity is a function of the momentum. However, in $ee\to ZZ\to
jjjj$ (orange, right), in which jets obtain large momentum from boosted color
rest frames, the dependence is significantly weaker. The means of each
distribution are shown as markers. (Bottom) The mean $\langle n_{90}\rangle$
is shown as a function of lab-frame jet momentum for multiple shower models.
Herwig, Pythia, and Vincia show similar behaviors. All samples use the same
matrix element events such that they are statistically identical up to the
parton shower model.

Despite the fact that this effect is modeled in modern simulations, the
typical practicing collider experimentalist ignores it when designing
experiments and analyses. The assumption that a light jet of 100 GeV is a
light jet of 100 GeV will break down from a color-connection dependence
effect. This has implications on many of the jet techniques used in modern
collider physics.

In particular, this FFS effect may have significant implications on how jet
tagging is done. Jet tagging algorithms try to gain insight into the origin of
a jet using the observable properties of its shower. In the design, training,
calibration, and validation of these taggers, the jet individualism assumption
is heavily used.

The tagging method with the largest tradition in hadron collider physics is
$b$-tagging. Simple $b$-taggers use the large lifetime of B hadrons to
identify displaced decay products within a jet, by observing large impact
parameter tracks or displaced track vertices. Modern $b$-taggers use much more
information about the jet, often employing deep neural networks with a large
amount of low-level information about the jet, such that these taggers may be
sensitive to FFS effects [31, 32].

Training $b$-taggers at high $p_{T}$ without controlling for the color rest
frame may lead to incorrect interpretation of selection efficiencies or non-
optimal performance. In Ref. [31], the ATLAS experiment describes their
$b$-tagging training procedure: “… the new Run 2 $b$-tagging algorithm
training strategy is based on the use of a hybrid sample composed of both the
baseline $t\bar{t}$ event sample and a dedicated sample of $Z^{\prime}$
decaying into hadronic jet pairs.” This $Z^{\prime}$, referring to a heavy,
color singlet, $Z$-like resonance, decays to $b\bar{b}$ pairs in these
samples. The $Z^{\prime}$ mass is set to $4$ TeV and a large range of jet
momenta are populated. For nonzero $Z^{\prime}$ momentum, the lab frame
momentum of the jets and the color rest frame momentum will differ. The
fragmentation will be pinned to the $m_{Z^{\prime}}/2$ scale and may not
represent $b$-jets from other processes at similar lab-frame momentum scales.
Especially as modern taggers use more information about the jets in advanced
machine learning techniques, these tools may become more sensitive to the FFS
effect in ways that are difficult to control.

Distinguishing quark-initiated and gluon-initiated jets is a popular technique
at modern colliders [14, 15, 33, 5]. Early in the LHC, these $q/g$ tagging
techniques used the track multiplicity, jet width, and other characteristics
to differentiate these jets, taking advantage of the gluon’s larger color
factor. Modern techniques include using lower level information with machine
learning techniques. LHC experiments build templates of these variables in
dedicated quark- and gluon-enriched control regions to inform taggers used in
data analyses, particularly those looking for quark-dominated processes [34].
Despite some structural differences between quark and gluon jets, the
differences are subtle and vary greatly with momentum [14, 15]. Since the
fragmentation will take place in the color rest frame, jets from the decay of
a boosted color singlet may be easily misidentified, particularly in decays
involving gluons.

These $q/g$ discrimination efforts have assumed jet individualism, without
regard to sibling jets. Community-wide $q/g$ discrimination challenges have
published shared ntuple datasets at the jet level and not the event level
[35]. A host of ML techniques have been engineered to take the properties of
individual jets as inputs. A recent experimental review of jet substructure at
the LHC, Ref. [7], when discussing the jet inputs used for a $q/g$
discriminator, uses the phrase “Since the distributions of these variables
depend on $\eta$, $p_{T}$,…”, which emphasizes the lab-frame, jet
individualistic assumptions throughout the field [36].

As put clearly in Ref. [37], “… there are well-known caveats to this picture
of jet generation, which go under the name of ‘sample dependence’.” Such
event-level effects are then argued to be small [37, 14] and subsequently
ignored. “Here, we assume that sample-dependent effects can either be
quantified or mitigated …” [37]. We argue that there exist sizable sample-
dependent effects that are neither simple to quantify nor to mitigate.

A particularly extreme example of how the FFS effect may affect the goals of
$q/g$ tagging efforts is in the tagging of jets from vector boson fusion (VBF)
and scattering (VBS) processes. At hadron colliders, VBF/VBS processes give
rise to two quark jets that are, at leading order, color connected to only the
beam remnants, and to nothing else in the event. Backgrounds for analyses
looking to measure these processes often give pure QCD (i.e., gluon enriched)
jets such that $q/g$ discrimination methods are attractive and often used [38,
39, 40].

However, each quark jet that emerges from the VBF/VBS process will fragment in
the color rest frame of the highly boosted color dipole formed with the
relevant beam remnant. At the LHC, these frames are highly boosted with
respect to the lab frame, and in detailed fragmentation observables, these
jets will look nothing like the typical jets used to train and characterize
such taggers. To successfully $q/g$-tag VBF/VBS processes, dedicated template
distributions would need to be derived or existing templates would need to be
altered to account for the FFS effect and somehow control for the beam remnant
momentum. None of which may be possible.

On the other hand, the FFS effect could be exploited for process
discrimination. In searches for boosted color singlets decaying to jets, the
details of the fragmentation would look very different from a lab-frame
fragmentation of the QCD background. This information could be exploited as an
additional handle in such searches for Beyond the Standard Model (BSM)
physics.

Fragmentation differences have been exploited in the past without explicitly
defining this source of the effect. Boosted $V$ searches occasionally use
track multiplicity as a discriminator between merged $V$ jets and background
QCD jets [41], which takes advantage of the difference between the $m_{V}/2$
momentum scale dictating the $V$-jet fragmentation and the TeV momentum scale
of the background. In boosted $V$ decays, well-isolated quark jets of a few
hundred GeV can be easily produced. As discussed above, such jets can have
very different fragmentation profiles compared to those from background QCD
processes. Using this difference can be an important additional handle in
further enriching samples in interesting signal processes.

The assumption that a hadronic jet can be described by its momentum and
species is overly simplistic. Since the fragmentation occurs in a particular
frame that need not be the lab frame, it’s not meaningful to talk about the
properties of jets individually as separate physics objects. Especially when
studying the detailed substructure of jets, sample dependence effects can be
significant, as shown here in simulation.

While well understood to those that consider the theory of QCD, this effect
removes the foundation of jet individualism used by many experimental tools in
collider physics. The training of jet-by-jet taggers should consider the
effect of boosted color rest frames, and the language around jet physics
should be made more precise. This effect also represents an under-explored
opportunity for discriminating jets from boosted color singlet decays,
especially in BSM searches.

###### Acknowledgements.

We thank Tova Holmes, Karri Folan DiPetrillo, Jessie Shelton, Brian Shuve,
Jesse Thaler, Zach Marshall, Nishita Desai, Kate Pachal, Max Swiatlowski,
Rikab Gambhir, and Ben Thornberry for incredibly useful discussions and
suggestions. We also thank Patrick Kirchgaeßer, Giordon Stark and the mario-
mapyde project, and Matthew Feickert and the scailfin project for very useful
Docker images used throughout this study. This work has been supported by the
Department of Energy, Office of Science, under Grant No. DE-SC0023321 and the
National Science Foundation, under Award No. 2235028.

## References

  * Dokshitzer  _et al._ [1997] Y. L. Dokshitzer, G. D. Leder, S. Moretti, and B. R. Webber, JHEP 08, 001 (1997), arXiv:hep-ph/9707323 .
  * Cacciari  _et al._ [2008] M. Cacciari, G. P. Salam, and G. Soyez, JHEP 04, 063 (2008), arXiv:0802.1189 [hep-ph] .
  * Komiske  _et al._ [2018] P. T. Komiske, E. M. Metodiev, and J. Thaler, JHEP 11, 059 (2018), arXiv:1809.01140 [hep-ph] .
  * Bandurin  _et al._ [2015] D. Bandurin _et al._ , Int. J. Mod. Phys. A 30, 1541001 (2015), arXiv:1409.4861 [hep-ex] .
  * Larkoski and Metodiev [2019] A. J. Larkoski and E. M. Metodiev, Journal of High Energy Physics 2019 (2019), 10.1007/jhep10(2019)014.
  * Frye  _et al._ [2017a] C. Frye, A. J. Larkoski, J. Thaler, and K. Zhou, Journal of High Energy Physics 2017 (2017a), 10.1007/jhep09(2017)083.
  * Kogler  _et al._ [2019] R. Kogler _et al._ , Rev. Mod. Phys. 91, 045003 (2019), arXiv:1803.06991 [hep-ex] .
  * Note [1] More unconventional signatures can also lead to anomalous distribution of energy within a jet due to displaced decays, showering via a hidden dark sector, and via other mechanisms [42, 43, 44].
  * Aaboud  _et al._ [2018a] M. Aaboud _et al._ (ATLAS), Eur. Phys. J. C 78, 847 (2018a), arXiv:1805.02935 [hep-ex] .
  * Aad  _et al._ [2023a] G. Aad _et al._ (ATLAS), Eur. Phys. J. C 83, 518 (2023a), arXiv:2209.07874 [hep-ex] .
  * Tumasyan  _et al._ [2023] A. Tumasyan _et al._ (CMS), Eur. Phys. J. C 83, 587 (2023), arXiv:2205.02905 [hep-ex] .
  * Cohen  _et al._ [2014] T. Cohen, M. Jankowiak, M. Lisanti, H. K. Lou, and J. G. Wacker, JHEP 05, 005 (2014), arXiv:1402.0516 [hep-ph] .
  * Aad  _et al._ [2015] G. Aad _et al._ (ATLAS), Phys. Rev. D 91, 112016 (2015), [Erratum: Phys.Rev.D 93, 039901 (2016)], arXiv:1502.05686 [hep-ex] .
  * Aad  _et al._ [2014] G. Aad _et al._ (ATLAS), Eur. Phys. J. C 74, 3023 (2014), arXiv:1405.6583 [hep-ex] .
  * Tumasyan  _et al._ [2022] A. Tumasyan _et al._ (CMS), JHEP 01, 188 (2022), arXiv:2109.03340 [hep-ex] .
  * Aad  _et al._ [2023b] G. Aad _et al._ (ATLAS), (2023b), arXiv:2303.17312 [hep-ex] .
  * Khachatryan  _et al._ [2017] V. Khachatryan _et al._ (CMS), JINST 12, P02014 (2017), arXiv:1607.03663 [hep-ex] .
  * Frye  _et al._ [2017b] C. Frye, A. J. Larkoski, J. Thaler, and K. Zhou, JHEP 09, 083 (2017b), arXiv:1704.06266 [hep-ph] .
  * Aad  _et al._ [2019a] G. Aad _et al._ (ATLAS), Phys. Rev. D 100, 052011 (2019a), arXiv:1906.09254 [hep-ex] .
  * Aad  _et al._ [2016a] G. Aad _et al._ (ATLAS), Eur. Phys. J. C 76, 322 (2016a), arXiv:1602.00988 [hep-ex] .
  * Note [2] The effects of color flow on the jet pull observable have been measured at the LHC [9, 10, 11]. In these measurements, the fragmentation patterns of pairs of jets is used to infer parton-level color connection.
  * Note [3] This was explicitly noted in Ref. [45].
  * Alwall  _et al._ [2014] J. Alwall, R. Frederix, S. Frixione, V. Hirschi, F. Maltoni, O. Mattelaer, H. S. Shao, T. Stelzer, P. Torrielli, and M. Zaro, JHEP 07, 079 (2014), arXiv:1405.0301 [hep-ph] .
  * Sjöstrand  _et al._ [2015] T. Sjöstrand, S. Ask, J. R. Christiansen, R. Corke, N. Desai, P. Ilten, S. Mrenna, S. Prestel, C. O. Rasmussen, and P. Z. Skands, Comput. Phys. Commun. 191, 159 (2015), arXiv:1410.3012 [hep-ph] .
  * Bierlich  _et al._ [2022] C. Bierlich _et al._ ,  (2022), 10.21468/SciPostPhysCodeb.8, arXiv:2203.11601 [hep-ph] .
  * Fischer  _et al._ [2016] N. Fischer, S. Prestel, M. Ritzmann, and P. Skands, Eur. Phys. J. C 76, 589 (2016), arXiv:1605.06142 [hep-ph] .
  * Bahr  _et al._ [2008] M. Bahr _et al._ , Eur. Phys. J. C 58, 639 (2008), arXiv:0803.0883 [hep-ph] .
  * Bellm  _et al._ [2016] J. Bellm _et al._ , Eur. Phys. J. C 76, 196 (2016), arXiv:1512.01178 [hep-ph] .
  * Cacciari  _et al._ [2012] M. Cacciari, G. P. Salam, and G. Soyez, Eur. Phys. J. C 72, 1896 (2012), arXiv:1111.6097 [hep-ph] .
  * de Favereau  _et al._ [2014] J. de Favereau, C. Delaere, P. Demin, A. Giammanco, V. Lemaître, A. Mertens, and M. Selvaggi (DELPHES 3), JHEP 02, 057 (2014), arXiv:1307.6346 [hep-ex] .
  * Aad  _et al._ [2019b] G. Aad _et al._ (ATLAS), Eur. Phys. J. C 79, 970 (2019b), arXiv:1907.05120 [hep-ex] .
  * Sirunyan  _et al._ [2018] A. M. Sirunyan _et al._ (CMS), JINST 13, P05011 (2018), arXiv:1712.07158 [physics.ins-det] .
  * Gallicchio and Schwartz [2011a] J. Gallicchio and M. D. Schwartz, Phys. Rev. Lett. 107, 172001 (2011a), arXiv:1106.3076 [hep-ph] .
  * Gallicchio and Schwartz [2011b] J. Gallicchio and M. D. Schwartz, JHEP 10, 103 (2011b), arXiv:1104.1175 [hep-ph] .
  * IML [2017] “IML Workshop - Mini Challenge on q/g jet tagging,” https://gitlab.cern.ch/IML-WG/IMLWorkshop2017-Challenge (2017), accessed: 2023-07-12.
  * Metodiev  _et al._ [2017] E. M. Metodiev, B. Nachman, and J. Thaler, JHEP 10, 174 (2017), arXiv:1708.02949 [hep-ph] .
  * Metodiev and Thaler [2018] E. M. Metodiev and J. Thaler, Phys. Rev. Lett. 120, 241602 (2018), arXiv:1802.00008 [hep-ph] .
  * Aad  _et al._ [2021] G. Aad _et al._ (ATLAS), Eur. Phys. J. C 81, 537 (2021), arXiv:2011.08280 [hep-ex] .
  * Aaboud  _et al._ [2018b] M. Aaboud _et al._ (ATLAS), Phys. Rev. D 98, 052003 (2018b), arXiv:1807.08639 [hep-ex] .
  * Khachatryan  _et al._ [2015] V. Khachatryan _et al._ (CMS), Phys. Rev. D 92, 032008 (2015), arXiv:1506.01010 [hep-ex] .
  * Aad  _et al._ [2019c] G. Aad _et al._ (ATLAS), JHEP 09, 091 (2019c), [Erratum: JHEP 06, 042 (2020)], arXiv:1906.08589 [hep-ex] .
  * Lee  _et al._ [2019] L. Lee, C. Ohm, A. Soffer, and T.-T. Yu, Prog. Part. Nucl. Phys. 106, 210 (2019), [Erratum: Prog.Part.Nucl.Phys. 122, 103912 (2022)], arXiv:1810.12602 [hep-ph] .
  * Alimena  _et al._ [2020] J. Alimena _et al._ , J. Phys. G 47, 090501 (2020), arXiv:1903.04497 [hep-ex] .
  * Cohen  _et al._ [2017] T. Cohen, M. Lisanti, H. K. Lou, and S. Mishra-Sharma, JHEP 11, 196 (2017), arXiv:1707.05326 [hep-ph] .
  * Aad  _et al._ [2016b] G. Aad _et al._ (ATLAS), Eur. Phys. J. C 76, 238 (2016b), arXiv:1509.04939 [hep-ex] .


# NeXt-TDNN: Modernizing Multi-Scale Temporal Convolution Backbone
for Speaker Verification

###### Abstract

In speaker verification, ECAPA-TDNN has shown remarkable improvement by
utilizing one-dimensional(1D) Res2Net block and squeeze-and-excitation(SE)
module, along with multi-layer feature aggregation (MFA). Meanwhile, in vision
tasks, ConvNet structures have been modernized by referring to Transformer,
resulting in improved performance. In this paper, we present an improved block
design for TDNN in speaker verification. Inspired by recent ConvNet
structures, we replace the SE-Res2Net block in ECAPA-TDNN with a novel 1D two-
step multi-scale ConvNeXt block, which we call TS-ConvNeXt. The TS-ConvNeXt
block is constructed using two separated sub-modules: a temporal multi-scale
convolution (MSC) and a frame-wise feed-forward network (FFN). This two-step
design allows for flexible capturing of inter-frame and intra-frame contexts.
Additionally, we introduce global response normalization (GRN) for the FFN
modules to enable more selective feature propagation, similar to the SE module
in ECAPA-TDNN. Experimental results demonstrate that NeXt-TDNN, with a
modernized backbone block, significantly improved performance in speaker
verification tasks while reducing parameter size and inference time. We have
released our code111https://github.com/dmlguq456/NeXt_TDNN_ASV for future
studies.

Index Terms—  speaker recognition, speaker verification, TDNN, ConvNeXt,
multi-scale

##  1 Introduction

With the rise of deep neural networks, the conventional human-crafted
embedding feature vector for speaker identity (i-vector) [1] was rapidly
replaced with the DNN-based vector (d-vector) [2] in speaker verification. In
particular, x-vector [3] has shown significantly improved performance through
the use of time delay neural network (TDNN), and its various improvements have
been studied [4, 5]. More recently, ECAPA-TDNN [6] has been proposed, which
improved the TDNN architecture and achieved state-of-the-art performance. To
capture the spectral structure in multi-scales, it utilized Res2Net [7] with
one-dimensional(1D) convolution as backbone layers. Additionally, squeeze-and-
excitation(SE) blocks [8] were used for feature gating across the global
temporal contexts. Finally, it introduced a multi-layer feature aggregation
(MFA) structure for utilizing shallow-layer features before temporal pooling.
Therefore, ECAPA-TDNN has become a standard model for speaker verification
tasks and been used as a base model in mainstream works [9, 10, 11].

Fig. 1: Block diagram for the proposed NeXt-TDNN architecture.

However, speech can be also regarded as spectral two-dimensional(2D) visual
features. Therefore, for extracting a speaker embedding vector, a simple 2D
ResNet-based architecture [12] has been often used, which also exhibited
stable results for speaker verification [13, 14, 15, 16]. In traditional
vision tasks, on the other hand, ConvNets including the conventional ResNet
structure have been repeatedly improved and modernized after the advent of the
vision Transformer [17]. ConvNeXt [18] is one of those improvements, which
refers to the architecture of the Transformer. In the following study,
ConvNeXt-V2 [19] was presented with global response normalization (GRN), which
emphasized the channel dimension in spatially global contexts.

In this paper, we present a modernized backbone block for TDNN inspired by the
recent ConvNeXt structure. As shown in Fig. 1, we have re-designed the
ConvNeXt block to be a suitable substitute for the SE-Res2Net block, as a two-
step ConvNeXt (TS-ConvNeXt) block. The TS-ConvNeXt block is composed of two
sub-modules. The first module is based on a parallel 1D depth-wise convolution
(DConv1D) layer with different scales, which we call multi-scale convolution
(MSC) module. Then, the separate feed-forward network (FFN) is placed like a
Transformer structure. Additionally, we adopted the GRN [19] in the FFN to
enhance the channel contrast, which may replace the SE module in the SE-
Res2Net block of the ECAPA-TDNN. Based on the proposed TS-ConvNeXt block, we
have developed the modernized NeXt-TDNN for extracting an improved speaker
embedding vector.

##  2 Proposed NeXt-TDNN Architecture

###  2.1 MFA layer and ASP as temporal pooling

As shown in Fig 1, the input feature is given as a mel-spectrogram with a
shape of $C_{\rm mel}\times T$, where $T$ is the number of frames. Then, it is
processed by a standard convolution layer with a kernel size of 4, which
converts the spectral dimension of $C_{\rm mel}$ to a latent channel dimension
of $C$. The output feature $\mathbf{F}^{(0)}\in\mathbb{R}^{C\times T}$ is then
processed by three stages with TS-ConvNeXt blocks. To aggregate the outputs
$\mathbf{F}^{(1)},\mathbf{F}^{(2)},\mathbf{F}^{(3)}\in\mathbb{R}^{C\times T}$
from all three stages, we utilized the MFA layer similarly to the ECAPA-TDNN
[6]. Specifically, they are concatenated as $\mathbf{F}\in\mathbb{R}^{3C\times
T}$ and processed by 1D point-wise convolution (PConv1D) with an output
dimension of $C_{\rm MFA}$ followed by Layer Normalization (LN).

To extract an utterance-level embedding from the frame-level features, we
utilized the ASP pooling layer [20] with channel-dependent attention values
$\boldsymbol{\alpha}_{t}\in\mathbb{R}^{C_{\rm MFA}\times 1}$ following the
ECAPA-TDNN. When the output of the MFA layer is given as
$\mathbf{H}=[\mathbf{h}_{1},...,\mathbf{h}_{T}]\in\mathbb{R}^{C_{\rm
MFA}\times T}$, the ASP layer calculates attention values between 0 and 1 from
these frame-level features and uses them for a weighted mean and a standard
deviation vector as
$\boldsymbol{\mu}=\sum_{t=1}^{T}\boldsymbol{\alpha}_{t}\odot\mathbf{h}_{t}$
and
$\boldsymbol{\sigma}=\sqrt{\smash{\sum}_{t=1}^{T}\boldsymbol{\alpha}_{t}\odot\mathbf{h}_{t}\odot\mathbf{h}_{t}-\boldsymbol{\mu}\odot\boldsymbol{\mu}}$
where $\odot$ denotes the Hadamard product. Then, the speaker embedding
$\mathbf{x}\in\mathbb{R}^{192\times 1}$ is extracted from these two statistics
using a linear layer.

###  2.2 Proposed TS-ConvNeXt block

As shown in Fig. 1, the backbone consists of three stages of TS-ConvNeXt
blocks and the blocks are repeated $B$ times in each stage. In the $n$-th
stage, $n\in\\{1,2,3\\}$, the input representation
$\mathbf{F}^{(n-1)}_{b-1}\in\mathbb{R}^{C\times T}$ at the $b$-th block,
$1\leq b\leq B$, is processed as follows:

$\displaystyle\tilde{\mathbf{F}}^{(n-1)}_{b-1}$
$\displaystyle=\mathbf{F}^{(n-1)}_{b-1}+\text{MSC}(\mathbf{F}^{(n-1)}_{b-1}),$
(1) $\displaystyle\mathbf{F}^{(n-1)}_{b}$
$\displaystyle=\tilde{\mathbf{F}}^{(n-1)}_{b-1}+\text{FFN}(\tilde{\mathbf{F}}^{(n-1)}_{b-1}),$
(2)

with $\mathbf{F}_{0}^{(0)}=\mathbf{F}^{(0)}$. The output of the $B$-th block
$\vspace{-.4mm}\mathbf{F}_{B}^{(n-1)}$ becomes the input of the MFA layer as
well as the first block of the next stage:
$\smash{\mathbf{F}_{B}^{(n-1)}=\mathbf{F}^{(n)}=\mathbf{F}_{0}^{(n)}}$. The
MSC module is used to capture inter-frame temporal contexts, while the FFN
module processes frame-wise features independently.

(a) Res2Conv module

(b) MSC module

Fig. 2:  Block diagrams of (a) the conventional Res2Conv module in the Res2Net
block ($s=4$) and (b) the MSC module in the TS-ConvNeXt block ($s=4$).

To effectively capture multi-scale features, we have replaced Res2Net [7] in
Fig. 2LABEL:sub@fig:res2 with $s$ parallel DConv1D layers in the MSC module.
Each layer has a different kernel size of $K_{1},...,K_{s}$, with a scale
factor of $s$ as shown in Fig. 2LABEL:sub@fig:LK_m. For the optimized training
at each scale, the input feature of the MSC module is projected to a reduced
dimension of $C^{\prime}$ before each DConv1D layer. Then, these multi-scale
features are concatenated to have a dimension of $s\cdot C^{\prime}$ and once
again projected to $C$ by PConv1D after GELU activation. The mechanism of MSC
is simple but similar to the multi-head self-attention (MHSA) in the
transformer [21]. The only difference is that the attention operation in MHSA
is replaced with DConv1D in MSC.

On the other hand, the FFN includes two PConv1D layers with an expansion
factor of 4 with GELU activation. Also, GRN [19] is adopted in the FFN to
enhance the contrast of individual channels. GRN is a simple and efficient
method, as it does not require additional parameter layers. Specifically, when
the hidden feature is given as
$\mathbf{G}=[\mathbf{g}_{1},...,\mathbf{g}_{T}]\in\mathbb{R}^{4C\times T}$
after the GELU activation, GRN calculates L2-norm across the temporal
dimension into a vector $\bar{\mathbf{g}}\in\mathbb{R}^{4C\times 1}$ and apply
a response normalization function $\mathcal{N}(\cdot)$ to the aggregated
values $\bar{\mathbf{g}}$ as
$\mathcal{N}(\bar{\mathbf{g}})=\bar{\mathbf{g}}/{\|\bar{\mathbf{g}}\|_{1}}$
where $\|\cdot\|_{1}$ is L1-norm of a vector222As in [19], the normalized
values are scaled by the channel dimension $4C$ in practice.. Then, the
original features $\mathbf{g}_{t}$ are calibrated using the values from the
response normalization function with skip connection, which is calculated as

$\text{GRN}({\mathbf{g}}_{t})=\mathbf{g}_{t}+\gamma\odot\mathcal{N}(\bar{\mathbf{g}})\odot\mathbf{g}_{t}+\beta,$
(3)

with trainable parameters $\gamma,\beta\in\mathbb{R}^{4C\times 1}$ for affine
transformation with their initial values set to zero. This allows the GRN to
operate as a bypass at the initial step and adapt gradually as the training
progresses.

(a) SE-Res2Net

(b) Transformer

(c) ConvNeXt

(d) TS-ConvNeXt

(e) TS-ConvNeXt-l

Fig. 3: Block designs of the conventional (a) 1D SE-Res2Net in ECAPA-TDNN, (b)
Transformer, and (c) 1D ConvNeXt and the proposed (d) 1D TS-ConvNeXt in NeXt-
TDNN and (e) 1D TS-ConvNeXt-l in NeXt-TDNN-l.

###  2.3 Rationale of the backbone block design

In Fig. 3, the block structure designs are shown for conventional and proposed
blocks. The SE-Res2Net block [7] in Fig. 3LABEL:sub@fig:ECAPA_TDNN follows the
conventional ResNet structure and consists of two PConv2D layers to control
the channel dimension. Each layer is followed by Batch Normalization (BN) and
ReLU activation. On the other hand, it replaces the standard convolution in
ResNet with a Res2 Dilated Conv1D layer of Fig. 2LABEL:sub@fig:res2 to capture
multi-scale contexts and adds an SE block to attend to the specific channels.
Meanwhile, the traditional Transformer [21] has two separate sub-modules of
MHSA and FFN as shown in Fig. 3LABEL:sub@fig:Transformer. Therefore,
ConvNeXt(-V2) block [18, 19] in Fig. 3LABEL:sub@fig:ConvNeXt was designed by
changing the ResNet block regarding the structure of the Transformer. In
particular, after changing the standard convolution of ResNet to DConv, the
ConvNeXt block moves up the DConv with a larger kernel size by expecting a
similar role of MHSA in the Transformer. It also uses an inverted bottleneck
structure with fewer norms and activations as in FFN of the Transformer. In
ConvNeXt-V2 [19], GRN was newly proposed and introduced behind the GELU
activation in the inverted bottleneck of ConvNeXt to enhance the performance.

To modernize the backbone block from the SE-Res2Net of the ECAPA-TDNN, we
designed TS-ConvNeXt from the ConvNeXt by considering the structures of SE-
Res2Net and Transformer more proactively as shown in Fig.
3LABEL:sub@fig:NeXt_TDNN. Specifically, we separated the temporal block of MSC
and position-wise processing block of FFN to perform in a two-step way and
introduced temporal multi-scale features in MSC module. This modified design
is more similar to the Transformer structure and can provide the benefit of
more flexible training for inter- and intra-frame contexts. In terms of SE-
Res2Net, MSC may replace the Res2Net for multi-scale temporal modeling, and
FFN with GRN can be used instead of the SE block for position-wise feature
processing. Additionally, we considered TS-ConvNeXt-l block in Fig.
3LABEL:sub@fig:NeXt_TDNN_light as a light version of TS-ConvNeXt. TS-
ConvNeXt-l uses a single DConv1D layer instead of the MSC module.

Table 2: Evaluation for conventional and proposed models on Voxceleb1-O, E, and H datasets. For conventional models, we considered Fast ResNet-34 [16], ECAPA-TDNN [6]1, and EfficientTDNN [9]2 as an improved version for ECAPA-TDNN. The kernel size $K$ of TS-ConvNeXt-l block was set to 65 in the NeXt-TDNN-l. For the MSC module of the TS-ConvNeXt in the NeXt-TDNN model, the scale factor and the set for multi-scale kernel sizes were set to $s=2$ and $[7,65]$, respectively. MACs and RTF were measured on 3-s long segments. RTF was measured by repeating the inference on a test environment sufficiently with Nvidia GeForce GTX 1080 Ti. | Model | Params | MACs | RTF | VoxCeleb1-O | VoxCeleb1-E | VoxCeleb1-H
---|---|---|---|---|---|---|---
|  |  |  |  ($\times 10^{-3}$) |  EER(%) | minDCF |  EER(%) | minDCF |  EER(%) | minDCF
mobile |  Fast ResNet-34 [16] | 1.4M | 0.675G | 1.67 | 2.08 | 0.2729 | 2.18 | 0.2632 | 4.19 | 0.3797
ECAPA-TDNN ($C$=256) | 1.9M | 0.410G | 1.60 | 1.56 | 0.1551 | 1.56 | 0.1656 | 2.70 | 0.2512
EfficientTDNN-Mobile [9] | 2.4M | 0.574G | 1.20 | 1.41 | 0.1247 | 1.53 | 0.1654 | 2.72 | 0.2526
NeXt-TDNN-l ($C$=192, $B$=1) | 1.6M | 0.417G | 0.51 | 1.39 | 0.1304 | 1.52 | 0.1497 | 2.49 | 0.2274
NeXt-TDNN-l ($C$=128, $B$=3) | 1.6M | 0.441G | 0.89 | 1.10 | 0.1079 | 1.24 | 0.1334 | 2.12 | 0.2006
NeXt-TDNN ($C$=192, $B$=1) | 1.8M | 0.478G | 0.63 | 1.31 | 0.1319 | 1.39 | 0.1409 | 2.28 | 0.2073
NeXt-TDNN ($C$=128, $B$=3) | 1.9M | 0.519G | 1.29 | 1.03 | 0.0954 | 1.17 | 0.1260 | 1.98 | 0.1903
base |  ECAPA-TDNN ($C$=512) | 6.2M | 1.569G | 1.80 | 1.13 | 0.1118 | 1.36 | 0.1464 | 2.44 | 0.2368
EfficientTDNN-Base [9] | 5.8M | 1.450G | 1.32 | 0.96 | 0.0924 | 1.20 | 0.1296 | 2.17 | 0.2073
NeXt-TDNN-l ($C$=384, $B$=1) | 5.9M | 1.609G | 0.63 | 1.05 | 0.0957 | 1.18 | 0.1208 | 2.02 | 0.1882
NeXt-TDNN-l ($C$=256, $B$=3) | 6.0M | 1.695G | 0.88 | 0.81 | 0.0909 | 1.04 | 0.1157 | 1.86 | 0.1844
NeXt-TDNN ($C$=384, $B$=1) | 6.7M | 1.862G | 0.71 | 0.93 | 0.0833 | 1.11 | 0.1160 | 1.89 | 0.1758
NeXt-TDNN ($C$=256, $B$=3) | 7.1M | 2.027G | 1.31 | 0.79 | 0.0865 | 1.04 | 0.1152 | 1.82 | 0.1818
|  |  |  |  |  |  |  |  |  |
Table 1: Evaluation on VoxCeleb-O for the proposed NeXt-TDNN depending on the backbone structure with $C=256$ and $B=3$. $K$ denotes the kernel size (or the set of sizes) in the DConv1D layer. Backbone block | GRN | $K$ | Params | EER(%) | minDCF
---|---|---|---|---|---
ConvNeXt |  | 7 | 5.9M | 1.08 | 0.0956
ConvNeXt | ✓ | 7 | 5.9M | 1.00 | 0.1153
ConvNeXt | ✓ | 65 | 6.0M | 1.05 | 0.1283
TS-ConvNeXt-l |  | 7 | 5.9M | 1.08 | 0.1016
TS-ConvNeXt-l | ✓ | 7 | 5.9M | 0.96 | 0.1039
TS-ConvNeXt-l | ✓ | 65 | 6.0M | 0.81 | 0.0910
TS-ConvNeXt ($s$=1) | ✓ | 65 | 7.2M | 0.84 | 0.0884
TS-ConvNeXt ($s$=2) | ✓ | (7,65) | 7.1M | 0.79 | 0.0865
TS-ConvNeXt ($s$=4) | ✓ | (7,15,33,65) | 7.1M | 0.84 | 0.0781
|  |  |  |  |

##  3 Experimental setup

###  3.1 Dataset and metrics

In our experiments, training and evaluation were based on VoxCeleb1 [22] and
VoxCeleb2 [13] datasets. VoxCeleb1 includes two subsets: the development set
with 1,211 speakers and the evaluation set with 40 speakers. Also, VoxCeleb2
is divided into two subsets: the development and evaluation sets, the number
of whose speakers are 5,994 and 118, respectively. As a training dataset, we
used the development dataset of VoxCeleb2. On the other hand, we used three
subsets from the VoxCeleb1 dataset for the evaluation: VoxCeleb1-O only with
its original test set, VoxCeleb1-E with its entire dataset including the
development and test sets, VoxCeleb1-H selected to have the same nationality
and gender from the VoxCeleb-E.

For evaluation, we measured the performance of the models by the equal error
rate (EER) and the minimum normalized detection cost function (minDCF) with
$P_{\rm target}=0.01$ and $C_{\rm FA}=C_{\rm Miss}=1$. We calculated scores
using the cosine distance of an embedding pair and applied score normalization
with adaptive s-norm [23]. 6,000 utterances were picked as an imposter cohort
in the training set and 300 top imposter scores were used for the score
normalization.

###  3.2 Configurations

As an input feature, 80 log-Mel-filterbanks ($C_{\rm mel}=80$) were extracted
from a spectrogram using an FFT size of 512 and a 25-ms-long Hamming window
with a 10-ms shift. We trained the network using randomly cropped 3-s segments
with AAM-softmax [24] with a margin of 0.3 and a scale of 40. For the proposed
NeXt-TDNN, the output dimension of the MFA layer $C_{\rm MFA}$ was set to $3C$
which was equal to its input dimension. For the MSC module in the TS-ConvNeXt
block, the projection dimension was set to $C^{\prime}=C/s$.

Following the ECAPA-TDNN [6], we also utilized the Kaldi recipe [4] for data
augmentation with noise source from MUSAN [25] and RIR [26]. SpecAugment [27]
was applied, too. We set the batch size of 500 for the mobile model size and
300 for base models, and the learning rates were initialized as $5e^{-4}$ and
$3e^{-4}$, respectively [28]. The models were trained up to 200 epochs, and
the learning rate was reduced by 0.8 times every 10 epochs. As an optimizer,
AdamW was used with a weight decay of $0.01$, and gradient clipping with a
maximum L2-norm of 1 was applied for stable training.

##  4 Experimental result

11footnotetext: We trained and evaluated the ECAPA-TDNN using the source code
implemented by speechbrain [29].22footnotetext: We evaluated using the
official pre-trained model provided by an author.

First, we validated the effectiveness of TS-ConvNeXt block in Table 1.
Generally, using GRN improved the performance in terms of the EER by
emphasizing the frame-level features based on global temporal context, similar
to the SE block in ECAPA-TDNN. Also, contrary to the ConvNeXt, TS-ConvNeXt-l
showed effectiveness with a larger kernel size of $K=65$, which demonstrates
that simply dividing ConvNeXt into two sub-modules is appropriate with the
large kernel. With the TS-ConvNeXt block, using a multi-scale kernel with
small and large kernels further improved the results than using a single
kernel of $65$.

In Table 2, we evaluated our proposed NeXt-TDNN and NeXt-TDNN-l for mobile and
base models. Also, we measured the multiply-accumulate operations (MACs) to
compare the computational costs and the real-time factors (RTFs) to evaluate
the inference speed. In particular, we considered two configurations for
proposed NeXt-TDNN and NeXt-TDNN-l: the faster version with $B=1$ and the
deeper one with $B=3$ while arranging the corresponding $C$ to keep the
parameter sizes similar.

Compared to the conventional models, our models consistently achieved improved
performances in both mobile and base model sizes. In particular, our NeXt-TDNN
with $B=1$ achieved better result with more than two times faster speed than
the ECAPA-TDNN. Furthermore, NeXt-TDNN with the MSC module generally improved
the performance compared to the NeXt-TDNN-l. Finally, it is noteworthy that
the mobile NeXt-TDNN with $C=128$ and $B=3$ achieved better results than even
the base ECAPA-TDNN with $C=512$ while being three times smaller in both the
parameter size and the computational costs (1.9M vs. 6.2M and 0.519G vs.
1.569G). Because the inference was performed using a GPU, the RTF was not
significantly affected by the channel dimension $C$ due to the advantage of
parallel computing, but rather by the block repetition $B$.

##  5 Conclusion

We have modernized the block design in TDNNs for speaker verification from the
popular ECAPA-TDNN. Inspired by the structure of Transformer and recent
ConvNets, we replaced the SE-Res2Net block in the ECAPA-TDNN with the novel
TS-ConvNeXt block. This block consists of two separated sub-modules: MSC and
FFN, which capture multi-scale temporal and position-wise channel contexts,
respectively. Additionally, we introduced GRN in the FFN modules to enhance
feature contrast. Experimental results showed that the NeXt-TDNN with the
modernized TS-ConvNeXt block was effective for speaker verification.

## References

  * [1] Najim Dehak, Patrick J. Kenny, Réda Dehak, Pierre Dumouchel, and Pierre Ouellet,  “Front-end factor analysis for speaker verification,”  IEEE TASLP, vol. 19, no. 4, pp. 788–798, 2011.
  * [2] Ehsan Variani, Xin Lei, Erik McDermott, Ignacio Lopez Moreno, and Javier Gonzalez-Dominguez,  “Deep neural networks for small footprint text-dependent speaker verification,”  in Proc. of ICASSP, 2014, pp. 4052–4056.
  * [3] David Snyder, Daniel Garcia-Romero, Gregory Sell, Daniel Povey, and Sanjeev Khudanpur,  “X-vectors: Robust DNN embeddings for speaker recognition,”  in Proc. of ICASSP, 2018, pp. 5329–5333.
  * [4] David Snyder, Daniel Garcia-Romero, Gregory Sell, Alan McCree, Daniel Povey, and Sanjeev Khudanpur,  “Speaker recognition for multi-speaker conversations using x-vectors,”  in Proc. of ICASSP, 2019, pp. 5796–5800.
  * [5] Daniel Garcia-Romero, Alan McCree, David Snyder, and Gregory Sell,  “Jhu-HLTCOE system for the voxsrc speaker recognition challenge,”  in Proc. of ICASSP, 2020, pp. 7559–7563.
  * [6] Brecht Desplanques, Jenthe Thienpondt, and Kris Demuynck,  “ECAPA-TDNN: Emphasized Channel Attention, Propagation and Aggregation in TDNN Based Speaker Verification,”  in Proc. Interspeech, 2020, pp. 3830–3834.
  * [7] Shang-Hua Gao, Ming-Ming Cheng, Kai Zhao, Xin-Yu Zhang, Ming-Hsuan Yang, and Philip Torr,  “Res2Net: A new multi-scale backbone architecture,”  IEEE TPAMI, vol. 43, no. 2, pp. 652–662, 2021.
  * [8] Jie Hu, Li Shen, and Gang Sun,  “Squeeze-and-excitation networks,”  in Proc. of CVPR, June 2018.
  * [9] Rui Wang, Zhihua Wei, Haoran Duan, Shouling Ji, Yang Long, and Zhen Hong,  “EfficientTDNN: Efficient architecture search for speaker recognition,”  IEEE/ACM TASLP, vol. 30, pp. 2267–2279, 2022.
  * [10] Jee weon Jung, Youjin Kim, Hee-Soo Heo, Bong-Jin Lee, Youngki Kwon, and Joon Son Chung,  “Pushing the limits of raw waveform speaker recognition,”  in Proc. Interspeech, 2022, pp. 2228–2232.
  * [11] Yang Zhang, Zhiqiang Lv, Haibin Wu, Shanshan Zhang, Pengfei Hu, Zhiyong Wu, Hung yi Lee, and Helen Meng,  “MFA-Conformer: Multi-scale Feature Aggregation Conformer for Automatic Speaker Verification,”  in Proc. Interspeech, 2022, pp. 306–310.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proc. of CVPR, June 2016.
  * [13] Joon Son Chung, Arsha Nagrani, and Andrew Zisserman,  “VoxCeleb2: Deep speaker recognition,”  in Proc. Interspeech, 2018, pp. 1086–1090.
  * [14] Weicheng Cai, Jinkun Chen, and Ming Li,  “Exploring the encoding layer and loss function in end-to-end speaker and language recognition system,”  in Proc. Odyssey 2018 The Speaker and Language Recognition Workshop, 2018, pp. 74–81.
  * [15] Hossein Zeinali, Shuai Wang, Anna Silnova, Pavel Matějka, and Oldřich Plchot,  “BUT system description to voxCeleb speaker recognition challenge 2019,” 2019.
  * [16] Joon Son Chung, Jaesung Huh, Seongkyu Mun, Minjae Lee, Hee-Soo Heo, Soyeon Choe, Chiheon Ham, Sunghwan Jung, Bong-Jin Lee, and Icksang Han,  “In Defence of Metric Learning for Speaker Recognition,”  in Proc. Interspeech, 2020, pp. 2977–2981.
  * [17] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby,  “An image is worth 16x16 words: Transformers for image recognition at scale,”  in International Conference on Learning Representations, 2021.
  * [18] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie,  “A Convnet for the 2020s,”  in Proc. of CVPR, June 2022, pp. 11976–11986.
  * [19] Sanghyun Woo, Shoubhik Debnath, Ronghang Hu, Xinlei Chen, Zhuang Liu, In So Kweon, and Saining Xie,  “ConvNext V2: Co-designing and scaling ConvNets with masked autoencoders,”  in Proc. of CVPR, June 2023, pp. 16133–16142.
  * [20] Koji Okabe, Takafumi Koshinaka, and Koichi Shinoda,  “Attentive statistics pooling for deep speaker embedding,”  in Proc. Interspeech, 2018, pp. 2252–2256.
  * [21] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin,  “Attention is all you need,”  in Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. 2017, vol. 30, Curran Associates, Inc.
  * [22] Arsha Nagrani, Joon Son Chung, and Andrew Zisserman,  “VoxCeleb: A Large-Scale Speaker Identification Dataset,”  in Proc. Interspeech, 2017, pp. 2616–2620.
  * [23] Pavel Matějka, Ondřej Novotný, Oldřich Plchot, Lukáš Burget, Mireia Diez Sánchez, and Jan Černocký,  “Analysis of score normalization in multilingual speaker recognition,”  in Proc. Interspeech, 2017, pp. 1567–1571.
  * [24] Jiankang Deng, Jia Guo, Niannan Xue, and Stefanos Zafeiriou,  “Arcface: Additive angular margin loss for deep face recognition,”  in Proc. of CVPR, June 2019.
  * [25] David Snyder, Guoguo Chen, and Daniel Povey,  “Musan: A music, speech, and noise corpus,” 2015.
  * [26] J. B. Alien and D. A. Berkley,  “Image method for efficiently simulating small‐room acoustics,”  The Journal of the Acoustical Society of America, vol. 60, no. S1, pp. S9–S9, 08 2005.
  * [27] Daniel S. Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D. Cubuk, and Quoc V. Le,  “SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognition,”  in Proc. Interspeech, 2019, pp. 2613–2617.
  * [28] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He,  “Accurate, large minibatch sgd: Training imagenet in 1 hour,” 2018.
  * [29] Mirco Ravanelli, Titouan Parcollet, Peter Plantinga, Aku Rouhe, Samuele Cornell, Loren Lugosch, Cem Subakan, Nauman Dawalatabad, Abdelwahab Heba, Jianyuan Zhong, Ju-Chieh Chou, Sung-Lin Yeh, Szu-Wei Fu, Chien-Feng Liao, Elena Rastorgueva, François Grondin, William Aris, Hwidong Na, Yan Gao, Renato De Mori, and Yoshua Bengio,  “SpeechBrain: A general-purpose speech toolkit,” 2021,  arXiv:2106.04624.


Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

4th Edition of Knowledge-aware and Conversational Recommender Systems (KaRS)
Workshop @ RecSys 2022, September 18–23 2023, Seattle, WA, USA.

<EMAIL_ADDRESS>] [1]

<EMAIL_ADDRESS>]

<EMAIL_ADDRESS>]

[1]Corresponding author.

# A Nonparametric Contextual Bandit with Arm-level Eligibility Control for
Customer Service Routing

Ruofeng Wen  Customer Engagement Technology, Amazon  Wenjun Zeng  Yi Liu

(2022)

###### Abstract

Amazon Customer Service (CS) provides real-time support for millions of
customer contacts every year. While bot-resolver helps automate some traffic,
we still see high demand for human agents, also called subject matter experts
(SMEs). Customers outreach with questions in different domains (return policy,
device troubleshooting, etc.). Depending on their training, not all SMEs are
eligible to handle all contacts. Routing contacts to eligible SMEs turns out
to be a non-trivial problem because SMEs’ domain eligibility is subject to
training quality and can change over time. To optimally recommend SMEs while
simultaneously learning the true eligibility status, we propose to formulate
the routing problem with a nonparametric contextual bandit algorithm (K-Boot)
plus an eligibility control (EC) algorithm. K-Boot models reward with a kernel
smoother on similar past samples selected by $k$-NN, and Bootstrap Thompson
Sampling for exploration. EC filters arms (SMEs) by the initially system-
claimed eligibility and dynamically validates the reliability of this
information. The proposed K-Boot is a general bandit algorithm, and EC is
applicable to other bandits. Our simulation studies show that K-Boot performs
on par with state-of-the-art Bandit models, and EC boosts K-Boot performance
when stochastic eligibility signal exists.

###### keywords:

Bandit Customer Service Routing Arm Eligibility Nonparametric

##  1 Introduction

In Amazon Customer Service (CS), we dispatch human agents, also called subject
matter experts (SMEs) in real-time to handle millions of customer contacts.
The SME routing automation process has two steps: first there is a natural
language understanding (NLU) model to process customer’s input and identify
the relevant domain (return policy, device troubleshooting, etc.); then it
dispatches an SME who is eligible. We define _eligibility_ when the SME
masters the required skill in the relevant domain through training. SME
routing turns out to be a non-trivial problem for four reasons. First, the NLU
model is unlikely to categorize the domain with perfect accuracy. Second, the
reliability in SME eligibility as identified by operation team is subject to
training program quality and readiness. Third, the domain taxonomy and SMEs’
eligibility status can change in a decentralized way. In reality, it is
difficult to keep track of all the eligibility updates, assuming correctness.
Finally, eligible SMEs do not guarantee customer satisfaction, leading to
noisy feedback signals. All these uncertainties make SME routing a challenging
problem.

Figure 1: The CS Routing Problem. The goal of the recommender is to select an
agent that will result in the best outcome of this customer contact.

To tackle the complexity, we formulate CS routing as a recommendation problem
and use contextual Bandit as a solution. Bandit, a framework for sequential
decision making, has been used for online recommendation across companies such
as Amazon, Google, Netflix and Yahoo [1]. In contextual bandit, the decision
maker sequentially chooses an arm/action (SME in our case), based on available
contextual information (contact transcript embedding, customer profile, etc.),
and observes a reward signal (customer satisfaction, contact transfer, etc.)
[2]. The objective is to recommend arms at each step to maximize the expected
cumulative reward over time. We apply bandit to the routing problem because it
can optimally explore uncertainties and adapt to dynamic changes [3].
Particularly, the uncertainties in SME eligibility motivate us to formulate a
new type of bandit to utilize arm-level eligibility signals.

Our contribution. We propose K-Boot, a nonparametric contextual bandit
algorithm to model reward and explore, and an Eligibility Controller (EC)
algorithm to model arm-level eligibility. K-Boot uses a $k$-nearest neighbors
($k$-NN) approach to find similar samples from the past, applies a
Nadaraya–Watson kernel regression among the found samples to estimate the
reward, and adopts Bootstrap Thompson Sampling as the exploration strategy.
The EC component implements a dynamic top arm filter based on its estimated
Spearman’s Rank Correlation Coefficient between eligibility and reward. We are
interested in this end-to-end nonparametric setup for practicality: robustness
in performance, strong interpretability and simple non-technical maintenance
which is friendly to business partners. For instance, the $k$-NN component
makes it easy to investigate which historical contacts support the SME
recommendation, and then deploy instant online fixes by trimming unwanted
outliers. While K-Boot and EC are proposed here as a suite, each can be
applied independently - K-Boot is a general Bandit algorithm and EC can
control arm-eligibility for other bandits, such as LinUCB [4].

In the remainder of the paper, we review related literature in Section 2, set
up the formal problem in Section 3 and detail the proposed algorithms in
Section 4. We then present our model results in Section 5, and conclude the
paper last.

##  2 Related Work

In most bandit applications, the items to recommend are products and webpage
content (widget, news articles, etc.). Recently, we see research efforts in
using bandit for routing recommendation in a _conversation_ [5, 6]. In [6],
they used contextual bandit to utilize query and user features along with the
conversational context and build an orchestration to route the dialog. In [5],
they built bandit models to assign solutions given customer’s queries on
Microsoft’s product to a chatbot. This is the most relevant work to our
problem. However, they assume an upstream model to provide a set of plausible
actions to start with and the bandit itself does not deal with the uncertainty
in arm eligibility. Overall, comparing to the extensive bandit literature
existing for product and webpage content recommendation, few bandit works are
there for routing recommendation.

Thompson Sampling (TS) is a heuristic for balancing exploration and
exploitation in bandits [7]. In the parametric manner, TS is implemented by
drawing the reward function parameter $\theta$ from a posterior distribution,
calculating rewards with the sampled parameters, and selecting the arm that
maximizes the estimated reward function. $\theta$ is often assumed to follow
Conjugate-Exponential Family distributions resulting closed-form posteriors.
There are also work where variational methods are used to provide an
analytical approximation to the posterior and enforce trackability [8].
Bootstrap TS introduces volatility in a different way: it pulls the arm with
the highest bootstrap mean, estimated from reward history in a nonparametric
way [9]. One drawback of the approach is the computational cost to train one
bandit model per Bootstrapped training set, which is difficult for large-scale
real-time problems. [10] proposed a general nonparametric bandit algorithm but
they fell back to the parametric reward function approach when there is
context. [11] further improved the exploration efficiency with Bayesian
Bootstrap, but also only for non-contextual bandit. We pair Bootstrap TS with
a single $k$-NN for nonparametric contextual exploration.

Kernel-based Bandit uses a nonparametric reward estimator via kernel
functions, combined with an exploration policy like TS or UCB. Gaussian
Process (GP) has wide applications in bandit domain, e.g. GP-UCB [12] and GP-
TS [13]. However, GP inference is expensive - the standard approach has
$O(N^{3})$ complexity, where $N$ is the number of training samples. The most
efficient sparse or low-rank GP approach still requires $O(ND^{2})$, where $D$
is a hyperparameter indicating the number of _inducing variables_ \- see [14]
for a review. We use $k$-NN to enable $O(k\log N)$ inference time.

##  3 Formulation: Contextual Bandit with Arm Eligibility

We define two types of eligibility setup with different data interfaces. (1)
Eligibility Scores: for a given context $\mathbf{x}$, a list of eligibility
scores for each arm $\mathbf{e}=(e_{1},e_{2},\dots)$ is observed, where
$e_{j}\in[0,1]$ is for arm $a_{j}$. A larger score means higher confidence in
the arm being eligible for the current sample/iteration. An intuitive
interpretation is that the arms are bidding for themselves. This score setup
assumes (the owner of) each arm is able to adaptively assess the dynamic
environment in a distributed and independent manner that can be unknown to the
bandit. Typical examples include ads bidding and voice assistant’s skills
detection - each ad/skill may be managed via the same API, but by different
clients under dynamic competition. (2) Eligibility States: assume the system
at any time can be classified into one of $L$ possible states. Each arm
_claims_ whether it is eligible under a state, represented by a constant
binary vector $\mathbf{c}_{j}$ of length $L$ for arm $a_{j}$. If the $l$-th
element of $\mathbf{c}_{j}$ is $1$, arm $a_{j}$ claims to be eligible under
the $l$-th state, and $0$ otherwise. Given a context $\mathbf{x}$, a
stochastic distribution over the $L$ states is observed, represented by a
probability vector $\mathbf{p}$ of length $L$. For CS routing, the state is
the type of customer issue, the claim is SME’s corresponding skill-set, and
$\mathbf{p}$ is the NLU predictive distribution. Note that a score can be
computed as the inner product of the claimed eligibility binary vector and
state probability vectors: $e_{j}:=\mathbf{c}_{j}^{\intercal}\mathbf{p}$, so
the state setup converges to the score setup. The major practical difference
between the two interfaces is the amount of effort in the claiming side: the
state interface simplifies the eligibility claims to static binary votes on a
finite set of states, while the score interface mandates scoring with context
awareness.

Consider a contextual bandit with a set of arms $\\{a_{1},a_{2},\dots\\}$. At
the $n$th round, context $\mathbf{x}_{n}$ is observed and eligibility score
$\mathbf{e}_{n}$ is either observed (score interface) or derived (state
interface). After an arm is pulled, a reward $r_{n}\in[0,1]$ is revealed. The
goal is to minimize the expected regret over $N$ rounds:
$\sum_{n=1}^{N}(\mathop{\mathbb{E}}[r|a^{n}_{*},\mathbf{x}_{n},\mathbf{e}_{n}]-\mathop{\mathbb{E}}[r|a^{n},\mathbf{x}_{n},\mathbf{e}_{n}])$,
where $a^{n}_{*}$ is the optimal action for this round in hindsight.

##  4 Methodology

The proposed algorithms run in order: Eligibility Controller (EC) to filter
out ineligible arms, and K-Boot to find the optimal one within the rest.
Below, we first introduce K-Boot to set the base and then EC.

###  4.1 K-Boot

K-Boot is a nonparametric bandit model. For a given context $\mathbf{x}$, it
estimates the reward for arm $a$ as the Nadaraya-Watson kernel weighted
average over the observed rewards of the $k$ nearest neighbors of $\mathbf{x}$
from all historical samples where arm $a$ was pulled. We use Bootstrap TS as
the exploration strategy. $k$-NN regression was known to fit well with
Bootstrap-Aggregation, with an analytical form of smoothed conditional mean
estimate that does not require actual resampling [15, 16]. However, sampling
from the confidence distribution of the mean estimate has little discussion.
We devise a trick to shrink the resampling range from all historical samples
to a local wrapper around the $k$-NN.

K-Boot is detailed in Algorithm 1. At iteration $n$ with context
$\mathbf{x}_{n}$, for the $m$th arm $a_{m}$, let $\mathcal{D}_{m}$ be the set
of historical samples where $a_{m}$ was pulled, and $N_{m}=|\mathcal{D}_{m}|$.
If $N_{m}$ is zero, we sample reward from a standard uniform distribution
(Line 6). If $N_{m}$ is greater than $K$, we first build an influential subset
$\mathcal{D}_{m}^{\prime}$ containing the $K^{\prime}$-NN of $\mathbf{x}_{n}$
($K<K^{\prime}$). Intuitively, the $K^{\prime}$-NN serves as a buffer to cover
enough sample variance around the $K$-NN, so that a Bootstrap on the
influential samples is a good approximate of that on all samples. Formally, a
sample is considered influential to make inference about $\mathbf{x}_{n}$, if
its probability of being in the $K$-NN of $\mathbf{x}_{n}$ _after_ a Bootstrap
on $\mathcal{D}_{m}$ is greater than $\varepsilon$. This probability is
computed analytically on Line 9, based on the derived equation (6) in [15].
Here the tolerance hyperparameter $\varepsilon$ controls the risk of missing
influential samples and thus the fidelity of approximated Bootstrap TS. In our
experiments with $N_{m}\leq 10^{4}$ and $\varepsilon=0.01$, $K^{\prime}$ is
empirically well bounded by $2K$. This process shrinks all later computation
to $K^{\prime}$ samples, with the overhead neighbors search cost $O(\log
N_{m})$ per sample (we used Hnswlib [17] for approximated search). If $N_{m}$
is less than $K$, $\mathcal{D}_{m}$ itself is the influential set. We then add
two pseudo samples to $\mathcal{D}_{m}^{\prime}$ on Line 14-15, in order to
expand reward’s empirical range for Bootstrap exploration [10]. To give
pseudo-samples proper contexts thus kernel weights, we set their distance to
$\mathbf{x}$ as that of a random observation in $\mathcal{D}_{m}^{\prime}$, so
its weight shrinks as more data seen. On Line 16-18, we then draw a Bootstrap
resample and select $K$ nearest samples from it to calculate the estimated
reward for $a_{m}$ as the kernel weighted average. we implement
$K_{h}(\cdot,\cdot)$ as the simplest $O(K)$ Nadaraya-Watson kernel estimator
with automatic bandwidth selection [20] \- more advanced models can be plugged
in.

As we model reward for each arm separately as a common practice, K-Boot is
flexible to add and removal of arms. This benefits applications like ours with
decentralized and independent arms management. In addition, K-Boot has simple
maintenance: (1) the nonparametric model has minimal assumption in data and
only a single important hyperparameter $K$ to balance between accuracy and
computation. $\varepsilon=0.01$ works well across our experiments. (2) the
algorithm is business friendly in terms of decision interpretability by
neighboring examples and allowing intuitive online instant modification of
model behaviors. For example, CS business owners may hide contacts with
undesired trending patterns during a specific period (e.g. under a legacy
policy), or let newly available SMEs "inherit" past example contacts or
eligibility claims (next section) via domain knowledge (e.g. a rehired agent
or additional training programs). The changes on data visibility will
instantly and predictably affect the bandit model in production, with clear
attribution. This data-driven while human-in-the-loop fungibility is essential
to fast-paced operational business like customer service.

Input : Number of iterations $N$, number of arms $M$, number of nearest
neighbors $K$, kernel function with bandwidth $K_{h}(\cdot,\cdot)$,
regularized incomplete beta function $F_{\alpha,\beta}(\cdot)$, approximation
tolerance $\varepsilon$.

1 Initialize sample pool $\mathcal{D}_{m}:=\varnothing$ and its size
$N_{m}:=0$, for each arm $m=1,\dots,M$

2 for  _$n=1,\cdots,N$_ do

3 Observe context $\mathbf{x}_{n}$

4 for  _$m=1,\cdots,M$_ do

5 if  _$N_{m}=0$_ then

6 Estimate reward: $\hat{r}_{m,n}\sim\mathcal{U}(0,1)$

7

8 else

9 if  _$N_{m} >K$_ then

10 $K^{\prime}:=\min(k^{\prime})$, s.t.
$\sum_{i=1}^{K}{[F_{i,N_{m}-i+1}(\frac{k^{\prime}}{N_{m}})-F_{i,N_{m}-i+1}(\frac{k^{\prime}-1}{N_{m}})]}>1-\varepsilon$

11 Find influential neighbors $\mathcal{D}_{m}^{\prime}:=$ the top
$K^{\prime}$ samples in $\mathcal{D}_{m}$, with the largest
$K_{h}(\mathbf{x}_{n},\cdot)$

12

13 else

14 Set $\mathcal{D}_{m}^{\prime}:=\mathcal{D}_{m}$

15

16 end if

17 Draw a random sample $(\mathbf{x}_{\star},r_{\star})$ from
$\mathcal{D}_{m}^{\prime}$

18 Add pseudo-samples:
$\mathcal{D}_{m}^{\prime}:=\mathcal{D}_{m}^{\prime}\cup\\{(\mathbf{x}_{\star},0),(\mathbf{x}_{\star},1)\\}$

19 Draw a Bootstrap sample $\mathcal{D}_{m}^{\star}$ from
$\mathcal{D}_{m}^{\prime}$

20 Find neighbors $\mathcal{D}_{m,K}^{\star}:=$ the top
$\min(K,|\mathcal{D}_{m}^{\star}|)$ samples in $\mathcal{D}_{m}^{\star}$, with
the largest $K_{h}(\mathbf{x}_{n},\cdot)$

21 Estimate reward:
$\hat{r}_{m,n}:=\sum_{i}{r_{i}K_{h}(\mathbf{x}_{n},\mathbf{x}_{i})}/\sum_{i}{K_{h}(\mathbf{x}_{n},\mathbf{x}_{i})}$,
summing over $\mathcal{D}_{m,K}^{\star}$

22

23 end if

24

25 end for

26 Pull arm $m^{\star}:=\arg\max_{m}\hat{r}_{m,n}$, and observe true reward
$r_{n}\in[0,1]$

27 Update
$\mathcal{D}_{m^{\star}}:=\mathcal{D}_{m^{\star}}\cup\\{(\mathbf{x}_{n},r_{n})\\}$
and $N_{m^{\star}}:=N_{m^{\star}}+1$

28

29 end for

Algorithm 1 K-Boot: a fully nonparametric contextual bandit

###  4.2 Eligibility Control

EC is used to recognize arm-eligibility and the associated uncertainties, for
optimized bandit exploration. In an ordinary contextual bandit model, the
eligibility information can be trivially considered as part of the context
$\mathbf{x}$ \- it is assumed to be positively correlated with $r$, thus
predictive as a plain input to a reward estimator. This assumes the reward
model is able to eventually learn the relation between $r$ and $e$ after
enough rounds. This trivial approach does not directly utilize eligibility to
limit the range of arm exploration, and may unnecessarily explore
inappropriate actions with catastrophic regret during cold-starts. The other
extreme is to strictly follow the eligibility information and ignore the
reward feedback: for the eligibility score interface, this could be simply
pulling the arm with the highest score as if it were an oracle; for the
eligibility state interface, this could be finding the state with the highest
probability then remove arms that did not claim that state. Therefore, the
empirical data would never be used to validate and correct the potentially
biased business logic - a common pitfall in practice.

The main idea of EC is to leave only the top-$k$ arms with the highest
eligibility scores before applying a normal bandit, and adjust $k$
periodically based on the empirical correlation between eligibility scores and
rewards. We use Spearman’s Rank Correlation Coefficient, denoted as $\rho$.
Using top-$k$ arms is a heuristic trade-off between $k=M$ (the trivial case;
$M$ is the total number of arms), and $k=1$ (the strict rule case).
Intuitively, for the case of perfect correlation between score and reward
($\rho=1$), $k=1$ is the oracle solution. If eligibility score has zero or
even negative correlation ($\rho\leq 0$) with reward, $k=M$ is the optimal
solution - otherwise the arm exploration is restricted adverserially or
randomly for no benefits. In the no-correlation case, the probability of “the
best arm by reward is not in the top-$k$ by score”, defined as a _leak_ , is
linear in $k$: $P(\text{leak}|k,\rho=0)=1-k/M$. It is obvious
$P(\text{leak}|k,0<\rho<1)<P(\text{leak}|k,\rho=0)$. This observation reveals
two insights: (1) $\alpha:=P(\text{leak}|k,\rho)$ characterizes a type of risk
in applying a top-$k$ score filter to arms; (2) when controlling the risk of a
leak at certain level, e.g. $\alpha=0.01$, $k$ is a function of $\rho$. The
true correlation $\rho$ between reward $r$ and eligibility score $e$ is
unknown, but can be estimated from historical observations:
$\\{(r_{i},e_{i})\\}_{i}$. Therefore, EC essentially calculates $k$ such that
the risk $P(\text{leak}|k,\hat{\rho})$ is controlled at a given level.

To pair with K-Boot, EC also models $P(\text{leak}|k,\rho)$ in a nonparametric
fashion to avoid extra assumptions. Per $\rho$, although Spearman’s rank
correlation coefficient is used for estimation, Kendall’s $\tau$ or any other
rank-based correlation measure applies similarly. Across the arms and rounds,
we assume the rank of $e$ is a noisy perturbation of the rank of $r$, and
parameterize this perturbation as “performing $p$ random neighbor inversions”.
An inversion is simply switching two elements in a sequence, and a neighbor
inversion switches two neighboring elements. Note $p=0$ indicates $\rho=1$
because the perturbed rank sequence is identical to the original one;
$p\rightarrow\infty$ is effectively a random permutation thus $\rho=0$. This
setup provides a generative process to simulate the joint distribution of all
parameters for a rank sequence of length $n$: (1) do $p$ random neighbor
inversions on the sorted sequence of ranks $(1,\cdots,n)$; (2) see if there is
a _leak_ , namely if the element $1$ is now at or beyond the $k$th position;
(3) compute $\hat{\rho}$ between the original and current sequences. The three
steps can be replicated for a sufficient number of times, to obtain the final
correlation coefficient $\hat{\rho}$ and risk level $\hat{\alpha}$ by
averaging individual $\hat{\rho}$ and counting the frequency of leaks. For
different combinations of $(k,p,n)$, as the above process does not depend on
any actual data, it can be performed offline in batch to get the corresponding
$(\hat{\rho},\hat{\alpha})$. The resulting empirical dictionary
$G:(n,\alpha,\rho)\rightarrow k$ is stored, and later queried during online
inference. To avoid unnecessary control in the edge case where eligibility
score turns out to be pure noise, $k$ is reset to $M$ (no EC) if $G$ outputs a
$k$ that is greater than the trivial value $(1-\alpha)M$. Finally note the
generative distribution of random neighbor inversions is assumed to be uniform
along the whole sequence, yielding the unbiasedness of the estimator
$\hat{\rho}$ even if the observed data points $\\{(r_{i},e_{i})\\}_{i}$ are
censored by the top-$k$ filter policy.

Input : Number of iterations $N$, number of arms $M$, risk level $\alpha$,
score initial threshold $k_{0}$, a pre-computed empirical dictionary
$G(n,\alpha,\rho)\rightarrow k$

1 Initialize threshold $k:=k_{0}$ and observation pool
$\mathcal{D}_{e}:=\varnothing$

2 for  _$n=1,\dots,N$_ do

3 Observe context $\mathbf{x}_{n}$, and eligibility scores
$\\{e_{1},\cdots,e_{M}\\}$, for each arm

4 Find the $k$th largest element $e_{[k]}$ among the scores

5 Sample reward for each arm if $e_{m}\geq e_{[k]}$ (Algorithm 1, Line 5-18)

6 Pull the $m^{\star}$th arm with highest reward estimate (Algorithm 1, Line
21-22)

7 Observe true reward $r_{n}$, and update
$\mathcal{D}_{e}:=\mathcal{D}_{e}\cup\\{(r_{n},e_{m^{\star}})\\}$

8 (Periodically) compute $\hat{\rho}$ from $\mathcal{D}_{e}$ and set
$k:=G(n,\alpha,\hat{\rho})$

9 Set $k:=M$ if $k\geq(1-\alpha)M$

10

11 end for

Algorithm 2 Eligibility Control

The full online EC process is described in Algorithm 2 (excluding the offline
dictionary generation). The eligibility state interface is converted into the
score interface before EC, so the scores are the only required inputs. The
algorithm takes K-Boot (Algorithm 1) as the bandit counterpart just for
demonstration, and applies to any bandit that has arm-independent reward
models. EC has a single hyperparameter: the controlled risk of a leak
$\alpha$. Note $\alpha$ is the risk of missing _the best_ arm, so its
influence on cumulative rewards depends on the arm reward distribution,
specifically the gap between the first and second best arm. We leave other
types of risk control mechanism with distributional assumptions to future
work.

##  5 Experiments

In this section, we evaluate the performance of K-Boot with two benchmarks:
LinUCB [4] and NeuralUCB [21]. The experiment setup mostly follows the
methodology reported in [21] with 4 synthetic simulations and 4 realworld
datasets. EC is tested on synthetic data with an eligibility score setup, then
on an Amazon Customer Service routing dataset. Datasets are introduced below.

Synthetic Datasets. The bandit has $M=10$ arms, and runs on $N=5000$
samples/rounds. It observes context with $d=20$ dimensions, each following
independent $\mathcal{N}(0,1)$. Four types of true reward functions are tested
- (1) _linear_ : $h_{0}(\mathbf{x})=0.1\mathbf{x}^{T}\mathbf{a}$; (2)
_quadratic_ : $h_{1}(\mathbf{x})=0.05(\mathbf{x}^{T}\mathbf{a})^{2}$; (3)
_inner-product_ :
$h_{2}(\mathbf{x})=0.002\mathbf{x}^{T}\mathbf{A}^{T}\mathbf{A}\mathbf{x}$; (4)
_cosine_ : $h_{3}(\mathbf{x})=\text{cos}(3\mathbf{x}^{T}\mathbf{a}$); where
each entry of the parameters $\mathbf{A}\in\mathbb{R}^{d\times d}$ and
$\mathbf{a}\in\mathbb{R}^{d}$ is drawn from an independent $\mathcal{N}(0,1)$,
different for each arm. The observed reward has noise:
$r:=h(\mathbf{x})+\varepsilon$, where
$\varepsilon\sim\mathcal{N}(0,\sigma_{r}^{2})$ and $\sigma_{r}$ is drawn from
$\mathcal{U}(0.01,0.5)$ independently for each arm. 20 runs are replicated by
random seeds.

Synthetic Datasets with Eligibility. Given above, the eligibility scores are
further simulated by perturbing the counter-factual reward of each arm:
$e:=wr+\varepsilon^{\prime}$, to induce the correlation. Here $w$ is an arm-
specific scaling coefficient draw from $\mathcal{U}(-0.1,1)$. It has a small
chance to leave $e$ and $r$ negatively correlated, as tolerating eligibility
claim error in systems under the overall positive correlation - the only
assumption of EC. The noise term
$\varepsilon^{\prime}\sim\mathcal{N}(0,\sigma^{2}_{e})$ controls the
correlation effect size. By setting a proper $\sigma_{e}$, the Spearman’s rank
correlation coefficient $\rho$ between reward and eligibility score can be
fixed at an arbitrary positive value.

UCI Classification. Four real-world datasets from UCI Machine Learning
Repository [22] are gathered: covertype, magic, statlog, and mnist. These
multi-class classification datasets are converted into multi-arm contextual
bandits problems, following the method in [4]: each class is treated as an
arm, and reward is $1$ if bandit pulls the correct arm (identify the correct
class) and $0$ otherwise. Each dataset is shuffled and split into 10 mutually
exclusive runs with 5000 samples each, and fed to bandit one in each round
(magic has less than 50000 samples so resampling is performed).

Figure 2: Benchmarking K-Boot, LinUCB and NeuralUCB. Left half: synthetic
datasets; right half: UCI datasets. Model hyperparameters are set as the best
on synthetic datasets. Metric is averaged across 10 runs with an 80%
confidence band.

CS Routing with Eligibility. Agent skill-level routing is considered: CS
agents are assigned to different skill groups by operation teams, and the
routing system determines which skill is required to resolve a given customer
contact based on the customer profile, policy rules and natural language
understanding. As a proof of concept before any online experiments, we
formulate an offline bandit dataset with historical observations. About 2
million Amazon US customer service text chats with bot-to-agent routing are
gathered. To introduce stochasticity, a historical routing policy emulator is
trained on a 95% random subset of the chats, by taking the customer-bot
transcripts before the routing action as input to predict which skill the
system chose. Specifically, the emulator consists of a pretrained GPT-2
transformer encoder [23], with a multi-class sequence classifier head to
predict the top 20 skill groups. The model is trained (fine-tuned) for one
epoch with learning rate $10^{-4}$ and batch size 32. For the bandit
simulation, the final actual resolving skill, after all the potential agent-
to-agent transfers since the initial routing, serves as the ground truth - if
the routed skill agrees with the final skill, the action is considered as
accurate and having avoided a potential transfer. At each round, the bandit
receives a 256-dimensional text embedding from the same GPT-2 encoder as
observed context, and a 20-dimensional probabilistic prediction from the
emulator as eligibility scores for each arm/skill. If the bandit chooses a
skill matching the final one, reward is $1$ and otherwise $0$. In this case,
the cumulative regret is an upper bound for the number of transferred
contacts, because agents assigned to different skills may resolve the contact
regardless (e.g. digital order agents are often equipped to resolve retail
order issues, so they may not transfer an incorrectly routed contact). The
rest 5% chats are used to generate 10 bandit runs with 8000 samples
each111From another perspective, this offline bandit-with-eligibility
simulation setup is equivalent to ”using a bandit for online improvement of a
black-box probabilistic classifier with unknown accuracy”.. We observe that
the empirical $\rho$ across the runs is 0.3492. We leave the below to future
work: (1) online experiments to measure real transfers and positive customer
reviews as the reward metric; (2) agent-level routing given agent profiles and
finer grain eligibility definitions than skill groups.

###  5.1 K-Boot Benchmarks

We compare K-Boot with LinUCB and NeuralUCB on both synthetic and UCI
classification datasets. With the 4 synthetic datasets, we first select the
following hyperparameters for each Bandit algorithm of interest (1) number of
nearest neighbors $k\in\\{20,50,100\\}$ for K-Boot; (2) weight parameter for
exploration $\alpha\in\\{0.1,1.0,10\\}$ for LinUCB; (3) regularization
parameter $\lambda\in\\{0.1,0.01,0.001\\}$ and exploration parameter
$\nu\in\\{0.2,0.02,0.002\\}$ for NeuralUCB - other hyperparameters such as
learning rate, batch settings and number of layers are set the same as in the
original code base222https://github.com/uclaml/NeuralUCB. We settle on
$k=100,\alpha=10,(\lambda,\nu)=(0.001,0.002)$ per having the lowest cumulative
regret averaged across $h_{0}\sim h_{3}$ and 10 replicated runs, and carry
these values over to compare the actual model performance on the 4 UCI
datasets. We believe this setup is more realistic because most bandit
applications do not have the luxury for intensive hyperparameter tuning due to
small sample size or non-stationary environment. Finally, all experiments in
this paper implement online, single-sample model updates. Figure 2 left shows
the performance of the models with final selected hyperparameters. Except for
the linear reward scenario where LinUCB/NeuralUCB has advantage in
correct/close model specification, there is no significant performance
difference between K-Boot and NeuralUCB while LinUCB is inferior. Figure 2
right shows the performance comparison on the UCI real-world datasets. K-Boot
and NeuralUCB have a tie of winning on two datasets each, and LinUCB is
consistently the worst. By examing the 80% confidence band (P10-P90 across 10
runs), we find NeuralUCB has larger performance volatility (wider bands) on
real data than the other two models, due to learning instability in certain
runs.

###  5.2 Eligibility Control Testing

Figure 3: EC under different Spearman’s Correlation $\rho$ between eligibility
score and reward, with different risk level $\alpha$. The bandit part is
K-Boot and eligibility scores are not in context.

For the synthetic data, we control $\sigma_{e}$ to simulate different levels
of reward-reflecting reliability in eligibility scores, with resulting
$\rho(r,e)\in\\{0.05,0.15,0.3,0.45,0.6,0.75\\}$, for each true reward function
$h_{0}$ \- $h_{3}$. In the algorithm, we set different risk level $\alpha$ in
EC. Note $\alpha=0$ is effectively not using EC, and we abuse the notation
$\alpha\to 1$ to denote the strict top-1 policy: pull the arm with the highest
eligibility score.

Figure 3 shows the results of applying EC to K-Boot, with eligibility scores
used by EC only (explained later). When the signal in $e$ is weak (low
$\rho$), EC adaptively raises the top-$k$ threshold close to $M$, achieving
the same performance as no EC. As $\rho$ grows, the advantage reveals - using
EC is consistently better than not. The dynamic thresholding may dominate the
top-1 policy even under strong eligibility signals, with the right $\alpha$.
EC performs the best for $\alpha=0.5$ across all synthetic datasets, and the
same value is carried over to the next experiment on CS Routing data.

EC can be applied to other bandits. Figure 4 shows the same synthetic data
results but with EC + LinUCB. Here eligibility scores are also added to bandit
context. The reason why the previous experiment did not take scores as K-Boot
input is because $k$-NN has no native feature selection mechanism. If
eligibility score is close to white noise (low $\rho$), model struggles to fit
the reward, leading to a distraction from other presented visual patterns. For
LinUCB, such side-effect is minimal for the simulated noise is Gaussian, so it
is a better condition to test the difference between the trivial way versus
the EC way of utilizing eligibility. EC still dominates no-EC in most cases.
There are a few exceptions for the linear true reward function $h_{0}$, where
$\alpha=0.5$ is worse because LinUCB learns so well that taking a high risk of
missing the best arm is not cost-effective. An interesting observation is
that, while the strict top-1 rule was dominated by K-Boot + EC (Figure 3), it
actually beats LinUCB + EC for nonlinear true reward functions even at
$\rho=0.15$. This indicates the power of the bandit model is still a key
driver for ML to out-perform static rules.

Figure 4: EC under different Spearman’s Correlation $\rho$ between eligibility
score and reward, with different risk level $\alpha$. The bandit part is
LinUCB and eligibility scores are part of context.

Figure 5 shows the result on CS Routing data, where EC significantly improves
routing accuracy. Routing to the skill with the highest probability from the
emulator serves a stochastic surrogate of the existing policy. Pure K-Boot
result without knowing the emulator outputs is set as a baseline. With only
8000 samples, the average accuracy of the emulator policy is improved by
K-Boot + EC from $53.37\%$ to $57.78\%$.

Figure 5: CS Routing Results. Metric is averaged across 10 runs with an 80%
confidence band.

##  6 Conclusions

We proposed a nonparametric contextual Bandit algorithm K-Boot with arm-level
eligibility control (EC) for routing customer contacts to eligible SMEs in
real-time. While K-Boot and EC are proposed here as a suite, each can be
applied independently - K-Boot is a general Bandit algorithm and EC can
control arm-eligibility for other bandits. We compared K-Boot with LinUCB and
NeuralUCB. When looking at average regret performance over simulation runs,
K-Boot and NeuralUCB had a tie in winning scenarios and were comparable in
terms of robustness to different data distributions. Both worked better than
LinUCB. However, we observe larger performance variability for NeuralUCB as
opposed to K-Boot. We further found the EC component improved K-Boot’s
performance on both synthetic datasets and a simulation scenario in CS routing
when eligibility exists.

## References

  * Elena et al. [2021] G. Elena, K. Milos, I. Eugene,  Survey of multiarmed bandit algorithms applied to recommendation systems,  International Journal of Open Information Technologies 9 (2021) 12–27.
  * Liu and Li [2021] Y. Liu, L. Li,  A map of bandits for e-commerce,  arXiv preprint arXiv:2107.00680 (2021).
  * Lattimore and Szepesvári [2020] T. Lattimore, C. Szepesvári, Bandit algorithms, Cambridge University Press, 2020.
  * Li et al. [2010] L. Li, W. Chu, J. Langford, R. E. Schapire,  A contextual-bandit approach to personalized news article recommendation,  in: Proceedings of the 19th international conference on World wide web, 2010, pp. 661–670.
  * Sajeev et al. [2021] S. Sajeev, J. Huang, N. Karampatziakis, M. Hall, S. Kochman, W. Chen,  Contextual bandit applications in a customer support bot,  in: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 3522–3530.
  * Upadhyay et al. [2019] S. Upadhyay, M. Agarwal, D. Bounneffouf, Y. Khazaeni,  A bandit approach to posterior dialog orchestration under a budget,  arXiv preprint arXiv:1906.09384 (2019).
  * Chapelle and Li [2011] O. Chapelle, L. Li,  An empirical evaluation of thompson sampling,  Advances in neural information processing systems 24 (2011).
  * Graepel et al. [2010] T. Graepel, J. Quiñonero Candela, T. Borchert, R. Herbrich,  Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft’s bing search engine,  in: Proceedings of the 27th International Conference on Machine Learning ICML 2010, Invited Applications Track (unreviewed, to appear), 2010.
  * Osband and Van Roy [2015] I. Osband, B. Van Roy,  Bootstrapped thompson sampling and deep exploration,  arXiv preprint arXiv:1507.00300 (2015).
  * Kveton et al. [2019] B. Kveton, C. Szepesvari, S. Vaswani, Z. Wen, T. Lattimore, M. Ghavamzadeh,  Garbage in, reward out: Bootstrapping exploration in multi-armed bandits,  in: International Conference on Machine Learning, PMLR, 2019, pp. 3601–3610.
  * Riou and Honda [2020] C. Riou, J. Honda,  Bandit algorithms based on thompson sampling for bounded reward distributions,  in: Algorithmic Learning Theory, PMLR, 2020, pp. 777–826.
  * Srinivas et al. [2009] N. Srinivas, A. Krause, S. M. Kakade, M. Seeger,  Gaussian process optimization in the bandit setting: No regret and experimental design,  arXiv preprint arXiv:0912.3995 (2009).
  * Chowdhury and Gopalan [2017] S. R. Chowdhury, A. Gopalan,  On kernelized multi-armed bandits,  in: International Conference on Machine Learning, PMLR, 2017, pp. 844–853.
  * Hensman et al. [2013] J. Hensman, N. Fusi, N. D. Lawrence,  Gaussian processes for big data,  arXiv preprint arXiv:1309.6835 (2013).
  * Steele [2009] B. M. Steele,  Exact bootstrap k-nearest neighbor learners,  Machine Learning 74 (2009) 235–255.
  * Biau et al. [2010] G. Biau, F. Cérou, A. Guyader,  On the rate of convergence of the bagged nearest neighbor estimate.,  Journal of Machine Learning Research 11 (2010).
  * Malkov and Yashunin [2018] Y. A. Malkov, D. A. Yashunin,  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs,  IEEE transactions on pattern analysis and machine intelligence 42 (2018) 824–836.
  * Johnson et al. [2019] J. Johnson, M. Douze, H. Jégou,  Billion-scale similarity search with GPUs,  IEEE Transactions on Big Data 7 (2019) 535–547.
  * Guo et al. [2020] R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simcha, F. Chern, S. Kumar,  Accelerating large-scale inference with anisotropic vector quantization,  in: International Conference on Machine Learning, PMLR, 2020, pp. 3887–3896.
  * Silverman [2018] B. W. Silverman, Density estimation for statistics and data analysis, Routledge, 2018\.
  * Zhou et al. [2019] D. Zhou, L. Li, Q. Gu,  Neuralucb: Contextual bandits with neural network-based exploration (2019).
  * Dua and Graff [2017] D. Dua, C. Graff, UCI machine learning repository, 2017. URL: http://archive.ics.uci.edu/ml.
  * Radford et al. [2019] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al.,  Language models are unsupervised multitask learners,  OpenAI blog 1 (2019) 9.