Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

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.

This research studies how to make good decisions even when the necessary information is delivered with delays. Taking autonomous driving as an example, a self-driving car experiences delays between sensing its surroundings and steering the vehicle. Delays that are unavoidable no matter how quickly the agent makes decisions also arise in communication networks, robotics, healthcare, and online advertising. We develop a mathematical framework for decision-making problems under delayed observations that can be applied across a wide variety of settings. We propose a strategy for how an AI agent should act in these settings and prove that it achieves a guaranteed level of performance. Moreover, we show that this guarantee is the best possible performance that any strategy can achieve. By these results, we answer the question of how observational delays affect the difficulty of decision-making problems. While it was known that delays affect decision-making by limiting the available strategies, our results additionally reveal that they slow down collecting the relevant information.