Computation of Strong Solutions to Stochastic Variational Inequalities

Abstract

This paper studies the computation of strong solutions of monotone variational inequalities (VIs) with Lipschitz continuous operators. Building on the idea of accumulative regularization (AR), we develop a general framework for VIs, with particular emphasis on stochastic settings. Under unbiased stochastic oracles with uniformly bounded variance $ \sigma^2$, AR computes an approximate solution with expected operator residual bounded by $\varepsilon$ using at most $ \widetilde{\mathcal{O}}\left(\tfrac{LD_0}{\varepsilon}+\tfrac{ \sigma^2}{\varepsilon^2}(\log\tfrac{LD_0}{\varepsilon})^3\right) $ stochastic oracle calls, where $L$ is the Lipschitz constant and $D_0$ bounds the initial distance to the solution. This substantially improves the existing $\mathcal{O}( \sigma^2/\varepsilon^4)$ complexity for residual reduction and matches the lower bound up to logarithmic factors. For strongly monotone VIs, measured by the distance to the solution, AR achieves the optimal oracle complexity when the strong monotonicity modulus is known. By treating the problem as merely monotone, AR still achieves nearly optimal complexity without knowledge of this modulus. We further introduce a state-dependent noise model applicable to general monotone VIs with potentially nonunique solutions, extending state-dependent noise analysis beyond the strongly monotone setting. We apply these results to policy evaluation in reinforcement learning, where we show that estimators of the projected Bellman operator satisfy our state-dependent noise condition. To the best of our knowledge, the AR framework, the improved complexity under uniformly bounded noise, the state-dependent noise model and its guarantees, the adaptivity to an unknown strong monotonicity modulus, and the improved guarantees for FTD learning are all new in the VI literature.