Learning the Best Under Constraints: A Duality-Based Framework

This paper studies a constrained linear best arm identification problem with covariate selection in the fixed-confidence setting, where each arm is evaluated across multiple performance metrics. The mean performance of each metric depends linearly on the feature vectors of both arms and covariates. The goal is to identify the arm with the highest expected value of one targeted metric while ensuring that the means of the remaining metrics stay below specified thresholds for each covariate. We first establish an instance-dependent lower bound on the sample complexity, formulated as a multi-level optimization problem that captures both feasibility and optimality. We then prove that this bound is tight by designing an algorithm that asymptotically matches it. Since the original algorithm is computationally intensive, we develop a relaxed version of the bound through a surrogate optimization problem and derive its convex dual. Using this bound, we propose a duality-based decomposition algorithm that is computationally efficient, updating only two coordinates and performing a single gradient step per iteration. We further show that the algorithm achieves the relaxed bound in theory and demonstrates its practical effectiveness through numerical experiments.

Many real-world decisions require more than simply choosing the option with the highest performance. The chosen option must also satisfy other requirements, such as safety, risk, or cost limits, and these requirements may vary across different contexts. This paper studies how to identify the best acceptable option efficiently when each option has multiple performance measures and is described by observable features. We first derive a theoretical benchmark that shows the minimum amount of data needed to confidently make the right choice. This benchmark also explains how sampling effort should be divided between checking feasibility and comparing performance. We then develop algorithms that approach this benchmark. To make the method practical, we propose a faster algorithm with strong theoretical guarantees, and numerical experiments show that it performs well.