强化学习-数学基础

总述

1

  • 基础工具

    1. 基本概念：state, action, reward, return, episode, policy, mdp…
    2. 贝尔曼公式：用于评价策略
    3. 贝尔曼最优公式：强化学习的最终目标是求解最优策略

  • 算法/方法

    1. 值迭代、策略迭代—— truncated policy iteration：值和策略update不断迭代
    2. Monte Carlo Learning：无模型学习
    3. 随即近似理论：from non-incremental to incremental
    4. 时序差分方法(TD)
    5. 值函数估计：tabular representation to function representation，引入神经网络
    6. Policy Gradient Methods：from value-based to policy-based
    7. Actor-Critic Methods：policy-based + value-based

 

1 基本概念

1. 专有名词

  1. grid-world：小机器人在网格里走路

  2. state：agent在环境中的状态，用s1、s2…表示；s是列向量，可表示速度、加速度等

  3. state space：即把所有的state放在一起的集合

  4. action：可采取的行动，如往上走、往右走…

  5. action-space：所有的action放在一起的集合，用A表示

  6. state transition：采取一个action后，从一个state转到另一个state的过程；定义了agent与环境的一种交互行为

  7. forbidden area：进去后受到惩罚/不可进入

  8. tabular representation：使用表格描述state transition

  9. state transition probability：使用条件概率来表述tate transition，用于描述随机性

  10. policy：使用箭头表示，告诉agent在某state时应该采取哪个action。基于policy，可以得到path

  11. mathematical representation：条件概率，用π表示某状态对应的策略

  12. stochastic policies：某状态对应多个不同概率的action

  13. reward：一个数(标量)；正奖励负惩罚

    2

    可视为 human-machine interface，即人类与机器交互的一种手段，引导机器该怎么做。

    同时也可以用 tabular representation 来表示reward，但只能表示唯一的reward；

    还可以使用 mathematical representation，用条件概率来表示。

  14. trajectory：一个 state-action-reward 链

  15. return：沿着 trajectory 所得到的 reward 总和，用于评估策略

  16. discounted rate、discounted return：

    3

    gamma 较小，比较近视，更加注重最近的一些 reward；反之 gamma 较大，比较远视。

  17. terminal states：终止状态

  18. episode/trail：通常被定义为一个会终止的 trajectory，这些任务被称为 episodic tasks

  19. continuing task：有些任务是不会结束，永远持续的/或时间比较长

    • 统一方法：把 episodic tasks 转为continuing task
      1. 把 target state 视为 absorbing state，不论采取什么 action 都会再回到这个状态，并且 reward 为0；
      2. 将 target state 视为一个普通的状态，可离开可留下。

 

2. 马尔可夫决策过程 (MDP markov decision process)

  • MDP 的关键组成：

    4

  • 用圆和边来表示 markov process：

    5

当 policy 确定后，markov process 就成了 markov decision process

 

 

2 贝尔曼公式

核心概念 state value、基础工具 bellman equation

1. 计算return

  1. 方法一：用定义

    6

  2. 方法二：Bootstrapping!

    7

    从某状态出发的return，依赖于从其他状态出发的 return

    简易贝尔曼公式：8

 

2. state value

  • 对于单步过程：

    9

state value 就是 Gt(discounted return) 的期望值

 

3. 贝尔曼公式

描述了不同状态的 state value 之间的关系，可用于计算 state value

  1. 推导

    10

    [!IMPORTANT]

    1. 如上所示，即为 Bellman equation，表示了不同状态的 state-value functions（左边是s的，右边是s’的）
    2. 有两项组成：当前 reward 和未来的 reward
    3. 该式子对所有的状态都成立！！！（若有 n 个状态，则会有 n 个这样的式子）
    4. 通过这 n 个式子，联立可求出 state value —— Bootstrapping!
    5. π 是给定的 policy，解决这个问题的过程就是 policy evaluation
    6. p 代表 dynamic model，可能已知或未知

    • 以下图 s1 为例：

      11

      联立所有的式子，并代入具体的gamma，即可求出所有的 state value；state value 越高，代表策略越好

  2. Matrix-vector form

    将所有状态的贝尔曼公式放在一起，并写成矩阵形式：

    12

    • 例如：

      13

  3. 求解 state value

    1. 为什么要求解 state value？

      给定 policy，求解 state value 的过程叫 policy evaluation，即评估策略好不好，它是 RL 的基础问题。

    2. 解析方法

      1. closed-form solution

        14

        逆难求，实际很少用

      2. iterative solution

        15

        16

 

4. action value

17

  • 区别：

    • state value：从一个状态出发，可以得到的平均 return
    • action value：从一个状态出发，并且选择了一个 action 后得到的平均 return

    18

    求 action value 的平均，可得 state value ；同理已知 state value 可求 action value

  • 例子：

    19

    虽然往右走，但所有的 action 都是可以计算的，非零！未来可变，详见后面的课程。

最后选择 action value 最大的那个 policy。

 

5. 小结

20

 

 

 

3 最优策略 与 贝尔曼最优公式

贝尔曼最优公式是贝尔曼公式的一种特殊情况 —— 强化学习的目的就是寻找最优策略

  • 重点关注：

    • 核心概念：optimal state value 和 optimal policy
    • 基础工具：the Bellman optimality equation (BOE)

  • 例子

    1. 求解 state value

      21

    2. 求解 action value

      22

      注：1、2、3、4、5 分别代表上右下左原地

    3. 如何改进策略？—— 使用 action value

      23

      观察到 a3 时，action value最大；若选择 a3 作为策略：

      24

    直观上来说，选择最大的 action value 可以得到最优的策略。

 

1. 最优策略(optimal policy) 定义

定义：某策略相比于其他的策略，能得到最大的 state value

  • 贝尔曼公式回答了如下问题：
    • 是否存在？
    • 是否唯一？
    • 确定性or非确定性？
    • 如何得到？

 

2. 贝尔曼最优公式(BOE)

25

  • 可向量化：

    26

  1. 如何理解左边 maxπ

    27

    化成了 v = f(v):

    28

  2. 压缩映射定理（Contraction Mapping Theotrm）

    • 不动点(fixed point)：集合上的一个点x，在函数f上满足f(x)=x，则该点称为不动点 —— 通过f又映射到了自己。

    • Contraction Mapping：若f满足不等式

      29

    • Contraction Mapping Theotrm:

      30

  3. 利用 Contraction Mapping Theotrm 求解 BOE

    v=f(v)满足 Contraction Property，可以使用定理解出。

    贝尔曼最优公式的解，必是最优的 state value，相对应的policy也是最优的。

    31

 

3. 分析最优策略

  1. 什么因素决定了它的最优策略：下式中红色元素

    32

    • gamma 大，更加远视
    • gamma 小，更加近视
    • gamma 为0，选择 immediate reward

  2. 将 r 改变为 ar+b 后，v的变化：

    33

  3. 除了 r，gamma 也可以约束智能体不要绕远路

    34

    绕远路意味着到达目标的奖励晚，对应的 gamma 次方大，打折厉害。

 

4. 总结

35

36