acceptodds
Under review as a conference paper at ICLR 2027

Exploration-Free Learning Needs an Exact Plug-In: Information Floors and Sharp Regret Constants for Event-Triggered Estimation

Abstract

Exploration is often viewed as the price of learning to act: a policy that simply plugs in its current parameter estimates can fail to gather the information it needs, and in online control of unknown linear systems minimax regret grows as sqrt(T). We study problems with an information floor, meaning that information about the unknown parameters arrives at a rate that no admissible policy can drive to zero, and show that this condition alone is not enough. Our main result is a dichotomy that is invisible in continuous time. Write r for the residual of the learner's plug-in map at the true parameter, i.e. the gap between the threshold it returns there and the optimum of the sampled problem. If r = 0, certainty equivalence attains regret C_Δ log τ + O(1) with an explicit constant; if r ≠ 0, its regret is linear at rate ½ J″_Δ(β*_Δ) r². The natural continuity-corrected map has r = Θ(Δ) and is therefore linearly regretful, so a statistically consistent estimator does not suffice: the map it is plugged into must be consistent for the sampled comparator too. A van Trees bound over shrinking neighborhoods matches C_Δ exactly for every locally consistent policy, one whose regret is o(τ) uniformly on a neighborhood of the truth. So within that class C_Δ is the price of parameter uncertainty rather than an artefact of one algorithm. We also sharpen the underlying discretization theory: the optimal sampled threshold is β*_Δ = β* − 0.5826 σ√Δ − σ²Δ/(8β*) + o(Δ), while the optimal cost rises by exactly λσ²Δ/6 + o(Δ). We instantiate the framework twice, through event-triggered remote estimation over a lossy channel with unknown volatility and loss rate and through repeated sequential testing with unknown noise scale, and the same dichotomy appears in both. All cost functionals come from a deterministic Fredholm solve validated against Monte Carlo: across eight parameter settings the measured regret slope matches C_Δ with ratio 1.00 ± 0.11, and the predicted linear rates of inexact plug-ins are confirmed to within 5%.

Primary area:
learning theory
Keywords:
online learning, regret bounds, certainty equivalence, exploration-free learning, event-triggered estimation, sequential analysis, Fisher information, van Trees inequality, local minimax lower bounds

Reviews

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

The authors consider online learning problems in which exploration is unnecessary because the learner obtains the necessary information regardless of policy employed and provide analytical and experimental results.

Critical strengths

I am not sure this paper has any discernible strengths.

Critical weaknesses

My biggest concern is that I think there is a chance this is (at best) very lightly edited AI output of a low quality as far as human readability is concerned. This is in line with the acknowledgment of the authors that they used AI to draft and edit the paper. Possibly in part as a consequence of this, the paper has the following weaknesses.

W1) The paper is filled with hard to understand jargon, and that goes for all parts of the paper including the introduction. This one might be partly on the responsible parties which have assigned this review to me despite my marginal expertise on the topic and refused to reassign it, but at the very least I would expect an understandable high-level explanation of what the authors are trying to achieve with this paper.

W2) There is zero discussion in the paper of why the particular type of online learning problem studied in this paper might be or become relevant in practice.

W3) I would be very surprised if the technical arguments in the paper hold water, although I probably am not familiar with this area to really judge this.

Questions for authors

Q1) How are the various symbols defined that appear in the introduction?

Q2) Please describe the problem setup better. I gather from the language that it might be some sort of communication network, but it is absolutely not clear to me how it is laid out or what it does.

Q3) Why is the Related Work section in the end of the paper? The usual choice would be to have it at the beginning so it could be more explicitly contrasted with the contributions list.

Q4) What are the 1-3 most significant contributions of the paper? The actual contributions list is over half a page long with seven distinct items and no discernible emphasis.

3 comments
AuthorsOpenReview ↗

Response to Reviewer uqUM

Thank you for the specific questions. Each is addressed in the revision.

AI use. We disclosed AI assistance in full under the ICLR policy, and the revised statement names the AI's main contributions and which proofs have not yet been checked by an independent expert. Every numerical result is produced by the released, seeded code, which regenerates all of them with one command; the solver behind them is validated against independent Monte Carlo. We accept the readability criticism and have rewritten the abstract and introduction.

Q1 (symbols in the introduction). The revised introduction describes every quantity in words before using its symbol; formal statements start in Section 3.

Q2 (setup). A sensor samples a randomly drifting signal at fixed intervals. It decides when to send its current value over a link that drops packets with unknown probability; failed sends are retried at a cost. The receiver is penalised for estimation error. The sensor must learn the signal's volatility and the link's reliability while choosing when to send. A figure is added.

Q3 (Related Work). Moved to Section 2 and contrasted directly with the contributions.

Q4 (main contributions).

  1. Even when information arrives whatever the policy does, plugging consistent estimates into an inexact formula, including the standard first-order correction, gives linear regret.
  2. With the exact formula, regret is logarithmic with an explicit constant, and no locally consistent policy can do better.
  3. Under a standard renewal-rate condition, a sharp characterization of how sampling shifts the optimal threshold and its cost.

W2 (practical relevance). Battery-limited sensors in IoT and networked control operate over lossy links with unknown statistics. Deliberate probing costs energy or accuracy, so it matters to know when probing is unnecessary and which plug-in rule is safe. A motivation paragraph is added.

W3 (technical arguments). Reviewer k2Ek identified two gaps in the proofs. The revision replaces both arguments, with details in our reply to that review. Limitations now states which results are proved in full, which are sketched, and which rest on a numerically verified assumption or a cited renewal-rate condition.

Thank you for the response. Can you please upload a revised version with changes compared to the original submission highlighted. Also, please clarify, what this sentence in the AI statement means: "the proofs in Appendices A.3, A.4, A.7 and A.8 have not been checked by an independent expert" -- have the authors checked these proofs or not?

Overall, I have to say I do not like the overall workflow that is becoming apparent with the thread of reviews and current version of the AI statement. The authors have AI write proofs, one of the reviewers points out flaws, then the authors have AI correct the proofs. It does seem to me as though the authors are mainly prompting the model and outsourcing an overly large proportion of the human work to reviewers.

AuthorsOpenReview ↗

Response to Reviewer uqUM: Highlighted Revisions, AI Use, and Author Verification

Thank you for your follow-up and for raising these important concerns.

Highlighted revision: We have uploaded a revised manuscript with new and substantially rewritten text highlighted in blue relative to the original submission.

AI use and proof verification: We have expanded the AI-use statement on page 9 to disclose Claude's contributions in detail. The authors personally checked the equations, assumptions, and reasoning in the proofs in Appendices A.3, A.4, A.7, and A.8, with AI assistance. This was author-led verification, not independent external review; no external expert has verified these proofs. The cited results from Asmussen (2003) and Borovkov (2013) were checked only through secondary sources.

Research responsibility: We acknowledge that AI contributed substantially to drafting the corrections following Reviewer k2Ek's comments. We recognise that errors in the original submission placed an additional verification burden on reviewers, and we sincerely regret this. We agree that peer review should not substitute for author verification, and we do not expect reviewers to validate AI-drafted proofs on our behalf.

We take full responsibility for the manuscript, its mathematical claims, and any remaining errors. We appreciate your careful scrutiny and the opportunity to address these concerns.

Reviewer_yZStOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

I tried to read the paper very carefully but dont understand the idea and what the paper is about. Also this paper is not my expertise. I am not the learning theory guys.

Critical strengths

No

Critical weaknesses

very hard to understand the paper, the abstract and introduction's contributions going too much detailed that nobody can digest all the single number terms about and meaning of it.

Questions for authors

no

1 comment
AuthorsOpenReview ↗

Response to Reviewer yZSt

Thank you for your time and your candour. We agree the abstract and introduction packed in too many constants. The revision rewrites both in plain language, and the abstract no longer contains numerical constants. Our general comment gives a short summary of the problem and findings.

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

In the abstract, the authors state that they study problems with an information floor, while in Sec. 2 they seem to consider a narrower class of channel transmission problems. It seems that a learner needs to learn the sampling threshold for transmitting messages. The authors propose the CE-Exact algorithm, whose key component seems to be computing a threshold y∗y^* using a Fredholm equation. Theoretically, the authors show that even if the diffusion coefficient σ\sigma of the Wiener process and the per-link erasure probability pp are known, linear regret is inevitable as long as a fixed threshold different from the discrete benchmark is used. In contrast, logarithmic regret can be achieved if an appropriate threshold is used.

Critical strengths

Some numerical experiments are conducted.

Critical weaknesses
  1. Presentation: I have to say that many parts of this work are rather difficult to follow. In particular:
    1. Many important concepts are not well explained or discussed. For instance, “information floor” appears in the title, abstract, and many parts of the introduction, yet it is presented without explanation or discussion in these places. Audience have to consult Definition 4 for its precise definition, but even there, its implications are not discussed or explained.
    2. Why do we need exploration-free learning in the channel transmission problem? This question is not well motivated and is actually not even mentioned in the abstract or introduction. I do not see the connection between the problem considered and the title “Exploration-Free Learning Needs an Exact Plug-In: Information Floors and Sharp Regret Constants for Event-Triggered Estimation”.
    3. Many equations are not well explained or discussed. For example, Eq. (1)–(4) in Sec. 2.
    4. Many sentences seem somewhat odd and are not well explained. For instance, on Line 144, the authors said that “Against the best sampled threshold”. What is meant by “the best sampled threshold”?
  2. Technical innovations: It is unclear to me what the main technical innovations are, as several key techniques seem to have already been investigated in many existing works. For example, [1] has already established a logarithmic regret upper bound for Wiener-process sampling with unknown delay statistics. The use of Fisher information and van Trees inequalities to establish lower bounds can also be found in [2].
  3. Correctness: I found that several key steps in the proofs seem to be problematic. In Appendix B.9, the overshoot constant is supported only by numerical values; it is not established by a rigorous proof. Furthermore, the proof of Lemma 10(a) seems to be incorrect, since twice continuous differentiability, a unique interior minimizer, and positive curvature at that minimizer do not imply strong convexity over the entire compact interval.

[1] Tang et al. Sampling of the Wiener Process for Remote Estimation over a Channel with Unknown Delay Statistics. Mobihoc, 22.

[2] Ziemann et al. On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix. L4DR, 21.

Questions for authors

Please see the weakness part above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer k2Ek

Thank you for the careful reading. Both correctness points were valid. The revision replaces the affected arguments, and we would welcome your check of the new ones.

Lemma 10(a). You are right: a unique interior minimiser with positive curvature there does not give convexity on the whole interval. The lower bound never needed convexity. The revised Lemma 10 proves two weaker facts under the same assumptions:

  • (a) Uniform quadratic growth. g(β,ϑ)=(JΔ(β;ϑ)−JΔ∗(ϑ))/(β−βΔ∗(ϑ))2g(\beta,\vartheta)=(J_\Delta(\beta;\vartheta)-J_{\Delta}^{\ast}(\vartheta))/(\beta-\beta_{\Delta}^{\ast}(\vartheta))^2 extends continuously to the minimiser with value 12JΔ′′(βΔ∗)>0\tfrac12 J_{\Delta}''(\beta_{\Delta}^{\ast})>0 and is positive elsewhere by uniqueness. By compactness, min⁡g=m/2>0\min g = m/2>0 uniformly near ϑ0\vartheta_0. This gives the global regret bound (Eq. (11) of the submission, Eq. (14) of the revision).
  • (b) Local curvature, as before.

The clipping step no longer uses monotonicity. With clipping radius ϵ\epsilon chosen small relative to the radius ϵ0\epsilon_0 of (b), a three-case argument proves a pointwise inequality (Eq. (15) of the revision), which integrates to the local regret bound (Eq. (12) of the submission, Eq. (16) of the revision): inside the clip (b) applies; outside the clip but within ϵ0\epsilon_0, (b) applies with a slightly smaller δ\delta; beyond ϵ0\epsilon_0, (a) gives a gap of at least m2ϵ02\tfrac m2\epsilon_0^2, which exceeds the clipped quadratic. The full proof is in Appendix A.7 and A.8, Step 1.

Appendix B.9. The revision proves Var(O∞)=1/4\mathrm{Var}(\mathcal O_\infty)=1/4 (Proposition 11). For symmetric continuous steps with unit variance and fourth moment μ4\mu_4:

  • Wiener–Hopf pairs the strict ascending with the weak descending ladder height. For a continuous step law the two descending versions coincide, so symmetry gives 1−φ(t)=∣1−χ+(t)∣21-\varphi(t)=|1-\chi_+(t)|^2, with χ+\chi_+ the ladder-height characteristic function.
  • The equilibrium overshoot has characteristic function ψO(t)=(χ+(t)−1)/(itE[H])\psi_{\mathcal O}(t)=(\chi_+(t)-1)/(it \mathbb E[H]), so ∣ψO(t)∣2=(1−φ(t))/(t2E[H]2)|\psi_{\mathcal O}(t)|^2=(1-\varphi(t))/(t^2 \mathbb E[H]^2).
  • Expanding 1−φ(t)=t22−μ4t424+o(t4)1-\varphi(t)=\tfrac{t^2}{2}-\tfrac{\mu_4t^4}{24}+o(t^4): the constant term gives Spitzer's E[H]=1/2\mathbb E[H]=1/\sqrt2, and the t2t^2 term gives Var(O∞)=μ4/12\mathrm{Var}(\mathcal O_\infty)=\mu_4/12, since ∣ψO∣2|\psi_{\mathcal O}|^2 is the characteristic function of the difference of two independent copies.

For Gaussian steps μ4=3\mu_4=3, so v=1/4v=1/4. The numerical table is kept as a check, and a deterministic solve confirms μ4/12\mu_4/12 to six digits for two non-Gaussian step laws. Appendix A.3, Step 2 now also proves that the two-sided exit used in Lemma 1 has this limiting overshoot law.

A correction of our own. While revising we found that Theorem 5(ii) stated the linear rate as 12J′′r2\tfrac12J''r^2, which is only its small-rr approximation. The exact rate is G(r)=JΔ(βΔ∗+r)−JΔ∗G(r)=J_\Delta(\beta_{\Delta}^{\ast}+r)-J_{\Delta}^{\ast}. With G(r)G(r), predicted and measured rates in Instance 1 agree to within 1% (2.202×10−22.202\times10^{-2} vs 2.20×10−22.20\times10^{-2}; 1.501×10−51.501\times10^{-5} vs 1.51×10−51.51\times10^{-5}).

Novelty relative to [1] and [2]. We agree, and Related Work says so: the logarithmic rate for Wiener sampling under unknown statistics is due to Tang et al., and van Trees lower bounds in adaptive control are standard, as in Ziemann & Sandberg. We claim neither. What is new is what a continuous-time analysis cannot see:

  1. Under an information floor, certainty equivalence is logarithmic only when the plug-in map is exact for the sampled comparator. The continuity-corrected map is linearly regretful.
  2. The regret constant CΔC_\Delta, attained without tuning and matched by a local-minimax lower bound.
  3. The sharp expansion of βΔ∗\beta_{\Delta}^{\ast} and of the value gap, under the renewal-rate condition (R) stated in Appendix A.3.

Presentation. "Best sampled threshold" means βΔ∗\beta_{\Delta}^{\ast}, the cost-minimising threshold among policies that can transmit only at sampling times. The revision defines it in words in the introduction, explains Eqs. (1)–(4) term by term, introduces the information floor informally before Definition 4, and motivates exploration-free learning.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers. All three found the paper hard to follow, and we agree. The revision rewrites the abstract and introduction, and we summarize the paper plainly here.

Problem. A sensor watches a randomly drifting signal and checks it at regular intervals. It can send its current reading to a receiver over an unreliable link. Each attempt costs energy, failed attempts are retried, and the receiver is penalized for being out of date. The best rule is "send when the signal has moved more than a threshold since the last delivery". The best threshold depends on two unknowns: how fast the signal moves and how reliable the link is. The sensor must learn both while operating.

Why no exploration. The sensor learns about the signal from every sample and about the link from every transmission, whatever threshold it uses. We call this an "information floor". One then expects "estimate, then plug in" to be optimal, with no deliberate probing.

Main finding. That expectation is only half right. The sensor acts at sampling times, so the threshold it must hit is the optimum of the "sampled" problem, which differs from the textbook continuous-time formula. If the plug-in formula hits the sampled optimum exactly, regret grows logarithmically, with a constant that no locally consistent policy can improve. If the formula is off by any fixed amount, regret grows linearly, although the parameter estimates are consistent. The standard first-order correction is off in this way.

Three contributions. (1) This dichotomy. (2) The regret constant, attained pointwise by certainty equivalence, with a local-minimax lower bound that has the same constant. (3) Under a renewal-rate condition, a sharp expansion of the sampled optimum and its cost.

Changes in the revision.

  • Plain-language abstract and introduction, a motivation paragraph and a problem figure.
  • Contributions reduced to three; Related Work moved to Section 2.
  • Lemma 10 replaced by a version that does not use convexity (thanks to Reviewer k2Ek).
  • A closed-form proof that the overshoot variance is 1/41/4 (new Proposition 11).
  • Theorem 5(ii) restated with the exact linear rate; Appendix A.9 updated.
  • The regularity of the sampled optimum that the proofs use is now an explicit assumption (Assumption 3), verified numerically at every parameter setting.
  • The lower bound's policy class is stated precisely (threshold fixed within each cycle), and its report-count step is proved in full.
  • The proofs of Lemma 1 and Proposition 2 are completed under an explicit renewal-rate condition (R): the overshoot of the Gaussian walk converges to its limit law at an exponential rate. This is a standard property that we cite and support numerically but do not reprove. Given (R), the optimal threshold is located by comparing values against an explicit function, without differentiating an asymptotic remainder.
  • The AI-use statement is updated to cover the revision and states which proofs have not been checked by an independent expert.
  • Theorem 7 now states the leading-order constant only, and Limitations says plainly that the upper bound is pointwise while the lower bound is local-minimax.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.