# Continuous-action Reinforcement Learning for Playing Racing Games: Comparing
SPG to PPO

Mario S. Holubar
Department of Artificial Intelligence
Bernoulli Institute
University of Groningen
<EMAIL_ADDRESS>
&Marco A. Wiering
Department of Artificial Intelligence
Bernoulli Institute
University of Groningen
<EMAIL_ADDRESS>

###### Abstract

In this paper, a novel racing environment for OpenAI Gym is introduced. This
environment operates with continuous action- and state-spaces and requires
agents to learn to control the acceleration and steering of a car while
navigating a randomly generated racetrack. Different versions of two actor-
critic learning algorithms are tested on this environment: Sampled Policy
Gradient (SPG) and Proximal Policy Optimization (PPO). An extension of SPG is
introduced that aims to improve learning performance by weighting action
samples during the policy update step. The effect of using experience replay
(ER) is also investigated. To this end, a modification to PPO is introduced
that allows for training using old action samples by optimizing the actor in
log space. Finally, a new technique for performing ER is tested that aims to
improve learning speed without sacrificing performance by splitting the
training into two parts, whereby networks are first trained using state
transitions from the replay buffer, and then using only recent experiences.
The results indicate that experience replay is not beneficial to PPO in
continuous action spaces. The training of SPG seems to be more stable when
actions are weighted. All versions of SPG outperform PPO when ER is used. The
ER trick is effective at improving training speed on a computationally less
intensive version of SPG.

##  1 Introduction

Reinforcement Learning (RL) (sutton2018reinforcement) is an Artificial
Intelligence paradigm which aims to develop policies for arbitrary tasks using
a reward function as a supervision signal. By trying different actions in some
environment and observing the outcome, an agent should be able to develop an
idea of what to do in which situation in order to maximize the reward signal.
A popular framework for this is actor-critic learning (konda2000actor). This
method uses two neural network function approximators, often called the actor
and critic networks; the former selects actions to take in the environment,
and the latter judges the quality of actions. As the actor interacts with the
environment, the critic learns how its actions affect the reward signal. It
can then teach the actor to perform better actions. The longer this process is
repeated, the better both networks become at their tasks.

Because of the large data requirement and amount of trial and error necessary
to learn a good policy, RL algorithms are usually trained in a simulated
environment. This can be an abstract control task, a video game or a
recreation of the real-world environment the agent will be deployed in.

In simulated environments, it is easy to provide the agent with a carefully
selected set of features in order to maximize its performance. It is also
possible to have the agent simply select one out of a list of predefined
actions at each timestep, since the environment handles the actual execution
of the actions. For robots to act in the real world however, it is important
that they are able to understand the data produced by their sensors, which is
almost always of continuous nature. They also often have to be able to exert
precise control over their actuators in order to interact with their
environment effectively. For these reasons, it is important to develop
reinforcement learning algorithms that can deal with continuous state- and
action-spaces.

In this paper, a racing environment for the OpenAI Gym (brockman2016openai)
baseline is introduced. In this task agents control a car and try to drive as
far along a racetrack as they can, obtaining rewards based on their speed. In
order to gain the highest reward possible, the agent has to learn to steer and
accelerate or brake as necessary.

The main focus of this paper will be the actor-critic learning algorithms
Sampled Policy Gradient (SPG) (wiehe2018sampled) and Proximal Policy
Optimization (PPO, schulman2017proximal). SPG is an algorithm that updates the
actor using action samples chosen by a Q-value network. It acts as a bridge
between Continuous Actor Critic Learning Automaton (CACLA)
(van2007reinforcement) and Deterministic Policy Gradient (DPG)
(silver2014deterministic). Two different configurations of SPG will be tested
on the racing environment and the effect of prioritizing action samples based
on their Q-value will be investigated. SPG will also be compared to an
implementation of PPO that does not use experience replay (ER), and a version
of PPO with a modified objective function that is able to utilize ER.

###  1.1 Contributions of this paper

  * •

The racing environment is interesting for research since it acts as a simple
baseline for continuous control, but can be extended in a large variety of
ways. It also models a real-world task, making it particularly useful. For
example, an agent could be pretrained using progressively more complex
versions of the racing environment before being deployed in a real robot,
minimizing the amount of trial and error required to reach good performance.

  * •

SPG is compared to a state-of-the-art learning algorithm (PPO), a version of
which was used in OpenAI’s Dota 2 agent OpenAI
Five111https://blog.openai.com/openai-five/. This comparison is especially
important since both of these approaches are fairly new and this comparison
has not been made before.

  * •

A modification of PPO is introduced that allows for the use of experience
replay in a continuous-action environment.

  * •

An extension to SPG is introduced that aims to improve training performance by
weighting action samples during the actor update step.

  * •

An extension to experience replay is introduced that aims to improve learning
speed while retaining the advantages of full ER.

###  1.2 Outline of the paper

Section 2 explains the background of the algorithms used in this paper.
Section 3 describes the environment, the PPO and SPG modifications, the
experience replay trick and the experimental setup. The results are presented
in section 4, followed by their discussion in section LABEL:sec:Conclusions.

##  2 Reinforcement learning

A reinforcement learning problem is generally modeled as a Markov Decision
Process (MDP). An MDP is a process that takes an agent from one state to
another, whereby the transition probabilities between different states depend
only on the current state and the action the agent takes. For each state
transition, the agent is given a reward $r_{t}$. The aim of the agent is to
maximize the sum of future discounted rewards, also known as the gain (G), at
every timestep t:

$G_{t}=\sum_{k=t}^{\infty}r_{k}\gamma^{k-t}$ (1)

$\gamma$ is the discount factor, which controls how rewards are weighed. A
lower discount factor means that immediate rewards are preferred, while a
discount factor close to 1 should be used for environments in which actions
have long-lasting consequences.

###  2.1 Actor-critic algorithms

The algorithms used in this paper are similar to the advantage actor-critic
(A2C) (konda2000actor) learning method. At the core of this approach are two
neural networks: one called the actor (or policy network) and one called the
critic (or value network). The actor takes the current state $s_{t}$ as its
input and returns an action to be taken. This action $a_{t}$ is then passed to
the environment, in which it is executed, producing a new state. This is
repeated for a set number of steps or until the agent has reached its goal.
This sequence is considered as one episode. During an episode, every timestep
is assigned a reward $r_{t}$ depending on a reward function. The rewards are
used by the critic to learn to estimate the gain for each step. The critic is
therefore defined as:

$V^{\pi}(s)=\hat{\mathbb{E}}_{\pi}[G_{t}|s_{t}=s]$ (2)

The Monte-Carlo learning rule used to update the critic is:

$V^{\pi}(s_{t})\leftarrow V^{\pi}(s_{t})+\alpha(G_{t}-V^{\pi}(s_{t})),$ (3)

where $\alpha$ is the learning rate.

The difference between the actual discounted reward for some state and the
critic’s prediction for it can be considered as an estimate of how much
better/worse than expected it is. This value is known as the advantage
$\hat{A}_{t}$, defined as:

$\hat{A}_{t}=G_{t}-V^{\pi}(s_{t})$ (4)

The advantage can be used to train the actor so that actions that resulted in
unexpectedly good outcomes are made more likely, and ones that resulted in
worse outcomes are made less likely.

###  2.2 Continuous action RL

Many reinforcement learning algorithms such as Q-learning (watkins1992q) use
discrete action spaces, which is sufficient for most tasks that are used in
research. However, in some applications it is not possible to discretize the
action space, either because it would result in too many discrete choices, or
because precise control is needed. This paper will discuss approaches that
work in a continuous action space.

A central question in RL research is the exploration vs exploitation dilemma.
In other words, to what degree should the agent try different things to learn
more about its environment vs use its already acquired knowledge to perform as
well as it can? This problem can be handled in various ways, such as
$\epsilon$-greedy or softmax exploration (tijsma2016comparing) (in the case of
Q-learning) or by having the policy network output a probability for each
action to be taken.

In order for the agent to act and explore in a continuous action space,
Gaussian noise could be added to the output of the actor with a decreasing
standard deviation, similarly to $\epsilon$-greedy exploration. In this paper
however a different approach is used for both PPO and SPG, in which the policy
network is given two output heads which correspond to the $\mu$ and $\sigma$
parameters of a normal distribution. The actions that are taken in the
environment are sampled from this distribution. The policy is updated by
minimizing or maximizing the log likelihood of the action being taken,
depending on the advantage. The corresponding objective function, which needs
to be maximized, is

$J^{PG}(\theta)=\hat{\mathbb{E}}_{t}[\log\pi_{\theta}(a_{t}|s_{t})\hat{A}_{t})].$
(5)

This allows for dynamic control over the exploration factor for each dimension
of the action space separately. If accelerating is always correlated with
higher reward, for example, the actor will reduce the standard deviation on
the throttle output and focus on steering instead. If the continued
acceleration then leads to crashes, the exploration on the throttle is
increased again.

This paper will explore the effectiveness of two fairly recent actor-critic
learning algorithms that are able to function in continuous spaces, which will
be described now.

###  2.3 PPO

One problem of traditional actor-critic methods is that there is no guarantee
for policy improvement; if the advantage at some state is negative, we only
know that the action taken at that state should be made less likely, but not
how much less likely. If multiple epochs of gradient descent are performed, it
is easy for the gradient update to become too large, resulting in the policy
being moved to an entirely unexplored (and potentially worse) area of the
action space.

The idea of trust regions was introduced by schulman2015trust to combat this
problem. It guarantees an improving policy by constraining the size of the
policy update based on the KL-divergence of the old and the current policy.
This has been shown to improve performance, however it comes at the cost of
simplicity. Trust Region Policy Optimization (TRPO) is not easy to implement
and is also not compatible with certain network architectures.

This led to the introduction of Proximal Policy Optimization
(schulman2017proximal), which aims to combine the simplicity of vanilla policy
gradient with the robustness and efficiency of TRPO. It does this by defining
a probability ratio $p_{t}(\theta)$:

$p_{t}(\theta)=\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}$
(6)

This ratio denotes the change the policy has gone through within an episode of
training. $\pi_{\theta_{old}}$ is the policy at the beginning of the update.
This means that during the first training epoch, $p_{t}(\theta)=1$.

The clipped surrogate objective function $J^{CLIP}(\theta)$ is then maximized
to update the policy:

$J^{CLIP}(\theta)=\hat{\mathbb{E}}_{t}[min(clip(p_{t}(\theta),1-\epsilon,1+\epsilon)\hat{A}_{t},p_{t}(\theta)\hat{A}_{t})]+\beta
H(\pi_{\theta}(s_{t})),$ (7)

where $\epsilon$ is a hyperparameter specific to PPO.

The entropy $H$ of a normal distribution is defined as:

$H=\frac{1}{2}ln(2\pi e\sigma^{2})$ (8)

Here, the entropy of the normal distribution given by $\pi_{\theta}(s_{t})$ is
multiplied by a factor $\beta$ and added to the objective to discourage
premature convergence (williams1991function). While this is not necessary, it
was found to increase performance significantly.

The $\epsilon$ and $\beta$ values used in this research can be found in the
appendix, along with all other hyperparameters discussed in this paper.

The clipped objective removes the incentive to move the policy far away from
the old one, allowing for multiple epochs of optimization. Taking the minimum
of the clipped and unclipped terms results in the objective only being clipped
if its value is improved by the new policy. If the value of the objective is
worse under $\pi_{\theta}$ than under $\pi_{\theta_{old}}$, the update is
allowed to be larger.

###  2.4 SPG

In Sampled Policy Gradient (wiehe2018sampled) the critic, which is usually a
state-value estimator, instead maps state-action pairs to Q-values. The term
Q-value is used here because the critic architecture is the same as in
Q-learning (watkins1992q); it tries to predict the quality (Q) of a state-
action combination:

$Q^{\pi}(s,a)=\hat{\mathbb{E}}_{\pi}[G_{t}|s_{t}=s,a_{t}=a]$ (9)

In the original SPG paper, temporal difference (TD) learning is used to update
the critic in an off-policy way. TD-learning relies on a process called
bootstrapping to update the critic with regard to an existing estimate of the
gain $G_{t}$. This, combined with off-policy learning and function
approximation, forms the "deadly triad" of reinforcement learning
(sutton2018reinforcement), which is known to cause instability and divergence
of the critic. In this research, a variant of SPG that utilizes Monte-Carlo
learning is used instead. The update rule for the critic is therefore:

$Q^{\pi}(s_{t},a_{t})\leftarrow
Q^{\pi}(s_{t},a_{t})+\alpha(G_{t}-Q^{\pi}(s_{t},a_{t}))$ (10)

In the policy update step, instead of performing gradient descent using the
action that was taken and its corresponding advantage, actions $a_{s}$ are
sampled from the action space. The critic is then used to obtain a Q-value for
each of the actions. The sampled action with the highest Q-value is used as
the backpropagation target for the gradient update of the actor:

$Target(s_{t})=\operatorname*{argmax}_{a_{s}}Q^{\pi}(s_{t},a_{s})$ (11)

The objective function for the actor that needs to be maximized is defined as:

$J^{SPG}(\theta)=\hat{\mathbb{E}}_{t}[\log\pi_{\theta}(Target(s_{t})|s_{t})].$
(12)

Several extensions to SPG are explained in the original paper. The algorithm
also allows for any search strategy to be used for sampling actions. In this
paper however, the standard algorithm is used with a simple Gaussian
exploration strategy; actions are sampled around the taken action $a_{t}$ with
an initial standard deviation $T$ that decays by some factor $\gamma_{T}$
after every episode. The original action $a_{t}$ is also included in the
Q-value comparison.

SPG is comparable to Deterministic Policy Gradient (DPG)
(silver2014deterministic) since it uses the same critic architecture. However,
whereas DPG updates the actor deterministically by taking the derivative of
the value function towards the action and updating the actor based on this,
SPG employs a more global search strategy. In theory, this makes it much less
likely to get stuck in local optima.

##  3 Methods

###  3.1 Environment

For this research, we introduce a simple racing game environment, in which
agents are represented as a car. They have to learn to accelerate, brake and
steer as appropriate in order to navigate a racetrack. The agent perceives its
environment by the means of five distance sensors pointing away from the car
at fixed relative angles. They measure the distance between the car and the
side of the racetrack. The current speed is also known to the agent. This set
of sensors has been shown to be optimal (togelius2007computational). It also
ensures that the only information that is utilized to make decisions is data
that would be available to a real robot, e.g. in the form of LiDAR and motor
sensors. Figure 1 shows a visualization of the environment and the distance
sensors.

Figure 1: Screenshot of the environment depicting the agent in red with rays
going towards the sides of the racetrack.

The actions the agent can take at any given time consist of throttle control
and steering. The former denotes the velocity the car is trying to reach; the
motor will accelerate or brake as needed until it matches the desired speed.
The latter controls the rotation of the car and is dependent on its velocity;
the faster it is, the less it can turn. When the speed is low, there is a
minimum turn radius that prevents it from making u-turns too quickly.

Both the states and actions are continuous and normalized between -1 and 1.
The throttle control is remapped so that it outputs a value between 0 and the
top speed of the car.

The racetrack is randomly generated and is made of a number of quadrilateral
polygons that act as checkpoints. If the agent drives off the racetrack, the
car is placed in the middle of the last passed checkpoint with a speed of
zero.

The reward given to the agent every timestep is its current velocity (in
pixels/sec) divided by its top speed. In order to gain the highest amount of
total reward, the agent must learn to manage its speed to be as fast as
possible, while avoiding crashing into walls. The reasoning behind this choice
of reward metric is that it could also be measured by the agent in a real-
world scenario and does not require the use of external tools or knowledge
about the racetrack. Furthermore, a reward of -10 is given if the agent leaves
the racetrack, however this is only necessary in this simulated environment
where agents respawn immediately after crashing. A real robot would lose
reward implicitly by being stuck on a wall; alternatively, another set of
sensors could be used to detect collisions.

###  3.2 Experience replay methods

In order to use the information gained during learning as efficiently as
possible, it should be used in multiple episodes of training. A method called
experience replay (lin1993reinforcement) is often used to allow this. The idea
is that instead of only using the state transitions from the current episode
in memory to train the agent, experiences are instead stored in a memory
buffer. The buffer keeps experiences until it is full, at which point the
oldest experiences are replaced. The agent’s value and policy networks can be
trained using this larger collection of data, allowing them to train in a more
robust way without requiring more interactions with the environment.

An issue with this method is that agents are now slower to incorporate new
information. For example, assume an agent has been training for a while. It
has improved to the point where it now encounters a new obstacle that it has
never seen before. With experience replay enabled, only a small fraction of
the learning step will actually deal with this new problem, since the memory
still consists of mostly old experiences. Only once the agent consistently
encounters the problem for a while does it learn how to deal with it
effectively. The result is slower training.

A potential solution to this issue is to split the training process into two
parts: first, the agent is trained using experiences from the replay buffer.
Then the same process is repeated with just "new" experiences, that is, ones
that were obtained during the most recent episode. In theory, this allows the
agent to retain the increased robustness gained from experience replay while
also being able to react to new discoveries quickly.

###  3.3 PPO with experience replay

PPO is an on-policy learning algorithm, in which the optimizer uses actions
that were taken under the current policy $\pi$. In theory, this prevents the
use of experience replay (mnih2013playing). However, in practice it has been
shown that combining on-policy learning with experience replay is useful under
certain conditions (sovrano2019combining).

Just using the normal PPO implementation with experience replay does not work
in a continuous-action environment. The reason for this is that to compute the
loss value, PPO uses the probability ratio $p_{t}(\theta)$ as described in
equation 6, working with the assumption that the action was taken under
$\pi_{\theta_{old}}$. If this is not the case, and the parameters of the
action sampling distribution have changed since the action was recorded,
$\pi_{\theta_{old}}(a_{t}|s_{t})$ can quickly tend towards 0, making
$p_{t}(\theta)$ tend towards infinity. If the advantage associated with
$a_{t}$ is negative, the ratio is not clipped, and the loss takes on an
extraordinarily large value, leading to exploding gradients.

In order to be able to use PPO with experience replay, the solution we propose
is to convert the algorithm to log space.

Let $\pi_{\theta}(a_{t}|s_{t})$ equal the log likelihood of selecting an
action $a_{t}$ at state $s_{t}$. The probability ratio is then defined as
follows:

$p_{t}(\theta)=\pi_{\theta}(a_{t}|s_{t})-\pi_{\theta_{old}}(a_{t}|s_{t})$ (13)

Under this equation, $p_{t}(\theta_{old})=0$.

The final step is to modify the clipping operator. It is possible to use a
hyperparameter $\epsilon_{log}$ for this and clip between $-\epsilon_{log}$
and $\epsilon_{log}$, but to allow for a fair comparison, the same
hyperparameter $\epsilon$ is used as in default PPO and the objective is
clipped between $log(1-\epsilon)$ and $log(1+\epsilon)$. The full objective
term that needs to be maximized then becomes:

$L^{CLIP}(\theta)=\hat{\mathbb{E}}_{t}[min(clip(p_{t}(\theta),log(1-\epsilon),log(1+\epsilon))\hat{A}_{t},p_{t}(\theta)\hat{A}_{t})]+\beta
H(\pi_{\theta}(s_{t}))$ (14)

The log-space transformation itself should not negatively affect PPO’s
performance, since $log(x)$ is monotonic with respect to x. In fact, gradient
descent methods are generally better at optimizing a function in log space
when dealing with probabilities, since the gradient of $log(p(x))$ is more
well-scaled than the one of $p(x)$. Additionally, it is more numerically
stable and not at risk of running into underflow problems.

###  3.4 Prioritized SPG

In most on-policy actor-critic algorithms such as PPO, each action is assigned
an advantage based on its relative value. This advantage acts as a weight
during the actor update step; it controls not only the direction but also the
amount of the policy shift. For example, if an action led to a significantly
worse outcome than expected, it is more important to make this action less
likely to occur than if it only slightly worsened the agent’s expected
performance.

SPG does not have access to advantage values for sampled actions, and does not
require their use: the estimated quality of the target action $Target(s_{t})$
is always equal to or higher than that of the original action $a_{t}$, so it
should never be made less likely. However, weighting the actions might still
provide some benefit, and is made quite easy thanks to the Q-value estimation:
the advantage of an action can be defined as the increase of its Q-value over
that of the original action $a_{t}$. Therefore,

$\hat{A}_{t}=Q(s_{t},Target(s_{t}))-Q(s_{t},a_{t})$ (15)

and the new objective function becomes:

$J^{SPG-p}(\theta)=\hat{\mathbb{E}}_{t}[\log\pi_{\theta}(Target(s_{t})|s_{t}))\hat{A}_{t}]$
(16)

This way, sampled actions that only offer a slight increase in Q-value do not
affect the policy as much, while ones that are estimated to be more useful are
weighed more heavily.

The SPG variant that uses prioritization will be denoted as SPG-p.

###  3.5 Experiment setup

Due to the fact that SPG requires action samples to be evaluated by the critic
for every step in an episode, the overhead associated with it is quite high.
This is especially the case when the policy optimizer is run for multiple
epochs. Hence, two versions of SPG with different hyperparameters will be
compared: one that uses the same learning hyperparameters as PPO, meaning the
actor update step is essentially run multiple times in a row with a low
learning rate; and one in which the update is only performed once per episode,
with a higher learning rate.

These two SPG configurations will be tested three times each: once without
experience replay, so the actor and critic are updated using only the most
recent episode’s experiences; once with purely experience replay, meaning that
after an episode the collected experiences are added to the replay buffer and
then the networks are trained using the whole buffer; and once with the hybrid
approach in which the networks are first trained using only the replay buffer,
and then using new experiences. In this case, both steps use half the amount
of experiences so the total amount of state transitions given to the optimizer
stays constant.

Additionally, the original PPO implementation using only recent experiences
will be compared to the logarithmic version with and without experience
replay, as well as to the different SPG variants.

An entropy bonus that encourages exploration was added to PPO’s loss function
since performance suffered significantly without it. It was determined in
prior experiments that this entropy bonus does not negatively affect PPO’s
final performance. SPG did not have any issues of this sort. In fact it
performed slightly worse with the entropy bonus, hence it was omitted.

All the experiments are repeated five times, where each time a different
racetrack is used. The different seeds used to generate the racetracks are the
same across algorithms to preserve fairness. Figure 2 shows the racetracks
produced by these seeds.

Figure 2: The five random racetracks used for the experiments.

Multilayer perceptrons (MLPs) are used as function approximators for the actor
and critic. Their architecture is the same in all algorithms. The critic
network consists of two hidden layers with 100 neurons each and the actor has
one hidden layer with 100 neurons. The activation function of the hidden
layers is tanh. No activation function is applied to the critic’s output
layer. The actor uses tanh and softplus for the $\mu$ and $\sigma$ output
heads, respectively. The critic and actor are optimized independently of each
other after every episode. This means a different number of epochs can be used
for the value and policy networks. The critic is optimized first so that new
experiences are already incorporated when it is used by SPG to sample actions
during the actor update. Every epoch, a minibatch of data is sampled from the
experiences of the most recent episode or the replay buffer and used to
perform gradient descent on the networks.

All hyperparameters used for this research can be found in the appendix. They
were initially selected according to the original papers’ recommendations and
then tuned in preliminary experiments.

##  4 Results

All reward curves are produced by recording the reward obtained by the agent
in each episode and averaging the results over the five racetracks.

Figure 3: SPG reward curves with multiple training epochs.

Figure 4: SPG reward curves with multiple training epochs and prioritization.

Figure 5: SPG reward curves with one training epoch.

Figure 6: SPG reward curves with one training epoch and prioritization.

It is evident from figures 4 to 6 that weighting actions based on their
Q-values does not have much effect on training speed or final performance; the
learning curves of the two variants are very similar, whether one or multiple
epochs of training is used. However, it does seem like training is slightly
more stable with prioritization. This is characterized by fewer downward
spikes in the learning curves and overall lower variance.

Since the difference between the results of these two variants is so small,
only SPG-p is used for all other comparisons.

Looking at the performance of just the multiple epoch variants of SPG (figures
4, 4), we can observe that experience replay gives it a large advantage.
Training is more reliable and results in higher final performances. The hybrid
variant that trains on both recent and old experiences seems to have equal or
even better performance.

In figures 6 and 6 the learning curves of the faster variant of SPG that
trains using only one epoch each episode are shown. When experience replay is
used, the final performance here is close to the one reached by the slower
method. However, the learning process is initially much slower and only
overtakes the recent-only performance when run for a sufficient number of
episodes. Here, the algorithm benefits from the hybrid method, which seems to
combine the learning speed of using recent experiences with the good final
performance of experience replay.

Figure 7: Reward curves of different approaches when no experience replay is
used.

Figure 8: Log-space PPO reward curves with and without experience replay.

Figure 9: Reward curves of SPG variants using both recent and old experiences
compared to PPO.

Figure 8 shows that the linear space and log space versions of PPO have nearly
identical performance when no experience replay is used. When SPG is used
without experience replay, it is outperformed by PPO in both configurations.
The multiple-epoch version of SPG offers no improvement over the faster
version in this case. It even seems to be less stable, with some trials
suffering from occasional temporary drops into negative reward, characterized
by large downward spikes of the reward curve.

From figure 8 it is evident that experience replay does not improve the
performance of PPO much. The variant with half new and half old experiences
had issues with exploding gradients, despite using the log space. It was not
able to run for 200 episodes without this problem occurring, and was therefore
omitted from the results.

Figure 9 shows that the faster SPG method using the hybrid approach matches
the performance of the slower multiple epoch variant. Both outperform PPO from
episode 30 onwards.


# Efficient Rollup Batch Posting Strategy on Base Layer††thanks: We thank Lee
Bousfield, Chris Buckland, Aysajan Eziz, Tim Roughgarden, and Thomas Thiery
for valuable feedback.

Akaki Mamageishvili  Offchain Labs  Edward W. Felten  Offchain Labs

(February 2023)

###### Abstract

We design efficient and robust algorithms for the batch posting of rollup
chain calldata on the base layer chain, using tools from operations research.
We relate the costs of posting and delaying, by converting them to the same
units and adding them up. The algorithm that keeps the average and maximum
queued number of batches tolerable enough improves the posting costs of the
trivial algorithm, which posts batches immediately when they are created, by
$8\%$. On the other hand, the algorithm that only cares moderately about the
batch queue length can improve the trivial algorithm posting costs by $29\%$.
Our findings can be used by layer two projects that post data to the base
layer at some regular rate.

##  1 Introduction

Ethereum blockchain satisfies high security and decentralization requirements,
but it is not scalable. Namely, transaction fees are too high for running
computationally heavy smart contracts. Also, it can only record a low number
of transactions on each block. To improve scalability, several different
solutions were proposed. Among them, one of the most successful solutions are
layer two (shortly L2) networks, called rollup protocols. Several rollup
protocols that build on top of Ethereum were proposed [7], [9]. While the
designs of these protocols of how heavy computation is delegated to them are
different, they share one thing in common: from time to time they post
(compressed) batches of transactions on the Ethereum main chain, referred to
as a base layer or a layer one (L1). These recorded transactions on the base
layer can be later used as a reference for rollup protocols and smart
contracts governing them if there is a dispute about the state of execution of
transactions. Rollup protocols create new economic design questions to solve.
In this paper, we address one of them. Namely, we study the question of
posting data batches of layer two rollup chains on a base layer, which
constitutes most of the costs the rollup chains incur. User transactions sent
to the rollup protocol are grouped together with fixed frequency and
compressed, which creates a batch. We study the question of how to decrease
these costs in this paper. We try to find an efficient strategy for when to
post transaction batches as the L1 price of posting data fluctuates. The
trade-off is clear: avoid posting batches when the price is high, but at the
same time, avoid delaying the posting. Such an algorithm adds to the
robustness of the system, and overall, to its security.

The question is motivated by historical experience with the Ethereum base fee,
which fluctuates in a partially predictable way, and occasionally, when some
major product is deployed on it, has intervals of very high base fee 111A
memorable instance involved a base fee of more than 100 times the norm for a
period of several hours. At least one rollup protocol (Arbitrum) decided to
take manual control of the batch posting policy during that instance.. Such
intervals are not too long and not too frequent, which gives a hope that after
some delay posting costs will be lower and posting can be resumed.

We decompose the cost in two parts: a posting cost that can be directly
observed when posting batches, and a delay cost that is not directly
measurable. More concretely, we interpret the total cost as the sum of posting
and delay costs. Delay cost has several components. The first is
psychological: users do not like when the batches are not posted for long
period, as it may suggest to them that components of the system are down or
unavailable. The second part is related to delayed finality: L2 transactions
are not fully final until they are posted as part of a batch and that batch
posting has finality on L1. Until that time, users must either wait for
finality or trust the L2 system’s sequencer to be honest and non-faulty.
Delayed finality imposes costs on some applications. The third part is related
to the specific technical nature of transaction fee computation on L2 rollups.
Namely, a transaction fee is calculated when transactions are created, not
when they are posted on L1. Therefore, more delay causes less precise
estimates of the L1 cost to attribute to L2 transactions, increasing the risk
of unfair or inefficient pricing of rollup transactions.

We model the problem as a Markov decision process. In each round, we calculate
total costs independently from the past rounds. Each round is characterized by
the current queue size and price, which constitutes a state. The price in the
next round is modeled as a random variable, which depends on the current
price. Depending on the strategy in the current round, the random variable
indicating the price in the next round moves the state to the next state. For
practical implementation, we discretize the price space and use a discrete
approximation of a continuous random variable. To solve the optimization
problem of finding the optimal strategy in each round, we use tools from
dynamic programming, in particular, q-learning. The structure of the solution
allows us to design a practical batch posting algorithm, which turns out to be
intuitive and simple. The algorithm is characterized by only two parameters.
We test the algorithm against a few natural benchmark algorithms, on the
previous year’s Ethereum base fee data 222The data covers the full period from
the introduction of EIP-1559 in August 2021 until November 2022.. Back-testing
allows us to find optimal parameter sets for all algorithms and compare their
performances. A comprehensive theoretical analysis of the EIP-1559 gas fee
scheme is given in [8].

### Related literature

The optimization problem at hand is very similar to the inventory policy (IP)
problem, long studied in economics and operations research literature, see [1]
and [6]. In IP problems, the newly produced items need to be sold for some
price, and the demand price distribution is given. Therefore, the IP
optimization problem is to maximize revenue, by maximizing revenue from trade
and minimizing maintenance costs, while our problem is to minimize both costs.
These two are dual. The only difference between our optimization problem and
IP problems is that the delay cost in IP problems is linear in the inventory
size, as the cost is interpreted as the maintenance cost of stored items,
whereas we model the cost as superlinear in the number of delayed items. The
optimality of pure stationary strategies in a wide range of Markov decision
processes is shown in [2]. The main tool for solving our optimization problem
is Q-Learning, which was introduced in [10]. Linear delay cost of transaction
inclusion is discussed in [4]. The convergence of the dynamic programming
algorithm that covers our case as well is discussed in [5].

##  2 Model

There is a discrete time with an infinite horizon. In round $i\in\mathbb{N}$,
one new batch is created. The number of batches currently queued is denoted by
$Q_{i}$. $P_{i}$ is the price of posting a batch in the round $i$.

At each round, the batch poster chooses a number of batches to publish,
denoted by $N_{i}$. It is proved in the operations research literature that
the optimal way of doing so is to apply a stationary strategy. Namely, by
applying a strategy function $S$ which must satisfy $0\leq S(P_{i},Q_{i})\leq
Q_{i}$. That is, it is optimal to assume that $N_{i}=S(P_{i},Q_{i})$ is only a
function of the posting price in the current round and the queue size. By
default, the algorithm posts batches that were created earliest (i.e., in FIFO
order). Intuitively, $S$ should be weakly increasing in $Q_{i}$ (if more
batches to post, we should not post less) and weakly decreasing in $P_{i}$ (if
more expensive to post, we should not post more). This intuition can be used
to test any (heuristic) solution we obtain.

In round $i$, the system incurs a cost

$C_{i}=C_{i,\mathrm{posting}}+C_{i,\mathrm{delay}}=P_{i}N_{i}+c(Q_{i}-N_{i})^{2}.$
(1)

In this paper, we assume that $C_{i,\mathrm{posting}}:=P_{i}N_{i}$ and
$C_{i,\mathrm{delay}}:=c(Q_{i}-N_{i})^{2}$, where the $c>0$ coefficient
represents the relative weight of the second component.

The first term represents the cost of posting batches. Here we assume that the
posting price is not affected by how many batches we post in each round. This
assumption could be violated in practice if $N_{i}$ is very large. The second
term represents the cost of delaying the posting of batches that remain in the
queue after this round, essentially assuming that the cost of delaying a batch
until the next round is linear in how long that batch has already been waiting
333Strictly speaking, the exact functional form of such delay would be
$\sum_{i=1}^{Q_{i}-1}i=\frac{Q_{i}(Q_{i}-1)}{2}$, however, we approximate by
ignoring the linear term in $Q_{i}$ and we absorb the factor of two into the
coefficient $c$.. The non-linear cost of delay is natural and is well-studied
in the economics literature.

Figure 1: Relative change of the Ethereum base fee per block, over the past
year. Each data point represents the ratio of the base fee in block $i+1$ to
the base fee in block $i$. The large bar at 1.125 is the case where block
$i+1$ is completely full so the base fee is increased by the maximum amount.

To move to the next round, we update:

$Q_{i+1}:=Q_{i}-N_{i}+1,$

representing posting of $N_{i}$ batches in round $i$ and the arrival of one
more batch in the queue in round $i+1$, and

$P_{i+1}:=R(P_{i}),$

where $R$ is some random function that models the fluctuation of the batch
posting price. Here we are making another implicit assumption that the L2
batch posting strategy does not affect the future base fee. This is a
reasonable approach especially if the number of batches posted is not very
large. Also, batches are created at a regular rate and their sizes are equal.
The latter is relevant as the price of posting is measured in gas units, that
is, the real cost is multiplied by how large the batches are in gas units.

To begin, we consider the price of the next block to be uniformly distributed
at the interval $[P_{i}\cdot{t_{1}},P_{i}\cdot t_{2}]$, where
$t_{1}=\left(\frac{7}{8}\right)$ and $t_{2}=\left(\frac{9}{8}\right)$, as the
base fee may change by $\frac{1}{8}$ either direction in every $12$ seconds.
Note that $t_{1}\cdot t_{2}\approx 0.984$ is smaller than $1$, that is, the
distribution is slightly skewed to the left. For a more realistic
distribution, we need to look at the data. We assume that each batch is
generated every minute (60 seconds), and the distribution of $R(P_{i})$ is a
result of uniform distribution convoluted $5$ times: $R(R(R(R(R(P_{i})))))$.
Theoretically, this approaches the normal distribution for a large enough
number of convolutions. For data on the Ethereum one-minute base fee changes,
see Figure 2. Note that there is a skew to the left direction, and there is an
outlier at point $1.8$, which is caused by a large outlier in the block base
fee change data, see Figure 1. A large outlier corresponds to full blocks and
a small outlier corresponds to empty blocks. Both outliers are observed in a
theoretical setup with rational miners (block proposers), that maximize their
own tips, see [3].

Figure 2: Relative change of the Ethereum base fee per minute, over the past
year. Each data point represents the ratio of the base fee at $i+1$ minutes to
the base fee at $i$ minutes. The distribution is similar to the result of
composing five steps drawn independently from the distribution in Figure 1.

Although we do see a large peak at the max increase in the per-block data, we
do not see a similarly large peak at the max increase in the per-minute data.
This suggests that the per-minute data is likely more consistent with the
hypothesis that per-block changes are independent of each other, and not that
there are extended periods of the maximum price increase. Perhaps a large
number of completely full blocks is due to different block producers having
different lower bounds on the tip they require so that when a block producer
with a low tip bound makes a block, that block includes a lot more
transactions. That would be consistent with an assumption of independence
between the base fee change in consecutive blocks.

An especially interesting factor is a potential support size of $R(P_{i})$.
The right endpoint of the support turns out to be $1.8P_{i}$. The reason is
that $1.8\approx(\frac{9}{8})^{5}$, and it seems to happen often that price
increases exponentially 444Somewhat against the assumption of uniform
distribution.. In fact, if we look at block data, the maximum increase appears
to happen $15\%$ of the time. The left endpoint is $0.6P_{i}$. The reason is
that $0.6\approx(\frac{7}{8})^{5}$.

### Objective functions

Our goal is to minimize the expected value of the total cost. We assume there
is an infinite horizon of rounds with discounted costs: we minimize
$\sum_{i=0}^{\infty}C_{i}\delta^{i}$, where $\delta<1$ is a discount of future
costs. This variant is very similar to the inventory policy problem, with the
only difference being that the delay cost in inventory policy problems is
linear in the delayed number.

As a side note, we optimize the cost with a finite number of rounds $n$: In
this variant, we minimize the total sum of costs $\sum_{i=1}^{n}C_{i}$. The
solution is described in section 5.

##  3 Bellman Equation/Q-Learning

We now turn to solve the main variant with an infinite number of rounds and
future cost discounting. To this end, we apply Q-Learning. Using standard
notation555See Bellman equation: https://en.wikipedia.org/wiki/Q-learning., we
calculate the following two matrices: $Q[s_{t},a_{t}]$ and $O[s_{t}]$. $s_{t}$
is the current state and $a_{t}$ is an action. In our case, $s_{t}$ is a pair
of $(Q_{i},P_{i})$, while $a_{t}$ is any natural number between 0 and $Q_{i}$.
The action $a_{t}$ corresponds to how many batches to post at round $t$.
$Q[s_{t},a_{t}]$ denotes the total cost, discounting the future cost.
$O[s_{t}]$ denotes the optimal action given the state $s_{t}$, that is, the
action that minimizes the total cost from this point on. We initialize
$O[s_{t}]$ with $Q_{i},$ that is, the initial assumption that the optimal move
is to publish all batches at each point. The value update iteration step is
the following:

$Q^{new}[s_{t},a_{t}]:=(1-\alpha)Q[s_{t},a_{t}]+\alpha(c_{t}+\delta\cdot\mathbb{E}_{R}[\min_{a}Q[s_{t+1},a])].$

$c_{t}$ is the cost incurred by taking action $a_{t}$, in this (stationary)
round. That is, in our setting, this is $c_{t}:=a_{t}\cdot
P_{i}+c(Q_{i}-a_{t})^{2}$. $\alpha$ is a learning rate, as in the computation
of the new matrix $Q$, we take the previously computed matrix $Q$ with weight
$1-\alpha$ and new improved values with weight $\alpha$. After updating all
states of the $Q$ matrix, we update all values of the $O$ matrix. Note that
$O$ matrix values appear in the calculation of $\min_{a}Q[s_{t+1},a]$ which is
replaced with $Q[s_{t+1},O[s_{t+1}]]$.

We arbitrarily666Any other initialization works, for example, we can assign
$0$ to all entries of $Q$ matrix. The only difference is in the convergence.
While the rate stays the same, good initialization gives fewer iteration
steps. initialize $Q[s_{t},a_{t}]$ as $a_{t}\cdot P_{i}+c(Q_{i}-a_{t})^{2}$
and $O[s_{t}]$ as $Q_{i}$, consistent with an initial hypothesis, to be
refined by Q-Learning, that the optimal move at each point in time is to
publish all batches.

###  3.1 Implementation

We discretize the continuum price space by taking a bounded interval. That is,
we assume that the price of batch posting will not go above some high bound.
This is a reasonable assumption in our context. The space complexity of the
implementation is $\Theta(PQ^{2})$, where $P$ is the number of price points
and $Q$ is the maximum number of batches we allow in the queue. To enforce
this upper bound on queue length, we impose an infinite cost for exceeding the
bound.

The run-time complexity of the system is $\Theta(IPQ^{2}f(P))$, where $I$ is
the number of iterations before convergence, which depends on the convergence
rate, which itself depends on the learning rate $\alpha$ and future discount
$\delta$. $f(P)$ is an average of support sizes of $R(P_{i})$ random
variables. In the case of a normal random variable, $f(P)\in\Theta(P)$. When
generating a random variable for the close-to-boundary prices, we put weights
only up until the upper bound price, as we do not have $Q$ matrix values. This
irregularity of implementation creates misleading $O$ values for high prices,
as the expectation by the implementation is that the price goes down in the
next rounds, while theoretically, we would like to study a general case where
there is no upper bound on the price.

Higher $\delta$ means that we care about the future costs more. For the
implementation, we take $\delta=0.999$, which is close enough to $1$, but not
too close, as it slows down the computation considerably 777It also increases
the magnitude of values in the matrix $Q$, as we weight future costs more..

We take $P=400$ and $Q=300$. The ratio of the highest to lowest Ethereum base
fee in our data is around $6000$. Therefore, to approximate the real price
data with our discrete points, we multiply all prices by
$\frac{6000}{400}=15.$ We take the learning rate $\alpha=0.1$. At this
threshold, we observe that the values of the $Q$ matrix for large values of
$P$ and $Q$ are stabilized. Generally speaking, lower $\alpha$ improves the
precision of the $Q$ matrix calculation, but it increases computation time.
Namely, the number of iterations is higher. In our case, we did not observe
major qualitative or quantitative differences by choosing different values of
$\alpha$. We assume that the algorithm has converged when the change in every
entry in $Q$ is less than $\epsilon=0.01$, that is when:

$\max_{s_{t},a_{t}}Q^{new}[s_{t},a_{t}]-Q[s_{t},a_{t}]<\epsilon.$

The program takes $72$ hours to finish, for approximately 14000 iterations, on
the input described above on Intel Core i7-8565U CPU @ 1.80GHz x 8. The
current implementation is without parallelism. Note that $Q^{new}$ matrix
calculation depends only on $Q$, therefore, full parallelization is feasible.

###  3.2 Observations

Running the Q-learning algorithm and analyzing its output yields a few
observations:

  1. 1.

There is a threshold price, below which all batches are posted. That is, there
exists $T_{P}$, so that when $P_{i}<T_{P}$, $S_{i}(P_{i},Q_{i})=Q_{i}$.

  2. 2.

Above this threshold price, there exists a threshold on the number of batches
that depends on the posting price, so that, below this threshold, no batches
are posted. That is, there exists $T_{Q}(P_{i})$, so that, when
$Q_{i}<T_{Q}(P_{i})$, $S_{i}(P_{i},Q_{i})=0$.

  3. 3.

On the other hand, if $Q_{i}>T_{Q}(P_{i})$, then
$S_{i}(P_{i},Q_{i})=Q_{i}-T_{Q}(P_{i})-1$. That is, the minimum number of
batches is posted, to guarantee that in the next round if the price does not
change, the threshold condition on the number of batches will still hold.

We conjecture that for any plausible functional form of the delay term of the
cost, and for most smooth and convex/concave random distributions $R$ on price
changes, these observations should hold. Verifying the hypothesis that this is
the case for a given delay cost with a (smooth) version of random variable
future batch posting price, by solving a dynamic programming problem for a
given $R$, is left for the future. The functional form of the function
$T_{Q}(P)$ depends on the delay cost. For the quadratic delay cost, we
conjecture that for $P>T_{P}$, the optimal threshold on the queue size,
$T_{Q}(P)$, is of order $\Theta(\sqrt{P})$.

##  4 Back-testing results

In this section, we compare the performance of the algorithm based on our
Q-Learning analysis to three other algorithms’ performances. We calculate how
much each algorithm would spend and how much delay cost each would incur, on
the last year’s time-series data of Ethereum base fees, taken after every
minute, that is, after every fifth block888Before the Ethereum Merge on 6
September 2022, the time between blocks was about 12 seconds on average. Since
the Merge, the interval between blocks is fixed at 12 seconds.. It is assumed
that each batch has the same unit size, which is a good approximation in
practice. If batches are created with less frequency, we can easily modify the
test set and optimize parameters accordingly.

For each algorithm, we measure a few properties: publishing cost; delay cost;
the average and worst-case delays experienced by batches; and the maximum
number of batches posted in any one round. The last measure is an important
robustness measure, as posting too many batches at the same time may affect
the future price or even be impossible to perform given the L1 block space
constraints. All performances given in the following subsections are on the
Pareto-efficient curve of the pair of publishing and delay costs. Back-testing
algorithms were optimized for approximately $100$ different instances. All
algorithms described below are linear in the data size, as the decision in
each round depends only on the current round price and queue size.

###  4.1 Current Arbitrum algorithm

The first algorithm is currently deployed by Arbitrum. We denote it by
$\mathcal{O}$. $\mathcal{O}$ is characterized by 3 parameters, over which we
minimize its total cost:

  * •

$ap$, intuitively an acceptable price measured in GWEIs,

  * •

$e$, an exponent,

  * •

and $ut$, an update time in minutes.

Every batch has these three features. If the base fee is lower or equal to
$ap$, the batch is posted. After $ut$ time passes and the batch is still not
posted on L1, the new acceptable price becomes $e$ times bigger. That is,
$ap^{new}:=e\cdot ap$.

The performance of the algorithm $\mathcal{O}$ for a few parameter sets is
documented in the following table.

Parameters $(e,ap,ut)$ |  Publishing cost |  Delay cost |  Maximum delay |  Avg. delay
---|---|---|---|---
$(1.2,144,60)$ |  $2.598e+07$ |  $5.99e+09$ |  $773$ |  $39.7986$
$(2,96,120)$ |  $3.170e+07$ |  $6.456e+07$ |  $193$ |  $2.23403$
$(2.8,72,140)$ |  $3.271e+07$ |  $1.866e+07$ |  $165$ |  $0.949142$

Note that publishing cost increases and maximum delay and average delay
decrease by increasing $e$. Both behaviors are natural as the algorithm posts
more aggressively for higher $e$. There is no clear upper bound on the delay
in round $i$ as a function of posting price $P_{i}$, as it depends on when the
exponential function catches up with the price, i.e., it depends on the
history as well.

The following table shows the performance of the Arbitrum algorithm where the
acceptable price does not do a step-function doubling every update time but
instead increases in a smooth exponential curve with the same doubling time.
That is, the exponent in each round is equal to $e^{\frac{1}{ut}}$.

Parameters $(e,ap,ut)$ |  Publishing cost |  Delay cost |  Maximum delay |  Avg. delay
---|---|---|---|---
$(1.2,144,60)$ |  $2.60294e+07$ |  $4.73071e+09$ |  $771$ |  $33.5433$
$(2,96,120)$ |  $3.19334e+07$ |  $1.72324e+07$ |  $183$ |  $1.08583$
$(2.8,72,140)$ |  $3.31778e+07$ |  $4.86956e+06$ |  $164$ |  $0.429163$

Compared to the step algorithm described above, publishing costs are slightly
increasing and delay costs are slightly decreasing. But qualitatively, the
results are very similar.

###  4.2 Q-learning algorithm

The second algorithm, $\mathcal{Q}$, is based on Q-Learning. We optimize over
two parameters: $d$ and $T_{p}$, when minimizing the cost of the $\mathcal{Q}$
algorithm. In particular, we test $T_{Q}(P)=\frac{\sqrt{P-T_{P}}}{d}$ and
$T_{P}:=T_{p}$.

The performance of the algorithm $\mathcal{Q}$ for a few parameter sets is
documented in the following table.

Parameters $(T_{p},d)$ |  Publishing cost |  Delay cost |  Max. delay |  Avg. delay |  Max. posted
---|---|---|---|---|---
$(60,2)$ |  $3.420e+07$ |  $1.283e+06$ |  $42$ |  $1.699$ |  $5$
$(60,1.6)$ |  $3.383e+07$ |  $2.339e+06$ |  $52$ |  $2.127$ |  $7$
$(80,1.2)$ |  $3.324e+07$ |  $4.111e+06$ |  $69$ |  $2.00$ |  $10$

Note that both delay cost and maximum delay are increasing in decreasing $d$,
while publishing cost is decreasing. The publishing cost is decreasing and the
delay cost is increasing with increasing $T_{P}$. As a robust measure for
$T_{P}$, we can take the value that is $80\%$ percentile of the base fee data
distribution. This allows the algorithm to be fully automatic, by updating
$T_{P}$ every month or two weeks, to adjust to the current trend of prices. We
do not include a maximum posted number in the performance of the other
algorithms as this number is equal to the maximum delay by definition. Unlike
the previous algorithm, the algorithm in this section gives an upper bound on
the delay in each round $i$ as a function of the price of posting $P_{i}$,
which is equal to $\frac{\sqrt{P_{i}-T_{P}}}{d}$ and adds to the robustness of
the system. This gives a global upper bound $\frac{\sqrt{P_{\max}-T_{P}}}{d}$
on the maximum delay, where $P_{\max}$ is the maximum posting price. Note that
the maximum base fee was about $8200$ GWEIs and the maximum delays in the
table approximately correspond to this upper bound. For example,
$\frac{\sqrt{8200}}{1.2}\approx 74>69$. In general, the upper bound does not
have to be achieved, as the price may increase very quickly and the delay
queue size may not catch up.

###  4.3 Price minimizing algorithm

The third algorithm, $\mathcal{D}$, delays posting until the price drops below
a certain threshold $T$ and then posts all batches.

The performance of the algorithm $\mathcal{D}$ for a few parameters is
documented in the following table.

Parameters $T$ |  Publishing cost |  Delay cost |  Maximum delay |  Avg. delay
---|---|---|---|---
$60$ |  $2.237e+07$ |  $2.658e+12$ |  $14975$ |  $584.191$
$80$ |  $2.632e+07$ |  $2.683e+11$ |  $8448$ |  $124.4$
$100$ |  $2.896e+07$ |  $3.835e+09$ |  $1394$ |  $15.66$

Notice that a huge value of the maximum delay would violate our assumption
that the price of posting in each round is not affected by how many batches we
post. We do not include a maximum posted number in the performance of the
other algorithms as this number is equal to the maximum delay by definition.

###  4.4 Trivial algorithm

A trivial algorithm, denoted by $\mathcal{T}$, posts every batch immediately.
$\mathcal{T}$ has its own merits. First, it keeps the delay costs to $0$,
which imposes a minimal load on the system. Second, it is simple to interpret
and easy to implement.

Testing on the same data as the above algorithms, we find that a trivial
algorithm has publishing costs equal to $3.6e+07$. Note that it does not have
any parameters and the delay cost is equal to $0$. We use this result as a
benchmark to measure the performance of other algorithms with respect to the
cost of publishing.

###  4.5 Tips

In the paper so far, we ignored tips that are given to L1 block builders for
inclusion in the block in the design and analysis of efficient batch posting
strategy. These tips should in principle be counted towards the price of
publishing. For example, Arbitrum has a fixed tip, 1 GWEI per gas, which is
enough to get included in $95\%$ of the cases. If we count the minimum tips to
be included in each block towards the total price of being posted and run the
same algorithms as before, we get very similar results as before, namely, in
$1\%$ proximity of both, publishing and delay costs. One potential explanation
is that when tips to be included are high, base fees are also high, therefore,
none of the algorithms post their batches. These observations can be seen as
indicators to simplify the decision problem by including the tips directly
towards the cost of publishing, instead of choosing them strategically.

##  5 Dynamic programming with fixed prices

In this section, we discuss the case where there is a fixed number of rounds
$n$, and posting prices in each round are fixed and given in advance. At the
end of the last round, we publish all batches that are left unpublished. The
use-case of this algorithm, for example, is if there are futures contracts on
base fees.

The optimum solution can be found by dynamic programming with run-time
$\Theta(n^{3})$ as described in the following. In $dp[i][j]$, we store the
minimum cost incurred if in the first $i$ rounds we publish exactly $j$
batches. We iterate $i$ through all rounds in the outermost loop, contributing
the first multiplicative factor $n$. In the second loop, we iterate $j$
between 0 and $i$, contributing another multiplicative factor $n$. In the
third and innermost loop, we iterate $take$ over newly published batches,
between 0 and $i+1-j$, therefore, contributing the last multiplicative factor
$n$. We update $dp[i+1][take+j]$ with the maximum between the following two
values:

$dp[i+1][take+j]:=\max(dp[i+1][take+j],dp[i][j]+cost),$ (2)

where $cost$ is calculated as $c(i-j-take+1)^{2}.$ We also record $take$ that
gives the minimum answer for each $i$ and $j$, which will allow us to recover
the answer, and the number of batches published at each round to minimize
global cost. The global cost is located at $dp[n][n]$ and we can reconstruct
the answer of how many to publish at each round using a backtracking
algorithm.

We generated prices according to different distribution functions and observed
that it is almost always optimal to publish zero or all batches.

##  6 Conclusions

We initiate the study of an efficient batch posting strategy by L2 rollup
chains on the L1 chain as a calldata. As an outcome, we obtain efficient
algorithms with robustness guarantees. Namely, in each round, the new
algorithm does not post too many batches and the number of batches kept in the
queue is bounded by a function of posting price in each round. Future avenues
of research include the optimization problem where current and future prices
depend on the number of batches posted in each round. This may be the case if
rollup protocols become dominant in the scalability of the base fee. Finding
out the optimal constant tip is also left for future research.

## References

  * [1] Kenneth J. Arrow, Theodore Harris, and Jacob Marschak.  Optimal inventory policy.  Econometrica, 19(3):250–272, 1951.
  * [2] Hugo Gimbert.  Pure stationary optimal strategies in markov decision processes.  In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 200–211. Springer, 2007.
  * [3] Jens Leth Hougaard and Mohsen Pourpouneh.  Farsighted miners under transaction fee mechanism EIP1559.  Working Paper, 2022.
  * [4] Gur Huberman, Jacob D. Leshno, and Ciamac Moallemi.  Monopoly without a monopolist: An economic analysis of the bitcoin payment system.  The Review of Economic Studies, 88(6):3011–3040, 2021.
  * [5] Tommi S. Jaakkola, Michael I. Jordan, and Satinder P. Singh.  On the convergence of stochastic iterative dynamic programming algorithms.  Neural Comput., 6(6):1185–1201, 1994.
  * [6] Arthur F. Veinott Jr.  The optimal inventory policy for batch ordering.  Operations Research, 13:424–432, 1965.
  * [7] Harry A. Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten.  Arbitrum: Scalable, private smart contracts.  In William Enck and Adrienne Porter Felt, editors, 27th USENIX Security Symposium, USENIX Security 2018, Baltimore, MD, USA, August 15-17, 2018, pages 1353–1370. USENIX Association, 2018.
  * [8] Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen, Efstratios Skoulakis, and Georgios Piliouras.  Dynamical analysis of the EIP-1559 ethereum fee market.  In Foteini Baldimtsi and Tim Roughgarden, editors, AFT ’21: 3rd ACM Conference on Advances in Financial Technologies, Arlington, Virginia, USA, September 26 - 28, 2021, pages 114–126. ACM, 2021.
  * [9] Diego Nehab and Augusto Teixeira.  The core of cartesi.  White Paper, 2018.
  * [10] Christopher John Cornish Hellaby Watkins.  Learning from delayed rewards.  1989\.


positive $TP$ be the diagnosis of the same disease $d$ by $C$ from both
reference and reconstructed X-ray images. False positive $FP$ of a disease $d$
implies that $d$ is diagnosed from the reconstructed chest X-ray image but not
diagnosed from the input. Similarly, false negative $FN$ indicates that a
disease is diagnosed from the reference input but it does not from the
reconstructed image. We can thus compute the precision ($\frac{TP}{TP+FP}$),
recall ($\frac{TP}{TP+FN}$), and F1 score (harmonic mean of the precision and
recall), respectively. Overall, Table 17 indicates that accurate disease
information can be inferred from the reconstructed X-ray images.

The high accuracy in conducting disease diagnosis over reconstructed images in
Table 17 indicates a serious leakage of patient’s confidential information. We
also localize lesions (see Appx. C clarifying attack setup at this step) of
reconstructed X-ray images and corresponding reference inputs in Fig. 17:
lesions in reconstructed images and reference inputs are highly consistent.

Fig. 20 reports the evaluation results of reconstructing audio data in LMS
graphs, whose x-axis represents time and y-axis denotes log-amplitude of
frequencies. The references and reconstructed recordings have mostly
consistent LMS graphs in all cases. As mentioned in Table 3 and Appendix C,
SC09 includes real-world “speech commands”; hence, recovering quality voice
recording indicates a strong likelihood of violating user privacy, such as
voice commands. Given that the LMS graphs of audio clips are usually too dense
to read on paper, we have also released reconstructed audio recordings [3];
interested readers can easily verify that the reconstructed audio clips
exhibit high quality with negligible noise.

Neglecting Non-Privacy Factors. Our manual inspection on the reconstructed
images also reveal several interesting cases in As presented in Fig. 24, while
the reconstructed images of celebrity faces are of good quality and highly
similar to the reference inputs, the reconstructed images do not contain
glasses. On one hand, we emphasize that the reconstructed images can be
matched to the reference inputs with above 99.9% confidence score using the
commercial face recognition APIs provided by Face++. This indicates that the
“privacy” related features that can uniquely recognize human identities are
successfully preserved in the reconstructed photos. More importantly, we
interpret this evaluation has shown the effectiveness of our customized
objective functions which aim to retain specific privacy indicators. Recall as
defined in Table 1, we enforce our autoencoder framework to particularly
retain human privacy related contents like gender. As a result, our
autoencoder framework narrows the focus to critical features and facilitates
commercial APIs extracting key perceptual contents. Non-privacy factors (e.g.,
glasses) are generally discouraged to distract the attention of our attack
framework.

Figure 25: Reconstructed images suffering from over-smoothing.

Ablation Evaluations. Recall in designing objective functions, we explain that
using only pairwise distance metrics can likely generate “over-smoothing”
images, thus clarifying the necessity of composing the objective function with
discriminator to implicitly capture the “semantics similarity” among reference
and reconstructed images. Fig. 25 presents several reconstructed images by
only using the pairwise distance. It is easy to see that the reconstructed
images exhibit low quality compared with sample cases shown in Fig. 15 and
Fig. 20. In particular, it suffers from over-smoothing, where the details in
the LMS images and chest X-ray photos become much blur, comparing with the
reference inputs. We view the results empirically demonstrate the necessity
and strength of adopting hybrid objective functions as the learning goal of
our autoencoder framework. Also, mode collapse may be potentially introduced
by the implicit objective function. Nevertheless, we clarify that high
discriminability of the reconstructed media data empirically demonstrates that
mode collapse is not a major concern of our framework.

Vulnerable Code. In addition to vulnerable code localized in FFmpeg and
reported in Sec. 6.2, we further report vulnerable code in libjpeg and
Hunspell in Fig. 26 and Fig. 27, respectively. Both code fragments contain
obvious input-dependent memory accesses (we mark program variables derived
from inputs in red). These input-dependent memory accesses further lead to the
accesses of different cache units or page table entries, thus enabling side
channel exploitations. To the best of our knowledge, MCU and putdic, as
vulnerable code fragments of libjpeg and Hunspell, were not pointed out by
existing works [117, 45]. In addition, we identify these stealthy code
fragments fully automatically using neural attention mechanisms. This
highlights the strength of our neural approach. And to confirm our findings,
we manually analyzed how inputs are propagated into certain program variables,
and how those program variables are used to access memory (and further lead to
side channels).

Also, we report all the localized assembly instructions that primarily
contribute to the reconstruction of private inputs. The corresponding line
number of localized assembly instructions are reported in [3]. We use the
default configuration to compile each media software, whose compiled
executable file can also be found in our released repository [3]. Hence,
developers can use our reported information and released executable files to
further localize and patch relevant code fragments.

⬇

1int HUFF_EXTEND(int x, int s@) {

2 // “ex_test” and “ex_offset” are

3 // pre-calculated arrays

4 if (x < ex_test[s])

5 return x + ex_offset[s];

6 else

7 return x;

8 }

9

10boolean decode_mcu_fast(j_decompress_ptr cinfo@,

11 JBLOCKROW *MCU_data) {

12 huff_entropy_ptr entropy =

13 (huff_entropy_ptr)cinfo->entropy;

14 /* preprocessing */

15 for (int i = 0; i < cinfo->blocks_in_MCU; i++)

16 d_derived_tbl *dctbl = entropy->dc_cur_tbls[i];

17 int s, k, r, l;

18 /* get index “idx” based on “s” */

19 /* update “r” */

20 s = dctbl->lookup[idx];

21 // “lookup” is pre-calculated array

22 if (s)

23 s = HUFF_EXTEND(r, s);

24 }

25 /* do something */

26 }

27 /* do something and return */

28}

Figure 26: Vulnerable code components in libjpeg. We mark variables depending
on libjpeg’s input in red, and bold input-dependent memory accesses (e.g.,
line 4).

⬇

1 boolean check(Hunspell** pMS, int* d@, string& token) {

2 // checking and transforming encoding of “token”

3 if pMs[*d]->spell(token)

4 return true;

5 return false;

6 // “pMs” is a hash table storing the dictionary

7 // spell() performs spell checking

8 }

9

10 int putdic(const std::string& word@, Hunspell* pMS) {

11 // checking and transforming encoding of “word”

12 size_t w = word.find(‘/‘, 1);

13 if (w == std::string::npos) {

14 if (word[0] == ‘*‘)

15 ret = pMS->remove(word.substr(1));

16 else

17 ret = pMS->add(word);

18 } else {

19 std::string affix = word.substr(w + 1);

20 word.resize(w);

21 if (!affix.empty() && affix[0] == ‘/‘)

22 affix.erase(0, 1);

23 ret = pMS->add_with_affix(word, affix);

24 }

25 // “pMs” is a hash table storing the dictionary

26 return ret;

27 }

Figure 27: Vulnerable code components in Hunspell. We mark variables depending
on Hunspell’s input in red, and bold input-dependent memory accesses (e.g.,
line 3). Figure 28: Reconstructed images on CIFAR-100. Table 18:
Generalization evaluation.

($k,N$) | ($1,100$) | ($5,100$) | ($20,100$)
---|---|---|---
libjpeg | 5.7% | 20.3% | 44.1%
Baseline | 1% | 5% | 20%

Generalization. As explained in Sec. 3, different types of media data (e.g.,
human face vs. vehicle photos) are generally projected toward distinct
manifold spaces [14, 88, 99]. Hence, training a unified model to recover media
data of different classes are beyond the scope of our SCA.

To thoroughly explore the potential limitations, this section provides an
empirical assessment of the generalization of our SCA framework. To this end,
we collect side channel traces logged when using libjpeg to process a general
dataset, CIFAR-100 [59]. These side channel traces are used to train our
autoencoder framework and to reconstruct unknown images in CIFAR-100 from
their induced side channel traces. The CIFAR-100 dataset comprises 60K images
of 100 classes. Each class of 600 images is divided into 500 training images
and 100 testing images.

Fig. 28 reports the qualitative evaluation results, by comparing the inference
inputs with their reconstructed images. In general, we observed that the
reconstructed images manifest much worse visual quality than those synthesized
from specific datasets (e.g., CelebA and Chest X-ray). Nevertheless, we still
observed that some expressive features, particularly sketch and color, are
retained in the reconstructed images.

For quantitative evaluation, we use SSIM [110] to assess similarity between
reconstructed images and reference inputs. Table 18 reports the evaluation
results of determining whether the reference input appears in the top-$k$ of
$N$ (e.g., top-$5$ out of randomly selected 100) images matched with the
reconstructed images. The overall matching rates are high and greatly
outperform the baseline — random guess. These findings indicate the promising
potential of our approach to exploit arbitrary datasets and recover
confidential user inputs. Though the reconstructed media data was not visually
vivid, it still notably facilities privacy stealth.

Note that a conventional approach in AI community is to provide the class
label of each image [18]. In short, the model can switch to proper manifold
according to image labels. Our experiment does not provide class labels and
mix all images together to faithfully explore model’s generalization
capability. We leave it as one future work to enhance generalization with
labeled data and more advanced models.

Figure 29: Qualitative evaluation results of perception blinding. Figure 30:
Qualitative evaluation results of perception blinding.

##  Appendix H Mitigation

In accordance with Sec. 6.3, Fig. 29 further reports qualitative evaluation
results of perception blinding-based mitigation. In short, Fig. 29 manifests
results and findings mostly comparable with evaluations launched in Sec. 6.3.
That is, “noise mask” (the first row) and “non-face mask” (the second row) are
generally not effective in blinding $i_{private}$; perceptual features can be
seen in the reconstructed images (e.g., face poses, hair style). Using real
face images from the CelebA dataset as the masks manifest highly encouraging
results to blind key perceptual-level features. In addition, to recover final
outputs (i.e., the “Recovered” columns), a larger $\alpha$, at least greater
than 0.10, should be desirable.

Regarding quantitative evaluation, Table 19 reports the adversary disease
diagnosis results after applying three blinding masks toward the Chest X-ray
dataset. Consistent with our findings from the CelebA dataset, using “X-ray#1”
image to blind chest X-ray images can achieve a much better result to reduce
the disease diagnosis accuracy. We also report the quantitative evaluation
results of mitigating DailyDialog datasets in Table 21, which manifest mostly
consistent results with Table 11.

Table 19: Mitigating adversary disease diagnosis attack on Chest X-ray
dataset. We report text data inference accuracy in terms of cache bank/cache
line/page table. We use three blinding masks as “Noise” “Non-X-Ray” and a real
X-ray photo “X-Ray #1”.

Mask | Disease | $\alpha=0.05$ | $\alpha=0.1$ | $\alpha=0.3$
---|---|---|---|---
Noise | Cardiomegaly | 0.61/0.55/0.54 | 0.61/0.54/0.53 | 0.63/0.58/0.53
| Consolidation | 0.82/0.82/0.81 | 0.82/0.81/0.81 | 0.82/0.81/0.81
| Atelectasis | 0.60/0.60/0.57 | 0.60/0.56/0.57 | 0.61/0.57/0.55
Non-X-Ray | Cardiomegaly | 0.61/0.54/0.58 | 0.63/0.55/0.56 | 0.63/0.52/0.51
| Consolidation | 0.81/0.81/0.82 | 0.82/0.82/0.82 | 0.81/0.81/0.81
| Atelectasis | 0.61/0.55/0.58 | 0.65/0.55/0.58 | 0.61/0.57/0.54
X-Ray #1 | Cardiomegaly | 0.15/0.19/0.14 | 0.20/0.21/0.19 | 0.20/0.27/0.20
| Consolidation | 0.73/0.83/0.79 | 0.74/0.82/0.80 | 0.74/0.85/0.83
| Atelectasis | 0.08/0.07/0.08 | 0.12/0.11/0.15 | 0.19/0.12/0.14

Table 20: Mitigating human voice matching attack on SC09 dataset with
blinding. We report text data inference accuracy in terms of cache bank/cache
line/page table. We use three blinding masks as “Noise” “Non-Voice” and a real
data sample “Voice”.

Mask | $\alpha=0.05$ | $\alpha=0.1$ | $\alpha=0.3$
---|---|---|---
Noise | 13.1/12.8/12.9% | 15.2/15.3/15.1% | 20.3/19.9/20.1%
Non-voice | 14.2/13.9/14.1% | 17.1/17.0/17.3% | 20.2/20.0/19.8%
Voice | 7.2/7.0/7.0% | 7.1/7.8/7.6% | 8.7/8.5/9.1%

Table 21: Mitigating DailyDialog text inference attack. We report text data
inference accuracy in terms of cache bank/cache line/page table. $\alpha=0.05$
denotes word appended with total 19 masks. $\alpha=0.1$ denotes word appended
with total 9 masks, while $\alpha=0.3$ denotes word appended with total 2
masks.

Mask | $\alpha=0.05$ | $\alpha=0.1$ | $\alpha=0.3$
---|---|---|---
“I” | 0.19/0.32/0.18% | 0.18/0.34/0.19% | 0.50/0.88/0.38%
“you” | 0.22/0.33/0.22% | 0.24/0.34/0.26% | 0.45/0.72/0.53%

##  Appendix I Noise Resiliency Evaluation Setup

Figure 31: Evaluation results of CelebA dataset in terms of 9 different noise
settings.

This section elaborates on the setup of noise resiliency evaluation launched
in Sec. 6.6. In sum, we evaluate adding noise to cache line access traces
logged by Pin and cache set access traces logged via Prime+Probe on Intel L1D
cache. First, given a Pin logged side channel trace, we leverage the following
schemes to insert noise into the trace.

Gaussian noise. We perturb every record $d$ on a side channel trace using
$d=x\times n+(1-x)\times d$, where $x\in\\{0.2,0.5\\}$. $n$ is randomly
generated noise following Gaussian distribution.

Removal. We randomly remove $x\%$ of the data points on the side channel,
where $x\in\\{20,50\\}$.

Round shifting. We round shift a side channel trace for $x$ steps, where
$x\in\\{10,100\\}$.

Note that each noise insertion scheme has two configurations. For the ease of
presentation, we use Low and High to denote two configurations, respectively.
For instance, Gaussian/High denotes an intensive setting such that we apply
Gaussian noise to perturb side channel traces when $x=0.5$. As for the cache
set access traces logged via Prime+Probe, we also launch the following three
perturbation schemes:

Leave cache hit/miss out. We randomly drop $x\%$ of the cache set hit/miss
records on the logged trace, where $x\in\\{20,50\\}$.

False cache hit/miss. We randomly flip $x\%$ of records in the logged cache
set access trace, where $x\in\\{20,50\\}$. This way, we create false cache
hits/misses.

Wrong order of cache hit/miss. We randomly select $x$ non-repetitive cache set
hit/miss records and compose $\nicefrac{{x}}{{2}}$ pairs of records, where
$x\in\\{100,500\\}$. We then exchange records in each pair.

Again, each noise insertion scheme has two configurations, and we use Low and
High to denote the intensity of two configurations. In addition, we also mimic
real-world noise, by introducing extra workload over the CPU core when
launching Prime+Probe. Particularly, in our exploitation launched Sec. 6.4,
only victim, spy, and coordinator processes occupy the CPU core. At this step,
however, we launch extra processes on the same CPU core, which can likely
introduce a considerable amount of noise on the trace. Particularly, we
consider the following three scenarios to systematically explore noise
introduced by real-world workload.

Bzip2. We pick the bzip2 software from SPEC CPU 2006 testsuite to compress a
large file (100MB) simultaneously when the spy is launching Prime+Probe attack
toward victim. SPEC CPU 2006 is a standard CPU-intensive benchmark suite that
is frequently used in security research.

Victim1. We launch another victim software (e.g., another libjpeg) on the same
core. This victim software will process the same input simultaneously when the
spy is launching Prime+Probe attack toward victim.

Victim2. We launch another victim software (e.g., another libjpeg) on the same
core. This victim software will process different inputs simultaneously when
the spy is launching Prime+Probe attack toward victim.

To certain extent, noise introduced by these three workloads could have been
subsumed by our inserted noise (e.g., Gaussian or false cache hits/misses).
Nevertheless, we still launch this evaluation to thoroughly benchmark the
noise resiliency of our SCA.

Table 22: Quantitative evaluation results of human voice reconstructed from
noisy side channels.

Noise | NA | Low | High
---|---|---|---
Gaussian | 28.8% | 20.4% | 17.0%
Shift | 28.8% | 28.6% | 26.3%
Removal | 28.8% | 25.0% | 24.5%
Leave hit/miss out | 81.8% | 80.7% | 80.0%
False hit/miss | 81.8% | 78.5% | 3.4%
Wrong order | 81.8% | 82.1% | 79.9%
Bzip2 | 81.8% | 66.0%
Victim1 | 81.8% | 67.5%
Victim2 | 81.8% | 55.8%

Table 23: Quantitative evaluation results of dialog text reconstructed from
noisy side channels.

Noise | NA | Low | High
---|---|---|---
Gaussian | 37.4% | 35.5% | 30.8%
Shift | 37.4% | 25.6% | 27.0%
Removal | 37.4% | 32.8% | 32.6%
Leave hit/miss out | 32.2% | 32.1% | 32.1%
False hit/miss | 32.2% | 32.2% | 32.2%
Wrong order | 32.2% | 32.0% | 32.2%
Bzip2 | 32.2% | 26.4%
Victim1 | 32.2% | 26.2%
Victim2 | 32.2% | 25.9%

We have reported key results in Sec. 6.6 on exploiting libjpeg and
reconstructing CelebA face photos. Fig. 31 reports the corresponding
qualitative evaluation results. The first column is the reference input and
the second column has images reconstructed from Pin-logged side channel traces
and Prime+Probe-logged cache side channels with no noise inserted. Each row
represents several configurations with the same intensity. Despite the
challenging noise insertion schemes, visually consistent contents (e.g.,
gender, face orientation, eyes, mouth) between the reconstructed images and
reference inputs can still be observed. When perturbing Pin-logged traces,
reconstructed images under the Round shifting scheme retain better visual
appearances, indicating better noise resilience capability. The Removal
scheme, which extensively removes records in a trace, triggers obvious quality
degradation — some perceptual contents become unaligned. Similarly, Gaussian
noise, particularly when $x=0.5$, changes the visual appearances.
Nevertheless, as we clarified in the paper, visual appearances change do not
necessarily indicate attack accuracy degradation: as reported in Table 14, we
still achieve a reasonably high attack success rates even in front of
Guarantee noise insertion. After introducing noise into cache side channels
collected by Prime+Probe (with three schemes presented in the third and fourth
rows of Fig. 31), features (e.g., hair style) in reconstructed face images are
still primarily aligned with images reconstructed without manual noise.
Moreover, increasing noise intensity only leads to negligible changes of
facial features. We interpret that these evaluations demonstrate the high
resilience of our autoencoder framework toward noisy settings. See our
discussion below in Noise Resilience Analysis. In addition, it is shown that
stressing Prime+Probe with extra workload can induce noticeable effect on the
reconstructed images. Nevertheless, many perceptual features are still
retained in the reconstructed images. Again, we view the results are generally
consistent with our quantitative evaluation results in Table 14. See Noise
Resilience Analysis below for further discussion.

Table 22 and Table 23 further present evaluation results on exploiting FFmpeg
and Hunspell. Round shifting is more effective in mitigating SCA toward text
data. We note that round shifting (especially with the High scheme) can
presumably change the “preceding words” of a to-be-predicted word and is thus
more effective in disturbing our decoder of discrete data (see Fig. 2). In
contrast, the reconstructed image and audio data are more resilient toward
round shifting. Similar to the libjpeg evaluation reported in Table 14, attack
on FFmpeg is notably undermined in front of the Removal and Gaussian noise
schemes. As clarified in Sec. 6.6, these two schemes extensively leave out or
perturb data points on the logged trace (e.g., Removal/High removes 50% of the
records on a trace), show greater influence on data reconstruction.
Nevertheless, reasonably high attack accuracy can still be achieved in the
presence of perturbed side channel traces. Manifold learning shows encouraging
resilience toward noisy inputs. In addition, as clarified in Appx. F, the
logged side channel traces are lengthy and highly sparse, where only a few
elements are informative and secret-dependent. Therefore, the inserted noise
does not necessarily break informative data points. We also report promising
results that noise on trace collected by Prime+Probe (i.e., the middle three
rows) imposes small influence in undermining our exploitation, except the
scheme False hit/miss & High on FFmpeg. The similar encouraging observations
can be found from noise introduced by three real-world workload schemes as
well.

Noise Resilience Analysis In line with our discussion on noise resilience
offered by manifold learning concept (Sec. 4.1) and neural trace encoder
(Appx. F), Sec. 6.6 and this appendix section empirically demonstrate the
noise resilience of our attack. We now discuss the noise resilience from the
empirical perspective. First, trace collected by Prime+Probe is very noisy
with high stddev; when training with such noisy traces, the autoencoder
framework is “enforced” to obtain higher generalization, but may sacrifice
some accuracy. That is, the robustness and noise resilience is indeed improved
when training with side channel records logged via Prime+Probe. Second, as
discussed in Appx. F, the logged side channel trace is generally sparse.
Suppose only “1”, denoting a cache hit $\rightarrow$ miss flip, in a logged
trace (collected by Prime+Probe) contributes to reconstructing media data,
“Leave out” only drops a small portion of 1. For “Wrong order”, since CNN is
translation-invariant (as we have introduced in Appx. F), suppose all
parameters in a kernel are $1$, and two exchanged records are in a $K\times K$
region, then the output will not change, because “convolution” is element-wise
multiplication followed by a sum function. Third, the results of FFmpeg
increase a lot on Prime+Probe but libjpeg and Hunspell decrease; this
indicates that traces collected using Prime+Probe toward FFmpeg is more
informative. Therefore, flipping $50\%$ of the records (the High scheme) will
more likely violate patterns learned by our autoencoder framework despite the
translation-invariance. This explains the accuracy drop for noise insertion
scheme False hit/miss & High. Again, suppose all parameters in a kernel are
$1$, since in most of the cases, the number of 0 is way larger than 1,
flipping records will induce a noticeable impact on the output of convolution
operations.