A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations.
Balázs GerencsérRomain HollandersJean-Charles DelvenneRaphaël M. JungersPublished in: J. Discrete Algorithms (2017)
Keyphrases
- complexity analysis
- policy iteration
- markov decision processes
- fixed point
- model free
- reinforcement learning
- optimal policy
- sample path
- theoretical analysis
- least squares
- lower bound
- temporal difference
- policy evaluation
- markov decision process
- average reward
- computational complexity
- linear programming
- infinite horizon
- dynamic programming
- markov decision problems
- state space
- finite state
- average cost
- optimal control
- long run
- convergence rate
- pairwise
- natural language