Publications

Low-rank structure is a common implicit assumption in many modern reinforcement learning (RL) algorithms. For instance, reward-free and goal-conditioned RL methods often presume that the successor measure admits a low-rank representation. In this work, we challenge this assumption by first remarking that the successor measure itself is not low-rank. Instead, we demonstrate that a low-rank structure naturally emerges in the shifted successor measure, which captures the system dynamics after bypassing a few initial transitions. We provide finite-sample performance guarantees for the entry-wise estimation of a low-rank approximation of the shifted successor measure from sampled entries. Our analysis reveals that both the approximation and estimation errors are primarily governed by the so-called spectral recoverability of the corresponding matrix. To bound this parameter, we derive a new class of functional inequalities for Markov chains that we call Type II Poincaré inequalities and from which we can quantify the amount of shift needed for effective low-rank approximation and estimation. This analysis shows in particular that the required shift depends on decay of the high-order singular values of the shifted successor measure and is hence typically small in practice. Additionally, we establish a connection between the necessary shift and the local mixing properties of the underlying dynamical system, which provides a natural way of selecting the shift. Finally, we validate our theoretical findings with experiments, and demonstrate that shifting the successor measure indeed leads to improved performance in goal-conditioned RL.

We investigate the mixing properties of a model of reversible Markov chains in random environment, which notably contains the simple random walk on the superposition of a deterministic graph and a second graph whose vertex set has been permuted uniformly at random. It generalizes in particular a result of Hermon, Sly and Sousi, who proved the cutoff phenomenon at entropic time for the simple random walk on a graph with an added uniform matching. Under mild assumptions on the base Markov chains, we prove that with high probability the resulting chain exhibits the cutoff phenomenon at entropic time \log n / h, h being some constant related to the entropy of the chain. We note that the results presented here are the consequence of a work conducted for a more general model that does not assume reversibility, which will be the object of a companion paper. Thus, most of our proofs do not actually require reversibility, which constitutes an important technical contribution. Finally, our argument relies on a novel concentration result for "low-degree" functions on the symmetric group, established specifically for our purpose but which could be of independent interest.

We investigate the mixing properties of a finite Markov chain in random environment defined as a mixture of a deterministic chain and a chain whose state space has been permuted uniformly at random. This work is the counterpart of a companion paper where we focused on a reversible model, which allowed for a few simplifications in the proof. We consider here the general case. Under mild assumptions on the base Markov chains, we prove that with high probability the resulting chain exhibits the cutoff phenomenon at entropic time \log n / h, h being some constant related to the entropy of the chain, when the chain is started from a typical state. However contrary to the reversible case uniform cutoff at entropic time does not hold, as we provide an example where the worst-case mixing time has at least polylogarithmic order. We also provide a polylogarithmic upper bound on the worst-case mixing time, which in fact plays a crucial role in deriving the main result for typical states. Incidentally, our proof gives a clear picture of when to expect uniform cutoff at entropic time: it appears as the consequence of a uniform transience property for the covering Markov chain used throughout the proof, which lies on an infinite state space and projects back onto the initial chain.

In operator algebra, the linearization trick is a technique that reduces the study of a non-commutative polynomial evaluated at elements of an algebra A to the study of a polynomial of degree one, evaluated on the enlarged algebra A ⊗M_r(C), for some integer r. We introduce a new instance of the linearization trick that is tailored to study a finitely supported random walk G by studying instead a nearest-neighbour coloured random walk on G x {1, ... , r }, which is much simpler to analyze. As an application, we extend well-known results for nearest-neighbour walks on free groups and free products of finite groups to coloured random walks, thus showing how one can obtain new results for finitely supported random walks, namely an explicit description of the harmonic measure and formulas for the entropy and drift.

Given integers d ≥2, n ≥1, we consider affine random walks on torii (Z/nZ)^d defined as X_t+1 = A X_t + B_t \mod n, where A ∈GL_d(Z) is an invertible matrix with integer entries and (B_t)_t ≥0 is a sequence of iid random increments on Z^d. We show that when A has no eigenvalues of modulus 1, this random walk mixes in O(log n log log n) steps as n →∞, and mixes actually in O(log n) steps only for almost all n. These results are similar to those of Chung et al. (Ann Probab 15(3):1148–1165, 1987) on the so-called Chung–Diaconis–Graham process, which corresponds to the case d=1. Our proof is based on the initial arguments of Chung, Diaconis and Graham, and relies extensively on the properties of the dynamical system x →A^⊤ x on the continuous torus R^d / Z^d. Having no eigenvalue of modulus one makes this dynamical system a hyperbolic toral automorphism, a typical example of a chaotic system known to have a rich behaviour. As such our proof sheds new light on the speed-up gained by applying a deterministic map to a Markov chain.