为无噪声逆优化提供紧致泛化界，揭示其与强化学习中择优问题的等价性。
Tight Generalization Bounds for Noiseless Inverse Optimization
- 基于观测数据推断决策者目标函数，给出高概率泛化误差上界
- 在唯一最优动作条件下，泛化率可达 $O(d/T)$，且对所有一致估计器紧致
- 提出无需调参的低复杂度算法，适用于参数估计与后悔控制场景
逆优化（IO）旨在从观察到的上下文-动作数据中推断决策者的客观目标参数。本文研究无噪声逆优化，其中示范数据由真实目标生成。我们给出了诱导动作集的高概率 $O(d/T)$ 泛化界，其中 $d$ 为未知参数数量，$T$ 为训练数据规模。在确保最优动作唯一性的附加条件下，进一步强化了该保证，使其与多臂赌博机中的最佳动作识别结果相匹配。我们证明 $O(d/T)$ 率在所考虑的所有一致估计器中是紧致的，并将结果扩展至瞬时与累积后悔。值得注意的是，所得后悔下界与对抗设定下的上界一致，表明在此类估计器下，随机逆优化实际上等价于对抗设定。最后，我们提出一种无需调参、每轮复杂度低于通用求解器的算法。实验验证了预测速率并展示了边界的紧致性。
原文摘要 · Abstract (English)
Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context--action data. We study noiseless IO, where demonstrations are generated by a ground-truth objective. We provide a high-probability ${O}(\frac{d}{T})$ generalization bound for the induced action set, where $d$ is the number of unknown parameters and $T$ is the size of the training dataset. We strengthen these guarantees under additional conditions that ensure uniqueness of the chosen action, bringing our IO guarantees in line with best-arm identification results in the bandit literature. We further show that the ${O}(\frac{d}{T})$ rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret. Notably, the resulting regret lower bound matches the corresponding upper bounds in the adversarial setting, indicating that the stochastic IO setting is effectively adversarial for the class of estimators studied here. Finally, we propose a parameter-free algorithm with lower per-iteration complexity than generic solvers. Experiments validate the predicted rates and illustrate the tightness of our bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。