Writing study: Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

← ICML 2026 oral writing corpus

Harin Lee, Kevin Jamieson · Official ICML 2026 oral record

Figure, table and section ledger

Editorial contribution type: Theory & formal analysis (primary).

Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.

Canonical PDF: 39 physical pages
Before references / appendix: ≈ 8.27 page-equivalents
Main figures / tables: 2 / 2
Attached appendix figures / tables: 1 / 0
Attached appendix span: ≈ 27.91 page-equivalents

Before references / appendix: ≈ 21.21%References / intervening material: ≈ 7.23%Attached appendix: ≈ 71.56%Estimated layout envelopes, not text/artwork area. Unresolved appendix boundaries remain within the undivided post-body material.

Source-bound correction: Source-checked physical-page text restores wrapped top-level heading labels on pp. 7. Heading starts and measured positions are unchanged; this is label completeness, not a new section. Newly detected unnumbered impact/singular-acknowledgment statements are retained from the size-aware source extraction; authored heading corrections are unchanged.

Section-by-section lengths and source pages

The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.

Top-level heading	Starts on PDF page	Estimated span	Share of entire PDF
1. Introduction	1	≈ 1.24 pp.	3.18%
2. Preliminaries	2	≈ 0.53 pp.	1.36%
3. Problem Setting	3	≈ 1.24 pp.	3.18%
4. Algorithm	4	≈ 1.38 pp.	3.54%
5. Theoretical Guarantees	5	≈ 0.7 pp.	1.79%
6. Regret Lower Bound	6	≈ 0.76 pp.	1.95%
7. Computational Hardness	7	≈ 0.25 pp.	0.64%
8. Proof Sketch: Generalization to MDPs with Partially Known Dynamics	7	≈ 1.45 pp.	3.72%
9. Conclusion	8	≈ 0.34 pp.	0.87%
Impact Statement	9	≈ 0.05 pp.	0.13%
Acknowledgements	9	≈ 0.04 pp.	0.1%
References	9	≈ 2.82 pp.	7.23%
A. Full Algorithms	12	≈ 1.22 pp.	3.13%
B. Proof of Theorem 5	13	≈ 5.3 pp.	13.59%
C. Proofs of Technical Lemmas in Appendix B	18	≈ 7.04 pp.	18.05%
D. Proof of Theorem 3	25	≈ 5.19 pp.	13.31%
E. Proof of Proposition 1	30	≈ 4.55 pp.	11.67%
F. Proofs of Technical Lemmas in Appendices D and E	35	≈ 3.7 pp.	9.49%
G. Auxiliary Lemmas	39	≈ 0.91 pp.	2.33%

All detected figure and table locations

Main text

Attached appendix

Figure 3 · p. 28

Argument and organization

Problem and contribution
Separates delayed observations during policy execution from delayed learning feedback, preventing superficially similar bandit/RL results from serving as invalid comparators.
Argument sequence
The augmented process leads to separate known/unknown-delay bounds, followed by lower bounds and hardness; a later general theorem explains both earlier results as corollaries.
Evidence and verification
The paper distinguishes polynomial statistical regret from exponential computational cost and gives a separate hardness argument rather than implying practical efficiency from sample efficiency.

Problem, claim and contribution

Separates delayed observations during policy execution from delayed learning feedback, preventing superficially similar bandit/RL results from serving as invalid comparators.

Related work and setting, pp. 2-3 · Main paper

Argument and section order

The augmented process leads to separate known/unknown-delay bounds, followed by lower bounds and hardness; a later general theorem explains both earlier results as corollaries.

Sections 4-8, pp. 4-8 · Main paper

Figures, captions and visual explanation

A compact transition diagram colors the known queue update separately from the unknown state transition; adjacent theorem pages explain which delay or branching factor controls each term.

Theorems 1-2, p. 5; Figure 2, p. 7; both PNGs inspected · Main paper

Tables, comparisons and evidence

The paper distinguishes polynomial statistical regret from exponential computational cost and gives a separate hardness argument rather than implying practical efficiency from sample efficiency.

Sections 5-7, pp. 5-7 · Main paper

Appendix and reproducibility

Full update ordering/exception handling is separated from the main informal algorithm; theorem-specific proofs then reduce the delayed setting to the general bound.

Appendix A, p. 12; B.4, pp. 17-18; D, pp. 25-30 · Main paper

Clarity and writing conventions

Discussion paragraphs interpret the bound's terms and say which improved factors arise from familiar bonuses versus the new analysis.

Discussion of Theorems 1-2, p. 5 · Main paper

What to reuse—and what not to infer

Transferable lesson: Explain what each bound term costs, and keep statistical optimality, computational hardness and practical runtime as distinct claims.

Boundary: Minimax optimality is up to logarithmic factors in the specified finite tabular setting; the generalization requires structured partially known dynamics and is not a ready-to-deploy scalable algorithm.

Apply this lesson using the argument and evidence worksheet.

Inspection record and sources

Checked: 2026-10-07
Reading status: Writing-focused manuscript scan + selected visuals inspected
Main text: Writing-focused distributed manuscript scan, not exhaustive technical/proof validation. Sections 1-9, pp. 1-8: execution-delay distinction, augmented process, shared-transition estimator, upper/lower regret bounds, computational hardness and general partially known dynamics abstraction.
Appendix / supplement: Writing-focused appendix scan; code, data and external assets not executed. Appendices A-G, pp. 12-39: complete algorithms, high-probability/optimism/regret proof, hard-instance construction, technical and auxiliary lemmas.
Visually inspected PDF pages: 5, 7

This is a writing-focused scan of the manuscript and the stated supplementary scope: framing, organization, visual explanation, evidence presentation and wording. It is not a line-by-line proof audit, reproduction of results or exhaustive scientific review.

Published ICML 2026 proceedings PDF, PMLR volume 306; retrieved 2026-10-07. Public OpenReview decision notes were not independently reverified. · 39 pages