Reinforcement Learning | Introduction and Model-Based Control

111學年第二學期選修交大資工所謝秉均老師開設之強化學習原理。

因為觀念複雜且不容易消化，所以決定在每次上完課之後，好好把課堂學到的東西整理成筆記，內化成自己的。
(希望我能堅持下去QQ)

另外我在上這堂課的同時，也有看 Stanford 的線上 RL 課程，所以筆記可能也會稍微整合一些些 Stanford 線上課的內容。

Reinforcement Learning | Stanford Online:
https://www.youtube.com/watch?v=FgzM3zpZ55o&list=PLoROMvodv4rOSOPzutgyCTapiGlY2Nd8u&index=1

Introduction

Overview

我們可以用一句話簡述強化學習 (Reinforcement Learning)：
Learn to take a sequences of actions to achieve a specific goal in an unknown environment.

• Learn: 表示我們事先不知道環境是如何活動的
• Sequence of actions: 表示和環境多次的互動
• Goal: 例如獲得高 reward

RL 的四個重點議題，也讓 RL 和其他機器學習方法有所分別：

• Optimization: Agent 需要最佳化自己的 action 來獲得最大的 reward
• Exploration: 透過與環境互動來嘗試不同的決定並學習，但可能會面臨 exploration 與 exploitation 兩者的 trade off
• Delayed consequences: 某個決定可能之後才有影響
• Generalization: Agent 是否能判斷某個 action 在之前沒經歷過的 state 下的好壞？

比較：
Supervised Learning: Optimization, Generalization
Imitation Learning: Optimization, Generalization, Delayed consequences

Sequential Decision Making

Agent 和 Environment 的互動可以用下圖來表示：

另一種 trajectory 的註記方式為：

$s_0,a_0,r_0,s_1,...$ ，兩個都可以

在 agent 和 environment 的交互之下，一個 agent 會採取一連串的 actions

$\{a_t\}$，並觀察到一連串的 states

$\{s_t\}$ 以及獲得一連串的 rewards

$\{r_t\}$。

一個 RL agent 常包含以下要素：

1. Model: 描述環境會如何針對 agent 的行為而改變
   包含 transition model，是所有 states 的集合

   $S$ 的機率分布：
   
   $$P(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$$
   以及 reward model：
   
   $$r(s_t=s,a_t=a)=\mathbb{E}[r_t|s_t=s,a_t=a]$$

2. Policy: 從 states 映射到 actions 的函數，決定 agent 會如何採取的 action
   可以是 deterministic 的：
   

   $$\pi (s)=a$$
   也可以是 stochastic 的：
   
   $$\pi (a|s)=P(a_t=a|s_t=s)$$

3. Value function: 當遵從某個 policy 時，在特定 state 或 action 之下可以獲得的 future rewards，定義為：
   

   $$V^{\pi }(s_t=s)={\mathbb{E}}_{\pi }[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...|s_t=s]$$

以上三點更詳細的概念會在後續陸續提到。

根據是否有明確的 model，RL algorithm 可以被分為以下兩種：

• Model-based
• Model-free

下圖分類了各種不同的 RL agents：

Markov Decision Process

建構環境 (Model the environment) 的方法有很多種，其中最基礎且重要的方法是 Markov Decision Process (MDP)。

Markov chain

Markov chain 是一種隨機過程，我們可以用經典的 Mars Rover Problem 作為例子：

一個抽樣的 trajectory 記作

$s_0,s_1,s_2,...,s_t,s_{t+1},...$，例如

$x_3,x_4,x_5,x_4,x_5,...$，而箭頭上的數值代表 transition probability，例如

$P(s_{t+1}=x_2|s_t=x_1)=0.5$

Markov chain 符合 Markov property，意即給定當前的 state ，則未來和過去的狀態無關。

Markov Property
A state

$s_t$ is Markov if and only if

$$P(s_{t+1}|s_t)=P(s_{t+1}|s_1,...,s_t)$$

Markov Chain
A Markov chain

$(S,P)$ is specified by:

1. State space
   $S$: a (finite) set of possible states.
2. Transition matrix
   $P=[P_{s{s}^{\prime }}]$ with elements
   $P_{s{s}^{\prime }}=P(s_{t+1}=s^{\prime }|s_t=s)$

$P$ 是一個

$|S|\times |S|$ 的矩陣，即

$$P=\left[\begin{array}{cccc}{P}_{11}& P_{12}& ...& P_{1n}\\ P_{21}& P_{22}& ...& P_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ P_{n1}& P_{n2}& ...& P_{nn}\end{array}\right]$$
其中

$P_{ij}=P(s_{t+1=j}|s_{t=i})$

$P$ 具有兩個性質：

1. 每個 entry 都是非負的
   這是因為每個 entry 都是一個機率值，不會出現負數
2. Row sum = 1
   例如：
   $P$ 的第一行是由
   $s_1$ 轉換到
   $s_1,...,s_n$ 的機率，故全部的值相加會等於
   $1$

Markov Reward Process

在 Markov chain 的基礎上，加上 reward function，則我們可以定義 Markov Reward Process：

Markov Reward Process
An MRP

$(S,P,R,\gamma )$ is specified by
Underlying dynamics:

1. State space
   $S$
2. Transition matrix
   $P=[P_{s{s}^{\prime }}]$ with
   $P_{s{s}^{\prime }}=P(s_{t+1}=s^{\prime }|s_t=s)$

Task:

3. Reward function
   $R_s=\mathbb{E}[r_{t+1}|s_t=s]$
4. Discount factor
   $\gamma \in [0,1]$

Markov Reward Process 用於描述一個在不同狀態之間轉換的系統，其中每個狀態都有一個與之相關聯的即時 reward，並且轉換的過程滿足 Markov Property。

Return

$G_t$ is the cumulative discounted rewards over a single trajectory from

$t$ onward (random).

$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{r}_{t+k+1}$$

State-value function

$V(s)$ is the expected return if state

$s$ is the starting state.

$$\begin{array}{rl}V(s)& =\mathbb{E}[G_t|s_t=s]\\ & =\mathbb{E}[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...|s_t=s]\end{array}$$

Return 的計算十分簡單。同樣再以 Mars Rover Problem 作為例子，令在

$x_1$ 的 reward

$R_1=0.05$，

$R_6=1$，其他為

$0$。令

$\gamma =0.9$，對於 episode

$x_5,x_6,x_6,x_5,x_4$，return 為：

$$G_t=0+(1\times 0.9)+(1\times {0.9}^2)+(0\times {0.9}^3)+(0\times {0.9}^4)$$

而 state-value function

$V(s)$ 該如何計算呢？

因為

$V(s)$ 是

$G_t$ 的期望值，一個非常直觀的方法是使用暴力解，只要我們抽樣夠多的 trajectories，則它們

$G_t$ 的平均即是

$V(s)$。

另一種較常見的方法是使用 dynamic programming：

$$\begin{array}{rl}V(s)& =\mathbb{E}[G_t|s_t=s]\\ & =\mathbb{E}[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...|s_t=s]\\ & =\mathbb{E}[r_{t+1}+\gamma G_{t+1}|s_t=s]\\ & =\mathbb{E}[r_{t+1}|s_t=s]+\gamma \mathbb{E}[G_{t+1}|s_t=s]\\ & =R_s+\gamma \sum _{s^{\prime }}P(s^{\prime }|s_t=s)\mathbb{E}[G_{t+1}|s_t=s,s_{t+1}=s^{\prime }]\\ & =R_s+\gamma \sum _{s^{\prime }}P(s^{\prime }|s_t=s)\mathbb{E}[G_{t+1}|s_{t+1}=s^{\prime }]\\ & =R_s+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}V(s^{\prime })\end{array}$$

$\mathbb{E}[G_{t+1}|s_t=s,s_{t+1}=s^{\prime }]=V(s^{\prime })$ 是因為符合 Markov Property

由此我們導出在 MRP 使用的 Bellman Expectation Equation：

Bellman Expectation Equation for MRP

$$V(s)=R_s+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}V(s^{\prime })$$

Bellman Expectation Equation 寫成矩陣型式：

$$\begin{gathered} V=R+\gamma PV \\ =>\left[\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_n)\end{array}\right]=\left[\begin{array}{c}{R}_1\\ R_2\\ ⋮\\ R_n\end{array}\right]+\gamma \left[\begin{array}{cccc}{P}_{11}& P_{12}& ...& P_{1n}\\ P_{21}& P_{22}& ...& P_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ P_{n1}& P_{n2}& ...& P_{nn}\end{array}\right]\left[\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_n)\end{array}\right] \end{gathered}$$

因為

$V=R+\gamma PV$，經由推導我們可得

$V=(I-\gamma P{)}^{-1}R$，得到

$V$ 之解。

然而若直接計算反矩陣來得到解，計算的時間複雜度為

$O(n^3)$，非常沒有效率，故我們需要其他的解法，這會在之後的內容中介紹。

---

在 MRP 中我們還使用到了 discount factor

$\gamma$。直觀而言，我們較不在乎離當前時間越遠的未來，故 future reward 會乘上

$\gamma$；數學上，有了 discount factor，可以避免 return 無法收斂。

$\gamma$ 的選擇：

• Continuing environment: 固定的
  $\gamma <1$
• Episodic environment:
  $\gamma \le 1$

Markov Decision Process

在 Markov Reward Process 的基礎上，加上各種可能的 actions ，則我們可以定義 Markov Decision Process：

Markov Decision Process
An MDP

$(S,A,P,R,\gamma )$ is specified by
Underlying dynamics:

1. State space
   $S$
2. Action space
   $A$
3. Transition matrix
   $P=[P_{s{s}^{\prime }}^a]$ with
   $P_{s{s}^{\prime }}^a=P(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$

Task:

3. Reward function
   $R_s^a=\mathbb{E}[r_{t+1}|s_t=s,a_t=a]$
4. Discount factor
   $\gamma \in [0,1]$

MDP 描述一個由狀態、行動、獎勵和轉移概率所構成的決策過程

有了 states 和 actions 後，我們便能夠定義 policy：

A (randomized) policy

$\pi$ is a conditional distribution over possible actions given state

$s$, i.e., for any

$s\in S$,

$a\in A$,

$$\pi (a|s):=P(a_t=a|s_t=s)$$

因為我們已經假設整個過程符合 Markov Property，故這裡我們專注於討論 stationary policy，意指

$\pi$ 和時間沒有關係。

對於一個 MDP，如果我們固定 policy

$\pi (a|s)$，則：

$$P_{s{s}^{\prime }}^{\pi }=\sum _{a\in A}\pi (a|s)P_{s{s}^{\prime }}^a$$

此固定 policy 之下由

$s\to s^{\prime }$ 的機率 =

$\sum _{a\in A}$ (此 policy 下在

$s$ 下採取

$a$ 的機率) X (採取

$a$ 時

$s\to s^{\prime }$ 的機率)

$$R_s^{\pi }=\sum _{a\in A}\pi (a|s)R_s^a$$

此固定 policy 之下

$s$ 作為起點的 reward =

$\sum _{a\in A}$ (此 policy 下在

$s$ 下採取

$a$ 的機率) X (採取

$a$ 時

$s$ 作為起點的 reward)

綜合以上兩點，我們可以發現對於一個 MDP，如果我們固定 policy

$\pi (a|s)$，則我們可以得到

$\pi$-induced MRP

$(S,P^{\pi },R^{\pi },\gamma )$

多了 actions 之後，我們便可以定義 MDP 的 return 和 state-value function：

Return

$G_t$ is the cumulative discounted rewards over a single trajectory from

$t$ onward (random).

$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^{k}r(s_{t+k+1},a_{t+k+1})$$

State-value function

$V^{\pi }(s)$ is the expected return if state

$s$ is the starting state.

$$V^{\pi }(s)=\mathbb{E}[G_t|s_t=s;\pi ]$$

值得注意的是，

$V^{\pi }(s)$ 具有隨機性，來源包含：

1. Reward
2. State transition
3. Policy

Model-Based Evaluation and Control

MDP Policy Evaluation

我們該如何評價一個 policy 的好壞呢？

在此需要先介紹新的定義：

Action-value function

$Q^{\pi }(s,a)$ is the expected return if we start from state

$s$ and take action

$a$, and then follow the original policy

$\pi$.

$$Q^{\pi }(s,a)=\mathbb{E}[G_t|s_t=s,a_t=a;\pi ]$$

$V^{\pi }(s)$ 和

$Q^{\pi }(s,a)$ 是具有關聯性的，可以互相以對方表示，也可以寫成遞迴式：

Bellman Expectation Equations:

• $V$ written in
  $Q$:
  
  $$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a)$$
• $Q$ written in
  $V$:
  
  $$Q^{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\pi }(s^{\prime })$$
• $V$ written in
  $V$:
  
  $$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)[R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\pi }(s^{\prime })]$$
• $Q$ written in
  $Q$:
  
  $$Q^{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a[\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })]$$

因為

$V^{\pi }$ 可以寫成自己的遞迴式，因此給定一個 policy

$\pi$，我們可以找出

$V^{\pi }$ 的值，此即為 policy evaluation。

兩種 policy evaluation 的方法：

1. Non-iterative policy evaluation
   Matrx form:
   
   $$\begin{array}{rl}& V^{\pi }=R^{\pi }+\gamma P^{\pi }{V}^{\pi }\\ =>& V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{R}^{\pi }\end{array}$$
2. Iterative policy evaluation

Iterative MDP Policy Evaluation (IPE)
For a fixed policy

$\pi$:
Initialize

$V_0^{\pi }(s)=0$ for all

$s$
For

$k=1,2,...$
 for all

$s$
  

$V_k^{\pi }(s)=\sum _{a\in A}\pi (a|s)[R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{k-1}^{\pi }(s^{\prime })]$

代入

$V_0^{\pi }(s)$ 可以得到

$V_1^{\pi }(s)$，代入

$V_1^{\pi }(s)$ 可以得到

$V_2^{\pi }(s)$，迭代直到 converge。

如果初始值

$V_0^{\pi }(s)=V^{\pi }(s)$，則一次迴圈就收斂啦

---

我們可能會好奇，利用 IPE 計算是否真的能夠使

$V_k^{\pi }(s)$ 收斂至

$V^{\pi }(s)$？

考慮一個 matrix vector space

$V_0^{\pi }(s),V_1^{\pi }(s),...,V_k^{\pi }(s)\in {\mathbb{R}}^{|S|}$，我們可以透過證明以下兩步驟來證明 IPE 會使

$V_k^{\pi }(s)$ converge：

1. IPE is an contraction operator.
2. Under any contraction operator, the points converge to a fixed point.

定義 IPE Operator：

IPE Operator (also called Bellman Expectation Backup Operator)

$$T^{\pi }(V):=R^{\pi }+\gamma P^{\pi }V$$

我們使用

$L_{\mathrm{\infty }}$-norm 來衡量兩個 value function

$V,V^{\prime }$ 之間的距離：

$$||V-V^{\prime }|{|}_{\mathrm{\infty }}:=ma{x}_{s\in S}|V(s)-V(s^{\prime })|$$

IPE is an contraction operator.
proof:

$$\begin{array}{rl}||T^{\pi }(V)-T^{\pi }(V^{\prime })|{|}_{\mathrm{\infty }}& =||(R^{\pi }+\gamma P^{\pi }V)-(R^{\pi }+\gamma P^{\pi }{V}^{\prime })|{|}_{\mathrm{\infty }}\\ & =\gamma ||P^{\pi }(V-V^{\prime })|{|}_{\mathrm{\infty }}\\ & \le \gamma ||V-V^{\prime }|{|}_{\mathrm{\infty }}\end{array}$$

第二行至第三行不等式成立是因為

$P^{\pi }$ 的每個 entry 都

$\le 1$

我們稱

$T^{\pi }$ 為

$\gamma$-contraction operator。

Under any contraction operator, the points converge to a fixed point.
上述可以根據 Banach Fixed-Point Theorem 得證：

Banach Fixed-Point Theorem
For any non-empty complete metric space, if

$T$ is a

$\gamma$-contraction operator, then

$T$ has a unique fixed point.

Complete: 表示極限 (limit) 是在 space 裡面

Summary:
Under IPE, the value function

$V_k^{\pi }$ converges to the correct

$V^{\pi }$, for any initialization

$V_0^{\pi }$.

Finding Optimal Policy

我們知道如何進行 policy evaluation 了，根據計算出來的評價，以下討論如何去找到最佳的 (optimal) policy。

定義：

Optimal State-Value Function

$$V^{\ast }(s)=\underset{\pi }{max}{V}^{\pi }(s)$$

對任意 state

$s$ 遵循最佳 policy 所能得到的 expected return

Optimal Action-Value Function

$$Q^{\ast }(s,a)=\underset{\pi }{max}{Q}^{\pi }(s,a)$$

對任意 state

$s$ 執行

$a$ 後再遵循最佳 policy 繼續執行所能得到的 expected return

什麼條件下才能說一個 policy 比另一個更好呢？

Partial Ordering of Policies

$$\pi \ge {\pi }^{\prime }\mathrm{i}\mathrm{f}{\mathrm{V}}^{\pi }(\mathrm{s})\ge {\mathrm{V}}^{{\pi }^{\prime }}(\mathrm{s}),\mathrm{\forall }\mathrm{s}$$

注意！一定要對每個狀態都成立

Optimal Policy
A policy

${\pi }^{\ast }$ is an optimal policy if it is better than or equal to all other policies, i.e.

$${\pi }^{\ast }\ge \pi ,\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\pi$$

${\pi }^{\ast }$ 無論如何都會存在嗎？

Theorem (Existence of Optimal Policy)
For any finite MDP, there always exists an optimal policy

${\pi }^{\ast }$ s.t.

$${\pi }^{\ast }\ge \pi ,\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\pi$$

---

Optimal policy 存在，但該如何找到？

當我們計算出了每個狀態下的最佳 action-value function

$Q^{\ast }(s,a)$ 時，我們便可以依此找出最優策略：

$${\pi }^{\ast }(a|s)=\arg \underset{a\in A}{max}{Q}^{\ast }(s,a)$$
也就是說對於每一個狀態

$s$，我們都能夠確定最佳的動作

$a$（即最大化

$Q^{\ast }(s,a)$ 的動作) ，從而找到對應的 optimal policy。

因此，計算出

$Q^{\ast }(s,a)$ 等同於找到 optimal policy。

接下來將討論如何找到

$Q^{\ast }(s,a)$。

定義：

Bellman Optimality Equations:

• $V^{\ast }$ written in
  $Q^{\ast }$:
  
  $$V^{\ast }(s)=\underset{a}{max}{Q}^{\ast }(s,a)$$
• $Q^{\ast }$ written in
  $V^{\ast }$:
  
  $$Q^{\ast }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })$$
• $V^{\ast }$ written in
  $V^{\ast }$:
  
  $$V^{\ast }(s)=\underset{a}{max}[R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })]$$
• $Q^{\ast }$ written in
  $Q^{\ast }$:
  
  $$Q^{\ast }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a(\underset{a}{max}{Q}^{\ast }(s^{\prime },a))$$

Bellman Optimality Equations 因為需要取最大值，無法像 Bellman Expectation Equations 一樣使用線性代數解得答案。以下為兩種 iterative 的求解方法：

1. Value Iteration
2. Policy Iteration

Value Iteration

我們知道 Bellman Optimality Equation：

$$V^{\ast }(s)=\underset{a}{max}[R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })]$$
因此我們可以透過 Bellman Optimality Equation 定義 Bellman Optimality Operator：

Bellman Optimality Operator

$$T^{\ast }(V)=\underset{a\in A}{max}(R^a+\gamma P^{a}V)$$

利用 Bellman Optimality Operator 進行 Value Iteration：

Value Iteration
Initialize

$k=0$ and set

$V_0(s)=0$ for all

$s$
Repeat until convergence:

$V_{k+1}\leftarrow T^{\ast }(V_k)$

計算

$V_{k+1}=T^{\ast }(V_k)$ 等同於計算：

for each

$s$
 

$V_{k+1}(s)=\underset{a}{max}[R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_k(s^{\prime })]=\underset{a}{max}{Q}_k(s,a)$

$\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })$ 需花

$O(|S|)$，找所有 action 中的 max 花

$O(|A|)$，而每步驟要對所有 states 計算花

$O(|S|)$，故 value iteration 的時間複雜度為

$O(|S{|}^2|A|)$。

值得注意的是，在未收斂之前，我們在迭代的過程中計算出的 intermediate value function

$V_k$ 可能不能對應到任何特定的 policy。

當我們找到

$V^{\ast }$ 之後，便可以透過 greedy policy 來找到最佳 policy。對於所有

$s$，選擇一個 action

$a$，使得

$Q^{\ast }(s,a)=r+\gamma V^{\ast }(s^{\prime })$ 最大化，即

$${\pi }^{\ast }(s)=\arg \underset{a}{max}{Q}^{\ast }(s,a)=\arg \underset{a}{max}(R(s,a)+\gamma \sum s^{\prime }P(s^{\prime }|s,a)V^{\ast }(s^{\prime }))$$

此 policy 即為 optimal policy。

---

Value Iteration 並不是很好理解，我們用馬力歐找寶藏的遊戲作為例子來解釋 Value Iteration 整個過程：

• States: 馬力歐的位置，在九宮格上共 9 種可能
• Actions: 上下左右，若有寶箱可拿寶箱
• Reward:
  • 馬力歐拿到寶箱，
    $R_s^a=0$
  • 馬力歐朝任一方向移動，
    $R_s^a=-1$
• 假設
  $\gamma =1$，且除非撞到牆壁，否則
  $P_{s{s}^{\prime }}^a=1$

假設座標由右至左、由上至下標註，寶箱在 (2, 3)。每一次迭代中，對於每個 state，我們都根據 Bellman optimality equation 計算它們的下一步 value，即計算

$$V_{k+1}(s)=\underset{a}{max}[R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_k^{\ast }(s^{\prime })]=\underset{a}{max}{Q}_k(s,a)$$
迭代過程如下：

• 初始化：所有 states 的

  $V_0(S)=0$

• 第一次 iteration

  • $V_1((2,3))=0+0=0$
  • 其他 states
    $V_1(s)$ 之值皆為
    $-1$，例如：
    $V_1((1,1))=-1+0=-1$

• 第二次 iteration

  • $V_2((2,3))=0+0=0$
  • 對於
    $(1,1)$ ，往下或往右可以有最大的 value，故
    $V_2((1,1))=(-1)+(-1)=-2$，
    $(1,2),(2,1),(3,1),(3,2)$ 同理
  • 對於
    $(1,3)$ ，往右可以有最大的 value，故
    $V_2((1,3))=(-1)+0=-1$，其他位於寶箱附近的 states 同理

• 第三次 iteration

  • $V_3((2,3))=0+0=0$
  • 對於
    $(1,1)$ ，往下或往右可以有最大的 value，故
    $V_3((1,1))=(-1)+(-2)=-3$，其他距離寶箱 3 步的 states 同理
  • 對於
    $(1,2)$ ，往下或往右可以有最大的 value，故
    $V_3((1,2))=(-1)+(-1)=-2$，其他距離寶箱 2 步的 states 同理
  • 對於
    $(1,3)$ ，往右可以有最大的 value，故
    $V_3((1,3))=(-1)+0=-1$，其他位於寶箱附近的 states 同理

• 第四次 iteration
  所有

  $V(s)$ 皆沒有變化，故已收斂

參考資料：
https://zhuanlan.zhihu.com/p/33229439

---

能夠用 Value Iteration 來找最佳 policy 的原因是 Value Iteration 收斂的性質：

Value iteration converges on

$V^{\ast }$
For any initial

$V_0$, value iteration achieves that

$V_k\to V^{\ast }$ (in

$L_{\mathrm{\infty }}$-norm)

此性質可透過以下三步來證明：

1.

$T^{\ast }$ is a contraction operator.
proof:

$$\begin{array}{rl}||T^{\ast }(V)-T^{\ast }(\hat{V})|{|}_{\mathrm{\infty }}& =\underset{s}{max}|T^{\ast }(V(s))-T^{\ast }(\widehat{V(s)})|\\ & =\underset{s}{max}|\underset{a}{max}(R_s^a+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^{a}V(S^{\prime }))-\underset{a^{\prime }}{max}(R_s^{a^{\prime }}+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^{a^{\prime }}V(S^{\prime }))|\\ & \le \underset{s}{max}\underset{a}{max}|(R_s^a+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^{a}V(S^{\prime }))-(R_s^a+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^{a}V(S^{\prime }))|\\ & \le \underset{s}{max}\underset{a}{max}|\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a(V(s^{\prime })-\hat{V}(s^{\prime }))|\\ & \le \gamma ||(V-\hat{V})|{|}_{\mathrm{\infty }}\end{array}$$
=>

$T^{\ast }$ is a

$\gamma$-contraction operator.

2. Under a contraction operator,

$V_k$ shall converge to the unique fixed point.
proof:
Since

$T^{\ast }$ is a

$\gamma$-contraction operator in a complete metric space, by Banach Fixed Point Theorem,

$T^{\ast }$ converges to the unique fixed point.

3. Since

$V^{\ast }$ is a fixed point,

$V_k\to V^{\ast }$ due to uniqueness.

若

$\gamma$ 很接近

$1$，則 value iteration 可能會迭代無限次而不收斂。

Policy Iteration

Policy iteration 的目的是透過交替進行 policy evaluation 和 policy improvement，逐步優化 policy，直到找到最佳 policy。

1. Policy evaluation:
   固定 policy，計算出對應的
   $V^{\pi }(s)$，可使用任意 policy evaluation 的演算法
2. Policy improvement:
   找出 policy
   ${\pi }^{\prime }\ge \pi$，可使用任意 policy improvement 的演算法

Policy Iteration
(註：這裡針對 deterministic policy)
Initialize

$k=0$ and set

${\pi }_0(s)$ arbitrarily for all

$s$
While

$k=0$ or

${\pi }_k\ne {\pi }_{k-1}$:
 Derive

$V^{{\pi }_k}$ via policy evaluation for

${\pi }_k$
 Derive

${\pi }_{k+1}$ by greedy one-step policy improvement

One-Step Policy Improvement
Given

$V^{{\pi }_k}$, compute

$Q^{{\pi }_k}(s,a)$:

$$Q^{{\pi }_k}(s,a)=R(s,a)+\gamma \sum _{s}P(s^{\prime }|s,a)V^{{\pi }_k}(s^{\prime })$$
Derive the new policy

${\pi }_{k+1}$ for all states

$s$:

$${\pi }_{k+1}(s)=\arg \underset{a}{max}{Q}^{{\pi }_k}(s,a)$$

為何 One-step policy improvement 合理？
假設我們採取

${\pi }_{k+1}$ 只進行一步動作，之後的動作維持遵循

${\pi }_k$，會比從頭到尾都遵循

${\pi }_k$ 來得更好。這是因為

${\pi }_{k+1}$ 選擇的 action 是使得

$Q^{{\pi }_k}(s,a)$ 最大的 action，因此

$$\begin{array}{rl}{V}^{{\pi }_{k+1}}(s)& =Q^{{\pi }_k}(s,{\pi }_{k+1}(s))\\ & =\underset{a}{max}{Q}^{{\pi }_k}(s,a)\\ & \ge R(s,{\pi }_k(s))+\gamma \sum _{s}P(s^{\prime }|s,a)V^{{\pi }_k}(s^{\prime })\\ & =V^{{\pi }_k}(s)\end{array}$$

若從頭到尾都採取

${\pi }_{k+1}$，也會比遵循

${\pi }_k$ 好：

Theorem (Monotonic Policy Improvement)
Under the one-step policy improvement step, we have

$V^{{\pi }_{k+1}}(s)\ge V^{{\pi }_k}(s),\mathrm{\forall }s$, and hence

${\pi }_{k+1}\ge {\pi }_k$

proof:

$$\begin{array}{rl}{V}^{{\pi }_k}(s)& \le \underset{a}{max}{Q}^{{\pi }_k}(s,a)\\ & =\underset{a}{max}R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{{\pi }_k}(s^{\prime })\\ & =R(s,{\pi }_{k+1}(s))+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,{\pi }_{k+1}(s))V^{{\pi }_k}(s^{\prime })\\ & \le R(s,{\pi }_{k+1}(s))+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,{\pi }_{k+1}(s))\underset{a^{\prime }}{max}{Q}^{{\pi }_k}(s^{\prime },a^{\prime })\\ & =R(s,{\pi }_{k+1}(s))+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,{\pi }_{k+1}(s))\\ & \times (R(s^{\prime },{\pi }_{k+1}(s))+\gamma \sum _{s^{\prime \prime }\in S}P(s^{\prime \prime }|s^{\prime },{\pi }_{k+1}(s^{\prime }))V^{{\pi }_k}(s^{\prime \prime }))\\ & ...\\ & =V^{{\pi }_{k+1}}(s)\end{array}$$

這個證明的想法可以用 “Peeling off" 的概念來想像：

已知由

$s$ 遵循

${\pi }_{k+1}$ 到

$s^{\prime }$ 後再遵循

${\pi }_k$ 比從頭到尾遵循

${\pi }_k$ 來得好，則同理，由

$s^{\prime }$ 遵循

${\pi }_{k+1}$ 到

$s^{\prime \prime }$ 後再遵循

${\pi }_k$ 也會比從

$s^{\prime }$ 到尾都遵循

${\pi }_k$ 來得好，以此類推。

---

若我們得到

${\pi }_{k+1}={\pi }_k$，則代表 policy iteration 收斂了，且也表示 Bellman optimality equation 被

${\pi }_k$ 滿足：

$$V^{{\pi }_k}(s)=\underset{a}{max}{Q}^{{\pi }_k}(s,a)$$
此時

${\pi }_k$ 必為 optimal policy。

Policy Iteration 和 Value Iteration 共同證明了 optimal policy 存在

值得一提的是，在只討論 deterministic policy 的情況下，policy iteration 會在有限次數的迭代內停下來。這是因為 deterministic policy 的數量為

$|A{|}^{|S|}$，因此我們最多迭代

$|A{|}^{|S|}$ 次一定會停下。

Quick Summary

Problem	Bellman Equation	Algorithm
Prediction	Bellman Expectation Equation	IPE
Control	Bellman Expectation Equation + Greedy Policy Improvement	Policy Iteration
Control	Bellman Optimality Equation	Value Iteration

Next

Reinforcement Learning | Policy Gradient
https://hackmd.io/@tsen159/RLNote2