Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample

• URL: http://arxiv.org/abs/2606.15978v1
• Date: Sun, 14 Jun 2026 19:04:37 GMT
• Title: Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample
• Abstract summary: Tsitsiklis proved convergence of Monte Carlo optimistic policy iteration under a uniform update structure.<n>We identify nonuniform update frequencies as a delicate obstruction.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tsitsiklis proved convergence of Monte Carlo optimistic policy iteration under a uniform update structure and identified nonuniform update frequencies as a delicate obstruction. We give a certified negative answer for the natural scalar-stepsize, unnormalized asynchronous state-value recursion with fixed nonuniform state-selection probabilities. In a three-state, two-action discounted MDP, the nonuniform update frequencies induce a diagonally scaled greedy-policy mean field with a certified nonconstant attracting hybrid periodic orbit. With a bounded unbiased geometric-horizon estimator and Robbins--Monro stepsizes, the original stochastic recursion remains trapped near the cycle with positive probability and therefore fails to converge. The example pinpoints a geometric obstruction: uniform sampling gives radial residual contraction, whereas scalar nonuniform sampling anisotropically distorts the residual dynamics and can generate switched attracting cycles.

Related papers

• Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic [3.756550107432323]
  entropy regularization is widely used to stabilize and accelerate Natural Policy Gradient methods.<n>We analyze a single-loop, entropy-regularized Natural Actor-Critic.<n>By training an uncentered critic, our critic tracking can remain stable even as the training policy approaches determinism.
  arXiv  Detail & Related papers  (2026-08-20T03:08:33Z)
• Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework [13.105625785987321]
  Unit (UE) is a common assumption in saddle avoidance, but it oversimplifies the actual noise structure.<n>In finite-sum problems, the gradient noise may lie in a low-dimensional, data-dependent subspace.<n>We prove an almost sure avoidance theorem for recursions without UE.
  arXiv  Detail & Related papers  (2026-08-04T01:34:36Z)
• Structure-Aware Variance Reduction for Unbiased Randomized Hamiltonian Simulation [0.0]
  Hamiltonian simulation methods are often governed by a trade-off between systematic bias and sampling overhead.<n>We show how classical variance-reduction techniques can be applied to such methods without changing their mean channel.
  arXiv  Detail & Related papers  (2026-06-22T16:17:55Z)
• A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling [7.035974899001363]
  We derive a finite-round upper-tail guarantee from a coupled-neighbor recursion stability and a weighted concentration step.<n>A one-dimensional counterexample shows why a gap, smoothing, or regularity condition is necessary.
  arXiv  Detail & Related papers  (2026-06-01T05:36:26Z)
• Geometric and Topological Obstructions to Hermitianization in Quasi-Hermitian Quantum Systems [2.679171884680826]
  Quasi-Hermitian quantum systems can be mapped to equivalent Hermitian systems via a similarity transformation.<n>We identify two distinct obstructions: geometric obstructions arising from the curvature of a metric-induced connection, and topological obstructions originating from non-trivial holonomies.<n>Our results establish a geometric and topological foundation for the Hermitianization of quasi-Hermitian systems.
  arXiv  Detail & Related papers  (2026-05-06T18:06:59Z)
• 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)
• Asymmetric regularization mechanism for GAN training with Variational Inequalities [1.529943343419486]
  We formulate the training of generative adversarial networks (GANs) as a Nash equilibrium seeking problem.<n>We propose an asymmetric regularization mechanism based on the classic Tikhonov step and on a novel zero-centered gradient penalty.
  arXiv  Detail & Related papers  (2026-01-20T12:50:18Z)
• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  In this work we explore a family of expressive and interpretable distributions over circle-valued random functions.<n>For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Gibbs sampling.<n>We present experiments applying this model to the prediction of wind directions and the percentage of the running gait cycle as a function of joint angles.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Metropolis Monte Carlo sampling: convergence, localization transition and optimality [0.0]
  We show that deviations from the target steady-state distribution can feature a localization transition. We argue that the relaxation before and after the localisation transition is respectively limited by diffusion and rejection rates.
  arXiv  Detail & Related papers  (2022-07-21T14:06:04Z)
• Non-Hermitian $C_{NH} = 2$ Chern insulator protected by generalized rotational symmetry [85.36456486475119]
  A non-Hermitian system is protected by the generalized rotational symmetry $H+=UHU+$ of the system. Our finding paves the way towards novel non-Hermitian topological systems characterized by large values of topological invariants.
  arXiv  Detail & Related papers  (2021-11-24T15:50:22Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.