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

Let $S$ be a nonempty finite state set of a finite Markov decision process, let $0\le \gamma <1$, and let $\pi$ be a stationary Markov policy. Define the policy Bellman operator by

Let $\mu :S\to [0,1]$ satisfy ${\sum }_{s\in S}\mu (s)=1$, and let ${\varphi }_1,\dots ,{\varphi }_d:S\to \mathbb{R}$ be a finite list of feature functions. Define $f{\sim }_{\mu }g$ when ${\sum }_{s\in S}\mu (s)(f(s)-g(s){)}^2=0$, let $H_{\mu }$ be the quotient of ${\mathbb{R}}^S$ by this relation, and define $⟨[f{]}_{\mu },[g{]}_{\mu }{⟩}_{\mu }={\sum }_{s\in S}\mu (s)f(s)g(s)$. Then this quotient is a finite-dimensional real inner-product space. The span $V_{\mu }$ of $[{\varphi }_1{]}_{\mu },\dots ,[{\varphi }_d{]}_{\mu }$ is finite-dimensional, and every $h\in H_{\mu }$ has a unique orthogonal projection ${\mathrm{\Pi }}_{\mu }h\in V_{\mu }$. Here orthogonal means that $h-{\mathrm{\Pi }}_{\mu }h$ has inner product zero with every vector in $V_{\mu }$. For each fixed $w\in {\mathbb{R}}^d$, put $v_w(s)={\sum }_{j=1}^d{\varphi }_j(s)w_j$ and ${\delta }_w=[T^{\pi }{v}_w-v_w{]}_{\mu }$. Then $\mathrm{\parallel }{\delta }_w{\mathrm{\parallel }}_{\mu }^2$ and $\mathrm{\parallel }{\mathrm{\Pi }}_{\mu }{\delta }_w{\mathrm{\parallel }}_{\mu }^2$ are well-defined real numbers, including when some state weights vanish or the features are linearly dependent.

The finite transition/reward model and stationary Markov policies.

The expected discounted policy Bellman operator.

Finite indexed sums over the state set.

Every vector in a real inner-product space has a unique orthogonal projection onto a finite-dimensional subspace.

Finite sums of nonnegative terms vanish only when each term vanishes.

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

Let $S$ be a nonempty finite state set of a finite Markov decision process, let $0\le \gamma <1$, let $\pi$ be a stationary Markov policy, and let $\mu :S\to [0,1]$ satisfy ${\sum }_{s\in S}\mu (s)=1$. The function $\mu$ is a fixed state-weighting distribution; it need not be stationary for $\pi$. Let $d$ be a positive integer, let $\varphi :S\to {\mathbb{R}}^d$ be a feature map, and for $w\in {\mathbb{R}}^d$ put $v_w(s)=\varphi (s{)}^{\mathsf{T}}w$.

For real functions $f,g:S\to \mathbb{R}$, write $f{\sim }_{\mu }g$ when ${\sum }_{s\in S}\mu (s)(f(s)-g(s){)}^2=0$. Let $[f{]}_{\mu }$ denote the equivalence class of $f$ and define $⟨[f{]}_{\mu },[g{]}_{\mu }{⟩}_{\mu }={\sum }_{s\in S}\mu (s)f(s)g(s)$ and $\mathrm{\parallel }[f{]}_{\mu }{\mathrm{\parallel }}_{\mu }^2=⟨[f{]}_{\mu },[f{]}_{\mu }{⟩}_{\mu }$. Let $H_{\mu }$ be the resulting finite-dimensional real inner-product space, and let $V_{\mu }$ be the span in $H_{\mu }$ of the equivalence classes of the $d$ coordinate feature functions.

For $h\in H_{\mu }$, let ${\mathrm{\Pi }}_{\mu }h$ be the unique vector in $V_{\mu }$ whose difference from $h$ is orthogonal to every vector in $V_{\mu }$. The Bellman-error vector for $v_w$ is ${\delta }_w=[T^{\pi }{v}_w-v_w{]}_{\mu }$. Define the mean square Bellman error and mean square projected Bellman error by ${\mathrm{BE}}_{\mu }(w)=\mathrm{\parallel }{\delta }_w{\mathrm{\parallel }}_{\mu }^2$ and ${\mathrm{PBE}}_{\mu }(w)=\mathrm{\parallel }{\mathrm{\Pi }}_{\mu }{\delta }_w{\mathrm{\parallel }}_{\mu }^2$.

A finite state/action model with a joint one-step reward-transition law and stationary Markov policies.

The finite discounted policy Bellman operator.

Finite indexed sums.

The finite weighted quotient and feature span admit the stated unique projection.

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

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

Let the states be $S=\{s_1,\dots ,s_7\}$ and the two actions available at each state be $\mathrm{d}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{e}\mathrm{d}$ and $\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{i}\mathrm{d}$. All rewards are zero and $\gamma =0.99$. Under $\mathrm{d}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{e}\mathrm{d}$, the next state is each of $s_1,\dots ,s_6$ with probability $1\mathrm{/}6$; under $\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{i}\mathrm{d}$, the next state is $s_7$ with probability $1$. The behavior policy has $b(\mathrm{d}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{e}\mathrm{d}\mid s)=6\mathrm{/}7$ and $b(\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{i}\mathrm{d}\mid s)=1\mathrm{/}7$ at every state, and the target policy selects $\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{i}\mathrm{d}$ with probability $1$. Use the uniform state weighting $\mu (s)=1\mathrm{/}7$. For standard basis vectors $e_1,\dots ,e_8$ of ${\mathbb{R}}^8$, set $\varphi (s_i)=2e_i+e_8$ for $1\le i\le 6$ and $\varphi (s_7)=e_7+2e_8$, and define $v_w(s)=\varphi (s{)}^{\mathsf{T}}w$. For a behavior transition $(S,A,S^{\mathrm{\prime }})$, draw $S$ from $\mu$, draw $A$ from $b(\cdot \mid S)$, and draw $S^{\mathrm{\prime }}$ from the stated action transition law. Put $\rho =\pi (A\mid S)\mathrm{/}b(A\mid S)$ and $\delta =\gamma v_w(S^{\mathrm{\prime }})-v_w(S)$, and define the expected semi-gradient TD(0) update by ${\bar{w}}^{+}=w+\alpha {\mathbb{E}}_{\mu ,b}[\rho \delta \varphi (S)]$. Also define the synchronous expected dynamic-programming update by $w^{+}=w+\frac{\alpha }{7}{\sum }_{s\in S}((T^{\pi }{v}_w)(s)-v_w(s))\varphi (s)$. For every step size $\alpha >0$, both deterministic update sequences starting at $w_0=(1,1,1,1,1,1,10,1)$ have Euclidean norm $\mathrm{\parallel }w{\mathrm{\parallel }}_2=({\sum }_{i=1}^8{w}_i^2{)}^{1\mathrm{/}2}$ tending to infinity. This is a claim about the stated expected/deterministic updates; it asserts no probability-one divergence result for individual stochastic TD trajectories.

The finite state/action transition model and stationary policies.

The fixed state weighting, feature map, and policy Bellman operator.

The expected discounted value of one policy-controlled transition.

An eigenvalue is a scalar with a nonzero eigenvector.

A positive geometric sequence with ratio greater than one diverges to infinity.

The Euclidean inner product satisfies Cauchy–Schwarz.

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

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

The “deadly triad” is used here only as an explanatory name for the interaction among off-policy sampling, bootstrapping, and function approximation. This example does not prove that every method using those ingredients diverges, and it gives no general convergence or divergence theorem for deep neural networks.

In the diagram, each circle is an actual state. Solid-action transitions are shown as solid arrows to $s_7$. The dashed box is a routing symbol, not a state: a two-segment dashed path represents one dashed-action transition, whose endpoint is chosen uniformly from the six upper states. All rewards are zero. The diagram restates the model; the proof uses the explicit transition probabilities and feature vectors above.

diagram failed to render:
\begin{tikzpicture}[>=stealth, every node/.style={font=\small}]
  \node[circle,draw] (s1) at (0,1.6) {$s_1$};
  \node[circle,draw] (s2) at (1.5,1.6) {$s_2$};
  \node[circle,draw] (s3) at (3,1.6) {$s_3$};
  \node[circle,draw] (s4) at (4.5,1.6) {$s_4$};
  \node[circle,draw] (s5) at (6,1.6) {$s_5$};
  \node[circle,draw] (s6) at (7.5,1.6) {$s_6$};
  \node[circle,draw] (s7) at (3.75,-0.2) {$s_7$};
  \node[draw,dashed,rounded corners,align=center] (U) at (9.5,1.6) {uniform draw\\from $\{s_1,\ldots,s_6\}$};
  \foreach \s in {s1,s2,s3,s4,s5,s6} {
    \draw[dashed,->,thin] (\s) to[bend left=10] node[above,sloped] {$\mathrm{dashed}$} (U);
    \draw[solid,->] (\s) to[bend right=12] node[below,sloped] {$\mathrm{solid}$} (s7);
  }
  \draw[dashed,->,thin] (s7) to[bend left=10] node[above,sloped] {$\mathrm{dashed}$} (U);
  \draw[solid,->] (s7) to[loop below] node[below] {$\mathrm{solid}$} (s7);
  \foreach \s in {s1,s2,s3,s4,s5,s6} {
    \draw[dashed,->,thin] (U) to[bend left=7] (\s);
  }
  \node[align=left,anchor=west] at (8.8,-0.5) {$b(\mathrm{dashed}\mid s)=6/7$\\$b(\mathrm{solid}\mid s)=1/7$\\$\pi(\mathrm{solid}\mid s)=1$};
\end{tikzpicture}

Assume the Axiom of Choice to form the infinite trajectory laws. Fix $0\le \gamma <1$. An actionless finite Markov reward process (MRP) here means a nonempty finite state set with a joint probability law for next state and reward at each state. Consider the following two MRPs, each with its stated stationary state-weighting distribution, meaning that one transition leaves the distribution unchanged.

In MRP 1 the state set is $\{A,B\}$, with transitions $A\to B$ receiving reward $0$ deterministically and $B\to A$ receiving reward $1$ with probability $1\mathrm{/}2$ or $B\to B$ receiving reward $-1$ with probability $1\mathrm{/}2$. Its stationary weighting is ${\mu }_1(A)=1\mathrm{/}3$, ${\mu }_1(B)=2\mathrm{/}3$.

In MRP 2 the state set is $\{A,B,B^{\mathrm{\prime }}\}$, with transitions $A\to B$ and $A\to B^{\mathrm{\prime }}$ each receiving reward $0$ with probability $1\mathrm{/}2$, $B\to A$ receiving reward $1$ deterministically, and $B^{\mathrm{\prime }}\to B$ or $B^{\mathrm{\prime }}\to B^{\mathrm{\prime }}$ each receiving reward $-1$ with probability $1\mathrm{/}2$. Its stationary weighting is ${\mu }_2(A)={\mu }_2(B)={\mu }_2(B^{\mathrm{\prime }})=1\mathrm{/}3$.

In both processes the observed feature is $\psi (A)=(1,0)$ and $\psi (B)=\psi (B^{\mathrm{\prime }})=(0,1)$, so a parameter $w=(a,b{)}^{\mathsf{T}}$ assigns values $v_w(A)=a$ and $v_w(B)=v_w(B^{\mathrm{\prime }})=b$. Starting from the stated stationary weighting, the two processes induce the same probability law on the observed feature/reward sequence $((\psi (S_n),R_{n+1}){)}_{n\ge 0}$. Their mean square Bellman errors, defined as the stationary-weighted square of the conditional expected one-step TD error, are

MRP 1 has the unique minimizer $(a,b)=(0,0)$ and minimum $0$. With $D=1+\gamma +{\gamma }^2$, MRP 2 has the unique minimizer $(a,b)=(-\frac{\gamma }{D},\frac{\gamma }{2D})$ and minimum $\frac{(\gamma +2{)}^2}{6D}$; also ${\mathrm{BE}}_2(0,0)=2\mathrm{/}3$. For every $0<\gamma <1$ the minimizing parameters differ. Thus the Bellman-error objective and, for positive discount, its minimizing parameter are not determined by the observable feature/reward sequence law. An MRP here has no action-dependent policy; it is not an unseen-action offline-MDP policy-impossibility claim.

The axiom used for the infinite trajectory-law construction.

Finite joint reward-transition laws and their state-transition marginals.

The state-weighted Bellman-error objective as the squared norm of the expected TD-error vector.

The finite discounted policy Bellman operator used for the conditional expected residual.

A finite MDP with a stationary policy has a reward-state path law under Choice.

Uniqueness of a path law with specified finite-prefix kernels under Choice.

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,” §§2 and 4.

The exact MRP 2 minimizer above has one-sided limit $(-1\mathrm{/}3,1\mathrm{/}6)$ as $\gamma \uparrow 1$. At the excluded endpoint $\gamma =1$, the objective is $\frac{1}{3}((b-a{)}^2+(1+a-b{)}^2+1)$ and is minimized exactly when $b-a=1\mathrm{/}2$, so $(-1\mathrm{/}2,0{)}^{\mathsf{T}}$ is one of multiple endpoint minimizers. It is not the limit of the unique minimizers for $\gamma <1$, despite the book’s printed limiting value. The exact finite-$\gamma$ calculation, rather than that limiting value, is used in the Statement.

Each arrow is a transition and its label gives the reward; the probability is shown in parentheses when that state has two outgoing edges. $B$ and $B^{\mathrm{\prime }}$ have the same feature, while $A$ has a separate feature. The diagrams encode the transition data in the Statement; the proof uses the explicit kernels and feature map.

diagram failed to render:
\begin{tikzpicture}[>=stealth, every node/.style={font=\small}]
  \node[circle,draw] (a1) at (0,0) {$A$};
  \node[circle,draw] (b1) at (2,0) {$B$};
  \draw[->] (a1) to[bend left=18] node[above] {$0$} (b1);
  \draw[->] (b1) to[bend left=18] node[below] {$1\;(1/2)$} (a1);
  \draw[->] (b1) to[loop right] node[right] {$-1\;(1/2)$} (b1);
  \node at (1,-1.25) {MRP 1};

  \node[circle,draw] (a2) at (5,0) {$A$};
  \node[circle,draw] (b2) at (7,0.45) {$B$};
  \node[circle,draw] (bp) at (9,0.45) {$B'$};
  \draw[->] (a2) to[bend left=18] node[above] {$0\;(1/2)$} (b2);
  \draw[->] (a2) to[bend right=18] node[below] {$0\;(1/2)$} (bp);
  \draw[->] (b2) to[bend left=22] node[above] {$1$} (a2);
  \draw[->] (bp) to[bend left=14] node[above] {$-1\;(1/2)$} (b2);
  \draw[->] (bp) to[loop right] node[right] {$-1\;(1/2)$} (bp);
  \node at (7,-1.25) {MRP 2};
\end{tikzpicture}