acceptodds
Under review as a conference paper at ICLR 2027

Budget-Aware State Criticality via Optimal Interventions under Decaying Agency

Abstract

In reinforcement learning, _critical states_ are situations where the chosen action has a disproportionately large impact on the final outcome. Identifying such critical states is a fundamental challenge, with applications in explainability, credit assignment, and human oversight of autonomous agents. We present CODA (**C**riticality via **O**ptimal Interventions under **D**ecaying **A**gency), a framework in which an agent can intervene by overriding the action of a fallback policy, but each intervention can make future ones less likely to take effect. Critical states are those where the agent still chooses to intervene, making criticality explicitly relative to the fallback policy. We show that the resulting problem decomposes into a cascade of coupled optimal stopping problems, and build on this structure to develop algorithms for both tabular and continuous environments. We prove that critical states exist if and only if the fallback policy is suboptimal, and that, unlike in penalty-based approaches, they are invariant to the scale of the reward. Empirically, CODA identifies intuitive critical states in grid worlds and continuous control, and, when used to allocate a limited intervention budget, matches or exceeds the returns achieved with State Importance and Lazy-MDPs.

Primary area:
reinforcement learning
Keywords:
critical state identification, explainable reinforcement learning, optimal stopping

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_w4UXOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

Proposed: CODA (criticality via Optimal Interventions under decaying agency), a method that permits agentic intervention of the fallback policy, but penalizes interventions by making future interventions less likely to take effect. Ie. ~If I intervene, I better be sure it is worth it, and this underscores the importance of those interventions. Namely,

  • This is analyzed/characterized as a sequence of coupled optimal stopping problems
  • Then they propose an algorithm corresponding to this perspective
Critical strengths

Strengths:

  • This fits nicely into popular frameworks like Lazy-MDP, building off it to penalize overriding but in a clever way of decreasing future agency
  • This obfuscates reward-scale tuning for intervention and makes the threshold state-dependent
  • The method is principled and budget-aware in comparison with the Q-variance heuristic solutions (Q-value spread, return-variance criticality)
  • The analysis and proofs look clear and correct, eg. Prop 5. (On the option-value vs global threshold) Is interesting and appears novel (if I am not mistaken)
  • This method can be controlled intuitively it appears from results, by tuning beta (exogenous chain example)
Critical weaknesses

Weaknesses:

  • Continuous evaluation is difficult and it seems unsolved totally by the proposed method
    • This is as the authors mention because compute scales with K
  • This requires random starts, as criticality is trustworthy only with good rho-visitation
  • Experimental results show a large overlap with Lazy-MDP
  • The experiments are largely confined to small environments where this works well, but neglects more complex tasks where the authors propose this method would be useful
  • Even a toy human-in-the-loop study is missing despite being a motivational case

Overall: CODA is a principled and interesting method that seems to work well for simple/small environments. That being said, the method is fundamentally limited in larger/continuous spaces and its evaluation is currently narrow, challenging its practical usage. It seems that if the authors could demonstrate the success in larger environments, they might convince me that additional tricks are needed to make the method work.

Questions for authors

None at this time

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

In this paper, the authors present CODA, a framework for identifying critical states in an MDP. The key idea is that, by default, a fallback policy (\rho) is executed in each state. The agent can intervene and override this policy, but interventions come at a cost: the intervention budget is limited in one setting, while the probability of successful future interventions decreases in the other two settings. The authors then develop Cascaded Value Iteration to solve the problem in tabular MDPs and DeepCODA for continuous environments. Both methods are validated through experiments across several environments.

Critical strengths

The paper is well-written, clearly structured, and easy to follow. It addresses the important problem of identifying critical states in reinforcement learning, which has potential applications in interpretability, human-AI collaboration, and resource-constrained decision-making.

The proposed framework provides an interesting perspective on state criticality by considering when an agent should intervene rather than follow a fallback policy. The authors establish several theoretical properties of the framework, including the existence of critical states for suboptimal fallback policies and invariance to reward scaling. They also establish a connection to the existing Lazy-MDP framework and provide algorithms for both tabular and continuous environments.

Finally, the experimental evaluation covers a range of environments and demonstrates that CODA can identify meaningful critical states and achieve competitive or improved performance compared with existing methods, particularly under tight intervention budgets.

Critical weaknesses

For me, the main weakness of the paper concerns its significance and potential impact. While I acknowledge the importance of the problem, I do not clearly see why the proposed framework and associated methods are preferable to existing approaches, or how the broader RL community would benefit from adopting this new framework.

At the same time, I acknowledge that I may not be sufficiently familiar with this particular area of reinforcement learning to fully understand the significance of the proposed approach. For this reason, I currently lean toward rejection, but I am open to reconsidering my assessment based on the authors' responses and further discussion.

Questions for authors

While reading the paper, I came up with a simple advantage-based criterion for state importance:

I(s)=Ea∼π~(⋅∣s)[Aρ(s,a)],I(s)=E_{a\sim\tilde{\pi}(\cdot\mid s)}[A^\rho(s,a)],

where (\tilde{\pi}) is a candidate intervention policy and (\rho) is the fallback policy. This quantity measures the expected improvement from switching from (\rho) to (\tilde{\pi}) at a particular state. We could then rank states according to this criterion and select the most important ones for intervention.

Would this simple approach identify similar critical states to CODA, or are there situations in which it would fail? In particular, could the authors clarify what advantages CODA offers over such an advantage-based criterion?

2 comments

Dear Reviewer dWrR,

As the discussion period ends in less than 24 hours, we wanted to check whether our response has addressed your concerns, and whether any questions remain that we can still answer.

In brief: our response addressed the significance issue by explaining the key properties that distinguish CODA from Lazy-MDP and by running a further experiment in a relaxed evaluation setting that showcases CODA's advantage, without requiring any additional training. To address your question about the proposed criticality criterion, we showed how it relates to our framework, especially in the context of Proposition 5, visualized its critical states on CliffMaze, and compared it against the baselines on the budgeted intervention task on UnlockPickup.

Since then, we have also added a comparison with Lazy-MDP on LunarLander, which you can find in our latest reply to Reviewer RzU1.

Thank you again for your review. We would be grateful for any further feedback.

I thank the authors for their response, and I apologize for the delay in replying. Before making my final decision, I wanted to follow the discussion with the other reviewers.

I believe the authors have adequately addressed my concerns, and I particularly appreciate their answers to my questions regarding the advantage-based criterion. Therefore, I have decided to increase my score to 3 — Weak Acceptance.

Reviewer_RzU1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper targets the problem of finding a set of critical states in an MDP. The critical states are states where the choice of the action can substantially impact the final performance of the policy. The paper introduces CODA (Criticality via Optimal Interventions under Decaying Agency), a framework to find the set of critical states where an expert intervention can substantially improve the performance of the overall policy. The paper discusses the properties needed for CODA with theoretical results to show that CODA is guaranteed to find a non-trivial set of critical states provided the baseline policy is suboptimal. The paper discusses the different choices for baseline policy and other relevant hyperparameters and explains how CODA is reward- scale invariant unlike Lazy-MDP. CODA is able to differentiate between states with similar reward statistics whereas Lazy-MDP and SI may fail to do the same. Additionally, the paper compares CODA performance against Lazy-MDP and SI (state importance) approaches under different budget constraints and with 2 different environments - UnlockPickUp, CliffMaze. The paper also provides additional comparisons against randomly gating for choosing critical states on Hopper and Lunar Lander environments.

Critical strengths
  • [S1] CODA approach is reward scale invariant making it a more practical option when there is no information about the reward scale of the environment. The guarantees of finding critical states under suboptimal policy provides theoretical validation for the framework.

  • [S2] Additionally, the paper investigates various different agency decay schedules and their impact on the set of critical states.

Critical weaknesses
  • [W1] Inconsistencies in Proofs: The proofs have several issues, most of them likely to be typos. The proof of Corollary 1 (Lines 672-695) and proof of Theorem 1 (use of Lemma 2) have inequality sign errors. These issues, and their downstream effects in the proof (if any), need correction.

  • [W2] Limited Evaluation of Deep CODA: The Deep CODA evaluation is limited. In continuous-environment experiments, only SI and random are included as baselines; Lazy-MDP is not included as baseline. Authors mention this in discussion but this should have been included in the paper.

  • [W3] Comparison in tabular setting: In the tabular setting, CODA does not consistently outperform Lazy-MDP (Figure 10), hence a consistent advantage over Lazy-MDP is not established even in the tabular settings.

  • [W4] The provided theoretical results are limited to tabular MDPs and the generalization of theory to continuous state-action scenarios is not discussed.

  • [W5] The wall-clock times of Deep CODA and other baselines are not presented.

Questions for authors
  • [Q1] Authors are requested to correct all the typos in the proofs (mentioned in [W1]), please highlight all the corrections in the rebuttal so that correctness can be verified.

  • [Q2] In section 5.1 (Tabular Environments), why is 30-50% of expert return (UnlockPickup) used as the criterion to compare number of interventions?

  • [Q3] Please provide detailed discussion and comparison on wall-clock times for Deep CODA and other baselines.

  • [Q4] Why is sparsity of the critical states important (line 353-355)?

  • [Q5] The Lazy-MDP paper provides results for a wider range of environments, including Atari games. Have the authors considered such experiments?

  • Typos and missing definitions: 1.(Line 210) MPD →\to MDP 2. (Line 200-202) ϵ\epsilon is not defined. 3. (Line 95-96) uses Δ\Delta as a probability simplex, whereas in (line 220-221) it is used as difference increments. 4. The tables on page 25 are referred as figures.

5 comments

Weaknesses

Here we briefly address the weaknesses which were not already addressed in a question.

[W2] Lazy-MDP is not included

We attempted to include Lazy-MDP in the continuous evaluation. It should be noted that the original paper focused on discrete action spaces and that their methods are specific to that setting. However, nothing about the Lazy-MDP framework itself prohibits an extension to continuous action spaces. The resulting MDP will have a hybrid action space, since the default action is discrete in an otherwise continuous action space. The results of our attempts were worse than what would be expected from Lazy-MDP and we did not want to report a misleading baseline. We have since trained Lazy-MDP models for different values of η\eta in the discrete-action version of LunarLander, which can be translated into the continuous action version. For Hopper, no such discrete action variant exists to our knowledge. After a proper evaluation, we will update Figure 5 and the LunarLander discussion in the paper.

[W3] Comparison in tabular setting

We agree: under the best-per-budget parameters, CODA and Lazy-MDP are on par, and we do not claim a consistent advantage in this evaluation. The differences lie in the parameterization (scale-free, guaranteed non-empty) and CODA's access to a family Ckk=0K−1\\{C_k\\}_{k=0}^{K-1} of critical states, as seen with CODA-step(B). We have also added an evaluation in which this restriction is lifted (Appendix E.2, Table 8): when both methods intervene with their own policies and CODA-exp may use all CkC_k, CODA is significantly ahead of both baselines for 11≤B≤1711 \le B \le 17 on UnlockPickup, reaching about twice the return of the best baseline at B=13B=13 (0.233 vs. 0.114), with a tie at B=19B=19.

[W4] Generalization to continuous state-action scenarios

We believe that all theoretical results except Proposition 2 (which was specific to the CVI algorithm) should carry over to the continuous state and action case. Naturally, this may require adaptations to the proofs and additional assumptions in the statements, which we do not feel we can confidently supply in the short rebuttal period. For this reason, we maintain the claims as they are and leave the extension of the theoretical results to continuous spaces to future work.

Thank you for your responses and updated manuscript. The updates answer the questions regarding correction to proofs and wall-time performance comparisons. Additionally the sparsity discussion explains its significance and why the community may want to focus on the same. While CODA takes several times longer to train as compared to LazyMDP, its performance is not clearly better on the tabular tasks. CODA is better on lower budget conditions as compared to LazyMDP on UnlockPickup, but it is worse in the CliffMaze environment in many cases. The results on two tabular tasks do not establish CODA's advantage over LazyMDP in tabular experimental setups. Additionally, DeepCODA has not been compared with LazyMDP on the continuous control tasks making it difficult to gauge its performance in that setting. Given the lack of experimental validation and unclear experimental advantage, I will maintain my score.

Thank you for the follow-up.

It is true that CODA takes longer to train than Lazy-MDP on the tabular tasks. In return, it yields a family of critical state sets with action recommendations, as described in our response to [W3]. When both methods use their own policies, CODA significantly outperforms Lazy-MDP on UnlockPickup for budgets between 11 and 17 (Table 8 in Appendix E.2). This does not affect training times, because the policies are computed anyway.

On CliffMaze, you are right that Lazy-MDP is ahead in several cases under the restricted evaluation: by small margins at B=15B=15 and 1616, and at low return targets, where CODA’s sparsest critical set (β→∞\beta \to \infty) already uses 13.9 interventions per episode, while Lazy-MDP’s can be made arbitrarily small through η\eta. Under the relaxed evaluation the two are on par, except at B=11B=11 (Table 10). We also note that CliffMaze is a much simpler environment than UnlockPickup: it features 110 states, compared to 17,000+ on UnlockPickup, and its states only encode the agent's position. UnlockPickup's state additionally maintains the state of the key and the door and therefore possesses more structure than CliffMaze.

As for the continuous evaluation, the Lazy-MDP runs on discrete-action LunarLander are now finished, and we apologize for the delay. The following table contains the results for CODA and Lazy-MDP under a B=100B=100 budget. For the sake of brevity we have omitted SI and random, but they can be found in the paper.

LunarLander, uniform ρ\rho, B=100B = 100, 3 seeds per parameter, 500 evaluation episodes: mean ± SE

methodparamreturninterventions / ep.
ρ\rho (no interventions)---146.8 ± 6.40.0 ± 0.0
CODAβ=0.5\beta=0.52.7 ± 4.350.9 ± 5.0
β=1\beta=1-7.6 ± 3.139.0 ± 6.8
β→∞\beta\to\infty-12.3 ± 4.426.9 ± 4.7
Lazy-MDPη=2\eta=24.2 ± 6.281.0 ± 8.0
η=2.5\eta=2.5-0.1 ± 8.575.0 ± 12.3
η=3\eta=3-5.7 ± 3.251.7 ± 1.1
η=3.5\eta=3.5-18.1 ± 11.337.4 ± 18.3
η=4\eta=4-16.7 ± 14.860.1 ± 25.1
η=4.5\eta=4.5-26.9 ± 5.733.9 ± 13.0
η=5\eta=5-55.0 ± 17.616.2 ± 4.7

At each of CODA’s three intervention counts, the Lazy-MDP model with the closest count has a lower mean return. The gap is clearest for β→∞\beta \to \infty (−12.3±4.4-12.3 \pm 4.4 at 26.9 interventions vs. −26.9±5.7-26.9 \pm 5.7 at 33.9 for η=4.5\eta = 4.5, about two standard errors), smaller for β=0.5\beta = 0.5 (2.7±4.32.7 \pm 4.3 vs. −5.7±3.2-5.7 \pm 3.2 for η=3\eta = 3), and within noise for β=1\beta = 1. We read this as CODA being at least on par with Lazy-MDP, with an advantage at low intervention rates. The Lazy-MDP runs on Pong are still ongoing, and we will report the results once finished.

More generally, our claim is that CODA matches the baselines empirically while offering properties they lack (a scale-free parameter, guaranteed non-empty critical sets, and budget-awareness), not that it outperforms them across the board.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.