# Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 22 Sep 2026.

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

- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [Inverse Optimization with Noisy Data](https://mlsanity.com/paper/1507.03266/) (2015)
- [Data-driven Inverse Optimization with Imperfect Information](https://mlsanity.com/paper/1512.05489/) (2015)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [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)
- [Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms](https://mlsanity.com/paper/2305.07730/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis](https://mlsanity.com/paper/2501.13648/) (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)

## Built on by (most cited first, 2 of 2)

- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)
- [Optimal and Efficient Online Inverse Optimization](https://mlsanity.com/paper/2610.08735/) (2026)

## Abstract (arXiv)

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the d-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is O(√ d) in expectation for every time horizon, without knowledge of the horizon. The dependence on d is optimal up to a constant factor by the known Omega(√ d) lower bound for horizons T≥ d. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the O(√ d) regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.