# Estimating the Maximum Expected Value: An Analysis of (Nested) Cross Validation and the Maximum Sample Average

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2013.

## Built on by (most cited first, 7 of 7)

- [Regularized Softmax Deep Multi-Agent Q-Learning](https://mlsanity.com/paper/2103.11883/) (2021)
- [Action Candidate Driven Clipped Double Q-learning for Discrete and Continuous Action Tasks](https://mlsanity.com/paper/2203.11526/) (2022)
- [Anti-Overestimation Dialogue Policy Learning for Task-Completion Dialogue System](https://mlsanity.com/paper/2207.11762/) (2022)
- [Action Candidate Based Clipped Double Q-learning for Discrete and Continuous Action Tasks](https://mlsanity.com/paper/2105.00704/) (2021)
- [Multi-Bellman operator for convergence of Q-learning with linear function approximation](https://mlsanity.com/paper/2309.16819/) (2023)
- [Calibration Matters: Tackling Maximization Bias in Large-scale Advertising Recommendation Systems](https://mlsanity.com/paper/2205.09809/) (2022)
- [Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits](https://mlsanity.com/paper/2412.00345/) (2024)

## Abstract (arXiv)

We investigate the accuracy of the two most common estimators for the maximum expected value of a general set of random variables: a generalization of the maximum sample average, and cross validation. No unbiased estimator exists and we show that it is non-trivial to select a good estimator without knowledge about the distributions of the random variables. We investigate and bound the bias and variance of the aforementioned estimators and prove consistency. The variance of cross validation can be significantly reduced, but not without risking a large bias. The bias and variance of different variants of cross validation are shown to be very problem-dependent, and a wrong choice can lead to very inaccurate estimates.