Blind Network Revenue Management and Bandits with Knapsacks under Limited Switches
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912589889404928 |
|---|---|
| author | Simchi-Levi, David Xu, Yunzong Zhao, Jinglong |
| author_facet | Simchi-Levi, David Xu, Yunzong Zhao, Jinglong |
| contents | This paper studies the impact of limited switches on resource-constrained dynamic pricing with demand learning. We focus on the classical price-based blind network revenue management problem and extend our results to the bandits with knapsacks problem. In both settings, a decision maker faces stochastic and distributionally unknown demand, and must allocate finite initial inventory across multiple resources over time. In addition to standard resource constraints, we impose a switching constraint that limits the number of action changes over the time horizon. We establish matching upper and lower bounds on the optimal regret and develop computationally efficient limited-switch algorithms that achieve it. We show that the optimal regret rate is fully characterized by a piecewise-constant function of the switching budget, which further depends on the number of resource constraints. Our results highlight the fundamental role of resource constraints in shaping the statistical complexity of online learning under limited switches. Extensive simulations demonstrate that our algorithms maintain strong cumulative reward performance while significantly reducing the number of switches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1911_01067 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Blind Network Revenue Management and Bandits with Knapsacks under Limited Switches Simchi-Levi, David Xu, Yunzong Zhao, Jinglong Machine Learning Computer Science and Game Theory Optimization and Control This paper studies the impact of limited switches on resource-constrained dynamic pricing with demand learning. We focus on the classical price-based blind network revenue management problem and extend our results to the bandits with knapsacks problem. In both settings, a decision maker faces stochastic and distributionally unknown demand, and must allocate finite initial inventory across multiple resources over time. In addition to standard resource constraints, we impose a switching constraint that limits the number of action changes over the time horizon. We establish matching upper and lower bounds on the optimal regret and develop computationally efficient limited-switch algorithms that achieve it. We show that the optimal regret rate is fully characterized by a piecewise-constant function of the switching budget, which further depends on the number of resource constraints. Our results highlight the fundamental role of resource constraints in shaping the statistical complexity of online learning under limited switches. Extensive simulations demonstrate that our algorithms maintain strong cumulative reward performance while significantly reducing the number of switches. |
| title | Blind Network Revenue Management and Bandits with Knapsacks under Limited Switches |
| topic | Machine Learning Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/1911.01067 |