强化学习：Q-Learning学习笔记（C语言实现）

一. 强化学习（增强学习）的概念：

机器学习算法大致可以分为三种：

  1. 监督学习(如回归，分类)

  2. 非监督学习(如聚类，降维)

  3. 强化学习

什么是强化学习呢？

强化学习（reinforcementlearning, RL）又叫做增强学习，是近年来机器学习和智能控制领域的主要方法之一。
定义: Reinforcement learning is learning what to do ----how to map situations to actions ---- so as to maximize a numerical reward signal.[1]
也就是说增强学习关注的是智能体（也就是agent）如何在环境中采取一系列行为，从而获得最大的累积回报。

强化学习的学习机制表明它是不断地与环境交互（可以看做是决策系统【采取action的系统】和环境的博弈），以试错的学习方式得到最优策略，是使得决策能力持续获取收益的关键技术。

强化学习以试错的机制与环境进行交互，通过最大化积累奖赏（R）的方式来学习最优策略，最简单的理解就是在训练的过程中，不断地去尝试，错了就惩罚，对了就奖励，由此训练得到各个状态环境当中最好的决策，例如骑车的过程，种瓜的过程。[4]

通过增强学习，一个智能体应该知道在什么状态下应该采取什么行为。RL是从环境状态到动作的映射的学习，我们把这个映射称为策略。
强化学习基本原理示意图

二. Q-learning

Q-learning思路

图1.1
图1.1
要解决的问题是：如上图 1.1 中有 5 个房间，分别被标记成 0-4，房间外可以看成是一个大的房间，被标记成 5，现在智能程序 Agent 被随机丢在 0-4 号 5 个房间中的任意 1 个，目标是让它寻找到离开房间的路（即：到达 5 号房间）。

图片描述如下：
图1.2
图1.2
给可以直接移动到 5 号房间的动作奖励 100 分，即：图1.2中，4 到 5 、 1 到 5 和 5 到 5 的红线。
在其它几个可移动的房间中移动的动作奖励 0 分。
如下图：
图1.3
图1.3
假设 Agent 当前的位置是在 2 号房间，这里就将 Agent 所在的位置做为“状态”，也就是 Agent 当前的状态是 2，当前 Agent 只能移动到 3 号房间，当它移动到 3 号房间的时候，状态就变为了 3，此时得到的奖励是 0 分。

而 Agent 根据箭头的移动则是一个“行为”。
根据状态与行为得到的奖励可以组成以下矩阵。R代表当前奖励。
图1.4
图1.4
同时，可以使用一个 Q 矩阵，来表示 Agent 学习到的知识，在图 1.4 中，“-1”表示不可移动的位置，比如从 2 号房间移动到 1 号房间，由于根本就没有门，所以没办法过去。
图1.5
图1.5
该 Q 矩阵就表示 Agent 在各种状态下，做了某种行为后自己给打的分，也就是将经验数据化，由于 Agent 还没有行动过，所以这里全是 0。

在 Q-Learning 算法中，计算经验得分的公式如下：
Q(state, action) = Q(state, action) + α(R(state, action) + Gamma * Max[Q(next state, all actions)] - Q(state, action))

当 α 的值是 1 时，公式如下：
Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]

  • state： 表示 Agent 当前状态。
  • action： 表示 Agent 在当前状态下要做的行为。
  • next state： 表示Agent 在 state 状态下执行了 action 行为后达到的新的状态。
  • Q(state, action)： 表示 Agent 在state 状态下执行了 action 行为后学习到的经验，也就是经验分数。
  • R(state, action)： 表示 Agent 在state 状态下做 action 动作后得到的即时奖励分数。（注意是即时奖励，不是经验）
  • Max[Q(next state, allactions)]： 表示 Agent 在 next state 状态下，自我的经验中，最有价值的行为的经验分数。
  • Gamma：γ，表示折损率，也就是未来的经验对当前状态执行 action 的重要程度。

Q-learning算法

Agent 通过经验去学习。Agent将会从一个状态到另一个状态这样去探索，直到它到达目标状态。我们称每一次这样的探索为一个场景（episode）。
每个场景就是 Agent 从起始状态到达目标状态的过程。每次 Agent 到达了目标状态，程序就会进入到下一个场景中。

  1. 初始化 Q 矩阵，并将初始值设置成 0。

  2. 设置好参数 γ 和得分矩阵 R。

  3. 循环遍历场景（episode）：

    （1）随机初始化一个状态 s。

    （2）如果未达到目标状态，则循环执行以下几步：

    1. 在当前状态 s 下，随机选择一个行为 a。

    2. 执行行为 a 得到下一个状态 s`。

    3. 使用 Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)] 公式计算 Q(state, action) 。

    4. 将当前状态 s 更新为 s`。

设当前状态 s 是 1， γ =0.8和得分矩阵 R，并初始化 Q 矩阵：
图2.1
图2.1
在这里插入图片描述
图2.2
由于在 1 号房间可以走到 3 号房间和 5 号房间，现在随机选一个，选到了 5 号房间。

现在根据公式来计算，Agent 从 1 号房间走到 5 号房间时得到的经验分数 Q(1, 5) ：

1.当 Agent 从 1 号房间移动到 5 号房间时，得到了奖励分数 100（即：R(1, 5) = 100）。

2.当 Agent 移动到 5 号房间后，它可以执行的动作有 3 个：移动到 1 号房间（0 分）、移动到 4 号房间（0 分）和移动到 5 号房间（0 分）。注意，这里计算的是经验分数，也就是 Q 矩阵，不是 R 矩阵！

所以，Q(1, 5) = 100 + 0.8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100 + 0.8 * Max{0, 0, 0} = 100
（已经达到目标状态5，所以进入下一个场景episode）

在次迭代进入下一个episode：
随机选择一个初始状态，这里设 s = 3，由于 3 号房间可以走到 1 号房间、 2 号房间和 4 号房间，现在随机选一个，选到了 1 号房间。

步骤同上得：Q(3, 1) = 0 + 0.8 * Max[Q(1, 3), Q(1, 5)] = 0 + 0.8 * Max{0, 100} = 0 + 0.8 * 100 = 80
即：
图2.3
图2.3

Q-learning的C语言实现：

C语言实现

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

//动作数
#define ACTIONS 6
//探索次数
#define episode 1000
//目标状态，即：移动到 5 号房间。
#define target_state 5
//γ，折损率，取值是 0 到 1 之间。
#define gamma 0.8

int max(int* p, int m)
{
	int i, max = *p;
	for (i = 1; i < m; i++)
	{
		if (*(p + i) > max)
			max = *(p + i);
	}
	return max;
}

int main()
{
	// 经验矩阵。
	int q[6][6] = { 0 };

	int r[6][6] = { 
	{ -1, -1, -1, -1, 0, -1},
	{-1, -1, -1, 0, -1, 100.0},
	{ -1, -1, -1, 0, -1, -1},
	{-1, 0, 0, -1, 0, -1},
	{0, -1, -1, 0, -1, 100.0},
	{ -1, 0, -1, -1, 0, 100.0 } 
	};

	int start_room;
	int current_state;
	int current_action;
	int current_action_point;
	int next_state;
	int step;
	int next_state_max_q;

	// 搜索次数。
	for (int i = 0; i < episode; i++)
	{
		srand(time(NULL));
		// Agent 的初始位置的状态。
		start_room = rand() % 5;
		// 当前状态。
		current_state = start_room;
		while (current_state != target_state)
		{
			//当前状态中的随机选取下一个可执行的动作。
			current_action = rand() % 6;
			// 执行该动作后的得分。
			current_action_point = r[current_state][current_action];
			if (current_action_point < 0)
			{
				q[current_state][current_action] = current_action_point;
			}
			else
			{
				// 得到下一个状态。
				next_state = current_action;
				// 获得下一个状态中，在自我经验中，也就是 Q 矩阵的最有价值的动作的经验得分。
				next_state_max_q = max(&q[next_state][0],6);
				// 当前动作的经验总得分 = 当前动作得分 + γ X 执行该动作后的下一个状态的最大的经验得分
				// 即：积累经验 = 动作执行后的即时奖励 + 下一状态根据现有学习经验中最有价值的选择 X 折扣率
				q[current_state][current_action] = current_action_point + gamma * next_state_max_q;
				current_state = next_state;
			}
		}
		printf("Q值表更新过程为：\n");
		for (int i = 0; i < 6; i++)
		{
			for (int j = 0; j < 6; j++)
			{
				printf("%d,", q[i][j]);
			}
			printf("\n");
		}
	}
	printf("\n 最终的Q值表为：\n");
	for (int i = 0; i < 6; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			printf("%d,", q[i][j]);
		}
		printf("\n");
	}

	start_room = rand()%5;
	current_state = start_room;
	step = 0;
	
	// 这里是进行测试，依据训练好的Q值，选择动作。
	while (current_state != target_state)
	{
		// 这里相当于python中的 np.argmax()函数，即当 np.argmax(f(x))中的f(x)取最大值的时候输出 x 的取值大小。
		// 用两个for循环实现。
		int m = -100;
		for (int i = 0; i < 6; ++i)
		{
			if (m < q[current_state][i])
			{//找最大值
				m = q[current_state][i];
			}
		}
		for (int j = 0; j < 6; j++)
		{
			if (m == q[current_state][j])
				next_state = j;
		}

		printf("\n Agent 由 %d 号房间移动到了 %d 号房间\n", current_state, next_state);
		current_state = next_state;
		step += 1;
	}
	printf("\n Agent 在 %d 号房间开始移动了 %d 步到达了目标房间\n", start_room, step);


	return 0;
}

运行截图：
在这里插入图片描述
在这里插入图片描述
GitHub链接：
https://github.com/97JOHN/Reinforcement_Learning_Train.git

参考资料：

[1] R.Sutton et al. Reinforcement learning: An introduction , 1998

[2] T.Mitchell. 《机器学习》，2003

[3] Andrew Ng.CS229: Machine learning Lecture notes

[4]深度学习，优化与识别，2017

Logo
CSDN学习社区

CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！

更多推荐

cover

用 OpenAI Assistants 做大模型应用开发

avatar CSDN学习社区
cover

1 小时解读鸿蒙 10 大热点问题

avatar CSDN学习社区
cover

1 小时解读鸿蒙 10 大热点问题

avatar CSDN学习社区