Despite being of practical importance, there is limited literature on stochastically delayed feedback in RL. Previous work has considered constant delays in observing the current state in an MDP [1]}. However, the challenges in this setting are somewhat different to that of delayed feedback. More recently, [2]} considered delayed feedback in adversarial MDPs. They consider adversarial delays and develop algorithms based on policy optimisation whose regret depends on the sum of the delays, the number of states and the number of steps per episode. For stochastic MDPs and adversarial delays, they also state that the regret will be increased by an additive term in the regret bound of order: \(H^4 SA \tau _{\max }\)  when all delays are less than \(\tau _{\max }\)  almost surely. In our paper, we consider stochastic delays and show that it is only the expected delay, which is often considerably smaller than the maximal delay, that impacts the regret.
