Prediction with expert advice under additive noise
Authors: Alankrita Bhatt
Victoria Kostina
Venue: NeurIPS 2025 poster ()
Keywords: information theory
no-regret
communication constraints
mean squared error
exponential weights
noisy communication
feedback control
Primary area: theory

Abstract: Prediction with expert advice serves as a fundamental model in online learning and sequential decision-making. However, in many real-world settings, this classical model proves insufficient as the feedback available to the decision-maker is often subject to noise, errors, or communication constraints. This paper provides fundamental limits on performance, quantified by the regret, in the case when the feedback is corrupted by an additive noise. Our general analysis achieves sharp regret bounds for canonical examples of such additive noise as the Gaussian distribution, the uniform distribution, and a general noise with a log-concave density. This analysis demonstrates how different noise characteristics affect regret bounds and identifies how the regret fundamentally scales as a function of the properties of the noise distribution.

Prediction with expert advice under additive noise
Alankrita Bhatt Granica Computing, Inc. alankrita. 112@@mail. com
Victoria Kostina California Institute of Technology vkostina@caltech. edu
Abstract
Prediction with expert advice serves as fundamental model in online learning and sequential decision-making However, in many real-world settings, this clas- sical model proves insufficient as the feedback available to the decision-maker is often subject to noise, errors, or communication constraints. This paper provides fundamental limits on performance, quantified by the regret, in the case when the feedback is corrupted by an additive noise. Our general analysis achieves sharp regret bounds for canonical examples of such additive noise as the Gaussian distri- bution, the uniform distribution, and general noise with log-concave density. This analysis demonstrates how different noise characteristics affect regret bounds and identifies how the regret fundamentally scales function of the properties of the noise distribution.
Introduction
The prediction with expert advice framework is cornerstone of online learning and sequential decision-making (CBFH+97 CBL06 16 Ora19]. In this setting, a decision-maker repeatedly selects action a sequence of rounds, leveraging the recommendations of finite collection of "experts." At each round, the decision-maker may choose one expert's action or form a mixture them. After observing the losses incurred by all experts, the learner updates its decision rule to guide future actions. The overarching goal is to ensure that the learner's 's cumulative loss remains close to that of the best single expert in hindsight. Because this framework abstracts broad range of applications in domains such as finance, online advertising, and game playing, it continues to serve as one of the most influential paradigms in online learning.
Despite its simplicity and generality, the classical expert setting assumes the dicission-maees observes exact feedback in the form of the experts' losses. However, this assumption often unrealistic prac- tical environments, where feedback can be noisy, incomplete, or rate-limited. Consider, for instance, autonomous driving: decision-making is constrained by the time and bandwidth needed process sensor data, while the sensory inputs themselves may be corrupted by noise from environmental or hardware factors. Similar challenges arise in financial markets, where imperfect information distorts feedback signals. In such cases, the learner must adapt to uncertainty not only from the environment, represented by the adversarially chosen losses, but also from the noise affecting feedback. This motivates the study of algorithms that can learn effectively under imperfect observations, maintaining robustness while still achieving low regret.
We now formalize the standard prediction with experts framework before extending it to noisy feedback. Let there be experts and time horizon of n rounds. At each round / [n]:
The decision Backer maker selects a probability distribution Pt A m- over the experts, based on all past observations. This can be viewed as assigning a weight to each expert.
The adversary then reveals a loss vector & E = [0, 1]mh, where l, denotes the loss of expert j at round I. The learner's expected loss for that round is (Et-)), G.), i.e. the average loss under the chosen mixture (where (..)) denotes the standard inner product).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

A strategy p thus corresponds to sequence of mappings Pr(-)=-1, with - - A Am11 Given any sequence of outcomes fn (eI....,fuy f.). the learner's regret defined as
Reg(p, (*) == Σ === 1p(c("
min / me
(I)
In words, the regret quantifies how much worse the learner performs compared to the best fixed expert chosen in hindsight-an expert whose identity cannot be known until the sequence ends. The learner's challenge is thus to minimize this gap causally, adapting its choices as it recieves more feedback.
central quantity of interest is the minimax regret, defined as the smallest possible regret achievable by any strategy against the most adversarial sequence of losses:
inf sup Reg(p, E*).
p &m
A classical result (CBFH+97] establishes sharp characterization of this value:
inf sup Reg(p, (*) O( logm).
(2)
p
where the notation (-) hides universal constants independent of n and m. This vn log m scaling represents the optimal rate for learning with expert advice, setting the benchmark for subsequent extensions to more complex feedback models.
We now describe the prediction with noisy expert advice setting, in which the decision-maker does not observe the true expert losses directly, but instead receives a corrupted or partial observation o of the loss vector l,. For instance, Ct might represent a noise-perturbed version of &,, quantized signal produced when the loss is transmitted through a rate-limited communication channel. Formally, the noisy feedback model consists of two components:
Channel: a (possibly stochastic) mapping applied to the sequence of losses, c C + C, where C denotes the output alphabet of the channel. This transformation may depend on the current and past losses and introduces the noise or compression governing the feedback.
Decision rule: at each round, the learner selects a probability distribution (r(c'=1) over experts, based solely on the previously observed channel outputs cf-1.
The central difficulty in this framework lies in the fact that the learner must compete against the best expert with respect the true (uncorrupted) losses l,, despite only observing the degraded signals Accordingly, we define the regret in this setting as
Reg(p, Paje, (*))
Σ
(Elpi(c-11) Ei)
min JE m
Ezjs
where the expectation is taken with respect to the randomness of the channel Paje-
This formulation generalizes the standard prediction-with-expeeee with-experts setup (cf. (T). While the benchmark term (the cumulative loss of the best fixed expert min [em]] Σx= Eej) remains identical, the learner now faces the additional challenge of operating under information degradation. As result, the achievable regret depends not only on the underlying loss sequence and the learner's strategy but also on measure of the channel's fidelity.
While the outlined noisy expert advice setting is quite general, the pnetically-motivateee class of additive-noise channels is of particular interest in this paper. This is subset of the class of channels with memoryless noise, where the o is the output of a fixed known random transformation Paje with input 4. In particular, the output c, l, + Z, where Z; is drawn from some fixed distribution. In this case, we wish to devise a decision strategy p that at time step maps the noisy outputs d² to a decision and achieves low regret defined in (3).
The study of additive noise channels motivated by numerous real-world applications where feedback is corrupted by predictable noise patterns. Gaussian additive noise represents perhaps the most ubiquitous noise model, arising naturally in settings such as sensor networks, where thermal noise in electronic components follows a Gaussian distribution; financial market predictions, where price

---

observations contain normally distributed measurement errors; and healthcare monitoring systems, where physiological measurements are subject to Gaussian instrument noise. Uniform additive noise, on the other hand, is particularly relevant in scenarios involving quantization and digital conversion, such as communication-constaae discretized with limited precision; in crowdsourced data collection where human bias introduces bounded random errors; and in privacy-preservee systems where uniform noise is deliberately added to protect sensitive information while maintaining utility. Both noise models represent fundamental corruption patterns that algorithms must contend with when learning from imperfect feedback, making their theoretical analysis particularly valuable for designing robust decision- makinn systems.
IoT networks where continuous signals must be
2
Main results
Our primary contribution a comprehensive characterization of the fundamental limits of prediction with expert advice under various additive noise channel models. These results also provide practical algorithmic insights for real-world applications where feedback is inherently noisy. particular, our results specialize to the following canonical additive noise models to yield the following results:
Gaussian noise: For Gaussian noise with variance o² (denoted by AWGN(o))
Rog(AWGN(o)) = (v(1
This quantifies how increasing noise variance directly impacts the achievable regret, with a clean dependency the standard deviation.
Uniform noise: When feedback is corrupted by uniform noise distributed in [-o, of (de- noted by AddUnif(a))
Reg Reg(AddUni((()) = (v(++)) logm
(5)
This result particularly interesting as reveals fundamentally different scaling with the noise parameter compared to the Gaussian case. The linear rather than quadratic dependence on a highlights how the shape of the noise distribution just its variance- criticalyy affects learning performance.
Symmetric log-concave noise: Extending beyond specific distributions, we provide bounds for the general class of symmetric log- log-concave noise distributions with variance o² (denoted by Add(fa))
Ω (V(1 (o < ReRe(Adddd/F so (v(1+ log
+
Symmetric log-concave distributions are particularly valuable to study as they encompass many real-world noise models in sensor networks, signal processing, and privacy-preservin systems. In particular, they encompass the previous two examples of Gaussian and Uniform distribution, and also include other noise distributions such as the Laplace (double expo- nential) distribution. This broad class maintains favorable concentration properties while often better modeling the heavier tails observed in practical measurement errors compared to purely Gaussian assumptions, making our bounds widely applicable to realistic noise scenarios. While the characterization (6) is not perfectly tight, it encompasses both previous results special cases: the lower bound is tight for uniform noise, and the upper bound is tight for Gaussian noise.
Our results reveal that as noise intensity increases (a - oc), the regret eventually grows superlinearly with time horizon n, indicating the fundamental impossibility of learning effectively when feedback becomes extremely corrupted. Conversely, our bounds smoothly transition to the classical noiscless case as noise diminishes. These theoretical guarantees are derived through an analysis combining two complementary techniques: (1) enhanced exponential weights algorithm adapted for noisy feed- back, and (2) infornation-theoretic lower bounds that precisely characterize what is fundamentally impossible achieve. In particular, we employ the following two results:
Theorem (informal) For any memoryless feedback channel
log + a n MSEsstiination
Regret S
CK
3

---

where m is the number of experts, T. is the time horizon, a is a learning rate parameter, and MSE estimaattionn represents the mean squared error estimating the true losses from noisy observations.
We note, in particular, that the regret additionally depends on the mean squared error (MSE) ob- tained by the estimator é,, drawing interesting connection between estimation and noisy regret minimization. This result echoes the well-known separation principle in measurement feedback control [SHH0), where optimal control cost can be decomposed into optimal estimation cost fol- lowed by optimal control cost based on the estimates. Our theorem suggests a similar phenomenon in online learning: the performance degradation due noisy feedback can be directly quantified through estimation eπrоr.
Theorem (informal) In memoryless channels
n log m (((e)
Regret 2 Q
where n((Pet) is the strong datc-procssiing constant of the channel-an information-theorelic measure quantifying how well the channel preserves information.
This lower bound demonstrates that the fundamental barrier learning is information-theoreti in nature: as the channel's ability to transmit information degrades (smaller 1)), the minimum achievable regret increases proportionally.
3 Related work
In this section, summarize prior work that relates most closely to the problem studied in this paper. For brevity, we focus only on the works that are most directly connected our setting, and defer more exhaustive literature overview to Appendix A
To our knowledge, the earliest study of prediction with noisy feedback for individual loss sequences f" was by Weissman, Merhav, and Somekh-Baut -aruhhh [WMSB01], following the foundational works of [FMG92 MF98]. Their analysis focused on the case where the losses are corrupted by binary symmetric channel (BSC). They introduced upper bounds and notion of conditional finite-state predictability, and proposed universal prediction schemes that are robust both the choice of the best expert in hindsight and to the unknown channel bias. Subsequent work by Weissman and Merhav [ MO1] generalized these ideas broader class of universal prediction schemes for noisy individual sequences, while [WM04] extended the analysis to noisy prediction of stationary ergodic sources. However, these results do not directly cover additive-noise channels, nor do they establish matching lower bounds on regret. The study in [WM0]] was later extended by Resler and Mansour [RM99] to the adversarial bandit tramework-winee only the loss of the chosen expert is revealed at each round-though though their setting also assumed BSC and is therefore not applicable to additive-noiss noise models.
In recent years, motivated partly by the rise of federated learning as a key paradigm in distributed optimization (M1)+ there has been growing interest in decision-making under communication or rate constraints. Similar questions have been explored in the context of stochastic bandits (HYF22 MHP23 MST23), which also served as inspiration for our work. In these studies, the focus is on quantifying how limited feedback precision affects achievable regret. Specifically, for multi-armed and linear bandit problems, (HYF22) and [MHP23] proposed communication-efficii
algorithms that attain regret comparable to the full-precision case while characterizing the number of bits required to do so. Mayekar et al. [MST23] considered an additional constraint, modeling the feedback channel power-limited limited AWGN link, and derived both achievability and converse bounds showing that the regret deteriorates by multiplicative factor of VI/SNR, where SNR denotes the signal-to-noiss ratio. Their analysis, however, limited to Gaussian channels and relies on a UCB-style algorithm that is not applicable in framework.
In contrast, this paper addresses the inll-informatio (experts) setting with adversarial losses for individual sequences. We establish near-optimal upper and lower bounds on the regret and specialize our results general family of additive-noise channels. Our findings unify and extend several existing results: for instance, in the cases of one-bit per-expert quantization and AWGN noise, our

---

regret bounds coincide (up to constants) with those in [HYF22 MST23] Finally, [BK24] recently investigated prediction with noisy expert advice, but their analysis has notable limitations that our work overcomes. Specifically, we handle both bounded and unbounded loss functions- an essential feature for dealing with additive noise that may have heavy tails. Moreover, whereas their Gaussian lower bound was stated without proof, our result derives it rigorously from unified framework (Theorem 2). Most importantl, our analysis provides tight or near-tight characterizations for a broad range of additive-noise channels, including uniform and symmetric log-concave distributions, which are not captured by their framework.
Upper bounds
In this Section, provide upper bounds for prediction with noisy expert advice with additive noise. To do this, we need to construct a decision-making strategy and prove its performance limits. To this end, consider the following estimator:
EW Pij
(d' x exp
where E is any function f(c)) satisfying Elf(c)) 4. other words, the employed strategy (which we denote by (EE) is simply the landmark exponential weights strategy (CBFH+9) 97 that is known be optimal in sense for the vanilla prediction with expert advice problem [CBL06 used in conjunction with an unbiased estimator for the true loss 4,, with fixed learning rate Unbiasedness of an estimator is an important property in statistical estimation, with several interesting and attractive consequences [LC06] Chapter 2]. In the realm of online learning, one of the prominent examples of the use of unbiased estimator as a proxy for an unknown loss in the celebrated EXP3 algorithm of [ACBFS95].
We state Theorem formally.
Theorem Let the channel Paje be memoryless and let Eo constructed using ct be an unbiased estimator. For any a >> O defining the event
:: (Et. - 2 1},
(8)
Reg(p Pole, 1"))
log m
an 1 + max Elees - -Tn]1² 3.6
V A4m222
(1+ max E(ee -6513) P(E).
We once again point out that the regret depends on the mean squared error (MSE) obtained by the estimator l, drawing interesting connection between estimation and noisy regret minimization. Theorem follows from a "second-order" analysis the exponential weights strategy pew which bounds the regret incurred by EEW in terms of the second moment of the loss functions [CBMS07 GSVE14). It follows the standard idea of constructing potential function and carefully bounding the change in the potential function at each time step, and the full proof is relegated to Appendix B
4.1 Application of Theorem I to canonical channel models
We apply our general upper bound from Theorem I to several important additive noise channels. For each channel model, we develop an appropriate unbiased estimator, calculate its estimation error variance, and determine the resulting regret guarantees by substituting these values into the framework established in Theorem [] Recall that for additive noise channels, the output Cij byy + Zi where all the Zry are independently and identically distributed.
Gaussian noise. Consider a l, Z, where Z ~ (1 o(, r2)). The most natural unbiased estimator to use simply Gt, with MSE El(e, - f,)2) = o². Note that in this case since the noise unbounded -act can be arbitrarily large- but the probability of this event occuring exponentially
5

---

small. In particular, recalling from 8 that the event & is defined as : {3t, -aej 2 1 we note for
log m m(1+03]
n11 + + log
P(E)=
Cij --
(6)
n11 + 0²) log
P
Zzj S
1=1
n11 + o²) log m
x mmP
Znj S
(9)
WV
mn exp
(10)
2 m
where (a) follows by the union bound, (b) follows since Ct -Zú + 45 and S by S 1, and
(c) follows by using that for Z NO x²) the complementary CDF P(Z Z x) S exp(->>/200
Thus, Theorem implies that the strategy paw which sets P: = p FwW (c with learning rate
log m achieves regret
m(l+o")
Reg(EEw AWGN()) (*) 2 (1+ (1 logm o(n).
(1I)
Uniform noise. For additive channels with uniform noise, the channel output Ctj lyj + Z5g where Zij Unif[-o, ol (so that the noise variance is o² /3). Since we are interested in how the regret scales as a increases, it suffices to assume that σ 2 1. Then, consider the following estimator & (which is function of c)):
o + if a oy < -0+1
if ao
(12)
0+1
if <ar
We observe that E[Geg] lij i.e. E, is unbiased and that the MSE for this estimator satisfies ElLe 2, < (full calculations relegated Appendix C
For choice of learning rate
log note that allz 2 -0a -o m11 [1-1)
log n(1+a)
1 for large
enough n. Therefore, if we use the strategy gEW with the unbiased estimator & in Theorem yields
Reg(p Unil(a), S 21 oom log m.
(13)
In Section we show matching lower bound to 13 and establish that the regret must grow as (1 + on log logm) showing the tightness of 13
Symmetric noise with tail constraints. If the additive noise is symmetric, i.e. the distribution of noise and Z is the same, the most natural unbiased estimator for is Eg c₁ (since the noise is additive and 0-mean) which achieves mean-square error E(ct) - l = o² where o² is the
variance of the noise Ztj. In order to apply Theorem with = n( m11+o2) to achieve regret scaling
log m
((v(1 + o²) log m) (as in the AWGN channel setting) we need to establish a bound on (PE). Following the line of reasoning employed to reach (9) we have
P(E) S mnP
n(1 + d²) 2
Zzi S
mnP
πi
2² log m
log m
which implies that a noise density with polynomially decaying tails (in particular for if the random variable Z satisfies for large that P(Z 2 x) < g04e where is positive absolute constant and 0) suffices to achieve regret
2 (1 d2) I m + o(n).
(14)

---

An important class of distributions that achieves this tail condition is log log-concave distribu- tions [SWI4], which are distributions having density f(z) for which the function + log f() is concave. This class has special significance across statistics and information theory and includes distributions such as the Gaussian distribution, the uniform distribution and the Laplace distribution. Since all log-concave distributions are subexponential (i.e. have exponentially decaying tails) these satisfy aforementioned the condition on P(E) as n grows larger. While for the specific cases of Gaussian and Laplace densities, is possible to achieve a matching 22( ((((1 + o²)n log m) lower bound for the regret, the most general lower bound
are able achieve bound of ( (11 + a o log m the regret when the class of noise densities is log-concave. While it might appear that the bound can be strengthened in general, we have seen that this fundamental lower bound can in fact be achieved for uniform noise distributions by constructing a different unbiased estimator that achieves O(v(1 o)n log m) regret.
fundamental lower
Lower bounds
In this section, we establish fundamental lower bounds on the regret max,s Reg(p, Pates (n) for any strategy To this end, need the following definition.
Definition The strong data processing constant of binary-input channel Pyjx is defined as
D(Px o Prix l1Qx o Prix)
m(Prx))= = sup Px#Qx
(15)
[(Px
where Px and Qx are distributions defined on 10,
Intuitively, this measure quantifies interpretation more clear by the alternate representation of nn( ((P)x) (see [PW22 Theorem 33.5))
of "loss of information" in noisy channel-this
Y(U;Y)
7 (Prx) Pox:U-X-- XX
sup
(16)
where U is an auxiliary random variable, and U + X + Y represents a Markov chain. The data processing inequality (CT06) from information theory immediately implies that (7 x) S 1; often, show subsequently,
can establish (Pri)) < 1. There has been much interest in characterizing 77 (Prj) for various channels due numerous applications arising in the domain of PW22 Chapter 33] for detailed survey.
statistical inference- see PW17 Rag16)
Next, we state Theorem 2 formally. This result is stated in BK24 Theorem (without a full proof), and we provide full proof in Appendix D
Theorem If the noise is memoryless and component-wise independent (i.e. Paje = 115= P Peyle, then
log(m/4)
sup Reg(p, Pole, (n))
(17)
16n(Pa4e)
gee
where with some abuse of notation, r/(Pete) (as in Definition 7 restricts the channel binary imput {0, 1).
We now instantiate Theorem 2 for the class of additive noise channels, recalling that for these channels Ctj lyj + Zez for (independent and identically distributed) random variables Zey. To quantify (((a))) we will utilize the following characterization from [PW17 Theorem 21]
Theorem For a binary-input channel Pyxx.
112 (P(( < (((Pi))
(P Prςx=1)
(18)
where H represents the Hellinger divergence between two distributions.
7

---

We can now use this result for the specific noise models we are interested in. Additive white Gaussian noise. If Zzj ~N(0, then (8) implies that 7(AWGN(0)) H² o.
x²
(xr 10-1.
1)2
exp
dx
(19)
2T
2o²
20²
=2 2 - 2e 1/80²
4
(20)
1 1+ 0²
where (20) follows since (1 e 11802) (1 + x S for all Using 20 in Theorem 2 implies that
sup Reg(p, (EC(e), (*) (1 a²) In log(m/4)
(21)
64
matching up to constants the upper bound in
Additive uniform noise. The uniform additive noise channel has the noise Zyj Unif[ /3. In this case Pylx= = Unif[-a, o| with density fo(x) = note that this noise has variance x² r²/3.
1 - S a). and Py|x=1 Unif[
1, 1] with density fi(x) 20 1 +1
2a
13. Let us assume that o 2 1; in this case
n(Uni((o)) < 1/2 [ o. Unill-o 1, +])
1 o+1
dx
(22)
2o -0+1
20
Combining 22 with the trivial bound v yields
((nni((o)) 1
(23)
++1
for all a > O; implying the fundamental lower bound on the regret when the feedback is corrupted with additive uniform noise
on lm4(m/4)
sup Reg(p, BEC((), (*)
(24)
16
matching the upper bound result obtained in up constants.
Additive symmetric, log-concanve noise, So far, in the additive noise examples we have considered (Gaussian and uniform noise), we established that noisy feedback incurs multiplicative cost (over the noiseless case) on the regret that depends on the moments of the noise and this cost strictly greater than 1 (v1 + x² and vI+ respectively). In light of the upper bound result in (14), might hope that for general additive noise channels with mild tail conditions on the noise one can achieve 7((Pcjd 2 (o). Unfortunately, this not the case in snneral-considerr the additive channel y = X Z with noise distribution Z ~ Uniform{ still n((x) = since given Y, X is perfectly known. Therefore, to obtain a more general result, more conditions need to be imposed the noise distribution.
o-]this noise distribution is bounded; but
We will show a lower bound for the general class of symmetric log- concave distributions considered in Section 4.1 which encompasses the Gaussian and uniform distributions considered previously. Consider a log-concave noise distribution with variance o² and let denote its density. Then,
(Prix) < H Pr)
(P x Pr(x=1)
[f(=) - f(=
(25)
where (a) follows from the well known inequality H² < 2TV between Hellinger and total variation distances, and (b) follows from the definition of the total variation distance (and, the fact that the density of Y|X is f(z 1)). Next, we further simplify (25) using the symmetry and unimodality

---

of f (since any log lon-concave distribution is also unimodal). Since f() is decreasing for 2 2 0 and
f(z -- is increasing for < for any 2 S 2. we have f(z 1) 1(1/2) f(z)
and similarly for 2z)(2) S f(z 1). Therefore,
f
00
1/2
/ L (f(2 1) f(=))ds
[f(z) f(2 1))d2 (f(z) f(z 1))d2 f(2-1))dz+ +
1122
(f(z 1) -f(=))dz
(26)
1/2
f(z -1)de L f(2)dz
=
1/2
1/2
f(2)dz - S f(2)dz)
=
1/2
1/2
2 2
[())dz
1/2
VA
(27)
where 27 is due to the following proposition, proof of which is provided in Appendix E
Proposition 1 For a symmetric, log-concave distribution with variance o², its density satisfies f(z) p
Putting together 27 and 25 along with the trivial bound 1 S see that for any additive noise
channel with symmetric, conccceevee density
8
m(Prpx) (1+
(28)
This furthermore implies in the experts problem that feedback is available with additive noise Cej Eij + Zij where Zij is symmetric and log-concave, then
o log(m/4)
sup Reg(p, BEC(e),
(29)
128
It is interesting to note that the lower bound in 29 is not tight in general. This is true in particular for Gaussian noise and Laplace (double exponential) additive noise-for for both, we can establish a VI+ x² scaling by direct computation of (Py 11)x=1) Nonetheless, it tight for uniform noise, which log-concave distribution, is tight in the sense that it cannot be improved without imposed further restrictions on the class of noise densities.
have shown matching upper bound in (13) Thus,
6 Discussion
This paper provides a comprehensive framework for prediction with expert advice under additive noise feedback, establishing tight regret bounds for Gaussian, uniform and Laplace noise, and nearly-tight bounds for the broader class of symmetric log-concave distributions. Our analysis reveals important differences in how noise characteristies affect learning performance-will regret penalties scaling quadratically with standard deviation for Gaussian noise but only linearly for uniform noise. We identify the strong data processinn coefficient as a critical measure characterizing how channel degradation impacts regret bounds. Important future directions include developing high-probabilityy guarantees beyond expected regret analysis for risk-sensitive applications, and extending our framework to alternative loss functions beyond linear losses and to infinite expert cuxses--onnectiinn this work broader statistical learning theory through concepts like Rademacher complexity under noisy observations.

---

References
[AAK*20] Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33:14315514325, 2020.
[ACBFS95] Peter Auer, Nicolo Cesa-Biancia Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 322 -31, 1995.
[ACL*21] Jayadev Acharya, Clément L Canonne, Yuhan Liu, Ziteng Sun, and Himanshu Tyagi. Interactive inference under information constraints, IEEE Transactions on Information Theory, 68(1):502-516, 2021.
[ACT20a] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi. Inference under informa- tion constraints I: Lower bounds from chi-square contraction. IEEE Transactions Information Theory, 66(12);7835-7855 2020.
[ACT20b] Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi. Inference under in- formation constraints II: Communication constraints and shared randomness. IEEE Transactions on Information Theory, 66(12):785--8877 2020.
[BDPSS09] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In Conference on Learning Theory, 2009.
[BHS23] Alankrita Bhatt, Nika Haghtalab, and Abhishek Shetty. Smoothed analysis of sequential probability assignment. Advances in Neural Information Processing Systems, 36, 2023.
[BK21] Alankrita Bhatt and Young-Han Kim. Sequential prediction under log-loss with side information. In Algorithmic Learning Theory, pages 340-344. Proceedings of Machine Learning Research, 2021.
[BK24] Alankrita Bhatt and Victoria Kostina. Prediction with noisy expert advice. 2024 IEEE International Symposium on Information Theory (ISIT), pages 3546-3551, IEEE, 2024.
[CBFH+97] Nicolo Cesa-Bianchi Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
[CBL06] Nicolo university press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge
[CBMS07] Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66:321-352, 2007.
[CT06] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley- Jaley-Intersccence, USA, 2006.
[DRS15] Mehmet A Donmez, Maxim Raginsky, and Andrew C Singer. Online optimization under adversarial perturbations. IEEE Journal of Selected Topics in Signal Processing, 10(2):256-269, 2015.
[FMG92] Meir Feder, Neri Merhav, and Michael Gutman. Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38(4):1258-1227)) 1270, 1992.
[GSVE14] Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A recond-order bound with excess losses. In Conference on Learning Theory, pages 176-196. Proceedings of Machine Learning Research, 2014.
[H+ 16] Elad Hazan al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 257-4): 2016.
10

---

[HACM22]
Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, and Panayotis Mertikopoulos. No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation. Advances in Neural Information Processing Systems, 2022.
[HKYF23] Osama A Hanna, Merve Karakas, Lin F Yang, and Christina Fragouli. Multi-arm bandits over action erasure channels. In 2023 IEEE International Symposium on Information Theory, pages 1312-1317. IEEE, 2023.
[HRS20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33, 2020.
[HYF22] Osama A Hanna, Lin Yang, and Christina Fragouli. Solving multi-arm bandit using few bits of communication. In International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, 2022.
[KH19] Victoria Kostina and Babak Hassibi. Rate-cost tradeoffs in control. IEEE Transactions on Automatic Control, 64(1 (14425-4540) 2019.
[KMA 21] Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1
2021.
[KSH00] Thomas Kailath, Ali H Sayed, and Babak Hassibi. Linear estimation. Prentice Hall, 2000.
[L.C06] Erich Lehmann and George Casella. Theory of point estimation. Springer Science Business Media, 2006.
[Luo22] Haipeng Luo. Adversarial bandits: Theory and algorithms, 2022. Available online at atttss:/ssimns berkeley /etp://ites//eefalttt/leeee////e 222///20/022222/////////
[MF98] Neri Merhav and Meir Feder. Universal prediction. IEEE Transactions on Information Theory, 44(6):2124-2147 1998.
[MHP23] Aritra Mitra, Hamed Hassani, and George Pappas. Linear stochastic bandits over a bit-constrained channel. In Learning for Dynamics and Control Conference, pages 1387-1399, Proceeding of Machine Learning Research, 2023.
[MST23] Prathamesh Mayekar, Jonathan Scarlett, and Vincent YF Tan. Communication- constrained bandits under additive gaussian noise. International Conference on Machine Learning, 2023.
[Ora19] Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213 132133 2019.
[PGZ22] Francesco Pase, Deniz Gündüz, and Michele Zorzi Rate-constrained remote contextual bandits. IEEE Journal Selected Areas in Information Theory, 2022.
[PW17] Yury Polyanskiy and Yihong Wu. Strong data- processioc inequalities for channels and bayesian networks. In Convexity and Concentration, pages 2 111-249. Springer, 2017.
[PW22] Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Book draft, 2022.
[Rag16] Maxim Raginsky. Strong data processing inequalities and ø-sobolev inequalities for discrete channels. IEEE Transactions on Information Theory, 62(6):3355-3389, 2016.
[Ris84] Jorma Rissanen. Universal coding, information, prediction, and estimation. IEEE Transactions on Information theory, (0(4))629-636. 1984.
[RM19] Alon Resler and Yishay Mansour. Adversarial online learning with noise. In Interna- tional Conference on Machine Learning, pages 5429-5437. Proceedings of Machine Learning Research, 2019.
11

---

[RWH* 12] Maxim Raginsky, Rebecca M Willett, Corinne Horn, Jorge Silva, and Roummel F Marcia. Sequential anomaly detection in the presence of noise and limited feedback. IEEE Transactions on Information T 58(8):5544) 2012.
[SPJM23] Ke Sun, Samir M Perlaza, and Alain Jean-Marie. 2x 2 zero-sum games with com- mitments and noisy observations. IEEE International Symposium on Information Theory, 2023.
[SRV18] Yanina Shkel, Maxim Raginsky, and Sergio Verdú. Sequential prediction with coded side information under logarithmic loss. In Algorithmic Learning Theory, pages 753- 769, Proceedings of Machine Learning Research, 2018.
[SW14] Adrien Saumard and Jon Wellner. Log-concavity and strong log-concavity; review. Statistics surveys, 8:45, 2014.
[TM04a] Sekhar Tatikonda and Sanjoy Mitter. Control over noisy channels. IEEE Transactions on Automatic Control, 49(7): 1196-121,, 2004.
[TM04b] Sekhar Tatikonda and Sanjoy Mitter. Control under communication constraints. IEEE Transactions automatic control, 49(7):1056-1065 2004.
[TSM04) Sekhar Tatikonda, Anant Sahai, and Sanjoy Mitter. Stochastic linear control over communication channel. IEEE Transactions on Automatic Control, 19(9):154--156,, 2004.
[WGS23] Changlong Wu, Ananth Grama, and Wojeiech Szpankowski. Robust online classifica- tion: From estimation to denoising, arXiv preprint arXiv:2309.01698, 2023.
[WM01] Tsachy Weissman and Neri Merhav. Universal prediction of individual binary sequences in the presence of noise. IEEE Transactions on Information Theory, 4766)22151-2173,
2001.
[WM04] Tsachy Weissman and Neri Merhav. Universal prediction of random binary sequences in a noisy environment. The Annals of Applied Probability, 14(1):54-89, 54, 2004.
[WMSBO1] Tsachy Weissman, Neri Merhav, and Anelia Somekh-Baruch. Twofold universal prediction schemes for achieving the finite-state predictability of noisy individual binary sequence. IEEE Transactions on Information Theory, 47(5):1849-1866. 2001.
[XB97] Qun Xie and Andrew R Barron. Minimax redundancy for the class of memoryless sources. IEEE Transactions on Information Theory, 43(2):646 657, 1997.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract, introduction and main results section reflect the paper's contribu- tions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The scope of the main results is outlined wherever applicable.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
All statements have full set of assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuia wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[NA]
This paper consists of theoretical advancements with no foresecable societal consequences.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper has no experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper contains no experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this paper does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur/e /2tp://///////ooeeeeeee///////// for what should or should not be described.
19

---

A Literature Review
closely related area where sequential decision-maiee making with noisy feedback has been considered is control. The question examined here is how control systems can maintain stability and performance despite the presence of noise in the feedback loop. While ceasuurement-fedbbaae control is classical topic [KSH00], the line of work [TM04b] [MM44] [SM04 [H19] examines fundamental limits of control performance when the feedback subject communication constraints.
1WH+12 considered sequential anomaly detection and sequential probability assignment (i.e. online prediction using the logarithmic loss [Ris84 XB97 BK21 CBL06) in the presence of noise and established minmax regret guarantees. Also the setting of sequential probability assignment, [SRVI8] considered compressed side information available noncausally- considers compressed feedback available causally, in the prediction with experts setting. Decision- making with noisy feedback in the sequential classification setting has been considered in [BDPSS09 WGS23). The effect of noisy observations on the equlibrium value of games was characterized in [ACM22 [SPMM33] The setting where rather than the feedback & the action Pe is communicated over a noisy channel is considered in [DRSI5] PGZ22
work
HKYF23 and minmax bounds on the
2CI,+ considers sequential statistical inference under constraints, designing optimal policies and well as establishing fundamental converse bounds.
regret incurred are established. The line work (ACT20a
ACT20b
We remark that our setting is distinct from that of i..d. & and adversarially injected corrup- tions [AAK*20 20), a model which aims to bridge the distance between the case where the losses l at chosen i.i.d. and the individual-ssqqence case (adversarial &). Moreover, our choice of benchmark being min,gim] Σn Eej (see the regret definition (3) makes our setting distinct from
smoothed analysis [HRS20, [HS233,, where the benchmark is the best expert in hindsight on the noisy loss function mmaking smoothed analysis beyond-word woost case setting.
B Proof of Theorem
First, the following proposition justifies the use of an unbiased estimator in the strategy.
Proposition 2 Let & (where &g is a possibly noisy function of c²) be such that Ele [11] = C,, and p be any strategy for the noiseless experts problem. Then, the strategy P that plays Pe. pr (?-11)
achieves
Reg(p, Paje, En) S
Σ ppe (1-)),
min fE(m
Eej
Proof.
(E(p ())())-))1,4 El(p (1-)), 1,)
(a) E((p((e ), E -
E(E((pr (e--1), R.) (2-22111
E (pi(e E.i
(30)
where (a) follows by the conditional unbiasedness of &o and (b) follows by the tower property of expectation. Moreover,
min 192
min ml)
Ees
(31)
where (a) follows by the unbiasedness of E. and linearity of expectation, and (b) follows since Elmiin-)] < min E(.] The Proposition follows by summing up (30) over I. and from 31
Proposition establishes that upon construction of an unbiased estimator Eg, the decision-maker can pretend that the benchmark is minje(m] Σ Lej. and employ no-regret strategy for this benchmark.
20

---

To construct scheme, we need to utilize no-regret strategy for the noiseless setting in conjunction with unbiased estimator l. To this end, utilize the landmark exponential weights/Hedge (EW) strategy. We will need the following analysis of the exponential weights strategy pr (see for example luuo22), which bounds the regret incurred by pFW in terms of the second moment of the loss functions [CBMS07] GSVE14).
Lemma If Pf is chosen to be the exponential weights strategy, and if en and a satisfy -akij S 1 for all t and j. we have
log m
7
Reg(p
EW
+ a
Ptj
BW
(32)
t=
1=
Proof. Define
m
1-1 cxp - a
Z, ==
Σ (1y)
j=1
i=1
the normalizing term in p.a that Pij to be the potential function and bound the difference in the potential function at each step. We have Note that
exp (-
Eij) /Ze Then, will consider log Ze
j=1 exp ( a
1=1 Egg 1-1
log Zet1 log Ze log
2j=1
1/ j=1 exp a i=1 (sg)
2==1 exp
m
- -1=1
i= fig) expl -alp)
log
Σラ=1 exp
Σi=1 (y)
m
log
Σ
Ptj
EW exp(
exp(-alls)
1=1
(6)
log
Σ
Ptj
EW (1 alej aZll))
j=l
log
1 -
Ptj
EW
Eij + a 2 Σ Peglit
(c)
0
Ptj
EW
Eij + a²
EW Ptj
j=1
j=1
aapp FW ()) +
taa
EW Ptj
(33)
j=1
where (a) follows by the definition of p Ew (b) follows since e" 51+x+12 for x S (and
x2
-aki 5 1), and (c) follows since log( + x) S x for all x. Now, we observe that
m Σ j=1
log Zn+1 = log
exp
(- Σtv) kn)
1=1
2 max log jé(m]
exp
(p Σ (1j)
min jE(m)
Eij
(34)
1=1
and that 2, = m. Summing up 33 over all E [n]. using 34 and rearranging yields the Lemma.
Recall the achievability strategy BW:
21

---

Construct an unbiased estimator &g for & from the channel output
Play ps EE
(C-1).
1}. which by the condition stated in the Theorem occurs with probability PEE). We will split the regret analysis into two cases: EL occurs, where Lemma I can be invoked, and if & occurs, where we will utilize a worst-case bound on regret. First,
Define the "bad" event := (3r,
we use Proposition which yields
Reg(Eew FEW Pales E") E")
SE
Σ w
EW (,
min je m
Eij
(35)
and we have
E
Σ
EW ((--));
min Σ Eaj
E
EW
(
min jElm]
Ets) 1 1(89)
( min fElml
+ E
(p EWW (2-11)
E
Ees
1187
(36)
We analyze the three terms in the right hand side of (36) separately. First, note that if 0 occurs, then the conditions in Lemma 1
are satisfied which can be employed to get
Σ 6 EW (e (,
min je
Ees
118
log m
+
EW C (
(37)
where (37 also uses that indicator is bounded by 1 and the term to be multiplied is positive. Next, note that
Elpr BWW (2
BW (2-)))t,) + Elptj EW (e (,)) EW ( (e-)))es( - Eej)
Ptj
ElP
FW (e )) + ElP
FW CC () El(Ce - E
(6)
(1+ EW (e ( max E((ee) 11 Elp
(38)
[.
where (a) follows from the fact that &e is independent of 2c1 and that E, is unbiased, and (b) uses
that ly S by assumption. Taking expectations on both sides of (37) and (38) yields
E
EW ( (,
min jE(m)
Ees (6s)I(E93 1(19))
log m
+ a Σ
(1
+ max E((eej - -1,))11 E Σ
EW
(e-11)
Pij
1=1
1=1
log m
+ an
1ax E(( -()))9
(39)
a
[.j
To bound the second term in 36). we apply
kp (e-)) <
E
16 EW (2-1), 10-1), 1
[ 1{}}
Σ
Σ 1
22

---

(1 max ElG,, lei1 P(E) b.
V
(40)
where (a) uses the Holder inequality and the fact that p p (c'-1) is a probability distribution, (b) uses the fact that the absolute maximum a vector is bounded by the sum of the absolute values,
(c) uses the
inequality, and (d) uses unbiasedness of Egz along with the fact that L S The third term (36) will be dealt with similarly:
E
min
les 118}
E
t=1
(1 (1+
S <mmy
max 6,3
Ele, loj
P(E)
(41)
where (41) follows from (40). Finally, using
39
400
and
in 36 concludes the proof. (41
C Upper bound for uniform additive noise
We first show that the estimator Egj in 12 is unbiased. Note that
11 110t))110000 -0+ +
1 ( 11-0+11s <o)
E(G =E
(ot 1
110 110
1
<o c-t + 1-o+15ayc0
2
+ ot
P slosay<ot)
(42)
Since Ct Lej + Zej is distributed as Unif] [ + lij, a + lej), we have
P P aj < <-o+1 +10+ 1 Ljj
(43)
20
20 1
P P 9j <0)
(44)
20
Ejj
( S ct 5 + 1)
(45)
20
Substituting (43)
444) and 45 in 42 yields
(-2a + 1)(1 - -ej)
20
(2o + 1)lej
E
(
+ 4g
+
46
4g
Eij
(46)
The MSE for this estimator satisfies
E(Go 1 = E(2))] Lg
= -(-o+ 2) P (1-osap < --0+1) P(-a+1saa<0 ( <a)
a 1
1
p 3 og <0 +1) - E
23

---

(a)
(2o
1)2
les)
(2o 1)
(2o 1)
8a
80
80
2
2
(47)
where (a) uses (43
(44) and
45
D Proof of Theorem 2
Consider the following (random) ensemble of loss vectors:
Pick J Uniform|ne [m]]
Given J =" the loss vectors f are generated i.i.d., with independent components per the distribution
(1/ - c),
if
Ei
(48)
(ern(112),
otherwise
for some 0 <<< </41/4 be determined later.
Intuitively, in order to achieve sublinear regret in n with these loss functions, the decision-maker must eventually detect the expert j that has the lowest bias and therefore this be thought of hypothesis testing problem. To formalize this, we have
sup Reg(p, Pales 1n)) 8m
Σ
(p
Es
(49)
j
Now, note that
E min
Egj
<
E
min
E
Les
J
(50)
j EE
[ms]
/EIm)
(51)
2
where (a) follows since E[min(-)] < min El-] and (b) follows since by the distribution on the losses (48)
j²
ElGyl [T]
2:
(52)
otherwise
To further bring out the analogy between hypothesis testing and the regret, note that for the random variable distributed as Jr ~ pe(ct-1) conditional on c1 (i.e. a random expert is chosen as per the distribution (c(-1))
El (,, E[L,,,le'-1, Ee).
and therefore
El(pr(c 1, 3,1 = E(LeJ.).
Then.
Ep
4. 1,41 = E(E (4.. [t]]
(a) E
1 [ # J²} +
2 -e) 11 11-== Jm3
1
cP[J, J
(53)
where (a) follows from
52
Using (33 along with 51) and 44 yields
sup Reg(p, Paje )m) 2
P[J. + J*}.
(54)
Zn
24

---

To further lower bound the regret, we apply the Fano inequality to each term in the right hand side of (54)
J 1(J"; J() + log
(55)
log m 1(J";e + log 2
(56)
log m
where (56) follows by the data processing inequality since J d - Jr. Since the noise is memoryless by assumption.
I(J = I((:))=H(() - H(dlJ²)
[(a) - H(dl)²)
@
(H(c) - H(Gl)))
Σ (J);a)
=1
(a)))))
(57)
where (a) follows by the subadditivity of entropy, (b) follows since given J c' are independent (because given J", el are independent as per (48) and the channel is memoryless by assumption), and finally (c) follows by symmetry (I' are identically distributed, therefore so are c¹). Next, we have
[(J";c,)= = D (Pa1s- Pa PP.))
m
D (Po.
m j=1
D
P PaIs-
Σ 3=1
PaIJ+e
(a)
m
m
j= j'=1
m²
D (PaI>==lPaal---
m
(Pa]J== 1|Pu--l
D D(Pe =1 | Poy))==2)
(4)
D(PanIJ-=111 -llanl + DIPaal--allPap 2-
D (Bern (1/2 1 e) Pele Bern(1/2) Pcle)
D (Bern11/2) o Pajell (1/2 - c) 0 Pajr)
(58)
where (a) follows since Q(P is convex in the pair P and Q, (b) follows by symmetry, (c) follows since the vector 0₁ has product distribution given _ (because E has a product distribution and the noise is component-wise independent) and (d) follows since all the other components except the first and second have the same distribution (Bern(1/2) Peje). Recalling the definition of (Pcc)) in Definition [ we have
D (Bern(1/2 - e) Pa B///eenn1/22 Paje) S ((Pak) (a(b-el3) (()-))
25

---

S <n nP(p)
(59)
-(
where d(-ll-) denotes the binary KL divergence, and the final inequality follows since
I 1
for < 1/ and e 1/4 by assumption. Using the same reasoning for the second of 588. and
using (59 in 57
we have
I(J" - 2tn(Pa/e)c
and therefore from (54) and (66) we get
2(t (P((Pc))cc + log
sup
Re Paje, ))
1
log
fr
t=1
2nn((Ppeee + log
(60)
log m
Finally, the choice of V
log(m/4) (Pae)
(which guarantees 1 1/4 for a large enough n) in 60 yields
log(m/4)
sup Reg(p, Poles (n) e²)
>
(61)
(6n(Pc
as claimed.
Remark (Lower bound for the noiseless problem) From (56). and since J - et - c', we
see that (()";c)) < [[J*; (.). Following the single-letterization argument in (57) and using the
arguments leading up to (58) we can recover the the lower bound for the noiseless prediction with experts problem.
E
Proof of Proposition 1
Define
= [(0) ex)xxxxxx))
Then, /(0) s(0) and (J(=) - g(=))dz = 10ºh f(z)dz So g(=)dz - 0. Since f.g + and 2 + oo, this implies that the function f(z) - g(z) crosses the origin at least once in 0. Moreover, any solution of f(z) 9=)) 0
f(=) = g(2) must satisfy also log lozg(z) = 0. Since z + log f(z) log (2) is a concave function (by virtue f(z) being log-coneave and g(2) being log-affine), this implies that log f(2) log (22) crosses the origin
at most once 2 > Therefore, putting the two together implies that f(z) g(2) = 0 occurs exactly at point in
oc. Let us call this point t, that f(t) g(t). Therefore, for all
< I, f()) 2 ((2) and for all = > 4, (2) < g(=). Putting these two together, we have
(f(x) g(=))( 22) 20
which implics that
x : 1²)()) ( =²)())dzz
(62)
Since Jo =²](z)dz a² and
[ [g(())d= = Lo =² eexp(-2a](0)))
85(0)² /0
1
2² >'exp(-2)dz 4f(0)2
662 yields
f(0)² < 20
(63)
which leads to the required Proposition.
26


Reviews:
[{"review_id": "EtPf85HH4A", "reviewer": "Reviewer_tNvt", "summary": "This paper addresses the problem of prediction with expert advice under additive noise, and aims to achieve performance comparable to the best fixed expert in hindsight on the uncorrupted loss. The main contribution is a characterization of performance limits via sharp regret bounds for various noise models. Specifically, the authors show that for Gaussian noise with variance $\\sigma^2$, regret scales as $\\Theta(\\sqrt{(1 + \\sigma^2)n \\log m})$, while for uniform noise in $[−\\sigma, \\sigma]$, it scales as $\\Theta(\\sqrt{(1 + \\sigma)n \\log m})$. For the broader class of symmetric log-concave noise distributions, bounds are provided to be between these regions, i.e.,  $\\Omega(\\sqrt{(1 + \\sigma)n \\log m}) \\leq Reg \\leq O(\\sqrt{(1 + \\sigma^2)n \\log m})$. These theoretical guarantees are derived by combining an enhanced exponential weights algorithm that leverages an unbiased estimator and information-theoretic lower bounds. This work overcomes prior limitations by providing a unified framework for both bounded and unbounded losses and establishestight characterizations for a wide range of additive noise channels.", "questions": "1) What is the reason for the persistent gap in regret bounds for general symmetric log-concave noise? Are there any specific technical barriers preventing tighter characterization? Does tighter bounds require a different analytical approach?\n\n2) What are the main conceptual and/or technical challenges in developing high-probability guarantees for prediction with expert advice under additive noise, beyond the expected regret analysis?\n\n3) What are the fundamental obstacles to extending your framework to alternative loss functions (beyond linear losses) and to infinite expert classes?\n\n4) Though no experiments are included, which theoretical aspects do you believe would be most insightful to validate empirically and the practical implications such validation might yield?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strengths\n\n1) The paper tackles the practical limitation of perfect feedback in online learning, focusing on additive noise in real-world scenarios like sensor inaccuracies and autonomous driving.\n\n2) It provides a comprehensive characterization of fundamental performance limits for prediction with expert advice under various additive noise models.\n\n3) It clearly demonstrates how different noise characteristics affect regret scales, noting superlinear regret growth with increasing noise intensity and a smooth transition to the noiseless case as noise diminishes.\n\n4) Guarantees are derived using an enhanced exponential weights algorithm with an unbiased estimator (linking regret to estimation MSE) and information-theoretic lower bounds based on the strong data-processing constant, which quantifies information preservation.\n\n# Weaknesses\n\n1) While \"nearly-tight,\" the bounds for the broad class of symmetric log-concave noise are not perfectly tight.\n\n2) The paper does not include experiments or empirical results, meaning the theoretical findings are not validated computationally.\n\n3) The paper itself identifies areas for future work which highlight current limitations, such as focusing only on expected regret analysis (lacking high-probability guarantees for risk-sensitive applications) and limiting the framework to linear losses and finite expert classes.", "was_revised": true, "final_justification": "I am keeping my score, which remains a positive.\n\nThe authors clarified that while the bounds are not universally tight for all symmetric log-concave distributions, they are \"nearly-tight\" because the upper bound is achieved by Gaussian noise and the lower bound by uniform noise, both of which are log-concave. This highlights the paper's key insight: the shape of the noise distribution, not just its variance, fundamentally impacts regret scaling. The exponential weights algorithm's effectiveness with unbiased estimators, quantifying performance degradation through estimation error (MSE), is now clearer.\n\nThe paper remains purely theoretical. While the authors stated theoretical plots suffice, empirical experiments would strengthen practical applicability. The analysis is confined to expected regret, linear losses, and finite expert classes, though extensions are noted as future work.\n\nI assign high weight to the enhanced theoretical clarity regarding noise-dependent regret scaling and the strong theoretical framework. The lack of empirical validation and current scope are given moderate weight, as the theoretical insights are valuable on their own.", "rebuttal": "We thank the reviewer for their detailed evaluation and insightful questions. We address each point below:\n\n\n1. Gap in Log-Concave Bounds. We are very interested in obtaining a more precise characterization of the regret. This would likely require a deeper understanding of the relationships between the estimation-theoretic and information-theoretic quantities than already established - such relationships are an active area of research. In our paper, we derive novel upper and lower bounds on the regret that apply to any log-concave symmetric noise. We further demonstrate that neither bound is vacuous - the Gaussian distribution satisfies the upper bound with equality, while the uniform distribution attains the lower bound. We conjecture that the tail behavior determines which regime applies. Indeed, our result shows that for any noise with polynomially decaying tails, $\\sigma^2$ scaling is achievable, and already for the Gaussian distribution, which has subexponentially decaying tails (as does any log-concave distribution), a better scaling cannot be achieved. Nevertheless, the uniform distribution, which is bounded, achieves the $\\sigma$ scaling; a better scaling is not achievable for any symmetric log-concave noise distribution. \n\n\n2. High-Probability Guarantees. We are optimistic that high-probability bounds would be quite achievable using standard concentration inequality techniques. The main technical steps would involve:\n- Applying martingale concentration inequalities (like Azuma-Hoeffding) to the noise-corrupted loss estimates\n- Using union bounds over the finite expert set and time horizon\n- Carefully tracking how estimation errors concentrate around their means\n- Our separation principle already decomposes the problem into estimation + exponential weights components, and both parts have well-developed high-probability analysis tools. This represents a tractable extension of our current framework.\n\n\n3. Extensions to Non-Linear Losses and Infinite Experts. For infinite expert classes, this extension seems quite feasible using techniques from statistical learning theory. The approach would involve replacing our finite $\\log m$ term with covering number bounds or Rademacher complexity, and further using metric entropy arguments to bound the effective number of experts. The estimation component of regret would be unchanged, while the exponential weights component of regret could be handled by the aforementioned techniques. For non-linear losses, while more challenging, we see promising directions: The separation principle could possibly be extended using appropriate bias-variance decompositions and techniques from online convex optimization might bridge the gap between estimation and regret. \n\n\n4. Empirical Validation Priorities. Thank you for raising this interesting question! We believe the most insightful empirical validation would focus on several key areas. Theoretical prediction verification would involve testing our scaling laws—in particular plotting regret vs. noise parameter $\\sigma$ to confirm the scaling with regret for Gaussian, Uniform and Laplace distributions. Estimator comparison studies would be particularly compelling, especially demonstrating that our uniform noise estimator (Equation 12) significantly outperforms naive estimation $\\widehat{\\ell}\\_t = c\\_t$, which should show dramatic improvements and validate our theoretical insight about optimal estimation. Robustness analysis to test model misspecification scenarios (e.g., assuming Gaussian when noise is heavy-tailed) and performance under parameter uncertainty would be insightful. Finally, a preliminary real-world motivated study could include asset price prediction in financial markets, assuming noisy observations. \n\n\nWe appreciate the reviewer's constructive suggestions and believe the extensions suggested by them represent exciting and achievable directions for future work."}, {"review_id": "w3YjXcez8v", "reviewer": "Reviewer_rqtx", "summary": "The paper considers prediction with expert advice where the losses are observed with stochastic noise. Upper bounds are shown for bounded losses using an EXP3-like algorithm (exponential weights + unbiased estimates) in three noise settings: Gaussian, uniform and log-concave. Lower bounds are shown for binary losses in terms of the information processing constant of the noising mechanism.", "questions": "I'd like to hear the authors view on submitting a paper with pages of text copied compared with their own earlier publication.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Clarity:\nThe paper is clear.\n\nQuality:\nThe problem is interesting. The results are an elegant characterization of the minimax regret.\n\nSignificance:\nThe problem of noisy feedback is reminiscent of (but simpler than) the information bottleneck present in bandits. Compared to [BK24], the new parts are the extension to unbounded noise, and the adaptation of Theorem 1. These are relatively moderate contributions.\n\n\nOriginality:\nThe work is an extended version of the ISIT publication [BK24]. Not a follow-up as is claimed. I say this because the text has significant overlap. If these are not the same authors, then this is clear plagiarism. Yet even if they are the same authors, this relation (of being the extended version of) is not mentioned in the paper. It is certainly pushing the boundary of the Neurips submission guideline \"Submissions that are identical (or substantially similar) to versions that have been previously published\".", "was_revised": true, "final_justification": "This paper has multiple pages of nearly identical text with a previous paper. It also has new results that significantly go beyond that earlier paper. The authors propose to remove the overlap. As I wrote to them below, I think it is in fact simpler to acknowledge that this is an extended version of their earlier paper, thus making the overlap non-problematic. This is not difficult or time consuming to implement, so it can be expected of the authors. \n\nWith that problem out of the way. We then end up with a collection of interesting new results, about which I am positive. I have updated the score accordingly.", "rebuttal": "We thank the reviewer for their careful evaluation and appreciate the opportunity to address their concerns about originality and our relationship to prior work.\n\nWe want to clarify our substantial technical extensions beyond the work in [BK24]. As explicitly stated in our paper (lines 171-178): \"[BK24] recently studied prediction with noisy expert advice, but their analysis had several limitations that the current work addresses. First, this paper provides a comprehensive treatment for both bounded and unbounded losses—this is a critical consideration when dealing with additive noise with potentially heavy tails. Second, while they presented (without proofs) an ad-hoc lower bound for Gaussian noise, this work derives it from a unified framework of Theorem 2. Third and most importantly, this work establishes tight characterizations for a wide class of additive noise channels, including the nearly-tight bounds for uniform and general symmetric log-concave distributions that do not follow from their work.\"\n\nWe now elaborate on this. Our technical contributions represent advances in several key areas:\n\n\n- New ideas in Optimal Estimation: Our discovery that optimal estimation can fundamentally differ from naive approaches represents a significant theoretical insight. As other reviewers have noted, \"the loss estimator for the uniform distribution is surprising\" and demonstrates that naive estimation $\\widehat{\\ell}_t = c_t$ can be suboptimal by factors up to $\\sqrt{\\sigma}$. This reveals structure about when and how distributional knowledge affects learning performance.The decomposition of noisy regret into estimation error plus optimal control (Theorem 1) provides a general principle with applications beyond this specific setting, offering new perspectives on the connection between estimation theory and online learning. \n\n\n- Comprehensive Analysis of Log-Concave Distributions: Our nearly-tight characterization of the broad class of symmetric log-concave noise distributions, with matching upper and lower bounds for specific cases (particularly the Laplace and uniform distributions), represents a theoretical contribution that significantly advances understanding of this problem. \n\n- Extension to Unbounded Noise: The treatment of unbounded distributions like Laplace noise required new technical approaches including an analysis of \"bad events\" and probability bounds that were not addressed in preliminary work.\n\n\n- On Textual Overlap Concerns: We acknowledge the reviewer's concern about textual similarity in certain sections. Upon reflection, we recognize that some passages in our introduction and problem setup as well as related work overlap with [BK24]. In particular, there is overlap in the Introduction section which elaborates on the problem (Lines 13-15, 21-26 that explain the vanilla experts problem, and lines 42,43,49-52, 56-63 that introduce the technical details of prediction with noisy experts problem as well as precise definitions) and overlap in the Section 3 (lines 142-170, which is an exposition of related work). This occurred because both works necessarily establish the same fundamental problem formulation and mathematical framework. This also reflects standard practice when extending preliminary results - foundational mathematical definitions and problem formulations necessarily share common elements. Similarities in the Sections on technical content include Lemma 1 (lines 809-810), Definition 1 (lines 251-252), and the ensemble in (48)---these are all standard results/definitions taken from the literature and therefore are similar. \n\n\nWe finally want to address some important points:\n\n-   Substantial New Content: The overwhelming majority of our paper consists of entirely new technical material. Our theoretical analysis, novel estimator constructions, information-theoretic converse for log-concave distributions, and applications to new noise models represent contributions that extend far beyond any preliminary work.\n\n\n-  Path Forward: We sincerely apologize for our oversight in writing. If our work is accepted, we will revise the intro and related work sections to minimize any textual similarities while preserving the necessary technical foundations. In particular, we will rewrite the introduction by motivating the importance of understanding the limits of real-time decision-making where the losses are corrupted by an additive noise whose distribution does not follow previously considered examples of binary channel models (BSC, BEC, AWGN) to encompass continuous distributions that arise naturally in practical signal processing and quantization applications. As a prominent example, uniform additive noise emerges in quantization-limited systems where continuous signals must be discretized with finite precision—ubiquitous in analog-to-digital conversion, communication-constrained IoT sensor networks, and federated learning with limited-precision arithmetic. Our discovery that uniform noise requires fundamentally different optimal estimation techniques represents a surprising theoretical insight with immediate practical implications for these quantization-dominated environments in order to achieve optimal regret. More broadly, symmetric log-concave noise distributions provide a rich framework encompassing Laplace distributions, truncated Gaussian models and other distributions that better capture measurement errors compared to pure Gaussian assumptions, making our theoretical framework useful for understanding fundamental performance limits across these diverse practical scenarios.\n\n\nWe appreciate the reviewer's diligence in evaluating our work and welcome any further clarification they may need about our technical contributions or relationship to prior work.  We also welcome any advice on how to best address their concerns."}, {"review_id": "RmqcTWGs0B", "reviewer": "Reviewer_YTLw", "summary": "The authors consider the problem of prediction with expert advice with adversarial losses, where the learner observes noisy versions of the losses which are obtained by perturbing the basic losses with some fixed distribution. The authors consider the specific examples of Gaussian and uniform noise, and establish optimal regret bounds in terms of the standard deviation of the noise in both cases. For more general noise distributions, the authors establish regret upper and lower bounds which are not tight in general, but are valid for all symmetric distributions with sufficiently light tails.", "questions": "I would highly appreciate it if the authors could address the points which I raised under \"Weaknesses\". In particular, regarding the extensions of the results to the bandit setting. I would also appreciate a comment regarding the tightness of the bounds for general symmetric distributions, and the overall technical challenges in the analysis.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* The problem studied in this paper is interesting and well-motivated.\n* The problem formulation is very simple and easy to understand.\n* The paper is written clearly, and the analysis is easy to follow.\n* Theorem 1 is a nice way to generalize the regret upper bounds obtained in the paper for all noise distributions.\n* Theorem 2 showing a lower bound which depends on the data-processing coefficient of the underlying noise distribution is a nice way to obtain specific lower bounds for certain noise distributions.\n* The fact that for some distributions estimating the loss directly via the noisy loss is not the optimal choice (as with the uniform distribution) is surprising and nontrivial.\n\nWeaknesses:\n\n* The fact that the bounds established in the paper are only tight for two given distributions (Gaussian and uniform) makes the overall contribution, in my opinion, a bit lacking. The result would be much stronger if certain distribution-dependent parameters were introduced which would result in tight bounds for the more general family of distributions.\n\n* In terms of technical challenges, the analysis presented in the paper seems quite straightforward, and in particular the general upper bound in Theorem 1 follows from standard arguments in the online learning literature. I think that the most interesting and technically novel part of the analysis is the fact that it is not always optimal to estimate the losses as the noisy losses directly (as with the uniform noise case), which could result in a better dependence on the standard deviation. I think the authors should put more emphasis on this idea compared to other more standard arguments.\n\n* I think the one most natural questions given the results presented in this paper concerns bandit feedback, which is not mentioned in the discussion section of the paper. It would seem to me that the technical difficulty in extending those results to the bandit setting arise when estimating the losses via importance sampling, which would possibly result in highly negative loss values on top of the noise being unbounded. Have the authors consider this extension? I think this paper would highly benefit from such a generalization as the results just for the full-information setting seem to me as more of an initial step in the right direction.\n\n* The estimators provided for the algorithm require knowledge of the noise standard deviation $\\sigma$. It would seem possible, though perhaps more complicated, to achieve similar regret bounds with adaptive algorithms which do not have such prior knowledge.\n\n* The lower order terms in the bounds written in Eqns (11), (14) are a bit confusing - rather than $o(n)$ which only signifies sublinear dependence on $n$, the bounds actually decay to zero as a function of $n$, so it should be $o(1)$.", "was_revised": true, "final_justification": "Having read the other reviews and comments, I am still leaning towards acceptance, though some valid concerns were raised regarding the similarity to [BK24]. It seems to me like this work does provide interesting extensions to this work which is why I don't view this as a major issue. I therefore maintain my overall score.", "rebuttal": "We thank the reviewer for their detailed evaluation and insightful comments. \n\n- On Tightness of the Bounds: We are very interested in obtaining a more precise characterization of the regret. As we mentioned in the reply to question 4 of reviewer vFEj, this would likely require a deeper understanding of the relationships between the estimation-theoretic and information-theoretic quantities than already established - such relationships are an active area of research. In our paper, we derive novel upper and lower bounds on the regret that apply to any log-concave symmetric noise. We further demonstrate that neither bound is vacuous - the Gaussian distribution satisfies the upper bound with equality, while the uniform distribution attains the lower bound. As highlighted by both reviewers Tk3H and YTLw, our uniform noise estimator is novel and represents a key insight—it demonstrates how the distributional knowledge can be leveraged to improve upon naive estimation in real-time decision-making. In our paper, we also demonstrated an example (lines 286-290) of an additive noise distribution which despite have $\\sigma^2$ variance, leads to $\\eta = 1$ and the noisy regret being exactly equal to the noiseless regret---this shows that simply restricting variance does not lead to a universal result. Upon imposing some more structure on noise density (log-concavity) we are able to achieve nearly-optimal characterization of regret; the question of both tightening the bounds and achieving such a characterization for an even larger class of noise distributions over symmetric log-concave remains an exciting open direction.\n\n\n- On Technical Challenges: In the revised manuscript, we will highlight the novelty beyond the uniform noise case. Note also that the lower bound (tight for the uniform noise) holds for any symmetric log-concave noise. Our approach to the converse encompassing such a wide family of distributions is novel - we leverage the strong data processing inequality, and we apply the log-concavity of the noise to bound the strong data processing constant in terms of the variance universally within that class.\n\n\n- On Bandit Extensions: This is an excellent and challenging question that we have considered. The bandit setting would indeed compound two sources of difficulty: importance sampling can create estimates with high variance, and additive noise makes this even worse since we might observe very negative values. However, we believe this is surmountable using techniques to control for these challenges. For instance, one could use truncated importance sampling (clipping estimates to reasonable ranges) combined with bias correction, or ideas for variance reduction. The key “separation principle” insight as in Theorem 1 would likely extend, but the specific estimator constructions would need to account for the importance sampling structure.\n\n\n- On Adaptive Algorithms: You raise an important practical limitation. The fundamental challenge is that our optimal estimators (particularly for uniform noise) require precise distributional knowledge. However, we believe there are promising approaches to achieve similar rates adaptively. One direction is using online parameter estimation—for instance, simultaneously learning the noise variance while running the expert algorithm, potentially using tricks to handle the exploration-exploitation tradeoff. Another approach might be developing estimators that are robust across parameter ranges, though this could sacrifice some optimality. The theoretical question of whether adaptive algorithms can match the optimal rates remains an intriguing open problem. \n\n\n- On lower-order terms: Thank you for pointing this out, we will correct it in the updated manuscript."}, {"review_id": "TBNrxRg78r", "reviewer": "Reviewer_vFEj", "summary": "This work investigates the setting of prediction with expert advice where each component $\\ell_t(i)$ of the loss vector observed by the learner is affected by zero-mean additive iid noise (where the noise $Z_t(i)$ in each observed loss component $\\ell_t(i) + Z_t(i)$ is iid across time $t$ and across experts $i$). As the noise may violate the requirement that $\\alpha\\ell_t(i) \\ge -1$, where $\\alpha$ is the learning rate, the regret bound now depends on the probability that in at least one round $t$ the boundedness loss condition $\\alpha(\\ell_t(i) + Z_t(i)) \\ge -1$ is violated for some expert $i$. The authors prove upper and lower bounds on the regret when $Z_t(i)$ are symmetric log-concave distributions parameterized by their variance. While these bounds are not matching, the authors also prove that the upper bound is achieved by Gaussian distributions and the lower bound is achieved by the Uniform distribution (which are both log-concave).", "questions": "1. What additional properties of symmetric log-concave noise distributions could capture the right scaling of the regret?\n\n2. Step (c) in display (40) seems to use independence between $\\widehat{\\ell}_{t,j}$ and $\\mathcal{E}$, which appears to be invalid. Can you commment?\n\n3. The analysis heavily relies on componentwise independence of the noise. Would the analysis of joint noise distributions require a significantly different approach?\n\n4. While the upper bound depends on the variance of the MSE, the lower bound depends on an information-theoretic quantity. Can you comment on the feasibiliy of deriving upper bounds depending on similar information-theoretic quantities using a more refined analysis?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: An elegant information-theoretic analysis of a simple yet fundamental setting. The upper and lower bounds capture the range of possible dependencies of the regret on the noise variance. The analysis contains some novel ideas and is technically solid and competent. In particular: the loss estimator for the uniform distribution is surprising, and the lower bound cleverly combines classical proofs with information-theoretic tools like the strong data-processing inequality. The overall presentation is clear.\n\nWeaknesses: The upper bound analysis is a rather straightforward application of the exponential weighting technique. The lower bound for symmetric log-concave noise distributions is not uniformly tight.\n\nI think this is an interesting contribution that deserves publication, but perhaps a research note could be a venue more appropriate than NeurIPS.", "was_revised": true, "final_justification": "My initial opinion on this submission was a bit mixed. I was happy to see that the rebuttal phase satisfactorily addressed my comments (including a technical issue that was actually pretty simple). After reading the other reviews, I decided to raise my score because I think the problem is rather fundamental and the solution is elegant.\n\nThere are some remaining unresolved questions that are correctly reported in the submission. I do not think they should prevent this work from being published.\n\nI do not see the lack of experiments as a problem for this type of contribution.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and constructive feedback. We address their questions below:\n\n- What additional properties of symmetric log-concave noise distributions could capture the right scaling of the regret? \n\nThis is an excellent question that touches on the heart of our contribution. We conjecture that the tail behavior determines which regime applies. Indeed, our result shows that for any noise with polynomially decaying tails, $\\sigma^2$ scaling is achievable, and already for the Gaussian distribution, which has subexponentially decaying tails (as does any log-concave distribution), better scaling cannot be achieved. Nevertheless, the uniform distribution, which is bounded, achieves the $\\sigma$ scaling; better scaling is not achievable for any symmetric log-concave noise distribution. \n\n- Step (c) in display (40) seems to use independence between $\\widehat{\\ell}\\_{t,j}$ and $\\mathcal{E}$, which appears to be invalid. Can you comment? \n\nStep (c) in equation (40) applies the Cauchy-Schwarz inequality: $\\mathbb{E}[|\\widehat{\\ell}\\_{t,j}|1(\\mathcal{E})] \\le \\sqrt{\\mathbb{E}[\\widehat{\\ell}\\_{t,j}^2]}\\sqrt{\\mathbb{E}[1(\\mathcal{E})]}$ for which an independence assumption is not required. The subsequent step (d) then uses the unbiasedness of the estimator and our MSE bounds to complete the analysis. We will clarify this in the revised manuscript. \n\n- The analysis heavily relies on componentwise independence of the noise. Would the analysis of joint noise distributions require a significantly different approach? \n\nYes, analyzing joint (non-componentwise independent) noise would require significantly different techniques. Our approach fundamentally relies on independence in two key places: the information-theoretic lower bound decomposes the mutual information across experts (equation 58), and the single-letterization argument bounds cumulative information linearly in time (equation 57). With correlated noise, both decompositions fail—we would need multivariate information-theoretic tools and potentially joint estimation across all experts rather than component-wise analysis. This represents an interesting but technically challenging extension of our framework. \n\n- While the upper bound depends on the variance of the MSE, the lower bound depends on an information-theoretic quantity. Can you comment on the feasibiliy of deriving upper bounds depending on similar information-theoretic quantities using a more refined analysis?\n\nIndeed,  achieving upper bounds in terms of $\\eta$ would provide a much more unified characterization. The key would be establishing that there exists an unbiased estimator with the MSE bounded by some function of $\\eta$. Potentially, this direction would require us to leverage results on relationships between information and estimation quantities such as extensions of the I-MMSE relationship beyond Gaussian channels to general channels. We view this as a compelling direction that could not only close the gap for general noise distributions, but potentially provide a unified characterization that eliminates the need for ad-hoc estimator construction for each noise distribution individually—our upper bounds already exhibit similar scaling with $\\eta$ as our lower bounds, suggesting such a unification may be achievable. More precisely, we hope to show that the minimum-variance unbiased estimator achieves MSE that can be upper bounded in terms of information-theoretic quantities like mutual information (in contrast to lower bounds in terms of information measures which are relatively better known). In establishing this relationship, we anticipate uncovering a principled path to optimal estimator construction that would naturally yield the naive estimator $\\widehat{\\ell}\\_t = c\\_t$ for Gaussian and Laplace noise (where simple estimation is optimal) and the sophisticated truncated construction of Equation (12) for uniform noise (where careful clipping is required). This would provide both fundamental performance guarantees and constructive guidance for deriving optimal estimators across different noise families."}, {"review_id": "SZ0Otyqmdy", "reviewer": "Reviewer_Tk3H", "summary": "The paper considers the problem of prediction with expert advice with corrupted feedback, assuming that the learner only gets to observe the loss functions up to additive noise. Various upper bounds are given for specific noise models, which are supported by lower bounds that are shown to be tight for some choices of the noise distribution.", "questions": "N/A", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I enjoyed reading the paper and found some of the results to be quite neat. In particular, I found the loss estimator uniform noise to be quite clever, and the resulting regret bound to be surprisingly tight. Together with the lower bounds, these results have revealed quite a bit of unexpected structure in this (otherwise quite innocent-looking) problem setting. On the technical side, I appreciated the clear and intuitive nature of both the upper bounds in Theorem 1 and the lower bounds in Theorem 2.\n\nPlaying the devil's advocate for a second, I can see that some readers may feel that the results are a bit \"elementary\". In particular, I myself have felt this to an extent as I started to read the paper and got to the upper bounds for the setting of Gaussian observation noise --- these results are not surprising at all. Similarly, Theorem 1 is far from being novel, and can be proved via very small adjustments to the classic analysis of exponential weighted averaging. Thankfully, the authors are reasonably low-key about this result and are not trying to make it look much more significant than it actually is.\n\nOtherwise, the surprise factor for the case of uniform noise has saved this paper for me. Given the simplicity of the estimator and its error analysis, I suspect that this trick might have been known previously but I have no knowledge of this. If the authors have a pointer, I would appreciate that (and also maintain my positive rating since the trick is definitely new in the context of online learning either way).\n\nOverall, I am happy to recommend acceptance.", "was_revised": true, "final_justification": "I continue to support acceptance of this paper.", "rebuttal": "We thank the reviewer for their detailed and encouraging remarks. \nWe have not seen the construction of the unbiased estimator for the uniform distribution appear previously in the literature. Since uniform error is closely related to noise due to quantization, we expect the tight results for the uniform error to translate into tight bounds for regret analysis with quantized feedback."}]

Author rebuttal:

Meta-review: This paper addresses the problem of prediction with expert advice under additive noise, and aims to achieve performance comparable to the best fixed expert in hindsight on the uncorrupted loss. The main contribution is a characterization of performance limits via sharp regret bounds for various noise models.

All reviewers are positive about the contributions of the paper with a consensual rating range (4-5).
An issue raised by a reviewer is an important textual overlap in text and setting presentation with a previous reference.
The contributions themselves are new and of independent interest as noted by all reviewers.
The authors promised to address this in the final version: "If accepted, we will revise the introduction and related work sections to minimize textual similarities while preserving necessary technical foundations."
Decision: Accept (poster)