In order to have reproducible results, we should instead use a random_state (added and initialized in the constructor), and then call shuffle on it.

Yes but in the following way:

from random import Random
from sklearn.utils import check_random_state
...

    # in __init__
    self.random_state = random_state

...

    # then in fit
    self.random_state = check_random_state(self.random_state)

    if self.budget:
        py_random_state = Random(self.random_random.rand())
        self.rolled_out_grid = list(IterGrid(param_grid))
        py_random_state.shuffle(self.rolled_out_grid)

What is the purpose of py_random_state? Not to change the estimator during fit? I would do
random_state = check_random_state(self.random_state) and then use random_state later. Or doesn't check_random_state make a copy? Maybe it should.

because AFAIK the numpy rng cannot shuffle inplace a python list.

Ok, that was the subtlety I knew I overlooked, thanks :)