Are policy gradient methods good for large discrete action spaces?

Question

I have seen this question asked primarily in the context of continuous action spaces.

I have a large action space (~2-4k discrete actions) for my custom environment that I cannot reduce down further:

I am currently trying DQN approaches but was wondering that given the large action space - if policy gradient methods are more appropriate and if they are appropriate for large action spaces that are discrete as in my scenario above. I have seen answers to this question with regard to large continuous action spaces.

Finally - I imagine there isn't a simple answer to this but: Does this effectively mean DQN will not work?

Answer 1

I don't think that (at least from a practical standpoint), there is much difference between continuous action space and discrete action space with >2k discrete actions. Quoting the "Continuous control with Deep RL" paper - which I'd recommend as a starting point for your investigation:

An obvious approach to adapting deep reinforcement learning methods such as DQN to continuous domains is to to simply discretize the action space. ... Such large action spaces are difficult to explore efficiently, and thus successfully training DQN-like networks in this context is likely intractable. Additionally, naive discretization of action spaces needlessly throws away information about the structure of the action domain, which may be essential for solving many problems.

The last sentence in the quote above is the most important point for dealing with your problem. The fundamental issue is inability to efficiently explore such a large action space - so the idea is to use its structure. I'm sure that your >2k discrete action set has a certain structure on it. Like some actions might be "closer" to others. If so, then you (1) can infer some information about "neighbor" actions even if you never took them (2) do some exploration by adding noise to your policy-preferred action.

The Actor-Critic class of algorithms matches perfectly the steps (1) and (2) above. The Critic Q-value network learns about your state-action space and the Actor policy network returns actions that you could smear.

Are policy gradient methods good for large discrete action spaces?

The Actor-Critic class of RL algorithms is a subclass of the Policy Gradient algorithms. So, the answer is yes - it looks like going that way is your best shot at making progress.

Does this effectively mean DQN will not work?

I don't think that there is a strict "it will not work" statement. The problem is that it just would be extremely difficult to make the DQN training stable "by hand". In principle you might be able to construct a neural architecture that captures the state-action space structure. And then figure out how to perform efficient exploration. And then ensure that nothing explodes anywhere. But that's exactly what DDPG and then TRPO/PPO approaches would do for you.

Answer 2

A side note for other people who have similar questions. A large number of actions is also problematic for the policy network. Basically, the policy network has an output for every action (one-hot encoding), and computing softmax over a large number of classes (more than 1K approximately) is not viable. One can use other activation functions or techniques that make a network more generalizable for such a large number of classes.