Metraipolis › archive › dc_cef2d9de54f6

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights — arXiv:2609.26978

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.26978
License (as archived)
CC0-1.0
Archived
2026-10-08T10:57:52.840Z
SHA-256 of the archived text
ed2aef8dd18e3322eef5c7effdc90bfd531c5a3a515c7946426913e64f6da69e
Stable URL of this page
https://metraipolis.com/documento/dc_cef2d9de54f6

How to cite

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights — arXiv:2609.26978 — arXiv (en), https://arxiv.org/abs/2609.26978 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cef2d9de54f6 (Metraipolis archive dc_cef2d9de54f6, sha256 ed2aef8dd18e3322eef5c7effdc90bfd531c5a3a515c7946426913e64f6da69e)
BibTeX
@misc{dccef2d9de54f6,
  title = {Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights — arXiv:2609.26978},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.26978},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cef2d9de54f6; sha256 ed2aef8dd18e3322eef5c7effdc90bfd531c5a3a515c7946426913e64f6da69e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.26978. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(\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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-24 in cs.LG).
Categorie arXiv: Machine Learning (stat.ML) ; Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.26978 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T10:06:16.795Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).