Temporal
Model-free tabular learning — one batched update fed by Q-learning, SARSA, expected SARSA or double-Q targets, plus eligibility traces and Dyna.
Prelude.Temporal learns a table of action values from experience, without a model of the environment. It separates the two halves of every temporal-difference method: a target — a vector with one entry per sample — and a single update that moves the table toward any target. Q-learning, SARSA, expected SARSA and double Q-learning are four target definitions sharing one update.
Conventions: q is the action-value table S×A. A batch of \(n\) transitions arrives as one-hot matrices — hs states n×S, ha actions n×A, hs2 next states n×S, ha2 next actions n×A — built with marked from Policies, for example marked(stateIds(q), s); rw is the reward vector n, done the 0/1 terminal flags n, g the discount and rate the step size \(\alpha\). Every target includes \((1 - \text{done})\), so a terminal transition never bootstraps from a state the episode did not reach.
The update is a scatter: each sample’s error lands in its own cell, and when a batch visits the same cell more than once the errors are averaged, not summed. That keeps \(\alpha\) meaning the same thing at any batch size, and makes a batch of one exactly the textbook update. The sample models QTable.hb, Sarsa.hb, Expected.hb, Double.hb, Traced.hb and Dyna.hb build model … : Learner declarations on this module.
Notation. \(Q \in \mathbb{R}^{S \times A}\) has entries \(Q_{sa}\). Sample \(i\) of the batch is in state \(s_i\) and takes action \(a_i\), so its one-hot rows are \(H^{s}_{is} = [\,s = s_i\,]\) and \(H^{a}_{ia} = [\,a = a_i\,]\); its next state is \(s'_i\), with \(H^{s'}_{it} = [\,t = s'_i\,]\). \([\,\cdot\,]\) is the Iverson bracket, and \(\operatorname{safe}(d) = d + [\,d = 0\,]\) is the guarded divisor from Linear algebra.
open Prelude.Temporal
Reading a table at a batch’s cells
rowsAt
rowsAt(q, h) · q table matrix S×A · h one-hot states matrix n×S → rows matrix n×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be a table and \(H \in \{0, 1\}^{n \times S}\) (the argument h) one-hot states. Then
The table row for each sample’s state.
Intuition Multiplying by a one-hot row is a lookup: it copies row \(s_i\) of the table into row \(i\) of the result. The whole batch is read in one matrix product, with no loop and no index arithmetic.
Use it when a target needs every action’s value in a state — the max for qTarget, a policy-weighted average for expectedTarget — or you want the policy row of each sample (rowsAt(pol, hs)). When you need only the one cell a sample acted in, use valuesAt.
table-indexingvalue-targets
def rowsAt(q, h) ≔ einsum("is,sa->ia", h, q)
valuesAt
valuesAt(q, hs, ha) · q table matrix S×A · hs one-hot states matrix n×S · ha one-hot actions matrix n×A → values vector n
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q), \(H^{s} \in \{0, 1\}^{n \times S}\) (the argument hs) and \(H^{a} \in \{0, 1\}^{n \times A}\) (the argument ha). Then, for \(i = 1, \dots, n\),
The value of each sample’s state–action pair.
Intuition Two one-hots pin down a single cell, so each sample reads its own \(Q(s_i, a_i)\): the current prediction that a TD target is compared against.
Use it when you compute TD errors (aim − valuesAt(q, hs, ha), as nudged does), log the prediction for the actions actually taken, or check what a learner believes about specific transitions. For the full row of action values use rowsAt.
table-indexingvalue-learning
def valuesAt(q, hs, ha) ≔ einsum("is,ia,sa->i", hs, ha, q)
visits
visits(hs, ha) · hs one-hot states matrix n×S · ha one-hot actions matrix n×A → counts matrix S×A
Let \(H^{s} \in \{0, 1\}^{n \times S}\) (the argument hs) and \(H^{a} \in \{0, 1\}^{n \times A}\) (the argument ha). Then
How many samples of the batch fall in each state–action cell.
Intuition A histogram of the batch over the table: each sample drops a 1 into its cell. It is the divisor that turns summed errors into averaged ones, and it is how often each action has been tried.
Use it when you keep the visit counts that UCB needs (add each batch’s visits to a running counts and pass it to confident), average per-cell quantities as nudged and payoffs do, or check which part of the table your data covers. With single transitions it is the 1-cell mask that accumulated adds to a trace.
event-countingbatched-updatesexploration
def visits(hs, ha) ≔ einsum("is,ia->sa", hs, ha)
scattered
scattered(hs, ha, d) · hs one-hot states matrix n×S · ha one-hot actions matrix n×A · d one value per sample vector n → table matrix S×A
Let \(H^{s} \in \{0, 1\}^{n \times S}\) (the argument hs), \(H^{a} \in \{0, 1\}^{n \times A}\) (the argument ha) and \(d \in \mathbb{R}^n\). Then
Adds each sample’s value into its state–action cell (cells with several samples receive the sum).
Intuition The inverse of valuesAt: instead of reading one number out of each sample’s cell, write one number into it. A batch of per-sample quantities becomes a table-shaped update that can be added to \(Q\).
Use it when you write custom batched updates (errors, rewards, gradients) back onto a table. It sums collisions, so the size of the change grows with how often a cell repeats in the batch; divide by safe(visits(hs, ha)) to average, which is what nudged and payoffs do.
batched-updatestable-indexing
def scattered(hs, ha, d) ≔ einsum("is,ia,i->sa", hs, ha, d)
nudged
nudged(q, hs, ha, aim, rate) · q table matrix S×A · hs one-hot states matrix n×S · ha one-hot actions matrix n×A · aim targets vector n · rate step size α scalar → updated table matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q), \(H^{s} \in \{0, 1\}^{n \times S}\) (the argument hs), \(H^{a} \in \{0, 1\}^{n \times A}\) (the argument ha), \(y \in \mathbb{R}^n\) (the argument aim) the targets and \(\alpha > 0\) (the argument rate) the step size. Let \(n_{sa} = \operatorname{visits}(H^{s}, H^{a})_{sa}\). Then
The temporal-difference update: each visited cell moves toward the mean of its samples’ targets, and unvisited cells are unchanged.
Intuition Learning as a running average: move each estimate a fraction \(\alpha\) of the way toward what the latest evidence says it should be. Which learning algorithm you get is decided entirely by the aim you pass in; this step is the same for all of them.
Use it when you run any tabular TD method: pair it with qTarget, sarsaTarget, expectedTarget or crossTarget, or with Monte Carlo returns. \(\alpha\) of 0.1 is a common start; lower it for noisy rewards. Because repeated cells are averaged, \(\alpha\) means the same at any batch size. For eligibility traces, where one error updates many cells, use tracedStep instead.
value-learningbatched-updatescontrol
def nudged(q, hs, ha, aim, rate) ≔ q + rate · scattered(hs, ha, aim − valuesAt(q, hs, ha)) / safe(visits(hs, ha))
Four targets
Off-policy Q-learning bootstraps from the best next action whatever the agent did; on-policy SARSA from the action it actually took next; expected SARSA averages over the policy’s next-action probabilities, which has the same expectation as SARSA with lower variance; and double Q-learning chooses the next action with one table and evaluates it with the other, which removes the maximisation bias of Q-learning.
qTarget
qTarget(q, hs2, rw, g, done) · q table matrix S×A · hs2 one-hot next states matrix n×S · rw rewards vector n · g discount scalar · done terminal flags vector n → targets vector n
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q), \(H^{s'} \in \{0, 1\}^{n \times S}\) (the argument hs2) the one-hot next states, \(r \in \mathbb{R}^n\) (the argument rw) the rewards, \(\gamma \in [0, 1]\) (the argument g) the discount and \(d \in \{0, 1\}^n\) (the argument done) the terminal flags. Then, for \(i = 1, \dots, n\),
The Q-learning target.
Intuition “What this action is worth if I behave optimally from the next state on”: the reward received plus the best value the table currently sees one step ahead. Because it assumes the best next action whatever the agent actually did, it learns the optimal policy’s values while acting in some other, exploratory way.
Use it when you want optimal control from data gathered by any behaviour policy — ε-greedy exploration, old logs, a replay buffer. The max over noisy estimates is biased upward, which can inflate values in stochastic environments; crossTarget removes that bias. If the agent must be safe while exploring, the on-policy sarsaTarget learns values that account for its own exploration.
value-targetsoff-policy-learningcontrol
def qTarget(q, hs2, rw, g, done) ≔ rw + g · (1 − done) · rowMost(rowsAt(q, hs2))
sarsaTarget
sarsaTarget(q, hs2, ha2, rw, g, done) · q table matrix S×A · hs2 one-hot next states matrix n×S · ha2 one-hot next actions matrix n×A · rw rewards vector n · g discount scalar · done terminal flags vector n → targets vector n
Let \(Q\), \(H^{s'}\), \(r\), \(\gamma\) and \(d\) be as in qTarget, and let \(H^{a'} \in \{0, 1\}^{n \times A}\) (the argument ha2) be the one-hot next actions, sample \(i\) taking \(a'_i\). Then
The SARSA target, using the next action actually taken.
Intuition Value what the agent really does, mistakes included. Bootstrapping from the next action it actually took means an exploratory step off a cliff edge lowers the value of walking near the edge, so SARSA learns the safer route that suits an agent that keeps exploring.
Use it when you learn on-policy with the same ε-greedy policy you act with, and exploration has real cost (the cliff-walking case). You need the next action, so the update waits one step. Its target is noisier than expectedTarget, which averages over the next action instead of sampling it; prefer that when the policy is known.
value-targetson-policy-learningcontrol
def sarsaTarget(q, hs2, ha2, rw, g, done) ≔ rw + g · (1 − done) · einsum("ia,ia->i", ha2, rowsAt(q, hs2))
expectedTarget
expectedTarget(q, pol, hs2, rw, g, done) · q table matrix S×A · pol policy matrix S×A · hs2 one-hot next states matrix n×S · rw rewards vector n · g discount scalar · done terminal flags vector n → targets vector n
Let \(Q\), \(H^{s'}\), \(r\), \(\gamma\) and \(d\) be as in qTarget, and let \(\pi \in [0, 1]^{S \times A}\) (the argument pol) be a row-stochastic policy. Then
The expected-SARSA target.
Intuition SARSA without the dice roll: instead of the one next action that happened to be sampled, use the average over all next actions weighted by the policy’s probabilities. Same expected target, less noise, and it does not need to know the next action.
Use it when you have the policy as a table — typically exploring(q, eps) or boltzmann(q, tau) — and want steadier learning than sarsaTarget, often with a larger \(\alpha\). Passing greedyOf(q) as the policy makes it exactly qTarget, and any other target policy makes it off-policy. It costs a full row of the policy per sample.
value-targetsvariance-reductionon-policy-learning
def expectedTarget(q, pol, hs2, rw, g, done) ≔ rw + g · (1 − done) · einsum("ia,ia->i", rowsAt(pol, hs2), rowsAt(q, hs2))
crossTarget
crossTarget(qa, qb, hs2, rw, g, done) · qa table that selects matrix S×A · qb table that evaluates matrix S×A · hs2 one-hot next states matrix n×S · rw rewards vector n · g discount scalar · done terminal flags vector n → targets vector n
Let \(Q^{A}, Q^{B} \in \mathbb{R}^{S \times A}\) (the arguments qa and qb) be the selecting and evaluating tables, and \(H^{s'}\), \(r\), \(\gamma\), \(d\) as in qTarget. Let \(G = \operatorname{greedyOf}(H^{s'} Q^{A})\), so \(G_{ia} = [\,Q^{A}_{s'_i a} = \max_b Q^{A}_{s'_i b}\,] / \sum_{a'} [\,Q^{A}_{s'_i a'} = \max_b Q^{A}_{s'_i b}\,]\). Then
The double Q-learning target: the greedy next action under qa (ties split equally), valued by qb. Alternate the roles of the two tables between updates.
Intuition The max of noisy estimates picks, on average, the ones that were overestimated. Double Q splits the two jobs: one table chooses the best-looking action, an independently trained table says what it is worth, so a lucky overestimate in one is not confirmed by the same noise.
Use it when Q-learning’s values drift above what the rewards justify — stochastic rewards, many actions, or noisy transitions. Keep two tables, update one per step with the other as evaluator (swap at random or alternately), and act on their sum or average. It learns more slowly at first because each table sees half the data; with deterministic rewards qTarget is usually fine.
value-targetsoverestimation-biasoff-policy-learning
def crossTarget(qa, qb, hs2, rw, g, done) ≔ rw + g · (1 − done) · einsum("ia,ia->i", greedyOf(rowsAt(qa, hs2)), rowsAt(qb, hs2))
Eligibility traces
A trace table tr (S×A) remembers recently visited cells so that one TD error updates all of them. Traces decay between consecutive steps, so they must be applied one transition at a time: applying a batch to a trace at once is a different algorithm with a different fixed point.
faded
faded(tr, g, lam) · tr trace matrix S×A · g discount scalar · lam trace decay λ scalar → trace matrix S×A
Let \(E \in \mathbb{R}^{S \times A}\) (the argument tr) be a trace, \(\gamma \in [0, 1]\) (the argument g) the discount and \(\lambda \in [0, 1]\) (the argument lam) the trace decay. Then
The trace decayed by one step.
Intuition Memory of how recently each cell was visited fades by \(\gamma\lambda\) per step, so a cell visited \(k\) steps ago keeps weight \((\gamma\lambda)^k\) of credit for the current error. It is the backward-view counterpart of the \(\lambda\)-return’s weights.
Use it when time passes without a visit you want to record, or when you build your own trace rule. Normally call accumulated or replaced, which fade and mark in one step. At the start of each episode reset the trace to zeros yourself; nothing here does it. \(\lambda = 0\) forgets at once (one-step TD), \(\lambda = 1\) approaches Monte Carlo.
eligibility-tracescredit-assignment
def faded(tr, g, lam) ≔ g · lam · tr
accumulated
accumulated(tr, hs, ha, g, lam) · tr trace matrix S×A · hs one-hot state matrix 1×S · ha one-hot action matrix 1×A · g discount scalar · lam λ scalar → trace matrix S×A
Let \(E \in \mathbb{R}^{S \times A}\) (the argument tr), \(H^{s} \in \{0, 1\}^{1 \times S}\) and \(H^{a} \in \{0, 1\}^{1 \times A}\) (the arguments hs and ha) the one-hot state \(s_1\) and action \(a_1\), and \(\gamma, \lambda \in [0, 1]\). Then
An accumulating trace: decay, then add 1 to the visited cell.
Intuition Every visit adds another unit of credit on top of what remains, so a cell visited three times in a short loop carries more than 1 and will take a larger share of the next TD error.
Use it when you implement textbook SARSA(\(\lambda\)) or Q(\(\lambda\)), one transition at a time, followed by tracedStep. In tasks that loop through the same state many times the trace can exceed 1 and make updates too large; replaced caps it at 1 and is often more stable there.
eligibility-tracescredit-assignment
def accumulated(tr, hs, ha, g, lam) ≔ faded(tr, g, lam) + visits(hs, ha)
replaced
replaced(tr, hs, ha, g, lam) · tr trace matrix S×A · hs one-hot state matrix 1×S · ha one-hot action matrix 1×A · g discount scalar · lam λ scalar → trace matrix S×A
Let \(E\), \(H^{s}\), \(H^{a}\), \(\gamma\) and \(\lambda\) be as in accumulated, and let \(n_{sa} = \operatorname{visits}(H^{s}, H^{a})_{sa}\). Then
A replacing trace: decay, then set the visited cell to 1 (for traces in \([0, 1]\)).
Intuition A revisit refreshes the memory instead of stacking it: the cell is marked “just visited” at full weight 1, however often it was seen before. Credit reflects recency, not frequency.
Use it when episodes revisit states often (loops, waiting in place), where accumulating traces over-credit repeated cells; replacing traces are usually more robust there. Apply it one transition at a time before tracedStep. It takes a max, so it only resets correctly for traces that stay in \([0, 1]\) — start from zeros and do not mix it with accumulated.
eligibility-tracescredit-assignment
def replaced(tr, hs, ha, g, lam) ≔ max(faded(tr, g, lam), visits(hs, ha) > 0)
tracedStep
tracedStep(q, tr, d, rate) · q table matrix S×A · tr trace matrix S×A · d TD error of the transition vector 1 · rate step size α scalar → updated table matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q), \(E \in \mathbb{R}^{S \times A}\) (the argument tr), \(\delta \in \mathbb{R}^{m}\) (the argument d) and \(\alpha > 0\) (the argument rate). Then
The trace update \(Q \leftarrow Q + \alpha\,\delta\,E\); the entries of d are summed, so pass the single transition’s error (\(m = 1\)).
Intuition One surprise, shared out backwards: the TD error of the latest transition updates every cell in proportion to its trace, so the actions that led here — recent ones most — all learn from it at once instead of waiting for the value to propagate back one step per visit.
Use it when rewards are delayed and one-step updates propagate too slowly. Per transition: compute \(\delta\) (for example target − valuesAt(q, hs, ha) for that one sample), update the trace with accumulated or replaced, then call this. Never feed a batch of errors; they are summed into one. For batched learning without traces use nudged.
eligibility-tracescredit-assignmentvalue-learning
def tracedStep(q, tr, d, rate) ≔ q + rate · einsum("i->", d) · tr
Dyna: learning a model by counting
Dyna learns an empirical model of the environment from the same experience and then plans with it, using the backups in Decisions. Transition counts are kept as a tensor S×A×S.
tallied
tallied(hs, ha, hs2) · hs one-hot states matrix n×S · ha one-hot actions matrix n×A · hs2 one-hot next states matrix n×S → counts tensor S×A×S
Let \(H^{s} \in \{0, 1\}^{n \times S}\), \(H^{a} \in \{0, 1\}^{n \times A}\) and \(H^{s'} \in \{0, 1\}^{n \times S}\) (the arguments hs, ha and hs2). Then
The number of observed transitions \((s, a) \to t\) in the batch. Add successive batches to accumulate.
Intuition The model of the world as a logbook: for each state and action, how many times each next state followed. Nothing is assumed about the dynamics; the counts are the evidence.
Use it when you build a model-based or Dyna learner, estimate how stochastic an environment is, or collect data for planning. Keep a running S×A×S count and add each batch’s tallied to it, then normalise with modelled. Memory is \(S^2 A\), so it suits small discrete problems only.
model-learningevent-countingplanning
def tallied(hs, ha, hs2) ≔ einsum("is,ia,it->sat", hs, ha, hs2)
modelled
modelled(c) · c counts tensor S×A×S → transition probabilities tensor S×A×S
Let \(C \in \mathbb{N}^{S \times A \times S}\) (the argument c) be transition counts, and let \(N_{sa} = \sum_{t'} C_{sat'}\). Then
The maximum-likelihood transition model. Unvisited pairs give rows of zeros.
Intuition Turn counts into frequencies: if \((s, a)\) led to \(t\) in 2 of 3 tries, predict \(t\) with probability \(2/3\). It is the best guess the data alone supports, and it sharpens as counts grow.
Use it when you plan with learned dynamics, feeding it with payoffs into the backups in Decisions (the Dyna recipe). Unvisited pairs become all-zero rows, which a backup reads as “no successor at all” — the action is worth its reward and nothing after — so either explore enough or add a small pseudo-count to the counts first. With few samples the model is overconfident.
model-learningplanningprobability-normalisation
def modelled(c) ≔ c / safe(totals(c))
payoffs
payoffs(hs, ha, rw) · hs one-hot states matrix n×S · ha one-hot actions matrix n×A · rw rewards vector n → mean rewards matrix S×A
Let \(H^{s} \in \{0, 1\}^{n \times S}\) (the argument hs), \(H^{a} \in \{0, 1\}^{n \times A}\) (the argument ha) and \(r \in \mathbb{R}^n\) (the argument rw), and let \(n_{sa} = \operatorname{visits}(H^{s}, H^{a})_{sa}\). Then
The mean observed reward of each state–action pair in the batch (zero for unvisited pairs).
Intuition The reward half of the learned model: the average of what each action paid in each state, taken over this batch. Together with modelled it is a complete empirical MDP.
Use it when you plan from experience (Dyna, certainty-equivalence) or estimate the reward table of a bandit per state. It averages only the batch you pass, so for a model learned over time keep running reward sums and visit counts and divide those instead. Unvisited pairs read as reward 0, which is optimistic or pessimistic depending on your reward scale.
model-learningreward-estimationplanning
def payoffs(hs, ha, rw) ≔ scattered(hs, ha, rw) / safe(visits(hs, ha))
Building blocks
totals(c)— Let \(C \in \mathbb{R}^{S \times A \times S}\). Then \(\operatorname{totals}(C)_{sat} = \sum_{t'=1}^{S} C_{sat'}\) for every \(t\). The count of each (s, a) pair, broadcast along the successor axis; used bymodelled.
Examples
The examples below live in one file, Tabular.hb, so the class is Tabular. The doorways take state and action numbers and one-hot them with marked, as the sample models do. Everything is passed as Tensor.
One Q-learning update
A two-state, two-action table whose second row is \([2, 4]\). The agent takes action 1 in state 0, receives 1 and lands in state 1. The target is \(1 + 0.9 \cdot 4 = 4.6\), and with \(\alpha = 0.5\) the cell moves from 0 to 2.3.
open Prelude.Temporal
fn qLearnOnce(q, s, a, rw, s2, done, rate, g) ↦ nudged(q, marked(stateIds(q), s), marked(actionIds(q), a), qTarget(q, marked(stateIds(q), s2), rw, g, done), rate)
using MLambda.Hilbert.Runtime;
using Examples;
var q = (Tensor)new double[,] { { 0, 0 }, { 2, 4 } };
var learned = Tabular.QLearnOnce(q,
(Tensor)new[] { 0d }, // state
(Tensor)new[] { 1d }, // action
(Tensor)new[] { 1d }, // reward
(Tensor)new[] { 1d }, // next state
(Tensor)new[] { 0d }, // done
0.5, 0.9);
Output (verified):
qLearn = shape [2, 2] values [0, 2.3, 2, 4]
SARSA and double-Q targets
With the same table, SARSA with next action 0 bootstraps from \(q(1, 0) = 2\): \(1 + 0.9 \cdot 2 = 2.8\). For double Q, a selecting table whose row is \([5, 1]\) chooses action 0, and the evaluating table values it at 2, giving the same 2.8 — whereas plain Q-learning would have used 4.
open Prelude.Temporal
fn sarsaAim(q, s2, a2, rw, g, done) ↦ sarsaTarget(q, marked(stateIds(q), s2), marked(actionIds(q), a2), rw, g, done)
fn doubleAim(qa, qb, s2, rw, g, done) ↦ crossTarget(qa, qb, marked(stateIds(qa), s2), rw, g, done)
using MLambda.Hilbert.Runtime;
using Examples;
var q = (Tensor)new double[,] { { 0, 0 }, { 2, 4 } };
var select = (Tensor)new double[,] { { 0, 0 }, { 5, 1 } };
var sarsa = Tabular.SarsaAim(q, (Tensor)new[] { 1d }, (Tensor)new[] { 0d }, (Tensor)new[] { 1d }, 0.9, (Tensor)new[] { 0d });
var dbl = Tabular.DoubleAim(select, q, (Tensor)new[] { 1d }, (Tensor)new[] { 1d }, 0.9, (Tensor)new[] { 0d });
Output (verified):
sarsa = [2.8]
double = [2.8]
A transition model learned by counting
Three times the agent took action 0 in state 0; it landed in state 1 twice and state 0 once. The learned model gives \(\hat p(0 \mid 0, 0) = 1/3\) and \(\hat p(1 \mid 0, 0) = 2/3\); unvisited pairs stay zero.
open Prelude.Temporal
fn countedModel(q, s, a, s2) ↦ modelled(tallied(marked(stateIds(q), s), marked(actionIds(q), a), marked(stateIds(q), s2)))
using MLambda.Hilbert.Runtime;
using Examples;
var q = (Tensor)new double[,] { { 0, 0 }, { 2, 4 } }; // only its shape is used
var model = Tabular.CountedModel(q,
(Tensor)new[] { 0d, 0d, 0d }, // states
(Tensor)new[] { 0d, 0d, 0d }, // actions
(Tensor)new[] { 1d, 1d, 0d }); // next states
Output (verified, rounded to six digits; the tensor is shown flat in s, a, t order):
model = shape [2, 2, 2] values [0.333333, 0.666667, 0, 0, 0, 0, 0, 0]