<p>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 <a href="http://www.eecs.berkeley.edu/~russell/papers/colt98-uncertainty.pdf" rel="nofollow">Learning agents for uncertain environments</a> 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.</p>

CC BY-SA 3.0
2012-06-26T10:33:59.660Z
I've just finished reading: [Andrew Y. Ng and Stuart J. Russell. 2000. Algorithms for Inverse Reinforcement Learning. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML '00), Pat Langley (Ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 663-670.](http://dl.acm.org/citation.cfm?id=657801), and that's definitely a good fit for my problem, thanks!
Charles
CC BY-SA 3.0
2012-06-25T14:43:08.103Z
2012-06-25T14:43:08.103Z
alto
<p>I've been able to model a particular decision problem as a
<a href="http://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow">Markov Decision Process</a>, 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.</p>

<p>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? </p>

<p>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. </p>

<p>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. </p>

<p>EDIT: Give a bit more details following Markus' comment</p>

<p>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, <em>after</em> executing an action in a state, I know in which state the system is. I also consider working at a finite horizon $n$. </p>

<p>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. </p>

<ul>
<li><p>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$? </p></li>
<li><p>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? </p></li>
<li><p>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? </p></li>
</ul>

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

CC BY-SA 3.0
2012-06-25T09:17:00.297Z
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 :)
Charles
CC BY-SA 3.0
2012-06-25T15:50:52.487Z
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, ...?
Markus
CC BY-SA 3.0
2012-06-25T18:34:51.100Z
@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!).
Charles
<ds.algorithms><reference-request><markov-chains>
Inferring optimal utility values from a decision process
Charles
# Inferring optimal utility values from a decision process

(Asked by: username_0 on 2012-06-25)

I've been able to model a particular decision problem as a
[Markov Decision Process](http://en.wikipedia.org/wiki/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 username_1' 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).

**Tags:** ds.algorithms, reference-request, markov-chains

> **Comments:**
> **username_0**: 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 :)  
> **username_1**: 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, ...?  
> **username_0**: @username_1: 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!).  

---

## 1 answers

### Answer by username_2 on 2012-06-25. Score: 1 | Accepted answer

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](http://www.eecs.berkeley.edu/~russell/papers/colt98-uncertainty.pdf) 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.

> **Comments:**
> **username_0**: I've just finished reading: [Andrew Y. Ng and Stuart J. Russell. 2000. Algorithms for Inverse Reinforcement Learning. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML '00), Pat Langley (Ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 663-670.](http://dl.acm.org/citation.cfm?id=657801), and that's definitely a good fit for my problem, thanks!  

---

