# 强化学习实战[updating]

## 编程语言

Why Julia?事实上，我更乐意使用Clojure，然而其基础工具库实在太匮乏，不得不放弃。Why not Python?我只是单纯觉得Julia写出来的代码更好看！不过阅读本文并不需要读者熟练掌握Julia，只需要有基本的编程思想即可，我会尽量将Julia这门语言独有的内容降到最低（必要的时候会给出解释和参考文献）。

# 1. Tabular Methods

“昨夜西风凋碧树，独上高楼，望尽天涯路。”

## 1.1 Day 1: Where’s Eve?

• $$\mathcal{A}$$：Actions, 动作空间,在这里包含两种可能{:left, :right}
• $$a_t$$: 在$$t$$时刻采取的行动
• $$\mathcal{S}$$: States, 状态空间，这里就是Eve所有可能的位置{-3, -2, -1, 0, 1, 2, 3, 4, 5}
• $$s_t$$: 在$$t$$时刻所处的状态
• $$\mathcal{R}$$:所有可能的奖励，这里由三个离散值{0, 3, 5}构成
• $$R_t$$：每一天获得的奖励，特别地，我们将游戏结束时的时间记为$$T$$，任务结束时获得的奖励为$$R_T$$

1. $$\bar{R_T} = \frac{\sum_{i=1}^{N} R_T^i}{N}$$，N次试验的平均收益(3.746)
2. $$\bar{T} = \frac{\sum_{i=1}^{N} T^i}{N}$$，N次试验平均行动的次数(16.164)

## 1.2 Day 2: The Value of State

$$$G_t = R_t + R_{t+1} + R_{t+2} ...$$$

$$$G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + ...$$$

$$$V_t(s) = \mathbb{E}(G_t | s) = \mathbb{E}(R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + ... | s) \label{value_equation}$$$ 从上帝视角来看，在环境不发生变化的情况下，显然每个状态s都有一个对应的固定的$$V(s)$$，这样，每次Eve决定怎么走的时候，只需要看下这张表，从可以到达的所有状态中，找到价值最高的状态$$s'$$，跳转过去即可。现在问题变成了如何计算$$V(s)$$。我们不妨先模拟下，将Eve放在不同的位置，然后分别执行原来的随机策略，计算平均收益$$\hat{G_t}$$，来估计$$V(s)$$

$$$P(s'|s) = \sum_{a \in A} P(s' | s, a)$$$

$$$\begin{bmatrix} 1.0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0.5 &0 & 0.5 &0 &0 &0 &0 &0 &0 \\ 0 &0.5 &0 & 0.5 &0 &0 &0 &0 &0 \\ 0 &0 &0.5 &0 & 0.5 &0 &0 &0 &0 \\ 0 &0 &0 &0.5 &0 & 0.5 &0 &0 &0 \\ 0 &0 &0 &0 &0.5 &0 & 0.5 &0 &0 \\ 0 &0 &0 &0 &0 &0.5 &0 & 0.5 &0 \\ 0 &0 &0 &0 &0 &0 &0.5 &0 & 0.5 \\ 0 &0 &0 &0 &0 &0 &0 &0 & 1.0 \\ \end{bmatrix}$$$

$$$V_t(s) = R_t(s) + \gamma \sum_{s' \in S} P(s' | s) V_{t+1}(s')$$$

$$$\begin{bmatrix} V^*(s_1) \\ \dots \\ V^*(s_N) \end{bmatrix} = \begin{bmatrix} R(s_1) \\ \dots \\ R(s_N) \end{bmatrix} + \gamma \begin{bmatrix} P(s_1|s_1) & \dots &P(s_N|s_1)\\ \vdots &\ddots &\vdots \\ P(s_1|s_N) &\dots &P(s_N|s_N) \end{bmatrix} \begin{bmatrix} V^*(s_1) \\ \dots \\ V^*(s_N) \end{bmatrix}$$$

$$$\begin{split} \boldsymbol{V} &= \boldsymbol{R} + \gamma \boldsymbol{P V}\\ \boldsymbol{V} &= (\boldsymbol{I} - \gamma \boldsymbol{P})^{-1} \boldsymbol{R} \end{split}$$$

P = diagm(repmat([0.5], 8), 1) + diagm(repmat([0.5], 8), -1)
P[1,1], P[1,2], P[end, end-1], P[end, end] = 1, 0, 0, 1
V(γ) = (diagm(ones(9)) -  γ*P)^-1 * R
show(V(0.9))
# [30.0, 19.9416, 14.3146, 11.8686, 12.0601, 14.9316, 21.1213, 32.0046, 50.0]
show(V(0.95))
# [60.0, 48.1992, 41.4721, 39.1104, 40.8656, 46.9225, 57.9186, 75.0113, 100.0]
show(V(0.99))
# [300.0, 301.464, 309.018, 322.814, 343.132, 370.383, 405.115, 448.032, 500.0]

### Value Iteration

$$$V^*(s) = \underset{a \in A}{max} \left( R(s, a) + \gamma \sum_{s' \in S}P(s' | s,a) V^*(s') \right)$$$

$$$\pi(s) \leftarrow \underset {a \in A} {arg \ max} \left( R(s, a) + \gamma \sum_{s' \in S}P(s' | s,a) V^*(s') \right)$$$

### Policy Iteration

Policy Iteration的思想是，先将所有状态对应的$$V$$置为0（也可以根据先验设置相应的值），针对每个状态，先随机初始化一个action(或根据前面设置的先验调整),记为$$\pi_0$$，在给定Policy之后，我们可以算出下一步所有状态对应的$$V(s')$$，即(Policy Evaluation)：

$$$V^{\pi}_t (s) = R(s, \pi(s)) + \gamma \sum_{s' \in S} P(s'|s, \pi(s)) V^{\pi}_{t+1}(s')$$$

$$$\pi_{k+1}(s) = \underset {a \in A} {arg \ max} \left( R(s,a) + \gamma \sum_{s' \in S} P(s' | s, a) V^{\pi_k}(s') \right)$$$

## 1.3 Day 3: Monte Carlo Methods in Depth

First Visit Monte Carlo Method 方法的思想就是，Agent在做出一次尝试之后，得到状态的序列$$s_0, s_1, ... s_T$$（将其想象成搜索空间中的一条路径），以及最终的$$r$$，然后，将该reward分配给路径上的第一次遇到的状态，重复多次之后，计算每个状态上r的平均值作为该状态的价值估计（显然，也不一定限制在first visit的state，只是这样处理更自然些）。假设我们对state之间的转换关系很清楚（即已知model），那么剩下的任务就是每次往前看一步，找到最优的state，跳转过去即可。对于model未知的情况，则需要考虑(state, action) pair，然后根据前面first visit的方法更新对应pair的价值，最后，在每个状态下找到使得pair的value最大的action即可。

1. exploring starts （引入 $$\epsilon$$-soft解决该问题）
2. infinite number of episodes （根据GPI中的思想，一步步优化）

TODO: 这个需要讲个专题

## 1.4 Day 4: Temporal-Difference Learning

$$$V(S_t) \leftarrow V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1} - V(S_t)))$$$

### SARSA

$$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t))$$$

$$$\begin{split} Q(S_t, A_t) & \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma \mathbb{E} (Q(S_{t+1}, A_{t+1} | S_{t+1}) - Q(S_t, A_t)) \\ & \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma \sum_{a} \pi(a|S_{t+1}) Q(S_{t+1}, a) - Q(S_t, A_t)) \end{split}$$$

Q-Learning

$$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma \ \underset {a } {max} \ Q(S_{t+1}, a) - Q(S_t, A_t))$$$

In some stochastic environments the well-known reinforcement learning algorithm Q-learning performs very poorly. This poor performance is caused by large overestimations of action values. These overestimations result from a positive bias that is introduced because Q-learning uses the maximum action value as an approximation for the maximum expected action value. We introduce an alternative way to approximate the maximum expected value for any set of random variables. The obtained double estimator method is shown to sometimes underestimate rather than overestimate the maximum expected value.

# 2. Approximate Methods

“衣带渐宽终不悔，为伊消得人憔悴。”

# 3. Deep Reinforcement Learning

“众里寻他千百度，蓦然回首，那人却在灯火阑珊处。”