True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

arXiv:2605.30532v1 Announce Type: cross Abstract: We study true self-avoiding walk (TSAW) as a mechanism for improving empirical integral estimation via Markov chain Monte Carlo (MCMC). We consider finite-state adaptive sampling dynamics associated with an irreducible Markov kernel P on a finite set, with stationary distribution pi, in which the transition probabilities are penalized according to empirical overuse. Our main result is that the empirical occupation counts L_t(i) and transition counts N_t(i,j) of the resulting TSAW-based walk satisfy [ L_t(i)-tpi_i = O(sqrt{log t}) quadext{and}quad N_t(i,j)-tpi_iP_{ij}=O(sqrt{log t}) qquadext{almost surely} ] for every state i and every edge (i,j) with P_{ij}>0. Consequently, for every bounded function f:Vomathbb R, the error of our integral estimator converges as [ left|frac1tsum_{s=0}^{t-1} f(X_s)-sum_{iin V}pi_i f(i)right| = Oleft(frac{sqrt{log t}}{t}right) qquadext{almost surely}. ] These results show that, in contrast with the usual t^{-1/2} error scaling for empirical averages under standard random-walk-based methods, TSAW-based estimator yields empirical integral errors of order O(sqrt{log t}/t) almost surely, thereby achieving a substantially sharper dependence on the sample size t.

Source: arXiv cs.LG | 2026-06-01