Adaptive Estimation of the Transition Density of Controlled Markov Chains
Imon Banerjee, Vinayak Rao, Harsha Honnappa · 2025
Read Adaptive Estimation of the Transition Density of Controlled Markov Chains by Imon Banerjee, Vinayak Rao, Harsha Honnappa (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-2505-14458.txt.
Introduction
Imon Banerjee, Vinayak Rao, and Harsha Honnappa build a gauge in a 2025 paper for how a steered chain moves from state to state. Such chains run through time study, trial-based learning, and probe work. Old gauge tools assume free samples and a known smoothness grade, both false when a hand steers the chain.
Their gauge adapts as it learns and asks for no prior smoothness grade. It also makes no call on how the steering hand acts, even when that hand has memory. The build rests on fresh work in free-form gauge craft. Field teams gain a tool that fits real steered data.
Catalog record
| CREATOR | Imon Banerjee, Vinayak Rao, Harsha Honnappa |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 170 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-14458
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive Estimation of the Transition Density of Controlled Markov Chains Imon Banerjee, Vinayak Rao, Harsha Honnappa Abstract Estimating the transition dynamics of controlled Markov chains is crucial in fields such as time series analysis, reinforcement learning, and system exploration. Traditional non-parametric density estimation methods often assume independent samples and require oracle knowledge of smoothness parameters like the Hölder continuity coefficient. These assumptions are unrealistic in controlled Markovian settings, especially when the controls are non-Markovian, since such parameters need to hold uniformly over all control values. To address this gap, we propose an adaptive estimator for the transition densities of controlled Markov chains that does not rely on prior knowledge of smoothness parameters or assumptions about the control sequence distribution. Our method builds upon recent advances in adaptive density estimation by selecting an estimator that minimizes a loss function and fitting the observed data well, using a constrained minimax criterion over a dense class of estimators. We validate the performance of our estimator through oracle risk bounds, employing both randomized and deterministic versions of the Hellinger distance as loss functions. This approach provides a robust and flexible framework for estimating transition densities in controlled Markovian systems without imposing strong assumptions. \DeclareSourcemap \maps [datatype=bibtex] \map \step [fieldset=addendum, null] \step [fieldset=note, null] 1 Introduction A stochastic process \{(X_{i},a_{i})\} is called a controlled Markov chain (CMC) [ 18 ] if the next “state” X_{i+1} depends only on the current state X_{i} and the current “control” a_{i} . Informally, this means: \displaystyle\mathbb{P}\bigl(X_{i+1}\in dy\mid X_{0},a_{0},\dots,X_{i},a_{i}\bigr)=\mathbb{P}\bigl(X_{i+1}\in dy\mid X_{i}=x_{i},\,a_{i}=l_{i}\bigr)=s(x_{i},l_{i},y)\,\mu_{\chi}(dy), where s(x_{i},l_{i},y) gives the probability density of moving from the current state x_{i} with action l_{i} to the next state y . Here, the actions a_{i} depend only on the information available up to time i . This paper addresses adaptive estimation of the transition density s of controlled Markov chains. In general, controlled Markov chains can be used to model both time-homogenous (like i.i.d [ 56 ] , Markovian [ 16 ] ) and time-inhomogenous (like i.n.i.d, time-inhomogenous Markovian [ 26 , 43 ] , Markov decision process [ 33 ] ) data. However, they also appear in numerous other problems like offline reinforcement learning [ 38 ] , system stabilisation [ 59 ] , or system identification [ 39 , 41 ] . As a specific example, consider prescribing medication to a diabetic patient, where the state is the current blood glucose level, and the control is the prescribed medication [ 53 ] . There is no reason to believe that the previous examples involve controls that are Markovian. It is known that certain categories of adversarial Markov games [ 57 ] , reward machines [ 34 ] , and minimum entropy explorations [ 47 ] induce Markovian state transitions with non-Markovian controls. This necessitates sharp estimates of the transition dynamics of Markovian systems in the presence of non-Markovian controls. Although nonparametric estimation of the density of i.i.d [ 56 ] or (more recently) Markovian [ 4 , 40 ] samples is a well-studied topic and has wide applications in settings like regression, classification, and unsupervised learning [ 42 ] , there is little existing work addressing the estimation of controlled Markov chains. An inherent challenge of this setup is non-stationarity. Recall from [ 4 ] that a natural approach to estimating the transition density of a Markov chain is to estimate the joint density X_{i},X_{i+1} and the marginal X_{i} density, and then take the ratio. This method works well even if the Markov chains are ergodic rather than stationary. However, if the process is non-stationary and non-ergodic, then there are no well-defined estimators for the joint or the marginal, and the conditional cannot be derived from their ratio. On a related note, a controlled Markov chain may have all amenable properties like recurrence and mixing without being ergodic (see Lemma 4 ). Furthermore, non-parametric estimation presents a number of difficulties, being highly sensitive to the choice of hyperparameters like the bandwidth of the estimator. For example, with n samples and assuming that the density s is \sigma -Hölder continuous, one can set the bandwidth to be O(n^{-1/(2\sigma+1)}) to obtain the minimax risk O(n^{-2\sigma/(2\sigma+1)}) [ 56 , Chapter 1] . However, while it is common practice to assume such oracle knowledge about \sigma , this is often unrealistic. Such an assumption is especially problematic when the data is generated by a controlled Markovian process since one requires it to hold for allpossible values of controls. Specifically, with X_{i} being the state at time i , a_{i} being the control at time i , and X_{i+1} being the state at time i+1 , one requires \mathbb{P}\left(X_{i+1}\in dx|X_{i}=x,a_{i}=l\right)=:s(x,l,y)\mu_{\chi}(dx) to be \sigma -Hölder continuous for all values of l . To avoid such strong assumptions, we rely upon the recent and rapidly evolving techniques of adaptive density estimation . This technique was pioneered by [ 12 ] and has been further developed in [ 42 , 8 , 10 , 11 , 17 , 52 ] . In this paper, our objective is to adapt this technique and create an adaptive estimator for the transition densities of controlled Markov chains. Informally, adaptive estimation selects a best estimator with respect to loss \mathcal{H} from a known class \mathcal{M} by minimising a contrast (which for us, is eq. Constrast below), thereby completely sidestepping the problem of manually setting the bandwidth. We refer the readers to Chapter 1 of the textbook [ 42 ] for more details. Two questions remain: 1) Is the optimisation problem introduced by the contrast computationally tractable for our choices of \mathcal{H} , and \mathcal{M} ?, and 2) Is the selected estimator minimax optimal over the class of all possible estimators under appropriate assumptions on the true density? The answer to both of these questions are in the affirmative. For the former, see Remark 3 , and for the latter, see Theroem 4 , and Corollaries 2 , and 3 . Importantly, the minimaxity guarantee is achieved without prior knowledge about smoothness parameters. Technical Contributions: Our main contribution is showing that an optimal histogram estimator (computable in polynomial time) of the transition function s based on the dyadic partitions satisfies an oracle risk bound irrespective of the distribution of the controls a_{i} (Theorem 1 ). Interestingly, we find that the optimal estimator can be constructed without any assumptions on the distribution of the control sequence {a_{i}} . We then validate its performance through oracle risk bounds, employing both instance dependent (Theorem 1 ) and instance independent (Theorems 2 , and 3 ) versions of the Hellinger distance as our loss function. Although [ 7 ] recently derived optimal estimators for the transition density of finite-state, finite-control controlled Markov chains (CMCs), there is surprisingly little work attempting to optimally estimate the transition density of a CMC with continuous state-control spaces. In a series of groundbreaking papers, adaptive estimators were developed for transition densities in various settings: i.i.d. data [ 9 ] , stationary Markov chains [ 37 ] , non-stationary \beta -mixing Markov chains [ 52 ] , and stationary \beta -mixing paired processes [ 1 ] . This paper generalizes all of these prior works in several directions. Unlike [ 9 , 37 , 1 ] , we do