Online Resource Allocation in Episodic Markov Decision Processes

Understand

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.