Technical Summary: Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

Problem Formulation

This paper addresses the Multi-Armed Bandits with Cost Subsidy (MAB-CS) problem, a framework designed for cost-sensitive online decision-making where the objective is to minimize cumulative cost subject to a quality constraint. Unlike standard MABs that maximize cumulative reward, MAB-CS seeks the cheapest arm among those that satisfy a minimum expected reward threshold.

The specific setting investigated here involves a quality constraint defined relative to the unknown best reward in the system. Given a set of arms $\mathcal{A} = \{a_1, \dots, a_K\}$ with expected rewards $\mu_k$ and known sampling costs $c_k$, the feasible set is $S = \{a_k \in \mathcal{A} \mid \mu_k \geq \mu_{CS}\}$. The threshold is defined as $\mu_{CS} = (1-\alpha)\mu^*$, where $\mu^* = \max_{a_k \in \mathcal{A}} \mu_k$ is the unknown best reward and $\alpha \in (0, 1)$ is a subsidy factor. The optimal arm $a^*$ is the cheapest arm in the feasible set $S$.

The paper defines two regret metrics:

1. Cost Regret: The excess cost incurred relative to the optimal arm $a^*$.
2. Quality Regret: The penalty incurred when the expected reward of the selected arm falls below the feasibility threshold $\mu_{CS}$.

The core challenge lies in jointly minimizing these regrets while simultaneously estimating the unknown threshold $(1-\alpha)\mu^*$ and identifying the cheapest feasible arm without prior knowledge of $\mu^*$.

Methodology: The COF Algorithm

The authors propose the Cost-Ordered Feasibility (COF) algorithm to solve the MAB-CS problem. COF operates by evaluating arms in increasing order of their known costs. For each candidate arm $a_\ell$, the algorithm determines feasibility by comparing it against a set of "gating arms" (arms more expensive than $a_\ell$).

Key mechanisms in COF include:

• Cost-Ordered Evaluation: Arms are tested sequentially from cheapest to most expensive. The first arm deemed feasible is selected as the optimal arm for the remainder of the horizon.
• Combining Samples (Aggregation): To determine if a candidate arm $a_\ell$ is infeasible, COF does not rely on a single pairwise comparison. Instead, it aggregates evidence from comparisons with all arms capable of disqualifying $a_\ell$. It computes an upper bound on the probability that $a_\ell$ is feasible relative to each gating arm and deems $a_\ell$ infeasible once the product of these probabilities drops below a tolerance $\delta$.
• Exclusive Sampling: If a candidate arm's sample count lags behind the most sampled gating arm, COF samples the candidate exclusively to "catch up," reducing the total number of sub-optimal samples required.
• BAI-Filter: During the evaluation of a candidate, COF employs a filter that stops sampling gating arms whose Upper Confidence Bounds (UCB) fall below the Lower Confidence Bound (LCB) of another gating arm. This prevents wasting samples on arms that are statistically unlikely to be the best reward arm ($i^*$).

Theoretical Contributions

The paper provides a rigorous theoretical analysis of MAB-CS, establishing both lower and upper bounds on regret.

1. Instance-Dependent Lower Bounds:

   • The authors derive lower bounds on the expected number of samples for cheap arms (cost $< c_{a^*}$) and expensive arms (cost $> c_{a^*}$).
   • A novel contribution is a joint lower bound for a collection of arms. This bound reflects the insight that an arm can be certified as infeasible if its reward is worse than the subsidized reward of any arbitrary arm, not just the best reward arm $i^*$. This generalizes prior bounds that treated $i^*$ singularly.

2. Regret Upper Bounds for COF:

   • The paper establishes instance-dependent upper bounds on the expected cumulative cost and quality regret for COF.
   • For cheap arms, the bound is shown to be order-optimal, matching the $O(\log T / \Delta_{Q,k}^2)$ dependence found in the lower bounds.
   • For expensive arms, the bound depends on the maximum of two terms: one related to the gap between the arm and the optimal arm, and another related to the joint gap required to eliminate the best cheap arm. The authors note a slight discrepancy between the lower and upper bounds for expensive arms, suggesting room for improvement in the theoretical analysis of sample complexity.

Experimental Results

The authors validate COF through extensive simulations on:

• Real-world datasets: Goodreads (book ratings) and MovieLens (movie ratings), where genres serve as bandit arms.
• Synthetic instances: Hand-designed problems to test specific algorithmic behaviors.

Key Findings:

• Performance: COF consistently outperforms baseline algorithms, including ETC-CS (fixed budget exploration), PE-CS (pairwise elimination), UCB-CS, and TS-CS.
• Robustness: Unlike UCB-CS and TS-CS, which can suffer from linear regret due to incorrectly including cheap, infeasible arms in their empirically feasible sets, COF maintains sub-linear regret by rigorously testing feasibility.
• Subsidy Factor Sensitivity: While PE-CS performs slightly better for very small subsidy factors ($\alpha$) due to tighter confidence intervals in high-sample regimes, COF avoids the performance plateauing observed in PE-CS as $\alpha$ increases.
• Ablation Studies: Experiments confirm that the "combining samples" and "exclusive sampling" features are critical for the algorithm's efficiency, significantly reducing regret compared to variants without these mechanisms.

Significance and Claims

The paper claims that COF offers a qualitatively superior theoretical framework and empirical performance for cost-sensitive bandit problems where the quality constraint is relative to the unknown best reward.

• Theoretical Advancement: The work provides the first instance-dependent lower bounds that jointly characterize the sample complexity of multiple arms, offering deeper insight into the structural challenges of MAB-CS than previous worst-case or single-arm analyses.
• Algorithmic Efficiency: By avoiding a dedicated Best Arm Identification (BAI) phase to find $\mu^*$ before testing feasibility, COF reduces unnecessary sampling. The "combining samples" strategy allows the algorithm to eliminate infeasible arms more efficiently than pairwise comparison methods.
• Practical Applicability: The authors highlight the relevance of MAB-CS to real-world scenarios such as LLM model routing, where different models have varying costs and unknown quality, and the system must balance cost against a performance floor relative to the best available model. Similarly, the framework applies to advertising modality selection and streaming service content delivery.

The authors conclude that while COF achieves order-optimal performance for cheap arms and demonstrates strong empirical results, future work should address the gap between the lower and upper bounds for expensive arms and explore cost-biased sampling variants for applications with highly uneven cost distributions.