acceptodds
Under review as a conference paper at ICLR 2027

Critical Circulations Govern Second-Order Complexity under Dynamic Access

Abstract

First-order sequential-design theory replaces an adaptive policy by its long-run occupation measure. This forgets order. Under dynamic access constraints, where choosing an experiment changes what can be chosen next, order can determine the first unbounded correction to sample complexity. We characterize that correction. The zero-dual-slack edges form a critical graph, whose signed circulations generate a linear space of relative likelihood drifts. With a full-support dual optimum and a strongly connected critical graph, its rank yields a dichotomy: full relative rank permits restoring control and excess, whereas a missing direction with nondegenerate noise forces excess. The criterion is computable by a nullspace and matrix-rank calculation on the first-order critical graph. An exact identity charges every excess sample either to terminal likelihood imbalance or to leaving the critical face. For a first-order-equivalent pair, we sharpen the two regimes to The gap persists in fixed confidence. A second pair keeps the statewise action menus and critical cycle rank fixed but changes the routing; its second-order cost changes again. Optimal frequencies and cycle count are therefore insufficient. What matters is where critical circulations point in relative likelihood space.

Primary area:
learning theory
Keywords:
active hypothesis testing, controlled sensing, second-order asymptotics, equential experimental design, sequential identification

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_16vhOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Not sure! The paper wasn't written clearly enough for me to follow. Even in the abstract there's a lot of undefined notation and unclear claims.

Critical strengths

Not sure! The paper wasn't written clearly enough for me to follow. Even in the abstract there's a lot of undefined notation and unclear claims.

Critical weaknesses

I was unable to follow this paper. Maybe the other reviewers will have more luck! But for me, before I can evaluate this positively, the paper would need to be completely rewritten for clarity.

Questions for authors

Sorry, but due to the clarity issues noted above I can't suggest any concrete questions here.

1 comment
AuthorsOpenReview ↗

Response to 16vh: The problem and contribution through a concrete example

Thank you for pointing out that the difficulty began in the abstract. Optimal sampling frequencies alone do not determine stopping cost: legal routes can allow or prevent correction of random evidence imbalance. We now introduce this distinction through a concrete example, then explain the criterion and policy it leads to.

1. Same frequencies, different stopping costs [W1: Problem and motivation]

We study sequential tests in which choosing an experiment changes which experiments can be performed next—for example, by moving a sensor or reconfiguring an instrument.

Consider two experiments, each supplying evidence against a different alternative. The test needs enough evidence against both. Our matched example has two ways to organize access:

  • Split: two consecutive uses of the same experiment before the next choice.
  • Coupled: one use of each experiment before the next choice.

Both systems have the same observation laws, optimal sampling frequencies, and best average information rate. If one evidence score falls behind, Split can devote the next cycle to it. Coupled's complete cycles always sample both.

For evidence threshold bb, first-order analysis predicts bb divided by that shared rate. The excess is the expected number of observations beyond this prediction. Its optimal value stays bounded in Split but grows on the b\sqrt b scale in Coupled. Routing alone creates this growing penalty.

2. What the criterion tells us to do [W1: Meaning of the main claims]

The general result asks which access systems permit such correction. An exact cost identity identifies two sources of growing excess: evidence accumulated ahead of the weakest score, and information lost along the sampling path.

Edges used by first-order-optimal flows form the critical graph. Its cycles preserve the optimal weighted information rate. The rank test examines their relative evidence drifts: can these legal cycles correct every direction of imbalance?

Under the assumptions of Theorem 4, full rank supplies a correcting cycle for every imbalance. The policy repeats that cycle enough to offset the effect of the connecting paths, achieving O(log⁡b)O(\log b) excess. A missing direction with unavoidable noise instead forces square-root excess even for the best policy. These results also extend to identification without knowing the true hypothesis: one procedure attains the corresponding upper bounds, and the lower bounds cover every procedure meeting the error guarantee.

3. Where the presentation has changed [W1: Abstract, definitions, and organization]

Revision: The revised manuscript now gives the reader the following route:

  • Abstract and introduction (pp. 1–2): explain the sampling problem through Split/Coupled before introducing the technical criterion.
  • Cost and geometry (§3–§4.2, pp. 3–5): explain what causes excess before defining the critical graph; introduce evidence differences and legal cycles before the rank operator.
  • Policy and identification (§4.3, pp. 6–7): state Algorithm 1 and its unknown-truth implementation as executable steps. The new Proposition 1 (p. 3) and Corollary 5 (p. 6) establish the general identification guarantee.

We hope these revisions and the concrete example above make clearer why access constraints matter for stopping costs and what our results establish.

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

This paper studies sequential hypothesis testing when taking an experiment changes which experiments are available next, departing from the idea that every experiment is infinitely repeatable which is already well understood (max-min type of solutions). Authors introduce the idea of random deficit at each timestep and show that these take the form of second order fluctuation on the sample complexity. They further show that they are related to a so-called access graph, and a rank test based on that graph shows whether the fluctuation is in O(log⁡b)O(\log b) or Θ(b)\Theta(\sqrt b). They illustrate it in Section 6 with an applied example.

Critical strengths

The problem posed is sound: it characterizes a second-order term in the sample complexity of hypothesis testing at confidence level bb that are described by random fluctuations due to dynamical access.

Authors further introduce the incidence and evidence matrices on the critical access graph (that contains the first order solutions) whose combination gives a rank test that fully describes the magnitude of the second-order term.

Critical weaknesses

The main weakness is the writing of this paper making this paper particularly hard to follow, a roadmap and more intuition would have been welcome as otherwise this paper reads as a collection of results. In particular, I am still struggling to understand the significance and importantly the practicality of this work (see questions below)

Questions for authors
  • Could authors motivate more why this second-order analysis is needed compared to existing first-order terms in practice? if the test shows that the rank is full, how does that combine with known first order strategies like TaS, can the shown Flex method generalize to it ?
  • For the rank test, it seems to depend on many steps including computing that EioE_i^o. There can be numerical instability, how robust and applicable is the rank test ?
3 comments
AuthorsOpenReview ↗

Response to ycNd Part 1: What second-order analysis changes in sampling design

Thank you very much for asking what second-order analysis changes in practice. It distinguishes first-order-equivalent access architectures and guides evidence-feedback sampling. On the five-state graph, feedback reduces certification excess by 84.9% relative to an optimal-flow tour.

1. Choosing between first-order-equivalent architectures [W1/Q1: Practical significance]

In the Bernoulli example, Split's two-step routes give mean evidence gains (2d,0)(2d,0) or (0,2d)(0,2d); in Coupled, either route gives (d,d)(d,d), with d>0d>0. Both systems have the same experiment laws, optimal frequencies (1/2,1/2)(1/2,1/2), and first-order rate d/2d/2. Yet Split can favor whichever evidence coordinate is lagging; Coupled cannot.

Their optimal certification excesses are respectively O(1)O(1) and Θ(b)\Theta(\sqrt b), where bb is the evidence threshold. First-order optimization gives no preference between these architectures. The rank criterion identifies which routing permits correction of random evidence imbalance.

2. Optimal frequencies do not by themselves remove the loss [Q1: Relation to allocation tracking]

The new Corollary 7 makes this distinction precise on the same Flex graph. There are rr informative actions, each contributing mean evidence dd to its own coordinate, and the optimal frequencies are uniform. For causal policies whose action counts satisfy, almost surely under H0H_0,

$ \sup_{t\ge0}\max_j |N_j(t)-t/r|\le K_b, \ K_b=o(\sqrt b), $

with deterministic KbK_b, we prove E0Tb=rb/d+κrb+o(b)\mathbb E_0T_b=rb/d+\kappa_r\sqrt b+o(\sqrt b), where κr>0\kappa_r>0. Here TbT_b is the certification time. Evidence feedback on that same graph achieves rb/d+O(1)rb/d+O(1).

Thus even exact knowledge of the optimal allocation is insufficient. Removing the square-root loss requires allowing sampling counts to adjust to realized evidence fluctuations, rather than keeping them tightly balanced.

Revision: We have reorganized the introduction around this design question (pp. 1–2) and added Corollary 7 (§5.2, p. 8; proof in Appendix D.5).

3. Combining first-order design with feedback [Q1: TaS and generalizing Flex]

First-order optimization supplies the information target; cycle feedback corrects realized evidence along legal paths. In our finite-hypothesis access model:

  • For each candidate, compute the optimal rate and critical graph (edges used by at least one optimal flow).
  • A pilot selects the candidate controller: cycle feedback when the restoring conditions hold, otherwise optimal-flow sampling. Feedback repeats a correcting cycle enough to compensate for connecting paths.
  • An all-candidate likelihood-ratio rule decides when to stop, regardless of the pilot's choice.

This replaces Flex's coordinatewise freezing by legal cycle control, including when observations update several evidence coordinates at once. Under the full-rank assumptions, Algorithm 1 achieves O(log⁡b)O(\log b) excess while using only critical edges. The unknown-truth procedure counts the pilot and all connecting observations.

Track-and-Stop estimates its optimal allocation target from data [1]; Corollary 7 concerns the fixed target defined above.

Revision: Algorithm 1 and the unknown-truth execution are now explicit in §4.3 (pp. 6–7). The new general transfer in Proposition 1 (p. 3) supplies the identification guarantee.

4. The improvement appears in executed sampling costs [Q1: Practical effect]

The added five-state experiment compares cycle feedback with a deterministic tour realizing an optimal flow. The baseline already knows that flow. Both policies use the same graph, observation laws, stopping threshold, and first-order rate C0⋆=0.2C_0^\star=0.2; each observation updates three evidence coordinates.

At the full-rank setting in Figure 2, under H0H_0 and b=1280b=1280:

QuantityOptimal-flow tourCritical feedback
Excess above b/C0⋆b/C_0^\star221.72±6.15221.72\pm6.1533.39±4.7533.39\pm4.75
Mean terminal imbalance43.9343.936.026.02
Accumulated dual slack0000

The excess falls by 84.9%. The accompanying decrease in imbalance, with zero slack for both policies, shows the mechanism: feedback reduces the waiting cost without changing the first-order benchmark. The intervals are mean ±1.96\pm1.96 Monte Carlo standard errors, using 4,000 trajectories per policy.

The gain also persists without supplying the true hypothesis. With the same pilot and δ\delta-correct stopping rule, at δ=0.01\delta=0.01 under H0H_0, mean total cost falls from 83.0583.05 to 78.4278.42, including about 36 pilot observations. An independent-seed repeat gives 83.0583.05 versus 78.8478.84.

Revision: These general-graph and unknown-truth experiments are added in §6 (pp. 9–10), Figure 2, and Appendix H.1–H.3 (Tables 3–5).

Reference

[1] A. Garivier and E. Kaufmann. Optimal Best Arm Identification with Fixed Confidence. COLT, 2016.

AuthorsOpenReview ↗

Response to ycNd Part 2: Certifying control before exact support recovery

Useful control can be certified before exact support recovery. Your question about the intermediate computations led us to test the full procedure, from the LPs to executed control. In Case C, three-decimal inputs retain ten edges rather than the exact eight, yet still certify a controller with low excess.

1. Computing the support, flow, and dual [Q2: Obtaining the critical edge set]

Let BB be the graph's incidence matrix and DD its mean-evidence matrix. The first-order LP maximizes cc subject to Bw=0Bw=0, 1⊤w=1\mathbf1^\top w=1, w≥0w\ge0, and Dw≥c1Dw\ge c\mathbf1. Write Ci⋆C_i^\star for its optimum. A single optimal flow may omit critical edges, so we solve an additional LP for each edge: maximize wew_e over the optimal face, using Dw≥Ci⋆1Dw\ge C_i^\star\mathbf1. The edge is critical exactly when this maximum is positive.

For numerical inputs, we round DD to pp decimal places, obtaining D~\widetilde D, and compute the optimum C^\widehat C. With LP feasibility tolerance τ\tau, the support LPs use the relaxed constraint D~w≥(C^−10τ)1\widetilde Dw\ge(\widehat C-10\tau)\mathbf1 and retain an edge when its maximum mass exceeds 10−310^{-3}. This produces a candidate subgraph HH.

On HH, a further LP maximizes the minimum edge mass using mixtures of normalized cycles. Rational reconstruction gives a strictly positive flow with exact conservation and normalization. A dual LP proposes evidence weights and a state potential. We enclose each edge's weighted drift plus potential difference in a verified interval. Taking the largest upper endpoint gives a dual-feasible value CUC_U; the lower endpoints then bound the retained edges' slack by εˉ\bar\varepsilon.

Revision: Appendix C.1 (pp. 24–25) now gives the support characterization, the actual LPs and selection thresholds, and the flow and dual constructions.

2. A quantitative guarantee, not just a rank label [Q2: Numerical stability]

For a strongly connected HH containing the initial state, we check an exact rational right inverse on the circulation space. Together with the positive flow and outward bounds on rounding errors, this yields a lower restoring margin η‾\underline\eta. If η‾>0\underline\eta>0, the feasible relative drifts contain a ball around zero: every evidence-imbalance direction can be opposed.

We run cycle feedback using the cycles and connecting paths of this computed HH. With bounded likelihood increments and a verified CU−εˉ>0C_U-\bar\varepsilon>0, the restoring argument and cost identity give

EiTb≤b+Klog⁡(b+2)+K0CU−εˉ\mathbb E_iT_b \le \frac{b+K\log(b+2)+K_0}{C_U-\bar\varepsilon},

where TbT_b is the certification time and K,K0K,K_0 do not depend on the evidence threshold bb. Thus additional near-critical edges have a quantified cost through their slack; they need not be resolved as exactly critical or noncritical before the controller can be certified.

Revision: We added the near-critical performance guarantee (Proposition 18, Appendix C, p. 23), the rational certificate (Lemma 20, p. 25), and their implementation-level explanation in §4.4 (p. 7).

3. From rounded inputs to executed control [Q2: Robustness and applicability]

The new experiment recomputes the support, flow, dual, and certificate from the model. Analytic solutions are used only to assess the outputs, not supplied to the algorithm.

Cases A and C both have eight true critical edges. A has a noncritical-edge slack gap of 0.030.03; C reduces it to 10−510^{-5}. The table uses LP tolerance 10−810^{-8} at three decimal places and 10−1010^{-10} at seven:

Case / decimal placesRetained edgesMargin lower boundSlack upper boundController excess
A / 388.16×10−38.16\times10^{-3}6.70×10−46.70\times10^{-4}31.77±4.6331.77\pm4.63
C / 3106.65×10−36.65\times10^{-3}6.80×10−46.80\times10^{-4}31.33±4.8131.33\pm4.81
C / 788.83×10−38.83\times10^{-3}2.01×10−92.01\times10^{-9}34.76±4.7634.76\pm4.76

Excess is measured above b/C0⋆b/C_0^\star at b=1280b=1280, with C0⋆=0.2C_0^\star=0.2. Each entry uses 4,000 trajectories; intervals are mean ±1.96\pm1.96 Monte Carlo standard errors.

In Case C, the computed flow tour has excess 222.82±6.12222.82\pm6.12, versus 31.33±4.8131.33\pm4.81 for the coarse-precision feedback controller. The gain is already available before the exact eight-edge support is recovered.

The sweep varies offline geometry precision; online likelihood ratios and cycle costs use the specified observation model. LPs and certification take 25–32 ms on these five-state instances.

Revision: §6 (p. 10) and Appendix H.5 report the complete experiment. Table 8 (p. 37) links numerical outputs to performance; Table 9 (p. 38) gives all 36 precision settings, and Table 10 (p. 39) reports the executed controllers and their independent-seed replication.

Thank you again for your feedback.

I thank the authors for their rebuttal which I unfortunately find as difficult to read as the paper itself. I also checked the revisions in introduction and Corollary 7. While the overall problem proposed seems of interest, as a human reader, I see this manuscript as a collection of results with no clear narrative/discussion of the approach/challenges. From my point of view, the current draft is not satisfying and I will keep my score as it is.

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

Based on my understanding, this paper studies sequential hypothesis testing when the experiment available next depends on an access state, in a simplified setting where the ground-truth hypothesis is already known. The stopping rule is also fixed to be the generalized likelihood-ratio test, so that the learning problem reduces to a control problem of stopping as early as possible. This control problem leads to a max-min LP that characterizes the first-order learning rate and the flows across the experiments, which further corresponds to a concept called the "critical graph". The most interesting result seems to be the "rank test" that the authors propose. Simply from the rank of a certain linear operator, one can characterize the residual term's order. In short, being full-rank implies O(log b) and rank deficiency implies \sqrt{b}. Here, b is the scale parameter that roughly translates to \log(1/\delta), where \delta is the error probability tolerance.

Critical strengths

There seem to be some interesting ideas. Second-order efficiency of sequential experiment design is indeed an important problem, especially under availability constraints of experiments.

Critical weaknesses

The paper is very difficult to read. A lot of notation and concepts are used without being properly defined or introduced. (Some of them may be directly adopted from some previous papers but not clearly introduced in this paper.) The English also reads a bit like AI.

It is hard to dive deeper into the technical details because of writing.

Questions for authors
  1. What is proposed policy to achieve the optimal residual order?
  2. For more classic setting in absence of restrictions on experiments, the bounded residual term seems to have appeared in the literature; see [Lalley–Lorden (1986), “A Control Problem Arising in the Sequential Design of Experiments."] and [Lalley (1986), “A First-Passage Problem for a Two-Dimensional Controlled Random Walk.”]. Why does this paper "sharpen" the previous results?
3 comments
AuthorsOpenReview ↗

Response to q8HY Part 1: The sampling policy and its unknown-truth guarantee

Thank you very much for asking us to make the achieving policy explicit. Our answer is a cycle-feedback controller that corrects evidence along legal paths, coupled with a procedure that selects its controller without knowing the truth. The new transfer result carries the rank-based guarantees to identification, including lower bounds for every correct procedure.

1. What the policy actually does [Q1: Achieving policy]

For a fixed candidate hypothesis, the policy observes which evidence coordinates are ahead or behind and chooses a legal cycle whose mean gain opposes that imbalance. Reaching the cycle matters: the connecting paths can initially push the evidence in the wrong direction.

Algorithm 1 handles this by repeating the chosen cycle enough times to cover that effect. It uses critical edges—edges used by some first-order-optimal stationary flow. Fix a root and critical paths to and from each simple critical cycle. At each return to the root:

  • Compute the current evidence differences and the expected drift of each critical edge in that direction.
  • Choose a minimum-mean-drift cycle. Denote its total directional drift by −g<0-g < 0 and the total drift of its two connectors by aa.
  • Follow the outward connector, repeat the cycle 1+⌈max⁡(a,0)/g⌉1+\lceil\max(a,0)/g\rceil times, and return. The expected directional drift of the entire block is then at most −g-g.

At zero imbalance, use a fixed critical closed walk. Update the evidence and test for stopping after every observation, including on connectors.

Under the assumptions of Theorem 4 (bounded increments, a full-support optimal dual multiplier, and strong connectivity of the critical graph), full relative rank supplies a uniform inward drift. The blocks have uniformly bounded lengths, giving O(log⁡b)O(\log b) expected imbalance at certification. Since critical edges incur no dual slack, the cost identity gives EiTb≤b/Ci⋆+O(log⁡b)\mathbb E_iT_b\le b/C_i^\star+O(\log b): TbT_b is the first time all evidence coordinates reach bb, and Ci⋆C_i^\star is the optimal first-order rate. For the noisy deficient-rank regime, optimal-flow sampling attains the matching square-root order.

Revision: The cycle construction is now explicit in Algorithm 1, with its performance argument immediately below (§4.3, pp. 6–7). We also added a five-state experiment implementing this controller with observations that jointly update three evidence coordinates (§6, pp. 9–10; Appendix H.1).

2. Certification and unknown-truth identification [W1: Problem scope and stopping rule]

The identification procedure is not given the truth. We fix ii only to analyze certification: collecting sufficient evidence against every alternative to ii. The new transfer result quantifies the cost of proceeding without this knowledge.

Let Vicert(b)V_i^{\mathrm{cert}}(b) be the optimal certification cost, and Vifc(δ)V_i^{\mathrm{fc}}(\delta) the optimal expected cost under ii among procedures that are δ\delta-correct under every hypothesis. With B=log⁡(1/δ)B=\log(1/\delta), Proposition 1 proves

$ V_i^{\mathrm{cert}}(B)-O(1) \le V_i^{\mathrm{fc}}(\delta) \le V_i^{\mathrm{cert}}(B)+O(\log(B+2)). $

The lower bound covers every δ\delta-correct procedure, regardless of its stopping rule. One procedure, without knowing the truth, attains the upper comparisons for all hypotheses. The transfer assumes a finite strongly connected graph, bounded all-pair log-likelihood increments, mutual absolute continuity, and pairwise distinguishability, but no rank condition.

Revision: The original paper gave unknown-truth consequences for Flex/Lock. Proposition 1 (§2.3, p. 3; Appendix A) is a new general transfer. Corollary 5 (p. 6) applies it to obtain the restoring O(log⁡B)O(\log B) upper bound and the noisy-deficiency Θ(B)\Theta(\sqrt B) optimal excess for unknown-truth identification.

3. How the procedure selects and stops [Q1: Execution without the true hypothesis]

To attain these structural orders, an exploratory closed walk first selects a candidate. We then reset the likelihood ratios and run its controller: cycle feedback when the restoring conditions hold, otherwise optimal-flow sampling. The final test can declare any hypothesis (not just the pilot's candidate) whose log likelihood exceeds every competitor's by B+log⁡rB+\log r, where rr is the number of alternatives. If no decision is reached by a prescribed linear-time cap, the procedure switches back to exploration at a root return, retaining the evidence.

Thus a mistaken pilot choice does not dictate the final decision. The stopping rule guarantees δ\delta-correctness, and the expected pilot cost is O(log⁡(B+2))O(\log(B+2)). All observations count, including those on connecting paths and during fallback. This execution is stated directly after Algorithm 1 (p. 6), with the cost analysis in Appendix A.

AuthorsOpenReview ↗

Response to q8HY Part 2: What access changes in classical restoring control

Restoring control is already present in the classical work you cite [1,2]. What access changes is whether legal routes supply the required corrections at the optimal information rate. Our criterion identifies these directions and, when a missing direction has unavoidable noise, establishes a lower bound for every policy.

1. Why the available experiments are not enough [Q2: Difference from unrestricted control; W1: Intuition]

In our Bernoulli construction, each of two experiments provides mean evidence d>0d>0 against one of two alternatives. Split and Coupled use the same observation laws and offer the same experiments at each state. They also have the same optimal frequencies (1/2,1/2)(1/2,1/2), first-order rate d/2d/2, and cycle count. We change only the destinations of actions:

SplitCoupled
Mean evidence gains over a two-step cycle(2d,0)(2d,0) or (0,2d)(0,2d)(d,d)(d,d) for either cycle
Optimal certification cost at threshold bb2b/d+O(1)2b/d+O(1)2b/d+κ2b+o(b)2b/d+\kappa_2\sqrt b+o(\sqrt b)

Here κ2>0\kappa_2>0 is explicit. When one evidence coordinate falls behind, Split can spend the next cycle sampling that coordinate. Coupled must sample each coordinate once, whichever route it chooses. Its mean correction to the evidence difference is therefore zero.

This is the obstruction created by access: the individual experiments can favor either coordinate, but the legal cycles can cancel those correcting directions. Neither the optimal frequencies nor the number of cycles reveals the difference.

Revision: We now use this existing pair to introduce the problem (p. 1) and explain why the rank test uses relative cycle drifts (§4.2, p. 5). The precise construction and cost separation are in §5.3 (Proposition 8, p. 8).

2. What the rank theorem establishes [Q2: New contribution and relation to bounded residuals]

With one access state, our geometry reduces to the convex hull of the relative drifts of critical experiments, connecting it to freely selectable restoring controls. With dynamic access, flow conservation restricts how those drifts can be combined. The theorem tests the resulting corrections, rather than treating each experiment as independently available.

Under bounded log-likelihood increments, a full-support optimal dual multiplier, and a strongly connected critical graph, Theorem 4 gives two conclusions:

  • Full relative rank means that feasible relative drifts of critical flows contain a neighborhood of zero. Every evidence imbalance can be opposed along legal paths, yielding the controller's O(log⁡b)O(\log b) excess bound.
  • If a missing direction has unavoidable positive critical variance, the optimal excess is Θ(b)\Theta(\sqrt b), with a lower bound covering every causal policy.

The second conclusion also covers policies that leave the critical graph. Noncritical edges may supply a missing correction, but using them incurs dual slack. Our cost identity charges both that information loss and the imbalance left at stopping, so correcting one cannot conceal the cost in the other. This is why the result is an obstruction for all policies, rather than a failure of one particular feedback rule.

As for “sharpen,” the word referred to refining our general bounds in the Flex/Lock example: O(1)O(1) excess for Flex and an explicit square-root coefficient for Lock, not an improvement over classical bounded-residual results.

Revision: We have clarified the single-state connection and the role of legal cycles in §4.2 (p. 5; Appendix B.2, p. 17), expanded the explanation of the all-policy lower bound in §4.3 (p. 7), and made the distinction from classical restoring control explicit in the introduction and Appendix I (pp. 40–41).

We thank you again for your feedback.

References

[1] S. P. Lalley and G. Lorden. A Control Problem Arising in the Sequential Design of Experiments. Annals of Probability, 1986.

[2] S. Lalley. A First-Passage Problem for a Two-Dimensional Controlled Random Walk. Journal of Applied Probability, 1986.

Thank you for the rebuttal. However, I echo with the other reviewer that I find the rebuttal also hard to read. Perhaps this paper is a starting point of a strong piece after it is fully developed. But as is, I find it difficult to recommend acceptance.

P.S. If there is "not an improvement over classical bounded-residual results," then you probably should not say that you have "sharpened" the bound.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.