楊 瑞

（天津大學(xué)數(shù)學(xué)學(xué)院 天津 300072）

1 引言

強(qiáng)化學(xué)習(xí)（Reinforcement Learning）［1］是解決這樣一個(gè)問(wèn)題的機(jī)器學(xué)習(xí)分支:智能體（Agent）與環(huán)境交互，如何自動(dòng)地學(xué)習(xí)到最佳策略以使自身獲得最大回報(bào)（Rewards）。最近 AlphaGo［2］擊敗了人類頂尖圍棋職業(yè)選手，其核心技術(shù)之一就是強(qiáng)化學(xué)習(xí)。強(qiáng)化學(xué)習(xí)在現(xiàn)代人工智能學(xué)中有著舉足輕重的地位，有著廣泛的應(yīng)用前景［3～4］。

強(qiáng)化學(xué)習(xí)是一種不告訴Agent如何去正確地決策，而是讓Agent自己去探索環(huán)境，在與環(huán)境交互的過(guò)程獲得知識(shí)，不斷優(yōu)化策略。Agent 與環(huán)境交互的過(guò)程如下:

1）Agent感知當(dāng)前環(huán)境狀態(tài)s；

2）針對(duì)當(dāng)前環(huán)境狀態(tài)s，Agent根據(jù)當(dāng)前行為策

馬爾科夫決策過(guò)程（MDPs）是強(qiáng)化學(xué)習(xí)的基本框架［5］，可以由四元組＜ S ，A ，P，R＞來(lái)表達(dá)。 S 是系統(tǒng)的有限狀態(tài)集，A 是Agent 的有限動(dòng)作空間，動(dòng)作用來(lái)控制系統(tǒng)的狀態(tài)轉(zhuǎn)移，:S×A×S'→[0,1]為Agent執(zhí)行動(dòng)作a 之后，系統(tǒng)由狀態(tài)s轉(zhuǎn)向s'的概率。:S'×A×S'→1R 表示當(dāng) Agent 執(zhí)行動(dòng)作a，系統(tǒng)由狀態(tài)s 轉(zhuǎn)到狀態(tài) s'后，系統(tǒng)反饋給略選擇一個(gè)動(dòng)作a；

3）當(dāng)Agent選擇a，環(huán)境由狀態(tài)s 轉(zhuǎn)移到當(dāng)前狀態(tài) s'，并給出獎(jiǎng)賞值（Rewards）R；

4）環(huán)境把R反饋給Agent。

如此循環(huán)此過(guò)程，直至終止?fàn)顟B(tài)，在這個(gè)過(guò)程中，并沒(méi)有告訴Agent 如何采取動(dòng)作，而是Agent 根據(jù)環(huán)境的反饋?zhàn)约喊l(fā)現(xiàn)的。

1.1 馬爾科夫決策過(guò)程（MDPs）

Agent的rewards。

策略（policy）定義了Agent 在給定狀態(tài)下的行為方式，策略決定了 Agent 的動(dòng)作。 π:S×A →[0,1]，π（s,a）表示在狀態(tài)s 下，執(zhí)行動(dòng)作 a 的概率。

在MDP 中，還定義了兩種值函數(shù)（Value Function）:狀態(tài)值函數(shù)Vπ(s)（State Value Function）和狀態(tài)-動(dòng)作值函數(shù) Qπ(s,a)（State-act Value Function）。

Vπ(s)表示 Agent 從狀態(tài) s 開始，根據(jù)策略 π 所獲得的期望總回報(bào)（Rewards）:

類似地:

值函數(shù)的確定了從一個(gè)狀態(tài)出發(fā)，按照π 所能獲得的期望總回報(bào)。

1.2 Bellman 方程

由于MDP 中，狀態(tài)轉(zhuǎn)移滿足Markov 性，1957年，Bellman證明了他的著名方程［6］:

類似地:

由此可知:系統(tǒng)的狀態(tài)轉(zhuǎn)移矩陣和回報(bào)均已知，則易求出Vπ(s)和 Qπ( )s,a強(qiáng)化學(xué)習(xí)的目標(biāo)是導(dǎo)出最優(yōu)策略π*:

1.3 模型未知的強(qiáng)化學(xué)習(xí)

MDPs 為強(qiáng)化學(xué)習(xí)提供了統(tǒng)一的框架，但實(shí)際問(wèn)題中有如下幾個(gè)問(wèn)題:

1）“維數(shù)災(zāi)難”:狀態(tài)空間超級(jí)巨大，要學(xué)習(xí)的參數(shù)隨著狀態(tài)空間的維數(shù)指數(shù)級(jí)爆炸。

2）收斂速度慢:很多強(qiáng)化學(xué)習(xí)算法的收斂性分析都要依賴“任意狀態(tài)都要被無(wú)數(shù)次訪問(wèn)到”這樣的前提條件。

3）很多實(shí)際問(wèn)題，我們是無(wú)法獲得系統(tǒng)的狀態(tài)轉(zhuǎn)移概率和回報(bào)函數(shù)的，對(duì)這種情況建立模型的算法稱為模型未知的強(qiáng)化學(xué)習(xí)算法。

最近，有研究人員提出 Q(σ) 算法來(lái)估計(jì)Qπ(s,a)，并且原文作者通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)收斂效果很好。本文將對(duì)Q(σ)的收斂性給予一個(gè)證明。

2 時(shí)間差分學(xué)習(xí)算法框架

時(shí)間差分算法（Temporal Difference）是強(qiáng)化學(xué)習(xí)最核心的一類算法，這項(xiàng)工作首次是在Suton 1988［7］年提出的。這類算法不需要知道系統(tǒng)的狀態(tài)轉(zhuǎn)移矩陣，能夠直接學(xué)習(xí)。假設(shè)Agent 在與環(huán)境交互中產(chǎn)生的一個(gè)軌道為

其中sT是終止?fàn)顟B(tài)。

2.1 Sarsa算法

Sarsa［8］算法是根據(jù)上述軌跡來(lái)迭代 Bellman 方法的解，其名稱是由Agent學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)而來(lái)的，數(shù)據(jù)是由一個(gè)(st,at)轉(zhuǎn)移到下一個(gè)(st+1,at+1)的五元組(st,at,rt+1,st+1,at+1)

Sarsa估值計(jì)算公式為

α 為學(xué)習(xí)率，δ 稱為Sarsa算法的時(shí)間差分。

2.2 Expected Sarsa算法

Expected Sarsa［9］:

由Sarsa 和Expected Sarsa 的迭代形式可知，Sarsa 是一個(gè)全采樣的算法，即在t 時(shí)刻，只用rt+1+γQt(st+1,at+1) 來(lái)作為目標(biāo)（target）進(jìn)行估值。而Expected sarsa 是采用下一狀態(tài)st+1的Q 值的期望 :來(lái)估值。根據(jù)Bellman 等式（4），從直覺(jué)上講，Expected Sarsa 的估值要穩(wěn)定一些［10］。首次證明了 Expected Sarsa 和Sarsa 有相同的 bias，但是 Expected Sarsa 的方差更小一些。

2.3 Q(σ) 算法

Q(σ)［11］算法的設(shè)計(jì)思想是:引入了參數(shù) σ ，σ是采樣的程度，如果σ=0，表示no-sampling，σ=1表示full-sampling。

單步Q(σ)算法的迭代形式:

2.4 多步時(shí)間差分算法

Sarsa，Expected Sarsa，Q(σ)［12～14］均可以推廣至多步的情況。

2.4.1 多步Sarsa

多步Sarsa值函數(shù)的估計(jì)公式:

多步Sarsa值函數(shù)的更新公式:

2.4.2 多步Expected Sarsa 算法，也稱多步Tree Backup算法

多步Expected Sarsa也是類似的，但有一些差別。

多步 Expected Sarsa［11］值函數(shù)的估計(jì)公式:

多步Expected Sarsa值函數(shù)的更新公式:

2.4.3 多步 Q(σ)

多步Q(σ)值函數(shù)的估計(jì)公式:

多步Q(σ)值函數(shù)的更新公式:

3 Q(σ)算法的收斂性分析

引理 1［15～16］:假設(shè)一個(gè)隨機(jī)過(guò)程 (ζt,Δt,Ft) ，ζt,Δt,Ft:X → R 滿足方程:

這里 xt?X,t=0,1,2,… 假設(shè) Pt是 σ -fields 的遞增序列，ζ0，Δ0是 P0-measurable，ζt，Δt以及Ft-1是 Pt-measurable，t ≥1。假定以下條件成立:

1）X是有限集；

2）ζt( xt)?[0 ,1],∑tζt( xt)=∞,∑t(ζt( xt))2＜ ∞

w.p.1且?x ≠ xt:ζt( x )=0；

3）∥E{Ft|Pt} ∥≤ κ ∥ Δt∥ +ct，κ ?[ 0,1),ct依概率收斂于0；

4）Var{Ft( xt)|Pt} ≤K(1 +κ ∥ Δt∥ )2,K 是常數(shù)。

其中∥?∥表示最大模；則Δt依概率收斂到0。

定理1:在MDP 框架下，對(duì)于任意的初始化Q( s,a), ? γ ? ( 0,1) 。

Q的更新按以下方式:

令 Δn=-Qπ(s,a) ，則 有 ||Δn+1||≤γ||Δn||，Δn按最大值范數(shù)是壓縮序列，即 Δn依概率收斂于0。

證明:由數(shù)學(xué)歸納法證明之。

For n=1:

假設(shè)對(duì)n也成立:

這里I( )a?,at+1是一個(gè)指示函數(shù):

定理2:在MDP 框架下，對(duì)于任意的初始Q( s,a),? γ ?( 0,1) 。

事實(shí)上，如果定理1中的 π(st+1,a?)滿足:

則這就是式（11）所表示的算法，也即是定理1中算法的特殊情況，由定理1 的收斂性可以得到該算法也是收斂的。

定理3:如果Q(σ)算法滿足條件:

1）狀態(tài)空間是有限集；

則Q(σ) 迭代產(chǎn)生的Qt(s,a) 依概率收斂于Qπ(s,a)。

定理3的證明:

Q(σ)是定理1 和定理2 所述算法的凸組合，易知 Q(σ) 迭代產(chǎn)生的 Qt(s,a) 依概率收斂于Qπ(s,a)。

4 結(jié)語(yǔ)

本文以時(shí)間差分學(xué)習(xí)算法為主線，系統(tǒng)簡(jiǎn)要地介紹了強(qiáng)化學(xué)習(xí)中的幾個(gè)重要估值算法，并對(duì)最近提出的一個(gè)新的時(shí)間差分學(xué)習(xí)算法Q(σ)算法作了理論分析，同時(shí)給出了Q(σ)算法的收斂性證明，這在強(qiáng)化學(xué)習(xí)理論研究中具有重要意義。