Pith. sign in

REVIEW 3 major objections 6 minor 85 references

Adaptive Estimation of the Transition Density of Controlled Markov Chains

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An adaptive histogram estimator with a data-driven penalty achieves oracle risk bounds for transition densities of controlled Markov chains with continuous states and actions, without smoothness or control-distribution assumptions.

desk verdict The framework is right, but the proof of Theorem 1 misapplies Proposition 10 and the main oracle inequality is not established as written; the paper deserves a serious referee, not desk rejection. read the letter →

arxiv 2505.14458 v1 pith:36PL2JGM submitted 2025-05-20 math.ST stat.TH

Imon Banerjee , Vinayak Rao , Harsha Honnappa This is my paper · ORCID
classification math.STstat.TH
keywords controlledtransitionadaptiveassumptionschainsdensityestimationestimator
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is about a statistical problem: you watch a system that moves from state to state, and at each step someone applies an action, or control. The goal is to learn the transition function, the probability rule s(x, l, y) that takes current state x and action l and gives the distribution of the next state y. These models, called controlled Markov chains, underlie reinforcement learning, time series analysis, and system identification. The usual nonparametric way to learn such a function needs the user to know in advance how smooth it is, to set a bandwidth, and the standard theory breaks down when the actions depend on the past in complicated, possibly adversarial ways. The paper's proposal is a set of candidate step functions (histograms) on finer and finer grids, with a penalty for how many cells each candidate uses. A data-driven score, called a contrast, picks the candidate that fits the observed transitions well without being too complex. The main guarantee, Theorem 1, says the selected histogram is within a constant factor of the best possible candidate, for any control sequence whatsoever, when performance is measured by a randomized version of the Hellinger distance. Switching to the usual deterministic Hellinger distance requires the process to mix exponentially fast, and when no long-run average occupation measure exists, to return to every grid cell reasonably often. In that regime the paper also provides matching lower bounds showing the remaining error is near the theoretical floor.
Extended reading notes

Core claim

Theorem 1: 'There exist universal constants L0 and C such that for all L >= L0 and l >= 1, the estimator s_hat satisfies C E[H^2(s, s_hat)] <= inf_{m in M_l} {E[H^2(s, V_m)] + pen(m)}.' If true, this means the adaptively selected dyadic histogram achieves the best trade-off between approximation error and model complexity for the transition density of any controlled Markov chain with compact state and action spaces, with no smoothness oracle, no mixing assumption, and no restriction on how the controls a_i are chosen.

Load-bearing premise

The weakest load-bearing premise sits in the deterministic-Hellinger theorems, not in the histogram construction. Theorem 3 (Section 3.3) requires the state-action process to be recurrent on dyadic cells with finite uniform expected return time T(S), and requires n >= 2T(S*); both Theorem 2 and 3 require Assumption 1, that the strong mixing coefficients decay exponentially, alpha_{i,j} <= e^{-c_p(j-i)}. This assumption is needed to apply the Bernstein-type inequality of [45] used in Proposition 23 (Section B.19), and the paper itself states no analogue exists for polynomial mixing. The premise is load-bearing because the authors prove in Theorem 4.2 that when n falls below a T(S*)^2-scale threshold the minimax risk is bounded below by a constant, so the oracle bounds are vacuous exactly when returns are slow.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes a penalized histogram estimator for the transition density of a controlled Markov chain with compact continuous state and control spaces. The main theoretical object is Theorem 1, an oracle inequality under an empirical Hellinger loss that is asserted to hold without any assumptions on the distribution or dependence structure of the control sequence. Theorems 2 and 3 convert this into deterministic Hellinger risk bounds under exponential strong mixing (Assumption 1) and, in Theorem 3, under a finite expected return-time condition; Theorem 4 states a minimax lower bound under the same conditions. Applications to Hölder and Besov classes and to fully connected Markovian and non-Markovian controlled chains are also given.

Significance. If the proofs are correct, this would be a valuable contribution: an instance-dependent oracle inequality for non-stationary, non-ergodic controlled Markov chains, a deterministic-Hellinger extension using α-mixing rather than β-mixing, a Kac-type return-time lower bound (Lemma 25) of independent interest, and explicit minimax statements. The paper also provides useful bridge results to existing adaptive density estimation theory and to fully connected models. However, the central proof of Theorem 1 contains a specific gap in the union-bound step, and the proofs of Theorem 2 and Theorem 4 contain direction errors. These are load-bearing issues, not presentation defects, so the current version cannot be accepted as written.

major comments (3)
  1. [Section B.2, Eq. (B.13) and Proposition 10] The proof of Proposition 2, and hence of Theorem 1, is missing a valid step at the union bound. The deviation event that must be controlled is of the form sup_{f∈s_{m'}, m'∈M_l} [(3/4)(1−1/√2)H2(ˆs_m,f)+T(ˆs_m,f)−pen(m')] + pen(m) + 1/n ≥ RHS, whose leading Hellinger term is H2(ˆs_m,f), the empirical Hellinger distance between two data-dependent histograms. Proposition 10, however, bounds an event whose leading term is (3/4)(1−1/√2)H2(s,f2) with f1,f2 piecewise constant functions and with the true transition density s in the Hellinger term. No inequality in Section B.10 or in Appendix A relates H2(ˆs_m,f) to H2(s,f2) in a way that makes the proposed union bound valid. In addition, Eq. (B.13) as printed bounds P(sup X_f ≤ RHS) by a sum of probabilities P(X_f ≤ RHS), which is the reverse of a tail union bound; even after correcting '≤' to '≥', the mismatch between H2(ˆs_m,f) and H2(s,f2) remains. Since Theorem 1 rests on Proposition 2, the central oracle inequality is not established as written.
  2. [Section B.19, proof of Theorem 2] The transition from Proposition 23 to the displayed 'only need to upper bound R(n)' formula is invalid in direction. Proposition 23 gives a remainder with denominator 4C∆ρ⋆(Sr), while the proof replaces this by the smaller denominator 4C∆ sup_i P((Xi,ai)∈Sr). For fixed numerator A>0, the function d ↦ exp(−A/d) is increasing in d>0, so decreasing the denominator makes the remainder term smaller, not larger. The proof therefore establishes an upper bound only for a quantity that is no larger than the R(n) that actually needs to be controlled in Proposition 23 and in the statement of Theorem 2. The later replacement of sup_i P((Xi,ai)∈Smin) by P((Xi,ai)∈Smin) has the same direction problem. The proof must keep ρ⋆, or an upper bound on it, throughout the derivation.
  3. [Section 3.3, Theorem 4 and Proposition 19] The minimax statement in Eq. (3.5) has the wrong inequality sign. Part 2 of Proposition 19 proves that there exists a controlled Markov chain for which no estimator satisfies E[h2_n(s,ˆs)] ≤ 1/(2(1+π^2)); this is a lower bound of the form inf_ˆs sup_s E[h2_n(s,ˆs)] ≥ 1/(2(1+π^2)), not the upper bound '≤' printed in Eq. (3.5). The proof is internally inconsistent with the statement. Additionally, the derivation of Proposition 19's lower bound shows P(h2_n(s,ˆs)>ε^2) > c for ε∈(0,1/32); integrating over t=ε^2 introduces a factor of 1/1024 that is not reflected in the constant 1/(2(1+π^2)). Both the direction error and the missing integration factor affect the paper's main minimax-optimality claim and need to be corrected.
minor comments (6)
  1. [Section 1, Technical Contributions] There is a typo: 'Theroem 4' should read 'Theorem 4'.
  2. [Section B.2, Case I] In the Case I display, H2(ˆsm, ˆsm) appears on the right-hand side; as printed this term vanishes, making the inequality trivial. The intended quantity appears to be H2(s, ˆsm) or an analogous term coming from Proposition 10.
  3. [Section B.19, Theorem 2] The denominator notation '4n−1' in the statement of Theorem 2 is ambiguous; it should read 4n^{−1}, as in the proof.
  4. [Section 3.2, proof of Corollary 1] The sentence 'The other case is handled similarly with more careful book-keeping' is too terse for a result that relies on identifying ρ⋆; the missing case should be written out or suppressed by a uniform argument.
  5. [Section B.5, proof of Proposition 5] The text says 'R(1)(n) = o(R(1)(n))'; this should be 'R(1)(n) = o(R(2)(n))'.
  6. [Abstract and Introduction] The abstract contains an awkward inserted '{and}' in 'minimizes a loss function {and} fitting the observed data well'; this should be cleaned up.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the oracle inequalities are proved against external benchmarks; self-citations are orientational or used only in an illustrative lemma, and the flagged Proposition 10 issue is a correctness gap, not a circular reduction.

full rationale

The central results are not circular. Theorem 1's selection scheme follows the Baraud/Birgé/Sart histogram-selection machinery (references [9], [10], [52]) and is proved by verifying the canonical extension to the controlled-Markov setting: Proposition 10 is an adaptation of Proposition B.1 of [52], the union bound in Section B.2 uses the dyadic-set cardinality bound of Proposition 11, and Proposition 1 is proved from scratch in Section B.1. Theorems 2 and 3 rest on concentration inequalities of [45], the covariance bound of Lemma 24, and the renewal-type lower bound of Lemma 25, none of which are taken from the authors' own papers. The only overlapping self-citations are [7, Lemma 1] inside the proof of Lemma 6 (Section B.6), which is used to pass from the Dobrushin coefficient to phi-mixing in an illustrative fully-connected-chain application, and [5] and [6] in the concluding remarks; these are not load-bearing for Theorems 1 through 4. The paper also explicitly discloses its weakest assumption: Remark 4 states 'To the best of our knowledge, there exists no equivalent results which relaxes the assumptions to accommodate polynomially decaying strong mixing coefficients,' and Section 5 repeats that concentration technology for summable mixing is open, which is an honest limitation rather than a circular justification. The skeptic's concern about Proposition 2 is a proof-level gap: Proposition 10, as stated, bounds H2(s,f2), while Section B.2 needs a bound on an event containing H2(s_hat_m,f); however, a proof gap is a correctness risk, not an instance of a derived quantity reducing by construction to its own input. No fitted constants are renamed as predictions, and no uniqueness theorem from the authors' prior work is invoked to force the choice of estimator. Overall circularity score 1 of 10, reflecting only the presence of minor, non-load-bearing self-citations.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The ledger is light: the central Theorem 1 is assumption-free beyond compactness and contains no fitted constants; the deterministic-Hellinger theorems pay for their strength with Assumption 1 and the return-time and recurrence assumptions, both explicitly flagged by the authors. The non-constructive universal constants (L0, C) are the main hidden load, recorded in the reproducibility and citation notes rather than as fitted parameters.

assumptions (7)
  • domain assumption Compactness of state and control spaces chi and I (or restriction of s to a compact subset A)
    Section 1.1: the theory is stated on compact chi and I; for non-compact spaces it applies to restrictions s restricted to A, which are not conditional densities.
  • domain assumption Assumption 1: geometric strong mixing of {(X_i, a_i)} with alpha_{i,j} <= e^{-c_p(j-i)}
    Entered in Section 3 under 'Mixing'; required by the Bernstein inequality of [45] used in Proposition 23; the paper notes no equivalent exists for polynomially decaying coefficients.
  • domain assumption Recurrence: T(S) < infinity for all dyadic cells S and n >= 2T(S*) in Theorem 3
    Section 3.3 states 'we implicitly assume throughout the rest of this section that T(S) < infinity for any S in m_ref^(2)'; without it Lemma 25 gives a vacuous lower bound, and Theorem 4.2 shows the deterministic minimax guarantee collapses below a T(S*)^2 threshold.
  • domain assumption Existence of the ergodic occupation measure nu with r_n = ||nu_n - nu||_TV (Theorem 2)
    Definition 2 and Remark 5: the deterministic Hellinger loss h^2 is defined with respect to nu; r_n = 0 under stationarity, and the paper assumes the limit defining nu exists.
  • domain assumption Assumption 2 (Corollary 3): Holder or Besov smoothness of sqrt(s) and uniform density bound Gamma on (X_i, a_i)
    Used in Section 4.1 to convert the oracle bound into rates over functional classes; the Besov condition restricts p, sigma, and the density bound Gamma.
  • domain assumption Assumption 3 (Section 4.3): minorization of controls, full connectivity, and alpha-mixing
    Used for Proposition 8 (return-time and mixing bounds); Lemma 9 shows minorization alone is insufficient, so the assumption is not redundant.
  • standard math External standard results: Bernstein inequality for alpha-mixing processes [45], Hajnal-Bartlett theorem [32], Kac's theorem [46], Doob's optional stopping, Cantelli's inequality
    Invoked without proof in Propositions 23, Lemma 6, Proposition 21, Lemma 25, and Lemma 22 respectively; these are standard background results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Estimation of the Transition Density of Controlled Markov Chains." pith.science (2026). https://pith.science/paper/36PL2JGM

@misc{pith2026250514458,
  author       = {Pith},
  title        = {Pith review of: Adaptive Estimation of the Transition Density of Controlled Markov Chains},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36PL2JGM}},
  note         = {Machine review of arXiv:2505.14458}
}
read the original 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\"older 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

85 extracted references · 56 canonical work pages

  1. [10]

    Estimating the intensity of a random measure by histogram type estimators

    Yannick Baraud and Lucien Birg ´e. “Estimating the intensity of a random measure by histogram type estimators”. en. In: Probability Theory and Related Fields 143.1 (Jan. 2009), pp. 239–284. ISSN : 1432-2064. DOI: 10.1007/s00440-007-0126-6

    doi:10.1007/s00440-007-0126-6 2009

  2. [1]

    Inhomogeneous and anisotropic conditional density estimation from dependent data

    Nathalie Akakpo and Claire Lacour. “Inhomogeneous and anisotropic conditional density estimation from dependent data”. In: Electronic Journal of Statistics 5.none (Jan. 2011), pp. 1618–1653. ISSN : 1935-7524, 1935-7524. DOI: 10.1214/11-EJS653

    doi:10.1214/11-ejs653 2011

  3. [2]

    An elementary view of Euler’s summation formula

    Tom M Apostol. “An elementary view of Euler’s summation formula”. In: The American Mathemat- ical Monthly 106.5 (1999), pp. 409–418

    1999

  4. [3]

    Ash and Catherine A

    Robert B. Ash and Catherine A. Doleans-Dade. Probability and Measure Theory. en. Academic Press,

  5. [4]

    Kernel Estimation for Real-Valued Markov Chains

    Krishna B Athreya. “Kernel Estimation for Real-Valued Markov Chains”. en. In: (1998), p. 18

    1998

  6. [5]

    CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Median

    Imon Banerjee and Sayak Chakrabarty. CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Median. May 2025. DOI: 10.48550/arXiv.2505.11725

    doi:10.48550/arxiv.2505.11725 2025

  7. [6]

    Goggin’s corrected Kalman Filter: Guarantees and Filtering Regimes

    Imon Banerjee and Itai Gurvich. Goggin’s corrected Kalman Filter: Guarantees and Filtering Regimes. Feb. 2025. DOI: 10.48550/arXiv.2502.14053

    doi:10.48550/arxiv.2502.14053 2025

  8. [7]

    Off-line Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity

    Imon Banerjee, Harsha Honnappa, and Vinayak Rao. “Off-line Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity”. In: Operations Research (Feb. 2025). ISSN : 0030- 364X. DOI: 10.1287/opre.2023.0046

    arXiv 2025

Show all 85 references
  1. [8]

    A new method for estimation and model selection:$$ \rho $$- estimation

    Y . Baraud, L. Birg ´e, and M. Sart. “A new method for estimation and model selection:$$ \rho $$- estimation”. en. In: Inventiones mathematicae 207.2 (Feb. 2017), pp. 425–517. ISSN : 1432-1297. DOI: 10.1007/s00222-016-0673-5

    2017 doi

  2. [9]

    Estimator selection with respect to Hellinger-type risks

    Yannick Baraud. “Estimator selection with respect to Hellinger-type risks”. en. In: Probability Theory and Related Fields 151.1 (Oct. 2011), pp. 353–401. ISSN : 1432-2064. DOI: 10.1007/s00440- 010-0302-y

    2011 doi

  3. [11]

    Rho-estimators revisited: General theory and applications

    Yannick Baraud and Lucien Birg ´e. “Rho-estimators revisited: General theory and applications”. In: The Annals of Statistics 46.6B (Dec. 2018), pp. 3767–3804. ISSN : 0090-5364, 2168-8966. DOI: 10. 1214/17-AOS1675

    2018

  4. [12]

    Risk bounds for model selection via penaliza- tion

    Andrew Barron, Lucien Birg ´e, and Pascal Massart. “Risk bounds for model selection via penaliza- tion”. en. In: Probability Theory and Related Fields 113.3 (Feb. 1999), pp. 301–413. ISSN : 1432-

    1999

  5. [13]

    Interpolation Spaces: An Introduction

    J ¨oran Bergh and J ¨orgen L¨ofstr¨om. Interpolation Spaces: An Introduction. en. Ed. by S. S. Chern et al. V ol. 223. Grundlehren der mathematischen Wissenschaften. Berlin, Heidelberg: Springer, 1976. ISBN : 978-3-642-66453-3 978-3-642-66451-9. DOI: 10.1007/978-3-642-66451-9

    1976 doi

  6. [14]

    Occupation measures for controlled Markov processes: char- acterization and optimality

    Abhay G. Bhatt and Vivek S. Borkar. “Occupation measures for controlled Markov processes: char- acterization and optimality”. In: The Annals of Probability 24.3 (July 1996), pp. 1531–1562. ISSN : 0091-1798, 2168-894X. DOI: 10.1214/aop/1065725192

    1996

  7. [15]

    Riddhiman Bhattacharya and Galin L. Jones. Explicit Constraints on the Geometric Rate of Conver- gence of Random Walk Metropolis-Hastings. July 2023. DOI: 10.48550/arXiv.2307.11644

    2023 doi arXiv

  8. [16]

    Statistical methods in Markov chains

    Patrick Billingsley. “Statistical methods in Markov chains”. In: The Annals of Mathematical Statistics (1961), pp. 12–40. 17

    1961

  9. [17]

    Model selection via testing: an alternative to (penalized) maximum likelihood estima- tors

    Lucien Birg ´e. “Model selection via testing: an alternative to (penalized) maximum likelihood estima- tors”. In: Annales de l’IHP Probabilit´es et statistiques. V ol. 42. 2006, pp. 273–325

    2006

  10. [18]

    Topics in controlled Markov chains

    Vivek S Borkar. Topics in controlled Markov chains. Harlow, UK: Longman Scientific & Technical, 1991

    1991

  11. [19]

    Basic Properties of Strong Mixing Conditions. A Survey and Some Open Ques- tions

    Richard C. Bradley. “Basic Properties of Strong Mixing Conditions. A Survey and Some Open Ques- tions”. In: Probability Surveys 2 (2005), pp. 107–144. DOI: 10.1214/154957805100000104

    2005 doi

  12. [20]

    Some Examples of Mixing Random Fields

    Richard C. Bradley. “Some Examples of Mixing Random Fields”. In: Rocky Mountain Journal of Mathematics 23.2 (June 1993), pp. 495–519. ISSN : 0035-7596. DOI: 10 . 1216 / rmjm / 1181072573

    1993

  13. [21]

    On the Consistency of Maximum Likelihood Estimation of Probabilistic Principal Component Analysis

    Arghya Datta and Sayak Chakrabarty. “On the Consistency of Maximum Likelihood Estimation of Probabilistic Principal Component Analysis”. en. In: Advances in Neural Information Processing Systems 36 (Dec. 2023), pp. 28648–28662

    2023

  14. [22]

    Trade-off Between Dependence and Complexity for Non- parametric Learning – an Empirical Process Approach

    Nabarun Deb and Debarghya Mukherjee. Trade-off Between Dependence and Complexity for Non- parametric Learning – an Empirical Process Approach . Jan. 2024. DOI: 10 . 48550 / arXiv . 2401.08978

    2024 doi arXiv

  15. [23]

    Degree of Adaptive Approximation

    Ronald A. DeV ore and Xiang Ming Yu. “Degree of Adaptive Approximation”. In: Mathematics of Computation 55.192 (1990), pp. 625–635. ISSN : 0025-5718. DOI: 10.2307/2008437

    1990 doi

  16. [24]

    Central Limit Theorem for Nonstationary Markov Chains. I

    R. L. Dobrushin. “Central Limit Theorem for Nonstationary Markov Chains. I”. In: Theory of Prob- ability & Its Applications 1.1 (Jan. 1956), pp. 65–80. ISSN : 0040-585X. DOI: 10.1137/1101006

    1956 doi

  17. [25]

    Central Limit Theorem for Nonstationary Markov Chains. II

    R. L. Dobrushin. “Central Limit Theorem for Nonstationary Markov Chains. II”. In: Theory of Proba- bility & Its Applications1.4 (Jan. 1956), pp. 329–383.ISSN : 0040-585X. DOI: 10.1137/1101029

    1956 doi

  18. [26]

    Dmitry Dolgopyat and Omri M. Sarig. Local Limit Theorems for Inhomogeneous Markov Chains . en. V ol. 2331. Lecture Notes in Mathematics. Cham: Springer International Publishing, 2023. ISBN : 978-3-031-32600-4 978-3-031-32601-1. DOI: 10.1007/978-3-031-32601-1

    2023 doi

  19. [27]

    Probability inequalities related to Markov’s theorem

    BK Ghosh. “Probability inequalities related to Markov’s theorem”. In: The American Statistician56.3 (2002), pp. 186–190

    2002

  20. [28]

    On a New Characterization of Harris Recurrence for Markov Chains and Processes

    Peter Glynn and Yanlin Qu. “On a New Characterization of Harris Recurrence for Markov Chains and Processes”. en. In: Mathematics 11.9 (Jan. 2023), p. 2165. ISSN : 2227-7390. DOI: 10.3390/ math11092165

    2023

  21. [29]

    Wide-sense regeneration for Harris recurrent Markov processes: an open prob- lem

    Peter W. Glynn. “Wide-sense regeneration for Harris recurrent Markov processes: an open prob- lem”. en. In: Queueing Systems 68.3 (Aug. 2011), pp. 305–311. ISSN : 1572-9443. DOI: 10.1007/ s11134-011-9238-x

    2011

  22. [30]

    Convergence of filters with applications to the Kalman-Bucy case

    E.M. Goggin. “Convergence of filters with applications to the Kalman-Bucy case”. In: IEEE Trans- actions on Information Theory 38.3 (May 1992), pp. 1091–1100. ISSN : 1557-9654. DOI: 10.1109/ 18.135648

    1992

  23. [31]

    Probability: a graduate course

    Allan Gut. Probability: a graduate course. V ol. 5. Springer, 2005

    2005

  24. [32]

    Weak ergodicity in non-homogeneous Markov chains

    John Hajnal and Maurice S Bartlett. “Weak ergodicity in non-homogeneous Markov chains”. In: Mathematical Proceedings of the Cambridge Philosophical Society . V ol. 54. Cambridge University Press, 1958, pp. 233–246

    1958

  25. [33]

    Recurrence con- ditions for Markov decision processes with Borel state space: a survey

    On ´esimo Hern´andez-Lerma, Ra´ul Montes-de-Oca, and Rolando Cavazos-Cadena. “Recurrence con- ditions for Markov decision processes with Borel state space: a survey”. In: Annals of Operations Research 28.1 (1991), pp. 29–46. 18

    1991

  26. [34]

    Using Reward Machines for High-Level Task Specification and Decom- position in Reinforcement Learning

    Rodrigo Toro Icarte et al. “Using Reward Machines for High-Level Task Specification and Decom- position in Reinforcement Learning”. en. In: Proceedings of the 35th International Conference on Machine Learning. PMLR, July 2018, pp. 2107–2116

    2018

  27. [35]

    Concentration inequalities for dependent random variables via the martingale method

    Leonid Aryeh Kontorovich, Kavita Ramanan, et al. “Concentration inequalities for dependent random variables via the martingale method”. In: Annals of Probability 36.6 (2008), pp. 2126–2158

    2008

  28. [36]

    Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing

    Vikram Krishnamurthy. Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing. Cambridge: Cambridge University Press, 2016.ISBN : 978-1-107-13460-7. DOI: 10.1017/ CBO9781316471104

    2016

  29. [37]

    Adaptive estimation of the transition density of a Markov chain

    Claire Lacour. “Adaptive estimation of the transition density of a Markov chain”. In: Annales de l’Institut Henri Poincare (B) Probability and Statistics 43.5 (Sept. 2007), pp. 571–597. ISSN : 02460203. DOI: 10.1016/j.anihpb.2006.09.003

    2007 doi

  30. [38]

    Offline reinforcement learning: Tutorial, review, and perspectives on open prob- lems

    Sergey Levine et al. “Offline reinforcement learning: Tutorial, review, and perspectives on open prob- lems”. In: arXiv preprint arXiv:2005.01643 (2020)

    2020 arXiv

  31. [39]

    System identification (2nd ed.): theory for the user

    Lennart Ljung. System identification (2nd ed.): theory for the user . NJ, USA: Prentice Hall PTR,

  32. [40]

    Spectral thresholding for the estimation of Markov chain tran- sition operators

    Matthias L ¨offler and Antoine Picard. Spectral thresholding for the estimation of Markov chain tran- sition operators. Oct. 2021. DOI: 10.48550/arXiv.1808.08153

    2021 doi arXiv

  33. [41]

    Active learning for nonlinear system identifi- cation with guarantees

    Horia Mania, Michael I Jordan, and Benjamin Recht. “Active learning for nonlinear system identifi- cation with guarantees”. In: arXiv preprint arXiv:2006.10277 (2020)

    2020 arXiv

  34. [42]

    Concentration Inequalities and Model Selection

    Pascal Massart. Concentration Inequalities and Model Selection . en. Ed. by Jean Picard. V ol. 1896. Lecture Notes in Mathematics. Berlin, Heidelberg: Springer, 2007. ISBN : 978-3-540-48497-4. DOI: 10.1007/978-3-540-48503-2

    2007 doi

  35. [43]

    On the local limit theorems for lower psi- mixing Markov chains

    Florence Merlev `ede, Magda Peligrad, and Costel Peligrad. “On the local limit theorems for lower psi- mixing Markov chains”. en. In: Latin American Journal of Probability and Mathematical Statistics 19.1 (2022), p. 1103. ISSN : 1980-0436. DOI: 10.30757/ALEA.v19-45

    2022 doi

  36. [44]

    On the local limit theorems for psi- mixing Markov chains

    Florence Merlev `ede, Magda Peligrad, and Costel Peligrad. “On the local limit theorems for psi- mixing Markov chains”. en. In: Latin American Journal of Probability and Mathematical Statistics 18.1 (2021), p. 1221. ISSN : 1980-0436. DOI: 10.30757/ALEA.v18-45

    2021 doi

  37. [45]

    Bernstein inequality and moderate de- viations under strong mixing conditions

    Florence Merlev `ede, Magda Peligrad, Emmanuel Rio, et al. “Bernstein inequality and moderate de- viations under strong mixing conditions”. In: High dimensional probability V: the Luminy volume 5 (2009), pp. 273–292

    2009

  38. [46]

    Markov chains and stochastic stability

    Sean P Meyn and Richard L Tweedie. Markov chains and stochastic stability . Springer Science & Business Media, 2012

    2012

  39. [47]

    The Importance of Non-Markovianity in Maximum State Entropy Exploration

    Mirco Mutti, Riccardo De Santi, and Marcello Restelli. “The Importance of Non-Markovianity in Maximum State Entropy Exploration”. In: arXiv preprint arXiv:2202.03060 (2022)

    2022 arXiv

  40. [48]

    A User’s Guide to Measure Theoretic Probability

    David Pollard. A User’s Guide to Measure Theoretic Probability. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge: Cambridge University Press, 2001. ISBN : 978-0-521-80242-

    2001

  41. [49]

    Asymptotic Theory of Weakly Dependent Random Processes

    Emmanuel Rio. Asymptotic Theory of Weakly Dependent Random Processes. en. V ol. 80. Probability Theory and Stochastic Modelling. Berlin, Heidelberg: Springer, 2017.ISBN : 978-3-662-54322-1 978- 3-662-54323-8. DOI: 10.1007/978-3-662-54323-8

    2017 doi

  42. [50]

    Sheldon M. Ross. Stochastic Processes. en. Wiley, 1983. ISBN : 978-0-471-09942-0. 19

    1983

  43. [51]

    Density estimation under local differential privacy and Hellinger loss

    Mathieu Sart. “Density estimation under local differential privacy and Hellinger loss”. In: Bernoulli 29.3 (Aug. 2023), pp. 2318–2341. ISSN : 1350-7265. DOI: 10.3150/22-BEJ1543

    2023 doi

  44. [52]

    DOI: 10.1017/CBO9780511811555

    doi

  45. [53]

    Modeling Medical Treatment Using Markov Decision Processes

    Andrew J. Schaefer et al. “Modeling Medical Treatment Using Markov Decision Processes”. en. In: Operations Research and Health Care: A Handbook of Methods and Applications . Ed. by Margaret L. Brandeau, Franc ¸ois Sainfort, and William P. Pierskalla. Boston, MA: Springer US, 2...

    2004

  46. [54]

    Semi-stationary processes

    Richard F. Serfozo. “Semi-stationary processes”. en. In: Zeitschrift f ¨ur Wahrscheinlichkeitstheo- rie und Verwandte Gebiete 23.2 (June 1972), pp. 125–132. ISSN : 1432-2064. DOI: 10 . 1007 / BF00532855

    1972

  47. [55]

    Reinforcement learning: An introduction

    Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018

    2018

  48. [56]

    Estimation of the transition density of a Markov chain

    Mathieu Sart. “Estimation of the transition density of a Markov chain”. In: Annales de l’IHP Proba- bilit´es et statistiques. V ol. 50. 2014, pp. 1028–1068

    2014

  49. [57]

    On the Foundation of Distributionally Robust Reinforcement Learning

    Shengbo Wang et al. On the Foundation of Distributionally Robust Reinforcement Learning . Jan

  50. [58]

    Products of Indecomposable, Aperiodic, Stochastic Matrices

    J. Wolfowitz. “Products of Indecomposable, Aperiodic, Stochastic Matrices”. In: Proceedings of the American Mathematical Society 14.5 (1963), pp. 733–737. ISSN : 0002-9939. DOI: 10.2307/ 2034984

    1963

  51. [59]

    Online Adversarial Stabilization of Unknown Linear Time-Varying Systems

    Jing Yu, Varun Gupta, and Adam Wierman. “Online Adversarial Stabilization of Unknown Linear Time-Varying Systems”. In:2023 62nd IEEE Conference on Decision and Control (CDC). Dec. 2023, pp. 8320–8327. DOI: 10.1109/CDC49753.2023.10383849. A Sketch of Proof of Proposition 2 We f...

    2023

  52. [61]

    Introduction to Nonparametric Estimation

    Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009

    2009

  53. [66]

    Furthermore, P m∈M∞ e−|m| ≤ P l≥0 2l(2d1+d2)e−2l(2d1+d2) ≤ 15, and for any m ∈ Ml, |m| ≤2l(2d1+d2) where |m| is the cardinality of the partition m

    Ml ⊂ Ml+1, for any l. Furthermore, P m∈M∞ e−|m| ≤ P l≥0 2l(2d1+d2)e−2l(2d1+d2) ≤ 15, and for any m ∈ Ml, |m| ≤2l(2d1+d2) where |m| is the cardinality of the partition m

  54. [67]

    If m ∈ Ml\Ml′, where l′ < l, then |m| > l′

  55. [68]

    , Kl} ∈S m∈Ml m such that K ⊂ Ki, i∈ {1,

    If K ∈ m ∈ Ml, then ∃ {K1, K2, . . . , Kl} ∈S m∈Ml m such that K ⊂ Ki, i∈ {1, . . . ,l}

  56. [69]

    To be precise, m ∨ m′ = [ K′∈m′ m ∨ K′ (A.1) where m ∨ K′ is as defined in eq

    Define m ∨ m′ as the set of non-empty intersections of m′ with the elements of m. To be precise, m ∨ m′ = [ K′∈m′ m ∨ K′ (A.1) where m ∨ K′ is as defined in eq. (2.5). Then, |m ∨ m′| ≤2(|m| + |m′|). The rest of the second case can now be divided into the following 3 steps. Ste...

  57. [70]

    Sincepen(m) = L(1.5+log n)|m|/n, and |χ×I×χ| = 1 −2 − L(1.5 + logn)/n ≤ 3 − L(1.5 + logn)|m⋆ 2 ∨ K|/n

    ≤ 3 − pen(m⋆ 2 ∨ K) with the second inequality following by definition. Sincepen(m) = L(1.5+log n)|m|/n, and |χ×I×χ| = 1 −2 − L(1.5 + logn)/n ≤ 3 − L(1.5 + logn)|m⋆ 2 ∨ K|/n. This, with a bit of rearrangement implies |m⋆ 2 ∨ K| ≤1 + 5n L(1.5 + logn) ≤ n. Therefore, there exist...

  58. [71]

    Hence, with probability at most exp − n pen(m1)+pen(m2) κ − n ζ , 1 − 1√ 2 H2 s, f2 + T f1, f2 − 1 + 1√ 2 H2 s, f1 ≤ 1 4 1 − 1√ 2 h H2 s, f2 + H2 s, f1 i + xκ n

    We set b = 1/ √ 2, x = n pen(m1) + pen(m2) + κζ κ , κ = 2 + 11 √ 2 2 √ 2 − 2 , implying 1.5 × (κ − b) = 1 − 1/ √ 2 /4. Hence, with probability at most exp − n pen(m1)+pen(m2) κ − n ζ , 1 − 1√ 2 H2 s, f2 + T f1, f2 − 1 + 1√ 2 H2 s, f1 ≤ 1 4 1 − 1√ 2 h H2 s, f2 + H2 s, f1 i + xκ...

  59. [72]

    We prove 3

    is an easy observation from construction. We prove 3. using induction. It holds trivially for l = 0. Let the statement be true for a given l. Now, let ml+1 be an element of Ml+1. As previously, observe that either ∃ml ∈ Ml+1\Ml such that K ∈ ml, or by Definition 1, K ∈ S(m, k)...

  60. [73]

    (A.1) m ∨ m′ = [ K′∈m′ m ∨ K′ where m ∨ K′ := K′ ∩ K : K ∈ m, K′ ∩ K ̸= Ø

    We first recall the definition of m ∨ m′ from eq. (A.1) m ∨ m′ = [ K′∈m′ m ∨ K′ where m ∨ K′ := K′ ∩ K : K ∈ m, K′ ∩ K ̸= Ø . For any two dyadic partitions m and m′ let Sagree(m, m′) := K : K ∈ m and K ∈ m′ . Observe from Definition 1 that if K′ ∈ m′ and K′ /∈ m, the it is con...

  61. [74]

    |Sagree(m, m′)| ≤ |m| + |m′|,

  62. [75]

    | ∪K∈m∩Sagree (m,m′)c Sdisagree(K, m′)| ≤ |m′|,

  63. [76]

    This gives us the required result

    | ∪K′∈m′∩Sagree (m,m′)c Sdisagree(K′, m)| ≤ |m|. This gives us the required result. B.12 Proposition 19 and proof of its upper bound Proposition 19. Assume the conditions of Theorem 3, and let ˜S⋆ := argmax S∈m(2) ref T (S), l ≤ n, and d1 ≥ 12 . Then,

  64. [77]

    (B.26) Then, R(n) ≤ 4/n 40

    if n (log n)3 ≥ cC−1 p T (S⋆)2 C∆ρ⋆(S⋆) + 1 T (S⋆) log T ˜S⋆ . (B.26) Then, R(n) ≤ 4/n 40

  65. [78]

    Broadly, our strategy is to pose the question of tightness of R(n) in terms of sample complexity, and then follow the usual techniques from [56] to show minimaxity

    if n ≤ C−1 p T (S⋆)2 C∆ρ⋆(S⋆) + 1 T (S⋆) , then R(n) > 1/2, and there exists a controlled Markov chain such that there exists no estimator ˆs satisfying E[h2 n(s, ˆs)] ≤ 1 2(1 + π2) . Broadly, our strategy is to pose the question of tightness of R(n) in terms of sample complex...

  66. [79]

    , d1/3}, the expected return time T as defined in definition 4 satisfies T (S) = 4 5ι2Vol(S)

    For any S ⊂ k(χ) i × k(I) j and any i ∈ {1, . . . , d1/3}, the expected return time T as defined in definition 4 satisfies T (S) = 4 5ι2Vol(S)

  67. [80]

    In particular, cp as written in Assumption 1 is only depends upon ι

    The α-coefficients of this controlled Markov chain satisfy αi,j ≤ (1 − ι)j−i−1. In particular, cp as written in Assumption 1 is only depends upon ι

  68. [81]

    Let Si,j = k(χ) i × k(I) j such that i ∈ {1, . . . , d1/3}. Then, ρ⋆(Si,j) (as defined in Theorem 3) satisfies ρ⋆(Si,j) < 9(1 − ι) 2d1d2 . Simplification of the Sample Complexity We can now substitute upper bounds derived from Proposition 21 in the right hand side of eq. (3.4)...

  69. [82]

    Cp only depends upon cp from Assumption 1, which in turn only depends upon ι for the class of CMC’s we consider (by Proposition 21 part 2). 44

  70. [83]

    C∆ only depends upon ι

  71. [84]

    (√s − p ¯f )2 ¯f + 1 # = 2 ¯f

    Since k(χ) i ×k(I) j create d1d2 uniform cubes of χ×I, for any Si,j = k(χ) i ×k(I) j , Vol(Si,j) = (d1d2)−1. Using the previous facts, and substituting the bounds from Proposition 21 into the right hand side of eq. (3.4) we get C−1 p T (S⋆)2 C−1 p ρ⋆(S⋆) + 1 T (S⋆) ≤ Cι C∆ 16d...

  72. [85]

    n−1X i=0 1 Sr (Xi, ai) #) = [ Sr∈m(2) ref ( − n 2 νn(Sr) ≥ n−1X i=0 1 Sr (Xi, ai) − E

    This completes the proof. B.17 Sketch of Proofs of Corollaries 2 and 3 Proof. Corollary 2 is proved similarly to part 1 of the proof of [10, Proposition 3]. □ To prove Corollary 3, we first use Theorem 1 to get, CE H2(s, ˆs) ≤ inf m∈Ml E H2 (s, Vm) + pen(m) . Now, it is easy t...

  73. [612]

    DOI: 10.1007/1-4020-8066-2_23

    ISBN : 978-1-4020-8066-1. DOI: 10.1007/1-4020-8066-2_23

    doi

  74. [1999]

    ISBN : 978-0-13-656695-3

  75. [2000]

    ISBN : 978-0-12-065202-0

  76. [2024]

    DOI: 10.48550/arXiv.2311.09018

    doi arXiv

  77. [2064]

    DOI: 10.1007/s004400050210

    doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.