Replacing eligibility traces
Mathematical Methods AIMech:ReplacingEligibilityTraces DRAFT
An eligibility-trace update that replaces a visited state’s eligibility by one while geometrically attenuating other state traces, preserving recent credit eligibility without adding repeated-visit multiplicity.
Identity Notes & Concept Scope
This source-scoped credit-memory component replaces visited state/selected feature traces rather than accumulating repeated-visit counts. It is distinct from a complete TD/Sarsa controller, the original Watkins hard-cut forward/delayed construction, neural MCQ-L and Peng–Williams two-error control. Existing owner264 retains general/true-online and other-variant residuals. Fresh collection on 15 October 2026 at14:35:54–14:37:34 UTC at actual merged base 73729051e58d582f36c9af9296a92b393be0a679 compared all763 native and442 pinned AIO records (4,807 identity-field occurrences,3,674 normalized values), with zero candidate collisions and15 context-only fields across eight neighboring records. Four ignored- and hidden-inclusive checkout searches retained3,967/3,981/9,015/10,567 occurrences (27,530 total), grouped into1,338 exact matching contents. Root read all39 focused candidate-bearing decoded contexts, all15 normalized contextual fields/eight definitions, all20 full matching frontier objects and the three newly merged342 definitions. This is bounded semantic inspection; root does not claim a verbatim reading of all1,084 broader decoded contexts or every repeated occurrence. All909main and393nested objects were queried recursively; historic primary/AIO and supporting inspections retain their separately documented scopes.
Claims & Grounded Evidence
5 Claims
Mechanism
#state-replacing-recurrence
For a visited state s_t, replace its eligibility by e_(t+1)(s_t)=1. For every other state s, set e_(t+1)(s)=gamma*lambda*e_t(s), with gamma and lambda in [0,1]. This differs from the accumulating rule e_(t+1)(s)=gamma*lambda*e_t(s)+1{s=s_t}: another visit replaces the current state trace rather than adding to its previous value.
Mechanism
#trace-as-td-credit-component
In the paper’s undiscounted absorbing-state prediction setting, the replacing trace enters the TD update as Delta V_t(s)=alpha_t(s)*[r_(t+1)+V_t(s_(t+1))-V_t(s_t)]*e_(t+1)(s), with terminal value zero. The trace determines which earlier states remain eligible for this learning signal; it is a component of the prediction update rather than a complete policy or control algorithm.
Scope
#bounded-recency-with-endpoints
For traces initialized in [0,1] and q=gamma*lambda in [0,1], the replacing recurrence preserves each trace in [0,1]. After k consecutive inactive updates, a trace equals q^k times its earlier value. Thus inactive traces vanish after one update when q=0 and do not decay when q=1. These are direct consequences of reset-to-one and multiplication by q; repeated visits do not build the accumulating rule’s visit-multiplicity sum.
Scope
#qualified-first-visit-correspondence
In the undiscounted absorbing prediction setting with gamma=lambda=1, repeated-batch replacing TD converges to the first-visit Monte Carlo sample estimate for sampled states with N(s)>0 under the paper’s fixed step size 0<alpha<1/N, where N is the number of training trials. Separately, offline replacing TD(1), applied after each completed trial with alpha_t(s) equal to the reciprocal number of first visits to s up through t, gives the first-visit sample-average update. These are the paper’s specified batch-limit and offline correspondences, not arbitrary finite-iteration online equalities.
Mechanism
#binary-feature-control-realization
The reported CMAC control realization maintains traces for action-specific binary features. After decaying old traces, it sets active features for the chosen action to one and clears the corresponding active features for other actions; the resulting trace vector weights a later scalar TD update. This chosen control convention is distinct from the alternative discussed in the paper, which replaces a state-action pair’s trace only when that same pair recurs.
⚠️ Curated Limitations & Negative Results
- This source-scoped recurrence is not the entire eligibility-trace family, a TD or Sarsa controller, MCQ-L, Peng–Williams Q(lambda), or a true-online trace algorithm. The original accumulating recursion already has a separate maintained TD-family context. General eligibility-family organization and other trace variants remain outside this record’s scope; the source’s earlier historical citations do not establish independently verified first-use priority.
- The [0,1] trace bound requires the stated initialization and gamma*lambda domain. A bounded trace does not bound arbitrary rewards, TD errors, step sizes or parameter changes, and does not itself prove stable or convergent learning. The endpoint gamma*lambda=1 retains inactive traces rather than forgetting them; no continuing undiscounted-return existence result follows from it.
- The first-visit correspondences retain the absorbing-process, completed-trial and step-size conditions stated in the claim. The batch result is a convergence limit, not equality after an arbitrary finite number of sweeps, and alpha=0 is excluded. The paper’s MSE comparisons are conditional and non-strict, with equality cases; they are not a universal superiority claim. No complete appendix-proof or external convergence-theorem certification is asserted.
- The selected chosen-action feature replacement with clearing of other actions is one control realization, not a universal definition of replacing traces. The source explicitly leaves comparisons with state-action-only replacement open. Tabular and binary-feature results are not a general nonlinear-network replacement prescription, and stationary prediction results do not automatically apply while the control policy changes.
- Figure 9 initializes all traces in step 1, but its end-of-trial branch returns to step 2 without an explicit all-trace reset. The note that the time index continues across trials does not settle that omission. This description preserves the printed recurrence and selected ongoing control steps without silently adding a reset or claiming a defect in unseen author software.
- Appendix B states that position is clipped within [-1.2,0.5] while also describing termination when the next position exceeds 0.5. A literal test after that clipping cannot terminate by this condition. Its displayed minus-g force together with negative g also requires a sign/convention clarification. These ambiguities limit a literal reading of that experimental environment; they do not invalidate the trace recurrence or establish how the experiments were implemented.
- The inspected evidence is a 36-page author-hosted prepublication layout associated with the 1996 journal article; local PDF page locators are used instead of inferred journal pagination. OCR was needed for prose, with selected equations and pseudocode checked visually. No author implementation, benchmark or full original-proof reproduction was performed for this evidence assessment; the reported random-walk and CMAC experiments do not establish universal performance or an optimal trace setting.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ReinforcementLearning
Reinforcement Learning
|
related_match | A credit-assignment component used within reinforcement-learning prediction/control; the broader pinned task is neither the recurrence itself nor a guaranteed outcome. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
singh-sutton1996
|
Satinder P. Singh, Richard S. Sutton
|
primary paper
full_text
|
ID: https://doi.org/10.1007/BF00114726
sha256:93193ac196bc…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-15T14:45:47Z
Updated: 2026-10-15T14:45:47Z
Source File:
data/curated/ReplacingEligibilityTraces.yaml