Contextual Search in Principal-Agent Games: The Curse of Degeneracy

In this work, we introduce and study contextual search in general principal-agent games, where a principal repeatedly interacts with agents by offering contracts based on contextual information and historical feedback, without knowing the agents’ true costs or rewards. Our model generalizes classical contextual pricing by accommodating richer agent action spaces. Over \(T\) rounds with \(d\)-dimensional contexts, we establish an asymptotically tight exponential \(T^{1-\Theta(1/d)}\) bound in terms of the pessimistic Stackelberg regret, benchmarked against the best utility for the principal that is consistent with the observed feedback.