acceptodds
Under review as a conference paper at ICLR 2027

Identifiability and exploration in performative reinforcement learning

Abstract

In performative reinforcement learning, deploying a policy changes the environment it acts in. The usual algorithms retrain on the environment the current policy induces and repeat, converging to a performatively stable policy. They do not explore, so their data come only from the state–action pairs their own policies keep visiting, and we ask what those data can identify. For performative MDPs whose response is an exponential tilt of a base model, the answer is exact in the limit: the data identify the response directions revealed by the pairs that stay visited, and nothing else. The directions left over form a blind subspace that can be computed before any data arrive, from a candidate policy and the known response design. This separates two cases. When no blind direction can change which policy is best, retraining loses coverage but not identifiability, as on the grid-world benchmark used in this literature. When one can, retraining can settle on a policy that its own data cannot refute, and a learner whose cumulative exposure to the revealing pairs stays bounded has linear regret. We analyse three remedies with regret guarantees: optimism and posterior sampling, which explore only among plausibly optimal policies yet suffice once rewards are observed, and minimal probing, which occasionally plays a cheap set of revealing pairs and needs only the planner that retraining already uses. Where the test fails, probing cuts the regret of certainty equivalence by 91% on generated environments and by 61% in a simulated battery charger whose lithium plating is hidden below an onset, with no detected difference from optimism at a quarter of its computation. In environments drawn without a blind spot built in, the failure is common above a dimension threshold and absent below it.

Primary area:
reinforcement learning
Keywords:
Performative Reinforcement Learning, A-Optimal Design, Exploration

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_JqfKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the performative reinforcement learning where deploying the policy can change the environment. The traditional repeated-retraining algorithms can converge to a stable policy while the visited state-action pairs are constrained to the frequent-visited space and the remaining directions form a blind subspace. If the blind space can change the optimal policy, then the converging policy derived from the traditional repeated-retraining algorithm is suboptimal. This paper propose three methods to deal with the sub-optimality: optimism, posterior sampling, and structure-directed probes. The generated experiments on synthetic data show that the proposed methods reduce the regret.

Critical strengths

The paper studies an important problem in performative reinforcement learning, where deploying a policy changes the environment. his policy-environment feedback can cause standard repeated-retraining or certainty-equivalent methods to converge to a stable but sub-optimal policy. Under a structured trigger model, this paper identify the blind space caused by limited observability. This paper also proposes different methods such as optimism, posterior sampling and structured probing to deal with the sub-optimality trap with theoretical guarantees.

Critical weaknesses
  1. The performative MDP model in eq. 1 is kind of restrictive. It assumes the transition dynamis is composed by fixed parameters B, W, and \phi, while only \epsilon is unknown. I'm not sure if this holds in general settings. It would strengthen the paper to provide further justification for this model in realistic applications and to study the robustness of the proposed methods under misspecified or estimated response structures. 2.The main empirical comparisons are conducted on relatively small tabular MDPs (6 states and 3 actions). Can the exploration methdos scale up to larger state/action space and beyond the tabular setting? Also, current settings are synthetic dataset, and more realistic benchmarks are missed.
Questions for authors

Please refer to weakness part.

1 comment

Dear Reviewer JqfK,

Thank you again for your review. As the discussion period nears its end, we wanted to check whether our response and revision address your concerns. In brief:

Response design: misspecified, incomplete and learned designs (Apps. P and S), and a new response outside the exponential tilt (App. T). Probing keeps its advantage over certainty equivalence in all of them. Scale: learners at up to 64 states, the size of the standard benchmark of Mandal et al. (2023) (App. Q). Certainty equivalence never recovers the decision-relevant action, while probing always does. Realism: the battery instance is now performative (§5.3, App. C).

All changes are marked in blue in the revised PDF. If any point remains unclear, we would be glad to clarify it before the discussion closes. If our response resolves your concerns, we would be grateful if you would consider reflecting this in your assessment.

Best regards, The authors

Reviewer_zSH1OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In Performative Reinforcement Learning, deploying a policy changes the environment’s transitions and rewards. Retraining may converge while abandoning actions that reveal important environmental effects which are often captured by the performative sensitivity parameters. This paper asks when the remaining observations identify enough of those effects to support good decisions. Its theory characterizes blind parameter directions, establishes regret consequences when unresolved uncertainty changes the optimal decision, and analyzes exploration remedies. Experiments examine both harmful blindness and benign coverage loss, showing when targeted probing improves learning. The central message is that losing coverage need not prevent identification, but losing decision-relevant information can sustain suboptimal behavior.

Critical strengths
  • The paper identifies an important problem and distinguishes coverage loss from decision-relevant information loss.
  • The theoretical analysis is substantial and carefully developed, connecting information geometry, adaptive deployments, regret, and exploration under explicit assumptions.
  • The probing approach provides a computationally attractive remedy.
  • The experiments include benign cases and negative findings, with transparent discussion of practical limitations.
Critical weaknesses
  1. Modeling rationale. The computational benefits of exponential-tilt transitions and affine rewards are explained, but their modeling interpretation is less clear. In particular, the justification for treating the response shapes and policy triggers as known is limited, making the setting’s practical applicability difficult to assess. For reference, [1] employs a simpler version of the reward and transition model to simplify their theoretical analysis as well but in this context it needs further justification.

  2. Clarity of the objective. The introduction does not clearly separate incomplete learning from the stability-optimality gap. Figure 1 is not discussed in the main text, leaving an opportunity to explain the central failure mechanism unused.

  3. Theoretical presentation. Statements such as Theorem 2 introduce several definitions and convergence conditions before establishing the underlying intuition. This makes the main identification message harder to follow than necessary.

  4. Connection between theory and experiments. The battery example does not clearly distinguish performative environmental change from ordinary action-dependent degradation. Separately, the strongest probing results use heuristic stopping outside the certified guarantee, limiting their direct connection to the theory.

[1] Basu, D., Das, U., Driss, B. and Mukherjee, U. (2026) 'Performative Policy Gradient: Optimality in Performative Reinforcement Learning', in Proceedings of the 43rd International Conference on Machine Learning. PMLR, vol. 306, pp. 6939–6983. Available at: https://proceedings.mlr.press/v306/basu26a.html.

Questions for authors
  • Could the authors explain the physical or behavioral interpretation of the response parameterisation addressing W1 and when its known components would be available?
  • A concrete example, linked to Figure 1 could clarify what the learner fails to identify and how that changes its decision?
  • Can Theorem 2 first be presented for an eventually fixed policy, with the general converging-policy statement deferred to the appendix?
  • What specifically makes the battery example performative? Could the experimental claims also distinguish more explicitly between certified probing and heuristic stopping?
Reviewer_NRgEOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper studies how repeated retraining in performative RL can limit what a learner knows about the environment. For an exponential tilt model with known response structure, the authors characterize the parameter directions that receive only bounded information as policies converge. They show that this can lead to suboptimal policies when the missing information matters for decision making. The paper also proves a linear regret lower bound for insufficient exploration and provides regret guarantees for optimism, posterior sampling, and a proposed minimal probing method. Experiments on synthetic MDPs compare these approaches, while a grid world benchmark and a battery charging simulator illustrate the effects of limited exploration.

Critical strengths
  1. The Fisher information analysis identifies which response directions a converging policy can no longer learn. This goes beyond simply checking state-action coverage. In the grid world benchmark, for example, retraining stops visiting many pairs, but the remaining unidentified direction does not affect the optimal policy.
  2. The regret analysis shows why continued exploration may be necessary even after retraining has settled on a policy. The authors establish a linear regret lower bound under bounded exposure to relevant parameter directions and provide sublinear regret guarantees for optimism, posterior sampling, and minimal probing. In the synthetic experiments, minimal probing with heuristic stopping achieves regret close to optimism and IDS while requiring less computation.
Critical weaknesses
  1. Two results in the appendices need further justification. In Proposition 7 (Appendix L.2), the construction does not establish that M′M' belongs to the original response class. The proof gives weaker Lipschitz and transition probability bounds than the statement requires. It also uses a limiting policy without assuming convergence. In Proposition 9 (Appendix M), the dimension result of Corollary 2 is extended without ensuring that the trigger Jacobian preserves rank. Proposition 8 establishes this equality when JJ is invertible, so an additional argument or assumption appears necessary.
  2. The theoretical guarantees are difficult to relate to the experimental results. The certified stopping rule never activates within the tested horizons, so the experiments use a heuristic threshold without the same guarantee. The theoretical burn-in for minimal probing is also far beyond these horizons. While the experiments show promising results, they do not establish how useful the finite sample bounds are in practice. The regret guarantees also compare against the best deterministic policy, although the authors report instances where stochastic policies achieve higher value.
Questions for authors
  1. In Proposition 7, the proof only establishes weaker Lipschitz and transition probability bounds than the statement requires. Can the result be proved under the original assumptions? The argument also refers to a limiting policy without assuming convergence.
  2. Proposition 9 extends the dimension result of Corollary 2, but Proposition 8 only establishes the dimension equality when the trigger Jacobian is invertible. Does Proposition 9 need the same assumption?
  3. The certified stopping rule never triggers in the experiments. How was the heuristic threshold chosen, and how much do the results change with different threshold values?
4 comments

Dear Reviewer NRgE,

Thank you again for your careful review of the appendices. As the discussion period nears its end, we wanted to check whether our response resolves your concerns. In brief:

Prop. 7 now uses a constant reward shift that stays in the original class, with linear regret under a stated value-gap condition (App. L.2). Prop. 9 is now stated as a lower bound, with equality when J is invertible (App. M, Lemma 10). Stopping and comparator: the threshold choice is documented in App. R, the burn-in is corrected in App. F, and the comparator is discussed in Remark 1.

All changes are marked in blue in the revised PDF. If any point remains unclear, we would be glad to clarify it before the discussion closes. If our response resolves your concerns, we would be grateful if you would consider reflecting this in your assessment.

Best regards, The authors

Thank you for the detailed rebuttal and revisions. I believe the paper makes meaningful theoretical contributions by characterizing the blind subspace using Fisher information and deriving a regret lower bound when unidentifiable directions affect the optimal policy. The experimental results are also significant. The authors have addressed my concerns regarding Propositions 7 and 9 in the revised manuscript. I also appreciate the additional threshold sensitivity experiments and the clarification of the regret comparator. However, the gap between certified stopping and the heuristic used in the experiments remains significant, and the practical relevance of the theoretical guarantees is limited. My original concerns about soundness have been resolved, but I will maintain my current score based on my overall assessment of the paper's contributions.

We thank the reviewer for the careful engagement.

Certified versus heuristic stopping.

  1. The experiments already evaluate the certified algorithm. At the horizons we run, the certified threshold of Corollary 3 is never reached. The certified algorithm therefore behaves exactly as probing without stopping, and that variant is reported: median regret 48.7 against 365.3 for certainty equivalence, with 100% recovery (App. R). The algorithm covered by the theory is thus tested directly, and it reduces regret by a factor of about 7.5.

  2. The heuristic improves on a method that already works. Heuristic stopping lowers median regret from 48.7 to between 25.2 and 28.4. The gap the reviewer identifies is therefore between two methods that both beat certainty equivalence by a wide margin. The theory's main claim, that settled learners fail and targeted probing fixes this, does not depend on the heuristic.

  3. The conservativeness sits in one place. It comes from the constants of the confidence radius (Theorem 5), as is usual for self-normalized confidence sets, whose theoretical radii are known to be much wider than the errors observed in practice. Only the stopping time depends on these constants. The blind-subspace characterization (Theorems 1 and 2), the lower bound (Theorem 4) and the T\sqrt{T} rate (Theorem 6) do not.

Practical relevance of the guarantees. The guarantees matter mainly for what they prescribe, and each prescription addresses a failure that has been documented in deployed ML systems.

  • A policy-generated dataset hides directions of the response. At YouTube, learning from logged feedback is biased because feedback is observed only on recommendations selected by previous versions of the recommender [1]. Recommenders trained on such confounded data homogenize user behavior without increasing utility [2]. In consequential decisions, observed outcomes are not a random sample of the population, because they depend on the existing decision policy [3]. Theorems 1 and 2 characterize exactly which directions such data leave unidentified, and the blind subspace can be computed before deployment.
  • Retraining on the policy's own data does not fix it. Predictive policing systems exhibit runaway feedback loops, in which police are repeatedly sent back to the same neighborhoods regardless of the true crime rate [4]. Theorem 4 makes the shared mechanism precise: a settled learner suffers linear regret whenever the blind subspace matters for the value.
  • Deployed systems explore, but not in a targeted way (minimal probing, Theorem 6). Yahoo!'s news recommender designates a small amount of traffic for exploration and reports a 12.5% click lift over a standard context-free bandit [5]. YouTube's production RL recommender likewise highlights the value of exploration [1]. In online RLHF, the preference data are generated by the current policy, so feedback reveals only what that policy already produces. [6] show that passive online exploration of this kind can fail to find optimal behavior when the initial model lacks coverage, and that adding an exploration bonus to online DPO lets the model explore beyond the support of the initial model and its preference data. [7] find that active exploration reaches high performance with far fewer human feedback queries than the standard passive practice of sampling response pairs at random. Our results give the performative counterpart: when the policy also shapes the environment, the blind subspace states which directions passive data miss, and minimal probing explores only those. Our minimal probing result says the probes only need to span the blind subspace, and Theorem 6 prices this at T\sqrt{T} regret.

These prescriptions survive when the probing design is learned (App. S) and when the response departs from the tilt.

References

[1] M. Chen, A. Beutel, P. Covington, S. Jain, F. Belletti, E. H. Chi. Top-K Off-Policy Correction for a REINFORCE Recommender System. WSDM 2019.

[2] A. J. B. Chaney, B. M. Stewart, B. E. Engelhardt. How Algorithmic Confounding in Recommendation Systems Increases Homogeneity and Decreases Utility. RecSys 2018.

[3] H. Lakkaraju, J. Kleinberg, J. Leskovec, J. Ludwig, S. Mullainathan. The Selective Labels Problem: Evaluating Algorithmic Predictions in the Presence of Unobservables. KDD 2017.

[4] D. Ensign, S. A. Friedler, S. Neville, C. Scheidegger, S. Venkatasubramanian. Runaway Feedback Loops in Predictive Policing. FAT* 2018, PMLR 81:160–171.

[5] L. Li, W. Chu, J. Langford, R. E. Schapire. A Contextual-Bandit Approach to Personalized News Article Recommendation. WWW 2010.

[6] T. Xie, D. J. Foster, A. Krishnamurthy, C. Rosset, A. Awadallah, A. Rakhlin. Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF. ICLR 2025.

[7] V. Dwaracherla, S. M. Asghari, B. Hao, B. Van Roy. Efficient Exploration for LLMs. ICML 2024, PMLR 235:12215–12227.

Thank you for the follow-up and additional clarifications. I will take these points into account during the reviewer-AC discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.