- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies performative reinforcement learning, in which the deployed policy affects the environment, and distinguishes local stability from global stability for mixtures of policies. The authors introduce an algorithm based on Hedge that achieves local stability under a possibly discontinuous environment response. They also use a counterexample to show that global stability may not be achievable. Under the bounded transition range assumption, the authors further provide an approximate global stability guarantee. The analysis is also extended to n-player Markov games. The results are supported by theoretical proofs, counterexamples, and finite-sample analysis.
Critical strengths
-
The authors provide local stability guarantees for mixtures of policies without requiring the environment response to be continuous. This relaxes the sensitivity assumptions in previous performative RL work and extends the analysis to environments with discontinuous responses.
-
The authors use a counterexample to separate local stability from global stability and provide approximate global stability guarantees under bounded transition range. These results help readers understand the capabilities and limitations of policy mixtures in RL and the conditions needed for stronger stability guarantees.
Critical weaknesses
The finite-sample guarantees in the appendix need correction. The step sizes in Theorem 7 and its proof differ by a factor of . Theorem 8 also appears to omit an optimization error term independent of batch size. Consider a fixed environment with one state, two actions, and deterministic rewards of 0 and 1. With , , , and the specified step size, all conditions are satisfied, but the local stability gap is approximately , exceeding the stated bound of . These issues appear fixable without changing the main results.
Questions for authors
The lower bound in Theorem 6 requires , where is the total number of trajectories. Could the authors explain how this finite-sample bound supports the claim of an unavoidable error floor linear in as the sample size goes to infinity with the problem size fixed?
If the authors can resolve the finite-sample issues and clarify the asymptotic lower-bound claim, I would consider raising my rating to 4.
4 comments
Thank you for the new counterexample. It answers my question about the linear error floor. For Theorem 8, should the simplified bound retain the optimization term from the preceding inequality?
Follow up
Dear Reviewer,
Thank you for the follow-up! We are glad to see that the new counter-example has answered your question.
Regarding theorem 8 (theorem 10 in the updated manuscript, line 1216) we are not sure which term you are referring as the optimization term. The proof upper bounds the local stability gap by two terms : term (I) is similar to the loss from exact gradient and term (II) is the loss due to bias in gradient estimation (). The term (II) is bounded by by Martingale concentration inequalities.
If you could provide a bit more context regarding the optimization term you are referring to, we would be happy to clarify.
Thank you for the responses and the new counterexample. My main question about the linear error floor has been addressed. I will maintain my rating of weak acceptance, with a minor concern remaining about the simplified bound in Theorem 8.
Rebuttal
Dear Reviewer 1H9y,
Thank you for your feedback and further questions. Below we provide our response. We would be happy to answer any further questions you might have.
Thank you for pointing out the errors. Both are typos. For theorem 7 (original version), the step size η does not include the S factor and the proof establishes that. The theorem statement has a typo. For theorem 8 (original version), the batch-size independent terms are included, however the local stability gap included a factor of A which should not be present. Both typos have been corrected in the recently uploaded version.
This is an important question! We have managed to find a new counter-example (lines 374-394) that establishes an unconditional lower bound of Ω(γϵP/(1−γ)) on the achievable global stability gap. This lower bound doesn't impose any restriction on the number of samples.
Our previous unconditional lower bound on global stability was Ω(ϵP2) (instance of Lemma 4) and in order to obtain a linear floor, we imposed the restriction on the number of samples. However, this is not necessary as the new counter-example shows. We probably failed to find the example earlier because we were mainly searching for counter-examples in the family of survival chain instances and the new example goes beyond that family.
Best, Authors