acceptodds
Under review as a conference paper at ICLR 2027

CoRoute: Certified Inverse Learning from Incomplete Trajectories

Abstract

Inverse reinforcement learning from incomplete trajectories alternates between estimating missing decisions and fitting a policy. Repeating the policy fit can be costly, but reusing a stored policy may become inaccurate as the estimated trajectories change. We introduce CoRoute, a learning procedure that checks when such reuse is justified. For finite deterministic MDPs with an absorbing goal, our main result bounds the loss from reusing a policy inside a two-terminal subgraph when both its completed edge counts and incoming flow change. Using the cached flow, it checks whether reuse meets a chosen error budget without computing the new optimal policy. It allows cycles and inexact caches, and controls both directions of divergence between complete path distributions. When only incoming flow changes, a sharp bound requires just the cached mean path exposure, even if paths can be arbitrarily long. Two supporting certificates check approximate completion and the accuracy of each policy-fitting step. Numerical studies approach the sharp bounds and reduce the cost of accepting shared learning proposals. Refining the reuse bound with one potential step certifies reuse of 275 of 768 caches, up from 234. The implemented outward-rounded acceptance tests certify improvement for the stored record kernels.

Primary area:
reinforcement learning
Keywords:
inverse reinforcement learning, incomplete trajectories, policy reuse, certified learning, flow optimization, KL divergence, cyclic MDPs, variational inference

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_1VY3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops certificates for inverse learning from incomplete trajectories in finite deterministic absorbing MDPs. Its main result bounds the loss incurred by retaining a cached policy within a two-terminal module when both completed counts and incoming throughput change. The guarantee accommodates cyclic modules and inexact caches, and a potential adjustment can tighten the certificate without changing the cached policy. Supporting results certify improvements in the record score and translate a frozen fitting gap into guarantees on complete-path distributions. The experiments investigate certificate sharpness, acceptance cost, and cache retention.

Critical strengths
  • The central certificate can be evaluated using the cached flow and the updated problem, without solving for the updated optimum. It also controls the KL divergence between complete-path distributions in both directions. Its coverage of cyclic modules and inexact caches broadens the scope of the result.

  • The mean-exposure bound is an appealing result. The repeated-loop construction in Appendix H demonstrates sharpness even when path lengths are unbounded. The flow-gap and Bregman decompositions also help clarify where the guarantees come from.

  • The paper distinguishes the behavioral policy from the completion distribution induced by the regularized score, and separately treats block accuracy, record-score improvement, and module reuse. These distinctions help prevent overinterpretation of the certificates.

Critical weaknesses
  • The practical benefit of reuse remains unclear. In the module study, a single refinement step retains only seven additional caches after actual problem changes, while increasing median batch time by approximately 24% relative to warm-started full solving. These results leave the computational value of the proposed reuse mechanism uncertain.

  • The method requires positive feasible flows and two-terminal modules without internal origins. The small real-data pilot does not establish how much of a realistic network satisfies these conditions or how much computational work falls within eligible modules.

  • The reported numerical certificates apply to stored record kernels. Kernel construction, flow feasibility, and Q reconstruction are checked through numerical audits, leaving a gap between certification of the stored-kernel problem and certification of the complete learning pipeline.

  • The results concern a particular, generally unnormalized score. Because alternative score conventions can produce different completion weights, predictive evaluation would help establish why this choice is appropriate for incomplete demonstrations.

Questions for authors
  • Could the module results be broken down by whether completed counts, incoming throughput, or both actually change, and by whether the cache is exact or inexact? A timing breakdown separating refinement cost from the refitting work avoided would also help clarify the practical benefit.

  • In the real-data pilot, what proportion of the eligible flow or fitting cost is covered by the retained modules? How much support is excluded by the acyclic restriction?

  • Could the paper provide a worked numerical error budget for one accepted stored-kernel update, showing the bounds on kernel-construction and reconstruction errors that would be needed to extend the certificate to the ideal objective?

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

The paper works on improving the efficiency of Inverse Reinforcement Learning (IRL) in the setting of incomplete trajectories with deterministic transitions. That could, for example, be a road network and people driving on it. The main goal of IRL is to learn rewards from an observed behavior, such that, under the learned reward, the policy that created the observed behavior makes sense or is optimal. In the setting of incomplete trajectories, the full behavior cannot be observed such that the learning process has to alternate between estimating the missing steps based on the current best guess of the behavioral policy (and consequentially the reward) and then updating the reward estimate. The paper works in the inverse soft-Q-learning setting, in which a single Q-function characterizes both the behavioral policy and the rewards; both of which can be computed from that Q-function. This is where the idea of the paper comes into play. Instead of repeating the policy/reward fitting procedure after every trajectory “recovery” step, in which visitation counts of state-action pairs (called edges, since each can represent, e.g., a chosen road) are estimated, it would be much more efficient to reuse parts of the estimated policy. However, reusing the policy results in growing inaccuracy which requires evaluating whether or not the reuse can be done without paying a high inaccuracy price or if a full re-computation is required. To that end they split the full graph of the MDP, such as the road network, into modules that are subgraphs with one state that serves as the entry and one node that serves as the exit. One can imagine a city block that can be entered from one intersection and exited at another intersection. For each of these modules the estimated policies/rewards can be cached and, potentially, reused depending on the changes that affect this module.

The authors introduce a certificate that bounds the error incurred by reusing the policy of a module under updated estimated edge visits. This allows to specify an error budget one is willing to accept and compare it against the error the certificate attests. Based on this, the decision between reuse and re-computation of the policy for that given module can be made. This certificate is obtained by bounding the error resulting from the updated edge visitation counts under the cached policy while under the constraint that the potentially updated inflow and outflow (e.g., of cars) at every state within that module, and hence also at the entire module, are equal. Further, each state within module has an additive offset that allows to shift its actions' Q-values, uniformly across all actions, up or down. This can be used to make the bound tighter without changing the underlying policy which, in turn, allows to tune that offset before requiring a module policy refit. If the allowed error budget can be achieved by adapting the offset, then a policy refit can be avoided for that module. This certificate is supported by two additional certificates that relate effects of reuse to the global perspective of the entire process. The first one checks whether the next update (that is based on cached policies) does not decrease the training objective. The second one checks whether the next update is close to the best possible fit by evaluating the width of a gap between an upper and a lower bound that the current estimate spans around the optimal estimate. If either of the two global certificates fails, a global refit (that also covers all modules) is triggered. This theory is then tested and evaluated on small synthetic graphs where all their theoretic bounds hold with respect to the numerical results. An additional experiment based on real-world data of the "MOBIS-Covid19" dataset also shows consistent results but under an adjusted setting, such as keeping edge visitation counts constant across fitting steps, which is a special case of the main theorem.

The authors point out that, for some modules, the computation of the certificate might be more expensive than updating the policy, so it is not a guaranteed speedup. Further, they do not claim that their method provides higher-quality predictions than other existing methods. Their main contribution is to establish a way to make a verifiable decision on policy reuse based on the module-level certificate and the two global certificates.

Critical strengths
  1. Providing verifiable decision parameters to reuse parts of the estimated policies is important as it makes decisions on cached-policy reuse tractable and thereby possible under error budgets in a way that heuristic rules cannot provide.
  2. Even though the real-world example is in a restricted setting, it is commendable that they test their theory on real-world data. This is especially noteworthy in a paper that has a strong focus on theory.
  3. I really like that a "result in the paper"-to-"experiment to run" map is included in the README of the provided code.
Critical weaknesses
  1. The notation of the paper makes it difficult to follow the argument. Many objects and variables are never explicitly introduced or defined, but instead mostly enter context through text. While inferring them from the context is possible, this is imprecise and can require re-reading segments with the insights obtained from later paragraphs. Some variable names are overloaded and the object they refer to has to be inferred from the parameters. While this is possible, it hinders clarity, especially in combination with the point above.
  2. A lot of results used in the main paper, e.g., Theorem F.1, are only stated in the appendix. Instead of being supplementary material, the appendix becomes mandatory reading and not just a place where a reader can find proofs and additional details. While it is difficult for theory heavy work to fit everything into the page limit of the conference, there are examples, such as Theorem F.1, where an equation from the appendix is explained in the main text; in those cases the equations should be placed in the main text.
  3. The provided code has some issues that, when resolved, would greatly improve accessibility and reproducibility. The documentation currently lacks version numbers for the required modules; these are important for long-term access to the experiments. Further, the code in its current form is hard to read and understand due to the formatting (no spaces around operators, semicolon-chained expressions, and dense, "space saving" layout) and the lack of docstrings. The formatting issue can easily be resolved by using any autoformatter. Adding docstrings tn functions that are not self-documenting would greatly improve the (future) usability of the code without requiring reverse-engineering of the map between the paper and the code.
Questions for authors
  1. Based on the note of "... the joint full solve is fastest on this small graph ..." in line 1930: Given the overhead of the reuse pipeline (checks, potential refinement, and fallback), is there a threshold, determined by a module’s structure, at which re-solving the module becomes faster than going through the reuse pipeline? Or is the overhead distributed more globally?
  2. Regarding Figure 1: (a) What is special about the dashed purple line compared to the green and yellow estimated edge traversals? (b) The cc and the hh belong to each of the states in the module, is that correct?
  3. Does the context xx carry the data required for count assignment, so that, e.g., a record with a gap contributes counts only to edges consistent with the constraints in that record’s xx? For example, if xx gives the times of the recorded states before and after the gap, would only edges on paths that fill the gap within that time window receive a count?
  4. Was the setting restricted in the real-world example due to it being difficult to find modules with a single entry and exit without internal origins since, in a city, modules with no internal origin seem very difficult to find and, especially in a city center, roads are quite densely connected?
Reviewer_yCXmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper asks when an old policy can be reused while learning from incomplete trajectories. The idea is to bound the error from keeping that policy as the inferred trajectories change, rather than fitting it again each time.

  • The setting is a finite, deterministic graph with an absorbing goal. The main result applies inside subgraphs with one entry, one exit and no internal origins. It bounds fitting loss and changes in the complete-path distribution when both inferred edge counts and incoming flow change, including subgraphs with cycles.
  • Supporting checks handle approximate completion of missing trajectories and the accuracy of the policy fit. The learner optimizes a specified regularized score, which changes the weights assigned to possible missing routes.
  • The experiments validate the bounds and reduce the cost of accepting proposed learning updates.
Critical strengths

Repeatedly fitting a policy to nearly unchanged data can waste computation, so it makes sense to consider the premise in the paper. The strongest contribution is a local guarantee that remains meaningful when cycles allow arbitrarily long trajectories.

  • The reuse bound can be checked without computing the new optimal policy. It also allows an imperfect cached policy. If the old fit is exact and only incoming flow changes, Corollary 5.1 needs just the cached mean path exposure, and the paper proves that this bound is sharp.
  • The guarantees have a clear reference policy: the best policy for the current inferred counts. The paper distinguishes this from recovering the true reward or proving global convergence of learning. That makes the scope fairly clear.
  • The controls in Tables 3–4 use the same proposals and return identical final policies, so the reduced acceptance costs are convincing on these testbeds. Additional ablations with decreasing proposals, inaccurate visit estimates, and independent solvers are helpful.
Critical weaknesses

My main concern is how much the reuse guarantee helps in practice. The local theorem is interesting, but the computational benefit and the availability of suitable subgraphs remain uncertain.

  • Figure 4 holds each module query fixed: refining the reuse check retains more cached policies, but usually takes longer than warm full solving. Table 7 also reports slower cache-based learning, although the learning trajectories and final scores differ, so it is not a comparison at the same final quality. The paper acknowledges these limits. A larger example where reuse reduces total time to the same learning target would make the computational motivation more convincing. The savings from the separate acceptance test do not settle this question.
  • It is unclear how often suitable subgraphs occur in the motivating network. The pilot in Appendix N.5 validates 19 small modules after restricting the network to corridors and removing edges that do not decrease hop distance. It also uses one fixed policy, rather than a learning run. This supports the calculation on the selected modules, but does not show how much of the original cyclic network meets the theorem's conditions, or how often cached policies would remain accurate during learning. The paper treats broader network evaluation as future work; this remains a limit on the demonstrated applicability.
Questions for authors

I would focus on the practical reach of the local guarantee. These questions concern its use in learning, rather than the validity of the bound.

  • Is there a larger learning problem (say inspired by real world settings) where certified reuse reaches the same record-score target faster than full solving, with all checks and fallbacks included?
  • How much of the original network belongs to valid modules before the pilot's forward-edge pruning, and how often would their cached policies pass the reuse check during learning?
1 comment
AuthorsOpenReview ↗

Awaiting Your Feedback on Our Rebuttal

Dear Reviewer yCXm,

Thank you again for your review. As the discussion period is drawing to a close, we would appreciate it if you could take a look at our rebuttal. We would be happy to clarify any points or address any remaining concerns while the discussion is still open.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.