# Optimal and Efficient Online Inverse Optimization

arXiv: https://arxiv.org/abs/2610.08735 · HTML: https://mlsanity.com/paper/2610.08735/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 13 of 13)

- [An Online-Learning Approach to Inverse Optimization](https://mlsanity.com/paper/1810.12997/) (2018)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Inverse Optimization via Learning Feasible Regions](https://mlsanity.com/paper/2505.15025/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Tight Generalization Bounds for Noiseless Inverse Optimization](https://mlsanity.com/paper/2605.08866/) (2026)
- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (2026)
- [Offline Reinforcement Learning via Inverse Optimization](https://mlsanity.com/paper/2502.20030/) (2025)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes](https://mlsanity.com/paper/2609.09809/) (2026)
- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)

## Abstract (arXiv)

In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on ℝd; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret O(√ d) with a randomized algorithm making (dT)O(d) linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret O(√ d) for every horizon T and runs in time polynomial in d and T. It is a variant of the variable-metric algorithms of Sakaue et al. and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.