Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

Harin Lee; Kevin Jamieson

cs.LGMar 3, 2026

Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

Authors: Harin Lee, Kevin Jamieson

Organizations: Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, Washington.

Abstract

We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps. We propose an algorithm that combines the augmentation method and the upper confidence bound approach. For tabular Markov decision processes (MDPs), we derive a regret bound of $\tilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})$ , where $S$ and $A$ are the cardinalities of the state and action spaces, $H$ is the time horizon, $K$ is the number of episodes, and $D_{\max}$ is the maximum length of the delay. We also provide a matching lower bound up to logarithmic factors, showing the optimality of our approach. Our analytical framework formulates this problem as a special case of a broader class of MDPs, where their transition dynamics decompose into a known component and an unknown but structured component. We establish general results for this abstract setting, which may be of independent interest.

Figures & tables

$h$	$s_{t_{h}}$	$\mathbf{a}$	$\widetilde{\Delta}_{h}$	$\Delta_{t_{h}}$	$D_{t_{h}}$
1	$s_{1}$	$\emptyset$	0	2	2
2	$s_{1}$	$(a_{1})$	1	-	-
3	$s_{1}$	$(a_{1},a_{2})$	2	-	-
4	$s_{2}$	$(a_{2},a_{3})$	0	0	2
5	$s_{3}$	$(a_{3},a_{4})$	0	0	2
6	$s_{4}$	$(a_{4},a_{5})$	0	0	2

Table 1: Example trajectory of a CDMDP with

H=6

and constant delay

2

. Each column denotes the time step

h

, the last observed state

s_{t_{h}}

, the action queue

\mathbf{a}

, the inter-arrival time counter

\widetilde{\Delta}_{h}

, the inter-arrival time

\Delta_{t_{h}}

, and the total delay

D_{t_{h}}

. Note that a new state is observed when

\widetilde{\Delta}_{h}

is equal to

\Delta_{t_{h}}

, or equivalently, when the length of the queue

\texttt{len}(\mathbf{a})

is equal to

D_{t_{h}}

$h$	$s_{t_{h}}$	$\mathbf{a}$	$\widetilde{\Delta}_{h}$	$\Delta_{t_{h}}$	$D_{t_{h}}$
1	$s_{1}$	$\emptyset$	0	1	1
2	$s_{1}$	$(a_{1})$	1	-	-
3	$s_{2}$	$(a_{2})$	0	2	3
4	$s_{2}$	$(a_{2},a_{3})$	1	-	-
5	$s_{2}$	$(a_{2},a_{3},a_{4})$	2	-	-
6	$s_{3}$	$(a_{3},a_{4},a_{5})$	(-1)	-1	2

Table 2: Example trajectory of an SDMDP with

H=6

with one possible realization of delays. Refer to Table 1 for the description of each column. States

s_{3}

and

s_{4}

are revealed at the same time step

h=6

because

\Delta_{3}=-1

Panel of Figure 1 — Figure 1: Illustration of the transition of the augmented MDP after taking one action. Gray states indicates intermediate states that have no actions. Straight lines represents the agent’s action and dotted lines represents augmented state transitions. $p_{t_{h},\widetilde{\Delta}}$ is shorthand for $P_{\mathtt{tran}}(s_{t_{h}},a_{t_{h}},\widetilde{\Delta})$ and $p_{t_{h}+1,-1}$ is shorthand for $P_{\mathtt{tran}}(s_{t_{h}+1},a_{t_{h}+1},-1)$ , where they show the probability of the transition.

Panel of Figure 2 — Figure 2: Illustration of core properties of the augmented MDP’s state transition. Consider a transition accompanied by an augmented state-action pair of $((s_{t_{h}};a_{t_{h}},\ldots,a_{h-1}),a_{h})$ . The orange-shaded part indicates that the transition dynamics for the action queue are known, which is simply shifting from the previous action queue. The blue-shaded part indicates that the unknown part of the state transition is determined only by $(s_{t_{h}},a_{t_{h}})$ and is irrelevant of the other part of the augmented state-action pair.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Illustration of hard instances for Theorem 3 . The structure consists of a tree structure (top) and a CodeMDP (bottom). The leaf states are labeled $l_{1},l_{2},l_{3},l_{4}$ . Each leaf state and action pair has its own probability distribution over the states in the CodeMDP. Once the agent takes an action from the leaf state, it must make $\widetilde{D}$ actions without observing which state it has landed in. The agent enters the success state $s_{\mathrm{succ}}$ if it landed at state $(i,b)$ and the $i$ -th out of $\widetilde{D}$ actions is $b$ , and it receives the reward. The agent enters the fail state $s_{\mathrm{fail}}$ if it landed at state $(i,b)$ and the $i$ -th out of $\widetilde{D}$ actions is not $b$ , and it cannot receive any reward.

Delayed RL

See all 13 papers

Diffusion-Guided Uncertainty-Aware Delayed Policy Optimization
Jul 6, 2026Junqi Tu, Zejiao Liu, Fangfei Li +1Reinforcement Learning Robotic RL
The Key Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai, China · The School of Mathematics, East China University of Science and Technology, Shanghai, China
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Mar 25, 2026Guy Zamir, Matthew Zurek, Yudong ChenRegret Minimization in RL Average-Reward RL
Department of Computer Sciences, University of Wisconsin–Madison
Delayed homomorphic reinforcement learning for environments with delayed feedback
Apr 4, 2026Jongsoo Lee, Jangwon Kim, Soohee HanDelayed RL Reinforcement Learning
Department of Convergence IT Engineering, POSTECH, Pohang, 37673, South Korea · Department of Electrical Engineering, POSTECH, Pohang, 37673, South Korea

Jul 6, 2026J/K move · Enter open · S save

Diffusion-Guided Uncertainty-Aware Delayed Policy Optimization

Junqi Tu, Zejiao Liu, Fangfei Li, Yang Tang

The Key Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai, China · The School of Mathematics, East China University of Science and Technology, Shanghai, China

Reinforcement Learning Robotic RL Delayed RL

Open paper AskPDF arXiv

Reinforcement learning in real world environments often suffers from severe performance degradation due to delayed feedback. Existing approaches typically mitigate performance degradation caused by observation delays by constructing augmented states or predicting the true states. However, these methods often overlook the inherent discrepancy between delayed state and true states induced by stochastic MDP. We theoretically prove the existence of such a discrepancy and show that it leads to the degradation of the optimal policy. To address this challenge, we propose Diffusion Guided Uncertainty Aware Delayed Policy Optimization (DUPO). Our method explicitly models the relationship between delayed state message and the current state using a diffusion model, and leverages the resulting discrepancy estimates to weight delayed policies. Extensive experiments on continuous robotic control tasks with multiple stochastic delays demonstrate that DUPO consistently outperforms existing methods and remains effective even under long and random delay scenarios.

Abstract

Delayed RL

Explore similar work

Diffusion-Guided Uncertainty-Aware Delayed Policy Optimization

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Delayed homomorphic reinforcement learning for environments with delayed feedback