一文带你理解Q-Learning的搜索策略，掌握强化学习最常用算法

原标题：一文带你理解Q-Learning的搜索策略，掌握强化学习最常用算法王小新 编译自 MediumQ-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和γ，其中：该模型的目标是在未给出MDP动态知识的情况下找到一个最优策略π*。要注意，如果具有这个动态知识，直接用最优值迭代方法就能找到最优策略。1defoptimal_value_iteration(mdp, V0, num_iterations, epsilon=0.0001):2V = np.zeros((num_iterations+1, mdp.S))3V[0][:] = np.ones(mdp.S)*V04X = np.zeros((num_iterations+1, mdp.A, mdp.S))5star = np.zeros((num_iterations+1,mdp.S))6forkinrange(num_iterations):7forsinrange(mdp.S):8forainrange(mdp.A):9X[k+1][a][s] = mdp.R[a][s] + mdp.discount*np.sum(mdp.P[a][s].dot(V[k]))10star[k+1][s] = (np.argmax(X[k+1,:,s]))11V[k+1][s] = np.max(X[k+1,:,s])12if(np.max(V[k+1]-V[k])-np.min(V[k+1]-V[k])) 13V[k+1:] = V[k+1]14star[k+1:] = star[k+1]15X[k+1:] = X[k+1]16break17else:pass18returnstar, V, X△奖励变化曲线最优策略是等到森林处于古老且茂盛的状态时进行砍伐，这容易理解，因为在森林处于最古老的状态时砍伐的奖励是等待让森林生长的奖励的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搜索策略，后面会详细介绍。1def q_learning(mdp, num_episodes, T_max, epsilon=0.01):2Q = np.zeros((mdp.S, mdp.A))3episode_rewards = np.zeros(num_episodes)4policy = np.ones(mdp.S)5V = np.zeros((num_episodes, mdp.S))6N = np.zeros((mdp.S, mdp.A))7fori_episode in range(num_episodes):8# epsilon greedy exploration9greedy_probs = epsilon_greedy_exploration(Q, epsilon, mdp.A)10state= np.random.choice(np.arange(mdp.S))11fort in range(T_max):12# epsilon greedy exploration13action_probs = greedy_probs(state)14action = np.random.choice(np.arange(len(action_probs)), p=action_probs)15next_state, reward = playtransition(mdp,state, action)16episode_rewards[i_episode] += reward17N[state, action] +=118alpha =1/(t+1)**0.819best_next_action = np.argmax(Q[next_state])20td_target = reward + mdp.discount * Q[next_state][best_next_action]21td_delta = td_target - Q[state][action]22Q[state][action] += alpha * td_delta23state= next_state24V[i_episode,:] = Q.max(axis=1)25policy = Q.argmax(axis=1)26returnV, policy, episode_rewards, N△奖励变化曲线 探索与利用的平衡序列学习算法会涉及到一个基本选择：合理平衡好探索和利用的关系，对智能体的学习能力有重大影响。过多的探索会阻碍智能体最大限度地获得短期奖励，因为选择继续探索可能获得较低的环境奖励。另一方面，由于选择的利用动作可能不是最优的，因此靠不完全知识来利用环境会阻碍长期奖励的最大化。ε-greedy搜索策略该策略在每一步利用概率ε来选择随机动作。这可能是最常用也是最简单的搜索策略，即用ε调整探索动作。在许多实现中，ε会随着时间不断衰减，但也有不少情况，ε会被设置为常数。1defepsilon_greedy_exploration(Q, epsilon, num_actions):2defpolicy_exp(state):3probs = np.ones(num_actions, dtype=float) * epsilon / num_actions4best_action = np.argmax(Q[state])5probs[best_action] += (1.0- epsilon)6returnprobs7returnpolicy_exp不确定优先搜索策略不确定优先（Optimism in Face of Uncertainty）搜索策略，最开始被用来解决随机式多臂赌博机问题（Stochastic Multi-Armed Bandit），这是一个很经典的决策问题，赌徒要转动一个拥有n个槽的老虎机，转动每个槽都有固定回报概率，目标是找到回报概率最高的槽并且不断地选择它来获取最高的回报。赌徒面临着利用还是探索的问题，利用机器获得最高的平均奖励或探索其他未玩过的机器，以期望获得更高的奖励。这个问题与Q-Learning算法中的探索问题非常相似：不确定优先状态：只要我们对某个槽的回报不确定时不确定手臂的结果，我们就会考虑当前环境来选择最佳的手臂。不确定优先算法有两方面：置信区间上界（Upper Confidence Bound, UCB）是一种常用的不确定优先算法[2]，我们把它结合到Q-Learning方法中，有：此时，智能体的目标为Argmax {Q(s, a)/ a ∈ A}，这意味着在状