David Silver argues, in his Reinforcement Learning course, that policy-based reinforcement learning (RL) is more effective than value-based RL in high-dimensional action spaces. He points out that the implicit policy (e.g., $\epsilon$-greedy) in Q-learning or Sarsa looks for a maximum for $Q_\pi$ in the action space in each time step, which may be infeasible when there are many actions.
However, from my understanding, policy gradient methods that use a neural network to represent the policy choose their actions from the output of a softmax:
$$ \pi(a|s, \theta) = \frac{e^{h(s, a, \theta)}}{\sum_b e^{h(s, b, \theta)}}, $$
where the denominator normalizes between all possible actions $b\in \mathcal{A}$ and $h(s, a, \theta)$ is a numerical preference (notation from the Reinforcement Learning book by Sutton and Barto) that is usually represented by a neural network.
By using a softmax in action preferences, don't we compute $\pi(a|s, \theta)$ for all actions, ending up with the same computational complexity as in value-based methods?