# Why are policy gradient methods more effective in high-dimensional action spaces?

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?

• Different but interesting related question Dec 16, 2022 at 12:58

Above softmax in action preferences is used for policy gradient methods with (large) spaces with discrete actions, while for continuous spaces with infinite number of actions Gaussian distribution is often used instead thus you don't need to compute all those potentially large amount of numerical preferences via NN or whatever models.

In the above softmax case sometimes you may simply fit the preferences as linear function of the feature vector $$x(s,a)$$ which is often much simpler than computing action values via Monte Carlo, TD or DP which all have much higher time complexity. Indeed in these cases policy gradient methods are more effective to learn since policy function is in fact much easier to approximate than action value function or certain types of domain knowledge can be incorporated in policy function as explained in the paper Why Most Decisions Are Easy in Tetris.

most of the problems are easy in the following sense: One can choose well among the available actions without knowing an evaluation function that scores well in the game. This is a consequence of three conditions that are prevalent in the game: simple dominance, cumulative dominance, and noncompensation. These conditions can be exploited to develop faster and more effective learning algorithms. In addition, they allow certain types of domain knowledge to be incorporated with ease into a learning algorithm

Finally if your softmax has to employ action values to compute the preferences such as in most actor-critic methods, then yes of course it has same computational complexity as its corresponding value-based methods during each time step which you cannot avoid. But additionally softmax would allow agent to explore different actions by sampling from the resulting distribution, rather than always select the action with the highest estimated value, thus it can find stochastic optimal policies in problems with heavy function approximations while "deterministic" value-based methods cannot.

• It's not the complexity of the function approximator I'm confused about. Rather, at "inference" time, the softmax output vector has the same dimensionality as the number of actions for a given state, so the complexity of choosing an action ends up being the same whether we're using a policy or value-based method. (Apparently that's not the case and policy-based methods are more efficient, I just don't see why.) Dec 17, 2022 at 16:05
• See my latest edit if that helps. Dec 17, 2022 at 22:48
• Thanks for the reply! So if I read correctly, you don't think policy-based methods are more efficient at choosing an action than value-based methods (setting aside the complexity of learning the preferences themselves)? Dec 18, 2022 at 12:40
• The complexity of learning the preferences themselves using action values in softmax as explained above is of same complexity as, say, Q/sarsa-learning. Setting aside this complexity, once you have the (approximated) softmax at hand in each time step, then you just need to sample one function value from it to select an action to proceed to policy parameters update, no need to worry about all the other numerous actions. Dec 18, 2022 at 17:34
• Additionally, though with same comupational complexity as value-based apporach in your case, the softmax function has the advantage of being able to smoothly interpolate between exploitation (selecting the action with the highest action-value) and exploration (selecting actions randomly with a probability that is proportional to their action-values). This can be useful for improving the efficiency of learning by allowing the agent to balance exploration and exploitation. Dec 18, 2022 at 22:09