Some Upper Bounds on the Running Time of Policy Iteration on Deterministic MDPs.
Ritesh GoenkaEashan GuptaSushil KhyaliaPratyush AgarwalMulinti Shaik WajidShivaram KalyanakrishnanPublished in: CoRR (2022)
Keyphrases
- policy iteration
- upper bound
- markov decision processes
- lower bound
- optimal policy
- model free
- reinforcement learning
- finite state
- fixed point
- markov decision process
- markov decision problems
- least squares
- sample path
- factored mdps
- average reward
- policy evaluation
- infinite horizon
- state space
- approximate dynamic programming
- temporal difference
- transition matrices
- linear programming
- dynamic programming
- average cost
- finite horizon
- reinforcement learning algorithms
- convergence rate
- cost function
- action space
- sample size
- partially observable
- long run
- optimal control
- decision problems
- discounted reward
- approximate policy iteration