📊 statistics

Bandits attack function optimization

This contribution presents Simultaneous Optimistic Optimization (SOO), a deterministic, domain-partitioning algorithm inspired by Multi-Armed Bandits that effectively balances exploration and exploitation under budget constraints to optimize functions, with its efficiency and solution guarantees demonstrated through an empirical evaluation on the CEC'2014 test suite.

Original authors: Philippe Preux, Rémi Munos, Michal Valko

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Philippe Preux, Rémi Munos, Michal Valko

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the deepest valley in a vast, foggy mountain range. You have a limited amount of fuel (your "budget") to fly your helicopter around. You cannot see the entire map, nor can you ask a guide for directions. You can only land at a specific spot, check the elevation, and then decide where to fly next.

This is the problem addressed by the work: Function Optimization. In the real world, this is comparable to trying to find the perfect setting for a complex machine, developing the best design for a new drug, or determining the most efficient route for a delivery truck, where testing every option costs time, money, or energy.

Here is how the authors, Philippe Preux, Rémi Munos, and Michal Valko, solve this puzzle with a clever strategy they call SOO (Simultaneous Optimistic Optimization).

The Core Dilemma: Explore or Exploit?

The work frames this problem as a game of "Explore vs. Exploit," borrowed from a concept known as the Multi-Armed Bandit.

The Bandit Analogy: Imagine a row of slot machines (bandits). You do not know which one pays out the most.
- Exploit: You keep pulling the lever on the machine that has paid out the most so far, hoping to get rich.
- Explore: You try a machine you have not touched yet, just in case it turns out to be the jackpot winner, even though it seems risky.
The Mountain Analogy:
- Exploit: You keep checking the area around the lowest point you have found so far, hoping to find the absolute bottom of that specific valley.
- Explore: You fly to a completely different, unknown mountain range, just in case there is a deeper valley there.

The challenge is to balance these two aspects. If you only explore, you waste fuel flying around without finding the ground. If you only exploit, you might get stuck in a small depression (a local optimum) and miss the truly deepest valley (the global optimum).

The Solution: SOO (Simultaneous Optimistic Optimization)

The authors propose a deterministic algorithm (meaning it follows a strict set of rules and does not rely on random guessing) that acts like a very clever, systematic explorer.

How it works (The Metaphor "Dividing the Map"):

Start Big: Imagine your entire search area as a single huge square piece of paper.
Cut and Check: You cut this paper into smaller pieces (sub-cells). You land in the middle of each new piece and check the elevation.
The "Optimistic" Choice: Here lies the magic. The algorithm considers all the pieces it has cut so far. It does not simply choose the piece with the lowest elevation found so far. Instead, it chooses the piece that could contain the lowest elevation, based on the information it has. It is "optimistic" that the unexplored parts of a promising-looking area might hide the true winner.
Repeat: It keeps cutting the most promising piece into smaller and smaller slices, concentrating its fuel budget where the "deepest valley" is most likely to be found.

Why is this special?
Most algorithms need to know how "smooth" the terrain is (e.g., are the hills gentle or jagged?) to work well. SOO is unique because it does not need this knowledge in advance. It adapts automatically. It assumes that the terrain near the best point is smooth, but it does not need to know exactly how smooth it is to begin.

The Results: Surprising Success

The authors tested their algorithm on a famous set of 30 difficult mathematical problems (the CEC'2014 competition).

The Expectation: They believed the algorithm would work okay for small maps (10 dimensions) but would fail miserably on huge, complex maps (100 dimensions).
The Reality: They were surprised! While it had difficulties with some very tricky, narrow valleys, it performed remarkably well on many high-dimensional problems. In some cases, increasing the complexity from 10 to 100 dimensions barely affected its performance.
Comparison: Compared to an older, famous algorithm called DiRect, SOO won in 21 out of 30 tests.
The "Local" Boost: The work notes that SOO is excellent at finding the general area of the best solution. If you take the best point SOO finds and pass it to a "local optimizer" (a tool that fine-tunes nearby), the results improve even further, often finding the exact bottom of the valley.

Summary

The work argues that finding the best solution for a complex problem is like a game of "Guess the Best Spot" with a limited budget. By using a strategy that systematically divides the search space and remains "optimistic" about where the best answer might lie, the SOO algorithm can find excellent solutions without needing to know the specific rules of the terrain in advance. It is easy to build, fast to execute, and surprisingly effective, even in very high-dimensional spaces.

Technical Summary: Bandit Attack on Function Optimization

Problem Definition

The article addresses the problem of global function optimization under a strict budget constraint, where the number of evaluations of the objective function is limited. The objective function is treated as a Black-Box, meaning the algorithm receives only the function value at queried points, without access to gradients or explicit functional forms. The authors emphasize that real-world functions often lack known smoothness properties (continuity, differentiability) and can even be non-deterministic.

The core challenge is formulated as a sequential decision problem under uncertainty. The algorithm must iteratively select the next point for evaluation to balance Exploration (searching the space to locate promising regions) and Exploitation (refining the search around potentially optimal points). In contrast to local optimization algorithms that guarantee only local optima, this work seeks algorithms with finite-time guarantees, providing a provable bound on the quality of the returned solution relative to the evaluation budget.

Methodology: Simultaneous Optimistic Optimization (SOO)

The authors introduce Simultaneous Optimistic Optimization (SOO), a deterministic algorithm inspired by the Multi-Armed Bandit problem, specifically the concept of "Optimism in the Face of Uncertainty."

Algorithm Mechanics

SOO operates by partitioning the search space into a tree of cells:

Initialization: The entire search space is treated as a single root cell.
Partitioning: In each iteration, the algorithm selects a cell to split. The splitting process divides a cell along a specific dimension into $S$ sub-cells (typically $S=3$ ).
Evaluation: The midpoint of each new sub-cell is evaluated.
Selection Strategy: SOO maintains a tree structure, identifying the cell with the lowest function value at each depth (assuming minimization). A cell is selected for splitting only if its value is lower than that of all previously selected cells at shallower depths. This ensures the algorithm focuses on the most promising regions while maintaining a global overview.
Termination: The process continues until the evaluation budget is exhausted. The point with the lowest observed value is returned.

Theoretical Properties

SOO is designed to operate under weak assumptions. It requires no prior knowledge of the function's smoothness or a Lipschitz constant. Instead, it assumes the function is locally smooth near its global optimum in a specific sense defined by the "Near-Optimality Dimension" ( $d$ ).

Key theoretical guarantees include:

Consistency: The algorithm converges asymptotically to the global optimum.
Finite-Time Regret: The difference between the value of the returned solution $f(x_t)$ and the global optimum $f^*$ decreases at a rate of $O(t^{-1/d})$ , where $t$ is the number of evaluations. In cases where $d=0$ , an exponential rate of $O(e^{-ct})$ is achievable.
Rank-Based: The algorithm relies solely on pairwise comparisons of function values, not their absolute magnitudes.

Experimental Evaluation

The authors evaluated SOO on the benchmark suite of the CEC'2014 competition for single-objective numerical optimization with real-valued parameters. The test suite comprised 30 objective functions in dimensions 10, 30, 50, and 100.

Key Findings

Performance in High Dimensions: Contrary to the authors' initial expectation that partitioning algorithms would degrade significantly beyond 5 dimensions, SOO demonstrated remarkable performance in high dimensions (up to 100D). For a significant portion of the functions (e.g., functions 5, 12, 13, 14, 23, 28, 29, 30), the performance degradation between 10D and 100D was less than 0.5%.
Comparison with DiRect: Compared to the DiRect algorithm (Dividing Rectangles) on 10-dimensional problems, SOO performed better on 21 out of 30 functions and matched it on another 5. The authors note that while DiRect assumes global Lipschitz continuity, SOO operates under weaker local assumptions and offers formal finite-time performance guarantees that DiRect lacks.
Hybrid with Local Optimization: The authors tested a hybrid approach where SOO identifies a promising region and a local, derivative-free optimizer (BOBYQA) refines the solution. This post-processing significantly improved results, bringing the solution very close to the optimum for all 30 functions in 10D and most in 30D.
Limitations: SOO struggled with functions where the optimum lies in a very narrow region (e.g., functions 1 and 2) or where the function combines difficult atomic components.

Significance and Claims

The article claims that the primary contribution is the conceptual shift to viewing function optimization as a sequential decision problem, thereby leveraging the rich theoretical framework of bandit algorithms.

The authors position SOO as a serious alternative for global optimization, highlighting three main strengths:

Theoretical Rigor: It is one of the few global optimization algorithms with formally proven finite-time performance guarantees under weak assumptions.
Simplicity and Efficiency: The algorithm is deterministic, easy to implement, and computationally efficient.
Robustness: It operates effectively in high-dimensional spaces without requiring manual adjustment of smoothness parameters.

The article concludes modestly, acknowledging that while SOO may not be the absolute best optimizer for every specific case, its combination of theoretical guarantees, simplicity, and unexpected robustness in high dimensions makes it a valuable tool. The authors suggest that future work should focus on automatic parameter tuning, handling stochastic (noisy) functions, and the theoretical analysis of the trade-off between global partitioning and local optimization.