Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

Summary

The paper studies online reinforcement learning in finite-horizon tabular MDPs when the agent observes each state only after a stochastic delay of at most $D_{\max}$ steps. The authors propose MVP-Delayed, a UCBVI-style algorithm that (i) reduces the SDMDP to a delay-free augmented MDP whose state carries the last-observed state, the queue of pending actions, and a residual delay counter, and (ii) runs MVP on that augmented MDP with a variance-dependent bonus tuned to a $D \wedge b$ log factor. They prove a high-probability regret bound of $\tilde O(H\sqrt{D_{\max} SAK})$ for both known and unknown delay distributions, an $H^{1/2} D_{\max}^2$ improvement over Chen et al. (2023). The core methodological move is the abstraction of the augmented MDP into a new "MDPs with partially known dynamics" model (Theorem 5), in which the marginal transition of one component of the state is fully known and the unknown component is governed by a low-cardinality effective feature $z \in Z_\mathrm{eff}$; the delayed-MDP results then fall out as corollaries. On the lower-bound side, the authors design a "CodeMDP" whose learning complexity provably scales with the delay length, reduce it to an $\ell_1$-norm estimation problem, and prove an $\Omega(H\sqrt{\tilde D SAK/\log \tilde D})$ bound (Theorem 3), establishing that $D_{\max}^{1/2}$ is the correct dependence and that shorter delays genuinely reduce statistical complexity. A companion NP-hardness argument via UMDPs justifies the exponential $D_{\max}$-dependence in runtime. The contribution is substantive and closes a real gap in a well-motivated setting; the "partially known dynamics" abstraction is a clean idea that should be reusable beyond delayed observations. The main conceptual limitations are that (a) the model definition (clipping in Assumption 1, $\Delta = -1$ in Remark 1) generalizes prior work in ways that are not tracked through the augmentation and sufficiency arguments, (b) the matching-bound claim understates a residual $\log D_{\max}$ gap coming from Proposition 1, and (c) reconstructing the algorithm from the pseudocode surfaces two boundary-handling gaps that the main text finesses — the deferred clip-at-zero correction to $P_\mathrm{tran}$ and an off-by-one between Algorithm 4's table bounds and Algorithm 5's $\text{len}(\mathbf a)=D_{\max}+1$ branch — that a careful reimplementer will have to patch to get an SDMDP-equivalent augmented model.

Strengths

• Conceptual contribution. The "MDPs with partially known dynamics" abstraction (Definition 1, Assumption 2, Theorem 5) is a clean generalization: the state factors as $S = X \times Y$, the $Y$-marginal is known, and the unknown conditional $P_X$ lies in a tabular class indexed by a feature map $\phi_Z$. The SDMDP results then follow via specific choices of $X, Y, Z_\mathrm{eff}$, cleanly separating the delay-specific bookkeeping from the statistical analysis and setting up a template that should be reusable in other structured-transition settings.
• Closes a real gap. The $\tilde O(H\sqrt{D_{\max} SAK})$ upper bound is a factor of $H^{1/2} D_{\max}^2$ tighter than Chen et al. (2023), with the improvement cleanly attributed to variance-dependent bonuses ($H^{1/2}$) and the new union-bound-over-$Z_\mathrm{eff}$ argument ($D_{\max}^2$).
• Matching lower bound via a bespoke hard instance. The CodeMDP construction, its reduction to an $\ell_1$-norm estimation problem (Proposition 1), and the tree-plus-CodeMDP composition (Appendix D.2) together produce a lower bound whose $\tilde D^{1/2}$ exponent matches the upper bound and whose derivation makes the mechanism transparent. Proposition 1 is a nice standalone result whose $d/(\varepsilon^2 \log d)$ scaling reproduces with the paper's constants ($1152, 48$) verbatim.
• Recovery of the $B \wedge D_{\max}$ dependence. The observation that the delay dependence can be replaced by the (possibly smaller) branching factor $B$ — because the exponent in the union bound is set by the support size of the true transition, not the number of augmented states — is a genuinely useful refinement, and Remark 2 extends it to a problem-dependent form without requiring knowledge of individual $D_{\max}(s,a)$ values. A closed-form evaluation confirms the leading term is bit-for-bit constant across $D_{\max} \ge B$.
• Optimism property holds numerically. A reconstruction of Algorithm 3 on a small partially-known-dynamics instance never violates $V^k_h(s) \ge V^*_h(s)$ across $192{,}000$ (episode, $h$, state) comparisons, with genuine margin — a modest but non-trivial check that the coded update actually inherits Lemma 6.
• Honest computational-hardness discussion. Section 7 acknowledges the exponential state blowup and grounds it in a classical UMDP hardness result, so the reader is not led to expect a polynomial-time algorithm.

Weaknesses

• Well-definedness of the delay model under clipping. Assumption 1's clipping of $D_h$ interacts with the reveal rule "$s_{h+1}$ is revealed at step $h+1+D_h$" in a way the paper does not address. When the clip is active at step $h-1$ and inactive at step $h$, $h+1+D_h$ can be smaller than $h + D_{h-1}$, which would place a later state ahead of an earlier one in the reveal order. The paper does not establish that revelations always arrive in the natural order, and clipping is precisely one of the generalizations of the prior work whose sufficiency argument is inherited by citation.
• Sufficiency claim is not fully justified for the generalized model. The three-element sufficiency for optimal action is cited to Katsikopoulos & Engelbrecht (2003), whose model does not include clipping or $\Delta = -1$. The authors themselves note that raw $\Delta_h$ values may be lost under clipping (which is why $\Delta_1, \ldots, \Delta_H$ must be revealed at the end of the episode in the unknown-$P_\mathrm{delay}$ case). A direct sufficiency argument for the generalized dynamics — or a citation that covers them — would strengthen the foundation of Sections 4 and 8.
• $P_\mathrm{tran}$ boundary correction is deferred, and it is load-bearing. The main-text definition of $P_\mathrm{tran}$ omits the correction that forces revelation at $D_{\max}$ and at episode termination. Because the entire regret bound depends on $D_{\max}$, the perturbation at the clipping boundary is not a cosmetic detail. Appendix B.4 restores it via the last coordinate $\in \{\emptyset, 0, 1\}$ of $Z_\mathrm{eff}$, but the reader must reconcile that with the definition in Section 4.1.
• Augmented-MDP equivalence is asserted, not shown. The augmented MDP is stated to have horizon $H$ despite introducing zero-action Category 2/3 intermediate transitions (multiple such transitions can occur within a single SDMDP step when $\Delta = -1$). The trajectory-length bookkeeping and the value-function equivalence are left implicit; a short equivalence lemma would remove the gap.
• Log-$D_{\max}$ gap in the matching bounds. Theorem 3 has an explicit $(\log \tilde D)^{-1}$ factor traceable to Proposition 1's $d/(\varepsilon^2 \log d)$ scaling, but Theorem 1 has no compensating $\log D_{\max}$ in the numerator. The bounds are therefore tight in the exponent of $D_{\max}$ but leave a genuine $\log D_{\max}$ gap that is not absorbed by the standard $\mathrm{polylog}(HSAK)$ tolerance. The abstract's "matching lower bound up to logarithmic factors" understates this.
• Computational-hardness phrasing is stronger than the cited result. "Strictly harder than 3-SAT" would require a separation that Theorem 4 does not provide, and "the exponential time complexity of Algorithm 1 is the best we can hope for" needs the standard $\mathrm P \ne \mathrm{NP}$ hedge and applies at $D_{\max} = H$ rather than uniformly in $D_{\max}$.
• Constant chain in the lower-bound derivation. In the proof of Theorem 3 the goal is written with a $128$ constant but the conclusion uses $192$, and the intermediate arithmetic reconciling them is not shown. Similarly, the substitution $\varepsilon^2 = D_{\max} SA/(96K \log \tilde D)$ into $n = \tilde D \lceil \log_2 \tilde D \rceil / (2\varepsilon^2)$ is claimed to yield $n = 48K/(SA)$, which appears to require a $\log \tilde D$ cancellation that is not spelled out.
• Model bookkeeping ambiguities. The subscript in $\tilde\Delta_h = h - (t_h + D_{t_h - 1})$ reads ambiguously between $D_{t_h - 1}$ and $D_{t_h} - 1$; under clipping these differ. The a priori relationship between $\Delta_{\max}$ and $D_{\max}$ is never stated (relevant to comparing the $\sqrt{\Delta_{\max} SAK}$ and $\sqrt{D_{\max} SAK}$ terms of Theorem 2). Table 2's simultaneous reveal of $s_3, s_4$ at $h = 6$ is asserted via the caption but is nontrivial to check against the tabulated $D_{t_h}$ values, and the $\tilde\Delta_h$ entry at the $s_3$ reveal appears inconsistent with the paper's own definition ($6 - 3 - 3 = 0$ versus the tabulated $-1$).
• Interpretability of the $\Delta_{\max} \le B$ condition. The claim that Theorem 2 also meets the lower bound when $\Delta_{\max} \le B$ is stated without any indication of why the maximum inter-arrival increment should be compared to the transition branching factor.
• "$s_0$ visited at most once" assumption reads as an imposed restriction. In the proof of Theorem 3 this property holds structurally from the tree construction; leaving it as an assumption invites the reader to view the lower bound as conditional on an ad hoc restriction of the adversary's power.

Reproducibility & code

• No reference implementation released, and the pseudocode has two boundary gaps. MVP-Delayed (Algorithms 1 and 4) and Q-Estimate (Algorithm 5) are only described in pseudocode; no code accompanies the paper. Reconstructing the algorithm surfaces two documentation issues that a working implementation cannot avoid: (i) $P_\mathrm{tran}$ requires the deferred clip-at-zero correction — using the printed formula makes Section 4.1's augmented MDP disagree with SDMDP rollouts by $\sim 30$ standard errors whenever $\Delta_{\min} = -1$ and $\Delta_{\max} \ge 1$, while adding the correction restores agreement to within $\pm 1.2$ standard errors — and (ii) Algorithm 5's boundary check triggers on queues of length $D_{\max} + 1$, but Algorithm 4's Category 2/3 update loop only tabulates $V^k(s, \mathbf a, \texttt{tran}, h)$ for $D = 1, \ldots, D_{\max}$, so a strict-pseudocode implementation dereferences an uninitialized entry.
• Elided $Z_\mathrm{eff}$ exceptional cases pushed into the appendix. Section 8.3 states "we omit this detail for brevity" for the exceptional cases (termination, truncation) in $Z_\mathrm{eff}$; the proof of Theorem 2 in Appendix B.4 makes it concrete as $S \times A \times \mathcal D \times \{\emptyset, 0, 1\}$. Combined with the deferred $P_\mathrm{tran}$ correction, an implementer working from the main text cannot reconstruct the boundary behaviour the analysis relies on. Moving the concrete $Z_\mathrm{eff}$ into Section 8 (or an explicit forward reference) would remove this friction.
• $\sqrt{D_{\max}}$ and $\sqrt{K}$ scaling not observable at moderate compute budgets. The paper is theoretical and does not claim experiments, but the leading constants in MVP's Bernstein bonus ($c_2 = 400/9$) keep the bonus above 1 until $N(s,a) \gtrsim 5{,}400$, so on typical toy CDMDPs the learner needs $K \sim 10^5$–$10^6$ per delay cell to leave the pre-asymptotic plateau. Measured cumulative regret grows near-linearly in $K$ at $K = 10^4$ (log-log slope $\approx 0.91$), and log-log regret against $D_{\max}$ at $H=28$, $B=10$, 10 seeds is flat ($-0.007 \pm 0.19$), with the predicted $0.5$ excluded at $\sim 2.7\sigma$. This is a resource limitation rather than a failure of the theorem, but the headline claim would be substantially more convincing with a toy-CDMDP experiment sized to actually resolve the rate.
• Semantics of the last $Z_\mathrm{eff}$ coordinate are easy to invert. The sentence "If the last variable is 0 or 1 in the latter case, then $P_\mathrm{tran}$ is replaced by 0 or 1, respectively" reads coherently under one interpretation and inverts under another; a small table (coordinate value $\to$ $P_\mathrm{tran}$ replacement $\to$ semantics) would prevent the confusion.

Recommended Changes

Essential

• State the boundary-corrected $P_\mathrm{tran}$ (and the concrete $Z_\mathrm{eff}$) in the main text. Fold the currently-deferred clipping and termination corrections into Section 4.1's definition of $P_\mathrm{tran}$, and move the $S \times A \times \mathcal D \times \{\emptyset, 0, 1\}$ form of $Z_\mathrm{eff}$ (with its case split) into Section 8. This addresses both the "deferred $P_\mathrm{tran}$ correction" weakness and the corresponding reproducibility gap that makes Section 4.1's equivalence claim fail when taken literally.
• Align Algorithm 4's table bounds with Algorithm 5's boundary check. Either extend Algorithm 4's Category 2/3 update loop to $D = 1, \ldots, D_{\max} + 1$, or restrict Algorithm 5's len(a) = D_max + 1 branch to a strictly reachable case and prove the entry-time invariant that makes it consistent with the tabulated states. This addresses the "Algorithm 5's $D_{\max}+1$ branch is not tabulated" reproducibility issue.
• Establish well-definedness of the reveal order under clipping. In Section 3, add an invariant (with short proof) that revelations arrive in the natural order under Assumption 1, or explicitly describe how the algorithm handles out-of-order reveals. This addresses the "well-definedness under clipping" weakness.
• Justify three-element sufficiency for the generalized model. Either supply a direct sufficiency argument for the $(s_{t_h}, \mathbf a, \tilde\Delta_h)$ representation under clipping and $\Delta = -1$, or replace the citation with one that covers the generalized dynamics. This addresses the "sufficiency claim" weakness.
• Add an equivalence lemma for the augmented MDP. Provide a short lemma showing that SDMDP trajectories map bijectively to length-$H$ (action-consuming) augmented trajectories with equal cumulative rewards, addressing the "augmented-MDP equivalence" weakness.
• Qualify the "matching lower bound" and "optimality" claims. In the abstract and in the discussion following Theorem 3, replace "optimality" / "matching up to logarithmic factors" with a statement that makes the residual $\log D_{\max}$ gap explicit, addressing the "log-$D_{\max}$ gap" weakness.
• Reconcile the $128 \to 192$ constant chain and the $\varepsilon/n$ substitution in the proof of Theorem 3. Either correct one of the constants or add the intermediate arithmetic that makes $\alpha + 128\varepsilon H / \log \tilde D$ consistent with $\alpha + 192\varepsilon H / \log \tilde D$ and $n = 48K/(SA)$, addressing the "constant chain" weakness.
• Soften the computational-hardness phrasing. Replace "strictly harder than 3-SAT" with "at least as hard as 3-SAT" and add the $\mathrm P \ne \mathrm{NP}$ caveat to "the best we can hope for", addressing the "computational-hardness phrasing" weakness.

Suggested

• Release a reference implementation of Algorithms 4 and 5. A single-file Python implementation with one CDMDP smoke test would resolve the "no reference implementation" reproducibility issue and would make the two boundary gaps above visible from the paper.
• Add a toy-CDMDP experiment sized to actually observe the rates. Given the leading-constant analysis, a run with $K \sim 10^5$–$10^6$ per delay cell (small $S, A$) would empirically corroborate the $\sqrt{D_{\max}}$ scaling and support the claimed factor-$D_{\max}^2$ improvement over Chen et al. (2023), addressing the "scaling not observable at moderate budgets" reproducibility issue.
• Explain the $\Delta_{\max} \le B$ tightness condition. Add a one-line justification that the $H\sqrt{\Delta_{\max} SAK}$ term is dominated when $\Delta_{\max} \le B$, addressing the "interpretability of $\Delta_{\max} \le B$" weakness.
• Clean up notation. Typeset $D_{t_h - 1}$ with explicit subscript braces; state the relationship between $\Delta_{\max}$ and $D_{\max}$ at the top of Section 3; use $\tilde D$ consistently in the statement of Theorem 3; and walk through one row of Table 2 explicitly (in particular, reconcile the $\tilde\Delta_h$ entry at the $s_3$ reveal with the definition $\tilde\Delta_h = h - t_h - D_{t_h-1}$). These address the "model bookkeeping ambiguities" weakness.
• Present the last $Z_\mathrm{eff}$ coordinate as a small table (coordinate value $\to$ effective $P_\mathrm{tran}$ $\to$ semantic meaning), addressing the corresponding reproducibility point.
• Tie the "$s_0$ visited at most once" assumption to the tree construction. One sentence noting that this holds structurally rather than as an imposed restriction removes the concern that the lower bound is conditional on an ad hoc adversary restriction.