Q-learning「房間問題」演算法的一個通用實現方法

在閱讀本文之前，請先對強化學習，Q-learning以及房間問題有一個初步的了解。可以參考下面這兩個鏈接：

Q-learning Step by Step Tutorial

「房間問題」簡單來說就是終點確定的最短路徑尋找問題，但是個單目標優化問題，也就是說僅僅只需要考慮路程最短，不需要考慮其它成本。在眾多關於Q-learning與「房間問題」的入門介紹的文章中，無一不是參考了上面兩篇文章中的方法。這個方法具有很好的可理解性，並可以快速的梳理出實現Q-learning的一般步驟，但存在一個很嚴重的問題，即需要人工給出Reward Matrix（獎勵矩陣），這樣很大程度上就限制了其通用性。面對一個僅有6個房間的問題，畫出節點圖，手工寫出獎勵矩陣並非難事，但如果是100個房間，10000個房間呢？這就比較難了，不僅手寫獎勵矩陣很困難，也會極大的增加訓練的時間複雜度。為什麼這麼說，還是用6個房間的這個例子比較好解釋。在建立Q-learning中被用來訓練更新的Q-Table時，通常以狀態(state)為行，動作(action)為列，但實際上在「6個房間問題」里，卻用的是當前狀態(current state)為行，下一狀態(future state)為列。所以需要一個6x6的Q-table：

在Q-learning演算法的實現過程中，每次的訓練都會有由state去確定action的步驟，即找到可行的action並確定下一個state，相應的Q-Table可以表示成Q(S, A)。也就是依據current state找尋future state，在確定當前狀態後，找尋可能的action和需要遍歷所有的未來狀態，對於「6個房間問題」而言，需要循環6次。假設對於某一特定的狀態可行的action和future state有n個，那麼在對這n個結果求解其Q(future state, fucture action)中的最大值，至少需要6(n - 1)次循環，如果加上action確定的6次循環，則一次迭代至少需要6n次。想像一下，如果是1920x1080個房間呢？毫無疑問運算量將大大增加。

通用方法

在此之前可先閱讀這兩篇文章:

強化學習(Q-learning~了解了一波

以上兩篇文章都是關於一維空間尋最短路徑的問題，其中的action只有左右兩個選項。然而對於一個二維平面的最短路徑尋找問題(Path-Finding)，處在任何一個狀態的動作都只有4個選項，上下左右，所以這個Q-Table也可以寫成如下形式（UDLR分別代表上下左右）：

這種6x4的矩陣才是通用方法中的Q-Table，即使state多達10000個，矩陣的維度也只有10000x4，遠小於第一種方法的10000x10000。使用這個形式Q-Table的關鍵問題在於如何由action獲得下一個的state，也就是action到state的轉化問題。還是以「6個房間問題」為例子，通過抽象化的處理，我可以把左邊這副實際的房間分布圖轉換成右邊的示意圖。

示意圖對原圖中房間的重新編號與新添的3號房間對最終結果並無任何影響。原先的0號房間編程了5號，1號成了4號，2號變為0號，3號變為1號， 4號成了2號，5號變成了6號。狀態0的action矩陣可以寫為：

在Action矩陣中，0表示路線被隔斷，1表示路線通暢。對於A0來說，只有向右的action是可以通暢的轉往狀態1的。可以很快的寫出A0~A6的Action矩陣，如若僅自動識別可行的action，4x6次循環即可，而如果是遍歷和每一個state的關聯，則需6x6次循環，效率的提升不言而喻。Action轉換為state的基本思想其實也很簡單，假設當前處在第r個房間也就是狀態r（總共有MxN個房間，M為列數，N為行數），其上下左右的狀態分別為，r-M

，r+M，r-1，r+1，處在邊界的狀態再特殊考慮：

基本的原理就是這樣了。

如需原碼，請參考鏈接：

https://github.com/JinyuGuan/Q-learning-Room-Problem.git

JinyuGuan/Q-learning-Room-Problem?

github.com
推薦閱讀：