Data-Driven Non-Parametric Model Learning and Adaptive Control of MDPs with Borel spaces: Identifiability and Near Optimal Design

Omar Mrani-Zentar, Serdar YükselarXiv 2025 · DOI · arXiv

Abstract

We consider an average cost stochastic control problem with standard Borel spaces and an unknown transition kernel. We do not assume a parametric structure on the unknown kernel. We present topologies on kernels which lead to their identifiability and ensures near optimality through robustness to identifiability errors. Following this, we present two data-driven identifiability results; the first one being Bayesian (with finite time convergence guarantees) and the second one empirical (with asymptotic convergence guarantees). The identifiability results are, then, used to design near-optimal adaptive control policies which alternate between periods of exploration, where the agent attempts to learn the true kernel, and periods of exploitation where the knowledge accrued throughout the exploration phase is used to minimize costs. We will establish that such policies are near optimal. Moreover, we will show that near optimality can also be achieved through policies that simultaneously explore and exploit the environment. Thus, our primary contributions are to present very general conditions ensuring identifiability, as well as adaptive learning and control which leads to optimality. Key tools facilitating our analysis are a general measurability theorem, robustness to model learning, and continuity of expected average cost in stationary policies under Young topology.

Introduction

In many real-world reinforcement learning and stochastic control problems, an agent must operate in an environment where the rules of state evolution—the transition kernel—are unknown. To minimize costs over time, the agent faces the classic exploration-exploitation trade-off: exploring the environment to learn its dynamics or exploiting current knowledge to minimize immediate costs.

Historically, solving this in continuous spaces (standard Borel spaces) required strong assumptions. Most existing methods assume the unknown model has a specific parametric form or requires all possible models to be absolutely continuous with respect to a reference measure. This research addresses a fundamental question: Can optimal adaptive control be achieved in continuous spaces without assuming a parametric structure or absolute continuity? By utilizing advanced topological tools, this paper establishes a non-parametric framework for model learning and control.

Theoretical Framework: Topological Robustness

The foundation of this approach lies in proving that the system's cost is robust to small identification errors. The authors utilize the "Young topology" and uniform weak convergence to demonstrate that the optimal cost is continuous with respect to the transition kernel.

This continuity is critical because it implies that if an estimated model is sufficiently close to the true model in a topological sense, the cost of using the estimated model's optimal policy will be very close to the true optimal cost. This robustness allows the agent to transition from learning the environment to controlling it effectively without requiring a perfect model of the dynamics.

Non-Parametric Learning Mechanisms

The paper proposes two distinct data-driven methods for identifying the unknown transition kernel in infinite-dimensional spaces:

  1. Bayesian Identifiability: The agent maintains a prior over the space of all possible kernels. If the agent employs an "exhaustive" exploration policy, the maximum likelihood estimator is proven to converge to the true kernel almost surely. This demonstrates that Bayesian learning remains viable even without the constraints of a parametric model, provided the initial prior assigns positive probability to the neighborhood of the true model.
  2. Empirical Identifiability via Quantization: As an alternative, the authors propose an empirical method based on systematic discretization. By quantizing the continuous state and action spaces, the agent can estimate the kernel using empirical occupation measures (counting transitions) in the approximated finite space. This bridges the gap between continuous-space theory and discrete-space estimation techniques.

Adaptive Control Strategies

Building on these identifiability results, two types of adaptive control policies are designed:

  • Alternating Policies: The agent switches between dedicated exploration phases, intended to refine the model, and exploitation phases, where it applies the best-known policy. These policies are proven to be near-optimal, achieving costs arbitrarily close to the true minimum as exploration phases increase in duration.
  • Simultaneous Policies: The agent exploits its current knowledge while occasionally taking random exploratory actions with a probability that decays over time. This research establishes that such simultaneous exploration/exploitation can achieve the exact optimal average cost asymptotically, effectively causing regret to vanish in the limit.

Key Results and Convergence

The primary contribution of this work is the mathematical proof that both Bayesian and empirical estimators converge almost surely to the true transition kernel. Furthermore, the study establishes that the resulting adaptive policies are either near-optimal or asymptotically optimal under very general conditions.

Unlike previous works that rely on absolute continuity or parametric assumptions, these results hold for general Borel spaces. The analysis is facilitated by a general measurability theorem and the application of the Young topology to ensure the continuity of expected average costs.

Limitations and Future Directions

While the non-parametric approach offers extreme generality, it comes with trade-offs. The authors note that they do not provide specific rates of convergence or sample complexity analysis; while the algorithms are guaranteed to converge, the speed of this convergence relative to parametric methods remains an open question. Additionally, the Bayesian approach assumes the existence of an "exhaustive" exploration policy, which may be challenging to design for highly complex environments. Future research may focus on deriving finite-time regret bounds to bridge the gap between these asymptotic guarantees and practical, finite-horizon performance.

Summary updated

Abstract

We consider an average cost stochastic control problem with standard Borel spaces and an unknown transition kernel. We do not assume a parametric structure on the unknown kernel. We present topologies on kernels which lead to their identifiability and ensures near optimality through robustness to identifiability errors. Following this, we present two data-driven identifiability results; the first one being Bayesian (with finite time convergence guarantees) and the second one empirical (with asymptotic convergence guarantees). The identifiability results are, then, used to design near-optimal adaptive control policies which alternate between periods of exploration, where the agent attempts to learn the true kernel, and periods of exploitation where the knowledge accrued throughout the exploration phase is used to minimize costs. We will establish that such policies are near optimal. Moreover, we will show that near optimality can also be achieved through policies that simultaneously explore and exploit the environment. Thus, our primary contributions are to present very general conditions ensuring identifiability, as well as adaptive learning and control which leads to optimality. Key tools facilitating our analysis are a general measurability theorem, robustness to model learning, and continuity of expected average cost in stationary policies under Young topology.
BibTeX
@misc{mranizentar2025data,
  author = {Omar Mrani-Zentar and Serdar Yüksel},
  title = {{Data-Driven Non-Parametric Model Learning and Adaptive Control of MDPs with Borel spaces: Identifiability and Near Optimal Design}},
  year = {2025},
  eprint = {2503.11058},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.11058},
  howpublished = {arXiv},
}
Figure