Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets

We study online inverse linear optimization, also known as contextual recommendation, where a *learner* sequentially infers an *agent*’s hidden objective vector from observed optimal actions over feasible sets that change over time. The learner aims to recommend actions that perform well under the agent’s true objective, and the performance is measured by the *regret*, defined as the cumulative gap between the agent’s optimal values and those achieved by the learner's recommended actions. Prior work has established a regret bound of $O(d\log T)$, as well as a finite but exponentially large bound of $\exp(O(d\log d))$, where $d$ is the dimension of the optimization problem and $T$ is the time horizon, while a regret lower bound of $\Omega(d)$ is known (Gollapudi et al. 2021; Sakaue et al. 2025). Whether a finite regret bound polynomial in $d$ is achievable or not has remained an open question. We partially resolve this by showing that when the feasible sets are *M-convex*—a broad class that includes matroids—a finite regret bound of $O(d\log d)$ is possible. We achieve this by combining a structural characterization of optimal solutions on M-convex sets with a geometric volume argument. Moreover, we extend our approach to adversarially corrupted feedback in up to $C$ rounds. We obtain a regret bound of $O((C+1)d\log d)$ without prior knowledge of $C$, by monitoring directed graphs induced by the observed feedback to detect corruptions adaptively.

Many systems need to infer a person’s or agent’s hidden preferences from the choices they make. This paper studies this problem in an online setting, where choices are observed over time and the learner aims to make good recommendations. We show that when the available choices have a useful combinatorial structure called M-convexity, the learner can achieve a finite performance guarantee that grows almost linearly with the problem dimension and does not depend on the time horizon. We also extend the method to handle corrupted observations without knowing in advance how many such observations will occur.