Optimal and Efficient Online Inverse Optimization
The paper addresses online inverse linear optimization, where a learner must recommend an action based on expert choices to maximize an unknown linear objective vector $w^*$ in $\mathbb{R}^d$. While previous randomized methods achieved optimal regret $O(\sqrt{d})$, this work presents a deterministic algorithm achieving the same optimal regret bound of $O(\sqrt{d})$ for every horizon $T$ in polynomial time, improving upon existing variable-metric approaches by revoking metric updates.