Online algorithm achieves optimal regret bound for inverse linear optimization

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

Data Structures and AlgorithmsMachine Learning

Summary

This paper looks at a problem where a system tries to figure out hidden preferences or rules by observing the best choices made repeatedly in different situations. The authors developed an algorithm that learns quickly from these observations with minimal mistakes, measured by regret, and this performance is proven to be as good as theoretically possible for the problem’s size. Their approach uses advanced math tools like matrix weights and scales to improve learning without needing to know how many rounds will be played. The algorithm also can be efficiently implemented under certain conditions, though making it run quickly in all cases remains an open question.

What this means in practice

  • For machine learning engineers: Design adaptive systems that infer user preferences from observed choices with guaranteed minimal learning error over time.
  • For operations research teams: Improve optimization models that back-calculate unknown cost or utility functions from recorded optimal decisions in dynamic environments.

Authors

Shinsaku Sakaue

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(\sqrt 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 $Ω(\sqrt d)$ lower bound for horizons $T\ge 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(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.
View PDFOpen arXiv