强化学习-不确定情况下的决策—多臂老虎机问题
在这节课中，我们将要
- 使用 k 臂老虎机问题形式化不确定性下的决策问题
- 介绍基本概念：actions，rewards，values
为什么要用bandits（摇臂赌博机）
- 简化强化学习问题
- 没有序列决策，不包含状态
- 提供了对于基本概念的解释，例如exploration-exploitation
- 虽然在研究的角度来讲并不是很完美
多臂老虎机问题
我们在不同k actions或者arms中选择，
- 每个臂返回一个（随机）reward
- reward的分布对于每个臂是未知的
Action-Values 动作值
为了决定拉下某个臂，我们需要知道每个action的expected reward → 这就叫做action value function
我们的目标就是最大化expected reward
估计Action-Values
Action Values是未知的，我们需要估计。
Monte-Carlo 仿真：（the sample-average method）
我们总是可以对于样本的期望进行近似：
对于action-values：
增量更新-Incremental update rule：我们不需要存储所有收集到的奖励→
通用更新规则：
其中alpha = 1/n 是对于样本平均方法的
非稳态老虎机问题 Non-stationary bandit problem
针对于上一个标题继续，当步长恒定的时候，会发生什么？
在这种情况下，越旧的rewards对我们的估计有更小的影响。为了看到这一点，我们可以重新排列式子的顺序：
然后把方程展开：
得到：
也就是说，旧rewards会呈指数衰减-exponential decay
- 这种公式通常用于非稳态老虎机
- 每个臂的预期奖励都会发生漂移（例如季节性影响）
- 通常称为“moving”或“dynamic”averaging
Action Selection 动作选择
考虑以下在时间步t的估计值
Greedy action selection： 贪婪动作选择
贪婪动作是具有最高action-value估计的动作
举例：
Values是非常随机的：
- 噪声也融入了reward
- action selections的数量
→ 导致贪婪动作Greedy action会陷入局部最优解或者次优解sub-optimal policy中
Exploration-Exploitation Trade-off 探索-利用
Exploration: Improve knowledge for long-term benefit 提高知识以获得长期利益
Exploitation: Exploit knowledge for short-term benefit 利用知识获取短期利益
但是何时探索，何时利用？
基于不确定性的行动选择优于 epsilon-greedy
最终的 epsilon-greedy 策略将始终是次优的（因为探索）
随着时间的推移和手臂被尝试的次数增加，UCB策略的探索倾向会降低，系统会越来越多地倾向于利用已知的信息 - Exploration diminishes for UCB
