Pith.

Machine Learning · arXiv:2611.17214 v1 · submitted 12 Nov 2026 · 16 references

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal √S and √K Dependencies in Tabular and Linear AMDPs

Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai

The paper says

“We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback.”

more of the abstract

In tabular AMDPs with S states, A actions, and horizon H, the best known K-episode regret is Õ(HS√AK), whose √S gap to the Ω(H√SAK) lower bound has long remained open. In linear AMDPs with d-dimensional features, after a five-year line of improvements starting from K14/15, computationally efficient algorithms without a simulator or exploratory assumptions still only attain Õ(K3/4) regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on K. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, Õ(poly(H)√SAK) regret in tabular AMDPs, resolving the open problem; and Õ(poly(d,H)√K) regret in linear AMDPs, giving the first efficient algorithm optimal in K. They also naturally extend to delayed AMDPs with a total feedback delay $\mathfrak D$, yielding the first bounds optimal in S and $\mathfrak D$ (tabular) and in K and $\mathfrak D$ (linear).

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up. Strong, self-contained theory paper that plausibly closes two open AMDP gaps; it deserves serious refereeing. This line is wrong

4 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 16 references say.

4 minor objections

The paper says, at Section 6, Appendix A.1 and B.1

Pith says: minor objection 1 of 4

Algorithms 4 and 5 appear only in the supplementary material, although Theorems 6.1 and 6.2 refer to them as if they were part of the main text; adding an explicit pointer in Section 6, or a short display of the delayed processing rule there, would make the main text more self-contained.

The paper says, at Sections 2.1 and 2.2

Pith says: minor objection 2 of 4

The performance-difference lemma and the regret decomposition are written with sums over S, even though the linear model of Definition 2.1 allows uncountable state spaces; a sentence saying that these expressions are to be read as integrals in the linear setting would remove ambiguity.

show 2 more

The paper says, at Footnote 1 and Table 1

Pith says: minor objection 3 of 4

The claim that all prior bounds have been translated into one common notation is not accompanied by the translation rules (for example, T=HK and the layered-state convention); spelling out these rules would make the comparison table easier to verify.

The paper says, at Section 3.2, Eq. (13)

Pith says: minor objection 4 of 4

The pseudo-inverse identity is displayed as an infinite series for 0\prec\Sigma\preceq I and is later applied to empirical covariance matrices with truncated eigenvalues; Lemma B.10 supplies the correct range-restricted interpretation, but a forward pointer at Eq. (13) would prevent a misreading.

This objection may describe the copy Pith gave the reviewer, not the paper.

What would settle it

Verify that the likelihood ratio bound in Lemma 3.1 holds under the stated conditions by independently re-deriving Lemma A.5 and Lemma B.9 from the paper's parameter choices (Eq. 37 and Eq. 64). If the derivation is correct, the central claim stands.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up confidence moderate
  2. Skeptic agrees 9 s · 73,371 tokens read, 392 written
  3. Editor wrote the verdict above 21 s · 74,229 tokens read, 2,099 written
  4. Referee accept: 4 minor 1 min 27 s · 74,626 tokens read, 936 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

Bottom line: if the proofs are right—and nothing I saw contradicts them—this paper settles the tabular sqrt(S) gap and gives the first efficient sqrt(K) linear AMDP algorithm. The mechanism, introduced feedback delays with GRR/MGRR and thresholding, is genuinely new. It is not past-data optimism or policy freezing dressed up; the estimates use future episodes while policy updates continue, and the rejection-sampling fix for policy drift is the core idea.

The paper earns credit for structure: Theorems 4.1 and 5.1 are stated with exact additive terms, high-probability statements, explicit parameter choices, and full appendix proofs (A.1–A.15, B.1–B.17, C.1–C.5). The weakest-looking link, the likelihood ratio bound in Lemma 3.1, is actually proved (A.5, B.9) by choosing eta small enough. There is no circularity: hyperparameters are fixed by the proof, lower bounds are external, and self-citations appear only as baselines. The paper also openly acknowledges its suboptimal H and d factors and the concurrent work.

Soft spots, in proportion. The proofs are long and not machine-checked; the linear part especially has many moving pieces (region construction, truncation, rejection, bias correction), and a mistake anywhere would be hard to catch. The policy-drift condition is load-bearing in both settings; if it failed, accepted trajectories would not be fresh pi_k trajectories. The authors prove it, but it is the place I would ask a referee to scrutinize. The linear result assumes sqrt(K) is an integer and D is known; both are standard and minor. The H and d gaps are real (tabular H5/2 versus lower bound H; linear d3 H4 versus d H3/2), and the paper says so. None of this undermines the central claims.

Who is this for: anyone working on AMDPs, bandit RL, or delayed feedback. It deserves a serious referee. I would not desk-reject; I would send it out and ask for a careful check of Section 5 and Appendix B. I would also cite it.

The strongest objection

No significant objection identified. The paper is a self-contained theoretical contribution with full appendix proofs. The central claim—that introduced feedback delays close the sqrt(S) gap in tabular AMDPs and achieve the first efficient sqrt(K) regret in linear AMDPs—is supported by detailed algorithmic constructions and rigorous analysis. The weakest link identified by the reader (the likelihood ratio bound in Lemma 3.1) is indeed a theorem proved in the appendix (Lemmas A.5 and B.9) rather than an assumption. The paper explicitly acknowledges non-optimal H and d dependencies and concurrent work. I find no internal inconsistency, circular dependence, or missing critical step that would undermine the central claim.

The reader's verdict is ACCEPT with MODERATE confidence, and the weakest_assumption correctly identifies the likelihood ratio bound as the most load-bearing link. The paper proves this bound (Lemmas A.5 and B.9) rather than assuming it, so it is a theorem. The paper also acknowledges limitations (non-optimal H and d dependencies) and concurrent work. I find no additional load-bearing concern beyond what the reader already considered. The concrete test I propose is a verification of the key lemma, which would increase confidence but is not required to accept the paper's claims as presented. Therefore, the verdict should remain UNCHANGED.

The referee's report

The contribution is substantial if the proofs are correct. The tabular result answers the long-standing \sqrt S gap between \tilde O(HS\sqrt{AK}) and \Omega(H\sqrt{SAK}), and the linear result removes the \tilde O(K^{3/4}) barrier in K without simulators or exploratory assumptions, with high-probability rather than in-expectation guarantees. The introduced-delays idea is a reusable algorithmic device, and the GRR/MGRR constructions with thresholding are elegant. The paper is unusually complete on the technical side: the parameter choices in Eqs. (37) and (64) are explicit, the lemmas in Appendices A, B, and C are stated and proved, and the theorems include the additive terms rather than hiding them. The authors also explicitly acknowledge the non-optimal H and d dependencies and note that the assumption that D is known can be removed by the doubling trick. I checked the most load-bearing link identified in the surrounding discussion, namely the likelihood-ratio bound that keeps accepted trajectories fresh in Lemma 3.1; that condition is proved in the appendix through Lemmas A.5 and B.9 rather than assumed.

Pith's reading of the paper (a machine's summary, not the authors')

The paper introduces a unified technique called "introduced feedback delays" to solve two long-standing open problems in adversarial Markov decision processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs, it achieves the first regret bound matching the lower bound in the state and action counts, closing a six-year gap. In linear AMDPs, it achieves the first computationally efficient algorithm with optimal square-root-K regret, closing a five-year gap. The key idea is to estimate the Q-function of a changing policy using future episodes rather than past data or freezing the policy, by voluntarily introducing feedback delays and using geometric resampling with rejection to correct for policy drift.

What carries the argument. Introduced feedback delays: a technique where the agent voluntarily delays the use of feedback from an episode, allowing the Q-function of a policy to be estimated using trajectories from future episodes while the policy continues to be updated. This is enabled by Geometric Resampling with Rejection (GRR), which uses rejection sampling to correct for policy drift between the episode being evaluated and the future episodes used for estimation. The key identity is that the likelihood ratio between two policies on a trajectory depends only on the actions taken, not the transitions, so it can be computed without knowing the transition probabilities.

Core claim. The paper discovers that the Q-function of a policy can be accurately estimated using trajectories from future episodes, even while the policy continues to be updated, by treating the feedback as if it were delayed. This is achieved through two procedures: Geometric Resampling with Rejection (GRR) for tabular AMDPs and Matrix Geometric Resampling with Rejection (MGRR) for linear AMDPs, which correct for the mismatch between the policy being evaluated and the policies generating the future trajectories. A thresholding mechanism handles rarely visited state-action pairs by leaving them unestimated and covering the resulting error with a large exploration bonus.

The premise it rests on. The likelihood ratio between the policy at the episode being evaluated and the policy at any later episode used for estimation must remain bounded by 2, which requires the policy to change slowly enough.

If the paper is right (Pith's inferences, not the authors')

Resolves the open problem of closing the sqrt(S) gap in tabular AMDPs with unknown transitions and bandit feedback, achieving the first bound matching the lower bound in S, A, and K.

Provides the first computationally efficient algorithm for linear AMDPs with optimal sqrt(K) regret, without requiring simulators or exploratory assumptions.

The technique naturally extends to delayed feedback settings, giving the first bounds optimal in both the state space and total delay for tabular AMDPs, and in both K and total delay for linear AMDPs.

The introduced feedback delays technique is general and may be applicable to other reinforcement learning settings where a changing policy needs to be evaluated without freezing the future, such as multi-agent reinforcement learning.

The technique might be applicable to other problems in online learning where a changing decision rule needs to be evaluated using future data, such as in adversarial bandits with changing action sets or in online convex optimization with delayed feedback.

The thresholding idea for handling rarely visited state-action pairs could be adapted to other settings where estimation variance is high for low-probability events, potentially improving sample efficiency in exploration.

The use of rejection sampling to correct for policy drift suggests a general principle: if the likelihood ratio between policies can be computed, future data can be used to evaluate past policies without freezing the policy, which could be useful in continual learning scenarios.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with S states, A actions, and horizon H, the best known K-episode regret is Õ(HS√AK), whose √S gap to the Ω(H√SAK) lower bound has long remained open. In linear AMDPs with d-dimensional features, after a five-year line of improvements starting from K14/15, computationally efficient algorithms without a simulator or exploratory assumptions still only attain Õ(K3/4) regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on K. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, Õ(poly(H)√SAK) regret in tabular AMDPs, resolving the open problem; and Õ(poly(d,H)√K) regret in linear AMDPs, giving the first efficient algorithm optimal in K. They also naturally extend to delayed AMDPs with a total feedback delay $\mathfrak D$, yielding the first bounds optimal in S and $\mathfrak D$ (tabular) and in K and $\mathfrak D$ (linear).

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-14

The authors' main claim, as the classifier picked it out 1.00

“With this unified technique, our policy optimization algorithms achieve, with high probability, $\tilde O(\text{poly}(H)\sqrt{SAK})$ regret in tabular AMDPs, resolving the open problem; and $\tilde O(\text{poly}(d,H)\sqrt K)$ regret in linear AMDPs, giving the first efficient algorithm optimal in $K$.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.79 · states limitation 0.19 · human participants 0.01 · controlled comparison 0.08 · randomized assignment 0.02 · states quantitative result 0.98 · compares with prior results 0.97 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. background 0.76 0.52 0.02 asserted 0.81
In tabular AMDPs with $S$ states, $A$ actions, and horizon $H$, the best known $K$-episode regret is $\tilde O(HS\sqrt{AK})$, whose $\sqrt S$ gap to the $\Omega(H\sqrt{SAK})$ lower bound has long remained open. gap 0.83 0.04 0.03 asserted 1.00
In linear AMDPs with $d$-dimensional features, after a five-year line of improvements starting from $K^{14/15}$, computationally efficient algorithms without a simulator or exploratory assumptions still only attain $\tilde O(K^{3/4})$ regret. background 0.52 0.07 0.02 asserted 1.00
A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on $K$. background 0.87 0.12 0.02 asserted 1.00
We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. method 0.65 0.90 0.08 asserted 0.99
While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. interpretation 0.67 0.66 0.07 asserted 0.87
We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. method 0.98 0.91 0.03 asserted 0.99
With this unified technique, our policy optimization algorithms achieve, with high probability, $\tilde O(\text{poly}(H)\sqrt{SAK})$ regret in tabular AMDPs, resolving the open problem; and $\tilde O(\text{poly}(d,H)\sqrt K)$ regret in linear AMDPs, giving the first efficient algorithm optimal in $K$. result 0.97 0.96 0.94 asserted 1.00
They also naturally extend to delayed AMDPs with a total feedback delay $\mathfrak D$, yielding the first bounds optimal in $S$ and $\mathfrak D$ (tabular) and in $K$ and $\mathfrak D$ (linear). result 0.95 0.92 0.15 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.79 · evidence from proof or derivation 0.99

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-14: 1 request, 7,479 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

References (16)
  1. [1] Formally, let nt be the number of episodes processed at the end of episodet(namelynt ≜ Pκ 1[t κ =t]), and let N(t 1, t2)≜ max{t1,t2}−1X t=min{t1,t2} nt be the number of episodes processed between decidingπt1 and πt2. As every processed episode only changes the received loss sl... on Pith
  2. [2] < 10ι2 ≤ν . A union bound over the estimates, the pairs, the values ofj, and the episodes kshows that (ii) fails with probability at most(HK+ιSAK)e −ι ≤3δ/32for a large enoughC. Combining the two parts gives the failure probabilityδ/32 + 3δ/32 =δ/8, as claimed. In particular, ... on Pith
  3. [3] Haolin Liu, Chen-Yu Wei, and Hanbin Zhou. A computationally efficient and rate-optimal algorithm for adversarial linear MDPs with (aggregate) bandit feedback.arXiv preprint arXiv:2610.30801, on PithPith's reviewarXiv
  4. [5] 23 Introducing Feedback Delays to Non-Delayed Adversarial MDPs Supplementary Materials A Proofs for (Delayed) Tabular AMDPs 24 A.1 Algorithm with Delayed Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 A.2 Estimates and Good Events . . . . . . .... on Pith
  5. [8] X s q⋆(s)b(1)k (s). Moreover,0 ≤Y k ≤ (1 + 4νH )ηH 3/θ2 = O(1/(ηι))by Eq. (37), as at mostH estimates start in episodek. Hence, by Freedman’s inequality (Lemma C.1(i) withδ′ =δ/32), except with probabilityδ/32, X k Yk ≤ 5(e−1)νc1 Xk,s q⋆(s)b(1)k (s) +O 1η ≤ 9νc1 Xk,s q⋆(s)b(1)... on Pith
  6. [9] A.7 BoundingReg-Term Reg-Term is the regret of exponential weights on the estimatesbQk −B k, which it receives late: the pieces of every estimate arrive over several episodes, and, with delays,−Bk arrives when episodek is processed. As in the analysis of delayed feedback (Jin ... on Pith
  7. [10] We apply Lemma A.8(i) with the weight 1 [Gk]q⋆(s)πk(a|s )(dk + σk) ≤ 2¯d at every attempt of the estimate(k, s, a), ϵk(s, a) = 1 /2, λ = θ/(8(1 + νH )¯d), and δ′ = δ/32, for which(1 + νH )λ· 2¯d = θ/4 ≤p k(s, a)/2on Gk. We then apply Lemma C.1(i) withδ′ =δ/32to the starts. Exc... on Pith
  8. [11] ≤ 2d3/2H 3√D, that is,RK = eO(d3H 4√K + d3/2H 3√D). Finally, Algorithm 5 is computationally efficient, asπk(· |s)takes poly(K, d, H, A)time to compute by replaying the updates ats. B.2 Properties of Algorithm 2 The first lemma shows that Algorithm 2 splits the features into fe... on Pith
  9. [12] = 1 −e −1/40 < 0.025and Hoeffding’s inequality (Lattimore and Szepesvári, 2020, Eq. (5.8)), we have Pr   √ KX i=1 1[U i = 0]≥ √ K 10   ≤e −2 √ K(0.1−0.025) 2 ≤e − √ K/100 . Similarly, U ′1, U′2, . . .are i.i.d. with mean1/(1 + e1/40) > 0.49, so the same inequality shows th... on Pith
  10. [13] ≤ 1 + log √K, log(8KH/δ ) ≤ι , and ν≥C 0m0ι with logK≤ι . A union bound overkandhfinishes the proof. Hence, on the events of Lemmas B.3 and B.12,uk(s, a) = 1if and only ifϕ(s, a)lies outside all regions. B.4 BoundingBias-1andBias-2 Unlike in Appendix A, the estimates of all pa... on Pith
  11. [14] H′i ≤1 +ηE[X| H ′]≤1 +ηm≤e ηm. For the second one, letZ≜η (E[X−ηX 2 | H′] −X + ηX 2). As X−ηX 2 is increasing inX∈ [−R, R], it takes values in an interval of length2R, so |Z| ≤2ηR≤ 1/2. Hence, byE[Z| H′] = 0, ev ≤ 1 + v + v2 for |v| ≤1/2, and|X−ηX 2| ≤(5/4)|X|, we have E eZ H′... on Pith
  12. [15] Pk 8m0H(dk + σk) ≤ 32m0HD,800( e− 1)η(ν + 4)H 3m20 ≤θ , and η(ν + 4)H 3 ≤ 1/(200( √ K+ 2 ¯d))by Eq. (65). Combining the bounds and usingν+ 4≤5νproves the claim. B.6 BoundingBonus Finally, as in Appendix A.8, we boundBonustogether with the bonuses used in Lemmas B.15 and B.16. ... on Pith
  13. [16] The indicators that the firstn next states equals′ have mean bPn(s′ |s, a)and sample variance at most nn−1 bPn(s′ |s, a). Hence, applying the empirical Bernstein bound (Maurer and Pontil, 2009, Theorem on Pith
  14. [2022] 21 Introducing Feedback Delays to Non-Delayed Adversarial MDPs Fritz John. Extremum problems with inequalities as subsidiary conditions, studies and essays presented to R. Courant on his 60th birthday, January 8, 1948, on Pith
  15. [2024] Mingyi Li and Taira Tsuchiya. Closing the horizon gap in policy optimization for adversarial MDPs.arXiv preprint arXiv:2610.12362, on PithPith's reviewarXiv
  16. [2025] Yuanhao Wang and Kefan Dong. Refined analysis of FPL for adversarial Markov decision processes.arXiv preprint arXiv:2008.09251, on PithPith's reviewarXiv

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment