反向強化學習3——求解線性規劃

來自專欄無痛的機器學習7 人贊了文章

本文收錄在無痛的機器學習第二季目錄中。

線性規劃求解過程

在上一節我們介紹了反向強化學習的公式形式，接下來我們就要完成求解了。這個問題本質上是一個線性規劃的問題，但是目前的公式形式還不是一個易於求解的形式，於是我們要把公式進行轉變，採用變數替換的方式，將問題變換成標準的線性規劃形式。這裡涉及兩個變數替換：

?

於是可以得到：

?

s.t.

?，?

? ，?

?

?

當我們將公式變成這個形式後，就可以進行求解了。我們可以從項目https://github.com/MatthewJA/Inverse-Reinforcement-Learning中找到關於這個問題的求解，具體的實現在irl/linear_irl.py中的irl函數，下面就來看看它是如何進行求解的。

代碼中使用了cvxopt這個庫，它實現常見的凸優化演算法，其中也包括線性規劃的求解方法。想要使用這個演算法庫進行求解，我們需要將問題整理成下面的形式：

?

s.t.

?

其中A?為矩陣，b、c?為向量。最終我們將?A、b?、c?三部分輸入到函數中，就可以利用演算法庫中的線性規劃演算法進行求解。

那麼，上面的公式該怎麼變成這個樣子呢？我們可以看到，為了方便計算，此時我們共有三組變數R?，T?和U?，三組變數的長度都是? ，所以我們的目標函數就變成了：

?

接下來按照這樣的形式，我們可以得到下面的條件約束，其中每一個表達式的維度都是(? )，每個表達式的N?有所不同，但是 ?是一樣的：

?上面的公式還是不夠詳細，更為更詳細的內容如圖所示。

按照圖14-1將數據組織好，我們就可以求解得到回報向量了。

實際案例

看完了上面的演算法，我們來看一個具體的例子，這個例子是Grid World。Grid World是一個很簡單的問題，我們給定一個?N* N的棋盤格，這個棋盤格上的每一個格子都可以作為落腳地。如圖所示，我們可以用5 * 5?的格子舉例子。

站在棋盤的格子上會產生不同的效果，棋盤格的最右下方是一個會得到獎勵的格子，站在上面會獲得1分，遊戲結束。站在其他的格子上不會獲得獎勵，遊戲仍會繼續。

玩家在初始狀態下會隨機站在某個格子上，接下來的每一個時刻，玩家都可以做出決定，選擇上下左右4個方向行進。但是世事無常，有時我們並不能到達我們想去的地方，遊戲中存在著一股「妖風」，它會以一定的概率觸發。觸發後玩家的行進將不受控制，會任意選擇一個方向前進，如果撞到棋盤的邊緣，玩家將被阻擋在那裡，停止前進。

整個遊戲的規則並不複雜，站在我們的角度看，因為右下角是得分點，因此我們只要不停地向那個方向前進就可以了；如果已經到達了那裡，那麼保持停留就可以。

如果我們換一個思路：我們並不知道遊戲的得分規則，只能看到一個老玩家的操作（這樣簡單的遊戲，相信老玩家也不會太老）。我們能不能通過老玩家的操作推斷出得分規則呢？這就是基於Grid World的反向強化學習問題。

由於這個問題並不複雜，我們可以用表格的方式表示問題中的策略、回報和價值向量，運用上面的演算法，我們可以得到最終的結果，如圖所示。

從圖的結果可以看出，我們復原的這個?的Reward結果和真實結果相差很小，或者說這點差距並不能阻礙我們選出正確的策略。這樣我們就完成了對這個問題的介紹。