---

强烈推荐结合《Reinforcement Learning：An Introduction》Second edition阅读！！！

---

Multi-armed Bandits

2.1 A k-armed Bandit Problem

想象一台老虎机，有k个拉杆（即k个action），每个拉杆动作后会产生reward。假设这些遵循某一概率分布，而不是固定值。所以估计reward的期望是很有必要的。因为当游戏的次数足够多时，reward的期望意味着执行这个action会获得的平均reward，这可以用于指导agent做决策policy。

2.2 Action-value Methods

该算法通过计算某个action获得所有reward的平均值来估计期望。决策使用贪心算法，也就是从已知的action中找到reward最大的。这种方法很稳健，但不去尝试新的方法（exploration），总是利用（exploitation）现有的知识决策，基本上不能获得高收益，就像理财。所以引入概率因子epislon，用于启发式的尝试non-greedy action，毕竟高风险高回报嘛，这就是epislon-greedy methods。

2.3 The 10-armed Testbed（例子）

2.4 Incremental Implementation

显然action-value methods每次计算均值时需要用到所有的回报Ri，不仅占内存，也消耗时间。

eq2.3.png

改写公式2.1得到式2.3，如上图所示。这样只需要维护三个数OldEstimate、StepSize、Target就可以计算新均值NewEstimate进行更新迭代。

2.5 Tracking a Nonstationary Problem

本节针对现实场景中reward分布常是动态的情况进行算法优化。对比上图中因子1/n并改为alpha，如下图所示。发现这样优化算法后，其实初始价值Q1随着训练次数增多的影响力（权重）逐渐减小，而越新的奖励Ri影响越大。

eq2.6.png
因权重成指数衰减，故称为exponential recency-weighted average。

2.6 Optimistic Initial Values

由式（2.6）可见，初始价值对后续的价值计算有影响。若初始值相对奖励值较大，且初始值相同则action的选择将更接近随机选择，有利于尝试新的动作（exploration）。

2.7 Upper-Confidence-Bound Action Selection

epislon-greedy算法的启发式搜索过于随机，甚至采用greedy action的概率相对non-greedy action还高一点。为了鼓励agent采用那些极少用的action以期待获得高汇报，引入公式（2.10）

eq2_10.png

显然Nt(a)越小，价值增幅越大。但文章又说该UCB方法不实用：1、难以应对动态奖励问题；2、难以应对海量状态空间。（第二个问题没太能体会到）

2.8 Gradient Bandit Algorithms

逻辑：（可能理解有误，欢迎指正。）agent执行action获得reward，并估计value用于决策。本节提出的Ht(a)类似（但并不是）之前出现的价值Qt(a)，并通过soft-max来计算执行各个行为的概率。
Ht(a)的迭代更新是基于梯度上升（和梯度下降一个意思，符号增量的符号换一换），后文有具体推导过程。

2.9 Associative Search (Contextual Bandits)

本章了解即可，介绍了现实中交互任务往往较为复杂，可以当作是多个k-armed bandit task复合而成。前述的算法难以应对这样的任务。