Mathematics foundation of reinforcement learning - Part 4 强化学习笔记4
Chapter 7 Temporal-Difference Methods
先做一个简单回顾：
第一部分，讲了利用bellman等式，在model based的情况下，通过
- 值迭代 value iteration
- 对每个状态s，遍历当前状态s下的所有操作a，取最优解为当前状态值，并进行下一轮迭代。
- 策略迭代的方式 policy iteration
- 策略评估，随机给定一个策略，计算各个状态下根据给定策略可以获得累积奖励的期望值
- 策略改进，对每个策略，遍历当前策略所有操作，取最优解更新原有策略
第二部分，介绍了蒙特卡洛贪心算法，对于策略迭代算法中的策略评估步骤，在没有模型的情况下(model free)，需要通过生成大量随机轨迹（episodes）数据来计算各个状态下各操作所能获得的即时奖励值，取其平均值变为该状态-动作值的期望值，可以看到蒙特卡洛算法的计算需要大量episode路径下的数据进行计算。
这一部分，对蒙特卡洛算法再进行优化，是否可以做到数据增量式incremental的算法。
以下介绍的，都是在model free的情况下，通过迭代及样本来获得随机变量的期望值
下图是对这章节算法的一个总结性描述，
![image.png]()
Temporal Difference Algorithm
使用TD算法来计算在策略π下，各个状态s的状态值vπ(s)state value，t表示时间
这个其实在上一章基础上不难理解，也是利用样本不断逼近最终值的一个思想， 的状态值等于这个状态下所能达到的所有下一个状态值的期望值
TD 算法推导
价值函数的目标定义：
对于给定状态 s，其值函数定义为 其中 是从时间步 t 开始的回报折扣累计和：
贝尔曼方程：
根据贝尔曼期望方程，状态值函数可以被递归地表示为
Robbins-Monro算法：
这里从数学上可以转化为求 的解
$$
\begin{align*}
\bar{g}(v_\pi(s_t))
&= v_\pi(s_t) - \Bigl[r_{t+1} + \gamma,v_\pi(s_{t+1})\Bigr] \
&=\underbrace{v_\pi(s) ;-; \mathbb{E}\pi\Bigl[R{t+1} + \gamma,v_\pi(S_{t+1}) ;\bigm|; S_t = s\Bigr]}{g(v\pi(s_t))} \
&\quad + \biggl(
\mathbb{E}\pi\Bigl[R{t+1} + \gamma,v_\pi(S_{t+1}) ;\bigm|; S_t = s\Bigr]
;-; \Bigl[r_{t+1} + \gamma,v_\pi(s_{t+1})\Bigr]
\biggr) \
&= g(v_\pi(s_t)) + \eta
\end{align*}
$$
这时候，根据RM算法，学习率a满足 且 的情况下，通过迭代会收敛得该状态的状态值函数。
$$
\begin{align}
v_{t+1}(s_t) &= v_t(s_t) - \alpha_t(s_t)\bar{g}(v_t(s_t)) \
&= v_t(s_t) - \alpha_t(s_t)(v_t(s_t)-[r_{t+1}+\gamma{v}\pi(s{t+1})])
\end{align}
$$
特别的
- 新估计值
- 原估计值
- $v_t(s_t)-[r_{t+1}+\gamma{v}\pi(s{t+1})]$ TD error，误差值/噪音
- $[r_{t+1}+\gamma{v}\pi(s{t+1})]$ TD target，目标值
Sarsa: state-action-reward-state-action
sarsa算法主要是用作求动作价值函数，注意这里 a 满足 且
这个的推导过程与TD也类似，同样可以把这个转化为求方程的解，然后使用RM算法进行迭代逼近。
由贝尔曼方程可以得到，
$$
q_\pi(s, a) = \mathbb{E}[r_{t+1}+\gamma{q}\pi(s{t+1}, a_{t+1}) | s_{t+1} \in s, a_{t+1} \in a] \
g(v_\pi{(s,a)}) = q_\pi(s, a) - \mathbb{E}[r_{t+1}+\gamma{q}\pi(s{t+1}, a_{t+1}) | s_{t+1} \in s, a_{t+1} \in a] = 0
$$
利用RM算法，求 的解，即可得sarsa算法。
Sarsa的实际使用
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
| public void sarsa() throws InterruptedException {
int round = 0;
while (round < maxRound) {
List<Step> episode = generateEpisode();
double alpha = 1.0 / (1+round);
for (int i = 0; i<episode.size()-1; i++) {
Step step = episode.get(i);
actionValue[step.x][step.y][step.action] -= alpha * ( actionValue[step.x][step.y][step.action] - (step.reward + discount * actionValue[step.nx][step.ny][episode.get(i+1).action]) );
}
for (int i = 0; i<size; i++)
for (int j = 0; j<size; j++) {
double max = actionValue[i][j][0];
for (int k = 1; k < 4; k++) if (actionValue[i][j][k] > max) {
max = actionValue[i][j][k];
policy[i][j] = k;
}
}
epsilon *= 0.999;
round++;
}
print(round);
}
|
N-Step Sarsa
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
| public void nStepSarsa() throws InterruptedException {
int count = 0;
while (count < maxRound) {
List<Step> episode = generateEpisode();
double alpha = 0.1;
for (int i = 0; i<episode.size()-1; i++) {
Step step = episode.get(i);
double G = 0.0;
double gammaPow = 1.0;
int lastIndex = Math.min(i + n, episode.size() - 1);
for (int j = i + 1; j <= lastIndex; j++) {
G += gammaPow * episode.get(j).reward;
gammaPow *= discount;
}
if (i + n < episode.size()) {
Step step_n = episode.get(i + n);
G += gammaPow * actionValue[step_n.x][step_n.y][step_n.action];
}
double oldQ = actionValue[step.x][step.y][step.action];
actionValue[step.x][step.y][step.action] += alpha * (G - oldQ);
}
for (int i = 0; i<size; i++)
for (int j = 0; j<size; j++) {
double max = actionValue[i][j][0];
for (int k = 1; k < 4; k++) if (actionValue[i][j][k] > max) {
max = actionValue[i][j][k];
policy[i][j] = k;
}
}
epsilon *= 0.999;
count++;
}
print(count);
}
|
Q-Learning
q-learning算法其实是基于bellman最优等式，即利用SGD对Bellman Optimism Equation求解的这么一个算法。
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 qLearning() {
int count = 0;
while (count < maxRound) {
List<Step> episode = generateEpisode();
double alpha = 0.1;
for (int i = 0; i<episode.size(); i++) {
Step step = episode.get(i);
double max = actionValue[step.nx][step.ny][0];
for (int k = 1; k < 4; k++) if (actionValue[step.nx][step.ny][k] > max) {
max = actionValue[step.nx][step.ny][k];
}
actionValue[step.x][step.y][step.action] -= alpha * ( actionValue[step.x][step.y][step.action] - (step.reward + discount * max) );
}
for (int i = 0; i<size; i++)
for (int j = 0; j<size; j++) {
double max = actionValue[i][j][0];
for (int k = 1; k < 4; k++) if (actionValue[i][j][k] > max) {
max = actionValue[i][j][k];
policy[i][j] = k;
}
}
epsilon *= 0.999;
count++;
}
print(count);
}
|
