The expression you are looking at in the link, $G_t \nabla_{\theta} \text{ln}(\pi(A_t|S_t,\theta_t))$, is not the cost function, but the estimated gradient of the cost function. You cannot simply remove the $\nabla_{\theta}$ to see the cost function, because the state distribution that weights components of the cost function (i.e. how often you will observe each trajectory) depends critically on $\theta$.
The real cost function would be the negative of expected return from the start (or stable for non-episodic) state distribution, i.e. $-J(\theta)$. This does not have a simple expansion, because it must be summed up over the distribution of states and the policy, both of which depend on $\theta$.
Usually in reinforcement learning, the optimisation is not stated as a cost function to minimise, but as an expression to maximise. We want to maximise $J(\theta)$ which summarises our expected return. Hence a factor of the gradient is added to $\theta$ during update steps.
From comments:
if the policy stumbles upon a set of parameters which makes $G_t=0$, doesn't that make the estimated gradient zero hence causing the policy to stop improving
Partially correct.
A return of zero from any single trajectory will make the updates from all actions also be zero, regardless of whether or not a return of zero is a good result. This motivates REINFORCE with baseline or Actor-Critic approaches that don't use final return $G_t$, but advantage, or a similar baselined value instead. These methods are less sensitive to absolute value of returns.
For the agent to get stuck with all zero gradients though, all possible trajectories would have to give a return of zero. This would be a problem for any experience-based system, and there is no reinforcement learning system that can find better actions if the feedback is all the same.
In fact this is also a problem regardless of what the fixed value is - if all experience returns the same end return, then nothing can be learned to differentiate actions. Simple REINFORCE would actually generate gradients (because $G_t$ multiplier will be non-zero), and it might look like it is learning something because $\theta$ will change with gradient-based steps. But actually it will end up choosing a policy pseudo-randomly, because as far as the agent can tell all policies are the same.
One thing to bear in mind is that the gradient estimates generated in REINFORCE (and policy gradients in general) are biased. You don't know the true gradient, and there is no simple way to remove the bias for a single sample - you have to rely on the gradient steps across very many samples to even out this bias. In fact you can add almost any offset to the multiplier $G_t$, provided it doesn't depend immediately on the policy, and you still have a valid gradient estimate for update steps. This is why advantage-based systems work, they choose an offset based on state value which conveniently reduces variance on each sample.
