Value Function

• $v_{\pi }(s)=E_{\pi }[G_t|S_t=s]$
• $v_{\pi }(s)=E_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]$
• $v_{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma E_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]]$
• $v_{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$

Action-Value Function

• $q_{\pi }(s,a)=E_{\pi }[G_t|S_t=s,A_t=a]$

Optimal Value Function

• $v_{\ast }(s)=ma{x}_a{q}_{{\pi }_{\ast }}(s,a)$
• $v_{\ast }(s)=ma{x}_a{E}_{{\pi }_{\ast }}[G_t|S_t=s,A_t=a]$
• $v_{\ast }(s)=ma{x}_a{E}_{{\pi }_{\ast }}[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]$
• $v_{\ast }(s)=ma{x}_{a}E[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a]$
• $v_{\ast }(s)=ma{x}_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]$

Optimal Action-Value Function

• $q_{\ast }(s,a)=E[R_{t+1}+\gamma ma{x}_{a^{\prime }}{q}_{\ast }(S_{t+1},a^{\prime })|S_t=s,A_t=a]$
• $q_{\ast }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma ma{x}_{a^{\prime }}{q}_{\ast }(s^{\prime },a^{\prime })]$

Policy Evalution

• TODO

Finding New Greedy Policy

• ${\pi }^{\prime }(s)=argma{x}_a{q}_{\pi }(s,a)$
• ${\pi }^{\prime }(s)=argma{x}_{a}E[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s,A_t=a]$
• ${\pi }^{\prime }(s)=argma{x}_a{\sum }_{s^{\prime },r}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$

Policy Iteration

• ${\pi }_0-E->v_{{\pi }_0}-I->{\pi }_1-E->v_{{\pi }_1}-I->{\pi }_2-E->...-I->{\pi }_{\ast }-E->v_{\ast }$

Value Iteration

• policy evaluation is stopped after just one sweep (one update of each state).
• $v_{k+1}(s)=ma{x}_{a}E[R_{t+1}+\gamma v_k(S_{t+1})|S_t=s,A_t=a]$
• $v_{k+1}(s)=ma{x}_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_k(s^{\prime })]$

Asynchronous Dynamic Programming

are in-place iterative DP algorithms that do not sweep through entire state set. examples include:

• update the value of ONLY one state at each value iteration update

Generalized Policy Iteration (GPI)

policy iteration:

• policy evaluation (PE)
• policy improvement (PI)

GPI refer to the general of letting PE and PI interact

GPI is the family that consist of value iteration and asynchronous dynamic programming