Megadose The AI curve, compressed.

Subprocess-Constrained Markov Decision Processes

· ArXiv · AI/CL/LG ·
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

score 5

Categories: Research