  We address the challenges posed by heteroscedastic noise in contextual
decision-making. We propose a consistent Shrinking Neighborhood Estimation
(SNE) technique that successfully estimates contextual performance under
unpredictable variances. Furthermore, we propose a Rate-Efficient Sampling rule
designed to enhance the performance of the SNE. The effectiveness of the
combined solution ``Contextual Optimizer through Neighborhood Estimation"(CONE)
is validated through theorems and numerical benchmarking. The methodologies
have been further deployed to address a staffing challenge in a hospital call
center, exemplifying their substantial impact and practical utility in
real-world scenarios.
