Maximizing the difference between best and second best value functions in reinforcement learning

Question

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?

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.