UA CSC696H 強化學習理論選講1 強化學習概覽

• • 強化學習相關概念
  • Markov Decision Processes(MDP)簡介
  • Policy Evaluation

強化學習（reinforcement learning, RL）研究智能體（intelligent agents）在給定情景下為了最大化累積獎勵（cumulative reward）應該如何采取行動（take actions）。按照這個描述，在應用強化學習時，至少需要明確應用情景、獎勵函數、以及可行的行動方案。比如要設計一個能自動開方子的智能體，就可以設想一個患者定期來問診的場景，第$t$期患者前來問診時智能體獲得患者當前身體狀況$x_t$作為輸入，同時開出這一期的方子$a_t$，把患者按這個方子抓藥服用后健康狀況增益作為當期獎勵$r_t$，設計這個智能體的目標定為最大化患者的長期身體健康狀況$\sum r_t$。

但這個專題課我是旁聽的，課程內容并不是強化學習的具體應用和算法，而是強化學習的理論基礎與分析強化學習算法的數學工具。其中理論基礎部分主要涉及Markov Decision Process、Optimization、Probability Contraction等，分析的強化學習performance用到的指標主要包括online regret（簡單來說就是如果從前我那樣做了，累積獎勵會不會更高，分析算法理論性質時我們希望是不會）, sample complexity（希望用盡可能少的行動獲得最高獎勵，主要是因為造訓練數據很貴）, computational complexity（計算復雜度當然是越低越好）。這一講是第一講，主要是敘述一些與強化學習有關的概念，并簡單引入Markov Decision Process。

---

強化學習相關概念

Online Supervised Learning
以垃圾郵件自動過濾器為例，用$t=1,?,T$表示收到郵件的時間點；在第$t$次收到郵件$x_t$時，過濾器根據$x_t$做出關于這封郵件是否是垃圾郵件的判斷${\hat{y}}_t$（用$\{(x_s,y_s){\}}_{s=1}^{t?1}$訓練過濾器并完成預測，目標是最小化誤判總數），同時記錄下郵箱用戶看到這封郵件后的判斷$y_t$；這個例子中預測基于實時樣本進行，并且樣本中有label，每一次進行預測時都是監督學習的框架，所以是一個online supervised learning，設計相關算法時需要著重考慮過濾器的泛化能力，也就是如何保證收到第$t$封郵件時的實時樣本$\{(x_s,y_s){\}}_{s=1}^{t?1}$中關于垃圾郵件分類的知識能夠遷移到$x_t$上。

Online Bandit Learning
用前文的自動開方子智能體作為例子，設想一個患者定期來問診的場景，第$t$期患者前來問診時智能體獲得患者當前身體狀況$x_t$作為輸入，同時開出這一期的方子$a_t$，把患者按這個方子抓藥服用后健康狀況增益作為當期獎勵$r_t$，設計這個智能體的目標定為最大化患者的長期身體健康狀況$\sum r_t$。這就不是online supervised learning了而是online bandit learning，因為在第$t$期做行動決策時已知信息只有$x_t$，以及$\{a_t\},\{r_t\}$。

Multi-armed bandits也是Online Bandit Learning中的一類，它可以用來解決exploration-exploitation trade-off的問題。比如要考慮接下來一學期中午吃黃燜雞米飯、隆江豬腳飯、重慶雞公煲還是咸肉菜飯，假設我們沒有關于這幾家店的先驗信息，而目標是最大化自己這學期午飯的體驗。按Multi-armed bandits的思路，我們首先應該先來體驗一下這幾家店，也就是exploration，但是不能只去一次，畢竟去一次有可能遇到老板和老板娘吵架影響用餐體驗，應該每家店都多去幾次，獲得多個體驗感的記錄，每多獲得一次記錄都可以重新計算各店體驗感的置信區間，根據置信區間選擇下一次午飯吃哪家。這樣做的好處是在exploration的同時收集數據，盡量降低潛在的bias。

Online Episodic RL
這類問題例子如下，在這一關中，小A應該怎么操作才能盡快拿到小星星。

假設$t$表示關卡或者章節（episodic），每一關初始狀態為$s_1^t$，用$h$表示這一關的第$h$次操作，$a_h^t$表示這次操作采取的行動，獎勵為$r_h^t～R(?|s_h^t,a_h^t)$，狀態轉移函數為$s_{h+1}^t～P(?|s_h^t,a_h^t)$，比如在上圖中，記A左下格子為$(1,1)$，則星星的位置為$(5,4)$，A的初始狀態為$s_1^t=(2,2)$，每一次可以采取的行動為$\{x\to x+1,x\to x?1,y\to y+1,y\to y?1\}$，獎勵函數為$R=1_{(5,4)}$，也就是只有在到達小星星的位置時才有獎勵。這類問題的難點在于每一次操作的后果是在關卡結束時結算的（delayed consequence），就不像是online bandit learning一樣每一步操作都有相應獎勵能用來幫助決策。以上的這些例子也涉及了RL算法設計需要處理的挑戰：generalization、exploration與delayed consequence。

---

Markov Decision Processes(MDP)簡介

MDP是分析序貫決策的常用工具。記MDP為$$M=(S,A,P,r,\gamma ,\mu )$$

其中$S$表示state space，$A$表示action space，$P$代表transition kernel（用來表示uncertainty in the environment），當前狀態為$s$，采取行動$a$，則下一期狀態為$s^{\prime }$的概率可以表示為$P(s^{\prime }|s,a)$，$r:S\times A\to [0,1]$代表reward function，$\gamma \in [0,1)$是折現因子，$\mu$是initial state distribution。

用上面那個小A找小星星的例子說明怎么用MDP來建模，思路很簡單，就是把MDP的相關參數寫出來就好。
$$\begin{gathered} S=\{1,2,3,4,5,6\}\times \{1,2,3,4,5\} \\ A=\{上，下，左，右，不動\} \end{gathered}$$

狀態轉移是確定的，所以transition kernel可以用identity function表示，比如
$$P(s^{\prime }|(2,2),上)={\text{1}}_{(2,3)}=\{\begin{array}{l}0,s^{\prime }=(2,2)\\ 1,s^{\prime }=(2,2)\end{array}$$

而只有到達小星星的位置才有獎勵，所以
$$r(s,a)={\text{1}}_{(5,4)}$$

Initial state是給定為$(2,2)$的，
$$\mu (s)={\text{1}}_{(2,2)}$$

因為中間步驟沒有獎勵，所以折現因子大于0即可。這樣我們就用MDP的語言描述了小A找小星星的例子。

接下來我們給出MDP更具體的描述：

初始狀態：$S_0～\mu$

在第$t$步時（$t=0,1,2,?$）
智能體采取行動$a_t$；
智能體獲得獎勵$r_t=r(s_t,a_t)$
智能體轉移到下一個狀態$s_{t+1}～P(?|s_t,a_t)$

在這個過程中，到第$t$步完成時，智能體記錄下的數據為
$$(s_0,a_0,r_0,?,s_t,a_t,r_t,s_{t+1})\in (S\times A\times [0,1]{)}^t\times S?H_t$$

這里$H_t$表示智能體的歷史數據集合。另外，智能體的目標是最大化獎勵的期望現值：
$$E[G_0]=E\left[\sum _{t=0}^{+\infty }{\gamma }^t{r}_t\right]$$

因為定義獎勵是屬于$[0,1]$的，所以
$$\sum _{t=0}^{+\infty }{\gamma }^t{r}_t\le \sum _{t=0}^{+\infty }{\gamma }^t=\frac{1}{1?\gamma }$$

$\gamma$越大，折現效應越弱，未來獎勵占比會增加，智能體傾向于長期決策；$\gamma$越小，折現效應越強，折現后的獎勵主要由近期獎勵構成，智能體傾向于更高的近期獎勵。

Policy Evaluation

Policy的含義
盡管上文給出了用MDP來描述動態決策過程的一些思路，但我們對智能體行為的了解還只停留在具體的某一步選擇什么行動上，為了對智能體整體的行為模式建模，我們需要用到Policy。記
$$H=\underset{t=0}{\overset{+\infty }{?}}{H}_t$$

Policy用$\pi$表示，它是定義在$A$上關于$H$生成的Filter的條件概率，也就是當智能體的歷史記錄為${\tau }_t$時，采取行動$a$的概率可以記為$\pi (a|{\tau }_t)$。如果$\pi (a|{\tau }_t)=\pi (a|s_t)$，就稱這樣的Policy為stationary policy。

Value Function的定義
Value function的作用是評估policy，也就是評估智能體的整體行為，它的定義是
$$V^{\pi }(s)=E[G_0|s_0=s,\pi ]$$

比較理想的Policy滿足$?s\in S$，$V^{\pi }(s)$都已經是最大值了，也就是不管初始狀態如何，我們理想中的最優Policy都應該最大化Value function。看起來這個理想好像很遠大，但現有結果說明，至少存在一個deterministic、stationary $\pi$能達到這種最優。

Value Function的計算
雖然實踐中可以用MC simulation等辦法估計value function，但既然我們要從理論上研究MDP，那還是要嘗試找出解析式的。下面討論stationary policy的情況，
$$\begin{array}{rl}{V}^{\pi }(s)& =E[G_0|s_0=s,\pi ]\\ & =\sum _{a\in A}\pi (a|s)E[G_0|s_0=s,a_0=a,\pi ]\\ & =\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a)\end{array}$$

這里$Q^{\pi }(s,a)=E[G_0|s_0=s,a_0=a,\pi ]$也是一類value function。
$$\begin{array}{rl}{Q}^{\pi }(s,a)& =E[G_0|s_0=s,a_0=a,\pi ]\\ & =E\left[\sum _{t=0}^{+\infty }{\gamma }^t{r}_t|s_0=s,a_0=a,\pi \right]\\ & =E\left[r_0+\sum _{t=1}^{+\infty }{\gamma }^t{r}_t|s_0=s,a_0=a,\pi \right]\end{array}$$

引入記號
$$G_{\tau }=\sum _{t=0}^{+\infty }{\gamma }^t{r}_{t+\tau }$$

代入上式
$$\begin{array}{r}E\left[r_0+\sum _{t=1}^{+\infty }{\gamma }^t{r}_t|s_0=s,a_0=a,\pi \right]\\ =r(s,a)+\gamma E\left[G_1|s_0=s,a_0=a,\pi \right]\end{array}$$

接下來處理$E\left[G_1|s_0=s,a_0=a,\pi \right]$，
$$\begin{gathered} E\left[G_1|s_0=s,a_0=a,\pi \right] \\ =\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)E[G_1|s_0=s，a_0=a,s_1=s^{\prime },\pi ] \end{gathered}$$

因為是stationary policy，
$$E[G_1|s_0=s，a_0=a,s_1=s^{\prime },\pi ]=E[G_1|s_1=s^{\prime },\pi ]=V^{\pi }(s^{\prime })$$

綜上
$$Q^{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })$$

到現在，我們用$Q$表示了$V$，也用$V$表示了$Q$，可以考慮代入消元了
$$\begin{array}{rl}{Q}^{\pi }(s,a)& =r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })\\ & =r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\end{array}$$

假設$|S\times A|$有限，則上式就是一個有$|S\times A|$個方程的線性方程組，求解出$Q$之后自然可以得到$V$的表達式。

總結

以上是生活随笔為你收集整理的UA CSC696H 强化学习理论选讲1 强化学习概览的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。