Robots are often trained to imitate a demonstration while staying free to move at their own pace: pausing, slowing down for a tight insertion, or speeding through easy stretches. The usual tool for this is dynamic time warping (DTW), an algorithm that finds the best stretching of the time axis to match two trajectories and reports the leftover mismatch as a distance. Today DTW enters reinforcement learning as a whole-trajectory score. The agent acts for an entire episode, and only then does it learn how well the episode matched the demonstration. That design has two costs. A score handed out once per episode is the noisiest possible learning signal. And recomputing the full alignment, whose cost grows with the square of trajectory length, for every rollout in a large parallel batch is expensive.
We propose to split DTW into per-step rewards whose sum equals the episode's DTW distance exactly. The dynamic program behind DTW already fills its table one row at a time. If each new agent state adds one row, the cost per step is linear in the demonstration length, or constant if alignment is limited to a band. The change in the best partial alignment cost then serves as a dense reward. Because these rewards telescope, the agent's undiscounted objective is unchanged. Only the timing of the credit changes, which should lower the variance of value targets in the way multi-step returns do. The remaining design question is what to show the value network so the redistributed reward stays Markov, meaning the reward depends only on what the network sees. We also ask whether discounting should count demonstration progress instead of wall-clock steps, so the speed invariance DTW provides is not undone by the discount factor.
Core Claim
Let the demonstration be $y_1,\dots,y_M$ and the agent's states $x_1,\dots,x_T$. Write $D_t(j)$ for the cost of the best warping that matches $x_{1..t}$ to $y_{1..j}$. Each new state updates one row:
$$D_t(j) = d(x_t, y_j) + \min\{D_{t-1}(j),\ D_{t-1}(j-1),\ D_t(j-1)\}.$$
Define a potential $\Phi_t = -\min_j \big[D_t(j) + \kappa (M-j)\big]$. Here $\kappa$ is a per-index charge for the part of the demonstration not yet matched, so an agent cannot score well by stopping early. The per-step reward is $r_t = \Phi_t - \Phi_{t-1}$. At the end of the episode the agent receives an extra correction $-(D_T(M) - \min_j[D_T(j)+\kappa(M-j)])$. These terms sum to $-D_T(M)$ (taking $\Phi_0 = -\kappa M$) for any $\kappa$. The objective is therefore identical to the episodic DTW reward used in AutoMate, but the signal is dense.
We make three claims. First, with this redistribution, generalized-advantage critics learn faster and with lower target variance than with the terminal score. Second, the redistributed reward is Markov only if the critic sees a summary of the current row $D_t$. The minimal useful summary is the matched demonstration index $j^*_t$ together with the row minimum. Leaving the summary out is a source of bias we can measure. Third, a band of width $B$ around the expected path reduces per-step cost to $O(B)$, in the spirit of Fast Global Alignment Kernels. The price is a second, measurable bias whenever the agent drifts out of the band.
Research Program
The work connects three literatures. AutoMate supplies the application and the motivation. It places DTW inside Proximal Policy Optimization (a standard on-policy policy-gradient method) to get speed-invariant imitation rewards for assembly. It does not analyze what the episodic DTW score does to gradient variance or critic bias, and it computes exact quadratic alignments. EgoBridge also uses DTW to compare human and robot motion with different pacing. It works in imitation learning without value functions and is likewise limited by quadratic cost. We borrow the motivation from both and change where and how often the alignment is computed.
The bias–variance side constrains the design and supplies the analysis tools. Averaging n-step Returns Reduces Variance shows that return estimators must be compared at matched contraction modulus, meaning the same effective learning speed. It also shows that averaging bootstrapped returns lowers variance when temporal-difference errors are not perfectly correlated. We use its matching protocol when comparing reward schedules. The Concept of Criticality shows that bootstrapping horizons can usefully vary along a trajectory. Its criticality signal is hand-supplied. Our alignment index $j^*_t$ is a data-driven progress coordinate along which horizons and discounting can instead be defined. Separable value functions across time-scales is a cautionary example: fixed discount ladders tied to wall-clock steps break under sparse rewards. Dense redistribution is one way to avoid that failure.
The construction has three parts. The first is a batched GPU kernel that keeps one banded DTW row per parallel environment and returns $r_t$, $j^*_t$, and the row minimum at each step. The second is a pair of critic-input variants: row summary versus no summary. The third is an optional phase-indexed discount $\gamma^{\,j^*_t - j^*_{t-1}}$, under which a pause that makes no demonstration progress is not discounted. Phase discounting changes the objective. It removes the incentive to finish quickly. We therefore treat it as a separate, ablated choice rather than part of the core claim.
On the analysis side, we will measure how often $j^*_t$ jumps backward or forward by more than one index. Such revisions are when the partial alignment changes its mind, and they are the main way dense credit can mislead the agent. We will also bound the band-truncation error as a function of $B$ and how far the agent's speed deviates from the demonstration's.
Baselines
The naive reference point is wall-clock tracking. The reward at step $t$ is $-d(x_t, y_t)$, which compares the agent to the demonstration at the same time index. It is cheap and dense but not speed-invariant. Any slowdown is punished, so it shows what speed invariance buys.
The strongest existing method is AutoMate's recipe: an episodic DTW imitation reward inside PPO with generalized advantage estimation. On AutoMate's assembly benchmark it reports specialist policies reaching "an 80%+ success rate on 80 out of 100 assemblies" in simulation (AutoMate). We will rerun this recipe ourselves on every benchmark, with the same demonstrations, PPO settings, number of environment steps, and hyperparameter search budget (an equal number of seeds and of λ/γ configurations for each method). Using DTW alone, without AutoMate's signature-transform term, isolates the reward-timing question. Beating it means one of two things at equal environment steps: higher final success, or reaching AutoMate-level success in measurably fewer samples, with confidence intervals over at least five seeds. Matching it at lower wall-clock cost is a weaker but still reportable result.
A third baseline is greedy monotone nearest-neighbor progress. At each step the agent's matched index advances to the nearest demonstration state at or after the current index, and the reward is the negative distance. This is the cheapest speed-tolerant shaping, and it is the main threat to the proposal.
Two ablations isolate the key ingredients. Telescoping DTW with no row summary given to the critic tests the Markov claim. Telescoping DTW with $B=M$ (unbanded) versus several finite $B$ separates the effect of the reward redistribution from the effect of truncation.
Why not just…?
Why not just keep the episodic DTW reward and lower variance with λ-returns? Generalized advantage estimation already smooths credit. Averaging n-step Returns reports λ-returns improving sample efficiency over n-step returns in 7 of 9 MuJoCo configurations. But λ-averaging only spreads a reward that arrives at the episode's end. It cannot assign that reward to the particular steps that caused misalignment. Our matched-contraction comparison, which sweeps λ for both reward schedules, settles whether redistribution adds anything beyond the best λ. If the gap closes at the best λ, we will report that dense DTW is unnecessary.
Why not just use greedy nearest-neighbor progress tracking? This is a real threat. On demonstrations that never revisit similar states, greedy monotone matching probably approximates DTW well and costs less. It fails when the demonstration loops or reverses, as in gait cycles, back-and-forth wiping, or approach–retract insertion. In those cases a greedy match locks onto the wrong repetition and cannot recover. The DTW row keeps every candidate alignment alive until later evidence resolves it. We will construct demonstration sets with and without such repeated structure. We predict an advantage only on the repeated-structure sets. If none appears there, the proposal reduces to a recommendation for greedy tracking.
Why not just recompute soft or exact DTW over the prefix at every step? This gives the same dense signal without any incremental bookkeeping. However, it costs $O(tM)$ at step $t$, or $O(T^2 M)$ per episode. Our incremental row update gives identical exact values at $O(M)$ per step, and $O(B)$ with a band. The choice is purely an engineering one, and we will report throughput in environment steps per second across trajectory lengths to quantify it.
Why not just learn a phase or progress estimator? A learned progress estimator is the closest analogue of the stage classifier in DynamicManip. It would need labeled phases or its own training signal, and it can drift. DTW gives an exact, label-free progress coordinate from a single demonstration. We treat a learned estimator as future work rather than claiming it is worse.
Proposed Experiments
We start with a tabular check. In a chain environment with known dynamics and a looping demonstration, we can compute the exact variance of value targets under terminal versus telescoping rewards, at matched contraction modulus. This verifies the variance claim and the Markov-summary claim before any deep RL.
Next comes continuous control on iMuJoCo. It provides 100 SAC-generated trajectories for each of 154 Hopper, HalfCheetah, and Walker2d variants. We time-resample the demonstrations by factors of 0.5 to 2 to create multi-speed references, train agents on the imitation reward alone, and score them on true task return and on DTW to held-out demonstrations. No reported result found on Lacuna for DTW-reward RL on iMuJoCo, so all numbers there will be our own reruns. Gait cycles naturally provide the repeated structure that separates DTW from greedy tracking.
Finally, if the assets can be reproduced, we run a subset of the AutoMate assemblies in simulation. There we compare against the 80%+ on 80/100 figure using our rerun of the episodic-DTW recipe.
The decisive checks are three. First, at matched contraction modulus and the best λ for each method, telescoping DTW must reach a fixed success threshold in fewer environment steps than episodic DTW. Second, removing the row summary from the critic must measurably hurt, which would confirm that the Markov fix matters. Third, the advantage over greedy tracking must appear on looping demonstrations and vanish on non-looping ones.
Supporting measurements include backward-revision frequency of $j^*_t$, success as a function of band width $B$ under increasing speed mismatch, and steps per second against trajectory length. Phase-indexed discounting is evaluated separately on time-resampled demonstrations. Its expected benefit is fewer learned "rush" behaviors at the cost of slower completion, and we will report both.
References
- AutoMate: Specialist and Generalist Assembly Policies over Diverse Geometries
- Fast Global Alignment Kernels
- EgoBridge: Domain Adaptation for Generalizable Imitation from Egocentric Human Data
- Averaging $n$-step Returns Reduces Variance in Reinforcement Learning
- The Concept of Criticality in Reinforcement Learning
- Separable value functions across time-scales
- DynamicManip: Enabling Dynamic Manipulation from a Single Static Demonstration