Repository: automl/SMAC3

Issue:
Integrate Multi-Objective caching
The runhistory caching does not work for MO right now.

Steps to do:
- Call `update_cost` if `num_obj` > 1 in _add
- Check if costs are cached in intensifier

Idea: Save metrics and average/normalize only if `get_cost()` is called. 

Discussion:

Patch:
diff --git a/changelog.md b/changelog.md
index 07965ca22..f23630226 100644
--- a/changelog.md
+++ b/changelog.md
@@ -1,3 +1,11 @@
+# 1.4.0
+
+## Improvements
+* Enabled caching for multi-objectives (#872). Costs are now normalized in `get_cost` 
+or optionally in `average_cost`/`sum_cost`/`min_cost` to receive a single float value. Therefore,
+the cached cost values do not need to be updated everytime a new entry to the runhistory was added.
+
+
 # 1.3.4
 * Added reference to JMLR paper.
 * Typos in documentations.
diff --git a/examples/python/plot_simple_multi_objective.py b/examples/python/plot_simple_multi_objective.py
index df87556bd..af5476610 100644
--- a/examples/python/plot_simple_multi_objective.py
+++ b/examples/python/plot_simple_multi_objective.py
@@ -27,7 +27,10 @@ def plot(all_x):
     plt.figure()
     for x in all_x:
         f1, f2 = schaffer(x)
-        plt.scatter(f1, f2, c="blue", alpha=0.1)
+        plt.scatter(f1, f2, c="blue", alpha=0.1, zorder=3000)
+
+    plt.vlines([1], 0, 4, linestyles="dashed", colors=["red"])
+    plt.hlines([1], 0, 4, linestyles="dashed", colors=["red"])
 
     plt.show()
 
diff --git a/smac/facade/smac_ac_facade.py b/smac/facade/smac_ac_facade.py
index c6173fbab..e9131f25a 100644
--- a/smac/facade/smac_ac_facade.py
+++ b/smac/facade/smac_ac_facade.py
@@ -530,7 +530,7 @@ class SMAC4AC(object):
 
         if scenario.multi_objectives is not None and num_obj > 1:  # type: ignore[attr-defined] # noqa F821
             # define any defaults here
-            _multi_objective_kwargs = {"rng": rng, "num_obj": num_obj}
+            _multi_objective_kwargs = {"rng": rng}
 
             if multi_objective_kwargs is not None:
                 _multi_objective_kwargs.update(multi_objective_kwargs)
diff --git a/smac/intensification/abstract_racer.py b/smac/intensification/abstract_racer.py
index 574c8722d..e83bc570f 100644
--- a/smac/intensification/abstract_racer.py
+++ b/smac/intensification/abstract_racer.py
@@ -89,7 +89,6 @@ class AbstractRacer(object):
         maxR: int = 2000,
         adaptive_capping_slackfactor: float = 1.2,
         min_chall: int = 1,
-        num_obj: int = 1,
     ):
 
         self.logger = logging.getLogger(self.__module__ + "." + self.__class__.__name__)
@@ -129,12 +128,6 @@ class AbstractRacer(object):
         # to mark the end of an iteration
         self.iteration_done = False
 
-        if num_obj > 1:
-            raise ValueError(
-                "Intensifiers only support single objective optimization. For multi-objective problems,"
-                "please refer to multi-objective intensifiers"
-            )
-
     def get_next_run(
         self,
         challengers: Optional[List[Configuration]],
@@ -303,9 +296,10 @@ class AbstractRacer(object):
         # reasons)
         chall_inst_seeds = run_history.get_runs_for_config(challenger, only_max_observed_budget=True)
         chal_sum_cost = run_history.sum_cost(
-            config=challenger,
-            instance_seed_budget_keys=chall_inst_seeds,
+            config=challenger, instance_seed_budget_keys=chall_inst_seeds, normalize=True
         )
+        assert type(chal_sum_cost) == float
+
         cutoff = min(curr_cutoff, inc_sum_cost * self.adaptive_capping_slackfactor - chal_sum_cost)
         return cutoff
 
@@ -348,8 +342,11 @@ class AbstractRacer(object):
 
         # performance on challenger runs, the challenger only becomes incumbent
         # if it dominates the incumbent
-        chal_perf = run_history.average_cost(challenger, to_compare_runs)
-        inc_perf = run_history.average_cost(incumbent, to_compare_runs)
+        chal_perf = run_history.average_cost(challenger, to_compare_runs, normalize=True)
+        inc_perf = run_history.average_cost(incumbent, to_compare_runs, normalize=True)
+
+        assert type(chal_perf) == float
+        assert type(inc_perf) == float
 
         # Line 15
         if np.any(chal_perf > inc_perf) and len(chall_runs) >= self.minR:
diff --git a/smac/intensification/hyperband.py b/smac/intensification/hyperband.py
index c80fda4b8..739bdd552 100644
--- a/smac/intensification/hyperband.py
+++ b/smac/intensification/hyperband.py
@@ -98,7 +98,6 @@ class _Hyperband(_SuccessiveHalving):
         min_chall: int = 1,
         incumbent_selection: str = "highest_executed_budget",
         identifier: int = 0,
-        num_obj: int = 1,
     ) -> None:
 
         super().__init__(
@@ -119,7 +118,6 @@ class _Hyperband(_SuccessiveHalving):
             adaptive_capping_slackfactor=adaptive_capping_slackfactor,
             min_chall=min_chall,
             incumbent_selection=incumbent_selection,
-            num_obj=num_obj,
         )
 
         self.identifier = identifier
diff --git a/smac/intensification/intensification.py b/smac/intensification/intensification.py
index 119367571..a50d280e6 100644
--- a/smac/intensification/intensification.py
+++ b/smac/intensification/intensification.py
@@ -144,7 +144,6 @@ class Intensifier(AbstractRacer):
         maxR: int = 2000,
         adaptive_capping_slackfactor: float = 1.2,
         min_chall: int = 2,
-        num_obj: int = 1,
     ):
         super().__init__(
             stats=stats,
@@ -159,7 +158,6 @@ class Intensifier(AbstractRacer):
             maxR=maxR,
             adaptive_capping_slackfactor=adaptive_capping_slackfactor,
             min_chall=min_chall,
-            num_obj=num_obj,
         )
 
         self.logger = logging.getLogger(self.__module__ + "." + self.__class__.__name__)
@@ -795,6 +793,7 @@ class Intensifier(AbstractRacer):
         """
         chal_runs = run_history.get_runs_for_config(challenger, only_max_observed_budget=True)
         chal_perf = run_history.get_cost(challenger)
+
         # if all <instance, seed> have been run, compare challenger performance
         if not self.to_run:
             new_incumbent = self._compare_configs(
@@ -896,11 +895,8 @@ class Intensifier(AbstractRacer):
         # because of efficiency computed here
         inst_seed_pairs = list(inc_inst_seeds - set(missing_runs))
         # cost used by incumbent for going over all runs in inst_seed_pairs
-        inc_sum_cost = run_history.sum_cost(
-            config=incumbent,
-            instance_seed_budget_keys=inst_seed_pairs,
-        )
-
+        inc_sum_cost = run_history.sum_cost(config=incumbent, instance_seed_budget_keys=inst_seed_pairs, normalize=True)
+        assert type(inc_sum_cost) == float
         return to_run, inc_sum_cost
 
     def get_next_challenger(
diff --git a/smac/intensification/parallel_scheduling.py b/smac/intensification/parallel_scheduling.py
index 4c15173f3..d08595d1b 100644
--- a/smac/intensification/parallel_scheduling.py
+++ b/smac/intensification/parallel_scheduling.py
@@ -89,7 +89,6 @@ class ParallelScheduler(AbstractRacer):
         inst_seed_pairs: Optional[List[Tuple[str, int]]] = None,
         min_chall: int = 1,
         incumbent_selection: str = "highest_executed_budget",
-        num_obj: int = 1,
     ) -> None:
 
         super().__init__(
@@ -103,7 +102,6 @@ class ParallelScheduler(AbstractRacer):
             run_obj_time=run_obj_time,
             adaptive_capping_slackfactor=adaptive_capping_slackfactor,
             min_chall=min_chall,
-            num_obj=num_obj,
         )
 
         # We have a pool of instances that yield configurations ot run
diff --git a/smac/intensification/simple_intensifier.py b/smac/intensification/simple_intensifier.py
index fe8d6d1d2..85836dcc6 100644
--- a/smac/intensification/simple_intensifier.py
+++ b/smac/intensification/simple_intensifier.py
@@ -46,7 +46,6 @@ class SimpleIntensifier(AbstractRacer):
         cutoff: Optional[float] = None,
         deterministic: bool = False,
         run_obj_time: bool = True,
-        num_obj: int = 1,
         **kwargs: Any,
     ) -> None:
 
@@ -61,10 +60,7 @@ class SimpleIntensifier(AbstractRacer):
             run_obj_time=run_obj_time,
             adaptive_capping_slackfactor=1.0,
             min_chall=1,
-            num_obj=num_obj,
         )
-        # Simple intensifier does not require comparing run results, thus we could simply ignore num_obj here
-
         # We want to control the number of runs that are sent to
         # the workers. At any time, we want to make sure that if there
         # are just W workers, there should be at max W active runs
diff --git a/smac/intensification/successive_halving.py b/smac/intensification/successive_halving.py
index 749fbcf8f..106fa7c86 100644
--- a/smac/intensification/successive_halving.py
+++ b/smac/intensification/successive_halving.py
@@ -137,7 +137,6 @@ class _SuccessiveHalving(AbstractRacer):
         min_chall: int = 1,
         incumbent_selection: str = "highest_executed_budget",
         identifier: int = 0,
-        num_obj: int = 1,
     ) -> None:
         super().__init__(
             stats=stats,
@@ -150,7 +149,6 @@ class _SuccessiveHalving(AbstractRacer):
             run_obj_time=run_obj_time,
             adaptive_capping_slackfactor=adaptive_capping_slackfactor,
             min_chall=min_chall,
-            num_obj=num_obj,
         )
 
         self.identifier = identifier
@@ -629,14 +627,16 @@ class _SuccessiveHalving(AbstractRacer):
         #   - 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)
+            inc_sum_cost = run_history.sum_cost(config=incumbent, instance_seed_budget_keys=inc_runs, normalize=True)
         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
 
-        # selecting instance-seed subset for this budget, depending on the kind of budget
+        assert type(inc_sum_cost) == float
+
+        # Selecting instance-seed subset for this budget, depending on the kind of budget
         if self.instance_as_budget:
             prev_budget = int(self.all_budgets[self.stage - 1]) if self.stage > 0 else 0
             curr_insts = self.inst_seed_pairs[int(prev_budget) : int(curr_budget)]
diff --git a/smac/optimizer/multi_objective/abstract_multi_objective_algorithm.py b/smac/optimizer/multi_objective/abstract_multi_objective_algorithm.py
index 6ce18d141..3d321772d 100644
--- a/smac/optimizer/multi_objective/abstract_multi_objective_algorithm.py
+++ b/smac/optimizer/multi_objective/abstract_multi_objective_algorithm.py
@@ -1,3 +1,5 @@
+from __future__ import annotations
+
 from abc import ABC
 from typing import Optional
 
@@ -10,10 +12,8 @@ class AbstractMultiObjectiveAlgorithm(ABC):
     It can be applied to rh2epm or epmchooser.
     """
 
-    def __init__(self, num_obj: int, rng: Optional[np.random.RandomState] = None):
-
+    def __init__(self, rng: Optional[np.random.RandomState] = None):
         if rng is None:
             rng = np.random.RandomState(0)
 
-        self.num_obj = num_obj
         self.rng = rng
diff --git a/smac/optimizer/multi_objective/aggregation_strategy.py b/smac/optimizer/multi_objective/aggregation_strategy.py
index d860583e8..297481149 100644
--- a/smac/optimizer/multi_objective/aggregation_strategy.py
+++ b/smac/optimizer/multi_objective/aggregation_strategy.py
@@ -1,3 +1,5 @@
+from __future__ import annotations
+
 from abc import abstractmethod
 
 import numpy as np
@@ -9,22 +11,24 @@ from smac.optimizer.multi_objective.abstract_multi_objective_algorithm import (
 
 class AggregationStrategy(AbstractMultiObjectiveAlgorithm):
     """
-    An abstract class to aggregate multi-objective losses to a single objective losses, which can then be utilized
-    by the single-objective optimizer.
+    An abstract class to aggregate multi-objective losses to a single objective loss,
+    which can then be utilized by the single-objective optimizer.
     """
 
     @abstractmethod
-    def __call__(self, values: np.ndarray) -> float:
+    def __call__(self, values: list[float]) -> float:
         """
         Transform a multi-objective loss to a single loss.
 
         Parameters
         ----------
-            values: np.ndarray[num_evaluations, num_obj].
+        values : list[float]
+            Normalized values.
 
         Returns
         -------
-            cost: float.
+        cost : float
+            Combined cost.
         """
         raise NotImplementedError
 
@@ -35,16 +39,18 @@ class MeanAggregationStrategy(AggregationStrategy):
     which can then be utilized by the single-objective optimizer.
     """
 
-    def __call__(self, values: np.ndarray) -> float:
+    def __call__(self, values: list[float]) -> float:
         """
         Transform a multi-objective loss to a single loss.
 
         Parameters
         ----------
-            values (np.ndarray): Normalized values.
+        values : list[float]
+            Normalized values.
 
         Returns
         -------
-            cost (float): Combined cost.
+        cost : float
+            Combined cost.
         """
-        return np.mean(values, axis=1)
+        return np.mean(values, axis=0)
diff --git a/smac/optimizer/multi_objective/parego.py b/smac/optimizer/multi_objective/parego.py
index 90b75efa5..b9b05a936 100644
--- a/smac/optimizer/multi_objective/parego.py
+++ b/smac/optimizer/multi_objective/parego.py
@@ -1,3 +1,5 @@
+from __future__ import annotations
+
 from typing import Optional
 
 import numpy as np
@@ -8,32 +10,32 @@ from smac.optimizer.multi_objective.aggregation_strategy import AggregationStrat
 class ParEGO(AggregationStrategy):
     def __init__(
         self,
-        num_obj: int,
         rng: Optional[np.random.RandomState] = None,
         rho: float = 0.05,
     ):
-        super(ParEGO, self).__init__(num_obj=num_obj, rng=rng)
+        super(ParEGO, self).__init__(rng=rng)
         self.rho = rho
 
-    def __call__(self, values: np.ndarray) -> float:
+    def __call__(self, values: list[float]) -> float:
         """
         Transform a multi-objective loss to a single loss.
 
         Parameters
         ----------
-            values (np.ndarray): Normalized values.
+        values : list[float]
+            Normalized values.
 
         Returns
         -------
-            cost (float): Combined cost.
+        cost : float
+            Combined cost.
         """
         # Then we have to compute the weight
-        theta = self.rng.rand(self.num_obj)
+        theta = self.rng.rand(len(values))
 
         # Normalize st all theta values sum up to 1
         theta = theta / (np.sum(theta) + 1e-10)
 
         # Weight the values
         theta_f = theta * values
-
-        return np.max(theta_f, axis=1) + self.rho * np.sum(theta_f, axis=1)
+        return np.max(theta_f, axis=0) + self.rho * np.sum(theta_f, axis=0)
diff --git a/smac/runhistory/runhistory.py b/smac/runhistory/runhistory.py
index a84a06a7c..48bd6db15 100644
--- a/smac/runhistory/runhistory.py
+++ b/smac/runhistory/runhistory.py
@@ -1,3 +1,5 @@
+from __future__ import annotations
+
 from typing import (
     Any,
     Dict,
@@ -30,6 +32,8 @@ __maintainer__ = "Marius Lindauer"
 __email__ = "lindauer@cs.uni-freiburg.de"
 __version__ = "0.0.1"
 
+logger = PickableLoggerAdapter(__name__)
+
 
 # NOTE class instead of collection to have a default value for budget in RunKey
 class RunKey(collections.namedtuple("RunKey", ["config_id", "instance_id", "seed", "budget"])):
@@ -192,9 +196,9 @@ class RunHistory(Mapping[RunKey, RunValue]):
         self._n_id = 0
 
         # Stores cost for each configuration ID
-        self._cost_per_config = {}  # type: Dict[int, float]
+        self._cost_per_config = {}  # type: Dict[int, float | list[float]]
         # Stores min cost across all budgets for each configuration ID
-        self._min_cost_per_config = {}  # type: Dict[int, float]
+        self._min_cost_per_config = {}  # type: Dict[int, float | list[float]]
         # runs_per_config maps the configuration ID to the number of runs for that configuration
         # and is necessary for computing the moving average
         self.num_runs_per_config = {}  # type: Dict[int, int]
@@ -207,111 +211,35 @@ class RunHistory(Mapping[RunKey, RunValue]):
         self.num_obj = -1  # type: int
         self.objective_bounds = []  # type: List[Tuple[float, float]]
 
-    def add(
-        self,
-        config: Configuration,
-        cost: Union[int, float, list, np.ndarray],
-        time: float,
-        status: StatusType,
-        instance_id: Optional[str] = None,
-        seed: Optional[int] = None,
-        budget: float = 0.0,
-        starttime: float = 0.0,
-        endtime: float = 0.0,
-        additional_info: Optional[Dict] = None,
-        origin: DataOrigin = DataOrigin.INTERNAL,
-        force_update: bool = False,
-    ) -> None:
-        """Adds a data of a new target algorithm (TA) run; it will update data if the same key
-        values are used (config, instance_id, seed)
-
-        Parameters
-        ----------
-            config : dict (or other type -- depending on config space module)
-                Parameter configuration
-            cost: Union[int, float, list, np.ndarray]
-                Cost of TA run (will be minimized)
-            time: float
-                Runtime of TA run
-            status: str
-                Status in {SUCCESS, TIMEOUT, CRASHED, ABORT, MEMOUT}
-            instance_id: str
-                String representing an instance (default: None)
-            seed: int
-                Random seed used by TA (default: None)
-            budget: float
-                budget (cutoff) used in intensifier to limit TA (default: 0)
-            starttime: float
-                starting timestamp of TA evaluation
-            endtime: float
-                ending timestamp of TA evaluation
-            additional_info: dict
-                Additional run infos (could include further returned
-                information from TA or fields such as start time and host_id)
-            origin: DataOrigin
-                Defines how data will be used.
-            force_update: bool (default: False)
-                Forces the addition of a config to the history
-        """
-        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)
-            )
+    def __contains__(self, k: object) -> bool:
+        """Dictionary semantics for `k in runhistory`"""
+        return k in self.data
 
-        # Squeeze is important to reduce arrays with one element
-        # to scalars.
-        cost = np.asarray(cost).squeeze()
+    def __getitem__(self, k: RunKey) -> RunValue:
+        """Dictionary semantics for `v = runhistory[k]`"""
+        return self.data[k]
 
-        # Get the config id
-        config_id_tmp = self.config_ids.get(config)
-        if config_id_tmp is None:
-            self._n_id += 1
-            self.config_ids[config] = self._n_id
-            config_id = cast(int, self.config_ids.get(config))
-            self.ids_config[self._n_id] = config
-        else:
-            config_id = cast(int, config_id_tmp)
+    def __iter__(self) -> Iterator[RunKey]:
+        """Dictionary semantics for `for k in runhistory.keys()`, enables.
 
-        if self.num_obj == -1:
-            self.num_obj = np.size(cost)
-        else:
-            if np.size(cost) != self.num_obj:
-                raise ValueError(
-                    f"Cost is not of the same length ({np.size(cost)}) as the number " f"of objectives ({self.num_obj})"
-                )
+        .items()
+        """
+        return iter(self.data.keys())
 
-        k = RunKey(config_id, instance_id, seed, budget)
-        v = RunValue(cost.tolist(), time, status, starttime, endtime, additional_info)
+    def __len__(self) -> int:
+        """Enables the `len(runhistory)`"""
+        return len(self.data)
 
-        # Construct keys and values for the data dictionary
-        for key, value in (
-            ("config", config.get_dictionary()),
-            ("config_id", config_id),
-            ("instance_id", instance_id),
-            ("seed", seed),
-            ("budget", budget),
-            ("cost", cost.tolist()),
-            ("time", time),
-            ("status", status),
-            ("starttime", starttime),
-            ("endtime", endtime),
-            ("additional_info", additional_info),
-            ("origin", config.origin),
-        ):
-            self._check_json_serializable(key, value, EnumEncoder, k, v)
+    def empty(self) -> bool:
+        """Check whether or not the RunHistory is empty.
 
-        # Each runkey is supposed to be used only once. Repeated tries to add
-        # the same runkey will be ignored silently if not capped.
-        if self.overwrite_existing_runs or force_update or self.data.get(k) is None:
-            self._add(k, v, status, origin)
-        elif status != StatusType.CAPPED and self.data[k].status == StatusType.CAPPED:
-            # overwrite capped runs with uncapped runs
-            self._add(k, v, status, origin)
-        elif status == StatusType.CAPPED and self.data[k].status == StatusType.CAPPED and cost > self.data[k].cost:
-            # overwrite if censored with a larger cutoff
-            self._add(k, v, status, origin)
+        Returns
+        -------
+        emptiness: bool
+            True if runs have been added to the RunHistory,
+            False otherwise
+        """
+        return len(self.data) == 0
 
     def _check_json_serializable(
         self,
@@ -384,24 +312,174 @@ class RunHistory(Mapping[RunKey, RunValue]):
                 # append new budget to existing inst-seed-key dict
                 self._configid_to_inst_seed_budget[k.config_id][is_k].append(k.budget)
 
-            # Update costs in multi-objective setting s.t. all costs are
-            # normalized the same.
-            # TODO: This is only a temporary solution because the caching is not used.
-            if self.num_obj > 1:
-                self.update_all_costs()
+            # if budget is used, then update cost instead of incremental updates
+            if not self.overwrite_existing_runs and k.budget == 0:
+                # assumes an average across runs as cost function aggregation, this is used for
+                # algorithm configuration (incremental updates are used to save time as getting the
+                # cost for > 100 instances is high)
+                self.incremental_update_cost(self.ids_config[k.config_id], v.cost)
             else:
-                # if budget is used, then update cost instead of incremental updates
-                if not self.overwrite_existing_runs and k.budget == 0:
-                    # assumes an average across runs as cost function aggregation, this is used for
-                    # algorithm configuration (incremental updates are used to save time as getting the
-                    # cost for > 100 instances is high)
-                    self.incremental_update_cost(self.ids_config[k.config_id], v.cost)
-                else:
-                    # this is when budget > 0 (only successive halving and hyperband so far)
-                    self.update_cost(config=self.ids_config[k.config_id])
-                    if k.budget > 0:
-                        if self.num_runs_per_config[k.config_id] != 1:  # This is updated in update_cost
-                            raise ValueError("This should not happen!")
+                # this is when budget > 0 (only successive halving and hyperband so far)
+                self.update_cost(config=self.ids_config[k.config_id])
+                if k.budget > 0:
+                    if self.num_runs_per_config[k.config_id] != 1:  # This is updated in update_cost
+                        raise ValueError("This should not happen!")
+
+    def _cost(
+        self,
+        config: Configuration,
+        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
+    ) -> list[list[float] | list[list[float]]]:
+        """Returns a list of all costs for the given config for further calculations.
+        The costs are directly taken from the runhistory data.
+
+        Parameters
+        ----------
+        config : Configuration
+            Configuration to calculate objective for.
+        instance_seed_budget_keys : list, optional (default=None)
+            List of tuples of instance-seeds-budget keys. If None, the run_history is
+            queried for all runs of the given configuration.
+
+        Returns
+        -------
+        Costs: list[list[float] | list[list[float]]]
+            List of all found costs. In case of multi-objective, the list contains lists.
+        """
+        try:
+            id_ = self.config_ids[config]
+        except KeyError:  # challenger was not running so far
+            return []
+
+        if instance_seed_budget_keys is None:
+            instance_seed_budget_keys = self.get_runs_for_config(config, only_max_observed_budget=True)
+
+        costs = []
+        for i, r, b in instance_seed_budget_keys:
+            k = RunKey(id_, i, r, b)
+            costs.append(self.data[k].cost)
+
+        return costs
+
+    def add(
+        self,
+        config: Configuration,
+        cost: Union[int, float, list, np.ndarray],
+        time: float,
+        status: StatusType,
+        instance_id: Optional[str] = None,
+        seed: Optional[int] = None,
+        budget: float = 0.0,
+        starttime: float = 0.0,
+        endtime: float = 0.0,
+        additional_info: Optional[Dict] = None,
+        origin: DataOrigin = DataOrigin.INTERNAL,
+        force_update: bool = False,
+    ) -> None:
+        """Adds a data of a new target algorithm (TA) run; it will update data if the same key
+        values are used (config, instance_id, seed)
+
+        Parameters
+        ----------
+        config : dict (or other type -- depending on config space module)
+            Parameter configuration
+        cost: Union[int, float, list, np.ndarray]
+            Cost of TA run (will be minimized)
+        time: float
+            Runtime of TA run
+        status: str
+            Status in {SUCCESS, TIMEOUT, CRASHED, ABORT, MEMOUT}
+        instance_id: str
+            String representing an instance (default: None)
+        seed: int
+            Random seed used by TA (default: None)
+        budget: float
+            budget (cutoff) used in intensifier to limit TA (default: 0)
+        starttime: float
+            starting timestamp of TA evaluation
+        endtime: float
+            ending timestamp of TA evaluation
+        additional_info: dict
+            Additional run infos (could include further returned
+            information from TA or fields such as start time and host_id)
+        origin: DataOrigin
+            Defines how data will be used.
+        force_update: bool (default: False)
+            Forces the addition of a config to the history
+        """
+        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)
+            )
+
+        # Squeeze is important to reduce arrays with one element
+        # to scalars.
+        cost_array = np.asarray(cost).squeeze()
+        num_obj = np.size(cost_array)
+
+        # Get the config id
+        config_id_tmp = self.config_ids.get(config)
+        if config_id_tmp is None:
+            self._n_id += 1
+            self.config_ids[config] = self._n_id
+            config_id = cast(int, self.config_ids.get(config))
+            self.ids_config[self._n_id] = config
+        else:
+            config_id = cast(int, config_id_tmp)
+
+        if self.num_obj == -1:
+            self.num_obj = num_obj
+        elif self.num_obj != num_obj:
+            raise ValueError(
+                f"Cost is not of the same length ({num_obj}) as the number " f"of objectives ({self.num_obj})"
+            )
+
+        # Let's always work with floats; Makes it easier to deal with later on
+        # array.tolist() returns a scalar if the array has one element.
+        c = cost_array.tolist()
+        if self.num_obj == 1:
+            c = float(c)
+        else:
+            c = [float(i) for i in c]
+
+        k = RunKey(config_id, instance_id, seed, budget)
+        v = RunValue(c, time, status, starttime, endtime, additional_info)
+
+        # Construct keys and values for the data dictionary
+        for key, value in (
+            ("config", config.get_dictionary()),
+            ("config_id", config_id),
+            ("instance_id", instance_id),
+            ("seed", seed),
+            ("budget", budget),
+            ("cost", c),
+            ("time", time),
+            ("status", status),
+            ("starttime", starttime),
+            ("endtime", endtime),
+            ("additional_info", additional_info),
+            ("origin", config.origin),
+        ):
+            self._check_json_serializable(key, value, EnumEncoder, k, v)
+
+        # Each runkey is supposed to be used only once. Repeated tries to add
+        # the same runkey will be ignored silently if not capped.
+        if self.overwrite_existing_runs or force_update or self.data.get(k) is None:
+            self._add(k, v, status, origin)
+        elif status != StatusType.CAPPED and self.data[k].status == StatusType.CAPPED:
+            # overwrite capped runs with uncapped runs
+            self._add(k, v, status, origin)
+        elif status == StatusType.CAPPED and self.data[k].status == StatusType.CAPPED:
+            if self.num_obj > 1:
+                raise RuntimeError("Not supported yet.")
+
+            # Overwrite if censored with a larger cutoff
+            if cost > self.data[k].cost:
+                self._add(k, v, status, origin)
+        else:
+            logger.info("Entry was not added to the runhistory because existing runs will not overwritten.")
 
     def update_cost(self, config: Configuration) -> None:
         """Stores the performance of a configuration across the instances in self.cost_per_config
@@ -417,7 +495,8 @@ class RunHistory(Mapping[RunKey, RunValue]):
             configuration to update cost based on all runs in runhistory
         """
         config_id = self.config_ids[config]
-        # removing duplicates while keeping the order
+
+        # Removing duplicates while keeping the order
         inst_seed_budgets = list(dict.fromkeys(self.get_runs_for_config(config, only_max_observed_budget=True)))
         self._cost_per_config[config_id] = self.average_cost(config, inst_seed_budgets)
         self.num_runs_per_config[config_id] = len(inst_seed_budgets)
@@ -425,11 +504,6 @@ class RunHistory(Mapping[RunKey, RunValue]):
         all_inst_seed_budgets = list(dict.fromkeys(self.get_runs_for_config(config, only_max_observed_budget=False)))
         self._min_cost_per_config[config_id] = self.min_cost(config, all_inst_seed_budgets)
 
-    def update_all_costs(self) -> None:
-        """Update all costs in the runhistory."""
-        for config in self.ids_config.values():
-            self.update_cost(config)
-
     def incremental_update_cost(self, config: Configuration, cost: Union[np.ndarray, list, float, int]) -> None:
         """Incrementally updates the performance of a configuration by using a moving average.
 
@@ -442,12 +516,18 @@ class RunHistory(Mapping[RunKey, RunValue]):
         """
         config_id = self.config_ids[config]
         n_runs = self.num_runs_per_config.get(config_id, 0)
-        old_cost = self._cost_per_config.get(config_id, 0.0)
 
         if self.num_obj > 1:
-            cost = self.average_cost(config)
+            costs = np.array(cost)
+            old_costs = self._cost_per_config.get(config_id, np.array([0.0 for _ in range(self.num_obj)]))
+            old_costs = np.array(old_costs)
+
+            new_costs = ((old_costs * n_runs) + costs) / (n_runs + 1)  # type: ignore
+            self._cost_per_config[config_id] = new_costs.tolist()
+        else:
+            old_cost = self._cost_per_config.get(config_id, 0.0)
+            self._cost_per_config[config_id] = ((old_cost * n_runs) + cost) / (n_runs + 1)  # type: ignore
 
-        self._cost_per_config[config_id] = ((old_cost * n_runs) + cost) / (n_runs + 1)  # type: ignore
         self.num_runs_per_config[config_id] = n_runs + 1
 
     def get_cost(self, config: Configuration) -> float:
@@ -464,96 +544,290 @@ class RunHistory(Mapping[RunKey, RunValue]):
             Computed cost for configuration
         """
         config_id = self.config_ids.get(config)
-        return self._cost_per_config.get(config_id, np.nan)  # type: ignore[arg-type] # noqa F821
 
-    def get_runs_for_config(self, config: Configuration, only_max_observed_budget: bool) -> List[InstSeedBudgetKey]:
-        """Return all runs (instance seed pairs) for a configuration.
+        # Cost is always a single value (Single objective) or a list of values (Multi-objective)
+        # For example, _cost_per_config always holds the value on the highest budget
+        cost = self._cost_per_config.get(config_id, np.nan)  # type: ignore[arg-type] # noqa F821
 
-        Note
-        ----
-        This method ignores capped runs.
+        if self.num_obj > 1:
+            assert type(cost) == list
+            # We have to normalize the costs here
+            costs = normalize_costs(cost, self.objective_bounds)
+            return float(np.mean(costs))
+
+        assert type(cost) == float
+        return float(cost)
+
+    def get_min_cost(self, config: Configuration) -> float:
+        """Returns the lowest empirical cost for a configuration, across all runs (budgets)
+
+        See the class docstring for how the costs are computed. The costs are not re-computed,
+        but are read from cache.
 
         Parameters
         ----------
-        config : Configuration from ConfigSpace
-            Parameter configuration
-        only_max_observed_budget : bool
-            Select only the maximally observed budget run for this configuration
+        config: Configuration
+
         Returns
         -------
-        instance_seed_budget_pairs : list<tuples of instance, seed, budget>
+        min_cost: float
+            Computed cost for configuration
         """
         config_id = self.config_ids.get(config)
-        runs = self._configid_to_inst_seed_budget.get(config_id, {}).copy()  # type: ignore[arg-type] # noqa F821
-
-        # select only the max budget run if specified
-        if only_max_observed_budget:
-            for k, v in runs.items():
-                runs[k] = [max(v)]
+        cost = self._min_cost_per_config.get(config_id, np.nan)  # type: ignore[arg-type] # noqa F821
 
-        # convert to inst-seed-budget key
-        rval = [InstSeedBudgetKey(k.instance, k.seed, budget) for k, v in runs.items() for budget in v]
-        return rval
+        if self.num_obj > 1:
+            assert type(cost) == list
+            costs = normalize_costs(cost, self.objective_bounds)
 
-    def get_all_configs(self) -> List[Configuration]:
-        """Return all configurations in this RunHistory object.
+            # Note: We have to mean here because we already got the min cost
+            return float(np.mean(costs))
 
-        Returns
-        -------
-            parameter configurations: list
-        """
-        return list(self.config_ids.keys())
+        assert type(cost) == float
+        return float(cost)
 
-    def get_all_configs_per_budget(
+    def average_cost(
         self,
-        budget_subset: Optional[List] = None,
-    ) -> List[Configuration]:
-        """Return all configs in this RunHistory object that have been run on one of these budgets.
+        config: Configuration,
+        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
+        normalize: bool = False,
+    ) -> float | list[float]:
+        """Return the average cost of a configuration. This is the mean of costs of all instance-
+        seed pairs.
 
         Parameters
         ----------
-            budget_subset: list
-
+        config : Configuration
+            Configuration to calculate objective for.
+        instance_seed_budget_keys : list, optional (default=None)
+            List of tuples of instance-seeds-budget keys. If None, the run_history is
+            queried for all runs of the given configuration.
+        normalize : bool, optional (default=False)
+            Normalizes the costs wrt objective bounds in the multi-objective setting.
+            Only a float is returned if normalize is True. Warning: The value can change
+            over time because the objective bounds are changing.
+
         Returns
         -------
-            parameter configurations: list
+        Cost: float | list[float]
+            Average cost. In case of multiple objectives, the mean of each objective is returned.
         """
-        if budget_subset is None:
-            return self.get_all_configs()
-        configs = []
-        for c, i, s, b in self.data.keys():
-            if b in budget_subset:
-                configs.append(self.ids_config[c])
-        return configs
+        costs = self._cost(config, instance_seed_budget_keys)
+        if costs:
+            if self.num_obj > 1:
+                # Each objective is averaged separately
+                # [[100, 200], [0, 0]] -> [50, 100]
+                averaged_costs = np.mean(costs, axis=0).tolist()
 
-    def get_min_cost(self, config: Configuration) -> float:
-        """Returns the lowest empirical cost for a configuration, across all runs (budgets)
+                if normalize:
+                    normalized_costs = normalize_costs(averaged_costs, self.objective_bounds)
+                    return float(np.mean(normalized_costs))
+                else:
+                    return averaged_costs
 
-        See the class docstring for how the costs are computed. The costs are not re-computed,
-        but are read from cache.
+            return float(np.mean(costs))
+
+        return np.nan
+
+    def sum_cost(
+        self,
+        config: Configuration,
+        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
+        normalize: bool = False,
+    ) -> float | list[float]:
+        """Return the sum of costs of a configuration. This is the sum of costs of all instance-seed
+        pairs.
 
         Parameters
         ----------
-        config: Configuration
+        config : Configuration
+            Configuration to calculate objective for.
+        instance_seed_budget_keys : list, optional (default=None)
+            List of tuples of instance-seeds-budget keys. If None, the run_history is
+            queried for all runs of the given configuration.
+        normalize : bool, optional (default=False)
+            Normalizes the costs wrt objective bounds in the multi-objective setting.
+            Only a float is returned if normalize is True. Warning: The value can change
+            over time because the objective bounds are changing.
 
         Returns
         -------
-        min_cost: float
-            Computed cost for configuration
+        sum_cost: float | list[float]
+            Sum of costs of config. In case of multiple objectives, the costs are summed up for each
+            objective individually.
+        """
+        costs = self._cost(config, instance_seed_budget_keys)
+        if costs:
+            if self.num_obj > 1:
+                # Each objective is summed separately
+                # [[100, 200], [20, 10]] -> [120, 210]
+                summed_costs = np.sum(costs, axis=0).tolist()
+
+                if normalize:
+                    normalized_costs = normalize_costs(summed_costs, self.objective_bounds)
+                    return float(np.mean(normalized_costs))
+                else:
+                    return summed_costs
+
+        return float(np.sum(costs))
+
+    def min_cost(
+        self,
+        config: Configuration,
+        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
+        normalize: bool = False,
+    ) -> float | list[float]:
+        """Return the minimum cost of a configuration.
+
+        This is the minimum cost of all instance-seed pairs.
+
+        Warning
+        -------
+        In the case of multi-fidelity, the minimum cost per objectives is returned.
+
+        Parameters
+        ----------
+        config : Configuration
+            Configuration to calculate objective for.
+        instance_seed_budget_keys : list, optional (default=None)
+            List of tuples of instance-seeds-budget keys. If None, the run_history is
+            queried for all runs of the given configuration.
+
+        Returns
+        -------
+        min_cost: float | list[float]
+            Minimum cost of the config. In case of multi-objective, the minimum cost per objective
+            is returned.
+        """
+        costs = self._cost(config, instance_seed_budget_keys)
+        if costs:
+            if self.num_obj > 1:
+                # Each objective is viewed separately
+                # [[100, 200], [20, 500]] -> [20, 200]
+                min_costs = np.min(costs, axis=0).tolist()
+
+                if normalize:
+                    normalized_costs = normalize_costs(min_costs, self.objective_bounds)
+                    return float(np.mean(normalized_costs))
+                else:
+                    return min_costs
+
+            return float(np.min(costs))
+
+        return np.nan
+
+    def compute_all_costs(self, instances: Optional[List[str]] = None) -> None:
+        """Computes the cost of all configurations from scratch and overwrites self.cost_perf_config
+        and self.runs_per_config accordingly.
+
+        Note
+        ----
+        This method is only used for ``merge_foreign_data`` and should be removed.
+
+        Parameters
+        ----------
+        instances: List[str]
+            List of instances; if given, cost is only computed wrt to this instance set.
+        """
+        self._cost_per_config = {}
+        self.num_runs_per_config = {}
+        for config, config_id in self.config_ids.items():
+            # removing duplicates while keeping the order
+            inst_seed_budgets = list(dict.fromkeys(self.get_runs_for_config(config, only_max_observed_budget=True)))
+            if instances is not None:
+                inst_seed_budgets = list(filter(lambda x: x.instance in cast(List, instances), inst_seed_budgets))
+
+            if inst_seed_budgets:  # can be empty if never saw any runs on <instances>
+                self._cost_per_config[config_id] = self.average_cost(config, inst_seed_budgets)
+                self._min_cost_per_config[config_id] = self.min_cost(config, inst_seed_budgets)
+                self.num_runs_per_config[config_id] = len(inst_seed_budgets)
+
+    def get_instance_costs_for_config(self, config: Configuration) -> Dict[str, List[float]]:
+        """Returns the average cost per instance (across seeds) for a configuration. If the
+        runhistory contains budgets, only the highest budget for a configuration is returned.
+
+        Note
+        ----
+        This is used by the pSMAC facade to determine the incumbent after the evaluation.
+
+        Parameters
+        ----------
+        config : Configuration from ConfigSpace
+            Parameter configuration
+
+        Returns
+        -------
+        cost_per_inst: Dict<instance name<str>, cost<float>>
+        """
+        runs_ = self.get_runs_for_config(config, only_max_observed_budget=True)
+        cost_per_inst = {}  # type: Dict[str, List[float]]
+        for inst, seed, budget in runs_:
+            cost_per_inst[inst] = cost_per_inst.get(inst, [])
+            rkey = RunKey(self.config_ids[config], inst, seed, budget)
+            vkey = self.data[rkey]
+            cost_per_inst[inst].append(vkey.cost)
+        cost_per_inst = dict([(inst, np.mean(costs)) for inst, costs in cost_per_inst.items()])
+        return cost_per_inst
+
+    def get_runs_for_config(self, config: Configuration, only_max_observed_budget: bool) -> List[InstSeedBudgetKey]:
+        """Return all runs (instance seed pairs) for a configuration.
+
+        Note
+        ----
+        This method ignores capped runs.
+
+        Parameters
+        ----------
+        config : Configuration from ConfigSpace
+            Parameter configuration
+        only_max_observed_budget : bool
+            Select only the maximally observed budget run for this configuration
+        Returns
+        -------
+        instance_seed_budget_pairs : list<tuples of instance, seed, budget>
         """
         config_id = self.config_ids.get(config)
-        return self._min_cost_per_config.get(config_id, np.nan)  # type: ignore[arg-type] # noqa F821
+        runs = self._configid_to_inst_seed_budget.get(config_id, {}).copy()  # type: ignore[arg-type] # noqa F821
 
-    def empty(self) -> bool:
-        """Check whether or not the RunHistory is empty.
+        # select only the max budget run if specified
+        if only_max_observed_budget:
+            for k, v in runs.items():
+                runs[k] = [max(v)]
+
+        # convert to inst-seed-budget key
+        rval = [InstSeedBudgetKey(k.instance, k.seed, budget) for k, v in runs.items() for budget in v]
+        return rval
+
+    def get_all_configs(self) -> List[Configuration]:
+        """Return all configurations in this RunHistory object.
 
         Returns
         -------
-        emptiness: bool
-            True if runs have been added to the RunHistory,
-            False otherwise
+            parameter configurations: list
         """
-        return len(self.data) == 0
+        return list(self.config_ids.keys())
+
+    def get_all_configs_per_budget(
+        self,
+        budget_subset: Optional[List] = None,
+    ) -> List[Configuration]:
+        """Return all configs in this RunHistory object that have been run on one of these budgets.
+
+        Parameters
+        ----------
+            budget_subset: list
+
+        Returns
+        -------
+            parameter configurations: list
+        """
+        if budget_subset is None:
+            return self.get_all_configs()
+        configs = []
+        for c, i, s, b in self.data.keys():
+            if b in budget_subset:
+                configs.append(self.ids_config[c])
+        return configs
 
     def save_json(self, fn: str = "runhistory.json", save_external: bool = False) -> None:
         """Saves runhistory on disk.
@@ -716,205 +990,3 @@ class RunHistory(Mapping[RunKey, RunValue]):
                 additional_info=additional_info,
                 origin=origin,
             )
-
-    def _cost(
-        self,
-        config: Configuration,
-        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
-    ) -> List[np.ndarray]:
-        """Return array of all costs for the given config for further calculations.
-
-        Parameters
-        ----------
-        config : Configuration
-            Configuration to calculate objective for.
-        instance_seed_budget_keys : list, optional (default=None)
-            List of tuples of instance-seeds-budget keys. If None, the run_history is
-            queried for all runs of the given configuration.
-
-        Returns
-        -------
-        Costs: list
-            Array of all costs.
-        """
-        try:
-            id_ = self.config_ids[config]
-        except KeyError:  # challenger was not running so far
-            return []
-
-        if instance_seed_budget_keys is None:
-            instance_seed_budget_keys = self.get_runs_for_config(config, only_max_observed_budget=True)
-
-        costs = []
-        for i, r, b in instance_seed_budget_keys:
-            k = RunKey(id_, i, r, b)
-            costs.append(self.data[k].cost)
-
-        return costs
-
-    def average_cost(
-        self,
-        config: Configuration,
-        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
-    ) -> float:
-        """Return the average cost of a configuration. This is the mean of costs of all instance-
-        seed pairs.
-
-        Parameters
-        ----------
-        config : Configuration
-            Configuration to calculate objective for.
-        instance_seed_budget_keys : list, optional (default=None)
-            List of tuples of instance-seeds-budget keys. If None, the run_history is
-            queried for all runs of the given configuration.
-
-        Returns
-        -------
-        Cost: float
-            Average cost
-        """
-        costs = self._cost(config, instance_seed_budget_keys)
-        if costs:
-            if self.num_obj > 1:
-                # Normalize costs
-                costs = normalize_costs(costs, self.objective_bounds)  # type: ignore[assignment]
-
-            return float(np.mean(costs))
-
-        return np.nan
-
-    def sum_cost(
-        self,
-        config: Configuration,
-        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
-    ) -> float:
-        """Return the sum of costs of a configuration. This is the sum of costs of all instance-seed
-        pairs.
-
-        Parameters
-        ----------
-        config : Configuration
-            Configuration to calculate objective for.
-        instance_seed_budget_keys : list, optional (default=None)
-            List of tuples of instance-seeds-budget keys. If None, the run_history is
-            queried for all runs of the given configuration.
-
-        Returns
-        -------
-        sum_cost: float
-            Sum of costs of config.
-        """
-        costs = self._cost(config, instance_seed_budget_keys)
-        if costs:
-            if self.num_obj > 1:
-                # Normalize costs
-                costs = normalize_costs(costs, self.objective_bounds)  # type: ignore[assignment]
-                costs = np.mean(costs, axis=1)
-
-        return float(np.sum(costs))
-
-    def min_cost(
-        self,
-        config: Configuration,
-        instance_seed_budget_keys: Optional[Iterable[InstSeedBudgetKey]] = None,
-    ) -> float:
-        """Return the minimum cost of a configuration.
-
-        This is the minimum cost of all instance-seed pairs.
-        Warning: In the case of multi-fidelity, the minimum cost per objectives is returned.
-
-        Parameters
-        ----------
-        config : Configuration
-            Configuration to calculate objective for.
-        instance_seed_budget_keys : list, optional (default=None)
-            List of tuples of instance-seeds-budget keys. If None, the run_history is
-            queried for all runs of the given configuration.
-
-        Returns
-        -------
-        min_cost: float
-            minimum cost of config.
-        """
-        costs = self._cost(config, instance_seed_budget_keys)
-        if costs:
-            if self.num_obj > 1:
-                # Normalize costs
-                costs = normalize_costs(costs, self.objective_bounds)  # type: ignore[assignment]
-                costs = np.mean(costs, axis=1)
-
-            return float(np.min(costs))
-
-        return np.nan
-
-    def compute_all_costs(self, instances: Optional[List[str]] = None) -> None:
-        """Computes the cost of all configurations from scratch and overwrites self.cost_perf_config
-        and self.runs_per_config accordingly.
-
-        Note
-        ----
-        This method is only used for ``merge_foreign_data`` and should be removed.
-
-        Parameters
-        ----------
-        instances: List[str]
-            List of instances; if given, cost is only computed wrt to this instance set.
-        """
-        self._cost_per_config = {}
-        self.num_runs_per_config = {}
-        for config, config_id in self.config_ids.items():
-            # removing duplicates while keeping the order
-            inst_seed_budgets = list(dict.fromkeys(self.get_runs_for_config(config, only_max_observed_budget=True)))
-            if instances is not None:
-                inst_seed_budgets = list(filter(lambda x: x.instance in cast(List, instances), inst_seed_budgets))
-
-            if inst_seed_budgets:  # can be empty if never saw any runs on <instances>
-                self._cost_per_config[config_id] = self.average_cost(config, inst_seed_budgets)
-                self._min_cost_per_config[config_id] = self.min_cost(config, inst_seed_budgets)
-                self.num_runs_per_config[config_id] = len(inst_seed_budgets)
-
-    def get_instance_costs_for_config(self, config: Configuration) -> Dict[str, List[float]]:
-        """Returns the average cost per instance (across seeds) for a configuration. If the
-        runhistory contains budgets, only the highest budget for a configuration is returned.
-
-        Note
-        ----
-        This is used by the pSMAC facade to determine the incumbent after the evaluation.
-
-        Parameters
-        ----------
-        config : Configuration from ConfigSpace
-            Parameter configuration
-
-        Returns
-        -------
-        cost_per_inst: Dict<instance name<str>, cost<float>>
-        """
-        runs_ = self.get_runs_for_config(config, only_max_observed_budget=True)
-        cost_per_inst = {}  # type: Dict[str, List[float]]
-        for inst, seed, budget in runs_:
-            cost_per_inst[inst] = cost_per_inst.get(inst, [])
-            rkey = RunKey(self.config_ids[config], inst, seed, budget)
-            vkey = self.data[rkey]
-            cost_per_inst[inst].append(vkey.cost)
-        cost_per_inst = dict([(inst, np.mean(costs)) for inst, costs in cost_per_inst.items()])
-        return cost_per_inst
-
-    def __contains__(self, k: object) -> bool:
-        """Dictionary semantics for `k in runhistory`"""
-        return k in self.data
-
-    def __getitem__(self, k: RunKey) -> RunValue:
-        """Dictionary semantics for `v = runhistory[k]`"""
-        return self.data[k]
-
-    def __iter__(self) -> Iterator[RunKey]:
-        """Dictionary semantics for `for k in runhistory.keys()`, enables.
-
-        .items()
-        """
-        return iter(self.data.keys())
-
-    def __len__(self) -> int:
-        """Enables the `len(runhistory)`"""
-        return len(self.data)
diff --git a/smac/runhistory/runhistory2epm.py b/smac/runhistory/runhistory2epm.py
index 10c72cf48..88178055b 100644
--- a/smac/runhistory/runhistory2epm.py
+++ b/smac/runhistory/runhistory2epm.py
@@ -473,7 +473,7 @@ class RunHistory2EPM4Cost(AbstractRunHistory2EPM):
 
                 # Let's normalize y here
                 # We use the objective_bounds calculated by the runhistory
-                y_ = normalize_costs([run.cost], runhistory.objective_bounds)
+                y_ = normalize_costs(run.cost, runhistory.objective_bounds)
                 y_agg = self.multi_objective_algorithm(y_)
                 y[row] = y_agg
             else:
@@ -489,7 +489,6 @@ class RunHistory2EPM4Cost(AbstractRunHistory2EPM):
                 self.max_y = np.max(y, axis=0)
 
         y = self.transform_response_values(values=y)
-
         return X, y
 
     def transform_response_values(self, values: np.ndarray) -> np.ndarray:
@@ -698,7 +697,7 @@ class RunHistory2EPM4EIPS(AbstractRunHistory2EPM):
 
                 # Let's normalize y here
                 # We use the objective_bounds calculated by the runhistory
-                y_ = normalize_costs([run.cost], runhistory.objective_bounds)
+                y_ = normalize_costs(run.cost, runhistory.objective_bounds)
                 y_agg = self.multi_objective_algorithm(y_)
                 y[row, 0] = y_agg
             else:
diff --git a/smac/utils/multi_objective.py b/smac/utils/multi_objective.py
index 9a5f7f7b5..a88eb397f 100644
--- a/smac/utils/multi_objective.py
+++ b/smac/utils/multi_objective.py
@@ -1,66 +1,40 @@
-from typing import List, Optional, Tuple, Union
+from __future__ import annotations
 
-import numpy as np
 
-
-def normalize_costs(
-    values: Union[np.ndarray, List, List[List], List[np.ndarray]],
-    bounds: Optional[List[Tuple[float, float]]] = None,
-) -> np.ndarray:
-    """Normalizes the costs to be between 0 and 1 if no bounds are given. Otherwise, the costs are
-    normalized according to the bounds.
-
-    Example
-    -------
-
-    [0, 10, 5] -> [[0], [1], [0.5]]
-    [[0], [10], [5]] -> [[0], [1], [0.5]]
-    [[0, 0], [10, 50], [5, 200]] -> [[0, 0], [1, 0.25], [0.5, 1]]
+def normalize_costs(values: list[float], bounds: list[tuple[float, float]] | None = None) -> list[float]:
+    """
+    Normalizes a list of floats with corresponding bounds.
 
     Parameters
     ----------
-    values : Union[np.ndarray, List, List[List]]
-        Cost values which should be normalized.
-        If array/list is one-dimensional, it is expanded by one dimension.
-    bounds : Optional[List[Tuple[float, float]]], optional
-        Min and max bounds which should be applied to the values, by default None.
-        If bounds are None the min and max values from the data are used.
+    values : list[float]
+        List of costs to be normalized.
+    bounds : list[tuple[float, float]] | None, optional
+        List of tuple of bounds. By default None. If no bounds are passed, the values are returned
+        unnormalized.
 
     Returns
     -------
-    np.ndarray
-        Normalized costs.
+    normalized_costs : list[float]
+        Normalized costs based on the bounds. If no bounds are given, the values are returned unnormalized.
+        Also, if min and max bounds are the same, the value of the corresponding objective is set to 1.
     """
-    _values: np.ndarray
-    if isinstance(values, list):
-        _values = np.array(values)
-    else:
-        _values = values
+    if bounds is None:
+        return values
 
-    if len(_values.shape) == 1:
-        _values = np.expand_dims(_values, axis=-1)
-
-    normalized_values = []
-    for col in range(_values.shape[1]):
-        data = _values[:, col].astype(float)
-
-        if bounds is not None:
-            assert len(bounds) == _values.shape[1]
-
-            min_value = bounds[col][0]
-            max_value = bounds[col][1]
-        else:
-            min_value = np.min(data)
-            max_value = np.max(data)
+    if len(values) != len(bounds):
+        raise ValueError("Number of values and bounds must be equal.")
 
-        denominator = max_value - min_value
+    costs = []
+    for v, b in zip(values, bounds):
+        assert type(v) != list
+        p = v - b[0]
+        q = b[1] - b[0]
 
-        # Prevent divide by zero
-        if denominator < 1e-10:
-            # Return ones
-            normalized_values.append(np.ones_like(data))
+        if q < 1e-10:
+            cost = 1.0
         else:
-            numerator = data - min_value
-            normalized_values.append(numerator / denominator)
+            cost = p / q
+        costs += [cost]
 
-    return np.swapaxes(np.array(normalized_values), 0, 1)
+    return costs


Test patch:
diff --git a/tests/test_multi_objective/test_schaffer.py b/tests/test_multi_objective/test_schaffer.py
index cffa8fddd..fb3630892 100644
--- a/tests/test_multi_objective/test_schaffer.py
+++ b/tests/test_multi_objective/test_schaffer.py
@@ -42,9 +42,13 @@ def get_optimum():
 
 def plot(all_x):
     plt.figure()
+
     for x in all_x:
         f1, f2 = schaffer(x)
-        plt.scatter(f1, f2, c="blue", alpha=0.1)
+        plt.scatter(f1, f2, c="blue", alpha=0.2, zorder=3000)
+
+    plt.vlines([1], 0, 4, linestyles="dashed", colors=["red"])
+    plt.hlines([1], 0, 4, linestyles="dashed", colors=["red"])
 
     plt.show()
 
@@ -73,7 +77,7 @@ class SchafferTest(unittest.TestCase):
         self.scenario = Scenario(
             {
                 "run_obj": "quality",  # we optimize quality (alternatively runtime)
-                "runcount-limit": 20,  # max. number of function evaluations
+                "runcount-limit": 25,  # max. number of function evaluations
                 "cs": self.cs,  # configuration space
                 "deterministic": True,
                 "multi_objectives": "metric1, metric2",
@@ -104,11 +108,12 @@ class SchafferTest(unittest.TestCase):
 
                 f1_inc, f2_inc = schaffer(incumbent["x"])
                 f1_opt, f2_opt = get_optimum()
+
                 inc = f1_inc + f2_inc
                 opt = f1_opt + f2_opt
                 diff = abs(inc - opt)
 
-                assert diff < 0.1
+                assert diff < 0.5
                 results.append(smac)
 
         return results
diff --git a/tests/test_runhistory/test_runhistory_multi_objective.py b/tests/test_runhistory/test_runhistory_multi_objective.py
index e21c5f2bc..3ef3a84a7 100644
--- a/tests/test_runhistory/test_runhistory_multi_objective.py
+++ b/tests/test_runhistory/test_runhistory_multi_objective.py
@@ -148,8 +148,6 @@ class RunhistoryMultiObjectiveTest(unittest.TestCase):
             status=StatusType.SUCCESS,
         )
 
-        print(rh._cost_per_config)
-
         # Only one value: Normalization goes to 1.0
         self.assertEqual(rh.get_cost(config1), 1.0)
 
@@ -550,8 +548,8 @@ class RunhistoryMultiObjectiveTest(unittest.TestCase):
         self.assertEqual(rh.objective_bounds[1], (10, 30))
 
         # Average cost returns us the cost of the latest budget
-        self.assertEqual(rh.average_cost(config1), 0.375)
-        self.assertEqual(rh.average_cost(config2), 0.75)
+        self.assertEqual(rh.get_cost(config1), 0.375)
+        self.assertEqual(rh.get_cost(config2), 0.75)
 
     def test_budgets(self):
         rh = RunHistory()
@@ -582,8 +580,8 @@ class RunhistoryMultiObjectiveTest(unittest.TestCase):
         # SMAC does not overwrite by default
         rh.add(
             config=config1,
-            cost=[50, 100],
-            time=10,
+            cost=[502342352, 23425234],
+            time=11,
             status=StatusType.SUCCESS,
             instance_id=1,
             seed=1,
@@ -604,9 +602,13 @@ class RunhistoryMultiObjectiveTest(unittest.TestCase):
         self.assertEqual(rh.objective_bounds[1], (50, 150))
 
         # Average cost returns us the cost of the latest budget
-        self.assertEqual(rh.average_cost(config1), 0.75)
-        self.assertEqual(rh.average_cost(config2), 0.5)
+        self.assertEqual(rh.get_cost(config1), 0.75)
+        self.assertEqual(rh.average_cost(config1), [40.0, 100.0])
+
+        self.assertEqual(rh.get_cost(config2), 0.5)
+        self.assertEqual(rh.average_cost(config2), [0, 150])
 
 
 if __name__ == "__main__":
     t = RunhistoryMultiObjectiveTest()
+    t.test_budgets()
diff --git a/tests/test_utils/test_multi_objective.py b/tests/test_utils/test_multi_objective.py
index 069901970..2300a2e02 100644
--- a/tests/test_utils/test_multi_objective.py
+++ b/tests/test_utils/test_multi_objective.py
@@ -1,6 +1,8 @@
 import unittest
+from multiprocessing.sharedctypes import Value
 
 import numpy as np
+import pytest
 
 from smac.utils.multi_objective import normalize_costs
 
@@ -10,61 +12,34 @@ __license__ = "3-clause BSD"
 
 class MultiObjectiveTest(unittest.TestCase):
     def setUp(self):
-        self.bounds_1d = [(0, 1)]
-        self.bounds_2d = [(0, 1), (50, 100)]
+        self.bounds = [(0, 50), (50, 100)]
+        self.bounds_invalid = [(0, 0), (5, 5)]
 
     def test_normalize_costs(self):
-        # Normalize between 0..1 given data only
-        v = np.array([[5, 2], [10, 0]])
+        # If no bounds are passed, we get the same result back
+        v = [5, 2]
         nv = normalize_costs(v)
-        self.assertEqual(list(nv.flatten()), list(np.array([[0, 1], [1, 0]]).flatten()))
+        self.assertEqual(nv, [5, 2])
 
         # Normalize between 0..1 given data only
-        v = np.array([[5, 75], [0.5, 50], [0.75, 60], [0, 100]])
-        nv = normalize_costs(v, self.bounds_2d)
-
-        self.assertEqual(
-            list(nv.flatten()),
-            list(np.array([[5, 0.5], [0.5, 0], [0.75, 0.2], [0, 1]]).flatten()),
-        )
-
-        # No normalization
-        v = np.array([[5, 2]])
-        nv = normalize_costs(v)
-        self.assertEqual(list(nv.flatten()), list(np.array([[1.0, 1.0]]).flatten()))
-
-        # Normalization with given bounds
-        v = np.array([[500, 150]])
-        nv = normalize_costs(v, self.bounds_2d)
-        self.assertEqual(list(nv.flatten()), list(np.array([[500, 2.0]]).flatten()))
-
-        # Test one-dimensional list
-        v = [500, 150]
-        nv = normalize_costs(v, self.bounds_1d)
-        self.assertEqual(list(nv.flatten()), list(np.array([[500], [150]]).flatten()))
-
-        # Test one-dimensional array without bounds
-        v = np.array([500, 150])
-        nv = normalize_costs(v)
-        self.assertEqual(list(nv.flatten()), list(np.array([[1.0], [0.0]]).flatten()))
-
-        # Test one-dimensional array without bounds
-        v = np.array([1000, 200, 400, 800, 600, 0])
-        nv = normalize_costs(v)
-        self.assertEqual(
-            list(nv.flatten()),
-            list(np.array([[1], [0.2], [0.4], [0.8], [0.6], [0.0]]).flatten()),
-        )
-
-        # Test one-dimensional array with one objective
-        v = np.array([500])
-        nv = normalize_costs(v, self.bounds_1d)
-        self.assertEqual(list(nv.flatten()), list(np.array([[500.0]]).flatten()))
-
-        # Test one-dimensional list with one objective
-        v = [500]
-        nv = normalize_costs(v, self.bounds_1d)
-        self.assertEqual(list(nv.flatten()), list(np.array([[500.0]]).flatten()))
+        v = [25, 50]
+        nv = normalize_costs(v, self.bounds)
+        self.assertEqual(nv, [0.5, 0])
+
+        # Invalid bounds
+        v = [25, 50]
+        nv = normalize_costs(v, self.bounds_invalid)
+        self.assertEqual(nv, [1, 1])
+
+        # Invalid input
+        v = [[25], [50]]
+        with pytest.raises(AssertionError):
+            nv = normalize_costs(v, self.bounds)
+
+        # Wrong shape
+        v = [25, 50, 75]
+        with pytest.raises(ValueError):
+            nv = normalize_costs(v, self.bounds)
 
 
 if __name__ == "__main__":