repro-bundle/v1/official_code/README.md

Asymptotically Optimal Sequential Testing with Markovian Data

This repository contains the implementation of the experiments for the paper "Asymptotically Optimal Sequential Testing with Markovian Data", ICML 2026 by Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal, Debabrota Basu, and P. N. Karthik.

Overview

We study one-sided, $\alpha$-correct sequential hypothesis testing for data generated by an ergodic, finite-state Markov chain. We establish a non-asymptotic, instance-dependent lower bound on the expected stopping time of any valid sequential test under the alternative hypothesis, and we propose a novel optimal test that matches this lower bound asymptotically as $\alpha \rightarrow 0$.

This repository provides the code to reproduce our empirical findings, illustrating the flexibility and optimality of our framework across several domains, including:

• Detecting model misspecification in Markov Chain Monte Carlo (MCMC).
• Testing structural properties (e.g., linearity of transition dynamics) in Markov Decision Processes (MDPs).
• Testing specific parametric families of Markov chains.

Repository Structure

The experiments are organized into self-contained Jupyter notebooks corresponding to different sections of the paper:

• G1_MCMC.ipynb: Implementation of the MCMCMisspecificationTest. Evaluates the sequential detection of model misspecification in MCMC applications, as specified in Appendix G.1 of the paper.
• G2_MDP.ipynb: Implementation of the LinearMDPTest. Contains experiments for testing structural properties in Markov decision processes (using gymnasium environments), as specified in Appendix G.2 of the paper.
• G3_ParametricFamily.ipynb: Experiments evaluating the test on specific parametric families of transition matrices, as specified in Appendix G.3 of the paper.
• G4_Baselines1.ipynb & G4_Baselines2.ipynb: Comparison of the proposed method's mean stopping time and runtime against existing baselines (such as the Fields Modified Jeffreys procedure collapsed for composite settings) across various confidence levels ($\alpha$), as specified in Appendix G.4 of the paper.

Dependencies

The code is written in Python 3. To run the notebooks, you will need the following libraries:

pip install numpy scipy matplotlib cvxpy tqdm gymnasium

Note: G4_Baselines2.ipynb utilizes GPU acceleration for certain baseline comparisons and requires cupy-cuda12x. Adjust the CuPy version based on your local CUDA toolkit installation if you are running it locally rather than on Google Colab.

pip install cupy-cuda12x 

Usage

You can run the experiments by simply launching Jupyter Notebook or JupyterLab and executing the cells in the respective notebooks:

jupyter notebook

Each notebook is designed to be self-contained. They initialize the respective environments or transition matrices, execute the sequential tests, and generate the plots (e.g., Stopping time vs confidence $\alpha$, distribution of stopping times) used in the paper.

Citation

If you find this code or our paper useful in your research, please consider citing our work:

@article{sethi2026asymptotically,
  title={Asymptotically Optimal Sequential Testing with Markovian Data},
  author={Sethi, Alhad and Sagar, Kavali Sofia and Agrawal, Shubhada and Basu, Debabrota and Karthik, P. N.},
  booktitle={Forty-third International Conference on Machine Learning},
  year={2026},
  url={https://arxiv.org/abs/2602.17587}
}