Dutch eligibility traces
Mathematical Methods AIMech:DutchEligibilityTraces DRAFT
An eligibility-trace update that propagates prior feature credit and adds a current-feature contribution adjusted by the prior trace’s projection onto that feature, using the source-specified step-size scaling convention.
Identity Notes & Concept Scope
Selects the vector-valued Dutch eligibility update as a mathematical component, not a complete TD, Sarsa or GTD algorithm. Scaled and constant-step-size unscaled conventions are explicitly related, while variable step sizes and arbitrary feature geometries retain their limits. Existing replacing and accumulating traces remain distinct. Fresh merged-base identity assessment on 15 October 2026, 17:07:16–17:08:53 UTC, at 9799fa6e2cb303d940fcb56249830c333cac7c90. All 772 native and 442 pinned AIO records supplied 4,834 identity fields and 3,693 normalized values, including local IDs and explicit candidate source spellings. No candidate collision was found. Four checkout scans included ignored and hidden files and retained 2,597 occurrences in 437 exact contents, including 250 new contents. Root read all 250 new contents, all 15 context-only normalized fields with nine definitions, all matching frontier fields and all four complete matching owners. Historical semantic source and mapping readings retain their prior scope; this does not claim a new manual reading of all historical context groups or every record mechanism. All 909 main and 393 nested frontier objects were mechanically queried. Absence is bounded to these snapshots and probes; no saturation is inferred.
Claims & Grounded Evidence
5 Claims
Scope
#named-trace-component
Dutch eligibility traces are a named feature-credit component. The 2014 UAI source applies this name to its general trace recurrence, and the 2016 journal source explicitly distinguishes the Dutch trace update from the separate changing-prediction correction in true online TD(lambda). The trace recurrence alone does not specify a reward target, weight update or action-selection rule.
Mechanism
#scaled-vector-recurrence
In the general step-size-weighted convention, initialize E_0=eta_0*phi_0. For t>0, update E_t=c_(t-1)*E_(t-1)+eta_t*(1-c_(t-1)*phi_t^T*E_(t-1))*phi_t, where E and phi are compatible real feature vectors and eta and c are scalars. The inner product uses the old trace E_(t-1). Equivalently, the update is c_(t-1)*(I-eta_t*phi_t*phi_t^T)*E_(t-1)+eta_t*phi_t; this rank-one form is an algebraic rewrite of the same recurrence.
Mechanism
#td-step-size-conventions
With q=gamma*lambda, the original 2014 TD convention and the 2016 time-dependent-step-size convention use E_t=q*E_(t-1)+alpha_t*phi_t-alpha_t*q*(E_(t-1)^T*phi_t)*phi_t, starting from E_(-1)=0. The 2016 constant-alpha unscaled convention instead uses e_t=q*e_(t-1)+phi_t-alpha*q*(e_(t-1)^T*phi_t)*phi_t, starting from e_(-1)=0. For a constant alpha and the same feature sequence, the compatible traces satisfy E_t=alpha*e_t. Time-varying step sizes remain inside the scaled recurrence.
Mechanism
#one-hot-specialization
For one-hot features and the unscaled TD convention, inactive coordinates obey e_t(j)=q*e_(t-1)(j), while the active coordinate i obeys e_t(i)=1+(1-alpha)*q*e_(t-1)(i), where q=gamma*lambda. From the same old trace this update map equals (1-alpha) times the accumulating update plus alpha times the replacing update. It is a convex combination only when alpha is in [0,1]; at alpha=1 the one-hot trace update becomes replacing.
Scope
#rank-one-memory-cost
For n dense feature coordinates, the trace recurrence can be evaluated using the old trace, the current feature vector, one inner product and vector operations, with O(n) arithmetic and O(n) trace storage per update. It does not require constructing the n-by-n rank-one matrix explicitly. These are costs of the trace recurrence; feature construction, action selection and the host learning rule have their own costs.
⚠️ Curated Limitations & Negative Results
- The component is distinct from complete true online TD or Sarsa, the general eligibility family and an entire forward-view learning algorithm. In the UAI theorem, forward/backward weight equality also requires its linear weight updates, companion correction and horizon-independent target-difference relation; inserting only this trace into an arbitrary host does not establish that equality.
- The scaled and unscaled conventions must be matched to the host update. Constant-alpha rescaling E=alpha*e does not justify the substitution E_t=alpha_t*e_t for varying step sizes. Division by alpha is undefined at alpha=0. A current zero alpha_t in the scaled recurrence leaves the decayed previous trace when earlier step sizes produced nonzero credit.
- The accumulating/replacing relation is an identity between one-hot update maps evaluated from the same old trace, not a mixture of separately evolved trace histories. It does not extend as a coordinatewise replacing rule to arbitrary overlapping binary or real features. Coincident one-hot trace updates do not make the complete learning algorithms identical.
- Dutch traces are not coordinatewise clipping and need not remain nonnegative or within [0,1]. In the general scaled recurrence, if z=c*phi^T*E_old and h=eta*||phi||^2, then phi^T*E_new=z+h*(1-z). For any starting projection, h in [0,1] keeps the new projection between its old value and one; unrestricted feature norms or step sizes can overshoot or amplify the deviation. The source phrase toward one does not imply exact unit attainment.
- The general UAI coefficient c is a scalar independent of the data horizon, not necessarily a number in [0,1]. Its description as shrinking requires additional magnitude conditions. The transition c*(I-eta*phi*phi^T) has feature-direction factor c*(1-eta*||phi||^2), so the recurrence supplies no unconditional numerical stability, contraction, convergence, variance reduction or performance guarantee.
- The source forward-view derivations concern linear prediction in the learned weights with the specified feature/target sequence and matching initialization. The vector trace formula can be evaluated on supplied features, but generic nonlinear or parameter-dependent feature learning does not automatically inherit those derivations. Dense O(n) bookkeeping does not imply cost proportional only to the current number of nonzero features or a universal wall-clock advantage.
- The 2014 PMLR paper supplies the earlier scaled recurrence; the 2014 UAI paper explicitly names the general form Dutch traces; the 2016 journal article presents unscaled, time-dependent and tabular conventions and attributes the name to van Hasselt and colleagues. This is inspected source lineage, not an exhaustive priority claim. The UAI proof locally omits +x_k in its first F_k restatement although the theorem and later expansion retain those terms, and the 2016 prose after Equation 17 points to Algorithm 2 although the local time-dependent box is Algorithm 4. These bounded display observations are not a certified defect of the trace recurrence, an official erratum or a full proof audit. No author implementation or benchmark reproduction is certified.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MathematicalFunction
Mathematical Function
|
related_match | The component defines a deterministic vector-valued update from prior trace, current feature vector and scalar parameters. This supports a qualified mathematical-rule association with the pinned generic function class, without exact identity, an asserted subclass edge, a scalar-output restriction or a neural-activation claim. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
vanseijen2014
|
Harm van Seijen, Richard S. Sutton
|
primary paper
full_text
|
ID: https://proceedings.mlr.press/v32/seijen14.html
sha256:c8f93a80ad42…
|
vanseijen2016
|
Harm van Seijen, A. Rupam Mahmood, Patrick M. Pilarski, Marlos C. Machado, Richard S. Sutton
|
primary paper
full_text
|
ID: https://www.jmlr.org/papers/v17/15-599.html
sha256:905d228fcd5e…
|
vanhasselt2014
|
Hado van Hasselt, A. Rupam Mahmood, Richard S. Sutton
|
primary paper
full_text
|
ID: https://www.auai.org/uai2014/acceptedPapers.shtml
sha256:d7bdba51b77d…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-15T17:16:20Z
Updated: 2026-10-15T17:16:20Z
Source File:
data/curated/DutchEligibilityTraces.yaml