區(qū)分Continuing Task和Episodic Task

前一節(jié)我們已經(jīng)解釋了什么是episode，episode即為從初始的狀態(tài)到終止狀態(tài)的整個過程。那么什么是Continuing Task婉称？ 什么是Episodic Task呢？其實，兩者最根本的區(qū)別就是Continuing Task是無法確認最終的終止狀態(tài)靠汁，其動作狀態(tài)會一直發(fā)生下去的即為Continuing Task。與此相反闽铐，Episodic Task是擁有有限長度的狀態(tài)蝶怔，也就是知道最終的結(jié)束狀態(tài)。

強化學習分類

強化學習基本上可以分為兩大類兄墅。第一類是有模型的強化學習踢星，另一類為無模型的強化學習。模型可以簡單地理解為transition-state probability隙咸。而動態(tài)規(guī)劃(Dynamic Programming)就是一個基于有模型的強化學習方法沐悦。分類圖如下所示：

強化學習分類

動態(tài)規(guī)劃(Dynamic Programming)

根據(jù)前面推導出來的Value Functions的表達公式，我們可以看出當前狀態(tài)的值可以通過接下來的狀態(tài)值計算出來五督。但是藏否，這兩個狀態(tài)的值函數(shù)我們都不知道。因此充包，該算法也被稱為自舉(bootstrapping)副签。接下來我們先看看動態(tài)規(guī)劃方法如何對policy來進行評估的遥椿。

策略評估(Policy Evaluation)

如何來評估策略的好壞呢？這時候我們需要從數(shù)學的角度出發(fā)淆储，也就是要通過數(shù)值的方式來對策略進行評估冠场。數(shù)值大代表策略好，數(shù)值小代表策略不是很好本砰，我們很容易就會想到Value Functions碴裙。

根據(jù)Bellman Equation我們得到state value的計算公式如下：

iterative policy evaluation

于是，我們就可以通過一次次的迭代來得到該policy的state value了点额。其偽代碼如下：

policy evaluation 偽代碼

從偽代碼中舔株，我們可以知道Policy Evaluation是對一個Policy進行計算的。當我們更新的state value值幾乎不變時咖楣，就可以讓其停止迭代了督笆。

列1:?我們有一個Gridworld的游戲，其中有2個終點诱贿，1-14數(shù)字分別代表14個不同的狀態(tài)(state)娃肿，我們可以朝四個方向走(上下左右)，也就是代表了我們的動作(action)珠十，每一次狀態(tài)的改變都會得到-1的獎勵料扰。游戲如下圖所示：

Gridworld Game

通過Iterative Policy Evaluation方法進行迭代，我們得到前兩次迭代的state value矩陣焙蹭。如下所示：

policy evaluation example

我們來看一下k=2時晒杈，-1.7是怎么計算出來的。因為我們可以采取4個動作孔厉，所以每個動作的概率都為0.25, 而在狀態(tài)1的位置上拯钻，其可以向左、向右撰豺、向下和原地不動粪般。因此，其state value就等于(0.0 * 0.25) + (-1 * 0.25) + (-1 * 0.25) + (-1 * 0.25) = -1.75污桦，四舍五入即為-1.7亩歹。

策略提升(Policy Improvement)

我們進行策略評估的目的就是為了找到最優(yōu)的策略。還是拿列1來舉例凡橱，當k=2時小作，我們已經(jīng)計算出了各個狀態(tài)下的state value，比如我們在狀態(tài)2的情況下稼钩，為了轉(zhuǎn)換到更好的狀態(tài)顾稀，我們就朝四個方向觀察一番，發(fā)現(xiàn)通過向左走可以得到更多(-1.7 > -2.0)的獎勵坝撑，于是我們便采取向左的動作础拨，使狀態(tài)轉(zhuǎn)換到了狀態(tài)1氮块。這就是策略提升。

通過例子诡宗，我們可以知道我們在狀態(tài)不好的情況下采取相應行動轉(zhuǎn)換到比較好的狀態(tài)的值(也就是action value)一定會大于當前狀態(tài)不好的值(state value)。通過公式推導击儡，我們只需要選擇state value值大的地方執(zhí)行策略即可塔沃。公式推導如下：

公式推導1

因此，我們可以使用貪婪策略(greedy policy)阳谍，也就是取其最大值蛀柴，來得出最優(yōu)的策略(在當前狀態(tài)下應該采取的動作)和最優(yōu)的state value。公式如下所示：

optimal policy

optimal state value

策略迭代(Policy Iteration)

策略迭代就是結(jié)合了策略評估和策略提升矫夯，通過一次次的迭代來得到最優(yōu)的策略鸽疾。如圖：

策略迭代

其中E表示進行一次Policy Evaluation，I表示進行一次Policy Improvement训貌，*表示最優(yōu)解制肮，0-n表示進行了多少次迭代。偽代碼如下所示：

Policy Iteration Code

值迭代(Value Iteration)

根據(jù)策略迭代算法递沪，每一次迭代都要進行策略評估和策略提升豺鼻，直到二者都收斂】羁可我們的目標是選出最優(yōu)的策略儒飒，那么有沒有可能在策略評估值沒有收斂的情況下，最優(yōu)策略已經(jīng)收斂了呢檩奠？答案是有這個可能桩了。我們還拿例1來看，迭代步驟如下所示：

Gridworld Game

可以看出當?shù)谌螘r埠戳，policy已經(jīng)收斂了井誉，因此無需再對其做策略評估。值迭代過程就是運用了這一點的原理乞而，使用縮減過的策略評估在每次迭代中送悔，都會求最大的policy值，直到其策略收斂爪模。其公式欠啤，偽代碼如下：

Value Iteration

偽代碼

GridWorld 部分代碼

代碼1

代碼2

Reference

1. Reinforcement Learning An Introduction

2.強化學習入門 第二講 基于模型的動態(tài)規(guī)劃方法?https://zhuanlan.zhihu.com/p/25580624

3.Github: Reinforcement Learning An Introduction?https://github.com/ShangtongZhang/reinforcement-learning-an-introduction