# Reinforcement Learning: An Introduction_Chapter 3 Finite Markov Decision Processes
###### tags: `Reinforcement Learning` `Second Edition`

[相關連結_Sutton_2nd](http://incompleteideas.net/book/the-book-2nd.html)
[David Silver_bilibili_簡中字幕](https://www.bilibili.com/video/BV1kb411i7KG/)
[程式碼參考_ShangtongZhang](https://github.com/ShangtongZhang/reinforcement-learning-an-introduction)
[程式碼參考_dennybritz](https://github.com/dennybritz/reinforcement-learning)
[程式碼參考_弱弱的我](https://github.com/shaoeChen/Reinforcement-Learning-An-Introduction-Record)

這一章會正式的開始介紹有限的馬可夫決策過程，或者稱為finite MDPs。這是本書後續試圖解決的問題。這是一個涉及評估回饋(evaluative feedback)，像是上一章提過的博賭機問題，還有結合性要素(associative aspect)，也就是在不同的情況之下選擇不同的actions。

MDPs是一種經典的序列決策的形式化，action影響的不僅是立即性的reward，還影響後續的情況(或稱state)以及與之相關未來的reward。MPDs涉及延遲的reward，因此誓必在立即性以及延遲性的reward之間要取一個權衡。

在上一章的賭博機問題中，我們為每一個action $a$衡量value $q_*(a)$，在MDPs中，我們衡量的value是$q_*(s, a)$，也就是每一個state $s$的每一個action $a$預計得到的value。不難看出之間的差異。或者也可以在給定最佳action的情況下衡量每一個state的value，也就是$v_*(s)$。

* 賭博機問題：$q_*(a)$，for all action $a$
* MDPs：
* $q_*(s, a)$，每一個state $s$的每一個action $a$預計得到的value
* $v_*(s)$：在給定最佳action的情況下衡量每一個state的value

這章會介紹幾個數學結構的關鍵問題，像是returns、value functions、Bellman equations。我們會試著將這些問題收斂成可以用finite MDPs來表示。

## 3.1 The Agent–Environment Interface
MDPs是一種透過交互學習來實現目標問題的簡易框架。其中學習器(learner)與決策製造者(decision maker)稱為agent。與agent交互作用的稱為environment(環境)。

agent與environment之間的交互作用是連續的，agent選擇actions，然後environment回應這些actions，然後呈現一個新的情境(state)給agent。environment會產生reward，通常是特定的數值，agent的目標就是最大化reward。

Figure 3.1說明著MPDs中，agent與environment之間的交互作用

上圖很直觀又清楚，agent在某一個時間$t$看見某一個state $S_t$，然後選擇一個action $A_t$，然後與環境交互作用之後得到reward $R_t$，也產出下一個state $S_{t+1}$，如此迭代。

:::warning
書中的表示對於action $A_t$的reward是以$R_{t+1}$來表示，而不是$R_t$
:::

更具體一點來說，就是agent與environment在每個離散時步(time steps)都在交互作用，其中time steps $t=0,1,2,3,4,\cdot$。在每一個時步$t$，agent都會收到environment的state的某些表示，$S_t \in \mathcal{S}$，然後在這些基礎上選擇一個action $A_t \in \mathcal{A}(s)$。一個時步之後，我們會收到因為這個action而產生的reward(數值)，$R_{t+1} \in R \subset \mathbb{R}$，然後進入下一個state $S_{t+1}$。這種交互之後會得到一個序列，或者稱為trajectory(軌跡)，像是這樣：
$$S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2 R_3, \cdots \tag{3.1}$$

在finite MDP情況中，$S, A, R$都是有限的。這種情況下，隨機變數$R_t, S_t$都是具有明確的離散機率分佈，而且僅取決於先前的state與action。也就是說，對於這些隨機變數$s' \in \mathcal{S}, r \in \mathcal{R}$的特定值，在給定先前的state與action的特定值情況下，發生在時間$t$的機率就是：
$$p(s', r \vert s, a) \dot{=} P_r \left\{S_t=s', R_t=r \vert S_{t-1}=s, A_{t-1}=a \right\} \tag{3.2}$$

上面的方程式是for 所有的$s', s \in \mathcal{S}, r \in \mathcal{R}, a \in \mathcal{A}(s)$。這公式很明確，在給定$S_{t-1}=s, A_{t-1}=a$的情況下，得到$S_t=s', R_t=r$的機率是多少。$\dot{=}$提醒我們這是一個定義，而且$p$ function也定義了MPD的動態性。

動態函數$p:\mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} -to [0, 1]$就只是一個擁有四個參數再普通不過的確定性函數。另外一點提醒，那就是函數$p$為每一個$s$與$a$的選擇都指定了一個機率分佈，也就是：
$$\sum_{s'\in\mathcal{S}} \sum_{r\in\mathcal{R}}p(s', r \vert s, a) = 1 \text{ for all } s \in \mathcal{S}, a\in\mathcal{A}(s) \tag{3.3}$$

:::warning
方程式3.3很直觀的說明，給定一個state、action之後的state與reward的搭配組合的機率加總就是1
:::

在MDP中，由$p$給出的機率完全描述出環境(environment)的動態性。也就是，$S_t$與$R_t$的每一個可能的值的出現機率都是取決上一個state $S_{t-1}$與action $A_{t-1}$，與更早之前的states、actions完全無關。這不是對決策過程的限制，而是對state的限制。state必需包含過去agent-environment交互作用得到的全方面信息，並對未來有一定的影響。滿足這個條件，那我們就說，這個state有著馬可夫性質(Markov property)。

從動態函數$p$(有四個參數)，我們可以計算關於環境的任何信息，像是狀態轉移機率(state-transition probabilities)(以擁有三個參數的函數來表示$p: \mathcal{S} \times \mathcal{S} \times \mathcal{A} \to [0, 1]$)：
$$p(s' \vert s, a) \dot{=} P_r\left\{S_t=s' \vert S_{t-1}, A_{t-1}=a\right\} = \sum_{r\in\mathcal{R}} p(s' , r\vert s, a) \tag{3.4}$$

:::warning
方程式3.4說明的是，next state $s'$的機率就是在$s'$情況下的所有可能的reward的機率加總，這邊談的是finite MDP，因此各種$r$的機率是可以窮舉的
:::

我們還可以計算給定state-action pairs的期望報酬(expected rewards)，這是一個兩個參數的函數：$r: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$：
$$r(s, a) \dot{=} \mathbb{E} [R_t \vert S_{t-1} = s, A_{t-1} = a] = \sum_{r\in\mathcal{R}}r \sum_{s' \in \mathcal{S}} p(s', r \vert s, a) \tag{3.5}$$

:::warning
方程式3.5就是計算給定$s, a$得到$s', r$這個pair的機率與報酬相乘之後的加總
:::

也可以計算給定state-action-next state的期望報酬，這是一個三個參數的函數：$r: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}$：
$$r(s, a, s') \dot{=} \mathbb{E}[R_t \vert S_{t-1}=s, A_{t-1}=a, S_t=s'] = \sum_{r \in \mathcal{R}} r \dfrac{p(s',r\vert s, a)}{p(s'\vert s, a)} \tag{3.6}$$

:::warning
方程式3.6，分母的部份可以看方程式3.4，$s'$的機率裡面的是$s', r$這個pair的機率，計算之後再乘上$r$
:::

書上主要使用3.2的函數，不過偶爾還是會用到其它的。

MDP這個框架是抽象而且靈活，可以用很多不同方法應用在不同問題上，一般來說，action可以是任何我們希望學習的決策，而state則是對於下決策有幫助的任何事情。而agent無法改變的事情則視為environment的一部份，但這並不代表agent對environment一無所知，因為agent至少可以知道如何利用一個action、state來得到多少的reward。我們通常將reward的計算視為是agnet的外部，因為reward定義著agent面臨的任務，而agent沒有辦法任意的改變它。但是某種情況下，agent也許會知道關於環境的一切，不過即使如此，這個強化學習任務依然是困難的。"The agent–environment boundary represents the limit of the agent’s absolute control, not of its knowledge"。實務上，一旦決定了states、actions、rewards，就是定義agent-environemnt的boundary，也就定義好一個具體的決策任務。

:::warning
這邊說明的應該是agent-environment之間，那些東西應該是視為agent，那些是視為environment，也許後續有實作再回來讀一次會更有感覺。
:::

MDP框架是一種基於交互作用的目標導向學習問題的高度抽象。不管要處理什麼問題，我們都可以將這個目標導向學習的行為概括為agent與environment傳遞的三個信號(signals)：
1. 表示agent的選擇(action)
2. 做出這個action的基礎(state)
3. agent的目標(reward)

書上給出一個範例，用機器撿回收做為說明：
假設有一個機器人，他有一個傳感器可以檢測易開罐，然後可以撿起來放到回收箱，還有自動回充功能，我們可以這樣定義問題：
1. 它有兩個state，$S=\left\{ \text{high, low}\right\}$，這代表著目前機器人的電力狀況
2. 在每個state的時候，機器人會有幾個action
* 尋找易開罐(search)
* 等待(wait)，因為電力不足就需要等人來救
* 回充(recharge)
3. reward
* 撿到易開罐就給一個正值的獎勵
* 把自己搞到沒電就給一個負值懲罰

當然，當機器人的電力充足(high)情況下是不允許它笨笨的回充，所以action set可以這樣定義：
* $A(\text{high})=\left\{\text{search, wait} \right\}$
* $A(\text{low})=\left\{\text{recharge, search, wait} \right\}$

這邊給出一個表格：

| $s$ | $a$ | $s'$ | $p(s'\vert s, a)$ | $r(s, a, s')$ |
| -------- | -------- | -------- | -------- | -------- |
| high | search | high | $\alpha$ | $r_{\text{search}}$ |
| high | search | low | $1-\alpha$ | $r_{\text{search}}$ |
| low | search | high | $1-\beta$ | -3 |
| low | search | low | $\beta$ | $r_{\text{search}}$ |
| high | wait | high | 1 | $r_{\text{wait}}$ |
| high | wait | low | 0 | $r_{\text{wait}}$ |
| low | wait | high | 0 | $r_{\text{wait}}$ |
| low | wait | low | 1 | $r_{\text{wait}}$ |
| low | recharge | high | 1 | 0 |
| low | recharge | low | 0 | 0 |

表格上將所有可能的狀態轉移給描述出來，可以看第3個row，當電力已經很低的情況下，它預估電力會提高而繼續尋找，這太喇叭了，馬上沒電，所以給出-3的reward。

書上另外給出一個利用transition graph來描述，見下圖：

兩個大圈圈是state，幾個小黑點是action，值得注意的是，離開一個action node(動作結點)的轉移機率之和為1，以上面表格第1、2個row為例，在state=high且action=search的情況下，它的下一個state的機率就是$\alpha + (1 - \alpha) = 1$。

## 3.2 Goals and Rewards
在強化學習中，agent的目標被形式化為一個特別的信號，就是reward，從environment傳遞給agent的一個信號。在每一個time step，reward都是一個數值，$R_t \in \mathbb{R}$。一般來說，agent的目標是最大化它所接收到的總報酬(total reward)。這意味著，最大化的不是當前reward，而是長時間所累積的報酬(cumulative reward)。我們可以將上面的想法表述為reward hypothesis，也就是"我們所有的目標都可以想成是最大化接收到的標量信號(也就是reward)的累積和的期望值"。

雖然這樣子的作法看起來有著限制性，不過實務上卻是很靈活，而且也有廣泛的可用性。舉例來說，讓機器人學習逃脫迷宮，在成功逃脫之前的每一個time step得到的reward都是-1，那agent就會試著快點讓機器人離開。或者是剛剛提過的收集易開罐的機器人，收到就得到+1，撞到人還是沒電就給-3。又或者是下棋，贏了就是+1，輸了就是-1。

上面幾個範例不難看到，agnet要做的就是學習如何最大化整個報酬(reward)。所以你想要它做什麼，那就給它reward，讓它最大化reward的同時是完成你希望它完成的事情。所以很重要的一點，我們設置的reward要能夠明確的表明我們想要完成的目標。不過要注意一點，reward的設置不能視為是完成目標的先驗知識，舉例來說，在象棋比賽中，我們的目標就是贏得棋盤比賽就得到reward+1，但如果設置成是吃掉對方1子就+1，那agent就可能學到輸掉比賽但是吃了對方很多子的方法。因為這個reward signal就只能用傳遞給agent我們想要的目標，而不是如何實現這個目標。
## 3.3 Returns and Episodes
剛剛用了一般性的說法來定義學習的目標，就是讓agent能夠最大化長時間接收到的累積報酬(cumulative reward)。如果要正式的定義，那我們說，在time step $t$之後接收到的報酬序列(sequence of reward)表示為$R_{t+1}, R_{t+2}, \cdots$，然後我們希望最大化[期望報酬](http://terms.naer.edu.tw/detail/416079/)(expected return)，以$G_t$來表示，最簡單的情況下，return是reward的總和：
$$G_t \dot{=} R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_{T} \tag{3.7}$$

其中$T$為最後一個time step。這種有最終time step的記錄是有意義的，這樣子agent與environment的互動就會被分類成子序列，我們把這種子序列稱為episodes。像是一種遊戲、一盤棋、一個旅遊，或是任何重覆性的互動。

每一個episode都在一個特殊狀態結束，稱為terminal state，隨後就重新開始(像是遊戲又回到開始畫面)。不管上一個episode是因為贏還是輸而結束，都不影響下一個episode的開始。因此這些episode可以想成是一樣的結束狀態，只是有不同的收益。這種類型的任務稱為episodic tasks。

在episodic tasks中，我們有時候會需要區分非終結狀態(nonterminal states)的集合，以符號$\mathcal{S}$表示，如果再加上終結狀態(terminal state)，那就以符號$\mathcal{S}^+$表示。終結的時間$T$是一個隨機變數，隨著episode的不同而不同。

:::warning
* 書中提到，有些文獻會將episode稱為trial。
:::

有些情況下，agent-environment的互動並沒有辦法被分成不同的episode，它是連續狀態，這類型的任務我們稱為continuing tasks。這時候如果用3.7的方程式來計算可能就不適合，因為$T = \infty$，每一個time step，agent都可以得到reward + 1，時間久了，自然就無限大了。

為此，我們引入一個稱為discounting的想法，下面給出公式：
$$G_t \dot{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^\infty \gamma^k R_{t+k+1} \tag{3.8}$$

其中$\gamma$是一個參數，稱為discount rate，且$0 \leq \gamma \leq 1$。

:::warning
$k$依下面所指是未來$k$個time steps，所以如果$k=0$那就只有現在，帶入上面的公式就是只有$R_{t+1}$
:::

這個discount rate決定未來報酬的現值：在未來$k$ time steps收到的reward只會有它現值的$\gamma^{k-1}$倍：
* $\gamma < 1$，那只要reward sequence $\left\{R_k \right\}$有bounded，那公式3.8的這個無限加總式子就會是有限值(finite value)
* $\gamma = 0$，那agent就會是"myopic"(短視近利)，就只會關心最大化當下立即性的reward
* 這種情況下，其目標就是學習如何選擇一個$A_t$而且僅最大化$R_{t+1}$
* 如果每一個agent的actions都剛好只影響當下的reward，而不影響未來的reward，那這種agent就可以利用各別最大化每一個當下的reward來最大化公式3.8
* $\gamma \approx 1$，當$\gamma$接近1的時候，return objective就會更加的考慮未來的reward，agent會變的更有遠見

不過通常最大化當下的reward都對讓未來的reward降低，因此總的來看return是降低的。

這種連續性time steps的returns彼此之間的關聯方式對於RL的理論與演算法而言很重要：
$$
\begin{align}
G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\
&= R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots)\\
&= R_{t+1} + \gamma G_{t+1}
\end{align} \tag{3.9}
$$

注意到，上面的公式適用於所有time steps $t < T$的情況，即使在$t+1$就發生終止(termination)，那就假設我們定義$G_T=0$。這通常讓我們從reward sequences計算returns變的簡單。

另外注意的是，雖然公式3.8是一個無限加總的項目，但如果它的reward是非零而且是常數，而且$\gamma < 1$，那它就仍然是有限的。舉例來說，如果reward是常數，+1，那return就是：
$$G_t = \sum_{k=0}^\infty \gamma^k = \dfrac{1}{1 - \gamma} \tag{3.10}$$

:::warning
* 這是幾何級數的推論，得到的應該是$\dfrac{1-\gamma^\infty}{1-\gamma}$，不過因為$\gamma < 1$，在無限次方的情況下就接近0，可以忽略掉，因此得到該公式
:::

### Example 3.4: Pole-Balancing
書上有給出一個平衡桿的範例，這個在openai開源的套件中可以做為練習，後續有空再來寫。


任務的目標就是要讓桿子在車子上不會倒，所以如果在一定的偏離角度或是車子偏離軌道就視為失敗。每一個time step只要桿子不倒，那reward就+1。這種情況下，其return就是經過幾個time steps(每次+1，5個time steps就是+5)，所以如果一直取得平衡不會倒就意謂著它的return會是無限大。

當然我們也可以把這個任務視為continuing task，使用discounting。這種情況下每次失敗reward就要給-1，其它time steps的reward則為0。這樣每次的return就會跟$-\gamma^{K-1}$有關，其中$K$就是輸掉之前的time steps。

## 3.4 Unified Notation for Episodic and Continuing Tasks
稍早討論過兩種強化學習的任務，一種是以episode為記錄的任務，一種是continuing tasks(連續型任務)。episode這種情況比較容易用數學來表示，因為它的每一個action的都只影響episode期間隨後收到的有限的reward的數量。不過書中兩種都會談，所以需要一個統一的表示。

要更精確的描述episode tasks，我們需要一些額外的符號。我們要考慮一系列的episodes(每個episode都是由有限的time steps的序列所組成)，而不是很長的time steps的序列。每個episode的time steps都會從零開始重新計數。所以我們在時間$t$的state的表示不應該是$S_t$，而是$S_{t,i}$，其中$i$是指episode的索引(類似的$A_{t,i}, R_{t_i}$)。不過其實我們討論的過程中並不會特別的去分是那一個episode，我們幾乎都是只考慮某一個特定的episode，或者對所有episodes都成立的描述。所以，其實，我們都還是用$S_t$來表示$S_{t,i}$。

我們需要另一種統一的符號約定，可以同時用於episode tasks與continuing tasks。回頭想，我們在公式3.7的時候將returns定義為有限的數量總和，而在公式3.8的時候將returns定義為無限的數量總和。我們可以利用將episode的結束視為進入一個特殊的absorbing state([吸收狀態](http://terms.naer.edu.tw/detail/3185736/))來統一這兩種情況，這種狀態只會轉移到自己，而且產生reward=0。

下面給出一個狀態轉移圖(state transition diagram)的範例：

粗框正方形表示對應一個episode結束的吸收狀態，一直在自己身上打轉，然後reward都是0。我們從$S_0$開始，得到reward sequence，$\left\{ +1, +1, +1, 0, 0, 0, 0, \cdots \right\}$。把這個reward sequence加總，可以看的到reward sequence與$T=3$有相同的return($T$代表結束)。即使我們導入discounting，這個結果仍然是成立的。所以我們可以根據公式3.8來定義return，不考慮episode的index，$\gamma=1$且總和依然定義的情況(因為所有的episodes都會有在有限時間內結束)。我們可以寫成這樣：
$$G_t\dot{=}\sum^T_{k=t+1} \gamma^{k-t-1}R_k \tag{3.11}$$

上面包含$T=\infty$或$\gamma=1$，但不會並存。上面的公式會貫穿本書其餘部份。

:::warning
* 這邊初看有點疑惑，不過因為前頭有提到，time step $t$決定的action $A_t=a$所得到的reward $R_{t+1}=r$，想像$t=1$，那$G_1=\sum_{k=2}^T$也是合理，當$k=2, t=1$，那$\gamma=1$，也就跟方程式3.8的第一個$R_{t+1}$得到一樣的結果

* 快速回憶：
$$G_t \dot{=} R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_{T} \tag{3.7}$$

$$G_t \dot{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^\infty \gamma^k R_{t+k+1} \tag{3.8}$$
:::

## 3.5 Policies and Value Functions
幾乎所有強化學習演算法都涉及價格函數(value function)的計算，value function估測著給定state(或給定state、action)的情況下，agent的表現有多好。有多好指的就是未來的reward的期望值，或者更精確的說return的期望值。這取決於agent所選定的action。因此，value function與特定的行為方式是有關的，我們稱為policies(策略)。

正確來說，policy是將state映射到每個可能action選擇的機率(想想賭俠的場景，電腦分析，百分之五十五是二，百分之三十八是Q，百分之七是九)。如果agent在時間$t$依著policy $\pi$，那麼$\pi(a\vert s)$就是給定$S_t=s$的情況下$A_t=a$的機率。$p, \pi$是一般函數；$\pi(a\vert s)$中間的這條$\vert$就只是提醒我們，它為每一個$s \in \mathcal{S}$定義了$a \in \mathcal{A}(s)$的機率分佈。強化學習方法明確說明了agent的policy如何依其經驗結果而改變。

在policy $\pi$下的state $s$的value function我們表示為$v_\pi(s)$，意思是從$s$開始，依著policy $\pi$的預期return。對於MDPs，我們可以將$v_\pi$定義為：
$$v_\pi(s) \dot{=} \mathbb{E}_\pi[G_t \vert S_t=s] = \mathbb{E}_\pi\left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \vert S_t=s \right], \text{ for all } s\in \mathcal{S} \tag{3.12}$$

其中$\mathbb{E}_\pi[\cdot]$代表agent在依著policy $\pi$的隨機變數的期望值，$t$可以是任意的time step。注意到，terminal state的值(如果有)始終為零。我們把函數$v_\pi$稱為policy $\pi$的state-value function。

類似地，我們定義在policy $\pi$下的state $s$所採用的action $a$的值，以$q_\pi(s, a)$表示，意思是從$s$開始，採用action $a$，最後依著policy $\pi$的預期return：
$$q_\pi(s, a) \dot{=} \mathbb{E}_\pi[G_t\vert S_t=s, A_t=a] = \mathbb{E}_\pi \left[\sum_{k=0}^\infty \gamma^k R_{t+k+1}\vert S_t=s, A_t=a \right] \tag{3.13}$$

我們將$q_\pi$稱為policy $\pi$的action-value function。

兩個value function，$v_\pi, q_\pi$，都可以從經驗來估測。舉例來說，如果agent按著policy $\pi$而且對遇到的每一個state都維持著遇到這個state實際的returns的平均值，那麼只要遇到這個state的次數趨近無限大，那這個平均值就會收斂到這個state的值，也就是$v_\pi(s)$。如果你把每個state中會採取的每一個action都保持單獨的平均值，那麼這些平均值也會類似上面一般的收斂到這個action的值，也就是$q_\pi(s, a)$。

我們把這樣子的估測方法稱為蒙地卡羅方法(Monte Carlo methods)，因為它們涉及了對很多實際return的隨機樣本計算平均值。這類的方法會在Chapter 5介紹。當然啦，如果有非常非常多的state，那麼去對每個不同的state分開維持平均值的作法就可能是不切實際的。相反的，agent必需要將$v_\pi$與$q_\pi$維持在一個參數化的函數(比states還要少的參數量)，然後利用調整參數來更好的匹配觀察到的returns(收益)。儘管這樣的作法很大程度上的取決於參數化函數逼近器(approximator)的特性，但終究還是可以產生準確的估測。後續會有討論。

在強化學習與動態規劃方面使用value functions的基本性質，就是它們已經滿足公式3.9建立的遞迴關係。對於任意的policy $\pi$與任意的state $s$，下面介於state $s$的值與其可能的後續的state的值之間的一致性條件成立：
$$
\begin{align}
v_\pi(s) &= \mathbb{E}_\pi[G_t \vert S_t=s] \\
&= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} \vert S_t = S] \tag{3.9} \\
&= \sum_a \pi(a\vert s) \sum_{s'} \sum_r p(s', r\vert s, a)\left[r + \gamma \mathbb{E}_\pi \left[ G_{t+1} \vert S_{t+1}=s' \right]\right] \\
&= \sum_a \pi(a \vert s) \sum_{s', r} p(s', r \vert s, a)[r + \gamma v_\pi(s')], \text{ for all } s \in \mathcal{S} \tag{3.14}
\end{align}
$$

:::warning
第二個公式只是將第一個公式再做一次的展開，與談到公式3.9的時候一樣的作法，第三個公式就是計算期望值，加總在給定state $s$的情況下，所有可能的action $a$的機率($\sum_a\pi(a\vert s)$)去乘上加總給定$s, a$的情況下，所有可能的next state $s'$與reward $r$的機率($\sum_{s', r}p(s', r\vert s, a)$)乘上reward $r$加上next state $s'$的value($r + \gamma v_\pi(s')$)
:::

:::warning
以向量化來表示的話，Bellman equation可以寫為$v = \mathcal{R} + \gamma \mathcal{P}v$，其中$\mathcal{P}$是狀態之間轉移的機率矩陣，而等號右邊的$v$你可以想像成是當前每一個state的value。

因此如果你的state有10個，那$v$就是10維，而$\mathcal{P}$就是一個10x10的矩陣。
:::
很明顯的，action $a$是來自集合$\mathcal{A}(s)$，下一個state，$s'$則是來自集合$\mathcal{S}$，然後，reward，$r$，是來自集合$\mathcal{R}$。至於上面最後一個數學式就只是為了簡化數學式而合併兩個summation。它實際上是三個變數，$a, s', r$，的所有值的總和。每一次的[三元組](http://terms.naer.edu.tw/detail/12974234/)(就是那三個變數的組合)，我們計算它的機率，$\pi(a\vert s)p(s', r\vert s, a)$，然後利用機率對括號內的值加權，然後加總所有的可能來得到期望值。

方程式3.14是$v_\pi$貝爾曼方程式(Bellman equation)。這解釋了state的值($s$)與後續state的值($s'$)之間的關聯。

如下圖所示，考量到從一個state到後續它所有可能的state：

每個[開圓](http://terms.naer.edu.tw/detail/2120937/)(open circle)都表示一個state，每個[實心圓](http://terms.naer.edu.tw/detail/3386229/)(solid circle)都表示一個state-action pair。從根節點的state $s$開始，按著它的policy $\pi$，agent可以採取任一組的actions，如上圖三個pair所示。

:::warning
* root的$s$下面有三個$a$可以選擇，這樣就形成三個pair
* $\pi(a\vert s)$，就可以看成是root的$s$到三個實心圓$a$的機率
* $p(s', r \vert s, a)$，就可以看成是給選定一個實心圓之後往下兩個$s', r$ pair的機率
:::

選擇任一組action之後，environment就會回應多個$s'$的其中一個，如上圖所示，每個action之後的$s'$都有兩個，意思就是選擇這個action之後後續會有兩種可能就是。還有reward $r$，這取決於function $p$給出的動態。

貝爾曼方程式(3.14)對所有可能性計算平均，然後根據發生的機率對每個可能性計算加權。這指出了，start state的值必需要等於next state預期的(折扣)值加上沿途預期的reward。

這個value function $\pi$是其貝爾曼方程式的唯一解。這後續的章節會有提到。我們把類似上面那種圖的圖稱為backup diagrams，因為它們繪製形成update或backup operation的關聯，這是強化學習方法的核心。這些operations將價值信息(value information)從其後續的state(或state-action pairs)傳遞回當下的state(或state-action pairs)。這整本書都會用backup diagrams來做為我們所討論的演算法的graphical summaries(圖總結?)。值得注意的是，與transition graphs不同，backup diagrams的state nodes並不需要是不同的state，舉例來說，一個state可以是自己後續的state。

### Example 3.5: Gridworld
下圖，Figure 3.2是一個Gridworld的範例，左邊是期望值的動態性，右邊則是等機率(equiprobable)隨機策略的state-value function：

上面這個矩形的gridworld代表一個簡單的finite MDP。grid裡面的cell代表environment的states。每一個cellfe上可能有四個actions可以選擇，就東、西、南、北，這個決定性導致agent在grid上相對應的方向上移動一個cell。如果actions會讓agent離開這個grid，那它就會停留在原地，然後reward-1。其它的actions的reward就是0，除了那些可以讓agent離開特殊的states，A、B除外。在state A，四個方向的action都會得到+10的reward，然後帶著agent到達A'。在state B，四個方向的action都會得到+5的reward，然後帶著agent到B'。

假設agent在所有的state情況下選擇任一個方向的機率都是一樣的，那上圖右說明的就是policy $\pi$的value function，$v_\pi$，然後$\gamma=0.9$，這個結果就是用方程式3.14計算得來的。可以注意到幾點：
1. 上表中下面的負值，會這樣是因為在隨機策略下它們有很高的機率會掉到外面的，所以負值
2. state A是這個policy下最好的state，但是注意到，A'的expected return(+8.8)比它的reward(+10)還要小，因為從A到A'很有機會掉到外面去
3. state B可以發現到它的expected return(+5.3)比它的reward(+5)還要來的大，這是因為到B'的時候它的exprected return依然是正數。從B'來看，可能掉到外面的預期懲罰(negative reward)會比困在A或B上的預期收益的補償還要來的高。

### Example 3.6: Golf
Figure 3.3，說明的是一個高爾夫球的範例，上半部說明的是推桿的state-value function，下半部說明的則是使用木桿的optimal action-value function


這個範例是將打高爾夫球描述成強化學習任務：
1. 球在進洞之前的每次打擊都會得到-1的reward
2. state就是球的位置
3. state的value就是當前位置到球進洞之前的擊球次數的負值(因為打一欠就是-1的reward)
4. actions就是如何瞄準與擊球，還有選擇什麼樣的球桿，假設前面的條件是給定的，那就只需要考慮選擇推桿還是木桿
5. policy $\text{putt}$始終會使用推桿，其可能的state-value function為$v_{\text{putt}}(s)$
6. 終止狀態，進洞(in-the-hole)的value為0
7. 只要是在果嶺的區域，我們假設是可以做推桿，這些state的value為-1，不過只要是在果嶺之外我們就無法推桿，因此value是低的
8. 如果我們可以利用推桿到果嶺區域，那這個state的value一定會比果嶺的value還要少1，也就是-2

為了簡單起見，我們假設我們可以非常精確、確定的推桿，只是範圍有限。這給了我們圖中標記為-2的[等高線](http://terms.naer.edu.tw/detail/844176/)。只要是在這個等高線內就只需要兩桿就保證可以進洞。推桿沒有辦法離開沙地，所以只要進入沙地那它的value就是$-\infty$。整體來說，我們就是需要六桿來進洞。

### Exercise 3.18
state的value是取決於在這個state上可能的actions的value，以及在當前的policy下每一個action被選到的機率。我們可以將這件事想像成下面這張圖：

上圖很好的說明了$v_\pi(s), q_\pi(s, a), \pi(a \vert s)$。給定一個state $s$，你可以利用$v_\pi(s)$來估測後續的state value。然後你也可以估測要選定那一個action，也就是$\pi(a \vert s)$，給定$s$的情況下，三個action要選擇那一個。然後就可以以$q_\pi(s, a)$來估測state action value。

### Exercise 3.19
action的value，$q_\pi(s, a)$，取決於預期的下一個reward與預期的剩餘reward的總合。與上面一樣，把它想成是一個backup diagram，只是它的root是一個state-action pair，然後分枝是可能的下一個state：

上面的圖很好的說明了給定$S_t=s, A_t=a$的情況下，預期的下一個reward，$R_{t+1}$與預期的下一個state value $v_\pi(S_{t+1})$，對應上面給出的state action function $q_\pi(s, a)$的計算公式。可參考方程式3.2。

:::warning
$$p(s', r \vert s, a) \dot{=} P_r \left\{S_t=s', R_t=r \vert S_{t-1}=s, A_{t-1}=a \right\} \tag{3.2}$$
:::

## 3.6 Optimal Policies and Optimal Value Functions
解一個強化學習任務的意思就是，找出一個policy，然後在長時間執行的過程中可以得到很大的reward。對於finite MDP，我們可以精確的定義一個optimal policy。而value function定義了policies的[偏序](http://terms.naer.edu.tw/detail/2121469/)。也就是，所有的state所預期的return比$\pi '$好或是一樣好，那$\pi$就被定義為比$\pi '$好或是一樣好。換句話說，$\pi \geq \pi'$，(若且唯若)$v_\pi(s) \geq v_{\pi'}(s) \space \forall s \in \mathcal{S}$。一定會有一個policy比別人好或是一樣好，那一個就是optimal policy。雖然可能會超過一個，但是我們就將這些optimal policies以$\pi_*$來表示。它們共用一個相同的state-value function，稱為optimal state-value function，以$v_*$表示，定義為：
$$v_*(s) \dot{=} \max_\pi v_\pi(s), \forall s\in \mathcal{S} \tag{3.15}$$

:::warning
簡單來看，既然是optimal state-value function，那它的$v_*$一定就是最好的，所以會等於$\max_\pi v_\pi(s)$
:::

optimal policies也共用同一個optimal action-value function，以$q_*$表示，定義為：
$$q_*(s, a) \dot{=} \max_\pi q_\pi(s, a) \forall s \in \mathcal{S}, a \in \mathcal{A}(s) \tag{3.16}$$

對於state-action pair($s, a$)，這個函數給出在state $s$情況下採取action $a$，然後依著optimal policy所能得到的expected return。因此我們可以寫成下面這樣：
$$q_*(s, a)=\mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1})\vert S_{t}=s, A_{t}=a] \tag{3.17}$$

### Example 3.7: Optimal Value Functions for Golf
Figure 3.3

回頭來看Figure 3.3的下半部所說明的可能的optimal action-value function $q_*(s, \text{driver})$。這些是每一個state的value，如果第一桿我們選擇用木桿來擊球，然後選擇木桿還是推桿，以較好的為主。木桿可以打的比較遠，但是準度不足。只有在很接近洞口的時候才有辦法用木桿一桿進洞；因此，在圖下半部可以看的出來，-1的等高線只涵蓋果嶺的一小部份。然而，如果我們有兩桿的機會，那就可以從比較遠的地方打到洞口(如-2等高線的說明)。這種情況下我們並不需要執著於那一個小小的-1等高線的區域，只要能夠打到果嶺，前就可以用推桿來一桿進洞。optimal action-value function給出特定的第一個action之後的value(這種情況下說的就是使用木桿)，但隨後就是那一種桿好就用那一種。-3的等高線圖更遠，它包含發球桿的區域。從這邊開始的話，最好的順序就是兩次木桿與一次推桿，三球進洞。

因為$v_*$是policy的value function，因此它必需滿足由Bellman equation對於state values(3.14)所給出的[自身一致性](http://terms.naer.edu.tw/detail/953271/)的條件。因為它是optimal value function，而$v_*$的一致性條件可以用一種特殊的形式來表示，而不需要參考任何特定的policy。這就是Bellman optimality equation。直觀來看，Bellman optimality euqation表達一件事，那就是在一個optimal policy底下的state的value一定會等於這個state的最佳action的expected return：
$$
\begin{align}
v_*(s) &= \max_{a \in \mathcal{A}(s)} q_{\pi_*}(s, a) \\
&= \max_{a} \mathbb{E}_{\pi_*}[G_t \vert S_t=s, A_t=a] \\
&= \max_{a} \mathbb{E}_{\pi_*}[R_{t+1} + \gamma G_{t+1} \vert S_t=s, A_t=a] \tag{3.9} \\
&= \max_a \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \vert S_t=s, A_t=a] \tag{3.18} \\
&= \max_a \sum_{s', r}p(s', r \vert s, a)[r + \gamma v_*(s')] \tag{3.19}
\end{align}
$$

最後兩個方程式就是$v_*$的Bellman optimality equation的兩種形式：
$$
\begin{align}
q_*(s, a) &= \mathbb{E}[R_{t+1} + \gamma \max_{a'}q_*(S_{t+1}, a') \vert S_t=s, A_t=a] \\
&= \sum_{s', r}p(s', r \vert s, a)[r + \gamma \max_{a'}q_*(s', a')] \tag{3.20}
\end{align}
$$

Figure 3.4的backup diagrams以圖形化來說明$v_*, q_*$的Bellman optimality equations中所考慮的未來的state與action。

Figure 3.4

這個前面提過的$v_\pi, q_\pi$的backup diagrams一樣，除了多了個弧(arcs)來表示agent的選擇的是給定某些policy情況下選擇maximum而不是的期望值。左邊的部份對照方程式的3.19，右邊則是3.20。

對於finite MDPs，$v_*$的Bellman optimality equations(3.19)有著唯一解。Bellman optimality equations實際上是一個[方程組](http://terms.naer.edu.tw/detail/1219247/)，每一個state都有一個方程組，如果有$n$個state，那在$n$個未知數中就會有$n$個方程組。如果environment的dynamics $p$是已知的，那麼，原則上就可以用解非線性方程式的各種方法中的任一種來解$v_*$。類似的方法也可以解$q_*$。

:::warning
上面有提到，Bellman equation的式子就是$v = \mathcal{R} + \gamma \mathcal{P} v$，那些許調整一下，$(1-\gamma\mathcal{P})v=\mathcal{R}$，最終你想解$v$就只是計算$(1-\gamma\mathcal{P})^{-1}\mathcal{R}$。

影片中蠻多人在討論這兩個$v$有前後的關係，有兩種說法是(1)當你sample無限多次之後，你的$v$基本上也是一個fixed point，因此視為兩者相等。(2)所有的state、轉移機率都已知的情況下，每個state的value應該就可以已知。
:::

有了$v_*$，那定義一組optimal policy就相對簡單。對每一個state $s$，那會有一個或多個actions可以在Bellman optimality equation下得到最大值。任何能夠只給這些actions非零機率的policy就是optimal policy。這可以視為是一種one-step search。如果你的手上有optimal value function $v_*$，那在one-step search之後的action就是optimal action。換個說法就是，對optimal evaluation function $v_*$來說，任何的policy只要是greddy，那它是一個optimal policy。

上一章有提到greedy就是都只找最好的，它只看短期、立即性的reward是最好的那就選擇它。但是使用$v_*$的好處就是，即使是greedy，長期來看它仍然是最好的，因為$v_*$已經存在著未來所有可能行為產生的reward的影響。通過使用$v_*$，optimal expected long-term return(最佳化的長期期望報酬)已經被轉換為每一個state的局部(locally)、立即的計算。因此，one-step-ahead search就可以直接生成long-term optimal actions。

使用$q_*$可以讓選擇optimal actions更簡單，甚至不需要使用one-step-ahead search：給定任意的state $s$，它可以很輕易的發現任意的action來最大化$q_*(s, a)$。action-value function可以有效地保存所有one-step-ahead searchs的結果。它讓optimal expected long-term returns變成每一個局部、立即可用的state-action pair的value。因此，以state-action pairs的函數做為表示(而非只有state)，其optimal action value function就可以在沒有任何關於下一個state、values的情況下選擇，也就可以說，不需要瞭解任何關於environment的動態性就可以選擇。

### Example 3.8: Solving the Gridworld
:::warning
prediction problem意謂著給定一個policy，評估一下未來會如何，就好像是，如果你一直往前走，那你會得到多少的reward。而control problem就是找出一個最好的policy，你要往那裡走才能得到最大的reward。在強化學習中我們要解決預測問題，進而解決控制問題。

因此你從下面Figure 3.5可以看的到，中間的$v_*$說明的就是預測問題，你在每一個cell裡面，依據你的policy去評估每一個cell有多好。而右邊的$\pi_*$則是跟你說，你應該往那裡去。你知道每一個cell有多好，自然就會知道你該往那裡去。
:::

Figure 3.5，下圖給出與先前相同的範例

我們已經知道$A \to A'$會得到10的reward，而$B \to B'$會得到5的reward(左圖)。中間的圖給出optimal value function $v_*$，右邊的圖則給出，你只要跟著箭頭的方向走，永遠都是最佳解，簡直跟中毒一樣，每次都會走到$A$。

### Example 3.9: Bellman Optimality Equations for the Recycling Robot
使用方程式3.19，我們可以明確的在回收機器人這個範例上使用Bellman optimality equation。以$h, l , s, w, re$分別表示state的high與low(電量狀態)，以及action的search、wait、recharg(搜尋、等待、回充)。因為只有兩個state，因此Bellman optimality equation包含兩個equations。$v_*(h)$的方程式如下：
$$
\begin{align}
v_*(h) &= \max \begin{Bmatrix} p(h \vert h, s) [r(h, s, h) + \gamma v_*(h)] + p(l \vert h, s)[r(h, s, l) + \gamma v_*(l)], \\ p(h \vert h, w) [r(h, w, h) + \gamma v_*(h)] + p(l \vert h, w)[r(h, w, l) + \gamma v_*(l)] \end{Bmatrix} \\
&= \max \begin{Bmatrix} \alpha[r_s + \gamma v_*(h)] + (1-\alpha)[r_s + \gamma v_*(l)], \\ l[r_w + \gamma v_*(h)] + 0[r_w + \gamma v_*(l)]\end{Bmatrix} \\
&= \max \begin{Bmatrix} r_s + \gamma[\alpha v_*(h) + (1 - \alpha)v_*(l)] \\ r_w + \gamma v_*(h) \end{Bmatrix}
\end{align}
$$

同樣的，$v_*(l)$可以得到下面方程式：
$$
v_*(l) = \max \begin{Bmatrix} \beta r_s - 3(1-\beta) + \gamma[(1-\beta)v_*(h) + \beta v_*(l)], \\ r_w + \gamma v_*(l), \\ \gamma v_*(h) \end{Bmatrix}
$$

對於任意的$r_s, r_w, \alpha, \beta, \gamma$，且$0 \leq \gamma <1, 0 \leq \alpha, \beta \leq 1$，確實存在一對的值，也就是$v_*(h), v_*(l)$，同時滿足這兩個非線性方程式。

顯性的解Bellman optimality equation給了一個找出optimal policy的途徑，從而解了強化學習問題。不過這種方法並不是那麼有效，因為這樣的作法類似窮舉所有一切的可能，然後計算每一種可能的expected rewards。這種解法依賴於實務上很難成真的假設：
1. 我們完全的知道環境的動態性
2. 計算資源能夠滿足完全的這些計算
3. state滿足Markov性質

對於我們感興趣的任務，只要沒有辦法滿足這三個條件，那就沒有辦法用剛才說的方法來處理。以西洋棋為例，也許可以滿足1、3兩個條件，但是2的話，所有的state大約是$10^{20}$個，如果要用Bellman equation來求解可能需要上千年。因此在強化學習中我們通常用近似解來解這類問題。

## 3.7 Optimality and Approximation
我們已經定義好optimal value functions與optimal policies。很明顯的，agent成功的學習到optimal policy，但事實上並非如此。對於我們感興 趣的任務，你要找到optimal policies需要極大的計算資源。因此實務上我們只能近似。

記憶體也是一個很重要的限制。在有限的狀態集合(state sets)，比較小型的任務中，我們可以把每一個state或state-action pair的近似值用array或是table來表示，這樣的作法稱為tabular case，相關的方法則稱為tabular methods。不過實務上你的states可能遠比能夠寫入table的記錄還要來的多。這種情况下，必須使用某種更為緊湊的參數化函數表示來近似函數。

其實上面這樣說一說不難發現到，我們必需要認真面對近似問題。但這也給了我們機會來實現有效的近似演算法。兩個例子說明：
1. 在近似最佳行為時，也許有很多的state，意思是說，agent遇到每一個state的機率都很低，因此即使選擇suboptimal actions對agent得到的reward影響也是很小
2. Tesauro的西洋雙陸棋戲玩家，它可能會選擇一些出其不意的決策，但這棋的決策可能結果是不好的。事實上，當遊戲的狀態集合很大的時候，它的決策通常很差

強化學習的在線質性讓它有可能以下面的方式來近似最佳的策略，也就是在學習中投入更多，來讓經常遇到的state可以做出好的決策，然後在不常遇到的state上花較少的精力。這是區分強化學習與其它解MDP的近似方法的一個關鍵特性。

## 3.8 Summary
強化學習的簡單總結：
1. 強化學習是在交互中學習為了達到目標該如何行動
2. 強化學習中，agent與environment會在一系列的離散時步上交互作用
3. action是由agent來選擇，而state是agent選擇該action的基礎，reward則是估測選擇的基礎(就是看選的好不好)
4. agent內的一切都是已知，而且可控的，而environment則是完全不可控，而且部份已知、部份未知
5. policy是agent選擇action的隨機規則(stochastic rule)，它是state的函數
6. agent的目標是隨著時間的推移來得到最大化的reward
7. return是agent要最大化的未來reward的函數
8. 在給定agent使用某個policy情況下，policy的value functions($v_\pi, q_\pi$)會分配到每個state或是state-action pari，然後從state、state-action pair得到expected return。
強化學習在明確定義轉移機率後，構成馬可夫決策過程(MDP)。finite MDP是一個存在著有限的state、action、reward集合的MDP。目前多數的強化學習理論都屬這類
9. optimal value function($v_*, q_*$)分配給要個state或state-action pair，利用任意的policy得到最大的expected return。value functions是最佳的那個policy就是optimal policy
10. 給定MDP情況下，states與state-actions pairs的optimal value function是唯一的，但是它們可以有多個optimal policies
11. 任意的policy，只要它在optimal value function上是greedy的，那它就是optimal policy
12. Bellman optimality equations是optimal value functions必需滿足特殊[一致條件](http://terms.naer.edu.tw/detail/2113474/)(相容條件?)，原則上可以解optimal value functions，從而可以相對容易的確定optimal policy

return會依是否要不要給予delayed reward計算折扣(discount)而有不同的定義：
* (undiscounted)不計算的話適用於episodic tasks，這類任務的agent-environment交互會很自然的分解成episodes
* (discounted)計算的話適用於continuing tasks，這類任是連續執行，而且沒有限制

上面兩個類型的任務我們也已經試著用相同的數學式來表述。

強化學習的問題可以用多種不同方式來表示，這取決於agent一開始能得到的知識水平的假設。在一個完全瞭解的問題中，agent有完整而精確的模型來表示環境(environment)的動態變化。如果environment是MDP，那就是像公式3.2所述的函數一般由四個參數的動態性函數所組成。

:::warning
$$p(s', r \vert s, a) \dot{=} P_r \left\{S_t=s', R_t=r \vert S_{t-1}=s, A_{t-1}=a \right\} \tag{3.2}$$
:::

即使agent有完整且精確的環境模型，仍然會受限於記憶體與計算能力而沒有辦法在每一個time step都全面的利用到環境模型。多數情況，states通常不是一個table能夠裝的下的，所以我們需要近似解。