with order $1$; on the other hand,
$\mathrm{rank}_{\mathbb{Z}}H^{0}(G_{v},\mathbb{Z})=1$ and prop. 6.8 gives
$\chi_{v}(\mathbb{Z})=1/\log(q)$. This concludes the proof. ∎

######  Remark.

  *   * •

The identification of the sign in Theorem 6.23 was inspired by [GS20].

  * •

The formula for proper smooth curves was already shown in [GS20, 3.1]; note
that the $\log(q)$ factor in ibid. is integrated in our Weil-étale Euler
characteristic, coming from the regulator pairing.

##  7 Twisted Artin $L$-functions of integral $G_{K}$-representations

We obtain as a corollary a result generalizing and precising [Tra16] ; we
allow singular points, we work also on curves, there is no need for a
correcting factor for the $2$-torsion, and we identify the sign.

Let $K$ be a global field and $X$ be an irreducible scheme, finite type over
$\mathbb{Z}$, of dimension $1$ and with residue field at the generic point
$K$. The morphism $X\to\operatorname{Spec}(\mathbb{Z})$ is either dominant or
factors through $\operatorname{Spec}(\mathbb{F}_{p})$, so $X$ is either a
curve over $\mathbb{F}_{p}$ or $X\to\operatorname{Spec}(\mathbb{Z})$ is quasi-
finite, hence by Zariski’s main theorem is the open subscheme of the spectrum
of a finite $\mathbb{Z}$-algebra, thus if $X$ is reduced of an order in $K$.
The singular locus of $X$ will be denoted $Z$ and the regular locus $U$.

Following [Den87], define the complex of sheaves

$\mathbb{G}_{X}=\left[(g_{\eta})_{\ast}\mathbb{G}_{m,\eta}\to\bigoplus_{v\in
X_{0}}(i_{v})_{\ast}\mathbb{Z}\right]$

where $X_{0}$ denotes the closed points, $\eta$ is the generic point and
$g_{\eta}$ (resp. $i_{v}$) is the canonical morphism
$\operatorname{Spec}(\mathcal{O}_{X,\eta})\to X$ (resp. $v\to X$). If $X$ is
regular, we have $\mathbb{G}_{X}\simeq\mathbb{G}_{m,X}$ [Gro67, 21.6.9].

Let $\pi:Y\to X_{red}\to X$ denote the normalization of $X_{red}$. Define
cohomology with compact support as in [Mil06, II.6], through the fiber
sequence:

$R\Gamma_{c}(X,-)\to R\Gamma(X,-)\to\prod_{v\in
S}R\Gamma(K_{v},(-)_{\eta_{v}})$

where $S$ is the set of places of $K$ not corresponding to a point of $Y$. The
corresponding cohomology groups will be denoted again $H^{i}_{c}(X,-)$;
propositions 2.1 and 2.4, as well as Artin-Verdier duality (theorem 3.2) still
hold ; this is easily seen by comparing $X$ to its regular locus $U$.

######  Corollary 7.1.

Let $f:X\to T$ denote either a quasi-finite morphism $X\to
T:=\mathbb{P}^{1}_{\mathbb{F}_{p}}$ (in the function field case), which exists
by the projective Noether normalization lemma, or the quasi-finite structural
morphism $X\to T:=\operatorname{Spec}(\mathbb{Z})$ (in the number field case);
then $f_{!}$ is well-defined. Let $F$ be a $\mathbb{Z}$-constructible sheaf on
$X$. We have the order and special value formula at $s=0$:

$\displaystyle r_{X}(F)=E_{T}(f_{!}F)$ $\displaystyle
L_{X}^{\ast}(F,0)=(-1)^{\mathrm{rank}_{\mathbb{Z}}F(K)}\chi_{T}(f_{!}F)$

Explicitly, we have:

$\displaystyle E_{T}(f_{!}F)$
$\displaystyle=\mathrm{rank}_{\mathbb{Z}}H^{1}_{c}(X,F)-\mathrm{rank}_{\mathbb{Z}}H^{0}_{c}(X,F)=\mathrm{rank}_{\mathbb{Z}}\operatorname{Hom}_{X}(F,\mathbb{G}_{X})-\mathrm{rank}_{\mathbb{Z}}\operatorname{Ext}^{1}(F,\mathbb{G}_{X})$
$\displaystyle\chi_{T}(f_{!}F)$
$\displaystyle=\frac{R(F)[\operatorname{Hom}_{X}(F,\mathbb{G}_{X})_{tor}][H^{0}_{c}(X,F)_{tor}]}{[\operatorname{Ext}^{1}_{X}(F,\mathbb{G}_{X})_{tor}][H^{1}_{c}(X,F)_{tor}]}$

where $R(F):=\frac{R_{1}(F)}{R_{0}(F)}$ with $R_{0}(F)$ is the absolute value
of the determinant of the pairing

$H^{0}_{c}(X,F)_{\mathbb{R}}\times\operatorname{Ext}^{1}_{U}(F,\mathbb{G}_{X})_{\mathbb{R}}\to\mathbb{R}$

and $R_{1}(g_{\ast}M)$ the absolute value of the determinant of the pairing

$H^{1}_{c}(X,F)_{\mathbb{R}}\times\operatorname{Hom}_{X}(F^{,}\mathbb{G}_{X})_{\mathbb{R}}\to\mathbb{R}$

in bases modulo torsion.

###### Proof.

We have $L_{T}(f_{!}F,s)=L_{X}(F,s)$ and
$R\Gamma_{c}(T,f_{!}F)=R\Gamma_{c}(X,F)$. The finite base change theorem
implies that

$Rf^{!}\mathbb{G}_{m,T}=Rf^{!}\mathbb{G}_{T}=\mathbb{G}_{X},$

which shows that
$R\operatorname{Hom}_{T}(f_{!}g_{\ast}M,\mathbb{G}_{m})=R\operatorname{Hom}_{X}(g_{\ast}M,\mathbb{G}_{X})$.
Theorem 6.23 then gives the first result, and for the second it suffices to
apply proposition 6.21. ∎

Denote $g:\operatorname{Spec}(K)\to X$ the canonical morphism, and let $M$ be
a finite type discrete $G_{K}$-module.

######  Definition 7.2.

The Artin L-function of $M$ (twisted by $X$) is defined as the Euler product

$L_{K,X}(M,s):=L_{X}(g_{\ast}M,s)=\prod_{v\in X_{0}}L_{v}(g_{\ast}M,s)$

where $X_{0}$ are the closed points of $X$, with local factors

$L_{v}(g_{\ast}M,s)=\det(1-N(v)^{-s}\mathrm{Frob}_{v}|(g_{\ast}M)_{v}\otimes\mathbb{C})$

where as before we denote $(-)_{v}$ the pullback to $v$ and
$\mathrm{Frob}_{v}\in G_{v}:=\mathrm{Gal}(\kappa(v)^{sep}/\kappa(v))$ is the
(arithmetic) Frobenius.

Define $r_{K,X}(M)$ the order at $s=0$ and $L_{K,X}^{\ast}(M,0)$ the special
value at $s=0$.

######  Proposition 7.3.

If $v$ is a non-singular point, thus corresponding to a place of $K$, then

$(g_{\ast}M)_{v}=M^{I_{v}}$

with its natural $G_{v}$-action, where $I_{v}$ is the inertia subgroup of a
place $\bar{v}$ of $K^{sep}$ above $v$.

###### Proof.

This is local so we can suppose $X$ is affine and regular. Fix an embedding
$K^{sep}\hookrightarrow K_{v}^{sep}$ ; this determines an extension $\bar{v}$
of $v$ on $K^{sep}$. Let $\mathcal{O}_{v}^{sh}$ be the strict henselization of
$X$ at $v$; then $\mathcal{O}_{v}^{sh}$ is the integral closure of
$\mathcal{O}_{X}(X)$ in the ring of integers of the maximal unramified
extension $K_{v}^{un}$ of the completion of $K$ at $v$. Denote $K_{v}^{sh}$
the field of fractions. The above embedding identifies $K_{v}^{sh}$ with the
subfield of $K^{sep}$ fixed by the inertia subgroup $I_{v}$. The formula for
stalks of pushforwards then gives

$(g_{\ast}M)_{v}=H^{0}(K_{v}^{sh},M)=M^{I_{v}}$

endowed with its natural $G_{v}\simeq D_{v}/I_{v}$-action, where
$D_{v}=\\{\sigma,\sigma\bar{v}=\bar{v}\\}\subset G_{K}$ is the decomposition
group. ∎

######  Remark.

  *   * •

If $X$ is regular, the twisted Artin L-function is by the above proposition
the usual Artin L-function associated to $S$ :

$L_{K,X}(M,s)=L_{S}(M,s)=\prod_{v\notin
S}\det(1-N(v)^{-s}\mathrm{Frob}_{v}|(M\otimes\mathbb{C})^{I_{v}})$

  * •

For $M=\mathbb{Z}$ we have $g_{\ast}\mathbb{Z}=\mathbb{Z}$ and
$L_{K,X}(\mathbb{Z},s)=\zeta_{X}(s)$ is the arithmetic zeta function of $X$.

  * •

The singular locus $Z$ of $X$ is finite and if $X$ is regular, it can be
completed with finitely many regular points to become proper. Thus the
L-function twisted by $X$ differs by a finite number of factors from the
ordinary Artin L-function.

######  Corollary 7.4.

Let $f:X\to T$ denote either a quasi-finite morphism $X\to
T:=\mathbb{P}^{1}_{\mathbb{F}_{p}}$ (in the function field case), which exists
by the projective Noether normalization lemma, or the quasi-finite structural
morphism $X\to T:=\operatorname{Spec}(\mathbb{Z})$ (in the number field case);
then $f_{!}$ is well-defined. We have the order and special value formula at
$s=0$:

$\displaystyle r_{K,X}(M)=E_{T}(f_{!}g_{\ast}M)$ $\displaystyle
L_{K,X}^{\ast}(M,0)=(-1)^{\mathrm{rank}_{\mathbb{Z}}M}\chi_{T}(f_{!}g_{\ast}M)$

###### Proof.

The sheaf $g_{\ast}M$ is $\mathbb{Z}$-constructible. ∎

######  Corollary 7.5.

Suppose $X$ is affine. We have the order and special value formula at $s=0$
for the arithmetic zeta function of $X$:

$\displaystyle\mathrm{ord}_{s=0}\zeta_{X}$
$\displaystyle=\mathrm{rank}_{\mathbb{Z}}(CH_{0}(X,1))$
$\displaystyle\zeta_{X}^{\ast}(0)$
$\displaystyle=-\frac{[\mathrm{CH}_{0}(X)]R_{X}}{\omega}$

where $R_{X}$ is the absolute value of the determinant of the regulator
pairing

$H^{1}_{c}(X,\mathbb{Z})_{\mathbb{R}}\times\mathrm{CH}_{0}(X,1)_{\mathbb{R}}\to\mathbb{R}$

after a choice of bases modulo torsion and $\omega$ is the number of roots of
unity in $K$.

###### Proof.

We apply cocorollary 7.1 to $F=\mathbb{Z}$. Using
$R^{q}g_{\ast}\mathbb{G}_{m}=0$ for $q>0$ (see [Mil06, II.1.4]),
hypercohomology computations give

$\displaystyle H^{0}(X,\mathbb{G}_{X})$
$\displaystyle=\mathrm{ker}(K^{\times}\xrightarrow{\sum\mathrm{mult}_{v}}\bigoplus_{v\in
X_{0}}\mathbb{Z})=\mathrm{CH}_{0}(X,1)$ $\displaystyle
H^{1}(X,\mathbb{G}_{X})$
$\displaystyle=\mathrm{coker}(K^{\times}\xrightarrow{\sum\mathrm{mult}_{v}}\bigoplus_{v\in
X_{0}}\mathbb{Z})=\mathrm{CH}_{0}(X)$

Moreover it is clear from the above that $\mathrm{CH}_{0}(X,1)_{tor}=\mu(K)$.

From the short exact sequence

$0\to\mathbb{Z}\to\pi_{\ast}\mathbb{Z}\to\oplus_{v\in
Z}i_{v,\ast}\left(\oplus_{\pi(w)=v}\mathrm{ind}^{G_{w}}_{G_{v}}\mathbb{Z}\right)/\mathbb{Z}\to
0,$

with $\pi:Y\to X$ the normalization,
$G_{v}=\mathrm{Gal}(\kappa(v)^{sep}/\kappa(v))$ and $G_{w}$ the Galois groups
of the residue fields, we find by taking cohomology with compact support that
$H^{0}_{c}(X,\mathbb{Z})=0$ and $H^{1}_{c}(X,\mathbb{Z})$ is torsion-
free151515see the computations in the proof of proposition 6.9. The regulator
$R(\mathbb{Z})$ contains no contribution from the perfect pairing of trivial
vector spaces

$H^{0}_{c}(X,\mathbb{Z})_{\mathbb{R}}\times
CH_{0}(X)_{\mathbb{R}}\to\mathbb{R}$

hence we have $R(\mathbb{Z})=R_{X}$. ∎

######  Remark.

  *   * •

We can compute $\mathrm{rank}_{\mathbb{Z}}\mathrm{CH}_{0}(X,1)=s+t-1$ where
$s=[S]$ and $t=\sum_{v\in Z}([\pi^{-1}(v)]-1)$ by using the localization
sequences associated to the open-closed decompositions $U\hookrightarrow
X\hookleftarrow Z$ and $U\hookrightarrow Y\hookleftarrow\pi^{-1}Z$.

  * •

Note that the proof above shows that
$\mathrm{CH}_{0}(X)=\operatorname{Ext}^{1}_{X}(\mathbb{Z},\mathbb{G}_{X})$ is
torsion, and Artin-Verdier duality shows that it is finite type, hence it is
finite.

######  Corollary 7.6.

Suppose $X$ is a proper curve, and denote $\mathbb{F}_{q}$ the field of
constants of $K$. We have the order and special value formula at $s=0$ for the
arithmetic zeta function of $X$:

$\displaystyle\mathrm{ord}_{s=0}\zeta_{X}$
$\displaystyle=\mathrm{rank}_{\mathbb{Z}}(\mathrm{CH}_{0}(X,1))-1$
$\displaystyle\zeta_{X}^{\ast}(0)$
$\displaystyle=-\frac{[\mathrm{CH}_{0}(X)_{tor}]R_{X}}{\omega\log(q)}$

where $R_{X}$ is the absolute value of the determinant of the regulator
pairing

$H^{1}(X,\mathbb{Z})_{\mathbb{R}}\times\mathrm{CH}_{0}(X,1)_{\mathbb{R}}\to\mathbb{R}$

after a choice of bases modulo torsion and $\omega$ is the number of roots of
unity in $K$161616Thus $\omega=q-1$.

###### Proof.

As in the previous proof we have
$H^{0}(X,\mathbb{G}_{X})=\mathrm{CH}_{0}(X,1)$,
$\mathrm{CH}_{0}(X,1)_{tor}=\mu(K)$ and
$H^{1}(X,\mathbb{G}_{X})=\mathrm{CH}_{0}(X)$, but this time we have
$H^{0}(X,\mathbb{Z})=\mathbb{Z}$. We now want to identify the pairing
$H^{0}(X,\mathbb{Z})_{\mathbb{R}}\times\mathrm{CH}_{0}(X)_{\mathbb{R}}\to\mathbb{R}$
coming from the regulator. For a closed point $w\in Y$ above $v\in X$, denote
$f_{w}:=[\kappa_{w}:\kappa_{v}]$ the residual degree. Considering $Y$ as a
curve over $\mathbb{F}_{p}$, the degree map
$\deg_{Y}:\mathrm{Pic}(Y)\to\mathbb{Z}$ has image $f\mathbb{Z}$, where
$p^{f}=q$. This easily implies that there is a similarly-defined degree map
$\deg_{X}:\mathrm{CH}_{0}(X)\to\mathbb{Z}$ with image $f\mathbb{Z}$. The snake
lemma applied to

${0}$${K^{\times}/\mathcal{O}_{Y}(Y)^{\times}}$${\bigoplus_{w\in
Y_{0}}\mathbb{Z}}$${\mathrm{Pic}(Y)}$${0}$${0}$${K^{\times}/\mathrm{CH}_{0}(X,1)}$${\bigoplus_{v\in
X_{0}}\mathbb{Z}}$${\mathrm{CH}_{0}(X)}$${0}$

shows that
$\mathrm{coker}(\mathrm{Pic}(Y)\to\mathrm{CH}_{0}(X))=\bigoplus_{v\in
Z}\mathbb{Z}/m_{v}\mathbb{Z}$, where
$m_{v}=\mathrm{pgcd}\\{f_{w},\leavevmode\nobreak\ \pi(w)=v\\}$. Since
$\mathrm{coker}(\mathrm{Pic}(Y)\to\mathrm{CH}_{0}(X))=\mathrm{coker}(\mathrm{Pic}^{0}(Y)\to\mathrm{ker}(\mathrm{deg}_{X}))$,
it follows from the finiteness of $\mathrm{Pic}^{0}(Y)$ that
$\mathrm{ker}(\mathrm{deg}_{X})$ is finite and hence equals
$\mathrm{CH}_{0}(X)_{tor}$. It is clear from the constructions that the
pairing
$H^{0}(X,\mathbb{Z})_{\mathbb{R}}\times\mathrm{CH}_{0}(X)_{\mathbb{R}}\to\mathbb{R}$
comes from the pairing
$H^{0}(X,\mathbb{Z})\times\mathrm{CH}_{0}(X)\to\mathrm{CH}_{0}(X)\xrightarrow{deg}f\mathbb{Z}$,
hence similarly to the proof of 6.10 we find that its determinant is
$f\log(p)=\log(q)$ ; it follows that $R(\mathbb{Z})=R_{X}/\log(q)$. ∎

######  Remark.

  *   * •

We can compute $\mathrm{rank}_{\mathbb{Z}}\mathrm{CH}_{0}(X,1)=t$ where
$t=\sum_{v\in Z}([\pi^{-1}(v)]-1)$ by using the localization sequences
associated to the open-closed decompositions $U\hookrightarrow X\hookleftarrow
Z$ and $U\hookrightarrow Y\hookleftarrow\pi^{-1}Z$. Thus if $X$ is unibranch
we have $R_{X}=1$.

  * •

We showed in the proof above that $\mathrm{CH}_{0}(X)_{tor}$ is the group of
classes of $0$-cycles of degree $0$.

######  Remark.

In [JP20], Jordan and Poonen prove an analytic class number formula for the
zeta function of a reduced affine finite type $\mathbb{Z}$-scheme of pure
dimension $1$. They note that even for non-maximal orders in number fields,
the formula seems new. Let us compare their results with ours. Define the
completed zeta function

$\widehat{\zeta}_{K}(s)=|d_{K}|^{s/2}\zeta_{Y}(s)\prod_{v\in
S}L_{v}(\mathbb{Z},s)$

where $Y$ is as before the normalization of $X$ in $K$, $d_{K}$ is the
discriminant of $K$, $L_{v}(\mathbb{Z},s)$ is the usual local factor if $v$ is
nonarchimedean and

$\displaystyle L_{v}(\mathbb{Z},s)$
$\displaystyle=2(2\pi)^{s}\Gamma(s),\leavevmode\nobreak\ v\leavevmode\nobreak\
\text{complex}$ $\displaystyle L_{v}(\mathbb{Z},s)$
$\displaystyle=\pi^{\frac{-s}{2}}\Gamma(\frac{s}{2}),\leavevmode\nobreak\
v\leavevmode\nobreak\ \text{real}$

By comparing $\zeta_{X}$ and $\zeta_{Y}$, we get the equality

$\zeta_{X}(s)=\widehat{\zeta}_{K}(s)|d_{K}|^{-s/2}\prod_{w\in
S}L_{w}(\mathbb{Z},s)^{-1}\prod_{v\in
Z}\left(\frac{L_{v}(\mathbb{Z},s)}{\prod_{\pi(w)=v}L_{w}(\mathbb{Z},s)}\right)$

Using the functional equation
$\widehat{\zeta}_{K}(s)=\widehat{\zeta}_{K}(1-s)$, we find the order and
special value at $s=0$ :

$\displaystyle\mathrm{ord}_{s=0}\zeta_{X}=s+t-1$
$\displaystyle\zeta_{X}^{\ast}(0)=-\frac{h(\mathcal{O})R(\mathcal{O}))}{\omega(\mathcal{O})[\widetilde{\mathcal{O}}:\mathcal{O}]}\prod_{v\in
Z}\frac{\gamma_{v}}{\prod_{\pi(w)=v}\gamma_{w}}$

where $Y=\operatorname{Spec}(\widetilde{\mathcal{O}})$,
$\gamma_{v}=\frac{1-N(v)^{-1}}{\log(N(v))}$,
$h(\mathcal{O})=[\mathrm{Pic}(X)]$, $R(\mathcal{O})$ is the covolume of the
image in $\mathbb{R}^{s}$ of $\mathcal{O}^{\times}$ via the classical
regulator of $\widetilde{\mathcal{O}}$, and
$\omega(\mathcal{O})=\mathcal{O}^{\times}_{tor}$. Our formula at $s=0$ seems
to be better in several aspects: it does not suppose $X$ to be reduced nor
affine and it is defined in terms of invariants intrisic to $X$.

##  Appendix A Some determinant computations

Let $M$ be a perfect complex of abelian group or $\mathbb{R}$-vector spaces.
We will denote $H^{ev}M:=\oplus_{i\equiv 0[2]}H^{i}M$ and
$H^{od}M:=\oplus_{i\equiv 1[2]}H^{i}M$. We fix determinant functors
$\det_{\mathbb{Z}}$ and $\det_{\mathbb{R}}$ on the derived categories of
perfect complexes of abelian groups/$\mathbb{R}$-vector spaces extending the
usual one on finite type projective modules (see section 6.1).

######  Lemma A.1.

Let M be a perfect complex of abelian groups with finite cohomology groups.
Then

$\mathrm{det}_{\mathbb{Z}}M\subset(\det_{\mathbb{Z}}M)_{\mathbb{R}}\simeq\det_{\mathbb{R}}M_{\mathbb{R}}\simeq\det_{\mathbb{R}}0=\mathbb{R}$

corresponds to the lattice

$\frac{1}{\prod_{i}[H^{i}(M)]^{(-1)^{i}}}\mathbb{Z}\subset\mathbb{R}$

###### Proof.

We have an isomorphism of determinants171717[Bre11, Section 5, in particular
prop 5.5 and its proof] and [Bre08, prop 3.4 and its proof]
$\det_{\mathbb{Z}}M\simeq\det_{\mathbb{Z}}H^{\ast}M\simeq\det_{\mathbb{Z}}H^{ev}M\otimes(\det_{\mathbb{Z}}H^{od}M)^{-1}$
compatible with base change, so we may assume $M$ to be concentrated in degree
$0$. Since $\det_{\mathbb{Z}}(A\oplus
B)\simeq\det_{\mathbb{Z}}(A)\otimes\det_{\mathbb{Z}}(B)$, we further reduce to
$M=\mathbb{Z}/m\mathbb{Z}$. Consider the short exact sequence

$0\to\mathbb{Z}_{0}\xrightarrow{m}\mathbb{Z}_{1}\to M\to 0$

where $\mathbb{Z}_{0}=\mathbb{Z}_{1}=\mathbb{Z}$. It induces an isomorphism
between the determinants
$i:\mathbb{Z}_{0}\otimes\det_{\mathbb{Z}}M\to\mathbb{Z}_{1}$ ; furthermore the
induced morphism after base change is
$i_{\mathbb{R}}:\mathbb{R}_{0}\otimes_{\mathbb{R}}\mathbb{R}=\mathbb{R}_{0}\to\mathbb{R}_{1}$,
given by $x\mapsto mx$ since it is obtained from the short exact sequence of
$\mathbb{R}$-vector spaces $0\to\mathbb{R}_{0}\xrightarrow{m}\mathbb{R}_{1}\to
0\to 0$. Consider now the following commutative diagram

${\mathbb{Z}_{0}^{-1}\otimes\mathbb{Z}_{1}}$${\mathbb{Z}_{0}^{-1}\otimes\mathbb{Z}_{0}\otimes\det_{\mathbb{Z}}M}$${\det_{\mathbb{Z}}M}$${\mathbb{R}_{0}^{-1}\otimes_{\mathbb{R}}\mathbb{R}_{1}}$${\mathbb{R}_{0}^{-1}\otimes_{\mathbb{R}}\mathbb{R}_{0}\otimes_{\mathbb{R}}\mathbb{R}}$${\mathbb{R}}$$\scriptstyle{1\otimes
i}$$\scriptstyle{\simeq}$$\scriptstyle{ev\otimes
1}$$\scriptstyle{\simeq}$$\scriptstyle{1\otimes i_{\mathbb{R}}=1\otimes
m}$$\scriptstyle{\simeq}$$\scriptstyle{ev\otimes 1}$$\scriptstyle{\simeq}$

where $ev(\varphi\otimes x)=\varphi(x)$. The integral basis $1^{\ast}\otimes
1$ of $\mathbb{Z}_{0}^{-1}\otimes\mathbb{Z}_{1}$ is sent under the above maps
to $\frac{1}{m}\in\mathbb{R}$. ∎

######  Lemma A.2.

Let $A$ and $B$ be free abelian groups of rank $d$ and $\phi:A_{\mathbb{R}}\to
B_{\mathbb{R}}$ be an isomorphism. Then

$\det_{\mathbb{Z}}A\otimes(\det_{\mathbb{Z}}B)^{-1}\subset(\det_{\mathbb{Z}}A)_{\mathbb{R}}\otimes_{\mathbb{R}}((\det_{\mathbb{Z}}B)^{-1})_{\mathbb{R}}\simeq\left(\det_{\mathbb{R}}A_{\mathbb{R}}\right)\otimes_{\mathbb{R}}\left(\det_{\mathbb{R}}B_{\mathbb{R}}\right)^{-1}\xrightarrow[1\otimes\det_{\mathbb{R}}(\phi)^{t}]{\simeq}\left(\det_{\mathbb{R}}A_{\mathbb{R}}\right)\otimes\left(\det_{\mathbb{R}}A_{\mathbb{R}}\right)^{-1}\simeq\mathbb{R}$

corresponds to the lattice $\det(\phi)\mathbb{Z}\subset\mathbb{R}$ where
$\det(\phi)$ is computed with respect to any choice of integral bases of $A$
and $B$.

###### Proof.

Fix bases $(e_{1},\ldots,e_{d})$ and $(f_{1},\ldots,f_{d})$ of $A$ and $B$
respectively. Then by definition $\det_{\mathbb{R}}(\phi)$ maps
$e_{1}\wedge\cdots\wedge e_{d}$ to $\det(\phi)f_{1}\wedge\cdots\wedge f_{d}$,
where $\det(\phi)$ is computed in the mentioned bases. Now the lemma follows
from the fact that
$\left(\det_{\mathbb{R}}A_{\mathbb{R}}\right)\otimes_{\mathbb{R}}\left(\det_{\mathbb{R}}B_{\mathbb{R}}\right)^{-1}\to\left(\det_{\mathbb{R}}A_{\mathbb{R}}\right)\otimes\left(\det_{\mathbb{R}}A_{\mathbb{R}}\right)^{-1}$
maps the canonical basis element $e_{1}\wedge\cdots\wedge
e_{d}\otimes(f_{1}\wedge\cdots\wedge f_{d})^{\ast}$ to
$e_{1}\wedge\cdots\wedge e_{d}\otimes\det(\phi)(e_{1}\wedge\cdots\wedge
e_{d})^{\ast}$. ∎

######  Proposition A.3.

Let $M$ be a perfect complex of abelian groups and let
$\phi:H^{ev}(M_{\mathbb{R}})\xrightarrow{\simeq}H^{od}(M_{\mathbb{R}})$ be a
"trivialisation" of $M_{\mathbb{R}}$. Then

$\det_{\mathbb{Z}}M\subset(\det_{\mathbb{Z}}M)_{\mathbb{R}}\simeq\det_{\mathbb{R}}M_{\mathbb{R}}\simeq\left(\det_{\mathbb{R}}H^{ev}M_{\mathbb{R}}\right)\otimes_{\mathbb{R}}\left(\det_{\mathbb{R}}H^{od}M_{\mathbb{R}}\right)^{-1}\xrightarrow[1\otimes_{\mathbb{R}}\det_{\mathbb{R}}(\phi)^{t}]{\simeq}\left(\det_{\mathbb{R}}H^{ev}M_{\mathbb{R}}\right)\otimes_{\mathbb{R}}\left(\det_{\mathbb{R}}H^{ev}M_{\mathbb{R}}\right)^{-1}\simeq\mathbb{R}$

corresponds to the lattice

$\frac{\det(\phi)}{\prod_{i}[H^{i}(M)_{tor}]^{(-1)^{i}}}\mathbb{Z}\subset\mathbb{R}$

where $\det(\phi)$ is computed with respect to any integral bases of
$H^{ev}(M)/tor$ and $H^{od}(M)/tor$.

###### Proof.

We have an isomorphism of determinants
$\det_{\mathbb{Z}}M\simeq\det_{\mathbb{Z}}H^{\ast}M\simeq\det_{\mathbb{Z}}H^{ev}M\otimes(\det_{\mathbb{Z}}H^{od}M)^{-1}$
compatible with base change. Using the short exact sequence $0\to A_{tor}\to
A\to A/tor\to 0$ for $A=H^{ev}(M),\leavevmode\nobreak\ H^{od}(M)$, we reduce
by functoriality of the determinant to the torsion case and to the free case,
which are the two previous lemmas. ∎

######  Lemma A.4.

Let $A^{\bullet}$, $B^{\bullet}$ be two bounded acyclic complexes of finite
type abelian groups, and suppose there is an isomorphism
$\phi:B_{\mathbb{R}}\xrightarrow{\simeq}\operatorname{Hom}(A_{\mathbb{R}},\mathbb{R})[-1]$.
Then

$\frac{\prod_{i}[B^{i}_{tor}]^{(-1)^{i}}}{\det(\phi)\prod_{i}[A^{i}_{tor}]^{(-1)^{i}}}=1$

where $\det(\phi)$ is defined as the alternated product
$\prod_{i}\det(\phi^{i}:B_{\mathbb{R}}^{i}\to\operatorname{Hom}(A_{\mathbb{R}}^{1-i},\mathbb{R}))^{(-1)^{i}}$
with determinants computed in bases modulo torsion.

###### Proof.

Consider the line
$\Delta:=\det_{\mathbb{Z}}A\otimes(\det_{\mathbb{Z}}B)^{-1}$. It has a naive
trivialisation

$\det_{\mathbb{Z}}A\otimes(\det_{\mathbb{Z}}B)^{-1}\xrightarrow{\det(0)\otimes(\det(0)^{t})^{-1}}\mathbb{Z}\otimes\mathbb{Z}^{-1}\to\mathbb{Z}$

This induces the naive trivialisation of $\Delta_{\mathbb{R}}$, under which
the embedding $\Delta\hookrightarrow\Delta_{\mathbb{R}}$ corresponds to the
natural embedding $\mathbb{Z}\hookrightarrow\mathbb{R}$. Moreover, the
isomorphism $\phi$ induces another trivialisation of $\Delta_{\mathbb{R}}$:

$\det_{\mathbb{R}}A_{\mathbb{R}}\otimes(\det_{\mathbb{R}}B_{\mathbb{R}})^{-1}\xrightarrow{\mathrm{id}\otimes(\det(\phi)^{t})^{-1}}\det_{\mathbb{R}}A_{\mathbb{R}}\otimes(\det_{\mathbb{R}}A_{\mathbb{R}})^{-1}\to\mathbb{R}$

under which the embedding $\Delta\hookrightarrow\Delta_{\mathbb{R}}$
corresponds by the previous lemmas to

$\frac{\prod_{i}[B^{i}_{tor}]^{(-1)^{i}}}{\det(\phi)\prod_{i}[A^{i}_{tor}]^{(-1)^{i}}}\mathbb{Z}\hookrightarrow\mathbb{R}$

Let us show that both trivialisations are compatible. We claim that the
following diagram commutes

${\det_{\mathbb{R}}A_{\mathbb{R}}\otimes(\det_{\mathbb{R}}B_{\mathbb{R}})^{-1}}$${\det_{\mathbb{R}}A_{\mathbb{R}}\otimes(\det_{\mathbb{R}}A_{\mathbb{R}})^{-1}}$${\mathbb{R}\otimes\mathbb{R}^{-1}}$${\mathbb{R}}$$\scriptstyle{\mathrm{id}\otimes(\det(\phi)^{t})^{-1}}$$\scriptstyle{\det(0)\otimes(\det(0)^{t})^{-1}}$$\scriptstyle{nat}$$\scriptstyle{\det(0)\otimes(\det(0)^{t})^{-1}}$$\scriptstyle{nat}$

The commutativity of the lower triangle is immediate, and the commutativity of
the upper triangle comes from the commutative diagram

${B_{\mathbb{R}}}$${\operatorname{Hom}(A_{\mathbb{R}},\mathbb{R})[-1]}$${0}$$\scriptstyle{\phi}$$\scriptstyle{0}$$\scriptstyle{0}$

The compatibility of the trivialisations implies that $\alpha=1$, and the
formula follows. ∎

## References

  * [BF03] D. Burns and M. Flach  “Tamagawa Numbers for Motives with (Noncommutative) Coefficients, II”  In _American Journal of Mathematics_ 125.3 Johns Hopkins University Press, 2003, pp. 475–512
  * [Bre08] Manuel Breuning  “Determinants of perfect complexes and Euler characteristics in relative K0-groups”, 2008  arXiv:0812.1556 [math.KT]
  * [Bre11] Manuel Breuning  “Determinant functors on triangulated categories”  In _Journal of K-Theory_ 8.2 Cambridge University Press, 2011, pp. 251–291  DOI: 10.1017/is010006009jkt120
  * [Chi11] Yi-Chih Chiu  “On the Weil-étale Cohomology of S-integers”, 2011
  * [Den87] Christopher Deninger  “Duality in the Étale cohomology of one dimensional proper schemes and generalizations”  In _Mathematische Annalen_ 277, 1987, pp. 529–541
  * [Fla08] Matthias Flach  “Cohomology of topological groups with applications to the Weil group”  In _Compositio Mathematica_ 144.3 London Mathematical Society, 2008, pp. 633–656  DOI: 10.1112/S0010437X07003338
  * [FM18] Matthias Flach and Baptiste Morin  “Weil-étale Cohomology and Zeta-Values of Proper Regular Arithmetic Schemes”  In _Documenta Mathematica_ 23 Universität Bielefeld, 2018
  * [Goo69] Jacob Eli Goodman  “Affine Open Subsets of Algebraic Varieties and Ample Divisors”  In _Annals of Mathematics_ 89.1 Annals of Mathematics, 1969, pp. 160–183
  * [Gro67] Alexander Grothendieck  “Éléments de géométrie algébrique : IV. Étude locale des schémas et des morphismes de schémas, Quatrième partie” 32, Publications mathématiques de l’I.H.É.S.  Institut des Hautes Études Scientifiques, 1967
  * [GS20] Thomas H. Geisser and Takashi Suzuki  “Special values of L-functions of one-motives over function fields”, 2020  arXiv:2009.14504 [math.NT]
  * [JP20] Bruce W. Jordan and Bjorn Poonen  “The analytic class number formula for 1-dimensional affine schemes”  In _Bulletin of the London Mathematical Society_ , 2020
  * [KM76] Finn Knudsen and David Mumford  “The projectivity of the moduli space of stable curves. I. Preliminaries on "det" and "Div"”  In _Math. Scand._ 39, 1976, pp. 19–55
  * [Knu02] Finn F. Knudsen  “Determinant functors on exact categories and their extensions to categories of bounded complexes”  In _Michigan Mathematical Journal_ 50.2 University of Michigan, Department of Mathematics, 2002, pp. 407–445  DOI: 10.1307/mmj/1028575741
  * [Lic09] Stephen Lichtenbaum  “The Weil-étale topology for number rings”  In _Annals of Mathematics_ 170.2 Annals of Mathematics, 2009, pp. 657–683
  * [Lur17] Jacob Lurie  “Higher Algebra” http://people.math.harvard.edu/~lurie/papers/HA.pdf, 2017
  * [Maz73] Barry Mazur  “Notes on étale cohomology of number fields”  In _Annales scientifiques de l’École Normale Supérieure_ 6.4 Elsevier, 1973, pp. 521–552  URL: http://eudml.org/doc/81926
  * [Mil06] James S. Milne  “Arithmetic Duality Theorems”  BookSurge, LLC, 2006, pp. viii+339
  * [Mil80] James S. Milne  “Étale Cohomology”  Princeton University Press, 1980
  * [Mor14] Baptiste Morin  “Zeta functions of regular arithmetic schemes at $s=0$”  In _Duke Math. J._ 163.7 Duke University Press, 2014, pp. 1263–1336  DOI: 10.1215/00127094-2681387
  * [Mor89] Laurent Moret-Bailly  “Groupes de Picard et problèmes de Skolem. I”  In _Annales scientifiques de l’École Normale Supérieure_ 4e série, 22.2 Elsevier, 1989, pp. 161–179  URL: http://www.numdam.org/articles/10.24033/asens.1581/
  * [Nar04] Władysław Narkiewicz  “Elementary and Analytic Theory of Algebraic Numbers”, Springer Monographs in Mathematics  Springer, 2004
  * [Neu99] Jurgen Neukirch  “Algebraic Number Theory” 322, Grundlehren der mathematischen Wissenschaften  Springer-Verlag Berlin Heidelberg New York, 1999
  * [NS18] Thomas Nikolaus and Peter Scholze  “On topological cyclic homology”  In _Acta Math._ 221.2 Institut Mittag-Leffler, 2018, pp. 203–409  DOI: 10.4310/ACTA.2018.v221.n2.a1
  * [Qui73] Daniel Quillen  “Higher algebraic K-theory: I”  In _Higher K-Theories_ Springer Berlin Heidelberg, 1973, pp. 85–147
  * [Ser68] Jean-Pierre Serre  “Corps locaux” 8, Publications de l’université de Mathématiques de Nancago  Hermann, 1968
  * [Ser80] Jean-Pierre Serre  “Corps locaux”, Actualités scientifiques et industrielles 1296  Paris: Hermann, 1980
  * [Stacks] The Stacks Project Authors  “Stacks Project”, https://stacks.math.columbia.edu, 2020
  * [Swa60] Richard G. Swan  “Induced representations and projective modules”  In _Annals of mathematics_ 71.3, 1960, pp. 552–578
  * [Tat84] John Tate  “Les Conjectures de Stark sur les Fonctions L d’Artin en s=0.” 47, Progress in Mathematics  Birkhauser, 1984
  * [Tra16] Minh-Hoang Tran  “Weil-etale Cohomology and Special Values of L-functions”, 2016  arXiv:1611.01720 [math.NT]
  * [Ver96] Jean-Louis Verdier  “Des catégories dérivées des catégories abéliennes” 239, Astérisque  Société Mathématique de France, 1996
  * [Wei95] André Weil  “Basic Number Theory”, Classics in Mathematics  Springer, Berlin, Heidelberg, 1995


# The DUNE-DAQ Application Framework

Eric L. Flumerfelt for the DUNE Collaboration Paper submitted for review May
16, 2024. Notice: This work was produced by Fermi Research Alliance, LLC under
contract No. DEAC02-07CH11359 with the U.S. Department of Energy,Office of
Science, Office of High Energy Physics. The United States Government retains
and the publisher, by accepting the work for publication, acknowledges that
the United States Government retains a non-exclusive, paid-up, irrevocable,
world-wide license to publish or reproduce the published form of this work, or
allow others to do so, for United States Government purposes. The Department
of Energy will provide public access to these results of federally sponsored
research in accordance with the DOE Public Access Plan
(http://energy.gov/downloads/doe-public-access-plan).Eric L. Flumerfelt is
with the Fermi National Accelerator Laboratory, Batavia, IL 60510 USA.

###### Abstract

The Deep Underground Neutrino Experiment (DUNE) is a next-generation neutrino
experiment that will probe the properties of these elusive particles with
unparalleled precision. It will also act as an observatory for neutrino bursts
caused by nearby supernovae, in the event that one occurs while the experiment
is in operation. Given these goals, the DUNE trigger and DAQ system must be
able to maintain extremely high uptime and provide a path for full readout of
the detectors for very long times (up to 100 s). To achieve these ends, we
have designed the DUNE DAQ system around a flexible “application framework”,
which provides a modular interface for specific tasks while handling the
interconnections between them. The application framework collects modules into
applications which can then be interacted with as units by the control,
configuration and monitoring systems. One of the key features of the framework
is its communications abstraction layer, which allows for modules to interact
with both internal queues and external network connections with a single
transport-agnostic interface. We will report on the architecture and features
of the framework.

###### Index Terms:

Data acquisition, Physics computing, Software packages

##  I Introduction

The Deep Underground Neutrino Experiment (DUNE) [1] is a next-generation
neutrino experiment that will probe the properties of these elusive particles
with unparalleled precision. It is based in Lead, SD and receives neutrino
beam from Fermilab, a 1300 km baseline, as seen in Figure 1.

Up to four far detector modules will be constructed, with the first two being
liquid-Argon time-projection chambers, Figure 2. It will also act as an
observatory for neutrino bursts caused by nearby supernovae, in the event that
one occurs while the experiment is in operation.

Given these goals, the DUNE trigger and DAQ system [2] must be able to
maintain extremely high up-time and provide a path for full readout of the
detectors for very long times (up to 100 s). To achieve these ends, we have
designed the DUNE DAQ system around a flexible “application framework”, which
provides a modular interface for specific tasks while handling the
interconnections between them.

During the first DUNE 35 T and initial ProtoDUNE test runs, the artdaq DAQ
framework from Fermilab was used [3]. The up-time requirement for DUNE DAQ is
99.5%, leading to a requirement that the DAQ be able to handle run-time
changes of the components selected for readout. It was found, however, that
artdaq lacked sufficient flexibility to provide this functionality.
Additionally, the artdaq system layout did not provide hooks for some of the
data processing steps needed at the readout level, resulting in less-
maintainable plugin implementations.

The DUNE DAQ application framework was designed to meet the requirements of
the DUNE. It provides a common set of APIs and utilities that allow for
implementation of the DAQ logic in a consistent and maintainable way, while
also providing upgradability through the use of dynamically-loaded plugin
implementations for well-defined application interfaces.

Figure 1: This cutaway illustration shows the path of neutrinos in the Deep
Underground Neutrino Experiment. A proton beam is produced in Fermilab’s
accelerator complex (improved by the PIP-II project). The beam hits a target,
producing a neutrino beam that travels through a particle detector at
Fermilab, then through 800 miles (1,300 km) of earth, and finally reaches the
far detectors at Sanford Underground Research Facility.

Figure 2: Long-Baseline Neutrino Facility South Dakota Site

##  II DUNE DAQ Overview

The DUNE DAQ consists of a number of application components which communicate
with one another as in Figure 3. Each application handles a specific set of
DAQ functionality using a number of ”DAQ Modules” specific to that
application.

  1. 1.

Readout applications receive and buffer data from detector electronics, and
send processed waveform data (called Trigger Primitives) to the trigger
applications. They listen for incoming data requests from the builder
application. The internal structure of a readout application is depicted in
Figure 4.

  2. 2.

The Hardware Signals Interface (HSI) application interfaces with the timing
hardware and the Central Trigger Board (CTB) to produce HSI Event messages for
periodic and beam event triggers.

  3. 3.

The trigger applications create trigger decisions based on configurable
algorithms using the trigger primitives sent from the readout. The trigger
primitives are broadcast to all applications which have registered themselves
as receivers, so the number of trigger applications is flexible and dependent
on the number of desired trigger algorithms.

  4. 4.

The trigger record builder applications receive trigger decisions, request
data from the readout and trigger applications, and build Trigger Records
which are saved to disk.

  5. 5.

The Dataflow Orchestrator (DFO) application arbitrates the distribution of
trigger decisions to builder applications based on current run-time
conditions, and protects the builder applications from becoming overwhelmed by
large trigger records, inhibiting the production of new trigger decisions if
necessary.

  6. 6.

An additional Trigger primitive writer application may be used to save the
Trigger Primitive stream to disk; these files can then be used for future
trigger algorithm development.

Figure 3: Current organization of the DUNE DAQ software applications.
Messaging connections between applications are shown along with their data
types, though it is important to note that DAQ modules within the applications
are sending and receiving messages, not the applications themselves.

Figure 4: Diagram of the readout application used in the DUNE DAQ. Modules are
represented by white boxes, and network connections and queues are also shown.
Queues are always strictly internal to the application, whereas network
connections are always single-sided from the application’s perspective.

##  III Application Framework Structure

The DUNE DAQ Application Framework consists of several software packages which
implement various sub-components and expose interfaces to the central
framework functionality, as shown in Figure 5, and the appfwk [4] package
which provides the main interfaces used by the implementation modules. As
previously stated, applications are composed of a number of DAQ modules which
implement the functionality for each application type, Figure 6. Services used
by the application framework abstract their implementations behind consistent
interfaces so that those implementations can be changed at-will, increasing
the longevity and maintainability of the framework. Figure 7 shows the
structure of the application framework packages, as well as including one of
the packages which uses the interfaces provided by the application framework
(listrev [5] is the application framework test package).

  1. 1.

The iomanager [6] package provides the messaging interface used by the
modules, whereas the DAQ module management facilities and API are implemented
in the appfwk package itself.

  2. 2.

The ipm [7] and serialization [8] packages are used for transmitting data
between applications.

  3. 3.

utilities [9] contains a number of tools that are used throughout the
framework (including DNS resolution, a generic base class for all application
framework objects, and threading tools).

  4. 4.

rcif [10] provides the interface to the run control system, implemented in
cmdlib [11].

  5. 5.

appdal [12] and coredal [13] provide the configuration interface and schema,
as well as recipes for generating the most commonly-used applications and
their messaging connections at run-time, using module configurations stored in
the configuration database.

  6. 6.

The opmonlib [14] package contains the interface and implementation of the DAQ
monitoring and metric collection code.

  7. 7.

logging [15] takes care of log message archiving and provides a fast, run-time
configurable interface for debug messages.

Figure 5: Logical stack diagram of the application framework. Core services
are exposed to the framework through interfaces, with plugin-based
implementations to allow for upgrading functionality as technologies evolve
during the life-time of the experiment. The framework’s core functionality
includes the definition of applications, the management of DAQ modules, and
the messaging API used by the modules. Applications of various types are
implemented on top of the framework to perform the data acquisition logic
required by the experiment.

Figure 6: Diagram of a generic application based on the framework, showing
queues and external network connections. Several facilities are available to
the application and exposed to DAQ modules through framework interfaces.

Figure 7: Software packages comprising the application framework. The listrev
package is shown as an example user of the framework, while several of the
packages containing service interfaces and implementations are also shown as
dependencies of the framework.

###  III-A Service Interfaces

The Application Framework provides a plug-in interface for these external
interfaces, allowing for both custom and commercial off-the-shelf
implementations to be used.

The Control interface keeps track of application state and validates incoming
commands. Command transmission between applications can use a REST or gRPC-
based [16] communication implementation. The Run Control system is a separate
set of applications which are outside of the application framework. When a
valid command is received, the application distributes it to its DAQ modules
via an ”action plan”, a pre-configured series of parallel steps. Each step of
an action plan is an ”action”, an aliased method within the DAQ module. A
single module may register multiple actions to be executed within a single
action plan, in order to define ”pre” and ”post” command steps.

Configuration information is provided to the application at startup using the
OKS system adapted from ATLAS [17]. The configuration system uses an object-
based model and retrieves configuration data based on object class and unique
names. Along with the logging interface, the configuration interface is one of
the basic components of the system which must be configured via the
application command-line; all other service interfaces and application
behavior are defined through the configuration.

Each ”monitorable” element of the system is given a unique name which it can
use to push metrics to the monitoring interface, which in turn publishes them
using a plugin-based output facility. Additionally, the monitoring interface
periodically polls for metrics in a top-down manner, ensuring that all
monitored elements regularly report their current values. Current output
facility implementations include JSON files and a protobuf [18] format via a
Kafka [19] broker. If distributed via Kafka, the data are stored in an
InfluxDB [20] database and plots are automatically construted via DUNE-
developed Grafana [21] dashboards.

Log messages are handled using the ERS package [22], also adapted from ATLAS
[23]. ERS provides for well-structured messages which can be collected in a
back-end database (currently implemented in Kafka) for further processing.
Additionally, Fermilab’s TRACE [24] package provides high-speed low-level
debug printouts which are assigned a name and a level, and these can be
enabled or disabled at run-time. The performance of TRACE has been measured at
<1 µs for enabled messages and O(1 ns) for disabled messages.

###  III-B DAQ Module Interface

The goal of the Application Framework is to simplify as much as possible the
interactions with other systems, so that DAQ modules can be written in a self-
contained, task-oriented manner. It consolidates interfaces for control,
configuration, monitoring, and logging; these systems interact with
applications, allowing them to ignore the internal complexity of the modules
and their interconnections. Users are provided with access to data received
from the configuration system and the interface used to aggregate monitoring
data. The framework marshals and delivers commands to modules when they are
received by the applications.

The modules register their interest in certain commands, so when a command is
received, the application can intelligently deliver it to just the modules
that have a corresponding action. The framework also provides an abstraction
layer for connections, allowing modules to send data to an endpoint identified
by a name without regard as to whether the module owning the endpoint is local
to the application or running elsewhere.

Apart from a single required init method, the developer is free to implement
whatever methods and internal threading is needed to accomplish the task of
the DAQ module. The encapsulation provided by the messaging system means that
the module is completely independent of other modules, though it is
recommended for modules to use the callback system provided by the messaging
API to schedule work on message arrival.

###  III-C Messaging API

One of the core functionalities of the Application Framework is its messaging
API. Each message channel consists of a unidirectional, strongly-typed
connection (i.e. each connection only handles one type of message data), with
both network and queue-based implementations for inter- and intra-process
messaging, respectively. Connections are indexed by name and data type
(converted to a string by macros defined in the serialization package and
called at data type definition), and can be retrieved from an external
connectivity service using pattern matching on the name. Supported topologies
include point-to-point, broadcast, and many-to-one connections. Endpoints are
classified as being ”bind”-type or ”connect”-type, based on whether the
endpoint should be at a well-known or ephemeral location for the given
topology. For example, in the many-to-one case, the receiver is the
”bind”-type endpoint, and all senders are ”connect” type. Meanwhile, for the
broadcast pattern, the sender is the ”bind”-type and any receivers are
”connect” type (this particular topology also allows for zero receivers).

The messaging API exposed to the DAQ modules is agnostic for whether messages
are internal to an application or sent over the network, allowing for greater
flexibility in how modules are organized into applications. This also allows
for custom applications implementing large portions of the DAQ logic to be
created for smaller test scenarios. Conversely, if a particular application
has a large processing load, it can be split up to take advantage of available
computing resources.

Network transport and serialization use plug-in interfaces, currently
implemented via ZMQ [25] (in ipm and MsgPack [26]). ZeroMQ ”push/pull” and
”pub/sub” socket types are used to implement the required connection
topologies. Several ZeroMQ socket options are used to guarantee that messages
are only accepted if the remote endpoints are connected, including sndtimeo
and rcvtimeo set to 0 and immediate set on the sender socket. These options
allow for the application to quickly detect when remote endpoints are not
functional and attempt to reconnect.

###  III-D Threading and Utilities

Several utility classes are provided by the Application Framework, diagrammed
in Figure 8. Most notable are the WorkerThread and ReusableThread interfaces,
which provide long-lived tasks and a thread pool implementation, respectively.
These threading helper classes help DAQ module developers to implement their
logic in a consistent way, improving system maintainability and allowing for
the framework to manage thread lifetime and exception handling.

The framework provides a naming hierarchy which is used for monitoring and
logging, and the utilities package provides the NamedObject interface which is
the base class for all application framework classes.

DNS resolution utilities provided by the Resolver class are used in the
network messaging implementation and have the ability to interface with the
Kubernetes DNS [27] for service-based endpoint resolution.

Figure 8: UML Class diagrams of the application framework utilities.

##  IV Testing and Examples

In order to ensure that the application framework meets the requirements of
the DUNE DAQ, each component of the system is tested in both individual unit
tests and through a series of integration tests of increasing complexity,
cumulating in tests that exercise a significant portion of the DAQ itself,
including real detector hardware.

Each package within the application framework has a suite of unit tests, and
the listrev example was created to exercise the functionality of the framework
as whole as part of the integration testing of the DUNE DAQ. Its operation is
as follows:

  1. 1.

A ”ReversedListValidator” module broadcasts a request to create a new list of
integers.

  2. 2.

Each RandomDataListGenerator uses the information in the create message to
product a list of integers.

  3. 3.

The ReversedListValidator requests a list identified by an iteration index
from the RandomDataListGenerators and the ListReverser.

  4. 4.

The ListReverser, upon receiving a request for a new list, in turn requests
the list from the RandomDataListGenerator, inverts the order of the list
received, and sends it to the ReversedListValidator.

  5. 5.

Once the ReversedListValidator has received the relevant pairs of data, it can
check that the list was indeed reversed and that it matches the pattern
specified in the create message, seeded by the iteration index.

This example showcases many different aspects of the application framework’s
functionality, including DAQ module creation and managment, several messaging
topologies and patterns (create messages use broadcasts, and the request of
one data type resulting in a data response of a different data type), and it
uses the control, monitoring, and configuration interfaces. This allows for a
discrete test of the application framework without relying on detector
hardware in well-controlled conditions.

Figure 9: Communication paths within the listrev example package. Several
iterations of the example are run as part of the application framework
integration test suite, to ensure that queues and network connections are
properly working in the required connectivity patterns, and that the DAQ
modules remain functional regardless of which application they are located in
or what other DAQ modules are also in that application. The configuration
shown has two generators in separate applications and one reverser and
validator in a third application.

##  V Implementations of the Framework

The DUNE DAQ Application Framework has been used as the basis for the DAQ
system for ProtoDUNE horizontal and vertical drift, as well as the ICEBERG
prototype detector at Fermilab and the TOAD Near Detector prototype. The
system has evolved with each iteration, with different DAQ modules being used
in different configurations. Readout has transitioned from Proto-WIBs to DUNE-
WIBs and from FELIX-based readout [28] to WIBEth Ethernet-based readout [29].
This has shown the framework’s ability to interface with different readout
hardware with a reasonable development period for the DAQ modules specific to
each readout type. The DUNE-DAQ Application Framework is being deployed at
ProtoDUNE II for data-taking activities in 2024, with the horizontal-drift TPC
currently being made ready for operations.

##  VI Conclusions

The application framework has been deployed at the ProtoDUNE test detector at
CERN, as well as other test detectors, and we have used the test runs to
refine and improve the framework. The framework is in the final stages of
development, with reviews being performed to finalize the functionality and
close out development of new features. As it is a central part of the DUNE
DAQ, any API changes results in a large amount of effort to reconcile existing
module implementations with the change, so it is imperative to have the
framework in a very stable state to allow development to reach a conclusion in
other parts of the system.

We have demonstrated that the framework’s plugin-based architecture allows for
easy extension to additional readout types, an essential feature for the DUNE
which will require readout from at least three and up to six different
detector technologies simultaneously. We believe that the framework may prove
useful as the basis for the DAQ suites of other high-energy physics
experiments in the future.

## References

  * [1] Dune homepage. [Online]. Available: https://dunescience.org. Accessed on: May 7, 2024.
  * [2] A. Abed Abud, C. Batchelor, K. Biery et al., “Trigger and data acquisition (tdaq) system design,” DUNE DAQ Project, Tech. Rep., Jan. 2023. [Online]. Available: https://edms.cern.ch/document/2812882. Accessed on: May 7, 2024.
  * [3] K. Biery, E. Flumerfelt, J. Freeman, W. Ketchum, G. Lukhanin, and R. Rechenmacher, “Artdaq: DAQ software development made simple,” Journal of Physics: Conference Series, vol. 898, no. 3, pp. 032013, Oct. 2017, DOI. 10.1088/1742-6596/898/3/032013.
  * [4] DUNE-DAQ/appfwk. [Online]. Available: https://github.com/DUNE-DAQ/appfwk. Accessed on: May 7, 2024
  * [5] DUNE-DAQ/listrev. [Online]. Available: https://github.com/DUNE-DAQ/listrev. Accessed on: May 7, 2024
  * [6] DUNE-DAQ/iomanager. [Online]. Available: https://github.com/DUNE-DAQ/iomanager. Accessed on: May 7, 2024
  * [7] DUNE-DAQ/ipm. [Online]. Available: https://github.com/DUNE-DAQ/ipm. Accessed on: May 7, 2024
  * [8] DUNE-DAQ/serialization. [Online]. Available: https://github.com/DUNE-DAQ/serialization. Accessed on: May 7, 2024
  * [9] DUNE-DAQ/utilities. [Online]. Available: https://github.com/DUNE-DAQ/utilities. Accessed on: May 7, 2024
  * [10] DUNE-DAQ/rcif. [Online]. Available: https://github.com/DUNE-DAQ/rcif. Accessed on: May 7, 2024
  * [11] DUNE-DAQ/cmdlib. [Online]. Available: https://github.com/DUNE-DAQ/cmdlib. Accessed on: May 7, 2024
  * [12] DUNE-DAQ/appdal. [Online]. Available: https://github.com/DUNE-DAQ/appdal. Accessed on: May 7, 2024
  * [13] DUNE-DAQ/coredal. [Online]. Available: https://github.com/DUNE-DAQ/coredal. Accessed on: May 7, 2024
  * [14] DUNE-DAQ/opmonlib. [Online]. Available: https://github.com/DUNE-DAQ/opmonlib. Accessed on: May 7, 2024
  * [15] DUNE-DAQ/logging. [Online]. Available: https://github.com/DUNE-DAQ/logging. Accessed on: May 7, 2024
  * [16] gRPC. [Online]. Available: https://grpc.io/. Accessed on: May 7, 2024
  * [17] R. Jones, L. Mapelli, Y. Ryabov, and Soloviev, I., “The OKS persistent in-memory object manager,” IEEE Trans. Nuclear Science, vol. 45, no. 4, pp. 1958-1964, Aug. 1998, DOI. 10.1109/23.710971
  * [18] Protocol Buffers Documentation. [Online]. Available: https://protobuf.dev/. Accessed on: May 7, 2024
  * [19] Apache Kafka. [Online]. Available: https://kafka.apache.org/. Accessed on: May 7, 2024
  * [20] InfluxDB Overview. [Online]. Available: https://www.influxdata.com/products/influxdb-overview/. Accessed on: May 7, 2024
  * [21] Grafana: The open observability platform. [Online]. Available: https://grafana.com/. Accessed on: May 7, 2024
  * [22] DUNE-DAQ/ers. [Online]. Available: https://github.com/DUNE-DAQ/ers. Accessed on: May 7, 2024
  * [23] S. Kolos,A. Kazarov, and L. Papaevgeniou, “The Error Reporting in the ATLAS TDAQ System,” Journal of Physics: Conference Series, vol. 608, no. 1, pp. 012004, Apr. 2015, DOI. 10.1088/1742-6596/608/1/012004
  * [24] S. Foulkes, and R. Rechenmacher, “TRACE - A System Wide Diagnostic Tool,” 2007 IEEE-NPSS Real-Time Conference, 2007, DOI. 10.1109/RTC.2007.4382742
  * [25] ZeroMQ: An open-source universal messaging library. [Online]. Available: https://zeromq.org/. Accessed on: May 7, 2024
  * [26] MessagePack: It’s like JSON, but fast and small. [Online]. Available: https://msgpack.org/index.html. Accessed on: May 7, 2024
  * [27] DNS for Services and Pods — Kubernetes. [Online]. Available: https://kubernetes.io/docs/concepts/services-networking/dns-pod-service/. Accessed on: May 7, 2024
  * [28] Soo Ryu on behalf of the ATLAS TDAQ Collaboration, “FELIX: The new detector readout system for the ATLAS experiment,” Journal of Physics: Conference Series, vol. 898, no. 3, pp. 032057, Oct. 2017, DOI. 10.1088/1742-6596/898/3/032057
  * [29] R. Sipos for the DUNE collaboration, “The Ethernet readout of the DUNE DAQ system,” 2024 IEEE-NPSS Real-Time Conference, Apr. 2024, to be published


Ivar Ekeland, Roger Temam, Jeffrey Dean, David Grove, Craig Chambers, Kim B.
Bruce, and Elisa Bertino

11institutetext: Kyushu University, Faculty of Information Science and
Electrical Engineering, 819-0395 Fukuoka, Japan
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Ruhr-University Bochum, Faculty of Electrical Engineering and
Information Technology, 44801 Bochum, Germany
22email<EMAIL_ADDRESS>
# Budgeted Recommendation with Delayed Feedback

Kweiguu Liu 11 Setareh Maghsudi 22

###### Abstract

In a conventional contextual multi-armed bandit problem, the feedback (or
reward) is immediately observable after an action. Nevertheless, delayed
feedback arises in numerous real-life situations and is particularly crucial
in time-sensitive applications. The exploration-exploitation dilemma becomes
particularly challenging under such conditions, as it couples with the
interplay between delays and limited resources. Besides, a limited budget
often aggravates the problem by restricting the exploration potential. A
motivating example is the distribution of medical supplies at the early stage
of COVID-19. The delayed feedback of testing results, thus insufficient
information for learning, degraded the efficiency of resource allocation.
Motivated by such applications, we study the effect of delayed feedback on
constrained contextual bandits. We develop a decision-making policy, delay-
oriented resource allocation with learning (DORAL), to optimize the resource
expenditure in a contextual multi-armed bandit problem with arm-dependent
delayed feedback.

###### keywords:

Budget Constraints, Delayed Feedback, Online Learning, Resource Allocation

##  1 Introduction

The contextual bandit problem is a well-known variant of the seminal multi-
armed bandit problem: A decision-maker (agent, hereafter) observes some random
context, i.e., features, at each round of decision-making. It then pulls one
of the available arms and immediately receives a reward generated by the
random reward process of the selected arm. Given the context, the agent
maximizes each round’s reward while effectively exploring the potential
alternatives. The state-of-the-art applications of the contextual bandit
problem include online advertising and personalized recommendation;
nevertheless, the current research neglects those applications with additional
constraints on resources [2] that cause the following challenges: (i) The
exploitation becomes limited by the resource available for exploration; (ii)
The agent can no longer seek to maximize the instantaneous rewards as the arm
with the highest reward can be an expensive one. Consequently, the work opted
for maximizing the accumulated rewards. One main assumption in budgeted
learning is immediately observable feedback, but feedback is usually late in
real-world applications. Delayed feedback exacerbates the difficulty of
exploration because the information about suboptimal arms procrastinates.
Consequently, delayed feedback makes resource allocation inefficient for
exploration and exploitation. A motivating example is the distribution of
medical supplies at the early stage of COVID-19. During the outbreak, medical
supplies, e.g., protective kits and ventilators, do not support urgent needs.
That renders an optimal allocation of scarce resources imperative;
nevertheless, delayed feedback about testing results hinders health
administrators from accomplishing that goal, as inaccurate estimates aggravate
the difficulty of making decisions for vital resources. To address this real-
world challenge, the Greek government collaborated with the schools from the
United States; [3] designed and deployed a national scale learning system
named Eva to save lives. Eva’s goal is to efficiently allocate scarce testing
resources to identify as many infected passengers as possible while striving
for more accurate estimates of COVID-19 prevalence from passengers. The
challenge Eva faced was the delayed feedback of COVID test results because
delayed feedback brings the following adverse effects in budgeted learning:

  1. 1.

Over-exploration: Delayed feedback yields an inaccurate estimation of unknown
parameters. Thus, the agent over-explores to retrieve the information that it
could have simply obtained in a non-delayed scenario.

  2. 2.

Inefficient allocation: Over-exploration results in ineffective budget
expenditure because over-exploration depletes the resources that could have
been used to explore arms with higher rewards and a longer response time.

  3. 3.

Ineffective allocation: The delayed feedback in Eva was guaranteed to return
in a shorter period. However, feedback in other real-world applications is
usually not guaranteed to return, and such unresponsive feedback makes
resource allocation challenging.

To tackle the challenges above, one shall incorporate delays in budget
planning, i.e., one needs to consider expected delayed rewards of arms because
resource allocation is also affected by delayed feedback. Hence, we
disentangle the adverse effects of delayed feedback by gradually filtering out
less-responsive arms, i.e., arms with excessively long or unbounded delays.
Next, we formulate a delay-oriented linear program to handle online resource
allocation. Specifically, our proposed algorithm _delay-oriented resource
allocation with learning_ (DORAL) consists of two stages: (i) using a fraction
of the budget, the first stage identifies a set of top responsive arms that
are likely to return feedback within a time window; (ii) with the remaining
budget, the second stage uses the obtained set of top responsive arms to form
delay-oriented linear programming to optimize resource allocation.

##### CONTRIBUTIONS.

Our proposed two-stage algorithm ensures an efficient online resource
allocation in a general setting, where arm-dependent delays can be excessively
long or unbounded. The previous works in constraint learning circumvent the
issues caused by delayed rewards via posterior sampling or patiently waiting
for feedback. Such remedies are applicable given prior information about
delays or when the waiting time is relatively short. Our alternative solution
handles delayed feedback directly through the joint allocation of resources
and learning time. Also, we propose a delayed version of the robust top arms
identification method.

##  2 Related Work

Recent research on learning with delayed feedback includes diverse
applications such as [7, 16] on personalized recommendation, [8, 10] on edge
computing,[1] on the military, and [6] on communication networks. The cutting-
edge research categorizes delayed feedback into two classes, namely, bounded-
and unbounded delays. For example, a medical result that arrives within $48$
hours is a bounded delay, whereas a customer’s feedback that usually never
returns is unbounded. The state-of-the-art methods combine existing learning
algorithms with the following concepts to handle delayed feedback: _waiting_
or _cut-off_. The cut-off is a predetermined waiting window discarding any
feedback outside its boundaries. Waiting for feedback to update the estimators
is a popular method; nonetheless, it is appropriate when delays are bounded
[14, 19]. In cases of significant delays, cut-off is the best fit, because
waiting indefinitely without updating estimators can worsen bias and increase
storage overhead. Reference [17] applies the concept to delayed linear
bandits. Similar applications appear in [15].

Resource allocation with delayed feedback has gained attention due to various
challenges in real-world applications. One solution to allocate resources with
delays is via posterior sampling to estimate delayed feedback. The Greek
government and [3] designed the system Eva for the urgent allocation of
limited medical resources during the COVID outbreak, and Eva circumvents
delayed feedback, i.e., testing results, by applying the empirical Bayes
procedure to estimate the prevalence of passengers from different countries.
Similarly, Northern American ride-sharing company Lyft allocates resources to
ad campaigns across periods to attract more drivers, but prospective drivers
cannot hit the road until finishing the mandatory requirements. Thus, [12]
applies Thompson Sampling to predict potential drivers, i.e., delayed rewards
for resource allocation. Compared to the previous work, our work considers
possible non-returned feedback that makes allocated resources ineffective, so
we need to identify which arms are less responsive to minimize ineffective
resource allocation.

##  3 Problem Formulation

We consider an environment with finite classes of contexts
$\mathcal{X}=\\{1,\dots,J\\}$. Let $\pi_{1},\dots,\pi_{J}$ denote a known
distribution over contexts. Each type of context is characterized by an
unknown parameter vector $\theta_{j}\in\mathbb{R}^{k}$, where $k$ denotes the
number of features. A finite set of arms (actions) is $\mathcal{A}$, and
$|\mathcal{A}|=A$. At each time $t$, a subset of $\mathcal{A}$, denoted by
$\mathcal{A}_{t}$, is available. Each arm $a_{t}\in\mathcal{A}_{t}$ has a
feature vector $\mathbf{f}_{a_{t}}\in\mathbb{R}^{d}$ and a corresponding fixed
cost $c_{a_{t}}$; $\mathbf{f}^{(j)}_{a_{t}}$ denotes the feature of $a_{t}$
selected for context $j$. Each arm has a delay distribution
$\mathcal{D}_{a_{t}}$ with unknown mean $d_{a_{t}}$ supported on positive
numbers, and delay $D_{a_{t}}\sim\mathcal{D}_{a_{t}}$ is sampled. Because arms
have different delays due to exogenous factors, $D_{a_{t}}$ does not depend on
the contexts. Initially, the agent has some budget $B$. At each round $t\in
T$, the remaining budget is $b_{t}$. The agent interacts with the environment
as follows until the budget is exhausted.

While $b_{t}>0,$ • At time $t$, the agent observes a context from
$j\in\mathcal{X}$, where the contexts arrive independent of each other and the
set of available arms $\mathcal{A}_{t}$; • The agent selects an arm
$a_{t}\in\mathcal{A}_{t}$ to maximize the weighted reward
$r^{(j)}_{t,u,a_{t}}=\langle\theta_{j},\mathbf{f}_{a_{t}}\rangle$, where $u$
is the latest time in which the reward shall become observable. The agent pays
the associated cost $c_{a_{t}}$ or not if she pulls no arm. The agent is
allowed to skip any round, i.e., pull no arm, whenever no arm can be
recommended given the remaining budget.

For $u>0$, $\mathbb{P}(D_{a_{t}}\leq u)=\tau_{a_{t}}(u)$. Following [9], we
assume $\tau_{a_{t}}(u)$ satisfying the following inequality. Let $\alpha>0$,

$|1-\tau_{a_{t}}(u)|\leq u^{-\alpha}$ (1)

By the assumption above, a smaller $\alpha$ implies a lower chance of
receiving feedback by $u$. When we consider the case with heavy-tailed delays,
we assume $\mathbb{E}|D_{a_{t}}-d_{a_{t}}|^{1+\varepsilon}\leq v_{a_{t}}$,
where $\varepsilon\in(0,1]$ and $v_{a_{t}}$ denotes variance. In other words,
delays are not assumed to be sub-Gaussian. Also, we assume each arm’s mean
delay is not larger than a certain portion of the budget, i.e., $d_{a_{t}}\leq
B/4$, because any mean delay larger than the budget is rarely observed and can
be discarded. The agent does not know feedback before $D_{a_{t}}$ exceeds
$u-t$. Thus, we define the delayed reward formally as

$\hat{r}_{t,u,a_{t}}=r_{t,u,a_{t}}\mathds{1}\\{D_{a_{t}}\leq u-t\\}$ (2)

where $\mathds{1}\\{D_{a_{t}}\leq u-t\\}$ is an indicator function that
returns one if the reward of the decision made at $t$ is observed by $u$ and
zero otherwise. The agent’s objective is to select the arms sequentially to
maximize the total accumulated reward given the budget constraint and delayed
feedback. Formally,

$\begin{split}\text{maximize}\quad&U(T,B)=\mathbb{E}\left[\sum_{t=0}^{T}\hat{r}_{t,u,a_{t}}\right]\\\
\text{subject to}\quad&\sum_{t=1}^{T}c_{a_{t}}\leq B\end{split}$ (3)

where the expectation is taken over the distribution of contexts and rewards.
Let $U^{*}(T,B)=\mathbb{E}[\sum_{t=0}^{T}\hat{r}_{t,u}^{*}]$ denote the total
optimal payoff when
$\hat{r}_{t,u}^{*}=\max\limits_{a_{t}\in\mathcal{A}_{t}}\hat{r}_{t,u,a_{t}}$.
We measure the performance by the regret, i.e., the difference between the
expected gain with hindsight knowledge and the actual gain, and it is defined
as

$R=U^{*}(T,B)-U(T,B)$ (4)

The agent minimizes the regret by optimal arm selection.

##  4 Algorithm Design

The proposed algorithm consists of two stages. The first stage is to identify
a set of top responsive arms. We describe this stage in Sec. 4.1. The second
stage is online allocation with learning; we explain this stage in Sec. 4.2.

###  4.1 Search for Top Responsive Arms

To mitigate the adverse effects of arm-dependent delays on resource
allocation, we need to know the arms’ response time in order to determine the
cut-off $m$ for contextual learning in the next stage. Hence, we first need to
identify the top responsive $A^{\prime}\leq A$ arms. This task boils down to
an identification problem in multi-armed bandits, where the rewards are the
average over the number of rounds in which the agent observes delays. Also,
ranking arms according to their responsiveness enables us to neglect the ones
with rare or no feedback, thus saving scarce resources for the rest.

We build our identification algorithm upon a strategy family known as
_Successive Acceptance and Rejection_ (SAR) from [5, 11]. Different variants
of SAR can optimize either the budget for a given confidence level or the
quality of exploration for a given threshold. However, in our setting, delays
make it challenging to decide on a necessary budget in the first place. To
address this issue, inspired by [13], we propose a variant of SAR, namely,
Patient-Racing SAR (PR-SAR), for a given threshold. Algorithm 1 describes PR-
SAR.

Let $S_{t}$ denote a set of accepting arms, $L_{t}$ a set of remaining arms at
time $t$, and $E_{t}$ a set of rejected arms. Till identifying top responsive
arms, $|S_{t}|=A^{\prime}$, PR-SAR continuously pulls arms from $L_{t}$, and
the method determines acceptance by comparing confidence bounds. However, due
to _delayed response_ and possible _non-sub-Gaussian delays_ , we need a
robust estimation method, namely, _median-of-means_ estimator by [4], to
measure the responsiveness of arms. The core idea is to prepare several
disjoint baskets, calculate the standard empirical mean of received feedback
in each basket and take a median value of these empirical means. $X\vee
Y\triangleq$ Specifically, for some arm $a$,
$T_{a}(u)=\sum_{t}^{u}\mathds{1}\\{a_{t}=a\\}$ denote the number of times the
agent observes arm $a$ by time $u$, and $h=\lfloor
8\log(\frac{e^{1/8}}{\delta}\wedge\frac{T_{a}(u)}{2}))\rfloor$ and
$N(u)=\lfloor\frac{T_{a}(u)}{h}\rfloor$. Let
$D_{a,t}=D_{a_{t}}\mathds{1}\\{a_{t}=a\\}$. Each basket’s estimated expected
waiting period then yields

$\hat{d}_{a,1}=\frac{1}{N(u)}\sum_{t=1}^{N(u)}D_{a,t},\hat{d}_{a,2}=\frac{1}{N(u)}\sum_{t=N(u)+1}^{2N(u)}D_{a,t},\dots,\hat{d}_{a,h}=\frac{1}{N(u)}\sum_{t=(h-1)N(u)+1}^{hN}D_{a,t}.$

Let $d_{a}^{M}$ denote the median-of-means estimator of empirical waiting
periods. We first need the following lemma to bound $d_{a}^{M}$; the lemma
states how the empirical mean behaves when delayed feedback exists. Due to the
limited space, the proof is omitted.

######  Lemma 4.1.

For some arm $a$ and $\alpha,\delta>0$, with probability at least
$1-\delta-B^{-\alpha}$, $\hat{d}_{a}\leq
d_{a}+\sqrt{\frac{2B\log\frac{2}{\delta}}{T_{a}(u)}}+2d_{a}T(u)^{-(\alpha\wedge
1/2)}$

The following theorem states the robust upper confidence bound (UCB) of
patient median-of-means estimation.

######  Theorem 4.2.

Let $\alpha>0,\delta>0$. For some $a$ and any $t>A$ with probability
$1-\delta-B^{-\alpha}$,

$|d_{a}^{M}-d_{a}|\leq\sqrt{\frac{2\log\left(\frac{16}{1-B^{-\alpha}}\right)}{T_{a}(u)}}+\frac{B}{2}T_{a}(u)^{-(\alpha\wedge
1/2)}$ (5)

######  Proof 4.3.

Let $Z_{l}=\mathds{1}\\{\hat{d}_{l}>d_{a}+\varepsilon,\forall
l\in\\{1,\dots,h\\}\\}$. According to Lemma 4.1, $Z_{l}$ follows a Bernoulli
distribution with
$p\leq\frac{v_{a}}{N(u)^{\varepsilon}\zeta^{1+\varepsilon}}+2\exp{\left(\frac{-2\zeta^{2}N(u)}{B^{2}}\right)}+B^{-\alpha}$.
If $\zeta=\sqrt{\frac{2\log\left(\frac{16}{1-B^{-\alpha}}\right)}{N(u)}}$, we
have $p\leq 1/4+B^{-\alpha}$. By Hoeffding’s inequality, we have

$\mathbb{P}(d^{M}_{a}>d_{a}+\varepsilon)=\mathbb{P}\left(\sum_{l=1}^{h}Z_{l}\geq\frac{h}{2}\right)\leq\exp{(-2h(1/2-p)^{2})}\leq\exp{(-h/8)}\leq\delta$

According to Theorem 4.2, PR-SAR accepts any arm whose lower confidence bound
(LCB) is larger than at least $K^{\prime}$ of UCB’s. Specifically, PR-SAR
compares the following delayed robust UCB’s and LCB’s.

$UCB_{d_{a}}(t)=d^{M}_{a}(t)+\sqrt{\frac{2\log\left(\frac{16}{1-B^{-\alpha}}\right)}{T_{a}(u)}}+2d_{a}T_{a}(u)^{-(\alpha\wedge
1/2)}$ (6)
$LCB_{d_{a}}(t)=d^{M}_{a}(t)-\sqrt{\frac{2\log\left(\frac{16}{1-B^{-\alpha}}\right)}{T_{a}(u)}}-2d_{a}T_{a}(u)^{-(\alpha\wedge
1/2)}$ (7)

After finding top responsive arms, PR-SAR determines the remaining budget for
resource allocation, i.e., $B_{ac}=B-B_{id}$ where $B_{id}$ is the amount of
budget spent on identification. PR-SAR can simply decides the cut-off
$m=\max_{a\in\mathcal{A}}UCB_{d_{a}}$. PR-SAR by construction is Hoeffding
race method, so it can find top responsive arms.

Algorithm 1 Patient Racing SAR

$\mathcal{A},B,S_{1}=\\{\emptyset\\},L_{1}=\\{1,\dots,K\\}$

$A^{\prime}$ accepted arms and $m=max\\{UCB_{d_{a}},\forall
a\in\mathcal{A}\\}$

while $|S_{t}|<A^{\prime}$ do

for $a\in L_{t}$ do

pull $a$ and compute $UCB_{d_{a}}$ using Eq. 6, $LCB_{d_{a}}$ using Eq. 7

end for

for $a\in L_{t}$ do $\triangleright$ Update top accepted arms

if $|\\{a^{\prime}\mid
LCB_{d_{a}}>UCB_{d_{a^{\prime}}}\\}|>A^{\prime}-|S_{t}|$ then

$S_{t}\leftarrow S_{t}\bigcup\\{a\\}$

$L_{t}\leftarrow L_{t}\backslash\\{a\\}$

end if

end for

end while

###  4.2 Resource Allocation with Delays

We first introduce the decision rule when delayed feedback exists, and then
explain online resource allocation with delayed feedback.

####  4.2.1 Learning Estimators with Delayed Feedback

Waiting indefinitely for feedback results in excessive computation overhead
and swift exhaustion of scarce resources. One solution to mitigate the problem
is to select a cut-off parameter $m$. Thus the delayed reward
$\hat{r}_{t,u,a}$ can be restated as

$\tilde{r}_{t,u,a}=r_{t,u,a}\mathds{1}\\{D_{t,a}\leq\min(m,u-t)\\}$ (8)

Let $\lambda>0$ be a regularization parameter. Following [17], we estimate
$\theta$ using the least square method as

$\hat{\theta}_{t}=\left(\sum_{t=1}^{u-1}\mathbf{f}_{a_{t}}\mathbf{f}_{a_{t}}^{\top}+\lambda
I\right)^{-1}\left(\sum_{t=1}^{u-1}\tilde{r}_{t,u,a}\mathbf{f}_{a_{t}}\right)=V_{t}(\lambda)^{-1}G_{t}.$
(9)

Let
$f_{t,\delta}=\sqrt{\lambda}+\sqrt{2\log\left(\frac{1}{\lambda})+k\log(\frac{k\lambda+t}{k\lambda}\right)}$.
Theorem 1 in [17] validates that, after a period of learning, the distance
between $\hat{\theta}$ and $\theta$ remains bounded with high probability.
Hence, we propose the following decision rule to select arms.

• At each round and for each arm $a$, define the index $\gamma_{t}(a)$ as
$\langle\hat{\theta}_{t},\mathbf{f}_{a}\rangle+\left(2f_{t,\delta}+\sum_{t=u-m}^{u-1}\|\mathbf{f}_{a_{t}}\|_{V_{t}(\lambda)^{-1}}\right)\|\mathbf{f}_{a}\|_{V_{t}(\lambda)^{-1}}$
(10) The index is the linear upper confidence bound (LinUCB) within the cut-
off. • The agent picks the arm with the highest index, i.e.,
$a_{t}^{*}=\operatorname*{arg\,max}{\gamma_{t}(a)}$, $a\in\mathcal{A}_{t}$.

####  4.2.2 Resource Allocation with Delayed Learning

Optimization of resource allocation in (3) with the hard budget constraint is
especially challenging with unknown delays. Hence, we approximate the optimal
solution with a relaxed budget constraint, i.e., the average budget constraint
$\rho=\frac{B}{T}$ at each round. Inspired by the approximation method in
[18], we develop an approach for near-optimal delay-oriented allocation. In
the following, we drop the parameter $m$ from $\tau_{a}(m)$ unless it is
necessary to avoid ambiguity. For simplicity, we assume that the distribution
of contexts is known and static. We have $\tau_{a}\rightarrow 1$ if
$m\rightarrow\infty$, but such $m$ increases the regret significantly. To
simplify the analysis, we assume $\tau_{a}$’s are given. Let
$\eta^{*}_{j}=\max_{a\in\mathcal{A}}\tau_{a}\tilde{r}_{j,a}$ the best expected
delayed reward the agent can obtain under context $j$ and
$\tilde{a}^{*}_{j}=\operatorname*{arg\,max}_{a\in\mathcal{A}}\tilde{r}_{j,a}$
the corresponding arm. Let $\mathbf{p}=(p_{1},\dots,p_{j})$ denote a
probability vector, and the agent’s goal is to solve the following linear
programming at each round:

$\begin{split}\text{$LP_{m}$~{}~{}~{}maximize}_{\mathbf{p}}\quad&\sum_{j}^{J}p_{j}\pi_{j}\eta^{*}_{j}\\\
\text{subject to}\quad&\sum_{j}^{J}p_{j}\pi_{j}\leq\rho\\\ \end{split}$ (11)

$LP_{m}$ maximizes the expected delayed reward with arms with higher
probabilities to return, while its constraint considers expected delayed costs
to avoid spending resources on arms with no feedback possibilities. The
solution of $LP_{m}$ can be expressed with some threshold $j(\rho)$, which is
a function of the average constraint ratio $\rho$, and the reinterpretation of
$LP_{m}$ can help simplify the regret analysis. Thus,

$j(\rho)=\max\\{j:\sum_{j^{\prime}}^{J}\pi_{j^{\prime}}\leq\rho\\}$ (12)
$p_{j}(\rho)=\begin{cases}1,&\text{if }1\leq i\leq j(\rho)\\\
\frac{\rho-\sum_{j^{\prime}=1}^{j(\rho)}\pi_{j^{\prime}}}{\pi_{j(\rho)+1}},&\text{if
}i=j(\rho)+1\\\ 0,&\text{if }i>j(\rho)+1\end{cases}$ (13)

and the optimal value of $LP_{m}$ can be expressed with (12) and (13).

$v(\rho)=\left(\sum_{j^{\prime}}^{j(\rho)}\pi_{j^{\prime}}\hat{\eta}_{j^{\prime}}^{*}\right)+p_{j(\rho)+1}\pi_{j(\rho)+1}\eta^{*}_{j(\rho)+1}$
(14)

With Algorithm 1 and the resource allocation rule (11), we present our
proposed decision-making strategy, i.e., delay-oriented resource allocation
with learning (DORAL), in Algorithm 2. The algorithm consists of two stages.
The first stage spends a portion of the budget $B_{id}$ and time $T_{id}$ to
identify top responsive arms, and the second stage explores and exploits with
the remaining budget $B_{ac}$ and time $T_{ac}$ using the cut-off obtained in
the first stage.

Algorithm 2 Delay-Oriented Resource Allocation with Learning

$\mathcal{A},S_{1}=\\{\emptyset\\}$, $B$, $T$, $\lambda\in(0,1)$

while $|S_{t}|\leq A^{\prime}$ do

Algorithm 1

end while

while $B_{ac}>0$ do

Observe context and pick $\tilde{a}^{*}_{j}(t)$ with $p_{j}(\frac{b_{t}}{t})$
that satisfies $LP_{m}$ with $\hat{\eta}^{*}_{j}$

Update $b_{t},\hat{\theta}_{j},V^{(j)}_{\lambda}(t)$, and $G^{(j)}_{t}$ if
delayed feedback returns.

end while

##  5 Experiments

Due to the difficulty of finding a dataset suitable for our scenarios, we
evaluate the performance of DORAL with a synthetic dataset with the following
settings: The budget is $85,000$ to ensure at least $50,000$ rounds. There are
$10$ context classes, and the distribution of the contexts is
$\boldsymbol{\pi}=[0.09,0.15,0.11,0.05,0.1,0.05,\\\ 0.08,0.14,0.13,0.1]$.
There are $10$ arms, and each has a unit cost. Each context and arm has five
features, where we represent each feature by some value between $(0,1)$. We
use geometric and Pareto distributions to generate delays for each assigned
arm. For the scenario of diverse delays, we have geometric delays for the
arms, and their expected delays are
$[100,120,140,160,200,220,240,260,280,300]$. For Pareto delays, we set each
arm’s minimum delay as $[200,220,240,260,280,320,\\\ 340,360,380,400]$, and
the arms share the same shape parameter $\alpha=2$. For the scenario of
similar and short delays, we use [100,110,120,130,140,150,160,170,180,190] for
geometric means and Pareto minimum values. We compare our proposed algorithm
with the following benchmarks. Delayed-LinUCB (D-LinUCB) by [17]: The method
selects the arms with the highest reward in each context class. The method
selects the arms with the highest reward in each class of context. Because the
type of delay distribution is unknown, we choose $m=500$ for the cut-off $m$.
This method can be interpreted as a greedy method in our scenario. Thus, we
have the lowest $\tau_{a}(m)=0.81$ in the case of geometric delays, and the
lowest $\tau_{a}(m)=0.36$ in the case of Pareto delays. Random Delayed-LinUCB
(Random): The method is similar to Delayed-LinUCB; Nevertheless, the selection
follows with the probability of $\rho$, i.e., the remaining budget concerning
the given budget. It also uses $m=500$ for the cut-off. Delayed adaptive
linear programming (D-ALP) of [18]: The method is similar to our proposed
method, but we let $\forall a\in\mathcal{A},\tau_{a}(m)=1$. Each figure is the
average of 50 runs. As DORAL spends some time identifying top responsive arms,
it starts late to accumulate rewards. In Fig. 1, because delays are short,
DORAL and D-ALP are overlapping. In Fig. 2 (a), D-ALP identifies a higher
$m>500$, so it’s expected to have more regret according to the theorems.
Nevertheless, DORAL outperforms D-ALP when facing heavy-tailed delays in Fig.
2 (b) even though both of them identify similar $m$, while they come close in
Fig. 2 (c). These cases indicate that utilizing expected delayed rewards in
diverse delays can simultaneously optimize rewards and learning altogether.

(a) Geometric Delays

(b) Pareto Delays

Figure 1: Similar delays

(a) Geometric Delays

(b) Pareto Delays

Figure 2: Diverse delays

##  6 Conclusion

To tackle the challenges in resource allocation with delayed feedback, we
developed a two-stage policy that can efficiently allocate resources while
learning with delayed feedback. Also, we proposed a robust method to identify
top responsive arms when information delays can be heavy-tailed. Future
research involves simultaneously determining cut-off on the fly while ensuring
efficient resource allocation. Context-dependent delays are more realistic and
challenging when compared to arm-dependent delays in our setting. Also, in our
setting, the feedback of different arms is equally important, although often,
there exist different levels of urgency to consider in a resource allocation
problem, e.g., in sharing limited medical supplies. Hence, another research
direction is studying such a hierarchical structure in real-world
applications.

## Acknowledgement

The work of S.M. was supported by Grant 01IS20051 and Grant 16KISK035 from the
German Federal Ministry of Education and Research.

## References

  * [1] Amuru, S., Buehrer, R.M.:  Optimal jamming using delayed learning.  In: 2014 IEEE Military Communications Conference, IEEE (2014) 1528–1533
  * [2] Badanidiyuru, A., Langford, J., Slivkins, A.:  Resourceful contextual bandits.  In: Conference on Learning Theory, PMLR (2014) 1109–1134
  * [3] Bastani, H., Drakopoulos, K., Gupta, V., Vlachogiannis, I., Hadjichristodoulou, C., Lagiou, P., Magiorkinis, G., Paraskevis, D., Tsiodras, S.:  Efficient and targeted covid-19 border testing via reinforcement learning.  Nature 599(7883) (2021) 108–113
  * [4] Bubeck, S., Cesa-Bianchi, N., Lugosi, G.:  Bandits with heavy tail.  IEEE Transactions on Information Theory 59(11) (2013) 7711–7717
  * [5] Bubeck, S., Wang, T., Viswanathan, N.:  Multiple identifications in multi-armed bandits.  In: International Conference on Machine Learning, PMLR (2013) 258–265
  * [6] Cesa-Bianchi, N., Gentile, C., Mansour, Y.:  Nonstochastic bandits with composite anonymous feedback.  In: Conference On Learning Theory, PMLR (2018) 750–773
  * [7] Chapelle, O., Manavoglu, E., Rosales, R.:  Simple and scalable response prediction for display advertising.  ACM Transactions on Intelligent Systems and Technology (TIST) 5(4) (2014) 1–34
  * [8] Chen, L., Xu, J.:  Task replication for vehicular cloud: Contextual combinatorial bandit with delayed feedback.  In: IEEE INFOCOM 2019-IEEE Conference on Computer Communications, IEEE (2019) 748–756
  * [9] Gael, M.A., Vernade, C., Carpentier, A., Valko, M.:  Stochastic bandits with arm-dependent delays.  In: International Conference on Machine Learning, PMLR (2020) 3348–3356
  * [10] Ghoorchian, S., Maghsudi, S.:  Multi-armed bandit for energy-efficient and delay-sensitive edge computing in dynamic networks with uncertainty.  IEEE Transactions on Cognitive Communications and Networking (2020)
  * [11] Grover, A., Markov, T., Attia, P., Jin, N., Perkins, N., Cheong, B., Chen, M., Yang, Z., Harris, S., Chueh, W., et al.:  Best arm identification in multi-armed bandits with delayed feedback.  In: International Conference on Artificial Intelligence and Statistics, PMLR (2018) 833–842
  * [12] Han, B., Gabor, J.:  Contextual bandits for advertising budget allocation.  Proceedings of the ADKDD 17 (2020)
  * [13] Heidrich-Meisner, V., Igel, C.:  Hoeffding and bernstein races for selecting policies in evolutionary direct policy search.  In: Proceedings of the 26th Annual International Conference on Machine Learning. (2009) 401–408
  * [14] Joulani, P., Gyorgy, A., Szepesvári, C.:  Online learning under delayed feedback.  In: International Conference on Machine Learning, PMLR (2013) 1453–1461
  * [15] Thune, T.S., Cesa-Bianchi, N., Seldin, Y.:  Nonstochastic multiarmed bandits with unrestricted delays.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., Garnett, R., eds.: Advances in Neural Information Processing Systems. Volume 32., Curran Associates, Inc. (2019)
  * [16] Vernade, C., Cappé, O., Perchet, V.:  Stochastic bandit models for delayed conversions.  In: Conference on Uncertainty in Artificial Intelligence. (2017)
  * [17] Vernade, C., Carpentier, A., Lattimore, T., Zappella, G., Ermis, B., Brueckner, M.:  Linear bandits with stochastic delayed feedback.  In: International Conference on Machine Learning, PMLR (2020) 9712–9721
  * [18] Wu, H., Srikant, R., Liu, X., Jiang, C.:  Algorithms with logarithmic or sublinear regret for constrained contextual bandits.  In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., Garnett, R., eds.: Advances in Neural Information Processing Systems. Volume 28., Curran Associates, Inc. (2015)
  * [19] Zhou, Z., Xu, R., Blanchet, J.:  Learning in generalized linear contextual bandits with stochastic delays.  Advances in Neural Information Processing Systems 32 (2019) 5197–5208