王小新 編譯自 Medium
量子位 出品 | 公眾號 QbitAI
Q-Learning是強化學習中最常用的算法之一。
Medium上有篇文章，討論了這種算法的一個重要部分：搜索策略。
量子位搬運過來，以下為博客譯文：
我們先介紹下有關概念和符號。
強化學習
強化學習（Reinforcement Learning, RL）屬於機器學習的一個分支，利用智能體（agent）通過狀態感知、選擇動作和接收獎勵來與環境互動。每一步中，智能體都會通過觀察環境狀態，選擇並執行一個動作，來改變其狀態並獲得獎勵。
馬爾可夫決策過程
在傳統環境中，馬爾可夫決策過程（Markov Decision Processes, MDP）可以解決不少RL問題。這裡，我們不會深入討論MDP的理論，有關MDP算法的更多內容可參考：
https://en.wikipedia.org/wiki/Markov_decision_process
我們用森林火災來解釋下MDP算法，代碼實現可使用python MDP Toolbox：
http://pymdptoolbox.readthedocs.io/en/latest/api/example.html
森林管理包括兩個動作，等待和砍伐。每年要做出一個決定，一是為林中動物保持古老森林，二是砍伐木材來而賺錢。而且，每年有p概率發生森林火災，有1-p的概率為森林生長。
先定義MDP算法中一些參數S、A、P、R和γ，其中：
S是狀態空間（有限），包括3種不同年齡樹木，年齡級分別為0-20年、21-40年和40年以上；
A是動作空間（有限），即等待或砍伐；
P和R分別是轉移矩陣和獎勵矩陣，很容易寫出它的閉合形式；
γ是數值在0與1之間的貼現因子，用來平衡短時和未來獎勵的關係；
策略π是當前狀態下決策的靜態分布；
該模型的目標是在未給出MDP動態知識的情況下找到一個最優策略π*。
要注意，如果具有這個動態知識，直接用最優值迭代方法就能找到最優策略。
獎勵變化曲線
最優策略是等到森林處於古老且茂盛的狀態時進行砍伐，這容易理解，因為在森林處於最古老的狀態時砍伐的獎勵是等待讓森林生長的獎勵的5倍，有r1=10，r2=50。
Q-Learning算法
Q-Learning算法中的「Q」代表著策略π的質量函數（Quality function），該函數能在觀察狀態s確定動作a後，把每個狀態動作對 (s, a) 與總期望的折扣未來獎勵進行映射。
Q-Learning算法屬於model-free型，這意味著它不會對MDP動態知識進行建模，而是直接估計每個狀態下每個動作的Q值。然後，通過在每個狀態下選擇具有最高Q值的動作，來繪製相應的策略。
如果智能體不斷地訪問所有狀態動作對，則Q-Learning算法會收斂到最優Q函數[1]。
有關Q-Learning的其他細節，這裡不再介紹，更多內容可觀看Siraj Raval的解釋視頻。
視頻1
下面我們給出關於Q-Learning算法的Python實現。
要注意，這裡的學習率α是w=4/5時的多項式，這裡使用了引用[3]的結果。
這裡使用的ε-greedy搜索策略，後面會詳細介紹。
獎勵變化曲線
探索與利用的平衡
序列學習算法會涉及到一個基本選擇：
利用：根據當前信息做出最佳決策；
探索：做出其他決策來收集更多信息。
合理平衡好探索和利用的關係，對智能體的學習能力有重大影響。過多的探索會阻礙智能體最大限度地獲得短期獎勵，因為選擇繼續探索可能獲得較低的環境獎勵。另一方面，由於選擇的利用動作可能不是最優的，因此靠不完全知識來利用環境會阻礙長期獎勵的最大化。
ε-greedy搜索策略
該策略在每一步利用概率ε來選擇隨機動作。
這可能是最常用也是最簡單的搜索策略，即用ε調整探索動作。在許多實現中，ε會隨著時間不斷衰減，但也有不少情況，ε會被設置為常數。
不確定優先搜索策略
不確定優先（Optimism in Face of Uncertainty）搜索策略，最開始被用來解決隨機式多臂賭博機問題（Stochastic Multi-Armed Bandit），這是一個很經典的決策問題，賭徒要轉動一個擁有n個槽的老虎機，轉動每個槽都有固定回報概率，目標是找到回報概率最高的槽並且不斷地選擇它來獲取最高的回報。
賭徒面臨著利用還是探索的問題，利用機器獲得最高的平均獎勵或探索其他未玩過的機器，以期望獲得更高的獎勵。
這個問題與Q-Learning算法中的探索問題非常相似：
利用：在給定狀態下選擇具有最高Q值的動作；
探索：做出其他決策來探索更多信息，通過選擇不了解或不夠了解的環境。
不確定優先狀態：只要我們對某個槽的回報不確定時不確定手臂的結果，我們就會考慮當前環境來選擇最佳的手臂。
不確定優先算法有兩方面：
若當前處於最佳環境，那算法會直接選擇最佳的手臂；
若當前不處於最佳環境，則算法會儘量降低不確定性。
置信區間上界（Upper Confidence Bound, UCB）是一種常用的不確定優先算法[2]，我們把它結合到Q-Learning方法中，有：
Q(s, a)：狀態s下動作a縮放後的Q值；
N(t，s，a)：在時刻t和狀態s下動作a被選擇的次數。
此時，智能體的目標為Argmax，這意味著在狀態s中選擇具有最高Q值的動作。但是在t時刻Q（s，a）值是未知的。
在t時刻，Q估計值為Q(t, s, a)，則有Q(s,a) =+ (Q(s,a) −)。
(Q(s,a) −)為相應誤差項。
霍夫不等式（Hoeffding’s inequality）可用來處理這類誤差。事實上，當t變化時，有：
優先策略可寫成：Argmax，且有：
當β大於0時，執行探索動作；當β為0時，僅利用已有估計。
這種界限方法是目前最常用的，基於這種界限後面也有許多改進工作，包括UCB-V，UCB*，KL-UCB，Bayes-UCB和BESA[4]等。
下面給出經典UCB算法的Python實現，及其在Q-Learning上的應用效果。
獎勵變化曲線
UCB搜索算法應該能很快地獲得高額獎勵，但是前期搜索對訓練過程的影響較大，有希望用來解決更複雜的多臂賭博機問題，因為這種方法能幫助智能體跳出局部最優值。
下面是兩種策略的對比圖。
總結與展望
Q-Learning是強化學習中最常用的算法之一。在這篇文章中，我們討論了搜索策略的重要性和如何用UCB搜索策略來替代經典的ε-greedy搜索算法。
更多更細緻的優先策略可以被用到Q-Learning算法中，以平衡好利用和探索的關係。
參考文獻
[1]T. Jaakkola, M. I. Jordan, and S. P. Singh, 「On the convergence of stochastic iterative dynamic programming algorithms」 Neural computation, vol. 6, no. 6, pp. 1185–1201, 1994.
[2]P. Auer, 「Using Confidence Bounds for Exploitation-Exploration Trade-offs」, Journal of Machine Learning Research 3 397–422, 2002.
[3]E. Even-Dar, and Y. Mansour, 「Learning Rates for Q-learning」, Journal of Machine Learning Research 5 1–25, 2003.
[4]A. Baransi, O.-A. Maillard, and S. Mannor, 「Sub-sampling for multi-armed bandits」, Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 115–131, 2014.
原文：https://medium.com/sequential-learning/optimistic-q-learning-b9304d079e11
—完—
加入社群
量子位AI社群17群開始招募啦，歡迎對AI感興趣的同學，加小助手微信qbitbot7入群；
此外，量子位專業細分群(自動駕駛、CV、NLP、機器學習等)正在招募，面向正在從事相關領域的工程師及研究人員。
進群請加小助手微信號qbitbot7，並務必備註相應群的關鍵詞~通過審核後我們將邀請進群。（專業群審核較嚴，敬請諒解）
誠摯招聘
量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，請在量子位公眾號(QbitAI)對話界面，回復「招聘」兩個字。