Accessibility Limits for Best-Arm Identification under Coupled Optimization

We study fixed-confidence selection of the unique best among \(K\) unknown objectives along one coupled optimization trajectory. Arm \(i\) has deployment quality \(f_i^\star=\inf_z f_i(z)\), while learning confines the state \(x\) to an affine set \(\mathcal F={x:Ax=b}\). A query returns a noisy value and full gradient, then triggers a prescribed projected update that can move every arm. Without resets or off-trajectory queries, the learner must identify \(\argmin_i f_i^\star\). We characterize the exact boundary between identifiability and impossibility. For fixed \(0<\mu<L\), complete noiseless feasible first-order information determines the best arm over the smooth \(\mu\)-strongly convex, \(L\)-smooth class exactly when feasible directions span every arm block. If this condition fails, two admissible instances can agree in all observable values and full gradients yet have different best arms. Within the identifiable regime and under explicit oracle and access conditions, we introduce Geometric Block Certificates, a \(\delta\)-correct method that turns feasible progress into confidence bounds on standalone optima. It stops with finite expected cost and satisfies quantitative high-probability and expected cost bounds. Finite-class lower bounds show that poor access can itself impose unavoidable cost. Finally, for known-Hessian quadratics under additional oracle conditions, corrected value–gradient observations can restore identifiability even when geometric access fails.