Online Resource Allocation in Episodic Markov Decision Processes
Authors:
Preprint
Abstract
This paper studies a long-term resource allocation problem over multiple periods where each period requires a multi-stage decision-making process. We formulate the problem as an online allocation problem in an episodic finite-horizon constrained Markov decision process with an unknown non-stationary transition function and stochastic non-stationary reward and resource consumption functions. We propose the observe-then-decide regime and improve the existing decide-then-observe regime, while the two settings differ in how the observations and feedback about the reward and resource consumption functions are given to the decision-maker. We develop an online dual mirror descent algorithm that achieves near-optimal regret bounds for both settings. For the observe-then-decide regime, we prove that the expected regret against the dynamic clairvoyant optimal policy is bounded by $\tilde O(ρ^{-1}{H^{3/2}}S\sqrt{AT})$ where $ρ\in(0,1)$ is the budget parameter, $H$ is the length of the horizon, $S$ and $A$ are the numbers of states and actions, and $T$ is the number of episodes. For the decide-then-observe regime, we show that the regret against the static optimal policy that has access to the mean reward and mean resource consumption functions is bounded by $\tilde O(ρ^{-1}{H^{3/2}}S\sqrt{AT})$ with high probability. We test the numerical efficiency of our method for a variant of the resource-constrained inventory management problem.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Online Stochastic Optimization with Wasserstein-Based NonstationarityManagement Science, 2025
- Bandits atop Reinforcement Learning: Tackling Online Inventory Models with Cyclic DemandsManagement Science, 2023
- The Best of Many Worlds: Dual Mirror Descent for Online Allocation ProblemsOperations Research, 2023
- Learning in Repeated Auctions with Budgets: Regret Minimization and EquilibriumManagement Science, 2019
- How the Experts Algorithm Can Help Solve LPs OnlineMathematics of Operations Research, 2016
- Introduction to Online Convex OptimizationFoundations and Trends® in Optimization, 2016
- A Dynamic Near-Optimal Algorithm for Online Linear ProgrammingOperations Research, 2014
- Real-Time Optimization of Personalized AssortmentsManagement Science, 2014
- AdWords and generalized online matchingJournal of the ACM, 2007
- The Passenger-Mix Problem in the Scheduled AirlinesInterfaces, 1982