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

By Hado van Hasselt. 2013

34 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Controlling Overestimation Bias with Truncated Mixture of Continuous Distributional Quantile Critics (2020, methodology): “The de facto standard for alleviating overestimations in discrete control is the double estimator (Van Hasselt, 2010; 2013).”
Estimating Maximum Expected Value through Gaussian Approximation (2016, methodology): “In many machine learning problems it is necessary to estimate the maximum expected value (MEV) of a set of random variables, given samples collected from each variable (van Hasselt, 2013).”
Estimating the Maximum Expected Value in Continuous Reinforcement Learning Problems (2017, background): “Estimator (DE) (Van Hasselt 2013) approximates the maximum by splitting the sample set into two disjoint sample sets.”
Estimating the Maximum Expected Value through Upper Confidence Bound of Likelihood (2017, background): “N (2) i ) [7], where N (1) i , N (2) i”
Interleaved Q-Learning with Partially Coupled Training Process (2019, methodology): “It has been proved in [22] that no general unbiased estimator exists even if all μ̂i are unbiased.”