Purdue University Graduate School
Thesis-Imon.pdf (1.31 MB)


Download (1.31 MB)
posted on 2023-12-06, 02:16 authored by Imon BanerjeeImon Banerjee

This thesis presents probably approximately correct (PAC) bounds on estimates of the transition kernels of Controlled Markov chains (CMC’s). CMC’s are a natural choice for modelling various industrial and medical processes, and are also relevant to reinforcement learning (RL). Learning the transition dynamics of CMC’s in a sample efficient manner is an important question that is open. This thesis aims to close this gap in knowledge in literature.

In Chapter 2, we lay the groundwork for later chapters by introducing the relevant concepts and defining the requisite terms. The two subsequent chapters focus on non-parametric estimation.

In Chapter 3, we restrict ourselves to a finitely supported CMC with d states and k controls and produce a general theory for minimax sample complexity of estimating the transition matrices.

In Chapter 4 we demonstrate the applicability of this theory by using it to recover the sample complexities of various controlled Markov chains, as well as RL problems.

In Chapter 5 we move to a continuous state and action spaces with compact supports. We produce a robust, non-parametric test to find the best histogram based estimator of the transition density; effectively reducing the problem into one of model selection based on empricial processes.

Finally, in Chapter 6 we move to a parametric and Bayesian regime, and restrict ourselves to Markov chains. Under this setting we provide a PAC-Bayes bound for estimating model parameters under tempered posteriors.


Degree Type

  • Doctor of Philosophy


  • Statistics

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Vinayak Rao

Additional Committee Member 2

Jun Xie

Additional Committee Member 3

Anindya Bhardra

Additional Committee Member 4

Harsha Honnappa