# Approximating Aggregated SQL Queries With LSTM Networks

Nir Regev, Lior Rokach, Asaf Shabtai  Dept. of Software and Information
Systems Engineering
Ben-Gurion University of the Negev
Be’er Sheva, Israel
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Despite continuous investments in data technologies, the latency of querying
data still poses a significant challenge. Modern analytic solutions require
near real-time responsiveness both to make them interactive and to support
automated processing. Current technologies (Hadoop, Spark, Dataflow) scan the
dataset to execute queries. They focus on providing a scalable data storage to
maximize task execution speed. We argue that these solutions fail to offer an
adequate level of interactivity since they depend on continual access to data.
In this paper we present a method for query approximation, also known as
approximate query processing (AQP), that reduce the need to scan data during
inference (query calculation), thus enabling a rapid query processing tool. We
use LSTM network to learn the relationship between queries and their results,
and to provide a rapid inference layer for predicting query results. Our
method (referred as “Hunch“) produces a lightweight LSTM network which
provides a high query throughput. We evaluated our method using twelve
datasets and compared to state-of-the-art AQP engines (VerdictDB, BlinkDB)
from query latency, model weight and accuracy perspectives. The results show
that our method predicted queries’ results with a normalized root mean squared
error (NRMSE) ranging from approximately 1% to 4% which in the majority of our
data sets was better then the compared benchmarks. Moreover, our method was
able to predict up to 120,000 queries in a second (streamed together), and
with a single query latency of no more than 2ms.

###### Index Terms:

Approximate query processing (AQP), LSTM, SQL, Supervised Learning

##  I Introduction

While Big Data opens new possibilities for extracting unprecedented insights,
this may come at the price of high processing latency and increased
computational resource requirements for answering queries over large data sets
[1]. AQP can be particularly useful for data analysts, who often need to
discover and explore large new data sets. This task requires a fast,
efficient, and cost-effective query engine and does not necessarily rely on
exact answers. In addition, when data becomes too large to fit in a single
machine, data processing platform vendors (e.g., Hadoop, Spark, Google Cloud
Dataflow) address this challenge by scaling out resources. However, this
strategy may be increasingly cost-prohibitive and could be inefficient for
large and distributed data sources [2]. As a result, it has been shown that
data exploration could be successfully performed in an approximate fashion
[3].

In this research we introduce a new method that can produce high-value
approximated results for SQL queries by training a LSTM network, without
a-priori domain knowledge, to learn the relationship between the different
elements of SQL queries and their results. Our method processes queries on
large datasets rapidly and in a fixed response time, regardless of the data
size.

We applied the proposed method on twelve data sets taken from the technology
industry. We evaluated the method predictions (approximations) using large
hold-out testing sets of queries. Our results show that the proposed solution
approximates query results within a controlled range of normalized error
(NRMSE), between 1% to 4%. In terms of execution latency, query latency (QL)
ranges from approximately 2 ms/q (millisecond per query) to 30 ms/q. We also
evaluated method performance on large batches of queries (processed in
parallel on a GPU). Our method demonstrated a query throughput (QT) of
approximately 2,000 queries per second to 120,000 queries per second,
depending on input dimension and the LSTM network architecture (number of
neurons and number of hidden layers).

In summary, the contributions of this paper are as follows:

  * •

we introduce a novel approach for producing lightweight data representation
layer in the form of a NN;

  * •

we propose an effective query processing method, with lightning-fast query
response times for big data platforms;

  * •

we present a forceful concurrent approach to process SQL queries with GPU
technology;

  * •

Finally, we make our code and datasets publicly available
@https://github.com/nirre1401/aqp.git

##  II Related Works

Query approximation by sampling. Previously, different approaches to
approximate database queries have been introduced, with the majority based on
executing queries over smart samples of data [4]. These approaches rely on the
ability to use a statistical method to deliver an approximated result within
confidence interval. While several research projects have explored the
benefits in data sampling [5], [6], [7], these methods are not widely used in
streaming engines [8, 9] with the noteworthy exception found in the SnappyData
project [10], which uses the notion of High-level Accuracy Contract (HAC),
which is also used in VerdictDB [11]. When memory is limited (as is often the
case), sampling may help to enable in-memory processing.

Interactive approximate query processing. The SnappyData [10] engine,
developed in 2015, was designed to support query approximation in streaming,
transnational, and interactive systems. It is based on many insights gained
from the BlinkDB project [12]. Spark, a contemporary distributed in-memory
data processing engine, manages smart query caching (referred to as delta
update queries) with confidence intervals utilized to minimize loss. It also
handles on-line aggregation to reduce processing latency by presenting
preliminary approximated results immediately on processing a small portion of
the whole dataset [13]. Oracle Database uses the HyperLogLog (HLL) algorithm
for approximate ‘count distinct’ operations.
Query approximation with ML. As mentioned above, the database research
community has proposed novel techniques for AQP that could give approximate
query results in orders of magnitude faster than the time needed to calculate
exact results. In this work, the usage of deep generative model, specifically
Variational auto-encoder (VAE), for answering aggregate queries specifically
for interactive applications such as data exploration and visualization[14].
Similar to our approach, this work utilized ML models to approximate
aggregated SQL queries [15]. Specifically, gradient Boosting Machines (GBM),
XGBoost and LightGBM were trained to predict the aggregated queries’ result.

TABLE I: AQP project benchmark comparison table. Paper | Name |  | Flat Query Latency
---
in sec.
(per 1Tb data)
| Guaranteed
---
Error bound
| GPU
---
Support
| Training
---
Requirement
| Preprocessing
---
/Sampling
Requirement
| Queries Batch
---
Concurrent
Processing
Support
| Result
---
Confidence
[16][17] | Hive Hadoop | 400 | no | yes | no | yes | yes | NA
[18][16] | Hive Spark | 40 | no | yes | no | yes | yes | NA
[19][12] | BlinkDB | 2 | 2-10% | no | no | yes | yes | 95%
[10][20] | SnappyData | 1.5 | NA | no | no | yes | yes | NA
[21][11] | VerdictDB | 1 | 2.6% | no | no | yes | yes | 95%
[22][23] | DICE | 0.5 | 10% | no | no | yes | no | NA
[14] | DeepGen | NA | 0.1-1.25% | yes | yes | yes | yes | No
[15] | ML AQP | 20 | 1-5% | no | yes | yes | no | NA
Our method |  | Hunch (DL)
---
AQP
10 | <2.5% | yes | yes | yes | yes | NA

##  III Proposed Method

The proposed method uses a process to generate the training set which is used
for fitting the query approximation model. This process is divided into four
phases: (1) generating artificial SQL queries (Section III-C), (2) obtaining
the labels for the training set by executing the queries on the database
(Section III-D), (3) inducing an encoder for transforming the queries into
numeric matrices (Section III-E) and finally (4) training a neural network to
approximate the queries labels (Section III-F).

###  III-A Query template and notations

As an example, assume a table ‘transactions’ that includes computer sales from
either physical or online shops. The table includes the attributes: ‘hour’
(time of transaction), the ‘store_type’ (physical or online), the
‘computer_type’, the ‘harddisk_size’ (hard disk size in Gb), and the ‘sales’
(amount in $). The method is designed to generate many instances of queries
conforming to a query template defined by the following:

  * •

$attr^{(c)}$ – denotes a continuous data attribute in the dataset (e.g.,
‘harddisk_size’).

  * •

$attr^{(n)}$ – denotes a nominal data attribute in the dataset (e.g.,
‘computer_type’, ‘store_type’).

  * •

$A=\\{a_{1},a_{2},\ ...\\}$ – denotes the set of optional aggregation
functions (e.g., avg, count).

  * •

$a_{i}(attr)$ – denotes an aggregation function $a_{i}\in A$ that is applied
on valid attribute $attr$ (either $attr^{(c)}$ or $attr^{(n)}$) in a select
query (e.g., avg(‘sales’), max(‘revenue’), or count(‘id’)).

  * •

$between_{attr^{(c)}}(l,u)$ \- a ‘between’ constraint argument defined on a
continuous data attribute $attr^{(c)}$, where $l$ is a lower bound and $u$ is
an upper bound on the values of $attr^{(c)}$.

  * •

$in_{attr^{(n)}}(v_{k})$ \- an ‘in’ constraint argument defined on a nominal
data attribute $attr^{(n)}$, where $(v_{k})$ is a single possible member of
$attr^{(n)}$.

###  III-B Support “Group By" queries with multiple aggregations

We support queries with "Group By" clause on multiple $attr^{(n)}$. This
enables flexibility in exploring and analyzing large datasets on one side, but
poses the following two challenges on the other side: (1) learning different
data distribution (characterized by the aggregation functions), and (2)
learning an output which may have varying dimensions (while NN models expects
fixed output types and dimension). The latter results from the fact that a
"Group By" query can return a table of one or more rows as shown by the
example in Table II which is the result of the following running example
query:

    SELECT computer_type, store_type,
    AVG(sales), MEDIAN(revenue)
    FROM transactions WHERE
    hour between (20 and 23) AND
    harddisk_size between (121 and 820)
    GROUP BY computer_type, store_type

To tackle these challenges, we transform each "Group By" query to multiple
‘flat’ (with no "Group By" term) queries with a single aggregation function.
These, by definition, returns one scalar. This way, every LSTM network has an
output layer which consists of a single linear output that is trained to learn
a specific aggregation function distribution.

TABLE II: An example for a group by result set. store_type | computer_type | AVG(sales) | MEDIAN(revenue)
---|---|---|---
online | MAC | 102 | 85
online | IBM | 80 | 82
phisical | MAC | 95 | 61
phisical | IBM | 94 | 50

###  III-C SQL queries generation

The goal of this phase is to generate a large representative set of aggregated
SQL queries $q_{i}$ that broadly represents the raw data.

Define query template parameters. A query template is define by the domain
expert which provides for each query template: (1) the SELECT clause
parameters, and (2) the filter template (i.e., the WHERE clause parameters).

In this phase, first, the domain expert choose a set of aggregation functions
and a set of data attributes. Then, the method constructs a SELECT clause
consisting of the selected aggregation functions, which are applied on a set
of valid data attributes, either continuous or nominal,
$\\{a_{i}(attr_{j})\\}$.
All aggregation functions can be applied on continuous data attributes,
whereas the only aggregation functions that can be applied on a nominal
attribute are ${{}^{\prime}count^{\prime}}$ and
${{}^{\prime}countDistinct^{\prime}}$. In our example, assuming the domain
expert chooses to apply all aggregation functions $A$ on all valid
$\\{a_{i}(attr_{j})\\}$, this results in the select clause:

    SELECT AVG(sales), MEDIAN(sales),
    AVG(revenue), MEDIAN(revenue)

As mentioned, each $\\{a_{i}(attr_{j})\\}$ will have a designated model (see
Section III-F) fitted to learn its distribution. This means that the training
set will be split for each $\\{a_{i}(attr_{j})\\}$ and learned separately. In
our example the first training set will consist of queries with AVG(sales) in
the select clause, the second training set will consist of queries with
MEDIAN(sales) and so on.

Next, the domain expert can choose a filter template which includes the list
of continuous data attributes $attr^{(c)}$ and nominal data attributes
$attr^{(n)}$ that can be included in each query. Then, for each
$querytemplate$ defined by the domain expert, the method generates a set of
$queryinstances$ as follows.

Generating filter. In this step, the method generates a rich set of filters
applied on (1) continuous data attributes $attr^{(c)}$ and (2) nominal data
attributes $attr^{(n)}$ in the following manner.

  1. 1.

For each $attr^{(c)}$, we calculate the intervals defined by: the minimum
value, the first quartile (25%), the median, the third quartile (75%), and
maximum value (four intervals). In order to select the lower and upper bounds
of a continuous attribute constraint $between_{attr^{(c)}}(l,u)$ we select two
intervals randomly. Then, from each selected interval, we randomly choose a
value (from a uniform distribution). This results into two numeric values
which form a filter , such that the smaller value will define the lower bound
and the larger value will define the upper bound. For instance, assume the
$harddisk\\_size$ continuous attribute values spanning from 1 to 1000. Given
those values, minimum=0, 25% quartile=250, median=500, the 75% quartile=750
and maximum=1000, and assuming the selected intervals are [0,250] and
[750,1000] the continuous constraint might take the values
$between_{harddisk\\_size}(121,820)$

  2. 2.

To construct a nominal filter, the method uses an "IN" constraint argument
defined on a nominal data attribute $attr^{(n)}$, filtered by $v_{k}$ \- a
possible member of $attr^{(n)}$. To determine which member to use in each
filter, the method constructs a "Group By" term on the nominal attribute and
once the query is executed against the dataset, the method systematically
extracts all possible combinations of members which exists in the result set
and constructs a nominal filter for each one. In our example, one combination
of members for $store\\_type$ and $computer\\_type$:

$\\{in_{store\\_type}(^{\prime}online^{\prime}),in_{computer\\_type}(^{\prime}Mac^{\prime})\\}$

  3. 3.

Finally, each of these combinations of nominal filters is paired with each of
the continuous filters to form a query filter; for example,
$\\{between_{harddisk\\_size}(121,820),\\\
in_{store\\_type}(`online^{\prime}),in_{computer\\_type}(`Mac^{\prime})\\}$.

###  III-D Obtaining labels for the training set

To build a supervised dataset for training the proposed method needs to obtain
real query results; therefore, our method runs the set of generated queries
$Q$ against the data source. As LSTM model requires a relatively large number
of training examples, the system needs to generate and execute hundreds of
thousands of queries. However, by using "Group By" queries, the actual size of
$Q$ is much smaller.

###  III-E Encoding queries

At this stage, a list of "flat" SQL queries and their real label (result) is
available. Since neural networks can take only numeric input, we encode the
queries into numeric matrices (see Figure 1) via an encoder model which is
constructed on the fly (during SQL queries generation), making use of a multi-
hot encoding technique. The reason for choosing this type of encoding is to
enable a distinctive representation for discrete data entities. That way,
entities like ‘Mac’ and ‘IBM’ will be represented by perpendicular bit-wise
vectors to signal the LSTM which entity exists in the input (query). The
encoding process starts by mapping all unique query tokens that exist in the
training set $Q$ and assigns each with a numeric sequential value, as
illustrated in Figure 1 (for example, the token avg(sales) is mapped to the
value 00001). Each numeric value is then transformed into binary (base 2)
numeric representation. Numeric query tokens (scalars) are also transformed
into their binary (base 2) representation.

Figure 1: Query encoding process: for each query token, the token encoding is
streamed into the LSTM model.

###  III-F LSTM network generation and training

At this point, the algorithm pipeline builds an LSTM network. The network
weights were initialized according to the Xavier initialization method [24].
The primary reason for choosing this architecture was related to the language
aspects of the problem, where SQL queries are treated as sentences with a
structured order of clauses and tokens. An LSTM network has proved its
efficiency in learning complex sequential data, which was our initial
motivation for selecting this architecture [25]. Upon data updates, we retrain
the LSTM from its last state on a training set consists of queries which span
on the new data.

##  IV Evaluation

###  IV-A Datasets

The system was evaluated using 12 unique data sets, both proprietary and open
source. The data sets characteristics are presented in Table III.

###  IV-B Training set partitioning

For each dataset, a training set was generated and split, using python package
sklearn ċross_validation (ṫrain_test_split), to three datasets: (1) training
set - 70% of the queries, (2) validation set - 15% and (3) testing set - 15%.

###  IV-C LSTM training cost function

The LSTM network is trained to minimize a quadratic cost function, defined as:

$MSE=\frac{1}{n}\sum^{n}_{i=1}{{\left({\hat{Y}}_{i}-\ Y_{i}\right)}^{2}}\ $
(1)

where $Y_{i}$ is the real query result, ${\hat{Y}}_{i}$ is the model
approximated query result, and $n$ is the batch size.

TABLE III: Datasets characteristics. | Dataset |  | Proprietary
---
data source
| Target
---
function
| #
---
$attr^{(n)}$
| #
---
$attr^{(c)}$
| # rows
---
| #
---
queries
| Mean
---
Entropy
| Input
---
Tensor
variance
| Target
---
column STD
1 | average_revenue | Yes |  | avg
---
(revenue)
3 | 2 | 1000000000 | 5205078 | 6.293 | 0.154 | 40400000
2 |  | average_success
---
_rate
Yes |  | avg
---
(build_time)
2 | 3 | 2333293 | 415791 | 2.264 | 5.421 | 19.196
3 |  | count_product
---
_pass
Yes |  | count
---
(machine_id)
1 | 5 | 4000000000 | 811928 | 0.942 | 0.151 | 2350516
4 |  | count_product
---
_fail
Yes |  | count
---
(machine_id)
1 | 5 | 95484 | 451173 | 0.942 | 0.153 | 8613
5 |  | count_product_
---
false_calls
Yes |  | count
---
(machine_id)
1 | 5 | 350232 | 378111 | 0.942 | 0.202 | 215315
6 |  | count_churn_
---
customers
Yes |  | count
---
(customer_id)
4 | 3 | 9263836 | 62092 | 2.782 | 0.13267 | 530
7 |  | sum_duration_
---
call
Yes |  | sum
---
(duration)
3 | 2 | 9349 | 100000 | 3.198 | 0.167 | 861
8 |  | average_ibm
---
_price
No |  | avg
---
(close_price)
1 | 2 | 1048575 | 340489 | 0.343 | 0.125 | 471
9 |  | average_realestate
---
_price
No |  | avg
---
(price)
3 | 2 | 22489348 | 508086 | 2.113 | 0.105 | 236
10 |  | avg_stock_close
---
_price
No |  | avg
---
(close_price)
2 | 1 | 63267 | 8721 | 5.703 | 0.157 | 118
11 |  | average_paid
---
_days
Yes |  | avg
---
(actual_paid
_days)
3 | 2 | 100000000 | 508365 | 0.451 | 0.099 | 25667553
12 |  | average_build_
---
duration
Yes | avg(duration) | 1 | 3 | 22276094 | 325935 | 0.993 | 0.129 | 7487

###  IV-D Evaluation metrics

Since the target variable (query result) is continuous, a simple regression
cost function such as MSE or RMSE can yield an unnormalized range of values
and is greatly influenced by the problem scale.
For this reason, we have chosen a normalized version of RMSE (NRMSE), defined
as follows:

$RMSE=\sqrt{\frac{\sum^{n}_{i=1}{{({\hat{Y}}_{i}-\ Y_{i})}^{2}}}{n}}\ $ (2)

where $i$ represent a query from testing set, $Y_{i}$ is the real query
result, ${\hat{Y}}_{i}$ is the model approximated query result, and $n$ is
number of testing set queries.

$NRMSE=\frac{RMSE}{Y_{max}-\ Y_{min}}$ (3)

where $Y_{max}$ is the max query result and $Y_{min}$ is the min query result.
Normalizing the RMSE facilitates the comparison between data sets with
different scales.
In addition, we calculated $QL$ – the duration of a single query execution in
milliseconds, as well as the queries throughput at batch mode (using GPU),
referred to as $QT$ and measured as follows:

$QT=\frac{T}{Q}$ (4)

where $\mathrm{\ }T$ is the total latency of the batch mode prediction
operation and $Q$ is the number of queries used in the testing set.

Lastly we calculate $ME$ mean entropy $\overline{\mathrm{H}}$ for data set
predictors (all columns in where clause), while for each categorical column
entropy is calculated as:

$\mathrm{H}\left(\mathrm{X}\right)\mathrm{=\
-}\sum^{n}_{i\mathrm{=1}}{P\mathrm{(}X_{i}}\mathrm{)}{Log}^{P\mathrm{(}X_{i}\mathrm{)}}_{\mathrm{2}}$

Where
$\mathrm{\ }i$ varies from 1 to n – number of distinct values for a
categorical column and

${P\mathrm{(}X}_{i}\mathrm{)}$ – is the number of rows containing value $i$
divided by total number of rows. For continuous columns, we first discretize
them to categorical columns using 10 equal-length bins and then use the above
entropy calculation. We chose 10 bins to allow enough bins to capture the
column variance, but not so many as to prevent reasonable calculation time.

$\overline{\mathrm{H}}=\ \frac{\sum^{M}_{j=1}{{H(X)}_{j}}}{M}$

Finally, we calculated the LSTM input layer variance using Tensorflow moments
111https://www.tensorflow.org/api_docs/python/tf/nn/moments.

Data complexity which is expressed by the data mean entropy $ME$, target
column STD (standard deviation) determine the problem complexity and
influences how well and how quick the LSTM can learn the data converge.
According to these measures, we have configured a hyper-parameters heuristic
that we found, by trial and error, to be effective.

###  IV-E DNN training cost function

The DNN is trained to minimize a quadratic cost function, which is also known
as mean squared error, maximum likelihood, and sum squared error, defined as:

$MSE=\frac{1}{n}\sum^{n}_{i-1}{{\left({\hat{Y}}_{i}-\ Y_{i}\right)}^{2}}\ $
(5)

$Y_{i}$ – real query result

${\hat{Y}}_{i}$ – model approximated query result

$n$ – batch size

Baseline methods and metrics. We have chose three baseline methods: (1)
VerdictDB [11], a novel AQP method which accelerates analytical queries and
(2) BlinkDB [12] \- an approximate query engine for running interactive SQL
queries on large volumes of data. We use mean query latency (QL) and NRMSE
metrics to evaluate performance and accuracy respectively.

###  IV-F Experiment Results

For each data set, Table IV specifies LSTM network training parameters and the
trained model performance metrics.

TABLE IV: Datasets models performance and accuracy metrics. | LSTM architecture and hyper-parameters | Model performance
---|---|---
# | Dataset name | LR | Batch size |  | LSTM
---
neurons
| Dense
---
Neurons
| input
---
shape
GPU Type |  | QT
---
(q/s)
| QL
---
(ms/q)
NRMSE |  | LSTM
---
size (Mb)
1 | average_revenue | 1.E-05 | 2048 | 512 | 200 | (7,17) | GTX 2060 | 25501 | 2.79 | 1.57 | 3.51
2 | average_success_rate | 1.E-02 | 1024 | 128 | 200 | (7,17) | GTX 2060 | 43512 | 2.55 | 3.75 | 2.51
3 | count_product_pass | 1.E-04 | 2048 | 512 | 400 | (16,18) | GTX 2060 | 1881 | 27.41 | 0.07 | 3.84
4 | count_product_fail | 1.E-03 | 1024 | 512 | 400 | (16,18) | AWS K80 | 6185 | 28.60 | 0.51 | 3.84
5 |  | count_product_false
---
_calls
1.E-04 | 1024 | 512 | 400 | (16,18) | AWS K80 | 1889 | 28.2 | 0.12 | 3.84
6 |  | count_churn_
---
customers
1.E-02 | 2048 | 128 | 200 | (17,17) | AWS K80 | 21304 | 3.55 | 0.14 | 2.56
7 | sum_duration_all | 1.E-02 | 128 | 256 | 200 | (7,20) | GTX 2060 | 1877 | 2.84 | 0.01 | 2.58
8 | average_ibm_price | 1.E-02 | 128 | 256 | 200 | (7,62) | AWS K80 | 26667 | 3.29 | 0.61 | 2.91
9 |  | average_realestate
---
_price
1.E-02 | 1024 | 128 | 200 | (13,61) | GTX 2060 | 76086 | 2.81 | 0.32 | 2.9
10 |  | avg_stock_close
---
_price
1.E-02 | 2048 | 128 | 200 | (6,61) | GTX 2060 | 121259 | 4.03 | 0.17 | 2.9
11 | average_paid_days | 1.E-05 | 2048 | 128 | 200 | (27,7) | AWS k80 | 62046 | 2.05 | 0.97 | 2.63
12 |  | average_build
---
_duration
1.E-04 | 1024 | 256 | 200 | (10,32) | GTX 2060 | 12159 | 4.01 | 0.15 | 2.74

Accuracy. As expected, NRMSE for the largest model (dataset #5) with 512 LSTM
neurons layer and a dense layer with 400 neurons, was the smallest (most
accurate) with a value of 0.12 while for the smallest model (dataset #6) with
128 LSTM neurons layer and a dense layer with 200 neurons, was the largest
with a value of 3.75. Query latency performance. Using GPU, a throughput (QT)
of approximately 121k queries per second was measured, while a single query
latency (QL) for our largest (slowest) model lasted 28 ms. Generally and as
can be expected, as the LSTM network is more complex (more layers, more
neurons, larger input), latency goes up and throughput goes down.

Baseline comparison results. Figure 3 and Figure 3 depicts the accuracy and
latency of Hunch and baseline methods - VerdictDB [11], and BlinkDB [12] on
all datasets. Figures 5 show a paired T-test analysis to determine whether our
method were found statistically better than the compared methods in terms of
accuracy (NRMSE) and query latency. From these figure, although it is evident
that our method was better the majority of data sets (both on the accuracy and
latency plots), statistically one cannot claim one method is superior to the
other.

Figure 2: Comparing the accuracy (NRMSE) performance of Hunch Verdict and
Blink).

Figure 3: Comparing the latency performance of Hunch with Verdict and Blink).

Figure 4: T-test analysis comparing Hunch with Verdict and Blink on NRMSE

Figure 5: T-test analysis comparing Hunch with Verdict and Blink latency
metric.

###  IV-G Discussion

Our proposed solution predicts query results within a controlled accuracy
(NRMSE), ranging between approximately 1% to 4%. QL ranges from approximately
2.0 ms/q to 30.0 ms/q for a single query. Moreover, for large datasets (20M -
4B records), our method is two orders of magnitude faster from the compared
methods. In batch mode (utilizing GPU batch processing) the method was capable
of calculating results at up to 120,000 queries per second. These encouraging
results led us to consider this solution as a novel query approximation tool,
capable of saving heavy-lifting database processing and data transfer from the
consumer to the database and back. Our method can predict missing data points
and data points that span in the future. For instance, when the system was
trained on temporal dimensions (e.g., dates in where clause), our 10th dataset
(named avg_stock_close in Table III) results shows a NRMSE of approximately
0.2% for testing set with future dates (which were not available during
training). Comparing our method to other state-of-the-art AQP methods, our
method is resilient to growing scale of datasets (2M rows). This is because
our method uses the LSTM network to calculate SQL query’s result and is
decoupled from the dataset after training process is done.

Although statistically we have not established supremacy of our method over
the compared methods in terms of accuracy and latency, we do believe our
method has the advantage of being lean (3Mb in average), thus enabling light
and rapid deployment on client production sites and end devices such as
cellular phones and tablets. This could be particularly useful since once our
model is deployed on such device, it can run queries on very large data sets
without relying on internet connection.

The shortcomings of our method are as follow : (1) the limited query structure
model which currently does not support join, exist operation and other sub-
queries operations. This limitation can be mitigated by persisting a join
query as a prepossessing step. (2) Changes in data sets. When new data is
appended, it requires retraining the LSTM from the last training checkpoint
(network state) with queries that are relevant to new data records. The
operation of retraining the LSTM requires significantly lower efforts and is
speculated to last only a fraction of the first LSTM training time.

##  V Conclusion and Future Research

The primary goal of this research was to develop a novel approach for AQP over
massive datasets. A secondary goal was to show how our method can serve as an
interactive analytical tool, demonstrating rapid responses processing a
queries on large datasets. Existing querying methods require ongoing access to
the underlying data. Once training is done, our proposed method does not
require online connection to the data to approximate SQL queries. This opens
up an array of potential use cases for big data analytics. Going forward, we
aim to develop our method to scenarios where dataset changes frequently, thus
the model should adapt more quickly to new data. In addition, we plan to
enrich the method to support additional SQL operations. 222Sisense®, and
Hunch™ are trademarks of Sisense Ltd. All other trademarks are property of
their respective owners. The Hunch Platform and additional products not listed
here are covered by US and foreign patents. Additional patent applications may
be pending.

## Acknowledgement

We want to thank Dr. Guy Levy-Yurista and Mr. Adi Azaria for supporting and
mentoring this project as their management, encouragement, suggestions and
comments were insightful and invaluable. We also want to thanks Sisense Ltd.
for hosting and supporting this research and all the required resources.

## References

  * [1] S. Chaudhuri, B. Ding, and S. Kandula, “Approximate query processing: No silver bullet,” in _Proceedings of the 2017 ACM International Conference on Management of Data_ , 2017, pp. 511–519.
  * [2] U. Sivarajah, M. M. Kamal, Z. Irani, and V. Weerakkody, “Critical analysis of big data challenges and analytical methods,” _Journal of Business Research_ , vol. 70, pp. 263–286, 2017.
  * [3] D. Ślęzak, R. Glick, P. Betliński, and P. Synak, “A new approximate query engine based on intelligent capture and fast transformations of granulated data summaries,” _Journal of Intelligent Information Systems_ , vol. 50, no. 2, pp. 385–414, 2018.
  * [4] B. Mozafari and N. Niu, “A handbook for building an approximate query engine.” _IEEE Data Eng. Bull._ , vol. 38, no. 3, pp. 3–29, 2015.
  * [5] A. Bagchi, A. Chaudhary, D. Eppstein, and M. T. Goodrich, “Deterministic sampling and range counting in geometric data streams,” _ACM Transactions on Algorithms (TALG)_ , vol. 3, no. 2, pp. 16–es, 2007.
  * [6] B. Babcock, M. Datar, and R. Motwani, “Sampling from a moving window over streaming data,” in _2002 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002)_. Stanford InfoLab, 2001.
  * [7] K.-t. Chuang, H.-l. Chen, and M.-s. Chen, “Feature-preserved sampling over streaming data,” _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , vol. 2, no. 4, pp. 1–45, 2009.
  * [8] B. Chandramouli, J. Goldstein, M. Barnett, R. DeLine, D. Fisher, J. C. Platt, J. F. Terwilliger, and J. Wernsing, “Trill: A high-performance incremental query processor for diverse analytics,” _Proceedings of the VLDB Endowment_ , vol. 8, no. 4, pp. 401–412, 2014.
  * [9] M. Zaharia, T. Das, H. Li, T. Hunter, S. Shenker, and I. Stoica, “Discretized streams: Fault-tolerant streaming computation at scale,” in _Proceedings of the twenty-fourth ACM symposium on operating systems principles_ , 2013, pp. 423–438.
  * [10] J. Ramnarayan, B. Mozafari, S. Wale, S. Menon, N. Kumar, H. Bhanawat, S. Chakraborty, Y. Mahajan, R. Mishra, and K. Bachhav, “Snappydata: A hybrid transactional analytical store built on spark,” in _Proceedings of the 2016 International Conference on Management of Data_ , 2016, pp. 2153–2156.
  * [11] Y. Park, B. Mozafari, J. Sorenson, and J. Wang, “Verdictdb: Universalizing approximate query processing,” in _Proceedings of the 2018 International Conference on Management of Data_ , 2018, pp. 1461–1476.
  * [12] S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica, “Blinkdb: queries with bounded errors and bounded response times on very large data,” in _Proceedings of the 8th ACM European Conference on Computer Systems_ , 2013, pp. 29–42.
  * [13] K. Zeng, S. Agarwal, A. Dave, M. Armbrust, and I. Stoica, “G-ola: Generalized on-line aggregation for interactive analysis on big data,” in _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data_ , 2015, pp. 913–918.
  * [14] S. Thirumuruganathan, S. Hasan, N. Koudas, and G. Das, “Approximate query processing for data exploration using deep generative models,” in _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 2020, pp. 1309–1320.
  * [15] F. Savva, C. Anagnostopoulos, and P. Triantafillou, “Ml-aqp: Query-driven approximate query processing based on machine learning,” _arXiv preprint arXiv:2003.06613_ , 2020.
  * [16] S. Agarwal, A. P. Iyer, A. Panda, S. Madden, B. Mozafari, and I. Stoica, “Blink and it’s done: interactive queries on very large data,” _ACM_ , 2012\.
  * [17] T. Dokeroglu, S. Ozal, M. A. Bayir, M. S. Cinar, and A. Cosar, “Improving the performance of hadoop hive by sharing scan and computation tasks,” _Journal of Cloud Computing_ , vol. 3, no. 1, p. 12, 2014.
  * [18] B. Todor, Ivanov; Max-Georg, “Evaluating hive and spark sql with bigbench,” _Arxiv.org_ , 2016.
  * [19] S. Agarwal, H. Milner, A. Kleiner, A. Talwalkar, M. Jordan, S. Madden, B. Mozafari, and I. Stoica, “Knowing when you’re wrong: building fast and reliable approximate query processing systems,” in _Proceedings of the 2014 ACM SIGMOD international conference on Management of data_ , 2014, pp. 481–492.
  * [20] B. Mozafari, J. Ramnarayan, S. Menon, Y. Mahajan, S. Chakraborty, H. Bhanawat, and K. Bachhav, “Snappydata: A unified cluster for streaming, transactions and interactice analytics.” in _CIDR_ , 2017.
  * [21] W. He, Y. Park, I. Hanafi, J. Yatvitskiy, and B. Mozafari, “Demonstration of verdictdb, the platform-independent aqp system,” in _Proceedings of the 2018 International Conference on Management of Data_ , 2018, pp. 1665–1668.
  * [22] P. Jayachandran, K. Tunga, N. Kamat, and A. Nandi, “Combining user interaction, speculative query execution and sampling in the dice system,” _Proceedings of the VLDB Endowment_ , vol. 7, no. 13, pp. 1697–1700, 2014\.
  * [23] N. Kamat, P. Jayachandran, K. Tunga, and A. Nandi, “Distributed and interactive cube exploration,” in _2014 IEEE 30th International Conference on Data Engineering_. IEEE, 2014, pp. 472–483.
  * [24] K. Young-Man, K. Yong-woo, C. Dong-Keun, and M.-J. Lim, “The comparison of performance according to initialization methods of deep neural network for malware dataset,” _International Journal of Innovative Technology and Exploring Engineering (IJITEE)_ , 2019.
  * [25] Z. C. Lipton, J. Berkowitz, and C. Elkan, “A critical review of recurrent neural networks for sequence learning,” _arXiv preprint arXiv:1506.00019_ , 2015.


# Assessing the Impact of Distribution Shift on Reinforcement Learning
Performance

Ted Fujimoto1 Joshua Suetterlein1 Samrat Chatterjee1,2 Auroop Ganguly2,1
1Pacific Northwest National Laboratory 2Northeastern University Corresponding
Author<EMAIL_ADDRESS>
###### Abstract

Research in machine learning is making progress in fixing its own
reproducibility crisis. Reinforcement learning (RL), in particular, faces its
own set of unique challenges. Comparison of point estimates, and plots that
show successful convergence to the optimal policy during training, may
obfuscate overfitting or dependence on the experimental setup. Although
researchers in RL have proposed reliability metrics that account for
uncertainty to better understand each algorithm’s strengths and weaknesses,
the recommendations of past work do not assume the presence of out-of-
distribution observations. We propose a set of evaluation methods that measure
the robustness of RL algorithms under distribution shifts. The tools presented
here argue for the need to account for performance over time while the agent
is acting in its environment. In particular, we recommend time series analysis
as a method of observational RL evaluation. We also show that the unique
properties of RL and simulated dynamic environments allow us to make stronger
assumptions to justify the measurement of causal impact in our evaluations. We
then apply these tools to single-agent and multi-agent environments to show
the impact of introducing distribution shifts during test time. We present
this methodology as a first step toward rigorous RL evaluation in the presence
of distribution shifts.

##  1 Introduction

The field of RL has enjoyed some spectacular recent advancements, like
reaching superhuman levels at board games (Silver et al., 2016, 2018; Bakhtin
et al., 2022), sailboat racing (McKinsey and Company, 2021), multiplayer poker
(Brown and Sandholm, 2019), and real-time strategy games (Berner et al., 2019;
Vinyals et al., 2019). Transitioning RL toward a rigorous science, however,
has been a more complicated journey. Like other fields in machine learning,
progress in RL might be compromised by a lack of focus on reproducibility
combined with more emphasis on best-case performance. To remedy this problem,
reliability metrics have been proposed to improve reproducibility by making RL
evaluation more rigorous. Some examples include the dispersion and risk of the
performance distribution (Chan et al., 2020), and interquartile mean with
score distributions (Agarwal et al., 2021). Past work, however, does not
assume the presence of distribution shift during test time.

In general, distribution shift in machine learning occurs when there is a
difference between the training and test distributions, which can
significantly impact performance when the machine learning system is deployed
in the real world (Koh et al., 2021). In supervised learning, distribution
shift could cause a decrease in accuracy. We will focus on distribution shift
in RL, which could cause a decline in expected returns. This impact on
performance is a symptom of overfitting in deep RL, which is a problem that
requires carefully designed evaluation protocols for detection (Zhang et al.,
2018). While there are many types of distribution shift, we will focus on
test-time adversarial examples and the introduction of new agents in multi-
agent ad hoc teamwork.

Taking inspiration from car crash tests and safety ratings from trusted
organizations, like the National Highway Traffic Safety Administration
(NHTSA), we believe RL would benefit from techniques that evaluate robust
performance after training. Here, we contribute some recommendations for
evaluation protocols for RL agents that encounter distribution shift at test
time. Specifically, we recommend (1) the comparison of time series forecasting
models of agent performance, (2) using prediction intervals to capture the
distribution and uncertainty of future performance, and (3) counterfactual
analysis when distribution shift has been applied by the experimenter. We
believe this stress-test methodology is a promising start towards reliable
comparison of pretrained RL agents exposed to distribution shift in both
single and multi-agent environments.

In section 2, we mention past related work on distribution shift and RL
reproducibility. In section 3, we argue why time series analysis is needed for
evaluation of RL algorithms under distribution shift. In section 4, we outline
our recommendations for RL evaluation with time series analysis. In section 5,
we provide examples of such analyses in single and multi-agent RL. In section
6, we conclude with suggestions for future research in RL evaluation and
describe how it can advance ML safety and regulation.

##  2 Related Work

Distribution (or dataset) shift occurs when the data distribution at training
time differs from the data distribution at test time (Quinonero-Candela et
al., 2008). The focus of this paper is not to detect distribution shift
(Rabanser et al., 2019), but to assume it exists while measuring agent
performance. There has been work on reproducibility under distribution shift
for supervised learning (Koh et al., 2021), but RL will be the focus here. In
particular, we focus on how overfitting to the training environment can affect
the agent’s performance during evaluation in a test environment (Zhang et al.,
2018). Although we are taking a time series perspective in this paper, we are
not proposing a new method of machine learning to train time series models
(Ahmed et al., 2010; Masini et al., 2023). Furthermore, we are not proposing a
method of causal machine learning (Peters et al., 2017). That is, we are not
advocating a model that learns causal representations. Furthermore, we do not
claim to be the first to use interventions in simulations for RL, or other
areas of machine learning (Ahmed et al., 2021; Lee et al., 2021; Verma and
Srivastava, 2021; Lee et al., 2023; Verma et al., 2023). We contribute a
methodology that includes counterfactual time series analysis, using the
impact visualization strategy from Brodersen et al. (2015), as a way to
measure the impact of distribution shift after training. We will use time
series and counterfactual analysis only as methods of RL performance
evaluation.

Any distribution shift can be used in our methodology. Due to the interest and
research progress in adversarial attacks and ad hoc teamwork, the distribution
shifts we investigate are adversarial attacks on images (Atari game
observations) and agent switching in multi-agent environments. There has been
extensive research on adversarial attacks on supervised learning models, like
support vector machines and neural networks (Huang et al., 2011; Biggio et
al., 2012; Goodfellow et al., 2014; Kurakin et al., 2016). While we will focus
on the adversarial attacks proposed in Huang et al. (2017), there has been
related research on adversarial attacks in single-agent (Kos and Song, 2017;
Pattanaik et al., 2017; Rakhsha et al., 2020; Zhang et al., 2020), and multi-
agent RL (Gleave et al., 2019; Ma et al., 2019; Figura et al., 2021; Fujimoto
et al., 2021; Casper et al., 2022; Cui et al., 2022). Another set of
experiments will test the ad hoc teamwork of the group of agents (Stone et
al., 2010; Barrett and Stone, 2015; Rahman et al., 2021; Mirsky et al., 2022),
where agent switching will be treated as a distribution shift among the group.

Rigorous evaluation of RL algorithms is still a topic that requires further
investigation. Henderson et al. (2018) show that even subtle differences, like
random seeds and code implementation, can affect the training performance of
deep RL agents. Engstrom et al. (2020) give a more thorough study of RL
implementation and provide evidence that seemingly irrelevant code-level
optimizations might be the main reason why Proximal Policy Optimization
(Schulman et al., 2017) tends to perform better than Trust Region Policy
Optimization (Schulman et al., 2015). Colas et al. (2018) show how the number
of random seeds relates to the probability of statistical errors when
measuring performance in the context of deep RL. The inherent brittleness in
current deep RL algorithms calls into question the reproducibility of some
published results. This has led to proposals for rigorous and reliable RL
evaluation techniques grounded in statistical practice. Chan et al. (2020)
recommended reliability metrics like interquartile range (IQR) and conditional
value at risk (CVaR). Jordan et al. (2020) suggested metrics like performance
percentiles, proposed a game-theoretic approach to quantifying performance
uncertainty, and developed a technique to quantify the uncertainty throughout
the entire evaluation procedure. Agarwal et al. (2021) recommended stratified
bootstrap confidence intervals, score distributions, and interquartile means.
For multi-agent cooperative RL, Gorsane et al. (2022) proposed a standard
performance evaluation protocol using RL recommendations from past papers.
What sets our methodology apart from past work is the emphasis on time series
analysis of RL performance with distribution shift during test time. Chan et
al. (2020) has included after learning metrics in their work, but focuses on
performance variability from trained policy rollouts alone, which is unlikely
to capture performance in the presence of significant environment changes.

##  3 The Need to Measure Performance Over Time

###  3.1 A Time Series Perspective

We argue for time series analysis as a solution to the problems that point
estimates and confidence intervals alone cannot fix. Because we are not
certain of the agent’s future performance, forecasting it is needed if we
assume the training and test environments are not identical. Point estimates
alone can fail to explain decreases in performance at test time. In Figure 1,
we assume three agents that act in an environment experience increasing
distribution shift as the number of episodes continues. All agents achieve the
same average returns, but there is a clear difference in performance over
time. In this hypothetical example, Agent 3 seems to have overfit to the
training environment because it starts high but ends as the lowest performer.
In the longer term, Agent 2 is preferable because its decrease in performance
is slower, and eventually outperforms Agent 3. Agent 1 represents the ideal RL
agent because its performance over time never decreases.

Figure 1: In this simplified plot of agent performance in the presence of
worsening distribution shifts over time. All three agents have average returns
of 10. It is clear, however, that agent 3 is the least desired agent over
time. Even though agent 3 starts out with the highest average returns, it
seems to have overfit to the training environment and fails to maintain its
superior performance. Point estimates alone would not capture this behavior.

Within-episode performance is difficult to measure because it requires
knowledge of the particular environment’s states to know when to make an
intervention. To make our methodology more general, we measure the impact of
distribution shift over many episodes, where $X^{A}(t)$ is the expected
performance at an episode $t$. This allows us to measure the positive (or
negative) impact of distribution shifts over time. An example of this could be
measuring the energy usage or customer satisfaction of a RL-trained HVAC
system each day over a week if exposed to distribution shift.

###  3.2 RL and the Fundamental Problem of Causal Inference

Practitioners of causal inference must remember its fundamental problem: If we
were to expose a unit $u$ to some intervention, we will never see the world
where we never exposed the unit $u$ to that intervention (Holland, 1986). That
is, observing individual treatment effect is impossible. This has not
discouraged researchers from developing methods that circumvent this problem
(Spirtes et al., 2000; Pearl, 2009; Imbens and Rubin, 2015; Peters et al.,
2017). These methods usually require assumptions that manage the messiness of
the real world, which makes it possible to construct valid arguments in favor
of causal inference. RL agents in simulated environments, however, allow us to
make assumptions that might be too strong for less predictable units (like
humans or animals). In a deterministic environment, with a given random seed,
regardless of how many times you reach a state $s$, the agent will choose the
same action and receive the same reward at state $s$. That is, RL agents in
deterministic environments with fixed random seeds allow us to see what
happens when we choose to intervene or not. This does not contradict Henderson
et al. (2018), where they argue that different random seeds can lead to
different performances and behaviors. Here, we claim that different RL agents
with their own random seed may exhibit different behaviors, but will repeat
those fixed behaviors. Now that we are concerned with RL evaluation over time,
we can make the following assumption:

######  RL Fixed Seed Assumption 3.1.

Let $T$, such that $1\leq T\leq N$, be the time an intervention occurs. Let
$G$ designate groups such that $G=1$ indicates the treatment group and $G=0$
indicates the control group. Consider a time series outcome $X^{A}(t)$, where
$A$ is a RL agent in a simulated deterministic environment $\mathcal{M}$. Let
$X^{A}(t<T)$ be the performance before time T. Then,

$\mathbb{E}[X^{A}(t<T)|G=1]=\mathbb{E}[X^{A}(t<T)|G=0]$ (1)

Let $X_{U=u}^{A}(t)$ be the performance measurement as above with the
counterfactual intervention $U=u$. We define $U=1$ and $U=0$ as being exposed
to an intervention (e.g., distribution shift) and not exposed, respectively.
Then, on average, the performance of the control group is the counterfactual
performance of the treatment group as if it had not been exposed to the
intervention:

$\mathbb{E}[X^{A}(t)|G=0]=\mathbb{E}[X_{U=0}^{A}(t)|G=1]$ (2)

This assumption basically says that if we have a fixed set of random
seeds111Reproducibility can be difficult to achieve when running on a GPU. We
discuss this further and how to control for it in the Appendix. in a
deterministic environment, then the expected returns of the control group is
the same as the expected returns of the counterfactual treatment group where
no out-of-distribution intervention ever occurred. This makes intuitive sense
because both groups will exhibit identical behavior in deterministic
environments if no outside influence is introduced. This is helpful when
justifying causal inference in the Appendix.

##  4 Recommendations for Time Series Evaluation

###  4.1 If you can control when the distribution shift occurs, measure the
causal impact

Similar to car crash tests in controlled settings, we propose an evaluation
method where the experimenter can control when a RL agent experiences a shift
in distribution. First, take a trained RL agent and have it interact in its
environment until some time (or episode) $T$, which will be the pre-treatment
period. At time $T$, the post-treatment period starts with the experimenter
applies a shift in distribution. Such distribution shifts include adversarial
examples (Goodfellow et al., 2014). In the multi-agent cooperative tasks,
sudden replacement of agents can also cause shifts in distribution (Mirsky et
al., 2022). The experimenter logs the performance scores at each point in
time. When the agent reaches the end of the experiment, evaluate the causal
impact from the counterfactual model (the RL agent control group) and the
treatment group’s post-treatment performance using difference-in-differences
(DiD) (Cunningham, 2021; Huntington-Klein, 2021). The results will show how
much the distribution shift impacted the performance of the agent assuming a
counterfactual model that represents the agent’s performance if the
distribution shift never happened. We will assume the trained agents have
achieved a flat (slope = 0) trend in raw performance (as opposed to noisy or
random) in the absence of distribution shift at test time.

To show the impact of the distribution shift, we use the template of time-
series impact plots from Brodersen et al. (2015). This template consists of
three panels: an original plot, a pointwise plot, and a cumulative plot. In
the original plot, the raw performance is shown. The pointwise plot shows the
difference between the observed data and the counterfactual predictions, which
is the inferred causal impact of intervention. The cumulative plot shows the
cumulative impact of the intervention over time. Instead of Brodersen et al.’s
choice of using Bayesian structural time-series models, we use DiD because we
are measuring only one variable (returns). The justification for DiD in this
methodology is provided in the methods section of the Appendix.

###  4.2 Otherwise, compare agents using simple time series trends with
prediction intervals

Figure 2: Left: The differences in performance are clear because the
prediction intervals do not overlap at the end of the plot. Hence, Agent 1 has
the best performance because the forecast is not decreasing and the prediction
interval is small. Right: Here, all agents have noisier performance. Even
though Agent 3 still has a downward trend, it briefly spikes up to match Agent
1’s performance. Hence, we want prediction intervals that anticipate this
uncertainty by showing interval overlap between agent performance over time.
There is no longer a significant difference between Agents 2 and 3 because
their prediction intervals overlap at every time step.

Here, we assume the experimenter has no control over when the distribution
shift will occur. It is also possible that distribution shift may not occur at
certain times. Such scenarios are intended to be a closer representation of
real-world RL agent deployment. This implies, without further assumptions, an
observational study is the best we can do. If we want to account for the
uncertainty of the performance trends, it would be preferable to understand
the distribution of values and where we expect our forecasting model to
generate the next data point sampled (Buteikis, 2020). We propose comparison
of RL performance using time series trends, like Holt’s Linear Damped Trend
Method (Gardner Jr and McKenzie, 1985; Holt, 2004; Hyndman and Athanasopoulos,
2018), with prediction intervals. An example is provided in Figure 2. Here, we
can compare the performance of agents trained on different RL algorithms. The
idea behind these graphs is the same as in Figure 1. The main differences are
that we use time series forecasts and prediction intervals to show the
predicted performance trend of each agent. Here, the performances between
episodes 0-50 are the measured performances of the agents in the environment.
The plots at episodes 50-100 are not measured performance, but prediction
trends of future performance with prediction intervals. This visualizes robust
performance by showing uncertainty in predicted average returns over time.
Ideally, the agent that performs the best would have the highest trend line
and the smallest prediction interval. Using time series forecasts with
prediction intervals are meant to be an improvement over point estimates with
confidence intervals to better show uncertainty in predicted average returns
over time. Since we will be using Holt’s linear damped trend method, 95%
prediction intervals might be too narrow (Hyndman, 2014). Hence, we will
default to 99% prediction intervals. Like in section 3, we interpret each time
point as an episode, and $X^{A}(t)$ represents the RL agent’s performance
during that episode. Further description of this method is provided in the
methods section of the Appendix.

In a style similar to Gorsane et al. (2022), we summarize the previous
recommendations into the following protocol:

A Protocol for Measuring Performance in the Presence of Distribution Shift
Input: Environments $E_{1}\dots E_{K}$, Algorithms $A_{1}\dots A_{M}$ with
corresponding time series metric $X^{A}(t)$, Distribution Shifts $d_{1}\dots
d_{N}$. 1\. Evaluation parameters - defaults • Number of episodes for impact
and observational plots. • Number of episodes for forecasting with prediction
intervals ($=100$). • Number of random seeds/runs ($=10$ from Agarwal et al.
(2021)). 2a. If you can control when the distribution shift occurs, measure
the causal impact • Measure the causal impact of each distribution shift
intervention $d_{n}$ using difference-in-differences with plots of the (i) raw
performance, (ii) pointwise impact, and (iii) cumulative impact (from
Brodersen et al. (2015)). • For each pair $(E_{k},d_{n})$, algorithm $A_{i}$
performs better than $A_{j}$ in the presence of $d_{n}$ if $A_{i}$’s
cumulative impact of average returns is higher than $A_{j}$’s at the end of
the experiment. 2b. Otherwise, compare agents using time series trends with
prediction intervals • In the presence of a distribution shift, plot a
forecast, using Holt’s Linear Damped Trend Method, with 99% prediction
intervals over 100 episodes after the last measured performance (from Holt
(2004)). • For each pair $(E_{k},d_{n})$, algorithm $A_{i}$ achieves
significantly higher trend in performance than $A_{j}$ in the presence of
$d_{n}$ if $A_{i}$ has a higher forecast prediction line than $A_{j}$ with no
overlap between the corresponding prediction intervals. 3\. Reporting •
Experiment Parameters: Report all distribution shift implementations,
hyperparameters, code-level optimizations, computational requirements, and
framework details. • Plots: For each environment $E_{1}\dots E_{K}$, create
plots from 2a or 2b (preferably both) for each algorithm $A_{1}\dots A_{M}$ in
the presence of distribution shifts $d_{1}\dots d_{N}$. • Analysis: Provide
analysis for the plots and derive conclusions.

##  5 Examples of RL Time-series Analysis

In our time series evaluation, we model the scenario as deploying the agent(s)
out in the intended environment. In this scenario, we have the pretrained
agents run over a number of episodes. As mentioned previously, the causal
impact procedure can be interpreted as the RL version of car crash tests,
where RL agent(s) are deployed in a controlled environment and undergo
repeated performance testing. When evaluating the causal impact of the
distribution shift, we introduce the shift at the halfway point. We measure
the performance of the treatment and control groups, then measure the
difference and cumulative impact of the shift. In both single and multi-agent
settings, we use the causal impact plot template from Brodersen et al. (2015).

In the observational case, we can interpret having the agents run over a
number of episodes as deploying the agent into the environment each day while
recording its performance. The distribution shifts in the observational
evaluations happen randomly, so the human maintainers have no control over how
the shifts are introduced. When plotting these evaluations, the single-agent
and multi-agent cases use different approaches to randomly introducing
distribution shift. In the single-agent case, we define a probability
threshold for adversarial attacks. If the random number generator (like
random.random() in Python) gives a number above the threshold, the Atari game
image is attacked. In the multi-agent case, we use a strategy similar to
Rahman et al. (2021), where the number of steps an agent is switched out is
drawn from a uniform distribution. Figure 4 provides some Atari game examples
of observational studies. We use 10 random seeds for both causal and
observational time-series evaluation. More information on the plots is
provided in the Appendix.

###  5.1 Analysis on Adversarial Attacks on A2C and PPO Agents

In this analysis, we measure the performance of RL agents trained on Atari
games (Bellemare et al., 2013) in the presence of adversarial attacks. In
Figure 3 and the Atari impact graphs in Appendix D, we use pretrained A2C and
PPO pretrained agents provided by RL Baselines3 Zoo (RLZoo) (Raffin, 2020)
implemented in Stable-Baselines3 (Raffin et al., 2021).

For adversarial attacks on the Atari game images, we use the Fast Gradient
Sign Method (FGSM) (Goodfellow et al., 2014). In most cases, like in Figure 3,
the adversarial attacks work as expected and generally decreases the
performance as $\epsilon$ increases. One noticeable pattern is that the agents
significantly deviate from the baseline performance when $\epsilon\geq 0.5$.
PPO performance is generally equal or worse than A2C after the distribution
shift intervention at the halfway point. There are games, like Qbert and Space
Invaders, where PPO achieves much worse cumulative returns than A2C when
exposed to the highest values of $\epsilon$. Another strange finding was that
the RLZoo A2C agent showed non-decreasing (or slightly increasing) cumulative
returns in Asteroids and Road Runner. One conclusion that can be drawn from
these findings is that the pretrained RLZoo A2C is more robust than PPO
against constant adversarial examples.

(a)

(b)

(c)

(d)

Figure 3: The causal impact plots shown here illustrate the impact of FGSM
adversarial attacks on RL agents trained on the Pong Atari game. Each row
represents an Atari game. Each column represents a RL algorithm (A2C or PPO).
The original plots here show the rolling mean of the rewards over time. The
pointwise plots show the difference between the counterfactual performance and
the performance when the agent is attacked. The cumulative performance is the
summation of the rewards gained or lost over time. As expected, the
performance tends to drop as $\epsilon$ increases.

The observational plots, like in Figure 4 and Appendix D, tell a more nuanced
story. Except for Pong, where the PPO performance trends are significantly
better than A2C, PPO’s forecasts trends are higher than A2C’s but there is
overlap between the prediction intervals. It seems that the PPO agents are
able to recover and choose better actions when not observing adversarial
examples. This is consistent with the RL Baselines3 Zoo benchmark scores,
where PPO scores higher than A2C in every Atari game (without the presence of
adversarial attacks). Hence, we conclude that RLZoo PPO agents have trends
that perform (not significantly) better in the presence of random attacks, but
the impact plots show clear signs of overfitting in some environments. On the
other hand, A2C agents tend to be relatively more robust than PPO against
adversarial attacks in Atari games.

Figure 4: These plots take the rolling mean (window=25) of the observational
performance up to a certain time point with some probability of being in the
presence of adversarial attacks. After that time point, it shows the time
series forecast with 99% prediction intervals. Top Row: In the
PongNoFrameskip-v4 plots, PPO performs significantly better and has smaller
prediction intervals. The plot on the right, however, uses attacks with higher
$\epsilon$, where both agents have larger prediction intervals. Bottom Row: In
the BreakoutNoFrameskip-v4 plots, the prediction intervals overlap. One
noticeable difference is that the stronger attacks cause the PPO interval to
shrink in size while the mean rewards are slightly less. This decrease in
variability accounts for the decrease in the maximum rewards achieved.

###  5.2 Analysis on Agent Switching in PowerGridworld

In the multi-agent case (Figure 5), we measure the performance of a
cooperative group of 5 decentralized PPO agents in the presence of ad hoc
agent switching. The multi-agent environment we use is a framework for power-
systems-focused simulations called PowerGridworld (Biagioni et al., 2022). As
seen on the impact plots in Figure 5, we investigate what happens when 1 to 3
agents in the group are switched out with the corresponding number of outside
pretrained or untrained agents. The outside pretrained agents were trained as
a separate group of 5 agents that achieve a score similar to the original
group. In this case, there was a slight impact when switching out 1 or 2
agents. The performance dramatically decreased when 3 agents were switched
out, which is a majority of the agents. Replacing one agent of the group with
one untrained agent, as can be seen in Figure 5, is much worse than switching
out 3 agents with outside pretrained agents. The observational PowerGridworld
plots in Appendix D provide complementary results. Hence, in this
PowerGridworld environment, we can conclude that (i) switching out and
replacing the majority of agents (including pretrained) can significantly
diminish performance, and (ii) replacing even one trained agent with an
untrained agent can be worse than switching out the majority with outside
trained agents. When switching the original agents with similarly-trained
outside agents, it seems that group performance is robust when only switching
out a minority of the agents, but is significantly less robust when a majority
of agents is switched out. In further studies, it would be interesting to see
if this behavior can be generalized to other decentralized groups, and if ad
hoc teamwork training methods can improve these results.

Figure 5: The plots here show the impact of the ad hoc switching of agents in
a group of 5 in the PowerGridworld environment. Left Column: We replace 1, 2,
or 3 agents out of the group of 5 with agents that trained with a different
group. While there is little change when only replacing 1 or 2 agents, we see
that performance dramatically decreases when 3 agents have been switched out.
Right Column: We see that just switching out 1 agent in the group with 1
untrained agent causes a significantly large decrease in group performance.

##  6 Conclusion

In this work, we show that relying on point estimates, even alternatives that
are more reliable and less biased than what is typically used in practice, are
limited in their ability to evaluate RL performance in the presence of
distribution shifts. In particular, we argue that the methodology proposed
here provides more of a necessary emphasis on test-time evaluation, and can
assess both single and multi-agent performance. If, or when, we choose to
deploy RL agents into the real world, how such agents perform after training
will matter more than during training. The decline in performance during ad
hoc agent switching in the PowerGridworld shows what could happen if we need
to start replacing intelligent agents to ensure energy usage is minimized.
Such experiments reveal a workflow that will likely be closer to representing
real-world safety checks and maintenance of AI systems. Our methodology might
also be useful for investigating general single or multi-agent RL behavior.

There is still work to accomplish in ensuring RL research is reproducible. One
weakness is that the generality of our protocol makes it difficult to make
environment-specific conclusions. For example, in an open-ended game like
Minecraft (Johnson et al., 2016; Guss et al., 2019; Fan et al., 2022), we
would also want task-specific explanations when the agent accomplishes a goal
in a massively multitask environment. Another weakness of our approach is that
it does not account for non-deterministic environments. Investigating if more
complex time series models would be appropriate in certain scenarios is
another next step. Time series clustering and motifs (Mueen et al., 2009;
Imani et al., 2021) can be used to better understand how different types of
distribution shift can affect RL performance. One could also investigate if
time series ensemble models (Wichard and Ogorzalek, 2004) provide better
forecasts than simpler models. Developing a methodology that provides
environment-specific explanations, accounts for more assumptions, and uses
more sophisticated time series models can be investigated in future research.

Nations, like the United States (White House, 2022), have signed legislation
to invest in the modernization of infrastructure and communities to meet the
growing challenges of the 21st century (e.g., cybersecurity and climate
change). RL is advancing the automation of complex decision making in real-
world infrastructure systems (e.g., energy and transportation). Like other
areas in AI, the role of RL in critical infrastructure and other high-
consequence applications requires robust, reliable, repeatable, and
standardized evaluation protocols (European Union, 2021; Biden Jr, 2023). The
methodology we propose here, inspired by the NHTSA ratings standards, is a
start toward a general, standardized protocol for evaluating pretrained RL
performance over time.

#### Acknowledgments

This research was supported by the National Infrastructure Simulation and
Analysis Center (NISAC), a program of the U.S. Cybersecurity and
Infrastructure Security Agency’s (CISA’s) National Risk Management Center.
Pacific Northwest National Laboratory is operated by Battelle Memorial
Institute for the U.S. Department of Energy under Contract No. DE-
AC05-76RL01830.

## References

  * Agarwal et al. [2021] Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare.  Deep reinforcement learning at the edge of the statistical precipice.  _Advances in neural information processing systems_ , 34:29304–29320, 2021.
  * Ahmed et al. [2010] Nesreen K Ahmed, Amir F Atiya, Neamat El Gayar, and Hisham El-Shishiny.  An empirical comparison of machine learning models for time series forecasting.  _Econometric reviews_ , 29(5-6):594–621, 2010.
  * Ahmed et al. [2021] Ossama Ahmed, Frederik Träuble, Anirudh Goyal, Alexander Neitz, Manuel Wuthrich, Yoshua Bengio, Bernhard Schölkopf, and Stefan Bauer.  Causalworld: A robotic manipulation benchmark for causal structure and transfer learning.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=SK7A5pdrgov.
  * Bakhtin et al. [2022] Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, et al.  Human-level play in the game of diplomacy by combining language models with strategic reasoning.  _Science_ , 378(6624):1067–1074, 2022.
  * Barhate [2021] Nikhil Barhate.  Minimal pytorch implementation of proximal policy optimization.  https://github.com/nikhilbarhate99/PPO-PyTorch, 2021.
  * Barrett and Stone [2015] Samuel Barrett and Peter Stone.  Cooperating with unknown teammates in complex domains: A robot soccer case study of ad hoc teamwork.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 29, 2015.
  * Bellemare et al. [2013] Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Berner et al. [2019] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al.  Dota 2 with large scale deep reinforcement learning.  _arXiv preprint arXiv:1912.06680_ , 2019.
  * Biagioni et al. [2022] David Biagioni, Xiangyu Zhang, Dylan Wald, Deepthi Vaidhynathan, Rohit Chintala, Jennifer King, and Ahmed S. Zamzam.  Powergridworld: A framework for multi-agent reinforcement learning in power systems.  In _Proceedings of the Thirteenth ACM International Conference on Future Energy Systems_ , e-Energy ’22, page 565–570, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450393973.  doi: 10.1145/3538637.3539616.  URL https://doi.org/10.1145/3538637.3539616.
  * Biden Jr [2023] Joseph Biden Jr.  Executive order on the safe, secure, and trustworthy development and use of artificial intelligence.  _White House_ , 2023.  URL https://www.whitehouse.gov/briefing-room/presidential-actions/2023/10/30/executive-order-on-the-safe-secure-and-trustworthy-development-and-use-of-artificial-intelligence/.  [Accessed November 2, 2023].
  * Biggio et al. [2012] Battista Biggio, B Nelson, P Laskov, et al.  Poisoning attacks against support vector machines.  In _Proceedings of the 29th International Conference on Machine Learning, ICML 2012_ , pages 1807–1814. ArXiv e-prints, 2012.
  * Brodersen et al. [2015] Kay H Brodersen, Fabian Gallusser, Jim Koehler, Nicolas Remy, and Steven L Scott.  Inferring causal impact using bayesian structural time-series models.  _The Annals of Applied Statistics_ , pages 247–274, 2015.
  * Brown and Sandholm [2019] Noam Brown and Tuomas Sandholm.  Superhuman ai for multiplayer poker.  _Science_ , 365(6456):885–890, 2019.
  * Buteikis [2020] A Buteikis.  Practical econometrics and data science.  _Vilnius University: Vilnius, Lithuania_ , 2020.
  * Casper et al. [2022] Stephen Casper, Dylan Hadfield-Menell, and Gabriel Kreiman.  White-box adversarial policies in deep reinforcement learning.  _arXiv preprint arXiv:2209.02167_ , 2022.
  * Chan et al. [2020] Stephanie CY Chan, Samuel Fishman, Anoop Korattikara, John Canny, and Sergio Guadarrama.  Measuring the reliability of reinforcement learning algorithms.  In _International Conference on Learning Representations_ , 2020.
  * Colas et al. [2018] Cédric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer.  How many random seeds? statistical power analysis in deep reinforcement learning experiments.  _arXiv preprint arXiv:1806.08295_ , 2018.
  * Cormen et al. [2022] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  _Introduction to algorithms_.  MIT press, 2022.
  * Cui et al. [2022] Jiaxun Cui, Xiaomeng Yang, Mulong Luo, Geunbae Lee, Peter Stone, Hsien-Hsin S Lee, Benjamin Lee, G Edward Suh, Wenjie Xiong, and Yuandong Tian.  Macta: A multi-agent reinforcement learning approach for cache timing attacks and detection.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Cunningham [2021] Scott Cunningham.  _Causal inference: The mixtape_.  Yale university press, 2021.
  * Engstrom et al. [2020] Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry.  Implementation matters in deep policy gradients: A case study on ppo and trpo.  _arXiv preprint arXiv:2005.12729_ , 2020.
  * European Union [2021] European Union.  Laying down harmonised rules on artificial intelligence (artificial intelligence act) and amending certain union legislative acts. proposal for a regulation of the european parliament and of the council, 2021.  URL https://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX:52021PC0206.
  * Fan et al. [2022] Linxi Fan, Guanzhi Wang, Yunfan Jiang, Ajay Mandlekar, Yuncong Yang, Haoyi Zhu, Andrew Tang, De-An Huang, Yuke Zhu, and Anima Anandkumar.  Minedojo: Building open-ended embodied agents with internet-scale knowledge.  _Advances in Neural Information Processing Systems_ , 35:18343–18362, 2022.
  * Figura et al. [2021] Martin Figura, Krishna Chaitanya Kosaraju, and Vijay Gupta.  Adversarial attacks in consensus-based multi-agent reinforcement learning.  In _2021 American Control Conference (ACC)_ , pages 3050–3055. IEEE, 2021.
  * Fujimoto et al. [2021] Ted Fujimoto, Timothy Doster, Adam Attarian, Jill Brandenberger, and Nathan Hodas.  Reward-free attacks in multi-agent reinforcement learning.  _arXiv preprint arXiv:2112.00940_ , 2021.
  * Gardner Jr and McKenzie [1985] Everette S Gardner Jr and ED McKenzie.  Forecasting trends in time series.  _Management science_ , 31(10):1237–1246, 1985.
  * Gleave et al. [2019] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell.  Adversarial policies: Attacking deep reinforcement learning.  In _International Conference on Learning Representations_ , 2019.
  * Goodfellow et al. [2014] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Gorsane et al. [2022] Rihab Gorsane, Omayma Mahjoub, Ruan John de Kock, Roland Dubb, Siddarth Singh, and Arnu Pretorius.  Towards a standardised performance evaluation protocol for cooperative marl.  _Advances in Neural Information Processing Systems_ , 35:5510–5521, 2022.
  * Guss et al. [2019] William H Guss, Brandon Houghton, Nicholay Topin, Phillip Wang, Cayden Codel, Manuela Veloso, and Ruslan Salakhutdinov.  Minerl: A large-scale dataset of minecraft demonstrations.  _arXiv preprint arXiv:1907.13440_ , 2019.
  * Henderson et al. [2018] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger.  Deep reinforcement learning that matters.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32, 2018.
  * Holland [1986] Paul W Holland.  Statistics and causal inference.  _Journal of the American statistical Association_ , 81(396):945–960, 1986.
  * Holt [2004] Charles C Holt.  Forecasting seasonals and trends by exponentially weighted moving averages.  _International journal of forecasting_ , 20(1):5–10, 2004.
  * Huang et al. [2011] Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and J Doug Tygar.  Adversarial machine learning.  In _Proceedings of the 4th ACM workshop on Security and artificial intelligence_ , pages 43–58, 2011.
  * Huang et al. [2017] Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel.  Adversarial attacks on neural network policies.  _arXiv preprint arXiv:1702.02284_ , 2017.
  * Hunter [2007] J. D. Hunter.  Matplotlib: A 2d graphics environment.  _Computing in Science & Engineering_, 9(3):90–95, 2007.  doi: 10.1109/MCSE.2007.55.
  * Huntington-Klein [2021] Nick Huntington-Klein.  _The effect: An introduction to research design and causality_.  CRC Press, 2021.
  * Hyndman [2014] Rob J Hyndman.  Prediction intervals too narrow, Oct 2014.  URL https://robjhyndman.com/hyndsight/narrow-pi/.
  * Hyndman and Athanasopoulos [2018] Rob J Hyndman and George Athanasopoulos.  _Forecasting: principles and practice_.  OTexts, 2018.
  * Imani et al. [2021] Shima Imani, Alireza Abdoli, and Eamonn Keogh.  Time2cluster: Clustering time series using neighbor information.  In _Time Series Workshop at the 38th International Conference on Machine Learning (ICML)_ , 2021.
  * Imbens and Rubin [2015] Guido W Imbens and Donald B Rubin.  _Causal inference in statistics, social, and biomedical sciences_.  Cambridge University Press, 2015.
  * Johnson et al. [2016] Matthew Johnson, Katja Hofmann, Tim Hutton, and David Bignell.  The malmo platform for artificial intelligence experimentation.  In _Ijcai_ , pages 4246–4247, 2016.
  * Jordan et al. [2020] Scott Jordan, Yash Chandak, Daniel Cohen, Mengxue Zhang, and Philip Thomas.  Evaluating the performance of reinforcement learning algorithms.  In _International Conference on Machine Learning_ , pages 4962–4973. PMLR, 2020.
  * Kim [2020] Hoki Kim.  Torchattacks: A pytorch repository for adversarial attacks.  _arXiv preprint arXiv:2010.01950_ , 2020.
  * Koh et al. [2021] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  In _International Conference on Machine Learning_ , pages 5637–5664. PMLR, 2021.
  * Kos and Song [2017] Jernej Kos and Dawn Song.  Delving into adversarial attacks on deep policies.  _arXiv preprint arXiv:1705.06452_ , 2017.
  * Kurakin et al. [2016] Alexey Kurakin, Ian J Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In _International Conference on Learning Representations_ , 2016.
  * Lee et al. [2021] Tabitha E Lee, Jialiang Alan Zhao, Amrita S Sawhney, Siddharth Girdhar, and Oliver Kroemer.  Causal reasoning in simulation for structure and transfer learning of robot manipulation policies.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 4776–4782. IEEE, 2021.
  * Lee et al. [2023] Tabitha Edith Lee, Shivam Vats, Siddharth Girdhar, and Oliver Kroemer.  SCALE: Causal learning and discovery of robot manipulation skills using simulation.  In _7th Annual Conference on Robot Learning_ , 2023.  URL https://openreview.net/forum?id=WmF-fagWdD.
  * Löning et al. [2022] Markus Löning, Franz Király, Tony Bagnall, Matthew Middlehurst, Sajaysurya Ganesh, George Oastler, Jason Lines, Martin Walter, ViktorKaz, Lukasz Mentel, chrisholder, Leonidas Tsaprounis, RNKuhns, Mirae Parker, Taiwo Owoseni, Patrick Rockenschaub, danbartl, jesellier, eenticott shell, Ciaran Gilbert, Guzal Bulatova, Lovkush, Patrick Schäfer, Stanislav Khrapov, Katie Buchhorn, Kejsi Take, Shivansh Subramanian, Svea Marie Meyer, AidenRushbrooke, and Beth rice.  sktime/sktime: v0.13.4, September 2022.  URL https://doi.org/10.5281/zenodo.7117735.
  * Ma et al. [2019] Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu.  Policy poisoning in batch reinforcement learning and control.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Masini et al. [2023] Ricardo P Masini, Marcelo C Medeiros, and Eduardo F Mendes.  Machine learning advances for time series forecasting.  _Journal of economic surveys_ , 37(1):76–111, 2023.
  * McKinsey and Company [2021] McKinsey and Company, Mar 2021.  URL https://www.mckinsey.com/capabilities/mckinsey-digital/how-we-help-clients/flying-across-the-sea-propelled-by-ai.
  * Mirsky et al. [2022] Reuth Mirsky, Ignacio Carlucho, Arrasy Rahman, Elliot Fosong, William Macke, Mohan Sridharan, Peter Stone, and Stefano V Albrecht.  A survey of ad hoc teamwork research.  In _Multi-Agent Systems: 19th European Conference, EUMAS 2022, Düsseldorf, Germany, September 14–16, 2022, Proceedings_ , pages 275–293. Springer, 2022.
  * Moraffah et al. [2021] Raha Moraffah, Paras Sheth, Mansooreh Karami, Anchit Bhattacharya, Qianru Wang, Anique Tahir, Adrienne Raglin, and Huan Liu.  Causal inference for time series analysis: Problems, methods and evaluation.  _Knowledge and Information Systems_ , 63:3041–3085, 2021.
  * Mueen et al. [2009] Abdullah Mueen, Eamonn Keogh, Qiang Zhu, Sydney Cash, and Brandon Westover.  Exact discovery of time series motifs.  In _Proceedings of the 2009 SIAM international conference on data mining_ , pages 473–484. SIAM, 2009.
  * Pattanaik et al. [2017] Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary.  Robust deep reinforcement learning with adversarial attacks.  _arXiv preprint arXiv:1712.03632_ , 2017.
  * Pearl [2009] Judea Pearl.  _Causality_.  Cambridge university press, 2009.
  * Peters et al. [2017] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  _Elements of causal inference: foundations and learning algorithms_.  The MIT Press, 2017.
  * Quinonero-Candela et al. [2008] Joaquin Quinonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence.  _Dataset shift in machine learning_.  Mit Press, 2008.
  * Rabanser et al. [2019] Stephan Rabanser, Stephan Günnemann, and Zachary Lipton.  Failing loudly: An empirical study of methods for detecting dataset shift.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Raffin [2020] Antonin Raffin.  Rl baselines3 zoo.  https://github.com/DLR-RM/rl-baselines3-zoo, 2020.
  * Raffin et al. [2021] Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann.  Stable-baselines3: Reliable reinforcement learning implementations.  _Journal of Machine Learning Research_ , 22(268):1–8, 2021.  URL http://jmlr.org/papers/v22/20-1364.html.
  * Rahman et al. [2021] Muhammad A Rahman, Niklas Hopner, Filippos Christianos, and Stefano V Albrecht.  Towards open ad hoc teamwork using graph-based policy learning.  In _International Conference on Machine Learning_ , pages 8776–8786. PMLR, 2021.
  * Rakhsha et al. [2020] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla.  Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning.  In _International Conference on Machine Learning_ , pages 7974–7984. PMLR, 2020.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In _International conference on machine learning_ , pages 1889–1897. PMLR, 2015.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Silver et al. [2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Spirtes et al. [2000] Peter Spirtes, Clark N Glymour, and Richard Scheines.  _Causation, prediction, and search_.  MIT press, 2000.
  * Stone et al. [2010] Peter Stone, Gal Kaminka, Sarit Kraus, and Jeffrey Rosenschein.  Ad hoc autonomous agent teams: Collaboration without pre-coordination.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 24, pages 1504–1509, 2010.
  * Verma and Srivastava [2021] Pulkit Verma and Siddharth Srivastava.  Learning causal models of autonomous agents using interventions.  _arXiv preprint arXiv:2108.09586_ , 2021.
  * Verma et al. [2023] Pulkit Verma, Rushang Karia, and Siddharth Srivastava.  Autonomous capability assessment of sequential decision-making systems in stochastic settings.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=VqclD6Nfaj.
  * Vinyals et al. [2019] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, 2019.
  * Waskom [2021] Michael L. Waskom.  seaborn: statistical data visualization.  _Journal of Open Source Software_ , 6(60):3021, 2021.  doi: 10.21105/joss.03021.  URL https://doi.org/10.21105/joss.03021.
  * White House [2022] White House.  A guidebook to the bipartisan infrastructure law for state, local, tribal, and territorial governments, and other partners.  _White House_ , 2022.  URL https://www.whitehouse.gov/wp-content/uploads/2022/05/BUILDING-A-BETTER-AMERICA-V2.pdf.  [Accessed November 2, 2023].
  * Wichard and Ogorzalek [2004] Jorg D Wichard and Maciej Ogorzalek.  Time series prediction with ensemble models.  In _2004 IEEE international joint conference on neural networks (IEEE Cat. No. 04CH37541)_ , volume 2, pages 1625–1630. IEEE, 2004.
  * Zhang et al. [2018] Chiyuan Zhang, Oriol Vinyals, Remi Munos, and Samy Bengio.  A study on overfitting in deep reinforcement learning.  _arXiv preprint arXiv:1804.06893_ , 2018.
  * Zhang et al. [2020] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu.  Adaptive reward-poisoning attacks against reinforcement learning.  In _International Conference on Machine Learning_ , pages 11225–11234. PMLR, 2020.

## Appendix

##  Appendix A Methods

We provide the following definition of RL agent time-series performance
measurements, similar to how performance is measured in RL training research,
that will be relevant in the next subsection:

######  Definition 1.

Let $X^{A}(t)$ the time series performance for $t=1\dots N$, where $A$ is an
RL agent in a simulated deterministic environment $\mathcal{M}$. For each
$X^{A}(t)$, there is an associated sample of performance measurements
$x^{A}(t)=(x^{A,1}(t),\dots,x^{A,M}(t))$. Here, the $i$ in $x^{A,i}(t)$ is a
random seed $i\in\mathfrak{S}$, where $\mathfrak{S}$ is a finite set of $M$
random seeds. Hence, we define:

$X^{A}(t)=\mathbb{E}[x^{A,i}(t)]\\\
=\frac{\sum_{i\in\mathfrak{S}}x^{A,i}(t)}{M}$ (3)

which is the expected performance222We use expected performance just as a
simple default. For example, in accordance with Agarwal et al. [2021], one
could replace expected performance with the interquartile mean. at time $t$
over all the random seeds in $\mathfrak{S}$.

###  A.1 Comparison of Simple Time Series Forecasting Trends

To compare RL algorithms at test time, we compare the performance forecasts of
each RL agent. This recommendation is inspired by the use of time complexity
or running time to measure the efficiency of an algorithm [Cormen et al.,
2022]. As illustrated in Figure 1, looking at performance trends of RL agents
is an informative way to observe overfitting during test time. Here, we use
simple time series forecasts over more complex time series models that might
better predict the performance trend. The reason is that one cannot make too
many strong, general assumptions (e.g., seasonality, how many past values to
use for autoregression) on the time series trend of agent performance in all
environments. For test-time distribution shift, we only assume the trend will
be pessimistic and not increase. This is reasonable if we assume the ideal
case is when performance never decreases (like Agent 1 in Figure 1). We
default to using Holt’s linear damped trend method [Gardner Jr and McKenzie,
1985, Holt, 2004, Hyndman and Athanasopoulos, 2018] to model the trend of
agent performance when in the presence of distribution shift. The damping
parameter discourages constant increasing trends, which will likely give more
accurate forecasts than Holt’s method without damping. Researchers evaluating
their own experiments, however, may find that more complex models would be
more appropriate for their own studies if they see performance trends that
warrant such assumptions.

Here, we define Holt’s linear damped trend method [Hyndman and Athanasopoulos,
2018]:
Let $\hat{y}_{t+h|t}$ be the short-hand estimate for $y_{t+h}$ based on data
$y_{1}\dots y_{t}$. The term $\ell_{t}$ is the estimate of the level of the
series at time $t$ with a smoothing parameter $\alpha$ such that
$0\leq\alpha\leq 1$. The term $b_{t}$ is the estimate of the trend (slope) of
the series at time $t$ with a smoothing parameter $\beta^{*}$ such that
$0\leq\beta^{*}\leq 1$. Let $\phi$ be the damping parameter such that
$0<\phi<1$. Then the trend method is represented as the forecast equation and
smoothing equations below:

$\displaystyle\hat{y}_{t+h|t}$
$\displaystyle=\ell_{t}+(\phi+\phi^{2}+\dots+\phi^{h})b_{t}$
$\displaystyle\ell_{t}$ $\displaystyle=\alpha y_{t}+(1-\alpha)(\ell_{t-1}+\phi
b_{t-1})$ $\displaystyle b_{t}$
$\displaystyle=\beta^{*}(\ell_{t}-\ell_{t-1})+(1-\beta^{*})\phi b_{t-1}$

###  A.2 Prediction Intervals over Future Performance

Along with time series forecasts, we recommend prediction intervals over
future average returns [Hyndman and Athanasopoulos, 2018]. The combination of
simple time series forecasts and prediction intervals map out the range of
average returns over time. As stated previously, point estimates with
confidence intervals are not enough to capture the range of returns over time.
Prediction intervals act as a compliment to the time series forecasting by
visualizing the uncertainty of the possible future average returns. When
applying both of these methods, we can specify the most robust RL algorithm as
the trend with the most optimistic forecast on performance and the smallest
prediction interval. Here, we assume there exists distribution shifts but do
not necessarily know when or where.

###  A.3 Difference-in-differences Analysis for RL Performance

Difference-in-differences (DiD) measures the causal effect between a treatment
and control group, where the treatment group is exposed to an intervention at
a certain point in time [Cunningham, 2021, Huntington-Klein, 2021].
Intuitively, it represents how much more the treatment group was affected by
the intervention at some time $t$ compared to the change of the unaffected
control group at the same time $t$. Since we are dealing with time series, we
will adhere to the DiD formulation in Moraffah et al. [2021]:

######  Definition 2.

If $t<T$ and $t>T$ denote the pre- and post- treatment periods, respectively,
then we can calculate the DiD measure using the average treatment effect
metric over a time series $X(t)$ as follows:

$DiD=\\{\mathbb{E}[X(t>T)|G=1]-\mathbb{E}[X(t<T)|G=1]\\}-\\{\mathbb{E}[X(t>T)|G=0]-\mathbb{E}[X(t<T)|G=0]\\}$
(4)

where $G$ indicates the treatment group $(G=1)$ and the control group $(G=0)$.

Any methodology that relies on DiD must satisfy the parallel trends
assumption, which says that _if no treatment had occurred, the difference
between the treated group and the untreated group would have stayed the same
in the post-treatment period as it was in the pre-treatment period_
[Huntington-Klein, 2021]. RL agents in deterministic environments with fixed
seeds trivially satisfy this because the agent will take the same action at
each state and receive the same reward regardless of how many times the
evaluation is repeated.

From the RL fixed seed assumption, DiD simplifies to the equation below when
evaluating RL performance:

$DiD=\mathbb{E}[X^{A}(t>T)|G=1]-\mathbb{E}[X^{A}(t>T)|G=0]$ (5)

where $A$ is the RL agent being evaluated. This follows from the pre-treatment
averages canceling each other out. Hence, we only need to measure the post-
treatment effect of RL performance. Using the RL fixed seed assumption, DiD
becomes the following:

$DiD=\mathbb{E}[X^{A}(t>T)|G=1]-\mathbb{E}[X_{U=0}^{A}(t>T)|G=1]$ (6)

Equations 5 and 6 say the following: Measuring the DiD effect is equivalent to
measuring the average time series post-treatment effect of agent $A$ between
the treatment and control group. If the agents in both the treatment and
control groups have the same fixed random seeds, we can interpret the
performance measurements of the control group as the counterfactual of the
treatment group as if the treatment group was never exposed to the
distribution shift intervention. Hence, we have shown that the RL fixed seed
assumption justifies causal inference in our time series analysis.

##  Appendix B Further Notes on the RL Fixed Seed Assumption

Reproducibility can be difficult to achieve when running on a GPU. As
described in PyTorch’s webpage on reproducibility, even identical seeds might
not provide reproducible results. Some reasons include nondeterministic
algorithms that improve performance and the use of different hardware can
affect the selection of such algorithms. To control these sources of
randomness in our experiments, we adhere to the reproducibility suggestions
provided on the webpage.

##  Appendix C Further Notes on Environments Used in Evaluations

All plots use 10 random seeds. In multi-agent settings, each agent shares the
same seed during an evaluation run. For example, if our seed numbers are 1 and
42, then the first evaluation run sets

###  C.1 Atari Games

The games of focus are a subset of Atari games AsteroidsNoFrameskip-v4,
BeamRiderNoFrameskip-v4, BreakoutNoFrameskip-v4, MsPacmanNoFrameskip-v4,
PongNoFrameskip-v4, QbertNoFrameskip-v4, RoadRunnerNoFrameskip-v4,
SeaquestNoFrameskip-v4, and SpaceInvadersNoFrameskip-v4. The agents we
evaluate are pretrained agents from RL Baselines3 Zoo [Raffin, 2020] that are
available on SB3’s Huggingface repository of models. The adversarial attacks
(FGSM) were implemented in torchattacks [Kim, 2020].

We evaluate each agent over 100 games per Atari game. In the causal impact
plots, the attacker intervenes at the 50th game. Here, since game scores
accumulate across lives, we define episodes as the life of the player. For
example, Pong only gives one life, which gives us a total of 100 episodes. In
Qbert, the player is given 4 lives. Hence, the attacker intervenes at episode
200 because (50 games) * (4 episodes/game) = 200 episodes (or lives). This
reasoning is also why there are 400 episodes in the Qbert experiments. This
strategy deliberately avoids the noisy artifacts that can emerge from the time
series data when accumulated performance suddenly drops when each game ends.

###  C.2 PowerGridworld

PowerGridworld is a modular, customizable framework for building power systems
environments to train RL agents. Because of this, we use an environment
provided in one of the example scripts. The class name is called
CoordinatedMultiBuildingControlEnv, which is a multi-agent coordination
environment. In addition to the original agent-level reward, grid-level
reward/penalty and system-level constraint(s) are considered. In particular,
we consider the voltage constraints: agents need to coordinate so the common
bus voltage is within the ANSI C.84.1 limit. If the constraints are not
satisfied, the voltage violation penalty will be shared by all agents. The
agents in this scenario are minimal implementations [Barhate, 2021] of PPO.

###  C.3 Time Series Tools

Trends and prediction intervals were implemented in the Python package sktime
[Löning et al., 2022]. Other Python visualization tools include Matplotlib
[Hunter, 2007] and Seaborn [Waskom, 2021].

##  Appendix D More Plots

###  D.1 Atari Game Causal Impact Plots

(a)  (b)

(c)  (d)

(e)  (f)

(g)  (h)

(i)  (j)

(k)  (l)

(m)  (n)

(o)  (p)

(q)  (r)

###  D.2 Observational Plots

All observational plots show forecasts with prediction intervals 100 episodes
after the last measurement.

####  D.2.1 PowerGridworld

Figure 6: PowerGridworld observational plots. Left: Comparing random switching
with pretrained agents at each episode. Right: Comparing random switching with
untrained agented at each episode.

####  D.2.2 Atari Games

##  Appendix E Hyperparameters for PowerGridworld PPO Training

Number of Training Episodes: 2,000,000
Maximum Number of Steps per Episode: 1000
Starting Standard Deviation for Action Distribution: 1.0
Standard Deviation for Action Distribution Decay Rate: 0.05
Minimum Standard Deviation for Action Distribution: 0.1
Standard Deviation Decay Frequency in time steps: 250,000

Policy: 2-layer Multilayer Perceptron
Hidden Units: 128 per layer
Policy is updated every 2000 time steps. During that time step, the policy
updated 5 epochs.

Clip parameter: 0.2
Discount factor $\gamma$: 0.99

Actor Learning Rate: 0.0003
Critic Learning Rate: 0.001

Main group random seed: 0
Outside group random seed: 1