acceptodds
Under review as a conference paper at ICLR 2027

Nonuniform Monte Carlo OPI Can Cycle

Abstract

Tsitsiklis (2002) proved convergence of discounted Monte Carlo optimistic policy iteration under uniform state selection and left convergence under fixed nonuniform state-selection frequencies open. We answer this question negatively for the scalar-stepsize, unnormalized asynchronous state-value recursion with model-based greedy improvement. For an explicit three-state, two-action MDP, nonuniform updates turn the greedy-policy mean dynamics into a rigorously certified stable six-policy cycle (a hybrid periodic orbit). With a bounded unbiased Monte Carlo return, we prove that, from a nonempty open set of initial conditions, sufficiently small square-summable Robbins–Monro stepsizes keep the original stochastic recursion near this cycle with any prescribed probability 1 − δ; the recursion therefore fails to converge on that event. The obstruction is geometric: uniform sampling produces radial residual contraction, whereas nonuniform scalar updates introduce an anisotropic distortion that can sustain policy switching. As a matched control, inverse-frequency normalization cancels this distortion and recovers a known almost-sure convergence guarantee for every strictly positive sampling law. The cycle persists on a relative open parameter neighborhood, the complete interval certificate succeeds independently at two nearby rational sampling laws, and continuation and paired stochastic experiments delineate the scalar-versus-normalized boundary.

Primary area:
reinforcement learning
Keywords:
optimistic policy iteration, nonuniform sampling, stochastic approximation, convergence, computer-assisted proof

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_Xdh9OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The authors provide a construction to demonstrate that discounted Monte Carlo optimistic policy iteration under nonuniform state sampling can cycle. Then, they prove that the original stochastic recursion also does not convergence with high probability under suitable initialization and stepsize conditions.

Critical strengths
  1. I think the problem is interesting, it's a problem that's been "open" for over 20 years. Although its practical significance may be debated, I think resolving this longstanding question is a worthwhile theoretical contribution.
Critical weaknesses
  1. I think there are issues with the presentation, to the point that it interferes with comprehension at places. For instance, at lines 60-61, it's not immediately clear that aa denotes an action (I admit it is inferable given some thought, but still). Again, in equation (3) (lines 70-71), RtR_t is used without being previously defined, and it again falls to the reader to interpret what it is. Introducing notation before or alongside its first use would make the setup easier to follow. I would encourage a careful pass through the manuscript to address such issues. A minor comment is that the AI-isms are sometimes distractingly heavy (things of the sort "this is X, not Y" etc.)
Questions for authors
  1. What does this result tell us, in that, how does it affect the way we would use Monte Carlo OPI in practice? Given the initialization and stepsize conditions in the nonconvergence theorem, how should practitioners judge the risk of cycling in their own applications?
Reviewer_ggb9OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper resolves a real open problem on optimistic policy iteration. But the scope is very narrow with small scale, with a very specific counter examples (a three-state, two-action MDP) are provided to show that OPI can cycle and does not converge even though we can sample infinitely often. But much of its content seems heavily AI generated and the construction is too murky and illusive to gain insights.

Critical strengths

The paper resolves an open problem on optimistic policy iteration and provided counter examples that show OPI can cycle.

Critical weaknesses
  1. The majority of the content of this paper seems AI-generated and almost unreadable. E.g. starting in line 91, what is the precise definition of mean dynamics, and the derivation of Eq.6-8. How can readers gain anything from it if the paper writing is so out of place? And most statements are plain assertions, without any explanation or justification. E.g. "Its mean multiplier is DW. The scalar algorithm has W= I;" What does this mean? There are many such examples across the entire paper.
  2. Even such results are indeed important; counterexamples in Sec. 3 seem to be constructed out of thin air. The paper starts with presenting a sequence of numerical results without any detail of how they found them.
  3. Finally, this paper merely states there are extreme case of cycling but provides no insight on how to address such issue.
Questions for authors

See limitation.

Reviewer_814DOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies the convergence of Monte Carlo Optimistic Policy Iteration (OPI) under fixed nonuniform state sampling. The authors construct a three-state, two-action MDP in which the mean-field dynamics exhibit an attracting periodic orbit involving six greedy policies. Using computer-assisted interval certificates and a stochastic approximation argument, they establish high-probability nonconvergence of the original stochastic updates under suitable initialization and stepsize conditions. The paper also discusses inverse-frequency normalization as an existing remedy that restores convergence.

Critical strengths
  1. Rigorous counterexample to an open convergence question.

The paper addresses the nonuniform sampling question left open by Tsitsiklis (2002). The construction of an attracting periodic orbit, together with the attempt to extend this result to stochastic nonconvergence, is an interesting theoretical contribution.

  1. Careful mathematical verification.

The use of interval arithmetic and Poincaré return-map analysis goes beyond numerical demonstrations of cycling. The authors also investigate the robustness of the counterexample under perturbations of the sampling distribution.

Critical weaknesses
  1. Limited practical relevance of the considered Monte Carlo update rule.

My main concern is that the counterexample relies on a rather restrictive version of Monte Carlo OPI.

In Eq. (3), the algorithm samples an initial state (I_t), generates a Monte Carlo return, and updates only (J_t(I_t)). However, an episode generally provides return information for multiple visited states. Standard first-visit or every-visit Monte Carlo methods can exploit these additional observations.

Consequently, the nonconvergence result is established for a particular single-coordinate update rule rather than for the broader class of trajectory-based Monte Carlo policy evaluation methods.

Furthermore, the state-selection distribution (q) is assumed fixed and independent of the greedy policy. In ordinary on-policy sampling, state visitation frequencies generally depend on the policy and its induced transitions. The corresponding mean-field dynamics would therefore differ substantially from the fixed-(D) system analyzed here.

These restrictions do not invalidate the counterexample, but they substantially limit its implications for commonly used reinforcement learning algorithms. The paper does not establish whether the same cycling behavior persists under first-visit or every-visit updates, exploratory behavior policies, or policy-dependent state visitation.

This limitation is particularly important because existing methods already provide ways to address nonuniform updates, including the inverse-frequency normalization discussed in the paper itself. The practical significance beyond the specific algorithmic setting remains unclear.

  1. Inconsistency in the stochastic perturbation argument.

There appears to be a mathematical inconsistency in Theorem 2.

Equation (15) defines the perturbed recursion as Yt+1=Yt+γth(Yt)+ξt+1,Y_{t+1}=Y_t+\gamma_t h(Y_t)+\xi_{t+1},

whereas Eq. (16) assumes bounded cumulative perturbations of the form sup⁡m∣∑t<mγtξt+1∣≤η.\sup_m\left|\sum_{t<m}\gamma_t\xi_{t+1}\right|\leq\eta.

The condition controls the scaled perturbations, not the additive perturbations appearing in Eq. (15). As written, it does not prevent arbitrarily large individual perturbations when (\gamma_t) is small.

Appendix D also defines the perturbation increments using (\gamma_t\xi_{t+1}), and the stochastic decomposition in Appendix E appears to omit a corresponding stepsize factor.

The intended recursion presumably contains (+\gamma_t\xi_{t+1}). If so, the statement and proof should be corrected consistently. Since Theorem 2 is used to establish Theorem 1, this issue should be resolved before the main stochastic nonconvergence claim can be fully assessed.

Questions for authors

Q1. Does the counterexample persist under standard first-visit or every-visit Monte Carlo updates?

Could the authors evaluate these update rules on the same three-state MDP? Since the trajectories are already generated, using returns from intermediate visited states would be a natural comparison. This experiment would materially clarify whether the cycling phenomenon is specific to single-coordinate updates or extends to more conventional Monte Carlo methods.

Q2. How does the result relate to commonly used exploration mechanisms?

Would the same nonconvergence phenomenon occur when trajectories are generated using an exploratory behavior policy, or when state visitation frequencies depend on the current policy? If these cases are outside the intended scope, I encourage the authors to emphasize the distinction and narrow the practical implications accordingly.

Q3. Could the authors clarify the perturbation scaling in Theorem 2?

Please reconcile Eqs. (15)–(16), the perturbation definitions in Appendix D, and the stochastic decomposition in Appendix E. Does the proof require the additive noise in Eq. (15) to be multiplied by (\gamma_t)?

Reviewer_APocOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers convergence for a non-uniform variant of so-called Monte-Carlo optimistic policy iteration (OPI). The authors state that while Tsitsiklis (2002) proved that this algorithm converges under uniform state selection and left fixed nonuniform selection open. In this paper the authors apply techniques from computer-verified numerical computation to show that the answer for nonuniform selection is negative. In particular, they exhibit an example of a 3 state 2 action MDP in which the deterministic dynamics has an attracting periodic orbit. From this they infer that, under some specific conditions, the stochastic OPI algorithm fails to converge with arbitrarily high probability. To show this they provide 4 proof obligations and numerically check them using a certified interval arithmetic, which allows them to transfer bounds from numerical computations to theoretical bounds.

Second, they show that the reason for this failure has a geometric intuition: uniform updates produce radial residual contraction, whereas nonuniform scalar updates introduce anisotropic distortion that can sustain policy switching. Finally, they use inverse- frequency normalization to remove this and obtain a known almost-sure convergence guarantee for every strictly positive fixed sampling law, which was already known in the literature. They show experiments illustrating their approach.

Critical strengths

On the positive side, the paper seems to solve an interesting problem. The using of numeric techniques to solve this is rather interesting. The proofs in appendix and code is also provided. Establishing a rigorous attracting cycle and lifting it to stochastic nonconvergence is potentially quite sophisticated. Also, the appendix does contain substantial mathematical arguments, not simply numerical outputs. All this makes the contents valuable.

Critical weaknesses

There are a few severe issues in the presentation, organization, clarity and ability to verify correctness.

  1. The introduction is extremely compressed. The paper does not adequately explain why nonuniform sampling is important, why the convergence question has remained unresolved, or what makes it mathematically difficult or the broader consequences of resolving this question. It effectively relies on the reader accepting that a question left open by Tsitsiklis in 2002 must be important.

While I believe the underlying insights are rather interesting (e.g., stable individual dynamical systems can produce oscillations when switched according to a greedy policy), these are not developed or motivated sufficiently (some of it comes much later, perhaps too late in section 3.1). In short, the introduction is not just short; it does not motivate, contextualize or explain enough.

  1. The organization of the paper is very non-intuitive and the reader is repeatedly asked to understand a result before explaining the construction or machinery that makes the result hold. This is not a problem in general, but in this paper the forward references hamper understanding of the results (e.g., the proof of Proposition 2 invokes conditions C1–C4, but these are explained only afterward in Section 3.2 and Appendix C; the main counterexample, which forms the main result of the paper is in Appendix, etc.)

  2. From a technical point, one issue is that the main negative result stems from a numerical computation. Unfortunately, it is difficult for a non-expert like myself to check a specialized numerical verification implementation to establish whether the central theorem has been proved. While this may not be the authors fault, in a conference like ICLR where the reviewers are given hardly few days for reviewing the paper, this makes it difficult to support the paper strongly.

  3. Finally, it is not clear if resolving this open problem significantly advance our understanding of reinforcement learning, or if it is just a specialized technical result.

Questions for authors
  1. Can the authors provide a simpler, independently checkable certificate of the four conditions C1–C4, rather than requiring reviewers to rely on the correctness of specialized interval-arithmetic verification scripts?

  2. Is there some simpler mathematical construction that demonstrates nonconvergence without requiring computer-assisted verification of a complicated six-policy periodic orbit? It would be good to know if this complexity is intrinsic to the problem or just a consequence of how the counterexample was found. This is important as it would help the reader understand the technical significance of the construction, rather than viewing it as a complicated numerical example that happens to work.

  3. Does resolving this open problem significantly advance our understanding of reinforcement learning, or does it mainly establish that a particular unnormalized update rule can fail?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.