Outperformance Inverse Optimization: 에이전트 결정보다 우수한 목적 함수 학습

Inverse optimization은 관찰된 결정을 최적 해로 설명하는 목적 함수의 가중치를 추정하며, 다양한 분야에서 사용됩니다. 혼합 정수 선형 계획법(MILPs)의 경우, 기존 방법들은 관찰을 최적 해로 재현하는 것을 목표로 하며, 따라서 관찰이 비최적일 때 절충 가중치(compromise weights)를 학습합니다. 본 논문에서는 아웃퍼포먼스 인버스 옵티마이제이션(outperformance inverse optimization)을 제안하며, 이는 대신 각 상태에서 관찰된 행동보다 모든 구성 요소 측면에서 우수한 최적 해를 유도하는 가중치를 찾습니다. 우리는 순방향 문제 오라클(forward-problem oracles)만으로 평가할 수 있는 손실 함수를 제공하며, 따라서 이를 최소화하기 위한 기울기 기반 및 DC 최적화 알고리즘과 함께 MILPs에 적용 가능합니다. 모든 관찰에서 고유한 아웃퍼포밍 최적 해를 유도하는 가중치에 대해, 새로운 상태에서 그러한 해를 유도하지 못할 확률(일반화 오차)이 관찰 횟수에 반비례하는 양으로 경계 지어지며, 이 경계는 로그 인자를 제외하고 관찰 횟수까지 타이트함(tight)을 증명합니다. 합성 데이터와 실제 데이터를 사용한 실험에서, 제안된 방법들은 기존 방법들보다 행동을 능가하는 해의 예측 성능을 향상시킵니다.