Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Abstract
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 Ω(√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.
Related
- Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
- Dynamic Regret and Tightened Constraint Violation for Communication-Efficient Distributed Online Bilevel Optimization
- Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
BibTeX
@misc{sakaue2026tight,
title = {{Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights}},
author = {Shinsaku Sakaue},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26978},
eprint = {2609.26978},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26978},
}
RIS
TY - UNPB
TI - Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
AU - Shinsaku Sakaue
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26978
UR - https://arxiv.org/abs/2609.26978
AB - 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 Ω(√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.
ER -