Efficient online inverse linear optimization

A learner repeatedly observes which feasible action an expert chooses under an unknown linear objective. The goal is to select good actions while keeping total regret and computation small.

Why it matters and what counts as progress

Why it matters: The result preserves the optimal regret order while making the running time polynomial.

What counts as progress: An algorithm should specify the regret, the running time in dimension and horizon, and how it accesses each round’s feasible set.

How the problem developed

  1. September 2026 · Development [1]

    Shinsaku Sakaue Obtained the optimal order of regret and asked whether it could be achieved in polynomial time.

  2. 6 Oct 2026 · Algorithm [2][3][4]

    Anupam Gupta and colleagues Gave a deterministic polynomial-time algorithm with optimal-order regret.

AI contribution

Optimal and Efficient Online Inverse Optimization

Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff

A deterministic algorithm attains O(d)O(\sqrt{d}) regret for every horizon T in online inverse linear optimization and runs in time polynomial in the dimension d and the horizon T in the paper’s optimization model.

AI involvementAI-autonomous
ImportanceNotable
Technical verificationFormal (Lean + human)
Human understandingFew
Paper date:

Sources

  1. Sakaue’s optimal regret bound and algorithmic question
  2. Original manuscript
  3. Conclusion and AI disclosure
  4. Lean project and target statement
Publication history