Reinforcement Learning notes(1)
Reference
Stanford CS229 notes 12: http://cs229.stanford.edu/notes/cs229-notes12.pdf
Summary
在CS229 notes 中提到了强化学习的意义：
In the reinforcement learning framework, we will instead provide our algorithms only a reward function, which indicates to the learning agent when it is doing well, and when it is doing poorly.
个人的理解就是强化学习就是让 agent 根据环境包含的信息与强化信号量判断策略的选择，同时策略的不同造成的结果会以反馈的形式产生强化信号量给 agent，最终 agent 以“得到最大化的正强化信号量”为标准，做出最佳的策略选择。
换句话说，强化学习不会给模型提供任何“正确的决策”规则，只会给 agent 从环境状态得来的强化信号量，通过这种方式，agent 在行动=>评价=>学习的过程中学习到了知识，学到了如何做出让评价最好的决策方式。
Markov decision processes (MDP)
马尔科夫决策过程为一个包含5个元素的元组
\[ MDP = (S,A,{P_{sa}},\gamma,R)\]
其中：
S 为 states，状态集，包含所有 agent 可能处于的状态。
A 为 actions，行动集，包含了所有 agent 在各种状态下可以采取的行动。
\(P_{sa}\) 为概率，代表了 agent 在 s 状态下做出 a 行动的概率
\(\gamma\) 的值 \(\gamma in [0,1)\)，称为“discount factor”，可以理解为“折算率”
R 为奖励函数（reward function），其值由\(S\times A \mapsto R\)或\(S \mapsto R\)决定。
马尔科夫决策过程即为 agent 从初状态\(s_0\)开始行动，在马尔科夫决策的 A（行动集）中选择一种行动方式 \(a_0 \in A\)，到达第二个状态\(s_1\)，接着选择\(a_1\)……
\[s_0 \overset{a_0}{\rightarrow} s_1\overset{a_1}{\rightarrow} s_2\overset{a_2}{\rightarrow} s_3\overset{a_3}{\rightarrow} ...\]
这个过程的价值（payoff）记作
\[R(s_0,a_0) + \gamma R(s_1,a_1)+\gamma^2 R(s_2,a_2) + ...\]
简写为
\[r_0 + \gamma r_1 + \gamma^2 r_2 + ...\]
\(\gamma^i\)会越来越小，因此越后面的 R 权值越小。
当 MDP 确定后，每次决策时的状态、行为都是确定的，为了让 agent 在任意状态做出最佳的行为让状态尽量达到最好的情况（即获得最大的奖励值），需要确定一组策略，让整个过程的价值尽量最大化。
整个过程的期望记为：
\[E[r_0 + \gamma r_1+\gamma^2 r_2 + ...]\]
将策略记为\(\pi\)，规定了任意情况下的\(s \rightarrow a\)，因此可以记为：
\[a = \pi (s)\]
这个策略的价值函数（value function）记为
\[V^\pi(s)=E[r_0 + \gamma r_1+\gamma^2 r_2 + ...| r_0=R(s),\pi]\]
上式表示的是在起点为\(s\)、使用策略[latex]pi[/latex]的情况下的价值函数值。
状态值函数
策略评价
对上式变换：
\[V^\pi(s)=E[r_0 + \gamma r_1+\gamma^2 r_2+ ...| r_0=R(s),\pi]\]
\[V^pi(s_t)=E_\pi[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ...]\]
\[V^\pi(s_t) = E_\pi[r_t + \gamma V^\pi(s_{t+1})]\]
上式的\(s_{t+1}\)指的是\(s_t\)状态经过策略\(\pi\)之后到达的下一个状态。根据\(P_{s\pi(s)}\)对上式期望值进行展开，同时考虑在状态\(s_t\)下的所有策略动作情况：
\[V^\pi(s_t) = E_\pi[r_t + \gamma V^\pi(s_{t+1})]\]
\[=\sum_{s_{t+1}} P(s_{t+1}|s_t,\pi(s)) [R(s_t,\pi(s),s_{t+1}) + \gamma V^\pi(s_{t+1})] \]
上式中的\(P(s_{t+1}|s_t,\pi(s))\)指的是在\(s_t\)状态下进行策略\(\pi(s)\)到达状态 \(s_{t+1}\)的概率，\(R(s_t,\pi(s),s_{t+1})\)为从状态 \(s_t\) 转移到状态 \(s_{t+1}\) 的期望回报值（其实就是之前的\(s_t\)）。
根据贝尔曼最优化方程，有
\[V^*(s_t) = \max_a \sum_{s_{t+1}} P(s_{t+1}|s_t,pi(s)) [R(s_t,\pi(s),s_{t+1}) + \gamma V^*(s_{t+1})]\]
因此，对于任意一种策略\(\pi\)，我们都能通过这种方法对各个动作得到的价值函数值进行最大化迭代，逐渐逼近最大价值函数值。
\[ \text{input pi} \\ \text{While }\Delta < \theta \{\\ \text{tmp} = V(s)\\ V(s) = \max_a \sum_{s_{t+1}} P(s_{t+1}|s_t,\pi(s))[R(s_t,\pi(s),s_{t+1}) +\gamma V^*(s_{t+1})\\ \Delta = \max(\Delta,|V(s) - \text{tmp}|)\\ \} \\ \text{output } V(s) \approx V^\pi(s)\]
策略改进
假设有\(\pi\)与\(\pi_1\)两种策略，如果\(Q^\pi(s,\pi_1(s)) \geq V^\pi(s)\)（也就是\(V^\pi_1(s) \geq V^\pi\)），那么说明\(\pi_1\)的效果一定比\(\pi\)要好。
以此为依据，可以在每个状态 s 下对决策允许集进行遍历，计算所有决策会产生的价值函数值，根据贪心策略找到产生做大价值函数值的策略\(\pi^*\)，它即为效果最好的策略。
\[\pi_1 = \arg \max_a Q^\pi(s,a)\]
\[=\arg \max_a \sum_{s_{t+1}} P(s_{t+1}|s_t,a) [R(s_t,a,s_{t+1}) + \gamma V^*(s_{t+1})] \]
策略迭代
由上面的策略评价进行计算，能够得到当前策略下最大的价值函数值，接着使用策略改进，得到更好的策略\(\pi_1\)，再接着对这个\(\pi_1\)再次使用策略评估……这样一遍又一遍地迭代计算，最终能得到趋近最佳值的策略价值函数值与对应的策略。
值迭代
