# A Large Deviations Perspective on
Policy Gradient Algorithms

Wouter Jongeneel All authors are with the Risk Analytics and Optimization
(RAO) Chair, École Polytechnique Fédérale de Lausanne (EPFL). WJ, ML, and DK
are supported by the Swiss National Science Foundation under the NCCR
Automation, grant agreement 51NF40_180545. Contact: envelope
{wouter.jongeneel, mengmeng.li<EMAIL_ADDRESS>linkwjongeneel.nl,
mengmenglior.github.io, epfl.ch/labs/rao/. Mengmeng Li11footnotemark: 1 Daniel
Kuhn11footnotemark: 1

###### Abstract

Motivated by policy gradient methods in the context of reinforcement learning,
we derive the first large deviation rate function for the iterates generated
by stochastic gradient descent for possibly non-convex objectives satisfying a
Polyak-Łojasiewicz condition. Leveraging the contraction principle from large
deviations theory, we illustrate the potential of this result by showing how
convergence properties of policy gradient with a softmax parametrization and
an entropy regularized objective can be naturally extended to a wide spectrum
of other policy parametrizations.

Keywords— large deviations, reinforcement learning
2020 Mathematics Subject Classification— 60F10 $\cdot$ 90C26

##  1 Introduction and related work.

Policy gradient methods are at the core of several reinforcement learning (RL)
algorithms. e.g., see [Sut+99, DPS12, Aga+21]. As such, a wide adoption of
these algorithms is aided by precisely understanding their performance. To
that end, in scenarios where policy gradients can only be evaluated
stochastically, it is crucial to understand the underlying distribution
governing the evolution of policy iterates. Despite the popularity of
stochastic policy gradient methods for over 20 years, global convergence has
been only understood recently [Faz+18, Zha+20, BR19, Aga+21]. Although global
convergence proofs are actively developed for different policy gradient
algorithm templates [BR19, Aga+21, Cen+22], two aspects of the current
convergence analysis would benefit from further study: 1) global convergence
guarantees are often stated in terms of expected suboptimality; and 2) the
choice of policy parametrizations impacts convergence behavior [Mei+20]. In
light of these observations, this paper aims to derive sharp convergence rates
in probability and to provide a unifying approach towards understanding the
effect of different policy parametrizations. As we build upon a rich history
of work, we succinctly comment on: (i) high probability analysis in stochastic
optimization and RL; and (ii) policy gradient methods in RL.

(i) Despite stochastic gradient descent (SGD) being over 70 years old [RM51],
there has been a surge of interest in terms of high probability analysis for
(SGD): for strongly-convex objectives [Har+19]; non-convex objectives
satisfying a Polyak-Łojasiewicz (PL) condition [MDB20]; and non-convex
objectives [GL13, Liu+23] with Lipschitz gradients. A motivation for studying
tight convergence bounds in terms of probabilities over convergence in
expectation is due to the fact that the iterates generated by SGD can be
brittle and large deviations from the expected value can occur, e.g., see
[Gow+20] and references therein. Hence, a high-probability bound is attractive
since it reassures the practitioner that certain behavior occurs at least with
a close-to-$1$ probability for a single realization of iterates.

(ii) Policy gradient methods can be interpreted as gradient descent applied to
the policy optimization problem in RL [SB18, Ch. 13], see in particular [SB18,
p. 337] for historical remarks. Therefore, when the state space is large
[Bot10] and due to necessary approximation, one oftentimes resorts to
stochastic variants, whose convergence guarantees are often stated in terms of
expectations [Lan23], with the exception of [DZL21], see also [MDB20, § 2.2].
The high-probability convergence rate provided in [DZL21] can be seen as a
loosened bound of the large deviation rate we aim to derive. The pursuit of a
tight high-probability concentration bound for the iterations produced by
stochastic policy gradient methods holds significant potential for bolstering
the practical implementation and interpretability of policy gradient methods,
thereby improving the overall applicability of RL. Studying the concentration
behavior of SGD iterates through the lens of large deviations is pioneered by
[BJK23]. It is worth mentioning that, however, their analysis exploits strong
convexity of the optimization objective. Then, a first step towards
understanding more precisely the concentration behavior of stochastic policy
gradient iterates would be to study its entropy-regularized variant, which
already faces the difficulties of non-convexity and non-uniformity of the PL
constant.

As the theory of large deviations is the key tool in this paper, we briefly
introduce it already at this stage. Let $X_{t}\in\mathbb{R}^{d}$ be the
$t^{\mathrm{th}}$ iterate of some stochastic algorithm aimed at driving
$X_{t}$ to $x^{\star}$ for $t\to+\infty$, then, many aforementioned works
provide statistical guarantees of the form
$\mathbb{P}(\|X_{t}-x^{\star}\|_{2}\leq\varepsilon)\geq 1-\beta$ $\forall
t\geq T$ for an appropriately chosen triple $(T,\varepsilon,\beta)$. Although
often impressive pieces of work, there are some remarks to be made. First, it
is often not clear if these high-probability bounds are tight. Secondly, the
discrepancy is often measured by a sufficiently simple function, like the
$\ell_{2}$-norm in this case, however, in practice one might be interested in
vastly different sublevel sets, e.g., sublevel sets capturing harmful events,
the ones that are of interest in safe RL. Third, the guarantees are oftentimes
states for particular policy parametrizations, a unifying framework the
generalizes performance analysis across different policy parametrizations
remains largely unexplored. The theory of large deviations is precisely
powerful when one aims to address these aforementioned points. Let us clarify
terminology and provide intuition, yet, while skipping some details. A
sequence of finite (probability) measures $(\mu_{t})_{t}$ on $\mathbb{R}^{d}$
is said to satisfy a large deviation principle (LDP) with rate function
$I:\mathbb{R}^{d}\to[0,+\infty]$ when for any Borel set
$\Theta\subseteq\mathbb{R}^{d}$

$\displaystyle-\overset{\circ}{r}:=-\inf_{\theta\in\overset{\circ}{\Theta}}I(\theta)\leq\liminf_{t\to+\infty}\frac{1}{t}\log\mu_{t}({\Theta})\leq\limsup_{t\to+\infty}\frac{1}{t}\log\mu_{t}({\Theta})\leq-\inf_{\theta\in\overline{\Theta}}I(\theta)=:-\overline{r}.$
(1.1)

Now, identifying $(\mu_{t})_{t}$ with a sequence of random variables
$(X_{t})_{t}$, we have after rearranging (1.1) that
$\mathrm{exp}(-\overset{\circ}{r}t+o(t))\leq\mathbb{P}(X_{t}\in\Theta)\leq\mathrm{exp}(-\overline{r}t+o(t)).$
As such, an LDP captures—possibly tight, e.g., under mild topological
assumptions—convergence rates. Indeed, regarding applicability, once the rate
function is identified, the corresponding inaccuracy rate can be obtained for
any new given region of interest. For a detailed exposition of large
deviations, we refer to an overview paper [Var08] and the book [DZ09]. As
alluded to above, we will use the theory of large deviations to study
stochastic policy gradient iterates, that is, to study the iterates of a non-
convex optimization algorithm. Although large deviation tools appeared in
seminal work on non-convex optimization [GL13], that work does not provide an
LDP. What is more, large deviations are intimately connected to rare events,
whose analysis is of interest to RL [FMP08]. Also, efficient adaptive sampling
techniques become available thanks to careful deployment of large deviation
theory [DW04], an approach that is recently attracting interest in the context
of SGD [Lah23].

#### Contributions.

  1. (i)

We find, with high probability, an upper bound on the rate function for
iterates generated by softmax policy gradient with an entropy regularized
objective (2.3), see Theorem 4.3. We also recover results similar to [MDB20],
yet, via large deviation theory, see Lemma 3.2.

  2. (ii)

We demonstrate the wide applicability of having established a large deviation
rate by leveraging the contraction principle to establish large deviation
rates for a wide range of tabular policy parametrizations beyond the softmax
parametrization. In particular, we recover the exponential rate from [Mei+20,
Thm. 4], yet, as a mere corollary to Theorem 4.3, see Corollary 5.2.

  3. (iii)

Effectively, we establish a LDP upper bound for SGD under a PL condition,
which is of independent interest.

In Section 2 we describe the RL setting under consideration whereas in Section
3 we derive a preliminary exponential bound on the convergence of the value
function in probability. Then, in Section 4 we provide our main result: a LDP
upper bound for the stochastic policy gradient iterates. At last, we show in
Section 5 that this LDP upper bound can be lifted from a softmax
parametrization to a whole family of parametrizations, which directly leads to
exponential convergence rates for existing and new policy parametrizations,
with high probability.

##  2 Problem statement.

#### Markov decision process (MDP).

We consider a finite MDP given by a six-tuple
$\left(\mathcal{S},\mathcal{A},P,c,\gamma,\rho\right)$ consisting of a finite
state space $\mathcal{S}=\\{1,\ldots,S\\}$, a finite action space
$\mathcal{A}=\\{1,\ldots,A\\}$, a transition kernel
$P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$, a cost-per-
stage function $c:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, assumed
to be bounded111One can set the cost of a particular stage to be $\infty$ but
that results in an infeasible/unbounded optimization problem., a discount
factor $\gamma\in(0,1)$, and an initial distribution
$\rho\in\Delta(\mathcal{S})$. Here, we use
$\Delta(\mathcal{S}):=\\{p\in\mathbb{R}^{|\mathcal{S}|}:\
\sum_{i=1}^{|\mathcal{S}|}p_{i}=1,p\geq 0\\}$ to denote the probability
simplex over $\mathcal{S}$. Throughout the rest of the paper we restrict
attention to stationary policies, which are described by a stochastic kernel
$\pi\in\Pi=\Delta(\mathcal{A})^{|\mathcal{S}|}$. The value function
$V^{\pi}:\Delta(\mathcal{S})\rightarrow\mathbb{R}$ associated with $\pi$ is
defined through

$\displaystyle
V^{\pi}(\rho):=\mathbb{E}\big{[}\textstyle\sum_{k=0}^{\infty}\gamma^{k}c\left(s_{k},a_{k}\right)|s_{0}\sim\rho,a_{k}\sim\pi\left(\cdot|s_{k}\right),s_{k+1}\sim
P(\cdot|s_{k},a_{k})\big{]},$ (2.1)

and the main objective is to minimize $V^{\pi}(\rho)$ across all $\pi\in\Pi.$

#### Entropy-regularized reinforcement learning (RL).

It is sometimes useful to work with the modified objective where a strongly
convex regularizer is added, that is,
$V^{\pi}_{\tau}(\rho):=V^{\pi}(\rho)+\tau\cdot H(\rho,\pi)$ [NJG17, Mei+20a],
where $\tau>0$ and

$H(\rho,\pi)={\mathbb{E}}\big{[}\textstyle\sum_{k=0}^{\infty}-\gamma^{k}\log\pi\left(a_{k}|s_{k}\right)|s_{0}\sim\rho,a_{k}\sim\pi\left(\cdot|s_{k}\right),s_{k+1}\sim
P\left(\cdot|s_{k},a_{k}\right)\big{]}.$

An optimal policy $\pi^{\star}\in\Pi$ is defined through the condition
$V_{\tau}^{\pi^{\star}}(\rho)\leq V_{\tau}^{\pi}(\rho)$ for all $\pi\in\Pi.$

#### Softmax policy gradient for entropy-regularized objective.

The softmax transform $\pi_{\theta}(\cdot|s):=$
$\operatorname{softmax}(\theta(s,\cdot))$ of any function
$\theta:\mathcal{S}\times\mathcal{A}\rightarrow$ $\mathbb{R}$ is defined
through

$\pi_{\theta}(a|s)=\frac{\mathrm{exp}\left({\theta(s,a)}\right)}{\sum_{a^{\prime}\in\mathcal{A}}\mathrm{exp}\left({\theta\left(s,a^{\prime}\right)}\right)}\quad\forall
a\in\mathcal{A}.$ (2.2)

In the remainder, we frequently think of $\theta$ as a policy parameter in
$\mathbb{R}^{d=|\mathcal{S}||\mathcal{A}|}$ and we use
$V^{\theta}_{\tau}(\rho)$ for $V^{\pi_{\theta}}_{\tau}(\rho)$. By [Nac+17,
Thm. 3] there exists $\theta^{\star}\in\mathbb{R}^{d}$ such that
$\pi_{\theta^{\star}}$ is the optimal policy of the entropy-regularized MDP.
By the policy gradient theorem [Sut+99], the policy gradient
$g(\theta_{t}):=\partial
V^{\theta}_{\tau}(\rho)/\partial\theta|_{\theta=\theta_{t}}$ is given by
$\partial V^{\theta}_{\tau}(\rho)/\partial\theta(s,a)=1/(1-\gamma)\cdot
d_{\rho}^{\theta}(s)\cdot\pi_{\theta}(a|s)\cdot A^{\theta}_{\tau}(s,a)$ ,
where $d_{\rho}^{\theta}$ denotes the discounted state-visitation frequency
measure, and $A^{\theta}_{\tau}$ is the advantage function associated with the
regularized objective, see also [Mei+20a, Lem. 1]. In practice, however,
computing the advantage function is computationally expensive. It is therefore
convenient to work with estimates of the exact gradient. Throughout the rest
of the paper we assume unbiased stochastic sample access to
$\partial_{\theta}V^{\pi_{\theta}}_{\tau}(\rho)|_{\theta=\theta^{\prime}}$,
denoted as $\tilde{g}(\theta^{\prime})$. Stochastic softmax policy gradient
with entropy-regularized objective thus suggests to update policy parameters
via

$\theta_{t+1}\leftarrow\theta_{t}-\eta_{t}\cdot\tilde{g}(\theta_{t}).$ (2.3)

######  Assumption 2.1 (Warm start with sufficient exploration).

The initial state distribution satisfies $\min_{s\in\mathcal{S}}\rho(s)>0$. In
addition, the initial iterate $\theta_{1}$ is chosen around a
$\Delta$-neighborhood of $\theta^{\star}$ for a universal constant $\Delta>0$.

The above assumption simplifies the exposition and such an initial
$\theta_{1}$ can be obtained by a stochastic policy gradient method such as
[DZL21, Alg. 3.2]. We additionally define
$Z_{t}:=g(\theta_{t})-\tilde{g}(\theta_{t}).$ As in [BJK23] we make the
following assumption.

######  Assumption 2.2 (Gradient estimation uncertainty).

The stochastic process $(Z_{t})_{t}$ satisfies: $(i)$ $Z_{t}$ depends on the
past only through $\theta_{t}$; $(ii)$ $\mathbb{E}[Z_{t}|\theta_{t}=\theta]=0$
for any $\theta$ and $(iii)$ the distribution of $Z_{t}$ is independent of the
iterate index $t\in\mathbb{N}$.

By Assumption 2.2 $(i)$, the process $(\theta_{t})_{t\geq 0}$ generated by
(2.3) is a Markov chain. We use
$\Lambda(\lambda;\theta)=\log\mathbb{E}[\mathrm{exp}(\langle\lambda,Z_{t}\rangle)\mid\theta_{t}=\theta]$
to denote the conditional log-moment generating function (LMGF) of
$Z_{t}\in\mathbb{R}^{d}$. We also define
$M(\nu;\theta)=\mathbb{E}[\mathrm{exp}(\nu\|Z_{t}\|_{2}^{2})\mid\theta_{t}=\theta]$
as the conditional moment-generating function (MGF) of $\|Z_{t}\|_{2}^{2}$.
Now, we impose the following technical assumption to ensure that the tail
probabilities of the disturbances $(Z_{t})_{t}$ decay sufficiently fast.

######  Assumption 2.3 (Sub-Gaussian process).

All elements of the sequence $(Z_{t})_{t}$ follow a $\sigma$-sub-Gaussian
distribution for some $\sigma>0$, i.e.,

$\Lambda(\lambda;\theta)\leq\tfrac{1}{2}\sigma^{2}\|\lambda\|_{2}^{2}\quad\forall\lambda,\theta\in\mathbb{R}^{d}.$
(2.4)

A Monte-Carlo gradient estimation method that satisfies the above assumptions
is proposed by [DZL21]. The method operates by generating trajectories of MDP
with policy parameter $\theta$ and then estimate the advantage function based
on these trajectories.

######  Lemma 2.4 ($L_{1}$-smoothness of the value function [Aga+21, Lem.
D.4]).

There exists a constant $L_{1}>0$ such that

$|V^{\pi_{\theta}}_{\tau}(\rho)-V^{\pi_{\theta^{\prime}}}_{\tau}(\rho)-\langle
g(\theta^{\prime}),\theta-\theta^{\prime}\rangle|\leq\tfrac{1}{2}{L_{1}}\|\theta-\theta^{\prime}\|_{2}^{2}\quad\forall\theta,\theta^{\prime}\in\mathbb{R}^{d}.$
(2.5)

For the dependency of $L_{1}$ on the four-tuple
$(c,\gamma,\tau,|\mathcal{A}|)$ see [Mei+20a, Lem. 7 & 14].

##  3 Preliminaries.

######  Lemma 3.1 (Non-uniform Polyak-Łojasiewicz condition).

If Assumption 2.1 hold, then
$\left\|g(\theta)\right\|_{2}^{2}\geq\mu(\theta)\big{(}V_{\tau}^{\theta}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\big{)},$
where
$\mu(\theta)=2\tau|\mathcal{S}|^{-1}\min_{s}\rho(s)$$\min_{s,a}\pi_{\theta}(a|s)^{2}$
$\|d_{\rho}^{\pi_{\theta^{\star}}}/\rho\|_{\infty}^{-1}.$ Moreover, if
Assumption 2.2 and 2.3 hold and $\eta_{t}\leq
1/(t+\sqrt{3\sigma^{2}/(2\epsilon\Delta)})$, for iterates generated by (2.3),
we have $\mu\\!=\inf_{t\geq 1}\mu(\theta_{t})\\!>\\!0$ with probability at
least $1-\epsilon/6$.

###### Proof.

By [Mei+20a, Lem. 15], we have
$\left\|g(\theta)\right\|_{2}^{2}\geq\mu(\theta)\big{(}V_{\tau}^{\theta}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\big{)},$
where
$\mu(\theta)=2\tau|\mathcal{S}|^{-1}\min_{s}\rho(s)\min_{s,a}\pi_{\theta}(a|s)^{2}\|d_{\rho}^{\pi_{\theta^{\star}}}/\rho\|_{\infty}^{-1}.$
According to [DZL21, Lem. 6.4] we have further $\inf_{t\geq
1}\pi_{\theta_{t}}(a|s)>0$ with probability $1-\epsilon/6$, which concludes
the proof. ∎

Lemma 3.1 states that along a trajectory of (2.3), with high probability, we
have that $\mu(\theta_{t})>0$ for all $t$. In what follows we will exploit
that $\mu\\!=\inf_{t\geq 1}\mu(\theta_{t})$ is strictly positive with high
probability. Next, we derive elementary recursive inequalities and provide the
first main result. If $\eta_{t}$ satisfies $0<\eta_{t}\leq 1/L_{1}$ for all
$t=1,\ldots,T$, then (2.3) implies that

$\displaystyle V^{\theta_{t+1}}_{\tau}(\rho)$
$\displaystyle=V^{\theta_{t}-\eta_{t}g(\theta_{t})+\eta_{t}Z_{t}}_{\tau}(\rho)$
$\displaystyle\leq V^{\theta_{t}}_{\tau}(\rho)-\eta_{t}\langle
g(\theta_{t}),g(\theta_{t})-Z_{t}\rangle+\tfrac{1}{2}{\eta_{t}^{2}L_{1}}\|g(\theta_{t})-Z_{t}\|_{2}^{2}$
$\displaystyle\leq
V^{\theta_{t}}_{\tau}(\rho)-\eta_{t}\|g(\theta_{t})\|_{2}^{2}+\eta_{t}\langle
g(\theta_{t}),Z_{t}\rangle+{\eta_{t}^{2}L_{1}}\big{(}\|g(\theta_{t})\|_{2}^{2}+\|Z_{t}\|_{2}^{2}\big{)}$
$\displaystyle\leq
V^{\theta_{t}}_{\tau}(\rho)+\mu\left({\eta_{t}^{2}L_{1}}-\eta_{t}\right)\big{(}V^{\theta_{t}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\big{)}+\eta_{t}\langle
g(\theta_{t}),Z_{t}\rangle+{\eta_{t}^{2}L_{1}}\|Z_{t}\|_{2}^{2},$

where the first inequality follows from the $L_{1}$-smoothness of the value
function, the second inequality exploits that $\|x-y\|_{2}^{2}\leq
2\|x\|_{2}^{2}+2\|y\|_{2}^{2}$ for all $x,y\in\mathbb{R}^{d}$, and the last
inequality holds because $\eta_{t}\leq 1/L_{1}$ and the PL condition from
Lemma 3.1. Subtracting $V_{\tau}^{\theta^{\star}}(\rho)$ from both sides
yields

$\begin{split}&V^{\theta_{t+1}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\\\
&\leq(1-\mu\eta_{t}+\mu\eta_{t}^{2}L_{1})(V^{\theta_{t}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho))+\eta_{t}\langle
g(\theta_{t}),Z_{t}\rangle+{\eta_{t}^{2}L_{1}}\|Z_{t}\|_{2}^{2}.\end{split}$
(3.1)

Also, observe that since222To show that $\mu\leq L_{1}$, one exploits that
$L_{1}$-smoothness implies Lipschitz continuity of the gradient and recalls
that the PL condition implies a quadratic growth condition [KNS16, App. A].
$\eta_{t}\leq 1/L_{1}$, $\mu\leq L_{1}$ and $\eta_{t},L_{1}>0$, we have
$\mu\eta_{t}(\eta_{t}L_{1}-1)\in(-1,0]$ and thus
$(1-\mu\eta_{t}+\mu\eta_{t}^{2}L_{1})\in(0,1]$ for $t=1,\dots,T$. Next, by
substituting the points $\theta^{\prime}=\theta-1/L_{1}\cdot g(\theta)$ and
$\theta$ into (2.5), we obtain $V^{\theta-1/L_{1}\cdot
g(\theta)}_{\tau}(\rho)\leq
V^{\theta}_{\tau}(\rho)-\tfrac{1}{2}L_{1}^{-1}\|g(\theta)\|_{2}^{2}$. Using
the optimality of $\theta^{\star}$, we may then conclude that
$V_{\tau}^{\theta^{\star}}(\rho)\leq V^{\theta-1/L_{1}\cdot
g(\theta)}_{\tau}(\rho)\leq
V^{\theta}_{\tau}(\rho)-\tfrac{1}{2}L_{1}^{-1}\|g(\theta)\|_{2}^{2}$ which
implies that

$\displaystyle\|g(\theta)\|_{2}^{2}$ $\displaystyle\leq
2L_{1}(V^{\theta}_{\tau}(\rho)-V^{\theta^{\star}}_{\tau}(\rho))\quad\forall\theta\in\mathbb{R}^{d}.$
(3.2)

######  Lemma 3.2 (Exponential upper bound).

Suppose Assumptions 2.1, 2.2, and 2.3 hold, and choose $T>1$,
$\epsilon\in(0,1)$. Then, there is a universal constant $C>0$ such that the
following hold with probability at least $1-\epsilon/6$. Let
$C_{\mathsf{M}}=(\sigma\sqrt{|\mathcal{S}||\mathcal{A}|}C)^{2}$ where $\sigma$
is as in (2.4). and set $\eta>0$ such that
$(\mu\eta-1)>\sigma^{2}/C_{\mathsf{M}}$. Let $\eta_{t}=\eta/(t+t_{0}+1)$ for
all $t=1,\ldots,T$ and choose $t_{0}$ and $K$ such that

$\displaystyle t_{0}\geq$
$\displaystyle\max\left\\{\frac{\eta^{2}L_{1}}{(\mu\eta-1)-B_{0}C_{0}\eta^{2}}-1,L_{1}\eta-2,\sqrt{\frac{3\sigma^{2}}{2\epsilon\Delta}}\right\\},$
$\displaystyle K\geq$
$\displaystyle\max_{t=1,\dots,T}\left\\{B_{0}^{-1},(t_{0}+1)\big{(}V^{\theta_{1}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\big{)},\frac{2c_{t}C_{\mathsf{M}}}{1-(a_{t}+B_{0}C_{0}b_{t}^{2})}\right\\},$
(3.3)

where $B_{0}=1/(2\eta^{2}L_{1}C_{\mathsf{M}})$, $C_{0}=2L_{1}\sigma^{2}$,

$\displaystyle
a_{t}=\frac{t+t_{0}+1}{t+t_{0}}\left(1-\mu\eta_{t}+\mu\eta_{t}^{2}L_{1}\right),\
b_{t}=\frac{\eta}{\sqrt{t+t_{0}}},\ \text{and}\
c_{t}=\frac{\eta^{2}L_{1}}{t+t_{0}+1}.$ (3.4)

Then, for any $\delta\geq 0$ and $t=1,\dots,T$ we have that

$\displaystyle\mathbb{P}\left(\big{(}V^{\theta_{t+1}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\big{)}\geq\delta\right)\leq
e^{1-(t+t_{0}+1)\delta/K}.$

The proof is inspired by [BJK23], with the difference being that they work
with strongly convex objective functions. Unfortunately,
$V^{\theta}_{\tau}(\rho)$ fails to be convex in $\theta.$

###### Proof.

Define an auxiliary process
$Y_{t}=(t+t_{0})(V^{\theta_{t}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)).$
Then, the recursion (3.1) implies that $Y_{t+1}\leq
a_{t}Y_{t}+b_{t}\sqrt{t+t_{0}}\langle
g(\theta_{t}),Z_{t}\rangle+c_{t}\|Z_{t}\|^{2},$ where $a_{t}$, $b_{t}$ and
$c_{t}$ are as in (3.4). Defining the MGFs associated with $Y_{t}$ as
$\Phi_{t}(\nu)=\mathbb{E}\left[\exp\left(\nu Y_{t}\right)\right]$ and
$\Phi_{t+1|t}\left(\nu;\theta_{t}\right)=\mathbb{E}\left[\exp\left(\nu
Y_{t+1}\right)\mid\theta_{t}\right]$ for $\nu\in\mathbb{R}$, the recursion
(3.1) further implies that

$\displaystyle\Phi_{t+1|t}\left(\nu;\theta_{t}\right)$
$\displaystyle\\!\leq\exp\left(a_{t}\nu
Y_{t}\right)\mathbb{E}\left[\exp\left(2b_{t}\nu\sqrt{t+t_{0}}\langle
g(\theta_{t}),Z_{t}\rangle\right)\mid\theta_{t}\right]^{1/2}\mathbb{E}\\!\left[\exp\big{(}2c_{t}\nu\left\|Z_{t}\right\|_{2}^{2}\big{)}\mid\theta_{t}\right]^{1/2}$
$\displaystyle\leq\exp\left(a_{t}\nu
Y_{t}\right)\exp\left(\sigma^{2}b_{t}^{2}\nu^{2}(t+t_{0})\|g(\theta_{t})\|_{2}^{2}\right)^{1/2}\mathbb{E}\left[\exp\big{(}2c_{t}\nu\left\|Z_{t}\right\|_{2}^{2}\big{)}\mid\theta_{t}\right]^{1/2}$
$\displaystyle\leq\exp\left(a_{t}\nu
Y_{t}\right)\exp\left(2L_{1}\sigma^{2}b_{t}^{2}\nu^{2}Y_{t}\right)^{1/2}\mathbb{E}\left[\exp\big{(}2c_{t}\nu\left\|Z_{t}\right\|_{2}^{2}\big{)}\mid\theta_{t}\right]^{1/2},$

where the first inequality follows from Hölder’s inequality, the second
inequality follows from (2.4) and the last inequality follows from (3.2).
Recall that $d=\mathrm{dim}(Z_{t})$ and define
$B_{0}=1/(2\eta^{2}L_{1}(\sigma\sqrt{d}C)^{2})$. Then, there is a constant
$C>0$ such that for all $\nu\in[0,B_{0}]$, we have by monotonicity of $c_{t}$,
Hölder’s inequality for $p=1/(\nu 2\eta^{2}L_{1}(\sigma\sqrt{d}C)^{2})\geq 1$
and [Jin+19, Lem. 2] that
$M(2c_{t}\nu;\theta)\leq\mathrm{exp}(2c_{t}\nu(\sigma\sqrt{d}C)^{2})$. Recall
that $(\sigma\sqrt{d}C)^{2}=C_{\mathsf{M}}$ because
$d=|\mathcal{S}||\mathcal{A}|$. Moreover, as
$\mathrm{exp}(x)\geq\mathrm{exp}(x)^{1/2}$ for $x\geq 0$, we can simplify the
above inequality to

$\displaystyle\Phi_{t+1|t}\left(\nu;\theta_{t}\right)$
$\displaystyle\leq\exp\left(a_{t}\nu
Y_{t}\right)\exp\left(2L_{1}\sigma^{2}b_{t}^{2}\nu^{2}Y_{t}\right)\mathrm{exp}(2c_{t}\nu
C_{\mathsf{M}})$ (3.5) $\displaystyle=\mathrm{exp}\left(\nu\left(a_{t}+\nu
C_{0}b_{t}^{2}\right)Y_{t}\right)\mathrm{exp}(2c_{t}\nu
C_{\mathsf{M}})\quad\forall\nu\leq B_{0}$

for $C_{0}=2L_{1}\sigma^{2}$. Taking expectations on both sides of (3.5)
yields

$\Phi_{t+1}(\nu)\leq\Phi_{t}\left(\nu(a_{t}+B_{0}C_{0}b_{t}^{2})\right)\mathrm{exp}(2c_{t}\nu
C_{\mathsf{M}})\quad\forall\nu\leq B_{0}.$ (3.6)

We aim to show that $\Phi_{t+1}(\nu)\leq\mathrm{exp}(\nu K)$ for $t=1,\dots,T$
by studying the magnitude of $(a_{t}+B_{0}C_{0}b_{t}^{2})$ and using
induction. First, it can be shown that $a_{t}<1$ for all $t\geq 1$. To do so,
rewrite $a_{t}$ as

$a_{t}=1-\frac{\mu\eta-1}{t+t_{0}}\left(1-\frac{\mu\eta^{2}L_{1}}{(\mu\eta-1)(t+t_{0}+1)}\right),$
(3.7)

where we exploit the identity $1+1/s=(s+1)/s$ for $s\neq 0$. We have that
$(\mu\eta-1)>0$. Now since $t_{0}\geq L_{1}\eta-2$ by assumption, we have
$\eta_{t}\leq 1/L_{1}$. Recall as well the fact that $\mu\leq L_{1}$, which
leads to $\eta_{t}\leq 1/\mu$ and thus $\mu\eta_{t}\leq 1$, that is,
$\mu\eta/(t+t_{0}+1)\leq 1$. Exactly this implies that
$(\mu\eta-1)/(t+t_{0})\in(0,1]$. This covers the first non-trivial fraction of
(3.7). Now for the second part, we have the implication that

$t_{0}+1\geq\frac{\mu\eta^{2}L_{1}}{\mu\eta-1}\implies\frac{\mu\eta^{2}L_{1}}{(\mu\eta-1)(t+t_{0}+1)}\in(0,1],$

from where we can conclude that $a_{t}\in[0,1)$ for any finite $t\geq 1$.
However, we will need $(a_{t}+B_{0}C_{0}b_{t}^{2})<1$. As $b_{t}$ decays with
$t_{0}$, this can be achieved by selecting a sufficiently large $t_{0}$.
Explicitly, let $\mu\eta=1+\varepsilon$ for some $\varepsilon>0$. By the
definition of $b_{t}$ and $a_{t}$ as in (3.7) we then obtain

$a_{t}+B_{0}C_{0}b_{t}^{2}=1-\frac{\varepsilon}{t+t_{0}}\left(1-\frac{B_{0}C_{0}\eta^{2}}{\varepsilon}-\frac{\mu\eta^{2}L_{1}}{\varepsilon(t+t_{0}+1)}\right).$
(3.8)

By assumption, we have $\mu\eta-1>\sigma^{2}/C_{\mathsf{M}}.$ This implies
that $\varepsilon>B_{0}C_{0}\eta^{2}.$ It then follows that
$a_{t}+B_{0}C_{0}b_{t}^{2}\in[0,1)$ for any finite $t\geq 1$ and
$t_{0}+1\geq\mu\eta^{2}L_{1}/(\varepsilon-B_{0}C_{0}\eta^{2}).$ Recall also
that $t_{0}\geq L_{1}\eta-2$ by assumption. Thus, we have $\eta_{t}\leq
1/L_{1}$. Assumption 2.1 allows then for the following inductive procedure.
Let $\nu\in[0,1/K]$ for $K$ as in (3.3) then, for $t=1$, we have
$\Phi_{1}(\nu)\leq\mathrm{exp}(\nu K)$ since $K\geq
t_{0}\left(V^{\theta_{1}}_{\tau}(\rho)-V_{\tau}^{\theta^{\star}}(\rho)\right)$.
Now suppose $\Phi_{t}(\nu)\leq\mathrm{exp}(\nu K)$ for some arbitrary $t\geq
1$, then, we have by the inductive assumption that
$\Phi_{t+1}\leq\mathrm{exp}(2c_{t}C_{\mathsf{M}}\nu)\mathrm{exp}(\nu(a_{t}+B_{0}C_{0}b_{t}^{2})K).$
However, since for $t=1,\dots,T$ we also have that $K\geq
2c_{t}C_{\mathsf{M}}/(1-(a_{t}+B_{0}C_{0}b_{t}^{2})),$ which is well-defined
since $(a_{t}+B_{0}C_{0}b_{t}^{2})<1$, by our selection of $t_{0}$ and $\eta$,
it follows that $\Phi_{t+1}(\nu)\leq\mathrm{exp}(\nu K)$ for $t=1,\dots,T$. By
[Har+19, Claim A.7], if a random variable $X\in\mathbb{R}$ satisfies
$\mathbb{E}[\mathrm{exp}(\lambda X)]\leq C_{1}\mathrm{exp}(\lambda C_{2})$ for
all $\lambda\leq 1/C_{2}$ and some universal constants $C_{1}$ and $C_{2}$,
then $\mathbb{P}(X\geq C_{2}\log(1/\delta))\leq C_{1}e\delta$. Hence, after
applying [Har+19, Claim A.7] one finds that $\mathbb{P}(Y_{t}\geq
C_{3})\leq\mathrm{exp}(1-C_{3}/K),$ for any choice of $C_{3}\geq 0$ and
$t=1,\dots,T$. The proof is concluded by substituting the expression for
$Y_{t}$ into the previous inequality and a union bound. ∎

We note that by the expressions for $(a_{t},b_{t},c_{t})$ and (3.8) it follows
that $\lim_{t\to+\infty}2c_{t}C_{\mathsf{M}}/$
2$(1-(a_{t}+B_{0}C_{0}b_{t}^{2}))$ is bounded, that is, one can freely select
$T$, which we will exploit later in Theorem 4.2.

##  4 Large deviations.

To provide our main result, we need to impose another assumption on the random
variables $(Z_{t})_{t}$.

######  Assumption 4.1 (Conditional LMGF regularity).

There is a $L_{\Lambda}\geq 0$ such that

$|\Lambda(\lambda;\theta_{1})-\Lambda(\lambda;\theta_{2})|\leq
L_{\Lambda}\|\lambda\|_{2}^{2}\|\theta_{1}-\theta_{2}\|_{2}\quad\forall(\lambda,\theta_{1},\theta_{2})\in\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}^{d}.$

We refer to [BJK23, p. 5] for a discussion of this assumption. For instance,
when the conditional distribution of $Z_{t}$ given $\theta_{t}=\theta$ is
Gaussian, and its covariance matrix is Lipschitz continuous in $\theta$, then
Assumption 4.1 holds. In particular, if the covariance is independent of
$\theta$, this trivially holds true. Next, we define the MGF of $\theta_{t}$
as
$\mathbb{R}^{d}\ni\lambda\mapsto\Gamma_{t}(\lambda):=\mathbb{E}\left[\mathrm{exp}(\langle\lambda,\theta_{t}-\theta^{\star}\rangle)\right]$
and similarly the LMGF as
$\mathbb{R}^{d}\ni\lambda\mapsto\log\Gamma_{t}(\lambda)$. Now we are equipped
to provide our main technical result, leading directly to a large deviation
principle (LDP) upper bound. Note that $\Gamma_{t}(\lambda)$ depends on the
optimal solution $\theta^{\star}$ which is fixed and unknown.

######  Theorem 4.2 (Limiting LMGF).

Suppose that Assumptions 2.1, 2.2, 2.3 and 4.1 hold and set
$\eta_{t}=\eta/(t+t_{0}+1)$ as in Lemma 3.2. Then, with probability at least
$1-\epsilon/6$ we have that

$\limsup_{t\to+\infty}\frac{1}{t}\log\Gamma_{t}(t\lambda)\leq
r(\lambda)+\int_{0}^{1}\Lambda\left(\eta
QD(x)Q^{\top}\lambda;\theta^{\star}\right)\mathrm{d}x=:\Psi(\lambda),$ (4.1)

where $r(\lambda)=O(\|\lambda\|^{3}_{2})$ with its expression presented in the
proof below, and $Q$ and $D(x)$ are such that $H(\theta^{\star})=QDQ^{\top}$,
$QQ^{\top}=I_{d}$, $D=\mathrm{diag}(\rho_{1},\dots,\rho_{n})$ being the
diagonalization of $H(\theta^{\star})$, and
$D(x)=\mathrm{diag}(x^{\eta\rho_{1}-1},\ldots,x^{\eta\rho_{n}-1})$.

To prove Theorem 4.2, we will largely follow the proof strategy of [BJK23,
Lem. 6], yet, with technical deviations regarding indexing of the sequences.
In addition, we cannot appeal to the strong convexity exploited in [BJK23].

###### Proof.

We provide a brief overview of the proof. Step 0 constructs a deterministic
sequence as a basis for deriving recursions of MGF. Step 1 defines a ball
around the optimal parameter and split the cases depending on whether
$\theta_{\ell}$ resides within the ball. Step 2-4 study individual cases
leading to their respective recursive relation. Finally, Step 5 summarizes the
previously derived recursions, takes the limit and concludes. Step 0,
sequence. Fix some vector $\lambda\in\mathbb{R}^{d}$, integer $t\geq 1$ and
define the sequence of vectors $\zeta_{\ell}=B_{t,\ell}\zeta_{t}$ via
$B_{t,\ell}=(I-\eta_{\ell}H(\theta^{\star}))\cdot...\cdot(I-\eta_{t-1}H(\theta^{\star}))$
and $\zeta_{t}=t\lambda$, with $1\leq\ell<t$. As $\eta_{t}\leq 1/L_{1}$ we
have that $\|I-\eta_{t}H(\theta^{\star})\|_{2}\leq
1-\eta_{t}\lambda_{\mathrm{min}}(H(\theta^{\star}))$. Hence, using [BJK23,
Lem. 2] and exploiting ${\eta\lambda_{\mathrm{min}}(H(\theta^{\star}))}>1$,
i.e., recall $\eta\mu>1$ from Lemma 3.2, one can show that

$\|\zeta_{\ell}\|_{2}\leq
t\left(\frac{\ell+t_{0}+1}{t+t_{0}+1}\right)^{\eta\lambda_{\mathrm{min}}(H(\theta^{\star}))}\|\lambda\|_{2}\leq(\ell+t_{0}+1)\|\lambda\|_{2}.$

Step 1, conditional MGF. Let $\mu_{\ell}$ and $\nu_{\ell}$ be Borel measures
induced by $\theta_{\ell}$ and $\|\theta_{\ell}-\theta^{\star}\|_{2}$,
respectively. Then, one readily shows that
$\Gamma_{\ell+1}(\zeta_{\ell})=\textstyle\int_{\mathbb{R}^{d}}\Gamma_{\ell+1|\ell}(\zeta_{\ell};\theta)\mu_{\ell}(\mathrm{d}\theta).$
Next, define the sets
$B_{\ell}(\theta^{\star},\delta)=\\{\theta_{\ell}:\|\theta_{\ell}-\theta^{\star}\|_{2}\leq\delta\\}$.
Now we can construct the decomposition
$\Gamma_{\ell+1}(\zeta_{\ell})=\Gamma_{\ell+1|B_{\ell}(\theta^{\star},\delta)}(\zeta_{\ell})+\Gamma_{\ell+1|B^{c}_{\ell}(\theta^{\star},\delta)}(\zeta_{\ell})$,
which we study separately. Step 2, $\theta\in
B_{\ell}(\theta^{\star},\delta)$. We have that

$\displaystyle\Gamma_{\ell+1|\ell}(\zeta_{\ell};\theta)=\mathrm{exp}\left(\Lambda(\eta_{\ell}\zeta_{\ell};\theta)+\langle\zeta_{\ell},\theta-\eta_{\ell}g(\theta)-\theta^{\star}\rangle\right).$

Let $H(\theta)$ denote the Hessian of $V^{\pi_{\theta}}_{\tau}(\rho)$ at
$\theta$ and define the residual term
$h(\theta)=g(\theta)-H(\theta^{\star})(\theta-\theta^{\star})$. Recall Step 0,
Assumption 4.1 and define the largest residual term
$\bar{h}(\delta)=\sup_{\theta\in
B_{\ell}(\theta^{\star},\delta)}\|h(\theta)\|_{2}$, it follows that

$\displaystyle\Gamma_{\ell+1|\ell}(\zeta_{\ell};\theta)\leq$
$\displaystyle\mathrm{exp}\left(\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star})+L_{\Lambda}\eta_{\ell}^{2}\|\zeta_{\ell}\|_{2}^{2}\delta+\eta_{\ell}\|\zeta_{\ell}\|_{2}\bar{h}(\delta)+\langle\zeta_{\ell-1},\theta-\theta^{\star}\rangle\right)$
$\displaystyle\leq$
$\displaystyle\mathrm{exp}\left(\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star})+r_{0}(\lambda,\delta)\right)\mathrm{exp}(\langle\zeta_{\ell-1},\theta-\theta^{\star}\rangle)$

for
$r_{0}(\lambda,\delta)=4L_{\Lambda}\eta^{2}\|\lambda\|_{2}^{2}\delta+2\eta\|\lambda\|_{2}\bar{h}(\delta)$.
Hence, integrating, we find that

$\Gamma_{\ell+1|B_{\ell}(\theta^{\star},\delta)}(\zeta_{\ell})\leq\mathrm{exp}\left(\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star})+r_{0}(\lambda,\delta)\right)\Gamma_{\ell}(\zeta_{\ell-1}).$
(4.2)

Step 3, contraction. We construct another recursive formula. Start from

$\displaystyle\|\theta_{t+1}-\theta^{\star}\|_{2}$
$\displaystyle=\|\theta_{t}-\eta_{t}g(\theta_{t})+\eta_{t}Z_{t}-\theta^{\star}\|_{2}\leq\|\theta_{t}-\eta_{t}g(\theta_{t})-\theta^{\star}\|_{2}+\eta_{t}\|Z_{t}\|_{2},$

and expand
$\|\theta_{t}-\eta_{t}g(\theta_{t})-\theta^{\star}\|^{2}_{2}=\|\theta_{t}-\theta^{\star}\|_{2}^{2}-2\eta_{t}\langle\theta_{t}-\theta^{\star},g(\theta_{t})\rangle+\eta_{t}^{2}\|g(\theta_{t})\|_{2}^{2}.$
Due to optimality of $\theta^{\star}$ and $L_{1}$-smoothness of
$V^{\theta}_{\tau}$ we have $\|g(\theta_{t})\|_{2}^{2}\leq
L_{1}^{2}\|\theta_{t}-\theta^{\star}\|_{2}^{2}$ and

$\displaystyle-\langle\theta_{t}-\theta^{\star},g(\theta_{t})\rangle$
$\displaystyle\leq\tfrac{1}{2}L_{1}\|\theta_{t}-\theta^{\star}\|_{2}^{2}+(V^{\theta_{t}}_{\tau}(\rho)-V^{\theta^{\star}}_{\tau}(\rho))$
$\displaystyle\leq\tfrac{1}{2}L_{1}\|\theta_{t}-\theta^{\star}\|_{2}^{2}+\frac{1}{2\mu(\theta_{t})}\|g(\theta_{t})\|_{2}^{2}$
$\displaystyle\leq\tfrac{1}{2}L_{1}\|\theta_{t}-\theta^{\star}\|_{2}^{2}+\frac{L_{1}^{2}}{2\mu(\theta_{t})}\|\theta_{t}-\theta^{\star}\|_{2}^{2}.$

As such, one can set
$\gamma_{t}=(1+\eta_{t}L_{1}+\eta_{t}L_{1}^{2}/M\mu(\theta_{t})+\eta_{t}^{2}L_{1}^{2})^{1/2}\leq(3+L_{1}/\mu)^{1/2}=\bar{\gamma}$
such that

$\displaystyle\|\theta_{t+1}-\theta^{\star}\|_{2}$
$\displaystyle\leq\gamma_{t}\|\theta_{t}-\theta^{\star}\|_{2}+\eta_{t}\|Z_{t}\|_{2}\quad
t=1,\dots,T.$ (4.3)

Step 4, $\theta\in B^{c}_{\ell}(\theta^{\star},\delta)$. Using Step 3 and
Assumption 2.3 one can show that
$\Gamma_{\ell+1|\ell}(\zeta_{\ell};\theta)\leq\mathrm{exp}\left(\tfrac{1}{2}\sigma^{2}\eta^{2}\|\lambda\|_{2}^{2}\right)\mathrm{exp}(\bar{\gamma}(\ell+t_{0}+1)\|\lambda\|_{2}\|\theta-\theta^{\star}\|_{2}).$
Hence, we have

$\displaystyle\Gamma_{\ell+1|B^{c}_{\ell}(\theta^{\star},\delta)}(\zeta_{\ell})\leq\mathrm{exp}\left(\tfrac{1}{2}\sigma^{2}\eta^{2}\|\lambda\|_{2}^{2}\right)\int_{\tau\geq\delta}\mathrm{exp}(\bar{\gamma}(\ell+t_{0}+1)\|\lambda\|_{2}\tau)\nu_{\ell}(\mathrm{d}\tau).$

Exploiting Lemma 3.2, i.e. $\nu_{\ell}$ being induced by
$\mathbb{P}\left(\|\theta_{\ell}-\theta^{\star}\|_{2}\geq\delta\right)\leq
e^{1-(\ell+t_{0})L_{1}\delta^{2}/(2\mu K)}$, we know there is a sufficiently
large $\delta(\lambda)=O(\bar{\gamma}\|\lambda\|_{2}\mu K/L_{1})$, denoted as
$\bar{\delta}(\lambda)$ such that

$\displaystyle\Gamma_{\ell+1|B^{c}_{\ell}(\theta^{\star},\delta)}(\zeta_{\ell})\leq\bar{C}\mathrm{exp}\left(\tfrac{1}{2}\sigma^{2}\eta^{2}\|\lambda\|_{2}^{2}\right)$
(4.4)

for some constant $\bar{C}$ cf. [BJK23, Proof of Lem. 6]. Step 5, limiting
recursion. Combining (4.2) and (4.4) then yields

$\Gamma_{\ell+1}(\zeta_{\ell})\leq\bar{C}\mathrm{exp}\left(\tfrac{1}{2}\sigma^{2}\eta^{2}\|\lambda\|_{2}^{2}\right)+\mathrm{exp}\left(\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star})+r(\lambda)\right)\Gamma_{\ell}(\zeta_{\ell-1}),$

where $r(\lambda)=r_{0}(\lambda,\bar{\delta}(\lambda))$. Continuing with the
recursion provides us with

$\displaystyle\Gamma_{t+1}(t\lambda)\leq$
$\displaystyle\mathrm{exp}\left(\textstyle\sum^{t}_{\ell=1}\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star})+r(\lambda)\right)\Gamma_{1}(\zeta_{1})$
$\displaystyle+\bar{C}\mathrm{exp}\left(\tfrac{1}{2}\sigma^{2}\eta^{2}\|\lambda\|_{2}^{2}\right)\textstyle\sum^{t}_{\ell=1}\mathrm{exp}\left(\textstyle\sum^{t}_{j=\ell}\Lambda(\eta_{j}\zeta_{j};\theta^{\star})+r(\lambda)\right)$

Note that $\Gamma_{1}(\zeta_{1})$ is finite by Assumption 2.1. Then we
immediately obtain that

$\limsup_{t\to+\infty}t^{-1}\log\Gamma_{t+1}(t\lambda)\leq
r(\lambda)+\limsup_{t\to+\infty}t^{-1}\textstyle\sum^{t}_{\ell=1}\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star}).$

To complete the proof, we appeal to [BJK23, Lemma C.3] and find that

$\displaystyle\lim_{t\rightarrow+\infty}t^{-1}\textstyle\sum_{\ell=1}^{t}\Lambda(\eta_{\ell}\zeta_{\ell};\theta^{\star})=\int_{0}^{1}\Lambda\left(\eta
QD(x)Q^{\top}\lambda;\theta^{\star}\right)\mathrm{d}x.$

∎

To provide our main result, we recall that the Legendre-Fenchel transform of a
function $\Psi:\mathbb{R}^{d}\to\mathbb{R}$ is defined by
$I(\theta^{\prime})=\sup_{\lambda\in\mathbb{R}^{d}}\langle\theta^{\prime},\lambda\rangle-\Psi(\lambda)$
for all $\theta^{\prime}$.

######  Theorem 4.3 (LDP upper bound).

Suppose that Assumption 2.1, 2.2, 2.3 and 4.1 hold and set
$\eta_{t}=\eta/(t+t_{0}+1)$ as in Lemma 3.2. Define $\Psi$ as in Theorem 4.2.
Then, with probability at least $1-\epsilon/6$ we have that the sequence
$(\theta_{t})_{t}$ satisfies a LDP upper bound with a rate function $I$. The
function $I$ is the Legendre-Fenchel transformation of $\Psi$. That is, for
any Borel set $\Theta\subseteq\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$, we
have that

$\limsup_{t\to+\infty}\frac{1}{t}\log\mathbb{P}(\theta_{t}\in\Theta)\leq-\inf_{\theta^{\prime}+\theta^{\star}\in\overline{\Theta}}I(\theta^{\prime}).$
(4.5)

###### Proof.

Directly from Theorem 4.2 and the Gärtner-Ellis theorem [Gär77, Ell84]. ∎

Note, one can also bring the offset term $\theta^{\star}$ into the left-hand-
side of (4.5), i.e., consider
$\mathbb{P}(\theta_{t}-\theta^{\star}\in\Theta)$. Indeed, strictly speaking,
the LDP upper bound is derived for the sequence
$(\theta_{t}-\theta^{\star})_{t}$.

##  5 Ramifications

One could argue that the results (bounds) from above contribute towards a
better understanding of the softmax transformation, the effect of the
regularization parameter $\tau$, the effect of initialization and the analysis
of restrictive policy parametrizations, all active topics of research [Hen+20,
Mei+20, Li+21, Mei+20a]. However, more interesting is that Theorem 4.3 also
allows for a simple proof of exponential decay, with high probability, for a
whole family of policy parametrizations different from softmax.

The structure of $\Psi$ (non-negativity and finiteness) immediately reveals
that its Fenchel conjugate (Legendre-Fenchel transform) $I$ satisfies
$I(0)=0$, better yet, $I(\theta^{\prime})>0$ for all $\theta^{\prime}\neq 0$.
Hence, $I$ can be identified as a good rate function [DZ09, p. 4]. Moreover,
for any Borel set $\Theta$ such that $\theta^{\star}\not\in\overline{\Theta}$
we have, with high probability, that the probability
$\mathbb{P}(\theta_{t}\in\Theta)$ decays exponentially fast. Not only that, we
can provide a bound on the convergence rate for any of those sets, i.e., let
$r:=\inf_{\theta^{\prime}+\theta^{\star}\in\overline{\Theta}}I(\theta^{\prime})$,
then, $\mathbb{P}(\theta_{t}\in\Theta)\leq\mathrm{exp}(-rt+o(t))$. To lift
this observation to any continuous transformation of the softmax
parametrization we need the following principle from the theory of large
deviations. To avoid pathological examples, we assume all our sets to be
topological Hausdorff spaces.

######  Theorem 5.1 (Contraction principle [DZ09, § 4.2.1]).

Consider $U\subseteq\mathbb{R}^{d}$ and $W\subseteq\mathbb{R}^{q},$ and
$f:U\to W$ a continuous map. Define $I^{\prime}:W\to\mathbb{[}0,+\infty]$
through $I^{\prime}(w)=\inf_{u\in U,w=f(u)}I(u)$ for all $w\in W,$ where
$I:U\to\mathbb{[}0,+\infty]$ is a good rate function. Then, $I^{\prime}$ is
also a good rate function on $W$.

Although we studied a softmax policy, the contraction principle, originally
used in [DV76], allows us to extend our LDP results to any continuous
transformation $f$ of $\theta_{t}-\theta^{\star}$, e.g., one recovers the
escort transformation [Mei+20] by transforming $\theta_{t}$ component-wise by
the map $\mathbb{R}\ni w\mapsto p\log|w|$ for $p\geq 1$. To be explicit,
whereas the softmax policy is given by (2.2), the escort parametrization is
given by
$\pi_{\theta}(a|s)={|{\theta(s,a)}|^{p}}/{\sum_{a^{\prime}\in\mathcal{A}}|{\theta\left(s,a^{\prime}\right)|^{p}}}$.
Hence, we directly infer that the exponential decay rate extends from the
softmax- to the escort parametrization. Indeed, $w\mapsto p\log|w|$ is not a
smooth function, yet, for $p\geq 2$ the escort policy parametrization is
differentiable, which is precisely the setting for which an exponential decay
rate under entropic regularization is provided by [Mei+20, Thm. 4]. To
formally summarize this observation, by combining Theorem 4.3 and Theorem 5.1
we get the following.

######  Corollary 5.2 (Going beyond softmax).

Let
$(\theta_{t}-\theta^{\star})_{t}\subset\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
be a sequence corresponding to softmax policy gradient and let the sequence
$(\omega_{t}-\omega^{\star})_{t}\subset\mathbb{R}^{q}$ be defined via a
continuous map $f:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\to\mathbb{R}^{q}$
through $\omega_{t}-\omega^{\star}:=f(\theta_{t}-\theta^{\star})$ $\forall t$,
then, with probability at least $1-\epsilon/6$,

$\limsup_{t\to+\infty}\frac{1}{t}\log\mathbb{P}(\omega_{t}\in\Omega)\leq-\inf_{\omega^{\prime}+\omega^{\star}\in\overline{\Omega}}I^{\prime}(\omega^{\prime}),$
(5.1)

for any Borel set $\Omega\subseteq\mathbb{R}^{q}$ and $I^{\prime}$ as in
Theorem 5.1.

Similar to the escort transformation, one can study spherical\- and Taylor
softmax [BV16]. However, Corollary 5.2 is ought to be most interesting to
apply to prospective policy parametrizations leading to (5.1) being non-
trivial. Indeed, we emphasize that one must verify that (5.1) is non-trivial,
there is no free lunch.

To remove the $(1-\epsilon/6)$-high probability statements throughout, future
work aims at studying the multiphase algorithm from [DZL21] in the context of
large deviations, this requires being able to study a controlled sequence
$(Z_{t})_{t}$, which is a non-trivial extension. We also remark that in the
context of SGD for an objective satisfying a PL condition, the LDP upper bound
always holds, simply since $\mu>0$, cf. Lemma 3.1.

### Bibliography

## References

  * [Aga+21] Alekh Agarwal, Sham M Kakade, Jason D Lee and Gaurav Mahajan  “On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift”  In _Journal of Machine Learning Research_ 22.98, 2021, pp. 1–76
  * [BJK23] Dragana Bajovic, Dusan Jakovetic and Soummya Kar  “Large deviations rates for stochastic gradient descent with strongly convex functions”  In _International Conference on Artificial Intelligence and Statistics_ , 2023, pp. 10095–10111
  * [Bot10] Léon Bottou  “Large-scale machine learning with stochastic gradient descent”  In _International Conference on Computational Statistics_ , 2010, pp. 177–186
  * [BR19] Jalaj Bhandari and Daniel Russo  “Global optimality guarantees for policy gradient methods”  In _arXiv preprint arXiv:1906.01786_ , 2019
  * [BV16] Alexandre Brébisson and Pascal Vincent  “An Exploration of Softmax Alternatives Belonging to the Spherical Loss Family”  In _International Conference on Learning Representations_ , 2016
  * [Cen+22] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei and Yuejie Chi  “Fast global convergence of natural policy gradient methods with entropy regularization”  In _Operations Research_ 70.4 INFORMS, 2022, pp. 2563–2578
  * [DPS12] Thomas Degris, Patrick M Pilarski and Richard S Sutton  “Model-free reinforcement learning with continuous action in practice”  In _IEEE American Control Conference_ , 2012, pp. 2177–2182
  * [DV76] Monroe D Donsker and S.R. Srinivasa Varadhan  “Asymptotic evaluation of certain Markov process expectations for large time—III”  In _Communications on pure and applied Mathematics_ 29.4 Wiley Online Library, 1976, pp. 389–461
  * [DW04] Paul Dupuis and Hui Wang  “Importance sampling, large deviations, and differential games”  In _Stochastics: An International Journal of Probability and Stochastic Processes_ 76.6 Taylor & Francis, 2004, pp. 481–508
  * [DZ09] Amir Dembo and Ofer Zeitouni  “Large Deviations Techniques and Applications”  Springer, 2009
  * [DZL21] Yuhao Ding, Junzi Zhang and Javad Lavaei  “Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization”  In _arXiv preprint
arXiv:2110.10117_, 2021

  * [Ell84] Richard S Ellis  “Large deviations for a general class of random vectors”  In _The Annals of Probability_ 12.1 Institute of Mathematical Statistics, 1984, pp. 1–12
  * [Faz+18] Maryam Fazel, Rong Ge, Sham Kakade and Mehran Mesbahi  “Global convergence of policy gradient methods for the linear quadratic regulator”  In _International Conference on Machine Learning_ , 2018, pp. 1467–1476
  * [FMP08] Jordan Frank, Shie Mannor and Doina Precup  “Reinforcement learning in the presence of rare events”  In _International Conference on Machine Learning_ , 2008, pp. 336–343
  * [Gär77] Jürgen Gärtner  “On large deviations from the invariant measure”  In _Theory of Probability & Its Applications_ 22.1 SIAM, 1977, pp. 24–39
  * [GL13] Saeed Ghadimi and Guanghui Lan  “Stochastic first-and zeroth-order methods for nonconvex stochastic programming”  In _SIAM Journal on Optimization_ 23.4 SIAM, 2013, pp. 2341–2368
  * [Gow+20] Robert M Gower, Mark Schmidt, Francis Bach and Peter Richtárik  “Variance-reduced methods for machine learning”  In _Proceedings of the IEEE_ 108.11 IEEE, 2020, pp. 1968–1983
  * [Har+19] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan and Sikander Randhawa  “Tight analyses for non-smooth stochastic gradient descent”  In _Conference on Learning Theory_ , 2019, pp. 1579–1613
  * [Hen+20] Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei, Rémi Munos, Julien Perolat, Marc Lanctot, Audrunas Gruslys, Jean-Baptiste Lespiau, Paavo Parmas and Edgar Duéñez-Guzmán  “Neural replicator dynamics: Multiagent learning via hedging policy gradients”  In _International Conference on Autonomous Agents and Multiagent Systems_ , 2020, pp. 492–501
  * [Jin+19] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade and Michael I Jordan  “A short note on concentration inequalities for random vectors with subGaussian norm”  In _arXiv preprint arXiv:1902.03736_ , 2019
  * [KNS16] Hamed Karimi, Julie Nutini and Mark Schmidt  “Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition”  In _European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2016, pp. 795–811
  * [Lah23] Thibault Lahire  “Importance Sampling for Stochastic Gradient Descent in Deep Neural Networks”  In _arXiv preprint arXiv:2303.16529_ , 2023
  * [Lan23] Guanghui Lan  “Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes”  In _Mathematical Programming_ 198.1 Springer, 2023, pp. 1059–1106
  * [Li+21] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu and Yuxin Chen  “Softmax policy gradient methods can take exponential time to converge”  In _Conference on Learning Theory_ , 2021, pp. 3107–3110
  * [Liu+23] Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene and Huy Lê Nguyen  “High Probability Convergence of Stochastic Gradient Methods”  In _arXiv preprint arXiv:2302.14843_ , 2023
  * [MDB20] Liam Madden, Emiliano Dall’Anese and Stephen Becker  “High-probability Convergence Bounds for Non-convex Stochastic Gradient Descent”  In _arXiv preprint arXiv:2006.05610_ , 2020
  * [Mei+20] Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári and Dale Schuurmans  “Escaping the gravitational pull of softmax”  In _Advances in Neural Information Processing Systems_ , 2020, pp. 21130–21140
  * [Mei+20a] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari and Dale Schuurmans  “On the global convergence rates of softmax policy gradient methods”  In _International Conference on Machine Learning_ , 2020, pp. 6820–6829
  * [Nac+17] Ofir Nachum, Mohammad Norouzi, Kelvin Xu and Dale Schuurmans  “Bridging the gap between value and policy based reinforcement learning”  In _Advances in neural information processing systems_ 30, 2017
  * [NJG17] Gergely Neu, Anders Jonsson and Vicenç Gómez  “A unified view of entropy-regularized Markov decision processes”  In _arXiv preprint arXiv:1705.07798_ , 2017
  * [RM51] Herbert Robbins and Sutton Monro  “A Stochastic Approximation Method”  In _The Annals of Mathematical Statistics_ 22.3 Institute of Mathematical Statistics, 1951, pp. 400 –407
  * [SB18] Richard S Sutton and Andrew G Barto  “Reinforcement Learning: An Introduction”  MIT press, 2018
  * [Sut+99] Richard S Sutton, David McAllester, Satinder Singh and Yishay Mansour  “Policy gradient methods for reinforcement learning with function approximation”  In _Advances in Neural Information Processing Systems_ , 1999, pp. 1057–1063
  * [Var08] S.R. Srinivasa Varadhan  “Special invited paper: Large deviations”  In _The Annals of Probability_ 36.2, 2008, pp. 397–419
  * [Zha+20] Kaiqing Zhang, Alec Koppel, Hao Zhu and Tamer Basar  “Global convergence of policy gradient methods to (almost) locally optimal policies”  In _SIAM Journal on Control and Optimization_ 58.6 SIAM, 2020, pp. 3586–3612


spacing=nonfrench

# An Evaluation of WebAssembly and eBPF as Offloading Mechanisms
in the Context of Computational Storage

Wenjun Huang
German Aerospace Center
<EMAIL_ADDRESS>Marcus Paradies
German Aerospace Center
<EMAIL_ADDRESS>Corresponding author

###### Abstract

As the volume of data that needs to be processed continues to increase, we
also see renewed interests in near-data processing in the form of
computational storage, with eBPF (extended Berkeley Packet Filter) being
proposed as a vehicle for computation offloading. However, discussions in this
regard have so far ignored viable alternatives, and no convincing analysis has
been provided. As such, we qualitatively and quantitatively evaluated eBPF
against WebAssembly, a seemingly similar technology, in the context of
computation offloading. This report presents our findings.

##  1 Introduction

Lately, a data processing paradigm called “computational storage” has been
gaining traction. The idea behind it is to do “code shipping” and process data
within storage devices directly, thereby reducing data movement and energy
consumption [4].

While past research and commercial development in this direction have largely
focused on specialized, ad-hoc hardware or software that tries to eke out as
much performance as possible for specific types of workloads [41, 48, 54, 58],
lately we have observed some renewed interests in enabling general computation
offloading (i.e., user-programmable, dynamically loadable computation).

However, recent discussions in this direction [6, 35, 51] have focused almost
exclusively on using eBPF [9] as the offloading mechanism, ignoring other
platform-independent bytecodes. Naturally, we have some reservations about
this trend, as there has yet been a convincing analysis showing that eBPF is
the best option for the job.

In this work, we hope to initiate the conversation around general offloading
mechanisms by qualitatively and quantitatively evaluating eBPF and
WebAssembly. Specifically, we would like to pose and answer the following
questions:

  * •

What are the current states of the options?

  * •

What are the advantages and disadvantages of each of the options?

  * •

How can we improve these options with regards to computational storage (and
near-data processing in general)?

##  2 Background

In this section, we describe briefly the various topics and building blocks
relevant to our work.

Near-data processing [5, 36, 1] Near-data processing (NDP) puts computations
close to data to reduce data movement. It promises a number of benefits, such
as avoiding I/O bottlenecks. It can take various forms, including, but not
limited to, processing in-memory (PIM) and computational storage.

The idea of NDP is not new, and research about it can be dated back to at
least 2 decades ago. Nonetheless, we note that recently there has been a
resurgence of interests in NDP, both in academia and in industry (e.g., [45,
2]).

Computational Storage [4, 35] Strictly speaking, computational storage is a
special case of NDP that concerns only with processing data inside of storage
devices. However, in practice, computational storage is not always implemented
in storage (e.g., in the _computational storage array (CSA)_ architecture). In
that sense, _near-storage processing_ is perhaps a better name for it.

Storage devices that support this kind of data processing are called
_computational storage devices (CSDs)_ , and there are already a few generally
available CSDs on the market (e.g., [52, 50]). Moreover, there are some
ongoing standardization efforts as well (e.g., [35, 6]).

eBPF [9] eBPF is an umbrella term covering numerous pieces of technology that
enable running sandboxed programs inside the Linux kernel (i.e., “kernel
programming”), but we are specifically interested in the register-based eBPF
bytecode here. eBPF has a number of use cases, such as packet filtering and
system monitoring with minimal overhead. Consider the following possible
workflow: users can write an I/O tracer in C and compile it into eBPF bytecode
using clang, and the bytecode can then be loaded into the kernel using libbpf
[14].

While eBPF is primarily used in the context of kernel programming, efforts
have been made to enable running eBPF bytecode in a standalone fashion [53,
49, 34, 11]. However, to the best of our knowledge, there has yet been any
significant usage of eBPF for general-purpose computations.

WebAssembly [37, 26] WebAssembly is a portable, low-level bytecode format for
a stack-based VM. It is designed for secure and efficient execution in web
browsers, but recent research has shown that WebAssembly can still use some
improvements in terms of security and efficiency [39, 42].

To generate WebAssembly code, tooling exists for several languages (e.g., [17]
for Python and [10] for C/C++). To execute WebAssembly code outside of
browsers, one can use wasmtime, a VM with JIT and embedding support [55],
wasmer [23], a more customizable option than wasmtime, or GraalVM,111As of
v21.2, GraalVM’s WebAssembly support is still “experimental.” a VM with JIT
and language interop support [12]. To interface with certain system calls
(e.g., for I/O), WASI may be used [19].

##  3 Limitations

Before diving into the evaluation, we would like to address some potential
issues with our work.

Implementation Dependence Given that both eBPF and WebAssembly are just
bytecode formats at the core, any evaluation of them that goes beyond mere
theoretical analysis will inevitably be implementation-dependent. However, we
believe that such evaluations still have their value.

First, having an implementation-dependent analysis is better than having no
analysis at all. Second, from an engineering point of view, “what is
achievable today?” is just as important as “what is possible in the future?”
If a certain solution is rather lacking at the moment, the question of whether
we can justify the costs of improving it naturally arises. Finally, if the
analysis happens to reveal some potential improvements for the
implementations, then being implementation-dependent actually helps to “kill
two birds with one stone”.

Single Node We do not concern ourselves with offloading in a distributed
setting, as then the focus would lean towards scheduling and coordination,
which are out of the scope of this work.

Safety and not Security We will discuss the safety (i.e., protection against
human errors) afforded by the offloading mechanisms, but not their security
(i.e., protection against attacks), as we are not security experts.

That said, we speculate that securing a WebAssembly runtime is likely easier
than securing an eBPF runtime, as the former has some isolation features built
in (e.g., linear memory [37]), but the latter relies more heavily on load-time
verification [9], which not only is prone to false positives [34] but also has
had flaws discovered in the past (e.g. [46, 47]).

Moreover, WebAssembly has already undergone a significant amount of scrutiny
regarding its semantics and security [37, 42, 56, 57, 44, 43, 38], but the
same cannot yet be said of eBPF in the context of general-purpose
computations.

##  4 Qualitative Evaluation

In this section, we will present our findings on the usability (i.e., the user
experience) of the two offloading mechanisms. Specifically, we will compare
them along 6 axes: safety, tooling, compatibility, portability, ergonomics,
and language-agnostic-ity. A summary of the comparison is provided in Table 1
(* = poor, ** = ok, *** = good).

|  eBPF |  WebAssembly
---|---|---
safety |  ? |  ***
tooling |  ** |  ***
compatibility |  * |  **
portability |  ** |  ***
ergonomics |  ** |  **
language-agnostic-ity |  * |  **
Table 1: Evaluation summaries of the offloading mechanisms

###  4.1 Safety

As suggested above, we will not cover multi-tenant or public-facing usage
here, so we only consider safety in terms of programmer mistakes – “what’s the
worst that can happen if the offloads misbehave due to bugs in them”?

For WebAssembly, the safety is pretty good, as the offload code will run in an
isolated memory space [28, 37] and also has no access to the file system by
default [21]. Since these properties are specified at the design level, they
are not implementation-dependent. While it is possible for WebAssembly code to
hang or waste CPU cycles222For wasmtime [55] hanging can be avoided via the
“fuel” feature., it is rather unlikely for careless mistakes to wreck havoc
outside of the WebAssembly runtime.

For eBPF, the situation is mostly dependent on the verifier. The one used by
the Linux kernel is very strict, banning many kinds of loops and memory
accesses [15]. However, using that verifier (and kernel-oriented verifiers
[34] in general) for data processing is not very practical, and a new verifier
implementation is needed [40]. Therefore, we cannot yet say much about the
safety of eBPF as an offloading mechanism.

Nonetheless, we suspect that getting eBPF runtime safety right will be a
trickier task, as it relies on a specific verifier to catch undesirable
behaviors. In comparison, WebAssembly clearly specifies what is allowed at the
spec level.

###  4.2 Tooling

Development Tools For WebAssembly, a suite of tools called wabt (The
WebAssembly Binary Toolkit) is available for inspecting and transforming
WebAssembly binaries [25].

For eBPF, bpftool can be used to inspect eBPF programs and maps [33]. It also
has some features meant for in-kernel eBPF usage, such as loading programs and
updating maps. However, since bpftool is inherently tied to in-kernel usage,
eBPF programs cannot be inspected unless they are loaded or attached into the
kernel. For a standalone option, llvm-objdump is a better choice [16].

Virtual Machines As mentioned before, WebAssembly has at least three feature-
rich VM implementations: wasmtime [55], wasmer [23], and GraalVM [12]. While
they share some common features like JIT support for common architectures,
each offers a number of unique features as well. For wasmtime, as of v0.29:

  * •

profiling via perf and VTune

  * •

debugging via lldb and gdb

  * •

embedding in several host languages

  * •

async host functions

  * •

host functions from closures

  * •

traps and backtraces

  * •

custom memory allocator

  * •

stack and heap limits

  * •

caching of compiled binaries

  * •

controlled code execution via fuel credits

  * •

SIMD and threading

For wasmer, as of v2.0:

  * •

embedding in several host languages

  * •

ahead-of-time and cross compilation via LLVM

  * •

multiple ways of storing compiler output

  * •

dynamic and static functions

  * •

custom heap management via Tunables

  * •

errors and backtraces

  * •

custom import resolution via Resolver

  * •

support for many experimental features like SIMD

For GraalVM, as of v21.2:

  * •

interop & embedding for a dozen languages

  * •

access to mature JVM technologies

  * •

creating standalone native binaries (“native images”)

  * •

debugging via Chrome DevTools and more

  * •

built-in CPU & memory profilers

  * •

visualizing compilation graphs

eBPF, on the other hand, still has a long way to go in this department. Both
uBPF [53] and rBPF [49] have JIT support (x86_64 only), but they are still
rather lacking when it comes to features like profiling and debugging, which
is not surprising, as they are not meant for in-production usage. In fact, the
README of rBPF clearly states that:

  * •

several features of the kernel eBPF implementation are not yet available
(e.g., tail calls)

  * •

it has a very simple verifier, so safety cannot be guaranteed

  * •

the JIT compiler does not emit run-time memory checks, so crashes are possible

  * •

a small number of eBPF instructions are not yet implemented

  * •

uBPF is mostly the same, so the above points likely hold for uBPF as well

###  4.3 Compatibility

Compatibility here refers to the users’ ability to re-use existing libraries
in the ecosystem. Any external dependency, including libc, must be re-compiled
and statically linked. For WebAssembly, this means that the wasi-sdk [22] is
likely needed for compilation. For example, to build zstd [32]:

⬇

CXX="wasi-sdk/bin/clang++" \

CC="wasi-sdk/bin/clang" \

AR="wasi-sdk/bin/ar" \

CFLAGS="--sysroot=wasi-sdk/share/wasi-sysroot" \

$(MAKE) -C zstd/lib libzstd.a

For eBPF, building zstd would fail, as libc is not available in the absence of
a WASI equivalent:

⬇

CXX="clang++" CC="clang" CFLAGS="-target bpf -Wall -Werror -O2" make -C
zstd/lib libzstd.a

make: Entering directory ’zstd/lib’

CC obj/conf_01069ccb7af67d6f99eda2da05bd0468/static/debug.o

CC obj/conf_01069ccb7af67d6f99eda2da05bd0468/static/entropy_common.o

In file included from common/entropy_common.c:18:

In file included from common/mem.h:24:

In file included from common/zstd_deps.h:27:

In file included from /usr/lib/llvm-12/lib/clang/12.0.0/include/limits.h:21:

/usr/include/limits.h:26:10: fatal error: ’bits/libc-header-start.h’ file not
found

#include <bits/libc-header-start.h>

^~~~~~~~~~~~~~~~~~~~~~~~~~

1 error generated.

make[1]: *** [Makefile:344:
obj/conf_01069ccb7af67d6f99eda2da05bd0468/static/entropy_common.o] Error 1

make: *** [Makefile:240: libzstd.a] Error 2

make: Leaving directory ’zstd/lib’

Without access to libc, a huge swath of existing libraries would be unusable,
so the compatibility of eBPF is quite poor. Additionally, clang -target bpf,
as of v12.0.1, also does not support several kinds of numeric operations. For
example, i64 divisions:

⬇

Error: Unsupport signed division for DAG: 0x556059b1c260: i64 = sdiv
0x556059b1ef90, 0x556059b1bf20Please convert to unsigned div/mod.

fatal error: error in backend: Cannot select: 0x556059b1c260: i64 = sdiv
0x556059b1ef90, 0x556059b1bf20

0x556059b1ef90: i64 = add 0x556059b1ef28, Constant:i64<2>

0x556059b1ef28: i64 = add 0x556059b1bbe0, 0x556059b1bd18

0x556059b1bbe0: i64 = mul 0x556059b1bc48, Constant:i64<7>

0x556059b1bc48: i64 = mul 0x556059b1beb8, 0x556059b1bff0

0x556059b1beb8: i64,ch = CopyFromReg 0x556059a67458, Register:i64 %3

0x556059b1bf88: i64 = Register %3

0x556059b1bff0: i64,ch = CopyFromReg 0x556059a67458, Register:i64 %7

0x556059b1c0c0: i64 = Register %7

0x556059b1b7d0: i64 = Constant<7>

0x556059b1bd18: i64 = mul nsw 0x556059b1bb10, 0x556059b1ba40

0x556059b1bb10: i64,ch = CopyFromReg 0x556059a67458, Register:i64 %5

0x556059b1b700: i64 = Register %5

0x556059b1ba40: i64,ch = CopyFromReg 0x556059a67458, Register:i64 %8

0x556059b1bcb0: i64 = Register %8

0x556059b1b8a0: i64 = Constant<2>

0x556059b1bf20: i64 = mul nsw 0x556059b1bb10, 0x556059b1be50

0x556059b1bb10: i64,ch = CopyFromReg 0x556059a67458, Register:i64 %5

0x556059b1b700: i64 = Register %5

0x556059b1be50: i64,ch = CopyFromReg 0x556059a67458, Register:i64 %2

0x556059b1bde8: i64 = Register %2

and floating point operations (passing -fno-builtin did not help here):

⬇

4-pi.c:1:8: error: A call to built-in function ’__muldf3’ is not supported.

double pi_digit(unsigned long n_th) {

^

4-pi.c:1:8: error: A call to built-in function ’__adddf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__subdf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__muldf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__ltdf2’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__adddf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__adddf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__muldf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__muldf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__adddf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__muldf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__muldf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__adddf3’ is not supported.

4-pi.c:1:8: error: A call to built-in function ’__adddf3’ is not supported.

The lack of support for these operations is not due to clang. Rather, the
issue stems from the fact that eBPF lacks the appropriate instructions for
clang to emit [15, 13]. As such, we do not see how these operations can be
used by eBPF offload programs unless eBPF is given significant extensions.

Of course, the compatibility of WebAssembly is not perfect either – since WASI
does not yet provide functions like fork() and pthread_*() [20], certain
existing libraries would not build (e.g., the multi-threaded version of zstd),
but the situation is arguably better than eBPF.333Furthermore, as WebAssembly
gains more traction, we expect to see more libraries providing official
WebAssembly support. TensorFlow would be one example. For now, the same cannot
be said of eBPF.

###  4.4 Portability

Since eBPF and WebAssembly are bytecodes designed to be executed by virtual
machines, they both have decent portability in theory (i.e., users can compile
their code once and reuse the built binaries everywhere).

However, in practice, eBPF is at a slight disadvantage on this front because
it is not endianness-independent. The LLVM static compiler llc 12.0.1 gives:

⬇

Registered Targets:

...

bpf - BPF (host endian)

bpfeb - BPF (big endian)

bpfel - BPF (little endian)

...

wasm32 - WebAssembly 32-bit

wasm64 - WebAssembly 64-bit

...

For many use cases, the host endianness is not that relevant, as they do not
involve parsing and interpreting data at the byte level. However, this
“parsing” task is arguably quite common during data processing (e.g., reading
numbers out of a file to perform calculations), so eBPF’s endianness-
dependence will likely affect the portability of many offload binaries.

For WebAssembly, little-endianness is always used [26], and it is up to the
runtime to handle the conversion if the host architecture is big-endian [30],
so there is no endianness-related portability concern.444This should not be a
performance concern either, as modern architectures often provide instructions
for handling endianness (e.g., MOVBE from x86). Moreover, the difference
between wasm32 and wasm64 is mostly about the largest memory size supported
[24], which can be transparently handled by the runtime and hence should not
lead to any difference in program behavior.

###  4.5 Ergonomics

For this section, we will take a look at the development processes of the two
offloading mechanisms and see if they are easy and straightforward.

####  4.5.1 Compilation

WebAssembly  As mentioned before, it is possible to generate WebAssembly code
from several source languages. To have a direct comparison with eBPF, we will
focus on C here. From C code, there are at least 2 ways to compile to
WebAssembly with libc support: Emscripten [10] and wasi-sdk [22]. With
Emscripten:

⬇

emcc \

-Wall -O3 -flto \

\--no-entry -Wl,--export-all \

-o code.wasm code.c

With wasi-sdk:

⬇

wasi-sdk/bin/clang \

\--sysroot=wasi-sdk/share/wasi-sysroot \

-Wall -O3 -flto -nostartfiles \

-Wl,--no-entry -Wl,--export-all \

-o code.wasm code.c

-flto enables link-time optimization (LTO), -nostartfiles disables the system libc, -Wl,--no-entry allows the absence of main(), and -Wl,--export-all makes sure that all functions, including unused ones, are emitted.

After compilation, wasm-opt from the binaryen toolchain [8] may be used to
further reduce code size: wasm-opt -Oz code.wasm -o code.wasm.

eBPF  For eBPF, both of the two mainstream compilers, gcc and clang, may be
used. We will stick with clang here since it is the more popular and mature
option: clang -target bpf -Wall -O2 -o code.o -c code.c

Compiling to eBPF appears to be much simpler than compiling to WebAssembly.
However, if we are actually compiling for in-kernel usage, then some
additional -I flags are likely needed to access kernel types.

####  4.5.2 Bytecode Inspection

WebAssembly  A tool called wasm2wat is included in wabt [25] for the purpose
of converting WebAssembly binaries to an official, human-readable text
format555wasmtime supports executing this text format directly. [31]. Here is
an example of this text format:

⬇

(module

(func (export "addTwo") (param i32 i32) (result i32)

local.get 0

local.get 1

i32.add))

One can also disassemble WebAssembly binaries using wasm-objdump:

⬇

wasm-objdump add_one.wasm

add_one.wasm: file format wasm 0x1

Code Disassembly:

0001bc func[0] <__wasm_call_ctors>:

0001bd: 01 | nop

0001be: 0b | end

0001c0 func[1] <malloc>:

0001c1: 20 00 | local.get 0

0001c3: 10 02 | call 2

0001c5: 0b | end

0001c8 func[2]:

0001c9: 0b 7f | local[0..10] type=i32

0001cb: 23 00 | global.get 0

0001cd: 41 10 | i32.const 16

0001cf: 6b | i32.sub

0001d0: 22 0a | local.tee 10

0001d2: 24 00 | global.set 0

0001d4: 02 40 | block

0001d6: 41 a0 08 | i32.const 1056

eBPF  Although eBPF does not yet have an official textual format,666Both rBPF
and uBPF provide (dis)assemblers for a textual assembly format, but it is not
an official format. if the eBPF binary of interest was compiled with debugging
information, it is possible to view the disassembled binary with interleaved
source code:

⬇

llvm-objdump -S \--no-show-raw-insn bpf.o

bpf.o: file format elf64-bpf

Disassembly of section fentry/blk_account_io_start:

0000000000000000 <blk_account_io_start>:

; int BPF_PROG(blk_account_io_start, struct request *req)

0: r8 = *(u64 *)(r1 + 0)

1: *(u64 *)(r10 - 8) = r8

2: r1 = 0

; struct req_info info = { 0 };

3: *(u64 *)(r10 - 16) = r1

4: *(u64 *)(r10 - 24) = r1

5: *(u64 *)(r10 - 32) = r1

6: *(u64 *)(r10 - 40) = r1

7: *(u64 *)(r10 - 48) = r1

8: *(u64 *)(r10 - 56) = r1

9: *(u64 *)(r10 - 64) = r1

10: *(u64 *)(r10 - 72) = r1

11: *(u64 *)(r10 - 80) = r1

12: *(u64 *)(r10 - 88) = r1

13: *(u64 *)(r10 - 96) = r1

14: *(u64 *)(r10 - 104) = r1

15: *(u64 *)(r10 - 112) = r1

16: *(u64 *)(r10 - 120) = r1

17: *(u64 *)(r10 - 128) = r1

18: *(u64 *)(r10 - 136) = r1

; u64 t = bpf_ktime_get_ns();

19: call 5

20: r6 = r0

###  4.6 Language-agnostic-ity

For WebAssembly, a variety of source languages can be used in theory [26].
However, in reality, the source language has to support exporting malloc(),
which is needed to allocate WebAssembly buffers and pass data between the host
and the WebAssembly VM. That said, this situation will change when the “module
linking” feature is stabilized [29], as then it will be possible for the host
to link needed functions, and more source languages may be used.

For eBPF, the only supported source language at the moment is C. While it is
possible to use other source languages in theory [7], significant efforts are
required from the user.

##  5 Quantitative Evaluation

In this section, we will describe how we evaluated the performance of the two
offloading mechanisms. We will also present the evaluation results.

###  5.1 Setup

The evaluation was carried out on two platforms, an AMD workstation (Ryzen
Threadripper Pro 3975WX [3] (x64), 128 GiB of RDIMM DDR4 ECC DRAM (3200 MHz),
Linux kernel 5.13.13) and an AWS c6g.xlarge instance (4 vCPU from AWS
Graviton2 (arm64), 8 GiB DRAM, Linux kernel 5.11.0) and for the configurations
as summarized in Table 2.

VM |  wasmtime v0.29.0 [55]
---|---
wasmer v2.0.0 [23]
GraalVM v21.2.0 [12]
rBPF @ 6c524b3 [49]
uBPF @ 9eb26b4 [53]
toolchain |  llvm / clang 12.0.1 (WX) & 12.0.0 (AWS)
wabt 1.0.24 (WX) & 1.0.20 (AWS) [25]
rustc 1.57.0-nightly (e30b68353 2021-09-05)
Table 2: Evaluation configurations

Since there is currently no libc support for eBPF, our evaluation consisted
only of simple arithmetic programs that are written in C:

  * •

a baseline dummy program that simply returns 1

  * •

fibonacci calculation

  * •

integer summing

  * •

Erdős prime counting

  * •

multi-factorial calculation

For our evaluation, clang -Oz was used to compile to all targets,777Of course,
there were additional flags involved. Please check the Makefiles in the repo.
and wasm-opt was used to further optimize WebAssembly binaries after clang
finishes. Moreover, the following VM configurations were evaluated:

  * •

graal: for running WASM binaries on GraalVM via a native image

  * •

rbpf: for running patched (see next section) eBPF binaries on rBPF

  * •

ubpf: for running patched (see next section) eBPF binaries on uBPF

  * •

wasmer: for running WASM binaries on wasmer

  * •

wasmtime: for running WASM binaries on wasmtime

  * •

wasmtime_cached: like wasmtime but with caching enabled

In addition to the WebAssembly VMs and the eBPF VMs, the native binaries were
also benchmarked888The native binaries were loaded using dlopen() and the
functions were invoked via dlsym(), so that the native binaries were used in a
way that is similar to how eBPF and WebAssembly binaries were used. so that
they may serve as a baseline. The performance metrics shown below were
collected using our own scripts and GNU time v1.9 [18] over 10 consecutive
runs.

Note that, since rBPF and uBPF do not currently provide JIT implementations
for arm64, we did not evaluate them on that architecture. The same applies for
wasmer, which was not able to compile the WebAssembly code on arm64 due to
LLVM errors. Thus, the tables below will show “NA” for the relevant cells.

###  5.2 Patching eBPF Binaries

eBPF programs cannot allocate memory (either statically or dynamically) or
call non-helper functions (i.e., functions that are not registered with the
VM). To make things work,999In our case, that means to have some support for
function calls and static memory. the binaries produced directly by clang had
to be disassembled and manually patched for our evaluation:101010See our
repository for more information and examples.

  1. 1.

in the original code file, add a pointer parameter to all functions that need
external memory, which shall be accessed through the said pointer

  2. 2.

compile the code file and disassemble the binary file produced

  3. 3.

create a plaintext file

  4. 4.

put the expected output of the program on the first line; this should be a u64
integer

  5. 5.

put the size of the needed static memory on the second line; this should be in
unit of bytes and can be 0

  6. 6.

paste the disassembled code after the second line, with the entry point pasted
first and all other functions pasted afterwards

  7. 7.

replace all call instructions and all exit instructions of the callees with ja
instructions to simulate function calls

  8. 8.

the address of the external memory will be placed in register r1, so make sure
you do not mess with r1 at the beginning

  9. 9.

make sure the file ends with an exit instruction

We will also surmise that it is unlikely for this patching process to be
automated post-compilation, as clang currently emits all eBPF function calls
as call -1, making it impossible to stitch assembly blocks together without
source information.

program |  VM |  rel. avg. max RSS |  rel. avg. latencies |  rel. avg. times |  rel. avg. times
---|---|---|---|---|---
dummy |  wasmtime |  3.85 |  92.0 |  4.37 |  2.71
wasmtime_cached |  3.52 |  80.6 |  4.25 |  2.59
graal |  10.4 |  25.5 |  20.4 |  2.87
wasmer |  16.0 |  267.0 |  4.63 |  7.31
rbpf |  1.11 |  1.59 |  0.0972 |  0.852
ubpf |  1.10 |  3.23 |  0.0887 |  1.11
fibonacci |  wasmtime |  3.85 |  94.0 |  3.77 |  2.89
wasmtime_cached |  3.52 |  79.2 |  4.10 |  2.62
graal |  10.4 |  27.9 |  34.1 |  3.22
wasmer |  16.8 |  283.0 |  3.82 |  8.00
rbpf |  1.09 |  2.53 |  0.185 |  0.962
ubpf |  1.11 |  3.83 |  0.160 |  1.07
integer summing |  wasmtime |  3.82 |  79.7 |  1.99 |  2.17
wasmtime_cached |  3.48 |  64.5 |  1.99 |  2.10
graal |  21.4 |  18.7 |  12.5 |  10.6
wasmer |  16.6 |  223.0 |  1.06 |  2.35
rbpf |  1.09 |  2.26 |  2.22 |  1.97
ubpf |  1.09 |  2.97 |  1.98 |  1.79
prime counting |  wasmtime |  2.81 |  77.7 |  0.969 |  1.55
wasmtime_cached |  2.48 |  58.8 |  0.978 |  1.43
graal |  39.1 |  26.1 |  36.8 |  27.2
wasmer |  12.3 |  297.0 |  0.814 |  3.34
rbpf |  1.02 |  4.73 |  0.907 |  0.935
ubpf |  1.05 |  6.71 |  0.942 |  0.999
multi-factorial |  wasmtime |  3.80 |  78.7 |  3.55 |  2.58
wasmtime_cached |  3.47 |  68.6 |  3.32 |  2.45
graal |  10.2 |  22.8 |  27.1 |  2.91
wasmer |  16.2 |  238.0 |  3.93 |  7.30
rbpf |  1.08 |  2.12 |  0.171 |  0.997
ubpf |  1.07 |  3.14 |  0.140 |  1.03
Table 3: Evaluation results for all (program,VM) combinations from the AMD workstation. Col. 3: max resident set sizes (bytes). Col. 4: startup latencies (ms). Col. 5: execution times (ms). Col. 6: total running times (ms). All values are 10-run averages and are relative to those of native binaries (= 1). program |  VM |  rel. avg. max RSS |  rel. avg. latencies |  rel. avg. times |  rel. avg. times
---|---|---|---|---|---
dummy |  wasmtime |  3.58 |  48.3 |  51.6 |  1.84
wasmtime_cached |  3.28 |  29.2 |  63.1 |  1.65
graal |  13.8 |  40.4 |  233.0 |  3.60
wasmer |  NA |  NA |  NA |  NA
rbpf |  NA |  NA |  NA |  NA
ubpf |  NA |  NA |  NA |  NA
fibonacci |  wasmtime |  3.61 |  39.1 |  27.8 |  1.80
wasmtime_cached |  3.28 |  24.9 |  31.1 |  1.63
graal |  13.8 |  34.7 |  241.0 |  3.58
wasmer |  NA |  NA |  NA |  NA
rbpf |  NA |  NA |  NA |  NA
ubpf |  NA |  NA |  NA |  NA
integer summing |  wasmtime |  3.53 |  39.8 |  1.24 |  1.30
wasmtime_cached |  7.84 |  26.4 |  1.24 |  1.31
graal |  28.2 |  37.1 |  11.5 |  10.7
wasmer |  NA |  NA |  NA |  NA
rbpf |  NA |  NA |  NA |  NA
ubpf |  NA |  NA |  NA |  NA
prime counting |  wasmtime |  2.33 |  49.2 |  1.27 |  1.47
wasmtime_cached |  3.44 |  23.6 |  1.27 |  1.40
graal |  48.0 |  45.3 |  48.1 |  38.1
wasmer |  NA |  NA |  NA |  NA
rbpf |  NA |  NA |  NA |  NA
ubpf |  NA |  NA |  NA |  NA
multi-factorial |  wasmtime |  3.55 |  38.1 |  32.3 |  1.80
wasmtime_cached |  3.24 |  23.7 |  37.2 |  1.67
graal |  13.7 |  34.1 |  243.0 |  3.57
wasmer |  NA |  NA |  NA |  NA
rbpf |  NA |  NA |  NA |  NA
ubpf |  NA |  NA |  NA |  NA
Table 4: Evaluation results for all (program,VM) combinations from AWS
c6g.xlarge. Col. 3: max resident set sizes (bytes). Col. 4: startup latencies
(ms). Col. 5: execution times (ms). Col. 6: total running times (ms). All
values are 10-run averages and are relative to those of native binaries (= 1).
NA is shown for failed configurations.

###  5.3 Runtime Memory Footprint

As the environments for computational storage and near-data processing tend to
be resource-constrained, the memory footprints of the VMs are naturally of
interest here.111111It is worth noting that neither WebAssembly nor eBPF has
GC at the moment. For the former, a GC proposal is in early-stage development
[27], and the current approach to reclaim resources is to use short-lived,
one-off execution contexts, which admittedly are inadequate for long-running
programs. For the latter, since in-kernel usage does not support libc and
therefore memory allocation, how memory management will be handled in a data
processing context is yet to be seen. Thus, we measured the memory usage of
the VMs for each of the programs mentioned before.

Figure 1: 10-run averages of max resident set sizes (bytes) of all
(program,VM) combinations, absolute values Figure 2: max resident set sizes
(bytes) of all (program,VM) combinations, absolute values in log10 scale

From Tables 3 and 4 (column 3) and Figures 1 and 2, we can see that on x64
rBPF and uBPF were able to achieve near-native performance when it comes to
max resident set sizes (RSS). Next comes wasmtime, whose max RSS values were
3$\sim$4 times those of native binaries on both architectures.

The much higher max RSS values of wasmer on x64 were likely due to its usage
of LLVM for ahead-of-time compilation (AOT). As for GraalVM native images, we
do not have sufficient knowledge of their inner workings to comment, but we
speculate that its support for language interop would require a heavier
runtime, which might have contributed to the high max RSS values.

From Figure 2, we can see that the max RSS values were fairly consistent
across runs, even though a few outliers do exist. However, it is worth noting
that max RSS values are max values – the VMs most likely do not need this much
memory for their entire lifetimes.

###  5.4 Runtime Startup Latency

Generally, runtime startup latencies do not matter, as they are one-off costs
that can be amortized by the execution times of the offload code. However, in
certain cases, offload code might have to be repeatedly invoked (e.g., on a
series of small files/objects), and significant runtime startup latencies can
be quite undesirable or even unacceptable in these situations. Thus, we will
also take a look at the startup latencies of the VMs when running our test
programs.

To get the startup latencies, we would record $t_{0}$, the time when runtime
setup starts, and $t_{1}$, the time when the test program can be executed, and
calculate $t_{1}-t_{0}$. Note that this value also includes the JIT/AOT
overhead. Fortunately, this process is not that complicated, as all VMs’ APIs
clearly differentiate between runtime setup calls and code execution calls.

Figure 3: 10-run averages of startup latencies (ms) of all (program,VM)
combinations, absolute values Figure 4: startup latencies (ms) of all
(program,VM) combinations, absolute values in log10 scale

From Tables 3 and 4 (column 4) and Figures 3 and 4, we can see some quite
dramatic variations in the startup latencies of different VMs. As discussed
before, rBPF and uBPF are a bit lacking in terms of their features, which
means they are likely more lightweight than the competition, so it is not
surprising that they were able to perform well in this category. On the other
hand, wasmer was once again bogged down by the expensive AOT compilation step,
making it the worst performer in this category.

That said, if one pays attention to the scale of the y-axis in Figure 3, which
shows absolute values, then one would notice that the startup latencies are
all quite small – on both architectures, they are mostly under 3 ms. As such,
they should not become a performance concern in general.

###  5.5 Execution Speed

In this section, we present the execution times of the aforementioned programs
on different VMs. Here, execution time refers to the amount of time spent on
actual computation (i.e., from calling the test program’s entry point function
to receiving its return value).

Figure 5: 10-run averages of execution times (ms) of all (program,VM)
combinations, absolute values Figure 6: Execution times (ms) of all
(program,VM) combinations, absolute values in log10 scale

The results can be found in column 5 of Tables 3 and 4 and in Figures 5 and 6.
For the execution times of the actual computation, the programs can be divided
into 2 groups for discussion: (dummy, fibonacci, multi_factorial),
(erdos_prime, and summing).

The first group is relatively light on computation – their bars are not even
visible in Figure 5. For these programs, rBPF and uBPF performed so well that,
amusingly, they were able to beat the native binaries by some margin. But
since these programs finished so quickly, it is not clear if we can draw any
meaningful conclusion here.

The second group of programs, due to their significant usage of loops and/or
memory accesses, are more intensive and can arguably put the VMs to test a
little bit. For these programs, wasmer’s high peak memory usage and startup
latencies finally paid off, as it ended up getting the best performance for
erdos_prime and summing on x64, excluding the native binaries in the latter
case. Otherwise, wasmtime’s performance was similar to that of rBPF and uBPF.

There are also two more points worth mentioning. First, on x64, the native
binary for erdos_prime performed rather poorly, as it got outperformed by all
VMs except GraalVM. Since erdos_prime is heavy on memory accesses, one might
speculate that the VMs somehow emitted more efficient machine code in this
regard. Second, GraalVM’s performance was pretty poor across the board, which
was, again, likely due to the weight of its language interop infrastructure.

###  5.6 Total Time

In this section, we present the total running times of the aforementioned
programs on different VMs. The total running time of a test program goes from
when the VM process is spawned to when the VM process exits. Thus, it can
include the time taken by the OS to perform symbol resolution and relocation,
spawn the process, etc., thereby also reflecting the weightiness of the VMs a
bit.

Given that we collected the data in a Python script, on top of GNU time, the
exact values might be slightly off, but since we only report the relative
values in the tables above, the skew should be consistent and thus irrelevant.
The results can be found in column 6 of Tables 3 and 4 and in Figures 7 and 8.

Figure 7: 10-run averages of total running times (ms) of all (program,VM)
combinations, absolute values Figure 8: Total running times (ms) of all
(program,VM) combinations, absolute values in log10 scale

Taking everything into account, rBPF and uBPF come on top once again on x64,
often beating the native binaries. After them comes wasmtime, whose total
times are still close to those of the native binaries, especially on the arm64
AWS instance. Enabling caching for wasmtime certainly helps with the total
times, but the margin is not dramatic by any means.121212This will of course
change as the code complexity increases. The AOT cost of wasmer cannot yet be
fully amortized on small programs like ours, but its numbers for erdos_prime
and summing are not that far behind wasmtime’s, so we believe it has great
potentials. As for GraalVM, once there is substantial operation involved, it
is a bit too slow to compete with the other options, so unless language
interop or the Java ecosystem is indispensable, we do not see why it should be
used for running WebAssembly programs.131313But to be fair, WebAssembly is
marked as an experimental feature of GraalVM.

###  5.7 Binary Sizes

The sizes of the compiled binaries can be of interest too, as over time, they
can have quite some impact on the efficiency of code transmission. The binary
sizes of our test programs can be found in Table 5 and Figure 9.

|  x64 |  arm64 |  eBPF |  patched eBPF |  wasm
---|---|---|---|---|---
dummy |  $13\,440$ |  5936 |  624 |  23 |  318
fibo-nacci |  13728 |  6152 |  920 |  238 |  354
sum-ming |  13728 |  6160 |  904 |  212 |  339
prime |  13960 |  6456 |  1856 |  1398 |  639
multi-fact |  13736 |  6160 |  856 |  148 |  344
Table 5: Binary sizes (bytes) Figure 9: Binary sizes (bytes)

The native binaries consistently have the largest sizes due to their inclusion
of much metadata information (e.g., the .symtab, or symbol table, section),
whereas the WebAssembly binaries consistently have the smallest sizes, if we
ignore “patched eBPF” for a second.

Patched eBPF “binaries” are a bit special. As discussed before, these have to
be manually created by a human at the moment, and they are stored as
plaintext, so they are not really compiled binaries in some sense.
Nevertheless, if we take them into consideration as well, then they are indeed
the smallest except for the erdos_prime program.

However, since erdos_prime also happens to be the most complicated among the
programs, we would argue that, as program complexity increases, WebAssembly
will likely be the winner in terms of binary sizes.

##  6 Discussion

While the eBPF VMs had a slight edge in our quantitative evaluation, the
amount of restrictions and extra efforts that eBPF currently imposes on its
users suggests that it is not yet ready to support data processing and
general-purpose computation. For that, WebAssembly seems to be a more sensible
choice, and it is ready for deployment. Below, we will propose some potential
improvements for both technologies.

WebAssembly  Being a fairly mature technology, WebAssembly and its
implementations can still use some improvements in these directions:

  * •

stabilize and finish implementing the SIMD and threading proposals

  * •

provide an interface for (preferably zero-copy) sharing of host data

  * •

address the security concerns pointed out by researchers (e.g. [42])

eBPF  Following the evaluation in the previous sections, it is our opinion
that eBPF still needs a lot of work before it can become a suitable vehicle
for data processing:

  * •

a mature VM, with support for things like debugging and profiling

  * •

an extended instruction set to support all common numeric operations (e.g.,
signed divisions)

  * •

a specification that clearly defines permitted operations

  * •

a reliable verifier developed in tandem with the specification

  * •

implementation of libc and other system services

  * •

undergo thorough security evaluations in the context of data processing

##  7 Conclusion

In this work, we have evaluated two mechanisms for the purpose of enabling
general computation offloading in the context of near-data processing –
WebAssembly and eBPF. From our point of view, we believe that WebAssembly is a
better choice for the job, but we welcome differing opinions, and we hope more
discussions in these directions will ensue.

## Acknowledgments

This project has received funding from the European Union’s Horizon 2020
research and innovation program under grant agreement No 957407.

## References

  * [1] Anurag Acharya, Mustafa Uysal, and Joel Saltz.  Active disks: Programming model, algorithms and evaluation.  ACM SIGOPS Operating Systems Review, 32(5):81–91, 1998.
  * [2] Paul Alcorn.  Samsung’s New HBM2 Memory Has 1.2 TFLOPS of Embedded Processing Power.  https://www.tomshardware.com/news/samsung-hbm2-hbm-pim-memory-tflops.
  * [3] AMD.  Ryzen Threadripper PRO 3975WX.  https://www.amd.com/en/products/cpu/amd-ryzen-threadripper-pro-3975wx.
  * [4] Antonio Barbalace and Jaeyoung Do.  Computational storage: Where are we today?  In CIDR, 2021.
  * [5] Antonio Barbalace, Anthony Iliopoulos, Holm Rauchfuss, and Goetz Brasche.  It’s time to think about an operating system for near data processing architectures.  In Proceedings of the 16th Workshop on Hot Topics in Operating Systems, pages 56–61, 2017.
  * [6] NVMe Computational Storage Task Group Co-Chairs.  Bringing Compute to Storage with NVM Express.  https://nvmexpress.org/bringing-compute-to-storage-with-nvm-express/.
  * [7] Geoffroy Couprie.  Poc: compiling to eBPF from Rust.  http://unhandledexpression.com/general/rust/2018/02/02/poc-compiling-to-ebpf-from-rust.html.
  * [8] binaryen developers.  binaryen.  https://github.com/WebAssembly/binaryen.
  * [9] eBPF developers.  eBPF.  https://ebpf.io.
  * [10] Emscripten developers.  Emscripten.  https://github.com/emscripten-core/emscripten.
  * [11] generic-ebpf developers.  generic-ebpf.  https://github.com/generic-ebpf/generic-ebpf.
  * [12] GraalVM developers.  GraalVM.  https://www.graalvm.org.
  * [13] IO Visor Project developers.  Unofficial eBPF spec.  https://github.com/iovisor/bpf-docs/blob/master/eBPF.md.
  * [14] libbpf developers.  libbpf.  https://github.com/libbpf/libbpf.
  * [15] Linux developers.  Linux Socket Filtering aka Berkeley Packet Filter (BPF).  https://www.kernel.org/doc/Documentation/networking/filter.txt.
  * [16] LLVM developers.  llvm-objdump.  https://llvm.org/docs/CommandGuide/llvm-objdump.html.
  * [17] RustPython developers.  RustPython.  https://github.com/RustPython/RustPython/.
  * [18] time developers.  GNU time.  https://www.gnu.org/software/time/.
  * [19] WASI developers.  WASI.  https://wasi.dev.
  * [20] WASI developers.  Wasi API Documentation.  https://github.com/WebAssembly/WASI/blob/main/phases/snapshot/docs.md.
  * [21] WASI developers.  Wasi Design Principles.  https://github.com/WebAssembly/WASI/blob/main/docs/DesignPrinciples.md.
  * [22] wask-sdk developers.  wasi-sdk.  https://github.com/WebAssembly/wasi-sdk.
  * [23] wasmer developers.  wasmer.  https://github.com/wasmerio/wasmer.
  * [24] WebAssembly developers.  Memory64 Proposal for WebAssembly.  https://github.com/WebAssembly/memory64.
  * [25] WebAssembly developers.  Wabt: The WebAssembly Binary Toolkit.  https://github.com/webassembly/wabt.
  * [26] WebAssembly developers.  WebAssembly.  https://webassembly.org.
  * [27] WebAssembly developers.  Webassembly GC Proposal.  https://github.com/WebAssembly/gc.
  * [28] WebAssembly developers.  Webassembly Memories.  https://webassembly.github.io/spec/core/syntax/modules.html#syntax-mem.
  * [29] WebAssembly developers.  Webassembly Module Linking Explainer.  https://github.com/WebAssembly/module-linking/blob/master/proposals/module-linking/Explainer.md.
  * [30] WebAssembly developers.  Webassembly Portability.  https://webassembly.org/docs/portability/.
  * [31] WebAssembly developers.  Webassembly Text Format.  https://webassembly.github.io/spec/core/text/index.html.
  * [32] zstd developers.  zstd.  https://github.com/facebook/zstd.
  * [33] eBPF developers.  bpftool.  https://man.archlinux.org/man/bpftool.8.en.
  * [34] Elazar Gershuni, Nadav Amit, Arie Gurfinkel, Nina Narodytska, Jorge A Navas, Noam Rinetzky, Leonid Ryzhyk, and Mooly Sagiv.  Simple and precise static analysis of untrusted linux kernel extensions.  In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1069–1084, 2019.
  * [35] SNIA Computational Storage Technical Work Group.  Computational Storage Architecture and Programming Model v0.8 rev 0.  Technical report, SNIA, 2021.  https://www.snia.org/tech_activities/publicreview.
  * [36] Boncheol Gu, Andre S Yoon, Duck-Ho Bae, Insoon Jo, Jinyoung Lee, Jonghyun Yoon, Jeong-Uk Kang, Moonsang Kwon, Chanho Yoon, Sangyeun Cho, et al.  Biscuit: A framework for near-data processing of big data workloads.  ACM SIGARCH Computer Architecture News, 44(3):153–165, 2016.
  * [37] Andreas Haas, Andreas Rossberg, Derek L Schuff, Ben L Titzer, Michael Holman, Dan Gohman, Luke Wagner, Alon Zakai, and JF Bastien.  Bringing the web up to speed with webassembly.  In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 185–200, 2017.
  * [38] Aaron Hilbig, Daniel Lehmann, and Michael Pradel.  An empirical study of real-world webassembly binaries: Security, languages, use cases.  In Proceedings of the Web Conference 2021, pages 2696–2708, 2021\.
  * [39] Abhinav Jangda, Bobby Powers, Emery D Berger, and Arjun Guha.  Not so fast: Analyzing the performance of webassembly vs. native code.  In 2019 USENIX Annual Technical Conference (USENIX ATC 19), pages 107–120, 2019.
  * [40] Kornilios Kourtis, Animesh Trivedi, and Nikolas Ioannou.  Safe and efficient remote application code execution on disaggregated nvm storage with ebpf.  arXiv preprint arXiv:2002.11528, 2020.
  * [41] Jeff LeFevre and Carlos Maltzahn.  Scaling databases and file apis with programmable ceph object storage.  Santa Clara, CA, February 2020. USENIX Association.
  * [42] Daniel Lehmann, Johannes Kinder, and Michael Pradel.  Everything old is new again: Binary security of webassembly.  In 29th USENIX Security Symposium (USENIX Security 20), pages 217–234, 2020.
  * [43] Brian McFadden, Tyler Lukasiewicz, Jeff Dileo, and Justin Engler.  Security chasms of wasm.  NCC Group Whitepaper, 2018.
  * [44] Shravan Narayan, Craig Disselkoen, Daniel Moghimi, Sunjay Cauligi, Evan Johnson, Zhao Gang, Anjo Vahldiek-Oberwagner, Ravi Sahita, Hovav Shacham, Dean Tullsen, et al.  Swivel: Hardening webassembly against spectre.  In 30th USENIX Security Symposium (USENIX Security 21), 2021.
  * [45] Joel Nider, Craig Mustard, Andrada Zoltan, John Ramsden, Larry Liu, Jacob Grossbard, Mohammad Dashti, Romaric Jodin, Alexandre Ghiti, Jordi Chauzi, et al.  A case study of processing-in-memory in off-the-shelf systems.  In 2021 USENIX Annual Technical Conference (USENIX ATC 21), pages 117–130, 2021.
  * [46] NIST NVD.  Cve-2020-8835.  https://nvd.nist.gov/vuln/detail/CVE-2020-8835.
  * [47] NIST NVD.  Cve-2021-20268.  https://nvd.nist.gov/vuln/detail/CVE-2021-20268.
  * [48] Ivan Luiz Picoli.  OX: Deconstructing the FTL for Computational Storage.  IT University of Copenhagen, Computer Science, 2019.
  * [49] rBPF developers.  rbpf.  https://github.com/qmonnet/rbpf.
  * [50] Samsung.  Samsung SmartSSD.  https://samsungsemiconductor-us.com/smartssd/.
  * [51] SNIAOnStorage.  What is eBPF, and Why Does it Matter for Computational Storage?  https://sniacmsiblog.org/2021/07/what-is-ebpf-and-why-does-it-matter-for-computational-storage/.
  * [52] NGD System.  NGD Newport NVMe Computational Storage Platform.  https://www.ngdsystems.com/solutions.
  * [53] uBPF developers.  ubpf.  https://github.com/iovisor/ubpf.
  * [54] Tobias Vinçon, Arthur Bernhardt, Ilia Petrov, and Andreas Koch.  nkv in action: accelerating kv-stores on native computational storage with near-data processing.  Proceedings of the VLDB Endowment, 13(12):2981–2984, 2020.
  * [55] wasmtime developers.  wasmtime.  https://github.com/bytecodealliance/wasmtime.
  * [56] Conrad Watt.  Mechanising and verifying the webassembly specification.  In Proceedings of the 7th ACM SIGPLAN International Conference on certified programs and proofs, pages 53–65, 2018.
  * [57] Conrad Watt, Andreas Rossberg, and Jean Pichon-Pharabod.  Weakening webassembly.  Proceedings of the ACM on Programming Languages, 3(OOPSLA):1–28, 2019.
  * [58] Tong Zhang.  The true value of storage drives with built-in transparent compression.  SDC2020, October 2020. SNIA.