On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization

@misc{chen2026exact,
  title = {{On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization}},
  author = {Jia-Yu Chen and Hsin-Yuan Huang and Tzu-Yang Teng and Yun-Jen Tsai and Hao-Hsiang Wu},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01863},
  eprint = {2611.01863},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01863},
}

TY  - UNPB
TI  - On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
AU  - Jia-Yu Chen
AU  - Hsin-Yuan Huang
AU  - Tzu-Yang Teng
AU  - Yun-Jen Tsai
AU  - Hao-Hsiang Wu
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01863
UR  - https://arxiv.org/abs/2611.01863
AB  - We study exact mixed-integer reformulations of a finite horizon Markov decision process (MDP) with transition revenues defined by local submodular revenue maximization problems. We start with the dual linear programming formulation of the MDP, where local optimal revenues appear in the objective function and the constraints describe the state probabilities from the initial state. We combine the dual formulation with the binary variables of the local problems and obtain an exact mixed-integer nonlinear formulation with bilinear terms. We use the submodular inequalities and an exact McCormick linearization to obtain an equivalent mixed-integer linear formulation. We also use the dual structure to conduct a sensitivity analysis of the MDP optimal value with respect to changes in the local revenue coefficients. Based on local incumbent revenues and upper bounds, this sensitivity analysis evaluates the effect of local optimality gaps on the global MDP optimality gap, without solving every local revenue maximization problem to optimality.
ER  -