Policy iteration

Policy iteration

Amir (guest) 22 Jun 2019 12:48

Hi,
In lecture 4 - slide 57 it is said that policy iteration takes O(|A|*|S|^2 + |S|^3).
Can you please explain why that is the case? what is the step that take |A|*|S|^2 and what is the part that takes |S|^3?

Thanks!

Re: Policy iteration

Lee Cohen 24 Jun 2019 18:04

Each iteration of the policy iteration has three parts:
1. (explicit) Policy Evaluation of $V^{\pi_k}$ by using the formula $V^{\pi_k}=(I-\gamma P^{\pi_k})^{-1}r^{\pi_k}$
- where the main component here is to calculate the inverse which takes $O(|S|^3)$ for a $|S|\times|S|$ matrix (e.g. by Gauss–Jordan elimination).
2. Policy Improvement: per each state s ($|S|$),
- we evaluate $\pi_{k+1}(s)$ by choosing the action ($|A|$) the maximizes the bellman equation with $V^{\pi_k}$, which requires to go through every next state s' ($|S|$).
- overall $O(|A||S|^2)$.
3. comparing $V^{\pi_k}$ to $V^{\pi_k}$ (and stop if they're equal)- which takes $O(|S|)$