New Paper Cracks the Tightest Possible AI Preference Learning Bound
A new randomized algorithm closes a long-standing gap in learning hidden utilities from optimal choices, hitting the provably optimal O(√d) regret bound.
- New paper proves the optimal regret for online inverse linear optimization is Θ(√d), matching the known lower bound.
- Algorithm uses matrix multiplicative weights over polynomial features at geometrically spaced scales.
- Regret bound holds for any horizon T without needing to know T in advance.
- Improves on recent O(d) results from Google Research and Dewasurendra.
- Major caveat: algorithm is not polynomial-time; efficient O(√d) remains an open problem.
- Full paper available on arXiv; no code released.
Tight √d regret for learning linear preferences from choices
A new single-author paper proves a tight regret bound for online inverse linear optimization. When utilities and actions lie in the d-dimensional Euclidean unit ball, its randomized algorithm achieves O(√d) expected regret for every horizon. That matches the known Ω(√d) lower bound when T ≥ d. The construction is oracle-computable, though the paper leaves polynomial-time implementation open.
Learning preferences from revealed choices
Online inverse linear optimization studies a learner trying to infer a fixed, hidden linear utility from an agent’s optimal choices. On round t, the learner receives a feasible action set, predicts a utility vector, and recommends the action that maximizes its predicted utility. The agent’s optimal action under the hidden utility then arrives as feedback.
If u* is the hidden utility, xt* is the agent’s action, and xt is the learner’s recommendation, cumulative regret is
RT = Σt=1T u* · (xt* − xt).
This quantity measures how much hidden utility the recommendations lose relative to the agent’s choices. The theorem controls decision regret. Several utility vectors can produce the same choices, so exact recovery of the hidden vector may remain impossible.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
