Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming.
Eugene A. FeinbergJefferson HuangBruno ScherrerPublished in: Oper. Res. Lett. (2014)
Keyphrases
- policy iteration
- markov decision processes
- dynamic programming
- infinite horizon
- optimal policy
- sample path
- average reward
- model free
- state space
- optimal control
- minimum cost flow
- least squares
- fixed point
- reinforcement learning
- strongly polynomial
- markov decision problems
- long run
- special case
- computational complexity
- temporal difference
- linear programming
- discounted reward