第二章 多臂老虎机
试错型学习（trial-and-error learning）：
是一种通过不断尝试不同的行为或动作，逐步找到能实现目标的最佳解决方案的学习过程。它的核心思想是通过反复进行尝试，在每次尝试后根据反馈（例如奖励或惩罚）进行调整，从而逐步优化行为。
在强化学习中，试错型学习是其基本机制之一。智能体在环境中进行动作，每次动作都会获得一个反馈信号（即奖励或惩罚），智能体通过这些反馈信号更新自己的策略，以期在未来的行为中最大化累积奖励。
试错型学习的几个关键特点：
- 探索与利用（Exploration and Exploitation）：智能体既需要探索新的行为以寻找更好的解决方案，也需要利用已经学到的知识来获得更高的即时奖励。
- 反馈机制：通过环境的反馈，智能体逐渐学习哪些行为是有益的，哪些行为需要避免。
- 延迟奖励：智能体在试错过程中可能无法立即看到行为的结果，而是需要依靠长远的奖励信号进行决策。
一个典型的例子是迷宫中的老鼠实验：老鼠会尝试不同的路径，遇到死胡同时就会选择其他路径，最终通过不断试错，找到通向食物的正确路径。
在机器学习中，强化学习算法如Q-learning和深度Q网络（DQN）都属于基于试错型学习的框架。
问题定义
多臂老虎机：简化版的强化学习问题，不存在状态信息，只有动作和奖励。
问题：
有一个拥有 K K K根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的概率分布 R R R。我们每次拉动其中一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励 r r r。
我们在各根拉杆的奖励概率分布未知的情况下，从头开始尝试，目标是在操作 T T T次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布是未知的，因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。
“采用怎样的操作策略才能使获得的累积奖励最高”便是多臂老虎机问题。
形式化描述问题：
< A , R \mathcal{A}, \mathcal{R} A,R>:
- A \mathcal{A} A：动作集合，一个动作表示拉动老虎机的一个拉杆，动作空间：{ a 1 , a 2 , . . . , a K a_1, a_2, ..., a_K a1,a2,...,aK}。 a t ∈ A a_t \in \mathcal{A} at∈A：表示任意一个动作。
- R \mathcal{R} R：奖励概率分布，老虎机的每一个拉杆都对应一个奖励概率分布 R ( r ∣ a ) \mathcal{R}(r|a) R(r∣a)，不同拉杆的概率分布不同。
假设每个时间步拉动一个拉杆，多臂老虎机的目标为： m a x ∑ t = 1 T r t , r t ∼ R ( ⋅ ∣ a t ) max \sum_{t=1}^Tr_t, r_t \sim \mathcal{R}(\cdot|a_t) max∑t=1Trt,rt∼R(⋅∣at)。
每个动作 a a a的期望奖励： Q ( a ) = E r ∼ R ( ⋅ ∣ a ) [ r ] Q(a)=\mathbb{E}_{r \sim \mathcal{R(\cdot|a)}}[r] Q(a)=Er∼R(⋅∣a)[r]。
最优期望奖励： Q ∗ = m a x a ∈ A Q ( a ) Q^* = max_{a\in\mathcal{A}}Q(a) Q∗=maxa∈AQ(a)。
懊悔（regret）： R ( a ) = Q ∗ − Q ( a ) R(a)=Q^*-Q(a) R(a)=Q∗−Q(a)，即拉动当前杆的动作 a a a与最优拉杆的期望值差异。
累积懊悔（cumulative regret）： σ R = ∑ t = 1 T R ( a t ) \sigma_R=\sum_{t=1}^TR(a_t) σR=∑t=1TR(at)。
目标：最大化累积奖励，也就等于最小化累积懊悔。
估计期望奖励的算法：
注意：计数器 N N N是一个列表，其中每个拉杆都有一个数值： N = [ N 1 , N 2 , … , N K ] N=[N_1, N_2, \dots, N_K] N=[N1,N2,…,NK]；
相应的，期望奖励估值 Q ^ \hat{Q} Q^也是一个列表： Q ^ = [ Q ^ ( a 1 ) , Q ^ ( a 2 ) , … , Q ^ ( a K ) ] \hat{Q} = [\hat{Q}(a_1), \hat{Q}(a_2), \dots, \hat{Q}(a_K)] Q^=[Q^(a1),Q^(a2),…,Q^(aK)]。
设计策略
探索与利用
- 探索（exploration） 是指尝试拉动更多可能的拉杆，这根拉杆不一定会获得最大的奖励，但这种方案能够摸清楚所有拉杆的获奖情况。
- 利用（exploitation） 是指拉动已知期望奖励最大的那根拉杆，由于已知的信息仅仅来自有限次的交互观测，所以当前的最优拉杆不一定是全局最优的。
设计策略时需要平衡探索和利用的次数，使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索，在对每根拉杆都有比较准确的估计后，再进行利用。目前已有一些比较经典的算法来解决这个问题，例如 ϵ \epsilon ϵ-贪婪算法 、上置信界算法和汤普森采样算法等。
ϵ \epsilon ϵ-贪婪算法
每次以概率 1 − ϵ 1-\epsilon 1−ϵ选择以往经验中期望奖励估值最大的那根拉杆（利用），以概率 ϵ \epsilon ϵ随机选择一根拉杆（探索）：
上置信界（upper confidence bound，UCB）算法
了解即可。
汤普森采样（Thompson sampling）
了解即可。
总结： ϵ \epsilon ϵ -贪婪算法的累积懊悔是随时间线性增长的，而另外 3 种算法（ ϵ \epsilon ϵ-衰减贪婪算法、上置信界算法、汤普森采样算法）的累积懊悔都是随时间次线性增长的（具体为对数形式增长）。
参考：
链接: 《动手学强化学习》（第二章）
