Repository: automl/SMAC3

Issue:
Racing: Configs worse than existing incumbent are not rejected `bug`
<!-- Instructions For Filing a Bug: https://github.com/automl/SMAC3/blob/master/CONTRIBUTING.md -->

#### Description
<!-- Describe what you wanted to do -->
I wanted to use the tell-interface of the HPOFacade (which uses racing for intensification, the related class being `Intensifier`) to warmstart the optimizer with data from previous runs which were all collected on the same seed, no instances were used.

#### Steps/Code to Reproduce
<!--
Please provide us with code to reproduce your issue. If the code is too long, feel free to put it in a public gist and link
it in the issue: https://gist.github.com
-->
https://gist.github.com/PhilippBordne/722c336dd0981859bfade198171f9c29

#### Expected Results
All configurations worse than the incumbent should be in the `_rejected_config_ids` list after using the tell interface for warmstarting. They should still be in it after `__post_init__` of `AbstractIntensifier` was run when starting the actual optimization loop. `__post_init__` will call `update_incumbents(config)` on the runhistory again and thus also update the `_rejected_config_ids` list.

#### Actual Results
The configs worse than the incumbent are in the `_rejected_config_ids` list after using the tell interface for warmstarting if they were "told" in an order that improves the cost with every new config. But they are not in the list after running `__post_init__` (They are all removed during the `update_incumbents` cycle on existing configs in `RunHistory` at the end of `__post_init__`). This can lead the subsequent optimization run to fail because the configs which are erroneously not in the `_rejected_config_ids` list will fill up the queue and make the intensifier use up all its retries on them. 
For details see the linked code to reproduce.

#### Proposed fix
The issue is caused by the current configs being _removed_ from `_rejected_config_ids` if the incumbent doesn't change during `update_incumbents(config)`, which is also the case if newly evaluated configs are worse than the existing incumbent. This can be fixed by inserting a simple check if the config is among the incumbents after `update_incumbents`.
A PR implementing this is incoming.

#### Versions
<!--
Please run the following snippet and paste the output below.
`import smac; print(smac.__version__)`
-->
2.0.2
<!-- Thanks for contributing! -->


Discussion:
dengdifan: Thanks for the PR. Looks good to me! 

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index aa2d5ae48..5ffa77ab5 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,8 +1,9 @@
 # 2.0.3
 
 ## Bugfixes
-- Add OrdinalHyperparameter for random forest imputer (#1065).
 - Fix path for dask scheduler file (#1055).
+- Add OrdinalHyperparameter for random forest imputer (#1065).
+- Configurations that fail to become incumbents will be added to the rejected lists (#1069).
 
 # 2.0.2
 
diff --git a/smac/intensifier/abstract_intensifier.py b/smac/intensifier/abstract_intensifier.py
index b94486727..cb537e9cc 100644
--- a/smac/intensifier/abstract_intensifier.py
+++ b/smac/intensifier/abstract_intensifier.py
@@ -571,8 +571,12 @@ class AbstractIntensifier:
 
         if len(previous_incumbents) == len(new_incumbents):
             if previous_incumbents == new_incumbents:
-                # No changes in the incumbents
-                self._remove_rejected_config(config_id)
+                # No changes in the incumbents, we need this clause because we can't use set difference then
+                if config_id in new_incumbent_ids:
+                    self._remove_rejected_config(config_id)
+                else:
+                    # config worse than incumbents and thus rejected
+                    self._add_rejected_config(config_id)
                 return
             else:
                 # In this case, we have to determine which config replaced which incumbent and reject it


Test patch:
diff --git a/tests/test_intensifier/test_abstract_intensifier.py b/tests/test_intensifier/test_abstract_intensifier.py
index ce980c49b..b8dc91a1c 100644
--- a/tests/test_intensifier/test_abstract_intensifier.py
+++ b/tests/test_intensifier/test_abstract_intensifier.py
@@ -109,6 +109,48 @@ def test_incumbent_selection_multi_objective(make_scenario, configspace_small, m
     assert intensifier.get_incumbents() == [config]
 
 
+def test_config_rejection_single_objective(configspace_small, make_scenario):
+    """ Tests whether configs are rejected properly if they are worse than the incumbent. """
+    scenario = make_scenario(configspace_small, use_instances=False)
+    runhistory = RunHistory()
+    intensifier = Intensifier(scenario=scenario)
+    intensifier.runhistory = runhistory
+
+    configs = configspace_small.sample_configuration(3)
+
+    runhistory.add(config=configs[0],
+                   cost=5,
+                   time=0.0,
+                   seed=0,
+                   status=StatusType.SUCCESS,
+                   force_update=True)
+    intensifier.update_incumbents(configs[0])
+
+    assert intensifier._rejected_config_ids == []
+
+    # add config that yielded better results, updating incumbent and sending prior incumbent to rejected
+    runhistory.add(config=configs[1],
+                   cost=1,
+                   time=0.0,
+                   seed=0,
+                   status=StatusType.SUCCESS,
+                   force_update=True)
+    intensifier.update_incumbents(config=configs[1])
+    
+    assert intensifier._rejected_config_ids == [1]
+
+    # add config that is no better should thus go to rejected
+    runhistory.add(config=configs[2],
+                   cost=1,
+                   time=0.0,
+                   seed=0,
+                   status=StatusType.SUCCESS,
+                   force_update=True)
+    intensifier.update_incumbents(config=configs[2])
+    
+    assert intensifier._rejected_config_ids == [1, 3]
+
+
 def test_incumbent_differences(make_scenario, configspace_small):
     pass