coursera by University of Alberta
Fundamentals of Reinforcement Learning
Week 1
1、action value
2、Sample-Average Method
由于 q*(a) 是如何分布的，事先并不知道，因此需要进行估计
Sample-Average Method 样本平均法是一种估计方法
其中，对每一种行动 a 有一个估计
当每次都选择最大估计值的行动的时候就为贪婪算法，即开发 exploit
non-greedy action : explore
greedy action : exploit
agent 不能同时选择 explore & exploit
3、Incremental update rule
在每次 Sample-Average Method 的时候，都需要对所有的奖励进行相加求和除以行动的次数，随着 agent 的行动越来越多，需要储存的奖励也越来越多，为了将算法的空间复杂度控制在常数范围内，提出了增量更新规则，进行迭代计算，不需要存储每次行动的奖励
改进：
当奖励的分布随着时间变化的时候 ( distribution of rewards changes with time ) ，就不能直接用 Incremental update rule 的公式，原因是在公式
中，奖励 Rn 会随着 n 的增大而减小其对 Q 值的贡献，换句话说，初始值对 Q 影响最大，越往后对 Q 值影响越小。若 Q 值在后面的时间当中，随着时间的增大而改变，那么 Rn 对 Q 值的影响也越大才符合实际，为了解决这个问题，提出了公式
其中， αn 是一个常数，不随时间的改变而改变，那么最近的奖励贡献最大，最初的奖励贡献最小
4、 Epsilon-Greedy action selection
exploration : improve knowledge for long-term benefit 探索哪种行动回报最多
exploitation : improve knowledge for short-term benefit 采取当前回报最多的行动
Epsilon-Greedy action selection
为了平衡探索和开发，采取在选择行动的时候以一定的概率来进行探索，其余的时候进行开发
5、 Optimistic Initial Values 乐观初始值
Optimistic Initial Values 指的是将估计值 q 初始值设置为比所有 reward 都要高，这样在 agent 初始阶段就会自动进行探索，随着不断地探索，估计值 q 也会不断地下降，下降到一定程度地时候 agent 就会停止探索，因此，它不适用于 q 值变化的情况
6、 Upper-Confidence Bound (UCB) Action Selection
在 Epsilon-Greedy action selection 中，对每种行动奖励的探索是均匀分布的，有时候并不符合实际，为了达到更好的探索的效果，提出了 UCB 方法
Qt(a) : exploitation 开发，指当前奖励最多的行动
c : 常数
t : agent 总步数
Nt(a) : 行动 a 所采取的总步数
在 UCB 方法中如果某一种行动执行比例远小于其他行动，那么将会执行该行动
Week 2
Markov Decision Processes
1、
马尔可夫性质：未来的状态和奖励只与当前的状态和行动有关，与之前的状态无关
2、智能体的目标
智能体 agent 的目标是最大化未来奖励的均值
3、Continuing Tasks 持续性任务
引入 discount rate 来解决持续性任务无限求和的问题
阶段性任务和持续性任务区别
持续性任务的目标函数
γ→0：只关心下一个时间戳的奖励
γ→1：关心以后时间戳的奖励
公式的递归形式
week 3
Value Functions & Bellman Equations
1、deterministic policy & stochastic policy
deterministic policy : 确定性政策，指的是每个状态 state 对应一个行为 action ， 一个 action 可以对应多个 state
stochastic policy：随机政策，指的是对于一个状态 state 对应行为 action 的分布函数 Π(a|s)
valid & invalid policies
在 MDP 当中，所选的政策 policy 只由之前的状态 state 决定，而不由其他因素决定，若 policy 受之前 action 的影响，则应将之前的 action 添加到 state 当中
2、state-value function & action-value function
Π：policy
S：state
R：reward
3、Bellman Equation
4、Bellman Equation 应用举例
规则：来到 state B 获得 5 分，其他情况 0 分，碰壁后 state 不变
策略 policy 是在四个方向上随机移动
从第一个公式到第二个公式能省略 p(s',r|s,a) 是因为在确定的 state 当中，每个 action 只能通向下一个确定的 state 以及 reward ，不存在某个 action 会通向不同的 state 的情况 ； 从第二个公式到第三个公式是指，在当前 state A ，使用各个 action 的情况
将各个 state 的 Bellman Equation 列出，构成线性方程组，即可解除各个 state 的 value function
这种直接解方程的方法在方程组较小的时候适用，在方程很大的时候不适用
5、optimal policy
optimal policy Π* ：指的是在任何一个 state ，Π* 的值都大于等于其他 Π 的值；在所有 policy 当中，必定存在至少一个 optimal deterministic policy ，但也可能不只一个
每个 optimal policy 对应同一个 optimal value funciton
当 policy 比较少的时候，可以使用蛮力搜索计算每个 policy 的 value ，但是当 policy 很多的时候，蛮力搜索方法不适用
当采取 optimal policy Π* 的时候，在每个 state 选择值最高的 action ，即将值最高 action 概率赋值为 1 ，其他 action 概率赋值为 0 ，从第一个公式到第二个公式
当采取 optimal policy Π* 的时候，得到 optimal action-value function
不能使用线性代数来直接解出 optimal value function 因为 max 是非线性的
6、Using Optimal Value Functions to Get Optimal Policies
从 optimal value function 到 optimal policy 是相对容易的，因此一般认为解 optimal value funciton 与 解 optimal policy 等价
v(s)：指的是对于确定的 state s ，计算每个 action a 的 value ，将最大值 value 作为 optimal value ，对应 action a 作为 Π(s) optimal action
如果有 optimal state value function ，则可以直接根据 optimal state action paire 得到 optimal action
week 4
Dynamic Programming
1、Policy Evaluation vs. Control
policy evaluation：根据当前 Π 计算出最优 VΠ
policy control：更新当前 Π 到在 当前 V 的情况下最优
2、Iterative Policy Evaluation
目的是更新 V ，将 V 在当前 Π 情况下更新为最优
方法是迭代更新，当更新到对于每个 state ， v(s) 都没有发生变化的时候，即 Vk(s)=Vk+1(s) ，则更新完成
可以使用两个 array 来存储每个 state 的值，得到新值 V' 后更新旧值 V；也可以使用一个 array 来实现，用刚刚更新的值来计算下一个要更新的值，一般这种方法更快一点
sweep：指的是对所有 state 的值都更新一遍
3、Policy Improvement
目的是根据 VΠ 来更新 Π
当在 VΠ 的情况下，使用贪婪算法获得新的 Π ，若新的 Π 与旧的 Π 一致，则 Π 已经是最优解，若新的 Π 与旧的 Π 不一致，则新的 Π ＞ 旧的 Π
策略提升理论：更新的 Π ≥ 旧的 Π
4、Policy Iteration
evaluation 和 improvement 交替进行，使 Π 和 V 朝着最优解的方向前进
5、Generalized Policy Iteration
将 evaluation 和 improvement 合并
6、synchronous & asynchronous 同步和异步
synchronous：指的是对 state-value function 更新的时候，对每个 state 按顺序遍历更新，即 sweep
asynchronous：当 state 数量很大的时候，对所有 state 遍历更新并不实际，因此，对随机 state 进行更新，也可以对重点 state 进行更新
7、Efficiency of Dynamic Programming
Monte Carlo method ：将每个 state 进行独立地估计，对同一个 state 收集大量的在同一个 Π 情况下的 reward ，取其平均值，使其收敛于 state value ，但是，这种方法计算量大
Dynamic Programming：不将每个 state 当成独立的问题，可以利用下一步 state 的值来估计当前 state 的值，称为 Bootstrapping
Brute-Force Search ：指的是使用蛮力法，穷举所有的 policy ，对每个 policy 计算其 value ，取出值最大的 policy ，但是，其复杂度呈指数级增长，计算量大
