Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis

Linear optimization is arguably the most widely used model of decision-making. Inverse linear optimization is its inverse problem, where the goal is to infer linear objective functions from observed outcomes. Since the early development in geographical science (Tarantola, 1988; Burton and Toint, 1992), inverse linear optimization has been an important subject of study (Ahuja and Orlin, 2001; Heuberger, 2004; Chan et al., 2019) and used in various applications, ranging from route recommendation to healthcare (Chan et al., 2023). Inverse linear optimization is particularly interesting when forward linear optimization is a decision-making model of a human agent.1 Then, the linear objective function represents the agent's internal preference. If the agent repeatedly takes an action upon facing a set of feasible actions, inverse linear optimization can be seen as online learning of the agent's internal preference from pairs of the feasible sets and the agent's choices. Bärmann et al. (2017) studied this setting and proposed an elegant approach based on online learning, which is the focus of this paper and is described below. Consider an agent who addresses decision problems of the following linear-optimization form for = 1,...,: maximize