Repository: Epistimio/orion

Issue:
TPE stuck during suggest()
@mgermain reported 2 cases where TPE apparently got stuck after as few as 30 trials. Last log line was `DEBUG::orion.core.worker.producer::### Algorithm suggests new points.` and nothing else was logged for hours. The search space was small, limited to about 300 points:
```python
{
    'x': 'choices(["vgg16", "mobilenet_v2", "mobilenet_v3_large", "mobilenet_v3_small"])',
    'y': 'loguniform(1e-5, 1e-1, precision=1)'
}
```

Needs to be reproduced and investigated.

Discussion:

Patch:
diff --git a/src/orion/algo/tpe.py b/src/orion/algo/tpe.py
index a2f26526..46d5a0b5 100644
--- a/src/orion/algo/tpe.py
+++ b/src/orion/algo/tpe.py
@@ -142,31 +142,37 @@ class TPE(BaseAlgorithm):
     ----------
     space: `orion.algo.space.Space`
         Optimisation space with priors for each dimension.
-    seed: None, int or sequence of int
+    seed: None, int or sequence of int, optional
         Seed to sample initial points and candidates points.
         Default: ``None``
-    n_initial_points: int
+    n_initial_points: int, optional
         Number of initial points randomly sampled. If new points
         are requested and less than `n_initial_points` are observed,
         the next points will also be sampled randomly instead of being
         sampled from the parzen estimators.
         Default: ``20``
-    n_ei_candidates: int
-        Number of candidates points sampled for ei compute.
+    n_ei_candidates: int, optional
+        Number of candidates points sampled for ei compute. Larger numbers will lead to more
+        exploitation and lower numbers will lead to more exploration. Be carefull with categorical
+        dimension as TPE tend to severily exploit these if n_ei_candidates is larger than 1.
         Default: ``24``
-    gamma: real
-        Ratio to split the observed trials into good and bad distributions.
+    gamma: real, optional
+        Ratio to split the observed trials into good and bad distributions. Lower numbers will
+        load to more exploitation and larger numbers will lead to more exploration.
         Default: ``0.25``
-    equal_weight: bool
+    equal_weight: bool, optional
         True to set equal weights for observed points.
         Default: ``False``
-    prior_weight: int
+    prior_weight: int, optional
         The weight given to the prior point of the input space.
         Default: ``1.0``
-    full_weight_num: int
+    full_weight_num: int, optional
         The number of the most recent trials which get the full weight where the others will be
         applied with a linear ramp from 0 to 1.0. It will only take effect if equal_weight
         is False.
+    max_retry: int, optional
+        Number of attempts to sample new points if the sampled points were already suggested.
+        Default: ``100``
 
     """
 
@@ -185,6 +191,7 @@ class TPE(BaseAlgorithm):
         equal_weight=False,
         prior_weight=1.0,
         full_weight_num=25,
+        max_retry=100,
     ):
 
         if n_initial_points < 2:
@@ -210,6 +217,7 @@ class TPE(BaseAlgorithm):
             equal_weight=equal_weight,
             prior_weight=prior_weight,
             full_weight_num=full_weight_num,
+            max_retry=max_retry,
         )
 
     @property
@@ -303,25 +311,32 @@ class TPE(BaseAlgorithm):
             if not candidates:
                 break
 
-        if samples:
-            return samples
-
-        return None
+        return samples
 
     def _suggest(self, num, function):
         points = []
 
         ids = set(self._trials_info.keys())
-        while len(points) < num:
+        retries = 0
+        while len(points) < num and retries < self.max_retry:
             for candidate in function(num - len(points)):
                 candidate_id = self.get_id(candidate)
                 if candidate_id not in ids:
                     ids.add(candidate_id)
                     points.append(candidate)
+                else:
+                    retries += 1
 
                 if len(ids) >= self.space.cardinality:
                     return points
 
+        if retries >= self.max_retry:
+            logger.warning(
+                f"Algorithm unable to sample `{num}` points with less than "
+                f"`{self.max_retry}` retries. Try adjusting the configuration of TPE "
+                "to favor exploration (`n_ei_candidates` and `gamma` in particular)."
+            )
+
         return points
 
     def _suggest_random(self, num):


Test patch:
diff --git a/tests/functional/algos/test_algos.py b/tests/functional/algos/test_algos.py
index 1b3840d5..cd29bcf2 100644
--- a/tests/functional/algos/test_algos.py
+++ b/tests/functional/algos/test_algos.py
@@ -31,6 +31,7 @@ algorithm_configs = {
             "equal_weight": False,
             "prior_weight": 1.0,
             "full_weight_num": 25,
+            "max_retry": 100,
         }
     },
     "asha": {"asha": {"seed": 1, "num_rungs": 4, "num_brackets": 1, "repetitions": 2}},
diff --git a/tests/unittests/algo/test_tpe.py b/tests/unittests/algo/test_tpe.py
index 56a5aacc..e3cbe8df 100644
--- a/tests/unittests/algo/test_tpe.py
+++ b/tests/unittests/algo/test_tpe.py
@@ -18,7 +18,7 @@ from orion.algo.tpe import (
     ramp_up_weights,
 )
 from orion.core.worker.transformer import build_required_space
-from orion.testing.algo import BaseAlgoTests
+from orion.testing.algo import BaseAlgoTests, phase
 
 
 @pytest.fixture()
@@ -718,6 +718,7 @@ class TestTPE(BaseAlgoTests):
         "equal_weight": True,
         "prior_weight": 0.8,
         "full_weight_num": 10,
+        "max_retry": 100,
     }
 
     def test_suggest_init(self, mocker):
@@ -826,5 +827,29 @@ class TestTPE(BaseAlgoTests):
         assert algo.n_observed == RANGE
         assert algo.n_suggested == RANGE
 
+    @phase
+    def test_stuck_exploiting(self, mocker, num, attr):
+        """Test that algo drops out when exploiting an already explored region."""
+        algo = self.create_algo()
+        spy = self.spy_phase(mocker, 0, algo, "space.sample")
+
+        points = algo.space.sample(1)
+
+        # Mock sampling so that always returns the same point
+        def sample(self, n_samples=1, seed=None):
+            return points
+
+        def _suggest_random(self, num):
+            return self._suggest(num, sample)
+
+        mocker.patch("orion.algo.tpe.TPE._suggest_random", _suggest_random)
+        mocker.patch("orion.algo.tpe.TPE._suggest_bo", _suggest_random)
+
+        with pytest.raises(RuntimeError):
+            self.force_observe(2, algo)
+
+        assert algo.n_observed == 1
+        assert algo.n_suggested == 1
+
 
 TestTPE.set_phases([("random", 0, "space.sample"), ("bo", N_INIT + 1, "_suggest_bo")])