Optimization and Exploration with Heterogeneous Costs

132 concepts121 papers4 proposals

Imagine you are given a fixed budget of $1,000 to find the best machine learning model configuration for a critical task. You can choose to evaluate a simple decision tree that takes two seconds to train, or a massive deep neural network that takes five hours.

Standard hyperparameter optimization algorithms treat these two choices identically. They operate under the uniform cost assumption, assuming that every trial, sample, or intervention incurs an identical cost. In the real world, however, evaluation costs are highly heterogeneous—varying by orders of magnitude in time, money, or physical risk.

By ignoring these cost disparities, traditional algorithms allocate resources inefficiently, often exhausting their budgets prematurely on expensive, low-value trials. A rapidly growing body of research seeks to dismantle this uniform cost assumption, building algorithms that explicitly balance the information gained from an action against the specific resource cost of taking it.

The Flaw of the Uniform Cost Assumption

To understand why traditional frameworks struggle, consider how a standard Bayesian Optimization (BO) or Multi-Armed Bandit (MAB) algorithm selects its next step. Typically, it calculates an acquisition function—such as Expected Improvement (EI) or Upper Confidence Bound (UCB)—across the search space and picks the point where this value is maximized. This approach works perfectly if every point costs the same to evaluate.

However, as Yaochu Jin et al. note in their survey, Recent Advances in Bayesian Optimization, real-world applications present highly uneven latency and cost landscapes. If an algorithm is blind to these variations, it might choose an evaluation point that offers a 1% increase in expected information over an alternative, but costs 100x more to compute.

This problem spans numerous domains:

  • Hyperparameter Tuning: Jasper Snoek et al. demonstrated in Practical Bayesian Optimization of Machine Learning Algorithms that different parameter configurations result in vastly different training times. Treating a lightweight model and a heavyweight model as equally costly leads to severe resource waste.
  • Pure Exploration and Bandits: In Best Arm Identification (BAI), Kellen Kanarios et al. and Chengshuai Shi et al. show that ignoring non-uniform sampling costs prevents algorithms from finding the optimal choice within practical economic constraints.
  • Causal Discovery: To learn a causal graph, you must perform interventions (experiments). However, changing a patient's diet is vastly cheaper and safer than manipulating their genetic code. Alex Dimakis et al. argue in Cost-Optimal Learning of Causal Graphs that experimental design must minimize total economic expenditure rather than just the raw number of tests.

How Cost-Aware Selection Works

To fix this blind spot, cost-aware algorithms alter how they value exploration. Instead of asking, "Which experiment gives me the most information?" they ask, "Which experiment gives me the most information per dollar?"

1. Cost-Weighted Acquisition Functions

The most direct way to build intuition for this is to look at modified acquisition functions. A classic heuristic divides the expected information gain by the estimated cost of the evaluation, optimizing for a metric like $\frac{EI(x)}{c(x)}$.

Because the true cost function $c(x)$ is often unknown and stochastic, researchers model the cost space alongside the objective space using a secondary Gaussian Process. In Evolve Cost-aware Acquisition Functions Using Large Language Models, Yiming Yao et al. demonstrate that meta-learned or evolved acquisition functions can dynamically adapt to these complex cost landscapes, significantly outperforming rigid, human-designed heuristics.

2. Nonmyopic and Budget-Aware Planning

Greedy, one-step-ahead (myopic) adjustments are not always enough. If an algorithm only looks one step into the future, it might continuously pick ultra-cheap, low-value points and run out of time before ever exploring the more expensive, high-value regions necessary to find the global optimum.

To solve this, David Eriksson et al. frame cost-constrained optimization as a Constrained Markov Decision Process (CMDP) in A Nonmyopic Approach to Cost-Constrained Bayesian Optimization. By using multi-step lookahead "rollouts," the algorithm treats its remaining budget as a state variable.

Early in the search, when the budget is flush, it plans sequences that can afford expensive, high-risk/high-reward evaluations. As the budget depletes, its strategy automatically shifts toward conservative, high-efficiency local refinements, a principle also explored by Zhiyun Lu et al. in Hyper-parameter Tuning under a Budget Constraint.

[High Budget] --------> Plan Long-term Rollouts ------> Mix Cheap & Expensive Trials
[Low Budget]  --------> Conserve Remaining Funds ----> Prioritize High-Efficiency Local Search

3. Multi-Fidelity Filtering

When evaluation costs are heterogeneous, we often have access to approximations or "proxies" of the true objective function. For example, we can test a machine learning model on a tiny subset of data (low fidelity/low cost) before committing to training it on the full dataset (high fidelity/high cost).

In Multi-Fidelity Best-Arm Identification, Alberto Maria Metelli et al. formalize how to use these multi-fidelity structures mathematically. The intuition is simple: use cheap, low-fidelity evaluations to quickly eliminate options that are clearly sub-optimal. By filtering out the "bad" choices at a fraction of the cost, the algorithm reserves its expensive, high-fidelity budget exclusively for distinguishing between the top-tier contenders.

Designing for Practical Constraints

Accounting for heterogeneous costs requires moving beyond idealized mathematical abstractions to embrace physical and structural realities.

For instance, in parallel computing environments, evaluation times are inherently unpredictable. Kirthevasan Kandasamy demonstrated in Parallelised Bayesian Optimisation via Thompson Sampling that asynchronous scheduling is vital when evaluation costs vary; forcing workers to wait for a slow, expensive trial to finish destroys parallel efficiency.

Similarly, Michael O Harding developed a framework called DBCARE in Balancing Performance and Costs in Best Arm Identification that adaptively decides exactly when to stop sampling altogether, matching theoretical lower bounds by directly trading off the cost of continuing to sample against the statistical risk of making an incorrect final choice.

Ultimately, the shift away from the uniform cost assumption represents a maturation of optimization theory. By treating time, computation, and capital as heterogeneous constraints rather than uniform constants, cost-aware frameworks allow algorithms to navigate real-world environments with the same pragmatic resource management as human experts.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_uniform_cost_assumption_heterogeneous_ev_48445630,
  title = {uniform cost assumption (heterogeneous evaluation costs)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniform-cost-assumption-heterogeneous-evaluation-costs/rdr_48445630f9a24fb3b225edccb1f03283},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_uniform_cost_assumption_heterogeneous_ev_48445630_v1,
  title = {uniform cost assumption (heterogeneous evaluation costs)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniform-cost-assumption-heterogeneous-evaluation-costs/rdr_48445630f9a24fb3b225edccb1f03283/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake