But calling fit multiple times in a warm start setting does not yield the same results (as expected, we want more trees, and we want different trees).

Just to be sure regarding the expectation after reading the docstring: were you expecting that the two trees in the forest to be identical due to the warm starting?
Basically, it is to make sure that we should change the docstring of random_state or the one of warm_start or both.

The example above produces a forest with two unique trees, and the overall forest is identical to creating at once with RandomForestClassifier(n_estimators=2, warm_start=False, random_state=0)

This is indeed the expected behaviour.

were you expecting that the two trees in the forest to be identical due to the warm starting?

It was rather that I could not tell from the documentation and had to resort to testing it out with the code snippet. My personal intuition was for it to work as it does, but when it came up in code review I realized that I couldn't even tell from the docs that it was correct.

This is indeed the expected behaviour.

I figured, I added it for clarity.

It was rather that I could not tell from the documentation and had to resort to testing it out with the code snippet. My personal intuition was for it to work as it does, but when it came up in code review I realized that I couldn't even tell from the docs that it was correct.

OK I see. Improving the documentation would then be interesting.

I am unsure which other estimators have a similar behavior with warm_start (presumably all?). I would suggest to add a remark similar to this to the warm_start docs:

When random_state is also set, the internal random state is also preserved between fit calls. This means that two fit calls to the same object might yield two different results (e.g. different trees in a random forest). With a set random_state, training the full model at once gives the same result as building it iteratively across multiple fit calls with warm_start.

I am unsure which other estimators have a similar behavior with warm_start (presumably all?).

At least all estimators in the ensemble module would benefit from the change.

I don't really have the time right now to experimentally verify/read docs and figure out how non-ensemble estimators behave. It seems to me that each individual estimator class has the documentation independently (as opposed to documenting shared parameters on the base class from which they are derived). Should the clarification be added to the general warm_start documentation, but clarify it is only true for ensemble? But that would be confusing if non-ensemble methods behave similarly. Alternatively, should this additional clarification be copied into the docstring of each (user-facing) ensemble class? Or is it better to wait until someone comes along with more time (and otherwise until I have more time myself in a few months) to figure out the exact behavior across all submodules?

how non-ensemble estimators behave.

In linear models, it is just that the optimization will start with some initial weights instead of random weights.

Should the clarification be added to the general warm_start documentation, but clarify it is only true for ensemble? But that would be confusing if non-ensemble methods behave similarly. Alternatively, should this additional clarification be copied into the docstring of each (user-facing) ensemble class? Or is it better to wait until someone comes along with more time (and otherwise until I have more time myself in a few months) to figure out the exact behavior across all submodules?

I would start with the tree-based model in the ensemble module and I would prefer to have a description that is related to this type of model. It might be easier to understand than a rather general explanation that would fit all model with a warm_start.