True online GTD(lambda)
Algorithms AIMech:TrueOnlineGTDLambda DRAFT
A linear off-policy state-value prediction algorithm that couples two Dutch eligibility traces with an accumulating gradient-correction trace and an auxiliary weight estimate to reproduce specified sampled interim forward-view updates.
Identity Notes & Concept Scope
Selects the linear off-policy state-value algorithm in the specified first-author version, with two scaled Dutch traces, a separate accumulating correction trace and auxiliary weights. It is distinct from on-policy true-online TD/Sarsa, the Dutch component, generic GTD/GQ, control and the later WIS variants. Empty aliases preserve those boundaries. 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
6 Claims
Mechanism
#linear-off-policy-state-value
True online GTD(lambda) estimates a specified target policy’s state values with V_t(s)=theta_t^T*phi(s), using transitions generated by a behavior policy b. For the sampled action A_t in state S_t, it uses the importance ratio rho_t=pi(A_t|S_t)/b(A_t|S_t). The source defines a linear state-value prediction algorithm, not an action-value control policy or an isolated eligibility-trace component.
Mechanism
#error-weighted-interim-forward-views
The construction uses the error-weighted interim return G_(k,h) of Equation 14 in the theta forward update of Equation 18, and a separate auxiliary least-mean-squares forward update of Equation 15 with the return of Equation 16. At each data horizon, the conceptual forward sequences replay from their respective matched initial weights. The gradient correction uses the already determined w_k, not a new horizon-replayed w_k^h. The source motivates these sampled forward sequences from a behavior-distribution mean-squared projected Bellman error; matching their backward implementation is distinct from taking an exact objective-gradient step.
Mechanism
#three-distinct-eligibility-traces
Let q_t=gamma_t*lambda_t and write g_t for the gradient-correction trace. The recurrences are e_t=rho_t*(q_t*e_(t-1)+alpha_t*(1-rho_t*q_t*phi_t^T*e_(t-1))*phi_t), g_t=rho_t*(q_t*g_(t-1)+phi_t), and e^w_t=rho_(t-1)*q_t*e^w_(t-1)+beta_t*(1-rho_(t-1)*q_t*phi_t^T*e^w_(t-1))*phi_t. Thus e and e^w are distinct step-size-scaled Dutch traces, while g is accumulating. Every trace inner product uses the corresponding old trace.
Mechanism
#coupled-prediction-and-auxiliary-update
In the indexed first-author version, delta_t=R_(t+1)+gamma_(t+1)*phi_(t+1)^T*theta_t-phi_t^T*theta_t. Using the newly computed traces, update theta_(t+1)=theta_t+delta_t*e_t+(e_t-alpha_t*rho_t*phi_t)*(theta_t-theta_(t-1))^T*phi_t-alpha_t*gamma_(t+1)*(1-lambda_(t+1))*(w_t^T*g_t)*phi_(t+1), and w_(t+1)=w_t+rho_t*delta_t*e^w_t-beta_t*(phi_t^T*w_t)*phi_t. Both right sides use the pre-update theta_t and w_t. The prior-weight prediction theta_(t-1)^T*phi_t retains its original timing.
Scope
#finite-horizon-linear-correspondence
For the specified realized data and fixed features, matched initial weights and step sizes, the source’s finite-horizon backward weights equal those of its specified forward sequences. The general target condition is Y_k^(h+1)-Y_k^h=c_k*(Y_(k+1)^(h+1)-Y_(k+1)^h), with c_k independent of horizon h. The theta construction uses eta_t=alpha_t*rho_t and c_(t-1)=gamma_t*lambda_t*rho_t; the auxiliary construction uses eta_t=beta_t and c_(t-1)=rho_(t-1)*gamma_t*lambda_t. The resulting dense updates use O(n) arithmetic and O(n) vector state per transition, independent of the elapsed horizon.
Scope
#gtd-zero-and-forward-view-boundary
When all lambda values are zero, e_t=alpha_t*rho_t*phi_t, g_t=rho_t*phi_t and e^w_t=beta_t*phi_t. The separate changing-prediction correction cancels, and the remaining coupled updates reduce to the source-defined GTD(0). At lambda=1 the explicit gradient-correction factor vanishes, but the error-weighted off-policy forward view is not identified with every off-policy Monte Carlo construction. The source treats other importance-weighting conventions and action-value extensions as separate constructions.
⚠️ Curated Limitations & Negative Results
- This is the original linear state-value off-policy algorithm, not GTD/GQ in general, an action-value controller, true online TD/Sarsa, WIS variants or Dutch/replacing traces alone. Setting every importance ratio to one does not generally eliminate the auxiliary gradient correction for lambda<1. A zero (1−lambda_(t+1)) factor removes that explicit correction, but does not by itself establish identity with every Monte Carlo algorithm.
- Finite-horizon equality to the specified sampled forward views is an algebraic statement, not a proof that each online step is an unbiased MSPBE gradient or that the coupled iterates converge, are stable, improve monotonically or reach an optimal policy. The expected objective uses a behavior-state distribution and an invertible feature second-moment matrix; existence of relevant returns/expectations, sufficient target-action support under behavior, and other convergence assumptions cannot be inferred merely from the update display.
- The derivation uses linear, fixed features and matched replay sequences. The source initializes e_0=alpha_0 rho_0 phi_0 and e^w_0=beta_0 phi_0; a zero pre-initial accumulating trace gives g_0=rho_0 phi_0. The first theta correction cancels, so no arbitrary theta_(−1) affects that first update. Later theta_(t−1)^T phi_t is a stored preceding-weight prediction, not a recomputation under theta_t. Replacing w_t by w_(t+1), swapping current and previous importance ratios, or simply replacing g with a Dutch trace changes the specified construction. Nonlinear or parameter-dependent features need separate justification.
- Alpha_t and beta_t are inside two different scaled traces; a constant-alpha unscaled TD/Sarsa convention cannot be substituted without a matched derivation. A zero current step size does not in general erase trace contributions from earlier nonzero steps. Importance ratios need not be at most one, and these Dutch or accumulating traces are not generally nonnegative or coordinatewise bounded by one. Linear dense cost excludes feature construction and does not imply cost only in current nonzero features.
- The inspected source retains mixed t/k indexing and the recursive superscript in Equation 6, and a scalar/vector mismatch in Equation 13 and nearby expectation prose. Its first proof restatement on PDF p. 3 also omits x_k despite its presence in the theorem and later algebra. These are bounded source-display observations; the explicit forward and backward updates remain separately identifiable. This record neither certifies nor invalidates the entire proof or author implementation.
- The statement on PDF p. 8 that MSPBE equals MSE at lambda=1 needs qualification. When the full-return operator yields v_pi and Pi is the stated d-orthogonal projection, MSE=J+||Pi*v_pi-v_pi||_d^2. The objectives then have the same minimizers, but their values are equal only when the projection residual vanishes. This direct projection identity does not establish convergence of the online algorithm.
- The evidence source is the exact acquired first-author-hosted version of the 2014 paper, with indexed discount/bootstrap expressions in Equation 16 and the final update. The retained conference, reissue and coauthor copies differ in the discount-product endpoint or some time indices; no verified revision date or comprehensive erratum notice is asserted. Experimental comparisons remain tied to the reported random-walk settings, representations and parameter searches, not universal superiority. No author software or benchmark reproduction is certified.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ReinforcementLearning
Reinforcement Learning
|
related_match | The algorithm estimates a specified policy’s state values from reward transitions generated by a potentially different behavior policy. This supplies prediction machinery used in reinforcement learning. The pinned class is a broader learning task involving exploration/performance optimization; the relation does not claim exact identity, an algorithm-to-task subclass edge, action selection, policy improvement or convergence. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
vanhasselt2014-author
|
Hado van Hasselt, A. Rupam Mahmood, Richard S. Sutton
|
primary paper
full_text
|
ID: https://www.auai.org/uai2014/acceptedPapers.shtml
sha256:b2d5ecc4acea…
|
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/TrueOnlineGTDLambda.yaml