This problem has been formally termed as Delayed MDP (Katsikopoulos & Engelbrecht, 2003)[1] - the actions generated are not instantly applied to the environment and/or the captured observations are not immediately seen by the agent, as expected in an MDP. The delay can either be:
a) A constant delay - Constant Delayed MDP (CDMDP) (Learning and planning in en-
vironments with delayed feedback, 2008)[2]
- The delay introduced by the environment is constant and known. Like the example you provide in the question.
b) A random delay - Random Delayed MDP
- We don't know what delay to expect, or when the delay will occur. This is more realistic for a real-world case.
TRIED APPROACHES
1. Just ignore the delay
This assumes the CDMDP is an MDP. We then attempt to search for the policy that best ignores the delay
$$
\pi(I_k)={\pi^∗(s)|I_k=(s, a_1,···,a_k)}
$$
$k$ is the number of time-steps between acting on the current state, and receiving feedback. This is simple and can give a reasonable result if the delay is small compared to the state transition magnitude [2].
2. Reconstruct the MDP from the CDMDP (Augmented approach)
The corresponding optimal policy for the reconstructed MDP will then the optimal policy for the CDMDP. This is however made intractable by the size of the action buffer growing with the delay length. It's therefore limited to small constant delays. [1] defines how to do the re-construction.
3. Predicting the delayed observation
This tries to "undelay" the environment by using a predictive model $P$ to approximate what the delayed observation would be, instead of keeping the agent patient to the end of the delay (Learning and planning in envs with delayed feedback, (2008)[5], At Human Speed: Deep RL with action delay, (2018)][6]).
e.g., For a delayed action:
$$
s_{t+i} = P(s_{t + i -1}, a_{t + i - delay})
$$
If the delay is on the observation, the most recent K actions can be used with the most recent observation to approximate the current state[2]. However, this also means the delays are part of the state - it's possible to have a better approach, as next described in the random delays part.
Estimating the current state enables the agent to act conditioned an estimate of the true state, on which the action is executed. The limitation is that it assumes a constant delay.
All the above approaches assume a constant delay
Handling random delays*
4. Partial Trajectory resampling (PTR)
A method that recursively resamples actions in the buffer, replacing them with on-policy actions. It uses the delay dynamics to simulate their effect on the current policy.
If random delays exist on an MDP, some actions present in the off-policy replay buffer will not influence the later delayed observations and rewards, for a number of timesteps. This will allow generation of on-policy sub-trajectories from the off-policy samples by recursively resampling the most recent actions from the action buffer. It will not invalidate the sub-trajectory.
The resampled action will be valid as long as the observation delay $\omega$ and the action delay $\alpha$ are both greater than the current time step $t$ i.e., No delayed observation depends on a resampled action.
$$
\omega_t + \alpha_t >= t
$$
Illustration of PTR, (3)
The benefits of this method:
Allows discarding of outdated information. e.g If the delay is such that the are no observations for $5$ timesteps, which then all arrive at step $5$, we can safely discard the transitions of steps $(1,2, 3,4)$. This is because this info will be compressed in the most recent observation.
Provides information on the "age" of an observation and the actions applied next
Efficient credit assignment
These factors give partial trajectory resampling better performance compared to concatenating the past $K$ actions with the most recent observation to estimate the current delayed state.
RL with random delays (2020)[3] describes and applies Partial Trajectory Resampling in RL. It's the only work I've managed to come across that handles both random and constant delayed MDPs.
What of the reward delay?
Reward delay, in this context, is referring to the rewards attributed to a delayed observation and action.
A solution to a delayed MDP will involve tackling the credit assignment problem. In this case, this is deciding what to do with the delayed rewards and how to give credit to the delayed actions and states.
This has had different approaches. For instance:
" ...we chose to accumulate the rewards corresponding to the [excessively delayed transitions we drop]. When an observation gets repeated
because no new observation is available, the corresponding reward is 0, and when a new observation arrives, the corresponding reward contains the sum of intermediate rewards in lost [dropped] transitions." [3]
Real time sample efficint RL for robots, (2013)[9] on the other hand, uses a decision tree to assign credit to an MDP reconstructed from a CMDP. The tree learns which delayed actions are relevant.
Related reads:
- Real-time Reinforcement Learning (2019)
- Thinking while moving: Deep reinforcement learning with concurrent control, (2020)