Is random state a parameter to tune? An issue that happens quite often in my experiments is the model varies in performance when random state for the algorithm is changed. So the question is simple, should I take random state as a hyperparameter?  Why is that? If my model outperforms others with different random state, should I consider the model as over fit a particular random state?
a log of decision tree in sklearn: (random_rate should be random state)

 A: No, you should not.
Hyperparameters are variables which control some high-level aspect of an algorithm's behavior. As opposed to regular parameters, hyperparameters cannot be automatically learned from training data by the algorithm itself. For this reason, an experienced user will select an appropriate value based on his intuition, domain knowledge and the semantic meaning of the hyperparameter (if any). Alternatively, one might use a validation set to perform hyperparameter selection. Here, we try to find an optimal hyperparameter value for the entire population of data by testing different candidate values on a sample of the population (the validation set).
Regarding the random state, it is used in many randomized algorithms in sklearn to determine the random seed passed to the pseudo-random number generator. Therefore, it does not govern any aspect of the algorithm's behavior. As a consequence, random state values which performed well in the validation set do not correspond to those which would perform well in a new, unseen test set. Indeed, depending on the algorithm, you might see completely different results by just changing the ordering of training samples.
I suggest you select a random state value at random and use it for all your experiments. Alternatively you could take the average accuracy of your models over a random set of random states.
In any case, do not try to optimize random states, this will most certainly produce optimistically biased performance measures.
A: What does the random_state effect? training and validation set splitting, or what? 
If it's the first case, I think you can try to find differences between the splitting scheme under two random states, and this might give you some intuition in your model(I mean, you can explore why it works to train model on some data, and use the trained model to predict some validation data, but doesn't work to train model on some other data, and predict some other validation data. Are they distributed differently?) Such Analysis may give you some intuition.
And by the way, I encountered this problem too:), and just don't understand it. Maybe we can work together on investigating it.
Cheers.
