Function approximation, off-policy instability, and deep-RL limits — Examples

Let the state set be $\{s\}$ with one available action, deterministic transition $s\to s$, reward $0$, and discount $0\le \gamma <1$. The unique behavior and target policies coincide, the state weighting is $\mu (s)=1$, the feature is $\varphi (s)=1$, and the value estimate is $v_w(s)=w$. For a fixed step size $0<\alpha \le 1$, apply the one-step TD(0) update $w_{n+1}=w_n+\alpha (0+\gamma v_{w_n}(s)-v_{w_n}(s))$ from any $w_0\in \mathbb{R}$. Then $w_n\to 0$.

The finite one-step transition/reward model and stationary policy.

The linear feature-value convention.

A geometric sequence with ratio of absolute value less than one tends to zero.

Tsitsiklis and Van Roy, “An Analysis of Temporal-Difference Learning with Function Approximation,” §IV.

The circle is the sole state and the loop is its deterministic transition under the unique action; its reward is zero. The diagram only displays the model stated above and is not used in the calculation.

diagram failed to render:
\begin{tikzpicture}[>=stealth, every node/.style={font=\small}]
  \node[circle,draw] (s) at (0,0) {$s$};
  \draw[->] (s) to[loop above] node[above] {$a,\ r=0$} (s);
\end{tikzpicture}

Use the seven-state MDP with zero rewards, discount $\gamma =0.99$, dashed transitions uniform over the six upper states, solid transitions to the seventh state, behavior probabilities $6\mathrm{/}7$ dashed and $1\mathrm{/}7$ solid, target policy always solid, feature values $2w_i+w_8$ at upper state $s_i$ and $w_7+2w_8$ at $s_7$, and initial vector $w_0=(1,1,1,1,1,1,10,1)$. Under the uniform-state expected semi-gradient TD(0) update, with step size $\alpha =1\mathrm{/}100$, the first reduced weight vector $(a,b,c)$, where $a=w_1=\cdots =w_6$, $b=w_7$, and $c=w_8$, is $(4486\mathrm{/}4375,174997\mathrm{/}17500,9413\mathrm{/}8750)$; in particular, the first six weights and $w_8$ increase on this update.

For every positive step size, both stated expected update sequences diverge from the specified initial vector.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed., §11.2.

Assume Choice for the infinite trajectory laws and set $\gamma =1\mathrm{/}2$. In MRP 1, the states are $A,B$; $A\to B$ has reward $0$ deterministically, while $B\to A$ has reward $1$ and $B\to B$ has reward $-1$, each with probability $1\mathrm{/}2$. Its stationary weighting is $(1\mathrm{/}3,2\mathrm{/}3)$. In MRP 2, the states are $A,B,B^{\mathrm{\prime }}$; $A\to B$ and $A\to B^{\mathrm{\prime }}$ each have reward $0$ and probability $1\mathrm{/}2$, $B\to A$ has reward $1$ deterministically, and $B^{\mathrm{\prime }}\to B$ and $B^{\mathrm{\prime }}\to B^{\mathrm{\prime }}$ each have reward $-1$ and probability $1\mathrm{/}2$. Its stationary weighting is $(1\mathrm{/}3,1\mathrm{/}3,1\mathrm{/}3)$. Both processes use feature $\psi (A)=(1,0)$ and $\psi (B)=\psi (B^{\mathrm{\prime }})=(0,1)$, and they induce the same stationary feature/reward sequence law. Their state-weighted mean square Bellman errors are

The unique minimizers are $(0,0)$ for MRP 1 and $(-2\mathrm{/}7,1\mathrm{/}7)$ for MRP 2. Their minimum Bellman errors are $0$ and $25\mathrm{/}42$, respectively, while ${\mathrm{BE}}_2(0,0)=2\mathrm{/}3$.

The axiom used to form the infinite trajectory laws.

The state-weighted mean square Bellman-error objective.

The general matched-observation MRP theorem and exact minimizing parameters.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed., §11.6.

Hutter, Yang-Zhao, and Majeed, “Conditions on Features for Temporal Difference-Like Methods to Converge,” §4.