The authors study inverse optimization (IO), where you observe someone's actions and try to figure out what objective function they were optimizing. They focus on the noiseless case—when demonstrations perfectly reflect some ground-truth objective—and prove tight statistical bounds showing you need roughly d/T samples (d parameters, T training examples) to generalize well. They also show this rate can't be beaten and propose a faster algorithm.
Main takeaways:
- Inverse optimization infers the parameters of someone's objective by watching context-action pairs (like watching a chess player and reverse-engineering their evaluation function)
- The generalization error is O(d/T) and this rate is tight—you can't do fundamentally better with any consistent estimator
- When actions are uniquely determined, the guarantees match bandit-style "best arm identification" results
- Surprisingly, the stochastic setting is effectively as hard as the adversarial one for these estimators
- They provide a parameter-free algorithm that's computationally cheaper than generic solvers