Does higher maximum Q value imply better or worse performance? Suppose I run a RL algorithm and for every episode, I grab the (average) maximum Q value. I do this for several runs (with different hyper-paramters, for instance) to compare performance of my RL algorithm. 
The curves look something like this. 

What can I say about the performance of these runs? Is larger the maximum Q value the better?
I have found some paper online (second to last page) that says:
"Since maximum Q value explodes....therefore the performance is worse..."
Can someone explain why this should be the case? By definition, Q value is the maximum expectation reward at state s, taking action a, following policy $\pi$. Why would a higher expected reward translate into worse performance? 
 A: When you say "maximum Q value", do you mean simply the Q value as estimated by the algorithm itself? If you use this as an evaluation metric, it does not really necessarily say anything. 
In practice, I suppose there will be some correlation with performance, because most RL algorithms do actually try to have meaningful, accurate Q-value estimates. 
However, suppose I propose a new RL algorithm that works simply by assigning a Q-value of infinity to every state-action pair, and then acts randomly. This is probably not a very good RL algorithm, but it would have an infinite score according to your metric. This is obviously a rather unrealistic example, but there are RL algorithms (such as regular Q-learning instead of Double Q-learning) that are known to be susceptible to overestimating Q-values, and as a result often perform worse than algorithms that address this.
If you want to accurately evaluate the performance of algorithms, you're better off using the actual Reward signals obtained, not any value that is internal to the algorithm.
