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?
-
1$\begingroup$ Is there any constraint on the vector size for the combined actions? Would it be meaningful to have the agent pick one action at a time? $\endgroup$– Neil SlaterAug 7, 2021 at 7:20
-
$\begingroup$ The agent needs to take a vector of actions each time. The sum over the elements must be a specific constant. $\endgroup$– StarAug 8, 2021 at 16:10
-
$\begingroup$ Is there a maximum size to the vector? As written, the agent could pick a vector of size 1,000,000 with most elements zero, and it is not clear whether this would be meaningful or useful for your use case. Even with a vector size limit of 10 you would have a huge action space to search, so it would be nice to know what the limits are. $\endgroup$– Neil SlaterAug 8, 2021 at 16:58
-
$\begingroup$ Real numbers? Your action space is huge! I hope that you are expecting similar state/action vectors to have similar utility in general? It's workable to have a few exceptions where value changes rapidly between similar inputs, but if results are more arbitrary then your agent will never be able to find a good policy. $\endgroup$– Neil SlaterAug 10, 2021 at 16:16
-
$\begingroup$ Sorry for the typo. I meant the elements are integer numbers. Please assume that the action vector is of size 10 and each element can pick an integer number in range(0,15). $\endgroup$– StarAug 11, 2021 at 3:09
1 Answer
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.
-
$\begingroup$ It's great! Thanks a lot, Neil. I have also read about action branching in DQN. I think both solutions would be helpful. $\endgroup$– StarAug 12, 2021 at 18:29
-
$\begingroup$ I wonder if dividing the time step by the number of possible actions could be a good idea. It seems to be realistic. In real world usually the sequence of the selected actions is also relevant. $\endgroup$ Sep 13, 2021 at 15:55
-
1$\begingroup$ @HermesMorales That can work for some optimisation tasks, such as those where this action sequence is meaningful - even better if there is some immediate reward signal. So e.g. for a knapsack type problem. If, as the OP states, there is no meaning to partial actions, and reward has to be calculated after the combined action, then there might still be a representation benefit that results in simpler faster code, but it could even be counter-productive to exploration. $\endgroup$ Sep 13, 2021 at 16:02