Online Resource Allocation with Convex-set Machine-Learned Advice
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917500953821184 |
|---|---|
| author | Golrezaei, Negin Jaillet, Patrick Zhou, Zijie |
| author_facet | Golrezaei, Negin Jaillet, Patrick Zhou, Zijie |
| contents | Decision-makers often have access to machine-learned predictions about future demand that can help guide online resource allocation decisions. However, such predictions may be inaccurate. We develop a framework for online resource allocation with potentially unreliable machine-learned advice, where the advice is represented as a convex uncertainty set for the demand vector rather than a single point estimate.
We introduce a parameterized class of Pareto-optimal online algorithms that balance consistency and robustness. The consistent ratio measures performance when the advice is accurate, while the robust ratio measures performance under adversarial demand when the advice is inaccurate. For a target consistency level C, our algorithms maximize robustness subject to achieving at least consistency level C.
Our approach extends classical protection-level algorithms by introducing adaptive protection levels that dynamically respond to uncertainty in the advice. We also provide a method for computing the maximum achievable consistency level. Numerical experiments demonstrate that our algorithms outperform benchmark methods, including approaches based solely on point forecasts, by effectively balancing worst-case and average-case performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_12282 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Online Resource Allocation with Convex-set Machine-Learned Advice Golrezaei, Negin Jaillet, Patrick Zhou, Zijie Data Structures and Algorithms Machine Learning Optimization and Control Decision-makers often have access to machine-learned predictions about future demand that can help guide online resource allocation decisions. However, such predictions may be inaccurate. We develop a framework for online resource allocation with potentially unreliable machine-learned advice, where the advice is represented as a convex uncertainty set for the demand vector rather than a single point estimate. We introduce a parameterized class of Pareto-optimal online algorithms that balance consistency and robustness. The consistent ratio measures performance when the advice is accurate, while the robust ratio measures performance under adversarial demand when the advice is inaccurate. For a target consistency level C, our algorithms maximize robustness subject to achieving at least consistency level C. Our approach extends classical protection-level algorithms by introducing adaptive protection levels that dynamically respond to uncertainty in the advice. We also provide a method for computing the maximum achievable consistency level. Numerical experiments demonstrate that our algorithms outperform benchmark methods, including approaches based solely on point forecasts, by effectively balancing worst-case and average-case performance. |
| title | Online Resource Allocation with Convex-set Machine-Learned Advice |
| topic | Data Structures and Algorithms Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2306.12282 |