SSP requires Omega(S A B_star^3 / (c_min epsilon^2)) samples in the worst case, with matching upper bounds that hold even for c_min=0 under bounded optimal hitting time.
Randomized linear programming solves the discounted markov decision problem in nearly-linear running time
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality and binary-tree data structures, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an $\epsilon$-optimal policy using nearly-linear run time in the worst case. When the Markov decision process is ergodic and specified in some special data formats, the algorithm finds an $\epsilon$-optimal policy using run time linear in the total number of state-action pairs, which is sublinear in the input size. These results provide a new venue and complexity benchmarks for solving stochastic dynamic programs.
years
2026 2verdicts
UNVERDICTED 2representative citing papers
Faster deterministic and randomized algorithms for exact DMDP optimization via reductions to policy evaluation and approximate solving.
citing papers explorer
-
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
SSP requires Omega(S A B_star^3 / (c_min epsilon^2)) samples in the worst case, with matching upper bounds that hold even for c_min=0 under bounded optimal hitting time.
-
Randomization for Faster Exact Optimization of Discounted Markov Decision Processes
Faster deterministic and randomized algorithms for exact DMDP optimization via reductions to policy evaluation and approximate solving.