强化学习

初识强化学习

机器学习分类

强化学习

强化学习(Reinforcement Learning)这一名词来源于行为心理学,表示生物为了趋利避害而更频繁实施对自己有利的策略。

例如,在工作中会根据策略决定做出各种动作。如果我的某些决定使我升职加薪,而另外一些决策使我受到了处罚,那么我在以后的工作中会更多采用使我升职加薪的决策。

正强化 VS 负强化

• 正强化使得生物趋向于获得更多利益。(升职加薪)
• 负强化使得生物趋向于避免损害。(遭受处罚)

人工智能领域中有许多类似的趋利避害的问题。例如,著名的围棋AI程序AlphaGo可以根据不同的围棋局势下不同的棋。如果它下得好,它就会赢;如果下得不好,它就会输。它根据下棋的经验不断改进自己的棋艺。

人工智能借用了行为心理学的这一概念,把与环境交互中趋利避害的学习过程称为强化学习。

强化学习的分类

强化学习的关键元素

在一个强化学习系统中,决策者可以观察环境,并根据观测做出行动。在行动之后,能够获得奖励。强化学习通过与环境的交互来学习如何最大化奖励。

例如,一个走迷宫的机器人在迷宫里游荡(见图1-1)。机器人观察周围的环境,并且根据观测来决定如何移动。错误的移动会让机器人浪费宝贵的时间和能量,正确的移动会让机器人成功走出迷宫。在这个例子中,机器人的移动就是它根据观测而采取的行动,浪费的时间能量和走出迷宫的成功就是给机器人的奖励(时间能量的浪费可以看作负奖励)。

强化学习的最大特点是在学习过程中没有正确答案,而是通过奖励信号来学习。

• 奖励(Reward):奖励是强化学习系统的学习目标。学习者在行动后会接收到环境发来的奖励,而强化学习的目标就是要最大化在长时间里的总奖励。
• 策略(Policy):决策者会根据不同的观测决定采用不同的动作,这种从观测到动作的关系称为策略。强化学习的学习对象就是策略。强化学习通过改进策略以期望获取最大化的总奖励。

强化学习的应用

1. 电动游戏:主要指玩家需要根据屏幕画面的内容进行操作的游戏，如主机游戏吃豆人(PacMan)、PC游戏星际争霸(StarCraft)。
2. 棋盘游戏:通过强化学习可以实现各种棋盘运动的AI。棋盘AI有着明确的目标——提高胜率，但是每一步往往没有绝对正确的答案,这正是强化学习所针对的场景。AlphaGo就是强化学习和深度学习结合的产物。

智能体/环境接口

强化学习问题常用智能体/环境接口(Agent-Environment Interface) 来研究。智能体/环境接口将系统划分为智能体和环境两个部分。

• 智能体(Agent):是强化学习系统中的决策者和学习者,它可以做出决策和接受奖励信号。一个强化学习系统里可以有一个或多个智能体。
• 环境(Environment)是强化系统中除智能体以外的所有事物,它是智能体交互的对象。

智能体/环境接口的核心思想:分隔主观可以控制的部分和客观不能改变的部分。

在智能体/环境接口中,智能体和环境的交互主要有以下三个环节:

1. 智能体观测环境,可以获得环境的观测(observation),记为$O$;
2. 智能体根据观测做出决策,决定要对环境施加的动作(action),记为$A$;
3. 环境受智能体动作的影响,改变自己的状态(state),记为$S$,并给出奖励(reward),记为$R$。

在很多任务中,智能体和环境是在离散的时间步骤上交互的,这样的问题可以将时间指标离散化,建模为离散时间智能体/环境接口。具体而言,假设交互的时间为$t=0,1,2,3,…$。在时刻t,依次发生以下事情:

• 智能体观察环境得到观测$O_t$ ;
• 智能体根据观测决定做出动作$A_t$;
• 环境根据智能体的动作,给予智能体奖励$R_{t+1}$ 并进入下一步的状态$S_{t+1}$。

马尔可夫决策过程

Markov决策过程(Markov Decision Process,MDP)是强化学习最经典、最重要的数学模型.

Markov决策过程模型

离散时间Markov决策过程模型可以在离散时间的智能体/环境接口的基础上进一步引入具有Markov性的概率模型得到。

Markov性:当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态；换句话说，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的，那么此随机过程即具有马尔可夫性质。

在离散时间智能体/环境接口中,智能体和环境交互的时刻为$\{0,1,2,3,…\}$。在时刻$t$,依次发生以下事情:

• 智能体观察状态$S_t \in S$的环境,得到观测$O_t \in O$,其中$S$是状态空间(state space),表示状态取值的综合;$O$是观测空间(observationspace),表示观测取值的集合。
• 智能体根据观测决定做出动作$A_t \in A$,其中$A$是动作集合。
• 环境根据智能体的动作,给予智能体奖励$R_{t+1} \in R$,并进入下一步的状态$S_{t+1} \in S$。其中$R$是奖励空间(reward space),表示奖励取值的集合。

一个时间离散化的智能体/环境接口可以用这样的轨道表示:$S_0,O_0,A_0,R_1,S_1,O_1,A_1,R_2,S_2,O_2,A_2,R_3….$。对于回合制的任务,可能会有一个终止状态$S_T$,则可以表示为$S_0,O_0,A_0,R_1,S_1,O_1,A_1,R_2,S_2,O_2,A_2,R_3….,S_T$。

引入概率和Markov性,就可以得到Markov决策过程模型。

定义在时间$t$,从状态$S_t=s$和动作$A_t=a$跳转到下一状态$S_{t+1}=s’$和奖励$R_{t+1}=r$的概率为:

$$
Pr[S_{t+1}=s’,R_{t+1} =r|S_t =s,A_t =a]
$$

模型中的Markov性:认为奖励$R_{t+1}$和下一状态$S_{t+1}$仅仅依赖于当前的状态$S_t$和动作$A_t$,而不依赖于更早的状态和动作。

[注意]: 智能体/环境接口没有假设状态满足Markov性。Markov性是Markov决策过程的特点。

策略

策略:智能体在当前状态根据其观测决定其行为的依据。

在Markov决策过程中,定义策略(policy)为从状态到动作的转移概率。对于有限Markov决策过程,其策略$\pi: S*A \to [0,1]$可以定义为$\pi(a|s)=Pr[A_t=a | S_t=s],s∈S,a∈A$。

状态	动作	概率
hungry	eat	1-x
hungry	not eat	x
full	eat	1-y
full	not eat	y

奖励、回报与价值函数

强化学习的核心概念是奖励,强化学习的目标是最大化长期的奖励

对于回合制任务,假设某一回合在第T步达到终止状态,则从步骤$t(t<T)$以后的回报(return)$G_t$可以定义为未来奖励的和
$$
G_t =R_{t+1}+R_{t+2} +…+R_{T}
$$

对于连续性任务,由于任务没有终止时间,所以$G_t$会包括$t$时刻以后所有的奖励信息。但是,如果对未来的奖励信息简单求和,那么未来奖励信息的总和往往是无穷大。所以引入了折扣(discount)这一概念,进而定义回报

$$
G_t =R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + … = \Sigma_{\tau = 0}^{+ \infty} R_{t+ \tau + 1}
$$

• 其中折扣因子$\gamma \in [0,1]$
• 折扣因子决定了如何在最近的奖励和未来的奖励间进行折中
• 若指定$\gamma=0$,智能体会只考虑眼前利益,完全无视远期利益,就相当于贪心算法的效果
• 若指定$\gamma=1$,智能体会认为当前的1单位奖励和未来的1单位奖励是一样重要的。

基于回报的定义,可以进一步定义价值函数(value function)

• 状态价值函数(state value function):状态价值函数$v_\pi(s)$表示从状态$s$开始采用策略$\pi$的预期回报。如下式所示:
  $$
  v_\pi(s)=E_\pi[G_t | S_t=s]
  $$

• 动作价值函数(action value function):动作价值函数$q_\pi(s,a)$表示在状态$s$采取动作$a$后,采用策略$\pi$的预期回报。如下式所示:

$$
q_\pi(s,a)=E_\pi [G_t |S_t=s,A_t =a]
$$

Q学习(Q-Learning)

强化学习的任务:学习一个最优策略使得智能体能够最大化长期的奖励。

方法:

• 对环境建模,计算最优策略
• 依靠经验学习出给定策略的价值函数和最优策略

Q学习(Q-Learning):一种异策(off policy)时序差分更新的无模型的机器学习算法

• 无模型的机器学习算法:在没有环境的数学描述的情况下,只依靠经验(例如轨迹的样本)学习出给定策略的价值函数和最优策略。在现实生活中,为环境建立精确的数学模型往往非常困难。因此,无模型的强化学习是强化学习的主要形式。
• 异策:同策(on policy)学习是边决策边学习,学习者同时也是决策者。异策学习则是通过之前的历史(可以是自己的历史也可以是别人的历史)进行学习,学习者和决策者不需要相同。
• 时序差分更新:回合制更新是在回合结束后利用整个回合的信息进行更新学习;而时序差分更新不需要等回合结束,可以综合利用现有的信息和现有的估计进行更新学习(每做一个Action就可以进行更新)。

如何根据经验学习:

• 在不同的状态下尝试不同的动作,然后可以得到一个对应的奖励,记录下不同状态下不同动作的奖励,然后在下一次决策的时候根据之前的记录选择一个可以得到较高奖励的决策(贪心)。
• 但是贪心算法可能陷入局部最优解,不能完全采用贪心算法,于是引入随机算法,在某些情况下随机选取策略。

Q学习算法

单步时序差分更新将依据$q_{\pi}(s,a)=E_{\pi}[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1})|S_t=s,A_t=a]$

在当前状态$s$,采取动作$a$后,进入了状态$S_{t+1}$。更新其对应的动作价值函数$q_π(s,a)$,一部分为当前获得的奖励$R_{t+1}$,另一部分为预测的之后可以获得的奖励$ \gamma q_{\pi}(S_{t+1}, A_{t+1})$。

定义Q学习时序差分目标:$U_{t:t+1}^{(q)} = R_{t+1} + \gamma max_{a \in A(S_{t+1})}q((S_{t+1}, a))$

• 上标$(q)$表示是对动作价值定义的
• 下标$t:t+1$表示用$(S_{t+1} ,\cdot)$估计值中的最大值来估计$(S_t,A_t)$。如果$S_{t+1}$是终止状态,默认有$q(S_{t+1}, \cdot)=0$。

动作价值函数的增量更新:$q(S_t,A_t) = q(S_t, A_t) + \alpha [U_t - q(S_t, A_t)]$

• $\alpha$ 为学习率
• 增量$U_t - q(S_t, A_t)$试图不断减小$[G_t - q(S_t,A_t)]^2$,使得$q(S_t, A_t)$不断接近实际的回报值.

Q学习算法求解最优策略

1. (初始化)$q(s,a) \gets any \ value$,$s \in S, a \in A$。如果有终止状态,令$q(s_T,a) \gets 0$
2. (初始化状态-动作对)选择状态S。
3. 如果回合未结束(例如未达到最大步数、S不是终止状态),执行以下操作:
   1. 用动作价值估计$q(S,\cdot)$确定的策略决定动作A(如$\epsilon$贪心策略);
   2. (采样)执行动作$A$,观测得到奖励$R$和新状态$S’$;
   3. (用改进后的策略计算回报的估计值);
   4. (更新价值和策略)更新$q(S,A)$(如$q(S,A) \gets q(S,A) + \alpha [U - q(S,A)]$);
   5. $S \gets S’$。

$\epsilon$贪心策略:假设$\epsilon=0.1$，以10%的概率随机选择，90%的概率采用贪婪选择。

A Game Demo

在一个4\*4的地图中,智能体(红色块)需要找到最短的路径到达目标位置(黄色块),但是需要避开陷阱(黑色块)。

分析

• 智能体：红色块

• 环境:4\*4的网格地图

• 状态:智能体当前所处的位置

• 动作:上、下、左、右移动

• 奖励：

  • 如果智能体到达黄色块得到正奖励。
  • 如果智能体到达黑色块则得到负奖励。

  参数

  • 学习率($\alpha$)
  • $\epsilon$贪心策略的概率($\epsilon$)
  • 折扣因子($\gamma$)

  数据结构

  Q-Table

  存储不同状态下不同动作的动作价值函数值。

state	up	down	left	right
(0,0)	0.2	0.4	0.2	0.4
(0,1)	0.3	0.2	0.3	0.2
(0,2)	0.05	0.05	0.4	0.5
…	…	…	…	…
(3,3)	0.1	0.1	0.7	0.1

• 不同状态下根据Q表中的值和选择的策略选择相应的动作
• 转移到新的状态并得到奖励后，更新Q表中的值

code

# 学习策略
def update():
    for episode in range(100):
        # initial observation
        observation = env.reset()

        while True:
            # fresh env
            env.render()

            # RL choose action based on observation
            action = RL.choose_action(str(observation))

            # RL take action and get next observation and reward
            observation_, reward, done = env.step(action)

            # RL learn from this transition
            RL.learn(str(observation), action, reward, str(observation_))

            # swap observation
            observation = observation_

            # break while loop when end of this episode
            if done:
                break

    # end of game
    print('game over')
    env.destroy()

# 贪婪策略选择动作
def choose_action(self, observation):
    self.check_state_exist(observation)
    # action selection
    if np.random.uniform() < self.epsilon:
        # choose best action
        state_action = self.q_table.loc[observation, :]
        # some actions may have the same value, randomly choose on in these actions
        action = np.random.choice(state_action[state_action == np.max(state_action)].index)
    else:
        # choose random action
        action = np.random.choice(self.actions)
    return action

# 更新Q表
def learn(self, s, a, r, s_):
    self.check_state_exist(s_)
    q_predict = self.q_table.loc[s, a]
    if s_ != 'terminal':
        q_target = r + self.gamma * self.q_table.loc[s_, :].max()  # next state is not terminal
    else:
        q_target = r  # next state is terminal
    self.q_table.loc[s, a] += self.lr * (q_target - q_predict)  # update

result

参考资料

• [1] [Reinforcement Learning.Sutton]
• [2] [强化学习：原理与Python实现]
• [3] [莫烦Python]（https://morvanzhou.github.io/tutorials/machine-learning/reinforcement-learning/）