Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems

1. Problem Statement

The paper addresses the challenge of deriving lower bounds for risk-sensitive performance in interactive statistical decision-making (ISDM) problems.

• Context: In modern learning and control (e.g., multi-armed bandits, reinforcement learning), algorithms interact with an environment. While traditional analysis focuses on Bayes Risk (expected loss), this metric can mask rare but catastrophic failures.
• Metric: The authors focus on Conditional Value-at-Risk (CVaR), denoted as $\text{CVaR}_\alpha(L)$. This measures the expected loss in the worst $(1-\alpha)$ tail of the loss distribution, making it sensitive to adverse events.
• The Gap: While a generalized Fano framework for Bayesian CVaR lower bounds was recently proposed by Bongole et al. [9], it remained abstract. The corollaries identified necessary quantities (a benchmark term and a divergence budget) but did not provide a concrete method to calculate them for specific problems.
• Objective: To "instantiate" this abstract framework, providing a reusable template to derive explicit, closed-form Bayesian CVaR lower bounds for canonical ISDM problems.

2. Methodology

The authors develop a two-point Hellinger–CVaR lower bound template derived from the generalized interactive Fano inequalities.

Core Framework

The approach relies on comparing a "hard" problem instance against a reference model using the squared Hellinger distance ($D_{H^2}$).

1. Two-Point Construction: The problem is restricted to a subfamily of two models, $\mathcal{M} = \{M_1, M_2\}$, with a uniform prior $\mu = \frac{1}{2}\delta_{M_1} + \frac{1}{2}\delta_{M_2}$.
2. Loss Condition: A "balanced-pair" condition is imposed on the loss function $L$:
   $$L(M_1, x) + L(M_2, x) \geq L_{\max}$$
   for all transcripts $x$. This ensures that if the algorithm performs well on one model, it must perform poorly on the other.
3. Divergence Budget: The squared Hellinger distance between the laws of the transcripts induced by the two models is bounded:
   $$D_{H^2}(P_{M_1, \text{Alg}} \| P_{M_2, \text{Alg}}) \leq \Gamma_H$$
4. Derivation: By applying Corollary 2 from [9] with the reference law $Q = P_{M_2}$ and using the properties of the Bernoulli distribution, the authors derive a minimization formula for the CVaR lower bound.

Key Mathematical Tool

The paper introduces a closed-form function $\Psi_\alpha(\rho)$ which encapsulates the result of the minimization over the threshold $t$:
$$\text{CVaR}_\alpha(L) \geq L_{\max} \cdot \Psi_\alpha(\rho)$$
where $\rho$ is related to the Hellinger distance budget. This function allows for explicit calculation of the bound based on the risk level $\alpha$.

3. Key Contributions

1. Reusable Template: Extraction of a specific Two-Point Hellinger–CVaR lower bound (Lemma 1 and Corollary 3) that transforms abstract Fano corollaries into a practical calculation tool.
2. Instantiation in Canonical Problems: Application of this template to two distinct settings:
   • Passive: Gaussian mean estimation.
   • Interactive: Two-armed Gaussian bandits.
3. Explicit Bounds: Derivation of closed-form lower bounds that explicitly show the dependence on the risk level $\alpha$, the problem parameters (e.g., sample size $n$, horizon $T$), and the gap between models.
4. Benchmarking: Clarification of the relationship between Bayesian CVaR and Bayesian Expected Loss. The paper proves that $\text{CVaR}_\alpha(L) \geq \mathbb{E}[L]$, establishing expected risk as a natural baseline, while showing that CVaR bounds capture additional tail-risk information.

4. Results

The authors apply their template to derive worst-case Bayesian CVaR lower bounds for the following scenarios:

A. Passive Gaussian Mean Estimation

• Setup: Estimating a mean $\theta \in \{-\Delta, +\Delta\}$ from $n$ i.i.d. samples $Y_i \sim \mathcal{N}(\theta, 1)$.
• Result: The worst-case Bayesian CVaR lower bound scales as:
  $$\sup_{\nu} \text{CVaR}_\alpha(L) \geq c_\alpha \frac{1}{\sqrt{n}}$$
  where $c_\alpha$ is a constant depending on $\alpha$.
• Insight: The bound recovers the standard $n^{-1/2}$ scaling of Bayes risk but includes a factor $c_\alpha$ that reflects the sensitivity to the tail risk level.

B. Two-Armed Gaussian Bandits

• Setup: A sequential decision problem with horizon $T$ and two arms having means $\pm g/2$.
• Result: The worst-case Bayesian CVaR lower bound on cumulative regret scales as:
  $$\sup_{\nu} \text{CVaR}_\alpha(R_T) \geq c_\alpha \sqrt{T}$$
• Insight: Similar to the passive case, the bound recovers the standard $\sqrt{T}$ regret scaling but explicitly retains the dependence on $\alpha$ via the function $\Psi_\alpha$ and constant $c_\alpha$.

Comparison with Expected Risk

The results confirm that while the order of the lower bounds (e.g., $1/\sqrt{n}$ or $\sqrt{T}$) matches the classical Bayes risk bounds, the constants differ. The CVaR bounds are strictly higher than the expected loss bounds (as expected by definition) and provide a more granular view of performance under the prior-predictive law, specifically highlighting the cost of rare failures.

5. Significance

• Practical Utility: The paper bridges the gap between theoretical information-theoretic limits and practical risk-sensitive analysis. It provides a "plug-and-play" method for researchers to calculate CVaR lower bounds without re-deriving complex inequalities from scratch.
• Risk-Sensitive Control: In safety-critical applications (finance, autonomous systems), knowing the expected performance is insufficient. This framework quantifies the fundamental limits of how well an algorithm can avoid worst-case scenarios.
• Validation of Framework: By recovering known scaling laws ($1/\sqrt{n}$ and $\sqrt{T}$) while adding $\alpha$-dependence, the work validates the generalized-Fano framework as a robust tool for analyzing tail risks in interactive learning.
• Future Directions: The authors suggest extending this to multi-point constructions for $K$-armed bandits and Markov Decision Processes (MDPs) to see if sharp scalings can be maintained while preserving explicit risk-level dependence.

In summary, this paper operationalizes a theoretical framework for risk-sensitive learning, demonstrating that fundamental information-theoretic limits exist not just for average performance, but also for the worst-case tails of the loss distribution in interactive settings.