Summary
_**Edit:** I have read the authors' rebuttal, and they have addressed all the concerns raised in my review._
The paper considers the problem of multi-objective reinforcement learning, when there is an unknown linear preference over the objectives, and approximate preference comparisons can be performed. The goal is to find an optimal policy (according to the true preference) while minimizing the number of comparisons.
The main task is identifying the unknown preference, which the paper shows how to do using Algorithm 1, Algorithm 3, and Theorem 1. Once the preference is (approximately) identified, Theorem 1 shows that solving the RL problem for this approximate preference returns a policy that is competitive with the optimal policy for the true preference.
Additionally, the paper also considers how preference comparisons could be implemented. One option is to ask the user to compare two policies directly, which might be hard to do. Because of this, the paper considers the case when the user can compare trajectories from two policies, which might be more interpretable to the user. To this end, the paper shows how to efficiently find a small (O(k)) weighted set of trajectories such that their weighted values are equal to the value of the policy (Algorithm 2).
Strengths
- The procedure for identification of linear preference is not limited to just RL and can be used in a wider setting, making it of general interest.
- Algorithm 1 adapts to $d \le k$, which could be helpful in cases when there are many redundant objectives.
- The weighted trajectory set representation of a policy is novel, interpretable, and possibly of wider interest.
Weaknesses
- Line 220: “we only need to run Algorithm 1 once for all users”. This seems to be incorrect, as Algorithm 1 uses preference comparisons which depend on the user. This means the leading factor in the bound on line 256 should change from $(k^2+n)$ to $n (k^2 + 1)$.
- The paper assumes the existence of a “do nothing” action, which might require a modified MDP. While this appears straightforward, it seems to me it requires domain-specific knowledge in order to modify it such that the “do nothing” policy has minimal value (which is the true requirement). E.g. in the chess example, perhaps refusing to play is considered a draw, which is better than a loss. Thus, a “do nothing” action would need to somehow always lose.
Questions
- Proof of Lemma 1: in the first inequality, shouldn't it be possible to reduce $k \epsilon$ to $\epsilon$? This would make Lemma 1 applicable to when $\epsilon \le v^\*/(2k)$ rather than $v^*/(2k^2)$.
- Is it possible to approximately estimate $\epsilon$ by comparing $\pi^1$ against a scaled version of itself (similar to the binary search in Algorithm 3)? If $\hat{\epsilon} \approx \epsilon$ can be estimated this way, can Theorem 2 be used with $\delta = k^{5/3} \hat{\epsilon}^{1/3}$, avoiding the problem of having to guess the hyperparameter $\delta$?
- Have you considered the case when the user can compare policy value vectors? In this case, we can query with “artificial” values directly (e.g. basis vectors), requiring no interaction with the MDP at all. Perhaps this makes the problem too simple?
- The preference identification procedure can be extended to general, non-tabular RL case. Is the same true for efficiently finding weighted trajectory sets?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The paper requires that preferences are linear, which is a fairly strong assumption. However, it is a good first step.