Best Arm Identification in Linear Bandits with Partially Observable Features

We study best arm identification (BAI) in linear bandits where feature vectors generating underlying rewards are only partially observable. Unobserved features induce non-uniform, arm-specific reward shifts that alter the true ranking of arms, causing standard stopping rules based solely on observed features to falsely identify suboptimal arms. To address this challenge, we formally introduce the problem of BAI with partially observable features and establish a theoretical lower bound on sample complexity that characterizes its fundamental hardness. We then propose CoLF, an algorithm that explicitly captures these reward shifts and achieves minimax optimal sample complexity up to logarithmic factors. CoLF reconstructs the feature space by augmenting observed features with the orthogonal complement of their row space, generated by a mixed $G$-optimal experimental design and estimates the reconstructed parameters that includes the unknown reward shifts via a doubly robust (DR) estimator. Empirical evaluations in synthetic environments demonstrate that CoLF accurately learns unobserved reward shifts and consistently identifies the true optimal arm.