Inverse Optimization in Finite-State Continuous-Time Markov Decision Processes

Inverse optimization involves finding parameter values that would render given values of decision variables optimal. Contrast this with the usual (forward) optimization, where optimal values of decision variables are determined using given values of parameters. Inverse optimization has been studied for models such as linear programs, network flow problems, shortest path problems, integer programs, semi-definite programs, and conic programs. It has also been studied in finite-state, discrete-time Markov decision processes (MDPs), to find rewards or transition probabilities that would render a given policy optimal. This paper considers inverse optimization in finite-state continuous-time Markov decision processes (CTMDPs). Unlike the model-free nonparametric version that is prevalent in discrete-time MDPs, we consider a model-based parametric problem here. That is, rewards are characterized using a finite set of parameters. The goal is to find values of these parameters that would make a given policy optimal. In fact, among all such parameter values, we wish to find those that are closest to some given estimates. We use uniformization to write Bellman’s equations of optimality for the forward problem and utilize them to formulate the inverse problem. We computationally illustrate our methodology on a batch manufacturing problem and a queue routing problem.