一文帶你理解Q-Learning的搜索策略

v.qq.com

下面我們給出關於Q-Learning演算法的Python實現。Q-Learning是怎麼回事？_騰訊視頻下面我們給出關於Q-Learning演算法的Python實現。

要注意，這裡的學習率α是w=4/5時的多項式，這裡使用了引用[3]的結果。

這裡使用的ε-greedy搜索策略，後面會詳細介紹。

1def q_learning(mdp, num_episodes, T_max, epsilon=0.01): 2 Q = np.zeros((mdp.S, mdp.A)) 3 episode_rewards = np.zeros(num_episodes) 4 policy = np.ones(mdp.S) 5 V = np.zeros((num_episodes, mdp.S)) 6 N = np.zeros((mdp.S, mdp.A)) 7 for i_episode in range(num_episodes): 8 # epsilon greedy exploration 9 greedy_probs = epsilon_greedy_exploration(Q, epsilon, mdp.A)10 state = np.random.choice(np.arange(mdp.S))11 for t in range(T_max):12 # epsilon greedy exploration13 action_probs = greedy_probs(state)14 action = np.random.choice(np.arange(len(action_probs)), p=action_probs)15 next_state, reward = playtransition(mdp, state, action)16 episode_rewards[i_episode] += reward17 N[state, action] += 118 alpha = 1/(t+1)**0.819 best_next_action = np.argmax(Q[next_state]) 20 td_target = reward + mdp.discount * Q[next_state][best_next_action]21 td_delta = td_target - Q[state][action]22 Q[state][action] += alpha * td_delta23 state = next_state24 V[i_episode,:] = Q.max(axis=1)25 policy = Q.argmax(axis=1)26 return V, policy, episode_rewards, N

探索與利用的平衡

序列學習演算法會涉及到一個基本選擇：

• 利用：根據當前信息做出最佳決策；
• 探索：做出其他決策來收集更多信息。

合理平衡好探索和利用的關係，對智能體的學習能力有重大影響。過多的探索會阻礙智能體最大限度地獲得短期獎勵，因為選擇繼續探索可能獲得較低的環境獎勵。另一方面，由於選擇的利用動作可能不是最優的，因此靠不完全知識來利用環境會阻礙長期獎勵的最大化。

ε-greedy搜索策略

該策略在每一步利用概率ε來選擇隨機動作。

這可能是最常用也是最簡單的搜索策略，即用ε調整探索動作。在許多實現中，ε會隨著時間不斷衰減，但也有不少情況，ε會被設置為常數。

1def epsilon_greedy_exploration(Q, epsilon, num_actions):2 def policy_exp(state):3 probs = np.ones(num_actions, dtype=float) * epsilon / num_actions4 best_action = np.argmax(Q[state])5 probs[best_action] += (1.0 - epsilon)6 return probs7 return policy_exp

不確定優先搜索策略

不確定優先（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 {Q(s, a)/ a ∈ A}，這意味著在狀態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 {Q+(t, s, a)/ a ∈ A}，且有：

當β大於0時，執行探索動作；當β為0時，僅利用已有估計。

這種界限方法是目前最常用的，基於這種界限後面也有許多改進工作，包括UCB-V，UCB*，KL-UCB，Bayes-UCB和BESA[4]等。

下面給出經典UCB演算法的Python實現，及其在Q-Learning上的應用效果。

1def UCB_exploration(Q, num_actions, beta=1):2 def UCB_exp(state, N, t):3 probs = np.zeros(num_actions, dtype=float)4 Q_ = Q[state,:]/max(Q[state,:]) + np.sqrt(beta*np.log(t+1)/(2*N[state]))5 best_action = Q_.argmax()6 probs[best_action] = 17 return probs8 return UCB_exp

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

— 完 —

推薦閱讀：