The complexity of Policy Iteration is exponential for discounted Markov Decision Processes.
Romain HollandersJean-Charles DelvenneRaphaël M. JungersPublished in: CDC (2012)
Keyphrases
- markov decision processes
- policy iteration
- optimal policy
- average reward
- sample path
- finite state
- state space
- reinforcement learning
- infinite horizon
- discount factor
- dynamic programming
- finite horizon
- discounted reward
- approximate dynamic programming
- partially observable
- reinforcement learning algorithms
- transition matrices
- average cost
- planning under uncertainty
- markov decision problems
- policy evaluation
- actor critic
- factored mdps
- markov decision process
- action space
- decision problems
- reward function
- policy iteration algorithm
- state and action spaces
- decision processes
- optimal solution