How to deal with the time delay in reinforcement learning?

Question

I have a question regarding the time delay in reinforcement learning (RL).

In the RL, one has state, reward and action. It is usually assumed that (as far as I understand it) when the action is executed on the system, the state changes immediately and that the new state can then be analysed (influencing the reward) to determine the next action. However, what if there is a time delay in this process. For example, when some action is executed at time $t_1$, we can only get its effect on the system at $t_2$ (You can imagine a flow: the actuator is in the upstream region and the sensor is in the downstream region, so that there will be a time delay between the action and the state). How do we deal with this time delay in RL?

Answer 1

Most RL algorithms assume a discretization of time (although RL can also be applied to continuous-time problems [1]), i.e., in theory, it doesn't really matter what the actual time between consecutive time steps is, but, in practice, you may have delays in the rewards or observations, so you cannot perform e.g. the TD updates immediately. One natural solution to your problem would be to keep track (e.g. in a buffer) of the reward obtained and the next state that the agent ended up in after having taken a certain action in a certain state, or use some kind of synchronization mechanism (note that I've just come up with these solutions, so I don't know if this has been done or not to solve problems). In practice, this may not work (in all cases), for example, during real-time inference, where you need to decide quickly what you need to do even without full information about the current state or reward.

Note that, in RL, rewards are often said to be delayed, in the sense that

1. you may know the consequences of an action only many time-steps after you have taken it (determining the consequences of an action is known as the credit assignment problem), or
2. you may get a non-zero reward only when the agent gets to a goal/final state (in this last case, these rewards are also known as sparse).

These two problems are common in RL. However, if I understand correctly your concerns, this is a bit different than your problem, because your problem also involves the potential delay of the state or even reward that was supposed to arrive at a previous time step, which can be due e.g. to an erratic or broken sensor/actuator. For instance, if you are using DQN, which typically builds an approximation of the current state by concatenating the last frames captured by your camera, if you have delays in the frames that cause the natural order of the frames to be changed, this could lead to a bad approximation of the current state, which could actually lead to a catastrophic event. So, yes, this is an important problem that needs to be tackled.

Given that I am not really familiar with the actual existing solutions, I'll refer you to the paper Challenges of Real-World Reinforcement Learning that I read a few weeks ago, which mentions this issue and points you to other research work that attempted to address it. Take a look at this answer too, if you're more interested in delayed/sparse rewards.

Answer 2

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:

1. 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.

2. Provides information on the "age" of an observation and the actions applied next

3. 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:

1. Real-time Reinforcement Learning (2019)
2. Thinking while moving: Deep reinforcement learning with concurrent control, (2020)