Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems Raghav Bongole, Tobias J. Oechtering, and Mikael Skoglund
arXiv:2604.12519v1 [cs.LG] 14 Apr 2026
Department of Information Science and Engineering (ISE) KTH Royal Institute of Technology
Abstract—Recent work established a generalized-Fano framework for lower bounding prior-predictive (Bayesian) CVaR in interactive statistical decision making. In this paper, we show how to instantiate that framework in concrete interactive problems and derive explicit Bayesian CVaR lower bounds from its abstract corollaries. Our approach compares a hard model with a reference model using squared Hellinger distance, and combines a lower bound on a reference hinge term with a bound on the distinguishability of the two models. We apply this approach to canonical examples, including Gaussian bandits, and obtain explicit bounds that make the dependence on key problem parameters transparent. These results show how the generalized-Fano Bayesian CVaR framework can be used as a practical lower-bound tool for interactive learning and risksensitive decision making. Index Terms—information theory and control, statistical learning
I. I NTRODUCTION Lower bounds play a central role in statistical decision making by quantifying the smallest loss or cost that any problem must incur. In a Bayesian formulation of statistical decision making, one assumes a prior µ on the model class M and evaluates performance under the prior-predictive probability. The resulting Bayes risk provides a natural benchmark for what can be achieved on average under the prior, and lower bounds on this quantity reveal informationtheoretic limits of learning and decision making. Classical tools such as Le Cam’s method, Assouad’s lemma, and Fano’s inequality are fundamental techniques for deriving such lower bounds in passive statistical estimation [1]. Many modern learning and control problems are interactive: the learner’s actions affect what data are observed. Chen et al. [2] formalize this through the interactive statistical decision making (ISDM) framework. In ISDM, a model M ∈ M specifies the environment, an algorithm Alg ∈ D chooses actions or decisions, and the resulting observation or transcript X is distributed according to an algorithm-dependent law X ∼ P M,Alg . This algorithm dependence is the key distinction from passive estimation, where the data law is fixed and independent of the estimator. The ISDM viewpoint encompasses passive estimation, multi-armed bandits, and reinforcement learning within a common framework [2]–[4]. This work is supported by the Knut and Wallenberg Foundation.
It is especially relevant in control and sequential decision making, where information acquisition and performance are inherently coupled: one must act in order to learn, and those actions shape both future information and eventual cost. Most lower-bound results in these settings focus on expected loss or expected regret. While expected risk is a natural measure of performance, it can conceal rare but costly failures. This motivates risk-sensitive criteria that emphasize the tail of the loss distribution. A standard example is Conditional Valueat-Risk, CVaRα (L), α ∈ [0, 1), which measures the expected loss in the worst (1 − α)-tail. For losses, CVaR is more sensitive to adverse events than the mean and is widely used in finance, optimization, and risk-sensitive control [5]– [7]. Related tail criteria, such as quantiles and Value-atRisk, have also been studied in statistical learning; see, for example, [8]. In contrast to Bayes expected-risk lower bounds, Bayesian CVaR lower bounds quantify how small the tail-sensitive performance criterion can be under the priorpredictive probability law, and hence what no algorithm can improve on. A recent step in this direction is the work of Bongole et al. [9], which extends the interactive Fano method of Chen et al. [2]. They consider bounded transforms of the loss and derive a generalized interactive Fano inequality for expected bounded transforms under the prior-predictive law. As a consequence, they obtain a general lower-bound template for Bayesian CVaR of bounded losses in ISDM. Their results show that tail-sensitive Bayesian performance criteria can be treated within the same information-theoretic framework as expected-risk and quantile-type criteria. The main challenge left open by [9] is instantiation. The corollaries identify the quantities: a benchmark term under a reference law and a divergence budget, but applying them in a concrete problem still requires a problem-specific calculation. In this work, the objective is to make this framework usable in concrete settings. To this end, a reusable two-point Bayesian CVaR template is extracted from the generalized-Fano corollaries and then instantiated in both a passive Gaussian mean estimation problem and an interactive two-armed Gaussian bandit problem. These examples show how explicit worstcase Bayesian CVaR lower bounds can be obtained and how the resulting bounds compare with the corresponding Bayesian expected-loss benchmarks.
Recent work on CVaR has largely focused on risksensitive criteria that are different from the prior-predictive quantity studied here. In stochastic bandits, Baudry et al. [10] evaluate each arm by the CVaR of its reward distribution and analyze the corresponding cumulative regret relative to the arm with best CVaR. Tan and Weng [11] instead study upper bounds on the CVaR of the regret random variable itself. Wang et al. [12] consider a cumulative CVaR-regret criterion in bandits and reinforcement learning and analyze its expectation, so the CVaR-based performance gap is defined within each environment and then aggregated. Du et al. [13] study an iterated-CVaR objective in episodic reinforcement learning, which yields a dynamic nested risk measure. In passive settings, Thomas and Learned-Miller [14] study estimation of CVaR from i.i.d. samples, Soma and Yoshida [15] study learning with a population objective of the form CVaR of the loss under a fixed data-generating distribution, and Mhammedi et al. [16] derive PAC-Bayesian generalization bounds for empirical CVaR; in each case, CVaR is evaluated under a single fixed model dependent law. By contrast, our setting is Bayesian: one first draws a model M from a prior µ, then generates the transcript under P M,Alg , and finally evaluates the tail risk of the resulting loss under this prior-predictive mixture law. In this work, we study Bayesian CVaR under the priorpredictive law, which is a natural risk-sensitive analogue of Bayes risk: it captures not only average performance under model uncertainty, but also the severity of unfavorable outcomes induced jointly by the prior and the algorithm. Our goal is to derive explicit information-theoretic lower bounds for this prior-predictive CVaR criterion by instantiating the generalized-Fano framework of Bongole et al. [9]. A. Contributions The main contribution is to make the abstract Bayesian CVaR lower-bound framework of [9] concrete and usable in canonical problems. In particular: • We extract a reusable two-point Hellinger–CVaR lowerbound template from the generalized interactive Fano corollaries. • We instantiate this template in both a passive and an interactive setting, namely two-point Gaussian mean estimation and the two-armed Gaussian bandit. • For both examples, we derive explicit fixed-prior Bayesian CVaR lower bounds that recover the same order as the corresponding Bayes-risk benchmarks, while also retaining dependence on the risk level α. In particular, these immediately imply corresponding worst-case (over priors) Bayesian CVaR lower bounds. • We clarify the relation between Bayesian CVaR and Bayesian expected loss through the inequality CVaRα [L] ≥ E[L], which provides a natural benchmark for interpreting the derived bounds and highlights what is gained by a tail-sensitive lower-bound analysis. B. Notation Random variables are denoted by capital letters, such as M , X, Yt , and HT ; realizations are denoted by lowercase
letters. We write E for expectation and 1{·} for indicators. For z ∈ R, let [z]+ := max{z, 0}. For a model m ∈ M and an algorithm Alg, we write P m,Alg for the law of the observation or transcript X induced by running Alg in model m. Equivalently, X ∼ P m,Alg means that P m,Alg is the probability distribution of X given model m and algorithm Alg. In two-point constructions, we use the shorthand Pi := P Mi ,Alg , i ∈ {1, 2}. For a prior µ ∈ P(M), where P(M) is the set of all probability distributions on M, we write Eµ,P M,Alg [·] for expectation under the joint law obtained by first drawing M ∼ µ and then X ∼ P M,Alg . Similarly, for a reference law Q on the transcript space, we write Eµ,Q [·] when M ∼ µ and X ∼ Q are independent. We write Bern(p) for the Bernoulli distribution with mean p. For probability measures P and Q on a common measurable space, DKL (P ∥Q) denotes the Kullback–Leibler divergence, and Hellinger divergence, where DH 2 (P ∥Q) denotes thesquared R dP dP and DH 2 (P ∥Q) := 1 − DKL (P ∥Q) := log dQ R q dP dQ dλ dλ dλ, where λ is any common dominating measure. We use the standard inequality DH 2 (P ∥Q) ≤ DKL (P ∥Q). For a loss random variable L, CVaRα (L) denotes the upper-tail Conditional Value-at-Risk n at level α ∈ [0,o1), 1 E[(L − t)+ ] . defined by CVaRα (L) := mint∈R t + 1−α II. P ROBLEM SETUP Interactive statistical decision making (ISDM) provides a common language for passive estimation, sequential decision making, and learning under uncertainty. Following [2], an ISDM problem is specified by • a model class M, • an algorithm class D, • a transcript space X , • and a nonnegative loss function L : M × X → R+ . For each model M ∈ M and algorithm Alg ∈ D, the interaction between the algorithm and the model induces a law X ∼ P M,Alg on the transcript X ∈ X . Thus: • in a passive estimation problem, if one observes samples Y1 , . . . , Yn and then outputs an estimate θb = Alg(Y1 , . . . , Yn ), the transcript X may be taken to include both the batch of observations and the final b decision, e.g. X = (Y1 , . . . , Yn , θ); • in a sequential decision problem, X may be the full interaction history, including actions, observations, and any terminal decision, for example X = b (A1 , Y1 , . . . , AT , YT , d). This formulation therefore covers both passive and interactive settings within the same framework. Under a prior µ ∈ P(M), the standard Bayesian performance criterion is the Bayes risk Eµ,P M,Alg [L(M, X)]. Much of the existing lower-bound literature focuses on this expected loss. In this work, the focus is instead on the riskM,Alg sensitive criterion CVaRαµ⊗P (L) = Z 1 min t + (L(m, x) − t)+ (µ ⊗ P M,Alg )(dm, dx) . t∈R 1−α
This criterion captures tail-sensitive performance and is especially relevant when rare but costly failures matter. The main aim in this work is to turn the abstract Bayesian CVaR lower-bound framework of [9] into concrete and usable converse results. The emphasis is on showing how its corollaries can be instantiated in canonical problems. In particular, the paper develops a reusable two-point Bayesian CVaR template and applies it in both a passive example and an interactive example, thereby illustrating how explicit CVaR lower bounds can be derived directly from the generalized interactive Fano method. A. Previous results The analysis below builds on the Bayesian CVaR lowerbound framework of [9]. We recall the two corollaries that are used in our instantiations. Corollary 1 (Bounded-hinge lower bound [9, Cor. 2]). Assume 0 ≤ L(M, X) ≤ Lmax , and fix t ∈ R. Define ϕt (ℓ) :=
(ℓ − t)+ ∈ [0, 1], Lmax
bt := Eµ,Q [ϕt (L)] =
1 Eµ,Q [(L − t)+ ]. Lmax
Let B := EM ∼µ Df (P M,Alg ∥Q), and n o a− (B; b) := inf a ∈ [0, 1] : D Bern(a) Bern(b) ≤ B . f f
Let L : M × X → [0, Lmax ] be a bounded loss. Assume that, for some C ∈ [0, 2Lmax ], L(M1 , x) + L(M2 , x) ≥ C
for all x ∈ X ,
(H1)
and that DH 2 (P1 ∥P2 ) ≤ ΓH .
(H2)
Then, for every α ∈ [0, 1), CVaRµ⊗P α Lmax min t + t∈R 1−α
s
M,Alg
(L) ≥
C/2 − t Lmax
−
p
ΓH
!2
+
+
.
Proof sketch: Apply Corollary 2 with f = H 2 and reference law Q = P2 . Use (H1) to lower bound the hinge benchmark bt , use (H2) to bound the Hellinger budget, and then apply the Bernoulli Hellinger inversion √ √ 2B)2+ . a− H 2 (B; b) ≥ ( b − A simplified version is convenient for the balanced twopoint constructions used below. Corollary 3 (Balanced-pair Hellinger simplification). Under the assumptions of Lemma 1, if in addition L(M1 , x) + L(M2 , x) ≥ Lmax
for all x ∈ X ,
(H3)
then, for every α ∈ [0, 1),
Then Eµ,P M,Alg [(L − t)+ ] ≥ Lmax a− f (B; bt ). Corollary 2 (Bayesian CVaR lower bound [9, Cor. 3]). Under the assumptions of Corollary 1, Lmax − a (B; bt ) . CVaRα (L) ≥ min t + t∈R 1−α f Corollaries 1–2 reduce the derivation of explicit tailsensitive lower bounds to a concrete instantiation problem: choose a reference law Q, lower bound the corresponding hinge term bt , and upper bound the divergence budget B. III. R ESULTS This section presents the reusable two-point Hellinger– CVaR bound and the baseline comparison with Bayes risk that underlie the later examples. Full proofs are deferred to Appendix A. The first result is a reusable two-point Hellinger–CVaR bound that will be instantiated in the examples below. Lemma 1 (Two-point Hellinger–CVaR lower bound). Let M = {M1 , M2 }, let 1 1 µ = δM1 + δM2 , 2 2 and fix an algorithm Alg. Let Pi := P Mi ,Alg ,
i = 1, 2.
CVaRµ⊗P α Lmax min t + t∈R 1−α
s
M,Alg
(L) ≥
1 t − 2 Lmax
−
p
ΓH
!2
+
+
.
Proof sketch: Set C = Lmax in Lemma 1. The next proposition gives a baseline comparison with Bayesian expected loss. Proposition 1 (Bayesian CVaR dominates Bayesian expected loss). Let L be any integrable loss, and let α ∈ [0, 1). Then CVaRα (L) ≥ E[L]. Consequently, for any prior µ, CVaRµ⊗P α
M,Alg
(L) ≥ Eµ⊗P M,Alg [L].
In particular, if for some prior µ and some quantity ψ > 0 one has Eµ⊗P M,Alg [L] ≥ c ψ for a constant c > 0, then CVaRµ⊗P α
M,Alg
(L) ≥ c ψ.
Moreover, sup CVaRµ⊗P α µ
M,Alg
(L) ≥ sup Eµ⊗P M,Alg [L]. µ
IV. E XAMPLES
We equip this subfamily with the bounded estimation loss
We now instantiate the two-point Hellinger template in a passive and an interactive Gaussian problem. In both cases, the lower bound is obtained by restricting the full problem class to a carefully chosen two-model subfamily and applying the fixed-prior two-point result on that hard pair. Since a lower bound for one fixed prior immediately implies a lower bound for the supremum over priors, the resulting theorems also yield worst-case (over priors) Bayesian CVaR lower bounds. For readability, we state the main bounds here and defer the full proofs to Appendix A. Both examples lead to the same one-dimensional minimization, so we first introduce the closed-form function that appears in the resulting bounds. For α ∈ [0, 1), define ρ2 1 − , 0 ≤ ρ ≤ α, α > 0, 2 2α 2 Ψα (ρ) := (1 − ρ) , α < ρ ≤ 1, 2(1 − α) 0, ρ ≥ 1,
L(θ, X) := min{|θb − θ|, 2∆}.
and, for α = 0, (1 − ρ)2+ . 2 The function Ψα is continuous at the breakpoints ρ = α and ρ = 1; these branch values are obtained by the scalar minimization carried out in Lemma 2 in the appendix. We will also use the optimized constant 2 1 27(1 − α) , 0 ≤ α ≤ 3 , cα := √ α 1 √ , 3 ≤ α < 1. 3 3 Ψ0 (ρ) :=
A. A passive Gaussian mean estimation example We begin with a passive Gaussian example, where the transcript consists of the observations together with the final estimator output. Consider the Gaussian mean estimation problem in which one observes Y1 , . . . , Yn i.i.d. N (θ, 1), with unknown parameter θ ∈ R, and outputs an estimator b 1 , . . . , Yn ). θb = θ(Y In the ISDM formulation, the transcript is
To apply the two-point Hellinger template, we restrict attention to the hard two-point subfamily θ ∈ {−∆, +∆}, where ∆ > 0 will be chosen later. Let M− := M−∆ ,
µ :=
Theorem 1 (Gaussian mean estimation: α-dependent Bayesian CVaR lower bound). For every estimator θb and every α ∈ [0, 1), √ M,Alg CVaRµ⊗P (L) ≥ 2∆ Ψα (2 n ∆). α Equivalently, M,Alg
CVaRµ⊗P (L) ≥ α s !2 √ ∆−t 2∆ . min t + − 2n ∆ t∈R 1−α 2∆ + +
In particular, optimizing over ∆ and ν gives the worst-case lower bound M,Alg M,Alg cα (L) ≥ √ . (L) ≥ sup CVaRµ⊗P sup CVaRν⊗P α α n ∆>0 ν∈P(M) Proof sketch: The proof has three steps. First, identify the bounded loss level Lmax = 2∆. Second, verify the balancedpair condition via the triangle inequality: L(+∆, x) + L(−∆, x) ≥ 2∆. Third, bound the Hellinger divergence between the transcript laws induced by M+ and M− using the Gaussian KL comparison, DH 2 (P M+ ,Alg ∥P M− ,Alg ) ≤ DKL (P M+ ,Alg ∥P M− ,Alg ) = 2n∆2 , and apply Corollary 3. The closed form then follows from Lemma 2, and optimizing over ∆ and subsequently over ν yields the stated worst-case n−1/2 lower bound. B. Two-armed Gaussian bandits We then turn to an interactive Gaussian example, where the transcript is the full action–observation history. Consider the two-armed Gaussian bandit problem with unit-variance rewards and horizon T . At each round t, the algorithm Alg chooses an arm At ∈ {1, 2} based on the past history and then observes a reward Yt . The resulting transcript is HT = (A1 , Y1 , . . . , AT , YT ).
b X = (Y1 , . . . , Yn , θ).
M+ := M+∆ ,
The following theorem gives a fixed-prior Bayesian lower bound on this hard subfamily and hence also a worst-case Bayesian lower bound for the Gaussian mean estimation problem.
1 1 δM + δM . 2 + 2 −
To apply the two-point Hellinger template, we restrict attention to the two-environment subfamily g g g g M1 := + , − , M2 := − , + , 2 2 2 2 where g > 0 will be chosen later, and equip this subfamily with the symmetric prior µ=
1 1 δM + δM . 2 1 2 2
For a ∈ {1, 2}, let Na (HT ) denote the number of pulls of arm a up to time T . The following theorem gives a fixed-prior Bayesian lower bound on this hard two-environment family and hence also a worst-case Bayesian lower bound for the two-armed Gaussian bandit problem. Theorem 2 (Two-armed Gaussian bandits: α-dependent worst-case Bayesian CVaR lower bound). For every algorithm Alg and every α ∈ [0, 1), √ µ⊗P M,Alg CVaRα (RT ) ≥ gT Ψα (g T ). Equivalently, CVaRµ⊗P α min
t∈R
t+
gT 1−α
s
M,Alg
(RT ) ≥
√ !2 gT /2 − t g T , − √ gT 2 +
V. C ONCLUSION AND F UTURE W ORK We instantiate the generalized-Fano Bayesian CVaR framework through a reusable two-point Hellinger template. We derive worst-case Bayesian CVaR lower bounds for canonical problems such as Gaussian mean estimation and two-armed Gaussian bandits showing the applicability of the Hellinger template. The resulting bounds recover the known Bayesian expected-risk scaling while also revealing tail risk level αdependence, which is invisible to expected-risk lower bounds. Natural next steps are to understand whether multi-point versions of the present Hellinger template can recover sharp Bayesian CVaR scalings in K-armed bandits and episodic Markov decision processes while preserving explicit dependence on the risk level α, and to compare those lower bounds with matching upper bounds for risk-sensitive algorithms.
+
R EFERENCES
[1] A. B. Tsybakov, Introduction to Nonparametric Estimation, 1st ed. Springer, 2009. and optimizing over g and ν gives the worst-case lower [2] F. Chen, D. J. Foster, Y. Han, J. Qian, A. Rakhlin, and Y. Xu, “Assouad, Fano, and Le Cam with interaction: A unifying lower bound bound framework and characterization for bandit learnability,” Advances in √ M,Alg M,Alg µ⊗P Neural Information Processing Systems, vol. 37, pp. 75 585–75 641, sup CVaRν⊗P (R ) ≥ sup CVaR (R ) ≥ c T . T T α α α 2024. g>0 ν∈P(M) [3] T. Lattimore and C. Szepesvári, Bandit Algorithms. Cambridge University Press, 2020. Proof sketch: The proof has the same three-step structure [4] R. S. Sutton and A. G. Barto, Reinforcement Learning: An as in the passive example. First, identify the bounded loss Introduction, 2nd ed. MIT Press, 2018. [Online]. Available: https://mitpress.mit.edu/9780262039246/reinforcement-learning/ level Lmax = gT . Second, verify the balanced-pair condition: [5] R. T. Rockafellar and S. Uryasev, “Optimization of conditional valueat-risk,” Journal of Risk, vol. 2, no. 3, pp. 21–41, 2000. RT (M1 , h) + RT (M2 , h) = gT [6] ——, “Conditional value-at-risk for general loss distributions,” Journal of Banking & Finance, vol. 26, no. 7, pp. 1443–1471, 2002. for every transcript h. Third, bound the Hellinger divergence [7] C. Acerbi and D. Tasche, “Expected shortfall: A natural coherent through the Gaussian KL comparison alternative to value at risk,” Economic Notes, vol. 31, no. 2, pp. 379– 388, 2002. g2 T [8] T. Ma, K. A. Verchand, and R. J. Samworth, “High-probability M1 ,Alg M2 ,Alg M1 ,Alg M2 ,Alg DH 2 (P ∥P ) ≤ DKL (P ∥P )= , minimax lower bounds,” arXiv preprint arXiv:2406.13447, 2024. 2 [9] R. Bongole, T. J. Oechtering, and M. Skoglund, “Generalizing the fano inequality further,” arXiv preprint arXiv:2601.12027, 2026. and apply Corollary 3. The closed form follows from [10] D. Baudry, R. Gautron, E. Kaufmann, and O. Maillard, “Optimal Lemma 2, and optimizing over √ g and subsequently over ν thompson sampling strategies for support-aware cvar bandits,” in yields the stated worst-case T lower bound. International Conference on Machine Learning. PMLR, 2021, pp. 716–726. Remark 1 (Interpretation and relation to the examples). [11] C. Tan and P. Weng, “Cvar-regret bounds for multi-armed bandits,” in Asian Conference on Machine Learning. PMLR, 2023, pp. 974–989. Proposition 1 shows that any Bayes-risk lower bound imK. Wang, N. Kallus, and W. Sun, “Near-minimax-optimal risk-sensitive mediately yields a CVaRα lower bound of the same order. [12] reinforcement learning with cvar,” in International Conference on Thus, Bayes expected risk provides a natural baseline for Machine Learning. PMLR, 2023, pp. 35 864–35 907. interpreting tail-sensitive converse bounds. The value of the [13] Y. Du, S. Wang, and L. Huang, “Provably efficient risk-sensitive reinforcement learning: Iterated cvar and worst path,” arXiv preprint generalized-Fano corollaries is that they target the tail diarXiv:2206.02678, 2022. rectly under the prior-predictive law, provide an instantiation [14] P. S. Thomas and E. Learned-Miller, “Concentration inequalities for conditional value at risk,” in Proc. 36th Int. Conf. Machine Learning template for both non-interactive and interactive regimes, (ICML), ser. Proceedings of Machine Learning Research, vol. 97. and can yield more informative statements than expectation PMLR, 2019, pp. 6225–6233. alone through explicit dependence on α. [15] T. Soma and Y. Yoshida, “Statistical learning with conditional value at risk,” arXiv preprint arXiv:2002.05826, 2020. For the Gaussian estimation and two-armed bandit exZ. Mhammedi, B. Guedj, and R. C. Williamson, “PAC-bayesian amples, the bounds obtained from the two-point Hellinger [16] bound for the conditional value at risk,” in Advances in Neural template recover the same scaling as the corresponding Information Processing Systems, 2020, neurIPS 2020. Also available √ as arXiv:2006.14763. Bayes-risk benchmarks, namely n−1/2 and T , respectively. M. Ang, J. Sun, and Q. Yao, “On the dual representation of coherent At the same time, unlike the expected Bayes-risk bound, they [17] risk measures,” Annals of Operations Research, vol. 262, no. 1, pp. retain α-dependence through Ψα (·) and cα . In this sense, 29–46, 2018.
the examples show that the generalized-Fano corollaries are both calibrated to the known Bayesian scaling in canonical two-point problems and capable of capturing tail-sensitive behavior.
A PPENDIX Lemma 2 (Scalar minimization). For α ∈ [0, 1) and ρ ≥ 0, define √ √ ( x − ρ/ 2)2+ 1 Fα,ρ (x) := − x + , x ∈ [0, 1/2]. 2 1−α Then inf Fα,ρ (x) = Ψα (ρ). x∈[0,1/2]
Moreover, sup ρ Ψα (ρ) = cα . ρ≥0
√ Proof. Write x = s2 , with s ∈ [0, 1/ 2]. Then √ (s − ρ/ 2)2+ 1 2 Fα,ρ (x) = − s + . 2 1−α We first identify √ inf x∈[0,1/2] Fα,ρ (x). If 0 ≤ s ≤ ρ/ 2, then 1 − s2 , 2 so the minimum on this region is 1 − ρ2 , 0 ≤ ρ ≤ 1, 2 2 Fα,ρ (x) =
ρ ≥ 1. √ √ Now suppose ρ/ 2 ≤ s ≤ 1/ 2. Then √ 1 (s − ρ/ 2)2 Fα,ρ (x) = − s2 + . 2 1−α If α = 0, this becomes 1 √ ρ2 − 2ρs + , 2 2 0,
√ which is decreasing in s, hence minimized at s = 1/ 2, with value (1 − ρ)2 (0 ≤ ρ ≤ 1). 2 Since 1 ρ2 (1 − ρ)2 ≤ − (0 ≤ ρ ≤ 1), 2 2 2 it follows that (1−ρ)2 , 0 ≤ ρ ≤ 1, 2 inf F0,ρ (x) = = Ψ0 (ρ). 0, x∈[0,1/2] ρ ≥ 1, √ √ Assume now 0 < α < 1. On [ρ/ 2, 1/ 2], √ 1 (s − ρ/ 2)2 2 Gα,ρ (s) := − s + 2 1−α is a convex quadratic with √ 2α 2ρ ′ Gα,ρ (s) = s− , 1−α 1−α so its critical point is ρ s⋆ = √ . 2α
√ √ If 0 ≤ ρ ≤ α, then s⋆ ∈ [ρ/ 2, 1/ 2], and Gα,ρ (s⋆ ) =
1 ρ2 − . 2 2α
√ If α√< ρ √ ≤ 1, then s⋆ > 1/ 2, so Gα,ρ is decreasing√on [ρ/ 2, 1/ 2], and its minimum is attained at s = 1/ 2, giving √ (1 − ρ)2 Gα,ρ (1/ 2) = . 2(1 − α) √ Finally, if ρ ≥ 1, choosing s = 1/ 2 gives value 0. Comparing with the first region,
and
1 ρ2 1 ρ2 − ≤ − 2 2α 2 2
(0 ≤ ρ ≤ α),
(1 − ρ)2 1 ρ2 ≤ − 2(1 − α) 2 2
(α < ρ ≤ 1).
Hence inf x∈[0,1/2]
Fα,ρ (x) = Ψα (ρ)
for all α ∈ [0, 1). It remains to maximize ρΨα (ρ). Since Ψα (ρ) = 0 for ρ ≥ 1, it suffices to work on [0, 1]. If α = 0, then ρΨ0 (ρ) =
ρ(1 − ρ)2 , 2
0 ≤ ρ ≤ 1,
whose derivative is (1 − ρ)(1 − 3ρ) . 2 Thus the maximum is attained at ρ = 1/3, with value (1/3)(2/3)2 2 = = c0 . 2 27 Now let 0 < α < 1. We have ρ ρ3 − 0 ≤ ρ ≤ α, 2 2α , ρΨα (ρ) = 2 ρ(1 − ρ) , α < ρ ≤ 1. 2(1 − α) On [0, α], the derivative is 1 3ρ2 − , 2 2α p so the critical point is ρ = α/3. Hence the maximum on [0, α] is √ 1 α √ if α ≥ , 3 3 3 and otherwise is attained at ρ = α, with value α(1 − α) . 2 On (α, 1], the derivative is (1 − ρ)(1 − 3ρ) , 2(1 − α)
so the interior critical point is ρ = 1/3. Hence the maximum on (α, 1] is 2 1 if α ≤ , 27(1 − α) 3 and otherwise is attained at the boundary ρ = α, with value α(1 − α) . 2 Since the two branches agree at ρ = α, it remains only to compare the boundary value with the interior one. For 0 ≤ α ≤ 1/3, 2 α(1 − α) ≤ , 2 27(1 − α) and for 1/3 ≤ α < 1, √ α α(1 − α) ≤ √ . 2 3 3
Corollary 2 gives M,Alg CVaRµ⊗P (L) ≥ min α t∈R
2 , 27(1 − α) sup ρ Ψα (ρ) = √ α ρ≥0 √ , 3 3 which is exactly cα .
then and so
0 ≤ α ≤ 13 , 1 3 ≤ α < 1,
Proof of Lemma 1. Apply Corollary 2 with f = H 2 and reference law Q := P2 . For each t ∈ R, define bt :=
√
√ √ a ≥ ( b − 2B)+ ,
√ √ a− (B; b) ≥ ( b − 2B)2+ . 2 H
(A.10)
Combining (A.7), (A.8), and (A.10), we obtain s !2 p C/2 − t − aH 2 (B; bt ) ≥ . − ΓH Lmax + +
Substituting this into (A.9) proves the claim. Proof of Corollary 3. Set C = Lmax in Lemma 1. This gives M,Alg
1 Lmax
(L) ≥ CVaRµ⊗P α s !2 p Lmax 1 t min t + . − − ΓH t∈R 1−α 2 Lmax +
Eµ,Q [(L − t)+ ].
Since µ = 12 (δM1 + δM2 ), bt =
Lmax − t+ a 2 (B; bt ) . (A.9) 1−α H
For Bernoulli laws, one has p √ DH 2 Bern(a) Bern(b) = 1 − ab − (1 − a)(1 − b) = √ √ √ 1 √ ( a − b)2 + ( 1 − a − 1 − b)2 . 2 Hence √ 1 √ DH 2 Bern(a) Bern(b) ≥ ( a − b)2 . 2 Therefore, if DH 2 Bern(a) Bern(b) ≤ B,
Therefore
+
1 EP2 (L(M1 , X) − t)+ + (L(M2 , X) − t)+ . 2Lmax
Fix x ∈ X . By convexity of u 7→ (u − t)+ , 1 (L(M1 , x) − t)+ + (L(M2 , x) − t)+ ≥ 2 L(M1 , x) + L(M2 , x) −t . 2 +
Proof of Proposition 1. By the dual representation of Expected Shortfall/CVaR [17], n o 1 , E[Z] = 1 . CVaRα (L) = sup E[LZ] : 0 ≤ Z ≤ 1−α Since the choice Z ≡ 1 is feasible, it follows that
Using assumption (H1), C 1 (L(M1 , x) − t)+ + (L(M2 , x) − t)+ ≥ −t . 2 2 + Taking EP2 and dividing by Lmax yields C/2 − t bt ≥ . Lmax +
CVaRα (L) ≥ E[L]. Applying this under the Bayesian law µ ⊗ P M,Alg gives CVaRµ⊗P α
M,Alg
(L) ≥ Eµ⊗P M,Alg [L].
The remaining claims follow immediately. (A.7)
Next, B = EM ∼µ DH 2 (P M,Alg ∥Q) = 1 1 1 DH 2 (P1 ∥P2 ) + DH 2 (P2 ∥P2 ) = DH 2 (P1 ∥P2 ). 2 2 2 Using (H2), ΓH B≤ . (A.8) 2
Proof of Theorem 1. We verify the assumptions of Corollary 3. Step 1: Boundedness and balanced-pair condition. By definition, 0 ≤ L(θ, X) ≤ 2∆. Hence Lmax = 2∆. Fix any realized estimate z ∈ R. Then |z − ∆| + |z + ∆| ≥ 2∆
Proof of Theorem 2. We verify the assumptions of Corollary 3.
by the triangle inequality, so min{|z − ∆|, 2∆} + min{|z + ∆|, 2∆} ≥ 2∆.
Step 1: Balanced-pair condition and boundedness. Under M1 , arm 1 is optimal and arm 2 is suboptimal by gap g, so
Applying this with z = θb gives L(+∆, X) + L(−∆, X) ≥ 2∆ = Lmax .
RT (M1 , HT ) = g N2 (HT ).
Step 2: Hellinger budget. The observation vector Y =
Under M2 , arm 2 is optimal and arm 1 is suboptimal by gap g, so RT (M2 , HT ) = g N1 (HT ).
(Y1 , . . . , Yn ) has laws N (∆, 1)⊗n
N (−∆, 1)⊗n
and
Hence, for every transcript h,
under M+ and M− , respectively. Since the transcript b X = (Y, θ),
RT (M1 , h) + RT (M2 , h) = g N1 (h) + N2 (h) = gT.
θb = Alg(Y ),
Also,
is a measurable function of Y , the data-processing inequality gives DH 2 (P
M+ ,Alg
∥P
M− ,Alg
⊗n
) ≤ DKL N (∆, 1)
⊗n
N (−∆, 1)
Now DKL N (∆, 1)⊗n N (−∆, 1)⊗n = (2∆)2 n DKL (N (∆, 1)∥N (−∆, 1)) = n · = 2n∆2 . 2 Hence we may take
0 ≤ RT (Mi , HT ) ≤ gT,
i = 1, 2.
Thus L(M, HT ) := RT (M, HT ) satisfies the balanced-pair condition with L max = gT . . Step 2: Hellinger budget. For this two-armed Gaussian construction, DH 2 (P M1 ,Alg ∥P M2 ,Alg ) ≤ DKL (P M1 ,Alg ∥P M2 ,Alg ) =
g2 T . 2
2
Hence we may take ΓH := g 2T . Step 3: Apply Corollary 3. We obtain
ΓH := 2n∆2 .
M,Alg
Step 3: Apply Corollary 3. We obtain M,Alg
CVaRµ⊗P (L) ≥ α s !2 √ 2∆ ∆−t − 2n ∆ min t + . (A.11) t∈R 1−α 2∆ + +
(RT ) ≥ CVaRµ⊗P α s √ !2 gT g T gT /2 − t min t + − √ . t∈R 1−α gT 2 + +
(A.12) Step 4: Closed form. Since 0 ≤ RT ≤ gT , the minimization in (A.12) may be restricted to t ∈ [0, gT ]. Set
Step 4: Closed form. Since 0 ≤ L ≤ 2∆, the minimization in (A.11) may be restricted to t ∈ [0, 2∆]. Set t 1 − ∈ [0, 1/2]. 2 2∆ Then t = 2∆(1/2 − x), and (A.11) becomes x :=
M,Alg
CVaRµ⊗P (L) ≥ α ( ) √ √ ( x − 2n ∆)2+ 1 2∆ inf −x+ . 2 1−α x∈[0,1/2] √ √ √ Since 2n ∆ = 2 √n2∆ , Lemma 2 with ρ = 2 n ∆ yields √ (L) ≥ 2∆ Ψα (2 n ∆). √ √ Finally, write ρ := 2 n ∆, so that 2∆ = ρ/ n. Then µ⊗P CVaRα
M,Alg
√ ρ Ψα (ρ) 2∆ Ψα (2 n ∆) = √ . n Maximizing over ρ ≥ 0 and using Lemma 2 gives M,Alg cα sup CVaRµ⊗P (L) ≥ √ . α n ∆>0
x :=
1 t − ∈ [0, 1/2]. 2 gT
Then t = gT (1/2 − x), and (A.12) becomes M,Alg
CVaRµ⊗P (RT ) ≥ α ( ) √ √ √ ( x − g T / 2)2+ 1 gT inf −x+ . 2 1−α x∈[0,1/2] √ Lemma 2 with ρ = g T yields √ M,Alg CVaRµ⊗P (RT ) ≥ gT Ψα (g T ). α √ √ Finally, write ρ := g T , so that gT = ρ T . Then √ √ gT Ψα (g T ) = ρ Ψα (ρ) T . Maximizing over ρ ≥ 0 and using Lemma 2 gives √ M,Alg sup CVaRµ⊗P (RT ) ≥ cα T . α g>0