Central Limit Theorems for Transition Probabilities of Controlled Markov Chains

\name Ziwei Su \email [email protected], \name Imon Banerjee \email [email protected], \name Diego Klabjan \email [email protected] · 2025

Read Central Limit Theorems for Transition Probabilities of Controlled Markov Chains by \name Ziwei Su \email [email protected], \name Imon Banerjee \email [email protected], \name Diego Klabjan \email [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01517.txt.

Introduction

Ziwei Su and co-authors prove limit theorems for controlled Markov chains in a 2025 paper. Such chains model systems where actions steer random state changes, the core of reinforcement learning. A nonparametric estimator can learn the transition matrices from logged data alone.

The team states exact conditions on the logging policy for that estimator to turn Gaussian at scale. Some settings provably admit no such limit theorem at all. Value, Q, and advantage functions for any steady policy then inherit their own limit laws. Goodness-of-fit tests fall out as a bonus, checking whether logged data are truly stochastic. Offline policy work gains firmer statistical footing.

Catalog record

CREATOR\name Ziwei Su \email [email protected], \name Imon Banerjee \email [email protected], \name Diego Klabjan \email [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01517

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Central Limit Theorems for Transition Probabilities of Controlled Markov Chains \name Ziwei Su \email [email protected], \name Imon Banerjee \email [email protected], \name Diego Klabjan \email [email protected] Abstract We develop a central limit theorem (CLT) for the non-parametric estimator of the transition matrices in controlled Markov chains (CMCs) with finite state-action spaces. Our results establish precise conditions on the logging policy under which the estimator is asymptotically normal, and reveal settings in which no CLT can exist. We then build upon it to derive CLTs for the value, Q-, and advantage functions of any stationary stochastic policy, including the optimal policy recovered from the estimated model. Goodness-of-fit tests are derived as a corollary, which enable us to test whether the logged data is stochastic. These results provide new statistical tools for offline policy evaluation and optimal policy recovery, and enable hypothesis tests for transition probabilities. Keywords: Markov chains, controlled Markov chains, mixing processes, non-parametric estimation, CLT 1 Introduction A discrete-time stochastic process \{(X_{i},a_{i})\} is called a controlled Markov chain (CMC) ( Borkar 1991 ) if the next “state” X_{i+1} depends only on the current state X_{i} and the current “control” a_{i} . Here, the actions a_{i} depend only on the information available up to time i . This paper studies the asymptotic distribution of the transition probabilities of finite state-action controlled Markov chains. In general, controlled Markov chains can be thought of as a generalization of time-homogeneous data (like i.i.d., Markovian), time-inhomogeneous data (like i.n.i.d., time-inhomogeneous Markovian ( Dolgopyat and Sarig 2023 ; Merlevède et al. 2022 ) , Markov decision process ( Hernández-Lerma et al. 1991 ) ), etc. They can also be used to model other problems such as system stabilization ( Yu et al. 2023 ) , or system identification ( Ljung 1999 ; Mania et al. 2020 ) . There is no reason to believe that the previous examples involve controls that are Markovian. For instance, it is known that certain categories of adversarial Markov games ( Wang et al. 2024 ) , reward machines ( Icarte et al. 2018 ) , and minimum entropy explorations ( Mutti et al. 2022 ) induce Markovian state transitions with non-Markovian controls. Therefore, there is an acute need to sharply estimate the transition dynamics of controlled Markovian systems in the presence of non-Markovian controls. A particularly relevant downstream task in modern machine learning is offline (batch) reinforcement learning (RL). Offline RL often begins with a fixed dataset of trajectories collected by some unknown logging policy (behavior policy), with no further control over data collection. A fundamental challenge in this setting is to accurately estimate the Markov transition dynamics of the environment from logged data \{(X_{i},a_{i})\}_{i=0}^{n} . Here, \{a_{i}\}_{i=0}^{n} is a sequence of actions and \{X_{i}\}_{i=0}^{n} is a sequence of states that, conditioned on a_{i} , follows a Markov transition kernel (see Definition 1 for the formal definition). The estimated transition probabilities are then used to evaluate policies or to find an optimal policy for the given dynamics (see Section 4.1 for more details). In a finite controlled Markov chain, i.e. when the state space and the action spaces are finite, the simplest and most natural approach is to use the non-parametric count-based empirical estimator (model) of the transition probabilities. We show that this estimator is essentially the maximum likelihood estimate of the transition probabilities (see Proposition 3 ). There have been some recent developments towards understanding the statistical properties of the marginal distributions of time-inhomogeneous Markov chains (see Sarig 2021 for details). However, despite the widespread prevalence of using the count-based estimator for the transition probabilities in model-based RL ( Mannor and Tsitsiklis 2005 ; Li et al. 2022 ) , the statistical properties of this estimator are poorly understood. One recent work ( Banerjee et al. 2025a ) establishing probably approximately correct (PAC) ( Valiant 1984 ) guarantees on the estimation error. But this analysis underpins the theoretical nature of PAC learning which does not always align with reality. In particular, it leaves open the important question of the exact asymptotic behavior of the estimators. This gap in theory limits our ability to evaluate estimation error, construct confidence intervals, or perform rigorous hypothesis tests for transition probabilities. This paper addresses this gap by developing the first asymptotic normality theory for count-based transition estimators in controlled Markov chains with finite states and actions. We answer the following question(s): Under what conditions does there exist a scaling such that the scaled estimation error of the empirical transition estimates obeys a CLT, and when does an asymptotic distribution fail to exist? We show that the answer depends crucially on properties of the logging policy (such as sufficient coverage of all state-action pairs). In fact, under some mild recurrence and mixing conditions, we prove that the empirical transition probabilities converge in distribution to a multivariate normal under appropriate randomized scaling. Our analysis reveals that the estimated transition probabilities, when appropriately scaled, have a multinomial behavior in the limit and are asymptotically independent across state-action pairs (see Theorem 15 ). This can be thought of as a generalization of the CLT for the transition probabilities of ergodic Markov chains ( Billingsley 1961 ) in non-ergodic, non-stationary stochastic processes, being a first of its kind. Furthermore, we also identify scenarios in which a CLT cannot be established for any estimator of the transition probabilities. To demonstrate the applicability of our results in downstream tasks such as offline policy evaluation (OPE) and optimal policy recovery (OPR), we then derive asymptotic guarantees for the value ( V ), action-value ( Q ), or advantage ( A ) functions for any stationary target policy by solving the Bellman equation with the plug-in transition estimator. In particular, by analyzing the value of the optimal policy calculated from the estimated transition probabilities, we establish a CLT for the value function of the optimal policy under the true transition kernel. Our results enable, for example, confidence intervals on the value of the optimal policy and high-probability guarantees for recovering the true optimal policy, providing a principled way for OPE and OPR using asymptotic statistics. Contributions In summary, the contributions of this paper are as follows: 1. We prove a central limit theorem for the count-based estimator of transition probability matrices in a finite controlled Markov chain (Theorem 15 ). This result holds under mild bounds on the return and hitting times of state action pairs (Assumption 5 ) and under weak mixing conditions (Assumption 7 ). We derive a goodness-of-fit (G.O.F.) test (Proposition 23 ) for the transition probabilities of the controlled Markov chain based on Theorem 15 . 2. We identify occasions when any transition estimate does not have a CLT (Proposition 16 ). In particular, if the policy fails to visit certain state-action pairs, we show that the estimator cannot be asymptotically tight. This result draws clear regions of testable and untestable dynamics in offline RL data. 3. Using our transition probabilities CLT (Theorem 15 ), we derive central limit theorems for the value function (Proposition 24 ), the Q-function (Proposition 25 ) and the advantage function (Proposition 27 ) for any stationary policy. We then establish a CLT for the optimal policy that maximizes the reward function for the

Read the complete text