强化学习之Q-Learning（附代码）

$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$算法介绍

  $Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$是强化学习的算法之一，$\mathrm{Q}$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$的主要目的就是学习状态动作价值函数的$Q(s,a)$，其中$Q(s,a)$表示的是在给定当前状态$s$和采取动作$a$之后能够获得的收益期望。$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$利用状态$s$和动作$a$张成一个$Q$表来储存$Q$值，然后根据$Q$值来选取能够获得最大收益的动作。$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$采用是值迭代的方法进行求解，其核心的迭代公式为$$Q_{k+1}(s,a)=\sum _{\hat{s}\in \mathcal{S}}p(\hat{s}|s,a)\left[R(s,a)+\gamma \cdot \underset{\hat{a}\in \mathcal{A}}{\max }\{Q_k(\hat{s},\hat{a})\}\right]$$其中$Q_{k+1}(s,a)$第$k+1$次迭代函数，$s$和$a$分别表示的是当前的状态和执行的动作并且它们分别属于状态空间$\mathcal{S}$和动作空间$\mathcal{A}$，$R(s,a)$表示的是在状态$s$执行动作$a$后的即时奖励，$\hat{s}$和$\hat{a}$表示的是下一个的状态和行为，$p(\hat{s}|s,a)$表示的是状态转移概率，$\gamma$表示的是折扣系数。
 当动作空间$\mathcal{A}$中的动作$a$划分的足够细时候，给定当前状态$s$和执行的动作$a$，就能够明确确定下一个状态$\hat{s}$，进而则有$p(\hat{s}|s,a)=1$，对上迭代公式进一步化简则有$$Q_{k+1}(s,a)=R(s,a)+\gamma \cdot \underset{\hat{a}\in \mathcal{A}}{\max }\{Q_k(\hat{s},\hat{a})\}$$一般情况下$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$算法用到的都是以上的迭代公式。

$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$具体实例

 如下左半图显示，该图共有六个状态，五个房间分别是状态$0$，$1$，$2$，$3$和$4$，以及房间外状态$5$，右半图为左半图的状态转移过程的抽象示意图。现在的问题是如果有一个人在任意的一个房间里，给他支个招让他走出房间外。我们就可以通过强化学习中的$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$方法来解决这个问题。

 在解决这个问题之前需要先确定奖励矩阵$R$，其元素表示的是当一个给定一个状态$s$，当执行某个动作$a$后，它的即时奖励$R(s,a)$的取值。规定当走出房间外到达状态$5$的动作奖励为$100$，如果没有走出房间外但在房间内可以走通的是奖励为$0$，如果房间内也不能走通的动作奖励为$-1$。奖励矩阵$R$具体取值如下所示。
$$R=\left[\begin{array}{rrrrrr}-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\end{array}\right]$$

• 首先确定折扣系数$\gamma =0.8$，并将$Q$初始化为一个零矩阵：$$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$
• 第一轮第一次迭代随机选择初始状态为房间$1$，然后观察矩阵$R$的第二行（对应房间$1$或者状态$1$），这一行中有两个非负值，即当前状态$1$的下一步行为有两种可能：转至状态$3$或$5$，此时选择随机选择转至状态$5$。观察矩阵$R$的第六行（对应房间$5$或者状态$5$），这一行有三个非负值，即当前状态$5$的下一步行为有三种可能：转至状态$1$，$4$或$5$。根据$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$值迭代公式则有$$\begin{array}{rl}Q(1,5)& =R(1,5)+0.8\times \max \left\{Q(5,1),Q(5,4),Q(5,5)\right\}\\ & =100+0.8\times \max \{0,0,0\}\\ & =100\end{array}$$则此时将矩阵$Q(1,5)$位置（即该矩阵的第二行第六列）用$100$进行数值更新。
  $$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 100\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$
• 第一轮第二次迭代随机选择状态为房间$3$，然后观察矩阵$R$的第四行（对应房间$3$或者状态$3$），这一行中有三个非负值，即当前状态$3$的下一步行为有三种可能：转至状态$1$，$2$或$4$，此时随机选择转至状态$1$。观察矩阵$R$的第二行（对应房间$1$或者状态$1$），这一行中有两个非负值，即当前状态$1$的下一步行为有两种可能：转至状态$3$或$5$。根据$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$值迭代公式则有$$\begin{array}{rl}Q(3,1)& =R(3,1)+0.8\times \max \left\{Q(1,3),Q(1,5)\right\}\\ & =0+0.8\times \max \{0,100\}\\ & =80\end{array}$$则此时将矩阵$Q(3,1)$位置（即该矩阵的第二行第六列）用$80$进行数值更新。
  $$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 100\\ 0& 0& 0& 0& 0& 0\\ 0& 80& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$
• 经过多轮迭代之后直至$Q$矩阵收敛，则此时的$Q$即为所求，最后对$Q$矩阵进行归一化。 $$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 400& 0\\ 0& 0& 0& 320& 0& 500\\ 0& 0& 0& 320& 0& 0\\ 0& 400& 256& 0& 400& 0\\ 320& 0& 0& 320& 0& 500\\ 0& 400& 0& 0& 400& 500\end{array}\right]⟹Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 80& 0\\ 0& 0& 0& 64& 0& 100\\ 0& 0& 0& 64& 0& 0\\ 0& 80& 51& 0& 80& 0\\ 64& 0& 0& 64& 0& 100\\ 0& 80& 0& 0& 80& 100\end{array}\right]$$

 下图表示的是经过$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$算法学习之后得到的最终的状态转移示意图，其中每个带有箭头的线上标明这个动作对应的即时收益。所以不管在哪个状态下，只要利用贪心策略找即时收益最大的行为就可以走出房间。

 以上实例中$Q$–$\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$算法的完整代码如下所示，代码比较简单大约50行就可以完整实现该功能

import numpy as np
import os
import random
def random_action(V):
	index_list = []
	for index, s in enumerate(list(V)):
		if s >= 0:
			index_list.append(index)
	return random.choice(index_list)
def reward_setting(state_num, action_num):
	R = -1 * np.ones((state_num , action_num))
	R[0,4] = 0
	R[1,3] = 0
	R[1,5] = 100
	R[2,3] = 0
	R[3,1] = 0
	R[3,2] = 0
	R[3,4] = 0
	R[4,0] = 0 
	R[4,3] = 0
	R[4,5] = 100
	R[5,1] = 0
	R[5,4] = 0
	R[5,5] = 100
	return R 
if __name__ == '__main__':
	action_num = 6
	state_num = 6
	gamma = 0.8
	epoch_number = 200
	condition_stop = 5
	Q = np.zeros((state_num , action_num))
	R = reward_setting(state_num , action_num)
	for epoch in range(epoch_number):
		for s in range(state_num):
			loop = True
			while loop:
				# Obtain random action a
				a = random_action(R[s,:])
				# Calculate maximum Q value
				q_max = np.max(Q[a,:]) 
				# Bellman optimal iteration equation
				Q[s,a] = R[s,a] + gamma * q_max
				s = a
				if s == condition_stop:
					loop = False
	Q = (Q / 5).astype(int)
	print(Q)

实验结果如下所示，大约训练200轮之后$Q$矩阵就可以收敛到理论值，并且理论推导与实验结果一致。