UA CSC696H 强化学习理论选讲1 强化学习概览
UA CSC696H 強化學習理論選講1 強化學習概覽
- 強化學習相關概念
- Markov Decision Processes(MDP)簡介
- Policy Evaluation
強化學習(reinforcement learning, RL)研究智能體(intelligent agents)在給定情景下為了最大化累積獎勵(cumulative reward)應該如何采取行動(take actions)。按照這個描述,在應用強化學習時,至少需要明確應用情景、獎勵函數、以及可行的行動方案。比如要設計一個能自動開方子的智能體,就可以設想一個患者定期來問診的場景,第ttt期患者前來問診時智能體獲得患者當前身體狀況xtx_txt?作為輸入,同時開出這一期的方子ata_tat?,把患者按這個方子抓藥服用后健康狀況增益作為當期獎勵rtr_trt?,設計這個智能體的目標定為最大化患者的長期身體健康狀況∑rt\sum r_t∑rt?。
但這個專題課我是旁聽的,課程內容并不是強化學習的具體應用和算法,而是強化學習的理論基礎與分析強化學習算法的數學工具。其中理論基礎部分主要涉及Markov Decision Process、Optimization、Probability Contraction等,分析的強化學習performance用到的指標主要包括online regret(簡單來說就是如果從前我那樣做了,累積獎勵會不會更高,分析算法理論性質時我們希望是不會), sample complexity(希望用盡可能少的行動獲得最高獎勵,主要是因為造訓練數據很貴), computational complexity(計算復雜度當然是越低越好)。這一講是第一講,主要是敘述一些與強化學習有關的概念,并簡單引入Markov Decision Process。
強化學習相關概念
Online Supervised Learning
以垃圾郵件自動過濾器為例,用t=1,?,Tt=1,\cdots,Tt=1,?,T表示收到郵件的時間點;在第ttt次收到郵件xtx_txt?時,過濾器根據xtx_txt?做出關于這封郵件是否是垃圾郵件的判斷y^t\hat y_ty^?t?(用{(xs,ys)}s=1t?1\{(x_s,y_s)\}_{s=1}^{t-1}{(xs?,ys?)}s=1t?1?訓練過濾器并完成預測,目標是最小化誤判總數),同時記錄下郵箱用戶看到這封郵件后的判斷yty_tyt?;這個例子中預測基于實時樣本進行,并且樣本中有label,每一次進行預測時都是監督學習的框架,所以是一個online supervised learning,設計相關算法時需要著重考慮過濾器的泛化能力,也就是如何保證收到第ttt封郵件時的實時樣本{(xs,ys)}s=1t?1\{(x_s,y_s)\}_{s=1}^{t-1}{(xs?,ys?)}s=1t?1?中關于垃圾郵件分類的知識能夠遷移到xtx_txt?上。
Online Bandit Learning
用前文的自動開方子智能體作為例子,設想一個患者定期來問診的場景,第ttt期患者前來問診時智能體獲得患者當前身體狀況xtx_txt?作為輸入,同時開出這一期的方子ata_tat?,把患者按這個方子抓藥服用后健康狀況增益作為當期獎勵rtr_trt?,設計這個智能體的目標定為最大化患者的長期身體健康狀況∑rt\sum r_t∑rt?。這就不是online supervised learning了而是online bandit learning,因為在第ttt期做行動決策時已知信息只有xtx_txt?,以及{at},{rt}\{a_t\},\{r_t\}{at?},{rt?}。
Multi-armed bandits也是Online Bandit Learning中的一類,它可以用來解決exploration-exploitation trade-off的問題。比如要考慮接下來一學期中午吃黃燜雞米飯、隆江豬腳飯、重慶雞公煲還是咸肉菜飯,假設我們沒有關于這幾家店的先驗信息,而目標是最大化自己這學期午飯的體驗。按Multi-armed bandits的思路,我們首先應該先來體驗一下這幾家店,也就是exploration,但是不能只去一次,畢竟去一次有可能遇到老板和老板娘吵架影響用餐體驗,應該每家店都多去幾次,獲得多個體驗感的記錄,每多獲得一次記錄都可以重新計算各店體驗感的置信區間,根據置信區間選擇下一次午飯吃哪家。這樣做的好處是在exploration的同時收集數據,盡量降低潛在的bias。
Online Episodic RL
這類問題例子如下,在這一關中,小A應該怎么操作才能盡快拿到小星星。
假設ttt表示關卡或者章節(episodic),每一關初始狀態為s1ts_1^ts1t?,用hhh表示這一關的第hhh次操作,ahta_h^taht?表示這次操作采取的行動,獎勵為rht~R(?∣sht,aht)r_h^t\sim R(\cdot|s_h^t,a_h^t)rht?~R(?∣sht?,aht?),狀態轉移函數為sh+1t~P(?∣sht,aht)s_{h+1}^t \sim P(\cdot|s_h^t,a_h^t)sh+1t?~P(?∣sht?,aht?),比如在上圖中,記A左下格子為(1,1)(1,1)(1,1),則星星的位置為(5,4)(5,4)(5,4),A的初始狀態為s1t=(2,2)s_1^t=(2,2)s1t?=(2,2),每一次可以采取的行動為{x→x+1,x→x?1,y→y+1,y→y?1}\{x \to x+1,x \to x-1,y \to y+1, y \to y-1\}{x→x+1,x→x?1,y→y+1,y→y?1},獎勵函數為R=1(5,4)R=1_{(5,4)}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,γ,μ)M=(S,A,P,r,\gamma,\mu)M=(S,A,P,r,γ,μ)
其中SSS表示state space,AAA表示action space,PPP代表transition kernel(用來表示uncertainty in the environment),當前狀態為sss,采取行動aaa,則下一期狀態為s′s's′的概率可以表示為P(s′∣s,a)P(s'|s,a)P(s′∣s,a),r:S×A→[0,1]r:S \times A \to [0,1]r:S×A→[0,1]代表reward function,γ∈[0,1)\gamma \in [0,1)γ∈[0,1)是折現因子,μ\muμ是initial state distribution。
用上面那個小A找小星星的例子說明怎么用MDP來建模,思路很簡單,就是把MDP的相關參數寫出來就好。
S={1,2,3,4,5,6}×{1,2,3,4,5}A={上,下,左,右,不動}S = \{1,2,3,4,5,6\} \times \{1,2,3,4,5\} \\ A = \{上,下,左,右,不動\}S={1,2,3,4,5,6}×{1,2,3,4,5}A={上,下,左,右,不動}
狀態轉移是確定的,所以transition kernel可以用identity function表示,比如
P(s′∣(2,2),上)=1(2,3)={0,s′≠(2,2)1,s′=(2,2)P(s'|(2,2),上)=\textbf 1_{(2,3)} = \begin{cases} 0, s' \ne (2,2) \\ 1,s' = (2,2) \end{cases}P(s′∣(2,2),上)=1(2,3)?={0,s′?=(2,2)1,s′=(2,2)?
而只有到達小星星的位置才有獎勵,所以
r(s,a)=1(5,4)r(s,a) = \textbf 1_{(5,4)}r(s,a)=1(5,4)?
Initial state是給定為(2,2)(2,2)(2,2)的,
μ(s)=1(2,2)\mu(s) = \textbf 1_{(2,2)}μ(s)=1(2,2)?
因為中間步驟沒有獎勵,所以折現因子大于0即可。這樣我們就用MDP的語言描述了小A找小星星的例子。
接下來我們給出MDP更具體的描述:
智能體采取行動ata_tat?;
智能體獲得獎勵rt=r(st,at)r_t=r(s_t,a_t)rt?=r(st?,at?)
智能體轉移到下一個狀態st+1~P(?∣st,at)s_{t+1} \sim P(\cdot|s_t,a_t)st+1?~P(?∣st?,at?)
在這個過程中,到第ttt步完成時,智能體記錄下的數據為
(s0,a0,r0,?,st,at,rt,st+1)∈(S×A×[0,1])t×S?Ht(s_0,a_0,r_0,\cdots,s_t,a_t,r_t,s_{t+1}) \in (S \times A \times [0,1])^{t} \times S \triangleq H_t(s0?,a0?,r0?,?,st?,at?,rt?,st+1?)∈(S×A×[0,1])t×S?Ht?
這里HtH_tHt?表示智能體的歷史數據集合。另外,智能體的目標是最大化獎勵的期望現值:
E[G0]=E[∑t=0+∞γtrt]E[G_0]=E \left[\sum_{t=0}^{+\infty} \gamma^t r_t\right]E[G0?]=E[t=0∑+∞?γtrt?]
因為定義獎勵是屬于[0,1][0,1][0,1]的,所以
∑t=0+∞γtrt≤∑t=0+∞γt=11?γ\sum_{t=0}^{+\infty} \gamma^t r_t \le \sum_{t=0}^{+\infty} \gamma^t = \frac{1}{1-\gamma}t=0∑+∞?γtrt?≤t=0∑+∞?γt=1?γ1?
γ\gammaγ越大,折現效應越弱,未來獎勵占比會增加,智能體傾向于長期決策;γ\gammaγ越小,折現效應越強,折現后的獎勵主要由近期獎勵構成,智能體傾向于更高的近期獎勵。
Policy Evaluation
Policy的含義
盡管上文給出了用MDP來描述動態決策過程的一些思路,但我們對智能體行為的了解還只停留在具體的某一步選擇什么行動上,為了對智能體整體的行為模式建模,我們需要用到Policy。記
H=?t=0+∞HtH = \bigcup_{t=0}^{+\infty}H_tH=t=0?+∞?Ht?
Policy用π\piπ表示,它是定義在AAA上關于HHH生成的Filter的條件概率,也就是當智能體的歷史記錄為τt\tau_tτt?時,采取行動aaa的概率可以記為π(a∣τt)\pi(a|\tau_t)π(a∣τt?)。如果π(a∣τt)=π(a∣st)\pi(a|\tau_t)=\pi(a|s_t)π(a∣τt?)=π(a∣st?),就稱這樣的Policy為stationary policy。
Value Function的定義
Value function的作用是評估policy,也就是評估智能體的整體行為,它的定義是
Vπ(s)=E[G0∣s0=s,π]V^{\pi}(s)=E[G_0|s_0=s,\pi] Vπ(s)=E[G0?∣s0?=s,π]
比較理想的Policy滿足?s∈S\forall s \in S?s∈S,Vπ(s)V^{\pi}(s)Vπ(s)都已經是最大值了,也就是不管初始狀態如何,我們理想中的最優Policy都應該最大化Value function。看起來這個理想好像很遠大,但現有結果說明,至少存在一個deterministic、stationary π\piπ能達到這種最優。
Value Function的計算
雖然實踐中可以用MC simulation等辦法估計value function,但既然我們要從理論上研究MDP,那還是要嘗試找出解析式的。下面討論stationary policy的情況,
Vπ(s)=E[G0∣s0=s,π]=∑a∈Aπ(a∣s)E[G0∣s0=s,a0=a,π]=∑a∈Aπ(a∣s)Qπ(s,a)\begin{aligned}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{aligned}Vπ(s)?=E[G0?∣s0?=s,π]=a∈A∑?π(a∣s)E[G0?∣s0?=s,a0?=a,π]=a∈A∑?π(a∣s)Qπ(s,a)?
這里Qπ(s,a)=E[G0∣s0=s,a0=a,π]Q^{\pi}(s,a)=E[G_0|s_0=s,a_0=a,\pi]Qπ(s,a)=E[G0?∣s0?=s,a0?=a,π]也是一類value function。
Qπ(s,a)=E[G0∣s0=s,a0=a,π]=E[∑t=0+∞γtrt∣s0=s,a0=a,π]=E[r0+∑t=1+∞γtrt∣s0=s,a0=a,π]\begin{aligned}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{aligned}Qπ(s,a)?=E[G0?∣s0?=s,a0?=a,π]=E[t=0∑+∞?γtrt?∣s0?=s,a0?=a,π]=E[r0?+t=1∑+∞?γtrt?∣s0?=s,a0?=a,π]?
引入記號
Gτ=∑t=0+∞γtrt+τG_{\tau} = \sum_{t=0}^{+\infty} \gamma^t r_{t+\tau}Gτ?=t=0∑+∞?γtrt+τ?
代入上式
E[r0+∑t=1+∞γtrt∣s0=s,a0=a,π]=r(s,a)+γE[G1∣s0=s,a0=a,π]\begin{aligned} 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{aligned}E[r0?+t=1∑+∞?γtrt?∣s0?=s,a0?=a,π]=r(s,a)+γE[G1?∣s0?=s,a0?=a,π]?
接下來處理E[G1∣s0=s,a0=a,π]E\left[G_1|s_0=s,a_0=a,\pi \right]E[G1?∣s0?=s,a0?=a,π],
E[G1∣s0=s,a0=a,π]=∑s′∈SP(s′∣s,a)E[G1∣s0=s,a0=a,s1=s′,π]E\left[G_1|s_0=s,a_0=a,\pi \right] \\ = \sum_{s' \in S}P(s'|s,a)E[G_1|s_0=s,a_0=a,s_1=s',\pi]E[G1?∣s0?=s,a0?=a,π]=s′∈S∑?P(s′∣s,a)E[G1?∣s0?=s,a0?=a,s1?=s′,π]
因為是stationary policy,
E[G1∣s0=s,a0=a,s1=s′,π]=E[G1∣s1=s′,π]=Vπ(s′)E[G_1|s_0=s,a_0=a,s_1=s',\pi] = E[G_1|s_1=s',\pi]=V^{\pi}(s')E[G1?∣s0?=s,a0?=a,s1?=s′,π]=E[G1?∣s1?=s′,π]=Vπ(s′)
綜上
Qπ(s,a)=r(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)Q^{\pi}(s,a) =r(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)V^{\pi}(s')Qπ(s,a)=r(s,a)+γs′∈S∑?P(s′∣s,a)Vπ(s′)
到現在,我們用QQQ表示了VVV,也用VVV表示了QQQ,可以考慮代入消元了
Qπ(s,a)=r(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)=r(s,a)+γ∑s′∈SP(s′∣s,a)∑a′∈Aπ(a′∣s′)Qπ(s′,a′)\begin{aligned} Q^{\pi}(s,a) & =r(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)V^{\pi}(s') \\ & = r(s,a)+\gamma \sum_{s' \in S}P(s'|s,a)\sum_{a' \in A} \pi(a'|s')Q^{\pi}(s',a')\end{aligned}Qπ(s,a)?=r(s,a)+γs′∈S∑?P(s′∣s,a)Vπ(s′)=r(s,a)+γs′∈S∑?P(s′∣s,a)a′∈A∑?π(a′∣s′)Qπ(s′,a′)?
假設∣S×A∣|S \times A|∣S×A∣有限,則上式就是一個有∣S×A∣|S \times A|∣S×A∣個方程的線性方程組,求解出QQQ之后自然可以得到VVV的表達式。
總結
以上是生活随笔為你收集整理的UA CSC696H 强化学习理论选讲1 强化学习概览的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 量子力学 一 基础8 经典概率与量子概率
- 下一篇: UA OPTI570 量子力学1 电磁波