Deep Q-Learning with multiple discrete actions

Question

I am working on a DQN project with Pytorch, where I should choose multiple discrete actions, each in a range, say, (0, 15). I am wondering how I can model it, such that the sum of actions is 15. Does anyone know how to model that?

Answer 1

As I understand it, you have a problem with a large action space - a vector of 10 integer variables. You also have a constraint on what valid actions should look like.

Even with the action vector discretised to integer amounts, there are millions of possible actions. This is beyond anything you can reasonably solve with value-based methods such as Q-learning. The problem is deriving the policy from the action value estimates. To select a greedy action, you need to find the action which maximises $\hat{q}(s,a, \theta)$, which in your case would mean either an insanely large output vector (covering all possible action combinations) or very large input batches to maximise over.

So, DQN is not really available to you as a method, before considering the constraint. What can you use instead? Any policy-gradient method or actor-critic method should work. These are more fiddly to understand and implement than value-based methods, although there are plenty of references for PyTorch, for example the PFRL library implements A3C, PPO, DDPG which would all be suitable as a start.

What a policy gradient method does for your problem is allow you to define a policy function $\pi(s, \theta)$ which will either output a single action or the parameters for an action probability distribution that you can sample from. The latter is actually more common, to create a neural network that outputs the parameters of a probability distribution. This allows for exploration in an on-policy approach. DDPG (Deep Deterministic Policy Gradients) is an example of a method that uses a deterministic policy function, but there is still an action sampling stage because DDPG adds a noise function to the policy in order to explore.

In your case, you could build a policy network that output a vector of 10 real values to repesent the means of the distribution, plus either 1 or 10 standard deviations if you are not using something like DDPG. Then the action choice could be sampled from the distribution that this defined.

This would not solve your other problem - a constraint on the sum of elements of the vector. You also have an implied constraint of a minimum value for each element.

For the constraint, I suggest you do not attempt to model it directly in the policy function, but instead define a fixed (no learnable parameters) mapping function from something that is easier to model in the neural network, to the constrained version. For instance, whatever action vector is output by sampling the neural network action, you could clip to minimum zero, then sum elements, divide by this sum and multiply by 15. Putting this function outside of the agent for training purposes - either part of the environment, or a "helper" - should make the maths and using the framework easier.

Optimising the raw, unconstrained policy function does mean you will have multiple equivalent policies once transformed, so makes it a less efficient search. However, this is offset by not needing to figure out valid probability distributions to sample from within the constrained space, or the gradients associated with the constraints.

Success of this approach will depend on a few details:

• Choice of distribution function for selecting actions

• Choice of mapping function to apply constraints

• Feasibility of exploring the state and action space sufficiently to find near optimal behaviour

You have some influence over the first two issues - if you have some sense of what "good" actions will be in the problem then you can try to ensure that the representation covers them well. For example if you expect that the vector should have multiple zeroes, then you could ensure the sampled values can go below zero easily and that you use a clipping function so that you are likely to get a few zeroes.

The last issue is beyond your control. It is possible the problem is too hard to explore using RL. This may be the case when only very specific action values out of the many possible will give you good results. RL relies on getting some kind of reward signal to guide improvements. If there is a very large search space and only sparse rewards in specific circumstances, then the trial and error process may never find the optimal behaviours.