Repository: optuna/optuna
Pull request: Fix bugs in `constant_liar` option
## Motivation
Currently, `constant_liar` option first fills `inf` in the values of running trials and splits them into "below" and "above". An example of 5-concurrent case (with `n_startup_trials = 3`) is given below:

|Event|`constant_liar=False`|`constant_liar=True`|
|------|------|------|
|ask 0|RandomSampler|RandomSampler|
|ask 1|RandomSampler|RandomSampler|
|ask 2|RandomSampler|`B, A = split({0…1}, γ(3))`|
|ask 3|RandomSampler|`B, A = split({0…2}, γ(4))`|
|ask 4|RandomSampler|`B, A = split({0…3}, γ(5))`|
|tell 0, ask 5|RandomSampler|`B, A = split({0…4}, γ(6))`|
|tell 1, ask 6|RandomSampler|`B, A = split({0…5}, γ(7))`|
|tell 2, ask 7|`B, A = split({0…2}, γ(3))`|`B, A = split({0…6}, γ(8))`|
|tell 3, ask 8|`B, A = split({0…3}, γ(4))`|`B, A = split({0…7}, γ(9))`|
|tell 4, ask 9|`B, A = split({0…4}, γ(5))`|`B, A = split({0…8}, γ(10))`|

Here, `B` stands for "below" and `A` stands for "above".

This behavior has the following problems:
* In "ask 2...4" step, no trials have generated results yet. However, if `γ(3)`...`γ(5)` is nonzero, some running trials are randomly chosen to be "below", and subsequent trials will be wrongly attracted toward that trial.
* In "ask 5...6" step, there are only 1 or 2 finished trials, but we choose `γ(6)` or `γ(7)` "below" trials. Since all running trials have value `inf`, the early trials are unconditionally chosen to be "below", no matter how good or bad their actual values are. Again, subsequent trials will be wrongly attracted toward early trials.

In practice, this causes performance deterioration when the number of concurrency is large, such as 50. One example of benchmark is given below, where `HPOBench` is used. (In the below image, "cl" stands for `constant_liar=True`.)

![constant_liar1](https://user-images.githubusercontent.com/24619922/195519525-dd1684d6-235b-44d2-94a3-1c5a40ea75dc.png)

As can be seen from the image, `constant_liar=True` performs worse than `constant_liar=False` until the budget reaches around 150.

## Description of the changes
We change the behavior to be following:

|Event|`constant_liar=False`|`constant_liar=True`|
|------|------|------|
|ask 0|RandomSampler|RandomSampler|
|ask 1|RandomSampler|RandomSampler|
|ask 2|RandomSampler|RandomSampler|
|ask 3|RandomSampler|RandomSampler|
|ask 4|RandomSampler|RandomSampler|
|tell 0, ask 5|RandomSampler|RandomSampler|
|tell 1, ask 6|RandomSampler|RandomSampler|
|tell 2, ask 7|`B, A = split({0…2}, γ(3))`|`B, A = split({0…6}, γ(3))`|
|tell 3, ask 8|`B, A = split({0…3}, γ(4))`|`B, A = split({0…7}, γ(4))`|
|tell 4, ask 9|`B, A = split({0…4}, γ(5))`|`B, A = split({0…8}, γ(5))`|

Note that `B, A = split({0…6}, γ(3))` is equivalent to 
```
B, A' = split({0…2}, γ(3))
A = A' + {3...6}
```
where we first split all finished trials, and then append all running trials to "above".

This improves the performance of HPOBench:
![constant_liar2](https://user-images.githubusercontent.com/24619922/195521193-4a6971c7-d09d-4741-8762-59648e4149f6.png)

One side effect of this change is that running trials will be ranked after pruned trials. (Note that currently running trials are ranked before pruned trials.) 
Another side effect is that it will now be trivial to support `constant_liar` in multi-objective settings.


Problem statement:
Add the specification of the behavior of `n_startup_trials` for `constant_liar` option
The `n_startup_trials`' document says, "The random sampling is used instead of the TPE algorithm until the given number of trials finish in the same study.", but it is inconsistent with ~~`group=True`~~ or `constant_liar=True`. We need to specify the behavior for these options.

Hints from issue discussion:
@not522 do you mind elaborating a bit on what must be discussed given it's labeled `needs-discussion` ?
I notice that `group=True` does not affect the behavior of `n_startup_trials`. 🙇

As far as I know, we do not have a concrete specification of `n_startup_trials` for the `constant_liar` option. We need to discuss the behavior.
The document says, "The random sampling is used instead of the TPE algorithm until the given number of trials finish in the same study."
The current default behavior is to count how many trials involving the interested parameter have been completed.
The behavior with `constant_liar=True` seems to be buggy. `TPESampler` counts `RUNNING` trials as finished.
Ah, thanks for the explanation. Given the documentation, it sounds like bugs but that needs to be fixed. 
But you mean that it may/may not be more intuitive to keep the current behavior with `constant_liar` and update the documentation to clarify this? 🤔 
Maybe we need to fix it, but I'm not sure which one is better. We need to benchmark with the `constant_liar` option.
This issue has not seen any recent activity.

Commit message: fix tests

Patch to review:
diff --git a/optuna/samplers/_tpe/sampler.py b/optuna/samplers/_tpe/sampler.py
index 9635a0eaaf0..461f4e2a50a 100644
--- a/optuna/samplers/_tpe/sampler.py
+++ b/optuna/samplers/_tpe/sampler.py
@@ -392,7 +392,7 @@ def _sample_relative(
         )
 
         # If the number of samples is insufficient, we run random trial.
-        n = len(scores)
+        n = sum(1 for (s, v) in scores if s < float("inf"))  # ignore running trials
         if n < self._n_startup_trials:
             return {}
 
@@ -441,7 +441,7 @@ def sample_independent(
             self._constraints_func is not None,
         )
 
-        n = len(scores)
+        n = sum(1 for (s, v) in scores if s < float("inf"))  # ignore running trials
 
         self._log_independent_sampling(n, trial, param_name)
 
@@ -652,13 +652,13 @@ def _get_observation_pairs(
                 else:
                     score = (-step, [signs[0] * intermediate_value])
             else:
-                score = (float("inf"), [0.0])
+                score = (1, [0.0])
         elif trial.state is TrialState.RUNNING:
             if study._is_multi_objective():
                 continue
 
             assert constant_liar
-            score = (-float("inf"), [signs[0] * float("inf")])
+            score = (float("inf"), [signs[0] * float("inf")])
         else:
             assert False
         scores.append(score)
diff --git a/tests/samplers_tests/tpe_tests/test_sampler.py b/tests/samplers_tests/tpe_tests/test_sampler.py
index 7a75570d6ea..67fbf4ab295 100644
--- a/tests/samplers_tests/tpe_tests/test_sampler.py
+++ b/tests/samplers_tests/tpe_tests/test_sampler.py
@@ -761,7 +761,7 @@ def objective(trial: Trial) -> float:
         (-float("inf"), [sign * 5.0]),  # COMPLETE
         (-7, [sign * 2]),  # PRUNED (with intermediate values)
         (-3, [float("inf")]),  # PRUNED (with a NaN intermediate value; it's treated as infinity)
-        (float("inf"), [sign * 0.0]),  # PRUNED (without intermediate values)
+        (1, [sign * 0.0]),  # PRUNED (without intermediate values)
     ]
     assert _tpe.sampler._get_observation_pairs(
         study, ["x"], False, constraints_enabled=constraints_enabled
@@ -855,7 +855,7 @@ def objective(trial: Trial) -> float:
                 -3,
                 [float("inf")],
             ),  # PRUNED (with a NaN intermediate value; it's treated as infinity)
-            (float("inf"), [sign * 0.0]),  # PRUNED (without intermediate values)
+            (1, [sign * 0.0]),  # PRUNED (without intermediate values)
         ],
         expected_violations,
     )
@@ -1083,7 +1083,7 @@ def test_constant_liar_observation_pairs(direction: str, multivariate: bool) ->
 
     # The value of the constant liar should be penalizing, i.e. `float("inf")` during minimization
     # and `-float("inf")` during maximization.
-    expected_values = [(-float("inf"), [float("inf") * (-1 if direction == "maximize" else 1)])]
+    expected_values = [(float("inf"), [float("inf") * (-1 if direction == "maximize" else 1)])]
 
     assert _tpe.sampler._get_observation_pairs(
         study, ["x"], multivariate, constant_liar=False


Code review comments:
diff_hunk: @@ -441,7 +441,7 @@ def sample_independent(
             self._constraints_func is not None,
         )
 
-        n = len(scores)
+        n = sum(1 for (s, v) in scores if s < float("inf"))  # ignore running trials
path: optuna/samplers/_tpe/sampler.py
text: @user1:
```suggestion
        n = sum(s < float("inf") for s, v in scores)  # Ignore running trials.
```
Ditto.

diff_hunk: @@ -392,7 +392,7 @@ def _sample_relative(
         )
 
         # If the number of samples is insufficient, we run random trial.
-        n = len(scores)
+        n = sum(1 for (s, v) in scores if s < float("inf"))  # ignore running trials
path: optuna/samplers/_tpe/sampler.py
text: @user1:
```suggestion
        n = sum(s < float("inf") for s, v in scores)  # Ignore running trials.
```
A nit.
https://github.com/optuna/optuna/wiki/Coding-Style-Conventions#block-and-inline-comments-are-supposed-to-be-sentences.