Why does REINFORCE perform badly at first in Sutton and Barto Figure 13.1?

Question

In Sutton and Barto (PDF, page 265), 2nd edition, Figure 13.1 applies REINFORCE to the "short corridor with switched actions" environment from Example 13.1. The figure looks like this:

My question is, why is the initial performance so poor? I believe it should be close to optimal even without any training.

My reasoning is this: If we initialize the algorithm with $\boldsymbol{\theta} = \boldsymbol{0}$, then the initial policy has

$$\pi({\tt right}|s,\boldsymbol{\theta}) = \frac{e^{\theta_1}}{e^{\theta_1} + e^{\theta_2}} = 0.5.$$

And from the figure in Example 13.1 (p. 323) --

-- we know that a policy that goes $\tt{right}$ with probability 0.5 in every state has an expected value that is very close to that of the optimal policy, around $-12$ or so. So shouldn't the policies produced by REINFORCE start close to optimal with essentially no training, and then just improve little to none after that?

My own experiment supports my hunch:

But it's possible I'm doing something wrong, both theoretically and computationally.

Answer 1

I'm actually working on this example too, implemented the REINFORCE algorithm, and got the same result as you. My only guess is that the authors chose a different initial $\theta$ value to show the convergence properties for different choices of $\alpha$. (For example maybe something like $\theta_0 = [-3; 0]$ so the initial probability of right action is ~0.05 and the initial expected cost is quite large.)