Cloned estimators have identical randomness but different RNG instances

### Describe the bug

Cloned estimators have identical randomness but different RNG instances. According to documentation, it should be the other way around: different randomness but identical RNG instances.

Related #25395 

The User Guide [says](https://scikit-learn.org/stable/common_pitfalls.html#controlling-randomness):
> For an optimal robustness of cross-validation (CV) results, pass RandomState instances when creating estimators

> ```python
> rf_inst = RandomForestClassifier(random_state=np.random.RandomState(0))
> cross_val_score(rf_inst, X, y)
> ```
> ...
> Since `rf_inst` was passed a `RandomState` instance, each call to `fit` starts from a different RNG. As a result, the random subset of features will be different for each folds

In regards to cloning, the same reference says:
> ```python
> rng = np.random.RandomState(0)
> a = RandomForestClassifier(random_state=rng)
> b = clone(a)
> ```
> Moreover, `a` and `b` will influence each-other since they share the same internal RNG: calling `a.fit` will consume `b`’s RNG, and calling `b.fit` will consume `a`’s RNG, since they are the same. 

The actual behaviour does not follow this description. 

### Steps/Code to Reproduce

```python
import numpy as np
from sklearn import clone
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_validate
from sklearn.ensemble import RandomForestClassifier

rng = np.random.RandomState(0)
X, y = make_classification(random_state=rng)
rf = RandomForestClassifier(random_state=rng)

d = cross_validate(rf, X, y, return_estimator=True, cv=2)
rngs = [e.random_state for e in d['estimator']]
# estimators corresponding to different CV runs have different but identical RNGs:
print(rngs[0] is rngs[1]) # False
print(all(rngs[0].randint(10, size=10) == rngs[1].randint(10, size=10))) # True

rf_clone = clone(rf)
rngs = [rf.random_state, rf_clone.random_state]
print(rngs[0] is rngs[1]) # False
print(all(rngs[0].randint(10, size=10) == rngs[1].randint(10, size=10))) # True
```

### Expected Results

True False True False

### Actual Results

False True False True

### Versions

```shell
Tested on a two-week-old dev build and also on the following version (Kaggle)

System:
    python: 3.7.12 | packaged by conda-forge | (default, Oct 26 2021, 06:08:53)  [GCC 9.4.0]
executable: /opt/conda/bin/python3.7
   machine: Linux-5.15.90+-x86_64-with-debian-bullseye-sid

Python dependencies:
          pip: 22.3.1
   setuptools: 59.8.0
      sklearn: 1.0.2
        numpy: 1.21.6
        scipy: 1.7.3
       Cython: 0.29.34
       pandas: 1.3.5
   matplotlib: 3.5.3
       joblib: 1.2.0
threadpoolctl: 3.1.0

Built with OpenMP: True
```

COMMENT:
As far as I could see, when an estimator is cloned, `random_state` attribute gets deepcopied. In [base.py:clone](https://github.com/scikit-learn/scikit-learn/blob/7922d4eae62e577347d1b6041488754b7fb532bb/sklearn/base.py#L74-L122), on Line 102 `clone()` is recursively called on `random_state` with `safe=False`, which causes `random_state` to be deepcopied on Line 83. As a result, an RNG instance is copied when an estimator is cloned.

There are several components to the issue.
1. When doing cross-validation, we want estimators to have different randomness. We want this to ensure that CV is not affected too badly by lucky or unlucky initialisations of a stochastic estimator.
2. When cloning an estimator, we want the documentation and the actual behaviour match.
3. We want reproducibility.

As for (2), the documentation says that clones should refer to one and the same RNG instance. However, if we implement this, don't we risk opening the Pandora Box of concurrency and race condition issues, and thereby killing any hope of reproducibility? I think, it is the documentation should be changed for (2), not the code.

As for (1), cross-validation routines seem to follow the "parallel-delayed-clone" pattern:
https://github.com/scikit-learn/scikit-learn/blob/9aaed498795f68e5956ea762fef9c440ca9eb239/sklearn/model_selection/_validation.py#L266-L268
Thus, one solution for (1) would be to ensure that cloned estimators have different randomness. This randomness should be controllable.

@betatim [mentioned](https://github.com/scikit-learn/scikit-learn/issues/25395#issuecomment-1503000643) what appears to be a nice solution. I quote him:
> Something related is https://numpy.org/devdocs/reference/random/parallel.html#seedsequence-spawning (in particular the end of the linked to section) which talks about how to spawn new generators from an existing one. It also links to more material about why `seed + fold_idx` to generate "reproducible seeds" and such schemes are error prone

I did not have a chance to look deeper into all this, but the solution could be a special treatment of `random_state` parameter in `base.clone`. If I am not mistaken, Python guarantees that list comprehension will be executed sequentially in "parallel-delayed-clone", and something like this should work:
```python
    for name, param in new_object_params.items():
        if name=="random_state" and type(param) is RandomState:
            new_object_params[name] = param.spawn()
        else:
            new_object_params[name] = clone(param, safe=False)
```

P.S. To sum up, the proposed solution is to ensure different randomness and different RNG instances.

Labels: Bug, Documentation, Needs Decision