  In this work, we study a natural nonparametric estimator of the transition
probability matrices of a finite controlled Markov chain. We consider an
offline setting with a fixed dataset, collected using a so-called logging
policy. We develop sample complexity bounds for the estimator and establish
conditions for minimaxity. Our statistical bounds depend on the logging policy
through its mixing properties. We show that achieving a particular statistical
risk bound involves a subtle and interesting trade-off between the strength of
the mixing properties and the number of samples. We demonstrate the validity of
our results under various examples, such as ergodic Markov chains, weakly
ergodic inhomogeneous Markov chains, and controlled Markov chains with
non-stationary Markov, episodic, and greedy controls. Lastly, we use these
sample complexity bounds to establish concomitant ones for offline evaluation
of stationary Markov control policies.
