Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
This work addresses the problem of delayed observations in online reinforcement learning for researchers and practitioners, providing a minimax optimal solution that is incremental but with theoretical guarantees.
The paper tackles reinforcement learning with delayed state observations by proposing an algorithm that combines augmentation and upper confidence bounds, achieving a regret bound of $ ilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})$ and proving its minimax optimality with a matching lower bound.
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.