This is a follow up question from yesterday. $\pi(s) = a_1$ refers to the optimal policy, and $a$ alone refers to non-optimal policies.

This inequality $(P_{a_1} - P_a)(I - \gamma P_{a_1})^{-1}R \geq 0$ (from Ng, Russell 2000) characterizes the solution set $R$, the reward function.

The paper continues to explain that $R$ here is not really unique, because $R=0$ is always a solution. This means that I can have the same reward $R=0$ for multiple policies, including the optimal policy.

So to alleviate this problem, we choose $R$ that optimizes the policy $\pi$. At the same, make any other solution that deviates from $\pi$ (meaning, NOT optimal) be as costly as possible.

Thus, we maximize $\sum \left ( Q^{\pi} (s,a_1) - \max_{a \in A \setminus a_1} Q^\pi (s,a) \right)$.

The second term inside the summation is the 'second best', because it refers to all actions that ARE NOT optimal.

I have two questions:

  1. So, the difference between the two terms is the difference between the best and the second best. What does it mean to 'maximize' the difference?

  2. At the end of the section, there is an optimization problem:

maximize $\sum \min_{a \setminus a_1} \{ (P_{a_1}(i) - P_a(i))(I - \gamma P_{a_1})^{-1}R \} - \lambda |R|_1$

such that $(P_{a_1} - P_a)(I - \gamma P_{a_1})^{-1}R) \geq 0$ and $|R_i| \leq R_{max}$ for $i = 1, 2, \cdots ,N$.

I understand each of the components of the problem EXCEPT for the sudden appearance of the penalty term $-\lambda |R|_1$. What is it for? And why is such a weight needed?


1 Answer 1


The key idea is to find some reward that performs exceptionally well compared to the rest. This is why they "maximise the difference" from the chosen reward to any other reward.

In the summation, remember $Q^\pi(s, a_1)$ gives a quantity for the chosen reward say $R_1$, and $max_{a \in A\setminus a_1}Q^\pi(s, a)$ gives the best value of the same quantity for "other rewards" (rewards induce a policy, which then selects actions). So yes, the difference is between best and second best, and maximise sort of means put a large margin (in reward space) between them.

The $\lambda$ in the LP is a penalty put to ensure exactly the large margin in the maximisation. It is a regularisation term and is useful esp because of the fact that different rewards can give rise to the same policy.

  • $\begingroup$ Thanks for your reply. I do not understand how the penalty term put the margin in the maximization? Can you give an analogy? Actually I am thinking of it as an optimization problem with a constraint. (Well, it really is.) But, I am not sure how to continue. Thanks $\endgroup$
    – cgo
    Dec 2, 2015 at 15:35
  • $\begingroup$ Maybe calling it a margin is slightly confusing. The penalty as used in this case help to have "simple rewards", by essentially decaying the parameters of $R$, the weights. $\endgroup$
    – makokal
    Dec 2, 2015 at 15:45
  • 1
    $\begingroup$ If the answer satisfies you remember to accept it and mark it as such $\endgroup$
    – makokal
    Dec 9, 2015 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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