I've been able to model a particular decision problem as a Markov Decision Process, where the optimal policy (i.e. what decision should be taken at each step) is defined in order to optimize a given utility function. Hence, given the utility function and the probabilistic behaviour of the system, I can calculate what actions to take.
I'm interested in knowing if there exists some "reverse" process: if I know the probabilistic behaviour of the system and which action should be taken, can I calculate what the utility values should be in order to get the expected behaviour?
My first guess was to look at Monte-Carlo simulations, where I would set up some (more or less) random utility values, perform some simulations, see if it's consistent with what I would expect, and keep going until I find something satisfactory. But I'm not sure it's converging, and I have the feeling that I'm not the first one to want to do this.
If it helps, the context is security decision mechanisms, where we would know the actual policy for some base cases, the goal being to calculate the utility values for more complex cases.
EDIT: Give a bit more details following Markus' comment
Let us assume I have a set of states $\Sigma$, a set of actions $A$ and a probabilistic transition function $P : \Sigma \times A \times \Sigma \to [0, 1]$. I also have a boolean function that can tell me, given a trace $\sigma_0, a_0, \sigma_1, a_1, \dots, \sigma_n$, if this trace is "good" or not. Note that I assume here that the system is completely observable, i.e, after executing an action in a state, I know in which state the system is. I also consider working at a finite horizon $n$.
The question becomes: how can I calculate a reward function $W : \Sigma \times A \times \Sigma \to U$, where U is a utility domain (e.g. $\mathbb{R}$) such that the optimal policy (i.e. the policy returning the maximum utility for a finite horizon $n$) only outputs "good" traces.
Refinement 1: What if I want to define the utility function only on the states and not on transitions, that is, if I just want to define a function $W : \Sigma \to U$?
Refinement 2: What if I consider that the state consists of some attributes $x_1, \cdots, x_k$, and I want to define a reward function only based on the attributes of the state?
Refinement 3: What if, instead of simply classifying the traces into the good ones, and the bad ones, I can define a partial order over them, can I calculate the reward function that always returns the "best" trace?
I hope this clarifies a bit the question, and although any general results is interesting, I'm also interested in practical approaches, that would provide only an approximation (since calculating the general solution is likely to be intractable in general).
