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:

```bash
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.*

```bash
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:

```bash
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:

```bibtex
@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}
}

```