The paper proposes Maturing Markov Decision Processes (MMDPs) built on information-action asymmetry, an expiring-action priority principle, and a structure-aware RL framework, with experiments showing efficiency gains on replenishment, cash management, and production tasks.
Maximum Weight Online Matching with Deadlines
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study the problem of matching agents who arrive at a marketplace over time and leave after d time periods. Agents can only be matched while they are present in the marketplace. Each pair of agents can yield a different match value, and the planner's goal is to maximize the total value over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. We provide a randomized 0.25-competitive algorithm building on a result by Feldman et al. (2009) and Lehman et al. (2006). We extend the model to the case in which departure times are drawn independently from a distribution with non-decreasing hazard rate, for which we establish a 1/8-competitive algorithm. When the arrival order is chosen uniformly at random, we show that a batching algorithm, which computes a maximum-weighted matching every (d+1) periods, is 0.279-competitive.
fields
cs.LG 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Maturing Markov Decision Processes: Decision Making under Increasing Information and Shrinking Action Sets
The paper proposes Maturing Markov Decision Processes (MMDPs) built on information-action asymmetry, an expiring-action priority principle, and a structure-aware RL framework, with experiments showing efficiency gains on replenishment, cash management, and production tasks.