- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how to compare non-Markovian tasks represented by reward machines. Different reward machine structures may represent the same task in a given environment. The authors propose STARM, an environment dependent pseudometric. STARM synchronizes two reward machines with the environment. It compares their behavior over feasible history action pairs. It also uses value adjusted advantages and normalization to remove differences caused by potential shaping and positive reward scaling. Experiments test representation invariance. And they also study the relationship between STARM distance, reference policy coverage, and worst case regret.
Critical strengths
- It addresses the limitation of direct automaton comparison. Different reward-machine representations can describe the same task. Some differences only appear on infeasible histories. Comparing reward machines over feasible environment histories is useful and well motivated.
- It connects STARM distance to policy performance. The regret bounds give the distance a clear practical meaning. This is useful when a policy is trained with an approximate or learned reward machine and evaluated with another one.
Critical weaknesses
The rare branch construction shows that STARM distance can become arbitrarily small while worst case regret remains maximal. Should STARM be interpreted as a reference policy weighted task distance rather than a uniform proxy for worst case policy disagreement?
Questions for authors
- In Theorem 1, please clarify why the value-adjusted reward or advantage associated with an individual RM is independent of the other RM used to construct the joint product.
- Lemma 1 relies on a Markovian reward-equivalence characterization. Could the authors explicitly state which assumptions of that result are required and explain why they hold for the reachable joint product process and the policy classes considered here?
2 comments
Thank you for the detailed response and revisions. My concerns have been largely addressed.
We thank you for your review. We incorporated changes based on your feedback to the uploaded file. To make it easier, you can find changes based on the reviews in blue color. We also left a general comment for all reviewers.
W. Yes, we agree with that reading. We formally state the relevant identity in the general response. STARM has the property that d=2sin(θ/2), with θ the angle between the natural policy gradients of the two reward machines at πref. In the construction of Proposition 2, the rare branch barely changes that gradient. We now state this identity in Section 3.2. In Section 3.4 we use it to explain Proposition 2. For worst-case policy disagreement, Appendix B.10 now notes that the value-range distance dval, the largest difference between the normalized returns of the two machines over all policies, bounds worst-case regret from above with a constant independent of the MDP and machine size.
Q1. Advantage ARi is defined from Ri, πref and the environment. πref depends only on the environment state, the reward of Ri depends only on its own state and the label, and the pair (s,ui) changes without uj. This means that ARi(ht,a) depends on ht only through (st,ui(ht)). The joint product only places both advantages on one state space. We expand on this argument in Appendix B.2.
Q2. Theorem 2.6 from [1] assumes finite states and actions and that every state is reachable, and it orders stationary policies. The reachable product is finite. Its states are reachable by construction. Every stationary product policy runs as a history-dependent policy with the same returns (see Section 3.1), so equivalent machines order these policies identically and the characterization applies. The converse of Lemma 1 telescopes for every history-dependent policy, so it does not use this characterization. We now state so in the proof in Appendix B.1.
[1] Joar Skalse and Alessandro Abate. Misspecification in inverse reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023