Mathematics foundation of reinforcement learning - Part 2 强化学习笔记2
Mathematics foundation of reinforcement learning - Part 2 强化学习笔记2
Syllabus
![image]()
Preparation
还是那句话，不要慌，听上去很唬人，看上去很复杂的公式，其实都是common sense。
Model Based & Model Free
什么是model based，就是对每个状态可以使用函数f(x)计算其状态价值的就是model based。
那么Model Free，就是没有或者不能用函数计算的那就是model free。
Mean Estimation （期望值计算）
对于 model based，如何计算期望呢？显然，可以通过 状态操作值 ✖ 概率 累加求得
那么对于 model free呢，由于没有了函数f(x)，所以没有办法直接获取状态操作值。
我们只能通过大量的样本sample {x1, x2, x3, …} 取平均求得期望值
当n趋向于无穷大时，取等号。这个由 大数定理(the law of large numbers) 保证。
Monte Carlo
有了以上了解，那就可以来看蒙特卡洛算法了。是不是很common sense，没啥复杂的数学要求。
回顾 policy iteratioin 策略迭代算法，为什么不是 值迭代，因为蒙特卡洛算法主要用于model free的场景，而值迭代算法是通过更新 所有状态 所有操作来逼近最优价值，对于model free场景，这个很难获取到，例如在俄罗斯方块游戏中，虽然可以建模但是需要的空间巨大，且难以实现。
关键点在于，蒙特卡洛算法不需要知道状态转移概率，只需要知道与环境实际交互的数据即可，这个更适用于一般场景。
策略迭代第一步，策略评估，根据当前策略，计算出能获得的奖励期望值
那么，当没有模型时，这个p(r|s,a), p(s’|s,a)是不知道的，所以回到定义
对于这个期望值，我们可以使用取平均值的方法计算，怎么理解呢，即对(s,a) 状态 s，执行操作 a 后，开始模拟，获取尽可能多的路径，求每天路径的值，再去平均值，最终得到这个策略评估函数值。
第二步，策略优化，这个还是和上一步一致，在当前策略模拟基础上，使用greedy 贪心获得能获取最大收益的操作值，进行策略更新，然后进行下一步迭代。所以，这个也叫蒙特卡洛贪心算法。
Monto Calro e-greedy Policies
有了基本概念，那下一步就是要将这个算法工程化了，算法简单来说分几步
随机策略（在我们这个迷宫例子中，则表现为随机一条长度为maxStep的路径）
这里为了能更好的收敛结果，使用随机因子epsilon
可以理解为当 ϵ = 1 时，为最公平算法，当ϵ = 0 时，为最贪心算法
代码实现中，初始化 ϵ=1，然后使用随机值 Math.random() < ϵ ，则操作为选取BestPolicy(s) ，反之取随机值。
为了让算法高效，可以逐渐收敛ϵ，例如每一次迭代完成，ϵ = 0.99 * ϵ。最终 ϵ -> 0。
评估策略
- 根据第一步的策略，可以不断获取每一步的 即时奖励 值。
- 利用 公式(5) ，我们需要 从后往前 计算，G(s,a) 的 累积奖励 值
- 然后 更新 G(s,a) 的期望值。
更新策略
- 通过不断迭代，会获得不同状态 s 下，各个动作 a 的累积奖励期望值
- 能获得最大累积奖励的操作 a 的值设定为 bestPolicy。当然，这个是临时的bestPolicy
判断是否终止，没有则继续迭代
Monto Carlo 实际应用
还是之前那个网格世界grid world例子，需要找到地图上每个点的最佳策略。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| public void mcGreedy() throws InterruptedException {
int round = 0;
do {
List<Step> episodeSteps = generateRandomRoute();
evaluatePath(episodeSteps);
updatePolicy();
epsilon *= 0.999;
round++;
} while (epsilon > THRESHOLD);
print(round);
}
private List<Step> generateRandomRoute() {
int x = (int) (Math.random() * size), y = (int) (Math.random() * size), step = 0;
List<Step> steps = new ArrayList<>();
while (step < maxStep) {
if (x == size-1 && y == size-1) break;
int action;
double random = Math.random();
if (random < epsilon) action = (int) (Math.random() * 5); else action = policy[x][y];
double reward = 0;
int nextX = x, nextY = y;
switch (action) {
case 0 -> {
if (x == 0) reward = punishment; else {
reward = grid[x][y];
nextX = x-1;
}
}
case 1 -> {
if (x == size-1) reward = punishment; else {
reward = grid[x][y];
nextX = x+1;
}
}
case 2 -> {
if (y == 0) reward = punishment; else {
reward = grid[x][y];
nextY = y - 1;
}
}
case 3 -> {
if (y == size-1) reward = punishment; else {
reward = grid[x][y];
nextY = y + 1;
}
}
default -> reward = grid[x][y];
};
steps.add(new Step(x,y,action, reward, nextX, nextY));
x = nextX;
y = nextY;
step++;
}
return steps;
}
private void evaluatePath(List<Step> steps) {
double G = 0.0;
for (int i=steps.size() -1 ; i>=0; i--) {
Step step = steps.get(i);
G = step.reward + discount * G;
int x = step.x, y = step.y, action = step.action;
actionValue[x][y][action] = (actionValue[x][y][action] * count[x][y][action] + G) / (count[x][y][action]+1);
count[x][y][action]++;
}
}
private int updatePolicy() {
int count = 0;
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++) {
double max = actionValue[i][j][policy[i][j]];
for (int k = 0; k < 5; k++) if (actionValue[i][j][k] > max) {
max = actionValue[i][j][k];
policy[i][j] = k;
count++;
}
}
return count;
}
|
测试样例
1
2
3
4
5
6
7
| {0, 0, 0, 0, 0},
{0, -1, -1, 0, 0},
{0, 0, -1, 0, 0},
{0, -1, 1, -1, 0},
{0, -1, 0, 0, 0}
punishment = -1;
discount = 0.9
|
输出:
取 maxStep = 10000; THRESHOLD = 1e-9;
1
2
3
4
5
6
| Round: 20713
right right right down down
down left right right down
right down down right down
up right stay left down
up right up right stay
|
