Contents：

1. Introduction

2. Multi-Armed Bandits

3. Contextual Bandits

4. MDPs

探索与利用

1. 探索和利用是一对矛盾, 探索尝试不同的行为继而收获更多的信息，可能会牺牲一些短期利益,利用则是做出当前信息下的最佳决定. 

2. 探索种类

- 行为空间的探索，依据每一个状态，以一定的算法尝试之前该状态下没有尝试过的行为

- 参数化探索， 针对参数化的策略函数，表现为尝试不同的参数设置，进而得到具体的行为.

3. 探索的原则：

探索原则

多臂赌博机

1. Regret ：

Regret 函数

2.  Regret 收敛：

- Greedy 算法总是选取具有最高价值函数的action. 

- -greedy 算法： 以 1- 的概率选择 a = argmax（a）， 以 概率随机选择任意一个action.

- decaying -greedy 算法：随着时间的推移，采用随机行为的概率越来越小. 

不同探索程度贪婪策略的总后悔值

常用的探索方法

1. Decaying -greedy 贪婪搜索：

注明：d 是次优行为与最优行为价值之间的相对差距. 

2. 不确定行为优先探索：

- 当个体不清楚一个行为的价值时，个体有较高的概率选择该行为, 具体在实现时可以使用乐观初始估计， 可信区间上限以及概率匹配三种形式.

-乐观初始估计：乐观初始估计给行为空间中的每一个行为在初始时赋予一个足够高的价值, 在选择行为时完全使用完全贪婪的探索方法. 使用递增式的蒙特卡洛评估来更新这个价值：

初始行为价值通常为：

- 置信区间上限：一般来说，差距越大后悔值越大，奖励分布的相似程度越高，后悔值越低.

- Lower Bound 定理：

- Hoeffding's Inequality定理 （Hoeffding 不等式）：

UCB1：

UCB1 算法

贝叶斯Bandits：Bayesian bandits 利用先验知识来探索得到rewards.

3. 概率匹配

- 通过个体与环境的实际交互的历史信息ht 估计行为空间中的每一个行为是最优行为的概率,然后根据这个概率来采样后续行为。

- Thompson Sampling：

基于信息价值的探索

1.