1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I wasn't sure whether to post this question on cstheorySE or on csSE, please feel free to migrate it if you think it a better fit for csSE. Also, any pointer is welcome :) $\endgroup$ – Charles Jun 25 '12 at 9:17
  • $\begingroup$ Sounds like an interesting variation of the classical reward problem for MDPs. Could you explain what you mean by "in order to get the expected behaviour"? Further, could you be more specific about the setting? That is, are we dealing with memoryless or memoryful behaviours, infinite or finite time horizon, ...? $\endgroup$ – Markus Jun 25 '12 at 15:50
  • $\begingroup$ @Markus: I just edited the question to be a bit more specific, does it help? About memory, I can assume that the state stores the information about the past, and I work with finite horizon (although results with infinite horizon are also interesting!). $\endgroup$ – Charles Jun 25 '12 at 18:34
1
$\begingroup$

You might want to have a look at Inverse Reinforcement Learning. IRL tries to infer a reward function given observed optimal behavior in some MDP. I believe the framework was originally described in the 1998 paper Learning agents for uncertain environments by Stuart Russel. This paper and and those that cite it should be a good place to start, assuming IRL is a good fit for your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.