# Large action space for deep reinforcement learning

I know that in normal Deep Reinforcement Learning(DRL) scenario, we learn a deep neural network to map current states to Q values. The number of the Q values (# of outputs of the neural network) is the same as the number of possible actions so that we can choose actions according to the associated Q values.

However, in this paper "Deep Reinforcement Learning with a Combinatorial Action Space for Predicting Popular Reddit Threads", the author uses states and actions as inputs. The network only outputs a single Q value (see pictures below). The $$s_t$$ is the state at time $$t$$ and $$a_t^i$$ is the $$i^{\text{th}}$$ action at time $$t$$ (you can ignore this but each action is a combination of the vector $$c_t^1$$ to $$c_t^3$$ ). $$Q_t$$ is just the $$Q$$ at time $$t$$ for action $$i$$. I am wondering why only a single Q value is learned? If this is the case, how do we determine the action for the next step?

I am wondering why only a single Q value is learned?

It is not a factor here, but it matches the Q-learning theory as written better to model $$\hat{q}(s,a,\theta) \approx Q(s,a)$$.

It is not numerically superior, and often less efficient than modelling a single network with multiple action outputs. However, it is clearly valid to approximate the action value function directly.

If the policy is separate to Q values, and you are using Q-learning to predict the values of that policy (as opposed to using Q-learning to control and find an optimal policy) then a single action value can be more efficient.

If this is the case, how do we determine the action for the next step?

If you want to drive a best guess at an optimal policy from action values $$Q(s,a)$$, then typically you calculate

$$\pi(s) = \text{argmax}_a Q(s,a)$$

This rule is not dependent on a neural network architecture, but the implementation does vary:

• If your neural network outputs all action values at once from the state, $$f_{nn}(s) \rightarrow [\hat{q}(s,a_0), \hat{q}(s,a_1), \hat{q}(s,a_2)...]$$ then you perform a single forward pass of the network and find the maximising action inside a single output vector.

• If your neural network outputs a single action value from a state, action $$f_{nn}(s,a) \rightarrow \hat{q}(s,a)$$ then you must run it for each possible action (typically in a minibatch) and find the maximising action across all outputs.

Unless you have some other way to generate the policies (e.g. you are using a policy network and policy gradients, the Q value is then for a baseline in something like an Actor-Critic agent), then you must collect all action values from each state in order to find the maximising action. There is no easy way around this, and the paper you link does not have a clever solution to it.

It seems that people think that make action as input is an effective way to ease the large action space problem. [From comments]

It can be, but not in the way you suppose.

Instead, the nature of the action representation is critical. In your question, you said "you can ignore this but each action is a combination of the vector $$c_t^1$$ to $$c_t^3$$" (emphasis mine). However, this is not an ignorable detail, and is an important part of the paper.

By compressing the action representation into a small number of scalar traits, the authors allow the neural network to generalise between similar actions. For example if one action is represented by $$c_t^1 = 0.5, c_t^2 = -0.3, c_t^3 = 0.25$$ and another action is represented by $$c_t^1 = 0.7, c_t^2 = -0.3, c_t^3 = 0.25$$, then an accurate value for the first action may result in at least an approximately accurate value for the second action, even if it has never been taken before in the current state.

Caveat: whether or not this is true or useful depends on the specifics of the problem being solved. It will not always be true, or be useful to transform the action space in this way. Actions with similar vectors need to be similar in some way that affects the outcome.

However, assuming it is true, the network design gives you an advantage in learning rate. Things that the agent learns about action values will be generalised more efficiently than a simpler network that enumerates each possible action. That makes the agent more sample efficient, it will need less experience to reach near optimal behaviour. It is this sample efficiency that the paper you linked is referring as an improvement to original DQN.

None of this changes the need to iterate over all possible actions when you want to evaluate the policy using DQN in this case.

TL;DR: The agent in the paper still has to evaluate all actions in each state in order to choose the best one. However, it does not have to try them all in order to discover which is best in the long term.

• Hi Neil, first thank you for your comment. I have some doubts about your reply. I am not an expert in DRL so what I write below just reflect my thinking and may not be correct. – Tong Lin Apr 16 '19 at 21:18
• I am reading another paper and they also claim that make action space an input is a way to handle large action space. The paper is "Handling Large-Scale Action Space in Deep Q Network", and the cite in the paper is "As we mentioned in Subsection A, the classic DQN could not handle the game with large-scale action space. we need to modify the structure of DQN to satisfy the huge action space. Since the neural network could be treated as a regression method, a straight-forward idea is receiving both state and action information as input and simply outputting the estimation value." – Tong Lin Apr 16 '19 at 21:20
• It seems that people think that make action as input is an effective way to ease the large action space problem. Thus, I doubt that they will forward pass each action into neural network to get every Q value since large action space will make this operation very expensive while this is what they want to avoid. In addition, in the paper above, the author also estimates a scalar Q value. However, neither of the paper clearly state how they choose the next-step action. – Tong Lin Apr 16 '19 at 21:26
• Please link the paper in the question. I suspect that as well as using action representation as input that there is some other factor that allows them to make use of it, or that makes one of the calculations more efficient with action as input. If actions are somehow similar to each other that may be a factor (as then the neural network may generalise better across different actions) - meaning there is a balance point between inefficient max value calculations for action choice, versus faster/better learning per sample. – Neil Slater Apr 16 '19 at 22:23
• Hi Neil, here is the link for paper "Handling Large-Scale Action Space in Deep Q Network" : drive.google.com/file/d/1DnKEJ2bqfMvEFVfZjLzU0EIDjh0hEKLX/… – Tong Lin Apr 17 '19 at 3:13