On the Complexity of Value Iteration
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal $n$-step payoff by iterating $n$ times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon $n$. In this paper, we settle the computational complexity of value iteration. We show that, given a horizon $n$ in binary and an MDP, computing an optimal policy is EXP-complete, thus resolving an open problem that goes back to the seminal 1987 paper on the complexity of MDPs by Papadimitriou and Tsitsiklis. As a stepping stone, we show that it is EXP-complete to compute the $n$-fold iteration (with $n$ in binary) of a function given by a straight-line program over the integers with $\max$ and $+$ as operators.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Phase retrieval with complexity guidance
Iterative phase retrieval methods based on the Gerchberg-Saxton (GS) or Fienup algorithm require a large number of iterations to converge to a meaningful solution. For complex-valued or phase objects, these approaches al…
RetrievalValue Mirror Descent for Reinforcement Learning
Value iteration-type methods have been extensively studied for computing a nearly optimal value function in reinforcement learning (RL). Under a generative sampling model, these methods can achieve sharper sample complex…
Reinforcement LearningFitted Value Iteration Methods for Bicausal Optimal Transport
We develop a fitted value iteration (FVI) method to compute bicausal optimal transport (OT) where couplings have an adapted structure. Based on the dynamic programming formulation, FVI adopts a function class to approxim…
Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We formulate the value function estimation procedure in value iteration as an…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Value Iteration in Continuous Actions, States and Time
Classical value iteration approaches are not applicable to environments with continuous states and actions. For such environments, the states and actions are usually discretized, which leads to an exponential increase in…
Deep Reinforcement Learning