Quantum Algorithms for Risk-Sensitive Bandits: Matching Upper and Lower Bounds for Quantum CVaR Estimation

Multi-armed bandit algorithms decide which option to try next when each choice both yields an outcome and reveals information. Standard methods rank options by average reward, but finance, medicine, and safety-critical control care about lower-tail performance, average performance in the worst $\alpha$ fraction of cases, formalized by the conditional value-at-risk. Quantum algorithms accelerate average-reward bandits, and risk-sensitive bandit theory is well developed classically, but the intersection has been empty. We give the first quantum algorithms for risk-sensitive bandits, with matching lower bounds. Our core primitive estimates conditional value-at-risk using quadratically fewer oracle queries than the analyzed classical sampling baseline, and an amplitude-aware refinement adds a further square-root advantage in the tail level by exploiting the fact that the estimated quantity is intrinsically small deep in the tail. Building on it we obtain best-arm identification that improves quadratically in the arm gap, and regret with no polynomial gap dependence. Adversary-method lower bounds show the estimator is optimal in both parameters.