Research map / Reinforcement learning / Policy gradient and actor-critic

Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts

NeurIPS 2026 · Reinforcement learning › Policy gradient and actor-critic · approach: Model-based RL with guarantees · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Constructs counterexamples showing tabular initial-visit and first-visit Monte Carlo Exploring Starts can converge to suboptimal solutions, and proves IV MCES converges to optimality when learning rates are scaled by 1/g_k(a|s).

Problem

Whether tabular Monte Carlo Exploring Starts (MCES) converges to optimal policies is a long-standing open question; prior counterexamples relied on heavily non-greedy-biased sampling.

Approach

Shows IV/SA MCES can get stuck at suboptimal boundary points even when greedy actions are updated at least as often; fixes IV MCES by scaling per-state learning rates by 1/g_k(a|s) (inverse conditional action-sampling probability), requiring only within-state action probabilities, and analyses convergence via the policy sequence. Also builds a 13-state cyclic MDP where FV/SA MCES appears to conver

Key results

• In a 3-state MDP with sampling strategy, 99.6% of IV/SA MCES solutions converge to a boundary point q ≈ 1.615 where q(s,a*)=q(s,ā), even though greedy actions are sampled at least as often.
• The proposed IV MCES with learning rates α_k/g_k(a|s) is proven to converge almost surely to q_π* under scalar Robbins-Monro, tie-breaking and strict exploring starts assumptions.
• In a 13-state cyclic MDP (γ=0.9999), FV/SA MCES simulations with 40,000 runs for 10^9 steps show escape proportion ~(2200/M)^5.4, with all runs from M=10^5 remaining trapped at 10^12 steps.

Surprising findings

• IV/SA MCES can converge to suboptimal stable boundary points even when the greedy action is updated at least as frequently as non-greedy actions in every state.
• Sample-average first-visit MCES appears to remain trapped in suboptimal basins for all simulated runs surviving 10^9 steps, even up to 10^12 steps.

Limitations

• FV counterexample is supported by simulation and mean-field analysis rather than a full proof of non-convergence.
• IV convergence proof requires strong assumptions: scalar non-increasing learning rates, uniform tie-breaking, and strict exploring starts.
• Applicability to function approximation is not demonstrated empirically; the modification is only analysed in tabular form.

Experimental setup

Metrics: fraction of runs converging to suboptimal point convergence to q_pi* in simulation

Baselines: IV MCES with sample-average updates FV MCES with sample-average updates uniform-sampling MCES with 1/sigma_k scaling

Builds on: Monte Carlo Exploring Starts Bertsekas and Tsitsiklis counterexamples Tsitsiklis asynchronous stochastic approximation theorem Monte Carlo off-policy/on-policy control (Sutton and Barto)

Closest papers by meaning

• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo (ICLR 2024 · similarity 0.88)
• Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
• Bayesian Exploration Networks (ICML 2024 · similarity 0.88)
• Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.88)
• Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.88)
• Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles (ICML 2024 · similarity 0.87)