acceptodds
Under review as a conference paper at ICLR 2027

Auditable Regret for Online Routing with Endogenous Feasible Sets

Abstract

Online routing consumes resources that change which routes remain feasible later. A deployment log can therefore support comparisons among actions on visited states without reconstructing the state trajectory that another policy would have generated. We formalize this distinction through an *auditable regret frontier* with two axes. L0/L1/L2 describe executed-action feedback, same-state candidate audit, and counterfactual-state reconstruction. Conditional on L1, a repayment window controls how long a comparator may carry positive safety pressure before repaying it. We show that unrestricted L1 comparators admit instances in which no algorithm can guarantee both sublinear reward regret and sublinear violation. In a normalized exact decision-time L1 oracle game with strict fallback, the minimax weighted cost is at and for . A CVQ-Routing specialization with exact coefficients supplies the matching-order upper bound. The deployable controller instead uses surrogates, and its pathwise certificate records coefficient mismatch, route-search error, queue drift, and comparator debt. Controlled synthetic and public-data replays probe these terms and the difference between same-state L1 evaluation and own-trajectory L2 replay. The resulting framework makes explicit which comparison objects are supported by an audit interface and how comparator strength changes their attainable cost.

Primary area:
learning theory
Keywords:
online learning, constrained online optimization, policy regret, safe learning, endogenous feasible sets, auditability, routing, resource constraints

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Yx4ZOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The authors seem to try to solve a online routing problem, where the routing selection consumes resources, which alter the available next-step actions. Honestly, I don't quite understand the problem that the authors are trying the solve, but I have a feeling the paper's theoretical depth is enough. I need a simple toy example to understand the scenario and challenges of the invested problem, which the authors do not provide.

Critical strengths

I went through the paper several times and admire two things from the authors: (1) the theretical depth, although I don't fully understand the paper's logical flow; (2) the layout style of the experimental figures

Critical weaknesses

It is really difficult for me to understand the paper, and thus very difficult to judge whether the paper advances state of the art or not. I badly need a simple toy example to explain the motivation of the paper and working scenario.

Questions for authors

I need a simple toy example to understand the scenario, the problem, the challenges of the invested prolem.

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

This paper studies online routing with limited resources, where each routing decision earns a reward and consumes the resources over a network. It aims to evaluate online routing performance through comparisons based on recorded deployment data. The main regret metric evaluates alternative routes on the same state trajectory generated by the online algorithm. The paper then proposes a Lagrangian-based routing algorithm and derives regret and constraint violation bounds when the comparator satisfies budget constraints over fixed time windows.

Critical strengths

Studying how to define and use benchmarks that can be evaluated from deployment logs is an interesting research direction. Competing with the offline optimum can be too strong in this setting, and such benchmarks may provide useful guidance for designing controllers.

Critical weaknesses
  • My main concern is the proposed same-state benchmark: the benchmark follows the same state trajectory as the online algorithm. This raises several questions about the benchmark. First, the benchmark's decisions can lead to states different from those generated by the algorithm, so they need not generate the state trajectory on which the benchmark is evaluated. It is therefore quite unclear how useful this benchmark is. More importantly, different policies consume different resources and generate different states. Restricting the comparator to the learner's state trajectory can therefore fail to penalize poor decisions, for example, once the learner depletes a valuable resource, the comparator also loses access to it.

  • The proposed controller in Algorithm 1 basically selects actions that optimize a Lagrangian-adjusted reward. This approach is not new.

  • The paper is poorly presented and is difficult to follow. For example, the problem formulation in Section 3.1 introduces many variables or parameters, such as xtx_t, τt\tau_t, GtopG_t^{op}, Mt(qt)M_t(q_t), and btb_t, without sufficiently clear definitions. The paper also does not provide a sufficiently clear explanation of the L0/L1/L2 hierarchy from the beginning. It takes considerable time to guess the meanings of the variables and concepts.

Questions for authors
  • How is the same-state benchmark justified? Does it provide useful guidance for designing better controllers compared with traditional benchmarks?
  • What are the new ideas behind the proposed algorithm, and what are the main technical challenges in analyzing it?
  • How are the predicted rewards and pressures obtained?
Reviewer_EKYrOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies online routing where executed actions consume resources and change which routes stay feasible. It separates an information axis (L0/L1/L2 audit levels) from a comparator axis. The authors provided theoretical analysis that a minimax frontier of 0 at W=1 and Θ(√(WT)) for W≥2 in an oracle game, and gives a deployable controller (CVQ-Routing) with a pathwise certificate. There are extensive experiments conducted.

Critical strengths

The endogenous-feasibility setting is real and well-motivated. QKD key consumption and inventory residual capacity genuinely make feasible sets path-dependent.

Critical weaknesses

Comparisons are mostly self-ablations. There is no external constrained-online-learning or resource-aware-routing baseline.

Questions for authors
  1. What is measured regret scaling as √(WT) across T and W in the main text?
  2. Could it be possible to provide inferential statistics for the L1-L2 gaps, especially the sign reversal?
  3. How tight is the pathwise certificate in practice?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.