本文主要是介绍马尔可夫决策过程(Markov decision process,MDP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 马尔可夫决策过程(MDP)在机器学习中应用
- 在机器学习中的引用
- 示例引用:
- 实例
- 场景:机器人导航
- MDP的定义:
- 引用示例:
- 在此基础上更具体的描述,并给出每一步的推断计算过程
- 场景描述:3x3网格中的机器人导航
- MDP的定义
- 强化学习算法:Q-Learning
- 具体实例与推断计算过程
- 总结
- Q-learning:强化学习中的基础算法
- Q-learning 的优点
- Q-learning 的局限性
- 深度Q网络 (Deep Q-Network, DQN)
- 总结
- 代码实现
- 问题描述
- Q-Learning代码实现
- 代码解释
- 运行结果
- 注意
- 关于作者
马尔可夫决策过程(MDP)在机器学习中应用
马尔可夫决策过程( M a r k o v D e c i s i o n P r o c e s s , M D P Markov Decision Process, MDP MarkovDecisionProcess,MDP)在机器学习中有广泛的应用,尤其是在强化学习领域。MDP为建模决策问题提供了一个数学框架,帮助算法在不确定环境中做出序列决策。引用 M D P MDP MDP的方式通常涉及以下几个方面:
-
状态空间 ( S t a t e S p a c e State Space StateSpace): M D P MDP MDP状态空间表示系统可能处于的所有不同状态。在机器学习中,状态通常对应于某种表示环境或问题的特征向量。
-
动作空间 ( A c t i o n S p a c e Action Space ActionSpace): 动作空间代表在给定状态下可以采取的所有可能的行动。在机器学习任务中,动作决定了系统从一个状态转移到另一个状态。
-
状态转移函数 ( T r a n s i t i o n F u n c t i o n Transition Function TransitionFunction): 这是一个概率分布,表示在执行某一特定动作后,系统从一个状态转移到另一个状态的概率。这个函数是MDP的核心,用来描述系统的动态行为。
-
奖励函数 ( R e w a r d F u n c t i o n Reward Function RewardFunction): 奖励函数定义了在给定状态采取某一动作所获得的即时回报。它是强化学习中用来评估动作好坏的主要依据。
-
折扣因子 ( D i s c o u n t F a c t o r Discount Factor DiscountFactor): 在 M D P MDP MDP中,折扣因子用于控制未来奖励对当前决策的影响程度。它帮助算法更好地平衡短期与长期收益。
在机器学习中的引用
**在强化学习算法(如Q学习、深度Q网络、策略梯度等)中, M D P MDP MDP被用作基础框架来定义和解决问题。**例如,Q学习算法通过在MDP定义的状态空间和动作空间中找到最优策略来最大化累积奖励。深度强化学习模型则使用神经网络来逼近Q值或策略函数,从而解决更复杂的MDP问题。
示例引用:
在强化学习任务中,我们通过定义一个马尔可夫决策过程(MDP)来建模问题。MDP包括一个状态空间( S S S),一个动作空间( A A A),一个状态转移函数( P P P),以及一个奖励函数 ( R R R)。通过最大化累积奖励 ( G t = G_t= Gt= ∑ k = 0 ∞ γ k R t + k + 1 \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} ∑k=0∞γkRt+k+1),算法能够学习最优策略。
这种引用方式通常出现在描述问题建模、算法设计或理论分析部分,旨在说明如何利用MDP结构化地解决复杂的序列决策问题。
实例
场景:机器人导航
假设我们正在开发一个机器人导航系统,目标是让机器人从起点移动到终点,同时避免障碍物。这个问题可以通过 M D P MDP MDP来建模和求解。
MDP的定义:
-
状态空间 (S): 机器人所在的每个可能位置都代表一个状态。假设机器人在一个 5 × 5 5 \times 5 5×5的网格上移动,那么状态空间 ( S S S) 可以定义为网格中的所有位置 ( x , y x, y x,y ),其中 x , y ∈ { 1 , 2 , 3 , 4 , 5 } x, y \in\{1,2,3,4,5\} x,y∈{1,2,3,4,5}。
-
动作空间 (A): 机器人可以在每个状态下选择的动作包括:向上 ( U p Up Up)、向下 ( D o w n Down Down)、向左 ( L e f t Left Left)、向右 ( R i g h t Right Right)。
-
状态转移函数 ( P ( s ′ ∣ s , a ) P\left(s^{\prime} \mid s, a\right) P(s′∣s,a)): 状态转移函数表示机器人在状态 ( s s s) 执行动作 ( a a a) 后,以一定概率 ( P P P) 转移到下一个状态 ( s ′ s' s′)。例如,如果机器人选择向右移动,则有 90 90 90%的概率转移到右边的格子, 10 10 10%的概率由于滑动等因素,可能转移到其他相邻格子。
-
奖励函数 ( R ( s , a ) R(s, a) R(s,a)): 在这个导航任务中,奖励函数可以设计为:机器人到达终点状态时获得正奖励 ( + 10 +10 +10),撞到障碍物时获得负奖励 ( − 10 -10 −10),其余情况下每次移动获得小的负奖励 ( − 1 -1 −1),以鼓励机器人尽快找到路径。
-
折扣因子 ( γ \gamma γ): 折扣因子通常设置为一个介于 0 0 0到 1 1 1之间的值,用来表示未来奖励的权重。假设在这个例子中,( γ \gamma γ),意味着机器人更关心当前的行动效果,但未来的收益也不能完全忽略。
引用示例:
为了让机器人学会自主导航,我们将该问题建模为一个马尔可夫决策过程 ( M D P MDP MDP)。状态空间 ( S S S ) 表示机器人的可能位置,动作空间 ( ) 表示机器人的可能位置,动作空间( )表示机器人的可能位置,动作空间(A ) 包括上下左右四种移动方式。通过定义状态转移函数 ( )包括上下左右四种移动方式。通过定义状态转移函数 ( )包括上下左右四种移动方式。通过定义状态转移函数(P\left(s^{\prime} \mid s, a\right) ) 和奖励函数 ( ) 和奖励函数 ( )和奖励函数(R(s, a) ) ,我们使用 Q 学习算法来计算最优策略,使机器人能够以最短路径到达目标位置,同时避免碰撞障碍物。该模型采用了折扣因子 ( ),我们使用Q学习算法来计算最优策略,使机器人能够以最短路径到达目标位置,同时避免碰撞障碍物。该模型采用了折扣因子 ( ),我们使用Q学习算法来计算最优策略,使机器人能够以最短路径到达目标位置,同时避免碰撞障碍物。该模型采用了折扣因子(\gamma$) 来平衡即时奖励与长期收益。
在此基础上更具体的描述,并给出每一步的推断计算过程
场景描述:3x3网格中的机器人导航
目标:让机器人从起点 ( 1 , 1 ) (1,1) (1,1)移动到终点 ( 3 , 3 ) (3,3) (3,3),同时避开障碍物 ( 2 , 2 ) (2,2) (2,2)。
MDP的定义
-
状态空间 ( S S S):
- 网格中的每一个位置都是一个状态。状态集为:
S = { ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 3 , 3 ) } S=\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\} S={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
- 网格中的每一个位置都是一个状态。状态集为:
-
动作空间 ( A A A):
- 机器人在每个状态下可以采取的动作包括四个方向:
$A = {\text{上(Up)}, \text{下(Down)}, \text{左(Left)}, \text{右(Right)}}
$
- 机器人在每个状态下可以采取的动作包括四个方向:
-
状态转移函数 ( P ( s ′ ∣ s , a ) P(s'|s, a) P(s′∣s,a) ):
- 在本例中,我们假设状态转移是确定性的,即执行某一动作后,机器人总是移动到预期的下一个状态,除非碰到边界或障碍物。
-
奖励函数 ( R ( s , a ) R(s, a) R(s,a) ):
- 奖励设计如下:
- 到达终点 ( 3 , 3 ) (3,3) (3,3)时,获得奖励 ($ +10 $)。
- 移动到障碍物 ( 2 , 2 ) (2,2) (2,2)时,获得惩罚 ( − 10 -10 −10 )。
- 其他每次合法移动获得惩罚 ( $-1 $)(鼓励机器人尽快到达终点)。
- 奖励设计如下:
-
折扣因子 ($ \gamma $):
- 设置为 ( γ = 0.9 \gamma = 0.9 γ=0.9 ),用于平衡即时奖励与未来奖励的重要性。
强化学习算法:Q-Learning
Q学习是一种无模型的强化学习算法,通过学习一个动作-价值函数 ($ Q(s, a)$ ) 来估计在状态 ($ s$ ) 下采取动作 ( a a a ) 的长期收益。算法的目标是学习最优策略,使得在每个状态下选择的动作都能最大化累积奖励。
Q学习更新规则:
Q ( s , a ) ← Q ( s , a ) + α [ R ( s , a ) + γ max a ′ Q ( s ′ , a ′ ) − Q ( s , a ) ] Q(s, a) \leftarrow Q(s, a) + \alpha \left[ R(s, a) + \gamma \max_{a'} Q(s', a') - Q(s, a) \right] Q(s,a)←Q(s,a)+α[R(s,a)+γmaxa′Q(s′,a′)−Q(s,a)]
上面这个公式为 B e l l m a n Bellman Bellman方程
其中:
- $\alpha $ 是学习率,控制更新步长。
- R ( s , a ) R(s, a) R(s,a) 是执行动作 ( a a a ) 后获得的即时奖励。
- $s’ $是执行动作 ( a a a ) 后到达的下一个状态。
- max a ′ Q ( s ′ , a ′ ) \max_{a'} Q(s', a') maxa′Q(s′,a′) 是在下一个状态 ( s ′ s' s′ ) 下,所有可能动作的最大Q值。
参数设置:
- 学习率 ($ \alpha = 0.5 $)
- 折扣因子 ($ \gamma = 0.9$ )
- 初始化 ( Q ( s , a ) = 0 Q(s, a) = 0 Q(s,a)=0 ) 对所有 ($ s \in S $) 和 ( a ∈ A a \in A a∈A )
具体实例与推断计算过程
我们将通过几个训练回合( e p i s o d e s episodes episodes)来展示Q学习算法的工作过程。
回合1( E p i s o d e 1 Episode 1 Episode1)
Step 1:
- 当前状态: s = ( 1 , 1 ) s = (1,1) s=(1,1)
- 选择动作:假设机器人随机选择 右( R i g h t Right Right)。
- 执行动作:从 $(1,1) 向右移动到 向右移动到 向右移动到 (1,2)$ 。
- 获得奖励:$ R = -1$ (普通移动)。
- 下一个状态:$ s’ = (1,2) $
- Q值更新:
Q ( ( 1 , 1 ) , Right ) ← 0 + 0.5 × [ − 1 + 0.9 × max a ′ Q ( ( 1 , 2 ) , a ′ ) − 0 ] Q((1,1), \text{Right}) \leftarrow 0 + 0.5 \times [ -1 + 0.9 \times \max_{a'} Q((1,2), a') - 0 ] Q((1,1),Right)←0+0.5×[−1+0.9×maxa′Q((1,2),a′)−0]- 由于所有 $Q((1,2), a’) = 0 $,则:
Q ( ( 1 , 1 ) , Right ) ← 0 + 0.5 × [ − 1 + 0 − 0 ] = 0 + 0.5 × ( − 1 ) = − 0.5 Q((1,1), \text{Right}) \leftarrow 0 + 0.5 \times [ -1 + 0 - 0 ] = 0 + 0.5 \times (-1) = -0.5 Q((1,1),Right)←0+0.5×[−1+0−0]=0+0.5×(−1)=−0.5
- 由于所有 $Q((1,2), a’) = 0 $,则:
这里的0是因为我们的链表并未记录 Q ( ( 1 , 2 ) , a ′ ) Q((1,2), a') Q((1,2),a′)的值,需要等后面表更新后才会有值,请继续往下看
Step 2:
- 当前状态: s = ( 1 , 2 ) s = (1,2) s=(1,2)
- 选择动作:假设机器人随机选择 下( D o w n Down Down)。
- 执行动作:从 $(1,2) $向下移动到 $ (2,2) $。
- 获得奖励:$R = -10 $(撞到障碍物)。
- 下一个状态: $s’ = (2,2) $(障碍物,假设此时回合结束,并重置到起点)。
- Q值更新:
Q ( ( 1 , 2 ) , Down ) ← 0 + 0.5 × [ − 10 + 0.9 × max a ′ Q ( ( 2 , 2 ) , a ′ ) − 0 ] Q((1,2), \text{Down}) \leftarrow 0 + 0.5 \times [ -10 + 0.9 \times \max_{a'} Q((2,2), a') - 0 ] Q((1,2),Down)←0+0.5×[−10+0.9×maxa′Q((2,2),a′)−0]- $(2,2) $是终止状态,假设所有 $ Q((2,2), a’) = 0$ ,则:
Q ( ( 1 , 2 ) , Down ) ← 0 + 0.5 × [ − 10 + 0 − 0 ] = 0 + 0.5 × ( − 10 ) = − 5.0 Q((1,2), \text{Down}) \leftarrow 0 + 0.5 \times [ -10 + 0 - 0 ] = 0 + 0.5 \times (-10) = -5.0 Q((1,2),Down)←0+0.5×[−10+0−0]=0+0.5×(−10)=−5.0
- $(2,2) $是终止状态,假设所有 $ Q((2,2), a’) = 0$ ,则:
回合1结束。Q表部分更新如下:
状态 | 动作 | Q值 |
---|---|---|
( 1 , 1 ) (1,1) (1,1) | R i g h t Right Right | − 0.5 -0.5 −0.5 |
( 1 , 2 ) (1,2) (1,2) | D o w n Down Down | − 5.0 -5.0 −5.0 |
其他状态 | 其他动作 | 0 0 0 |
回合2( E p i s o d e 2 Episode 2 Episode2)
Step 1:
- 当前状态: s = ( 1 , 1 ) s = (1,1) s=(1,1)
- 选择动作:假设机器人选择 下( D o w n Down Down)。
- 执行动作:从 ( 1 , 1 ) (1,1) (1,1) 向下移动到 ( 2 , 1 ) (2,1) (2,1) 。
- 获得奖励:$ R = -1$ (普通移动)。
- 下一个状态:$ s’ = (2,1)$
- Q值更新:
Q ( ( 1 , 1 ) , Down ) ← 0 + 0.5 × [ − 1 + 0.9 × max a ′ Q ( ( 2 , 1 ) , a ′ ) − 0 ] Q((1,1), \text{Down}) \leftarrow 0 + 0.5 \times [ -1 + 0.9 \times \max_{a'} Q((2,1), a') - 0 ] Q((1,1),Down)←0+0.5×[−1+0.9×maxa′Q((2,1),a′)−0]- 由于所有 Q ( ( 2 , 1 ) , a ′ ) = 0 Q((2,1), a') = 0 Q((2,1),a′)=0 ,则:
Q ( ( 1 , 1 ) , Down ) ← 0 + 0.5 × [ − 1 + 0 − 0 ] = 0 + 0.5 × ( − 1 ) = − 0.5 Q((1,1), \text{Down}) \leftarrow 0 + 0.5 \times [ -1 + 0 - 0 ] = 0 + 0.5 \times (-1) = -0.5 Q((1,1),Down)←0+0.5×[−1+0−0]=0+0.5×(−1)=−0.5
- 由于所有 Q ( ( 2 , 1 ) , a ′ ) = 0 Q((2,1), a') = 0 Q((2,1),a′)=0 ,则:
Step 2:
- 当前状态:$ s = (2,1)$
- 选择动作:假设机器人随机选择 右( R i g h t Right Right)。
- 执行动作:从 $(2,1) $ 向右移动到 ( 2 , 2 ) (2,2) (2,2) 。
- 获得奖励:$R = -10 $(撞到障碍物)。
- 下一个状态: s ′ = ( 2 , 2 ) s' = (2,2) s′=(2,2) (障碍物,回合结束,重置到起点)。
- Q值更新:
Q ( ( 2 , 1 ) , Right ) ← 0 + 0.5 × [ − 10 + 0.9 × max a ′ Q ( ( 2 , 2 ) , a ′ ) − 0 ] Q((2,1), \text{Right}) \leftarrow 0 + 0.5 \times [ -10 + 0.9 \times \max_{a'} Q((2,2), a') - 0 ] Q((2,1),Right)←0+0.5×[−10+0.9×maxa′Q((2,2),a′)−0]- ( 2 , 2 ) (2,2) (2,2) 是终止状态,假设所有 $Q((2,2), a’) = 0 $,则:
Q ( ( 2 , 1 ) , Right ) ← 0 + 0.5 × [ − 10 + 0 − 0 ] = 0 + 0.5 × ( − 10 ) = − 5.0 Q((2,1), \text{Right}) \leftarrow 0 + 0.5 \times [ -10 + 0 - 0 ] = 0 + 0.5 \times (-10) = -5.0 Q((2,1),Right)←0+0.5×[−10+0−0]=0+0.5×(−10)=−5.0
- ( 2 , 2 ) (2,2) (2,2) 是终止状态,假设所有 $Q((2,2), a’) = 0 $,则:
回合2结束。Q表部分更新如下:
状态 | 动作 | Q值 |
---|---|---|
( 1 , 1 ) (1,1) (1,1) | R i g h t Right Right | − 0.5 -0.5 −0.5 |
( 1 , 1 ) (1,1) (1,1) | D o w n Down Down | − 0.5 -0.5 −0.5 |
( 1 , 2 ) (1,2) (1,2) | D o w n Down Down | − 5.0 -5.0 −5.0 |
( 2 , 1 ) (2,1) (2,1) | R i g h t Right Right | − 5.0 -5.0 −5.0 |
其他状态 | 其他动作 | 0 0 0 |
回合3( E p i s o d e 3 Episode 3 Episode3)
Step 1:
- 当前状态:$ s = (1,1)$
- 选择动作:为了展示Q值更新,我们选择 右( R i g h t Right Right)。
- 执行动作:从 $ (1,1) $向右移动到 $(1,2) $。
- 获得奖励:$ R = -1$ (普通移动)。
- 下一个状态:$ s’ = (1,2) $
- Q值更新:
Q ( ( 1 , 1 ) , Right ) ← − 0.5 + 0.5 × [ − 1 + 0.9 × max a ′ Q ( ( 1 , 2 ) , a ′ ) − ( − 0.5 ) ] Q((1,1), \text{Right}) \leftarrow -0.5 + 0.5 \times [ -1 + 0.9 \times \max_{a'} Q((1,2), a') - (-0.5) ] Q((1,1),Right)←−0.5+0.5×[−1+0.9×maxa′Q((1,2),a′)−(−0.5)]- 首先计算内部括号的值:
− 1 + 0.9 × max a ′ Q ( ( 1 , 2 ) , a ′ ) − ( − 0.5 ) -1 + 0.9 \times \max_{a'} Q((1,2), a') - (-0.5) −1+0.9×maxa′Q((1,2),a′)−(−0.5)- 现有 $ Q((1,2), a’)$ : $Q((1,2), \text{Down}) = -5.0 ,其他动作( ,其他动作( ,其他动作(Up, Left, Right$)尚未更新,假设为 ( 0 0 0 )。
- 因此:
max a ′ Q ( ( 1 , 2 ) , a ′ ) = max ( − 5.0 , 0 , 0 , 0 ) = 0 \max_{a'} Q((1,2), a') = \max(-5.0, 0, 0, 0) = 0 maxa′Q((1,2),a′)=max(−5.0,0,0,0)=0 - 将数值代入:
− 1 + 0.9 × 0 − ( − 0.5 ) = − 1 + 0 + 0.5 = − 0.5 -1 + 0.9 \times 0 - (-0.5) = -1 + 0 + 0.5 = -0.5 −1+0.9×0−(−0.5)=−1+0+0.5=−0.5
- 完整更新:
Q ( ( 1 , 1 ) , Right ) ← − 0.5 + 0.5 × ( − 0.5 ) = − 0.5 − 0.25 = − 0.75 Q((1,1), \text{Right}) \leftarrow -0.5 + 0.5 \times (-0.5) = -0.5 - 0.25 = -0.75 Q((1,1),Right)←−0.5+0.5×(−0.5)=−0.5−0.25=−0.75
- 首先计算内部括号的值:
Step 2:
- 当前状态: s = ( 1 , 2 ) s = (1,2) s=(1,2)
- 选择动作:为了继续展示,我们选择 左( L e f t Left Left)。
- 执行动作:从 $(1,2) $向左移动到 $ (1,1) $。
- 获得奖励: R = − 1 R = -1 R=−1 (普通移动)。
- 下一个状态: s ′ = ( 1 , 1 ) s' = (1,1) s′=(1,1)
- Q值更新:
Q ( ( 1 , 2 ) , Left ) ← 0 + 0.5 × [ − 1 + 0.9 × max a ′ Q ( ( 1 , 1 ) , a ′ ) − 0 ] Q((1,2), \text{Left}) \leftarrow 0 + 0.5 \times [ -1 + 0.9 \times \max_{a'} Q((1,1), a') - 0 ] Q((1,2),Left)←0+0.5×[−1+0.9×maxa′Q((1,1),a′)−0]- 现有 $ Q((1,1), a’)$ : $Q((1,1), \text{Right}) = -0.75 , , ,Q((1,1), \text{Down}) = -0.5 ,其他动作( ,其他动作( ,其他动作(Up, Left$)尚未更新,假设为( $0 $)。
- 因此:
max a ′ Q ( ( 1 , 1 ) , a ′ ) = max ( − 0.75 , − 0.5 , 0 , 0 ) = 0 \max_{a'} Q((1,1), a') = \max(-0.75, -0.5, 0, 0) = 0 maxa′Q((1,1),a′)=max(−0.75,−0.5,0,0)=0 - 将数值代入:
Q ( ( 1 , 2 ) , Left ) ← 0 + 0.5 × [ − 1 + 0.9 × 0 − 0 ] = 0 + 0.5 × ( − 1 ) = − 0.5 Q((1,2), \text{Left}) \leftarrow 0 + 0.5 \times [ -1 + 0.9 \times 0 - 0 ] = 0 + 0.5 \times (-1) = -0.5 Q((1,2),Left)←0+0.5×[−1+0.9×0−0]=0+0.5×(−1)=−0.5
Step 3:
- 当前状态: s = ( 1 , 1 ) s = (1,1) s=(1,1)
- 选择动作:为了展示进一步的更新,我们选择 下( D o w n Down Down)。
- 执行动作:从 $ (1,1) $向下移动到 $ (2,1) $。
- 获得奖励: R = − 1 R = -1 R=−1(普通移动)。
- 下一个状态: s ′ = ( 2 , 1 ) s' = (2,1) s′=(2,1)
- Q值更新:
Q ( ( 1 , 1 ) , Down ) ← − 0.5 + 0.5 × [ − 1 + 0.9 × max a ′ Q ( ( 2 , 1 ) , a ′ ) − ( − 0.5 ) ] Q((1,1), \text{Down}) \leftarrow -0.5 + 0.5 \times [ -1 + 0.9 \times \max_{a'} Q((2,1), a') - (-0.5) ] Q((1,1),Down)←−0.5+0.5×[−1+0.9×maxa′Q((2,1),a′)−(−0.5)]- 计算内部括号的值:
− 1 + 0.9 × max a ′ Q ( ( 2 , 1 ) , a ′ ) − ( − 0.5 ) -1 + 0.9 \times \max_{a'} Q((2,1), a') - (-0.5) −1+0.9×maxa′Q((2,1),a′)−(−0.5)- 现有 $Q((2,1), a’) $: Q ( ( 2 , 1 ) , Right ) = − 5.0 Q((2,1), \text{Right}) = -5.0 Q((2,1),Right)=−5.0 ,其他动作( U p , D o w n , L e f t Up, Down, Left Up,Down,Left)尚未更新,假设为 ( 0 0 0 )。
- 因此:
max a ′ Q ( ( 2 , 1 ) , a ′ ) = max ( − 5.0 , 0 , 0 , 0 ) = 0 \max_{a'} Q((2,1), a') = \max(-5.0, 0, 0, 0) = 0 maxa′Q((2,1),a′)=max(−5.0,0,0,0)=0 - 将数值代入:
− 1 + 0.9 × 0 − ( − 0.5 ) = − 1 + 0 + 0.5 = − 0.5 -1 + 0.9 \times 0 - (-0.5) = -1 + 0 + 0.5 = -0.5 −1+0.9×0−(−0.5)=−1+0+0.5=−0.5
- 完整更新:
Q ( ( 1 , 1 ) , Down ) ← − 0.5 + 0.5 × ( − 0.5 ) = − 0.5 − 0.25 = − 0.75 Q((1,1), \text{Down}) \leftarrow -0.5 + 0.5 \times (-0.5) = -0.5 - 0.25 = -0.75 Q((1,1),Down)←−0.5+0.5×(−0.5)=−0.5−0.25=−0.75
- 计算内部括号的值:
回合3结束。Q表部分更新如下:
状态 | 动作 | Q值 |
---|---|---|
( 1 , 1 ) (1,1) (1,1) | R i g h t Right Right | − 0.75 -0.75 −0.75 |
( 1 , 1 ) (1,1) (1,1) | D o w n Down Down | − 0.75 -0.75 −0.75 |
( 1 , 2 ) (1,2) (1,2) | D o w n Down Down | − 5.0 -5.0 −5.0 |
( 1 , 2 ) (1,2) (1,2) | L e f t Left Left | − 0.5 -0.5 −0.5 |
( 2 , 1 ) (2,1) (2,1) | R i g h t Right Right | − 5.0 -5.0 −5.0 |
其他状态 | 其他动作 | 0 0 0 |
总结
通过上述多个回合的训练,Q学习算法逐步更新了各个状态-动作对的Q值。随着训练的进行,Q值将逐渐逼近真实的动作价值,从而指导机器人选择最优路径到达目标,同时避开障碍物。
在实际应用中,随着更多回合的训练,Q表中的Q值会不断优化。例如,机器人可能学会以下策略:
- 从 ( 1 , 1 ) (1,1) (1,1) 向右移动到 ( 1 , 2 ) (1,2) (1,2) ,然后向下到 ( 1 , 3 ) (1,3) (1,3),再向下到 $ (2,3) $,最后向下到 $ (3,3) $,以避开障碍物 $(2,2) $。
- 从 $(1,1) $向下移动到 $ (2,1) $,然后向下到 $ (3,1) $,再向右到 $ (3,2) $,最后向右到 $ (3,3) $。
通过这种方式, M D P MDP MDP框架结合强化学习算法(如Q学习)能够有效地帮助机器人在复杂环境中学习和优化决策策略。
Q-learning:强化学习中的基础算法
Q-learning是强化学习(Reinforcement Learning)领域中的一种经典算法,它通过不断地与环境交互,学习在不同状态下采取何种行动才能获得最大的累计奖励。
Q-learning 的优点
- 模型无关:不需要对环境进行建模。
- 离线学习:可以利用历史数据进行学习。
- 收敛性:在一定的条件下,Q-learning 能够收敛到最优策略。
Q-learning 的局限性
- 维度灾难:当状态空间和动作空间非常大时,Q值表的存储和更新会变得非常困难。
- 不适用于连续状态和动作空间:对于连续的状态和动作空间,需要采用函数逼近的方法来表示Q值函数。
深度Q网络 (Deep Q-Network, DQN)
为了解决Q-learning 在高维状态空间中的问题,DeepMind 提出了深度Q网络。DQN 将神经网络与Q-learning 结合起来,用神经网络来逼近Q值函数,从而能够处理高维的输入。
总结
Q-learning 是强化学习领域的基础算法,它为后续的强化学习算法奠定了基础。虽然Q-learning 存在一些局限性,但是通过与其他技术的结合,如深度学习,Q-learning 仍然在很多领域得到了广泛应用,例如游戏、机器人控制等。
- ε-greedy 策略:一种平衡探索和利用的策略。
- Bellman 方程:动态规划中的一个重要方程,用于计算最优值函数。
- 深度Q网络 (DQN):如何将神经网络应用于Q-learning。
- 其他强化学习算法:如SARSA、Policy Gradient等。
代码实现
问题描述
假设我们有一个简单的迷宫,智能体(agent)的目标是从起点到达终点。迷宫中的每个格子都是一个状态,智能体可以选择上下左右四个方向移动。当智能体到达终点时,会获得一个正的奖励,其他状态的奖励为0。
Q-Learning代码实现
import numpy as np# 定义迷宫
maze = np.array([[0, 0, 1, 0],[0, 0, 0, 0],[0, 0, 1, 0],[0, 1, 0, 0]
])
# 1表示墙壁,0表示可通行
goal = (3, 3)# 定义动作
actions = ['up', 'down', 'left', 'right']# 超参数设置
alpha = 0.1 # 学习率
gamma = 0.9 # 折扣因子
epsilon = 0.1 # 探索率# 初始化Q表
Q = np.zeros((maze.shape[0], maze.shape[1], len(actions)))def choose_action(state):if np.random.uniform(0, 1) < epsilon:action_index = np.random.choice(len(actions))else:action_index = np.argmax(Q[state])return action_indexdef take_action(state, action_index):i, j = stateif actions[action_index] == 'up':next_i = max(i - 1, 0)next_j = j# ... 其他动作的处理if maze[next_i, next_j] == 1: # 如果撞墙,则留在原地next_i, next_j = i, jreturn (next_i, next_j)def update_q(state, action, reward, next_state):Q[state][action] += alpha * (reward + gamma * np.max(Q[next_state]) - Q[state][action])# 训练过程
num_episodes = 1000
for episode in range(num_episodes):state = (0, 0) # 初始化状态while state != goal:action_index = choose_action(state)next_state = take_action(state, action_index)reward = 1 if next_state == goal else 0update_q(state, action_index, reward, next_state)state = next_state# 使用训练好的Q表进行控制
state = (0, 0)
while state != goal:action_index = np.argmax(Q[state])state = take_action(state, action_index)print(state)
代码解释
- 迷宫定义: 用一个二维数组表示迷宫,1表示墙壁,0表示可通行。
- 动作定义: 定义了四个可能的动作:上、下、左、右。
- Q表初始化: 初始化一个三维数组,用来存储在不同状态下执行不同动作的Q值。
- 选择动作: 根据ε-greedy策略选择动作,在探索和利用之间平衡。
- 执行动作: 根据选择的动作更新智能体的位置,并判断是否撞墙。
- 更新Q值: 根据Bellman方程更新Q值。
- 训练过程: 重复进行多个episode,直到智能体学会找到从起点到终点的最优路径。
运行结果
运行这段代码后,你将会看到智能体逐渐学会从起点到达终点的最优路径。
注意
- 简化版本: 上述代码是一个简化的版本,没有考虑连续状态和动作空间,也没有使用神经网络来逼近Q值函数。
- 改进方向: 可以尝试使用更复杂的迷宫、增加噪声、或者使用深度Q网络来解决更复杂的问题。
想了解更多吗?
- 可视化: 可以使用可视化工具将迷宫和智能体的行动轨迹展示出来,更直观地观察学习过程。
- 其他环境: 可以将Q-learning应用到其他环境中,比如游戏、机器人控制等。
- 深度强化学习: 可以将Q-learning与深度学习结合起来,解决更复杂的问题。
关于作者
大家好,我是孙成,新加坡国立大学2024级机器人学研究生
喜欢动手做一些有意思的东西(虽然是个手残党…)
喜欢尝试,不怕丢脸
博客地址:CSDN主页
代码仓库:常用:Github、不定时同步:Gitee
Email:scforwork@163.com
WeChat: ac20311
这篇关于马尔可夫决策过程(Markov decision process,MDP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!