python量化與機器學習-tft每日頭條

Q-learning 是強化學習中的一種常見的算法，近年來由于深度學習革命而取得了很大的成功。本教程不會解釋什麼是深度 Q-learning，但我們将通過 Q-learning 算法來使得代理學習如何玩 tic-tac-toe 遊戲。盡管它很簡單，但我們将看到它能産生非常好的效果。

要理解本教程，不必有任何關于強化學習的知識，但最好有一定的微積分和線性代數基礎。首先，我們将通過一些必要的背景知識來快速了解強化學習，然後我們将介紹 Q-learning 算法，最後我們将介紹如何通過它來使得一個代理學會玩 tic-tac-toe。

強化學習簡介

強化學習是指代理在不同狀态的環境中，根據某種獎勵函數來優化其行為的一門學科。在本教程中，環境是 tic-tac-toe 遊戲，它有明确定義的動作，代理必須決定選擇哪些動作才能赢得遊戲。此外，代理人赢得遊戲将獲得一定獎勵，這鼓勵它在遊戲中學習更好的策略。

強化學習的一個常見框架是（有限）馬爾可夫決策過程（MDP, Markov Decision Process）。它幫助我們定義一組動作和狀态，代理基于這些動作和狀态進行決策。

MDP 通常包括有：

· 一組有限的動作 A（在遊戲面闆上所有可以放置标記的位置）

· 一組有限的狀态 S（遊戲面闆上的所有可能情形）

· 一種獎勵函數 R(s,a)

· 轉移函數 T(s,a,s')

轉換函數給出了在執行動作 a 時從狀态 s 移動到 s' 的概率。當我們不确定動作是否總是産生期望結果時，轉移函數十分必要。但是需要注意的是，對于 tic-tac-toe 遊戲，我們确切地知道每個動作會做什麼，所以我們不會使用轉移函數。

python量化與機器學習（Python手寫強化學習Q-learning算法玩井字棋）1

在本例中，當前玩家可以執行六個可能的操作

MDP框架幫助我們将問題形式化，這樣我們就可以根據當前狀态确定哪些操作将在遊戲期間使代理的總回報最大化。本教程中獎勵函數 R(s,a) 将非常簡單：

· 如果代理在狀态 s 執行一個操作 ,最終赢得遊戲，那麼 R(s,)=1.

· 如果代理在狀态 s 執行一個操作 ,最終輸了遊戲，那麼 R(s,)=-1.

· 否則，R(s,)=0.

在強化學習中，我們通常找到一個最優策略，代理通過該策略決定選擇哪些動作。本教程中我們使用 Q-learning，簡單地将策略表示為當代理處于s狀态時執行動作 a 使函數 Q(s,a) 最大化：

python量化與機器學習（Python手寫強化學習Q-learning算法玩井字棋）2

Q-learning 中的狀态更新

Q(s,a) 即代理在 s 狀态下選擇動作 a，則在遊戲最後給出對應的獎勵或懲罰。由于代理希望将其報酬最大化，因此它會選擇使 Q 最大化的動作。

python量化與機器學習（Python手寫強化學習Q-learning算法玩井字棋）3

在場景中，首先計算當前玩家X所有動作的Q值，然後選擇Q值最大的動作

要計算 Q(s,a)，代理必須探索所有可能的狀态和動作，同時從獎勵函數 R(s,a) 獲得反饋。在 tic-tac-toe 遊戲中，我們通過讓代理與對手進行多場比賽來疊代更新 Q(s,a)，用于更新 Q 的方程如下：

python量化與機器學習（Python手寫強化學習Q-learning算法玩井字棋）4

· 在當前狀态 s 下執行動作 a

· 考慮執行動作後的所有狀态，計算其中的最大 Q 值。是執行動作 a 之後的新狀态，是下一個狀态中的最佳動作

· 學習率 α 決定我們覆蓋舊值的程度，本例中将使用 α=0.1

· 折現因子 γ 決定了在當前時間步 t 中，未來的獎勵應加權多少。通常選擇 γ=0.9

Q-learning 算法實現

為了得到一個經過充分訓練的代理，我們需要獲得 Q(s,a) 的值，這将通過讓兩個代理互相比賽來完成。首先，引入一個概率 ε，即每個代理選擇一個随機動作，否則，它将根據 Q(s,a) 選擇最佳動作。這樣，我們就保證了學習的平衡，使代理有時探索新的行為，而其他時候則利用代理已經學習到的信息來執行動作。

訓練階段可以通過以下僞代碼進行描述：

Initialise: Q(s,a) = 0, starting state s, starting player P, iterations N for t = 0 : N With probability ε : P picks random action a Else, pick action a that maximise Q(s,a) Observe new state ŝ and reward R(s,a) If current player is our agent, update Q(s,a) = (1-α)Q(s,a) α[R(s,a) γ*max(Q(ŝ,â))] s = ŝ Switch turn, P = the other player

值得注意的是，疊代次數 N 必須相對較大，本例中進行了大約 500000 次疊代。此外，Q(s,a) 可以通過 Python dict 的數據格式進行存儲；如果我們将 (s,a) 表示為整數，則可以通過二維數組的數據格式進行存儲。最後，可以随時間改變概率 ε，以強調在早期疊代中更多的随機探索，從而加快學習速度。

在用上述算法訓練代理之後，可以保存 Q(s,a) 并在想要進行比賽時加載它。然後，代理隻需遵循最優策略，選擇使 Q(s,a) 最大化的動作來赢得比賽。雖然由于 tic-tac-toe 遊戲并不複雜，代理并沒有獲得高級智能，但是嘗試這個方法可以學習如何實現 Q-learning 并了解它是如何工作的。

結語

本文首先介紹了馬爾可夫決策過程以及如何在強化學習中應用它。然後使用狀态、行動、獎勵函數來對 tic-tac-toe 遊戲進行建模。除此之外，我們還定義了函數 Q(s,a)，該函數通過該狀态 s 中選擇動作 a 來量化預期的獎勵，并通過重複玩遊戲來計算 Q(s,a)。

作者：Rickard Karlsson

deephub翻譯組：oliver lee

本文github代碼： RickardKarl/bill-the-bot