Subprocess-Constrained Markov Decision Processes
Using the full decision history enables a polynomial-time solution with explicit reward and constraint-error guarantees.
Jiarui Gan and Debmalya Mandal study policies whose expected discounted future cost must meet a state-specific bound after every reachable history. They show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. Their algorithm implicitly represents a history-dependent policy with expected reward within ε of the optimal feasible value and each cost-bound violation at most δ. It also computes the policy’s action distribution in polynomial time for any given history.
ArXiv · AI/CL/LG's note
Jiarui Gan and Debmalya Mandal study policies whose expected discounted future cost must meet a state-specific bound after every reachable history. They show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. Their algorithm implicitly represents a history-dependent policy with expected reward within ε of the optimal feasible value and each cost-bound violation at most δ. It also computes the policy’s action distribution in polynomial time for any given history.
ArXiv · AI/CL/LG's note
score 5