Q学习（Q-learning）入门小例子及python实现(Meaning)
一、從馬爾科夫過程到Q學(xué)習(xí)
# 有一定基礎(chǔ)的讀者可以直接看第二部分
Q學(xué)習(xí)（Q-learning）算法是一種與模型無關(guān)的強化學(xué)習(xí)算法，以馬爾科夫決策過程（Markov Decision Processes, MDPs）為理論基礎(chǔ)。
標(biāo)準的馬爾科夫決策過程可以用一個五元組<S,A,P,R,γ>表示，其中：
- S是一個離散有界的狀態(tài)空間；
- A是一個離散的動作空間；
- P為狀態(tài)轉(zhuǎn)移概率函數(shù)，表示agent在狀態(tài)s下選取動作a后轉(zhuǎn)移到a’的概率；
- R為回報函數(shù)，用于計算agent由當(dāng)前狀態(tài) 選取動作 后轉(zhuǎn)移到下一狀態(tài) 得到的立即回報值，由當(dāng)前狀態(tài)和選取的動作決定，體現(xiàn)了馬爾科夫性的特點；
- γ是折扣因子，用于確定延遲回報與立即回報的相對比例， 越大表明延遲回報的重要程度越高。
馬爾科夫決策問題的目標(biāo)是找到一個策略 ，使其回報函數(shù) 的長期累積值的數(shù)學(xué)期望
最大。其中，策略π只和狀態(tài)相關(guān)，與時間無關(guān)（靜態(tài)的）。 是t時刻的環(huán)境狀態(tài)， 是t時刻選擇的動作。
根據(jù)Bellman最優(yōu)準則，得到最優(yōu)策略 對應(yīng)的最優(yōu)指標(biāo)為：
其中，R(s,a)為r(st,at)的數(shù)學(xué)期望， 為在狀態(tài)s下選取動作a后轉(zhuǎn)移到下一狀態(tài)狀態(tài)s’的概率。由于某些環(huán)境中狀態(tài)之間的轉(zhuǎn)移概率P不容易獲得，直接學(xué)習(xí) 是很困難的，而Q學(xué)習(xí)不需要獲取轉(zhuǎn)移概率P，因而可用來解決此類具有馬爾科夫性的問題。
Q學(xué)習(xí)是一種與環(huán)境無關(guān)的算法，是一種基于數(shù)值迭代的動態(tài)規(guī)劃方法。定義一個Q函數(shù)作為評估函數(shù)：
評估函數(shù)Q(s,a)的函數(shù)值是從狀態(tài)s開始選擇第一個動作a執(zhí)行后獲得的最大累積回報的折算值，通俗地說，Q值等于立即回報值r(s,a) 加上遵循最優(yōu)策略的折算值，此時的最優(yōu)策略可改寫為：
該策略表達式的意義在于：如果agent用Q函數(shù)代替 函數(shù)，就可以不考慮轉(zhuǎn)移概率P，只考慮當(dāng)前狀態(tài)s的所有可供選擇的動作a，并從中選出使Q(s,a)最大的動作，即agent對當(dāng)前狀態(tài)的部分Q值做出多次反應(yīng)，便可以選出動作序列，使全局最優(yōu)化。
在Q學(xué)習(xí)中，agent由初始狀態(tài)轉(zhuǎn)移到目標(biāo)狀態(tài)的過程稱為“Episode”，即“場景”。Q函數(shù)可以表示為以下的迭代形式進行Q矩陣的更新：
在每一步的迭代中，上式又可寫為：
即Q矩陣(st,at)位置元素的值等于回報函數(shù)R的相應(yīng)值加上折扣因子γ乘以轉(zhuǎn)換到下一個狀態(tài)后最大的Q值。
上述的Q學(xué)習(xí)算法可以看出，當(dāng)劃分的狀態(tài)有限時，每一場景開始時隨機選擇的初始狀態(tài)s在算法的指導(dǎo)下探索環(huán)境，最終一定可以到達目標(biāo)狀態(tài)s*，回報函數(shù)R(s,a)是有界的，并且動作的選擇能夠使每個狀態(tài)映射到動作對的訪問是無限頻率，則整個學(xué)習(xí)過程就能夠訓(xùn)練出來。
Q學(xué)習(xí)通過對環(huán)境的不斷探索，積累歷史經(jīng)驗，agent通過不斷試錯來強化自身，最終可以達到自主選擇最優(yōu)動作的目標(biāo)，即不論出于何種狀態(tài)，都可給出到達目標(biāo)狀態(tài)的最優(yōu)選擇路徑，該算法中環(huán)境和動作相互影響，動作的選擇影響環(huán)境狀態(tài)，環(huán)境也可以通過強化回報函數(shù) 來反饋動作的優(yōu)劣性，影響動作的選擇。
參考文獻：
[1]汪黎明.制造企業(yè)零庫存管理物資調(diào)度方法研究[J].價值工程, 2019,38(23):126-129.
二、由一個廣為流傳的小例子了解Q學(xué)習(xí)的算法邏輯
一個由門連接的建筑物中有五個房間，如下圖所示，分別用0-4號標(biāo)識，將外界看作一個大房間，同樣標(biāo)識為5。
每個房間代表一個節(jié)點，門代表連線，可以將上圖抽象為下面這樣：
agent會被隨機放置在任意一個房間里，然后從那個房間出發(fā)，一直走到建筑外（即5號房間為目標(biāo)房間）。門是雙向的，所以相鄰節(jié)點間是雙向箭頭連接。通過門可以立即得到獎勵值100，通過其他門獎勵值為0。將所有箭頭標(biāo)注獎勵值如下圖：
在Q學(xué)習(xí)中，目標(biāo)是達到獎勵最高的狀態(tài)，所以如果agent到達目標(biāo)，它將永遠在那里。 這種類型的目標(biāo)被稱為“吸收目標(biāo)”。
想象一下，我們的agent是一個想象的虛擬機器人，可以通過經(jīng)驗學(xué)習(xí)。 agent可以從一個房間轉(zhuǎn)移到另一個房間，但它沒有上帝視角，也不知道哪一扇門通向外面。
按照第一部分Q學(xué)習(xí)的理論，我們把每個房間抽象為一個狀態(tài)，選擇進入哪號房間作為動作，把狀態(tài)圖和即時獎勵值放到下面的獎勵值表“回報矩陣R”中：（-1表示不可選擇的動作，兩個狀態(tài)間沒有連接）
現(xiàn)在我們將添加一個類似的矩陣“Q”給我們agent的大腦，代表了通過經(jīng)驗學(xué)到的東西的記憶。 矩陣Q的行表示agent的當(dāng)前狀態(tài)，列表示導(dǎo)致下一個狀態(tài)的可能動作（節(jié)點之間的連線）。
agent開始什么都不知道，矩陣Q被初始化為零。 在這個例子中，為了解釋簡單，我們假設(shè)狀態(tài)的數(shù)目是已知的（六個，0-5）。 如果我們不知道涉及多少個狀態(tài)，矩陣Q可能從只有一個元素開始。 如果找到新的狀態(tài)，則在矩陣Q中添加更多的列和行是一項簡單的任務(wù)。
Q學(xué)習(xí)的更新規(guī)則如下：
根據(jù)這個公式，分配給矩陣Q的特定元素的值等于矩陣R中相應(yīng)值加上學(xué)習(xí)參數(shù)γ乘以下一狀態(tài)下所有可能動作的Q的最大值。
每一場景的探索都會為agent增加經(jīng)驗，Q矩陣得到更新。訓(xùn)練的基本思路如下圖：
基于算法思想，訓(xùn)練Q矩陣的具體流程如下：
步驟1.初始化倉庫環(huán)境和算法參數(shù)（最大訓(xùn)練周期數(shù)，每一場景即為一個周期，折扣因子γ，即時回報函數(shù)R和評估矩陣Q。）。
步驟2.隨機選擇一個初始狀態(tài)s，若s=s*，則結(jié)束此場景，重新選擇初始狀態(tài)。
步驟3.在當(dāng)前狀態(tài)s的所有可能動作中隨機選擇一個動作a，選擇每一動作的概率相等。
步驟4.當(dāng)前狀態(tài)s選取動作a后到達狀態(tài)s’。
步驟5.使用公式對Q矩陣進行更新。
步驟6.設(shè)置下一狀態(tài)為當(dāng)前狀態(tài)，s=s‘。若s未達到目標(biāo)狀態(tài)，則轉(zhuǎn)步驟3。
步驟7.如果算法未達到最大訓(xùn)練周期數(shù)，轉(zhuǎn)步驟2進入下一場景。否則結(jié)束訓(xùn)練，此時得到訓(xùn)練完畢的收斂Q矩陣。
上面的流程是給agent用來學(xué)習(xí)經(jīng)驗的。 每一場景都相當(dāng)于一個培訓(xùn)課程。 在每個培訓(xùn)課程中, agent將探索環(huán)境 (由矩陣R表示), 接收獎勵 (如果有), 直到達到目標(biāo)狀態(tài)。訓(xùn)練的目的是提高我們的agent的 “大腦”（矩陣 Q）。 場景越多，Q矩陣越優(yōu)化。 在這種情況下, 如果矩陣 Q 得到了增強,四處探索時并不會在同一個房間進進出出, agent將找到最快的路線到達目標(biāo)狀態(tài)。
參數(shù)γ的范圍為0到1（0 <= γ<1）。 如果γ接近零，agent將傾向于只考慮立即得到獎勵值。 如果γ更接近1，那么agent將會考慮更多的權(quán)重，愿意延遲得到獎勵。
我們使用Python為訓(xùn)練agent編寫代碼：
import numpy as np
import random
# 初始化矩陣
Q = np.zeros((6, 6))
Q = np.matrix(Q)
# 回報矩陣R
R = np.matrix([[-1,-1,-1,-1,0,-1],[-1,-1,-1,0,-1,100],[-1,-1,-1,0,-1,-1],[-1,0,0,-1,0,-1],[0,-1,-1,0,-1,100],[-1,0,-1,-1,0,100]])
# 設(shè)立學(xué)習(xí)參數(shù)
γ = 0.8
# 訓(xùn)練
for i in range(2000):
# 對每一個訓(xùn)練,隨機選擇一種狀態(tài)
state = random.randint(0, 5)
while True:
# 選擇當(dāng)前狀態(tài)下的所有可能動作
r_pos_action = []
for action in range(6):
if R[state, action] >= 0:
r_pos_action.append(action)
next_state = r_pos_action[random.randint(0, len(r_pos_action) - 1)]
Q[state, next_state] = R[state, next_state] + γ *(Q[next_state]).max() #更新
state = next_state
# 狀態(tài)4位最優(yōu)庫存狀態(tài)
if state==5:
break
print(Q)
運行結(jié)果為：
這個矩陣Q可以通過將所有的非零條目除以最高的數(shù)字（在這種情況下為500）來歸一化（即轉(zhuǎn)換為百分比）：
一旦矩陣Q足夠接近收斂狀態(tài)，我們知道我們的agent已經(jīng)學(xué)習(xí)了任意狀態(tài)到達目標(biāo)狀態(tài)的最佳路徑。
例如：
從初始狀態(tài)2開始，agent可以使用矩陣Q作為指導(dǎo),從狀態(tài)2開始，最大Q值表示選擇進入狀態(tài)3的動作。
從狀態(tài)3開始，最大Q值表示有兩種并列最優(yōu)選擇：進入狀態(tài)1或4。假設(shè)我們?nèi)我膺x擇去1。
從狀態(tài)1開始，最大Q值表示選擇進入狀態(tài)5的動作。
因此，最優(yōu)策略是2 – 3 – 1 – 5。
同時，若狀態(tài)3時選擇進入狀態(tài)4，最優(yōu)策略為2-3-4-5。
兩種策略的累計回報值相等，故從狀態(tài)2到5有兩種最優(yōu)策略。
# 例子較為簡單，讀者可以根據(jù)流程圖和步驟解釋手算以便加深印象。
總結(jié)
以上是生活随笔為你收集整理的Q学习（Q-learning）入门小例子及python实现(Meaning)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 跟我学jQuery(二) 初识jQuer
- 下一篇： Asp.net MVC 示例项目Sute