Preamble

This note provides a brief introduction to changepoint detection and reinforcement learning with some relevant applications and literature.

The note just serves as a guideline for you to pick up some background knowledge and motivating examples. To acquire a systematic understanding and required skills (in theory/methodology/computing) to complete your MSc dissertation, it is necessary to study more relevant literature from other resources.

Theme 1. Changepoint Detection

Quantitative statistical/machine-learning approaches become very popular in analysing data generated in a sequence. An very important problem is to find efficient methods for continuous surveillance and for detecting structure changes to the system. Many statistical tools have been developed to discover an unknown number of historical parametric or nonparametric changes, such as change-in-mean, change-in-variance, change-in-slope and change-in-distribution. Such tools enable us to fit the data and localise each structure changes, under the so-called off-line setting. The principal idea of this theme is to examine different changepoint detection methods in real-world data, and if time permits also exploit its online machinery, i.e., sequentially recovering the most recent changes.

In this project, you are expected to learn state-of-the-art changepoint detection methods and apply them to modern data applications. Substantial coding in R will be necessary to implement and compare different changepoint algorithms via simulation. You might also learn how to write your code into an R package.

Alt text Alt text Alt text

Offline setting: all data points are available, and we perform a detect alogrithm retrospectively to find the changepoints. The key point is to find an algorithm that estimate the number and locations of changepoints simultaneously.

For example, in univariate data typical techniques include:

The method can be extended to multivariate/high dimensional data, or dependent data such time series and markov random fields.

Project Topics Examples:

  • Changepoint detection in timeseries (application, theory)

    • Time Series Analysis of COVID-19 Infection Curve: A Change-Point Perspective. (2020). JoE. Feiyu Jiang, Zifeng Zhao, Xiaofeng Shao
    • Segmenting Time Series via Self-Normalization. 2022. arXiv. Zifeng Zhao, Feiyu Jiang, Xiaofeng Shao.

  • Fast pruning algorithms for changepoint detection (algorithm, coding)

    • Fast Online Changepoint Detection via Functional Pruning CUSUM statistics. (2021). arXiv. Gaetano Romano, Idris Eckley, Paul Fearnhead, Guillem Rigaill.
    • gfpop: an R Package for Univariate Graph-Constrained Change-Point Detection. (2020). arXiv. Vincent Runge, Toby Dylan Hocking, Gaetano Romano, Fatemeh Afghah, Paul Fearnhead, Guillem Rigaill.

  • Changepoint detection in categorical data with applications in Covid genetic variants (application, coding)

    • Online Change-Point Detection in Categorical Time Series (2010). Michael Hohle
    • Change-point detection in multinomial data with a large number of categories (2018). Guanghui Wang, Changliang Zou, Guosheng Yin

Some Literatures:

  • Baranowski, R., Chen, Y. and Fryzlewicz, P. (2019). Narrowest-Over-Threshold detection of multiple change-points and change-point-like features. Journal of the Royal Statistical Society: Series B. (Methodology/Algorithm/Coding/Application)
  • Chu, L., Chen, H. (2019). Asymptotic distribution-free change-point detection for multivariate and non-Euclidean data. Annals of Statistics. (Methodology/Algorithm/Coding)
  • Eichinger, B. and C. Kirch (2018). A MOSUM procedure for the estimation of multiple random change points. Bernoulli. 24, 526-564. (Methodology)
  • Fearnhead, P., Maidstone, R., and Letchford, A. (2018). Detecting changes in slope with an L0 penalty. Journal of Computational and Graphical Statistics. (MethOdology/Algorithm/Application)
  • Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. Annals of Statistics. (Methodology/Algorithm/Coding)
  • Frick, K., Munk, A., Sieling, H. (2014). Multiscale Change-Point Inference. Journal of the Royal Statistical Society: Series B. (Methodology/Algorithm)
  • Matteson, D.S. and James, N.A. (2014). A nonparametric approach for multiple change point analysis of multivariate data. Journal of the American Statistical Association. (Methodology/Algorithm)
  • Killick, R., Fearnhead, P., and Eckley, I. A. (2012) Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association. (Methodology/Algorithm/Application)
  • Kim, S.-J., Koh, K., Boyd, S., and Gorinevsky, D. (2009). L1-trend filtering. SIAM review. (Algorithm)
  • Lavielle, M. and Moulines, E. (2000). Least-squares estimation of an unknown number of shifts in a time series. Journal of Time Series Analysis. (Theory/Methodology)
  • Page, E. S. (1955). A test for a change in a parameter occurring at an unknown point. Biometrika. (Methodology)
  • Roy, S., Atchade, Y. and Michailidis, G. (2017). Change point estimation in high dimensional Markov random-field models. Journal of the Royal Statistical Society. Series B. (Methodology)
  • Wang, T. and Samworth, R. J. (2018). High-dimensional changepoint estimation via sparse projection. Journal of the Royal Statistical Society. Series B. (Methodology/Algorithm/Application)
  • Wang, D., Yu, Y. and Rinaldo, A. (2018). Optimal change point detection and localization in sparse dynamic networks. arXiv preprint. (Algorithm)
  • Yu, Y., Padilla, O, Wang, D., and Rinaldo, A. (2020) A Note on Online Change Point Detection. arXiv preprint. (Algorithm)
  • Zheng, C., Eckley, I., and Fearnhead, P. (2019). Consistency of a range of penalised cost approaches for detecting multiple changepoints. arXiv preprint. (Theory)

Theme 2. Bandit Algorithms and Reinforcement Learning

Reinforcement learning (RL) is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning, which is a interdiscipline research area of statistical learning and optimal control, concerning with how an intelligent agent ought to take actions in a dynamic environment in order to maximize the cumulative reward (miminize the regret). The relevant techiniques have been used by big techs such as DeepMind/openAI to initiate artificial intelligence in how to play complex games (like chess, Go and computer games), self-driving cars, trading and finance, and healthcare, etc.

In this project, you will study basics methods,theory, implementation, and applications of reinforcement learning, including multi-armed bandits and contexture bandits algorithms. Substantial coding in R and Python will be necessary.

Project Topics Examples:

  • Upper confidence bound (UCB) algorithm and its applications in multi-armed bandit problem

    • Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning. Auer, P., Cesa-Bianchi, N., and Fischer, P.
    • Introduction to Multi-Armed Bandits (2019).arXiv. Slivkin, A.

  • Contextual bandits with approximate solutions

    • Contextual bandits with linear payoff functions (2011) ICAIS. Chu,W., Li, L., Reyzin, L., and Schapire, R. E..
    • Beyond UCB: Optimal and efficient contextual bandits with regression oracles. (2020) ICML. Foster, D. J., and Rakhlin A.
    • Contextual: Evaluating contextual multi-armed bandit problems in R (2020). arXiv. van Emden, R., and Kaptein, M.

  • Decision making process and Estimation-to-Decisions (E2D) algorithm

    • Minimax regret bounds for reinforcement learning (2017). ICML. Azar, M. G., Osband, I., and Munos, R..
    • The statistical complexity of interactive decision making (2021). arXiv. Foster, D.,J., Kakade, S.,M., Qian, J., and Rakhlin, A.

Some Literatures:

  • Foster, D. J., and Rakhlin A. (2023) Foundations of Reinforcement Learning and Interactive Decision Making. (Tutorial/Theory)
  • Slivkin, A. (2019) Introduction to Multi-Armed Bandits. (Tutorial/Theory)
  • Lattimore, T., and Szepesvari C. (2020). Bandit Algorithms. (Tutorial/Theory)
  • Multi-Armed Bandits 1-3 (2022). Web tutorial. Dan Carter. (Tutorial/Coding)