Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 35

The deadly triad: Baird's counterexample

Seven states, two actions, all rewards zero. The dashed action leads to one of the six upper states uniformly at random, the solid action to the bottom state. The value is linear in eight weights (\(2w_i+w_8\) for upper state \(i\), \(w_7+2w_8\) for the bottom state), so the true value 0 of the target policy that always takes the solid action is represented exactly by \(\mathbf w=0\). Data come from a behaviour policy that takes the solid action with probability \(q\) (the book: \(q=1/7\)). Semi-gradient TD(0) with importance ratios \(\rho=\pi_e/\pi_b\) combines off-policy data, bootstrapping and function approximation, and the weights diverge; with on-policy data they do not. The upper plot shows the weights, the lower plot \(\log_{10}\|\mathbf w\|\).

Behaviour: probability of the solid action q

Discount γ

Step size α

Steps

Update

Data and target

Try these

Initial weights \((1,1,1,1,1,1,10,1)\). Sampled: one trajectory of the behaviour policy (the next state does not depend on the current one, so the states are independent draws from the behaviour state distribution), update \(\mathbf w\leftarrow\mathbf w+\alpha\rho\,\delta\,\boldsymbol\phi(s)\), \(\delta=\gamma V(s')-V(s)\), with \(\rho=1/q\) for solid and 0 for dashed. Expected: the mean update \(\mathbf w\leftarrow\mathbf w-\alpha A\mathbf w\), \(A=\Phi^\top D(I-\gamma P)\Phi\) with \(D\) the behaviour state distribution. On-policy evaluates the behaviour policy itself from its own data (also zero value). The growth factor is the spectral radius of \(I-\alpha A\), found by power iteration: above 1 means the mean dynamics diverge.

In the lecture notes