Counterexamples and Fix for Monte Carlo Exploring Starts

The asymptotic behavior of Monte Carlo Exploring Starts (MCES) in reinforcement learning has long been an unresolved question, even for tabular settings. This research investigates the convergence properties of tabular MCES and constructs specific examples where the algorithm fails to converge to optimal solutions, instead settling on suboptimal ones. The paper provides new counterexamples for both initial-visit and first-visit MCES. It shows that stable suboptimal solutions can exist for initial-visit MCES, even when greedy actions are updated more frequently than non-greedy ones. Crucially, the study also offers a modification that restores convergence to optimality for the initial-visit case. This fix involves scaling learning rates inversely to update frequencies on a state-by-state basis. Unlike previous uniformization methods, this modification is applicable to large-scale problems where value functions are approximated. These findings largely resolve a fundamental open problem, emphasizing that exploring starts alone do not guarantee optimality and that the choice of learning rates and the balance between exploration and exploitation are critical.