Jiayu Lou's Blog
Mathematics foundation of reinforcement learning - Part 1 强化学习笔记1
JiayuLou Lv 1
  2025-01-09   2025-01-22    3

Mathematics foundation of reinforcement learning - Part 1 强化学习笔记1

既然是笔记，就用大白话写一下自己学习的理解，而不是简单的将书中内容copy paste。讲义已给出python code，但为了让自己能更好理解，以及锻炼自己工程能力，使用java进行编程。

Since this is a note, I’ll write down my own understanding in plain language rather than simply copy and paste the book’s content. The handouts already provide Python code, but to deepen my understanding and strengthen my engineering skills, I’ll use Java for the implementation.

Big Thanks

感谢老师的讲解与分享，让小白也能上手学习RL

Thank you, teacher, for your explanation and sharing. Thanks to you, even beginners can get started with reinforcement learning.

Syllabus

image

  • Chapter 1: 介绍了基本概念，如状态(state)，动作(action)，奖励(reward)，回报(return)，策略(policy)。并引出了Markov Decision Process（MDP）概念

  • Chapter 2: 在MDP基础上，推导出Bellman Equation 贝尔曼等式

  • Chapter 3: 数学证明收敛性，以及利用不动点特性推出Optimal State Value

  • Chapter 4: 值迭代算法 (Value Iteration)，策略迭代算法 (Policy Iteration) ，及截断策略迭代算法 (Truncated Policy Iteration)

Basic Concepts

一口气学完前四章，没有想象中那么复杂困难，不要被那些繁琐的数学表达式唬住，慢慢解开就会发现，其实大部分都是common sense.

I finished the first four chapters in one go, and it wasn’t as complicated or difficult as I had imagined. Don’t be intimidated by those cumbersome mathematical expressions—once you break them down, you’ll find that most of them are actually common sense.

  • 状态 state (s)

  • 动作 action (a)

  • 奖励 Reward ( R(s,a) )，表示状态 s 下 执行动作 a 会获得的即时奖励。

    ⚠️ 注意这里的是即时奖励

  • 累积奖励 G，表示从初始状态到当前状态 s，所获的所有即时奖励的和，为累积奖励

  • 转移概率 Probablity ( P(s’ | s, a) ) ，表示状态 s 执行动作 a 后，转移到状态 s’ 的概率

  • 折扣因子 (γ) : 范围为 [0,1]，这个用在计算即时回报时前面的系数

  • 策略 Policy (π) : 指每个状态下的动作集合，最终目的，就是求最优的π，使得 累积奖励最大化。

    ⚠️ 注意这里指的是累积奖励，如果是即时奖励，那就是贪心算法，并不能保证累积奖励最大化。

  • 轨迹 Trajectory：指从某一状态开始，执行一系列操作，获得一系列即时奖励的集合，可以是无穷也可以是有限的

  • 回合 Episode ：与轨迹定义类似，但回合只能是有限的

Markov Decision Process

这个用大白话说，求最优解的过程叫MDP。

如果用数学表达式来描述的话 就是求下面表达式的最大值。
$$
G_t=R_t+γR_{t+1}+γ^2R_{t+2}+⋯=∑{k=0}^∞γ^kR{t+k}
$$

状态价值函数 State Value Function：描述从状态s开始，然后遵循策略π时的期望累积奖励

就是按照策略 π , 从状态s开始执行操作，然后将每一步获得的即时奖励累加。

数学表达式：

操作价值函数 Action Value Function：

指从状态s开始，执行动作a，然后遵循策略π时的期望累积奖励，

Bellman Equation

贝尔曼表达式 Bellman Equation

状态值最优函数

简单理解，就是求 状态 s 下的最优策略，从而获取最大的累积期望值

$$
Vπ^(s)=\mathop{\max}{a}∑{s’}P(s′∣s,a)[R(s,a)+γV_π^(s′)]
$$
解释：

  • 根据策略选择动作a

  • 根据转移概率 P(s’ | s,a) 计算可能转移到的状态s’ → 状态 s 在执行操作 a 后 到状态 s’ 的概率

  • 累加及时奖励 R(s,a) 和 折扣后的未来值Vπ(s’) → 状态 s 下，执行操作 a 后得到的即时奖励

状态-动作值函数的贝尔曼方程：

那么怎么求呢，有两种求解方法

值迭代 Value Iteration

通过反复更新值函数直到收敛，直接求解

简单来说，就是

  1. 初始化所有状态值为0
  2. 开始迭代，对每个状态 s 遍历当前状态 s 下 所有操作 a
  3. 求 可以获得 即时奖励 最大 的操作 a 记录为当前状态的状态值
  4. 进行下一轮迭代，直到收敛，即变化值小于阈值（如 1e-6）

用一个例子来举例，在一个grid[][] 地图中，有边界，有障碍格以及空格。有个智能体，目标从起点(0,0)走到起点(n,n)。智能体不能超出边界，会有惩罚值，且会退回先前格，可以进入障碍格，但也会有惩罚值。求到终点的最优路径。

JAVA 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void valueIteration() throws InterruptedException {
        double delta;
        do {
            delta = 0;
            for (int i = 0; i < size; i++)
                for (int j = 0; j < size; j++) {
                    double oldValue = stateValue[i][j];
                    // getBestAction(i，j) 获取当前状态能获得的最大即时奖励及对应policy
                    BestActionPair bestActionPair = getBestAction(i,j);
                    // 更新状态值 及 策略
                    stateValue[i][j] = bestActionPair.getActionValue();
                    policy[i][j] = bestActionPair.getPolicy();
                    // 计算是否收敛
                    delta = Math.max(delta, Math.abs(stateValue[i][j] - oldValue));
                }
            clearConsole();
            print(delta);
            Thread.sleep(100);
        } while (delta > THRESHOLD);
    }

策略迭代 Policy Iteration

策略迭代分为两步

  • 策略评估
    • 计算当前策略下，各个状态根据当前策略能获得的奖励的期望值
  • 策略改进
    • 顾名思义，对各个状态遍历，看是否有能获得更大即时奖励期望值的动作
    • 有的话，更新当前策略
  • 策略迭代
    • 如果有策略更新，则进行迭代，即重新计算当前策略下各个章台的奖励期望值
    • 没有策略更新，则说明已经达到最优
JAVA 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public void policyIteration() throws InterruptedException {
        boolean policyStable;
  			// 开始迭代
        do {
           // 评估策略，获取当前策略下，每个状态能获得的奖励期望值
            policyEvaluation();
            // 改进策略
            policyStable = true;
            for (int i = 0; i < size; i++)
                for (int j = 0; j < size; j++) {
                    int oldAction = policy[i][j];
                  	// 获取 最优策略
                    policy[i][j] = getBestAction(i,j).getPolicy();
                    if (oldAction != policy[i][j]) policyStable = false;
                }
        } while (!policyStable);

    }

private void policyEvaluation() throws InterruptedException {
        double delta ;
        do {
            delta = 0;
           // 计算 当前策略下，各个状态的收敛值
            for (int i = 0; i < size; i++)
                for (int j = 0; j < size; j++) {
                    double oldValue = stateValue[i][j];
                    stateValue[i][j] = getExpectedValue(i,j,policy[i][j]);
                    delta = Math.max(delta, Math.abs(stateValue[i][j] - oldValue));
                }
        } while (delta > THRESHOLD);
        clearConsole();
        print(delta);
        Thread.sleep(100);
    }
 Comments
Comment plugin failed to load
Loading comment plugin
  1. Mathematics foundation of reinforcement learning - Part 1 强化学习笔记1
    1. Big Thanks
    2. Syllabus
    3. Basic Concepts
      1. Markov Decision Process
    4. Bellman Equation
      1. 值迭代 Value Iteration
      2. 策略迭代 Policy Iteration
  1. Mathematics foundation of reinforcement learning - Part 1 强化学习笔记1
    1. Big Thanks
    2. Syllabus
    3. Basic Concepts
      1. Markov Decision Process
    4. Bellman Equation
      1. 值迭代 Value Iteration
      2. 策略迭代 Policy Iteration