基本概念
强化学习
机器通过与环境交互来实现目标的一种计算方法。
决策任务往往涉及多轮交互，即序贯决策；而预测任务总是单轮的独立任务。如果决策也是单轮的，那么它可以转化为“判别最优动作”的预测任务
价值和奖励(Reward)
强化学习最基本的两个概念。对于一个Agent（强化学习的主体）来说，Reward是立刻获得的，内在的甚至与生俱来的。比如处于饥饿状态下，吃饭会有Reward。而Value是延迟的，需要计算和慎重考虑的。比如饥饿状态下去偷东西吃可以有Reward，但是从Value(价值观)的角度这(可能)并不是一个好的Action。
强化学习的本质就是通过与环境的互动来学习怎么达成一个目标。这个学习和做决策的主体就叫Agent。Agent交互的对象就是环境(Environment)
Agent会持续的和环境交互，根据当前的状态选择行为(Action)，而环境会给Agent新的状态和Reward。
与面向决策任务的智能体进行交互的环境是一个动态的随机过程，其未来状态的分布由当前状态和智能体决策的动作来共同决定，并且每一轮状态转移都伴随着两方面的随机性：一是智能体决策的动作的随机性，二是环境基于当前状态和智能体动作来采样下一刻状态的随机性
Agent和环境的交互假设是时刻t=0,1，…。在t时刻，Agent处于某个状态St∈S，这里S表示所有可能状态的集合，也就是状态空间。它可以选择一个行为At∈A(St)，其中A(St)是状态St时可以选择的所有行为的集合。选择了行为 At之后，环境会在下一个(t+1)时刻给Agent一个新的状态St+1和Reward Rt+1∈R⊆R。
在每个时刻t，Agent根据当前的状态St会选取不同的行为 At，选择的方法叫做策略(Policy)，一般假设是它一个概率分布（确定的策略是它的特殊情况）πt(At|St)，如果这个随机过程是平稳的(Stationary)，那么我们的策略也一般与时间无关的，即πt(At|St)=π(At|St)。策略有好有坏，Agent的目标是学习到最好的策略
每个时刻t，环境都会给Agent一个RewardRt，而Agent的目标(Goal)是最大化最终得到的所有Reward的和。这里隐含的意思是：我们的目标不是短期的Reward，而是长期Reward的累加。
从任务的初始状态到结束状态，我们称之为一个episode。比如下象棋，从开始下棋到最终分出胜负(或者和棋)一局游戏结束就叫一个episode。
由于未来的不确定性，我们一般会对未来的Reward进行打折(Discount)
Gt=Rt+1+γRt+2+γ2Rt+3+…=∑k=0∞γkRt+k+1
理想的，我们期望状态信号能够紧凑的压缩过去所有的信息，它能够保留所有相关的信息而尽量丢弃无关的信息。这通常要求状态不仅包含当前时刻的信号，还可能包含之前的一些信息，当然通常不需要所有过去的信息。如果一个状态信号包含了所有相关的信息，那么就叫它具有马尔科夫属性(Markov Property)。比如下象棋，当前的局面（包括所有棋子的位置和谁走下一步棋）包含了所有的信息。不管是先走车再走马还是先走马再走车，总之它们到达了相同的局面。因此通常马尔科夫属性通常与具体的“路径”无关。
行为策略 是用来与环境互动产生数据的策略，即在训练过程中做决策
目标策略 在行为策略产生的数据中不断学习、优化，即学习训练完毕后拿去应用的策略
为了解决强化学习中的exploitation(利用)和exploration（探索），利用（行为策略）保持探索性，提供多样化的数据，不断优化另一个策略（目标策略）
on-policy 的目标策略和行为策略是同一个策略，简单粗暴，但只是局部最优
off-policy 的目标策略和行为策略分开可以保持探索的同时求全局最优值，难点在于如何在一个策略产生的数据优化另一个策略
On-policy-与Off-policy的区别在于：更新价值所使用的方法是沿着既定的策略（on-policy）抑或是新策略（off-policy）
算法
时序差分算法
时序差分学习可以直接从与环境互动的经验中学习策略，无需构建关于环境动态特性的模型，也就是常说的model-free方法。像上文的动态规划方法就需要已知环境的动态特性，属于model-based方法。
时序差分学习利用经验来解决预测。也就是说需要根据给定策略学习来的一些经验数据，来对状态价值函数 VπV_{pi}Vπ 进行更新。
Q-learning和SARSA都是基于时序差分的算法
Q-learning
基于价值的经典算法，通过维护Q-table记录状态在不同动作下的期望收益，不断训练迭代 off-policy。
采用下一个状态的数据进行学习
Q(s,a)←Q(s,a)+α[r+γa′maxQ(s′,a′)−Q(s,a)]
缺点 只适合状态和动作空间不大的空间
怎么迭代 行动策略是e-greedy策略，更新Q表的策略是贪婪策略
应用
SARSA
基于价值的经典算法，通过维护Q-table记录状态在不同动作下的期望收益，不断训练迭代 on-policy。
怎么迭代 行动策略是e-greedy策略，目标策略也是e-greedy
Q(s,a)←Q(s,a)+α[r+γQ(s′,a′)−Q(s,a)]
总结
Q-table的更新不止一轮，比如下象棋是需要很多轮的更新，每轮直到赢输或者和棋为止。对于Q-learning来说，先根据e-greedy选择动作到下一状态，然后下一状态所有可能的动作中价值最大的那个用来更新上一状态的价值函数，但是并不一定就接着走那一步，而是接着依据e-greedy进行。
而SARSA算法 则不然，它只会依据下一状态选择的动作更新上一状态的价值函数，这就是关键的区别。
