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.
est. 32% chance this paper gets accepted at ICLR 2027.
What do you think this paper will get?
All positions stay anonymous.