policy iteration will allow us to get an optimal policy.

1. start with some initial policy \(\pi\) (this scheme converges to an optimal policy regardless of where you start)
2. solve for \(U^{\pi}\)
3. create a new policy \(\pi’\) by creating a value-function policy on \(U^{\pi}\)
4. repeat 2-3

Since there are a finite policies, this will eventually converge.

At each point, the utility of the policy increases.

At each step, the utility of the resulting policy will necessarily be larger or equal to than the previous one as we are greedily choosing “better” (or equivalent) actions as measured by the utility of the previous policy.

Policy Optimization deals with algorithms that, unlike value iteration/policy iteration/online planning which uses a surrogate (like value function or some future discounted reward) to calculate a policy, directly optimizes against policy parameters \(\theta\) for a policy \(\pi_{\theta}\).

• Local Policy Search (aka Hooke-Jeeves Policy Search)
• Genetic Policy Search
• Cross Entropy Method
• Policy Gradient, Regression Gradient and Likelyhood Ratio Gradient
• Reward-to-Go

A polynomial is a polynomial

constituents

• a function \(p: \mathbb{F} \to \mathbb{F}\)
• coefficient \(a_0, \dots, a_{m} \in \mathbb{F}\)

requirements

A polynomial is defined by:

\begin{equation} p(z)=a_0+a_1z+a_2z^{2}+\dots +a_{m}z^{m} \end{equation}

for all \(z \in \mathbb{F}\)

additional information

degree of a polynomial \(\deg p\)

A polynomial’s degree is the value of the highest non-zero exponent. That is, for a polynomial:

\begin{equation} p(z) = a_0+a_1z+\dots +a_{m}z^{m} \end{equation}

with \(a_{m} \neq 0\), the degree of it is \(m\). We write \(\deg p = m\).

\begin{equation} \text{PH} = \bigcup_{c \in \mathbb{N}} \Sigma_{c} = \bigcup_{c \in \mathbb{N}} \pi_{c} \end{equation}

“a language is in the polynomial hierarchy if it can be described with a constant number of qualifiers”

results and conjectures

polynomial hierarchy conjecture

“the polynomial hierarchy is infinite”—that is, each arrow to a harder language is strict.

\(P \neq NP\), \(NP \neq \pi_{2}\)

PSPACE bounds the entire hierarchy

\(\text{PH} \subseteq \text{PSPACE}\)

because for every \(\exists\) you only have to keep one of it around.