Truthful Calibration Measures for Sequential Prediction

Truthful Calibration Measures for Sequential Prediction Anagha Gokul∗

Jason Hartline†

Northeastern University

Northwestern University

Lunjia Hu‡

Jonathan Ullman§

Northeastern University

Northeastern University ¶

arXiv:2608.21348v1 [cs.DS] 21 Aug 2026

Yifan Wu

Microsoft Research

Abstract Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Recently, Haghtalab et al. [14] proposed an approximately truthful calibration measure in the online setting, leaving open whether exact truthfulness is compatible with the completeness and soundness of a calibration measure. We answer this question in the negative for sequential binary prediction. On the one hand, we show that exact truthfulness is incompatible with the completeness and soundness of a calibration measure, even for independent outcomes. On the positive side, we show that this impossibility is specific to exact truthfulness. We provide two general reductions from a base calibration measure: one produces an additively approximately truthful calibration measure, and the other produces a multiplicatively approximately truthful calibration measure. Using the latter reduction, for every

0 < ε < 1 we construct a sound and complete calibration measure that is 1 + exp − 21 T (1−ε)/2 -multiplicatively truthful. This improves the approximate truthfulness guarantee of Haghtalab et al. [14].

∗

Khoury College of Computer Sciences. Email: gokul.a@northeastern.edu. Department of Computer Science. Email: hartline@northwestern.edu. ‡ Khoury College of Computer Sciences. Email: lunjia@alumni.stanford.edu. § Khoury College of Computer Sciences. Email: j.ullman@northeastern.edu. Supported by NSF awards CNS2232692 and CNS-2247484. ¶ Microsoft Research New England. Email: yifan.wu2357@gmail.com. †

1

Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 4

2 Technical Overview 2.1 Impossibility of Truthfulness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Approximate truthfulness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 6 7

3 Preliminaries 3.1 Sequential Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Calibration Measures, Completeness and Soundness . . . . . . . . . . . . . . . . . . 3.3 Truthfulness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 8 9

4 Product-Distribution Impossibility

10

5 Quantitative Lower Bounds from Impossibility 13 5.1 Hybrid Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6 Approximately Truthful Reductions 6.1 The Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Additively Approximate Truthfulness . . . . . . . . . . . . . . . . . . . . . . 6.1.2 Multiplicatively Approximate Truthfulness . . . . . . . . . . . . . . . . . . . 6.2 Preserving Soundness and Completeness . . . . . . . . . . . . . . . . . . . . . . . . .

16 16 17 18 19

A Truthfulness and Weak Soundness A.1 The Comparison Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Constant-Predictor Consequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Weak Constant-Predictor Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 22 26 27

B Concentration for Smooth Calibration Error

29

2

1

Introduction

Probabilistic prediction is increasingly important in high-stakes decision making, where predictions are used to quantify uncertainty. Dawid [5] proposed calibration as a desirable property of probabilistic reports. Calibration requires predictions to be conditionally unbiased, thus interpretable at face value. For example, if a weather predictor reports a 70% chance of rain on many days, then rain should occur on 70% of those days. Formally, for every report value p, conditional on report p, the event should occur with frequency approximately p. A calibration measure assigns an error to a sequence of probability reports and outcomes to quantify the level of miscalibration. Classical examples include the Expected Calibration Error (ECE) and its smooth variants [13, 18]. Concretely, given T samples (pt , yt )t∈[T ] of binary probability reports, ECE calculates the averaged report bias in the sample. For every report value p, write P np as the number of times that p is reported, and p̂ := n1p t:pt =p yt as the empirical frequency conditional on report value p. The report bias is defined as the absolute distance |p̂ − p| between the conditional empirical frequency p̂ and the reported value p. ECE is the average bias weighted by the fraction np /T of samples assigned report p: ECET (p1:T , y) :=

X np p∈R

T

|p̂ − p| ,

where R is the set of values reported by the predictor. However, ECE does not incentivize truthful reporting even when the predictor knows the ground-truth distribution. Example 1.1 shows that while a truthful predictor  √data-generating  suffers Ω 1/ T sampling error, a strategic predictor can achieve ECE= 0 by misreporting. Example 1.1 ([14]). Split the time horizon into three equal blocks. In the first block, outcomes are independent fair coin flips. In the second block, every outcome is 0. In the third block, every outcome is 1. The truthful predictor reports 1/2 in the first block, 0 in the second block, and 1 in the third block. The deterministic  √  blocks are then perfectly calibrated. The only contribution to ECE comes from the Θ 1/ T sampling error in the first block. A strategic predictor may look perfectly calibrated by using the later deterministic blocks to correct this sampling error. It also reports 1/2 throughout the first block. After seeing that block, if the conditional empirical frequency at report 1/2 is above 1/2, the predictor reports 1/2 on enough later zero outcomes to balance them, and similarly otherwise. At the end, the report 1/2 has exactly 1/2 of ones. Thus the strategic predictor obtains ECE= 0. A recent line of work studies whether calibration measures can be made truthful. Haghtalab et al. [14] initiated this direction in the sequential prediction setting by proposing an approximately truthful calibration measure. In the batch setting, Hartline et al. [16] and Lu et al. [20] show that perfectly truthful calibration measures exist. These results leave a natural gap: whether exact truthfulness is possible in the sequential prediction problem. Our paper answers this question negatively. We show that exact truthfulness is incompatible with the completeness and soundness requirements of a calibration measure in the sequential prediction problem. On the positive side, we reduce the construction of an approximately truthful calibration measure to finding a sound and complete base calibration measure that is uniformly complete.

3

1.1

Our Contributions

Our first result shows that exact truthfulness is impossible for sequential calibration. The main idea is that completeness and soundness require a calibration measure to assign lower expected error to calibrated product samples than to miscalibrated ones, when the sample size is sufficiently large. In the sequential setting, that comparison can occur on a rare history. With exponentially small but nonzero probability, the truthful transcript can look very miscalibrated, while an alternative transcript induced by a strategic report looks more calibrated. When this happens, the strategic predictor can lower expected calibration error by deviating to the alternative report. In Section 4, we formalize this intuition using a hybrid argument. Recall that completeness and soundness imply the separation of calibrated distribution from a miscalibrated one, when there are T i.i.d. prediction outcome pairs from these distributions. A hybrid is a mixture where the first m pairs are drawn from a calibrated distribution, and the later T −m pairs are from a miscalibrated distribution. This hybrid argument finds a local profitable deviation at sample m under some realization of prefix, by enumerating m over all such hybrids. Our second result gives a quantitative lower bound for the gap from being truthful, which is exponentially small in T . In Section 5, we lower bound the largest online gain from strategic misreporting by an exponentially small multiple of the offline distinguishing gap between the calibrated and miscalibrated distributions. The exponential factor reflects the probability of reaching the rare prefix realization on which the local strategic deviation is useful. Our third result shows that the impossibility is specific to exact truthfulness. In Section 6, we reduce the construction of an approximately truthful calibration measure to finding a sound and complete base calibration measure that is uniformly complete. Here, uniformly complete means that the truthful error can be uniformly bounded by the sampling error. The reduction proceeds in two stages. Subtracting a vanishing sampling-error threshold first gives an additively approximately truthful measure. Adding a vanishing squared-loss term to this measure then strengthens the guarantee to (1 + o(1))-multiplicative truthfulness. Both stages preserve the completeness and soundness of the base measure. Applying the multiplicative reduction with smooth calibration error

as the base measure, using the concentration bound in Appendix B, gives a 1 + exp − 21 T (1−ε)/2 multiplicatively truthful calibration measure for every 0 < ε < 1.

1.2

Related Work

Existing literature proposes several desiderata of calibration measures, including truthfulness, continuity, and decision-theoretic implications. Sequential calibration. The classical literature on sequential forecasting established asymptotically calibrated procedures, including against adversarial outcome sequences [10]. Subsequent work has investigated finite-horizon rates, developing stronger lower bounds for calibration error [21] and studying the related distance-to-calibration objective [23, 1]. Most recently, Dagan et al. [4] broke the longstanding T 2/3 barrier for sequential calibration. Truthfulness. We discuss truthfulness first. Truthfulness was introduced for calibration measures by Haghtalab et al. [14]. Recent literature observes that existing calibration measures can reward strategic misreporting (e.g., [9, 21]). Haghtalab et al. [14] introduce a multiplicatively approximately truthful calibration measure for the sequential prediction problem. Qiao and Zhao [22] show that truthfulness is incompatible with decision-theoretic calibration guarantees. In the batch setting, Hartline et al. [16] show that perfect truthfulness is compatible with soundness and

4

completeness, and Lu et al. [20] extend this direction to multi-class prediction. We consider the sequential prediction problem. Our results identify the incompatibility of exact truthfulness with the completeness and soundness of calibration measures, and improve the approximation in Haghtalab et al. [14]. Continuity. Continuity is another natural desideratum. Continuity requires that a calibration measure should be robust to small perturbations of the reported probabilities, with the outcomes held fixed. This rules out ECE and binned ECE, where an empirically calibrated sequence can acquire large error after arbitrarily small perturbations of the reports because the perturbation splits previously identical reports into separate buckets. The distance-to-calibration framework of Blasiok et al. [3] and smooth calibration error [18] propose continuous calibration measures. Decision-theoretic guarantees. A third desideratum concerns decision-theoretic guarantees for downstream decision makers. This desideratum is orthogonal to the scope of our paper, but we include it here for reference. A calibration measure should upper bound the swap regret of any downstream decision maker. Equivalently, calibration guarantees that decision makers who best respond to the report do not lose payoff relative to the same predictor after calibration. Kleinberg et al. [19] initiate this decision-theoretic perspective and propose relaxations based on no-externalregret guarantees for downstream decision makers, which are strictly weaker than swap regret. Hu and Wu [17] consider the equivalent no-swap-regret guarantee. They propose calibration decision loss, the maximum swap regret over payoff-bounded downstream decision tasks, and show that vanishing error gives simultaneous no-regret guarantees for all such tasks. In subsequent work, Hartline et al. [15] show that smooth or distance-based calibration can be post-processed to obtain small ECE and calibration decision loss. Qiao and Zhao [22] study how decision-theoretic guarantees interact with truthfulness and construct a calibration measure that is both approximately truthful and decision-theoretic under smooth distributions. More recently, Bairaktari et al. [2] introduce soft-binned calibration decision loss (SCDL), which is fully actionable for unrestricted swap regret under a specified rounded response rule and is testable at a nearly optimal rate. Independent work on impossibility of truthfulness. Independent of our work, two recent manuscripts by Dewasurendra also showed impossibility results for designing perfectly truthful, sound, and complete calibration measures for sequential prediction [7, 8]. The truthfulness, soundness, and completeness notions considered in their work differ subtly from our main impossibility result in Section 4. In particular, they require the stronger notion of truthfulness that allows the true outcomes y1 , . . . , yT to follow an arbitrary joint distribution on {0, 1}T . Our main impossibility result in Section 4 only requires truthfulness to hold when the outcomes y1 , . . . , yT follow a product distribution. The soundness and completeness notions considered by Dewasurendra are also different and are aligned with the setting of [14]. Our impossibility results in Appendix A uses truthfulness, soundness, and completeness notions closer to the work of Dewasurendra.

2

Technical Overview

Before giving the formal definitions, we summarize the proof ideas behind the three main parts of the paper: the exact impossibility, the quantitative lower bounds obtained from that proof, and the approximate construction. The notation used here is made formal in Section 3; in particular, δz denotes the point mass at z and x+ = max{x, 0}.

5

2.1

Impossibility of Truthfulness.

The source of the impossibility is that exact truthfulness asks the predictor to report the next conditional mean even on rare histories where the transcript so far looks badly miscalibrated. Completeness and soundness, however, reward transcripts that look calibrated. On such histories, a strategic predictor may prefer a report that repairs the accumulated imbalance. Warm-Up Example: Symmetric Case We first illustrate the idea under a symmetry assumption: suppose the calibration measure depends only on the empirical distribution of the transcript, not on the order of the time steps. Let T = 2n. In the first n rounds the ground-truth datagenerating distribution is Bernoulli with mean 1/2, so the truthful report is 1/2. In the remaining n rounds the outcome is deterministically 1, so the truthful report is 1. Now condition on the rare history where every outcome in the first block is realized to be 0, which happens with probability 2−n . On that history, the truthful history of prediction-outcome pairs (r, y) contains n copies of (1/2, 0) followed by n copies of (1, 1). A strategic predictor can behave truthfully everywhere except on this rare history. If the first block is all zeros, it keeps reporting 1/2 during the deterministic-one rounds instead of switching to 1. Then the transcript contains n copies of (1/2, 0) and n copies of (1/2, 1), which looks perfectly calibrated at report 1/2. Completeness and soundness then favor the calibrated history produced by the strategic predictor. Thus, the strategic predictor has a lower error on this rare history and achieves the same error as the truthful predictor everywhere else. Truthful reporting is then not an optimal strategy. Hybrid Argument: General Case The full result removes the symmetry assumption of the calibration measure using a hybrid argument. We start with two offline one-sample distributions over prediction-outcome pairs, one calibrated and one miscalibrated. Completeness and soundness imply that, for all sufficiently large T , their T -fold product distributions are separated in expectation. The hybrid argument then changes the transcript one coordinate at a time, so some adjacent pair of hybrids must carry a positive part of the endpoint gap. That coordinate becomes the time step where the strategic online predictor benefits from a deviating report. For the overview, take the fair-coin pair D = (1/2)δ(1/2,0) + (1/2)δ(1/2,1)

and

D′ = (1/2)δ(1/2,0) + (1/2)δ(1,1) .

The distribution D is calibrated. The distribution D′ is miscalibrated because the report 1/2 appears only with outcome 0. For all sufficiently large T , the calibration measure gives smaller expected error to DT than to (D′ )T . To connect these two histories, we define T + 1 hybrids, which are random sequences of prediction-outcome pairs. Hybrid j ∈ {0, . . . , T } is constructed such that: • the first j samples are drawn from the miscalibrated distribution D′ ; • the later T − j samples are drawn from the calibrated distribution D. The first hybrid, with switching point 0, is fully calibrated, and the last hybrid, with switching point T , is fully miscalibrated. Hence some adjacent pair of hybrids must account for a positive part of the endpoint gap. These two hybrids share the same prefix before time m, where each pair is either (1/2, 0) or (1, 1), and the same calibrated Bernoulli(1/2) tail after time m. At time m, they agree on the zero-outcome pair (1/2, 0) and differ only when the outcome is 1: the calibrated version reports 1/2 with (1/2, 1), while the miscalibrated version reports 1 with (1, 1). Since this 6

adjacent gap is positive on average over the common prefix, there is a fixed prefix realization of length m − 1 for which the same local preference holds. This fixed prefix is the rare history where the predictor benefits from misreporting: • it is generated by m − 1 i.i.d. draws from D′ , so the reports are either 1/2 or 1, which specifies the construction of the data-generating distribution; • conditioning on the prefix, if the mth outcome is deterministically 1 and the later rounds are drawn from the calibrated Bernoulli(1/2) tail, the expected calibration error is lower when time m reports 1/2 than when it reports the truthful value 1. Lower Bounds for Approximate Truthfulness The same proof gives a quantitative statement. Let ∆T (1/2) be the offline distinguishing gap between (D′ )T and DT , and let Advprod (Cal) T be the largest additive gain achievable by a non-anticipating misreporting strategy under a product data-generating distribution. In the fair-coin case, the hybrid proof yields 22−T ∆T (1/2). T The factor is exponentially small because the online strategy must wait for the particular prefix selected by the hybrid argument. The appendix generalizes the impossibility of truthfulness under the weak completeness and soundness requirements in Haghtalab et al. [14]. That work requires a calibration measure to distinguish the calibration from miscalibration of only constant predictors. This weak completeness asks that a constant predictor who reports the true Bernoulli mean has small expected error, while soundness only asks that a constant report separated from that mean has large expected error. Our main definitions are stronger: they require the measure to distinguish calibrated from miscalibrated one-sample distributions for arbitrary predictors. A comparison lemma shows that, under truthfulness, the expected error of a constant misreport q under Ber(p)T is at most p(1 − q)/(q(1 − p)) times the error of the truthful constant report p. This bound is independent of T , and therefore shows the impossibility of truthfulness under the weak completeness and soundness requirement. (Cal) ≥ Advprod T

2.2

Approximate truthfulness.

We reduce the construction of an approximately truthful calibration measure to finding a sound and complete base calibration measure that is uniformly complete. Additively Approximate Truthfulness Given such a base measure, the additive truthfulness construction subtracts a sampling-error threshold τT :
Caladd T (r, y) = ErrT (r, y) − τT + . We require the base measure Err to be uniformly complete: for any ground truth distribution, the tail after extracting a sampling error τT can be bounded. The additively approximate truthfulness follows immediately from the fact that the error measure is non-negative. Multiplicatively Approximate Truthfulness The multiplicative approximation adds a small normalized squared-loss term to the additive one: T

Calmult (r, y) = Caladd T T (r, y) + λT ·

1X (rt − yt )2 . T t=1

7

The squared-loss term is proper round by round and gives a universal lower bound on the expected P ∗ error of every strategy at the scale of the intrinsic variance t E[pt (1 − p∗t )]/T . Consequently, Calmult is 1 + ηT /λT multiplicatively truthful. T

3

Preliminaries

We study binary sequential prediction over a fixed horizon T ∈ N. Write [T ] = {1, . . . , T } and let Ber(p) denote the Bernoulli distribution with mean p. A realization is denoted Y = (Y1 , . . . , YT ) ∈ {0, 1}T . We write δz for the point mass at z and x+ = max{x, 0} for the positive part of a real number.

3.1

Sequential Prediction

A data-generating distribution is a joint distribution over the outcome sequence Y = (Y1 , . . . , YT ). At each time t, a predictor observes the past outcomes Y<t = (Y1 , . . . , Yt−1 ) and then reports a probability rt ∈ [0, 1]. The predictor is assumed to know the ground-truth data-generating distribution before play begins. We use r for an arbitrary report sequence and p∗ for the truthful sequence. The first object we need is the set of admissible reporting rules. The non-anticipation restriction below is what makes the problem sequential: reports may depend on the past and on the known ground truth, but not on future realized outcomes. Definition 3.1 (Prediction strategy). A prediction strategy, relative to a fixed known groundtruth data-generating distribution, is a sequence of maps St : {0, 1}t−1 → [0, 1]. Given an outcome sequence Y , it produces the predictable report vector
S(Y ) = S1 , S2 (Y1 ), . . . , ST (Y<T ) . The maps St may depend on this data-generating distribution, but not on future realized outcomes. We suppress this dependence from the notation. Two classes of data-generating distributions are used throughout. In the product-distribution case, there are numbers p∗1 , . . . , p∗T ∈ [0, 1] and the outcomes are generated independently as Yt ∼ Ber(p∗t ). In the correlated case, the ground truth is an arbitrary joint distribution Π on {0, 1}T , and the truthful report is the conditional mean p∗t (Y<t ) = EΠ [Yt | Y<t ]. Thus p∗t is predictable with respect to the outcome history.

3.2

Calibration Measures, Completeness and Soundness

A calibration measure assigns a non-negative error to a transcript of probability reports and realized outcomes; all truthfulness and soundness requirements are constraints on this map. Definition 3.2 (Calibration measure). A calibration measure is a map CalT : [0, 1]T × {0, 1}T → R≥0 . Smaller values of CalT represent better calibration. 8

When Zt = (rt , yt ) ∈ [0, 1] × {0, 1} and Z = (Z1 , . . . , ZT ), we also write CalT (Z) = CalT (r1 , . . . , rT ; y1 , . . . , yT ). For a distribution D over prediction-outcome pairs, DT denotes the distribution of T independent draws from D. A sequence distribution is a probability distribution Λ on ([0, 1] × {0, 1})T . Completeness and soundness distinguish calibrated data from miscalibrated data. The following definition fixes what calibrated means for a one-sample distribution over a report and an outcome. Definition 3.3 (Calibrated distribution). A distribution D over [0, 1] × {0, 1} is calibrated if, for (R, Y ) ∼ D, E[Y | R] = R almost surely. Completeness and soundness formalize the statistical meaning of a calibration measure. Following Hartline et al. [16], we use the sample-access asymptotic definitions: calibrated product distributions should have vanishing expected error, while miscalibrated product distributions should have error bounded away from zero in the limit. Since our measure CalT is written directly as a function of a length-T transcript, evaluating it on Z ∼ DT is the same sample-access experiment. Completeness is the vanishing-error side of the statistical guarantee: if the reports are genuinely calibrated, then the expected calibration error should disappear as the sample size grows. Definition 3.4 (Completeness). A sequence of calibration measures Cal = (CalT )T ≥1 is complete if, for every calibrated distribution D over [0, 1] × {0, 1}, lim EZ∼DT [CalT (Z)] = 0.

T →∞

Soundness is the separating side of the same guarantee: a fixed miscalibrated distribution should retain a positive expected error in the large-sample limit. Definition 3.5 (Soundness). A sequence of calibration measures Cal = (CalT )T ≥1 is sound if, for every miscalibrated distribution D over [0, 1] × {0, 1}, lim inf EZ∼DT [CalT (Z)] > 0. T →∞

Together, completeness and soundness imply that every fixed calibrated one-sample distribution is eventually separated in expected error from every fixed miscalibrated one-sample distribution. The appendix also discusses a weaker constant-predictor notion from Haghtalab et al. [14], where one only asks calibrated constant reports to have small expected error and separated constant reports to have larger expected error. The same incompatibility with truthfulness holds for this weaker notion; see Appendix A. The normalized smooth calibration error [18, 3] used later is T

smCET (r, y) :=

X 1 f (rt )(yt − rt ) , sup T f ∈F

(1)

t=1

where F is the class of 1-Lipschitz functions f : [0, 1] → [−1, 1].

3.3

Truthfulness

We first define the truthful strategy, which reports the conditional probability of the next outcome under the ground truth. 9

Definition 3.6 (Truthful strategy). Given a ground-truth data-generating distribution Π, a prediction strategy S ∗ is truthful if, for every t and every history y<t with PrΠ [Y<t = y<t ] > 0, St∗ (y<t ) = EΠ [Yt | Y<t = y<t ]. Values on histories with zero probability are immaterial. We write p∗ = S ∗ (Y ) for the realized truthful report sequence. Truthfulness of a calibration measure [14] requires the truthful strategy to minimize expected calibration error for every joint data-generating distribution. Definition 3.7 (Truthfulness). A calibration measure CalT is truthful if, for every joint distribution Π on {0, 1}T , with truthful reports p∗t (Y<t ) = EΠ [Yt | Y<t ], and every prediction strategy S that may depend on Π, we have EΠ [CalT (p∗ , Y )] ≤ EΠ [CalT (S(Y ), Y )]. We also use approximate versions of this truthfulness requirement. The additive version is the scale used by the quantitative lower bound in Section 5. Definition 3.8 (Additive approximate truthfulness). A calibration measure CalT is βT -additively truthful for product distributions if, for every product distribution and every prediction strategy S that may depend on that product distribution, E[CalT (p∗ , Y )] ≤ E[CalT (S(Y ), Y )] + βT . The version for arbitrary joint distributions requires the same inequality for every joint distribution of Y and every prediction strategy that may depend on that joint distribution. The second stage of the positive construction gives the stronger multiplicative guarantee. We define that version separately because both notions are used in Section 6. Definition 3.9 (Multiplicative truthfulness). A calibration measure CalT is αT -multiplicatively truthful for product distributions if, for every product distribution and every prediction strategy S that may depend on that product distribution, E[CalT (p∗ , Y )] ≤ αT E[CalT (S(Y ), Y )]. The version for arbitrary joint distributions requires the same inequality for every joint distribution of Y and every prediction strategy that may depend on that joint distribution.

4

Product-Distribution Impossibility

We first prove that exact truthful reporting can fail even under product data-generating distributions. Even a very weak finite-sample discrimination requirement is enough: if a calibration measure assigns smaller expected error to an i.i.d. calibrated distribution than to a simple i.i.d. miscalibrated distribution, then the measure creates an incentive for a strategic predictor to misreport. The proof is a hybrid argument. The offline separation between the two distributions can be localized to a single round where the truthful report is 1, but the strategic predictor prefers 10

the report q. We then use this local preference to construct an online prediction problem with a product data-generating distribution. The two product distributions in the theorem below represent the weakest natural test that distinguishes a calibrated report from a miscalibrated one at a single report value. Under Dq = (1 − q)δ(q,0) + qδ(q,1) , the predictor always reports q, and the outcome has conditional mean q, so this distribution is calibrated. In contrast, under Dq′ = (1 − q)δ(q,0) + qδ(1,1) , the report q appears only when the outcome is 0, so the conditional mean of the outcome, given report q, is 0 rather than q. Thus Dq′ is miscalibrated in this elementary way. The finite-sample theorem below is the core of the impossibility. Any measure that distinguishes this calibrated pair from the miscalibrated pair already creates a profitable online deviation, even under independent outcomes. Theorem 4.1 (Hybrid impossibility). Fix T ∈ N and q ∈ (0, 1). Let Dq = (1 − q)δ(q,0) + qδ(q,1)

and

Dq′ = (1 − q)δ(q,0) + qδ(1,1) .

If a calibration measure CalT satisfies EZ∼DqT [CalT (Z)] < EZ∼(Dq′ )T [CalT (Z)],

(2)

then there is a product data-generating distribution and a prediction strategy S such that, writing p∗ for the truthful report sequence, E[CalT (S(Y ), Y )] < E[CalT (p∗ , Y )]. Proof. For m = 0, 1, . . . , T , define a hybrid distribution Hm over T prediction-outcome pairs by drawing the first m pairs independently from Dq′ and the remaining T − m pairs independently from Dq . Thus H0 = DqT and HT = (Dq′ )T . By (2), there is some m ∈ [T ] such that EZ∼Hm−1 [CalT (Z)] < EZ∼Hm [CalT (Z)]. The two hybrids differ only in coordinate m. In that coordinate, Dq and Dq′ agree on (q, 0) and differ only on the outcome-one point: (q, 1)

under Dq ,

(1, 1)

under Dq′ .

Let Z<m = ((P1 , Y1 ), . . . , (Pm−1 , Ym−1 )) denote the common prefix random vector of Hm−1 and Hm . Its support is {(q, 0), (1, 1)}m−1 . For a prefix z<m = ((p1 , y1 ), . . . , (pm−1 , ym−1 )) and a ∈ {q, 1}, define h i Φa (z<m ) := EYm+1:T ∼Ber(q)⊗(T −m) CalT (p1 , . . . , pm−1 , a, q, . . . , q; y1 , . . . , ym−1 , 1, Ym+1:T ) . 11

  EZ∼Hm [CalT (Z)] − EZ∼Hm−1 [CalT (Z)] = q EZ<m Φ1 (Z<m ) − Φq (Z<m ) .

(3)

Here the (q, 0) contribution cancels, since it appears with the same probability 1 − q under both hybrids. Because the left-hand side of (3) is strictly positive, there exists a prefix ẑ<m in the support of Z<m such that Φq (ẑ<m ) < Φ1 (ẑ<m ) (4) Equivalently, after this prefix and conditioned on Ym = 1, reporting q at time m gives strictly smaller expected calibration error than reporting 1. We now build a prediction problem with a product data-generating distribution. Let the truthful probabilities be   p̂t , t < m, ∗ pt = 1, t = m,   q, t > m, and draw the outcomes independently as Yt ∼ Ber(p∗t ). Define a prediction strategy S = (S1 , . . . , ST ) by  ∗  pt , t ̸= m, St (y<t ) = q, t = m and y<m = (ŷ1 , . . . , ŷm−1 ),   1, t = m and y<m ̸= (ŷ1 , . . . , ŷm−1 ). Equivalently, S reports truthfully on all histories except the history E = {Y1 = ŷ1 , . . . , Ym−1 = ŷm−1 }. On E, at time m it reports q instead of the truthful value 1. The event E has positive probability, because Pr(E) =

m−1 Y

Pr(Yt = ŷt ) =

t=1

Y

(1 − q) > 0;

t: p̂t =q

when p̂t = 1, necessarily ŷt = 1 and the corresponding factor is 1. Conditioned on E, the outcome at time m is equal to 1 almost surely and the remaining outcomes are independent with distribution Ber(q). Therefore (4) is exactly the statement that E[CalT (S(Y ), Y ) | E] < E[CalT (p∗ , Y ) | E]. On E c , the two report sequences coincide, so E[CalT (S(Y ), Y ) | E c ] = E[CalT (p∗ , Y ) | E c ]. Since Pr(E) > 0, taking total expectations gives E[CalT (S(Y ), Y )] < E[CalT (p∗ , Y )]. Thus, for this product distribution, the strategic predictor achieves strictly smaller expected calibration error than the truthful predictor. 12

The asymptotic completeness and soundness definitions eventually imply the finite-sample separation required by the hybrid theorem. The corollary records the resulting no-deviation impossibility. Corollary 4.2 (Completeness and soundness rule out truthfulness). No sequence of calibration measures Cal = (CalT )T ≥1 can be complete and sound while also satisfying the following nodeviation condition at every horizon: E[CalT (p∗ , Y )] ≤ E[CalT (S(Y ), Y )] for every product data-generating distribution and every prediction strategy S, where p∗ is the truthful report sequence. Proof. Fix any q ∈ (0, 1) and let Dq , Dq′ be the pair of distributions from Theorem 4.1. The distribution Dq is calibrated and Dq′ is miscalibrated. By completeness, lim EZ∼DqT [CalT (Z)] = 0,

T →∞

while by soundness there is a constant γ > 0 such that, for all sufficiently large T , EZ∼(Dq′ )T [CalT (Z)] ≥ γ. For all sufficiently large T , the calibrated expectation is smaller than γ, so EZ∼DqT [CalT (Z)] < EZ∼(Dq′ )T [CalT (Z)]. Theorem 4.1 then implies that CalT is not minimized by truthful reporting on some product datagenerating distribution at that horizon. We note that the theorem is deliberately finite-sample. It does not require any asymptotic notion of soundness. For any fixed time horizon, a separation between the calibrated product distribution DqT and the miscalibrated product distribution Dq′ T already implies that, at the same horizon, a strategic predictor can strictly improve over truthful reporting.

5

Quantitative Lower Bounds from Impossibility

In this section, we quantify the reduction behind Theorem 4.1. For each q ∈ (0, 1), let ∆T (q) denote the offline distinguishing gap between the calibrated product distribution DqT and the miscalibrated product distribution (Dq′ )T . Let Advprod (Cal) denote the largest expected gain available to a T strategic predictor under a product distribution. The hybrid argument converts any positive offline gap into a positive incentive to deviate from truthful reporting. Quantitatively, the reduction loses a factor from averaging over the T hybrid steps and another from the probability of reaching the T −1 ∆T (q), history on which the strategic predictor deviates. This gives a lower bound of order (1−q) qT which is exponentially small in the horizon.

5.1

Hybrid Lower Bound

For a calibration measure CalT , define the product-distribution strategic advantage Advprod (Cal) := sup (E[CalT (p∗ , Y )] − E[CalT (S(Y ), Y )])+ , T p∗ ,S

13

where the supremum is over all product distributions Yt ∼ Ber(p∗t ) and all prediction strategies S. Thus Advprod (Cal) = 0 exactly means that no strategy can improve on truthful reporting under a T product distribution, while Advprod (Cal) ≤ βT is additive βT -truthfulness. T For q ∈ (0, 1), define Dq = (1 − q)δ(q,0) + qδ(q,1)

and

Dq′ = (1 − q)δ(q,0) + qδ(1,1) .

The corresponding distinguishing gap is ∆T (q) := EZ∼(Dq′ )T [CalT (Z)] − EZ∼DqT [CalT (Z)]. Theorem 5.1 (Quantitative hybrid lower bound). For every q ∈ (0, 1), Advprod (Cal) ≥ T

(1 − q)T −1 ∆T (q). qT

Proof. If ∆T (q) ≤ 0 the claim is immediate, so assume ∆T (q) > 0. Let Hm be the hybrid distributions from the proof of Theorem 4.1. By telescoping, ∆T (q) =

T X

EZ∼Hm [CalT (Z)] − EZ∼Hm−1 [CalT (Z)] .

m=1

Therefore for some m ∈ [T ], EZ∼Hm [CalT (Z)] − EZ∼Hm−1 [CalT (Z)] ≥

∆T (q) . T

Let Z<m = ((P1 , Y1 ), . . . , (Pm−1 , Ym−1 )) denote the common prefix random vector of Hm−1 and Hm . Its support is contained in {(q, 0), (1, 1)}m−1 . For a prefix z<m = ((p1 , y1 ), . . . , (pm−1 , ym−1 )) and a ∈ {q, 1}, define h i Φa (z<m ) := EYm+1:T ∼Ber(q)⊗(T −m) CalT (p1 , . . . , pm−1 , a, q, . . . , q; y1 , . . . , ym−1 , 1, Ym+1:T ) . Then, as in Section 4, EZ∼Hm [CalT (Z)] − EZ∼Hm−1 [CalT (Z)] = q EZ<m [Φ1 (Z<m ) − Φq (Z<m )] .

(5)

The expectation on the right-hand side of (5) is therefore at least ∆T (q)/(qT ). Hence there exists a prefix ẑ<m = ((p̂1 , ŷ1 ), . . . , (p̂m−1 , ŷm−1 )) in the support of Z<m such that Φ1 (ẑ<m ) − Φq (ẑ<m ) ≥

∆T (q) . qT

(6)

Embed this prefix into the same product distribution as in the qualitative proof: p∗t = p̂t for t < m, p∗m = 1, and p∗t = q for t > m. Let S be the strategy that reports q at time m on the prefix event E = {Y1 = ŷ1 , . . . , Ym−1 = ŷm−1 } 14

and otherwise reports truthfully. Exactly as in the proof of Theorem 4.1, Y Pr(E) = (1 − q) = (1 − q)|{t<m:p̂t =q}| ≥ (1 − q)T −1 . t: p̂t =q

Conditioned on E, (6) is exactly E[CalT (p∗ , Y ) − CalT (S(Y ), Y ) | E] ≥

∆T (q) . qT

On E c , the two strategies coincide. Therefore ∆T (q) (1 − q)T −1 ≥ ∆T (q). qT qT Taking the supremum over product distributions and strategies proves the theorem. E[CalT (p∗ , Y )] − E[CalT (S(Y ), Y )] ≥ Pr(E) ·

For complete and sound calibration measures, the distinguishing gap for each fixed q is eventually bounded below by a positive constant. Choosing q as a function of a target exponential rate gives the following consequence. Corollary 5.2 (Exponential lower bound under completeness and soundness). Let Cal = (CalT )T ≥1 be complete and sound. For every ρ ∈ (0, 1), there exists a constant cρ > 0 such that, for all sufficiently large T , (Cal) ≥ cρ ρT . Advprod T Proof. Fix ρ ∈ (0, 1), and set q :=

1−ρ . 2

Then q ∈ (0, 1) and 1+ρ > ρ. 2 The distribution Dq is calibrated, whereas Dq′ is miscalibrated. Completeness and soundness therefore imply that there are constants δρ > 0 and T0 such that 1−q =

∆T (q) ≥ δρ for every T ≥ T0 . By Theorem 5.1, (Cal) ≥ Advprod T

δρ (1 − q)T −1 . qT

Since (1 − q)/ρ > 1, the ratio (1 − q)T −1 T ρT tends to infinity. In particular, this ratio is at least 1 for all sufficiently large T . The claim follows with cρ = δρ /q > 0. This quantitative statement also constrains additive truthfulness. The next corollary rewrites the lower bound as a necessary upper bound on the distinguishing gap between the two product distributions. Corollary 5.3 (Necessary condition for additive truthfulness). If CalT is βT -additively truthful for product distributions, then for every q ∈ (0, 1), ∆T (q) ≤

qT βT . (1 − q)T −1

Proof. Additive βT -truthfulness implies Advprod (Cal) ≤ βT . Apply Theorem 5.1 and rearrange. T 15

6

Approximately Truthful Reductions

Section 4 shows that exact truthfulness is incompatible with even weak soundness requirements. This impossibility comes from exponentially rare prefix realizations, where a truthful predictor looks miscalibrated and is thus incentivized to correct historical realizations by strategizing in the future. Approximate truthfulness, however, relaxes this truthful requirement on every historical prefix realization. Approximate truthfulness only requires the truthful expected error to approximate the expected error of an adaptive strategy, where both expectations are calculated ex-ante. In this section, we reduce approximate truthfulness to a concentration property of a sound and complete base calibration measure. The reduction has two stages. First, we subtract a samplingerror threshold from the base measure. If the error remaining under truthful reporting is uniformly small, this thresholded measure is additively approximately truthful. We then add a vanishing squared-loss term to the additive construction. The conditional squared-loss decomposition supplies a variance-scale lower bound that turns the additive comparison into a multiplicative one. The base calibration measure need not be truthful by itself. It is sufficient that, under truthful reporting, the part of the error that remains after subtracting the sampling error is small compared to the truthful squared loss T

T

t=1

t=1

1X 1X E[(p∗t − Yt )2 ] = E[p∗t (1 − p∗t )]. T T We show that both stages preserve the statistical guarantees of the base measure, and then instantiate the multiplicative reduction with smooth calibration error.

6.1

The Reduction

We first explain the requirements of the base measure for the reduction to hold. Let Err = (ErrT )T ≥1 be a sequence of base calibration measures, where ErrT : [0, 1]T × {0, 1}T → [0, 1]. Write " # T T X 1 1X V T := E[p∗t (1 − p∗t )] = E (p∗t − Yt )2 . T T t=1

t=1

This V T is the average intrinsic variance of the outcome-generating process. We require uniform completeness of the error. When the predictor is truthful, uniform completeness gives a quantification of the sampling error in the calibration measure. Precisely, there exists τT accounting for the sampling error, and ηT accounting for the tail, such that, after subtracting the sampling error τT , the tail can be controlled by multiples of the variance ηT V T . Definition 6.1 (Uniform completeness). The error Err is uniformly complete if there exist sequences (τT )T ≥1 and (ηT )T ≥1 with τT > 0,

ηT ≥ 0,

τT → 0,

ηT → 0,

such that the following holds for every T and every joint distribution of Y1 , . . . , YT . If p∗t = E[Yt | Y<t ] denotes the truthful report, then h
i E ErrT (p∗ , Y ) − τT + ≤ ηT V T . (7) The sequences τT and ηT are independent of the joint distribution of Y . 16

We note that uniform completeness is not directly implied by the completeness of a calibration measure. Known calibration measures are uniformly complete. The following lemma establishes uniform completeness of the normalized smooth calibration error, which we will use later. Lemma 6.2 (Uniform completeness of smooth calibration error). Fix 0 < α < 1/2. There exists T0 = T0 (α) such that ( 2, T < T0 ,
τT = T −α and ηT = (1−2α)/2 exp −T , T ≥ T0 . The normalized smooth calibration error smCE = (smCET )T ≥1 is uniformly complete with witness sequences defined above. The proof is deferred to Appendix B. 6.1.1

Additively Approximate Truthfulness

To achieve additively approximate truthfulness, the reduction subtracts the sampling-error threshold and truncates at zero. Define
Caladd (8) T (r, y) := ErrT (r, y) − τT + . Uniform completeness controls the expected value of this measure under truthful reporting. Since the measure is non-negative, additive approximate truthfulness follows immediately from the tail bound. Theorem 6.3 (Additive-truthfulness reduction). Let Err = (ErrT )T ≥1 be uniformly complete with witness sequences τT and ηT as in Definition 6.1. Then for every joint distribution of Y and every prediction strategy S, h i h i add ∗ E Caladd T (p , Y ) ≤ ηT V T ≤ E CalT (S(Y ), Y ) + ηT V T . In particular, Caladd is ηT /4-additively truthful for arbitrary joint distributions. T Proof. By (7), h i ∗ E Caladd (p , Y ) ≤ ηT V T . T On the other hand, E[Caladd T (S(Y ), Y )] ≥ 0 for every prediction strategy S. Adding this nonnegative quantity gives the first claim. Finally, p∗t (1 − p∗t ) ≤ 1/4 almost surely for every t, so V T ≤ 1/4. The second claim follows from Definition 3.8. Corollary 6.4 (Additive truthfulness for smooth calibration error). Fix 0 < α < 1/2, and define the thresholded smooth calibration error
Calsm,add (r, y) := smCET (r, y) − T −α + . T
For all sufficiently large T , Calsm,add is 14 exp −T (1−2α)/2 -additively truthful for arbitrary joint T distributions. Proof. By Lemma 6.2, for all sufficiently large T the uniform-completeness witnesses for smCET are   τT = T −α and ηT = exp −T (1−2α)/2 . The claim follows from Theorem 6.3, which gives additive slack ηT /4. 17

6.1.2

Multiplicatively Approximate Truthfulness

The multiplicative truthfulness reduction adds a normalized squared-loss term to the additive construction. For λT > 0, define T

Calmult (r, y) := Caladd T T (r, y) + λT ·

1X (rt − yt )2 . T

(9)

t=1

The additive construction in Equation (8) controls the absolute gain from a deviation, but does not give a relative comparison when the error is close to zero. This squared loss provides the error needed for a relative comparison. To see this, every prediction strategy pays at least λT V T in expected squared loss: for every predictable report rt , E[(rt − Yt )2 | Y<t ] = (rt − p∗t )2 + p∗t (1 − p∗t ) ≥ p∗t (1 − p∗t ), which is of the same order as the squared loss term. The following theorem formalizes this second stage of the reduction. Theorem 6.5 (Multiplicative-truthfulness reduction). Let Err = (ErrT )T ≥1 be uniformly complete with witness sequences τT and ηT as in Definition 6.1. Then for every λT > 0, the measure T
1X Calmult (r, y) := Err (r, y) − τ (rt − yt )2 + λ · T T T T + T t=1

is (1 + ηT /λT )-multiplicatively truthful for arbitrary joint distributions. Proof. Fix a joint distribution of Y and write µ=

T X

E[p∗t (1 − p∗t )].

t=1

If µ = 0, then Yt = p∗t almost surely for every t, and the assumed bound forces the truthful thresholded error and truthful squared loss both to be zero, so the conclusion is immediate. Assume now that µ > 0. By (7) and E[(p∗t − Yt )2 ] = E[p∗t (1 − p∗t )], µ E[Calmult (p∗ , Y )] ≤ (ηT + λT ) . T T Now let S be any prediction strategy and set rt = St (Y<t ). Since rt is measurable with respect to the past, E[(rt − Yt )2 | Y<t ] = (rt − p∗t )2 + p∗t (1 − p∗t ) ≥ p∗t (1 − p∗t ). Therefore

T

E[Calmult (S(Y ), Y )] ≥ λT · T

µ 1X E[(rt − Yt )2 ] ≥ λT . T T t=1

Combining the two inequalities gives E[Calmult (p∗ , Y )] ≤ T

  ηT 1+ E[Calmult (S(Y ), Y )]. T λT

18

Corollary 6.6 (Multiplicative truthfulness for smooth calibration error). Fix 0 < α < 1/2, let   1 (1−2α)/2 , λT := exp − T 2 and define T
1X −α (rt − yt )2 . Calsm,mult (r, y) := smCE (r, y) − T + λ · T T T + T t=1

For all sufficiently large T , Calsm,mult is T 



1 1 + exp − T (1−2α)/2 2

 -multiplicatively truthful

for arbitrary joint distributions. Proof. By Lemma 6.2, for all sufficiently large T the uniform-completeness witnesses for smCET are   τT = T −α and ηT = exp −T (1−2α)/2 . Applying Theorem 6.5 gives the factor   ηT 1 (1−2α)/2 1+ = 1 + exp − T . λT 2

6.2

Preserving Soundness and Completeness

The next result covers both stages of the reduction: setting λT = 0 gives the additive construction, while λT > 0 gives the multiplicative construction. Theorem 6.7 (Preservation of soundness and completeness). Let ErrT : [0, 1]T × {0, 1}T → R≥0 be a sequence of base calibration measures. Let τT , λT ≥ 0 satisfy τT → 0 and λT → 0, and define T
1X CalT (r, y) := ErrT (r, y) − τT + + λT · (rt − yt )2 . T t=1

If Err = (ErrT )T ≥1 is complete, then Cal = (CalT )T ≥1 is complete. If Err is sound, then Cal is sound. Proof. We first prove completeness. Fix a calibrated one-sample distribution D over [0, 1] × {0, 1}, and draw Z = ((R1 , Y1 ), . . . , (RT , YT )) ∼ DT . Since τT ≥ 0,
ErrT (Z) − τT + ≤ ErrT (Z). Moreover, calibration of D implies   1 E[(R − Y )2 ] = E E[(R − Y )2 | R] = E[R(1 − R)] ≤ . 4 19

Therefore

λT . 4 If Err is complete, the first term tends to zero for every calibrated D, and the second term tends to zero by assumption. Hence Cal is complete. We next prove soundness. Fix a miscalibrated one-sample distribution D. For every x ≥ 0 and every τ ≥ 0, (x − τ )+ ≥ x − τ . Since the squared-loss term is non-negative, EZ∼DT [CalT (Z)] ≤ EZ∼DT [ErrT (Z)] +

EZ∼DT [CalT (Z)] ≥ EZ∼DT [ErrT (Z)] − τT . If Err is sound, then lim inf EZ∼DT [ErrT (Z)] > 0. T →∞

Because τT → 0, the same positive lower limit is retained by Cal. Thus Cal is sound.

AI Disclosure The authors used ChatGPT 5.4 to assist in developing and editing the proofs of the peeling lemma and the comparison lemma in Section A. The authors independently verified the correctness and originality of all content, including all references.

References [1] Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, and Mirah Shi. An elementary √ predictor obtaining 2 T distance to calibration. arXiv preprint arXiv:2402.11410, 2024. [2] Konstantina Bairaktari, Lunjia Hu, Huy L. Nguyen, and Jonathan Ullman. Testable and actionable calibration for full swap regret, 2026. URL https://arxiv.org/abs/2605.17749. [3] Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1727–1740, 2023. [4] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, and Princewill Okoroafor. Breaking the t2/3 barrier for sequential calibration, 2025. [5] A. P. Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):605–610, 1982. doi: 10.1080/01621459.1982.10477856. URL https://www. tandfonline.com/doi/abs/10.1080/01621459.1982.10477856. [6] Victor H. de la Peña. A general class of exponential inequalities for martingales and ratios. The Annals of Probability, 27(1):537–564, 1999. doi: 10.1214/aop/1022677271. URL https: //doi.org/10.1214/aop/1022677271. [7] Pahan Dewasurendra. Characterizing perfect truthfulness in continuous online calibration, 2026. URL https://github.com/andotheror/ perfect-truthfulness-online-calibration/blob/main/main.pdf. [8] Pahan Dewasurendra. No perfectly truthful sequential calibration measure, 2026. URL https://andotheror.github.io/pdf/ no-perfectly-truthful-sequential-calibration-measure.pdf. 20

[9] Dean P Foster and Sergiu Hart. Forecast hedging and calibration. Journal of Political Economy, 129(12):3447–3490, 2021. [10] Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, 85(2):379–390, 1998. [11] David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100– 118, 1975. doi: 10.1214/aop/1176996452. URL https://doi.org/10.1214/aop/1176996452. [12] Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359–378, 2007. [13] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321–1330. PMLR, 2017. [14] Nika Haghtalab, Mingda Qiao, Kunhe Yang, and Eric Zhao. Truthfulness of calibration measures. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [15] Jason Hartline, Yifan Wu, and Yunran Yang. Smooth calibration and decision making. arXiv preprint arXiv:2504.15582, 2025. [16] Jason Hartline, Lunjia Hu, and Yifan Wu. A perfectly truthful calibration measure. In Steve Hanneke and Tor Lattimore, editors, Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 3185–3223. PMLR, 29 Jun–03 Jul 2026. URL https://proceedings.mlr.press/v336/hartline26a.html. [17] Lunjia Hu and Yifan Wu. Predict to minimize swap regret for all payoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 244–263. IEEE, 2024. [18] Sham M. Kakade and Dean P. Foster. Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences, 74(1):115–130, 2008. ISSN 0022-0000. doi: 10.1016/j.jcss.2007.04.017. URL https://www.sciencedirect.com/science/article/pii/ S0022000007000633. [19] Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory, pages 5143–5145. PMLR, 2023. [20] Yuxuan Lu, Yifan Wu, Jason Hartline, and Lunjia Hu. Truthful calibration errors for multiclass prediction, 2026. URL https://arxiv.org/abs/2510.06388. [21] Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 456–466, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539. doi: 10.1145/3406325.3451050. URL https://doi.org/10.1145/3406325. 3451050. [22] Mingda Qiao and Eric Zhao. Truthfulness of decision-theoretic calibration measures. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 4686–4739. PMLR, 30 Jun–04 Jul 2025. URL https://proceedings.mlr.press/v291/qiao25a.html. 21

[23] Mingda Qiao and Letian Zheng. On the distance from calibration in sequential prediction. arXiv preprint arXiv:2402.07458, 2024.

A

Truthfulness and Weak Soundness

This appendix proves the truthfulness impossibility result deferred from the main text. We work with the weak constant-predictor completeness and soundness requirement considered by Haghtalab et al. [14]: constant reports should have small expected error when they match the Bernoulli mean and noticeably larger expected error when they are separated from it. Our goal is to show that no truthful calibration measure can satisfy this requirement. The proof proceeds by first establishing a comparison lemma for constant predictors. We show that truthfulness forces the expected error of one constant report under a Bernoulli product distribution to be controlled by the expected error of another constant report under the same distribution. The main technical step is a first-round decomposition: we peel off the first round, identify its contribution with a proper binary loss, and show that the tail that remains still defines a non-negative truthful calibration measure. We then apply this comparison lemma to the weak constant-predictor soundness and completeness requirement. Completeness says that a truthful constant predictor must have small expected error, while the comparison lemma transfers this upper bound to a separated constant misreport. This contradicts the lower bound required by soundness, and therefore no truthful calibration measure can satisfy the weak constant-predictor requirement.

A.1

The Comparison Lemma

The key step is a comparison inequality for constant reports.

Notation We first define some notation for arguing about first round decompositions. We call rounds 2, . . . , T the tail. A tail outcome sequence is an element w = (w1 , . . . , wT −1 ) ∈ {0, 1}T −1 . For i = 1, . . . , T −1, write w<i = (w1 , . . . , wi−1 ). A tail strategy is a sequence σi : {0, 1}i−1 → [0, 1].

σ = (σ1 , . . . , σT −1 ),

Given a tail outcome sequence w, the realized tail report vector generated by σ along the tail outcome sequence w is given by
σ[w] := σ1 (∅), σ2 (w1 ), . . . , σT −1 (w<T −1 ) ∈ [0, 1]T −1 . Thus σ is a rule for producing reports, while σ[w] is the report vector produced when the tail outcome sequence is w. If ν is a distribution on {0, 1}T −1 , let W = (W1 , . . . , WT −1 ) ∼ ν. We write π ν for the truthful tail strategy under ν. That is, for each i = 1, . . . , T − 1 and each history w<i with ν(W<i = w<i ) > 0, we define πiν (w<i ) = Pr[Wi = 1 | W<i = w<i ]. ν

22

On histories w<i with ν(W<i = w<i ) = 0, we set πiν (w<i ) = 0. We write π ν [w] for the realized tail report vector generated by π ν along w. Finally, for r ∈ [0, 1], s ∈ [0, 1]T −1 , b ∈ {0, 1}, and w ∈ {0, 1}T −1 , we use the abbreviation
CalT (r, s; b, w) := CalT (r, s), (b, w) . Here r is the first-round report, s is the vector of reports in rounds 2, . . . , T , b is the first outcome, and w is the vector of outcomes in rounds 2, . . . , T . Since {0, 1}T −1 ⊆ [0, 1]T −1 , when z ∈ {0, 1}T −1 is a deterministic tail outcome sequence, we may also use z as the corresponding deterministic tail report vector. The first-round decomposition can be characterized by a peeling lemma. The main idea is this: once the tail distribution is fixed, the first round behaves like a proper binary loss. The remainder of the objective is still a non-negative truthful calibration measure on the tail sequence. Lemma A.1 (Peeling lemma). Let T ≥ 2, and let CalT : [0, 1]T × {0, 1}T → R≥0 be truthful. For a distribution ν on {0, 1}T −1 and b ∈ {0, 1}, define Aνb (r) = EZ∼ν [CalT (r, π ν [Z]; b, Z)] . Then there is a non-negative proper binary loss ℓ : [0, 1] × {0, 1} → R≥0 and constants Bb (ν) such that Aνb (r) = ℓ(r, b) + Bb (ν)

for all r ∈ (0, 1).

Moreover, ℓ may be chosen so that for every deterministic tail sequence z ∈ {0, 1}T −1 , there are constants βb (z) ≥ 0 satisfying CalT (r, z; b, z) = ℓ(r, b) + βb (z)

for all r ∈ (0, 1).

Finally, for every b ∈ {0, 1} and every r ∈ (0, 1), define Rb,r (s; z) := CalT (r, s; b, z) − CalT (r, z; b, z),

s ∈ [0, 1]T −1 , z ∈ {0, 1}T −1 .

Then Rb,r (s; z) ≥ 0 for every s, z. Moreover, Rb,r is truthful on the remaining T − 1 rounds: for every distribution Λ on {0, 1}T −1 and every tail strategy σ,   EZ∼Λ Rb,r (π Λ [Z]; Z) ≤ EZ∼Λ [Rb,r (σ[Z]; Z)] . Proof. Fix two distributions ν0 , ν1 on {0, 1}T −1 . For α ∈ [0, 1], consider the joint distribution under which Y1 ∼ Ber(α), and conditional on Y1 = b, the tail (Y2 , . . . , YT ) is drawn from νb . Under this joint distribution, the truthful first-round prediction is α. After observing Y1 = b, the truthful continuation strategy is π νb . Therefore truthfulness implies that r = α minimizes (1 − α)Aν00 (r) + αAν11 (r) 23

over r ∈ [0, 1]. Thus, for every pair (ν0 , ν1 ), the pair (Aν00 , Aν11 ) is a proper binary loss. Moreover, because CalT is finite-valued and the tail outcome space is finite, every Aνb is real-valued on [0, 1]. Hence these induced losses are regular, and the Savage representation applies [12]. We use the following standard consequence of this representation. If F0 and F1 are two families of functions such that every pair (f, g) ∈ F0 × F1 is a proper binary loss, then all functions in F0 differ by additive constants, and likewise for F1 . Indeed, fixing g ∈ F1 and applying the representation to (f, g) and (fe, g) shows that f − fe is constant on (0, 1). The symmetric argument applies to F1 . Applying this consequence to the families {Aν0 }ν and {Aν1 }ν , we obtain a proper binary loss ℓ and constants Bb (ν) such that Aνb (r) = ℓ(r, b) + Bb (ν)

for all r ∈ (0, 1).

We now choose the normalization of ℓ. For a deterministic tail sequence z, the truthful tail report vector under δz is z. Hence r 7→ CalT (r, z; b, z) is the special case Aδbz (r). Therefore each such function differs from ℓ(r, b) by an additive constant. Since there are finitely many deterministic tail sequences, for each b ∈ {0, 1} we may choose a deterministic tail zb⋆ whose additive constant is minimal, and set ℓ(r, b) := CalT (r, zb⋆ ; b, zb⋆ ). This choice preserves propriety, since every pair of deterministic-tail functions gives a proper binary loss. It also makes ℓ non-negative, because CalT is non-negative. After this normalization, we redefine the constants Bb (ν) accordingly, so that Aνb (r) = ℓ(r, b) + Bb (ν) continues to hold. For every deterministic tail z, we then have CalT (r, z; b, z) = ℓ(r, b) + βb (z) for some constant βb (z) ≥ 0. It remains to prove the residual statement. Fix b ∈ {0, 1}, r ∈ (0, 1), and a deterministic tail sequence z. Embed this in a joint distribution where Y1 ∼ Ber(r) and, conditional on Y1 = b, the tail is deterministically equal to z. Since r ∈ (0, 1), the event Y1 = b has positive probability. On this event, the truthful tail report vector is z. Suppose for contradiction that some s ∈ [0, 1]T −1 satisfies CalT (r, s; b, z) < CalT (r, z; b, z). Then we could define a full strategy that reports r in the first round, reports truthfully off the branch Y1 = b, and on the deterministic branch (Y1 , Y2 , . . . , YT ) = (b, z) reports the tail vector s. Since the tail is deterministic on this branch, the fixed vector s can be implemented by specifying the corresponding report on each prefix of z. Since this branch has positive probability, this strategy would strictly improve the unconditional expected calibration error, contradicting truthfulness. Therefore Rb,r (s; z) ≥ 0 24

for every s, z. Finally, let Λ be an arbitrary distribution on {0, 1}T −1 . Embed Λ after the branch Y1 = b in a full joint distribution with Pr[Y1 = 1] = r, and define the other branch arbitrarily. On the branch Y1 = b, the truthful tail strategy is π Λ . If some tail strategy σ satisfied   EZ∼Λ [Rb,r (σ[Z]; Z)] < EZ∼Λ Rb,r (π Λ [Z]; Z) , then we could define a full strategy that reports r in the first round, reports truthfully off the branch Y1 = b, and uses the tail strategy σ after the branch Y1 = b. This strategy would strictly improve the expected value of CalT under the full joint distribution. This contradicts truthfulness. Therefore Rb,r is truthful on the remaining T − 1 rounds. We can now prove the comparison lemma. This is the technical step that turns full truthfulness into a quantitative restriction on constant misreports, which is the ingredient needed for the weaksoundness impossibility below. Lemma A.2 (Comparison lemma). Let CalT : [0, 1]T × {0, 1}T → R≥0 be truthful. Then for every 0 < q < p < 1, EY ∼Ber(p)⊗T [CalT (q, . . . , q; Y )] ≤

p(1 − q) E ⊗T [CalT (p, . . . , p; Y )] . q(1 − p) Y ∼Ber(p)

Proof. We prove the claim by induction on T . The base case T = 1 is the standard comparison inequality for non-negative proper binary losses: if ℓ is a non-negative proper binary loss and 0 < q < p < 1, then (1 − p)ℓ(q, 0) + pℓ(q, 1) ≤

p(1 − q) (1 − p)ℓ(p, 0) + pℓ(p, 1) . q(1 − p)

Assume the claim holds for horizon T − 1. Fix 0 < q < p < 1, and set K :=

p(1 − q) . q(1 − p)

Let ν = Ber(p)⊗(T −1) be the product distribution on the last T − 1 outcomes. Under ν, the truthful tail report vector is (p, . . . , p). Apply Lemma A.1. For b ∈ {0, 1}, r ∈ (0, 1), and deterministic z ∈ {0, 1}T −1 , we have CalT (r, z; b, z) = ℓ(r, b) + βb (z), with βb (z) ≥ 0, and hence Rb,r (s; z) = CalT (r, s; b, z) − ℓ(r, b) − βb (z). Fix b ∈ {0, 1}. Since Rb,q is non-negative and truthful on the tail, the induction hypothesis applied to Rb,q gives EZ∼ν [Rb,q (q, . . . , q; Z)] ≤ KEZ∼ν [Rb,q (p, . . . , p; Z)] .

25

Therefore EZ∼ν [CalT (q, q, . . . , q; b, Z)] = ℓ(q, b) + EZ∼ν [βb (Z)] + EZ∼ν [Rb,q (q, . . . , q; Z)] ≤ ℓ(q, b) + EZ∼ν [βb (Z)] + KEZ∼ν [Rb,q (p, . . . , p; Z)] . We now compute EZ∼ν [Rb,q (p, . . . , p; Z)] = EZ∼ν [CalT (q, p, . . . , p; b, Z) − ℓ(q, b) − βb (Z)] = Aνb (q) − ℓ(q, b) − EZ∼ν [βb (Z)] = Bb (ν) − EZ∼ν [βb (Z)]. Substituting this into the previous inequality gives EZ∼ν [CalT (q, q, . . . , q; b, Z)] ≤ ℓ(q, b) + EZ∼ν [βb (Z)] + K (Bb (ν) − EZ∼ν [βb (Z)]) = ℓ(q, b) + KBb (ν) − (K − 1)EZ∼ν [βb (Z)] ≤ ℓ(q, b) + KBb (ν), where the last step uses K > 1 and βb (Z) ≥ 0. Averaging over b ∼ Ber(p), we obtain EY ∼Ber(p)⊗T [CalT (q, . . . , q; Y )] ≤ Eb∼Ber(p) [ℓ(q, b)] + KEb∼Ber(p) [Bb (ν)]. By the one-step comparison inequality for the non-negative proper loss ℓ, Eb∼Ber(p) [ℓ(q, b)] ≤ KEb∼Ber(p) [ℓ(p, b)]. Hence EY ∼Ber(p)⊗T [CalT (q, . . . , q; Y )] ≤ KEb∼Ber(p) [ℓ(p, b) + Bb (ν)] . Using the peeling identity once more, ℓ(p, b) + Bb (ν) = Aνb (p) = EZ∼ν [CalT (p, p, . . . , p; b, Z)] . Therefore Eb∼Ber(p) [ℓ(p, b) + Bb (ν)] = EY ∼Ber(p)⊗T [CalT (p, . . . , p; Y )] . Combining the previous inequalities gives EY ∼Ber(p)⊗T [CalT (q, . . . , q; Y )] ≤ KEY ∼Ber(p)⊗T [CalT (p, . . . , p; Y )] , which is the desired claim.

A.2

Constant-Predictor Consequence

The comparison lemma immediately gives a quantitative impossibility result for truthful calibration measures evaluated on constant predictors. If a truthful constant report has small expected error, then every fixed constant misreport below it must also have comparably small expected error, where the comparison factor is independent of the horizon. For p, p̂ ∈ (0, 1), write MT (p̂, p) := EY ∼Ber(p)⊗T [CalT (p̂, . . . , p̂; Y )] . 26

By Lemma A.2, for every 0 < q < p < 1, MT (q, p) ≤

p(1 − q) MT (p, p). q(1 − p)

Consequently, suppose that a truthful calibration measure satisfies the constant-predictor completeness bound MT (p, p) ≤ c1 (T ) for every p ∈ (0, 1). For any separation c ∈ (0, 1), set p∗ =

1+c 2

and

p̂ =

1−c . 2

Then |p̂ − p∗ | = c, and the comparison lemma gives   1+c 2 ∗ MT (p̂, p ) ≤ c1 (T ). 1−c Thus a truthful calibration measure cannot have c1 (T ) = o(1) while requiring a constant lower bound on the expected error of every constant misreport separated from the true Bernoulli mean by a fixed amount. The next subsection formalizes this conclusion as a fixed-horizon impossibility for weak completeness and soundness.

A.3

Weak Constant-Predictor Soundness

We now formalize the consequence of the comparison lemma for soundness. The point is that the comparison factor p(1 − q) q(1 − p) does not depend on T . Therefore, if a truthful calibration measure gives small expected error to truthful constant reports, then it cannot simultaneously assign a fixed positive error to all constant reports that are separated from the truth by a fixed amount. The definition below formalizes this weak constant-predictor notion of completeness and soundness. Definition A.3 (Weak constant-predictor soundness). Fix parameters c, c1 , c2 > 0. A calibration measure CalT satisfies (c, c1 , c2 )-weak constant-predictor completeness and soundness if: 1. for every p ∈ [0, 1], EY ∼Ber(p)⊗T [CalT (p, . . . , p; Y )] ≤ c1 ; 2. for every p̂, p∗ ∈ [0, 1] with |p̂ − p∗ | ≥ c, EY ∼Ber(p∗ )⊗T [CalT (p̂, . . . , p̂; Y )] ≥ c2 . Applying the comparison lemma to this weak requirement gives the final impossibility: even this constant-predictor version of completeness and soundness is incompatible with truthfulness. Theorem A.4 (Truthfulness vs. weak soundness). For every 0 < c2 ≤ 1, no truthful calibration measure CalT : [0, 1]T × {0, 1}T → R≥0 can satisfy (1/4, c2 /4, c2 )-weak constant-predictor completeness and soundness. 27

Proof. Suppose such a truthful CalT exists. Completeness at p = 3/4 gives EY ∼Ber(3/4)⊗T [CalT (3/4, . . . , 3/4; Y )] ≤

c2 . 4

Applying Lemma A.2 with q = 1/2 and p = 3/4 gives the comparison factor p(1 − q) (3/4)(1/2) = = 3. q(1 − p) (1/2)(1/4) Therefore

3c2 < c2 . 4 But |1/2−3/4| = 1/4, so soundness requires this same expectation to be at least c2 , a contradiction. EY ∼Ber(3/4)⊗T [CalT (1/2, . . . , 1/2; Y )] ≤

The correlated version of weak soundness only strengthens the product condition, since it includes i.i.d. Bernoulli outcome sequences. The corollary records that the same impossibility therefore applies to that formulation as well. Here the correlated condition requires the two bounds in the preceding definition to hold for every joint distribution on {0, 1}T whose coordinates have common marginal mean p, without assuming independence. Definition A.5 (Correlated weak constant-predictor soundness). Fix c, c1 , c2 > 0. A calibration measure CalT satisfies (c, c1 , c2 )-weak correlated constant-predictor completeness and soundness if: 1. for every p ∈ [0, 1] and every joint distribution Π on {0, 1}T satisfying for every t ∈ [T ],

EΠ [Yt ] = p we have

EY ∼Π [CalT (p, . . . , p; Y )] ≤ c1 ; 2. for every p̂, p∗ ∈ [0, 1] with |p̂ − p∗ | ≥ c and every joint distribution Π on {0, 1}T satisfying EΠ [Yt ] = p∗

for every t ∈ [T ],

we have EY ∼Π [CalT (p̂, . . . , p̂; Y )] ≥ c2 . This condition strengthens the product condition because, for every p ∈ [0, 1], the product distribution Ber(p)⊗T is a joint distribution on {0, 1}T satisfying E[Yt ] = p for every t ∈ [T ]. Corollary A.6 (Correlated weak soundness). For every 0 < c2 ≤ 1, no truthful calibration measure can satisfy (1/4, c2 /4, c2 )-weak correlated constant-predictor completeness and soundness in the sense of Definition A.5. Proof. Restricting the correlated condition to Π = Ber(p)⊗T gives the product weak constantpredictor condition ruled out by Theorem A.4.

28

B

Concentration for Smooth Calibration Error

This section proves Lemma 6.2. The main input is the following scale-sensitive tail bound for smooth calibration error under truthful reporting. Lemma B.1 (Truthful tail bound for smooth calibration error). Fix 0 < α < 1/2. Let smCET be the normalized smooth calibration error from Section 3. Suppose p∗t is σ(Y1 , . . . , Yt−1 )-measurable and, conditional on the past, Yt ∼ Ber(p∗t ). Then, for sufficiently large T , T   1X   ∗ −α (1−2α)/2 Pr smCET (p , Y ) ≥ T ≤ exp −T · E[p∗t (1 − p∗t )]. T t=1

The proof is a martingale concentration argument based on the exponential-moment method for bounded martingale differences; see, e.g., [11, 6]. Under truthful reporting, Yt − p∗t is a bounded martingale difference, and smooth calibration error is the supremum of predictable Lipschitz test functions applied to these martingale differences. Proof. We use the notation Ft = σ(Y1 , . . . , Yt ),

Xt = Yt − p∗t ,

σt2 = p∗t (1 − p∗t ),

VT =

T X

σt2 ,

t=1

and set µ := E[VT ]. If µ = 0, then Xt = 0 for every t almost surely, and there is nothing to prove. We first record the exponential-moment estimate used below. Let h1 , . . . , hT be predictable with |ht | ≤ 1, and put Dt := ht Xt ,

Nj :=

j X

qt := h2t σt2 ,

Dt ,

νh :=

t=1

T X t=1

Fix 0 < λ ≤ 1 and define aλ :=

λ2 eλ . 2

For every z ∈ [−1, 1], Taylor’s formula gives e−λz ≤ 1 − λz + aλ z 2 .

eλz ≤ 1 + λz + aλ z 2 ,

Since E[Dt | Ft−1 ] = 0 and E[Dt2 | Ft−1 ] = qt , we get E[e±λDt | Ft−1 ] ≤ 1 + aλ qt . Let Gj := eλNj + e−λNj − 2 = 2(cosh(λNj ) − 1). Conditioning on Ft−1 and using 0 ≤ qt ≤ 1 and Gt−1 ≥ 0,   E[Gt | Ft−1 ] ≤ (1 + aλ qt ) eλNt−1 + e−λNt−1 − 2 = Gt−1 + aλ qt (Gt−1 + 2) ≤ (1 + aλ )Gt−1 + 2aλ qt .

29

E[qt ].

Iterating this recursion yields E[cosh(λNT ) − 1] ≤ aλ eaλ T νh .

(10)

Now use the one-dimensional structure of the Lipschitz class. Define R :=

T X

Xt ,

B(u) :=

T X

t=1

1[u ≤ p∗t ]Xt ,

u ∈ [0, 1].

t=1

Every f ∈ F is absolutely continuous and admits an a.e. derivative gf with |gf | ≤ 1. Therefore T X

f (p∗t )Xt = f (0)R +

Z 1 gf (u)B(u) du. 0

t=1

Consequently, with T X

L := sup

f ∈F t=1

we have

f (p∗t )Xt ,

Z 1 L ≤ |R| +

|B(u)| du. 0

Apply (10) with ht = 1 to get E[cosh(λR) − 1] ≤ aλ eaλ T µ. For each fixed u, apply (10) with ht (u) = 1[u ≤ p∗t ]. If " T # X ν(u) := E 1[u ≤ p∗t ]σt2 , t=1

then E[cosh(λB(u)) − 1] ≤ aλ eaλ T ν(u). Moreover Z 1 ν(u) du = E

" T X

0

# p∗t σt2 ≤ µ.

t=1

Let s := T 1−α . If L ≥ s, then either |R| ≥ s/2 or by Markov’s inequality: Pr[|R| ≥ s/2] ≤

R1

0 |B(u)| du ≥ s/2. The first event is bounded

aλ eaλ T µ . cosh(λs/2) − 1

For the second event, Jensen’s inequality gives  Z 1  Z 1 Z 1 cosh λ |B(u)| du − 1 ≤ (cosh(λ|B(u)|) − 1) du = (cosh(λB(u)) − 1) du. 0

0

0

Therefore another application of Markov’s inequality gives Z 1  aλ eaλ T µ . Pr |B(u)| du ≥ s/2 ≤ cosh(λs/2) − 1 0 30

Combining the two estimates, Pr[L ≥ s] ≤

2aλ eaλ T µ . cosh(λs/2) − 1

Finally choose λ = T −α /2 and set d := 1 − 2α > 0. For all sufficiently large T , we have eλ ≤ 3/2 and hence 3 3 λs 1 aλ ≤ T −2α , aλ T ≤ T d , = T d. 16 16 2 4 x Since cosh(x) − 1 ≥ ce for all sufficiently large x, it follows that µ µ ≤ exp(−T d/2 ) T T P for sufficiently large T . Since d/2 = (1 − 2α)/2, smCET (p∗ , Y ) = L/T and µ = Tt=1 E[p∗t (1 − p∗t )], this is the desired bound. Pr[L ≥ T 1−α ] ≤ CµT −2α exp(−T d /16) = CT d exp(−T d /16)

Proof of Lemma 6.2. Fix 0 < α < 1/2. Choose T0 = T0 (α) so that Lemma B.1 holds for every T ≥ T0 . Let Y have any joint distribution, and let p∗t = E[Yt | Y<t ]. Because Yt is binary, conditional on Y<t it is Bernoulli with parameter p∗t , so the tail lemma applies. For T ≥ T0 , the bound 0 ≤ smCET ≤ 1 gives
 smCET (p∗ , Y ) − T −α + ≤ 1 smCET (p∗ , Y ) ≥ T −α . Taking expectations and applying Lemma B.1 yields h  
i E smCET (p∗ , Y ) − T −α + ≤ exp −T (1−2α)/2 V T . It remains to control the finitely many horizons T < T0 . Since every f ∈ F takes values in [−1, 1], T 1X smCET (p∗ , Y ) ≤ |Yt − p∗t |. T t=1

Moreover, E [|Yt − p∗t | | Y<t ] = 2p∗t (1 − p∗t ). Therefore

h E

i smCET (p∗ , Y ) − T −α + ≤ E[smCET (p∗ , Y )] ≤ 2V T .

Thus τT = T −α and the piecewise sequence ηT in Lemma 6.2 satisfy (7) for every T and every joint distribution of Y . Both sequences converge to zero, which completes the proof.

31

Related documents

• Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability#670696
• Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability#668631
• Realizable Bayes-Consistency for General Metric Losses#155294
• Refining Ground Truth Poses in Autonomous Driving Datasets via Neural Rendering#1035285
• Temporal Difference Calibration in Sequential Tasks: Application to Vision-Language-Action Models#124076