Tabular TD(0) policy prediction

Inputs: A finite MDP with nonempty state set $S$, discount $0\le \gamma <1$, terminal set $S_{†}\subseteq S$, stationary policy $\pi$, an initial-state rule specifying a distribution on $S$ at each episode boundary (a fixed distribution $\nu$ sampled independently for each episode is a special case), an episode budget $m\in \mathbb{N}\cup \{\mathrm{\infty }\}$, an initial table $V_0:S\to \mathbb{R}$ with $V_0(s)=0$ on $S_{†}$, and a step-size rule giving ${\alpha }_n(S_n)\in [0,1]$ from the available history before the next reward and state are observed. Deterministic per-state sequences ${\alpha }_k(s)$ indexed by visit count are a special case. Assume the Axiom of Choice for the path laws defining $V^{\pi }$, and that every episode used reaches $S_{†}$ almost surely from its start state.

Interpret successive draws on finite discrete transition-record spaces, including a restart record at each episode boundary. Conditional on the full available history and its current state $s$, choose the action using $\pi (a\mid s)$ and the next reward/state using $p(s^{\mathrm{\prime }},\rho \mid s,a)$; the initial-state rule gives the restart kernel. Require all sampling and step-size rules to be measurable with respect to their available histories. The table and counts are computed from these records. Under the stated AC assumption, the history-dependent kernel construction supplies this law, with a fixed stop symbol after a finite budget.

Output: The value table after every transition update and after every completed episode. A finite budget returns the final table after those episodes; budget $\mathrm{\infty }$ specifies the successive tables indefinitely, with no final output or convergence assertion.

Initialize $V=V_0$ and visit counts $C(s)=0$ for $s\mathrm{\notin }{S}_{†}$. For each episode allowed by the budget, sample its start state using the initial-state rule. If it is terminal, end that episode without an update. Otherwise, at each current nonterminal state $S_n$, sample $A_n$ from $\pi (\cdot \mid S_n)$, obtain ${\alpha }_n(S_n)$ from the step-size rule, and then observe $(R_{n+1},S_{n+1})$ from the MDP's joint reward-transition law conditional on the available history and selected pair. For a visit-index schedule use $k=C(S_n)$. Form

$${\delta }_n^V=R_{n+1}+\gamma V_n(S_{n+1})-V_n(S_n),$$

where the continuation term is zero when $S_{n+1}\in S_{†}$. Update

$$V_{n+1}(S_n)=V_n(S_n)+{\alpha }_n(S_n){\delta }_n^V\mathrm{.}$$

Leave every other coordinate unchanged, increment $C(S_n)$, and output the updated table. If $S_{n+1}$ is terminal, end the episode; otherwise continue from $S_{n+1}$. The next episode starts by applying the initial-state rule again, retaining the table and counts; stop after $m$ completed episodes when $m$ is finite. Thus the sampled transitions use the policy whose value is estimated. This is a one-step bootstrapped prediction procedure and makes no convergence claim.

Under AC, successive history-dependent probability kernels give the sampling law.

The finite joint reward-transition law and stationary policies.

The discounted return and state value under a stationary policy.

The policy Bellman operator.

The policy value is a fixed point of its Bellman operator.

The episodic return and state TD-error conventions.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.