mlsanityData to 7 Oct 2026

Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity

arXiv 2211.07092 ↗First posted 14 Nov 2022stat.ML cs.LG math.STcited by 5

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 17 of its 71 references that are in the map. First posted on arXiv 14 Nov 2022.

Builds on

17 of 71 references.

References · 17

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020MOPO: Model-based Offline Policy Optimizationcited by 630
  3. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 582
  4. 2017Robust Adversarial Reinforcement Learningcited by 439
  5. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  8. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  9. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 78
  10. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  11. 2014Algorithms for multi-armed bandit problemscited by 63
  12. 2020Queueing Network Controls via Deep Reinforcement Learningcited by 40
5 more
  1. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  2. 2020Probabilistic Machine Learning for Healthcarecited by 23
  3. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  4. 2018Multi-Agent Reinforcement Learning: A Report on Challenges and Approachescited by 5
  5. 2020Active Learning for Linear Parameter-Varying System Identificationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Mediancited by 2
  2. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  3. 2025Central Limit Theorems for Transition Probabilities of Controlled Markov Chainscited by 1
  4. 2026Adaptive Estimation and Optimal Control in Offline Contextual MDPs without Stationaritycited by 1
  5. 2026Model-based Bootstrap of Controlled Markov Chainscited by 0