Bilateral Trade Under Heavy-Tailed Valuations:
Minimax Regret with Infinite Variance
March 06, 2026
We study contextual bilateral trade under full feedback when trader valuations have bounded density but infinite variance. We first extend the self-bounding property of Bachoc et al.(ICML 2025) from bounded to real-valued valuations, showing that the expected regret of any price \(\pi\) satisfies \(\mathbb{E}[g(m,V,W) - g(\pi,V,W)] \le L|m-\pi|^2\) under bounded density alone. Combining this with truncated-mean estimation, we prove that an epoch-based algorithm achieves regret \(\widetilde{O}(T^{1-2\beta(p-1)/(\beta p + d(p-1))})\) when the noise has finite \(p\)-th moment for \(p \in (1,2)\) and the market value function is \(\beta\)-Hölder, and we establish a matching \(\Omega(\cdot)\) lower bound via Assouad’s method with a smoothed moment-matching construction. Our results characterize the exact minimax rate for this problem, interpolating between the classical nonparametric rate at \(p{=}2\) and the trivial linear rate as \(p \to 1^+\).
Bilateral trade—the simplest two-sided market—requires a broker to set prices between a buyer and a seller whose private valuations are unknown. The celebrated impossibility theorem of Myerson and Satterthwaite [1] shows that no incentive-compatible, individually rational, budget-balanced mechanism can achieve full efficiency in a single round. This spurred a rich literature on approximate mechanisms [2] and, more recently, on online bilateral trade, where the broker learns from repeated interactions and regret—the cumulative loss from suboptimal pricing—replaces the single-shot efficiency objective.
Bachoc, Cesari, and Colomboni [3] initiated the study of contextual online bilateral trade, where a public context vector \(x_t\) arrives each round and trader valuations depend on an unknown function \(m(x_t)\). Under bounded noise densities and finite variance, they established an \(O(Ld\log T)\) parametric regret bound and an \(\widetilde{O}(\sqrt{LdT})\) bound under two-bit feedback; the nonparametric setting was subsequently treated in [4]. A key structural insight is the self-bounding property: the expected regret of pricing at \(\pi\) instead of \(m\) is at most \(L|m-\pi|^2\), reducing regret control to mean estimation. However, their algorithms rely on ordinary least squares, which requires finite variance (\(\mathbb{E}[\xi^2] < \infty\)). In many applications—financial markets, insurance, real estate—valuations exhibit heavy tails well-modeled by Student’s \(t(\nu)\) with \(\nu < 2\), where the variance is infinite [5]. This raises a natural question: what regret is achievable when the noise has bounded density but infinite variance?
We answer this question with three contributions. (C1) We extend the self-bounding property from bounded to real-valued valuations (Lemma 1), showing that bounded density alone—without any moment condition beyond \(\mathbb{E}[|\xi|] < \infty\)—suffices to control regret via squared estimation error. (C2) We design epoch-based algorithms using truncated-mean estimation [6] and prove tight regret rates: \(\widetilde{O}(T^{(2-p)/p})\) in the parametric case and \(\widetilde{O}(T^{1 - 2\beta(p-1)/(\beta p + d(p-1))})\) in the nonparametric case, where \(p \in (1,2)\) is the moment parameter and \(\beta\) is the Hölder smoothness. (C3) We establish matching lower bounds via Assouad’s method [7] combined with a smoothed moment-matching construction (Proposition 5, Remark 6), proving that our rates are minimax optimal up to logarithmic factors.
Bilateral trade. Online bilateral trade was initiated by Cesa-Bianchi et al.and has since been studied under various feedback models and distributional assumptions; see [3] and references therein. The contextual setting was introduced in [3] (parametric) and [4] (nonparametric), both under finite-variance noise. Our work extends this line to the infinite-variance regime.
Robust mean estimation. Estimation under heavy tails has a long history. Catoni [8] introduced influence-function estimators achieving sub-Gaussian deviations under finite variance. Bubeck, Cesa-Bianchi, and Lugosi [6] analyzed truncated-mean estimators under finite \(p\)-th moments (\(p \in (1,2]\)), achieving the minimax rate \((u/n)^{(p-1)/p}\); this is the estimator we use. Lugosi and Mendelson [5] survey the broader landscape, including median-of-means and multivariate extensions. Hopkins [9] showed that sub-Gaussian rates are achievable in polynomial time under finite variance; our regime (\(p < 2\), infinite variance) lies strictly below this threshold.
Online learning with heavy tails. Bubeck et al. [6] studied multi-armed bandits under heavy-tailed rewards, and Medina and Yang [10] extended this to linear bandits. Our problem differs from standard bandits: the self-bounding property of bilateral trade squares the estimation error in the regret decomposition, altering the rate.
Nonparametric regression. The minimax rate \(T^{d/(2\beta+d)}\) for \(\beta\)-Hölder regression in \(d\) dimensions was established by Stone [11] under finite variance. Our Theorem 3 generalizes this to the heavy-tailed regime through the bilateral trade self-bounding lens.
We study online contextual bilateral trade where noise may have infinite variance. Over \(T\) rounds, at round \(t\): a context \(x_t \in [0,1]^d\) is revealed; two traders arrive with valuations \(V_t = m(x_t) + \xi_t\) and \(W_t = m(x_t) + \zeta_t\); the broker posts price \(P_t\) and observes \((V_t, W_t)\) (full feedback). The gain from trade is \(g(p,v,w) = (v \vee w - v \wedge w)\cdot\mathbb{1}\{v \wedge w \le p \le v \vee w\}\), and regret is \(R_T = \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[g(m(x_t), V_t, W_t) - g(P_t, V_t, W_t)]\).
Assumption 1 (Bounded Density). \(\xi_t, \zeta_t\) are independent with zero-mean densities bounded by \(L \ge 1\). This is necessary: without it, \(R_T = \Omega(T)\) [3].
Assumption 2 (Finite \(p\)-th Moment). \(\mathop{\mathrm{\mathbb{E}}}[|\xi_t|^p] \le \sigma_p^p\) for some \(p \in (1,2)\); \(\mathop{\mathrm{\mathbb{E}}}[\xi_t^2]\) may be \(\infty\). Example: \(\xi_t \sim t(\nu)\), \(\nu \in (1,2)\).
Assumption 3 (Smoothness). \(m:[0,1]^d \to \mathbb{R}\) is \((\beta, L_H)\)-Hölder: \(|m(x) - m(x')| \le L_H \|x - x'\|^\beta\).
The gap. Bachoc et al. [3] proved the self-bounding property \(\mathop{\mathrm{\mathbb{E}}}[g(m, V, W) - g(\pi, V, W)] \le L|m - \pi|^2\) for valuations in \([0,1]\), where noise is bounded and variance is automatically finite—infinite variance is impossible in that model. Their Algorithm 2 further uses OLS on \(Y_t = (V_t{+}W_t)/2\), requiring \(\mathop{\mathrm{\mathbb{E}}}[\xi^2] < \infty\). We make two contributions: (C1) extend the self-bounding property to \(V_t,W_t \in \mathbb{R}\) (Lemma 1), and (C2) close the algorithmic gap via robust estimation under finite \(p\)-th moment (Theorems 2–3).
Remark 1 (Two-bit feedback). Under two-bit feedback, observations are binary—bounded regardless of noise tails. The rate \(\widetilde{O}(\sqrt{LdT})\) from [3] holds without finite variance. Our contribution is specific to full feedback.
Lemma 1 (Generalized self-bounding property). Under Assumption 1 with \(\mathop{\mathrm{\mathbb{E}}}[|\xi_t|],\mathop{\mathrm{\mathbb{E}}}[|\zeta_t|] < \infty\) (implied by \(p > 1\)), for all \(\pi \in \mathbb{R}\): \[\label{eq:selfbound} \mathop{\mathrm{\mathbb{E}}}[g(m, V, W) - g(\pi, V, W)] \le L\,|m - \pi|^2.\tag{1}\] Moreover, \(m\) uniquely maximizes \(\pi \mapsto \mathop{\mathrm{\mathbb{E}}}[g(\pi,V,W)]\), and \(\mathop{\mathrm{\mathbb{E}}}[g(m,V,W)] \le 2\sigma_p\).
Proof sketch (full proof in Appendix 8). Write \(\delta = \pi - m\). Define \(h(\delta) = \mathop{\mathrm{\mathbb{E}}}[g(m{+}\delta, V, W)]\). By independence of \(\xi,\zeta\) and dominated convergence (the integrand is bounded by \(|\xi{-}\zeta|\), integrable since \(p > 1\)), one obtains \[\label{eq:derivative} h'(\delta) = -\delta\bigl[f_\xi(\delta) + f_\zeta(\delta)\bigr].\tag{2}\] Since \(h'(\delta)\cdot\delta < 0\) for \(\delta \ne 0\), \(m\) is the unique maximizer. Integrating and using \(f_\xi,f_\zeta \le L\): \(h(0) - h(\delta) = \int_0^{|\delta|} s\,[f_\xi(\pm s) + f_\zeta(\pm s)]\,ds \le L|\delta|^2\).0◻ ◻
Theorem 2 (Parametric). Let \(m(x) = x^\top \phi\), \(\phi \in \mathbb{R}^d\) with \(\|\phi\| \le B\) for a known bound \(B > 0\). Under Assumptions 1–2 with full feedback, assuming \(x_t\) are i.i.d.with \(\|x_t\| \le 1\) a.s.and \(\Sigma := \mathop{\mathrm{\mathbb{E}}}[x_t x_t^\top] \succeq \lambda I_d\) for some \(\lambda > 0\): \(R_T = \widetilde{O}\!\left(L\, d\, \sigma_p^2\, T^{(2-p)/p}\right)\). When \(p{=}2\): recovers \(O(Ld\log T)\) [3]. As \(p \to 1^+\): approaches \(\widetilde{O}(T)\).
Theorem 3 (Nonparametric). Under Assumptions 1–3, with \(x_t\) having density \(\ge \mu_0 > 0\) on \([0,1]^d\): \(R_T = \widetilde{O}\!\left(T^{\;1 - 2\beta(p-1)/(\beta p + d(p-1))}\right)\). When \(p{=}2\): gives \(\widetilde{O}(T^{d/(2\beta+d)})\), the classical rate [11]. As \(p \to 1^+\): gives \(\widetilde{O}(T)\).
Remark 4 (Rate comparison).
| Setting | Variance | Regret |
|---|---|---|
| Parametric, \(p{=}2\) | finite | \(O(Ld\log T)\) [3] |
| Parametric, \(p{\in}(1,2)\) | \(\infty\) | \(\widetilde{O}(T^{(2-p)/p})\) [Thm 2] |
| Nonparametric, \(p{=}2\) | finite | \(\widetilde{O}(T^{d/(2\beta+d)})\) |
| Nonparametric, \(p{\in}(1,2)\) | \(\infty\) | \(\widetilde{O}(T^{1-2\beta(p{-}1)/(\beta p{+}d(p{-}1))})\) [Thm 3] |
The proof has four steps. We first construct a robust estimator of \(\phi\) using coordinate-wise truncated means of score vectors \(S_s = x_s Y_s\), obtaining high-probability error bounds under finite \(p\)-th moments alone (Step 1). We then translate this into a prediction error bound via the empirical Gram matrix (Step 2), decompose the per-epoch regret into good and bad events using the self-bounding property of Lemma 1 (Step 3), and sum a geometric series over doubling epochs to obtain the final rate (Step 4).
Algorithm. Divide \(T\) rounds into \(K = \lceil\log_2 T\rceil\) epochs, where epoch \(k\) spans rounds \([2^{k-1}, 2^k)\) and has length \(n_k = 2^{k-1}\). In epoch \(1\), play any fixed price (contributing \(O(1)\) regret). For \(k \ge 2\), use the \(n = n_{k-1} = 2^{k-2}\) samples from epoch \(k{-}1\) to construct an estimate \(\hat{\phi}_k \in \mathbb{R}^d\), then play \(P_t = x_t^\top \hat{\phi}_k\) for all \(t\) in epoch \(k\).
Step 1: Construction of \(\hat{\phi}_k\) via truncated score vectors. Let \(Y_s = (V_s{+}W_s)/2 = x_s^\top\phi + \eta_s\) where \(\eta_s := (\xi_s{+}\zeta_s)/2\). By the triangle inequality in \(L^p\), \(\|\eta_s\|_p \le \tfrac{1}{2}(\|\xi_s\|_p + \|\zeta_s\|_p) \le \sigma_p\). Form the score vectors \(S_s = x_s Y_s \in \mathbb{R}^d\), so that \(\mathop{\mathrm{\mathbb{E}}}[S_s] = \Sigma\phi\).
For each coordinate \(j \in [d]\), the \(j\)-th component satisfies \([S_s]_j = [x_s]_j\,Y_s\). Since \(|[x_s]_j| \le \|x_s\| \le 1\): \[\label{eq:rawmoment} \mathop{\mathrm{\mathbb{E}}}\bigl[\bigl|[S_s]_j\bigr|^p\bigr] \le \mathop{\mathrm{\mathbb{E}}}[|Y_s|^p] \le \bigl(\|\phi\| + \sigma_p\bigr)^p \le (B + \sigma_p)^p =: u.\tag{3}\] Define the coordinate-wise truncated mean of \(\Sigma\phi\): \[\label{eq:muhat} \hat{\mu}_j = \frac{1}{n}\sum_{s=1}^{n} [S_s]_j \cdot \mathbb{1}\!\bigl\{|[S_s]_j| \le \tau\bigr\}, \quad \tau = \Bigl(\frac{u\,n}{\log(dT)}\Bigr)^{\!1/p},\quad j \in [d].\tag{4}\] By the truncated-mean concentration inequality [6] (Lemma 1, with \(1{+}\varepsilon = p\) in their notation): for each \(j\), with probability \(\ge 1 - 1/(dT)\), \[\label{eq:percoord} |\hat{\mu}_j - [\Sigma\phi]_j| \le 4\,u^{1/p}\!\left(\frac{\log(dT)}{n}\right)^{\!(p-1)/p} = 4(B + \sigma_p)\!\left(\frac{\log(dT)}{n}\right)^{\!(p-1)/p}\!.\tag{5}\] A union bound over \(j \in [d]\) gives: with probability \(\ge 1 - 1/T\), \[\label{eq:muconc} \|\hat{\mu} - \Sigma\phi\|_\infty \le 4(B + \sigma_p)\!\left(\frac{\log(dT)}{n}\right)^{\!(p-1)/p} =: \varepsilon_0.\tag{6}\]
Next, form the empirical Gram matrix \(\hat{\Sigma} = n^{-1}\sum_{s=1}^n x_s x_s^\top\). Since \(\|x_s x_s^\top\|_{\mathrm{op}} \le \|x_s\|^2 \le 1\), by the matrix Hoeffding inequality, with probability \(\ge 1 - 1/T\): \(\|\hat{\Sigma} - \Sigma\|_{\mathrm{op}} \le C_1\sqrt{d\log(dT)/n}\). For \(n \ge 4C_1^2\,d\log(dT)/\lambda^2\) (satisfied in all but \(O(1)\) initial epochs), \(\hat{\Sigma} \succeq (\lambda/2)\,I_d\). Set \(\hat{\phi}_k = \hat{\Sigma}^{-1}\hat{\mu}\).
Step 2: Prediction error bound. Define the “good event” \(\mathcal{G}_k\): both 6 and the matrix Hoeffding bound hold. Then \(\Pr(\mathcal{G}_k) \ge 1 - 2/T\). On \(\mathcal{G}_k\): \[\begin{align} \|\hat{\phi}_k - \phi\|_2 &= \|\hat{\Sigma}^{-1}(\hat{\mu} - \hat{\Sigma}\phi)\|_2 = \|\hat{\Sigma}^{-1}\bigl[(\hat{\mu} - \Sigma\phi) + (\Sigma - \hat{\Sigma})\phi\bigr]\|_2 \notag\\ &\le \frac{2}{\lambda}\Bigl(\sqrt{d}\,\varepsilon_0 + C_1\sqrt{\frac{d\log(dT)}{n}}\,\|\phi\|\Bigr).\label{eq:phierr} \end{align}\tag{7}\] The first term dominates: for \(p < 2\), \((p{-}1)/p < 1/2\), so \(\varepsilon_0 = \Theta(n^{-(p-1)/p})\) decays slower than the Gram error \(\Theta(n^{-1/2})\). Thus for all sufficiently large epochs: \[\label{eq:prederr} |P_t - m(x_t)| = |x_t^\top(\hat{\phi}_k - \phi)| \le \|x_t\| \cdot \|\hat{\phi}_k - \phi\|_2 \le \underbrace{\frac{8(B + \sigma_p)\sqrt{d}}{\lambda}}_{=: C_\phi}\left(\frac{\log(dT)}{n}\right)^{\!(p-1)/p}\!.\tag{8}\]
Step 3: Per-epoch regret. Fix epoch \(k \ge 2\) with length \(n_k = 2^{k-1}\), using an estimator built from \(n = 2^{k-2}\) samples.
Good event (\(\mathcal{G}_k\), probability \(\ge 1 - 2/T\)): By Lemma 1 and 8 , the per-round regret is at most \(L\,|P_t - m(x_t)|^2 \le L\,C_\phi^2\,(\log(dT)/n)^{2(p-1)/p}\). Summing over \(n_k\) rounds: \[\label{eq:goodepoch} R_k^{\mathrm{good}} \le n_k \cdot L\,C_\phi^2\left(\frac{\log(dT)}{n}\right)^{\!2(p-1)/p} = L\,C_\phi^2\,(\log(dT))^{2(p-1)/p}\cdot \frac{2^{k-1}}{(2^{k-2})^{2(p-1)/p}}.\tag{9}\]
Bad event (\(\mathcal{G}_k^c\), probability \(\le 2/T\)): The per-round regret is at most \(\mathop{\mathrm{\mathbb{E}}}[g(m, V, W)] \le 2\sigma_p\) by Lemma 1. Hence: \[\label{eq:badepoch} R_k^{\mathrm{bad}} \le n_k \cdot 2\sigma_p \cdot \Pr(\mathcal{G}_k^c) \le 2^{k-1} \cdot 2\sigma_p \cdot \frac{2}{T}.\tag{10}\]
Step 4: Summing over epochs. Bad-event total. \(\sum_{k=1}^{K} R_k^{\mathrm{bad}} \le \frac{4\sigma_p}{T}\sum_{k=1}^K 2^{k-1} \le \frac{4\sigma_p}{T}\cdot 2T = 8\sigma_p.\)
Good-event total. From 9 , writing \(\alpha := 2(p{-}1)/p \in (0,1)\): \[\label{eq:epochgeo} \sum_{k=2}^{K} R_k^{\mathrm{good}} \le L\,C_\phi^2\,(\log(dT))^\alpha \sum_{k=2}^{K} \frac{2^{k-1}}{2^{(k-2)\alpha}} = L\,C_\phi^2\,(\log(dT))^\alpha \cdot 2^{1+\alpha}\sum_{k=2}^{K} 2^{k(1-\alpha)}.\tag{11}\] Since \(1 - \alpha = (2{-}p)/p > 0\), this is a geometric sum dominated by \(k = K \approx \log_2 T\): \[\label{eq:geosum} \sum_{k=2}^{K} 2^{k(1-\alpha)} \le \frac{2^{(K+1)(1-\alpha)}}{2^{1-\alpha} - 1} \le \frac{2^{1-\alpha}}{2^{1-\alpha}-1}\cdot T^{(2-p)/p}.\tag{12}\] Combining 11 –12 : \[R_T = \sum_{k=1}^K (R_k^{\mathrm{good}} + R_k^{\mathrm{bad}}) \le \underbrace{L\,C_\phi^2\,(\log(dT))^{2(p-1)/p}}_{\text{problem constants}} \cdot \underbrace{\frac{2^{1+\alpha}}{2^{1-\alpha}-1}}_{O(1)} \cdot T^{(2-p)/p} + 8\sigma_p + O(1),\] which gives \(R_T = \widetilde{O}(L\,d\,\sigma_p^2\,T^{(2-p)/p})\) as claimed, where \(C_\phi^2 = O(d\,\sigma_p^2(B/\sigma_p + 1)^2/\lambda^2)\) contributes \(d\,\sigma_p^2\) and problem-dependent constants are absorbed into \(\widetilde{O}\). 0◻
Algorithm (epoch-partition). As in Section 4, divide \(T\) rounds into \(K = \lceil\log_2 T\rceil\) epochs, where epoch \(k\) spans rounds \([2^{k-1},2^k)\) with length \(n_k = 2^{k-1}\). In epoch \(1\), play any fixed price. For each epoch \(k \ge 2\), fix a partition side length \(h > 0\) (to be optimized globally) and tile \([0,1]^d\) into \(M = \lceil h^{-1}\rceil^d\) axis-aligned cells \(\{C_j\}_{j=1}^M\) of side \(h\), with centers \(c_j\). Using the \(n = n_{k-1} = 2^{k-2}\) samples from epoch \(k{-}1\): for each cell \(j\), compute a truncated-mean estimate \(\hat{m}_k(c_j)\) of \(m(c_j)\) from the observations \(\{Y_s : x_s \in C_j\}\) where \(Y_s = (V_s{+}W_s)/2\). In epoch \(k\), for each round \(t\) with \(x_t \in C_j\), play \(P_t = \hat{m}_k(c_j)\).
Step 1: Cell-count concentration. Let \(n_j^{(k)} = |\{s \in \text{epoch}\;k{-}1 : x_s \in C_j\}|\). Since \(x_s\) has density \(\ge \mu_0\) on \([0,1]^d\), \(\mathop{\mathrm{\mathbb{E}}}[n_j^{(k)}] \ge n\,\mu_0\,h^d\). By a multiplicative Chernoff bound, for \(n\,\mu_0\,h^d \ge c_1\log(MT)\): \[\label{eq:chernoff} \Pr\!\left(n_j^{(k)} < \tfrac{1}{2}\,\mu_0\,n\,h^d\right) \le \exp(-\mu_0\,n\,h^d/8) \le \frac{1}{MT}.\tag{13}\] A union bound over all \(M\) cells gives: with probability \(\ge 1 - 1/T\), every cell satisfies \(n_j^{(k)} \ge \mu_0\,n\,h^d/2\). This holds for all epochs \(k\) with \(n \ge n_0 := C\,h^{-d}\log(h^{-d}T)/\mu_0\) (i.e., all but \(O(\log(1/h))\) initial epochs, contributing \(O(\log T)\) total regret).
Step 2: Per-cell truncated-mean concentration. Fix a cell \(j\) in epoch \(k\) with \(n_j \ge \mu_0\,n\,h^d/2\) samples. Each observation \(Y_s = m(x_s) + \eta_s\) where \(\eta_s = (\xi_s{+}\zeta_s)/2\), so \(\|\eta_s\|_p \le \sigma_p\). For \(x_s \in C_j\): \(Y_s = m(c_j) + [m(x_s) - m(c_j)] + \eta_s\). The bias is \(|m(x_s) - m(c_j)| \le L_H h^\beta\) by the Hölder condition. Let \(Z_s = Y_s - [m(x_s) - m(c_j)]\) so that \(\mathop{\mathrm{\mathbb{E}}}[Z_s] = m(c_j)\) with \(\mathop{\mathrm{\mathbb{E}}}[|Z_s - m(c_j)|^p] = \mathop{\mathrm{\mathbb{E}}}[|\eta_s|^p] \le \sigma_p^p\).
However, the learner observes \(Y_s\), not \(Z_s\). The truncated mean of \(\{Y_s\}\) estimates the local average \(\bar{m}_j := n_j^{-1}\sum_{s: x_s \in C_j} m(x_s)\), which satisfies \(|\bar{m}_j - m(c_j)| \le L_H h^\beta\). Let \(B_m = \sup_x |m(x)|\); this is finite since \(m\) is Hölder on the compact domain \([0,1]^d\) (\(B_m \le |m(0)| + L_H\)). Set \(u = (B_m + \sigma_p)^p\). By [6] (Lemma 1), for each cell, w.p.\(\ge 1 - 1/(MT)\): \[\label{eq:cellconc} |\hat{m}_k(c_j) - \bar{m}_j| \le 4\,u^{1/p}\!\left(\frac{\log(MT)}{n_j}\right)^{\!(p-1)/p}\!.\tag{14}\] A union bound over all \(M\) cells gives: with probability \(\ge 1 - 1/T\), 14 holds simultaneously for all cells.
Step 3: Prediction error (bias + estimation). For round \(t\) with \(x_t \in C_j\), on the good event: \[\begin{align} |P_t - m(x_t)| &= |\hat{m}_k(c_j) - m(x_t)| \notag\\ &\le \underbrace{|\hat{m}_k(c_j) - \bar{m}_j|}_{\text{estimation}} + \underbrace{|\bar{m}_j - m(c_j)|}_{\le L_H h^\beta} + \underbrace{|m(c_j) - m(x_t)|}_{\le L_H h^\beta} \notag\\ &\le 4u^{1/p}\!\left(\frac{\log(MT)}{n_j}\right)^{\!(p-1)/p} + 2L_H\,h^\beta.\label{eq:npprederr} \end{align}\tag{15}\] Substituting \(n_j \ge \mu_0 n h^d/2\) and writing \(C_{\mathrm{est}} = 4u^{1/p}(2/\mu_0)^{(p-1)/p}\): \[\label{eq:nppred2} |P_t - m(x_t)| \le C_{\mathrm{est}}\!\left(\frac{\log(MT)}{n\,h^d}\right)^{\!(p-1)/p} + 2L_H\,h^\beta =: \varepsilon_k(h).\tag{16}\]
Step 4: Per-epoch regret. Define the “good event” \(\mathcal{G}_k\): cell counts 13 and estimation 14 both hold. Then \(\Pr(\mathcal{G}_k) \ge 1 - 2/T\) (union of cell-count and estimation events).
Good event: By Lemma 1, per-round regret \(\le L\,\varepsilon_k(h)^2\). Over \(n_k\) rounds: \[\label{eq:npgood} R_k^{\mathrm{good}} \le n_k\,L\,\varepsilon_k(h)^2 \le 2n_k\,L\!\left[C_{\mathrm{est}}^2\!\left(\frac{\log(MT)}{n\,h^d}\right)^{\!2(p-1)/p} + 4L_H^2\,h^{2\beta}\right],\tag{17}\] where we used \((a+b)^2 \le 2(a^2 + b^2)\).
Bad event: \(R_k^{\mathrm{bad}} \le n_k \cdot 2\sigma_p \cdot 2/T\), by Lemma 1.
Step 5: Summing over epochs and balancing. Bad-event total: \(\sum_k R_k^{\mathrm{bad}} \le \frac{4\sigma_p}{T}\sum_k 2^{k-1} \le 8\sigma_p\).
Good-event total (estimation term): Writing \(\alpha = 2(p{-}1)/p\) as before: \[\sum_{k=2}^K n_k \cdot \left(\frac{\log(MT)}{n\,h^d}\right)^{\!\alpha} = (\log(MT))^\alpha\,(h^d)^{-\alpha}\sum_{k=2}^K \frac{2^{k-1}}{(2^{k-2})^\alpha}.\] This geometric sum has the same form as 11 –12 ; it is dominated by \(k = K\) and evaluates to \(O(T^{(2-p)/p}\cdot h^{-2d(p-1)/p}\cdot(\log T)^\alpha)\).
Good-event total (bias term): \(\sum_k n_k \cdot h^{2\beta} = T\,h^{2\beta}\).
Combining: \(R_T \le L\bigl[C_{\mathrm{est}}^2\,(\log T)^\alpha\,T^{(2-p)/p}\,h^{-2d(p-1)/p} + L_H^2\,T\,h^{2\beta}\bigr] + O(\sigma_p)\).
Balancing. Set the two terms equal. From \(T^{(2-p)/p}\,h^{-2d(p-1)/p} = T\,h^{2\beta}\) we get \(h^{2\beta + 2d(p-1)/p} = T^{-2(p-1)/p}\). Solving: \[\label{eq:hopt} h = T^{-(p-1)/(\beta p + d(p-1))}.\tag{18}\] Substituting into \(T\,h^{2\beta}\): \[T\,h^{2\beta} = T^{1 - 2\beta(p-1)/(\beta p + d(p-1))}.\] Therefore: \[\label{eq:npfinal} R_T = \widetilde{O}\!\left(T^{\;1 - 2\beta(p-1)/(\beta p + d(p-1))}\right),\tag{19}\] with problem constants \(L, L_H, \sigma_p, B_m, \mu_0, d, \beta\) absorbed into \(\widetilde{O}\).
Sanity checks. \(p{=}2\): \(h = T^{-1/(2\beta+d)}\), \(R_T = \widetilde{O}(T^{d/(2\beta+d)})\), recovering Stone [11]. \(p \to 1^+\): \(h \to T^0 = 1\) (single cell, no spatial resolution), \(R_T \to \widetilde{O}(T)\). 0◻
Proposition 5. Under the conditions of Theorem 3, assuming \(f_\xi(0) + f_\zeta(0) > 0\), \[R_T = \Omega\!\left(T^{\;1 - 2\beta(p-1)/(\beta p + d(p-1))}\right).\]
Proof. Step 1 (Assouad reduction). Partition \([0,1]^d\) into \(M = h^{-d}\) subcubes of side \(h\). For each \(\theta \in \{-1,+1\}^M\), define \(m_\theta(x) = \sum_{j=1}^M \theta_j\,\varepsilon\,\psi_j(x)\) where \(\psi_j\) is a \((\beta,L_H)\)-Hölder bump supported on subcube \(j\) with \(\psi_j(c_j)=1\). The Hölder constraint requires \(\varepsilon \le L_H h^\beta\). By Assouad’s method, any algorithm satisfies \[\label{eq:assouad} \sup_\theta R_T(m_\theta) \ge \frac{M}{2}\sum_{t: x_t \in \text{subcube}}\!\! c_0\,\varepsilon^2\cdot\bar{p}_e,\tag{20}\] where \(\bar{p}_e\) is the average pairwise testing error and \(c_0 = \inf_{|s|\le\varepsilon}[f_\xi(s)+f_\zeta(s)]/2 > 0\) arises from the reverse self-bounding property: \(h(0) - h(\varepsilon) = \int_0^\varepsilon s[f_\xi(s)+f_\zeta(s)]\,ds \ge c_0\,\varepsilon^2\). With \(x_t\) having density \(\ge\mu_0\), each subcube receives \(n \ge \mu_0 Th^d/2\) rounds (w.h.p.). Hence \[\label{eq:assouad2} R_T \ge \frac{c_0}{4}\,T\,\varepsilon^2\cdot\bar{p}_e.\tag{21}\]
Step 2 (Full-feedback KL). Fix subcube \(j\). Under hypothesis \(m_j = \varepsilon\), the learner observes \((V_t,W_t) = (\varepsilon+\xi_t,\,\varepsilon+\zeta_t)\). By independence, the per-round KL divergence for observing the pair is \[\mathrm{KL}(P_\varepsilon^{(V,W)} \| P_0^{(V,W)}) = \mathrm{KL}(P_\varepsilon^\xi \| P_0^\xi) + \mathrm{KL}(P_\varepsilon^\zeta \| P_0^\zeta) = 2\,\mathrm{KL}(P_\varepsilon \| P_0).\] This is exactly twice the KL from observing a single marginal—full feedback provides no order-of-magnitude advantage over the mean oracle \(Y_t = (V_t{+}W_t)/2\).
Step 3 (Moment-matching construction). The lower bound for mean estimation under \(p\)-th moment [6] (Theorem 2) uses discrete two-point distributions. To satisfy our bounded-density assumption, we smooth: replace each atom \(\delta_x\) with a uniform bump of width \(1/L\) centered at \(x\). This preserves the mean gap exactly, changes the \(p\)-th moment by \(O(1/L)\), and yields densities \(\le L\). Crucially, the KL divergence is exactly preserved: within each bump region, both distributions share the same support, so the likelihood ratio equals the atom-weight ratio, independent of bump width. (Non-overlap of bumps requires \(1/L < 1/\gamma\) where \(\gamma = (2\varepsilon)^{1/(p-1)}\), i.e., \(\varepsilon < L^{p-1}/2\); this holds for all large \(T\).)
The smoothed distribution has \(p\)-th moment at most \(\sigma_p^p + (2L)^{-p} \le \sigma_p^p(1+o(1))\) for \(\sigma_p\) bounded away from \(0\), so the moment constraint is satisfied for all sufficiently large \(T\). The resulting pair \(P_0,P_1\) has densities \(\le L\), \(p\)-th moments \(\le 2\sigma_p^p\), means differing by \(\varepsilon\), and \[\label{eq:klmoment} \mathrm{KL}(P_0 \| P_1) = O(\varepsilon^{p/(p-1)}).\tag{22}\] With \(n \asymp Th^d\) samples per subcube, the total KL from full feedback is \(2n\cdot O(\varepsilon^{p/(p-1)})\). By Le Cam’s inequality, \(\bar{p}_e \ge \frac{1}{2}(1 - \sqrt{n\cdot\mathrm{KL}/2})\). For \(\bar{p}_e \ge 1/4\), we need \(n \cdot \varepsilon^{p/(p-1)} \le c\), giving \[\label{eq:epsbarrier} \varepsilon \ge c'\,(Th^d)^{-(p-1)/p}.\tag{23}\]
Step 4 (Optimization). Set both constraints active: \((Th^d)^{-(p-1)/p} = h^\beta\), i.e., \(h^{\beta + d(p-1)/p} = T^{-(p-1)/p}\), giving \(h = T^{-(p-1)/(\beta p + d(p-1))}\). Then \(\varepsilon = h^\beta = T^{-\beta(p-1)/(\beta p + d(p-1))}\). From 21 : \[R_T \ge \frac{c_0}{4}\,T\,\varepsilon^2 = \Omega\!\left(T^{\;1 - 2\beta(p-1)/(\beta p + d(p-1))}\right).\] Sanity checks. \(p{=}2\): exponent \(= d/(2\beta{+}d)\), matching Stone [11]. \(p \to 1^+\): exponent \(\to 1\), matching trivial barrier. 0◻ ◻
Remark 6 (Parametric lower bound). The parametric rate \(\widetilde{O}(T^{(2-p)/p})\) of Theorem 2 is also tight. Apply the same Assouad argument with \(M = d\) hypotheses on coordinate directions: \(m_\theta(x) = \varepsilon\sum_{j=1}^d \theta_j x_j\), \(\theta \in \{-1,+1\}^d\). Each hypothesis is linear with \(\|\phi_\theta\| = \varepsilon\sqrt{d}\). The moment-matching barrier gives \(\varepsilon \ge c\,(T/d)^{-(p-1)/p}\), and Assouad yields \(R_T \ge c'\,d\,\varepsilon^2 = \Omega(d\,T^{-2(p-1)/p}) = \Omega(d\,T^{(2-p)/p})\). Alternatively, take \(\beta \to \infty\) in Proposition 5: the exponent \(1 - 2\beta(p{-}1)/(\beta p + d(p{-}1)) \to (2{-}p)/p\), recovering the parametric rate.
Established: Lemma 1 extends the self-bounding property to \(\mathbb{R}\)-valued valuations under bounded density and \(\mathop{\mathrm{\mathbb{E}}}[|\xi|] < \infty\) alone (no variance needed); truncated mean optimality under \(p\)-th moment [6], [8]; epoch-based upper bounds (parametric and nonparametric); matching lower bounds via Assouad + moment matching (Proposition 5, Remark 6). Remaining: optimality of epoch-based approach vs.online alternatives; extension to \(p \ge 2\) with sub-Gaussian tails.
Open questions. (Q1) Can an online robust estimator eliminate the epoch-based \(O(\log T)\) overhead? (Q2) Lemma 1 shows the exponent is exactly \(2\) for all bounded-density distributions. Can specific tail shapes (e.g., sub-Gaussian) improve the constant? (Q3) Heteroskedastic extension: if \(\sigma_p(x)\) depends on context, can regret scale with \(\mathop{\mathrm{\mathbb{E}}}[\sigma_p(x_t)^2]\) rather than \(\max_x \sigma_p(x)^2\)?
We prove all three claims: the self-bounding inequality 1 , the unique maximizer property, and the bound \(\mathop{\mathrm{\mathbb{E}}}[g(m,V,W)] \le 2\sigma_p\).
Step 1: Noise-coordinate representation. Write \(\delta = \pi - m\). Substituting \(V = m + \xi\), \(W = m + \zeta\): \[\label{eq:app:gnoise} g(m{+}\delta,\;m{+}\xi,\;m{+}\zeta) = (\xi{-}\zeta)\,\mathbb{1}\{\zeta \le \delta \le \xi\} + (\zeta{-}\xi)\,\mathbb{1}\{\xi \le \delta \le \zeta\}.\tag{24}\] Define \(h(\delta) = \mathop{\mathrm{\mathbb{E}}}[g(m{+}\delta,\, V,\, W)]\). We must show \(h(0) - h(\delta) \le L\,|\delta|^2\).
Step 2: Decomposition by case. Define the one-sided expectations \(\Psi_\xi(\delta) = \mathop{\mathrm{\mathbb{E}}}[(\xi - \delta)^+]\) and \(\Phi_\xi(\delta) = \mathop{\mathrm{\mathbb{E}}}[(\delta - \xi)^+]\), and analogously for \(\zeta\). Split \(h = I_1 + I_2\) according to the two cases in 24 : \[\begin{align} I_1(\delta) &= \iint_{\zeta \le \delta \le \xi} (\xi - \zeta)\,f_\xi(\xi)\,f_\zeta(\zeta)\,d\xi\,d\zeta = \int_{-\infty}^{\delta}\!f_\zeta(\zeta)\!\int_{\delta}^{\infty}\!(\xi - \zeta)\,f_\xi(\xi)\,d\xi\,d\zeta, \tag{25}\\ I_2(\delta) &= \iint_{\xi \le \delta \le \zeta} (\zeta - \xi)\,f_\xi(\xi)\,f_\zeta(\zeta)\,d\xi\,d\zeta = \int_{\delta}^{\infty}\!f_\zeta(\zeta)\!\int_{-\infty}^{\delta}\!(\zeta - \xi)\,f_\xi(\xi)\,d\xi\,d\zeta. \tag{26} \end{align}\]
Step 3: Differentiation via Leibniz rule. We differentiate each integral with respect to \(\delta\). Dominated convergence justifies passing the derivative inside: the integrand in 25 is bounded by \(|\xi - \zeta| \le |\xi| + |\zeta|\), which is integrable since \(\mathop{\mathrm{\mathbb{E}}}[|\xi|] < \infty\) (implied by \(p > 1\)).
Applying the Leibniz integral rule to 25 (differentiating the upper limit of the inner integral and the upper limit of the outer integral): \[\label{eq:app:I1prime} I_1'(\delta) = f_\zeta(\delta)\!\int_{\delta}^{\infty}\!(\xi - \delta)\,f_\xi(\xi)\,d\xi - f_\xi(\delta)\!\int_{-\infty}^{\delta}\!(\delta - \zeta)\,f_\zeta(\zeta)\,d\zeta = f_\zeta(\delta)\,\Psi_\xi(\delta) - f_\xi(\delta)\,\Phi_\zeta(\delta).\tag{27}\] Similarly, from 26 : \[\label{eq:app:I2prime} I_2'(\delta) = -f_\zeta(\delta)\,\Phi_\xi(\delta) + f_\xi(\delta)\,\Psi_\zeta(\delta).\tag{28}\] Combining: \[\label{eq:app:hprime95raw} h'(\delta) = f_\zeta(\delta)\bigl[\Psi_\xi(\delta) - \Phi_\xi(\delta)\bigr] + f_\xi(\delta)\bigl[\Psi_\zeta(\delta) - \Phi_\zeta(\delta)\bigr].\tag{29}\]
Step 4: Simplification to the key formula. The pointwise identity \((\xi - \delta)^+ - (\delta - \xi)^+ = \xi - \delta\) yields, upon taking expectations (valid since \(\mathop{\mathrm{\mathbb{E}}}[|\xi|] < \infty\)): \[\label{eq:app:psiphi} \Psi_\xi(\delta) - \Phi_\xi(\delta) = \mathop{\mathrm{\mathbb{E}}}[\xi] - \delta = -\delta,\tag{30}\] and similarly \(\Psi_\zeta(\delta) - \Phi_\zeta(\delta) = -\delta\). Substituting into 29 : \[\label{eq:app:hprime} h'(\delta) = -\delta\bigl[f_\xi(\delta) + f_\zeta(\delta)\bigr].\tag{31}\] Verification: \(h'(0) = 0\) (consistent with \(m\) being a critical point), \(h'(\delta) > 0\) for \(\delta < 0\), and \(h'(\delta) < 0\) for \(\delta > 0\) (consistent with \(m\) being a maximum).
Step 5: Integration and the self-bounding inequality. For \(\delta > 0\) (the case \(\delta < 0\) is symmetric by the substitution \(s \mapsto -s\)): \[\label{eq:app:integrate} h(0) - h(\delta) = -\int_0^{\delta} h'(s)\,ds = \int_0^{\delta} s\bigl[f_\xi(s) + f_\zeta(s)\bigr]\,ds.\tag{32}\] Since \(f_\xi(s) + f_\zeta(s) \le 2L\) for all \(s\): \[\label{eq:app:bound} h(0) - h(\delta) \le 2L\int_0^{|\delta|} s\,ds = 2L\cdot\frac{|\delta|^2}{2} = L\,|\delta|^2.\tag{33}\] This is precisely 1 since \(h(0) - h(\delta) = \mathop{\mathrm{\mathbb{E}}}[g(m,V,W) - g(\pi,V,W)]\) and \(|\delta| = |\pi - m|\).
Unique maximizer: From 31 , \(h'(\delta) = 0\) iff \(\delta = 0\) or \(f_\xi(\delta) + f_\zeta(\delta) = 0\). Since \(f_\xi(\delta) + f_\zeta(\delta) = 0\) for \(|\delta| > R\) does not prevent \(\delta = 0\) from being the unique global maximizer (the integral 32 is strictly positive for all \(\delta \ne 0\) in a neighborhood of \(0\), and \(h\) is continuous with \(h(\delta) \to 0\) as \(|\delta| \to \infty\) by dominated convergence).
Gain bound: \(g(m, m{+}\xi, m{+}\zeta) = |\xi - \zeta|\,\mathbb{1}\{\min(\xi,\zeta) \le 0 \le \max(\xi,\zeta)\} \le |\xi| + |\zeta|\). Hence \(\mathop{\mathrm{\mathbb{E}}}[g(m,V,W)] \le \mathop{\mathrm{\mathbb{E}}}[|\xi|] + \mathop{\mathrm{\mathbb{E}}}[|\zeta|] \le 2\sigma_p\) by Jensen’s inequality (\(\mathop{\mathrm{\mathbb{E}}}[|\xi|] \le (\mathop{\mathrm{\mathbb{E}}}[|\xi|^p])^{1/p} = \sigma_p\) for \(p \ge 1\)). 0◻