{"id":"b95b0e27-11bb-44f1-ba95-3d2f582065d0","arxiv_id":"2611.17214","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A rejection-sampling trick that evaluates a policy from future episodes yields sqrt(SAK) regret for tabular adversarial MDPs and the first efficient sqrt(K) regret for linear AMDPs, with high probability.","lead":"A new technique called introduced feedback delays evaluates each policy using future episodes while the policy keeps updating, yielding near-optimal regret bounds for tabular and linear adversarial MDPs. If correct, this closes a six-year gap in state dependence and gives the first computationally efficient sqrt(K) algorithm for linear AMDPs without simulators.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"No significant objection identified","rationale":"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.","tokens_in":73371,"tokens_out":392,"duration_ms":8838,"concrete_test":"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.","verdict_should_be":"UNCHANGED","load_bearing_attack":"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.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"This paper studies episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback, in both tabular and linear function-approximation settings. The central proposal is \"introduced feedback delays\": rather than estimating the current policy's Q-function from past data or freezing the policy to collect future samples, the algorithms evaluate each policy on future episodes while continuing to update the policy, treating the feedback as if it were delayed. Technically, the paper develops Geometric Resampling with Rejection (GRR) for tabular inverse visitation probabilities and Matrix Geometric Resampling with Rejection (MGRR) with feature-region thresholding for linear inverse covariance matrices. The stated results are: a tabular regret bound of \\tilde O(H^{5/2}\\sqrt{SAK}+H^4S^2A) with probability 1-\\delta (Theorem 4.1), matching the lower bound in S, A, and K; a linear regret bound of \\tilde O(d^3H^4\\sqrt K) (Theorem 5.1), described as the first computationally efficient high-probability bound optimal in K without simulators or exploratory assumptions; and delayed-feedback extensions with overheads \\tilde O(H^3\\sqrt D) and \\tilde O(d^{3/2}H^3\\sqrt D) (Theorems 6.1 and 6.2). The main text provides proof sketches, and the supplementary material contains the full lemma chain and parameter choices.","tokens_in":74626,"tokens_out":936,"duration_ms":86759,"significance":"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 6, Appendix A.1 and B.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Sections 2.1 and 2.2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Footnote 1 and Table 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 3.2, Eq. (13)","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"accept"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"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.\n\nThe 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.\n\nSoft 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 H^{5/2} versus lower bound H; linear d^3 H^4 versus d H^{3/2}), and the paper says so. None of this undermines the central claims.\n\nWho 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.","headline":"Strong, self-contained theory paper that plausibly closes two open AMDP gaps; it deserves serious refereeing.","tokens_in":74229,"tokens_out":2099,"duration_ms":21080},"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"Voluntarily delayed feedback closes the square-root S and K gaps in adversarial MDPs.","keywords":["adversarial MDP","regret minimization","bandit feedback","unknown transitions","tabular MDP","linear MDP","delayed feedback","geometric resampling"],"falsifier":"Run Algorithm 1 on a constructed episodic AMDP where the adversary switches the optimal policy between two distinct actions every other episode; if the observed regret grows linearly in the number of episodes instead of scaling as sqrt(SAK), the likelihood-ratio bound must have been violated.","tokens_in":76372,"feed_emoji":"","tokens_out":2796,"duration_ms":86635,"temperature":0.7,"pith_summary":"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.","feed_headline":"Deliberate delays close long-standing gaps in adversarial MDPs","feed_subtitle":"By voluntarily introducing feedback delays, algorithms achieve optimal sqrt(S) and sqrt(K) regret in tabular and linear AMDPs.","key_machinery":"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_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Established the best known regret bound eO(HS sqrt(AK)) for tabular AMDPs with unknown transitions and bandit feedback, and posed the open problem of closing the sqrt(S) gap that this paper resolves.","marker":"[Jin et al., 2020a]"},{"why":"Provided the best known computationally efficient algorithm for linear AMDPs with regret eO(K^{14/15}), which this paper improves to eO(sqrt(K)).","marker":"[Luo et al., 2021]"},{"why":"Achieved eO(d^{3/2} H^3 K^{3/4}) regret for linear AMDPs with an efficient algorithm, the previous best before this paper, and also showed that eO(sqrt(K)) regret is achievable inefficiently.","marker":"[Liu et al., 2024]"},{"why":"Introduced Geometric Resampling, which the paper extends with rejection sampling to handle changing policies.","marker":"[Neu and Bartók, 2016]"},{"why":"Introduced Matrix Geometric Resampling, which the paper extends with rejection sampling for linear AMDPs.","marker":"[Neu and Olkhovskaya, 2020]"},{"why":"Established the Omega(H sqrt(SAK)) lower bound for tabular AMDPs that this paper matches.","marker":"[Jin et al., 2018]"},{"why":"Established the Omega(d H^{3/2} sqrt(K)) lower bound for linear AMDPs that this paper matches in K.","marker":"[Zhou et al., 2021]"}],"fun_headline_variants":["Voluntary feedback delays yield optimal regret in adversarial MDPs","Self-imposed delays close open regret gaps in tabular and linear AMDPs","Feigned feedback delays achieve optimal sqrt S and sqrt K regret","Deliberate feedback delays resolve AMDP regret gaps in S and K"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Voluntary feedback delays yield optimal regret in adversarial MDPs","Self-imposed delays close open regret gaps in tabular and linear AMDPs","Feigned feedback delays achieve optimal sqrt S and sqrt K regret","Deliberate feedback delays resolve AMDP regret gaps in S and K"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000142,"raw_usage":{"cost":0.0001420692,"is_byok":false,"cost_details":{"upstream_inference_cost":0.0001420692,"upstream_inference_prompt_cost":3.81472e-05,"upstream_inference_completions_cost":0.000103922},"total_tokens":1735,"prompt_tokens":1164,"completion_tokens":571,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":931,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":505}},"tokens_in":1164,"tokens_out":571,"cost_source":"openrouter_usage","duration_ms":7590,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":505,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T09:15:41.352913+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Run Algorithm 1 on a constructed episodic AMDP where the adversary switches the optimal policy between two distinct actions every other episode; if the observed regret grows linearly in the number of episodes instead of scaling as sqrt(SAK), the likelihood-ratio bound must have been violated.","supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}