aiqbench analysis
This paper presents a rigorous counterexample demonstrating that nonuniform update frequencies can prevent convergence in Monte Carlo optimistic policy iteration under scalar stepsize rules. By constructing a specific three-state Markov decision process, the authors prove that anisotropic distortion of residual dynamics creates attracting hybrid periodic orbits where uniform sampling would otherwise ensure radial contraction. This finding establishes critical geometric obstructions for asynchronous reinforcement learning algorithms relying on fixed state-selection probabilities.
Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample
arXiv:2606.15978v1 Announce Type: new 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.
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.
Machine Learning (cs.LG)
arXiv:2606.15978 [cs.LG]
(or arXiv:2606.15978v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.15978 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 214 words
Related coverage
Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates
arXiv · Jun 10, 2026
On the convergence of optimistic policy iteration for stochastic shortest path problem
arXiv · Aug 21, 2026
Iterative GRPO: Batch-Online Policy Iteration for Multi-Turn RL via Single-Turn RLHF
arXiv · Sep 2, 2026
Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic
arXiv · Aug 21, 2026