Reinforcement Learning with Random Delays

1 INTRODUCTION

• Action and observation delays are common in real-world reinforcement learning, but prior work mainly assumed constant delays.Earlier planning methods attempted to undelay the environment by simulating future observations.Source: §1 · p. 1
• The paper studies random-delay environment structure and uses hindsight resampling of trajectory fragments to enable off-policy multi-step value estimation.It derives DCAC from Soft Actor-Critic and reports improved performance in delayed environments.Source: §1 · p. 1
• The authors release code that includes a wrapper for adding custom delays to OpenAI Gym environments.Source: §1 · p. 1

2 DELAYED ENVIRONMENTS

• The setting separates random action and observation communication delays from the underlying undelayed environment.At each time-step the agent computes from its most recent available observation while the latest delayed action is applied.Source: §2 · p. 1
• For a delayed observation, observation delay counts elapsed steps before use, action delay tracks the influencing action’s timing, and total delay is their sum.Source: §2 · p. 2
• Using only the last received observation breaks the Markov assumption when delay exceeds one step, motivating a model that includes communication dynamics.The motivating WiFi-delay dataset was collected between a decision-making computer and a flying robot.Source: §2 · p. 2

2.1 RANDOM DELAY MARKOV DECISION PROCESSES

• A Markov state requires at least the last K sent actions alongside the delayed observation, where K is the combined maximum action and observation delay.Including delays in the state can represent self-correlated delays and provide information useful for credit assignment and partial trajectory resampling.Source: §2.1 · p. 2
• The RDMDP augments the state with a delayed observation, an action buffer, and action and observation delays, with transitions modeling delay evolution, buffer updates, and environment outcomes.The action buffer stores the last K sent actions, with the most recent action first.Source: §2.1 · pp. 2–3
• The RDMDP transition construction uses discrete delay distributions and accumulates intermediate rewards when observations are skipped or repeated.Constant action and observation delays reduce the RDMDP to the Constantly Delayed MDP described by Walsh et al. (2008).Source: §2.1 · p. 3

3 REINFORCEMENT LEARNING IN DELAYED ENVIRONMENTS

• On-policy multi-step rollouts address delayed credit assignment, but their sample inefficiency motivates reusing old samples through off-policy methods.Conventional off-policy backups can use outdated action buffers, so the section leverages known delay dynamics to transform trajectory fragments.Source: §3 · p. 3

3.1 PARTIAL TRAJECTORY RESAMPLING IN DELAYED ENVIRONMENTS

• Partial trajectory resampling updates action buffers under the current policy while leaving other trajectory elements unchanged, provided resampled actions do not influence delayed observations.When resampled actions are delayed and do not affect the environment over the fragment, the resulting trajectory can be treated as on-policy.Source: §3.1 · p. 4

3.2 MULTI-STEP OFF-POLICY VALUE ESTIMATION IN DELAYED ENVIRONMENTS

• The transformed fragment's length is the number of steps until its first action influences subsequent delayed observations, minus one.The transformation applies to subsequent transitions until total delay is shorter than the fragment length.Source: §3.2 · p. 5
• Unlike importance sampling and Retrace, this method does not suffer from variance explosion because transformed fragments need no policy-ratio weighting.The fragments are transformed into on-policy trajectories before multi-step value estimation.Source: §3.2 · p. 5

4 DELAY-CORRECTING ACTOR-CRITIC

• DCAC derives an improved SAC variant for random delays by using off-policy trajectories to construct on-policy multi-step estimators.This targets the more difficult credit assignment introduced by random delays.Source: §4 · p. 6

4.1 VALUE APPROXIMATION

• Replay trajectories are truncated at the greatest length satisfying the delay condition, then partially resampled into an equivalent on-policy sub-trajectory for the soft value target.The resulting trajectory is used with the delayed on-policy n-step soft state-value estimator.Source: §4.1 · p. 6

4.2 POLICY IMPROVEMENT

• DCAC also uses its multi-step value estimator for policy improvement, with reparameterized gradients backpropagated through the action buffer.The DCAC actor loss is less biased than SAC’s under the stated assumption of similarly biased parametric value estimators.Source: §4.2 · pp. 6–7

5 EXPERIMENTAL RESULTS

• The authors release a Gym wrapper for adding custom multi-step delays to classical turn-based environments, including MuJoCo continuous control.Each experiment uses six seeds and shades 90% confidence intervals.Source: §5 · p. 7
• The comparisons use SAC in the same RDMDP augmented-observation setting, while naive SAC with unaugmented delayed observations gives near-random results.The comparison also includes RTAC; DCAC reduces to RTAC when ω = 0 and α = 1.Source: §5 · p. 7
• With a constant total delay of five time-steps, DCAC shows a very strong performance advantage over the tested algorithms using the same augmented observations.The reported constant-delay comparison uses ω = 2 and α = 3.Source: Figure 6 · p. 7, §5 · p. 8
• DCAC clearly dominates the baselines with WiFi-sampled random delays; Ant is difficult for all tested algorithms, while only DCAC escapes HalfCheetah local minima.Figure 7 uses action and observation delays sampled from a real-world WiFi dataset.Source: Figure 7 · p. 8, §5 · p. 8
• The random-delay setup uses 20 ms time-steps and discards superseded communications, clipping long delays that are almost always superseded in the example.The WiFi dataset contains outliers up to 1 s, while delays longer than 80 ms are almost always superseded.Source: §5 · p. 8

6 RELATED WORK

• Katsikopoulos and Engelbrecht (2003) first discussed delayed Markov decision processes and asynchronous rewards; Walsh et al. (2008) studied constant observation delays using a model-based algorithm to predict the environment’s current state.Source: §6 · p. 8
• Hester & Stone (2013) handled random delays with action buffers and implicit credit assignment, whereas this paper uses delay measurements for explicit credit assignment.Ramstedt & Pal (2019) formalized real-time reinforcement learning for the special case α = 1 and ω = 0.Source: §6 · p. 9
• Xiao et al. (2020) considered action-selection time within a larger time-step, but their framework permits only delays shorter than one time-step.The passage notes that large time-steps are incompatible with high-frequency control.Source: §6 · p. 9

7 CONCLUSION AND FUTURE WORK

• DCAC uses delay measurements to generate actual on-policy sub-trajectories from off-policy samples, addressing credit assignment in real-world random-delay settings.The authors also note that action buffers are required for a Markovian RDMDP state, though they may be approximated in an RNN hidden state.Source: §7 · p. 9
• The approach handles arbitrary time-step durations, although time-steps shorter than the upper bound of inference time require practical adjustments.Source: §7 · p. 9

A.1 SELF-CORRELATED DELAYS

• Timestamps on actions and observations let the environment and agent identify and discard outdated messages, preserving the most recently received information.An observation can carry the applied-action timestamp and capture timestamp; synchronized clocks also allow inference of observation delay.Source: §A.1 · p. 12, §A.2 · p. 12

A.3 SCALABILITY OF THE ACTION BUFFER

• The maximum delay K is a practical design choice; observations exceeding K should be discarded, with a procedure for runs of more than K such arrivals.Long delays may be superseded by shorter ones, and run-length encoding is one possible alternative to a simple action buffer.Source: §A.3 · p. 12

A.4 DELAYED REWARDS

• When observations are dropped, the chosen reward definition accumulates rewards from lost transitions and assigns zero reward to repeated observations.If cumulative-reward reporting is unavailable, delayed rewards may instead be repeated, which raises reward variance without affecting the analysis.Source: §A.4 · p. 12

A.5 LONG OBSERVATION CAPTURE

• When observation capture is not instantaneous, the action buffer must include actions whose influence on the observation is uncertain, but DCAC’s backup length need not change.The backup still depends on the first action known not to have influenced the delayed observation.Source: §A.5 · p. 13

A.6 COMBINED OBSERVATIONS

• For observations combining parts captured at different times, the action buffer must cover the maximum possible combined total delay.Source: §A.6 · p. 13

B.1 MORE INFORMATION AS INPUT TO THE MODEL

• The action delay for the previously applied action is used by DCAC, and all tested algorithms also receive the delay of the action due to be applied when the observation is sent.Source: §B.1 · p. 13

B.2 MODEL ARCHITECTURE

• The experiments use separate actor and critic MLPs with two 256-unit hidden layers; DCAC’s critic estimates state-value v(x), unlike SAC’s action-value q(x).The actor outputs an action distribution, and both networks use Adam; twin critics and target-weight tracking are used for stability.Source: §B.2 · p. 13

B.3 HYPERPARAMETERS

• SAC, RTAC, and DCAC share a set of hyperparameters beyond their neural-network architecture.Source: §B.3 · p. 13

C VISUAL EXAMPLES

• Figure 8 contrasts constant delays, where the augmented observation includes an action buffer and delayed observation, with random delays, where newer messages can supersede older ones.Source: Figure 8 · p. 14

D.1 IMPORTANCE OF THE AUGMENTED OBSERVATION SPACE

• With a one-step constant action delay, SAC using augmented observations learns, while SAC using only delayed observations has near-random results because those observations are not Markov.Source: Figure 9 · p. 15

D.2 CONSTANT DELAYS

• At total constant delay 1, DCAC/RTAC slightly outperforms SAC; at total delay 3, DCAC clearly outperforms all other approaches.Source: Figure 10 · p. 15, Figure 11 · p. 16

D.3 RANDOM DELAYS

• Under uniformly sampled action and observation delays, all tested approaches fail on Ant, while DCAC has a clear advantage over SAC on the other tasks.The stated ranges are ω ∈ [0, 2] and α ∈ [1, 3].Source: Figure 12 · p. 16

F.1 LEMMA ON STEADY-STATE VALUE ESTIMATION BIAS

• Lemma 3 concerns the expected bias of an n-step value estimator under a steady-state distribution, if that distribution exists.Source: §F.1 · p. 17

F.2 LEMMA ON A DIRAC DELTA PRODUCT DISTRIBUTION

• Lemma 4 states that when p(u, v) is a Dirac delta at u = c times q(u, v), finite q at c permits replacing q(u, v) with q(c, v).Source: §F.2 · p. 17

F.3 LEMMA ON F

• Lemma 5 states that the dynamics described by f depend neither on the input action nor on a range of actions in the action buffer.Source: §F.3 · p. 17

F.4 LEMMA ON PARTIAL RESAMPLING

• Partial resampling transforms trajectories collected under policy µ into trajectories distributed according to π, subject to matching initial state, delay variables, and relevant actions in the initial buffers.Source: §F.4 · p. 18
• The lemma’s proof proceeds by induction, with the zero-length trajectory as its base case.Source: §F.4 · p. 18

• Definition 3’s resampling transforms off-policy trajectories into on-policy trajectories, provided delayed observations do not depend on resampled actions.Source: G PROOFS OF THE RESULTS FROM THE MAIN… · pp. 19–20
• The soft value function averages expected reward plus discounted next-state soft value under the policy, with a log-policy term subtracted.Source: G PROOFS OF THE RESULTS FROM THE MAIN… · p. 20
• DCAC’s actor loss is less biased than SAC’s when both use similarly biased parametric value estimators.Source: G PROOFS OF THE RESULTS FROM THE MAIN… · p. 21
• The proof assumes replay-memory states follow the policy’s steady-state distribution, though the authors say this can be avoided with more complicated estimator-bias assumptions.Source: G PROOFS OF THE RESULTS FROM THE MAIN… · p. 21