Practise: Learning by Acting

Lever A has estimate $4/7=0.571428\dots$ and lever B has estimate $3/4=0.75$. The gap is $$\frac{3}{4}-\frac{4}{7}=\frac{21-16}{28}=\frac{5}{28}=0.178571\dots ,$$ which rounds to 0.179. The greedy rule picks B, because 0.75 is larger. Four pulls is thin evidence, so a rule that explores would still pull A sometimes. The gap is a difference of estimates, not a difference of true payout rates.

The return is $$5+0.5\times 0+0.5^2\times 4=5+0+1=6.$$ The zero in the middle costs nothing, and the 4 at the end counts as 1. A sequence with the same total but paid later, $0,5,4$, has return $0+2.5+1=3.5$. Both sequences pay 9 in total. Discounting separates them because it cares when each payment arrives.

The return is $$3\sum _{k=0}^{\infty }0.8^k=\frac{3}{1-0.8}=\frac{3}{0.2}=15.$$ At $\gamma =0.9$ the same reward stream is worth $3/(1-0.9)=30$, because later payments keep more of their value. The sum is finite only because the discount is below 1. At $\gamma =1$ every term is 3 and the sum diverges.

The state count is $$4\times 2=8.$$ The record count is $$4^7=16,384.$$ Each state therefore accounts for $$\frac{16,384}{8}=2,048$$ records. A table indexed by the full record needs 16,384 rows; a table indexed by the state needs eight. The compression is lossless only if the door bit carries everything about the past that changes the next step. If the door's future depends on how long it has been open, the bit is too small and the state fails the Markov test.

The two backups are $$1+0.5\times 4=3,0+0.5\times 8=4.$$ The policy averages them: $$\frac{3+4}{2}=\mathrm{3.5.}$$ The value lies between the two one-step backups, as an average must. It is not the best of the two, because the policy still takes the worse action half the time. The best-action version of the same backup would return 4, and that is the value-iteration step, not policy evaluation.

Start at $V_0=0$. The sweeps give $$V_1=2+0.75\times 0=2,$$ $$V_2=2+0.75\times 2=3.5,$$ $$V_3=2+0.75\times 3.5=\mathrm{4.625.}$$ The sequence approaches the fixed point $V=2/(1-0.75)=8$, the value of staying forever. After three sweeps the estimate is a little more than half the final value. Each sweep adds one more future reward, so the estimate climbs toward 8 from below.

The target is $$2+0.5\times 1.2=\mathrm{2.6.}$$ The TD error is $$2.6-0.6=\mathrm{2.0.}$$ The update moves the old value a quarter of the way: $$0.6+0.25\times 2.0=\mathrm{1.1.}$$ The estimate rises because the sampled step paid more than the old value promised. A second identical step would use the new value 1.1 in the target and move the estimate again. The update uses one sample, not the model, so it carries noise; the step size decides how much of that noise enters the table.

The score step is $$0.2\times 5\times (1-0.4)=0.2\times 5\times 0.6=\mathrm{0.6.}$$ The other action's probability is also 0.6, so its score moves by $$-0.2\times 5\times 0.6=-\mathrm{0.6.}$$ The log-odds of A therefore rise by $0.6+0.6=1.2$. The new probability is $$\frac{1}{1+e^{-(\log (0.4/0.6)+1.2)}}=0.689,$$ so one good episode moves the dial from 0.40 to about 0.69. The return multiplies the whole step, so a return of 0 would leave both scores unchanged.