AIMech AI

True online Sarsa(lambda)

Algorithms AIMech:TrueOnlineSarsaLambda DRAFT
A linear on-policy action-value control algorithm that combines a Dutch eligibility trace with a correction for changing predictions, using the next action selected by its behavior policy and preserving the specified pre-update action and prediction timing.
Identity Notes & Concept Scope Selects the linear on-policy action-value control algorithm combining a Dutch trace, prediction correction and the specified preupdate successor-action/value timing. It is distinct from true-online state-value TD prediction, replacing traces, MCQ-L, Peng–Williams and Watkins methods. Finite-time equivalence is conditional on the same realized sequence, not convergence. Existing owner 264 retains its prior three record IDs and both earlier resolutions. The fresh collection on 15 October 2026 at 16:12:44–16:13:52 UTC covers 769 native and 442 pinned AIO records at merged base 41221e5f8916ff024296a8ed34622bda702c276d, with only the five reviewed schema/renderer/docs/test edits applied. All 4,825 identity fields (3,687 normalized values), including local IDs and the explicit Sarsa lambda source spellings, were compared. No candidate identity collision was found. Four ignored- and hidden-inclusive checkout scans retained 4,432 occurrences in 367 exact contents. Root read all 304 newly encountered contents, all 11 contextual fields and nine neighboring definitions, and seven complete matching frontier owners. The supporting assessment read all 367 contents, including 63 historical ones, and reconstructed every occurrence. All 909 main and 393 nested frontier objects were mechanically queried. This is a dated, bounded identity assessment, not global absence or discovery saturation.

Claims & Grounded Evidence

6 Claims
Mechanism #linear-on-policy-control
True online Sarsa(lambda) applies the true online temporal-difference construction to a linear action-value estimate Q(s,a)=theta^T psi(s,a), with lambda in [0,1]. Its behavior policy uses the current action-value estimates, for example through epsilon-greedy selection. The source gives action-specific blocks of state features as a common representation, not as a required feature layout.
Mechanism #selected-successor-action
Execute the currently carried action A and observe reward R and successor state S_next. Before changing theta, select A_next using the behavior policy and obtain psi_next=psi(S_next,A_next). Compute Q=theta^T psi and Q_next=theta^T psi_next with the pre-update weights, and delta=R+gamma*Q_next-Q. For a terminal successor, use psi_next=0. The bootstrap uses the selected successor action rather than a maximum over successor actions.
Mechanism #dutch-trace-plus-correction
With constant step size alpha and the unscaled trace convention, update e=gamma*lambda*e_old+psi-alpha*gamma*lambda*(e_old^T psi)*psi. Then update theta_new=theta+alpha*(delta+Q-Q_old)*e-alpha*(Q-Q_old)*psi. The inner product in the trace update uses e_old, while the weight update uses the newly updated e. Both the Dutch trace and the prediction correction are part of the method; changing only the trace in ordinary Sarsa does not generally yield this update.
Mechanism #stored-prediction-and-carried-action
After the weight update, set Q_old to the already computed Q_next, then carry psi_next and A_next into the following transition. Q_old therefore retains a prediction made with the preceding weights; it is not recomputed using theta_new. At the start of each episode reset e=0 and Q_old=0 while retaining the learned weights across episodes. The initially zero trace gives e=psi on the first update, so the dependence on the initial stored prediction cancels in that first weight update.
Scope #specified-finite-time-correspondence
For a fixed linear feature mapping, matched initial weights and step size, and the same realized action-feature-reward sequence, the Sarsa backward recurrence inherits the specified online lambda-return forward sequence’s finite-horizon weight correspondence. This comparison holds the realized sequence fixed rather than reselecting actions at intermediate forward-replay weights. At lambda=0, e=psi and the separate prediction correction cancels, giving the corresponding one-step linear Sarsa update.
Scope #continued-credit-and-feature-cost
Algorithm 3 continues its Dutch-trace recurrence without a Watkins nongreedy-action trace reset or a replacing-control rule that clears other actions’ credit. For a linear action-feature vector of dimension d, the dense trace and weight updates use O(d) arithmetic and vector storage per transition. Feature construction and behavior-policy action selection have additional costs; an action-block representation can make d depend on the number of actions.

⚠️ Curated Limitations & Negative Results

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes
AIO Target Class Mapping Relation Mapping Rationale
AIO:ReinforcementLearning
Reinforcement Learning
related_match The source-scoped algorithm learns state-action values from reward transitions and uses those estimates for behavior selection, with exploration such as epsilon-greedy. This supports a qualified association with the pinned reinforcement-learning task. It asserts neither exact identity nor an algorithm-to-task subclass relation, and it supplies no guarantee of exploration, convergence or optimal control.

Evidence Sources & Primary Literature

2 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…

Curation Provenance

Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-15T16:28:32Z
Updated: 2026-10-15T16:28:32Z
Source File: data/curated/TrueOnlineSarsaLambda.yaml