Learning with a Budget: Identifying the Best Arm with Resource Constraints
In many applications, evaluating the effectiveness of different alternatives comes with varying costs or resource usage. Motivated by such heterogeneity, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem, where an agent seeks to identify the best alternative (aka arm) in the presence of resource constraints. Each arm pull consumes one or more types of limited resources. We make two key contributions. First, we propose the Successive Halving with Resource Rationing (SH-RR) algorithm, which integrates resource-aware allocation into the classical successive halving framework on best arm identification. The SH-RR algorithm unifies the theoretical analysis for both the stochastic and deterministic consumption settings, with a new \textit{effective consumption measure
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Best Arm Identification with Resource Constraints
Motivated by the cost heterogeneity in experimentation across different alternatives, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem. The agent aims to identify the best arm under resourc…
Budgeted Training: Rethinking Deep Neural Network Training Under Resource Constraints
In most practical settings and theoretical analyses, one assumes that a model can be trained until convergence. However, the growing complexity of machine learning datasets and models may violate such assumptions. Indeed…
General Classificationimage-classificationImage ClassificationInstance Segmentation+5Identifying Best Interventions through Online Importance Sampling
Motivated by applications in computational advertising and systems biology, we consider the problem of identifying the best out of several possible soft interventions at a source node $V$ in an acyclic causal directed gr…
Blind Network Revenue Management and Bandits with Knapsacks under Limited Switches
Our work is motivated by a common business constraint in online markets. While firms respect the advantages of dynamic pricing and price experimentation, they must limit the number of price changes (i.e., switches) to be…
Decision MakingManagementBiased Pareto Optimization for Subset Selection with Dynamic Cost Constraints
Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget, which has various applications such as influence maximization a…