[BUG] Decreasing objective values after using GridArchive.add()

[patrickab]

• pyribs version: 0.6.3
• Python version: 3.10.12
• Operating System: Linux Mint

Description

Strangely, I can observe a quality decline when using GridArchive.add(). I've already checked the source code in ArchiveBase to see, if there's maybe some reason that could explain this behavior, but I can't find it. Below I've provided the code. There I am adding solutions to the archive inside a for loop. Yet, when I calculate the sum over the objective_batch(), I can observe a quality decline in nearly every function call of update_archive(). At this point it is important to note, that the batches added in each iteration can reach a size of 50,000-100.000 solutions.

Steps to Reproduce

def update_archive(self, gp, archive: GridArchive, bhv_cellgrid, mes_cellgrid, bhv_cellbounds, candidate_sol):

    acq_sum_t0 = np.sum(archive.as_pandas().objective_batch())

    if candidate_sol.shape[0] == 0:
        return

    for i in range(0, candidate_sol.shape[0], BATCH_SIZE):

        # [...] prepare inputs for acq_mes() 

        # evaluate mes & add solutions
        solution_batch, acquisition_batch, measure_batch = acq_mes(self=self, genomes=i_candidate_sol, gp_model=gp, cellgrids=_mes_cellgrids, cellbounds=_cellbounds)
        archive.add(solution_batch, acquisition_batch, measure_batch)

    acq_sum_t1 = np.sum(archive.as_pandas().objective_batch())

    if acq_sum_t0 > acq_sum_t1:
        raise ValueError("acq_sum_t0 < acq_sum_t1")

    return archive

[btjanaka]

Hi @patrickab, thanks for sending in this issue. Do you have a minimum reproducible example that I might be able to run? Right now, it's hard to see what's going on; in particular I can't see how your archive is defined, and I don't know exactly how much your objectives are decreasing. If you could provide these details or an MRE, I think I'd be better able to help you.

[patrickab]

Hi @btjanaka, unfortunately the code is part of a complex project, so tayloring a MRE would be rather difficult. However, I'd love to contribute to pyribs and help to fix this bug. I think providing you with necessary information output would be a convenient way, but if you like I can also provide you with a link to the repo. For my project I could hotfix the error by extracting the ArchiveDataframe before adding new solutions, and then re-insert these solutions, objectives and measures.

Regarding the amount of objective decrease its hard to pinpoint the numerical value to a meaning, as objective value ranges may differ across bins. However, before i tested it and the difference for individual bins was rather significant, and cannot be attributed to rounding errors. Additionally, in some bins objectives increased, just as expected. Tomorrow I can produce some detailled output with percentual increase/decrease.

Regarding the archive, I am not doing anything unusual, here's how I've defined it:

        acq_archive = GridArchive(
            solution_dim=11,
            dims=[15,15],
            ranges=[(0.2625,0.6875), (0.0725,0.1875)],
            qd_score_offset=-600,
            threshold_min = 0,
            dtype=np.float64,
        )

[btjanaka]

@patrickab Thanks for the info! I believe your error is caused by your use of threshold_min=0. This activates CMA-MAE behavior in the archive (specifically, it is CMA-MAE with default learning rate of 1.0 and threshold min of 0). This means that when you insert solutions into the archive, the threshold for the cells is computed with the batch threshold update rule from the CMA-MAE paper (Appendix H here). You can see the computation on this line.

Here are a couple potential solutions:

• Set threshold_min=-np.inf (i.e., the default). Note that this does allow solutions with negative objectives into the archive. I'm guessing you intended to use threshold_min to prevent low-performing solutions from getting into the archive, but that's not quite the role of threshold_min in pyribs archives.
• Add an elitist result archive, i.e., another archive that stores the best performers. We have support for this in the scheduler -- essentially you create an extra archive. More info in the CMA-MAE tutorial.

Overall, I don't think this is really a bug, although it may be a confusing feature. The easiest solution I can think of would be to add a warning in the CMA-MAE tutorial. I'm potentially open to adding a warning in the code where setting threshold_min without setting learning_rate would raise a warning (currently, the inverse of setting learning_rate without setting threshold_min throws an error because of the mechanics of CMA-MAE).

[patrickab]

Thank's a lot for the information! Exactly, thats how intended it's use. Before that I used positive threshhold values & they seemed to work just as intended for a long time. Just recently I've set this value to 0, and that's when I started to observe the issue. From what I understand now I am not right to assume, that setting my threshold to some marginal value above 0 would work as expected?

I think adding more information to the tutorial & API documentation on the website would be a great idea! Personally, I would have never expected to find the issue related to this variable.

[btjanaka]

@patrickab I think there's still a slight misunderstanding here. Unlike MAP-Elites, CMA-MAE inserts solutions into the archive based on a threshold value rather than the objective value of the solution currently in the archive. This threshold is initialized to threshold_min, and whenever solutions are inserted, they are used to update the threshold. Importantly, the threshold may be lower than the objective of the solution currently in the cell, which means that a high-performing solution can be replaced by a lower-performing solution, as long as that new solution crosses the threshold for that cell.

Based only on the description in the CMA-MAE paper, you'd expect that the threshold would match the objective value of the current solution, since the default learning rate (alpha) is 1.0. Since you're using batch addition, however, the batch threshold update rule kicks in, which adjusts the threshold based on the average of all new solutions in the batch for that cell. Long story short, the threshold can still be lower than the objective value of the solution in the cell. Thus, what you're likely seeing is that solutions with high performance are replaced by solutions with low performance since those solutions crossed the threshold.

In short, setting any threshold value here will not achieve your goal of filtering solutions by objective value. That being said, I do recommend adding an elitist archive and trying out CMA-MAE -- we've found it works much better than CMA-ME in many problems. The CMA-MAE tutorial and paper I linked above are good resources for this.

[patrickab]

thank's a lot for this detailled explanation!! I'd love to also integrate the approach into my work, actually I had already considered to integrate CMA-ME in the context of your pyribs gradient emitter, unfortunately my deadline is moving closer. I appreciate your your assistance and also your recommendation, I'll keep it in mind for future.

[btjanaka]

You're welcome! Based on your descriptions, I think the easiest thing I can suggest is to get rid of threshold_min entirely, and then filter for solutions above 0 during post-processing, i.e., when you manipulate the dataframe from as_pandas. Best of luck!