Repository: automl/SMAC3

Issue:
Fix/Extend BOHB
* BOHB facade should inherit from the existing SMAC4HPO facade
* unit tests for the new functions in rh2epm and runhistory to test the selection with budgets (https://github.com/automl/SMAC3/pull/569)
* Change the SH and HB examples to use the new facade.


Discussion:
codecov-io: # [Codecov](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=h1) Report
> Merging [#610](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=desc) into [development](https://codecov.io/gh/automl/SMAC3/commit/92cabfeb089f9c9bda784eb1027cd1567bc5cc5d?src=pr&el=desc) will **decrease** coverage by `0.07%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/automl/SMAC3/pull/610/graphs/tree.svg?width=650&token=0Z9cm7CRSY&height=150&src=pr)](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=tree)

```diff
@@               Coverage Diff               @@
##           development     #610      +/-   ##
===============================================
- Coverage        86.04%   85.97%   -0.08%     
===============================================
  Files               61       61              
  Lines             5545     5517      -28     
===============================================
- Hits              4771     4743      -28     
  Misses             774      774
```


| [Impacted Files](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [smac/intensification/successive\_halving.py](https://codecov.io/gh/automl/SMAC3/pull/610/diff?src=pr&el=tree#diff-c21hYy9pbnRlbnNpZmljYXRpb24vc3VjY2Vzc2l2ZV9oYWx2aW5nLnB5) | `89.4% <ø> (ø)` | :arrow_up: |
| [smac/facade/smac\_bohb\_facade.py](https://codecov.io/gh/automl/SMAC3/pull/610/diff?src=pr&el=tree#diff-c21hYy9mYWNhZGUvc21hY19ib2hiX2ZhY2FkZS5weQ==) | `100% <100%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=footer). Last update [92cabfe...dfedf0a](https://codecov.io/gh/automl/SMAC3/pull/610?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/ci_scripts/run_examples.sh b/ci_scripts/run_examples.sh
index aff344e63..5a5aba087 100755
--- a/ci_scripts/run_examples.sh
+++ b/ci_scripts/run_examples.sh
@@ -17,6 +17,13 @@ if [ "$rval" != 0 ]; then
     echo "Error running example QCP"
     exit $rval
 fi
+python SMAC4AC_spear_qcp.py
+rval=$?
+if [ "$rval" != 0 ]; then
+    echo "Error running python example QCP"
+    exit $rval
+fi
+
 cd ..
 
 cd branin
diff --git a/examples/SMAC4HPO_mlp_hyperband.py b/examples/BOHB4HPO_mlp.py
similarity index 93%
rename from examples/SMAC4HPO_mlp_hyperband.py
rename to examples/BOHB4HPO_mlp.py
index 7646ed5a0..0916670d7 100644
--- a/examples/SMAC4HPO_mlp_hyperband.py
+++ b/examples/BOHB4HPO_mlp.py
@@ -23,8 +23,7 @@ from sklearn.model_selection import cross_val_score, StratifiedKFold
 from sklearn.neural_network import MLPClassifier
 
 from smac.configspace import ConfigurationSpace
-from smac.facade.smac_hpo_facade import SMAC4HPO
-from smac.intensification.hyperband import Hyperband
+from smac.facade.smac_bohb_facade import BOHB4HPO
 from smac.scenario.scenario import Scenario
 
 digits = load_digits()
@@ -74,7 +73,7 @@ def mlp_from_cfg(cfg, seed, instance, budget, **kwargs):
             random_state=seed)
 
         # returns the cross validation accuracy
-        cv = StratifiedKFold(n_splits=5, random_state=seed)  # to make CV splits consistent
+        cv = StratifiedKFold(n_splits=5, random_state=seed, shuffle=True)  # to make CV splits consistent
         score = cross_val_score(mlp, digits.data, digits.target, cv=cv, error_score='raise')
 
     return 1 - np.mean(score)  # Because minimize!
@@ -127,10 +126,8 @@ max_iters = 50
 # intensifier parameters
 intensifier_kwargs = {'initial_budget': 5, 'max_budget': max_iters, 'eta': 3}
 # To optimize, we pass the function to the SMAC-object
-smac = SMAC4HPO(scenario=scenario, rng=np.random.RandomState(42),
+smac = BOHB4HPO(scenario=scenario, rng=np.random.RandomState(42),
                 tae_runner=mlp_from_cfg,
-                intensifier=Hyperband,  # you can also change the intensifier to use like this!
-                # This example currently uses Hyperband intensification,
                 intensifier_kwargs=intensifier_kwargs)  # all arguments related to intensifier can be passed like this
 
 # Example call of the function with default values
diff --git a/examples/SMAC4HPO_sgd_hyperband_instances.py b/examples/BOHB4HPO_sgd_instances.py
similarity index 90%
rename from examples/SMAC4HPO_sgd_hyperband_instances.py
rename to examples/BOHB4HPO_sgd_instances.py
index be558a562..56e1010d2 100644
--- a/examples/SMAC4HPO_sgd_hyperband_instances.py
+++ b/examples/BOHB4HPO_sgd_instances.py
@@ -26,8 +26,7 @@ from sklearn.model_selection import cross_val_score, StratifiedKFold
 
 # Import ConfigSpace and different types of parameters
 from smac.configspace import ConfigurationSpace
-from smac.facade.smac_hpo_facade import SMAC4HPO
-from smac.intensification.hyperband import Hyperband
+from smac.facade.smac_bohb_facade import BOHB4HPO
 # Import SMAC-utilities
 from smac.scenario.scenario import Scenario
 
@@ -81,7 +80,7 @@ def sgd_from_cfg(cfg, seed, instance):
         # get instance
         data, target = generate_instances(int(instance[0]), int(instance[1]))
 
-        cv = StratifiedKFold(n_splits=4, random_state=seed)  # to make CV splits consistent
+        cv = StratifiedKFold(n_splits=4, random_state=seed, shuffle=True)  # to make CV splits consistent
         scores = cross_val_score(clf, data, target, cv=cv)
     return 1 - np.mean(scores)  # Minimize!
 
@@ -117,16 +116,13 @@ scenario = Scenario({"run_obj": "quality",  # we optimize quality (alternative t
 intensifier_kwargs = {'initial_budget': 1, 'max_budget': 45, 'eta': 3,
                       'instance_order': None,  # You can also shuffle the order of using instances by this parameter.
                       # 'shuffle' will shuffle instances before each SH run and
-                      # 'shuffle_once' will shuffle instances once before the 1st
-                      # SH iteration begins
+                      # 'shuffle_once' will shuffle instances once before the 1st SH iteration begins
                       }
 
 # To optimize, we pass the function to the SMAC-object
-smac = SMAC4HPO(scenario=scenario, rng=np.random.RandomState(42),
+smac = BOHB4HPO(scenario=scenario, rng=np.random.RandomState(42),
                 tae_runner=sgd_from_cfg,
-                intensifier=Hyperband,  # you can also change the intensifier to use like this!
-                # This example currently uses Hyperband intensification,
-                intensifier_kwargs=intensifier_kwargs)  # all parameters related to intensifier can be passed like this
+                intensifier_kwargs=intensifier_kwargs)  # all arguments related to intensifier can be passed like this
 
 # Example call of the function
 # It returns: Status, Cost, Runtime, Additional Infos
diff --git a/examples/spear_qcp/SMAC4AC_spear_qcp.py b/examples/spear_qcp/SMAC4AC_spear_qcp.py
index cf04082fc..fc4df0d6e 100644
--- a/examples/spear_qcp/SMAC4AC_spear_qcp.py
+++ b/examples/spear_qcp/SMAC4AC_spear_qcp.py
@@ -23,6 +23,7 @@ if __name__ == '__main__':
                           # non-deterministic target algorithm
                           'initial_budget': 1,
                           'eta': 3,
+                          'min_chall': 1  # because successive halving cannot handle min_chall > 1
                           }
 
     smac = SMAC4AC(scenario=scenario,  # scenario object
diff --git a/smac/epm/rfr_imputator.py b/smac/epm/rfr_imputator.py
index a413ad875..d339ce1fe 100644
--- a/smac/epm/rfr_imputator.py
+++ b/smac/epm/rfr_imputator.py
@@ -64,7 +64,7 @@ class RFRImputator(smac.epm.base_imputor.BaseImputor):
         self.change_threshold = change_threshold
         self.cutoff = cutoff
         self.threshold = threshold
-        self.seed = rng.random_integers(low=0, high=1000)
+        self.seed = rng.randint(low=0, high=1000)
 
         self.model = model
 
diff --git a/smac/facade/smac_ac_facade.py b/smac/facade/smac_ac_facade.py
index d34857ef7..ac85b7878 100644
--- a/smac/facade/smac_ac_facade.py
+++ b/smac/facade/smac_ac_facade.py
@@ -414,7 +414,7 @@ class SMAC4AC(object):
             intensifier_instance = intensifier(**intensifier_def_kwargs)  # type: ignore[arg-type] # noqa F821
         else:
             raise TypeError(
-                "Argument intensifier must be None or an object implementing the Intensifier, but is '%s'" %
+                "Argument intensifier must be None or an object implementing the AbstractRacer, but is '%s'" %
                 type(intensifier)
             )
 
diff --git a/smac/facade/smac_bohb_facade.py b/smac/facade/smac_bohb_facade.py
index 0c80c8271..69ad03ac7 100644
--- a/smac/facade/smac_bohb_facade.py
+++ b/smac/facade/smac_bohb_facade.py
@@ -1,9 +1,7 @@
 import typing
 
-from smac.facade.smac_ac_facade import SMAC4AC
+from smac.facade.smac_hpo_facade import SMAC4HPO
 from smac.runhistory.runhistory2epm import RunHistory2EPM4LogScaledCost
-from smac.optimizer.acquisition import LogEI
-from smac.epm.rf_with_instances import RandomForestWithInstances
 from smac.initial_design.random_configuration_design import RandomConfigurations
 from smac.intensification.hyperband import Hyperband
 
@@ -12,7 +10,7 @@ __copyright__ = "Copyright 2018, ML4AAD"
 __license__ = "3-clause BSD"
 
 
-class BOHB4HPO(SMAC4AC):
+class BOHB4HPO(SMAC4HPO):
     """
     Facade to use BOHB i.e., SMAC with a Hyperband intensifier for hyperparameter optimization
 
@@ -42,49 +40,18 @@ class BOHB4HPO(SMAC4AC):
         kwargs['initial_design'] = kwargs.get('initial_design', RandomConfigurations)
         kwargs['runhistory2epm'] = kwargs.get('runhistory2epm', RunHistory2EPM4LogScaledCost)
 
-        init_kwargs = kwargs.get('initial_design_kwargs', dict())
-        init_kwargs['n_configs_x_params'] = init_kwargs.get('n_configs_x_params', 10)
-        init_kwargs['max_config_fracs'] = init_kwargs.get('max_config_fracs', 0.25)
-        kwargs['initial_design_kwargs'] = init_kwargs
-
         # Intensification parameters
         # select Hyperband as the intensifier ensure respective parameters are provided
         kwargs['intensifier'] = Hyperband
+
+        # set Hyperband parameters if not given
         intensifier_kwargs = kwargs.get('intensifier_kwargs', dict())
-        intensifier_kwargs['min_chall'] = 1
+        if intensifier_kwargs.get('eta') is None:
+            intensifier_kwargs['eta'] = 3
+        if intensifier_kwargs.get('instance_order') is None:
+            intensifier_kwargs['instance_order'] = 'shuffle_once'
         kwargs['intensifier_kwargs'] = intensifier_kwargs
-        scenario.intensification_percentage = 1e-10
-
-        model_class = RandomForestWithInstances
-        kwargs['model'] = model_class
-
-        # == static RF settings
-        model_kwargs = kwargs.get('model_kwargs', dict())
-        model_kwargs['num_trees'] = model_kwargs.get('num_trees', 10)
-        model_kwargs['do_bootstrapping'] = model_kwargs.get('do_bootstrapping', True)
-        model_kwargs['ratio_features'] = model_kwargs.get('ratio_features', 1.0)
-        model_kwargs['min_samples_split'] = model_kwargs.get('min_samples_split', 2)
-        model_kwargs['min_samples_leaf'] = model_kwargs.get('min_samples_leaf', 1)
-        model_kwargs['log_y'] = model_kwargs.get('log_y', True)
-        kwargs['model_kwargs'] = model_kwargs
-
-        # == Acquisition function
-        kwargs['acquisition_function'] = kwargs.get('acquisition_function', LogEI)
-
-        kwargs['runhistory2epm'] = kwargs.get('runhistory2epm', RunHistory2EPM4LogScaledCost)
-
-        # assumes random chooser for random configs
-        random_config_chooser_kwargs = kwargs.get('random_configuration_chooser_kwargs', dict())
-        random_config_chooser_kwargs['prob'] = random_config_chooser_kwargs.get('prob', 0.2)
-        kwargs['random_configuration_chooser_kwargs'] = random_config_chooser_kwargs
-
-        # better improve acquisition function optimization
-        # 1. increase number of sls iterations
-        acquisition_function_optimizer_kwargs = kwargs.get('acquisition_function_optimizer_kwargs', dict())
-        acquisition_function_optimizer_kwargs['n_sls_iterations'] = 10
-        kwargs['acquisition_function_optimizer_kwargs'] = acquisition_function_optimizer_kwargs
 
-        print(scenario.__dict__.get('always_race_against'))
         super().__init__(**kwargs)
         self.logger.info(self.__class__)
 
diff --git a/smac/intensification/abstract_racer.py b/smac/intensification/abstract_racer.py
index adbe5566d..66ed7ef10 100644
--- a/smac/intensification/abstract_racer.py
+++ b/smac/intensification/abstract_racer.py
@@ -340,6 +340,12 @@ class AbstractRacer(object):
                 self.logger.debug("Incumbent (%.4f) is at least as good as the "
                                   "challenger (%.4f) on %d runs." %
                                   (inc_perf, chal_perf, len(chall_runs)))
+                if log_traj and self.stats.inc_changed == 0:
+                    # adding incumbent entry
+                    self.stats.inc_changed += 1  # first incumbent
+                    self.traj_logger.add_entry(train_perf=inc_perf,
+                                               incumbent_id=self.stats.inc_changed,
+                                               incumbent=incumbent)
                 return incumbent
 
             # Challenger is better than incumbent
diff --git a/smac/intensification/intensification.py b/smac/intensification/intensification.py
index 740ad8147..0930a2eba 100644
--- a/smac/intensification/intensification.py
+++ b/smac/intensification/intensification.py
@@ -24,7 +24,7 @@ class IntensifierStage(Enum):
     """Class to define different stages of intensifier"""
     RUN_INCUMBENT = 1  # Lines 3-7
     RUN_CHALLENGER = 2  # Lines 8-17
-    RUN_DEFAULT = 3
+    RUN_BASIS = 3
 
 
 class Intensifier(AbstractRacer):
@@ -197,26 +197,14 @@ class Intensifier(AbstractRacer):
             # we run incumbent once and then challenger in the next
             if self.stage == IntensifierStage.RUN_INCUMBENT:
                 # Lines 3-7
-                self._add_inc_run(incumbent=incumbent, run_history=run_history)
-            elif self.stage == IntensifierStage.RUN_CHALLENGER:
+                self._add_inc_run(incumbent=incumbent, run_history=run_history, log_traj=log_traj)
+            elif self.stage == IntensifierStage.RUN_CHALLENGER or \
+                    self.stage == IntensifierStage.RUN_BASIS:
                 # Lines 8-17
                 incumbent = self._race_challenger(challenger=challenger,
                                                   incumbent=incumbent,
                                                   run_history=run_history,
                                                   log_traj=log_traj)
-            else:
-                if self.always_race_against and \
-                        challenger == incumbent and \
-                        self.always_race_against != challenger:
-                    self.logger.debug("Race against constant configuration after incumbent change.")
-                    incumbent = self._race_challenger(challenger=self.always_race_against,
-                                                      incumbent=incumbent,
-                                                      run_history=run_history,
-                                                      log_traj=log_traj)
-                else:
-                    # move on to next iteration
-                    self.stage = IntensifierStage.RUN_INCUMBENT
-                    self.continue_challenger = False
 
         except BudgetExhaustedException:
             # We return incumbent, SMBO stops due to its own budget checks
@@ -249,7 +237,8 @@ class Intensifier(AbstractRacer):
 
     def _add_inc_run(self,
                      incumbent: Configuration,
-                     run_history: RunHistory) -> None:
+                     run_history: RunHistory,
+                     log_traj: bool = True) -> None:
         """Add new run for incumbent
 
         *Side effect:* adds runs to <run_history>
@@ -260,6 +249,9 @@ class Intensifier(AbstractRacer):
             best configuration so far
         run_history : smac.runhistory.runhistory.RunHistory
             stores all runs we ran so far
+        log_traj: bool
+            Whether to log changes of incumbents in trajectory
+
         """
         inc_runs = run_history.get_runs_for_config(incumbent, only_max_observed_budget=True)
 
@@ -325,6 +317,11 @@ class Intensifier(AbstractRacer):
             # maximum runs for incumbent reached, do not run incumbent
             self.stage = IntensifierStage.RUN_CHALLENGER
 
+        self._compare_configs(
+            incumbent=incumbent, challenger=incumbent,
+            run_history=run_history,
+            log_traj=log_traj)
+
     def _race_challenger(self,
                          challenger: Configuration,
                          incumbent: Configuration,
@@ -410,15 +407,23 @@ class Intensifier(AbstractRacer):
                 incumbent=incumbent, challenger=challenger,
                 run_history=run_history,
                 log_traj=log_traj)
+
+            # update intensification stage
             if new_incumbent == incumbent:
                 # move on to the next iteration
                 self.stage = IntensifierStage.RUN_INCUMBENT
                 self.continue_challenger = False
 
             elif new_incumbent == challenger:
+                # New incumbent found
                 incumbent = challenger
-                # New incumbent found. Go to the next stage
-                self.stage = IntensifierStage.RUN_DEFAULT
+                # compare against basis configuration if provided, else go to next iteration
+                if self.always_race_against and \
+                        self.always_race_against != challenger:
+                    self.stage = IntensifierStage.RUN_BASIS
+                else:
+                    self.stage = IntensifierStage.RUN_INCUMBENT
+                    self.continue_challenger = False
 
             else:  # Line 17
                 # challenger is not worse, continue
@@ -512,6 +517,11 @@ class Intensifier(AbstractRacer):
         # sampling from next challenger marks the beginning of a new iteration
         self.iteration_done = False
 
+        # if in RUN_BASIS stage, return the basis configuration (i.e., `always_race_against`)
+        if self.stage == IntensifierStage.RUN_BASIS:
+            self.logger.debug("Race against basis configuration after incumbent change.")
+            return self.always_race_against, False
+
         # if the current challenger could not be rejected, it is run again on more instances
         if self.current_challenger and self.continue_challenger:
             return self.current_challenger, False
diff --git a/smac/intensification/successive_halving.py b/smac/intensification/successive_halving.py
index 0a3c2449e..0cab8b0f1 100644
--- a/smac/intensification/successive_halving.py
+++ b/smac/intensification/successive_halving.py
@@ -9,7 +9,7 @@ from smac.stats.stats import Stats
 from smac.utils.constants import MAXINT
 from smac.configspace import Configuration
 from smac.runhistory.runhistory import RunHistory
-from smac.tae.execute_ta_run import BudgetExhaustedException, CappedRunException, ExecuteTARun
+from smac.tae.execute_ta_run import BudgetExhaustedException, CappedRunException, ExecuteTARun, StatusType
 from smac.utils.io.traj_logging import TrajLogger
 
 
@@ -45,8 +45,8 @@ class SuccessiveHalving(AbstractRacer):
 
     Examples for successive halving (and hyperband) can be found here:
     * Runtime objective and multiple instances *(instances as budget)*: `examples/spear_qcp/SMAC4AC_spear_qcp.py`
-    * Quality objective and multiple instances *(instances as budget)*: `examples/SMAC4HPO_sgd_hyperband_instances.py`
-    * Quality objective and single instance *(real-valued budget)*: `examples/SMAC4HPO_mlp_hyperband.py`
+    * Quality objective and multiple instances *(instances as budget)*: `examples/BOHB4HPO_sgd_instances.py`
+    * Quality objective and single instance *(real-valued budget)*: `examples/BOHB4HPO_mlp.py`
 
     Parameters
     ----------
@@ -129,9 +129,9 @@ class SuccessiveHalving(AbstractRacer):
 
         if self.min_chall > 1:
             raise ValueError('Successive Halving cannot handle argument `min_chall` > 1.')
+        self.first_run = True
 
         # INSTANCES
-
         self.n_seeds = n_seeds if n_seeds else 1
         self.instance_order = instance_order
 
@@ -184,6 +184,7 @@ class SuccessiveHalving(AbstractRacer):
         self.curr_inst_idx = 0
         self.running_challenger = None
         self.curr_challengers = set()  # type: typing.Set[Configuration]
+        self.fail_challengers = set()  # type: typing.Set[Configuration]
 
     def _init_sh_params(self,
                         initial_budget: typing.Optional[float],
@@ -288,13 +289,18 @@ class SuccessiveHalving(AbstractRacer):
             incumbent and incumbent cost
         """
         # calculating the incumbent's performance for adaptive capping
-        #   - this check is required because there is no incumbent performance
-        #     for the first ever 'intensify' run (from initial design)
-        if incumbent:
+        # this check is required because:
+        #   - there is no incumbent performance for the first ever 'intensify' run (from initial design)
+        #   - during the 1st intensify run, the incumbent shouldn't be capped after being compared against itself
+        if incumbent and incumbent != challenger:
             inc_runs = run_history.get_runs_for_config(incumbent, only_max_observed_budget=True)
             inc_sum_cost = run_history.sum_cost(config=incumbent, instance_seed_budget_keys=inc_runs)
         else:
             inc_sum_cost = np.inf
+            if self.first_run:
+                self.logger.info("First run, no incumbent provided; challenger is assumed to be the incumbent")
+                incumbent = challenger
+                self.first_run = False
 
         # select which instance to run current config on
         curr_budget = self.all_budgets[self.stage]
@@ -320,7 +326,7 @@ class SuccessiveHalving(AbstractRacer):
                                         inc_sum_cost=inc_sum_cost)
             if cutoff is not None and cutoff <= 0:
                 # ran out of time to validate challenger
-                self.logger.debug("Stop challenger itensification due to adaptive capping.")
+                self.logger.debug("Stop challenger intensification due to adaptive capping.")
                 self.curr_inst_idx = np.inf
 
         self.logger.debug('Cutoff for challenger: %s' % str(cutoff))
@@ -351,23 +357,34 @@ class SuccessiveHalving(AbstractRacer):
                                   "Interrupting current challenger and moving on to the next one")
                 # ignore all pending instances
                 self.curr_inst_idx = np.inf
+                status = StatusType.CAPPED
 
             # adding challengers to the list of evaluated challengers
-            self.curr_challengers.add(challenger)
+            #  - should not capped
+            #  - should be successful in at least 1 run
+            # curr_challengers is a set, so "at least 1" success can be counted by set addition (no duplicates)
+            # If a configuration is successful, it is added to curr_challengers.
+            # if it fails after, it is added to fail_challengers too.
+            if np.isfinite(self.curr_inst_idx) and \
+                    status == StatusType.SUCCESS:
+                self.curr_challengers.add(challenger)  # successful configs
+            else:
+                self.fail_challengers.add(challenger)   # capped/crashed configs
 
             # get incumbent in the last stage if all instances have been evaluated
             if n_insts_remaining <= 0:
-                incumbent = self._get_incumbent(challenger=challenger,
-                                                incumbent=incumbent,
-                                                run_history=run_history,
-                                                log_traj=log_traj)
+                incumbent = self._compare_configs(challenger=challenger,
+                                                  incumbent=incumbent,
+                                                  run_history=run_history,
+                                                  log_traj=log_traj)
         except BudgetExhaustedException:
             # Returning the final incumbent selected so far because we ran out of optimization budget
             self.logger.debug("Budget exhausted; "
                               "Interrupting optimization run and returning current incumbent")
 
         # if all configurations for the current stage have been evaluated, reset stage
-        if len(self.curr_challengers) == self.n_configs_in_stage[self.stage] and n_insts_remaining <= 0:
+        num_chal_evaluated = len(self.curr_challengers.union(self.fail_challengers))
+        if num_chal_evaluated == self.n_configs_in_stage[self.stage] and n_insts_remaining <= 0:
 
             self.logger.info('Successive Halving iteration-step: %d-%d with '
                              'budget [%.2f / %d] - evaluated %d challenger(s)' %
@@ -478,12 +495,14 @@ class SuccessiveHalving(AbstractRacer):
             self.configs_to_run = []  # type: typing.List[Configuration]
             self.curr_inst_idx = 0
             self.running_challenger = None
-            self.curr_challengers = set()
+            self.curr_challengers = set()  # successful configs
+            self.fail_challengers = set()   # capped configs
 
         else:
             self.stage += 1
 
-            if self.stage < len(self.all_budgets):
+            if self.stage < len(self.all_budgets) and \
+                    len(self.curr_challengers) > 0:
                 # if this is the next stage in same iteration,
                 # use top 'k' from the evaluated configurations for next iteration
 
@@ -511,16 +530,17 @@ class SuccessiveHalving(AbstractRacer):
                 if self.instance_order == 'shuffle':
                     self.rs.shuffle(self.inst_seed_pairs)
 
-        # to track successful (without capping) configurations for the next stage
-        self.curr_challengers = set()
+        # to track configurations for the next stage
+        self.curr_challengers = set()  # successful configs
+        self.fail_challengers = set()   # capped configs
         self.curr_inst_idx = 0
         self.running_challenger = None
 
-    def _get_incumbent(self,
-                       challenger: Configuration,
-                       incumbent: typing.Optional[Configuration],
-                       run_history: RunHistory,
-                       log_traj: bool = True) -> Configuration:
+    def _compare_configs(self,
+                         incumbent: Configuration,
+                         challenger: Configuration,
+                         run_history: RunHistory,
+                         log_traj: bool = True) -> typing.Optional[Configuration]:
         """
         Compares the challenger with current incumbent and returns the best configuration
 
@@ -540,22 +560,9 @@ class SuccessiveHalving(AbstractRacer):
         typing.Tuple[Configuration, float]
             incumbent and incumbent cost
         """
-        # compare challenger with current incumbent
-        if incumbent is None:  # first intensify run from initial design
-            new_incumbent = challenger
-            inc_perf = run_history.get_cost(new_incumbent)
-            self.logger.info("First Incumbent found! Cost of incumbent is (%.4f)" % inc_perf)
-            self.logger.info("incumbent configuration: %s" % str(challenger))
-            if log_traj:
-                # adding incumbent entry
-                self.stats.inc_changed += 1  # first incumbent
-                self.traj_logger.add_entry(train_perf=inc_perf,
-                                           incumbent_id=self.stats.inc_changed,
-                                           incumbent=new_incumbent)
-
-        elif self.instance_as_budget:
-            new_incumbent = self._compare_configs(incumbent, challenger,
-                                                  run_history, log_traj)
+
+        if self.instance_as_budget:
+            new_incumbent = super()._compare_configs(incumbent, challenger, run_history, log_traj)
             # if compare config returned none, then it is undecided. So return old incumbent
             new_incumbent = incumbent if new_incumbent is None else new_incumbent
         else:
@@ -607,6 +614,12 @@ class SuccessiveHalving(AbstractRacer):
                 else:
                     self.logger.debug("Incumbent (%.4f) is at least as good as the challenger (%.4f) on budget %.4f.",
                                       inc_cost, chall_cost, inc_run.budget)
+                    if log_traj and self.stats.inc_changed == 0:
+                        # adding incumbent entry
+                        self.stats.inc_changed += 1  # first incumbent
+                        self.traj_logger.add_entry(train_perf=inc_cost,
+                                                   incumbent_id=self.stats.inc_changed,
+                                                   incumbent=incumbent)
                     new_incumbent = incumbent
 
         return new_incumbent
diff --git a/smac/runhistory/runhistory.py b/smac/runhistory/runhistory.py
index 6aa340c7d..6498c9d35 100644
--- a/smac/runhistory/runhistory.py
+++ b/smac/runhistory/runhistory.py
@@ -195,6 +195,13 @@ class RunHistory(object):
                 Defines how data will be used.
         """
 
+        if config is None:
+            raise TypeError('Configuration to add to the runhistory must not be None')
+        elif not isinstance(config, Configuration):
+            raise TypeError(
+                'Configuration to add to the runhistory is not of type Configuration, but %s' % type(config)
+            )
+
         # Get the config id
         config_id_tmp = self.config_ids.get(config)
         if config_id_tmp is None:
diff --git a/smac/tae/execute_func.py b/smac/tae/execute_func.py
index c3b75947a..039e25afd 100644
--- a/smac/tae/execute_func.py
+++ b/smac/tae/execute_func.py
@@ -50,7 +50,8 @@ class AbstractTAFunc(ExecuteTARun):
 
         super().__init__(ta=ta, stats=stats, runhistory=runhistory,
                          run_obj=run_obj, par_factor=par_factor,
-                         cost_for_crash=cost_for_crash)
+                         cost_for_crash=cost_for_crash,
+                         abort_on_first_run_crash=abort_on_first_run_crash)
         """
         Abstract class for having a function as target algorithm
 


Test patch:
diff --git a/test/test_facade/test_smac4bohb_facade.py b/test/test_facade/test_bohb4hpo_facade.py
similarity index 100%
rename from test/test_facade/test_smac4bohb_facade.py
rename to test/test_facade/test_bohb4hpo_facade.py
diff --git a/test/test_intensify/test_intensify.py b/test/test_intensify/test_intensify.py
index 2e4e3f807..a0071a3ab 100644
--- a/test/test_intensify/test_intensify.py
+++ b/test/test_intensify/test_intensify.py
@@ -37,11 +37,11 @@ class TestIntensify(unittest.TestCase):
         self.rh = RunHistory()
         self.cs = get_config_space()
         self.config1 = Configuration(self.cs,
-                                     values={'a': 0, 'b': 100})
+                                     values={'a': 1, 'b': 100})
         self.config2 = Configuration(self.cs,
                                      values={'a': 100, 'b': 0})
         self.config3 = Configuration(self.cs,
-                                     values={'a': 100, 'b': 100})
+                                     values={'a': 0, 'b': 100})
 
         self.scen = Scenario({"cutoff_time": 2, 'cs': self.cs,
                               "run_obj": 'runtime',
@@ -384,9 +384,9 @@ class TestIntensify(unittest.TestCase):
         with self.assertRaisesRegex(ValueError, "No configurations/chooser provided"):
             intensifier._generate_challengers(challengers=None, chooser=None)
 
-    def test_eval_challenger(self):
+    def test_eval_challenger_1(self):
         """
-            test eval_challenger() - a complete intensification run
+            test eval_challenger() - a complete intensification run with a `always_race_against` configuration
         """
         def target(x):
             return x['a']
@@ -398,40 +398,145 @@ class TestIntensify(unittest.TestCase):
             tae_runner=taf, stats=self.stats,
             traj_logger=TrajLogger(output_dir=None, stats=self.stats),
             rng=np.random.RandomState(12345),
-            instances=[1], run_obj_time=False,
+            instances=[1, 2], run_obj_time=False,
             deterministic=False, always_race_against=self.config3, run_limit=1)
 
+        self.assertEqual(intensifier.n_iters, 0)
+
+        # intensification iteration #1
         # run incumbent first if it was not run before
-        config, _ = intensifier.get_next_challenger(challengers=[self.config2, self.config1, self.config3],
+        config, _ = intensifier.get_next_challenger(challengers=[self.config2, self.config1],
                                                     chooser=None)
-        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=None,
-                                             run_history=self.rh,)
-
+        self.assertEqual(config, self.config2)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)
+        # eval config 2 (=first run)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=None, run_history=self.rh, )
         self.assertEqual(inc, self.config2)
         self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+        self.assertEqual(self.stats.inc_changed, 1)
 
         # run challenger now that the incumbent has been executed
-        config, _ = intensifier.get_next_challenger(challengers=[self.config2, self.config1, self.config3],
+        config, _ = intensifier.get_next_challenger(challengers=None,  # don't need a new list here as old one is cont'd
                                                     chooser=None)
-        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc,
-                                             run_history=self.rh,)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+        self.assertEqual(config, self.config1)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc, run_history=self.rh, )
 
-        # challenger should have a better performance, so incumbent should have changed
+        # challenger has a better performance, so incumbent has changed
         self.assertEqual(inc, self.config1)
-        self.assertEqual(self.stats.inc_changed, 1)
-        self.assertEqual(intensifier.stage, IntensifierStage.RUN_DEFAULT)
+        self.assertEqual(self.stats.inc_changed, 2)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_BASIS)
         self.assertFalse(intensifier.continue_challenger)
 
-        # run `always_race_against` now since the incumbent has changed
-        config, _ = intensifier.get_next_challenger(challengers=[self.config2, self.config1, self.config3],
+        # run basis configuration (`always_race_against`)
+        config, _ = intensifier.get_next_challenger(challengers=None,  # don't need a new list here as old one is cont'd
                                                     chooser=None)
-        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc,
-                                             run_history=self.rh,)
+        self.assertEqual(config, self.config3)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_BASIS)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc, run_history=self.rh, )
 
-        self.assertEqual(inc, self.config1)
+        # the basis configuration (config3) should be better than incumbent
+        self.assertEqual(inc, self.config3)
+        self.assertEqual(self.stats.inc_changed, 3)
         self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)
         self.assertEqual(len(self.rh.get_runs_for_config(self.config3, only_max_observed_budget=True)), 1)
-        self.assertEqual(intensifier.n_iters, 1)
+        self.assertEqual(intensifier.n_iters, 1)  # 1 intensification run complete!
         self.assertIsInstance(intensifier.configs_to_run, collections.Iterator)
+        # no configs should be left at the end
+        with self.assertRaises(StopIteration):
+            next(intensifier.configs_to_run)
+
+        # intensification iteration #2
+        config, _ = intensifier.get_next_challenger(challengers=None,  # don't need a new list here as old one is cont'd
+                                                    chooser=None)
+        self.assertEqual(config, self.config1)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc, run_history=self.rh, )
+
+        # incumbent is run on the 2nd instance
+        self.assertEqual(inc, self.config3)
+        self.assertEqual(self.stats.inc_changed, 3)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config1, only_max_observed_budget=True)), 1)
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config2, only_max_observed_budget=True)), 1)
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config3, only_max_observed_budget=True)), 2)
+
+    def test_eval_challenger_2(self):
+        """
+            test eval_challenger() - a complete intensification run without a `always_race_against` configuration
+        """
+
+        def target(x):
+            return x['a']
+
+        taf = ExecuteTAFuncDict(ta=target, stats=self.stats)
+        taf.runhistory = self.rh
+
+        intensifier = Intensifier(
+            tae_runner=taf, stats=self.stats,
+            traj_logger=TrajLogger(output_dir=None, stats=self.stats),
+            rng=np.random.RandomState(12345),
+            instances=[1], run_obj_time=False,
+            deterministic=True, always_race_against=None, run_limit=1)
+
+        self.assertEqual(intensifier.n_iters, 0)
+
+        # intensification iteration #1
+        # run incumbent first if it was not run before
+        config, _ = intensifier.get_next_challenger(challengers=[self.config2, self.config1],
+                                                    chooser=None)
+        self.assertEqual(config, self.config2)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)
+        # eval config 2 (=first run)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=None, run_history=self.rh, )
+        self.assertEqual(inc, self.config2)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+        self.assertEqual(self.stats.inc_changed, 1)
+
+        # run challenger now that the incumbent has been executed
+        config, _ = intensifier.get_next_challenger(challengers=None,  # don't need a new list here as old one is cont'd
+                                                    chooser=None)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+        self.assertEqual(config, self.config1)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc, run_history=self.rh, )
+
+        # challenger has a better performance, so incumbent has changed
+        self.assertEqual(inc, self.config1)
+        self.assertEqual(self.stats.inc_changed, 2)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)  # since there is no `always_race_against`
+        self.assertFalse(intensifier.continue_challenger)
+        self.assertEqual(intensifier.n_iters, 1)  # 1 intensification run complete!
+        # no configs should be left at the end
         with self.assertRaises(StopIteration):
             next(intensifier.configs_to_run)
+
+        # intensification iteration #2
+        # run incumbent
+        config, _ = intensifier.get_next_challenger(challengers=None,  # since incumbent is run, no configs required
+                                                    chooser=None)
+        self.assertEqual(config, self.config1)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc, run_history=self.rh, )
+
+        self.assertEqual(inc, self.config1)
+        self.assertEqual(self.stats.inc_changed, 2)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config1, only_max_observed_budget=True)), 1)
+        self.assertEqual(intensifier.n_iters, 1)
+        self.assertIsInstance(intensifier.configs_to_run, collections.Iterator)
+
+        # run challenger
+        config, _ = intensifier.get_next_challenger(challengers=[self.config3],  # provide next challengers
+                                                    chooser=None)
+        self.assertEqual(config, self.config3)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_CHALLENGER)
+        inc, _ = intensifier.eval_challenger(challenger=config, incumbent=inc, run_history=self.rh, )
+
+        self.assertEqual(inc, self.config3)
+        self.assertEqual(self.stats.inc_changed, 3)
+        self.assertEqual(intensifier.stage, IntensifierStage.RUN_INCUMBENT)
+
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config1, only_max_observed_budget=True)), 1)
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config2, only_max_observed_budget=True)), 1)
+        self.assertEqual(len(self.rh.get_runs_for_config(self.config3, only_max_observed_budget=True)), 1)
diff --git a/test/test_intensify/test_successive_halving.py b/test/test_intensify/test_successive_halving.py
index e04fd02b1..18e3fe1b5 100644
--- a/test/test_intensify/test_successive_halving.py
+++ b/test/test_intensify/test_successive_halving.py
@@ -1,4 +1,5 @@
 import unittest
+from unittest import mock
 
 import logging
 import numpy as np
@@ -143,7 +144,7 @@ class TestSuccessiveHalving(unittest.TestCase):
         intensifier = SuccessiveHalving(
             tae_runner=None, stats=self.stats, traj_logger=None,
             rng=np.random.RandomState(12345),
-            instances=[1], initial_budget=1)
+            instances=[1, 2], initial_budget=1)
         self.rh.add(config=self.config1, cost=1, time=1,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None)
@@ -193,6 +194,25 @@ class TestSuccessiveHalving(unittest.TestCase):
             intensifier._top_k(configs=[self.config2, self.config1, self.config3],
                                k=1, run_history=self.rh)
 
+    def test_top_k_3(self):
+        """
+            test _top_k() for not enough configs to generate for the next budget
+        """
+        intensifier = SuccessiveHalving(
+            tae_runner=None, stats=self.stats, traj_logger=None,
+            rng=np.random.RandomState(12345),
+            instances=[1], initial_budget=1)
+        self.rh.add(config=self.config1, cost=1, time=1,
+                    status=StatusType.SUCCESS, instance_id=1, seed=None,
+                    additional_info=None)
+        self.rh.add(config=self.config2, cost=1, time=1,
+                    status=StatusType.CRASHED, instance_id=1, seed=None,
+                    additional_info=None)
+        configs = intensifier._top_k(configs=[self.config1], k=2, run_history=self.rh)
+
+        # top_k should return whatever configuration is possible
+        self.assertEqual(configs, [self.config1])
+
     def test_get_next_challenger_1(self):
         """
             test get_next_challenger for a presently running configuration
@@ -324,13 +344,66 @@ class TestSuccessiveHalving(unittest.TestCase):
            test eval_challenger with runtime objective and adaptive capping
         """
 
-        def target(x):
-            time.sleep(1.5)
+        def target(x: Configuration, instance: str):
+            if x['a'] == 100 or instance == 2:
+                time.sleep(1.5)
             return (x['a'] + 1) / 1000.
 
         taf = ExecuteTAFuncDict(ta=target, stats=self.stats, run_obj="runtime")
         taf.runhistory = self.rh
 
+        intensifier = SuccessiveHalving(
+            tae_runner=taf, stats=self.stats,
+            traj_logger=TrajLogger(output_dir=None, stats=self.stats),
+            rng=np.random.RandomState(12345), deterministic=True, cutoff=1,
+            instances=[1, 2], initial_budget=1, max_budget=2, eta=2, instance_order=None)
+
+        # config1 should be executed successfully and selected as incumbent
+        config, _ = intensifier.get_next_challenger(challengers=[self.config1], chooser=None, run_history=self.rh)
+        inc, _ = intensifier.eval_challenger(challenger=config,
+                                             incumbent=None,
+                                             run_history=self.rh, )
+        self.assertEqual(config, self.config1)
+        self.assertEqual(self.stats.ta_runs, 1)
+        self.assertEqual(self.stats.inc_changed, 1)
+
+        # config2 should be capped and config1 should still be the incumbent
+        config, _ = intensifier.get_next_challenger(challengers=[self.config2], chooser=None, run_history=self.rh)
+        inc, _ = intensifier.eval_challenger(challenger=config,
+                                             incumbent=inc,
+                                             run_history=self.rh,)
+
+        self.assertEqual(inc, self.config1)
+        self.assertEqual(self.stats.ta_runs, 2)
+        self.assertEqual(self.stats.inc_changed, 1)
+        self.assertEqual(list(self.rh.data.values())[1][2], StatusType.CAPPED)
+
+        # config1 is selected for the next stage and allowed to timeout since this is the 1st run for this instance
+        config, _ = intensifier.get_next_challenger(challengers=[], chooser=None, run_history=self.rh)
+        inc, _ = intensifier.eval_challenger(challenger=config,
+                                             incumbent=inc,
+                                             run_history=self.rh, )
+        self.assertEqual(inc, self.config1)
+        self.assertEqual(self.stats.ta_runs, 3)
+        self.assertEqual(list(self.rh.data.values())[2][2], StatusType.TIMEOUT)
+
+    @mock.patch.object(SuccessiveHalving, '_top_k')
+    def test_eval_challenger_capping(self, patch):
+        """
+            test eval_challenger with adaptive capping and all configurations capped/crashed
+        """
+
+        def target(x):
+            if x['b'] == 100:
+                time.sleep(1.5)
+            if x['a'] == 100:
+                raise ValueError('You shall not pass')
+            return (x['a'] + 1) / 1000.
+
+        taf = ExecuteTAFuncDict(ta=target, stats=self.stats, run_obj="runtime",
+                                abort_on_first_run_crash=False)
+        taf.runhistory = self.rh
+
         intensifier = SuccessiveHalving(
             tae_runner=taf, stats=self.stats,
             traj_logger=TrajLogger(output_dir=None, stats=self.stats),
@@ -342,17 +415,41 @@ class TestSuccessiveHalving(unittest.TestCase):
                         status=StatusType.SUCCESS, instance_id=i + 1, seed=0,
                         additional_info=None)
 
-        intensifier._update_stage(run_history=None)
-
+        # provide configurations
+        config, _ = intensifier.get_next_challenger(challengers=[self.config2],
+                                                    chooser=None, run_history=self.rh)
         # config2 should be capped and config1 should still be the incumbent
-        inc, _ = intensifier.eval_challenger(challenger=self.config2,
+        inc, _ = intensifier.eval_challenger(challenger=config,
                                              incumbent=self.config1,
-                                             run_history=self.rh,)
-
+                                             run_history=self.rh, )
         self.assertEqual(inc, self.config1)
         self.assertEqual(self.stats.ta_runs, 1)
+        self.assertEqual(list(self.rh.data.values())[2][2], StatusType.CRASHED)
+        self.assertEqual(len(intensifier.curr_challengers), 0)
+
+        # provide configurations
+        config, _ = intensifier.get_next_challenger(challengers=[self.config3],
+                                                    chooser=None, run_history=self.rh)
+        # config3 should also be capped and config1 should be the incumbent
+        inc, _ = intensifier.eval_challenger(challenger=config,
+                                             incumbent=self.config1,
+                                             run_history=self.rh, )
+        self.assertEqual(inc, self.config1)
+        self.assertEqual(self.stats.ta_runs, 2)
         self.assertEqual(self.stats.inc_changed, 0)
-        self.assertEqual(list(self.rh.data.values())[2][2], StatusType.CAPPED)
+        self.assertEqual(list(self.rh.data.values())[3][2], StatusType.CAPPED)
+        self.assertEqual(len(intensifier.curr_challengers), 0)
+        # top_k() should not be called since all configs were capped
+        self.assertFalse(patch.called)
+
+        # now the SH iteration should begin a new iteration since all configs were capped!
+        self.assertEqual(intensifier.sh_iters, 1)
+        self.assertEqual(intensifier.stage, 0)
+
+        # should raise an error as this is a new iteration but no configs were provided
+        with self.assertRaisesRegex(ValueError, 'No configurations/chooser provided.'):
+            config, _ = intensifier.get_next_challenger(challengers=None,
+                                                        chooser=None, run_history=self.rh)
 
     def test_eval_challenger_3(self):
         """
@@ -372,7 +469,7 @@ class TestSuccessiveHalving(unittest.TestCase):
             instances=[0, 1], instance_order='shuffle', eta=2,
             deterministic=True, cutoff=1)
 
-        intensifier._update_stage(run_history=None)
+        intensifier._update_stage(run_history=self.rh)
 
         self.assertEqual(intensifier.inst_seed_pairs, [(0, 0), (1, 0)])
 
@@ -414,50 +511,56 @@ class TestSuccessiveHalving(unittest.TestCase):
 
         config, _ = intensifier.get_next_challenger(challengers=[self.config2], chooser=None, run_history=self.rh)
         inc, _ = intensifier.eval_challenger(challenger=config,
-                                             incumbent=None,
+                                             incumbent=inc,
                                              run_history=self.rh)
 
         self.assertEqual(config, self.config2)
         self.assertEqual(len(self.rh.get_runs_for_config(self.config2, only_max_observed_budget=True)), 2)
 
     def test_do_not_update_incumbent_on_lower_budget(self):
+        """
+            test _compare_config for incumbent selection according to budget
+        """
         intensifier = SuccessiveHalving(
             tae_runner=None, stats=self.stats, traj_logger=None,
-            rng=np.random.RandomState(12345),
-            instances=[1], initial_budget=1)
+            rng=np.random.RandomState(12345), run_obj_time=False,
+            instances=[1], initial_budget=1, max_budget=2, eta=2)
+
+        # SH considers challenger as incumbent in first run in eval_challenger
         self.rh.add(config=self.config1, cost=1, time=1,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=1)
-        inc = intensifier._get_incumbent(challenger=self.config1, incumbent=None, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config1, incumbent=self.config1,
+                                           run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config1)
         self.rh.add(config=self.config1, cost=1, time=1,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=2)
-        inc = intensifier._get_incumbent(challenger=self.config1, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config1, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config1)
 
         # Adding a worse configuration
         self.rh.add(config=self.config2, cost=2, time=2,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=1)
-        inc = intensifier._get_incumbent(challenger=self.config2, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config2, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config1)
         self.rh.add(config=self.config2, cost=2, time=2,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=2)
-        inc = intensifier._get_incumbent(challenger=self.config2, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config2, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config1)
 
         # Adding a better configuration, but the incumbent will only be changed on budget=2
         self.rh.add(config=self.config3, cost=0.5, time=3,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=1)
-        inc = intensifier._get_incumbent(challenger=self.config3, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config3, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config1)
         self.rh.add(config=self.config3, cost=0.5, time=3,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=2)
-        inc = intensifier._get_incumbent(challenger=self.config3, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config3, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config3)
 
         # Test that the state is only based on the runhistory
@@ -469,10 +572,10 @@ class TestSuccessiveHalving(unittest.TestCase):
         self.rh.add(config=self.config4, cost=0.1, time=3,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=1)
-        inc = intensifier._get_incumbent(challenger=self.config4, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config4, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config3)
         self.rh.add(config=self.config4, cost=0.1, time=3,
                     status=StatusType.SUCCESS, instance_id=1, seed=None,
                     additional_info=None, budget=2)
-        inc = intensifier._get_incumbent(challenger=self.config4, incumbent=inc, run_history=self.rh, log_traj=False)
+        inc = intensifier._compare_configs(challenger=self.config4, incumbent=inc, run_history=self.rh, log_traj=False)
         self.assertEqual(inc, self.config4)
diff --git a/test/test_runhistory/test_runhistory.py b/test/test_runhistory/test_runhistory.py
index 27a6be7e5..fa39877b2 100644
--- a/test/test_runhistory/test_runhistory.py
+++ b/test/test_runhistory/test_runhistory.py
@@ -54,6 +54,18 @@ class RunhistoryTest(unittest.TestCase):
             loaded_rh = pickle.load(fh)
         self.assertEqual(loaded_rh.data, rh.data)
 
+    def test_illegal_input(self):
+        rh = RunHistory()
+
+        with self.assertRaisesRegex(TypeError, 'Configuration to add to the runhistory must not be None'):
+            rh.add(config=None, cost=1.23, time=2.34, status=StatusType.SUCCESS)
+
+        with self.assertRaisesRegex(
+            TypeError,
+            "Configuration to add to the runhistory is not of type Configuration, but <class 'str'>",
+        ):
+            rh.add(config='abc', cost=1.23, time=2.34, status=StatusType.SUCCESS)
+
     def test_add_multiple_times(self):
         rh = RunHistory()
         cs = get_config_space()
@@ -192,6 +204,31 @@ class RunhistoryTest(unittest.TestCase):
 
         self.assertTrue(rh.get_cost(config1) == 20)
 
+    def test_get_configs_per_budget(self):
+
+        rh = RunHistory()
+        cs = get_config_space()
+
+        config1 = Configuration(cs,
+                                values={'a': 1, 'b': 1})
+        rh.add(config=config1, cost=10, time=10,
+               status=StatusType.SUCCESS, instance_id=1,
+               seed=1, budget=1)
+
+        config2 = Configuration(cs,
+                                values={'a': 2, 'b': 2})
+        rh.add(config=config2, cost=20, time=20,
+               status=StatusType.SUCCESS, instance_id=1,
+               seed=1, budget=1)
+
+        config3 = Configuration(cs,
+                                values={'a': 3, 'b': 3})
+        rh.add(config=config3, cost=30, time=30,
+               status=StatusType.SUCCESS, instance_id=1,
+               seed=1, budget=3)
+
+        self.assertListEqual(rh.get_all_configs_per_budget([1]), [config1, config2])
+
     def test_json_origin(self):
 
         for origin in ['test_origin', None]:
diff --git a/test/test_runhistory/test_runhistory2epm.py b/test/test_runhistory/test_runhistory2epm.py
index 1e53fb682..89de18057 100644
--- a/test/test_runhistory/test_runhistory2epm.py
+++ b/test/test_runhistory/test_runhistory2epm.py
@@ -338,6 +338,31 @@ class RunhistoryTest(unittest.TestCase):
         c_sol = np.array([False, False, True, True])
         self.assertTrue(np.all(c == c_sol))
 
+    def test_budget_selection(self):
+        '''
+            adding some rundata and check budget selection
+        '''
+
+        rh2epm = runhistory2epm.RunHistory2EPM4Cost(num_params=2,
+                                                    scenario=self.scen)
+
+        self.rh.add(config=self.config1, cost=1, time=1,
+                    status=StatusType.SUCCESS, instance_id=1,
+                    seed=None, budget=1,
+                    additional_info=None)
+        self.rh.add(config=self.config1, cost=2, time=2,
+                    status=StatusType.SUCCESS, instance_id=1,
+                    seed=None, budget=2,
+                    additional_info=None)
+
+        X, y = rh2epm.transform(self.rh, budget_subset=[1])
+        self.assertTrue(np.allclose(X, np.array([[0.005, 0.995]]), atol=0.001))
+        self.assertTrue(np.allclose(y, np.array([[1]])))
+
+        X, y = rh2epm.transform(self.rh, budget_subset=[2])
+        self.assertTrue(np.allclose(X, np.array([[0.005, 0.995]]), atol=0.001))
+        self.assertTrue(np.allclose(y, np.array([[2]])))
+
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/test/test_utils/test_validate.py b/test/test_utils/test_validate.py
index a69b3887e..1285f95c8 100644
--- a/test/test_utils/test_validate.py
+++ b/test/test_utils/test_validate.py
@@ -5,6 +5,7 @@ import shutil
 
 import numpy as np
 
+from smac.configspace import Configuration
 from smac.scenario.scenario import Scenario
 from smac.stats.stats import Stats
 from smac.tae.execute_ta_run import StatusType
@@ -159,20 +160,19 @@ class ValidationTest(unittest.TestCase):
         validator = Validator(scen, self.trajectory, self.rng)
 
         # Get runhistory
-        old_configs = ['config1', 'config2', 'config3',
-                       'config4', 'config5', 'config6']
+        old_configs = [Configuration(scen.cs, values={'x1': i, 'x2': i}) for i in range(1, 7)]
         old_rh = RunHistory()
-        old_rh.add('config1', 1, 1, StatusType.SUCCESS, instance_id='0', seed=0)
-        old_rh.add('config2', 1, 1, StatusType.TIMEOUT, instance_id='0', seed=0)
-        old_rh.add('config3', 1, 1, StatusType.CRASHED, instance_id='0', seed=0)
-        old_rh.add('config4', 1, 1, StatusType.ABORT, instance_id='0', seed=0)
-        old_rh.add('config5', 1, 1, StatusType.MEMOUT, instance_id='0', seed=0)
-        old_rh.add('config6', 1, 1, StatusType.CAPPED, instance_id='0', seed=0)
+        old_rh.add(old_configs[0], 1, 1, StatusType.SUCCESS, instance_id='0', seed=0)
+        old_rh.add(old_configs[1], 1, 1, StatusType.TIMEOUT, instance_id='0', seed=0)
+        old_rh.add(old_configs[2], 1, 1, StatusType.CRASHED, instance_id='0', seed=0)
+        old_rh.add(old_configs[3], 1, 1, StatusType.ABORT, instance_id='0', seed=0)
+        old_rh.add(old_configs[4], 1, 1, StatusType.MEMOUT, instance_id='0', seed=0)
+        old_rh.add(old_configs[5], 1, 1, StatusType.CAPPED, instance_id='0', seed=0)
 
         # Get multiple configs
-        expected = [_Run(inst_specs='0', seed=0, inst='0', config='config3'),
-                    _Run(inst_specs='0', seed=0, inst='0', config='config4'),
-                    _Run(inst_specs='0', seed=0, inst='0', config='config6')]
+        expected = [_Run(inst_specs='0', seed=0, inst='0', config=old_configs[2]),
+                    _Run(inst_specs='0', seed=0, inst='0', config=old_configs[3]),
+                    _Run(inst_specs='0', seed=0, inst='0', config=old_configs[5])]
 
         runs = validator._get_runs(old_configs, ['0'], repetitions=1, runhistory=old_rh)
         self.assertEqual(runs[0], expected)