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

Taihei Oki, Shinsaku Sakaue

TL;DR

This paper resolves a long-standing open question in online inverse linear optimization by proving that a finite, polynomial-in-dimension regret bound is achievable when action sets are M-convex (a broad class that includes matroids). By combining discrete convex analysis with a geometric volume argument, the authors achieve an $O(d \log d)$ regret bound that is completely independent of the time horizon and highly robust to adversarial corruptions.

What Problem Does This Paper Address?

Imagine trying to learn a customer's hidden preferences (an objective vector $w^*$) simply by watching the choices they make from a changing menu of options (feasible sets $X_t$). This is the core setup of online inverse linear optimization, also known as contextual recommendation. The goal of the learner is to recommend actions that minimize "regret"—the cumulative gap between the utility of the agent's truly optimal choice and the utility of the choice recommended by the learner.

Prior algorithms faced a frustrating trade-off. Their regret bounds either grew indefinitely with the time horizon $T$ (typically scaling as $O(d \log T)$), or they were independent of $T$ but exploded exponentially with the dimension $d$ ($\exp(O(d \log d))$). This left open a fundamental question: Is it possible to achieve a finite regret bound that scales polynomially with the dimension $d$?

Methods

The authors achieve their breakthrough by focusing on M-convex action sets, a class of discrete structures from discrete convex analysis that generalizes matroids (like spanning trees or uniform selection sets).

Their approach relies on three key pillars:

  1. The Local Exchange Property: M-convex sets possess a structural property where a solution is globally optimal if and only if it cannot be improved by making local, pairwise swaps between elements. This allows the learner to turn complex optimization feedback into simple pairwise constraints (e.g., "component $i$ must be preferred over component $j$").
  2. Geometric Volume Reduction: Instead of picking an arbitrary estimate for the preference vector, the algorithm maintains a "version space" (a polytope of all objective vectors consistent with past observations) and selects its center of gravity as the current estimate. By applying Grünbaum’s theorem, the authors prove that whenever the learner makes a suboptimal recommendation, the volume of this version space shrinks by a guaranteed constant factor ($1 - 1/e$).
  3. Graph-Based Corruption Detection: To handle scenarios where the agent's feedback might be adversarially corrupted for up to $C$ rounds, the algorithm tracks the pairwise constraints in a directed graph. In an uncorrupted setting, this graph must remain acyclic. If a cycle appears, it serves as an undeniable "certificate of corruption," prompting the algorithm to adaptively execute a clean restart without needing to know $C$ in advance.

Datasets

The paper evaluates its algorithms using a synthetic benchmark rather than real-world datasets. The authors simulate a time-varying uniform matroid setting where a learner chooses from $d = 20$ items, with $k = 10$ items randomly made unavailable at each round. The agent selects optimal subsets of size $m = 5$ over a horizon of $T = 5000$ rounds.

Key Insights and Ideas

  • Bridging Continuous Geometry and Discrete Optimization: The core "aha moment" is realizing that the combinatorial properties of M-convexity perfectly align with continuous geometric cutting-plane methods. M-convexity ensures that every mistake yields a clean hyperplane cut through the parameter space.
  • Self-Policing Feedback Loops: Rather than running multiple parallel copies of an algorithm to hedge against unknown corruption levels (a common but expensive technique in contextual search), the authors show that the preference graph can police itself. A simple topological sort acts as a zero-cost corruption detector.

Key Results

  • Finite Regret Bound: The algorithm achieves a regret bound of $O(d \log d)$ in uncorrupted settings, completely removing the dependency on time horizon $T$.
  • Robustness to Noise: In the presence of $C$ corrupted rounds, the bound gracefully degrades to $O((C+1)d \log d)$.
  • Near-Optimal Bounds: The authors establish an $\Omega(d)$ lower bound for M-convex action sets, proving that their upper bound is tight up to a minor $\log d$ factor.

As shown in the paper's literature review, this work fills a crucial gap in the history of regret bounds for this problem class:

Table 1: Regret bounds for online inverse linear optimization (contextual recommendation). Here, we treat the sizes of the agent’s feasible sets and the learner’s decision set as constants; see Sakaue et al. (2025b, Appendix A) for a discussion on how these sizes affect the regret bounds. The column “Corruption” indicates whether corrupted feedback is considered, while the way of handling corruption differs among the works; see Section 2.2 for a discussion.

In synthetic experiments, the proposed algorithm significantly outperformed standard baselines like Online Newton Step (ONS) and Online Gradient Descent (OGD), with regret flattening out completely as observations accumulated.

Limitations and Future Work

  • Computational Complexity: Computing the exact center of gravity of a high-dimensional polytope is #P-hard. Although the authors successfully implement a randomized polynomial-time approximation using hit-and-run sampling, the per-round complexity scales as $\tilde{O}(d^6)$, making it computationally heavy for very large dimensions.
  • Strict Coordinate Assumptions: The corruption-detection mechanism relies on the assumption that the components of the true objective vector $w^*$ are strictly distinct to reliably identify cycles caused by adversarial manipulation.
  • The Logarithmic Gap: A small $O(\log d)$ gap remains between the paper's upper bound and the proven lower bound, leaving room for future tight alignment.

Summary updated

Abstract

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 $Ω(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.
BibTeX
@inproceedings{oki2026finite,
  author = {Taihei Oki and Shinsaku Sakaue},
  title = {{Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=g7LE4mukGq},
}
Figure