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

Taihei Oki, Shinsaku Sakaue

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. 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.

Introduction

Online Inverse Linear Optimization (OILO) is a fundamental problem in machine learning where a system learns user preferences by observing their choices. In each round $t$, the learner presents a feasible set $X_t$, and the agent selects an action $x^*_t \in X_t$ that maximizes their internal linear objective $w^* \cdot x$. The learner's goal is to minimize the cumulative regret: the difference between the utility of the agent's optimal choice and the utility of the learner's recommendation $\hat{x}_t$.

A major challenge in OILO has been the trade-off between time-dependent and dimension-dependent regret bounds. While $O(d \log T)$ bounds exist, they grow indefinitely with the time horizon $T$. Conversely, existing "finite" bounds (independent of $T$) were exponentially large in the dimension $d$, specifically $\exp(O(d \log d))$. This paper bridges this gap by introducing a polynomial finite regret bound for a significant class of problems.

Methodology: Leveraging M-Convexity

The core innovation of this work lies in focusing on M-convex action sets. M-convexity is a central concept in discrete convex analysis that generalizes structures like matroids, spanning trees, and certain integer resource allocation problems.

Structural Characterization

The authors exploit a unique property of M-convex sets: local optimality implies global optimality. Specifically, an action is optimal if and only if it cannot be improved by a "local exchange" of one unit between two indices. This allows the learner to transform each observed action into a set of linear constraints on the hidden vector $w^*$.

The Center of Gravity Algorithm

The algorithm maintains a "version space"—a polytope $P_t$ containing all objective vectors consistent with past observations. By choosing the center of gravity of $P_t$ as the current estimate $\hat{w}_t$, the authors ensure that any suboptimal recommendation provides a "cut" that reduces the volume of the version space by a constant factor (at least $1/e$). This geometric shrinkage is the key to achieving finite regret.

Adaptive Corruption Handling

In real-world scenarios, agents may provide "noisy" or corrupted feedback. The authors handle up to $C$ adversarial corruptions by monitoring a directed graph of inferred preferences. If the preferences form a cycle (e.g., $i \succ j \succ k \succ i$), the algorithm detects a corruption and adaptively restarts. This mechanism does not require prior knowledge of $C$.

Key Results and Comparison

The proposed approach achieves a regret bound of $O(d \log d)$ in the uncorrupted case and $O((C+1)d \log d)$ in the presence of $C$ corruptions. This represents the first finite, polynomial-in-$d$ bound for this problem class.

Comparison of regret bounds across different settings and prior works.

As shown in the table above, this work significantly improves upon the exponential bounds of previous finite-regret algorithms while maintaining robustness to adversarial corruption. The $O(d \log d)$ bound is also near-optimal, given the known lower bound of $\Omega(d)$.

Conclusion

By identifying M-convexity as a key structural property, this paper provides a definitive answer to the feasibility of polynomial finite regret in OILO. The integration of geometric volume arguments with discrete convex analysis offers a robust framework for contextual recommendation, even under adversarial conditions. Future work may address the computational complexity of calculating the center of gravity and explore extensions to more general action sets.

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