How to calculate average action-value Q for Deep Q learning I have used Deep Q learning to train an agent for a specific game.  In DeepMind's paper on Deep Q-Learning for Atari video games (here), they have plotted average action-value Q. My question is that how can we do that? What parameters are we taking average over? All states and all actions?
In this paper, it is said that the average is computed over the held-out set of states. What does it mean? 
 A: The plots Fig 2c and 2d in the paper mainly demonstrate the stability of the algorithm, and do not have much else in the way of useful interpretations (such as measuring performance of the agent). This is confirmed by the published Supplementary Information

In this paper, it is said that the average is computed over the held-out set of states. What does it mean?

How the states were originally chosen for the assessment does not appear to be explained - I cannot find any reference to how they were collected. If the terminology is used correctly, I would suspect that here "held-out" refers to a set of states collected from emulations separate to the training. This could be almost anything - from random play, from humans playing the game, from other training runs. The resulting data set is some unspecified number of sets of 4 frames (perhaps already pre-processed) that are fed into the network.
The point of using unseen data is similar to supervised learning, to demonstrate generalisation - up to a point. Unfortunately, there is no easy way to get a "true" average Q value to compare this to.

My question is that how can we do that? What parameters are we taking average over? All states and all actions?

In this case, a pre-selected set of states, and all possible actions that could be taken in those states. These can then just be fed into the network to get a batch of Q value predictions, that are averaged. So it is relatively cheap to calculate.
This is not a very meaningful metric. It is self-referential (i.e. how the agent rates itself, not confirmed by any measure of its performance), the set of states is not necessarily related to optimal trajectories, and by taking an average of all possible actions in each state, it does not relate to choices the agent makes in practice. However, by covering these cases, it is reasonable to use in a learning curve as a demonstration of stability; for instance if otherwise unreachable state/action pairs (in a practical sense of never being seen or played by the agent) were to start changing estimated value due to over-fitting, then this metric might show the problem with deviations from the learning curve.
There are possibly more meaningful learning curves that could be plotted. For instance, instead of using self-referential Q values from the network, the game could be set in those states, played using the agent, and actual sampled returns (discounted sum of rewards) collected from each starting state. That would be independent confirmation of whether the Q values were accurate. However, that would also be very time-consuming to collect - instead the plots 2a and 2b show actual rewards collected by the agent whilst playing (and still with a non-zero $\epsilon$ for some reason).
