Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces

• URL: http://arxiv.org/abs/2604.22948v1
• Date: Fri, 24 Apr 2026 18:39:50 GMT
• Title: Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces
• Abstract summary: We propose a framework that summarizes history by a running average of score evaluations in $Rd$, where $d$ is the dimension of the score and state representation.<n>This history is converted into a surrogate target through an exponential score tilt, indexed with $$ that represents the strength of repellence in controlling the magnitude of the history-based repulsion.<n>Experiments on continuous targets and discrete energy-based models demonstrate improved estimator variance and mode coverage, while retaining $O(d)$ memory usage and modest per-it overhead.
• Score: 48.37754141688874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: History-dependent sampling can reduce long-run Monte Carlo variance by discouraging redundant revisits, but existing schemes typically encode history through empirical measure on finite state spaces, which is infeasible in high-dimensional discrete configuration spaces or ill-posed in continuous domains. We propose Score-Repellent Monte Carlo (SRMC) framework that summarizes trajectory history by a running average of score evaluations in $R^d$, where $d$ is the dimension of the score and state representation. This history is converted into a surrogate target through an exponential score tilt, indexed with $α$ that represents the strength of repellence in controlling the magnitude of the history-based repulsion. The surrogate family is normalization-free in the standard MCMC sense, yielding a generic wrapper: at each iteration, any base kernel targeting $π$ can instead be run on the current surrogate $π_{θ_n}$ while the history is updated online. We analyze the coupled evolution of the history recursion and Monte Carlo estimators using stochastic approximation with controlled Markovian noise, establishing almost sure convergence and a joint central limit theorem. We further identify regimes in which the asymptotic covariance decreases as $α$ increases, with scaling $O(1/α)$, extending the near-zero-variance effect of finite-state history-dependent samplers to general state spaces with constant memory. Experiments on continuous targets and discrete energy-based models demonstrate improved estimator variance and mode coverage, while retaining $O(d)$ memory usage and modest per-iteration overhead.

Related papers

• Data Driven Block Replacement Scheduling [0.0]
  We develop data-driven algorithms for maintaining $N$ independent identical machines under a textitblock replacement policy<n>The goal is to learn the cost-minimizing interval $k*$ from operational data when the lifetime distribution is unknown.<n>A complementary Kaplan--Meier renewal algorithm estimates the lifetime distribution noncensorally from censored data, achieving almost-sure policy consistency and empirically near-zero incremental regret at long horizons.
  arXiv  Detail & Related papers  (2026-07-16T17:31:15Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• $κ$-Explorer: A Unified Framework for Active Model Estimation in MDPs [20.944349513772067]
  We introduce a parameterized family of objective functions $U_$ that explicitly incorporate intrinsic estimation complexity and visitation frequency.<n>We propose $$-Explorer, an active exploration algorithm that performs Frank-Wolfe-style optimization over state-action occupancy measures.<n>Experiments on benchmark MDPs demonstrate that $$-Explorer provides superior performance compared to existing exploration strategies.
  arXiv  Detail & Related papers  (2026-02-23T22:56:32Z)
• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
  We establish an optimal sample complexity of $O(-2)$ for obtaining an $$-optimal global policy using a single-timescale actor-critic (AC) algorithm.<n>These mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.
  arXiv  Detail & Related papers  (2026-02-02T00:35:42Z)
• Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
  We study finite-state Markov chains with $n$ states and transition matrix $P$.<n>We show that all non-decaying modes are captured by a real peripheral invariant subspace $mathcalK(P)$, and that the induced operator on the quotient space $mathbbRn/mathcalK(P) is strictly contractive, yielding a unique quotient solution.
  arXiv  Detail & Related papers  (2026-01-31T02:57:01Z)
• SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
  gradient descent (SGD) is shown to accommodate both independent and dependent information under a broad class of stepsize schedules and exploration rate schemes.<n>We show that SGD simultaneously achieves statistically optimal estimation error and regret, extending and improving existing results.<n>For online sparse regression, we develop a new SGD-based algorithm that uses only $d$ units of storage and requires $O(d)$ flops per iteration.
  arXiv  Detail & Related papers  (2026-01-04T04:52:11Z)
• Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs [7.434126318858966]
  We propose a history-driven target (HDT) framework in Markov Chain Monte Carlo (MCMC) to improve any random walk algorithm on discrete state spaces.<n>We show that HDT preserves lightweight implementation by requiring only local information between the current and proposed states.<n>Experiments in graph sampling demonstrate consistent performance gains, and a memory-efficient Least Recently Used (LRU) cache ensures scalability to large general graphs.
  arXiv  Detail & Related papers  (2025-05-23T18:46:10Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Online covariance estimation for stochastic gradient descent under Markovian sampling [20.02012768403544]
  Convergence rates of order $Obig(sqrtd,n-1/8(log n)1/4big)$ are established under state-dependent and state-independent Markovian sampling. Our method is applied to the strategic classification with logistic regression, where adversaries adaptively modify features during training to affect target class classification.
  arXiv  Detail & Related papers  (2023-08-03T00:21:30Z)
• Exponential Family Model-Based Reinforcement Learning via Score Matching [97.31477125728844]
  We propose an optimistic model-based algorithm, dubbed SMRL, for finitehorizon episodic reinforcement learning (RL) SMRL uses score matching, an unnormalized density estimation technique that enables efficient estimation of the model parameter by ridge regression.
  arXiv  Detail & Related papers  (2021-12-28T15:51:07Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.