The Cross-Entropy Method Optimizes for Quantiles

Sergiu Goschin, Ari Weinstein, Michael Littman
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):1193-1201, 2013.

Abstract

Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores. We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-goschin13, title = {The Cross-Entropy Method Optimizes for Quantiles}, author = {Goschin, Sergiu and Weinstein, Ari and Littman, Michael}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {1193--1201}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/goschin13.pdf}, url = {https://proceedings.mlr.press/v28/goschin13.html}, abstract = {Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores. We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.} }
Endnote
%0 Conference Paper %T The Cross-Entropy Method Optimizes for Quantiles %A Sergiu Goschin %A Ari Weinstein %A Michael Littman %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-goschin13 %I PMLR %P 1193--1201 %U https://proceedings.mlr.press/v28/goschin13.html %V 28 %N 3 %X Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores. We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.
RIS
TY - CPAPER TI - The Cross-Entropy Method Optimizes for Quantiles AU - Sergiu Goschin AU - Ari Weinstein AU - Michael Littman BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-goschin13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 1193 EP - 1201 L1 - http://proceedings.mlr.press/v28/goschin13.pdf UR - https://proceedings.mlr.press/v28/goschin13.html AB - Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores. We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality. ER -
APA
Goschin, S., Weinstein, A. & Littman, M.. (2013). The Cross-Entropy Method Optimizes for Quantiles. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):1193-1201 Available from https://proceedings.mlr.press/v28/goschin13.html.

Related Material