The Trick That Closes a Long-Open Gap in Adversarial MDPs: Voluntarily Delay Your Own Feedback

Resolves an open problem in adversarial RL by deliberately introducing feedback delays — achieving optimal √S and √K regret dependencies where the field has been stuck for years.

Imagine you're a chef in a restaurant that changes its menu every night based on customer complaints — but the complaints only arrive two days late. That delay sounds like a handicap, and in most RL literature, it is. This paper asks: what if you deliberately impose that delay on yourself, even when you don't have to? The counterintuitive answer is that voluntarily delaying feedback lets you estimate the Q-function of your *current* policy using data from *future* episodes — sidestepping the fundamental correlation problem that has bottlenecked adversarial MDP regret bounds for years. The committed claim: in tabular adversarial MDPs with S states, A actions, and horizon H, the authors achieve Õ(poly(H)√(SAK)) regret over K episodes with bandit feedback and unknown transitions, closing the √S gap to the known Ω(H√(SAK)) lower bound. In linear AMDPs with d-dimensional features, they achieve Õ(poly(d,H)√K) regret — the first computationally efficient algorithm optimal in K without a simulator or exploratory assumptions, after a five-year progression that started at K^{14/15} and had stalled at K^{3/4}. The core mechanism is what they call 'introduced feedback delays.' In standard policy optimization for AMDPs, you need to estimate the Q-function of the policy you're currently running, but your data comes from earlier, different policies. The usual fix — freeze the policy and collect fresh on-policy data — costs you in the K dependency. Instead, the authors let the policy keep updating but treat the Q-function estimate as if it were delayed, using future episode data to evaluate the current policy. They develop Geometric Resampling with Rejection (GRR) to handle the distributional mismatch caused by policy changes during the delay window, and threshold visitation probabilities to prevent rarely-visited state-action pairs from causing unbounded delay. The ladder position is strong. In the tabular setting, the best prior bound was Õ(HS√(AK)) — this paper shaves off the extra √S that separated it from the information-theoretic lower bound. In the linear setting, the progression from K^{14/15} (2020-era) through K^{6/7} and K^{3/4} to the new √K is a clean five-year arc where each step required a genuinely new idea, not just tighter analysis. The paper also naturally extends to the *actual* delayed feedback setting, yielding the first bounds optimal in both S and total delay 𝔇 (tabular) and in both K and 𝔇 (linear). Architecturally, this is policy optimization in the occupancy measure framework, not value-based or model-based RL. The key structural choice — voluntary delay plus importance-weighted resampling — sits in the same family as off-policy correction methods but inverts the usual direction: instead of correcting past data to look like the present policy, it uses future data and corrects for the fact that the policy drifted forward. GRR is a rejection-sampling scheme that geometrically resamples trajectories until the distribution matches the target policy's visitation, with hard thresholds preventing runaway rejection rates. Integrity is theoretical: the results are high-probability regret bounds with formal proofs, not empirical benchmarks. This is standard and appropriate for this corner of the field — the contribution is mathematical, and the claim is that specific polynomial dependencies are achieved. There are no experiments to cherry-pick and no benchmarks to game. The validation is the proof itself, which means the community will verify by reading the argument, not by running code. The absence of empirical demonstrations is not a red flag here — it's how this subfield operates. The obvious next experiment the authors did not run: empirical evaluation showing the practical constant factors. Theory papers in this space often have polynomial dependencies that are tight in the leading term but hide enormous constants in the poly(H) or poly(d,H) factors. Whether this algorithm is practical — or whether the constants make it unusable for any real problem size — is genuinely unknown. The honest read: this is (c), saving it for future or companion work, because the contribution is the proof technique, not a practical algorithm. Alternatively, the constants might be bad enough that empirical results would undercut the narrative.