acceptodds
Under review as a conference paper at ICLR 2027

Comparing Non-Markovian Tasks Represented by Reward Machines

Abstract

In reinforcement learning, when reward functions are learned from data, it is useful to be able to make quantitative comparisons of reward functions. The overwhelming majority of work on metrics for comparing reward functions is focused on cases where the rewards are Markovian. On the other hand, temporally extended tasks whose rewards depend on history, where the agent has to accomplish multiple steps in a correct order, are non-Markovian. A popular way of formalising non-Markovian reward functions is by using reward machines, a type of deterministic finite automaton. Building on existing work for Markovian reward functions, we introduce a family of environment-dependent pseudometrics for comparing reward machines. We compare rewards over a common space of feasible histories, making the comparisons consistent across different representations of the same task. We show zero distance coincides with task equivalence, and we establish policy regret bounds for reward machines of bounded size. Our experiments demonstrate invariance of our method to reward machine representations. Our method provides a basis for evaluating learned reward machines by how well they represent an intended task, rather than how well they reconstruct a particular automaton.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Reward Machines, Metrics, Automata, Reward Functions

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_qCFDOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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

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)d=2\sin(\theta/2), with θ\theta the angle between the natural policy gradients of the two reward machines at πref\pi_{\rm 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 dvald_{\rm val}, 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 ARiA_{\mathcal R_i} is defined from Ri\mathcal R_i, πref\pi_{\rm ref} and the environment. πref\pi_{\rm ref} depends only on the environment state, the reward of Ri\mathcal R_i depends only on its own state and the label, and the pair (s,ui)(s,u_i) changes without uju_j. This means that ARi(ht,a)A_{\mathcal R_i}(h_t,a) depends on hth_t only through (st,ui(ht))(s_t,u_i(h_t)). 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

Thank you for the detailed response and revisions. My concerns have been largely addressed.

Reviewer_7wjiOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes STARM, an environment-dependent pseudometric between reward machines (RMs) that compares the non-Markovian tasks they induce in a fixed MDP. The construction composes the MDP with the two RMs into a synchronized product, on which rewards become Markovian and STARC (Skalse et al., 2024) applies. The key design choice is to weight product state-action pairs by the discounted visitation distribution of a fixed reference policy over histories, which makes the distance consistent across different products and, unlike a uniform weighting, a genuine pseudometric. The main theoretical results are that the distance is zero exactly when the two RMs induce the same ordering over history-dependent policies (Theorem 1); that it bounds worst-case regret from both sides (prop 1); and that, in deterministic environments satisfying label-coverage and anchoring conditions, task equivalence identifies the deshaped minimal RM up to isomorphism and positive scaling (Theorem 2). The experiments verify representation invariance on constructed examples and report rank correlations between the distance and worst-case regret on tabular benchmarks, against a uniform-weight baseline and other distances.

Critical strengths
  1. A clear goal, reached with a clean and correct construction. The paper sets out to build a pseudometric between reward machines that measures differences in the induced task rather than in the automaton, and it delivers: STARM is a genuine pseudometric (its weights come from a history measure fixed independently of the pair being compared, which is exactly what the uniform-weight alternative lacks; the counterexample in Sec. 3.3 is convincing), its zero set coincides with environmental task equivalence (Theorem 1), it is invariant to representation (Fig. 2, left), and it is computable in closed form on the finite product. Theorem 2, which shows that task equivalence identifies the deshaped minimal automaton under coverage and anchoring, with counterexamples showing that each condition is needed, is the most original result and connects the metric to automata learning. This matters for my assessment because the core claims are correct and precisely stated; my reservations are about how much they add over applying STARC to the product, not about their validity.

  2. Theoretically sound and readable despite its density. The authors provide good high-level intuition for each result and state their own limitations (Prop. 2, Discussion) rather than hiding them.

Critical weaknesses
  1. The parts that go beyond “STARC on the synchronized product” are not shown to matter. Composing the RM with the MDP is the standard way to make the problem Markovian; once that is done, STARC applies directly and Prop. 1 is a corollary. The two non-trivial additions are the reference-weighted history measure (which buys the pseudometric property) and Theorem 2. But the experiments do not show that the weighting is useful: pooled over all pairs, the naive uniform-weight baseline d_u, which is not a pseudometric, correlates better with worst-case regret in both environments (Table 1: 0.958 vs 0.921 in Maze, 0.948 vs 0.939 in Office-World, with bootstrap intervals excluding zero). STARM wins only on independently sampled pairs, where both methods correlate poorly (0.4–0.6); on positive-regret pairs even graph edit distance nearly ties it (Table 5), and the uniform raw distance without VAL matches or exceeds it (Table 4). The same picture holds for optimizer regret (Eq. 6), which is what a practitioner would actually care about (Table 4). Theorem 2, in turn, holds only under strong per-pair, per-environment assumptions (deterministic dynamics, label coverage, anchoring).

  2. The regret guarantee is too loose to be meaningful in practice, and the looseness is structural. The constants in Prop. 1 depend on the size bound K and on π_ref, and Prop. 2 shows that U_K grows at least like (γ/p)^{k/2}: the bound is exponentially loose in the number of RM states and in the inverse coverage of the reference policy (Fig. 2, right: d ≈ 10⁻⁶ with Reg = 1). The authors are upfront about this, but the issue is intrinsic to the design: a pair-independent history measure necessarily assigns vanishing weight to deep, rarely visited branches, which are exactly what worst-case regret is driven by, so the property that makes STARM a pseudometric is the property that makes it a weak proxy for regret. This is consequential because the motivating application, bounding the loss from training on a learned RM and deploying on the true one (Eq. 4), is never demonstrated (no experiment uses learned RMs or RL-trained policies), and, as the Discussion acknowledges, computing d requires known dynamics and the ground-truth RM, so it cannot serve as an objective during RM inference; at most it is an evaluation tool for benchmarks with known ground truth.

Questions for authors
  1. The paper targets equivalence as “same ordering over all history-dependent policies”, whereas in practice one mostly cares about (near-)optimal policies. I understand that a weaker target such as “same optimal policy” is incompatible with a sound pseudometric, but this is never explained, and many readers will share the intuition that the target is too strong. Could the authors make this explicit? Relatedly, since the practically relevant quantity is optimizer regret (Eq. 6), could the bound of Prop. 1 be tightened for that target?

  2. Keeping the same equivalence notion, consider d_val(R₁,R₂) = sup_π |J̃₁(π) − J̃₂(π)|, with J̃ the min–max normalized return over the common space of policies (J̃ᵢ(π) = (Jᵢ(π) − min Jᵢ)/rng Jᵢ). This is a pseudometric by construction, representation-invariant, has the same zero set as STARM (via Lemma 1), is computable with LPs of the same size as those of Prop. 3, and, unless I am mistaken, satisfies d_val/5 ≤ Reg ≤ 2·d_val with constants independent of the MDP, the RM sizes and any reference policy (on the pairs of Prop. 2 it stays equal to 1 for all k). What does the L² construction of STARM buy relative to such a distance in the tabular, known-dynamics setting studied here?

4 comments

Thank you for the detailed review. You can find the changes addressing the reviews in the revised file in blue color. We also state them here, and we left a general comment for all reviewers.

Before answering the questions and addressing the weaknesses, we have two remarks.

Ground-truth. dd compares any two machines. It needs access to the ground truth reward machine only when we want to compare against it. The same goes for STARC and Markovian reward functions. In the Discussion we mention distances between hypotheses, which do not use ground truth RMs, as future work, and we adjusted its wording accordingly.

Known dynamics. It is correct that dd requires known dynamics. This is standard in theoretical work on comparing Markovian reward functions. This is STARC's setting, where canonicalizations receive the transition function as input. DARD and your dvald_{\rm val} use the dynamics as well. Every distance with two-sided regret bounds depends on the dynamics, since its zero set is task equivalence, which depends on the dynamics (as shown in our Figure 1). On the other hand, EPIC does not use the MDP dynamics, but its zero set is then finer than task equivalence, making it bound regret only from above.

W1, W2. We added new results that show that on learned reward machines, the reference policy weighting matters. The new last row of Table 1 (Section 4) uses 1,746 hypotheses of a SAT-based JIRP variant and a DFA learner, with details in Appendix D.5. The Spearman correlation with worst-case regret is 0.917 / 0.810 (Maze / Office-World) for dd against 0.647 / 0.608 for dud_{\rm u}. With the left side of Equation 4 (which is one of the two terms of the optimizer regret Regopt\mathrm{Reg}_{\rm opt} you mention), it is 0.765 / 0.759 against 0.608 / 0.672. With the true return lost by taking five natural policy gradient steps on the learned machine instead of the true one, it is 0.772 / 0.753 against 0.688 / 0.681. With both learners together, all intervals for the difference exclude zero (bootstrap over runs). Per learner, three of 16 intervals include zero, for learner 2 with worst-case regret in both environments and for learner 1 with the five-step natural policy gradient target in environment Maze (Appendix D.5). In the benchmark rows we show in Table 1, the two machines of a perturbation or interpolation pair have the same transitions, so their joint product is the product of either machine. For hypotheses with positive worst-case regret, the joint product with the true machine has a median of 1.92 / 2.29 times as many states as the true machine's product.

Raw distance (Table 4). Between dd and draw,ud_{\rm raw,u}, Table 4 changes the weights and VAL. With fixed weights, omitting VAL lowers every correlation in Table 4, for dd against drawd_{\rm raw} (+0.022 / +0.019 with worst-case regret, intervals excluding zero, Table 6) and for dud_{\rm u} against draw,ud_{\rm raw,u}. The lead of draw,ud_{\rm raw,u} over dd comes with the uniform weights, as for dud_{\rm u}. Under deterministic dynamics and anchoring, the raw distances have the zero set of dd (Corollary 1). When rewards also depend on environment states, they are 1.15 to 1.46 on task-equivalent machines that differ by shaping, where d=0d=0 (Table 2).

W2, looseness. We agree that a fixed history measure gives deep, rarely visited branches little weight. We formalize this in our Proposition 2. The pseudometric property comes from comparing all machines on one common space. Notice that the suggested dvald_{\rm val} also compares them on a common space, the policies. Appendix B.10 shows Reg≤2dval\mathrm{Reg}\le2d_{\rm val} with a constant independent of the MDP and machine size. So being a pseudometric does not force the dependence on machine size. The upper constant of Proposition 1 depends on machine size because STARM averages over histories under πref\pi_{\rm ref}, as Section 3.4 explains for the pairs of Proposition 2. This averaging gives the gradient identity of Section 3.2.

GED (Table 5). Over all families in Table 5, GED nearly ties STARM on positive-regret pairs. That subset removes the 228 / 183 task-equivalent pairs, which include all task-preserving pairs. STARM is zero there by Theorem 1, and GED is positive on 223 / 181 of them because it counts automaton edits (more in Appendix D.3). The comparison on positive-regret pairs leaves out the pairs that test representation invariance.

Theorem 2. With a condition on the environment, label coverage and anchoring hold for every pair of reward machines that self-loop on empty labels (Appendix C.3, also see our answer to Reviewer bnxL, Q2).

Q1. We have Regopt≤Reg\mathrm{Reg}_{\rm opt}\le\mathrm{Reg}, which is covered by Proposition 1. Its constant cannot be independent of KK, since the pairs of Proposition 2 have Regopt=3/4\mathrm{Reg}_{\rm opt}=3/4 for every kk while d→0d\to0. There is no pseudometric that bounds Regopt\mathrm{Reg}_{\rm opt} from both sides. Take the example of rewards for four possible actions, R1=(1,1−ϵ,0,0)R_1=(1,1-\epsilon,0,0), R2=(1−ϵ,1,1−ϵ,0)R_2=(1-\epsilon,1,1-\epsilon,0) and R3=(0,1−ϵ,1,0)R_3=(0,1-\epsilon,1,0). Then Regopt(R1,R2)=Regopt(R2,R3)=ϵ\mathrm{Reg}_{\rm opt}(R_1,R_2)=\mathrm{Reg}_{\rm opt}(R_2,R_3)=\epsilon while Regopt(R1,R3)=1\mathrm{Reg}_{\rm opt}(R_1,R_3)=1. Bounds lδ≤Regopt≤uδl\delta\le\mathrm{Reg}_{\rm opt}\le u\delta for a pseudometric δ\delta would give 1/u≤δ(R1,R3)≤2ϵ/l1/u\le\delta(R_1,R_3)\le2\epsilon/l for every ϵ>0\epsilon>0. We mention all of this in Section 3.4.

Q2. The distance dvald_{\rm val} compares the two tasks over all policies. STARM compares how the two machines would change πref\pi_{\rm ref}. With θ\theta the angle between their natural policy gradients at πref\pi_{\rm ref}, we have cos⁡θ=1−d2/2\cos\theta=1-d^2/2. If we take a small natural policy gradient step for one RM, the other RM's return improves about cos⁡θ\cos\theta times as much as it would from its own step of the same size (in the Fisher metric). When d>2d>\sqrt2, the return gets worse. This holds for machines of any size (Section 3.2). STARM also keeps the construction of STARC. It canonicalizes each reward with VAL, normalizes it, and takes a norm of the difference. It only evaluates πref\pi_{\rm ref}.

Following your question, we added dvald_{\rm val} as a baseline. We define it in Appendix B.10 and report it in Tables 4 and 8. On all learned machines and the targets of W1, W2 above, dvald_{\rm val} correlates at 0.729 / 0.661 with the five-step target, against 0.772 / 0.753 for dd. Both intervals for the difference exclude zero (bootstrap over runs). After 20 steps and for the left side of Equation 4, dd is higher in Office-World (0.771 against 0.697, and 0.759 against 0.685), with intervals excluding zero, and the two tie in Maze. The left side of Equation 4 does not involve training from πref\pi_{\rm ref}. On worst-case regret, dvald_{\rm val} is higher by about 0.01, and the intervals for the difference include zero. Over all benchmark pairs, whose targets are Reg\mathrm{Reg} and Regopt\mathrm{Reg}_{\rm opt}, dvald_{\rm val} has the higher correlation.

After the joint products are built, dd takes 7 seconds for all 2,420 benchmark pairs on one CPU thread (three linear systems per pair), while dvald_{\rm val} takes 119 seconds (six planning problems per pair, as explained in Appendix D.3).

Thank you for the detailed response and the new experiments. Three points are settled for me. The learned-machine study is a real improvement and shows that a representation-consistent distance is needed (dud_u falls to 0.647 / 0.608 on Reg\mathrm{Reg}). The argument that no pseudometric bounds optimizer regret from both sides answers Q1. And you are right about W2: being a pseudometric does not force the dependence on machine size, as dvald_{\mathrm{val}} shows. I withdraw that sentence.

I am keeping my rating. The revision is better than the submission, but the paper now contains a simpler distance with stronger regret guarantees than STARM and the best correlation with its primary target, and the main text does not say so. Addressing that means reorganizing the paper rather than adding to it, which cannot be assessed in this round. Since there is no time left for another exchange, please read the rest as suggestions for the next version.

Why I raised dvald_{\mathrm{val}}. My Q2 asked what STARM buys relative to it, and you answered the question as posed. I should have been more explicit. I did not mean dvald_{\mathrm{val}} as a rival for STARM to be defended against. I suggested it because it appeared to solve the problem this paper sets for itself, and I hoped the paper would use it. Both distances belong to your paper now. The question is not which of them wins, but what the best way is to compare reward machines by the tasks they induce.

What the revision shows.

  1. Theory. dvald_{\mathrm{val}} is a pseudometric with the same zero set as STARM (your B.10), is representation-invariant by construction, needs no reference policy, and satisfies dval≤Reg≤2dvald_{\mathrm{val}} \le \mathrm{Reg} \le 2 d_{\mathrm{val}} for every MDP and every pair of reward machines of any size, with both constants tight (B.10 states only the upper bound, though). So dvald_{\mathrm{val}} is worst-case regret up to a factor of two. For STARM, Prop. 2 rules out any size-independent constant.
  2. Experiments. On the target the paper calls primary, dvald_{\mathrm{val}} has the highest correlation of all distances in Table 4 (0.982 / 0.979, against 0.921 / 0.939 for STARM, intervals excluding zero, higher in all eight family cells), and also the highest with optimizer regret. On learned machines it matches STARM on Reg\mathrm{Reg} (0.928 / 0.819 against 0.917 / 0.810, Table 8).

Where it sits in the current version. dvald_{\mathrm{val}} is defined in the last subsection of Appendix B, mentioned in one sentence of Sec. 3.4 that states none of these properties, and absent from Table 1, which still compares STARM only with dud_u. The limitations report the non-uniformity in machine size without saying that it is avoidable, and the Discussion proposes scaling to very large machines, the regime where STARM's constant degrades and that of dvald_{\mathrm{val}} does not. A reader of the main text would not learn that the paper contains a distance with size-independent, two-sided regret guarantees.

I think this undersells your own work. STARM has merits that dvald_{\mathrm{val}} lacks, and your response makes them clearer: it only evaluates πref\pi_{\mathrm{ref}} (three linear systems, no planning), it has the natural-gradient interpretation of Sec. 3.2, and on learned machines it correlates better with NPG 5 and, in Office-World, with Eq. 4 and NPG 20. Those are reasons to present the two as complementary. As you point out, both obtain the pseudometric property by comparing machines on a common space: histories for STARM, policies for dvald_{\mathrm{val}}. That is the unifying idea.

Suggestions for the next version.

  1. State the two-sided bound for dvald_{\mathrm{val}} as a proposition in the main text, next to Props. 1–2.
  2. Report dvald_{\mathrm{val}} in the main results table, and say plainly which distance tracks which target.
  3. Organize the paper around the common-space idea, with a global, regret-calibrated distance and a local, evaluation-only one, and with Prop. 2 stating exactly what the cheaper one gives up. Give guidance on when to use each, and update the abstract, limitations and discussion accordingly.
  4. Investigate why STARM is ahead on the deployment targets in Office-World. If STARM is the better choice for evaluating learned hypotheses, that is a valuable finding, and the paper should explain when and why.

I believe that would be a stronger paper than one about STARM alone.

Thank you for the follow-up and for the confirmation that most of your earlier concerns are settled.

We agree that we could present dvald_{\rm val} more prominently in the main text. We want to emphasize that we disagree with three points you made in your response.

1. The correlation with Reg\mathrm{Reg} is built into dvald_{\rm val}. The theory and experiment items of your comment state the same fact.

2. dvald_{\rm val} is more expensive. In short, computation takes the same kind of global optimization as directly computing Reg\mathrm{Reg}. The paper already includes an experiment showing that it is much slower than STARM. This was with known dynamics. Without the dynamics, we are convinced this gap in performance would grow. For NN reward machines STARM needs NN evaluations of πref\pi_{\rm ref} on one shared set of rollouts, while dvald_{\rm val} needs N(N+1)N(N+1) RL problem optimizations. The upper bound only works for exact solutions of the optimizations. If we miss the maximizing policy, we would unknowingly get a smaller dvald_{\rm val}. In [2], STARC authors call evaluating a learned reward by optimizing unsatisfactory. It is costly and it is difficult to separate optimizer failures from reward errors. Earlier in your review, you noted that computing dd requires known dynamics, so it is at most an evaluation tool. Clearly, dvald_{\rm val} requires known dynamics as well, along with global optimization. We expect STARM to scale better and therefore think it is the correct choice for the paper's main focus. We did not run experiments based around estimation. We will keep this stated as future work.

3. The remaining concern is easily fixable. We appreciate the suggestions. We will address the valid points in the camera-ready version. In particular, stating the two-sided bound as a proposition and adding dvald_{\rm val} to Table 1, together with the limitations update. Apart from a short proof of the lower bound, every result in these edits is already in the revision you saw.

[2] Joar Skalse, Lucy Farnik, Sumeet Ramesh Motwani, Erik Jenner, Adam Gleave, and Alessandro Abate. STARC: A general framework for quantifying differences between reward functions. ICLR, 2024

Reviewer_bnxLOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper extends the STARC (Standardized Reward Comparison) framework of Skalse et al. to non-Markovian rewards represented by deterministic finite-state reward machines. STARC compares reward functions by canonicalizing and normalizing them to remove differences due to policy order preserving transformations such as positive scaling, potential-based reward shaping, and next-state redistribution. The proposed extension STARM (STARC for RMs) uses a common history distribution to make comparisons independent of the chosen reward-machine representation.

The theoretical results are the following: 1) zero distance in terms of task equivalence, 2) upper and lower bounds on normalized worst-case regret over reward machines of bounded size, and 3) sufficient conditions under which task equivalence "determines" reward-machine structure. The paper provides an example showing that uniform weighting d_u can violate the triangle inequality and lead to incorrect pruning in similarity search. The regret correlation experiments show that both STARM and the uniform-weight baseline d_u correlate strongly with worst-case regret; however, d_u achieves higher overall correlation in both Maze and Office-World.

Critical strengths
  • Extending STARC to reward machines is well motivated and appears novel.
  • The common-history construction addresses a key consistency problem when comparing machines with different representations. The counterexample nicely connects this problem to incorrect pruning in similarity search.
  • The theoretical development is sound. Theorem 1 and Proposition 1 provide useful equivalence characterizations and regret guarantees, respectively.
Critical weaknesses
  • The presentation is difficult to follow and assumes considerable familiarity with STARC. I needed to read the original paper to understand the construction and assess the novelty. A more self-contained explanation would help the ICLR audience.
  • The paper should more clearly distinguish which results follow from applying STARC to a fixed synchronized product and which require new arguments, particularly for the common-history construction and uniform bounded-size regret guarantees.
  • Although the paper discusses the correlation differences between STARM and d_u, the experiments do not establish when representation consistency provides a meaningful practical advantage beyond the constructed examples. An evaluation of its benefit in a downstream task would be helpful.
  • Comparison with an established baseline (e.g., DARD adapted to the product construction) would strengthen the paper.
Questions for authors
  1. Can you summarize which results require new arguments beyond applying STARC to the synchronized product?

  2. How restrictive are the assumptions of Theorem 2? Can you give concrete examples of environments and reward machines that satisfy them?

  3. Would it be feasible to compare STARM with DARD adapted to the product construction?

2 comments

We appreciate the effort you put into reviewing our manuscript. Your comments helped us make the contribution more accessible. We address them below, with references to the revised file, where changes responding to reviews are marked in blue. The revision is more self-contained and separates our contribution from existing work more clearly. We also left a general comment for all reviewers.

W1. In the revision of Section 2, we explain each step of STARC. VAL subtracts the reference policy's values, so a shaping potential cancels, and normalization removes positive scaling. Both regret bounds of Proposition 1 come from STARC's results on each product. The general class of STARC metrics moved to Appendix B.4, where the proof of Proposition 1 uses it, and the linear algebra of Section 3.2 moved to Appendix B.2. The introduction now says what is new relative to STARC.

W2 / Q1. Each pair of machines has its own product, so a distance between machines needs one space for all pairs. STARM uses environment histories weighted by ν\nu. STARM inherits from STARC that VAL removes shaping, and the regret bounds for each product. Lemma 1 and Proposition 3 apply known results to the product. We need new arguments for the pseudometric on reward machines (Theorem 1), the constants for bounded size and their failure without the bound (Propositions 1 and 2), and results regarding structural recovery (Theorem 2, Corollary 2). STARC with uniform weights on each pair's product is dud_{\rm u}, which is not a pseudometric. In Section 3.2 we now state what STARM inherits on each fixed product. Lemma 1 and Proposition 3 are now more clear about what existing results they use.

W3. In our data, we see the advantage of STARM where the two RMs are different in their transitions. Their joint product is then larger than either RM's own product. The weights of dud_{\rm u} are different from pair to pair. As we show in Section 4, perturbation and interpolation pairs share their transitions, and dud_{\rm u} does well there. In our experiments, independent-template pairs have the widest range of joint-product sizes (Table 3). STARM has the higher correlation with worst-case regret there. Now we also included learned reward machines, representing the downstream case. For hypotheses with positive worst-case regret, the joint product with the true machine has a median of 1.92 / 2.29 (Maze / Office-World) times as many states as the true machine's product. On all 1,746 learned machines, STARM correlates at 0.917 / 0.810 with worst-case regret, against 0.647 / 0.608 for dud_{\rm u}. With the loss on the true machine of the worst policy that is optimal for the learned machine (left side of Equation 4), it correlates at 0.765 / 0.759, against 0.608 / 0.672. With the true return lost by taking five natural policy gradient steps on the learned machine instead of the true one, it correlates at 0.772 / 0.753, against 0.688 / 0.681. We include all of these numbers in the paper, with more details in Appendix D.5.

W4 / Q3. We ran DARD on the product and added it as a baseline to Table 4. The definition is in Appendix D.3. Here we state some of the results. Its Spearman correlation with worst-case regret is 0.853 / 0.834 (Maze / Office-World), against 0.921 / 0.939 for STARM. With optimizer regret it is 0.805 / 0.784, against 0.819 / 0.859. Its correlations are close to those of the EPIC extension in Table 4 (0.839 / 0.834 and 0.796 / 0.791). Compared to EPIC, DARD evaluates rewards on transitions closer to those the dynamics allow, and STARM already compares the machines only on feasible histories. On the product, DARD pairs the RM state of a successor of one state with the label of a successor of another, which is not a product transition. On such a pair, shaping by RM potentials is not a difference of product potentials. DARD exceeds 0.05 on 68 / 75 of the 120 task-preserving pairs, whereas STARM has a theoretical guarantee (Theorem 1) to get 0 there.

Q2. Among the assumptions of Theorem 2, determinism is the main restriction. Label coverage and anchoring follow from a condition on the environment. Concretely, suppose the agent can move among the unlabeled states forever and reach any of them from any other without visiting a labeled state. Suppose also that labeled states are one step away from the unlabeled states in both directions. Moving among unlabeled states does not change the state of an RM which self-loops when receiving empty labels. From any reachable pair of machine states, the agent can then emit any label and return to the unlabeled states. You can see more details in Appendices C.3 and D.3, including that these conditions hold for Office-World. For the reward machines, deshaping and then minimizing gives reachability and distinguishability without changing the task. Irreversible MDP phases can violate label coverage. Environments in which every state is labeled violate anchoring.

Dear authors, I appreciate the time you took to revise the paper and run the additional experiments. The experiments with learned reward machines address my main concern. –– bnxL

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response for all reviewers

Thank you for the reviews. We uploaded a revision in which changes made to address reviewer concerns are currently in blue. Here we provide some general answers that may interest all of the reviewers.

  1. Experimental results with learned machines. In Section 4, we now compare 1,746 reward machines learned by two SAT-based algorithms with the true reward machines. The results are in the new last row of Table 1, with details in Appendix D.5. With both learners together, our dd correlates more strongly than dud_{\rm u} with worst-case regret, with the loss of the worst policy that is optimal for the learned machine, and with the true return lost by training on the learned machine with natural policy gradient. So when reward machines are learned, STARM is the better guide to how much performance they lose.

  2. Why STARM. In Subsection 3.2 we now include more explanations on choices behind STARM. These mostly concern the relation between our advantage formulation and natural policy gradients. Specifically, consider softmax policies with one logit per history and action, πϵ(a∣ht)∝πref(a∣st)exp⁡(ϵξ(ht,a))\pi_\epsilon(a\mid h_t)\propto\pi_{\rm ref}(a\mid s_t)\exp(\epsilon\xi(h_t,a)) for bounded ξ\xi. The derivative of JiJ_i along ξ\xi is ⟨ARi,ξ⟩ν/(1−γ)\langle A_{\mathcal R_i},\xi\rangle_\nu/(1-\gamma), so the natural gradient of JiJ_i at πref\pi_{\rm ref} is ARi/(1−γ)A_{\mathcal R_i}/(1-\gamma). For nonzero advantages, we have d(R1,R2)=2sin⁡(θ/2)d(\mathcal R_1,\mathcal R_2)=2\sin(\theta/2), with θ\theta being the angle in L2(ν)L_2(\nu) between the natural policy gradients of the two reward machines at πref\pi_{\rm ref}. Also, in Subsection 3.4 we provide additional results on optimizer regret and pseudometrics, and in Appendix B.10 we compare STARM with an alternative distance. This way, STARM extends the notion of comparing learned reward functions to non-Markovian settings while at the same time connecting it to natural policy gradients.

  3. Other changes. In Section 2, we now explain each step of STARC. In Section 3.2 we state what STARM inherits from STARC. The linear algebra of Section 3.2 is moved to Appendix B.2. Appendix C.3 discusses the condition of Theorem 2, giving better intuition about the environment assumptions.

We thank the reviewers once more and summarize what was achieved during the discussion period.

Main changes

  • Learned reward machines. STARM correlates more strongly than the uniform-weight dud_{\rm u} with worst-case regret, with the loss of the worst policy that is optimal for the learned machine, and with the return lost by training with natural policy gradient on the learned machine.
  • Baselines. We added DARD adapted to the product. We also added the value-range distance dvald_{\rm val} (Appendix B.10).
  • Presentation. Section 2 explains each step of STARC. Section 3.2 states what STARM inherits from STARC and adds the identity about the angle between the natural policy gradients at πref\pi_{\rm ref}. Section 3.4 discusses optimizer regret. Appendix C.3 gives more details about environment conditions, which are analyzed for our specific benchmark environments.

Status of the discussion

  • Reviewer bnxL wrote that the learned-machine experiments address their main concern.
  • Reviewer qCFD wrote that their concerns have been largely addressed.
  • Reviewer 7wji considers the experiments with learned reward machines, Q1 and W2 settled. For the rest, see our latest response to their comment.

We would be grateful if the reviewers took the revision into account in their final ratings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.