Researchers Prove Convergence of Monte Carlo Optimistic Policy Iteration Under Relaxed Conditions

A new preprint posted to arXiv addresses a long-standing open question in reinforcement learning theory: under what conditions does Monte Carlo Optimistic Policy Iteration (MC-O-PI) provably converge to an optimal policy when the environment model is unknown. The prior state of the art required episodes to be initialized uniformly over all state-action pairs, which is infeasible when the state space is large or not fully enumerable. The authors prove that convergence is guaranteed even when uniformity is required only over actions within each state, allowing states themselves to be visited at arbitrary frequencies. The proof introduces a novel analytical approach, departing from the classical commutativity argument of Tsitsiklis, which breaks down under non-uniform state update frequencies. Instead, the authors establish that the algorithm's mean-field dynamics produce monotonically improving policies under the relaxed condition, and then use an extended lock-in argument from the stability-ODE method to show that stochastic noise cannot persistently obstruct this improvement. The authors suggest this framework may generalize to the broader class of optimistic policy-iteration algorithms. The work is a theoretical contribution and has not yet undergone formal peer review.