An adaptive stochastic optimization algorithm for resource allocation

Xavier Fontaine, Shie Mannor, Vianney Perchet
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:319-363, 2020.

Abstract

We consider the classical problem of sequential resource allocation where a decision maker must repeatedly divide a budget between several resources, each with diminishing returns. This can be recast as a specific stochastic optimization problem where the objective is to maximize the cumulative reward, or equivalently to minimize the regret. We construct an algorithm that is adaptive to the complexity of the problem, expressed in term of the regularity of the returns of the resources, measured by the exponent in the Łojasiewicz inequality (or by their universal concavity parameter). Our parameter-independent algorithm recovers the optimal rates for strongly-concave functions and the classical fast rates of multi-armed bandit (for linear reward functions). Moreover, the algorithm improves existing results on stochastic optimization in this regret minimization setting for intermediate cases.

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-fontaine20a, title = {An adaptive stochastic optimization algorithm for resource allocation}, author = {Fontaine, Xavier and Mannor, Shie and Perchet, Vianney}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {319--363}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/fontaine20a/fontaine20a.pdf}, url = {https://proceedings.mlr.press/v117/fontaine20a.html}, abstract = {We consider the classical problem of sequential resource allocation where a decision maker must repeatedly divide a budget between several resources, each with diminishing returns. This can be recast as a specific stochastic optimization problem where the objective is to maximize the cumulative reward, or equivalently to minimize the regret. We construct an algorithm that is adaptive to the complexity of the problem, expressed in term of the regularity of the returns of the resources, measured by the exponent in the Łojasiewicz inequality (or by their universal concavity parameter). Our parameter-independent algorithm recovers the optimal rates for strongly-concave functions and the classical fast rates of multi-armed bandit (for linear reward functions). Moreover, the algorithm improves existing results on stochastic optimization in this regret minimization setting for intermediate cases.} }
Endnote
%0 Conference Paper %T An adaptive stochastic optimization algorithm for resource allocation %A Xavier Fontaine %A Shie Mannor %A Vianney Perchet %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-fontaine20a %I PMLR %P 319--363 %U https://proceedings.mlr.press/v117/fontaine20a.html %V 117 %X We consider the classical problem of sequential resource allocation where a decision maker must repeatedly divide a budget between several resources, each with diminishing returns. This can be recast as a specific stochastic optimization problem where the objective is to maximize the cumulative reward, or equivalently to minimize the regret. We construct an algorithm that is adaptive to the complexity of the problem, expressed in term of the regularity of the returns of the resources, measured by the exponent in the Łojasiewicz inequality (or by their universal concavity parameter). Our parameter-independent algorithm recovers the optimal rates for strongly-concave functions and the classical fast rates of multi-armed bandit (for linear reward functions). Moreover, the algorithm improves existing results on stochastic optimization in this regret minimization setting for intermediate cases.
APA
Fontaine, X., Mannor, S. & Perchet, V.. (2020). An adaptive stochastic optimization algorithm for resource allocation. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:319-363 Available from https://proceedings.mlr.press/v117/fontaine20a.html.

Related Material