1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 人工智能

Sarsa算法和Q-learning算法

• 人工智能 • 阅读 90

1、马尔可夫决策过程(MDP)四元组

马尔可夫四元组

s：state 状态
a：action 动作
r：reward 奖励
p：policy 状态转移概率 p ( s t + 1 , r t ∣ s t , a t ) p(s_{t+1},r_t | s_t,a_t)p (s t +1 ​,r t ​∣s t ​,a t ​)，变表示在 t 时刻的状态 s t s_t s t ​ 下，采取动作 a t a_t a t ​ ，状态转移到 s t + 1 s_{t+1}s t +1 ​ 并且收获奖励 r t r_t r t ​
的概率。此处，假设假设事件具有马尔科夫性，该决策过程为一个马尔可夫决策过程 (MDP)。
故：马尔可夫决策过程四元组（MDP四元组）为 (s,a,r,p)

另外：五元组 则是多一个 折扣因子参数 γ，用于表示未来对当前的 reward 的影响， 0≤γ≤1， γ=0_表示只关注当前 action 在下一步带来的reward； γ=1_表示当前 action 在未来所有时间带来的 reward。

2、Q表格

Sarsa和Q-learning都是基于表格的强化学习算法，在此，先对Q表格做简单介绍。

Q表格是一个维度为 M * N 的表格，其中， M_表示某一环境下所有的状态 (observation) 数量； N表示所有可采取的行为 (action) 的数量；其中的每一个值 Q代表在某一个状态下采取一个行为的长远收益，此处长远收益区别于 reward， reward为每一个动作的奖励，Q代表在某一个状态下采取某一个行为在未来会产生的收益_，公式如下：

Q = r e w a r d 1 + γ ∗ r e w a r d 2 + . . . + γ ∗ r e w a r d n \ Q=reward_1+\gamma *reward_2+…+\gamma * reward_n Q =r e w a r d 1 ​+γ∗r e w a r d 2 ​+…+γ∗r e w a r d n ​

其中， γ∈(0,1)， 当 γ=0_表示只看当前一步带来的收益；当 γ=1_表示关注未来所有带来的收益。

举例说明Q表格的作用，以＂ 悬崖漫步＂环境为例

observation/action0123100002000030000……………

上述示例中， observation 表示所有的状态，action表示所有的行为，在悬崖环境下，observation就是 agent的坐标，每个值代表一个坐标，例如1代表（0，0）点； action有四个， 0,1,2,3分别代表 上、下、左、右四个方向的行动。

有了Q表格，就可以根据其中的Q值选取合适的action，不断用选择的action与环境交互得到经验，更新优化Q值，这就是强化学习的过程，最后达到收敛状态。收敛时Q表格的变化应该趋于0.

这也是Sarsa 和 Q-learning的算法的学习思路，下面对两种算法进行说明。

３、Sarsa算法

强化学习中agent 的需要做的两件事：一是选择action（采用ε-greedy方法，在代码视线中会有介绍）；二是学习learning，也就是更新Q表格。

Sarsa根据下一步的Q值更新当前的Q值，下面给出Sarsa的流程。

３.1 Sarsa算法流程

首先，Sarsa更新Q值采用时序差分的方式进行更新，其更新公式如下：

Q ∗ ( s t , a t ) = Q ( s t , a t ) + α [ r t + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ] \ Q^*(s_t,a_t) = Q(s_t,a_t) + \alpha[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]Q ∗(s t ​,a t ​)=Q (s t ​,a t ​)+α[r t ​+γQ (s t +1 ​,a t +1 ​)−Q (s t ​,a t ​)]

该更新方式为 时序差分更新，即：当前值 +【（目标值-当前值）✖ 学习因子 】

Sarsa 的算法流程则是完全按照上述的思路进行： 需要当前的状态s t s_t s t ​ ，当前的行为a t a_t a t ​ ，当前行为的奖励r t r_t r t ​ ，采取当前行为后环境达到的新的状态s t + 1 s_{t+1}s t +1 ​ ，下一步的行为a t + 1 a_{t+1}a t +1 ​，这也是Sarsa算法名称的由来。

Sarsa算法和Q-learning算法

; ３.2 Sarsa实现

下面以＂ 悬崖漫步＂环境为例，简单介绍Sarsa算法的实现：

首先创建Agent 类，如上所述，实现Agent的两个方法：选择action，更新Q值

"""
-*- coding:utf-8 -*-
@Time       :2022/5/27 11:21
@AUTHOR     :Lxy
@SOFTWARE   :RL
@description:
@para       :
"""
import random

import numpy as np

class Agent:
"""
    :param:observation为所有状态数量
    :param:act_n为所有的策略数量
    :param:epsilong为 ε-greedy 算法中的概率值
    :param:gama为折扣因子，表示当前action在未来带来的收益的衰减因子
    :param:alfa为学习率
"""

    def __init__(self, obser_n, act_n, epsilong, gama, alfa):
        self.act_n = act_n
        self.Q_table = np.zeros((obser_n, act_n))
        self.epsilong = epsilong
        self.gama = gama
        self.alfa = alfa

"""
    根据当前 Observation选择最优 action,采用 ε-greedy 算法，即：ε 概率探索，否则选择Q值最大的策略
    每个observation 用一个数字表示，例如：索引1表示observation（1，1）
"""

    def actionChoose(self, observation):
        Q_observation = self.Q_table[observation, :]
        if random.uniform(0, 1) > (1 - self.epsilong):
            return np.random.choice(self.act_n)
        else:
            return self.getMaxOfQtable(observation)

    def getMaxOfQtable(self, observation):
        Q_observation = self.Q_table[observation, :]
        maxList = np.where(Q_observation == max(Q_observation))[0]
        return np.random.choice(maxList)

    def learn(self, observation, action, reward, next_observation, next_action, is_done):
        if is_done:
            target_value = reward
            this_value = self.Q_table[observation][action]
            self.Q_table[observation][action] += self.alfa * (target_value - this_value)
        else:

            target_value = reward + self.gama * self.Q_table[next_observation][next_action]

            this_value = self.Q_table[observation][action]

            diff = target_value - this_value

            self.Q_table[observation][action] += self.alfa * diff

    def getQtable(self):
        return self.Q_table

然后，train.py 用于训练

"""
-*- coding:utf-8 -*-
@Time       :2022/5/27 14:13
@AUTHOR     :Lxy
@SOFTWARE   :RL
@description:
@para       :
"""
import gym
from Agent import Agent
import matplotlib.pyplot as plt

def main():
    env = gym.make("CliffWalking-v0")
    agent = Agent(
        obser_n=env.observation_space.n,
        act_n=env.action_space.n,
        epsilong=0.1,
        gama=0.9,
        alfa=0.01
    )
    rewardList = []
    for epoch in range(1000):
        observation = env.reset()
        action = agent.actionChoose(observation=observation)
        step = 0
        total_reward = 0
        while True:
            next_observation, reward, is_done, _ = env.step(action)
            next_action = agent.actionChoose(next_observation)
            agent.learn(observation, action, reward, next_observation, next_action, is_done)
            observation = next_observation
            action = next_action
            total_reward += reward
            step += 1
            if is_done:
                break
        print("第" + str(epoch + 1) + "个epoch.......")
        print("总step:" + str(step))
        print("总reward:" + str(total_reward))
        print("-------------------------------------------------")
        rewardList.append(total_reward)
    print(agent.getQtable())

    plt.plot(rewardList)
    plt.title("Sarsa")
    plt.show()

if __name__ == "__main__":
    main()

４、Q-learning算法

Q-learning算法与Sarsa基本类似，都采用 ε-greedy算法选择行为。区别在于，Q-learning在更新下一步的Q值的时候不关心下一步所采取的行为action，而是使用下一步中最大的Q值来更新当前步的Q值。 也就是说，Q-learning不管下一步的行为是什么，始终选择下一步最大的行为的Q值来更新当前步的Q值。
这也是Q-learning的两种策略， 行为策略和 目标策略，其中行为策略采用 ε-greedy算法选择下一步的i行为； 目标策略则选择下一步最大的Q值来更新当前的Q值。而Sarsa中只存在一种策略。

４.1 Q-learning算法流程

Q-learning的Q值更新方式同样采用时序差分的方式，与Sarsa相同，不同点是目标值不同，直接给出 Q-learning的Q更新公式：

Q ∗ ( s t , a t ) = Q ( s t , a t ) + α [ r t + γ max ⁡ a ′ ( Q ( s t + 1 , a ′ ) ) − Q ( s t , a t ) ] \ Q^*(s_t,a_t) = Q(s_t,a_t) + \alpha[r_t+\gamma \max_{a’} (Q(s_{t+1},a’))-Q(s_t,a_t)]Q ∗(s t ​,a t ​)=Q (s t ​,a t ​)+α[r t ​+γa ′max ​(Q (s t +1 ​,a ′))−Q (s t ​,a t ​)]

以及算法流程：

Sarsa算法和Q-learning算法

; ４.2 Q-learning实现

Ｑ-learning的实现方式与Sarsa相同，只是修改了Q值更新的方式

首先创建Agent 类，如上所述，实现Agent的两个方法：选择action，更新Q值

"""
-*- coding:utf-8 -*-
@Time       :2022/5/31 11:45
@AUTHOR     :Lxy
@SOFTWARE   :RL
@description:
@para       :
"""

import random
import numpy as np

class Agent:
"""
    :param:observation为所有状态数量
    :param:act_n为所有的策略数量
    :param:epsilong为 ε-greedy 算法中的概率值
    :param:gama为折扣因子，表示当前action在未来带来的收益的衰减因子
    :param:alfa为学习率
"""

    def __init__(self, obser_n, act_n, epsilong, gama, alfa):
        self.act_n = act_n
        self.Q_table = np.zeros((obser_n, act_n))
        self.epsilong = epsilong
        self.gama = gama
        self.alfa = alfa

"""
    根据当前 Observation选择最优 action,采用 ε-greedy 算法，即：ε 概率探索，否则选择Q值最大的策略
    每个observation 用一个数字表示，例如：索引1表示observation（1，1）
"""

    def actionChoose(self, observation):
        Q_observation = self.Q_table[observation, :]
        if random.uniform(0, 1) > (1 - self.epsilong):
            return np.random.choice(self.act_n)
        else:
            return self.getMaxOfQtable(observation)

    def getMaxOfQtable(self, observation):
        Q_observation = self.Q_table[observation, :]
        maxList = np.where(Q_observation == max(Q_observation))[0]
        return np.random.choice(maxList)

    def learn(self, observation, action, reward, next_observation, next_action, is_done):
        if is_done:
            target_value = reward
            this_value = self.Q_table[observation][action]
            self.Q_table[observation][action] += self.alfa * (target_value - this_value)
        else:

            target_value = reward + self.gama * max(self.Q_table[next_observation, :])

            this_value = self.Q_table[observation][action]

            diff = target_value - this_value

            self.Q_table[observation][action] += self.alfa * diff

    def getQtable(self):
        return self.Q_table

然后，train.py 用于训练

"""
-*- coding:utf-8 -*-
@Time       :2022/5/31 11:46
@AUTHOR     :Lxy
@SOFTWARE   :RL
@description:
@para       :
"""

import gym
from QlearningAgent import Agent
import matplotlib.pyplot as plt

def main():
    env = gym.make("CliffWalking-v0")
    agent = Agent(
        obser_n=env.observation_space.n,
        act_n=env.action_space.n,
        epsilong=0.1,
        gama=0.9,
        alfa=0.01
    )
    rewardList = []
    for epoch in range(1000):
        observation = env.reset()
        action = agent.actionChoose(observation=observation)
        step = 0
        total_reward = 0
        while True:
            next_observation, reward, is_done, _ = env.step(action)
            next_action = agent.actionChoose(next_observation)
            agent.learn(observation, action, reward, next_observation, next_action, is_done)
            observation = next_observation
            action = next_action
            total_reward += reward
            step += 1
            if is_done:
                break
        print("第" + str(epoch + 1) + "个epoch.......")
        print("总step:" + str(step))
        print("总reward:" + str(total_reward))
        print("-------------------------------------------------")
        rewardList.append(total_reward)
    print(agent.getQtable())

    plt.plot(rewardList)
    plt.title("Q-learning")
    plt.show()

if __name__ == "__main__":
    main()

５、on-policy和off-policy

理解了Sarsa和Q-learning的区别就能理解on-policy和off-policy，下面再次进行解释

on-policy 在只存在一种策略，无论是选择 action 还是更新Q值，都采用同一种策略，也就是说，on-policy更新Q值采用的 action 和下一步选择的 action 一定是相同的；也就是 Sarsa 算法。
off-policy 存在两种策略， 行为策略和 目标策略，行为策略用于与环境交互，不断探索环境，将环境的反馈回馈给目标策略，目标策略更新Q值。 也就是说，off-policy 更新Q和选择 action 不是同一种策略，也就是Q-learning算法。选择下一步实际的 action 时采用是ε-greedy 算法，但是在更新Q值时采用最大的 action。

6、代码

以上所有可执行代码均存放于我的gitee，地址：强化学习

Original: https://blog.csdn.net/weixin_43340697/article/details/125094732
Author: 桂花味的六神
Title: Sarsa算法和Q-learning算法

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/651230/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球