mlsanityData to 14 Oct 2026

Online Resource Allocation in Episodic Markov Decision Processes

arXiv 2305.10744 ↗First posted 18 May 2023cs.DS cs.LG math.OCcited by 1

Not on the map. Why?

Abstract (arXiv)

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(ρ-1H3/2S√AT) where ρ∈(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(ρ-1H3/2S√AT) with high probability. We test the numerical efficiency of our method for a variant of the resource-constrained inventory management problem.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 29 of its 56 references that are in the map. First posted on arXiv 18 May 2023.

Builds on

29 of 56 references.

References · 29

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2020Exploration-Exploitation in Constrained MDPscited by 149
  3. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  4. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  5. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  6. 2020The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problemscited by 58
  7. 2020Dual Mirror Descent for Online Allocation Problemscited by 52
  8. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  9. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  10. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  11. 2014Fast Algorithms for Online Stochastic Convex Programmingcited by 36
  12. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
17 more
  1. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  2. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  3. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  4. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  5. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  6. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  7. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  8. 2020Simple and Fast Algorithm for Binary Integer and Online Linear Programmingcited by 27
  9. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  10. 2020Online Stochastic Optimization with Wasserstein Based Non-stationaritycited by 25
  11. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  12. 2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18
  13. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
  14. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  15. 2014How the Experts Algorithm Can Help Solve LPs Onlinecited by 11
  16. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
  17. 2019Large Scale Markov Decision Processes with Changing Rewardscited by 7

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcited by 1