科学网—Qlearning系列从一个简单的寻路问题深入Qlearning

那我们就先上结果吧,这样看着比较直观,左图起点为左上角的方块,坐标为(1,1),沿着最短路线到达终点,红色方块。右图起点为下方偏右的方块,坐标为(14,16):

接下来我们再对这个解决思路的实现进行逐条解释,所遇到的问题进行逐个解决。

问题分析与方法实现:

首先是第一条,对地图的重采样。这个很简单,先检测一个格子的像素数,采样点就放在每个格子的中心位置。这里每个格子是由24x24个像素点组成,共有20x20个格子,还有两个2x480个像素点是边框的黑线。对于一个24x24的格子来说,中心位置就是坐标(13,13),所以在遍历482x482个像素点时,假设每个像素点的坐标为(x,y),中心点坐标(Px,Py)一定满足(mod为取余计算):

二、三两点实际上可以整合到第四点,也就是说PossibleAction矩阵和Reward矩阵(奖励矩阵)可以不进行单独计算,在Q-learning的过程中也可进行赋值,其本质上就是动态Q-Table的计算处理,日后有机会在做展开,这里讨论的依然限制在严格Q-Table的计算中,也就是说Q-Table的size是固定的,状态的数量也是固定的,像对于这个有着20x20个方格学习的实例,有且只有400个状态。显然,Q-Table的size就是400x4,PossibleAction矩阵和奖励矩阵同样也为400x4。

这里必须要讨论的一点就是PossibleAction矩阵和奖励矩阵之间的关系。PossibleAction矩阵的4列表示4种可行的动作,每一行表示当前所处的状态。举个例子,如下给出一个400x4的PossibleAction矩阵:

在这个PossibleAction矩阵中,UDLR分别为up,down,left,right,即为上下左右四个动作。如若当前状态为1,做向上移动的动作,可以表示为PossibleAction(state=1,action=U)=0,结果为0表示不可行。如若当前状态为1,做向下移动的动作,PossibleAction(state=1,action=D)=1,结果为1表示可行。这里使用图像表示或更为直观,图中清楚的表示出了处于状态1只可向下或向右移动。

奖励矩阵(RewardMatrix)和PossibleAction矩阵的维度相同,且行列意义相同,但矩阵内的值不同。这里我们实行一种最简单的奖励策略。这里我们用R(i,j)表示奖励矩阵中的第i行第j列的元素之值,“i”表示第i个状态,“j”表示动作j。

不难看出,R(state,action)=-1或0的情况与PossibleAction(state,action)=0或1的情况是有重叠的,且满足前一种情况的state和action是满足后一种情况的state和action的子集。Reward矩阵和PossbleAction矩阵最大的不同点在于,可以到达目标的状态动作的Reward值为100,而对于PossibleAction而言只是一个可行的状态动作而已,值依旧为1。这个区别也是Q-learning中的Q-Table可以收敛的重要依据之一。如果我们使用图示的方法来表述就更为直观了。

如图所示,只有这三种情况的Reward值可以为100。为什么说这样的奖励策略可以使得所有状态的Q值的最大值收敛于一个最佳的可行的动作上。事实上,这里可以分割为两个问题:

Q-learning的本质:

这就牵涉到了Q-learning的本质机理。我们先来解决第一个问题,解题思路中的第5点提到Q-Table中任意一个状态的所有动作中Q值最大的那个动作就是为了达到目标在当前状态下的最佳选择。所以当状态S的Q最大值收敛于动作A,那么动作A就是处于状态S的最佳选择。当然在理解了第二个问题的原理后,对一个问题也会有更深层的认识。在对第二个问题的解释之前,我们先做一个Q-learning探索者的模拟。模拟过程也是迭代过程的一部分。事实上,Q-learning中的Q-Table计算的迭代过程基本分为四个阶段:

我们着重讨论从第二阶段到第三阶段的过程,也就是Q值收敛的过程。迭代中的Q-Table的更新原则如下(在公式中,使用矩阵Q(s,a)表示Q-Table,sf和af表示下个状态动作集):

基于这种Q-Table的刷新原则,在状态S下,新的Q值与之前的Q值没有任何直接的关系,我们姑且将其称之为无记忆刷新策略。接下来,依据无记忆刷新策略,从Q-Table值变化的第一步开始模拟。

如此从第1步到第6步,我们便完成了一个简单的对Q(S1,D)计算的一次循环过程。重复第1到第6步多次后,Q(S1,D)便可以收敛。如果,探索者的动作选择是完全随机的,第n次刷新的Q(S1,D),Q(St,R)和Q(S3,L)之间一定存在如下关系:

联立上述的三个等式,可以得出:

很显然,Q(S1,D)是一个等比数列,可以求出其通项,已知在Q(S1,D)的初值是100,可得:

当n趋于正无穷时,也就是随着迭代次数的增加,毫无疑问地,Q(S1,D)的值是收敛的。当gamma值为0.8时,可以计算出,Q(S1,D)收敛于277.78,并且这里需要强调一点,状态S1周边的4个状态,比如S2和St都会收敛于状态S1的Q值最大值的0.8倍,以此类推到所有的400个状态,下图给出了每个方格Q峰值的分布图,左图为目标状态坐标(10,10)的情形,右图为目标状态坐标(3,16)的情形,图中的红框即是目标状态点,图像颜色由黑到白表示出Q峰值由小到大。

注:左图中的纯黑块和右图中的纯白块为障碍块

这两幅图直观的解释了Q-Table解决寻路问题的终极机理。无论起点在哪,只要沿着比当前状态的Q值高的状态前进,一定会找到目标,而且一定是最近的路线。

THE END
1.PaddlePaddle/PaddleClas:AtreasurechestforvisualDeep residual learning for image recognition[C]//Proceedings of the IEEE conference on computer vision and pattern recognition. 2016: 770-778. [2] He T, Zhang Z, Zhang H, et al. Bag of tricks for image classification with convolutional neural networks[C]//Proceedings of the IEEE Conferencehttps://openi.pcl.ac.cn/PaddlePaddle/PaddleClas/src/branch/develop/docs/zh_CN/models/ImageNet1k
2.强化学习QLearning算法详解qlearning算法详解QLearning是强化学习算法中value-based的算法,Q即为Q(s,a)就是在某一时刻的 s 状态下(s∈S),采取 动作a (a∈A)动作能够获得收益的期望,环境会根据agent的动作反馈相应的回报reward r,所以算法的主要思想就是将State与Action构建成一张Q-table来存储Q值,然后根据Q值来选取能够获得最大的收益的动作。 https://blog.csdn.net/qq_30615903/article/details/80739243
3.Q学习(Qlearning)简单理解「建议收藏」腾讯云开发者社区下面给出整个Q-learning算法的计算步骤算法1.1(Q-learning算法)Step1给定参数γ和reward矩阵RStep2令Q=0Step 3For each episode:3.1随机选择一个初始的状态s 3.2若未达到目标,状态则执行以下几步 (1)在当前状态的所有可能行为中选取一个行为a (2)利用选定的行为a得到下一个状态s~ (3)按照转移规则公式计算 Q(https://cloud.tencent.com/developer/article/2163196
4.WhatisQQ-learning is a machine learning approach that enables a model to iteratively learn and improve over time by taking the correct action. Q-learning is a type of reinforcement learning. With reinforcement learning, a machine learning model is trained to mimic the way animals or children learn. Gohttps://www.techtarget.com/searchenterpriseai/definition/Q-learning
5.Qlearning路径规划基于 QLearning算法智能体可以在不知道整体环境的情况下,仅通过当前状态对下?步做出判断。 Q-Learning是强化学习算法中value-based的算法,Q是指在某?时刻的某?状态下采取某?动作期望获得的收益。环境会根据智能体的动 作反馈相 应的回报,所以算法的主要思想就是将状态与动作构建成?张Q值表,然后根据https://www.iteye.com/resource/sinat_36236351-12053691
6.Q学习QQ 学习 (Q-Learning) 是一种无模型、离策略的强化学习算法,它将在给定智能体当前状态的情况下找到最佳的行动方案。根据 agent 在环境中的位置,它将决定下一步要采取的操作。「Q」指的是算法计算的函数——在给定状态下采取的行动的预期奖励。 Q 学习的目标是根据当前状态找到最佳行动方案。为此,它可能会制定自己https://hyper.ai/cn/wiki/28830
7.什么是Qlearning?–编程技术之美Q学习(Q-learning)是一种价值迭代算法,它通过采样来学习动作价值函数Q,从而获得最优策略。 Q学习的主要思想是: agents以ε-greedy策略选择动作,在环境中采样。 根据采样结果更新Q表中的 Q(s,a)值,使用下面的更新规则: Q(s,a) = Q(s,a) + α * (r + γ * maxQ(s’,a’) – Q(s,a)) http://www.itzhimei.com/archives/6817.html
8.什么是Qlearning?4. 5. 评估:采取行动得到了奖励后就可以用Q函数更新 Q(s,a): 重复这个过程一直到训练停止,就可以得到最优的 Q-table。 参考文献: https://www.freecodecamp.org/news/an-introduction-to-q-learning-reinforcement-learning-14ac0b4493cc/https://www.jianshu.com/p/b45e0297fe92
9.测试运行使用C#执行Q为了创建演示程序,我启动了 Visual Studio 并创建了一个新 C# 控制台应用程序项目名为 QLearning。我使用 Visual Studio 2017,但演示程序并不重要的.NET 依赖,因此任何版本的 Visual Studio 可以正常工作。在模板代码加载到之后我删除了所有的编辑器不需要的 using 语句,只留下对引用 System 命名空间。然后我添加到https://msdn.microsoft.com/zh-cn/magazine/mt829710
10.机器学习探究QQ-Learning算法是一种强化学习方法,它专注于学习一个名为Q函数的值表,该值表估计了在给定状态下采取特定行动所能获得的长期回报。Q-Learning的目标是找到一个最优策略,即在每个状态下选择能够最大化长期回报的行动。这个过程可以分为以下几个关键步骤: https://developer.aliyun.com/article/1496910
11.QLearning算法详解数据学习者官方网站(Datalearner)Q Learning是一种无模型(model-free reinforcement learning)强化学习,也是强化学习中十分重要的一种基础模型。谷歌旗下的DeepMind基于Q Learning提出的Deep Q Network是将强化学习与深度学习融合的经典模型,也将强化学习往前推动了一大步。因此,对于学习现代的强化学习模型来说,Q Learning是必须理解的一个基础模型。本文http://datalearner.com/blog/1051661501498544
12.QThe Q-learning algorithm is an off-policy reinforcement learning method for environments with a discrete action space. A Q-learning agent trains a Q-value function critic to estimate the value of the optimal policy, while following an epsilon-greedy policy based on the value estimated by the crhttps://www.mathworks.com/help/reinforcement-learning/ug/q-learning-agents.html
13.使用QTable进行Q更新Q 表: best_q = np.amax(q_table[tuple(state_new)]) bellman_q = reward + discount_rate * best_q indices = tuple(np.append(state_prev,action)) q_table[indices] += learning_rate*( bellman_q - q_table[indices]) 将下一个状态设置为上一个状态,并将奖励添加到剧集的奖励中: https://www.kancloud.cn/wizardforcel/mastering-tf-1x-zh/1278740
14.Qlearning算法学术百科提供全面的“Q-learning算法”相关文献(论文)下载,论文摘要免费查询,Q-learning算法论文全文下载提供PDF格式文件。Q-learning算法中文、英文词汇释义(解释),“Q-learning算法”各类研究资料、调研报告等。https://wiki.cnki.com.cn/HotWord/2182924.htm
15.5什么是QLearning(ReinforcementLearning强化学习)学员1、什么是强化学习? (Reinforcement Learning) 03:17 学员2、强化学习方法汇总 (Reinforcement Learning) 05:54 学员3、1 why? 01:40 学员4、2 要求准备 05:06 学员5、什么是 Q Learning (Reinforcement Learning 强化学习) 06:10 学员6、2.1 简单例子 https://bbs.easyaiforum.cn/lesson-1683.html
16.转载强化学习入门:基于Qclass QLearning: #Agent def __init__(self, actions, q_table=None, learning_rate=0.01, discount_factor=0.9, e_greedy=0.1): self.actions = actions # action 列表 self.lr = learning_rate # 学习速率 self.gamma = discount_factor # 折扣因子 https://xueqiu.com/9582187848/169660237
17.深度强化学习之深度Q网络DQN详解请耐心,答案在下面揭晓。下面先看个例子,这是一个Flappy Bird小游戏(原网址:https://enhuiz.github.io/flappybird-ql/),你可以自己点击屏幕玩这个游戏,也可以点击下方“Enable Q-learning”按钮,用Q-learning算法来自动玩这个游戏,给程序一两分钟,他就能轻易取得超过超过人类的成绩。https://www.flyai.com/article/522
18.OfflineReinforcementLearningwithImplicitQLearningOffline reinforcement learning requires reconciling two conflicting aims: learning a policy that improves over the behavior policy that collected the dataset, while at the same time minimizing the deviation from the behavior policy so as to avoid errors due to distributional shift. This trade-off ishttps://ui.adsabs.harvard.edu/abs/arXiv:2110.06169
19.7Papers&RadiosMIT造出薄如纸的音响;腾讯“绝艺”打麻将战胜人7. Provably Efficient Kernelized Q-Learning. (from Hao Su) 8. Staying the course: Locating equilibria of dynamical systems on Riemannian manifolds defined by point-clouds. (from Ioannis G. Kevrekidis) 9. Differentially Private Learning with Margin Guarantees. (from Mehryar Mohri) https://www.thepaper.cn/newsDetail_forward_17899633
20.AtrustawaretaskallocationmethodusingdeepqThird, to solve large-scale MCMDP problems in a stable manner, this study proposes an improved deep Q-learning-based trust-aware task allocation (ImprovedDQL-TTA) algorithm that combines trust-aware task allocation and deep Q-learning as an improvement over the uncertain mobile crowdsourcing https://dl.acm.org/doi/10.1186/s13673-019-0187-4
21.双Q学习机器之心此更新方法和随机梯度下降具有相似的工作方式,会逐渐趋向目标值 Y^Q_t 来更新当前值 Q(S_t, A_t; \theta_t)。 Deep Q-Networks: 基于价值的深度强化学习不仅仅是把 Q Learning 中的价值函数用深度神经网络近似,还做了其他改进。 这个算法就是著名的 DQN 算法,由 DeepMind 在 2013 年在 NIPS 提出。DQNhttps://www.jiqizhixin.com/graph/technologies/0d189dc7-7f80-4643-9ff4-74941694d7d4
22.MazelearningbyahybridbrainGraded levels of MFB stimuli are mapped from the converged result of Q-learning algorithm in the task T1, which is explicitly required by the computer model. While in the task T2 MFB stimulation of a single level was used, in the task T3, the same level MFB stimulation was replaced by https://www.nature.com/articles/srep31746
23.MachineLearningSubjects: Machine Learning (cs.LG); Computational Engineering, Finance, and Science (cs.CE); Statistical Finance (q-fin.ST) [33] arXiv:2412.14526 [pdf, html, other] Knowledge Distillation in RNN-Attention Models for Early Prediction of Student Performance Sukrit Leelaluk, Cheng Tang, Valdehttp://arxiv.org/list/cs.LG/pastweek?skip=30&show=524