Derive: Learning by Acting

Taking the expectation of the return recursion under the forced policy gives $$V(A)=1+\frac{1}{2}V(B),V(B)=0+\frac{1}{2}V(A).$$ Substituting the second line into the first gives $$V(A)=1+\frac{1}{2}\cdot \frac{1}{2}V(A)=1+\frac{1}{4}V(A).$$ Moving the $V(A)$ term to the left gives $$\frac{3}{4}V(A)=1,$$ so $$V(A)=\frac{4}{3}=1.333\dots ,V(B)=\frac{1}{2}\cdot \frac{4}{3}=\frac{2}{3}=0.666\dots .$$ The direct check starts at A and follows the path. The rewards are $1,0,1,0,\dots$ at steps $0,1,2,3,\dots$, so $$V(A)=1+\frac{1}{2}\cdot 0+\frac{1}{4}\cdot 1+\frac{1}{8}\cdot 0+\cdots =\sum _{k=0}^{\infty }{\left(\frac{1}{4}\right)}^k=\frac{1}{1-\frac{1}{4}}=\frac{4}{3}.$$ The two routes agree because the return recursion and the Bellman equation are the same statement once the policy and the transitions are fixed. Section 23.2 supplies the recursion; section 23.4 turns it into one equation per state. The derivation also shows why the value is finite: the reward returns every two steps, and each return is discounted by $1/4$.

The return is $$\sum _{k=0}^{\infty }{\gamma }^k{2}^k=\sum _{k=0}^{\infty }(2\gamma {)}^k.$$ This is a geometric series with ratio $x=2\gamma$. It converges exactly when $2\gamma <1$, that is, when $$\gamma <\frac{1}{2}.$$ On that set its value is $$\frac{1}{1-2\gamma }.$$ At $\gamma =0.4$ the ratio is $0.8$ and the return is $$\frac{1}{1-0.8}=5.$$ At $\gamma =0.9$ the ratio is $1.8$, which is above 1. The terms $1.8^k$ grow, and the partial sums grow without bound; the return is infinite. The counterexample shows that a discount below 1 is not by itself enough. The chapter's guarantee needs bounded rewards, and the bound can fail when the reward itself grows with time. A designer who wants a finite return must control both the discount and the reward scale.

Take logs: $$\log {\pi }_A=z_A-\log \left(e^{z_A}+e^{z_B}\right).$$ Differentiate with respect to each score: $$\frac{\partial \log {\pi }_A}{\partial z_A}=1-\frac{e^{z_A}}{e^{z_A}+e^{z_B}}=1-{\pi }_A,$$ $$\frac{\partial \log {\pi }_A}{\partial z_B}=0-\frac{e^{z_B}}{e^{z_A}+e^{z_B}}=-{\pi }_B.$$ Because the two probabilities sum to 1, ${\pi }_B=1-{\pi }_A$. The REINFORCE rule adds $\alpha G$ times the slope to each score, so $$z_A\leftarrow z_A+\alpha G(1-{\pi }_A),z_B\leftarrow z_B-\alpha G(1-{\pi }_A).$$ The log-odds change is the difference of the two steps: $$\Delta d=\alpha G(1-{\pi }_A)+\alpha G(1-{\pi }_A)=2\alpha G(1-{\pi }_A).$$ When ${\pi }_A=1/2$, the factor $2(1-{\pi }_A)$ equals 1, so the shift is $\alpha G$. That is the equal-score case in the chapter's worked example. Away from equal scores the shift is smaller when A is already likely and larger when A is unlikely. For the numbers given, the old log-odds are $$d_0=\log \frac{0.2}{0.8}=\log 0.25=-1.386294\dots ,$$ and the shift is $$\Delta d=2\times 0.05\times 5\times (1-0.2)=\mathrm{0.4.}$$ The new log-odds are $$d_1=-1.386294+0.4=-0.986294\dots .$$ The new probability is $${\pi }_A=\frac{1}{1+e^{-d_1}}=\frac{1}{1+e^{0.986294\dots }}=0.27164\dots ,$$ which rounds to 0.272. The update raises A's probability from 0.2 to about 0.272. The exact log-odds step is a property of the two-score softmax, not of this example; it is why the rule can be read as moving a dial whose step shrinks as the chosen action becomes more likely.