# Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

arXiv: https://arxiv.org/abs/2606.23096 · HTML: https://mlsanity.com/paper/2606.23096/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 22 Jun 2026.

## Builds on (most cited first, 16 of 16)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [Information Extraction Under Privacy Constraints](https://mlsanity.com/paper/1511.02381/) (2015)
- [Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy](https://mlsanity.com/paper/2501.14928/) (2025)
- [Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Making](https://mlsanity.com/paper/2510.05808/) (2025)
- [The Privacy Funnel from the viewpoint of Local Differential Privacy](https://mlsanity.com/paper/2002.01501/) (2020)
- [High-Probability Bounds For Heterogeneous Local Differential Privacy](https://mlsanity.com/paper/2510.11895/) (2025)
- [Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning](https://mlsanity.com/paper/2605.05102/) (2026)

## Abstract (arXiv)

Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures. To address this concern, we develop a δ-explicit minimax-quantile theory for interactive statistical decision making (ISDM). We first provide structural relations between minimax quantiles, lower minimax quantiles, and minimax risk. This includes a quantile-to-expectation conversion and an equivalence between strict and lower minimax quantiles outside a countable set of confidence levels. We then derive two converse tools for ISDM: a high-probability interactive Fano's method and a high-probability interactive Le Cam's method. Then, we show that mutual-information (MI) privacy can be handled in the same framework by restricting the admissible decision class. For coordinatewise Gaussian privatization, we derive a two-point template that isolates the privacy-induced variance inflation. We instantiate this template for Gaussian mean estimation, and use the same two-point strategy directly for two-armed Gaussian bandits. We then derive a minimax quantile lower bound for the K-armed Gaussian bandit problem, showing that the interactive Fano method captures the exploration cost over multiple possible best arms. The resulting lower bounds are explicit in the confidence level δ and in the privacy budget for the private problems. They yield log(1/δ)/n scaling for squared-error Gaussian mean estimation, √Tlog(1/δ) scaling for two-armed bounded-mean Gaussian bandits, and √KTlog(1/δ)-type scaling for the K-armed bandits, with privacy appearing through a Gaussian variance-inflation factor for the private problems.