Are policy gradient methods good for large discrete action spaces?
I don't think that (at least from a practical standpoint), there is much difference between continuous action space and discrete action space with &gt;2k discrete actions. Quoting the &quot;Continuous control with Deep RL&quot; 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 &gt;2k discrete action set has a certain structure on it. Like some actions might be &quot;closer&quot; to others. If so, then you (1) can infer some information about &quot;neighbor&quot; 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 &quot;it will not work&quot; statement. The problem is that it just would be extremely difficult to make the DQN training stable &quot;by hand&quot;. 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.