Markov Chains and Stochastic Stability

By Sean P. Meyn, Richard L. Tweedie. 1993

Subfields: Probabilistic & Bayesian Methods, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

In Statistical Learning Theory

Citations in the corpus

Batch Stationary Distribution Estimation (2020, background): “For ergodic Markov chains, one has | 2 | 1 (Meyn et al., 2009, Chap 20).”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, background): “For γ = 1, in the discrete case, the fixedpoint exists as long as T is ergodic; in the continuous case, the conditions for fixed-point existence become more complicated (Meyn & Tweedie, 2012) and beyond the scope of this paper.”
Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, background): “(s t;a t) p(t) b (s t;a t) ; w t(s t) = p(t) e (s t) p(t) b (s t) : For an MDP, the variables C ˇ= f(s t;a t;r t) : t0g generated by P ˇ form a Markov chain. When this is a Harris ergodic chain (see Meyn and Tweedie, 2009), then we have almost surely that, 1 T+ 1 XT t=0 r t!E p(1) ˇ [r]; c T( ) XT t”
Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shift (2019, background): “This distribution is unique when P defines a Markov chain with a single recurrent class (called a unichain, Meyn and Tweedie 2012).”
On Convergence of Emphatic Temporal-Difference Learning (2015, background): “X, Theorem 2.1); see also (Meyn and Tweedie, 2009, Theorem 17.1.2)].”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, neutral): “The non-averaged iterate sequence ( θ n ) is a homogeneous Markov chain; under appropriate technical conditions, this Markov chain has a unique stationary (invariant) distribution and the sequence of iterates ( θ n ) converges in distribution to this invariant distribution; see [17, Chapter 17].”
Least Squares Temporal Difference Methods: An Analysis under General Conditions (2012, methodology): “1(i) is a stochastic Lyapunov function for the Markov process {(it, Zt)} and has powerful implications on the behavior of the process (see [23, 21]).”
Robustness and generalization (2010, background): “Definition 4 A Markov chain {zi}∞i=1 on a state space Z is a Doeblin chain (with α and T ) if there exists a probability measure ϕ on Z , α > 0, an integer T ≥ 1 such that Pr(zT ∈ H |z0 = z) ≥ αϕ(H); ∀ measurable H ⊆ Z; ∀z ∈ Z.”
Exact finite approximations of average-cost countable Markov decision processes (2007, positive): “ leaving Z. Let the random times ν and ν 0 be as in the sentence that precedes Theorem 3.1. Under the recurrence assumption the limit of the average cost ﬂow exists. It follows from Theorem 17.2.1 of [MT] that under σ the process pair {xk,ak} possesses an invariant probability measure which we denot”
Basic properties of strong mixing conditions. A survey and some open questions (2005, background): “[112].”
Regularization in reinforcement learning (2011, background): “This behavior is obscure in previous results such as Munos [2007]; Antos et al.”
Regular variation of GARCH processes (2002, methodology): “The strong mixing condition The Markov chain (Xn) satis2es a mixing condition under quite general conditions as for example provided in Meyn and Tweedie (1993).”
Bandit Algorithms (2020, background): “For a little more history on this see the preface of the book by Meyn and Tweedie [2012].”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, background): “First, standard measures of eﬃciency of Markovian kernels, like the total variation convergence rate (c.f. Meyn and Tweedie (2009); Roberts and Rosenthal (2004)), L 2 ( π ) spectral gap (Diaconis and Stroock (1991); Roberts (1996); Saloﬀ-Coste (1997); Levin et al. (2009)) or asymptotic variance…”
Asymptotic operating characteristics of an optimal change point detection in hidden Markov models (2004, background): “2 of Meyn and Tweedie (1993), the solution ∆r satisfies ∆r ≤Rr(V (x) + 1) for r = 1,2.”
Music recommendation and discovery in the long tail (2008, methodology): “To simulate a user surfing the recommendation network, we apply a Markovian stochastic process (Meyn and Tweedie, 1993).”
Equivalence of exponential ergodicity and L2-exponential convergence for Markov chains (2000, background): “About the convergence in total variation, there is a great deal of publications, see for instance Down et al. (1995), Lund et al. (1996), Meyn and Tweedie (1993) and Nummelin (1984) and references within.”