acceptodds
Under review as a conference paper at ICLR 2027

THE LAST CRITIC BUYS PARALLELISM: A QUERY–FEEDBACK LAW FOR CRITIC LIBRARIES

Abstract

A critic can be redundant for exact identification yet valuable for parallel acquisition. We study separately optimized singleton-avoidance critics in a finite discounted MDP with states and actions per state. Any critics identify the transition kernel exactly, but noise makes the identity of a stable omission depend on the unknown kernel. We ask how many feedback rounds are needed to match the complete library's recovery and execution rates as the horizon and noise level vary, when each batch is chosen before any of its columns arrives. For any fixed row-diameter bound , let . When , a blockwise residual rule for arbitrary finite nonempty action sets uses queries in at most \[ \left\lceil n-2b-1 \right\rceil \] rounds and achieves the same error scaling. If and , a hidden-core lower bound shows that at least \[ \left\lceil n-1b \right\rceil \] rounds are necessary. Under the same conditions, if each round can carry at most critics, the minimum identifying budget has depth \[ \Theta\!\left(1+n\max{\kappa,W^-1}\right). \] Without a per-round cap, these depths are for critics and one for all . The penultimate critic buys identifiability; the final buys parallelism by removing the adaptive bottleneck, not the per-round cap.

Primary area:
reinforcement learning
Keywords:
Theoretical Reinforcement Learning, Markov Decision Processes, Sequential Decision Making, Model Identification, Adaptive Querying

Reviews

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

This paper examines how many previously learned optimal critics are required to reconstruct the transition dynamics of an unknown Markov Decision Process (MDP). Also it investigates how many adaptive feedback rounds are necessary to achieve robust recovery when critic values are noisy.

Critical strengths

The paper identifies an important difference between exact identifiability and robust identifiability under noise. The observation that an algebraically redundant critic can still substantially reduce acquisition latency provides a meaningful perspective on critic-library reuse.

Critical weaknesses

The experiments do not represent practical effectiveness in larger or more realistic environments. Experiments on larger state spaces, different action counts, and benchmark reinforcement-learning environments would strengthen the experimental results.

Questions for authors

How does the proposed algorithm scale computationally with the number of states and actions?

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

My understanding is that this paper aims to address a fairly specific reinforcement learning problem: given a set of critics already trained on different auxiliary rewards, if we can only obtain a portion of their noisy Q-values in batches at a time, how many rounds of feedback must we wait before achieving a transition model reconstruction accuracy close to that of the full critic library? The authors distinguish between “how many columns of critics to query” and “how many feedback rounds to wait.” I believe this distinction itself is worth investigating, because even if n−1n-1 exact critics are already capable of identifying the transition kernel of an MDP, it may not be robust to fix in advance which column to omit when noise is present.

Critical strengths

S1: What I find most compelling is the combined discussion of upper and lower bounds on the number of feedback rounds. The authors’ batch-query algorithm and the hidden-core lower bound demonstrate that, within the proposed query model, an additional, seemingly redundant critic can indeed eliminate the need for adaptive waiting. This goes a step further than simply proving that Bellman inversion can recover the transition kernel. In particular, they include methods that allow for continued online learning during the execution phase in their lower bound, which I consider an important theoretical distinction.

S2: I also find the occupancy matrix formed by separately optimized critics quite interesting. Although each column corresponds to a different subsequent policy, the authors still obtain a special inverse matrix structure and joint occupancy bounds, thereby enabling them to determine which critics can be omitted with relative stability. I believe there is genuine mathematical substance here, rather than simply renaming existing identification results.

Critical weaknesses

W1: However, I originally had significant questions about the research setup. Why would a real-world system provide entire columns of singleton-avoidance critic values? Why is the query budget precisely capped at n−1n-1? In how many RL tasks does the global transition-overlap assumption hold? I am concerned that if these conditions are too specific, the theoretical feedback complexity may be far removed from real-world policy learning. I also hope the authors clarify whether this result pertains to a bottleneck in information acquisition or whether it has already demonstrated a general improvement in downstream control performance.

W2: The experiments have not fully alleviated my concerns. Many of the omitted critics in the main experiment were stable to begin with, and the recovery errors for sequential and batch queries were similar. What I would like to see is: under the same n−1n-1 query budget, under what conditions does feedback from earlier batches actually determine which critic to read later? The hidden-core example illustrates the worst-case scenario, but it remains to be seen how broadly it represents MDPs—this requires careful clarification.

Questions for authors

Q1: I would like the authors to explain, using a clear RL scenario, why these critics need to be accessed in batches, and to point out exactly where the new learning bottleneck lies compared to existing Bellman inversion work.

Q2: I also want to know how the reduction in feedback rounds was measured, and whether the authors conflated it with “smaller recovery error” or “higher policy reward.”

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

The main thrust of the paper appears to be the setting of tabular, known-state, discounted MDP setup where the learning happens in two stages. The first stage is a reward free-pretraining stage followed by a zero-shot transfer learning stage. The key aspect being that the pretraining does not learn the transition function but instead an oracle of noisy optimal critics queried in batches. The main results of the paper established how many adaptive rounds and acquired critics are needed to acquire critics from a library of n optimized critics, which can allow us to match the full library accuracy. The paper provides experiments in support of the given bounds.

Critical strengths
  1. Prior works, such as Letcher 2026, answer the question whether the a critic library can be used to infer the dynamics of the system, this work answers the question about how many rounds of queries are needed for inferring the dynamics of the system.
  2. The work gives a detailed breakdown of feedback depth required for different number of queries (less than n-2 and equal to n-1). Matching upper and lower bounds are provided, which is a step above most theoretical analyses where only an upper bound is supplied. The insight that the second to last critic buys identifiability and the last buys parallelism, is a genuinely insightful result.
Critical weaknesses
  1. The main weakness of this paper, in my view is the presentation. In it's current form, the paper seems to lack a coherent story it is trying to tell. It seems as if a situation has been constructed in which the given result is obtained. There is no introduction, of what is the relevance of the problem to the ML community, what have been the past attempts in the literature, and what are ways in which this work improves upon the existing results. That I think is a core requirement of any ML paper and this one does not seem to satisfy that criteria in the current stage.
  2. During the reading of this paper, there are several terms such introduced without clearly stating what exactly is it that they mean. Examples include things like 'singleton avoidance critics', 'Stable omission/stably redundant' in section 1. The terms 'Complete library’s horizon–noise order' in section 2 is not clear as to what it is trying to convey. In section 4 the term 'inverse mass' is used without any intuition about what it represents in the MDP. This is by no means an exhaustive list, at many points in the work the introduction of terms seems to not follow a coherent flow.
  3. The experiments done at the end do not make it clear
Questions for authors
  1. Can you describe a concrete scenario which describes the setup used in this paper? i.e where a learner has noisy access to a complete critic library, the learner can only read at most n−1 columns, and the columns themselves are received only in batches? Why would the last column alone be costly to obtain?
  2. The setting resembles zero-shot or reward-free RL (successor features, forward–backward representations, reward-free exploration): pretraining without the reward, then a reward revealed later. Can you position the work relative to that line and explain what the critic-oracle view adds?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.