# OSL-ActionSpotting: A Unified Library
for Action Spotting in Sports Videos

Yassine Benzakour  Montefiore Institute, University of Liège
Email<EMAIL_ADDRESS>Bruno Cabado  Cinfo & CITIC
Research Center,
University of A Coruña
Email<EMAIL_ADDRESS>Silvio Giancola  IVUL, KAUST
Email<EMAIL_ADDRESS>Anthony Cioppa  Montefiore Institute,
University of Liège
<EMAIL_ADDRESS>Bernard Ghanem  IVUL, KAUST
Email<EMAIL_ADDRESS>Marc Van Droogenbroeck  Montefiore
Institute, University of Liège
Email<EMAIL_ADDRESS>
###### Abstract

Action spotting is crucial in sports analytics as it enables the precise
identification and categorization of pivotal moments in sports matches,
providing insights that are essential for performance analysis and tactical
decision-making. The fragmentation of existing methodologies, however, impedes
the progression of sports analytics, necessitating a unified codebase to
support the development and deployment of action spotting for video analysis.
In this work, we introduce _OSL-ActionSpotting_ , a Python library that
unifies different action spotting algorithms to streamline research and
applications in sports video analytics. _OSL-ActionSpotting_ encapsulates
various state-of-the-art techniques into a singular, user-friendly framework,
offering standardized processes for action spotting and analysis across
multiple datasets. We successfully integrated three cornerstone action
spotting methods into OSL-ActionSpotting, achieving performance metrics that
match those of the original, disparate codebases. This unification within a
single library preserves the effectiveness of each method and enhances
usability and accessibility for researchers and practitioners in sports
analytics. By bridging the gaps between various action spotting techniques,
OSL-ActionSpotting significantly contributes to the field of sports video
analysis, fostering enhanced analytical capabilities and collaborative
research opportunities. The scalable and modularized design of the library
ensures its long-term relevance and adaptability to future technological
advancements in the domain.

Keywords. Video understanding, Action spotting, Sports Analytics, Python
library, Benchmark, Algorithms.

##  I Introduction

Action spotting in sports videos is a critical task in sports analytics,
allowing for the detailed analysis of player actions, game events, and overall
performance. This process is instrumental in enhancing strategies, training
programs, and audience engagement. However, the diversity of action spotting
methodologies has led to a fragmented landscape where integrating these
techniques is challenging. Existing systems often operate in isolation,
leading to inefficiencies and difficulties in achieving a comprehensive
analytical perspective. The necessity for consistency, efficiency, and
scalability in sports analytics drives the need for a unified approach in
action spotting. Moreover, the rapid evolution of video analysis technologies
demands a flexible and adaptable framework that can incorporate new methods
and adapt to changing analytical requirements.

In response to these challenges, we propose OSL-ActionSpotting, a
comprehensive library that integrates multiple state-of-the-art action
spotting methods into a single, cohesive framework, illustrated in Figure 1.
This library aims to standardize action spotting across various sports
disciplines and enhances the accessibility and efficiency of these analyses
for researchers and practitioners alike. The library is available at
https://github.com/OpenSportsLab/OSL-ActionSpotting.

Figure 1:  OSL-ActionSpotting is a plug-and-play library that unifies action
spotting algorithms. The design of OSL-ActionSpotting is inherently versatile,
making it applicable to a broad spectrum of sports video analyses. This
adaptability ensures that OSL-ActionSpotting can facilitate the development of
novel action spotting techniques, and accelerate the deployment of these
methods, providing a robust and comprehensive tool for researchers and
analysts in various sports domains.

Contributions: (i) We release the first action spotting Python library that
includes the most impactful algorithms developed in the literature, into a
modularized framework that will empower future algorithmic development. (ii)
We develop a video data loader based on DALI, that efficiently pre-process
videos to be fed into our algorithm, enabling faster training of end-to-end
algorithms. (iii) We formalize a novel action spotting dataset format in a
unique JSON that enables the usage of OSL-ActionSpotting’s algorithms on new
video datasets.

##  II Related Work

###  II-A Sports Video Understanding

The field of sports video analysis has evolved into an important research area
due to the intricate nature of sports video understanding [1, 2]. Early
approaches primarily focused on video classification tasks [3], which included
recognizing distinct actions [4] and categorizing various phases of gameplay
[5]. Research expanded into different domains of sports video understanding,
covering areas such as player detection [6], tracking [7], image segmentation
[8], and player identification [9]. It also explored the analysis of tactics
[10]. It investigated specific aspects like pass completion likelihood [11],
3D ball positioning in basketball [12], and the reconstruction of shuttle
trajectories in badminton videos [13]. To facilitate research in this domain,
numerous research collectives have made available comprehensive datasets,
including those by Pappalardo et. al. [14], Yu et. al. [15], SoccerTrack [16],
SoccerDB [17], and DeepSportRadar [18]. The SoccerNet dataset, introduced by
Giancola et. al. [19], has set benchmarks for over $12$ specific tasks in
soccer video analytics. These include areas such as action spotting [20],
camera calibration [21, 22], player tracking [23] and re-identification [21],
multi-view foul detection [24], comprehensive video captioning [25],
explainability [26], depth estimation [27] and game state reconstruction [28].
These datasets have become a cornerstone for yearly competitions [29, 30],
promoting cooperative research efforts in the field of sports video analysis.
In this work, we propose an easy-to-use library for action spotting, i.e. the
task of localizing events in untrimmed videos, identified with a single
timestamp.

###  II-B Action spotting

Giancola et. al. [19] introduced the task of action spotting, defined as the
process of localizing key actions within long untrimmed videos, such as
penalties, goals, or corner kicks in football. This task differs from temporal
activity localization, where activities are identified over durations [31]. In
contrast, action spotting focuses on the precise moment of an event, with a
single timestamp, in accordance with football regulations [32]. Giancola et.
al. [19] propose a first baseline to solve this task based on learnable
pooling methods, later improved with temporally-aware pooling [33]. Rongved
et. al. [34] developed a method using 3D ResNet on video frames analyzed in a
sliding window of five seconds. Multimodal techniques were explored by
Vanderplaetse et. al. [35] and Xarles et. al. [29], who merged visual and
auditory data for action detection. Further advancements include Cioppa et.
al.’s [36, 37] context-aware loss function that leverages temporal dynamics,
Vats et. al.’s [38] multi-tower CNN for managing action localization
uncertainty, and Tomei et. al.’s [39] approach of refining feature extraction
with a masking strategy targeting post-action frames. The current state-of-
the-art on SoccerNet-v2 for published methods has been set by Denize et. al.
[40], with their end-to-end methodology. This method outperforms previous
leaders like Soares et. al. [41], who employed an anchor-based strategy, and
Hong et. al. [42], pioneers of the precise temporal spotting (PTS) technique.
The PTS approach integrates an end-to-end trainable feature extraction and
spotting mechanism, utilizing a lightweight RegNet architecture enhanced with
GSM [43] and GRU [44] modules. This surpassed the 2022 challenge’s top
contenders, showcasing advancements over earlier methods like spatio-temporal
encoders [45], graph-based processing layers [46], and transformer models
[47]. In this work, we re-implement feature-based and end-to-end methods from
cornerstone action spotting algorithms [36, 33, 42, 48] into a unified
library.

##  III OSL-ActionSpotting

OSL-ActionSpotting is a streamlined, plug-and-play library tailored for
efficient action spotting in sports videos, suitable for football and other
sports. It merges various advanced action spotting algorithms into one
framework, promoting modularity and facilitating further research development
in this field.

Figure 2:  OSL-ActionSpotting contains methods for efficient data loading,
modularized action spotting, and comprehensive evaluation. The dataloader
provides videos $V$ or frame features $F$. The backbone converts the videos
$V$ into frame features $F$. The neck lifts the frame features $F$ into neck
features $F^{\prime}$, further processed by the spotting head that predicts
the actions $A$. The evaluation compares the action predictions $A$ with the
ground truth $GT$.

###  III-A Definitions

Action spotting in sports videos is the task of identifying and anchoring
temporally specific actions semantic within a video. Let $V$ be a video with
frames $i_{1},i_{2},...,i_{T}$, where $T$ is the total number of frames. The
objective is to detect the set of $n$ actions $A=\\{a_{1},a_{2},...,a_{n}\\}$
in $V$, each associated with a timestamp $t_{i}$. Formally, an action spotting
algorithm is defined as a function $\mathcal{F}:V\rightarrow A\times T$,
mapping the video $V$ to a set of action-timestamp pairs $(a_{i},t_{i})$. This
function aims to accurately align the predicted timestamps with the actual
occurrence times of actions in the video. The algorithmic structure can be
segmented into three primary components: the backbone, the neck, and the head.

Backbone. The backbone is the fundamental part of the action spotting
algorithm, primarily responsible for feature extraction. Given a video $V$
with frames $i_{1},i_{2},...,i_{T}$, the backbone processes these frames to
extract a set of features $F=\\{f_{1},f_{2},...,f_{T}\\}$. Formally, this can
be represented as:

$F=Backbone(i_{1},i_{2},...,i_{T})\,,$

where $F$ is the feature set corresponding to the frames in $V$.

Neck. The neck serves as an intermediate processing layer that refines and
transforms the features $F$ extracted by the backbone. Its purpose is to
enhance the feature representation for more effective action spotting. The
processed features $F^{\prime}$ can be expressed as:

$F^{\prime}=Neck(F)\,,$

where $F^{\prime}$ are the neck features input to the spotting head.

Head. The head is the final component of the algorithm, responsible for action
identification and timestamp assignment. It utilizes the refined features
$F^{\prime}$ to identify actions $A$ and their corresponding timestamps $T$.
This can be formulated as:

$(A,T)=Head(F^{\prime})\,,$

where $A$ is the set of detected actions and $T$ their timestamps.

Together, these components form the complete action spotting algorithm, where
the backbone extracts raw features from video frames, the neck refines these
features, and the head utilizes the refined features to detect and timestamp
actions. The pipeline is illustrated in Figure 2.

###  III-B Action Spotting Algorithms

The OSL-ActionSpotting library incorporates a variety of modular action
spotting algorithms, each consisting of a backbone, neck, and head, to address
different aspects of sports video analysis. The unified framework of OSL-
ActionSpotting is designed to operate with these algorithms, Here, we detail
some of the key action spotting algorithms already integrated into OSL-
ActionSpotting.

Temporally-Aware Learnable Pooling [33]. Backbone: The features are pre-
extracted offline using a CNN (e.g. ResNet), focusing on detailed spatial
analysis of video frames. Neck: It applies learnable and temporal pooling to
these features, emphasizing temporal dynamics and relevance to action
spotting. The learnable aspect is based on feature clustering (e.g. NetVLAD),
while the temporal aspect learns specific pooling before and after the action
of interest. Head: It processes further the pooled features with linear layers
to predict the actions and their timestamps as a clip classification task.

Context-Aware Loss Function (CALF) [36]. Backbone: CALF utilizes the same pre-
extracted features based on deep CNNs to learn spatial frame features. Neck:
The segmentation module learns the context of the action to spot, enhancing
the features with semantic information around the actions. Head: CALF employs
the context-enhanced features from the neck in its spotting module for precise
action localization regression for action candidates within the video clips.

Precise Temporal Spotting (PTS) [42]. Backbone: PTS learns spatio-temporal
features end-to-end with the remaining of the architecture. It typically
relies on lighter spatial CNN such as RegNetY with intermediate temporal
aggregation with GSM or TSM. Head: PTS does not contain any neck, it directly
processes the backbone features in its recurrent spotting head (e.g. GRU),
which achieves a precise localization of the actions through a frame
classification task.

These algorithms have been incorporated in OSL-ActionSpotting, demonstrating
the library’s capability to cater to diverse needs in sports video analysis.
Through the systematic integration of these diverse algorithms, OSL-
ActionSpotting offers a robust and flexible solution for action spotting,
adaptable to the specific requirements of different sports and analytical
objectives.

###  III-C Data Handling and Processing

In OSL-ActionSpotting, the data handling and processing are paramount to
ensure reproducible performance of action spotting algorithms. The library
accommodates two primary types of data loaders: feature-based and video-based,
gathered into a unified action spotting dataset format.

Feature-Based Data Loader. This loader is designed for scenarios where
features are pre-extracted and stored separately from the raw video data. It
is optimized for quick access and loading of these features, facilitating
efficient processing in use cases where the action spotting algorithms rely on
pre-computed feature sets. The feature-based data loader streamlines the
workflow by directly ingesting these features into the action spotting models,
bypassing the need for a backbone and thus speeding up the analysis process.

Video-Based Data Loader. The video-based data loader, on the other hand, is
tailored for processing raw video files directly, extracting features online
as part of the action spotting pipeline. OSL-ActionSpotting leverages both the
OpenCV video reader and the NVIDIA DALI (Data Loading Library) for this
purpose, an efficient video data loader that significantly accelerates the
preprocessing and feature extraction stages. DALI optimizes the data pipeline,
handling tasks like decoding, cropping, and resizing the video directly on the
GPU, which minimizes the latency and computational overhead associated with
these operations. The DALI-integrated video-based data loader in OSL-
ActionSpotting streamlines the training process by efficiently handling large-
scale video datasets, ensuring fast and scalable video processing.

Unified action spotting dataset format. This new dataset format is a core
aspect of OSL-ActionSpotting, and is a novelty for the field of action
spotting. It is designed to harmonize the input data structure across various
action spotting datasets, and encapsulates the essential elements of action
spotting. Inspired by the COCO format for image understanding, it is a single
JSON file that includes the path of all videos or features, along with their
annotations and associated metadata. We envision this format to facilitate the
integration of new datasets in OSL-ActionSpotting, enabling easier training,
fine-tuning, testing, and deployment on new domains.

In summary, OSL-ActionSpotting’s data handling, with its feature-based and
video-based data loaders, as well as its unified action spotting dataset JSON
format, offers a streamlined and adaptable framework for efficient action
spotting training on novel domain, optimizing data preparation whether using
pre-extracted features or raw video content.

###  III-D Evaluation metrics

In OSL-ActionSpotting, the evaluation framework for action spotting algorithms
focuses on measuring their effectiveness and accuracy using two main metrics:
loose and tight average mean Average Precision (mAP).

Loose Average mAP: This metric assesses the algorithm’s performance with a
lenient approach, allowing predictions to be considered correct if they fall
within a broad temporal window around the actual event, ranging from $5$ to
$60$ seconds. It gauges the algorithm’s general ability to detect actions
without requiring pinpoint temporal accuracy.

Tight Average mAP: Contrasting with the loose approach, the tight average mAP
enforces a stringent temporal matching criterion, where predictions must
closely align with the ground truth action timestamps, within a $1$ to $5$
second tolerance. This metric evaluates the algorithm’s precision in
accurately localizing actions in time.

These two mAP metrics provide a comprehensive view of an action spotting
algorithm’s performance in OSL-ActionSpotting, balancing between general
detection capabilities and precise temporal localization. Through this
evaluation approach, OSL-ActionSpotting ensures a robust assessment of action
spotting algorithms, facilitating the refinement and enhancement of their
performance in sports video analysis.

###  III-E User-friendly Tools and Module

OSL-ActionSpotting utilizes the PyTorch Lightning framework to offer
streamlined tools for training, inference, and evaluation, enhancing the ease
of use and efficiency in training action spotting algorithms. The training
tools facilitate model training with automated batch processing and
checkpointing, allowing for flexible and efficient model development. The
inference tools enable quick and accurate action detection in videos,
optimized for both real-time and batch-processing environments. The evaluation
tools provide detailed performance metrics to assess and compare the
effectiveness of action spotting models within OSL-ActionSpotting. These
tools, integrated in OSL-ActionSpotting with PyTorch Lightning, simplify the
deep learning workflow, making advanced action spotting accessible and
manageable for users across the sports analytics field.

##  IV Experiments / Benchmark

We validate the reproducibility of our OSL-ActionSpotting implementation with
respect to established methods.

Dataset. We focus our experiments on the SoccerNet-v2 action spotting dataset
[20], as it is the most widely used dataset in the literature. Yet, more
datasets can be tested with our library. SoccerNet-v2 provides videos for
$500$ football games from the big five European leagues, fully annotated with
more than $110{,}458$ temporally-anchored actions, from $17$ common action
classes. We refer to the SoccerNet-v2 paper [20] for a more detailed
description of the dataset.

Methods. For the feature-based methods, we focus our experiments on the pre-
extracted ResNet-152 features reduced with a PCA at a dimension of 512,
provided with the SoccerNet-v2 dataset [20]. For the Temporally-Aware
Learnable Pooling methods [33], we test the non-parametric pooling necks
(MaxPooling, AvgPool), the learnable pooling necks (NetVLAD++, NetRVLAD++) and
the temporally-aware pooling necks (Maxpool++, Avgpool++, NetVLAD++,
NetRVLAD++). For the cluster-based approaches, we set the number of clusters
to $64$. The head is a single linear layer that projects the neck features to
a dimension equal to the class number, followed by a softmax activation for
the logits. We keep the training parameters similar to the original
implementation. For the Context-Aware Loss Function (CALF) method [36], we
define the segmentation module as the neck, and the spotting head as the head.
We keep the training parameters and the temporal parameters similar to the
original implementation. For the end-to-end approach Precise Temporal Spotting
(PTS) [42], we use the 224p videos at 25fps as input. The backbone processes
the frames at 2fps with RegNetY (RNY) and a GSM temporal shift. PTS does not
have any neck, and we select the GRU head to accumulate the temporal
information and predict the class activations. We keep the training parameters
similar to the original implementation meant for the SoccerNet-v2 dataset.

Results. We present in Table I the results of our experiments. We reproduce
the same performances as the original implementation in terms of loose and
tight Average-mAP. We report the training time (per epoch between
parenthesis), as well as the time for inference of the complete testing set of
SoccerNet-v2 composed of $100$ videos of $45$min. The timing for all methods
was estimated on 1 GPU RTX1080, 2 CPU cores and 32GB RAM, except for the PTS
that required 4 GPU RTX A500 and 80GB of RAM.

TABLE I:  OSL-ActionSpotting: Reproduced Results.

Method | Average-mAP | Timing (sec)
---|---|---
loose | tight | Training | Testing
Maxpool [33] | 20.8 |  2.1 | 1268 (7) |  118
Avgpool [33] | 29.4 |  2.3 |  886 (7) |  118
NetVLAD [33] | 46.3 |  4.4 | 1328 (7) |  119
NetRVLAD [33] | 44.8 |  4.8 | 1371 (7) |  118
Maxpool++ [33] | 32.2 |  5.3 | 1172 (7) |  118
Avgpool++ [33] | 40.8 |  6.9 |  974 (7) |  118
NetVLAD++ [33] | 51.5 |  8.1 | 1185 (8) |  120
NetRVLAD++ [33] | 49.8 |  8.3 | 1147 (8) |  118
CALF [36] | 39.5 | 12.4 | 1639 (4) |  26
PTS (RNY002) [42] | 70.4 | 63.9 | 140700 (1200) | 1500
PTS (RNY008) [42] | 72.2 | 66.2 | 249780 (1500) | 1800

##  V Discussions

Performances reproduction. OSL-ActionSpotting successfully meets its primary
goal of reproducing the performance metrics documented in existing literature,
demonstrating its capability and reliability in the domain of sports video
analysis.

DALI: accelerated video loading. Integrating DALI for video loading in OSL-
ActionSpotting improved the processing of the video data, overcoming the
inefficiencies of traditional CPU-based loading methods like OpenCV video and
PyTorch image data loaders. This shift to GPU processing with DALI results in
significant time improvement, streamlining OSL-ActionSpotting ’s data
pipeline. Compared to OpenCV video data loaders, best cases result in around
33% time improvement for the training steps and 50% improvement for each
epoch’s validation steps. Furthermore, compared to the PyTorch image data
loader, we remove the need of pre-extracting frames from videos. Pre-
extracting frame typically requires a significant extra volume space to store
this data, typically around 10 fold, and presents a reading bottleneck due to
a large number of file access. By adopting DALI, OSL-ActionSpotting enhances
pre-processing efficiency and sets a new standard for speed, storage, and
performance in sports video analysis, paving the way for more sophisticated
and expansive video pre-processing for action spotting research, including
larger resolution and higher frame rate.

JSON-based action spotting dataset format. The JSON-based action spotting
dataset format in OSL-ActionSpotting marks a significant advance in
standardizing data handling for sports analytics, aligning with algorithm
needs by organizing timestamps, action labels, and metadata cohesively. This
format enhances interoperability and eases integration with analytics tools,
streamlining dataset preparation and parsing for efficient model training and
evaluation. Standardization with OSL-ActionSpotting’s JSON format boosts
consistency in video analysis, supporting more scalable and collaborative
research efforts, and facilitating innovation in sports analytics.

##  VI Conclusion

OSL-ActionSpotting marks a novel development in sports video analysis by
introducing the first Python library to consolidate major action spotting
algorithms into a modular framework, fostering future algorithmic development.
Its efficient video data loader, powered by DALI, streamlines video pre-
processing, facilitating rapid training of end-to-end algorithms. Furthermore,
the introduction of a novel JSON-based action spotting dataset format with
OSL-ActionSpotting enhances the adaptability and application of its algorithms
across various datasets and video analyses. We envision OSL-ActionSpotting as
the one-stop Python library for action spotting algorithms, that will
centralize the efforts of the sports analytics community into an easy-to-use
modular library, accelerating the development and deployment of these tools.

## Acknowledgment

A. Cioppa is funded by the F.R.S.-FNRS. This work was partly supported by the
King Abdullah University of Science and Technology (KAUST) Office of Sponsored
Research through the Visual Computing Center (VCC) funding and the SDAIA-KAUST
Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST
AI). Bruno Cabado wish to thanks the Axencia Galega de Innovación the grant
received through its Industrial Doctorate program (23/IN606D/2021/2612054).
CITIC is funded by Xunta de Galicia (ED431G 2019/01) and ERDF funds.

## References

  * [1] G. Thomas, R. Gade, T. B. Moeslund, P. Carr, and A. Hilton, “Computer vision for sports: current applications and research topics,” Comput. Vis. Image Underst., vol. 159, pp. 3–18, Jun. 2017.
  * [2] B. T. Naik, M. F. Hashmi, N. D. Bokde, and Z. M. Yaseen, “A comprehensive review of computer vision in sports: Open issues, future trends and research directions,” Appl. Sci., vol. 12, pp. 1–49, Apr. 2022.
  * [3] F. Wu, Q. Wang, J. Bian, H. Xiong, N. Ding, F. Lu, J. Cheng, and D. Dou, “A survey on video action recognition in sports: Datasets, methods and applications,” arXiv, vol. abs/2206.01038, 2022.
  * [4] A. Cioppa, A. Deliège, and M. Van Droogenbroeck, “A bottom-up approach based on semantics for the interpretation of the main camera stream in soccer games,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Salt Lake City, UT, USA), pp. 1846–1855, Jun. 2018.
  * [5] B. Cabado, B. Guijarro-Berdiñas, and E. J. Padrón, “Real-time classification of handball game situations,” in IEEE Int. Conf. Tools Artif. Intell. (ICTAI), (Macao, China), pp. 686–691, Oct. 2022.
  * [6] R. Vandeghen, A. Cioppa, and M. Van Droogenbroeck, “Semi-supervised training to improve player and ball detection in soccer,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (New Orleans, LA, USA), pp. 3480–3489, Jun. 2022.
  * [7] A. Maglo, A. Orcesi, and Q.-C. Pham, “Efficient tracking of team sport players with few game-specific annotations,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (New Orleans, LA, USA), pp. 3460–3470, Jun. 2022.
  * [8] A. Cioppa, A. Deliege, M. Istasse, C. De Vleeschouwer, and M. Van Droogenbroeck, “ARTHuS: Adaptive real-time human segmentation in sports through online distillation,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Long Beach, CA, USA), pp. 2505–2514, Jun. 2019.
  * [9] V. Somers, C. De Vleeschouwer, and A. Alahi, “Body part-based representation learning for occluded person Re-Identification,” in IEEE/CVF Winter Conf. Appl. Comput. Vis. (WACV), (Waikoloa, HI, USA), pp. 1613–1623, Jan. 2023.
  * [10] G. Suzuki, S. Takahashi, T. Ogawa, and M. Haseyama, “Team tactics estimation in soccer videos based on a deep extreme learning machine and characteristics of the tactics,” IEEE Access, vol. 7, pp. 153238–153248, 2019.
  * [11] A. Arbués Sangüesa, A. Martín, J. Fernández, C. Ballester, and G. Haro, “Using player’s body-orientation to model pass feasibility in soccer,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Seattle, WA, USA), pp. 3875–3884, Jun. 2020.
  * [12] G. Van Zandycke and C. De Vleeschouwer, “3D ball localization from a single calibrated image,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (New Orleans, LA, USA), pp. 3471–3479, Jun. 2022.
  * [13] P. Liu and J.-H. Wang, “MonoTrack: Shuttle trajectory reconstruction from monocular badminton video,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (New Orleans, LA, USA), pp. 3512–3521, Jun. 2022.
  * [14] L. Pappalardo, P. Cintia, A. Rossi, E. Massucco, P. Ferragina, D. Pedreschi, and F. Giannotti, “A public data set of spatio-temporal match events in soccer competitions,” Sci. Data, vol. 6, pp. 1–15, Oct. 2019.
  * [15] J. Yu, A. Lei, Z. Song, T. Wang, H. Cai, and N. Feng, “Comprehensive dataset of broadcast soccer videos,” in IEEE Conf. Multimedia Inf. Process. Retr. (MIPR), (Miami, FL, USA), pp. 418–423, Apr. 2018.
  * [16] A. Scott, I. Uchida, M. Onishi, Y. Kameda, K. Fukui, and K. Fujii, “SoccerTrack: A dataset and tracking algorithm for soccer with fish-eye and drone videos,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (New Orleans, LA, USA), pp. 3568–3578, Jun. 2022.
  * [17] Y. Jiang, K. Cui, L. Chen, C. Wang, and C. Xu, “SoccerDB: A large-scale database for comprehensive video understanding,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Seattle, WA, USA), p. 1–8, ACM, Oct. 2020.
  * [18] M. Istasse, V. Somers, P. Elancheliyan, J. De, and D. Zambrano, “DeepSportradar-v2: A multi-sport computer vision dataset for sport understandings,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Ottawa, Ontario, Can.), pp. 23–29, ACM, Oct. 2023.
  * [19] S. Giancola, M. Amine, T. Dghaily, and B. Ghanem, “SoccerNet: A scalable dataset for action spotting in soccer videos,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Salt Lake City, UT, USA), pp. 1792–179210, Jun. 2018.
  * [20] A. Deliège, A. Cioppa, S. Giancola, M. J. Seikavandi, J. V. Dueholm, K. Nasrollahi, B. Ghanem, T. B. Moeslund, and M. Van Droogenbroeck, “SoccerNet-v2: A dataset and benchmarks for holistic understanding of broadcast soccer videos,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Nashville, TN, USA), pp. 4508–4519, Jun. 2021.
  * [21] A. Cioppa, A. Deliège, S. Giancola, B. Ghanem, and M. Van Droogenbroeck, “Scaling up SoccerNet with multi-view spatial localization and re-identification,” Sci. Data, vol. 9, pp. 1–9, Jun. 2022.
  * [22] F. Magera, T. Hoyoux, O. Barnich, and M. Van Droogenbroeck, “A universal protocol to benchmark camera calibration for sports,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Seattle, WA, USA), Jun. 2024.
  * [23] A. Cioppa, S. Giancola, A. Deliege, L. Kang, X. Zhou, Z. Cheng, B. Ghanem, and M. Van Droogenbroeck, “SoccerNet-tracking: Multiple object tracking dataset and benchmark in soccer videos,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (New Orleans, LA, USA), pp. 3490–3501, Jun. 2022.
  * [24] J. Held, A. Cioppa, S. Giancola, A. Hamdi, B. Ghanem, and M. Van Droogenbroeck, “VARS: Video assistant referee system for automated soccer decision making from multiple views,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Vancouver, Can.), pp. 5086–5097, Jun. 2023.
  * [25] H. Mkhallati, A. Cioppa, S. Giancola, B. Ghanem, and M. Van Droogenbroeck, “SoccerNet-caption: Dense video captioning for soccer broadcasts commentaries,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Vancouver, Can.), pp. 5074–5085, Jun. 2023.
  * [26] J. Held, H. Itani, A. Cioppa, S. Giancola, B. Ghanem, and M. Van Droogenbroeck, “X-vars: Introducing explainability in football refereeing with multi-modal large language models,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Seattle, WA, USA), Jun. 2024.
  * [27] A. Leduc, A. Cioppa, S. Giancola, B. Ghanem, and M. Van Droogenbroeck, “SoccerNet-Depth: a scalable dataset for monocular depth estimation in sports videos,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Seattle, WA, USA), Jun. 2024.
  * [28] V. Somers, V. Joos, S. Giancola, A. Cioppa, S. A. Ghasemzadeh, F. Magera, B. Standaert, A. M. Mansourian, X. Zhou, S. Kasaei, B. Ghanem, A. Alahi, M. Van Droogenbroeck, and C. De Vleeschouwer, “SoccerNet game state reconstruction: End-to-end athlete tracking and identification on a minimap,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Seattle, WA, USA), Jun. 2024.
  * [29] S. Giancola, A. Cioppa, A. Deliège, F. Magera, V. Somers, L. Kang, X. Zhou, O. Barnich, C. De Vleeschouwer, A. Alahi, B. Ghanem, M. Van Droogenbroeck, and et. al., “SoccerNet 2022 challenges results,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Lisbon, Port.), pp. 75–86, ACM, Oct. 2022.
  * [30] A. Cioppa, S. Giancola, V. Somers, F. Magera, X. Zhou, H. Mkhallati, A. Deliège, J. Held, C. Hinojosa, A. M. Mansourian, P. Miralles, O. Barnich, C. De Vleeschouwer, A. Alahi, B. Ghanem, M. Van Droogenbroeck, and et. al., “SoccerNet 2023 challenges results,” arXiv, vol. abs/2309.06006, 2023.
  * [31] F. Caba Heilbron, V. Escorcia, B. Ghanem, and J. Carlos Niebles, “ActivityNet: A large-scale video benchmark for human activity understanding,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (Boston, MA, USA), pp. 961–970, Jun. 2015.
  * [32] IFAB, “Laws of the game,” tech. rep., The International Football Association Board, Zurich, Switzerland, 2022.
  * [33] S. Giancola and B. Ghanem, “Temporally-aware feature pooling for action spotting in soccer broadcasts,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. (CVPR), (Nashville, TN, USA), pp. 4490–4499, Jun. 2021.
  * [34] O. Rongved, M. Stige, S. Hicks, V. Thambawita, C. Midoglu, E. Zouganeli, D. Johansen, M. Riegler, and P. Halvorsen, “Automated event detection and classification in soccer: The potential of using multiple modalities,” Machine Learning and Knowledge Extraction, vol. 3, pp. 1–25, Dec. 2021.
  * [35] B. Vanderplaetse and S. Dupont, “Improved soccer action spotting using both audio and video streams,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Seattle, WA, USA), pp. 3921–3931, Jun. 2020.
  * [36] A. Cioppa, A. Deliège, S. Giancola, B. Ghanem, M. Van Droogenbroeck, R. Gade, and T. B. Moeslund, “A context-aware loss function for action spotting in soccer videos,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (Seattle, WA, USA), pp. 13123–13133, Jun. 2020.
  * [37] A. Cioppa, A. Deliège, S. Giancola, F. Magera, O. Barnich, B. Ghanem, and M. Van Droogenbroeck, “Camera calibration and player localization in SoccerNet-v2 and investigation of their representations for action spotting,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Nashville, TN, USA), pp. 4532–4541, Jun. 2021.
  * [38] K. Vats, M. Fani, P. Walters, D. A. Clausi, and J. Zelek, “Event detection in coarsely annotated sports videos via parallel multi receptive field 1D convolutions,” arXiv, vol. abs/2004.06172, 2020.
  * [39] M. Tomei, L. Baraldi, S. Calderara, S. Bronzin, and R. Cucchiara, “RMS-net: Regression and masking for soccer event spotting,” in IEEE Int. Conf. Pattern Recognit. (ICPR), (Milan, Italy), pp. 7699–7706, Jan. 2021.
  * [40] J. Denize, M. Liashuha, J. Rabarisoa, A. Orcesi, and R. Hérault, “COMEDIAN: Self-supervised learning and knowledge distillation for action spotting using transformers,” in IEEE Winter Conf. Appl. Comput. Vis. Work. (WACVW), (Waikoloa, HI, USA), pp. 530–540, Jan. 2024.
  * [41] J. V. B. Soares, A. Shah, and T. Biswas, “Temporally precise action spotting in soccer videos using dense detection anchors,” in IEEE Int. Conf. Image Process. (ICIP), (Bordeaux, France), pp. 2796–2800, Oct. 2022.
  * [42] J. Hong, H. Zhang, M. Gharbi, M. Fisher, and K. Fatahalian, “Spotting temporally precise, fine-grained events in video,” in Eur. Conf. Comput. Vis. (ECCV), vol. 13695 of Lect. Notes Comput. Sci., (Tel Aviv, Israël), pp. 33–51, Springer Nat. Switz., 2022.
  * [43] S. Sudhakaran, S. Escalera, and O. Lanz, “Gate-shift networks for video action recognition,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (Seattle, WA, USA), pp. 1099–1108, Jun. 2020.
  * [44] K. Cho, B. van Merrienboer, D. Bahdanau, and Y. Bengio, “On the properties of neural machine translation: Encoder-decoder approaches,” in Workshop on Syntax, Semantics and Structure in Statistical Translation, (Doha, Qatar), pp. 103–111, Association for Computational Linguistics, Oct. 2014.
  * [45] A. Darwish and T. El-Shabrway, “STE: Spatio-temporal encoder for action spotting in soccer videos,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Lisbon, Port.), pp. 87–92, ACM, Oct. 2022.
  * [46] A. Cartas, C. Ballester, and G. Haro, “A graph-based method for soccer action spotting using unsupervised player classification,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Lisbon, Port.), pp. 93–102, ACM, Oct. 2022.
  * [47] H. Zhu, J. Liang, C. Lin, J. Zhang, and J. Hu, “A transformer-based system for action spotting in soccer videos,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Lisbon, Port.), pp. 103–109, ACM, Oct. 2022.
  * [48] B. Cabado, A. Cioppa, S. Giancola, A. Villa, B. Guijarro-Berdiñas, E. Padrón, B. Ghanem, and M. Van Droogenbroeck, “Beyond the Premier: Assessing action spotting transfer capability across diverse domains,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Seattle, WA, USA), Jun. 2024.


# Non-Parametric Quickest Detection of a Change in the Mean of an Observation
Sequence

Yuchen Liang  ECE Department and Coordinated Science Lab
University of Illinois at Urbana-Champaign
Urbana, IL
<EMAIL_ADDRESS>Venugopal V. Veeravalli This work was supported in part
by the National Science Foundation under grant ECCS-2033900, and by the Army
Research Laboratory under Cooperative Agreement W911NF-17-2-0196, through the
University of Illinois at Urbana-Champaign. ECE Department and Coordinated
Science Lab
University of Illinois at Urbana-Champaign
Urbana, IL
<EMAIL_ADDRESS>
###### Abstract

We study the problem of quickest detection of a change in the mean of an
observation sequence, under the assumption that both the pre- and post-change
distributions have bounded support. We first study the case where the pre-
change distribution is known, and then study the extension where only the mean
and variance of the pre-change distribution are known. In both cases, no
knowledge of the post-change distribution is assumed other than that it has
bounded support. For the case where the pre-change distribution is known, we
derive a test that asymptotically minimizes the worst-case detection delay
over all post-change distributions, as the false alarm rate goes to zero. We
then study the limiting form of the optimal test as the gap between the pre-
and post-change means goes to zero, which we call the Mean-Change Test (MCT).
We show that the MCT can be designed with only knowledge of the mean and
variance of the pre-change distribution. We validate our analysis through
numerical results for detecting a change in the mean of a beta distribution.
We also demonstrate the use of the MCT for pandemic monitoring.

###### Index Terms:

Quickest change detection (QCD), non-parametric methods, minimax robust
detection

##  I Introduction

Quickest Change Detection (QCD) is a fundamental problem in mathematical
statistics. Given a stochastic sequence whose distribution changes at some
unknown change-point, the goal is to detect the change after it occurs as
quickly as possible, subject to false alarm constraints. The QCD framework has
had a wide range of applications, including but not limited to line-outage in
power systems [1], dim-target manoeuvre detection [2], stochastic process
control [3], structural health monitoring [4], and, more recently, in the
Multi-Armed Bandit (MAB) problem with piece-wise stationary bandits [5]. Two
formulations are used in the classical QCD problem: the Bayesian formulation
[6], where the change-point is assumed to follow some prior distribution, and
the minimax formulation [7, 8], where the worst-case detection delay is
minimized over all possible change-points, subject to false alarm constraints.
In both the Bayesian and minimax settings, if the pre- and post-change
distributions are known, low-complexity efficient solutions to the QCD problem
can be found [9].

In many practical situations, we may not know the exact distribution in the
pre- or post-change regimes. Although it is reasonable to assume that we can
obtain a large amount of data in the pre-change regime, this may not be the
case for the post-change regime. In applications such as the epidemic
detection problem and the MAB problem, a change in a specific statistic (e.g.,
the mean) of the distribution is of interest. This is different from the
original QCD problem where any distributional change needs to be detected.
Furthermore, in many applications, the support of the distribution is bounded.
For example, the observations representing the fraction of some specific group
in the entire population are bounded between 0 and 1. This is the case, for
example, in the pandemic monitoring problem that we discuss in detail in
Section IV.

There have been a number of lines of work on the QCD problem when the pre-
and/or post-change distributions are not completely known. The most prevalent
is the Generalized Likelihood Ratio (GLR) approach, in which the maximum of
the test statistics corresponding to each possible change-points is used to
construct the test. A GLR approach for a Gaussian mean-change detection
problem is proposed in [10]. A GLR test for the case where the pre- and post-
change distributions come from one-parameter exponential families is analyzed
in [11]. A kernel approach to construct GLR statistics is discussed in [12].
More recently, a GLR mean-change test for sub-Gaussian observations using scan
statistics is proposed and analyzed in [13], and this approach is applied to
the MAB problem in [5]. In all of these methods, the complexity of computing
the test statistic at each time-step grows at least linearly with the number
of samples. In practice, a windowed version of the GLR test statistic is used
to keep the complexity small, while suffering some loss in performance. An
alternative to the GLR approach was given in [14], where a histogram is used
to estimate the post-change distribution, and a low complexity test with a
recursive structure is constructed.

Another line of work is the one based on a minimax robust approach [15], in
which it is assumed that the distributions come from mutually exclusive
uncertainty classes. Under certain conditions on the uncertainty classes,
e.g., joint stochastic boundedness [9], a low-complexity saddle-point solution
to the minimax robust QCD problem can be found. In this paper, we use an
asymptotic version of the minimax robust QCD problem formulation to develop
algorithms for the non-parametric detection of a change in mean of an
observation sequence. Our contributions are as follows:

  1. 1.

We study the problem of quickest detection of a change in the mean of an
observation sequence under the assumption that no knowledge of the post-change
distribution is available other than that it has bounded support.

  2. 2.

For the case where the pre-change distribution is known, we derive a test that
asymptotically minimizes the worst-case detection delay over all possible
post-change distributions, as the false alarm rate goes to zero.

  3. 3.

We study the limiting form of the optimal test as the gap between the pre- and
post-change means goes to zero, which we call the Mean-Change Test (MCT). We
show that the MCT can be designed with only knowledge of the mean and variance
of the pre-change distribution.

  4. 4.

We validate our analysis through numerical results for detecting a change in
the mean of a beta distribution. We also demonstrate the use of the MCT for
pandemic monitoring.

##  II Problem Statement

Let $X_{1},\dots,X_{t},\dots\in[0,1]$ be independent samples, with
$X_{1},\dots,X_{\nu}\sim P_{0}$, and $X_{\nu+1},\dots\sim P_{1}$. Let
$\mathbb{P}^{P_{0},P_{1}}_{\nu}\left\\{\cdot\right\\}$ denote the probability
measure on the entire sequence of observations when the pre- and post-change
distributions are $P_{0}$ and $P_{1}$, respectively, and the change-point is
at $t=\nu$, and let $\mathbb{E}^{P_{0},P_{1}}_{\nu}\left[\cdot\right]$ denote
the corresponding expectation. We will first consider the case where $P_{0}$
is completely known, and then study extensions to the cases where only partial
(moment) information about $P_{0}$ is available. The change-time $\nu$ is
unknown but deterministic. The problem is to detect the change quickly while
not causing too many false alarms. Let $\tau$ be a stopping time [9] defined
on the observation sequence associated with the detection rule, i.e. $\tau$ is
the time at which we stop taking observations and declare that the change has
occurred. If both the pre- and post-change distributions are known, Lorden [7]
proposed solving the following optimization problem to find the best stopping
time $\tau$:

$\inf_{\tau\in\mathcal{C}_{\alpha}}\text{WADD}^{P_{0},P_{1}}\left(\tau\right)$
(1)

where

$\text{WADD}^{P_{0},P_{1}}\left(\tau\right):=\\\ \sup_{\nu\geq
1}\operatorname*{ess\,sup}\mathbb{E}^{P_{0},P_{1}}_{\nu}\left[\left(\tau-\nu+1\right)^{+}|X_{1},\ldots,X_{\nu-1}\right]$
(2)

is a worst-case delay metric and

$\mathcal{C}^{\\{P_{0}\\}}_{\alpha}:=\left\\{\tau:\text{FAR}^{P_{0}}\left(\tau\right)\leq\alpha\right\\}$
(3)

is the feasible set where
$\text{FAR}^{P_{0}}\left(\tau\right):=\mathbb{E}^{P_{0},P_{1}}_{\infty}\left[\tau\right]^{-1}$.
Note that $\mathbb{E}^{P_{0},P_{1}}_{\infty}\left[\cdot\right]$ is the
expectation operator when the change never happens, and
$(\cdot)^{+}:=\max\\{0,\cdot\\}$.

Lorden also showed that Page’s Cumulative Sum (CUSUM) algorithm [16] whose
test statistic is given by:

$\begin{split}\Lambda^{P_{0},P_{1}}(t)&=\max_{1\leq k\leq t}\sum_{i=k}^{t}\ln
L^{P_{0},P_{1}}(X_{i})\\\ &=\left(\Lambda^{P_{0},P_{1}}(t-1)+\ln
L^{P_{0},P_{1}}(X_{t})\right)^{+}\end{split}$ (4)

with $\Lambda^{P_{0},P_{1}}(0)=0$ solves the problem in (2) asymptotically,
where $L^{P_{0},P_{1}}(x)=p_{1}(x)/p_{0}(x)$ is the likelihood ratio between
the densities. The CUSUM stopping rule is given by:

$\tau\left(\Lambda^{P_{0},P_{1}},b_{\alpha}\right):=\inf\\{t:\Lambda^{P_{0},P_{1}}(t)\geq
b_{\alpha}\\}$ (5)

where $b_{\alpha}:=|\ln\alpha|$. It was shown by Moustakides [17] that Page’s
test is exactly optimal for the problem in (2).

When the pre-change and post-change distributions are unknown but belong to
some uncertainty sets, a minimax robust metric can be applied:

$\inf_{\tau\in\mathcal{C}_{\alpha}^{\mathcal{P}_{0}}}\sup_{(P_{0},P_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau\right)$
(6)

where the feasible set becomes

$\mathcal{C}_{\alpha}^{\mathcal{P}_{0}}=\left\\{\tau:\sup_{P_{0}\in\mathcal{P}_{0}}\text{FAR}^{P_{0}}\left(\tau\right)\leq\alpha\right\\}$
(7)

A pair of uncertainty sets $(\mathcal{P}_{0},\mathcal{P}_{1})$ is said to be
jointly stochastically (JS) bounded by
$(\bar{P}_{0},\bar{P}_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}$ if, for any
$(P_{0},P_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}$ and any $t>0$,

$\displaystyle P_{0}\\{L^{\bar{P}_{0},\bar{P}_{1}}(X)>t\\}$
$\displaystyle\leq\bar{P}_{0}\\{L^{\bar{P}_{0},\bar{P}_{1}}(X)>t\\}$ (8)
$\displaystyle P_{1}\\{L^{\bar{P}_{0},\bar{P}_{1}}(X)>t\\}$
$\displaystyle\geq\bar{P}_{1}\\{L^{\bar{P}_{0},\bar{P}_{1}}(X)>t\\}$ (9)

where $L^{\bar{P}_{0},\bar{P}_{1}}$ is the likelihood ratio between
$\bar{P}_{1}$ and $\bar{P}_{0}$ as defined previously [9]. The distributions
$\bar{P}_{0}$ and $\bar{P}_{1})$ are called least favorable distributions
(LFDs) within the classes ${\cal P}_{0}$ and ${\cal P}_{1}$, respectively. If
the pair of pre- and post-change uncertainty sets is JS bounded, the test
statistic $\Lambda^{\bar{P}_{0},\bar{P}_{1}}(t)$ with the stopping rule
$\tau(\Lambda^{\bar{P}_{0},\bar{P}_{1}},b_{\alpha})$ solves (6) exactly [18].

A pair of uncertainty sets $(\mathcal{P}_{0},\mathcal{P}_{1})$ is said to be
weakly stochastically (WS) bounded by
$(\tilde{P}_{0},\tilde{P}_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}$ if

$D(\tilde{P}_{1}||\tilde{P}_{0})\leq
D(P_{1}||\tilde{P}_{0})-D(P_{1}||\tilde{P}_{1})$ (10)

for all $P_{1}\in\mathcal{P}_{1}$, and

$\mathbb{E}^{P_{0}}\left[L^{\tilde{P}_{0},\tilde{P}_{1}}(X)\right]\leq\mathbb{E}^{\tilde{P}_{0}}\left[L^{\tilde{P}_{0},\tilde{P}_{1}}(X)\right]=1$
(11)

for all $P_{0}\in\mathcal{P}_{0}$ [2], where
$\mathbb{E}^{P}\left[\cdot\right]$ denotes the expectation operator with
respect to distribution $P$. It is shown in [2] that if a pair of uncertainty
sets is JS bounded by $(\bar{P}_{0},\bar{P}_{1})$, it is also WS bounded by
$(\bar{P}_{0},\bar{P}_{1})$.

######  Theorem II.1.

[2] If $(\tilde{P}_{0},\tilde{P}_{1})$ solves

$\inf_{(P_{0},P_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}}D(P_{1}||P_{0})$
(12)

and if furthermore, $\mathcal{P}_{1}$ is convex, and (11) holds for all
$P_{0}\in\mathcal{P}_{0}$, then $(\mathcal{P}_{0},\mathcal{P}_{1})$ is WS
bounded by $(\tilde{P}_{0},\tilde{P}_{1})$, and
$\tau(\Lambda^{\tilde{P}_{0},\tilde{P}_{1}},b_{\alpha})$ solves the problem in
(6) asymptotically as $\alpha\to 0$. Also, the worst-case delay is

$\small\inf_{\tau\in\mathcal{C}_{\alpha}^{\mathcal{P}_{0}}}\sup_{(P_{0},P_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau\right)=\frac{|\ln\alpha|}{D(\tilde{P}_{1}||\tilde{P}_{0})}(1+o(1))$
(13)

In this paper, we consider the problem of quickest change detection for
observations with bounded support. The goal is to construct a test to detect
when the mean of the observations exceeds some pre-specified threshold, i.e.,
$P_{1}\in\mathcal{P}_{1}$ such that

$\mathcal{P}_{1}:=\\{P:\mathbb{E}^{P}\left[X\right]\geq\eta>\mu_{0}\\}$ (14)

In this expression, $X$ denotes a generic observation in the sequence, $\eta$
is a pre-designed threshold on the mean, and
$\mu_{0}:=\mathbb{E}^{P_{0}}\left[X\right]$. Define

$\Delta:=\frac{\eta-\mu_{0}}{2}$ (15)

Also, for $i=0,1$, let the density (w.r.t. the Lebesgue measure) of $P_{i}$ be
$p_{i}$. Define

$\kappa_{0}(\lambda)=\ln\mathbb{E}^{P_{0}}\left[e^{\lambda X}\right]$ (16)

to be the cumulant-generating functiong (cgf) under measure $P_{0}$. We
present our main results below.

##  III Main Results

###  III-A Known Pre-change Distribution

Throughout we will assume that $\mathcal{P}_{1}$ is as defined in (14). In
this subsection, we study the case where $\mathcal{P}_{0}=\\{P_{0}\\}$.

######  Theorem III.1.

For ${\cal P}_{0}=P_{0}$, and ${\cal P}_{1}$ given in (14), define

$p_{1}^{*}(x)=p_{0}(x)e^{\lambda^{*}x-\kappa_{0}(\lambda^{*})}$ (17)

where $\kappa_{0}(\lambda)$ is the cgf under $P_{0}$ and $\lambda^{*}$
satisfies

$\kappa_{0}^{\prime}(\lambda^{*}):=\frac{\mathbb{E}^{P_{0}}\left[Xe^{\lambda^{*}X}\right]}{\mathbb{E}^{P_{0}}\left[e^{\lambda^{*}X}\right]}=\eta$
(18)

Then, the statistic

$\Lambda^{P_{0},P_{1}^{*}}(t)=\max_{1\leq k\leq
t}\sum_{i=k}^{t}\left(\lambda^{*}X_{i}-\kappa_{0}(\lambda^{*})\right)$ (19)

and the stopping rule $\tau(\Lambda^{P_{0},P_{1}^{*}},b_{\alpha})$ with
threshold $b_{\alpha}=|\ln{\alpha}|$ solves the minimax robust problem in (6)
asymptotically as $\alpha\to 0$, and

$\small\inf_{\tau\in\mathcal{C}_{\alpha}^{\mathcal{P}_{0}}}\sup_{(P_{0},P_{1})\in\mathcal{P}_{0}\times\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau\right)=\frac{|\ln{\alpha}|}{\lambda^{*}\eta-\kappa_{0}(\lambda^{*})}(1+o(1))$
(20)

###### Proof.

We follow the procedure outlined in [19, Sec. 6.4.1]. We want to minimize
$D(P_{1}||P_{0})=\mathbb{E}^{P_{1}}\left[\ln(p_{1}(x)/p_{0}(x))\right]$
subject to $\mathbb{E}^{P_{1}}\left[X\right]\geq\eta$. We consider the
Lagrangian

$\begin{split}L(p_{1},\lambda,\mu)&=\mathbb{E}^{P_{1}}\left[\ln(p_{1}(x)/p_{0}(x))\right]\\\
&\qquad+\lambda(\eta-\mathbb{E}^{P_{1}}\left[X\right])+\mu\left(1-\int_{[0,1]}p_{1}(x)dx\right)\\\
&=\int_{[0,1]}\left(\ln\frac{p_{1}(x)}{p_{0}(x)}-\lambda
x-\mu\right)p_{1}(x)dx\\\ &\qquad\quad+\lambda\eta+\mu\end{split}$ (21)

where the Lagrange multiplier $\lambda\geq 0$ corresponds to the constraint
that the post-change mean is greater than $\eta$, and $\mu$ corresponds to the
constraint that $p_{1}(x)$ is a probability measure. For an arbitrary
direction $z$, since $p_{1}$ is continuous by assumption, we take the Gateaux
derivative with respect to $p_{1}$:

$\begin{split}\nabla_{p_{1},z}L(p_{1},\lambda,\mu)&:=\lim_{h\to
0}\frac{L(p_{1}+hz,\lambda,\mu)-L(p_{1},\lambda,\mu)}{h}\\\
&=\int_{[0,1]}\left(\ln\frac{p_{1}(x)}{p_{0}(x)}-\lambda
x-\mu^{\prime}\right)zdx\end{split}$ (22)

where $\mu^{\prime}=\mu-1$, and since $z$ is arbitrary, we arrive at

$\ln\frac{p_{1}(x)}{p_{0}(x)}-\lambda x-\mu^{\prime}=0$ (23)

By the Generalized Kuhn–Tucker Theorem [20], if $p_{0}(x)$ is bounded,
$p_{1}(x)=p_{0}(x)e^{\lambda x+\mu}$ is a necessary condition for optimality.
Furthermore, since $L(p_{1},\lambda,\mu)$ is convex in $p_{1}$, this is also a
global optimum. To satisfy the constraints,

$\mu^{\prime}=-\ln\int_{[0,1]}p_{0}e^{\lambda x}dx=-\kappa_{0}(\lambda)$ (24)

and $\lambda^{*}$ satisfies

$\eta=\mathbb{E}^{P_{1}}\left[X\right]=\frac{\mathbb{E}^{P_{0}}\left[Xe^{\lambda^{*}X}\right]}{\mathbb{E}^{P_{0}}\left[e^{\lambda^{*}X}\right]}=\kappa_{0}^{\prime}(\lambda^{*})$
(25)

Thus, $P_{1}^{*}$ in (17) minimizes the KL divergence when $P_{0}$ is known.
By Theorem II.1, since $(P_{0},P_{1}^{*})$ minimizes the KL divergence,
$\mathcal{P}_{1}$ is convex in that the expectation operator is linear, and
$\mathcal{P}_{0}$ is a singleton, the uncertainty classes
$\mathcal{P}_{0}\times\mathcal{P}_{1}$ are WS bounded by $(P_{0},P_{1}^{*})$.
Therefore, an asymptotically optimal test is $\Lambda^{P_{0},P_{1}^{*}}$ as in
(19).

Furthermore, the minimum KL-divergence is

$\begin{split}D(P_{1}^{*}||P_{0})&=\int_{[0,1]}(\lambda^{*}x-\kappa_{0}(\lambda^{*}))p_{1}^{*}(x)dx\\\
&=\lambda^{*}\eta-\kappa_{0}(\lambda^{*})\end{split}$ (26)

Hence, the worst-case delay satisfies

$\small\begin{split}\inf_{\tau\in\mathcal{C}^{\\{P_{0}\\}}_{\alpha}}\sup_{P_{1}\in\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau\right)&=\frac{|\ln{\alpha}|}{D(P_{1}^{*}||P_{0})}(1+o(1))\\\
&=\frac{|\ln{\alpha}|}{\lambda^{*}\eta-\kappa_{0}(\lambda^{*})}(1+o(1))\end{split}$
(27)

as $\alpha\to 0$. ∎

Since $p_{0}$ is a density on $[0,1]$, $p^{*}$ is also a density on $[0,1]$.
Indeed, $p^{*}$ is the exponentially-tilted distribution (or the Esscher
transform) of $p_{0}$.

###  III-B Approximation for Small $\Delta$

Even though we have an expression for the test statistic when $P_{0}$ is
known, as given in (19), the exact solution of $\lambda^{*}$ is not available
in closed-form. Fortunately, if the mean-change gap $\Delta$ is small, we
obtain a low-complexity test in terms of only the pre-change mean and variance
that closely approximates the performance of the asymptotically minimax
optimal test in the previous section.

As the gap is asymptotically small, the worst-case post-change mean
$\eta\to\mu_{0}$. Hence, $\lambda^{*}\to 0$. From the Taylor expansion on
$\kappa_{0}$ around 0, we obtain

$\begin{split}\kappa_{0}(\lambda^{*})&=\kappa_{0}(0)+\kappa_{0}^{\prime}(0)\lambda^{*}+\frac{\kappa_{0}^{\prime\prime}(0)}{2}(\lambda^{*})^{2}+o((\lambda^{*})^{2})\\\
&=\mu_{0}\lambda^{*}+\frac{\sigma_{0}^{2}}{2}(\lambda^{*})^{2}+o((\lambda^{*})^{2})\end{split}$
(28)

In this same regime, by continuity of $\kappa_{0}^{\prime}(\cdot)$,

$\begin{split}\lambda^{*}&=\frac{\kappa_{0}^{\prime}(\lambda^{*})-\kappa_{0}^{\prime}(0)}{\kappa_{0}^{\prime\prime}(0)}+o(\Delta)\\\
&=\frac{\eta-\mu_{0}}{\sigma_{0}^{2}}+o(\Delta)\\\
&=\frac{2\Delta}{\sigma_{0}^{2}}+o(\Delta)\end{split}$ (29)

where we have used $\kappa_{0}^{\prime}(\lambda^{*})=\eta$. Hence, the
approximate test statistic is

$\begin{split}\lambda^{*}X_{t}-\kappa_{0}(\lambda^{*})&=\lambda^{*}X_{t}-(\mu_{0}\lambda^{*}+\frac{\sigma_{0}^{2}}{2}(\lambda^{*})^{2})+o((\lambda^{*})^{2})\\\
&=\frac{2\Delta}{\sigma_{0}^{2}}(X_{t}-\mu_{0})-\frac{\sigma_{0}^{2}}{2}\left(\frac{2\Delta}{\sigma_{0}^{2}}\right)^{2}+o(\Delta^{2})\\\
&=\frac{2\Delta}{\sigma_{0}^{2}}\left(X_{t}-\frac{\mu_{0}+\eta}{2}\right)+o(\Delta^{2})\end{split}$
(30)

and the corresponding minimum KL-divergence is approximated as:

$D(P_{1}^{*}||P_{0})=\frac{2\Delta^{2}}{\sigma_{0}^{2}}+o(\Delta^{2})$ (31)

Let $\sigma_{0}^{2}$ be the variance of $X$ under $P_{0}$. Since

$\small\frac{2\Delta}{\sigma_{0}^{2}}\left(X_{t}-\frac{\mu_{0}+\eta}{2}\right)>b_{\alpha}\iff
X_{t}-\frac{\mu_{0}+\eta}{2}>\tilde{b}_{\alpha}$ (32)

where

$\tilde{b}_{\alpha}:=\frac{|\ln{\alpha}|\sigma_{0}^{2}}{2\Delta}=\frac{|\ln{\alpha}|\sigma_{0}^{2}}{\eta-\mu_{0}},$
(33)

the stopping rule $\tau(\Lambda^{P_{0},P_{1}^{*}},b_{\alpha})$ can be
approximated by the stopping rule
$\tau(\tilde{\Lambda}^{\mu_{0},\eta},\tilde{b}_{\alpha})$, where

$\begin{split}\tilde{\Lambda}^{\mu_{0},\eta}(t)&=\max_{1\leq k\leq
t}\sum_{i=k}^{t}\left(X_{i}-\frac{\mu_{0}+\eta}{2}\right)\\\
&=\left(\tilde{\Lambda}^{\mu_{0},\eta}(t-1)+\left(X_{t}-\frac{\mu_{0}+\eta}{2}\right)\right)^{+}\end{split}$
(34)

with $\tilde{\Lambda}^{\mu_{0},\eta}(0)=0$. We call
$\tau(\tilde{\Lambda}^{\mu_{0},\eta},\tilde{b}_{\alpha})$ the Mean-Change Test
(MCT), and $\tilde{\Lambda}^{\mu_{0},\eta}$ the MCT statistic.

Noe that the worst-case delay satisfies

$\begin{split}\inf_{\tau\in\mathcal{C}^{\\{P_{0}\\}}_{\alpha}}\sup_{P_{1}\in\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau\right)&=\frac{|\ln{\alpha}|}{D(P_{1}^{*}||P_{0})}(1+o(1))\\\
&\approx\frac{|\ln{\alpha}|\sigma_{0}^{2}}{2\Delta^{2}}(1+o(1))\end{split}$
(35)

where the approximation becomes more accurate as $\Delta\to 0$.

Therefore, if the gap is small, it is sufficient to know only the mean and
variance to construct a good approximation to the asymptotically minimax
robust test. Furthermore, only the mean of the pre-change distribution is
needed to construct the MCT statistic. From the simulation results in Section
IV, the performance of the MCT is very close to that of the asymptotically
minimax robust test. Since the mean and variance of a distribution are much
easier and more accurately estimated than the entire density, this test can be
useful and accurate when only a moderate number of observations in the pre-
change regime is available.

###  III-C Performance Analysis of MCT for moderate $\Delta$

We now study the asymptotic performance of the MCT for the case where $\Delta$
is moderate, as $\alpha\to 0$.

######  Lemma III.2.

Fix $P_{0}\in\mathcal{P}_{0}$. For simplicity, denote
$\tau:=\tau(\tilde{\Lambda}^{\mu_{0},\eta},b)$,
$Z_{i}:=X_{i}-(\mu_{0}+\eta)/2$, and $S_{t}=\sum_{i=1}^{t}Z_{i}$. For any
threshold $b>1$,

$\small\begin{split}P_{0}\left\\{S_{\tau}\geq b\right\\}&\leq
2R_{0}\sqrt{\frac{b^{2}}{\Delta^{2}}}K_{1}\left(\frac{R_{0}^{2}b\Delta}{\sigma_{0}^{2}}\right)\exp{\left(-\frac{R_{0}^{2}\Delta}{\sigma_{0}^{2}}b\right)}\\\
&\sim\sqrt{\frac{2\pi\sigma_{0}^{2}b}{\Delta^{3}}}\exp{\left(-\frac{2R_{0}^{2}\Delta}{\sigma_{0}^{2}}b\right)},\text{
as }b\to\infty\end{split}$ (36)

where

$R_{0}=\sigma_{0}^{2}/\left(\sigma_{0}^{2}+\Delta\cdot\max\\{\mu_{0},1-\mu_{0}\\}/3\right)$
(37)

and $K_{\beta}(z)$ is the modified Bessel function of the second kind with
order $\beta$.

###### Proof.

Let $M=\max\\{\mu_{0}/3,(1-\mu_{0})/3\\}$. Note that
$\mathbb{E}^{P_{0}}\left[Z_{i}\right]=(\mu_{0}-\eta)/2=-\Delta$. Thus, we have

$\displaystyle P_{0}\left\\{S_{\tau}\geq b\right\\}$
$\displaystyle=P_{0}\left\\{\sum_{i=1}^{\tau}Z_{i}\geq b\right\\}$
$\displaystyle=\sum_{t=1}^{\infty}P_{0}\left\\{\sum_{i=1}^{t}Z_{i}\geq
b,t=\tau\right\\}$
$\displaystyle\leq\sum_{t=1}^{\infty}P_{0}\left\\{\sum_{i=1}^{t}Z_{i}\geq
b\right\\}$
$\displaystyle=\sum_{t=1}^{\infty}P_{0}\left\\{\sum_{i=1}^{t}(Z_{i}+\Delta)\geq
b+t\Delta\right\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=1}^{\infty}\exp\left(-\frac{(b+t\Delta)^{2}}{2(t\sigma_{0}^{2}+M(b+t\Delta))}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\int_{0}^{\infty}\exp\left(-\frac{(b+x\Delta)^{2}}{2(x\sigma_{0}^{2}+M(b+x\Delta))}\right)dx$
$\displaystyle=a\int_{0}^{\infty}\exp\left(-\frac{(a\Delta
y+C)^{2}}{2y}\right)dy$ $\displaystyle=ae^{-a\Delta
C}\int_{0}^{\infty}e^{-((a^{2}\Delta^{2}/2)y+(C^{2}/2)y^{-1})}dy$
$\displaystyle=\frac{2C}{\Delta}e^{-a\Delta C}K_{1}(a\Delta C)$ (38)

where $a:=(\sigma_{0}^{2}+M\Delta)^{-1}$ and
$C:=\sigma_{0}^{2}b/(\sigma_{0}^{2}+M\Delta)$. In the series of inequalities
above, (a) is by Bernstein’s inequality [21, p. 9], and (b) is from bounding
the sum with an integral. Since $K_{1}(z)\sim\sqrt{\frac{\pi}{2z}}e^{-z}$ as
$|z|\to\infty$, the asymptotic result follows. ∎

######  Theorem III.3.

Let

$\sqrt{\frac{2\pi\sigma_{0}^{2}\tilde{b}^{\prime}_{\alpha}}{\Delta^{3}}}\exp{\left(-\frac{2R_{0}^{2}\Delta}{\sigma_{0}^{2}}\tilde{b}^{\prime}_{\alpha}\right)}=\alpha$
(39)

then (7) is satisfied asymptotically as $\alpha\to 0$. Furthermore,

$\tilde{b}^{\prime}_{\alpha}=\frac{\tilde{b}_{\alpha}}{R_{0}^{2}}(1+o(1))$
(40)

where $R_{0}$ is defined in (37).

###### Proof.

As $\alpha\to 0$, $\tilde{b}^{\prime}_{\alpha}\to\infty$. As a result, for any
$P_{1}\in\mathcal{P}_{1}$, $P_{0}\left\\{S_{\tau}\geq
b\right\\}\leq\alpha(1+o(1))$. From [22, Sec. 2.6], it can be shown that

$\begin{split}\mathbb{E}^{P_{0},P_{1}}_{\infty}\left[\tau\right]&=\frac{\mathbb{E}^{P_{0}}\left[S_{\tau}\right]}{P_{0}\left\\{S_{\tau}\geq
b\right\\}}\\\ &\geq\frac{1}{P_{0}\left\\{S_{\tau}\geq b\right\\}}\\\
&\geq\alpha^{-1}(1+o(1))\end{split}$ (41)

since $\mathbb{E}^{P_{0}}\left[S_{\tau}\right]\geq 1$. Thus, the false alarm
constraint is satisfied asymptotically.

For the second result, it is sufficient to show that
$(\tilde{b}^{\prime}_{\alpha}-\tilde{b}_{\alpha})/\tilde{b}_{\alpha}=R_{0}^{-2}-1+o(1)$.
Let

$D:=\frac{2\Delta}{\sigma_{0}^{2}}\tilde{b}^{\prime}_{\alpha}-|\ln\alpha|$
(42)

Note that the desired ratio
$(\tilde{b}^{\prime}_{\alpha}-\tilde{b}_{\alpha})/\tilde{b}_{\alpha}=D/|\ln\alpha|$.
Plugging into (36), we have

$\sqrt{\frac{\sigma_{0}^{4}\pi}{\Delta^{4}}(D+|\ln\alpha|)}e^{-R_{0}^{2}(D+|\ln\alpha|)}=\alpha$
(43)
$-\frac{1}{2}\ln\left(\frac{\sigma_{0}^{4}\pi}{\Delta^{4}}(D+|\ln\alpha|)\right)+R_{0}^{2}(D+|\ln\alpha|)=|\ln\alpha|$
(44)

Now, we hypothesize that $D=D_{1}|\ln\alpha|+o(|\ln\alpha|)$. The first term
then vanishes because

$\small\begin{split}\ln\left(\frac{\sigma_{0}^{4}\pi}{\Delta^{4}}(D+|\ln\alpha|)\right)&=\ln\left(\frac{\sigma_{0}^{4}\pi}{\Delta^{4}}((D_{1}+1)|\ln\alpha|+o(|\ln\alpha|)\right)\\\
&=O(\ln(|\ln\alpha|))\\\ &=o(|\ln\alpha|)\end{split}$ (45)

From the second term, we validate our hypothesis that

$D=(R_{0}^{-2}-1)|\ln\alpha|+o(|\ln\alpha|)$ (46)

and the second result follows. ∎

######  Remark.

In practice, the threshold can be set to be
$\sigma_{0}^{2}/(2R_{0}^{2}\Delta)$ using equation (40).

######  Theorem III.4.

Fix $P_{0}\in\mathcal{P}_{0}$. The worst-case delay satisfies

$\sup_{P_{1}\in\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau(\tilde{\Lambda}^{\mu_{0},\eta},\tilde{b}^{\prime}_{\alpha})\right)\leq\frac{|\ln{\alpha}|\sigma_{0}^{2}}{2\Delta^{2}R_{0}^{2}}(1+o(1))$
(47)

as $\alpha\to 0$.

###### Proof.

For any $P_{1}\in\mathcal{P}_{1}$, as $\alpha\to 0$,

$\begin{split}\text{WADD}^{P_{0},P_{1}}\left(\tau(\tilde{\Lambda}^{\mu_{0},\eta},\tilde{b}^{\prime}_{\alpha})\right)&=\frac{\tilde{b}_{\alpha}^{\prime}}{\Delta}(1+o(1))\\\
&=\frac{\tilde{b}_{\alpha}}{\Delta R_{0}^{2}}(1+o(1))\\\
&=\frac{|\ln{\alpha}|\sigma_{0}^{2}}{2\Delta^{2}R_{0}^{2}}(1+o(1))\end{split}$
(48)

where the first line is by renewal theory [23]. ∎

######  Remark.

As $\Delta\to 0$, $R_{0}\to 1$. Thus, the result above becomes

$\sup_{P_{1}\in\mathcal{P}_{1}}\text{WADD}^{P_{0},P_{1}}\left(\tau(\tilde{\Lambda}^{\mu_{0},\eta},\tilde{b}^{\prime}_{\alpha})\right)\sim\frac{|\ln{\alpha}|\sigma_{0}^{2}}{2\Delta^{2}}(1+o(1))$
(49)

where $o(1)$ goes zero as $\alpha$ and $\Delta$ go to zero, which coincides
with the minimax robust worst-case delay in (35).

##  IV Numerical Results and Discussion

We study the performance of the proposed tests through simulations for the
case where the pre- and post-change distributions are beta(4,16)
($\mu_{0}=0.2$) and beta(4.5,16) ($\mu_{1}=0.2195$), respectively. The mean-
threshold $\eta$ is set to be $0.21$. In particular, we compare the
performances for the following three statistics:

  1. 1.

The CUSUM statistic that knows both the pre- and post-change distributions,
defined in (4).

  2. 2.

The statistic when only the pre-change distribution is known, defined in (19).

  3. 3.

The MCT statistic defined in (34).

For all three statistics, based on their recursive structure, it is easy to
show that the worst-case value of the change-point for computing WADD in (2)
is $\nu=0$. Therefore we can estimate the worst-case delay by simulating the
post-change distribution from time 0.

Figure 1: Performances of different statistics. The pre- and post-change
distribution are Beta(4,16) ($\mu_{0}=0.2$) and Beta(4.5,16)
($\mu_{1}=0.2195$), respectively. The mean-threshold $\eta=0.21$. .

We see in Fig. 1 that the performance of MCT is very close to the test that
uses knowledge of the entire pre-change distribution. Note that the MCT
statistic only uses the pre-change mean; the variance is needed for setting
the threshold to meet a given FAR constraint.

Figure 2: COVID-19 monitoring example. The upper subplot is the three-day
moving average of the new cases of COVID-19 as a fraction of the population in
Wayne County, MI (left), St. Louis County, MO (middle), and Hamilton County,
OH (right). The x-axis is the number days elapsed after January 21, 2020. The
pre-change mean and variance are estimated using data from days 120 to 150.
The FAR threshold $\alpha$ is set to $0.01$. For each county, the mean-
threshold $\eta$ (in green) is set to be 3.3 times of the estimated pre-change
mean (in cyan). The lower subplot shows the evolving of the statistic
$\tilde{\Lambda}$ in the corresponding county. The $\Lambda$-threshold
$\tilde{b}_{\alpha}$ (in red) is calculated using equation (33).

In Fig. 2, we apply the MCT to monitoring the spread of COVID-19 using new
case data from various counties in the US [24]. The incremental cases from day
to day can be assumed to be roughly independent. The goal is to detect the
onset of a new wave of the pandemic based on the incremental cases as a
fraction of the county population exceeding some pre-specified level. The pre-
change mean and variance are estimated using observations for periods in which
the increments remain low and roughly constant. We set the mean-threshold
$\eta$ to be a multiple of the pre-change mean, with understanding that such a
threshold might be indicative of a new wave. With this choice, we observe that
the MCT statistic significantly and persistently crosses the test-threshold
around late November in all counties, which is strong indication of a new wave
of the pandemic. More importantly, unlike the raw observations which are
highly varying, the MCT statistic shows a clear dichotomy between the pre- and
post-change settings, with the statistic staying near zero before the
purported onset of the new wave, and taking off nearly vertically after the
onset.

## References

  * [1] Y. C. Chen, T. Banerjee, A. D. Dominguez-Garcia, and V. V. Veeravalli, “Quickest line outage detection and identification,” _IEEE Transactions on Power Systems_ , vol. 1, no. 31, pp. 749–758, 2016.
  * [2] T. L. Molloy and J. J. Ford, “Misspecified and asymptotically minimax robust quickest change detection,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 21, pp. 5730–5742, 2017.
  * [3] G. Tagaras, “A survey of recent developments in the design of adaptive control charts,” _Journal of Quality Technology_ , vol. 30, no. 3, pp. 212–231, 1998\.
  * [4] J. Czarnecki and C. Farrar, “Structural health monitoring using statistical process control,” _Journal of Structural Engineering_ , vol. 126, no. 11, pp. 1356–1363, Nov. 2000.
  * [5] L. Besson and E. Kaufmann, “The generalized likelihood ratio test meets KL-UCB: An improved algorithm for piece-wise non-stationary bandits,” _arXiv preprint arXiv:1902.01575_ , 2019.
  * [6] A. Tartakovsky and V. Veeravalli, “General asymptotic bayesian theory of quickest change detection,” _SIAM Theory of Probability and Its Applications_ , vol. 49, Jan. 2005.
  * [7] G. Lorden, “Procedures for reacting to a change in distribution,” _The Annals of Mathematical Statistics_ , vol. 42, no. 6, pp. 1897–1908, Dec. 1971\.
  * [8] M. Pollak, “Average run lengths of an optimal method of detecting a change in distribution,” _The Annals of Statistics_ , vol. 15, no. 2, pp. 749–779, Jun. 1987.
  * [9] P. Moulin and V. V. Veeravalli, _Statistical Inference for Engineers and Data Scientists_. Cambridge, UK: Cambridge University Press, 2018.
  * [10] D. Siegmund and E. S. Venkatraman, “Using the generalized likelihood ratio statistic for sequential detection of a change-point,” _The Annals of Statistics_ , vol. 23, no. 1, pp. 255–271, Feb. 1995.
  * [11] T. Lai and H. Xing, “Sequential change-point detection when the pre- and post-change parameters are unknown,” _Sequential Analysis_ , vol. 29, no. 2, pp. 162–175, May 2010.
  * [12] S. Li, Y. Xie, H. Dai, and L. Song, “M-statistic for kernel change-point detection,” in _Advances in Neural Information Processing Systems_ , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds., vol. 28. Curran Associates, Inc., 2015, pp. 3366–3374.
  * [13] O.-A. Maillard, “Sequential change-point detection: Laplace concentration of scan statistics and non-asymptotic delay bounds,” in _Proceedings of the 30th International Conference on Algorithmic Learning Theory_ , ser. Proceedings of Machine Learning Research, A. Garivier and S. Kale, Eds., vol. 98. Chicago, Illinois: PMLR, Mar. 2019, pp. 610–632.
  * [14] T. Lau, W. P. Tay, and V. Veeravalli, “A binning approach to quickest change detection with unknown post-change distribution,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 3, pp. 609–621, Nov. 2018.
  * [15] P. J. Huber, “A robust version of the probability ratio test,” _The Annals of Mathematical Statistics_ , vol. 36, no. 6, pp. 1753–1758, Dec. 1965\.
  * [16] E. S. PAGE, “Continuous Inspection Schemes,” _Biometrika_ , vol. 41, no. 1/2, pp. 100–115, Jun. 1954.
  * [17] G. V. Moustakides, “Optimal stopping times for detecting changes in distributions,” _Annals of Statistics_ , vol. 14, no. 4, pp. 1379–1387, Dec. 1986.
  * [18] J. Unnikrishnan, V. V. Veeravalli, and S. P. Meyn, “Minimax robust quickest change detection,” _IEEE Transactions on Information Theory_ , vol. 57, no. 3, pp. 1604–1614, 2011.
  * [19] B. C. Levy, _Principles of Signal Detection and Parameter Estimation_. New York, NY: Springer, 2008\.
  * [20] D. G. Luenberger, _Optimization by Vector Space Methods_ , 1st ed. 605 Third Ave, New York, NY, US: John Wiley & Sons, Inc., Jan. 1997.
  * [21] L. Wasserman, _All of Nonparametric Statistics_. 233 Spring Street, New York, NY 10013, USA: Springer, 2006.
  * [22] D. Siegmund, _Sequential analysis: Tests and confidence intervals_. Springer, 1985.
  * [23] V. V. Veeravalli and T. Banerjee, “Quickest change detection,” in _Academic press library in signal processing: Array and statistical signal processing_. Cambridge, MA: Academic Press, 2013.
  * [24] Rearc. AWS Marketplace: Coronavirus (COVID-19) Data in the United States — The New York Times. [Online]. Available: https://urldefense.com/v3/__https://aws.amazon.com/marketplace/pp/Coronavirus-COVID-19-Data-in-the-United-States-The/prodview-jmb464qw2yg74__;!!DZ3fjg!oSxTS0VgkopT_Gqp0XiRZGO24wcouQ5xRXh389-5cY88mGOynh9goKIh8x9_ogUY$